Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 77
Текст из файла (страница 77)
Тп ГРАДИЕНТИЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ $73. е-шаговые градиентные методы наискорейшего спуска В предыдуших трех параграфах мы рассматривали одношаговые градиентные методы, связанные с полной или неполной релаксацией функции ошибок и установили, что нзилучший результат за один шаг дает метод наискорейшего спуска. Естественно поставить вопрос о том, как опРеделить множители Тп..., Т, с тем, побы, исходЯ (о( из начального приближения Х( ~, получить наилучший результат после з шагов процесса и как объединить эти з шагов в один шаг нового вычислительного процесса.
Иначе говоря, как построить вычислительный процесс, один шаг которого равносилен з ша~ам одношагового градиентного метода, выбранным согласно наилучшей стратегии. Пусть Х,=Х(" Х, =Х,+Т,(Š— АХ,) Хв — Х, + Т, (~ — АХ,) Х(Н=Х,=Х,,+Тв, (Р— АХ,,). Тогда, переходя к векторам ошибки, получим ~'в= Уо — Тодро=(Š— То4) Уо Уг = ) в — Т1АУг = (Š— ТвА) ) в У ' = Ув = Ув-г — Тв-гА) в-в = (Š— Тв-вА) У -г (н откуда У(П = (Š— Тод)(Ф вЂ” Т„4) . (Š— Тв-вА) ~'о = =(Е+с,А+свА + ...
+с,А') Уо= =)'о+с,го+ ° .. +свА' го где го= Р— АХ( ~ Х =Х вЂ” сгго — .. — с,А го. и) (о> в-г (4) Таким образом, задача сводится к определению коэффициентов с,..., с, так, чтобы значение г" (Х(П) функции ошибки было бы наименьшим. Эта задача была уже решена ранее в 9 69 при изучении метода сопряженных градиентов.
Действительно, на стр. 445 было устано- $73) 8" шлговые гвлдивнтныв катоды нлискоевйшего спяскл 473 влено, что з-е приближение метода сопряженных градиентов минимизирует функцию ошибки среди векторов Х(о)+(г, где вектор принадлежит подпространству, натянутому на го, Аго,..., А' 'го. Итак, результат одного шага з-шагового метода наискорейшего спуска совпадает с результатом з-го приближения метода сопряженных градиентов. Именно, Х(1) Х!0) + Х а 87 (б) где а =го (6) з) ч-~ = ) ) + п|е) Поэтому при фактическом проведении з-шагового метода нзискорейшего спуска нам не нужны ни коэффициенты с,, ..., с„нн, тем более, коэффициенты 7о..., 7о. Однако нетрудно отдать себе отчет в том, что представляют собой те и другие коэффициенты.
При рассмотрении метода сопряженных градиентов было показано, что го = — г, (А) го Уц) = ), (А) 1'! ), (7) и, следовательно, где г, (Г) полипом и" 69, п. 3. Но, с другой стороны, Г~'~=(Е+с)А+ ... +с,А') Го. Следовательно, 1 + С~! -)- ... + Сот = Го (Г), т. е. коэффициенты с,,..., с, суть не что иное, как коэффициенты полинома го(Г). Далее, из равенства (1 — 7оФ)(! — 7,1) ... (1 — 7о гт)= !+с,(+соР+... +со!о=го(С) следует, что линома г (С).
Отметим, рекуррентно цесса может не все числа (ап гг-)) (г)-), г;-)) г;=г;,— п,Аап и,= ' А —— 'А (гп зе) (сн зг) (гг гг) () г Ао)) ь)=— (г; и го,) (з), Аз)) (1= 1, 2, ..., з — 1). числа 7о, ..., 7, , суть числа, обратные к корням по- что если вместо формулы (5) вектор Л.) вычислять . (!) по формулам ( 1 ), то на некоторых шагах этого пропроизойти даже увеличение функции ошибки, так как 7о. .. 7, , обеспечивают релаксацию .
[гл. чн о' СЧ «0 О\ 0 «0 С ф СЧ Чс «0 <:~ сч о о о «сч с о яро ~Й 'о о сс сч о о «0 С' «0 СО о '«СЧ «0 ОЪ Б С С СО Сс сч о о 0 СС. «0 СО ' о и О и сс О. сч о о о о СО О со о СО СО 00 СО СО о й и и и и С.) и й О О сс и и ОР о 00 Со о со о 0 СО О СЧ О о СО о о с о: со о сО сО сО о ь о г о со О «0 8 Я «0 СЧ о Ы о о о СЧ СО оЙ й о о о о СО с 0 о со Сс О о о СО О~ Со Я Я -.
о. о о о о о 8 Р О «О «0 о о о о о о ~- СЧ Й О сО сО о о о о о оооо СО «о СЧ о сч о о с1 00 С' 04 СЧ С О Со СЧ СО С' СЧ С С СЧ СЧ СЧ Ф СЧ С' О сО о О й 11 С 10 о ' о СО О «с О о о о о сО «0 С-.. оооо о о оо ооо о ф М О О Ф Б СС О. О М 2 СС О С О и си з Ю О сс и и и 0 Фи гглдиинтныя итигиционныи иитоды о О О О С Н си О о О и ж сс О С( О и Ю и 9 73! э-шлговыв гглдиентные мвтоды нлисковвйшего спгскл 475 (го го) — (го Аго) с, — ... — (го А"го) с, = 0 оэ1 (го Аго) — (го, Азго)с1 — ..
— (го А го)со=О (го '4 го) (го '4 го) со ... — (го, .4 го) со = О (8) Лля каждого последующего шага начальная невязка г должна быть заменена невязкой, полученной в результате предыдущего шага. Рассмотрим применение дзухшагового метода для нахождения решения системы (9) 9 23. Вычисления по разным схемам приведены в табл. Ч!!. 6, Ч!!. 7 и т'!!.8. Таблица $ЧД8 Лвухшаговый метод наискорейшего спуска. Схема с решением систем Х10 Хгй Х10) Х1з> Хнз Аого Аго го — 1.2648177 — 1.2572769 0.0650098 0.0434889 1.02201! 9 1.0387865 1.4854642 1.4818605 З.Я564 2.90652 2.74284 3.26676 0.3 0.5 0.7 0.9 1А82 1.246 1,220 1.472 — ! .2577 994 0.0435034 1.
0391674 1.4823838 — 1.2577931 0.0434873 1.0391657 1А823923 12.55176 5.420 1 Действительно, если э=л и аа 7о пРинЯть число —. з аа го л, (го го) 1 вектоР У„. то по= = —,, 7о=доао=до)а, так что Чо= а (Аго го) го ' = 1" —— р и потому оо > 2, если р) 2. 1 Вычисление приближения Х. можно проводить и пользуясь метод! дом А-минимальных итераций. Действительно, как мы видели (стр, 445), последовательные приближения, полученные по этому методу, при ро=го совпалают с соответствУющими пРиближеннЯми метода сопРЯ- женных градиентов.
Многошаговый метод наискорейшего спуска впервые был описан в работах Л. В. Канторовича (2), [3!. В этих работах для составле- ния последовательных приближений фактически находились коэффи- циенты с,, ..., с, посредством решения системы з линейных уравне- ний. Эта система для перво~о шага имеет вид 476 [гл. Тп ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЪ! Для нахождения Х") в табл. Ч!1. 8 вычисляем коэффициенты с, и с иа системы уравнений 3.2464с, + 7. 404024с, = 1.64 7А04024с, + 17.164478са = 3.2464.
Это дает с, = 4.5542139 с = 1.7753589. При а ) 2 1-я и 2-я схемы предпочтительнее, так как в последней схеме на каждом шаге процесса нужно решать вспомогательную систему линейных уравнений. Так же как и одношаговые градиентные процессы, а-шаговый метол наискорейшего спуска можно включить в общую схему итерационных процессов Х<Ю вЂ” Х!а Г) ! Н)а) (7, АХГŠ— г)) НГ )= Н„ )(А) полагая при (9) Действительно, уы) <а),!Е-)),га-1)+( 00 ) <а г) Отсюда Х =Х ~+(Š— г~ )(А)) у!~ ~)=Х1~ ~)+-Н~)~)(А)АУ)" =Х! )+Н~ )(А)(Р— АХ!" 'Г) (! 0) и, следовательно, Ясно, что полиномы Н~ ~(!) алесь меняются от шага к п)агу.
)а) Установим теперь сходимость г-шагового процесса наискорейшего спуска и оценим быстроту сходимости, Прежде всего заметим, что один шаг а-шагового процесса наискорейшего спуска дает не худший результат в смысле уменьшения функции ошибок, чем э шагов одношагового метода наискорейшего спуска. Отсюда непосредственно следует, что а-шаговый метод наискорейшего спуска сходится. и для функции ошибок имеет место оценка й 731 а-шлговыв гелдиентные методы нлнскоеейшвго спгскл 477 Х~ 1=Х~ 1+На(А)( — АХ1 1), (12) где Н,(() некоторый полипом степени а — 1. Ясно, что каков бы ни был полипом Н,((), каждый шаг а-шагового метода наискорейшего спуска будет обеспечивать не худшее уменьшение функции ошибок, чеч один шзг, проведенный по формуле (12), исходя из предыдущего приближения метода наискорейшего спуска.
Пусть Х~ зто приближение, Л" следующее прн1а-1) ,ию ближение а-шагового метода наискорейшего спуска, Х'ю = Хт"-"+ Н, (А) ( — АХ'"-") (13) Пусть далее г'~ ~, Г' 1 и Г~ ) соответствующие векторы ошибки. 1а- Ю бй -Ы> Из формулы (13) следует, что угю Ф (1 „,1а-и где Ф (г) = 1 — (Н (г). Для оценки функции ошибки положим, как это делалось неоднократно, А =- Ва, где В положительно-определенная матрица.
Тогда 7(Х~ 1) = (Ау1 1, К1 1) = (ВУ1 1, ВР 1) = ~ В(Г1 1) ~ . В Г '=ВФв(А) )'~" '1= Фа(А)ВГ~" '~, Но и потому !ВР~ 1(=(Ф (А) ВУ1 '1! </(Ф (А)/~ )ВУ~ '1(. (7, = ~! Ф, (А) )! . 7(Хгю) < д,'7(Х'"-'>) 7(хйо) < а' 7(х'"-н). Пусть Тогда (14) (15) и подавно (16) Матрица Ф,(А) — симметричная, так что ее норма с(, равна наибольшему нз модулей ее собственных значений, которые равны, очевидно, Ф,()ч), ..., Фв(Л„). Полипом Ф,((), очевидно, обладает свойством Ф,(0) =-1, его стелень равна а, в остальном он произволен.
Мы получим наилучшую г) М. Ш. Б и р м з н (11. .Однако для а-шагового метода наискорейшего спуска можно дать и лучшие оценки '), сравнивая его со стационарным итерационным процессом 478 (гл, ми ггвдивнтныя нтввлционныв мвтоды сов в агссов сов в агссов тв (17) причем максимум отклонения равен Е,= гпах ~ Т,(е) ~— ! сов в вгс сов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
