Скачать .docx Скачать .pdf

Реферат: Численные методы

ЛЕКЦИЯ №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 = х01 <…<xn = b

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

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

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

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

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