Уравнения (18) имеют так называемую трехточечную структуру. Такие системы имеют следующий вид:
(23)
y0=0, yn=0 (24)
соответствует системе линейных уравнений с трехдиагональной матрицей Т для определения вектора неизвестных у =(у1, у2, …, уп-1):
Ту=F,
где
(25)
При этом легко видеть, что в нашем случае
(26)
поскольку
(27)
решение таких систем эффективно решается с помощью методов прогонки.
Пример.
Для функции y=f(x)=3x на отрезке [-1; 1] с узлами интерполяции х0=-1, х1=0, х2=1. Построить кубический сплайн.
Найти его значение при х=1/2 (т.е. приближенно ). Определить погрешность сплайна.
Решение. В данном случае имеем равномерную сетку с шагом h=1. на сетке одна внутренняя точка – х1 и две граничные: х0 и х2. система (20) сводится к одному уравнению относительно коэффициента с1, которое с учетом дополнительных соотношений (16), определяющих нулевые значения коэффициентов с0 и с2, принимает вид:
таким образом, с0=0, с1=2 и с2=0. Остальные коэффициенты сплайна определим из формул (7), (21), (22): а1=1, а2=3, d1=2, d2=-2, b1=4/3, b2=7/3.
Теперь можно выписать кубические полиномы, определяющие сплайн:
Легко проверить, что построенная таким образом функция S(x) непрерывна вместе с первой и второй производной во внутренней узловой точке х=0.
Вычислим значение сплайна в точке х=1/2, т.е посчитаем приближенное значение :
Значительная погрешность обусловлена, прежде всего, большим шагом h=1. определенную роль играют условия (4):
(*).
Вторая производная рассматриваемой функции f(x)=3x в точках х=±1 в ноль не обращается, т.е. условие (*) дает о ней искаженную информацию. Если при построении сплайна учесть истинные значения вторых производных в граничных точках, то точность аппроксимации улучшится.
Техническим аналогом булевой функции в вычислительной технике является так называемая комбинационная схема, на вход которой поступают и с выхода снимаются электрические сигналы в виде одного из уровней напряжения, соответствующих значениям логического 0 и логической 1.
Для выяснения, что же такое комбинационная схема, рассмотрим схему, имеющую m входов и n выходов. На её входы могут быть поданы наборы значений входных переменных Xi {0,1}, i=1,m, а на выходах формируются выходные переменные Yj {0,1},j=1,n.
Схема называется комбинационной, если каждую из n функций её выходов Y1,Y2,...,Yn можно представить как булеву функцию входных переменных X1,X2,...,Xm, причем значения выходных сигналов в любой момент времени однозначно определяются комбинацией входных сигналов в тот же момент времени.
Комбинационная схема описывается с помощью системы уравнений.
Y1=F1(X1,X2,...,X1)
Y2=F2(X1,X2,...,X2)
...................
Yn=Fn(X1,X2,...,Xm)
Структурно комбинационная схема может быть представлена как совокупность элементарных логических схем – логических элементов (ЛЭ). ЛЭ выполняют над входными переменными элементарные логические операции типа И-НЕ, И, ИЛИ, ИЛИ-НЕ и т.д.
В таблице3 лекции №8 некоторым из элементарных функций поставлены в соответствие логические элементы.
Число входов логического элемента соответствует числу аргументов воспроизводимой им булевой функции. Графическое изображение комбинационной схемы, при котором показаны связи между различными элементами, а сами элементы представлены условными
обозначениями, называется ф у н к ц и о н а л ь н о й схемой.
З а д а ч а с и н т е з азаключается в построении из заданного набора логических элементов комбинационной схемы, реализующей заданную систему булевых функций.
Решение задачи синтеза не является однозначным, можно предложить различные варианты комбинационных схем, реализующих одну и ту же систему булевых функций, но отличающихся по тем или иным параметрам. Разработчик комбинационных схем из этого множества вариантов выбирает один, исходя из дополнительных критериев: минимального количества логических элементов, необходимых для реализации схемы, максимального быстродействия и т.д. Существуют различные методы синтеза комбинационных схем, среди которых наиболее разработан канонический метод.
При каноническом методе предполагается, что каждая выходная функция реализуется своей схемой, совокупность которых и даёт требуемую КС. Поэтому синтез сложной КС с n выходами заменяется синтезом n схем с одним выходом.
Согласно каноническому методу синтез КС включает в себя ряд этапов.
1. Работа проектируемого логического устройства описывается сначала словесно, затем в виде таблицы истинности.
2. На основе таблицы истинности создается математическое описание ФАЛ
в виде СДНФ.
3.С использованием методов минимизации определяется минимальная ДНФ (МДНФ) или минимальная КНФ (МКНФ). Из полученных двух минимальных форм выбирается более простая.
4.Булеву функцию в минимальной форме согласно п.3 представляют в заданном (или выбранном разработчиком) базисе .
5.По представлению функции в заданном базисе строят комбинационную схему.
Пример №1.
Синтезировать схему, заданную таблицей истинности (табл.2) в базисе И, ИЛИ, НЕТ.
Табл.2
Х1
Х2
Х3
У
Так как единиц в столбце функции меньше чем нулей, то СДНФ будет проще, чем СКНФ.
Создаем СДНФ: У = х1х2х3+х1х2х3+х1х2х3
Ввиду простоты выражения минимизируем без карт Карно, используя правило дополнения (х2+ х2=1): У = х1х2х3+х1х3(х2+х2) = х1х2х3+х1х3.
Наконец, синтезируем схему в заданном базисе (см.рис.1)
Пример №2
Синтезировать схему, которая реализует следующую ФАЛ:
У = х3х4+х1х2х4+х1х2х4+х1х2х3+х1х3х4.
Дополняем исходную ФАЛ до СДНФ, добавляя в каждое слагаемое отсутствующие аргументы (используя правило дополнения):
(23)
(25)
(26)
(27)
). Определить погрешность сплайна.
:
(*).
00
11
1
1
1
Рис.3.
У = (х3+х4)+(х1+х2+х3)+(х1+х2+х3). Реализация ФАЛ в электронном изделии будет иметь вид, изображенный на рис.5
x1 + x2 + x3 Рис.5.