ЛЕКЦИЯ №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).

Постановка задачи интерполяции.

Для того чтобы конкретизировать постановку задачи приближения функции необходимо ответить на следующие вопросы:

что известно о ¦(c) (способ задания, степень гладкости);

к какому классу, семейству функций должна принадлежать j(c);

что понимаем под близостью 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+…+аnxn.

Для того, чтобы считать 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) представляет собой альтернативную форму записи интерполяционного полинома, точность приближения функции также может быть оценена по формуле (6.5)

(7.1)-интерполяционная схема Эйткина.

КОНЕЧНЫЕ РАЗНОСТИ

Пусть функция ¦(c) задана на системе равноотстоящих узлов xi=x0+ih,

где h-шаг сетки, yi=¦(ci).

Конечной разностью первого порядка в точке x0 называется ∆y0=y1-y0

Конечной разностью первого порядка в точке xi: ∆yi=yi+1-y0-yi

Конечной разностью второго порядка в точке x0 : ∆2y0=∆y1-∆y0

Конечной разностью второго порядка в точке xi: ∆2yi=∆yi+1-∆yi

Общая формула для конечной разности k-того порядка в точке xi:

∆kyi=∆k-1yi+1-∆ky (7.2)

Заметим: ∆0yi= yi

Формула (7.2) позволяет вычислять рекуррентно конечные разности

Связь конечных разностей и производных

чем меньше h, тем точность выше

Аналогично можем получить связь

; (7.3)

Свойства конечных разностей

В связи с производными вида (7.3) конечные разности обладают свойствами:

постоянные, равны нулю;

постоянный множитель у функции выносится за знак

суммы 2-х функций равны сумме каждой функции

полинома n-ой степени, n-го порядка постоянны и равны

∆ny=hnann!

an-коэффициент при xn полинома Rn(x)

Верно и обратное утверждение: все конечные разности n-го порядка некоторой функции постоянны и одинаковы, конечные разности n +1-го порядка равны 0, а конечные разности n-1-го порядка различны, то функция представляет собой полином n-ой степени.

Распространение ошибки в исходных данныхпри вычислении конечные разности

Любые измерения несут в себе погрешность (ошибка округления, точность измерения приборов)

Пусть значения функции определены в узлах x0, и в некоторой точке xk значение некоторой точке xk значение функции найдено с ошибкой ε, т.е ỹk+ ε

Составим таблицу конечных разностей

xk-2 yk-2 ∆yk-2 ∆2yk-2 ∆3yk-3 + ε

xk-1 yk-1 ∆yk-1 + ε ∆2yk-2 + ε ∆3yk-2 -3 ε

xk yk+ε ∆yk-1 - ε ∆2yk-1 - 2 ε ∆3yk-1 + 3 ε

xk+1 yk+1 ∆yk+1 ∆2yk+ ε ∆3yk- ε

xk+2 yk+2 ∆2yk+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+a10+…+an0 a0= y0

i=1: Nn(x1)=y1= y0+a1(x1-x0) + a20+…+an0

x1=x0+1h=x1-x0=h

i=2: Nn(x2)=y2= y0+∆y0/h(x2-x0) (x2-x1) + a30+…+an0

x2-x0=2h

x2-x1=h

y2= y0+∆y02+a22h2

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+∆y0g+…+ ∆n y0 /n!g(g-1)(g-2)(g-n+1) (8.4)

Полином Ньютона в силу единственности существования интерполяционного полинома Лагранжа является одной из форм записи полинома Лагранжа, поэтому для полинома (8.3) справедливо, что формула остаточного члена полинома Лагранжа

Для вычисления функции в точках находящихся в середине сетки узлов интерполяции либо в ее конце, т. е близкие к xn, применяют два подхода

строят формулы для вычисления функции в точках х, близких к середине сетки интерполяции

формулы для точек х, близких к х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 был самым близким к х, а все остальные узлы тем более удаленные по увеличению расстояния к х.