Учебник - Практические занятия по вычислительной математике - Аристова (1238839), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Кроме того, этот метод крайне ненадежен: он может сходитьсямедленнее метода деления отрезка пополам или не сходиться вовсе.2. Метод парабол базируется на квадратичной интерполяции функции. Этот метод является трехточечным, т.е. для построения очередногоприближения к нулю функции нам необходимо знать три предыдущиеточки приближений xn, xn – 1, xn – 2. По трем точкам проводится парабола, издвух точек пересечения которой с осью x выбирается та, которая ближе кпоследнему приближению.3. Адаптированный метод Брендта является двухшаговым: из исходной пары точек, локализующих корень, за два шага строится еще дветочки, также локализующие корень. Целью метода является построениедвух точек, лежащих ближе к корню и по разные стороны от него. Система проверок гарантирует, что скорость сходимости метода будет не хуже,чем у метода деления отрезка пополам.1 шаг – строится линейная интерполяция по точкам a и b, как в методе секущих с проверкой знаков:caF (b)  bF (a).F (b)  F (a)88IV.4.

Метод простой итерации2 шаг . Пусть выпуклость функции такова, что F(a) F(c) > 0. Тогдастроится линейная интерполяция по точкам a и c:dcF (a)  aF (c).F ( a )  F (c )Далее делаются проверки полученных точек, обеспечивающие скорость сходимости не ниже деления отрезка пополам:1)Если d > (b + c)/2, тополагают d = (b + c)/2.2)d > с + , где  – заданная точность, в противном случае полагают d = с + .При заданной выпуклости корень лежит правее c, поэтомубрать точку левее с +  бессмысленно.Рис. 4.3 метод БрендтаВ идеале имеем F(c) F(d) < 0, т.е. корень локализован на отрезке [c,d].Сходимость квадратичная.

Если из-за сдвига точки d получилосьF(c) F(d) > 0, тогда корень локализован на [d,b] и сходимость не хуже линейной. В этом случае функция не может быть представлена линейнойфункцией с небольшой квадратичной поправкой.Если F(a) F(c) < 0, то F(b) F(c) > 0, то делают все то же самое с заменой a на b:dcF (a)  aF (c),F ( a )  F (c )d < (b + c)/2, то d = (b + c)/2d > с – , то d = с – F(c) F(d) < 0, след. отрезок [c,d]F(c) F(d) > 0, след.

отрезок [a,d]IV.4. Метод простой итерацииПусть известно, что интересующий нас корень x* уравнения F(x) = 0лежит в интервале Y = {x| a < x < b}. Приведем уравнение F(x) = 0 к равносильному уравнению видаx = f (x).(4.1)*Для отыскания решения x , принадлежащего интервалу Y, зададим x0,а затем вычислим последующие xn по формуле89IV. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙx n 1  f ( x n ),n = 0, 1, 2, …(4.2)По построению очевидно, что метод является одноточечным и нетребует отрезка локализации корня. Методы вида (4.2) называются методом простой итерации (МПИ).Теорема 1. Если функция f(x) удовлетворяет условию Липшица сконстантой q < 1:| f(x) – f(y)| < q |x – y| ,то метод простой итерации (4.2) сходится и справедлива оценка|xk + 1 – x*| < qk |x0 – x*| или|xk + 1 – x*| < qk/(1 - q) |x1 – x0|.Способов приведения к виду (4.1) существует множество.

Можно положить, например,f(x) = x + τF(x),(4.3)где τ = const. Такой вариант метода простых итераций иногда также называют методом релаксации.По Теореме 1 МПИ сходится при |1 + τF’(x)| < 1, т.е. при–2 < τF’(x) < 0.Если в некоторой окрестности корня F’(x) < 0 и имеет место оценка0 < m < |F’(x)| < M, то метод релаксации сходится при τ < 2/M.Наиболее быстрая сходимость будет достигнута при выбореτ = 2/(M + m).(4.4)IV.5. Метод НьютонаМетод Ньютона является одноточечным, т.е. для построения следующего приближения нам нужно знать только одно значение приближенного решения. Пусть приближение xn к корню x* уравнения F(x) = 0 уженайдено. Воспользуемся приближенной формулойF ( x)  F ( x n )  Fx  ( x  x n ),(5.1)точность которой возрастает при приближении xn к x*. Вместо исходногоуравнения F(x) = 0 воспользуемся линейным уравнениемF ( x n )  Fx ( x n )  ( x  x n )  0.Решение этого уравнения примем за приближение xn +1:90IV.5.

Метод Ньютонаx n1  x n  [ Fx ( x n )] 1  F ( x n ),n = 0, 1, 2, …(5.2)Метод линеаризации Ньютона допускаетпростую геометрическую интерпретацию(рис. 4.4). График функции F(x) заменяетсякасательной к нему в точке (xn, F(xn)). За приближение xn +1 принимается точка пересечения полученной прямой с осью абсцисс.Формулу (5.2) можно интерпретироватькак метод простой итерации с функциейРис. 4.4. Метод Ньютонаf (x) = x – [F'x]–1 F(x). В точке простого корня x* уравнения F(x) = 0 выполняется равенствоf 'x = F(x*) F''(x*)/F '2(x*) = 0,поэтому неравенство |f 'x| < q верно для любого положительного фиксированного значения q в достаточно малой окрестности корня.Следовательно, асимптотически последовательность погрешностейεn = |x* – xn| метода Ньютона убывает быстрее последовательности членовгеометрической прогрессии.Справедлива теорема о квадратичной сходимости метода Ньютона.Теорема 2. Пусть функция F (x) определена на интервалеa  r  x  a  r,r 0и удовлетворяет следующим условиям:1) F(x) дважды непрерывно дифференцируема на этом интервале;2) для всех точек интервала F'(x) ≠ 0 и существуют конечные значенияM1  sup | [ F ( x)]1 |,M 2  sup | F ( x) |, M 2  0;3) уравнение F(x) = 0 имеет корень x* :a  r  x* 2M x*  x* 2M a  r,где M = M1M2.

Тогда для любого значения x0:x* 2M x 0  x* 2M,итерационный процесс сходится к x* , причемM | x x |  2 n*2n 1n| x0  x* |2 .91IV. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙНа практике более привлекательна такая формулировка условий сходимости метода Ньютона, для которой не нужна никакая информация орешении уравнения. Примером формулировки может служить следующаятеорема.Теорема 3. Пусть функция F(x) определена и дважды непрерывнодифференцируема на интервале |x – x0| < r (r > 0). Пусть также F(x0) ≠ 0,F'(x) ≠ 0, существует конечное значение M = sup|[F'(x0)] –1F''(x)| > 0 и2M F (x 0 ) 1,F ( x 0 )F (x 0 )2F ( x 0 ) r.Тогда итерации процесса Ньютона сходятся к некоторому решениюуравнения x*, для погрешности справедлива оценкаF ( x0 )| x n  x* |  2M0 F ( x )2n M 12n.По аналогии с методом Ньютона могут строиться методы высшихпорядков сходимости.

Пусть у нас имеется итерационный процессxn 1  f ( xn ) .Решение уравнения есть неподвижная точка такого отображенияx* = f(x*). Вычтем второе равенство из первогоxn 1  x*  f ( xn )  f ( x* )и разложим правую часть в ряд Тейлора в окрестности точки x*:f ( x* ) nf ( x* ) nx n 1  x*  f ( x* )( x n  x* ) ( x  x* ) 2 ( x  x* )3  ...26Если в точке x* решения нелинейного уравнения F(x) = 0 обращается внуль не только коэффициент при (xn – x*), но и при (xn – x*)2, то методимеет третий порядок сходимости.

Однако методы высоких порядковсходимости используются довольно редко в силу повышенных требований к гладкости функции и жестких условий на начальное приближение,обеспечивающих сходимость метода.IV.6. Метод простой итерации для систем нелинейных уравненийнийМПИ может быть обобщен для решения систем нелинейных уравне-92IV.7.

Метод Ньютона для систем нелинейных уравненийF(u) = 0.(6.1)Пусть эту систему можно представить в эквивалентном виде(6.2)u = f(u),то следующие приближения к решению можно строить как последовательность итерацийun + 1 = f(un).Отображение v = f(u) называется сжимающим в замкнутой выпуклойобласти   R N , если существует q, 0 < q < 1 такое, что(f (u1 ), f (u 2 ))  q(u1 , u 2 )для любых двух точек u1 , u 2   .Теорема 4. Если отображение v = f(u) является сжимающим в замкнутой выпуклой области Ω, то уравнение (6.2) имеет единственноерешение u* и имеет место оценкаqn a(u n , u* ) , где a  (u1 , u 0 ) .1 qТеорема 5.

(Достаточное условие сходимости МПИ). Пусть область   R N выпуклая, а компоненты fi(u) вектор-функции f(u) = (f1,…,fn(u))т имеют равномерно непрерывные производные первого порядка.Пусть норма матрицы Якобиf1  f1 u ... u 1n df (6.3)J  ...du  f n ... f n  uun  1не превосходит некоторого числа q, 0 < q < 1, т.е. J  q u   , тогдаотображение v = f(u) является сжимающим в Ω.IV.7. Метод Ньютона для систем нелинейных уравненийМетод Ньютона для систем нелинейных уравнений (6.1) являетсяобобщением метода Ньютона для одного нелинейного уравнения. Линеаризуем систему уравнений (6.1) в окрестности предыдущего приближенияF(uk+1)  F(uk)+ J(uk+1 – uk) = 0.93IV. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙТогда следующее приближение к корню может быть построено какuk+1  uk + J-1F(uk)какJ – матрица Якоби исходной системы (не путать с (6.3)!) вычисляется F1 u1dF J  ...du  Fn u 1F1 un .Fn ...un Достаточное условие сходимости метода Ньютона имеет достаточносложный вид, и проверить его на практике почти никогда не удается.

Характеристики

Список файлов книги