А.А. Самарский - Введение в численные методы (1113832), страница 20
Текст из файла (страница 20)
Если же А = Аа ) О, то верны оценки ~!гв (((ра~!гв(~, 1(Лу„— )) =рЦЛуа — й (4) 2 Где гм п тв — точные границы спектра оператора А, В самом деле, так как прп значения т, 1 согласно (3) норма 11г,,11 минимальна, то прп любом татаа, она должна возрастать, поэтому 11гв+ 11 = 11гв тв ЛГР 11гв таАг„11 К 11Е т АР11г 11", С другой сторонвз, язвестно, что 11Š— таА11 = ра при т, = 2Пу, + аа). Отсюда и следует, что '1г„+,11 ~ р,11г,'11. 1зз Гл пь Гвюлннв хлгввохнчкскнх углвнвпнн Таням образом, метод минимальных певязок сходится с тон ьке скоростью, что и метод простой итерация (еслп в методе простой птсрацпп пспользулгтся точные значения 7,п бо), В случае неявного метода певязок, нлп летоба поправок, вместо (1) получаем уравнение для поправки: В»+» +Лир»=оо »=0,1, т» ю» гг 1» ~со Е (Ауо 7)1 (б) где т,+, определяется по формуле ( пг»,;,) (В 'Ам», Ай») (6) (о- — — О, 1, Вместо (4) получаем оценку ~~АУ» — 71в-» ~~ро(ЛУо — Лв-» 2.
Метод скорейшего спуска. Лвный гзетод скорейиоего спуска отличается от метода мпннмальных невязок то»о.- ко формулой для т»ю: (г,, г,) т»о»=-- ~,, А==0,1, (Агю г») ' (7) (Лг»о и г»о») = (А㻠— т»».»А гю 㻠— т»»»Лг») = = (㻠— т»отЛгю 㻠— т»»,г») = (гто г»)— — 2т»о»(г», г») + т»о, (Лг„г„). Дпфференцпруя (гав.,()»о по т,, п прправпивая пропзводную нулю, получим (7). Далее, имеем (! г»о»(л = "„(Š— т»+,А) г»)(", (1(Š— тЛ) г»((»г ( ~. 1Š— тоЛ 1»1г»'1'» ~ «Ро'(г» 1А, Эта формула получается либо из условия минимума нормы 1г»о,1~ погрешпостн г„о, = у„о, — и, либо нз условия ортогональностн певязок г, н г»оо Уинояоая скалярно уравнение г»»1=㻠— т»+1Лг, на г„получаем 0 = (г,, г„)— — т„+,(Аг„, г,), откуда следует формула (7).
Поскольку Лг,=Ау,— Аи= г„то 1 6 ВАРиАционнолгткРАционньгк методы 129 Ву, = ( — т,А)у„+ т,й Мы рассмотрим жвгод сопряженных градиен сов, широко используемый на практлпте. Для него итерационные параметры ало, и тоы определяются по формупам (ол, ъа) тлел (гл '"л) — "=('- — ' — — Г' (Аил, ио) ' (РА л,ил л) ал / (9) где й=О, т, 2... в цредполощепип, что А =Л*)0, В = В* > О, "(,В < Л < (,В, "(, > О. Формулы для тлло ал,, поолучалотси из требования минимума нормы разреша1ощего Оператора. )1ри этих оптимальных значениях итерационных параметров верна оценка 2Ро Чо. 1 + Р;" 1 — М 1 '-Уй ' ~~ у„— и((А(о„!~у — и(,'А — (10) т т, е.
скорость сходимости метода сопряткенпых градиентоз — такая гке, как н скорость сходкмостп двухслойного итерационного метода с чебыпгевскими параметрамк (которьгй использует (, и (, при вычислеилш1 параметров тлл,). Поэтому для числа итераций имеем оценки по (е) «( п (е) ~ по (е) + 1, п, (з) = =! п —. 1 2 Б качестве оператора В мокино взять факторизованный оператор поиеременно-треугольного метода В = (В + ыЛ,) В ' (В + о>Ло), А,+А„— А~О, Л,'=..Лм Ю=ЮА>0.
1 А+ Ь= !(ул- — НЬ <ро ~!уо — и(~:. Метод скорейптего спуска сходится в Н* с той яое скоростью, что и метод простой итерации. 3. Метод сопряокеиных градиентов. Более быстро сходящиеся методы варнацпонного попа мояоно найти в классе неявных трехслойных итерационных схем: Ву,з: = а„,( — т,+,А)у„+ (1 — а„,)Ву,, + +ал ~т,л,(, й=(,2, ..., (8) гас гл. пп Ргшвпне Алгевгапческих УРАВненпп Расчеты показывают, что число итераций по попеременно-треугольяому методу в сочетании с методом сопряженных градиентов меньше, чем в случае использования чебышевской схемы.
$ 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) Проиллюстрпруем метод Ньютона на примере навлечения квадратного корня пз числа а ) О, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
