Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 75
Текст из файла (страница 75)
Выбирается произвольный вектор Х,. Вычисляется направление, противоположное градиенту функционала Н(Х) (нли, что то же самое, градиенту функции ошибки) в этой точке, которое совпадает с направлением невязки го = г" — АХ, выбранного начального приближения. Из точки Хо мы двигаемся в выбранном направлении до точки Х,, в которой функционал Н(Х) становится минимальным. Так как 458 [гл. чп ГРАДИЕНТНЫЕ ИТЕРАЦНОННЫЕ МЕТОДЫ и процесс продолжается далее по формулам Ха„, — — Ха+ ааг„ га-— — Р— АХа — — га .,— 11а Агаан где (га, га) "а =— (Ага, га) ' (б) При этом (г, г„)г [(Х„.,) = [(Х„) — — ' (Ага, га) ' Заметим сразу, что прн фактическом проведении процесса векторы га, особенно при большом порядке матрицы системы, удобнее вычислять по формуле га —— — г„, — аа,Ага о Однако, вследствие ошибок округления, тзк вычисленные векторы га после нескольких шагов процесса могут начагь отклоняться от истинных невязок г" — АХА.
Поэтому следует время от времени вычислять векторы га по формуле га=г — АХа. Теорема 7О.У Последовательные приближения Хе, Х,, Хг, ... сходятся к решению системы АХ= г с быстротой геометрической ирогрессии '), Доказательство, Покажем прежде всего, что последовательность значений функции ошибок стремится к нулю при я -+ со.
Имеем У(Ха,!) — ПХа) =— (гм'гар (Агм га) ' С другой стороны, Г(Х1г).=(А 'га, га). Поэтому г(ха -1) 1 (га' г1)г У(Х1г) (А 11'а га)(Ага га) 7(Хат1) ("а "а)е — 1 7(Х ) (А 'га, га) (Ага, га) г„=с,(у,+ ... +с„и„, т) Л. В, К а н т о р о в и ч [2[. Оценим снизу вычитаемое в правой части последнего равенства, Пусть Л, (), ( ...
(Л„собственные значения матрицы А, Уг, Уг, ..., У„принадлежашие им собственные векторы, ортогональные друг к другу и нормированные так, что ((гн (г'1) = 1 при ! 1, ..., и. Так как А положительно определена, все Л; ) О. Пусть т (Л,, Л„(А4. Пусть далее й 70) метод нйискогейшего спяскй для гашения линейных систем 461 Оценим теперь длину вектора ошибки, т. е. вектора У„=Х вЂ” Х„. Так как 7' (х„) = (А У„, Уй) ) лй ! Уй !2, < /у(х.«(м— то (12) Тем самым доказано, что ( Уй~ стремится к нулю со скоростью геометрической прогрессии. Теорема доказана. Оценке для 7(Х») можно придать несколько иную форму, если Лч ввестн в рассмотрение Р-чнсло обусловленности, т. е.
число р= — ". Л Именно, можно принять, что т=Л,, с«4= — Л„. Тогда т(Х„) <(,'" л„') 7(Х,)=( — ',') у(Х,). (1И) ~Х вЂ” Х„,~<1Х' Х„~. Иначе говоря, длина вектора ошибки при переходе к новому при- ближению строго убывает. Действительно, Уй+, — — Уй — айгй н, следовательно, .( «й+,, «й й,) = (1 го Ус ) — 2яй ( Уй, г») + ай (гй, гй) = "й "( й'сй)( й' сс) 2 =(Уй, Уй) — ей(У», гс,) — — ~ ' — (гй сй)' (;;)~ — (у„у,) — ей(У„, сй) — " 1(У»с, г„)(Агй, гй) — (гй.
г»)1. Покажем, что (Уй, г„)(Аг„, г„) — (гй, гй)2) О. Положим А=В', где В положительно-определенная матрица. Тогда (Ую гй) (Агй, г») — (г», г»)2 =(А йгй, гй) (Агю г») — (гй, г„)2 = =(В гй В гй))(Вгй Вгй) — (Вгй В 'гй) )~ 0 Отметим два свойства приближений Хй метода наискорейшего спуска. 1, Невязкн двух последовательных приближений ортогональны друг другу. Действительно, г„ , = ㄠ— е»Ас.й, откуда (г„+,, гй) = (гй, гй)— — ей(Агй, гй) = 0 на основании определения ой. 2. Каждое последующее приближение ближе к точному решению, чем предыдущее, т. е.
462 (гл. чп ГРЛДИЕНТНЫЕ НТЕРЛЦИОННЫЕ МЕТОДЫ в силу неравенства Коши — Буняковского. Таким образом, (!о+о ~'ь+!) ~((га, уа) — аа(гь, гь) < (ую 'га). ибо еь) 0 и (1'о, га) =(А)'ю 1'„) ) О. Наконец, из сравнения соответствующих формул вытекает, что приближение Хаю совпадает с первым приближением метода сопряженных градиентов, проводимого из начального приближения Х».
Решение системы линейных уравнений г, = го — «оАго А го го 1.4245790 О. ! 499557 2,0993795 1.2746233 1.3808 2.3008 1.227456 1.8744460 Приведем примеры применения метода наисеоэейшего спуска. П р и м е р 1. Решим систему с матрицей 0.78 — 0.02 — 0.12 — 0.14 — 0.02 0.86 — 0.04 0.06 — О.!2 — 0.04 0.72 — 0.08 — 0.14 0.06 — 0.08 0.74 и свободным членом (0.76, 0.08, !.12, 0.68)'.
В табл. ч!!. 1 приведено начало вычислительного процесса (чтобы пояснить вычислительную схему метода) и результаты последующих шагов. Здесь в первой части таблицы записываются последовательно векторы Хо го Аго во второй — результат контрольного вычисления по столбцовым суммам для Аг,, в третьей — соответствующие скалярные произведения (го гг) и (Аг;. го), в четвертой — коэффициенты ео Для сравнения вектор г, вычислен двумя способами. 0.76 0.03 1.12 0.68 0.36!6 0.0496 0.6576 0.3120 0.08220033 — 0,01297252 — Од 1263569 0.09517285 9 701 метод нлискогейшего сптска для вешания линейных систем 463 Сравнение хода процесса наискорейшего спуска с результатами вычислений по методу последовательных приближений и циклическому одношаговому процессу показывает, что в данном примере метод наискорейшего спуска сходится быстрее.
Именно, восьмой шаг метода наискорейшего спуска дает лучшие результаты, чем десятый шаг в обоих упомянутых методах. Десятый же шаг лает решение уже с точностью до 1 10 '. Таблица Ь'11. 1 по методу нвискорейшэго спуска Х, Х, гг = Т вЂ” АХ~ Аг~ Хоо 0.08220030 — 0.01297254 — 0.11263567 0.09517284 0.03107890 0.02277678 0.02866984 1.2587313 В качестве 2-го примера рассмотрим решение системы (9) 9 23. Результаты, полученные по методу наискорейшего спуска, помещены в табл.
ЧП.2. Таблица )г11 2 Решение системы линейных уравнений по методу наискорейшего спуска 0.3536225 0.4546575 0.1515525 0.2525875 х, 1.4786412 1А820379 1.4823232 1А823900 1А823928 — 1.2546235 — 1.2573084 — 1.2577348 — 1.2577912 — 1.2577937 х х Хга Хоо 0.06456777 — 0.00258459 — 0.09805664 0.06715236 1,5280471 0.1336268 1.9576015 1.3944203 0.0434210 0,0435634 0.0434859 0.0434873 0 0434873 1.5349633 1.5349634 ОЛ220118 0.1220090 1.9751502 1.9751560 1.4129515 1.4129545 1.0365064 1.0389273 1.0391170 1.0391642 1.0391662 !.5349650 0 1220097 1.9751560 1.4!29552 [гл. Ин ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ Теоретические оценки быстроты сходимости метода наискорейшего спуска показывают, что с возрастанием числа обусловленности матрицы коэффициентов сходимость метода наискорейшего спуска быстро замедляется.
Оказывается, что теоретические оценки почти не являются завышенными, и в действительности процесс очень медленно сходится дзже при не очень больших числах обусловленности. Так, в последнем примере Р-число обусловленности 10. Методу наискорейшего спуска можно придать следующую геометрическую интерпретацию. Рассмотрим в л-мерном пространстве семейство поверхностей 7" (Х) = с, Рис. 7. где 7"(Х) — функция ошибки. Это семейство есть семейство подобных эллипсоидов.
Процесс наискорейшего спуска геометрически может быть объяснен так. Через приближение Хе проводится эллипсоид У<Х) =Х,, в точке Хе проводится нормаль к этому эллипсоиду и затем в семействе находится эллипсоид, касающийся этой нормали. Точка касания %' будет следующим приближением. Для и = 2 геометрическая картина показана на рис. 7.
Геометрически очевидно, что если эллнпсоиды семейства вытянуты в одном направлении и какое-то приближение попало довольно близко Рис. 8. к большой оси, то и последующие приближения будут близки к концам больших осей подобных эллипсоидов. Так, для п = 2, если начальное приближение находится в точке, нормаль к которой образует угол в 45' с большой осью соответствующего эллипса, то н для всех последующих приближений угол между нормалью н большой осью будет равняться + 45' (рис. 8).
Нетрудно убедиться (для И=2), что именно при таком выборе начального приближения сходимость процесса будет самой медленной н быстрота сходимости будет совпадать с теоретической оценкой. й 71) гвадивнтный метод с минимдльнымн нввязкдми 465 5 71. Градиентный метод с минимальными неаязками Этот метод описан в работе М. й.
Кр асносельского и С. Г. Крейна [11. Пусть А положительно-определенная матрица, Хе начальное приближение к решению системы АХ= Г. Следующее приближение Х, ищется, так же как и в методе наискорейшего спуска, в виде Хе+рге, но параметр р подбирается так, чтобы минимизировалзсь длина вектора невязки ~г! или, что то же самое, (г, г)=~»1е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
