Численные методы. Ионкин (2012) (неоффициальные) (косяки есть) (1160437), страница 9
Текст из файла (страница 9)
. . , ϕn (x) ∈ L2илиZbϕ2i dx < ∞,i = 0, naСоставим многочленϕ(x) = c0 ϕ0 (x) + c1 ϕ1 (x) + . . . + cn ϕn (x) =nXck ϕk (x),x=0где ϕ(x) — обобщенный многочлен, построенный по функциям ϕi (x).Среди всех многочленов ϕ(x) нужно найти многочлен ϕ(x):ϕ(x) =nXk=0ck ϕk (x),(1)62который минимизирует интеграл (норму)kf (x) −ϕ(x)k2L2ZbZb2(f (x) − ϕ(x)) dx = min=(f (x) − ϕ(x))2 dx.ϕ(x)aaВ этом случае говорят, что ϕ(x) — наилучшее среднеквадратичное приближение(НСКП) f по системе {ϕi (x)}n0 .
Построим НСКП в случае, когда базисная функцияϕ0 (x) одна, то есть при n = 0 :Zbϕ20 (x)dx < ∞,ϕ0 (x) ∈ L2aЯсно, чтоZbF (c0 ) =(f (x) − c0 ϕ0 (x))2 dx =Zbaf 2 (x)dx − 2c0aZbZbf (x)ϕ0 (x)dx +ac20 ϕ20 (x)dxa— квадратичная функция относительно c0 . Коэффициент c0 в наилучшем среднеквадратичном приближении находится из условия F 0 (c0 ) = 0:Zb2Zbf (x)ϕ0 (x)dx = 2c0aϕ20 (x)dxa⇓Rbc0 =f (x)ϕ0 (x)dxaRb=ϕ20 (x)dx(f, ϕ0 )(ϕ0 , ϕ0 )aТаким образом НСКП ϕ(x) = c0 ϕ0 (x) =(f, ϕ0 )ϕ0 . Если(ϕ0 , ϕ0 )Rbϕ0 (x) = 1,c0 =то,(b − a)Rbϕ(x) = c0 · 1 =f (x)dxaf (x)dxa(b − a)будет являться средним значением интеграла.,63Перейдем к общему случаю.
Пусть {ϕi (x)}n0 — система линейно независимых(базисных) функций из L2 , то естьZbϕ2i (x)dx < ∞,ϕi (x) ∈ L2 [a, b].aТогда составим функциюZb(f (x) −F (c0 , c1 , . . . , cn ) =nXck ϕk (x))2 dx.k=0aНайдем минимум этой функции. Заметим, что он достигается, когда∂F= 0,∂ckk = 0, n,Итак,F (c0 , c1 , . .
. , cn ) =ZbZbZbnnnXXX= f 2 (x)dx − 2ck f (x)ϕk (x)dx +ckcl ϕk (x)ϕl (x)dx =k=0a= (f, f ) − 2nXk=0ack (f, ϕk ) +nXk=0k=0cknXl=0acl (ϕk , ϕl )l=0Минимум функции F (c0 , c1 , . . . , cn ) достигается в точке, где∂F (c0 , . . . , cn )= 0,∂ckk = 0, n.В итоге получаем систему уравнений:nXcl (ϕk , ϕl ) = (f, ϕk ),k = 0, n.l=0Или в координатном виде:c0 (ϕ0 , ϕ0 ) + c1 (ϕ0 , ϕ1 ) + . . .
+ cn (ϕ0 , ϕn ) = (f, ϕ0 )c (ϕ , ϕ ) + c (ϕ , ϕ ) + . . . + c (ϕ , ϕ ) = (f, ϕ )110111n1n1...c0 (ϕn , ϕ0 ) + c1 (ϕn , ϕ1 ) + . . . + cn (ϕn , ϕn ) = (f, ϕn )Правые части системы известны. Выпишем матрицу из коэффициентов:(ϕ0 , ϕ0 ) (ϕ0 , ϕ1 ) . . . (ϕ0 , ϕn ) (ϕ1 , ϕ0 ) (ϕ1 , ϕ1 ) . . . (ϕ1 , ϕn ) . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . = G(ϕ0 , . . . , ϕn ), |G| > 0(ϕn , ϕ0 ) (ϕn , ϕ1 ) . . . (ϕn , ϕn )(1)64Полученная матрица является матрицей Грама. Если система линейно независима, то матрица Грама невырожденная. Следовательно, по критерию определенностиСЛАУ существует единственное решение:c0 , c1 , . .
. , cnЭти коэффициенты позволяют выписать обобщенный многочленϕ(x) =nXci ϕi (x),i=0который является НСКП для функции f .Если система исходных базисных функций {ϕi (x)}n0 ортонормирована, то матрица Грама превратится в единичную (G = E) иci = (f, ϕi ),i = 0, n,(2)где ei — коэффициенты Фурье.Рассмотрим систему линейно независимых функций:1, x, x2 , . . . , xn ,ϕi (x) = xiисходя из нее можно построить ортогональную систему. Для этого рассматриваетсяскалярное произведение:Zβρ(x)ϕk (x)ϕl (x)dx = (ϕk , ϕl ),αгде α и β – выбираемые границы, ρ(x) > 0 – весовая функция. Если выбирать различные α, β и ρ(x), то можно получить полиномы Якоби, Лежандра, Чебышева идругие. Эти полиномы — ортогональные полиномы.( по ним строить НСКП наиболееудобно).Замечание. Если система {ϕi (x)}n0 ортонормирована, то нетрудно вычислить отклонение от НСКП:Zb[f (x) −F (c0 , c1 , .
. . , cn ) =aТогда(f, f ) >nX2ck ϕk (x)] dx = (f, f ) −k=0nXc2k ,nXc2k > 0.k=02kf k >k=0nXc2kk=0Это есть неравенство Бесселя.Если {ϕi }n0 — ортонормированный базис, то неравенство переходит в равенство Парсеваля:nXkf k2 =c2kk=0Глава 3Численное решение нелинейныхуравнений и систем нелинейныхуравнений§1 ВведениеПусть задана функция f (x), x ∈ R, причем функция f непрерывна. Будем решать уравнение на отрезке [a, b].f (x) = 0,x ∈ [a, b](1)Решая это уравнение нужно пройти 2 этапа:1.
Локализация корней уравнения.Пусть x∗ — кореньf (x∗ ) = 0.Нужно указать окрестность корня:Ua (x∗ ) = {x : |x∗ − x| < a}.2. Построение итерационного процессаxn −→ x∗ .Аналогичная задача будет ставиться и для системы :f1 (x1 , . . . , xm ) = 0f (x , . . . , x ) = 02 1m...fm (x1 , . . . , xm ) = 065(2)66Введя вектор x = (x1 , x2 , .
. . , xm ), f = (f1 , . . . , fm )τ , можем систему (2) переписать в виде f (x) = 0.Можно f трактовать как отображение Rm −→ Rm (нелинейное). Укажем способы локализации корня:1. Если f — непрерывная функция, то разобьем отрезок на узлы xi и вычислимзначения в узлах. Если f (xi )f (xi−1 ) < 0, то ясно, что на этом частичном отрезкеесть по крайней мере один корень. Далее этой процедуре подвергаем отрезок[xi , xi−1 ].
Тогда найдем а–окрестность Ua (x∗ ).2. Метод бисекции. Пусть есть отрезок [a, b], на котором есть корень. И пустьдля определенности f (a) < 0, f (b) > 0. Сначала рассмотрим середину отрезка(a + b). Вычислив значение в этой точке (пусть оно > 0), определим,x0 =2что корень принадлежит [a, x0 ].
Зная это проделываем то же самое и получаем(a + x0 )точку x1 =. Пусть это значение тоже > 0, тогда значение x∗ находится2в интервале [a, x1 ]. Далее продолжаем процесс до нужной точности.Предположим, что корней в x∗ много, тогда на первом этапе выразимf = (x − x∗ )g(x).Далее будем проводить процесс для g(x).§2 Метод простой итерацииРассмотрим нелинейное уравнение:f (x) = 0(1)Пусть задана окрестность корня Ua (x∗ ). Тогда метод простой итерации строится исходя из уравнения:x = S(x)(2)по формуле:xn+1 = S(xn ),где n = 0, 1, . . . ,(3)x0 ∈ Ua (x∗ ).
Функция S(x) выбирается в видеS(x) = x + r(x)f (x),(4)где f (x) — исходная функция, r(x) — функция: sign(r(x)) 6= 0 ∀x ∈ Ua (x∗ ).Определение. S(x) удовлетворяет условию Липшица с константой q, если∀x1 , x2 ∈ Ua (x∗ ) выполняется неравенство:|S(x1 ) − S(x2 )| 6 q|x1 − x2 |(5)67Утверждение. Пусть S(x) — удовлетворяет условию Липшица с константой q ∈(0, 1) и пусть начальное приближение x0 берется из Ua (x∗ ). Тогда метод простойитерации сходится со скоростью геометрической прогрессии со знаменателем q.Доказательство: Докажем по индукции. n = 0 : x0 ∈ Ua (x∗ ). Покажем, что еслиxn ∈ Ua , то и xn+1 ∈ Ua .
Это будет означать, что при итерационном процессе мы невыйдем из окрестности Ua .Оценим |xn+1 − x∗ |: так как xn+1 = S(xn ), то|xn+1 − x∗ | = |S(xn ) − S(x∗ )| 6 q|xn − x∗ |.Так как q < 1, то это означает, чтоq|xn − x∗ | < a.А значит xn+1 ∈ Ua (x∗ ).Это соотношение можно применять как рекуррентное:|xn − x∗ | 6 q n |x0 − x∗ |и при n → ∞:lim q n = 0.n→∞Это означает, что в пределе при n → ∞ xn даст нам x∗ .
Данный итерационный методимеет медленную сходимость, так как связь xn+1 и xn — линейная.Замечание. Пустьmax |S 0 (x)| = q < 1,x∈Uaтогда МПИ сходится, если x0 ∈ Ua (x∗ ).Замечание. Рассмотрим следующий итерационный процесс:xn+1 − xn+ f (xn ) = 0,τ(6)где n ∈ N0 , x0 ∈ Ua (x∗ ), τ > 0.Пусть для определенности f 0 (x) > 0. Запишем метод (6), как метод простойитерации:S(x) = x − τ f (x).В силу первого замечания, если |S 0 (x)| < 1, то сходимость есть.S 0 (x) = 1 − τ f 0 (x), в предположении, что f — гладкая.ОбозначимM1 = max |f 0 (x)|.x∈Ua (x∗ )Тогда|1 − τ M1 | < 1=⇒−1 < 1 − τ M1 < 1=⇒0<τ <2.M168Ускорение сходимости итерационного метода (метод Эйткена)Пусть известно, что две соседние итерации удовлетворяют следующему условию:xn − x∗ ≈ Aq n ,n = 1, 2, 3, .
. .Запишем 3 соседних итерации:xn−1 − x∗ ≈ Aq n−1(7)xn − x∗ ≈ Aq n(8)xn+1 − x∗ ≈ Aq n+1(9)Поставим задачу выразить корень через эти итерации:x∗ ≈ xn+1 − Aq n+1 ,(xn+1 − xn )2 = A2 q 2n (q − 1)2 ,(xn+1 − 2xn + xn−1 ) = Aq n−1 (q − 1)2 .(xn+1 − xn )2= Aq n+1 .(xn+1 − 2xn + xn−1 )В итогеx∗ ≈ xn+1 −(xn+1 − xn )2.(xn+1 − 2xn + xn−1 )Так как все равенства приближенные, то x∗ берется за значение xn+1 итерации.§3 Метод Ньютона и метод секущихРассматриваем нелинейное уравнениеf (x) = 0(1)Корень уравнения локализован, то есть указана окрестность Ua (x∗ ). Обозначим n –ю итерацию через xn .
Тогда запишем:xn+1 = xn −f (xn ), n = 0, 1, 2, 3, . . . x0 ∈ Ua (x∗ )0nf (x )(2)Методом Ньютона решения нелинейного уравнения f (x) = 0 называется метод, записанный в виде (2). Для доказательства сходимости метода Ньютона будем требовать,чтобы функция была гладкой до третей производной. ( так же этот метод называетсяметодом касательных)Если дана функция f (x) то уравнение касательной в точке (xn , f (xn )) будетиметь вид: y − f (xn ) = f 0 (xn )(x − xn ). Тогда за xn+1 принимается абсцисса точки, вкоторой касательная пересекает ось ординат.
Формулу (2) легко получить из следующих соображений. Разложим по формуле Тейлора в окрестности корня: f (x∗ ) = 0 =69f (x) + (x∗ − x)f 0 (xn ) + . . . . Тогда если вместо x∗ подставить xn+1 и вместо (x − xn ),то получим:0 = f (xn ) + (xn+1 − xn )f 0 (xn )Разрешим уравнение относительно xn+1 при условии, что f 0 (x) 6= 0 :xn+1 = xn −f (xn )f 0 (xn )Приведем графически пример, когда при неудачном выборе начального приближения метод Ньютона зациклится:yxx∗x1x0x2Рассмотрим модифицированный метод Ньютона:xn+1 = xn −f (xn ), n = 0, 1, 2, 3, . .
. x0 ∈ Ua (x∗ )f 0 (x0 )(3)Один из плюсов этого метода - не нужно считать производную на каждой итерации.Но сходимость этого метода ( в смысле скорости) будет хуже чем (2). Запишеммодифицированный метод Ньютона для нелинейных систем. Пусть существует дванелинейных уравнения :(f1 (x1 , x2 ) = 0f2 (x1 , x2 ) = 0В качестве решения системы понимается точка (x∗1 , x∗2 ), в которой fi (x∗1 , x∗2 ) = 0, i =701, 2. Разложим обе функции в ряд Тейлора:0 = f1 (x∗1 , x∗2 ) = f1 (x1 , x2 ) + (x∗1 − x1 )∂f1 (x1 , x2 )∂f1 (x1 , x2 )+ (x∗2 − x2 )+ ...∂x1∂x20 = f2 (x∗1 , x∗2 ) = f2 (x1 , x2 ) + (x∗1 − x1 )∂f2 (x1 , x2 )∂f2 (x1 , x2 )+ (x∗2 − x2 )+ ...∂x1∂x2Сделаем замену xi на xni , x∗i на xn+1innnnf1 (xn , xn ) + (xn+1 − xn ) ∂f1 (x1 , x2 ) + (xn+1 − xn ) ∂f1 (x1 , x2 ) = 0121212∂xn1∂xn2nnnnn+1n+1nnn ∂f2 (x1 , x2 )n ∂f2 (x1 , x2 )f(x,x)+(x−x)+(x−x)=0 2 1 21212∂xn1∂xn2Чтобы записать данную систему в компактном виде, введем векторы f =(f1 , f2 )T , x = (x1 , x2 )T и матрицу∂f1 ∂f1 1 ∂x2 (5)J(x) = ∂x∂f2 ∂f2 ∂x1 ∂x2: f (xn ) = J(xn )(xn+1 −xn ) = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
