Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 76
Текст из файла (страница 76)
Таким образом, здесь минимнзнруется функционал (г, г) в направлении, противоположном градиенту д р у г о г о функционала, именно функции ошибок, После выполнения первого шага процесс повторяется. Выведем формулы, связывающие соседние приближения. Пусть Ха, = Ха+ ~ага, тогда га „, — — га — раА»а. (2) Следовательно, (га,, га,,) =(га, г7) — 2~а(А»а, га)+~а(А»а, Ага) = (А7, га)а Г (Аг, г ) =(7'а га) — +(Ага, Ага) ~~а— (Аг, А7а) ' ~ (Агы Ага) ~ откуда следует, что (га.„, га„,) принимает минимальное значение (Ага' га)е (.477с 7а) равное (7'а' га) А А Ри Ра А А (Ага, Аг,) ' (Ага, Ага) ' Итак, рабочими формулами метода будут Ха,, = Ха+ 3„»а га = Г АХа = га-7 д»а-7А»а (Ага, га) (Ага, Ага) ' (3) 30 Зад.
97Е. Д. К. Фаддеев в В. Н. Фаддеева Теорема 77.7. 77оследоеательные приближения Хе, Х,, ... сходятся и решению системы АХ= г с быстротой геолеетричесной прогрессии, Справедливость теоремы будет следовать из более общей теоремы, которая будет доказана в следующем параграфе. В табл. ЧП. 3 приведено решение первого примера а 70. Быстрота сходимости процесса для данного примера такая же. как и в методе наискорейшего спуска. [гл. чп 466 ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ Решение системы линейных уравнений градиентным г1 = Р— АХг ХО го АХо х, 1.3808 1.227456 0.66299648 0.22033655 1О 1Н 1.2620108 1,851376З й 72.
Градиентные методы с неполной релаксацией Пусть по-прежнему А положительно-определенная матрица, и ищется решение системы АХ= Г. Рассмотрим итерационный процесс, в котором каждое последующее приближение получается иа предыдущего изменением в направлении, противоположном градиенту функции ошибок, причем так, что на каждом шаге функция ошибок уменьшается. Формулы для получения последовательных приближений, очевидно, должны иметь вид Х„,, = Х„+ таг„.
Для дальнейшего исследования нам удобно положить (2) Тя = ЙРа где ая соответствующий коэффициент в методе наискорейшего спуска. Имеем У(Ха+,) =((Хь) — 2та(га, г„)+та(Ага, г„)= =.7(ХА) — 2дрь(га, га)+Г7;'а;',(Аг„, гь) =- (гм га)Т ., (гь, г„)Т ((Х„) 712 т (гн гаР (3) 0.76 0.08 1,12 0.68 0.3616 0.0496 0.6576 ~ 0.3120 1.4070460 0.1481101 2.0735415 1.2589359 0,09054233 — 0 01! 82826 — 0.09746508 0.10237059 9 72) гвхдивнтныв методы с нвполной ввллкслцивй 467 Таблица (г77 3 методом с минимальными невязиами гг = го — 8о 4го Хо Агт Хто 0.04769058 0.17459165 10 Из этой фоРмУлы Ясно, что длЯ того, чтобы 7" (Хоо,) было бы меньше, чем 7'(Х„), необходимо и достаточно выполнение для множителейй Релаксации ~То неРавенств 0(9 С2.
(4) Будем называть группу методов, в которых не все до равны 1, методами неполной градиентной релаксации (одношаговыми). Если все множители релаксации до (1, но не все равны единице, метод назгивается методом н и ж н е й р е л а к с а ц и и, если все до)~1, но не все 17„.=1, — методом ве р хне й релаксации.
Так, л~етод с минимальными невязками является методом нижней релаксации, нбо в нем (Агы го)о оо (Агь. Аго)~гы гл) (5) по неравенству Коши — Буняковского. Здесь знак равенства возможен, только если г„есть собственный вектор матрицы А. В группу методов неполной релаксации входит и градиентный метод с п о с т о я н н ы м множителем Т„= Т, если зтот множитель удовлетворяет неравенству (6) где Л4 наибольшее собственное значение матрицы А. 0.09054233 — 0.01!82826 — 0.09746505 0.10237059 0.06822351 — 0.00194231 — 0.08875643 0.07016581 1.5213114 0.1331827 !.9505396 1.3881287 1.5349632 0.1220091 1.9751557 !.4129543 1.5349648 0.1220099 1.975!558 1.4!29551 468 [гл.
Тп ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ Действительно, в этом предположении О(дь — — - — = ' ( ТЛ (2. Т(Ага, га) «А (( Ь га) 2 Условие О ( т ( — является так же необходимым для того, чтобы М функция ошибки уменьшалась при любом начальном векторе. Действительно, О ( д„( 2 дает (Агь гл) < 2 т (гь гь) откуда О « (2юЬ га) (Агь гк) Так как последнее неравенство должно выполнягьсн при всех должно быть выполнено неравенство О<Т(ш(п — ' 2(а, г) 2 (АР, х) М' Заметим, что градиентный метод с постоянным множителем есть не что иное, как процесс последовательных приближений, примененный к системе, подготовленной следующим образом Х= — (Š—,А) Л'+1Е. Необходимые и достаточные условия сходимости метода совпадаю~ 2 с условием О ( Т ( —.
Действительно, наибольшее по модулю соб- М ственное значение матрицы Š— ТА будет большее по модулю из чисел 1 — ТМ н 1 — Тт. Таким образом, для сходимости метода последовательных приближений необходимо и достаточно выполнение неравенств — 1(1 — Тт <1 — 1<1 — ТМ<1, 2 2 откуда следует, что Т) О.
-( — и т ( —. Выполнение третьего т М ' неравенства обеспечивает выполнение второго. Наибольшее по модулю собственное значение матрицы Š— ТА будет наименьшим из возможных, если 1 — Тт= — (! — ТМ), т. е. 2 М вЂ” т если т= .
В этом случае 1 — Тт=, Следовательно, т+М ' М+т ' быстрота сходимости при таком выборе множителя Т будет оцениваться неравенстом 1у»~ <("+„)" ~,~ $ 72[ ггьдивнтныв методы с нвполной вильксьцивй 469 при Теорема 72.7. Если в процессе неполной градиентной релаксации мноокители релаксации удовлетворяют условию е ( дь ( ( 2 — е, 0 ( е ( 1, то процесс сходится к решению со скоростью геометрической прогрессии. Доказательство. Пусть Մ— и-е приближение методз неполной релаксации, удовлетворяющего условиям теоремы.
Обозначим через Х„„ приближение, получающееся из Х„однньг шагом метода наискорейшего спуска, через Уьь, и гь„— соответствующие векторы ошибок. Как мы видели выше 7(Хьь,) ( т)'(Хь), =( +-)' 7 (Хь) — 7(Хь „) )~(! — г) 7(Хь). где Следовательно, Далее .г (Хььг) = 7 (Хь) — (2с!ь — г7ь) ( ! ' откуда У(Хь) — УРан) = (2йь йь) А — — (2йь гф [7 (Хь) — 7 (Хььг)!, ибо (г г)я [(Х) 7'(Х ) ( ь ь) Таким образом, 7 (Хь) — 7 (Хь„) > (2аь — а!) (! ) 7 (Хь), н потому 7(Ль+г) ( [! — ~27, — д~~) (1 — т)]7 (Хь) ( [1 — (2з — зг) (1 — г)[ У (Хь), Положим т = 1 — (2е — гг) (1 — ), ь) И.
П. И а т а н с о н [1[. т. е. имеет тот же порядок, что и в методе наискорейшего спуска' ). Вся группа методов неполной релаксации (включая и случай полной релаксации, когда все оь = 1, что соответствует методу наискорейшего спуска) естественно укладывается в обшую схему итерационных методов, описанных в главе П!. Именно, онн получаются из общей итерационной формулы Х„,, = Х„+ Н'"+" (Š— АЛ;,) 470 гглдивнтнгяв итвгационныз мвтоды 1гл. чп Ясно. что 0(т,(1, ибо 0(2е — ез(1, 0(1 — с(1. Из последнего неравенства следует, что 7(Ха„) (т,"7(Ха). (7) Таким образом, при )г-+со 7'(Ха)-ь0 со скоростью геометрической прогрессии, !'а — +О и Ха-+Х*.
Теорема доказана-. Из доказанной теоремы следует, в частности, сходимость метода с минимальными невЯзками, так как в этом слУчае множители 9а удовлетворяют неравенству е (~)а«(1, где е= Действительно 1з йа (Ага, га)з (А'га, А ага) (ц г)з аа (Ага, Ага)(га, га) 7 з 1 1( ~ ~ ! (Аг, а) (А-тг, з)' ~А 'га, А ага/~А ага, Азга/ Здесь г=Азга. Поэтому в силу неравенства (9) В 70 имеем Неравенство да (1 было уже отмечено. Быстрота сходимости метода при таком способе доказательства сильно занижена. В упомянутой выше работе М. А. Красносельского и С. Г.
Крейна установлено, что быстрота сходимости имеет тот же порядок, что и в методе наискорейшего спуска. В оценке (7) никак не учитывается, будет ли на данном шаге да больше или меньше 1. Есть основание предполагать, что если применяется верхняя релаксация, приведенные оценки не являются существенно завышенными. Для нижней релаксации они, по всей вероятности, являются завышенными, так как при нижней релаксации ломаная с вершинами в последовательных приближениях будет теснее примыкать к линии наискорейшего спуска, чем аналогичные ломаные для полной и верхней релаксации. В вычислительном отношении удобно брать множители релаксации да не зависящими от л. В табл.
ЧП.4 и ЧП. 5 приводятся результаты вычисления решения системы (9) ф 23 грздиентным методом с применением неполной релаксапми при 9=0.8 и 9=1.2. Из таблиц видно, что в данном примере нижняя релаксация приводит к решению быстрее, чем полная (табл. ЧП.2), а верхняя медленнее. 9 72) гглдивнтныв мвтоды с няполной гвллкслцивй 471 Таблица !гП. 4 Решение системы линейных уравнений градиентным методом с неполной релаксацией при а = 0.8 0.2020700 0.0435581 0.0434876 0.0434873 0.2828980 1.0390689 1.0391658 1.0391662 0.1212420 — 1.25749!9 — 1.2577926 — 1.2577936 0.3637260 1А822318 1.4823922 1А823928 Х1 Х11 Х Хав Таблица !1П.8 Решение системы линейных уравнений градиентным методом с неполной релаксацией прн ц = 1.2 В заключение этого параграфа рассмотрим метод, являющийся предельным случаем для метода верхней релаксации.
формулы метода ') следующие Х„а, = Х„+ 2а„гь, где ал коэффициент метода наискорейшего спуска. В этом случае функция ошибок от шага к шагу не уменьшается и последовательные приближения не стремятся к решению. Однако, если начальное приближение не ортогонально к собственному вектору, принадлежащему наибольшему собственному значению матрицы А, то последовательности Ха, Х,,... и Хн Х,, ... сходятся.
При этом полусумма пределов этих последовательностей дает решение системы, а полуразность есть собственный вектор, принадлежащий наибольшему собственному значению. Доказательство соответствующей теоремы читатель найдет в упомянутой работе В. Н. Костарчука.') 1) В. Н. К о с т а р ч у к 11). Х1 Х18 Х« Х11 Хы Хш 0.1818630 — 1.2251212 — ! .2551442 — !.2566377 — 1.2577672 — 1.2577904 0.3031050 0,0452191 0.0436275 0.0437154 0.0434887 0.0434875 0.4243470 1.0164571 1.0373248 1.0386884 1.03'.!! 478 1.0391640 0.5455890 1А498670 1.479?554 1.4816669 1.4823665 1.4823896 472 (гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
