ЛЕКЦИЯ №5
МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
СНУ
Пусть дана система вида:
(5.1)
f'(x)= - производная
Частная производная - вектор (все значения).
МЕТОД НЬЮТОНА
Дана система вида (5.1), где fi
один раз непрерывно дифиринцируемые функции, т.е. существуют все частные первые производные этих функций.
Строим последовательность приближений сходящуюся к точному решению системы .
Пусть - некоторое начальное приближение к решению, а - катое приближение к решению. Построим зависимость, позволяющую на основании построить .
Точное приближение
ξ-корень обращает уравнение в верное равенство(тождество).
(5.2)
Разложим функции fi
из системы (5.2) в ряд Тейлора в окрестности точки хк
до линейных составляющих.
(5.3)
Система (5.3) представляет собой систему линейных алгебраических уравнений для поиска компонента вектора поправки hk
.
Перепишем систему (5.3) в виде:
(5.4)
Сокращаем запись системы (5.4) : (5.5)
Решим систему (5.5) методом обратной матрицы. Определитель Якобиана в точке хк
не равен 0.
Получили связь последующего приближения с предыдущим.
(5.6)
условие окончания вычислений. (5.7)
- расстояние между векторами (метрика).
МЕТОД ИТЕРАЦИЙ
Пусть дана система вида (5.1). Преобразуем ее к виду (5.8)
Система (5.8) в векторном виде (5.9)
Необходимо найти неподвижную точку систему
Очевидно, что эта точка ξ – решение системы (5.1)
Пусть дано -некоторое начальное приближение к ξ и на k-том шаге получено приближение . Тогда последующее приближение :
(5.10)
Условие окончания совпадает с (5.7)
Всегда ли метод сходится?
Пусть М- матрица, составлена из элементов mij
M=[mij
], где mij
=
Определение нормы матрицы А: -число удовлетворяющее свойствам.
1) ≥0, =0≡0
2) число
3)
4)
Способы задания нормы матрицы:
1) =
2) =
3) =
Достаточное условие сходимости метода итераций:
Если , i=1,n , на Сч и Сч, то процесс итераций сходится независимо от выбора начального приближения.
МЕТОД ЗЕЙДЕЛЯ
Пусть дана система вида (5.1), преобразуем ее к виду (5.8). Как и в методе итераций строим последовательность приближений к неподвижной точке.
ускорение сходимости за счет подстановки предыдущего приближения.
Достаточное условие совпадает с достаточными условиями сходимости метода итераций.
Условие окончания получения приближений совпадает с (5.7).
ЛЕКЦИЯ № 6, 7
ПРИБЛИЖЕНИЕ ФУНКЦИИ
Общая постановка задачи.
Пусть ¦(c) – некоторая функция, которая можетбыть известно, частично известной и неизвестной. Эту функцию необходимо заменить некоторой «хорошей» функцией j(c), которая будет достаточно близкой ¦(c).
Постановка задачи интерполяции.
Для того чтобы конкретизировать постановку задачи приближения функции необходимо ответить на следующие вопросы:
1. что известно о ¦(c) (способ задания, степень гладкости);
2. к какому классу, семейству функций должна принадлежать j(c);
3. что понимаем под близостью j(c) и ¦(c) каков критерий согласия;
Часто приближение функции называют аппроксимацией
Постановка задачи интерполяции.
Пусть ¦(c) задана на некотором разбиении отрезка [a;b] точками хi
,
i=0,n , где a = х0
<х1
<…<xn
= b
интерполяция
– вычисление ¦(c) в точке Î[a;b], x¹xi
, i = 0,n
экстраполяция
– вычисление функции ¦(c) в точке ХÎ[a;b];
Определение интерполяции ввел в 1656 году Джон Уолесс, а в 1655 году ввел символ ¥.
Для полиномиальной интерполяции j(c) имеет вид j(c)=а0
+а1
х+а2
х2
+…+аn
xn
.
Для того, чтобы считать j(c) к ¦(c) вводится ограничение j(ci
)= ¦(ci
), i=0,n ;
Т.е значения этих функций в точке хi
должны совпадать. Точки х
i
будем называть узлами интерполяции
Интерполяционный многочлен Лагранжа
Необходимо определить коэффициенты полинома степени n(их будет n+1), построения аппроксимации функции, заданной в n+1 узле. Используя ограничения на j(c): j(ci
)= ¦(ci
)=y, i=0,n , составим систему:
(6.
1)
Выпишем определитель этой системы
Определитель
Вандермонда
При условии: x0
¹xj
приi¹j определитель системы (6.1) отличен от нуля, следовательно, система имеет единственное решение.
Вывод:
если задано разбиение в виде n+1различной точки, то всегда существует функция в виде полинома n-ой степени, которая проходит через все точки графика ¦(c),определенной на этом разбиении.
Посторонние приближенияфункции при помощи полиномов указанным способом весьма трудоемко и обладает большой вычислительной погрешностью, поэтому его использование для большого числа узлов интерполяции нецелесообразно.
Лагранж предложил строить интерполяционные полиномы в виде:
Pn
(x)=∑ Ci
li
(x) (6.2)
Ci
=
yi
=
¦(ci
), li
(x)=полиномы n-ой степени, которые удовлетворяют условию:
Для полинома узлы интерполяции xj
, j=0,n , j≠I являются корнями, причем действительными и попарно различными (все имеют кратность 1)
Тогда полином li
может быть записан в виде:
(6.3)
Общий вид полинома Лагранжа:
(6.4)
Встает вопрос о точности, о приближения функции. Вводится понятие остаточного члена многочлена Лагранжа ; для того, чтобы оценить аппроксимации ¦(c) в некоторой точке xÎ[a;b]
Функцию ¦(c) представим в виде ¦(c)= Pn
(x)+Rn
(x), где Rn
(x)- остаточный член многочлена Лагранжа в процессе длительного и трудоемкого вывода для Rn
(x) получена следующая формула:
(6.5)
Строится система вложенных отрезков
¦(
n
+1)
-производная (n+1)-го порядка
Пусть
(6.6)
Если ¦(c)-полином n-ой степени, то производная (n+1)-го порядка равна 0, тогда Rn
(x)≡0 и мы получаем точную аппроксимацию.
Теорема:
Многочлен Лагранжа вида (6.4) для таблично заданной функции единственен.
Доказательство:
Пусть Qn
(x)- многочлен Лагранжа, построенный для этой же функции ¦(c) по тем же узлам интерполяции. Qn
(x)¹Pn
(x) Qn
(xi
)=yi
=Pn
(xi
),
Рассмотрим многочлен Ln
(x)= Qn
(x)-Rn
(x)-это многочлен n-ой степени, для которого точки xi
, i=0,n являются корнями. Это противоречит основной теореме алгебры, которая говорит о том, что полином n-ой степени имеет ровно n корней . А Ln
(x) имеет n+1 корней . Противоречие доказывает теорему.
Интерполяционная схема Эйткина
Поскольку при большом числе узлов интерполяции вычисление значения полинома Лагранжа по формуле (6.4) громоздко, необходимо получить рекуррентную формулу.
Пусть ¦(c)- непрерывна, узлы выбраны на отрезке [a;b] таким образом, что:
Введем функцию
xi
-узлы интерполяции;
yi=
¦(c)
Полином Лагранжа: Pn
(x) см. (6.4)
Таким образом, функция Q0,1
(x) представляет собой полином Лагранжа l-ой степени, построенной по узлам x0
,x1
введем функцию вида
Функция Q1,2
(x)- интерполяционный полином Лагранжа, построенный по узлам x1
,x2
.
Введем теперь функцию
Аналогично:
Q0,1,2
(x2
)= у2
В силу единственности полинома Лагранжа, построенного по узлам x0
, x1
,x2
функция Q0,1,2
(x) представляет собой интерполяционный полином Лагранжа 2-ой степени, построенный по узлам x0
, x1
,x2
.
Введем функцию:
(7.1)
Функция представляющая собой полином Лагранжа 2-ой степени, построенного по узлам x0
, x1,…
xi
.
Формула (7.1) позволяет рекуррентно вычислять полином Лагранжа любой степени.
Т.к. (7.1) представляет собой альтернативную форму записи интерполяционного полинома, точность пр
(7.1)-интерполяционная схема Эйткина.
КОНЕЧНЫЕ РАЗНОСТИ
Пусть функция ¦(c) задана на системе равноотстоящих узлов xi
=x0
+ih,
где h-шаг сетки, yi
=¦(ci
).
Конечной разностью первого порядка в точке x0
называется ∆y0
=y1
-y0
Конечной разностью первого порядка в точке xi
: ∆yi
=yi
+1
-y0
-yi
Конечной разностью второго порядка в точке x0
: ∆2
y0
=∆y1
-∆y0
Конечной разностью второго порядка в точке xi
: ∆2
yi
=∆yi
+1
-∆yi
Общая формула для конечной разности k-того порядка в точке xi
:
∆
k
yi
=∆
k
-1
yi
+1
-∆
k
y
(7.2)
Заметим: ∆0
yi
=
yi
Формула (7.2) позволяет вычислять рекуррентно конечные разности
Связь конечных разностей и производных
чем меньше h, тем точность выше
Аналогично можем получить связь
;
(7.3)
Свойства конечных разностей
В связи с производными вида(7.3)конечные разности обладают свойствами:
1. постоянные, равны нулю;
2. постоянный множитель у функции выносится за знак
3. суммы 2-х функций равны сумме каждой функции
4. полинома n-ой степени, n-го порядка постоянны и равны
∆n
y=hn
an
n!
an
-коэффициент при xn
полинома Rn
(x)
Верно и обратное утверждение: все конечные разности n-го порядка некоторой функции постоянны и одинаковы, конечные разности n +1-го порядка равны 0, а конечные разности n-1-го порядка различны, то функция представляет собой полином n-ой степени.
Распространение ошибки в исходных данных
при вычислении конечные разности
Любые измерения несут в себе погрешность (ошибка округления, точность измерения приборов)
Пусть значения функции определены в узлах x0
, и в некоторой точке xk
значение некоторой точке xk
значение функции найдено с ошибкой ε, т.е ỹk
+ ε
Составим таблицу конечных разностей
xk
-2
yk
-2
∆yk
-2
∆2
yk
-2
∆3
yk
-3
+ε
xk
-1
yk
-1
∆yk
-1
+ε∆2
yk
-2
+ε∆3
yk
-2
-3ε
xk
yk
+ε ∆yk
-1
-ε∆2
yk
-1
-2ε∆3
yk
-1
+3ε
xk
+1
yk
+1
∆yk
+1
∆2
yk
+ε ∆3
yk
-ε
xk
+2
yk
+2
∆2
yk
+1
Как видно из таблицы конечных разностей при увеличении порядка конечных разностей ошибка в исходных данных распространяется и растет.
Такое взаимодействие ошибок называют шумом, если это ошибки округлений - то шумом округлений
.
Если ошибки округлений достаточно большие, то может происходить следующее явление: при увеличении порядка конечных разностей они могут уменьшаться и→0, но, дойдя до некоторого малого значения, опять могут начать расти из-за шума округлений.
Столбец в таблице конечных разностей, в которой все конечные разности ≈0, называют «практическим постоянным»; при этом конечные разности высших порядков не используют.
Для интерполяции целесообразно использовать многочлен такой степени, которая совпадает с порядком «практической постоянной» конечных разностей.
ЛЕКЦИЯ №8
ИНТЕРПОЛЯЦИОННАЯ ФОРМУЛА НЬЮТОНА ДЛЯРАВНООТСТОЯЩИХ УЗЛОВ
Дана функция y=¦(c),заданная на сетке равноотстоящих узлов:
yi
=¦(ci
), xi
=x0
+ihi
,
Строим интерполяционный полином с целью упрощения записи полинома (интерполяционного) и представления его в виде, позволяющем оценивать влияние каждого из компонентов на значение аппроксимации, запишем его так:
Nn
(x)=-a0
+a1
(x-x0
)+a2
(x-x0
)(x-x1
)+…+an
(x-x0
)…(x-xn-1
) (8.1)
Необходимо посчитать его коэффициенты ai
. Будем находить из условия
Nn
(xi
)=yi
i=0
: Nn
(x0
)=y0
=a0
+a1
0+…+an
0 a0
= y0
i=1
: Nn
(x1
)=y1
= y0
+a1
(x1
-x0
) + a2
0+…+an
0
x1
=x0
+1h=x1
-x0
=h
i=2
: Nn
(x2
)=y2
= y0
+∆y0
/h(x2
-x0
) (x2
-x1
) + a3
0+…+an
0
x2
-x0
=2h
x2
-x1
=h
y2
= y0
+∆y0
2+a2
2h2
i
=
k
: (8.2)
Запишем теперь, используя (8.2)
, полином (8.1)
в виде:
Nn
(x)= y0
+∆y0
/h(x-x0
)+…+ ∆n
y0
/n!hn
(x-x0
)(x-x1
)… (x-xn-1
) (8.3)
Полином (8.3)
1-ый интерполяционный многочлен Ньютона. Он наиболее приспособлен для вычисления значения функции в точках, близких к x0
С целью упрощения записи полинома введем переменную
x=x0
+gh
Если g-целое, то будет совпадать с номером узла
x0
– базовый узел полинома (8.3)
xi
=x0
+gh- x0
-ih=h(g-i);
Nn
(g)= y0
+∆y0
g+…+ ∆n
y0
/n!g(g-1)(g-2)(g-n+1) (8.4)
Полином Ньютона в силу единственности существования интерполяционного полинома Лагранжа является одной из форм записи полинома Лагранжа, поэтому для полинома (8.3) справедливо, что формула остаточного члена полинома Лагранжа
Для вычисления функции в точках находящихся в середине сетки узлов интерполяции либо в ее конце, т. е близкие к xn
, применяют два подхода
1. строят формулы для вычисления функции в точках х, близких к середине сетки интерполяции
2. формулы для точек х, близких к хn
(упорядочивание узлов интерполяции).
Соответственно получаются формулы Стирлинга , Бесселя, Гаусса, и 2-ой интерполяционный многочлен Ньютона .
Второй путь: в качестве узла х0
для заданной точки х берут тот узел, который наиболее близок к х, узел х1
выбирают как самый близкий из оставшихся узлов к х.
Т.е последовательность упорядочившаяся по возрастанию.
Для вычисления значения функции в точке х используется 1-ый интерполяционный многочлен Ньютона.
х0 х1 х2 х3 х4 х5 х6
Преобразуем узлы:
х0
′=x3;
x1
′=x4
;
x2
′=x2
;
x3
′=x5
;
Разделенные разности
Пусть функция ¦(c),задана на системе неравно отстоящих узлов.
Разделенной разностью 1-го порядка назовем выражение:
Разделенной разностью 2-го порядка:
Разделенной разностью k-го порядка:
(8.6)
|x-x0
|,
Свойства разделенной разности:
- на сетке равноотстоящих узлов разделенной разности совпадают конечными разностями
- разделенные разности понижают степень многочлена
- разделенные разности n-го порядка постоянны и равны
Интерполяционная формула Ньютона для не равноотстоящих узлов
Пусть функция ¦(c), задана на сетке не равноотстоящих узлов xi
, .Запишем следующие разделенные разности:
Выполним такие действия n-1 раз, получим:
Полином Ньютона:
Nn
(x)=¦0
(c)
Rn
(x)= ¦(c,c0,…
cn
)(x-x0
)… (x-xn
) (8.8)
То¦(c)= Nn
(x)+ Rn
(x)
Nn
(x) ≈ ¦(c)
Rn
(x) = ¦(c) - Nn
(x)
Если ¦(c) имеет (n+1)-ую производную, то остаточный член может быть преобразован к виду остаточного члена (8.9)
полинома Лагранжа.
При вычислении полинома в точке х узлы интерполяции лучше переименовать так, чтобы х0
был самым близким к х, а все остальные узлы тем более удаленные по увеличению расстояния к х.