Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 20
Текст из файла (страница 20)
1Š— тоЛ 1»1г»'1'» ~ «Ро'(г» 1А, Эта формула получается либо из условия минимума нормы 1г»о,1~ погрешпостн г„о, = у„о, — и, либо нз условия ортогональностн певязок г, н г»оо Уинояоая скалярно уравнение г»»1=㻠— т»+1Лг, на г„получаем 0 = (г,, г„)— — т„+,(Аг„, г»), откуда следует формула (7). Поскольку Лг,=Ау,— Аи= г„то 1 6 ВАРиАционнолгткРАционньгк методы 129 1 А+ Ь= !(РА- — иЬ <Р7~!Ув — и(~:.
Метод скорейптего спуска сходится в Н* с той я1е скоростью, что и метод простой итерации. 3. Метод сопрягкеиных градиентов. Более быстро сходящиеся методы варнацпонного югпа моя'но найти в классе неявных трехслойных итерационных схем: Ву,з: = амп( — т,е,А)у„+ (1 — а„,)Ву,, + +ат ~т,~,(, й=(,2, ..., (8) Ву, = ( — т,А)р„+ т,й Мы рассмотрим жвгод сопряженных градиентов, широко используемый на практже. Для него итерацпонпые параметры атэ, и т„+, определяются по формупам (аь, ъа) тАР1 (пи '"л) — "=('- — ' — — Г' (Аиь, иь) ' (РА пиа т) аа / (9) где й=О, т, 2... в цредполощепип, что А =Л*)0, В = В* > О, "(,В < Л < (,В, "(, > О.
Формулы для т,е„аг,, получаготся из требования минимума нормы разреша1ощего Оператора. )1ри этих оптимальных значениях итерационных параметров верна оценка ~~ у„— и((А(о„!~у — и(,'и — (10) т т, е. скорость сходимости метода сопряткенпых градиентоз — такая же, как н скорость сходт1мосвп двухслойного итерационного метода с чебыптевскими параметрамк (которьгй использует (, и (, при вычислешш1 параметров т,э,).
Поэтому для числа итераций имеем оценки по (е) «( п (е) ~ пв (е) лп 1, п, (з) = =! и —. 1 2 Б качестве оператора В мокино взять факторизованный оператор поиеременно-треугольного метода В = (В + ыЛ,) В ' (В + о>Лг), А,+А„— А~О, Л,'=..Лм Ю=ЮА>0. гас гл. пп Ргшвпне Алгевгапческих УРАВненпп Расчеты показывают, что число итераций по попеременно-треугольяому методу в сочетании с методом сопряженных градиентов меньше, чем в случае использования чебышевской схемы. $ 7, Решение нелинейных уравнений $. Итерационные методы. Рассмотрим нелинейное уравнение (х) =0 хы1а Ы (1) Ф где 1(х) — непрерывная функция.
Уравнение может иметь один плп несколько корней. Требуется: 4) установить существование корней уравнения; 2) найтн приближенные значения корней. '1асто обе задачи решаются одновременно. Для нахозкдепия корней применяются итерационные методы. Простейшим является метод дихотомии (деления тзополам). Пусть /(х„)1(х,) ~0; тогда па отрезке (х„х,) лежит ве менее одною корня. Найдем 1(х,), где х, = =(х,+х,У2, и возьмем х,— то из значений х, пли хо для которого выполняется условие )(х~))(х,) ~ О, Отрезок 1х„х,1 снова делим пополам, и т.
д, Деление продолжим до тех пор, пока длина отрезка станет меныпе 2е, где е — точность, с которой надо определить корень. Тогда середина этого отрезка и дает значение корня с требуемой точностью е. Процесс, очевидно, сходится со скоростью геометрической прогрессии со знаменателем 1/2. Недостатки метода; выбор начального отрезка 1хп х~) — заранее неясно, к какому корню сойдется процесс (если вх несколько па (х„х,1).
Второй метод — слетай простой итерации, Перепишем травненне (1) в виде (2) х = ср(х), где ~р(х) можно определить одним пз способов: <р(х) = х — и1(х), а = сопят, ~р(х) =.х+ р(х)~(х), р(х) — произвольная функция, не именующая корней на отрезке 1а, Ы. Метод простой итерации определяется формулой х,, =ср(х,), я=0, 1, 2, ..., (3) где п — помер итерации, х, — заданное произвольно начальное приближение. Требуется найти приблиязенно В ь Рьпшпиг нГлипеин1 на углвквпяп О1 решение (корень) х = хе уравнения х = «р(х) с относительной погрешностью е ) О, так, чтобы при всех и > и, выполнялось неравенство )х„— х~! = а)х, — х*!, и ~ п,(е). (4) Ото условие может быть выполнено, если последовательность итераций (х ) сходится при п - к пределу хе;!пп х„ = х*.
Если (4) имеет место, то вычисления и можно прекратить при л =л,, Отсюда видно, что основным является вопрос о сходимости итераций, а также о скорости их сходимости, т. е. о минимальном чнслеитераций и,(е), при котором выполнено (4), Предположим, что в некоторой б-окрестности Л=(х,— б, х,+б), б) О, (5) точки х, функция фх) удовлетворяет условию Лнпшица: !~р(х" ) — фх')! < о!х" — х'! для любых х', х" ш Л (8) с коэффициентом д < 1: 9<9<1 (7) н пусть начальная невязка х„ — ~р(х,) мала, так что )х, — ~р(х,) ! -.= (1 — д)б.
(8) 'Тогда справедливы следующие утверждения: — все итерации х. (л = 1, 2, ...) принадлежат интервалу Л: х„ж йб — последовательность (х„) при и -~ 0 сходится к пределу хе, являющемуся корнем уравнения (8); — уравнение (2) имеет только одни корень в Ь. Условие х„ж Ь означает, что (х„— х„! < б. (9) В силу (8) имеем (х, — х,! = )ср(х,) — х;,! -= (1 — д)б < б, т. е. (9) выполнено при Й = 1, Докажем методом индукции, что (9) справедливо для всех й = 1, 2, ..., Предположим, что (9) выполнено прн й = 1, 2,..., и, тогда можно вычислить ~р(х„) и х,е, = ~(х.).
Иа (О) следует, что !х,,— х,! = Пр(х,) — гр(х„,)! < д!х„— х,,), т. е. !х„ь, — х.! < д(х„- х„,!. (10) Последовательно применяя зто неравенство, находим (х,ь,— х,! - д")х,— х,), й=1, 2, ..., п, (11) 1Я ХЛ. ПЬ РЕШЕНИЕ АЗП'ЕБРАИЧЕСКИХ УРАВНЕНИИ Учитывая, что х,+о — х, (х„+, — х„) + (х„— х,,) +... ... + (хо — хо) + (хо хо)о пол) чим ! х„чг — х )«(д + д + ... + д+ 1) (хг — х,! = !хг хо!» (хг "о!«б 1 я 1 о 1 Д 1 т.
е. х.+, ~Л. Так как неравенство (9) в силу (8) верно для )о = 1, то опо выполняется и для й = 2, 3, ... Рассмотрим теперь разность х„„- х, = (х„о..— — х,о» .) + (Х„,о, — х„+»+,) 1- ... +(х„о, -х„о,) + (х„.,— — х„) н оценим ее: ! хо~.» — хо ! «(Д + Д + ... + Д + 1) ! хотг — хо ! «» ~1 — о «! ! об т. е, !х., — х.(- О при п- и любом т=1, 2, ... Отсюда, в силу критерия Коши, следует сходп- мость (х„): 1пп х„= хо ИА. Переходя затем в (3) к предез в лу прн и-, убеждаемся, что х* есть корень уравнения (2): х*= ~р(хо). Этот корень единственный, В самом деле, пусть существует два разных корня х' и х" Фх, так что х' = <р(х'), Х" =х(х»).
Тогда )х" — х'! !<Р(Х" )— « ~х -х !, что невозможно. Для погрешности г„+, — — х»ы — х~ имеем !г.„! = !д (х.) — (р(х') ! ~ д)х„- х'!- = д!г„! < д"'!г,!, (12) (г.о~! ~ д +'(г„!, т. е. метод простой итерации сходится со скоростью гво- метрической прогрессии.
Число итераций, при котором выполнено неравенство (4), определяется из условия д «(е,т.е. п ) )л — ()п —. 1 о1 д' Мннггмапьное число я,(е) итераций, при которых (4) выполнено, очевидно, равно по(е) = ~)п — !1п — ~, 1/ 11 (13) где (а1 — целая часть числа а > О. з ь екшкник нхлинкиньгх твавнннии 1ЗЗ 3 а меч ание. Если фх) имеет производную на Л, то (6) выполнено в случае, когда )~р'(х)) == 7 для всех хш Л.
(14) 2. Метод Ньютона, Метод определяется формулой / (хо) х,е, = х„— —;м- —, /'(х„):фОг и = 0,1,2, ... (15) //' (х„)' Эта формула получается, если в разложенип О =- /(хе) = /(х„) + (х* — х ) /' (х„) + — (х" — х )з /" я), 5= х.-(-0(х* — х„), 0(8(1, (16) где х* — точное решение уравнения /(х) О, отбросить последний член, заменив х* на х„,,: 0 = /(х„) + /'(х„)(х„+, — х„). Метод Ньютона называют также ьчетодоз касательных олн .методом линеаризации.
Его геометрическая интерпретация — участок кривой у /(х) при хю(х., х„ч,), если х. (х„з, (пли прн х и (х„+„х.), если х. >х.е,), ааменяется отрезком касательной, проведенной из точки х = х,. Записывая /(х) = 0 в виде х фх), видим, что метод Ньютона можно трактовать как метод простой итераций (3) с правой частью гр(х) х — /(х)// (х). (17) Проиллюстрпруем метод Ньютона на примере навлечения квадратного корня пз числа а ) О, т. е. решения уравнения х' = а илп /(х) = х' — а =О. Применяя формулу (15), получим 1/ ат — 2 (х„+ — ~, л Пусть а=2.
Выбирая ха =1, найдем х, 1,5, х, -"* 1,417, х, = 1,414, ..., т. е. итерации сходятся очень быстро. Оценим скорость сходпмости итераций. Лредполо ким, что существует вещественный корень х* уравнения (1). Рассмотрим некоторую окрестность корня: е = (х — бю х*+ б,), б, > 0 Будем считать, что функция (17) дважды дифференцируе- )34 гл, пь Равнение лчгевгхичвсиих гглв!п5пий ма в й, п ее вторая ирои:июдиая ограничена; !гр" (х)! «2й/, (18) где г/ ) 0 — постоянная.
Разложим ср(,т) в строку Тейлора в окрестности х = х*: <р(х) =- ~р(х*) + ~р'(х*) (х — хг) .р ™ (х ха)г $ =. х* — ', 0(х — х*), 0 0(1. (19) Вычисляя затехг и замечая, что ср (х*) = 0 прп / (х*) Ф О, получим ср (х„) = юр (х") + ", ~р" (Б). (20) Для погрегпностп г„„=х„+, — х* получим формулу: г„.„= х,+т — х* — -- ~р (х„) — ~р (та) =- — (х, — х~)'-гр" (с), т г —:г = 2 й (ь) г ° Отсюда и пз (20) следует ) г„:,)(дг, (21) Ооозначая в, = р,'г„), получаем г„, «» г',,(» г„, ('...:6, »(... » «г1 » «гз, и, следовательно, )г; (( — (Ч(=О()г"' ' Ч (22) /)тсюда видно, что птерац|пг (15) сходятся к корню ха ири и —, если г/~г,) < 1 плп (г,! )х„— х*! ( 1/д, (23) т. е. начальное приблигиеняе находится в окрестности Л~ = (х* — 1/д, ха + 1/о) с 6, = 1/о корня х = х* уравпеяия (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
