Численные методы (стр. 1 из 3)

ЛЕКЦИЯ №5

МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

СНУ

Пусть дана система вида:

(5.1)

f'(x)=

- производная

Частная производная

- вектор (все значения).

МЕТОД НЬЮТОНА

Дана система вида (5.1), где f_i один раз непрерывно дифиринцируемые функции, т.е. существуют все частные первые производные этих функций.

Строим последовательность приближений

сходящуюся к точному решению системы .

Пусть

- некоторое начальное приближение к решению, а - катое приближение к решению. Построим зависимость, позволяющую на основании построить .

Точное приближение

ξ-корень обращает уравнение в верное равенство(тождество).

(5.2)

Разложим функции f_i из системы (5.2) в ряд Тейлора в окрестности точки х^к до линейных составляющих.

(5.3)

Система (5.3) представляет собой систему линейных алгебраических уравнений для поиска компонента вектора поправки h^k.

Перепишем систему (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)

Всегда ли метод сходится?

Пусть М- матрица, составлена из элементов m_ij

M=[m_ij], где m_ij=

Определение нормы матрицы А:

-число удовлетворяющее свойствам.

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 = х₀<х₁<…<x_n= b

интерполяция – вычисление ¦(c) в точке Î[a;b], x¹x_i, i = 0,n

экстраполяция – вычисление функции ¦(c) в точке ХÎ[a;b];

Определение интерполяции ввел в 1656 году Джон Уолесс, а в 1655 году ввел символ ¥.

Для полиномиальной интерполяции j(c) имеет вид j(c)=а₀+а₁х+а₂х²+…+а_nxⁿ.

Для того, чтобы считать j(c) к ¦(c) вводится ограничение j(c_i)= ¦(c_i), i=0,n ;

Т.е значения этих функций в точке х_i должны совпадать. Точки х_i будем называть узлами интерполяции

Интерполяционный многочлен Лагранжа

Необходимо определить коэффициенты полинома степени n(их будет n+1), построения аппроксимации функции, заданной в n+1 узле. Используя ограничения на j(c): j(c_i)= ¦(c_i)=y, i=0,n , составим систему:

(6_.1)

Выпишем определитель этой системы

Определитель

Вандермонда

При условии: x₀¹x_jприi¹j определитель системы (6.1) отличен от нуля, следовательно, система имеет единственное решение.

Вывод:

если задано разбиение в виде n+1различной точки, то всегда существует функция в виде полинома n-ой степени, которая проходит через все точки графика ¦(c),определенной на этом разбиении.

Посторонние приближенияфункции при помощи полиномов указанным способом весьма трудоемко и обладает большой вычислительной погрешностью, поэтому его использование для большого числа узлов интерполяции нецелесообразно.

Лагранж предложил строить интерполяционные полиномы в виде:

P_n(x)=∑ C_il_i(x) (6.2)

C_i=y_i=¦(c_i), l_i(x)=полиномы n-ой степени, которые удовлетворяют условию:

Для полинома узлы интерполяции x_j, j=0,n , j≠I являются корнями, причем действительными и попарно различными (все имеют кратность 1)

Тогда полином l_iможет быть записан в виде:

(6.3)

Общий вид полинома Лагранжа:

(6.4)

Встает вопрос о точности, о приближения функции. Вводится понятие остаточного члена многочлена Лагранжа ; для того, чтобы оценить аппроксимации ¦(c) в некоторой точке xÎ[a;b]

Функцию ¦(c) представим в виде ¦(c)= P_n(x)+R_n(x), где R_n(x)- остаточный член многочлена Лагранжа в процессе длительного и трудоемкого вывода для R_n(x) получена следующая формула: