Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 72
Текст из файла (страница 72)
Решение в форме (3) можно предстзвить как последний член по- следовательности векторов Хо, Х,, ..., Хв, где Х» = Хо + с~~ а»Ве; = Х», + а»Вз», Е-1 а векторы Хо, Х,..., Х„рассматривать как последов ательн ы е п р и б л и ж е н и я к решению. При этом последовательные не- вязки го, г,, ... будут связаны друг с другом по формуле г» = г», — а»АВво (6) Действительно, '» = Р— АХ» = Р— АХ;, — а»АВе» = г,, — а»АВз ..
При построении»-го приближения Х» нет необходимости знать всю систему сопряженных направлений, так как оно определяется лишь первыми 1 векторами системы. Поэтому свойства последовательных приближений Хо, ..., Х, не будут зависеть от того, каким образом система векторов Вз,, ..., Вз» (или в,, ..., е;) будет продолжена до полной. Построенная система приближений будет обладать следуюшими экстремальными свойствами.
Теорема 63.1. Среди всех векторов вида Л=Х + Р', где ~' принадлежит подпространству, натянутому на векторы Вз„..., Вво вектор Х» наименее по й;длине отличается от точного решения. Иначе говоря, обобщенная функиия ошибок уя,(2) = =(й,(Х вЂ” Л), Х вЂ” л) будет принимать наименьшее значение при л =Х». $ 681 методы соцгяжзнных нлпвхвлвний и их оыциз свойства 436 Доказательство. Пусть к=Хе+~ Т/Вз.
Тогда 1-1 / з, (а) = Я1(Х вЂ” Е), Х вЂ” Л) = / / / / 77 и1 1 И1Я а/Вз,— ~~~ Т/Вз/)~, ~~„', 'а/Вз —.'г', Т;Вз/ 1-1 1=1 /=1 1=1 7 к з =~~'„(а/ — т/)1(Ю., 5,)+,»', а,'(Йзр 5))~ ~~Р ~а~(Ю1ч 5,), /=-1 1'=111 1=7 1 Отметим еще следующие свойства последовательных невязок г,, г,, ..., гг и векторов 5,, ..., 5о Теорема 68.3. Справедливы равенства (Сго з/) =0 (Сгп 5.) =(Сг,, з;) (7) Доказательство.
Имеем ге= — АХ»=А(Х вЂ” Хе) = Ъ, ' "о 'а' АВза (зм Юа) 1-1, 1 Следовательно, 77 %т (Сго за) Сг; = г„( ' ' Утза. а=1 1 Отсюда (Сгн 5/)=О, если / с,,1+1. Далее, (Сгм 5/) (Сг, 51) = (Юр 5/) =(Сгв, з/), = (85,,5,) если /)~1+1. Тем самым теорема доказана. Методы сопряженных направлений обладают следующим неприятным свойством. В случае, если система векторов, подвергающихся процессу обобщенной ортогонализацин, далека от ортогональной по причем равенство достигается при Т = а . Тем самым минимум /з, (Л) достигается при е.= Х.= Х„+~~.','а Взр /= Теорема 68.2.
Обобгценная функция ошибок убывает ари возрастании индекса Д Справедливость теоремы непосредственно вытекает из теоремы 68.! . Легко также проверить ее непосредственно вычислением. Именно, (, (Сыад' 436 [гл. Тп МЕТОД МИНИМАЛЬНЫХ ИТЕРАЦИЙ отношению к выбранной метрике, то ири проведении процесса ортогонализации может произойти значительная потеря точности. Положение может быть нсправлено ,доортогонализацией" полученной системы, т.
е. по сути дела построением новой ортогональной системы, исходя из уже построенной. Эта доортогонализация должна быть проведена по общим формулам обобщенной ортогонализации, что требует вычисления некоторых малых поправочных коэффициентов нз треугольной системы с сильно преобладающей главной диагональю. Искомое решение системы затем должно быть найдено по формулам (3) и (4) (нли (5) и (6)), примененным к вновь построенной системе векторов. В случае, если А положительно-определенная матрица, можно принять гс =- А, В = С = Е.
В этом случае процесс решения системы АХ=- Р имеет простой геометрический смысл. Рассмотрим л-мерное точечное пространство, в котором выбрана декартова система координат. Каждой точке пространства сопоставим вектор, исходящий из начала координат в эту точку. Точку и соответствующий ей вектор будем отождествлять в том смысле, что говоря о результате каких-либо действий над точками мы будем понимать одноименные действия над соответствующими им векторами. Рассмотрим поверхность, заданную векторным уравнением г(Х)=(А(Х вЂ” Х*), Х вЂ” Л ) =-с. (Здесь Л точное решение системы).
Ясно, что эта поверхность прн с) О есть эллипсоид Ю'„с центром в точке Л . При различных значениях с уравнение определяет подобные эллипсоиды с общим центром. Прямые Яо Я„ ..., 3„, проходящие через центр эллипсоида в направлениях А-ортогональных векторов эо з,, ..., Ею образуют систему сопряженных диаметров эллипсоида у(Х) = с. Пусть Хз начальное приближение. Возьмем с ) у(Ха). В этом предположении точка Ха будет находиться внутри эллипсоида у'(Х) = с. Проведем через точку Хе прямую Р„параллельную 5о затем плоскость Р,, параллельную ог и 5а, трехмерную плоскость Р„ параллельную Вп Ва Я, и т. д.
Прямая Р, пересечется с телом г"(Х) с с эллипсоида ~'(Х) ='- с по отрезку )к',, плоскость Р, по плоскому эллипсу %'м трехмерная плоскость Р, по трехмерному эллипсоиду гг'з и т. д. Обозначим через Х, середину отрезка Ж',, через Х, центр эллипса Уг'а, чеРез Х, центР эллипсоида %'а и т. д. Последней точкой Х„ этого ряда будет центр всего и-мерного эллипсоида В'„, т. е. решение Л системы АХ= Е. Геометрически ясно, что из всех векторов, исходящих из центра эллипсоида гг'„ и опирающихся на к-мерную плоскость Рю наименьшую А-длину имеет вектор Х„ — Х*, направленный в центр Х„ эллип- 9 69] некОтОРые методы сопРяженных нАНРАВлений 4зу соила В'а.
Но как раз этим же экстремальным свойством обладает й-е приближение в методе сопряженных направлений. Поэтому центры Хн Х,, ..., Х„ представляют собой не что иное, как последовательные приближения в методе сопряженных направлений. Сам процесс последовательного построения точек Ха, Х,, ..., Х, может быть описан следующим образом. Через Ха проводится хорла В', эллипсоида 1Р„, параллельная диаметру ВР Середина этой хорды есть Х,. Через Х, проводится хорда )Е;, параллельная Я,.
Эта хорда будет з эллипсе Ф; диаметром, сопряженным с хордой К'Р Ее середина будет центром эллипса %', т. е. точкой Х,. Далее, через Ха Рис. 5. проводится хорда гр'„ параллельная Ям Эта хорда есть диаметр эллипсоида Ж'и сопряженный с его плоским сечением Ф'а и ее середина Х, есть центр эллипсоида и т. д.
(см. рис. 5) В заключение этого параграфа приведем формулы для нахождения обратной матрицы. Условия В-ортогональности векторов Рн ..., г„ в матричной форме записываются в виде В'ЯЯ = Л, где Я вЂ” матрица со столбцами ао ..., а„, Л=[(ао Ю,), ..., (а, Йьи)!. Отсюда следует, что Я'САВВ = Л и А '=ВЯЛ ~В'С=(ВЯ)Л (С'5)', Если В= — А, В=С вЂ” — Е, то А '=ВЛ 'Я'. (9) Я 69. Некоторые методы сопряженных направленнй В современной литературе описаны и изучаются несколько методов сопряженных направлений. В этих методах в качестве системы векторов Ео ..., 2„, подвергающихся процессу й-ортогоналнзации 438 [гл.
ю мвтод минимлльньзх итяглцнй берется или система единичных векторов е,, ..., е„, или система последовательных итераций некоторого проиэвольного вектора матрицей !с. 1. Метод ортогональных векторов. В этом методе ') А положительно-определенная, !с= А, Л! =-е,, ..., 2„= е„. Соответствуюшие формулы получаются иа формул $ 68 при С = В =Е, !с!=А. Векторами направлений будут А-ортогональные векторы е! = е; — Тпа, — ... — Ти зез-! при (АеьеЕ) /1=2, ..., л (Аез, зЕ) т /=1,..., !' — 1 Если Хе=О, то Х= ~~.', агап ! ! (2) где (г, гч) (Г, гч) а (ез, Аз!) (ез, АеД' Отметим, что векторы Ае; суть не что иное, как столбцы А матрицы А. Таким образом, (Аз, е!) ТВ= (А), ее) а= — (' (3) А, Р е! ез ез (ео Ае,) (Ан е;) Тз| а; ! А! Аз Аз !1 контроль !И !Ч Ч В табл. Ч!.18 приведено решение системы уравнений (9) й 23 по методу ортогональных векторов.
Установим теперь свяаь между методом ортогональных векторов и эскалаторным методом Я 26). з) Фокс, Хаски, Уиль винсон [1]. Контроль вычислений осуществляется вычислением величин (Ао е!) при /) д которые теоретически должны равняться нулю. Вычисление решения по методу ортогональных некторов уклады. вается в схему: некотоеые методы сонеяженных нлпелвненнй 439 ф 691 ! ! ! о о о ооо 43 ОО с4 о о о В О ! ! о о СО о о о о о Ос С4 Д СО ооо о о о оооо сО ооо й Ц Ос СЧ оо 'о ЯЗЯ~ о 'оо о о о й О О. О й О О СЛ :О О О Ф О.
4 й С ! и й О С С'4 СО Я о ОО .С СЖ с~ о о о ! с Сс 4 сО '4' С'4 СО с о о о С СО сО Я Б с Ос о о Ос Ос СО Сс Ь СО 440 [ГЛ. Ч1 метод минимальных итеглций Соотношения г,=е, г2 = Р2 — Т21г! могут быть записаны в виде е, =г, е, = Та,г, + га Е Т 1г! т Т 2г2 Г ''' +Тле-!г ! Гг или сокращенно в виде е = Р5', (4) где 1 0 ... 0 0 о о — Та! Т2!2 ' ' ' Г1!г! — 1 1 а 5 матрица, столбцами которой являются векторы направлений. Поэтому о = Г' н, следовательно, Я является правой треугольной матрнцей с единичной главной диагональю. Далее, ортогональность векторов г; к векторам Агг, при 1' ~ У может быть сокращенно записана в виде матричного равенства, УАЯ=Л, где Л вЂ” диагональная матрица.
Действительно. элемент Г-й строки и у-го столбца матрицы 5'АЯ равен, очевидно, (г2, Аг,) и потому равен нулю при !' Ф~'. Таким образом, А=5' 'ЛЯ '=ГЛЯ Ровно такое же разложение лежит в основе эскалаторного метода при Я=У в обозначениях й 26. При проведении вычислений по обоим методам фактически определяются элементы матриц Р, Л и 5. Вычислительные схемы методов з основном совпадают. 2.. Метод А-минимальных итераций. Метод укладывается в общую схему методов сопряженных направлений при !с=А, А положительно-определенная, Я!=!Те, ..., Л„=А" !ге (в предположении линейной независимости векторов д, ..., А" де).
Как и $ 69] некотоРые методы сопРяженных нАпРАВлений 441 где г) Ш т и ф е л ь ]1], Х е с т н н с и Ш т н ф е л ь ]1]. в предыдущем методе С =  — — Е, )с, = А. Система векторов сопряженных направлений т, ..., д„ , строится непосредственно по трехчленным рекуррентным формулам (1] 65), минуя вычисления векторов Ац, ..., А дь и А-ортогонализации системы д,, Адт ° . .4 Чо. 3. Метод сопряженных градиентов. В методе сопряженных градиентов ') гс = А, А положительно-определенная, В = С = Е, й, = А. А-ортогональные векторы яо ..., я„ теоретически строятся процессом А-ортогонализации невязок г,, г,, ..., г„ , последовательных приближений Хз, Х,, ..., Х,, определяемых по формулам метода сопряженных направлений, т. е.
по формулам Х; = Х + ~~'„а я., (га яу) Таким образом, здесь система векторов, подвергающихся процессу ортогонализации, не задается заранее, а строится параллельно с построением векторов сопряженных направлений и соответствующих им последовательных приближений. Отметим, что название метода связано с тем обстоятельством, что невязка гг является градиентом функции ошибок, вычисленным в точке Хе Очевидно, что метод сопряженных градиентов естественно связывается с решением лишь одной системы АХ= Е, хотя знание базиса я,, ..., я„позволяет решать тзк же и системы с отличными от Е свободными членами.
Процесс построения последовательных прнближений оборвется, как только некоторая невязка г„окажется равной нулю, т. е. как только приближение совпадает с точным решением системы. А рпог! мыслима другая причина остановки процесса, не приводящая к точному решению. Именно, процесс может остановиться, если некоторая невязка г„окажется линейной комбинацией предыдуших. Тогда получится я„„.= О и гье, — — г„.
Однако зто невозможно, в силу следующей теоремы. ТеоРема 69.1. НЯНУлевые незлзки гв, г,, ..., гь, взаимно ортогакальны. Доказательство. рассмотрим (го гя) при т)у'. Так как векторы я,, ..., яз., получаются А-ортогоиализацией системы векторов гз, ..., ген заключаем, что вектор г~ есть линейная комбинация векторов я,, ..., яз , и потому (го г,) есть линейная комбинация чисел (г, яз) при )е = 1, ..., у'+ !.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
