Численные методы

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