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

ЛЕКЦИЯ №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<sub/>, 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<sub/> будем называть узламиинтерполяции

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

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

           />                                    (6.1)

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

/>

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

Вандермонда

При условии: x0¹xj  при<sub/> i¹j определитель системы (6.1) отличенот нуля, следовательно, система имеет единственное решение.

Вывод:

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

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

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

Pn(x)=∑ Ci li(x)                                                                  (6.2)

Ci=yi=¦(ci),li(x)=полиномы n-ойстепени, которые удовлетворяют условию:

/>

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

Тогда полином li<sub/>может быть записан в виде:

/>     (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<sub/>, 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       введем функцию вида<sub/>

/>

Функция 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)конечные разностиобладают свойствами:

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

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

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

4. полинома 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<sub/>εxk                yk+ε        ∆yk-1 -  ε                ∆2yk-1 -<sub/>2<sub/>ε                     ∆3yk-1  +<sub/>3<sub/>εxk+1         yk+1             ∆yk+1                       ∆2yk+<sub/>ε                    ∆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)+…+ ∆ny0/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, применяют два подхода 

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