Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 73
Текст из файла (страница 73)
Ио, в силу теоремы 68.3. (гн я„) = О при й ( С в частности, при /г = 1, ..., /+ !. Из доказанной теоремы следует, что если гь чь О, то г„ не может быть линейной комбинацией невязок гз, ..., гь о так что обрагцение невязки в нуль является единственной причиной остановки процесса. 442 (гл. ч» метод минимальных итаглций следует г» = г»,— а»Аао (7) причем а» ~ О, ибо г;, чь г». Допустим, что мы уже построили векторы гп ..., г» и га, ..., г;. Покажем, что следующий вектор направления а»~, строится по формуле л»,,»=г»+а»а», (8) где (г», АаД (а», АаД Для того чтобы убедиться в этом, достаточно доказать, что так построенный вектор а»+, будет А-ортогонален к векторам зп Ясно, (э»е» Аа») =(г» Аа») — ' 1 ' (а», Аэ») = О.
Рассмотрим теперь (г»+„Аа;) прн /=1, 2...,„1 — 1. Прел»де всего отметим, что (з,+,. Аг )=(го Аа»). Далее, по формуле (7) 1 имеем Аз» вЂ”вЂ” — (г»,— г»), так что а» 1 1 (г»+„Аа ) = — (г,. гу,) — — (го г») =О а» в силу того, что 7'(О / — 1 <1 и невязки ортогональны. Итак, формула (8) справедлива.
Отметим, что вычисление коэффициентов а» и Ь» можно производить и по формулам а (»Ч г»-г) (г»-и г»-») а»= (гч А,») = (а» А,») ь (») (г» и г»-») ' (9) справедливость которых легко устанавливается, При практическом применении метода коэффициенты следует вычислять по формуле (г»», г»») а»вЂ” пользуясь формулой (»в г»-») (аь Аа») В»введем теперь расчетные формулы процесса. Заметим, прежде всего. что из формул Х» = Х», + а зп а; = (б) (Аа», а») $ 69] некотОРые методы сопРЯженных нАпРАВлений 443 для контроля.
Формула же (гр ~») чувствительна к ошибкам округления и ее применение нецелесообразно. Таким образом, расчетные формулы метода сопряженных градиентов таковы. Выбирается произвольное приближение Хр к решению системы АХ= г и вычисляется невязка гр =- г' — ЛХр. ))алев, по рекуррентным соотношениям »р г», — а»Лг» (г»-» 㻠— ») (з» г»-») (а», Аз») (г», А»Д г» + Ь»з» (гр г») (г», ААД (19) (г» Р г»») (г», Аа») строятся векторы направлений яо ею ... и невязки г,, г,, ... Процесс заканчивается тем, что при некотором т (п окажется г =-О.
Решение системы получается по формуле Х = Х + «~'„» а»з». (1 1) Как правило, процесс протекает без вырождения, так что»н=л. Контроль вычислений производится при помаши вычисления ска.чярных произведений (з», Лг») нлн скалярных пронаведеннй (гн гу), которые должны быть нулями. Из формул (10) видно, что вычислительная схема метода сопряженных градиентов близка к двучленной форме метода минимальных итераций. В табл. Н!.19 приведено решение системы (9) 9 23 по методу сопряженных градиентов. Установим теперь связь между методом сопряженных градиентов и методом А-минимальных итераций. Из рекуррентных соотношений для построения векторов гр, г,, ..., г» и а,, з,. , а»+» ясно, что как одна. так и другая системы векторов состоят из линейных комбинаций векторов гр, Агр, ..., А гр.
Векторы гр, г„..., г» ортогональны. Следовательно, они лишь скалярными множителями отличаются от векторов рр, р,, ..., р» метода минимальных итераций, построенных исходя из рр = гр. Итак, р»=м»г». Векторы же а,, ..., а;„, А-ортогональны, так что они лишь скалярными множителями отличаются от векторов др = г, 444 !Тл. чь МЕТОД МИНИМАЛЪИЫХ ИТЕРАЦИЙ Б~9я Ф!,.=Ф О О Р О з 8 О О с с' О О О СС СС О о с'с "БЯВ И о сс оооо О О О с О ОООО оооо М с О О О 8 О О ! О 'Ф О сс о 3 "с' Л О сс О О с 1 о О СС а С О О О О О О О Э с О О О 'С С О О О О О О О О О, О М О О сс с М И И сс с сс й сс О й сс О СС СС Д О сС О о сс О с- О 1 Я О АВВЫ оооо й О ф 00 ф Сф с с- О Ъ с- со "3 О Сс ь О $ О О оооо $Я И д оо о Ос о о о о О О О ! ОЯОО оооо сб !~ сс О ф О О О О ! ! $59) некотОРые методы солРяжеиных нллвлвлений 445 1~, я,р,+а,(, 191-1 д1, ..., 41 метода А-минимальных итераций, т.
е. а|+1 — — 111)1. Согласно расчетным фомулам метода сопряженных градиентов, по- лучим й|р|= д1-1р1-1 а|11-1А|71-1. Сравнивая эти формулы с двучленными формулами метода минималь- ных итерация, заключаем, что и а1= — а|11 1, откуда Далее, а1 = 1,:= ( — 1)1 а,аа... ао г; =. г| (А) го а| = г1(А) го, (14) где г,(() и з;(1) полиномы, определяемые по рекуррентным фор- мулам го (г) = а| Ж = 1 г|(1) = г|, (г) — а|са1 (1) аье1 (1) = Г| (1) + а|81 (1) (15) 1-1 Л| 1 81 — 1 =- Л1 и| а,й ь 1 1-1 (12) 11 Коэффициенты "„и 31 метода А-минимальных итерю|ий выражаются черев коэффициенты а| и Ь1 по формулам 1+41+1 т1 = (13) о ага|+1 ' Отметим, что последовательные приближения Хь вычисленные по методу сопряженных градиентов, будут совладать с последовательными приближениями, вычисленными по методу А-минимальных итераций, исходя нз начального приближения Х, и до=го. Действительно, соответствующие этим методам векторы направлений отличаются только нормировкой.
Это же обстоятельство следует н из теоремы 68.1. Действительно, приближения Х; обоих методов минимизируют функцию ошибок среди векторов Хо+Ъ', где (г принадлежит подпространству, натянутому на г|Р Аг, ..., А' го. Метод сопряженных градиентов можно применить и к решению полной проблемы собственных значений. Ясно, что для векторов г; и а; имеют место представления 446 метод минимальных итвгьций [гл. ч» ( » ге ("») г -» (Л») го+ + (»е ге) ' ' ' (г„», г»»-») есть собственный вектор, принадлежащий собственному значению Л;, Это следует из аналогичной формулы метода минимальных итераций. Далее, из рекуррентных соотношениИ ясно, что г»(1)=1 при 1=0, 1...
а. Поэтому г»(1)= . Заметим еше, что полир»(») = р»(1) ' номы я»(Г) при 1=1, ..., л лишь нормировкой отличаются от полиномов»)»»(г) метода А-минимальных итераций. 4. Метод ортогоиализации столбцов. Здесь А — любая неособенная матрица. Я:=А А, 2» =-е,, ..., Л„= е„. В этом случае С= А', В = Е, Я» = )(». Формулами метода будут (мы считаем Хе=О) Х=.)»~ а»я» »» я»=е,— у»»я» — ...
— П»,я;, (яр А'Ае») (Ая;, А») Т»» (яр А'Ае») (Аяу, Ая) (А'Р, я») (Р, Ая») (я», А'Ае,) (Аяь А») ' (1,6) Здесь А;=Ае; есть 1-й столбец матрицы А. Векторы Ая,, ..., Ая„образуют ортогональную систему (ибо (Ая», Ая»)=(я, А'Ая») =(я»ь Ю)) =О при г' чье) и Ая» = А» — у»» Ая, — ... — у»»»Ая»». Поэтому векторы Ая,, ..., Ая„фактически находятся процессом ортогонализации столбцов матрицы А. Векторы направлений ян ..., я„можно строить затем по формуле ;=е» вЂ” т я — "— т,»-»я;- нспольауя вычисленные уже коэффициенты ортогоиализации Однако построения векторов яо ..., я„можно избежать.
Именно, нетрудно проверить, что искомые неизвестные определяются по При невырожденном течении процесса полипом г„(1) лишь скалярным множителем будет отличаться от характеристического поли- нома матрицы А. Это ясно хотя бы из того, что полиномы г»(1) лишь постоянными множителями отличаются от. полиномов р;(г) метода минимальных итераций.
Легко проверяется, что если Л» собственное значение матрицы А, то 9 69[ нвкотогыв методы сопгяжзннык нлпвавлвний 447 рекуррентным формулам х„, = а,, — Т„„,х„ (17) х1 = йг Тыхз . Ти!хз По сушеству метод ортогонализацин столбцов эквивалентен применению метода ортогональных векторов к системе, полученной из данной системы 1-й трансформацией Гаусса. В табл. 71.20 дается пример решения системы уравнений методом ортогонализации столбцов по данным табл.
П. 1. Табл. '41. 20 заполняется по схеме. 1 П !П и, оз из О~ х, хз х, х, 5. Метод ортогонализации строк '). Здесь А любая неособенная матрица, )с = АА', Л, = е,, ..., Л„ = е„. В этом случае С = Е, В= — А', !с = Е. 1 Формулы метода таковы (18) (АА'зь е;) (А'зь А'е~) Здесь векторы з; получаются по формулам = е; — Тцзг — — Тп— (19) где (зт, АА'е~) (А'зз, А'ет) (А'зь А') Т (зд, АА'еу) (А'з), А'е)) (А'з), АЗ) и А'е! — — Аг есть 1-я строка матрицы А. т)Ю. Шрейдер[1[, Ю Ч! Аг Аз Аз Аз Р Лз~ контроль (Азо (Азн (.4о Х= ~~ а;А'з; в т а— Аз Азз Азз Аз,) Аз;) Аз;) 448 [гл. и! метод минимлльных итеессций о о 00 СО о о о' о о о ! о о со о с'! о сс о оооо с! СО 'О О Сс О СО 00 о о ! о о о о о с- о ооо с[ о о о С'0 С ! О! о о о о с о о о о о о СО О ОО' с о 'Ф О ооо и О сО О О и О Д сс и О О о О и О ст О и СО С! СО СЧ Я[ Яо со 00 с-, С оооо о о о О Д СО ооо СО О ! ! 00 СО 'с' ! сс о о СО О О! О 00 О! Сс со о с! СО О С'0 С'0 О! о С! ОС о 00 00 СО с с' о 6 69) НЕКОТОРЫЕ МЕТОДЫ СОПРЯЖЕННЪ|Х НАПРАВЛЕНИЯ 449 Таким образом, основную роль в формулах метода играют вспомогательньзе векторы Агам которые, очевидно, могут быть получены ортогонализацией строк А' матрицы А по формулам А'в!= — Аз — ТОА'з,— ...
— 7; з гА'зз (20) с прежними значениями коэффицяентов 76. Сами векторы зн..., Е„нужны лишь для вычисления числителей Ез=(Е, зз) коэффициентов аь Так же как в предыдущем методе, их можно исключить. Действительно, имеем Ез=!Е. з)=(Е, зз — Тз..— .. — 7;,з,з;,)= =Л 7 Е . ° — Т,з-зЕз- !2!) Здесь Л вЂ” — (Е, ез) есть г-я компонента вектора Е. Таким образом, числа Е; находятся параллельно с вычислением ортогонализованных строк А'зз по тем же рекуррентным формулам. Метод эквивалентен применению метода ортогональных векторов к системе, полученной 2-й трансформацией Гаусса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
