Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 55
Текст из файла (страница 55)
Предполагая противное, получим гьэ = ~ у<г', где т) уз и О. Тогда гь+ Е 5ь. С дру<ой стороны, в силу (4), вектор г"'"< артогонавен векторам гв, Агв,..., Льгв, образующим базис и 5ь, а значит и всем векторам из бь. Так как по предположение< г ч е бю то это и<пможно 19. Мюсл сопряженных градиентов лишь при ге~~ = О, что противоречит исходной посылке о линейной зависимости ге, г1,..., ге+~.
полученное противоречие доказывает линейну!о независимое!в ге, г 112 Твк как гс, Агс,..., А" 1ге образуют базис в ܄— 1, то соотношения (4) означают, что векшр г" ортогонвлен всему псдпространству йа что в свою очередь может быть (по доказанному выше) записано в виде (г", г(] = О, ( =- О,..., и — 1. (6) Покажем, что векторы г", г',..., г" ', Аг" ' также образуем базис в 1„,. Вектор г 1 по даю!ванному имыт внд а-1 ь=с и этот вектор ортогонален векторам гс, Агс,..., А згс.
Кспффипиент ( ! — 1) .( -1) с(, ! ) не равен нулю. Действигельно, предполюня с„! ) — — О, получим г" ' =Т с'" "Л'г'=Т с'" "А'г' т1кда по построению 2 с„л = Р„т(л), покуда сь —— сь, й = т (»-1) Ь,, (»-1),(е-з) ь=е О,...,п — 2, и г" ' = га 2, что противоречит орсогонвльностн век!оров га†! э — 2 и г Предполон1им, что векторы гс, г1,..., г 1, Аг'" 1 не образуют линейно ншависимую систему. '1огда Лг" ' 6 Ь 1. С друшй стороны, е -1 1 — С 1-:Е Но по доказанному выше векторы гс, Аг",.... А"гс линейно незалнсимы прн и < 11 — 1 н с(" ) у О, т.е.
Аг" ! й 6„1. Полученное противоречие поклзьюаи!) гю велторы 1гс, г',, г Аг" ' действительно образуют Ож1ис в 1„. Тогда вектор г Е Ве может Оыть разложен по этой системе единственным образом г" .= ) уьг" + у„Аг" 1. (7) Так как по построению г" ортогоиален г' при у = О,..., и — 1 и (А! 1, г!) = (г" ', Аг!) = О при у = О,..., и — 3, то из (7) следует, что у1,.
= О, й =- О,..., и — 3. Тогда (7) имеет вид г" = у„уг" 1+ у„тг" '2+ у Аг (8) Глава б. Численные машды алгебры 298 Из разложений г г'=г +') ьгЛ~А"г~, 1 =-и — 2, и — 1, Аг" ' = ~~ рлА г л=! ь:=е и условия (Агл ь, г") = О, гь > 2, получаем р! = О. Тогда из (8) имеел! г = (г, ! -!- 1„2)г +~~ел' Ллг = Р(А)г . л=! Но Р,,(0) = 1, откуда у„! 6 ул 2 = 1, н уравнение (8) может быль и! репислно в виде г" = ув ьг" '+ (1 — 'Ув-!)г" г+ У„Агл '.
Вводя обозначения у„! — 1 = о„п гь = Д,-ь, получим окончательное соотношение, связывающее невязки на трех соседних слоях г" = г' '+о„ь(г" ' — г" г) +()л ьАг" '. (О) Подсгашшя в (9) вмеого г! его выражение Лх! — Ь и примеляя к обеим частям равенства оператор А ь, получим х" = х" ' ром ь(х" ! — х" г)+б„ь(Ах" ! — Ь). (10) (1+ ...И(г -'(('+Д, ь() " '((л=-0 ,))г — 2))2+(1, ь(Лг» ', г" !) = О. На первом пшге, когда известно значение х и надо найти х из условия минимума функционала Е(х!), получаем формулу негода наискорейшегп градиентного спуска г г 2 Лг ! е )( "((г е ))"((г (12) или, что то жо самое, х! хе Ь'))' А е Ь )) о))г ( ((гв)) т.е. пв = О, !Ос = —.
))те))г ' (Рй) По доюшанному выше, метен (10) эквивалентен исходному методу (2), который определен однозначно. Отсьцда следует, что коэффициенты п„ь, )1в ! находятся нз условий (6) ор»пгонэльности нелязок единственным образом! сисшма уравнений двя определения этих кьнффициентоа илюег внд 299 1 9. Мшод сопряженных градиентов Покажем конечность итерационного процесса (10), т.е. что за конечное числа итераций при отсутствии ошибок округления мы получим точное решение исходной сишемы (1). Пусть, как и ранее, ге = ~г,еп где шз е,— глбственные векторы А, отвечающие различным собствнппям значениям.
Обозначим через Бт ~ линейную обояочку векторов еп..., ет. Так как все г", й = 9,..., д — 1. находяпя из соотношений (9), (12), то гь и Ь з и обРазУют в нем оРтпгональный базис. ВектоР г" б Ь ~ и по доказанному выше ортоговалеп векторам гс,..., гт ~. Это вгвможио тольхо в случае гт = 0 Таким образом, производя 9 итераций по бюрмулам (13), (9), мы получим точное решение системы уравнений (1) при условии отсутствия ошибок округления.
Оценим скорость сходимости метена. Для зтозп примоним приом, который уже употреблялся при оценке скорости сходимости ыеггда наискорейшего градиентного спуска. Пусть у = х и уг --приближения, получаемые при решении уравнения (1) линейным оптимальным процессом. Тозжа по доказанному в з б погрешности «е = у" — Х удовлетворяют ихнношвнию я=де(А) Р, Ое(О)=1, и имеет место оценка ))О.(АИ)< ., „, гдг Ле=,~ Отсюда, в частншши, следует, что Получим оценку скорости сходимогти линейного оптимального проч цесса в других норьшх. Пусть «в = ~ шзе,. (Нетрудно видеть, что ;=1 пл = г„/Ло) Тогда а г е = гз„(А) е = ~пьб),(А)е; = ) п~Щ,(Л,)ез вм )(тт"ц', — ч(Аш ът ) = ~ ызЛяО.
(Л.) < шах С~ (Л)) Л шов ле(ь, м) = Щ„(А)()~ )(зт~))~л < ( „я) ))«Д)5, Лв+Ле Глава б. Численные пеням елпбры 300 т. е. )) ")(л < .. () '()л (15) Так как ((ив((х = (А(у — Х), у" — Х) = (А '(Ау — Ъ), Ау — Ь) = )(я"((с~ „ где в" = Асс", то из (15) следует оценка 2 Ле 4Л„ (15) Применяя к обеим частям (14) матрицу А, полу шы ургсвненне, связыввюпцн левсгшси иа и и и яулевом шагах линейного оптимального про- цесса и" =- Яа(А)к~ = ()а(А)г~. (17) !( г" ((,С- с < () ва (( Л вЂ” с < „ )( я" )),С вЂ” с = †„ )) г" ((,с в с . Но тах хек ))г"()л-с — — ((х" — Х)(л, то нз последнего соотношения получаем оценку скорсятн гхадимости метсСца сопряженных градиентов ((„- х((„< 2 ((х х((, А."+Л-,а (18) Зехсечаиссе.
5Ье не обсуждали вопрос численной устойчивоспс нахожде- ниЯ паРаматРов а, 1ла ссоскшсьнУ он тйсбУег спыгиюсьного РасслсатРсвсив. 2 10. Итерационные методы с использованием спектрально-эквивалентных операторов Кроме лсетсдов простой итерации вида х"Ш = х" — а(Азс — Ь) часто применяются итерационные методы Вхв+' = Вх" — (Ахв — Ь), (2) где матрица В Ю Ь' такова„чти система уравнений яу быть респена.
Коли соотношение (2) умножить на Л х"+с =- х" — ов с(Ах — Ь). = с легко может то получится По построению вектор г" минимизирует функционал (~у(~л-с среди нектаров вида (2) или, что то же самое, ха минилсизирует г(у) среди векторов у таких, что г = у — Х именг вид (2). Тогда г (х") < г (уа), откуда ЗО1 11О.Итерационвыемепялм Таким образом, итерациснньгй процесс (2) равносилен методу просияй итерации с матрицей  — глВ 'А.
Рассмотрим случай, когда А > О и отношение максиыального М и минимальною р из собственных значений матрицы А велико. Тогда рассматривавшиеся ранее итерационные прэцессы сходятся медлелпго. Пусгь В>ои (Ах, х),(А, «) Предположим, что систелга уравггений с лгатрлгцей В легко решается и Мл/дг « М/р. В случае, когда отношенио М,/1н по очень велико, итерационные методы типа рвссматриввелгых в настоящем параграфе принято условно называть итерационными методама г игпслезаеанпем спектральна-экеиваленганиз: операторов (Л.В. Канторович, Е.П Дьяконов).
В настоящее время зти итерационные меюды назывшот методами с пгрсабрслаелиеанием, а матрицу (оператор) В переабуглавлиеапгглем. Покажем, чзо при удачном подборе лгатрицы В метод итераций (2) сбладапг лучшей сходимастыо по сравнению с глростейшии методом [1). Точнее решение Х удовлетноряет равенству ВХ = ВХ вЂ” о(Ах — В); вычигая его из (2), получим уравнение огнссительл|о погрешности Вг" ы = Вга — оАг". (4) Приведем матрицу В при помощи ортогональною преобразования к диа- гональному виду.
Пусть В = ПтЛВ, где  — оРтогональнаЯ матРиЦа. Замнгилб что все Аг. > О Через ъ/В принято обозначать ыатрицу вила Очевидно, ъ'В > О, (ъгв) г = ъ/В, ъгВъгВ = В. Уыножилл обе части урав- ненив (4) слева на (ъ/В) г и положим ъ/Вг = ъ". Получим равенство ти Ы = т" — оСъ", где С = ( /В) А( /В)— Глава 6.
Чвслевные методы гшмбры 302 Вследствие соотногпений А = Ат, (ъ~В) = (ь'В)т, матрица С симме. трична. Рассмотрим выражение ш(я) =- (Сх, х)/(х, х). Положив (ьгВ) гх =- у, можем написать равенство (з) = (угВу) = (Ау, у)/(Ву, у). Согласно (3) имеем ш(к) б (рг, Мг), поэтому все собственные значения матрицы С также принадлежат отрезку (дг, Мг).
При гг = 2/(Мг -1- рг) собственные значения матрицы Я вЂ” оС по моду. лю не провоглодят величины (Мг — рг)/(Мг -у рг). Поэтому ~(Š— ггС~)з < (Мг — рг)/(Мг -Ь рг) и аналогично (6.13) имеем ))т ()з < ))у ))з. ь Мг+рг г (6] Напомним, что »ьч, и /ггш, уг г = Лвд г Если 0 < рг < (Ву, у)/(у, у) < Мз при вгех у, то из (6) следует оценка Так как функция М вЂ” д 1 — (д/М) М+ р 1 у (р/М) мовогогшо убывваг с уменыпеннем М/р, то скорость скодимости нового итерационного процесса быстрее, чем у (1).
При гжон гательном решении еоврога о переходе от итераций ао г/ормрлом (1) к итерог1илм по формрлам (2) гмсдрепг рчетоь коли ысглео арифмсти аскат операций, оыполнлемыгг. ео ерема эагггя ггагероций. Если таеунтпн по формрлам (2) игргброаг ПГщесглоснао больигего колпчсснгоо ггпсраггггй то такой переход мо:вост оказаться нецелесообразным.
Задача 1. Пусть Т(А) — количество арифлгетвческих операпрй, выполняемых во время одной итерации по формуле (1), Т(В) — колнчегггво арифметичы:ких операций, выполняемых во время одной итерации по формуле (2). Приве<та соображения в пшгьзу того, что переход к нпрацням по формуле (2) целесообразен, если Т(ВФ М +Р У <Т(А) ()пи Р) По аналогии с тем, квк по итерационному методу (1) был построен метод (2), можно настроить вивлог любого из рассматривавшихся в Я 8— 10 методов. зоз 110. ИтеРационныеметоды Пусн, имеется итерационный щюцесс, где по«решноств последующих прибли- жений связаны рэвенснюм г"+« = (Я вЂ” ) а,А«) гц Напишем равенство т'"»« = (Š— ~ о,С') т", «=« (7] где С' = (ъГВ) «А(ъ«В) ', положим г" = ъ'Вг" и умножил«(7) свеев на ъ«В. Получим уравнение Вг'ы' = Вг'* — А о,(АВ ')' «Аг". Таксе уравнение для по«зжшноств соответст вуег ишрационному процессу Вхэ+' = Вх" — ] а«(АВ «)««(Ахе — Ь).
(8) =« Ешш про«швестн оптимизацию параметров а, так, чтобы оценка огношення норм ))т"" «])э1')]т"))г была наилучшей, ю так же, кэк в з 6, получншя наилучший итерационный метод вцла (8). Аналогом оптимального линейного вюрацяонного метода (6.26), (6.26) будет нгерацвоннь«й процесс Ву"+« = Вув + йайе,В(у — у" '] — (1+ Щи„«)(Аув — Ь), 2 М«+д« где ш строятся по М«н д«так же, как ы„по М в д (см. (6.26)). Об«ящвне««неь«ыетода (2) с мет«щом наискорейшего спуска являежв следу«о- щнй метоц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
