Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 8
Текст из файла (страница 8)
Метод итераций (метод последовательных приближений).В этом параграфе мы познакомимся еще с одним численным методом решенияуравнений. Предположим, что уравнение можно записать в виде(19)x = ϕ ( x).Возьмем произвольную точку x0 из области определения функции ϕ ( x ) и будемстроить последовательность чисел { xn } , определенных с помощью рекуррентнойформулы(20)xn+1 = ϕ ( xn ) .Последовательность { xn } называется итерационной последовательностью. При ееизучении встают два вопроса:- 35 1.
Можно ли процесс построения последовательности { xn } продолжатьнеограниченно, т. е. будут ли эти числа принадлежать области определения функцииϕ ( x) ?2. Если итерационная последовательность (20) бесконечна, то как ведут себя еечлены при n → ∞ ?Ответ на оба вопроса дает следующая теорема.Теорема о сходимости итерационной последовательности.Пусть c - корень уравнения (19) и пусть функция ϕ ( x ) удовлетворяет на отрезке[c − δ , c + δ ] условию Липшица с константой L < 1y2 − y1 = ϕ ( x2 ) − ϕ ( x1 ) ≤ L x2 − x1 , L < 1 .(21)Тогда при любом выборе x0 на отрезке [ c − δ , c + δ ] существует бесконечнаяитерационная последовательность { xn } (20), сходящаяся к корню уравнения (19)x = c . Этот корень является единственным на отрезке [ c − δ , c + δ ] .Напомним известный факт из математического анализа: выполнение условияЛипшица (21) будет заведомо обеспечено, если предположить, что функция ϕ ( x )имеет на отрезке [ c − δ , c + δ ] непрерывную производную, ϕ ′ ( x ) модуль которойменьше единицы: ϕ ′ ( x ) ≤ m < 1 .
В этом случае согласно формуле конечныхприращений Лагранжа будем иметь(22)y2 − y1 = ϕ ′ (ξ )( x2 − x1 ) ≤ m x2 − x1 .Мы получили неравенство (21) с константой Липшица L = m .После этого замечания перейдем к доказательству теоремы. Число c являетсякорнем уравнения (19), так что c = ϕ ( c ) . Возьмем произвольную точку x0 на отрезке[c − δ , c + δ ] .
Она отстоит от точки c не больше, чем на δ : x0 − c ≤ δ .Вычислим x1 = ϕ ( x0 ) . При этом будем иметьx1 − c = ϕ ( x0 ) − ϕ ( c ) ≤ L x0 − c ≤ Lδ .(23)Неравенство (23) показывает, что точка x1 принадлежит отрезку [ c − δ , c + δ ] ирасположена ближе к точке c чем x0 .Продолжим построение итерационной последовательности. Вычислимx2 = ϕ ( x1 ) .
При этомx2 − c = ϕ ( x1 ) − ϕ ( c ) ≤ L x1 − c ≤ L2 x0 − c ≤ L2δ .Точка x2 тоже принадлежит отрезку [ c − δ , c + δ ] и расположена ближе к точке c чемx1 . На второй итерации мы опять приблизились к c .По индукции легко доказать, что все последующие итерации также существуюти удовлетворяют неравенствам- 36 Отсюда следует, чтоxn − c ≤ Ln x0 − c ≤ Lnδ .(24)lim ( xn − c ) = 0 , т.
е. lim xn = c .(25)n →∞n→∞Нам остается доказать, что корень x = c является единственным решениемуравнения (19) на отрезке [ c − δ , c + δ ] . Действительно, предположим, что существуетеще один корень x = c1(26)c1 = ϕ ( c1 ) , c − δ ≤ c1 ≤ c + δ .Примем c1 за нулевое приближение и будем строить итерационнуюпоследовательность (20). С учетом (26) получим xn = c1 , n = 0,1, 2,K . С другойстороны, по доказанному lim xn = c , т.
е. c1 = c . Никаких других решений, кроме x = c ,n→∞уравнение (19) на рассматриваемом отрезке не имеет.Доказанная теорема имеет простой смысл. Будем говорить, что функция ϕ ( x )осуществляет отображение точки x отрезка [ c − δ , c + δ ] на точку y = ϕ ( x ) .Рассмотрим пару точек x1 , x2 и их образы y1 , y2 .Условие Липшица (21) приводит ктому, что расстояние между образами оказывается меньше расстояния междуисходными точками, т. е. отображение y = ϕ ( x ) является сжимающим. Корень c неподвижная точка отображения: c = ϕ ( c ) . В результате каждый шаг в итерационномпроцессе, сжимая расстояние, приближает очередную итерацию к корню.Центральная идея метода итераций – сжимающие отображения – являетсявесьма общей.
Например, одно из доказательств теоремы существования иединственности решения задачи Коши для обыкновенных дифференциальныхуравнений основано на методе последовательных приближений в условиях, когдадействует принцип сжимающих отображений. Для многих сложных нелинейных задачпринцип сжимающих отображений оказывается основным методом исследования.Задача 2.Записать уравнение (16) в видеx = cos x ,и найти приближенное значение его корня методом итераций.В данном случае(27)ϕ ( x ) = cos x , ϕ ′ ( x ) = − sin x .На отрезке [ 0,1] , на котором расположен корень уравнения (27), для модуляпроизводной справедлива оценкаϕ ′ ( x ) ≤ sin1 < 0.85Она обеспечивает выполнение условия Липшица с константой Липшица L = 0.85 .Результаты вычислений по рекуррентной формулеxn+1 = cos xn- 37 даны в таблице 2.
За нулевое приближение выбрана средняя точка отрезка x0 = 0.5 .Для удобства анализа итерационной последовательности ее члены расположены подва в строке. В результате образовались столбцы членов с четными и нечетныминомерами. Сравнивая их между собой, мы видим, что четные члены меньше нечетных:итерационная последовательность «скачет» то вверх, то вниз. С возрастанием номерачетные члены последовательности возрастают, а нечетные убывают, приближаясьдруг к другу. Такое поведение последовательности означает, что корень уравнениялежит между ними.
Четные члены дают его значение с недостатком, нечетные – сизбытком. Это позволяет легко контролировать точность, достигнутую после любогочисла итераций: погрешность не превышает разности между последним нечетным ичетным членами. Мы остановили процесс вычислений на 19-ой итерации и можемнаписать для корня c двойное неравенствоx18 = 0.738912449332 < c < x19 = 0.739201444135или, отбрасывая лишние десятичные знаки,0.73891 < c < 0.73921 .Таким образом, члены итерационной последовательности x18 и x19 определяют c снедостатком и с избытком с погрешностью, которая не превышает разности x19 − x18 :ε < ∆19 = x19 − x18 < 0.0003 .Точность, которой мы достигли после 19 итераций, примерно соответствует точности12 шагов метода вилки.
Причина такого различия ясна. В обоих методах погрешностьубывает по закону геометрической прогрессии. Для метода вилки знаменательпрогрессии равен 1/2. Он не зависит от вида функции f ( x) . Для метода итерацийзнаменатель прогрессии равен константе Липшица. В рассматриваемом примереL = 0.85 . Поэтому скорость сходимости метода итераций медленнее скоростисходимости метода вилки.
Метод итераций имеет преимущество перед методом вилкив скорости сходимости только при L < 1/ 2 .Таблица 2n0123456789x2n0,5000000000000,6390124941650,6947780267880,7191654459420,7300810631380,7350063090150,7372357254420,7382462383320,7387045393570,738912449332x2 n+10,8775825618900,8026851006820,7681958312820,7523557594220,7451203413510,7418265226430,7403296518780,7396499627700,7393414522810,739201444136- 38 §3. Метод касательных (метод Ньютона).Метод касательных, связанный с именем Ньютона, является одним из наиболееэффективных численных методов решения уравнений.
Идея метода очень проста.Предположим, что функция f ( x) , имеющая корень c на отрезке [ a, b ] ,дифференцируема на этом отрезке и ее производная f ′( x) не обращается на нем вноль. Возьмем произвольную точку x0 ∈ [ a, b ] и запишем уравнение касательной кграфику функции f ( x) в этой точке(28)y = f ( x0 ) + f ′( x0 ) ( x − x0 ) .График функции f ( x) и ее касательной близки около точки касания, поэтомуестественно ожидать, что точка x1 пересечения касательной с осью x будетрасположена недалеко от корня c (см.
рис. 2). Для определения точки x1 имеемуравнениеf ( x0 ) + f ′( x0 ) ( x1 − x0 ) = 0 ,согласно которомуf ( x0 ).x1 = x0 −f ′ ( x0 )Повторим проделанную процедуру: напишем уравнение касательной к графикуфункции f ( x) в точке x1 и найдем для нее точку пересечения x2 с осью x (см. рис. 2):f ( x1 ).x2 = x1 −f ′ ( x1 )Продолжая этот процесс, получим последовательность { xn } , определенную спомощью рекуррентной формулыf ( xn ).(29)xn+1 = xn −f ′ ( xn )При ее исследовании, как и при исследовании последовательности (20) методаитераций, встают два вопроса:1.
Можно ли процесс вычисления чисел { xn } по рекуррентной формуле (29)продолжать неограниченно, т. е. будут ли эти числа принадлежать отрезку [ a, b ] ?2. Если процесс (29) бесконечен, то как ведет себя последовательностьn → ∞?{ xn }приПри анализе этих вопросов предположим, что корень x = c является внутреннейточкой отрезка [ a, b ] , а функция f ( x) дважды непрерывно дифференцируема наданном отрезке, причем ее производные удовлетворяют неравенствам(30)f ′( x) ≥ m > 0 , f ′′( x) ≤ M , x ∈ [ a, b ] .- 39 Следует обратить внимание на то, что в неравенствах (30) величина m дает оценкумодуля первой производной f ′( x) снизу, а величина M оценку модуля второйпроизводной f ′′( x) сверху.Теорема о сходимости метода касательных.Если функция f ( x) удовлетворяет сформулированным условиям, то найдется такоеδ : 0 < δ ≤ min( c − a , b − c ) , что при любом выборе начального приближения x0 наотрезкесуществуетбесконечнаяитерационная[ c − δ , c + δ ] ⊂ [ a, b ]последовательность (29) и эта последовательность сходится к корню c .В силу предположения о дифференцируемости функции f ( x) и неравенственулю ее производной, уравнение (1) эквивалентно на отрезке [ a, b ] уравнениюf ( x),(31)f ′( x )так что корень x = c исходного уравнения является одновременно корнем уравнения(31).
Исследуем возможность отыскания этого корня с помощью метода итераций.Вычислим и оценим производную функции ϕ ( x ) (31):x = ϕ ( x ) , где ϕ ( x ) = x −( f ′ ( x ) ) − f ( x ) f ′′ ( x ) = f ( x ) f ′′ ( x ) ,ϕ ′( x ) = 1 −( f ′( x ))( f ′( x ))222(32)M(33)f ( x) .m2Теперь воспользуемся непрерывностью функции f ( x) и ее равенством нулю в точкеx = c . Возьмем ε = m 2 / ( 2 M ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
