А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 62
Текст из файла (страница 62)
Величина р определяет скорость сходимости метода простой итерации. Поэтому из полученной здесь оценки (15) следует, что любой двухслойный градиентный метод сходится не медленнее соответствующего метода простой итерации. Приведем оценки для р, полученные в Я 3, 4 главы Ч! при различных предположениях относительно операторов А, В и Р. 1. Если оператор РВ 'А самосопряжен в Н, а у, и у,— постоянные из неравенств (3), то р=(1-$)!(1+$), 3=7,!7,. (17) 2.
Пусть оператор РВ 'А несамосопряжен в Н; а) если выполнены условия (4), то Р=Л вЂ” Ь 5=7,/7,; (18) б) если выполнены условия (3), (5), то 1 — $ ,. 1 — нтд Уе !+й' 1+хтг' )," + ! ' Итак, доказана Теорема 1. Если для схемы (2) метод простой итерации сходится, то сходится двухслойный градиентный метод (2), (12). При атом для погрешности г„справедлива оценка 1г.Ь<Р'1 г.1„ где р определено в (!7), если оператор РВ 'А самосопряжен в Н и выполнены условия (3), р определено в (18), если для несамосопряженноео оператора РВ-'А выполнены условия (4), и в (19), если выполнены условия (3), (!5). Оценка для числа итераций дана в (16).
Замечание. Если уравнение (1) рассматривается в комп- лексном гильбертовом пространстве, то итерационный параметр т„+, должен быть выбран по формуле Рмм вэ) Теорема 1 сохраняет силу, только условия (3), (4) должны быть заменены на неравенства 7,(Рх, х)<Ке(РВ 'Ах, х) 7,(Рх, х), у,(Рх, х)(Ке(РВ 'Ах, х), (РВ 'Ах, В-'Ах).=у, Ке(РВ-'Ах, х), где Кег — действительная часть комплексного числа г. 4. Неулучшаемость оценки в самосопряжеином случае. Пока- жем, что на классе произвольных начальных приближений у, в случае самосопряженного оператора РВ 'А в коиечномерном пространстве Н априорная оценка погрешности итерационного метода (2), (12), полученная в теореме 1, является неулучшае- мой. Для этого достаточно указать такое начальное приближе- ние х„ при котором для решения уравнения (7) имеет место равенство (х„„ (= р()х ), где р определено в (17).
Найдем искомое начальное приближение х,. Пусть Н вЂ” ко- нечномерное пространство (Н =Н,). Так как оператор РВ 'А самосопряжен в Н, то оператор С=Р-'м(РВ-'А) Р-'м также самосопряжен в Н. Следовательно, существует полная система собственных функций о„о„..., о, оператора С. Обозначим через Л собственное зйачейие оператора С, соответствующее собственной функции пм так что Со =Л оы й=1, 2, ..., М. Пусть Л,<Л,(...<Л~. Так как неравейства (3) эквивалентны неравенствам уЕ(С<уЕ, у,>0, то в (3) в качестве у, и у, можно взять Л, и Л,.
При этом р, определенное в (17), можно записать в следующем виде: р = (Л~ — Л,)((Л,ч+ Л,). Выберем начальное приближение х,=$~Л о,+)/Л,э . (20) Тогда Сх, = ЛД/ Лтэ, + Лч) гЛ, э . Используя ортонормирован- ность системы собственных функций о„о,,, эч, получим (х„х,) = Л, + Лд„ (Схо, хо) =2Л,Лл, (Сх„Сх,) = Л,Л (Л, + Л ).
Подставляя эти значения в (9), (! 1), получим т,=21(Л,+Л, ), р,=(Л вЂ” Л,)~'(Л„+Л,) =р. Из (1О) следует ранено~во 1х,,'/=р/~х,//, а из (7) найдем х,: х,=р()~Лл,о,— 3/Лги ). 336 Дальнейшие вычисления дают Сх .= р () « ~Лм о — Л,«)~ Л о,ч), (х„х,) = р'(х„х,), (Сх„х,) = р' (Сх„х,), (Сх„, Сх») = р' (Сх„Сх,). Поэтому (Сх„х«) (Схо, хо) р о (Сх,, х,)о (Схо, хо)о (СхьСх«) («ох,) (Схо, Ско) (хо, хо) Следовательно, )х,(=р)!х„(1 Кроме того, х,=х,— т,Сх,=рок„ т. е.
х, пропорционально х,. Отсюда сразу следует, чтот,=т,=т„ р,=р и х,=р'х,. Поэтому для любого Лч т„— = 2/(Л, + Лм), ро = — р = (Л~ — Л,)((Л««+ Л,), ~,хо.,~~=р) х»1~. Утверждение доказано. Итак, мы показали, что если начальное приближение выбрано по формуле (20), то в двухслойном градиентном методе все параметры т одинаковы и совпадают с параметром метода простой итерации (см. Э 3 гл. Ч(), погрешности через одну итерацию пропорциональны, а скорость сходимости самая медленная.
Отметим, что такая медленная сходимость метода имеетместо лишь для специального «плохого» начального приближения. В случае же «хорошего» начального приближения скорость сходимости метода может быть значительно большей. Более детальное изучение характера изменения скорости сходимости метода будет проведено в следующем пункте, а здесь мы рассмотрим один пример, иллюстрирующий приведенное выше замечание. Покажем, что если в качестве начального приближения хо взять любую собственную функцию о, то двухслойный градиентный метод сойдется за одну итерацию.
Действительно, пусть х,с в . Тогда несложные вычисления дают Сх, == Л о =Л„х„(Сх„х,)=Л„(х„х,), т. е. х,=О или у,=и. Это качественно новое свойство двухслойных градиентных методов — возможность увеличивать скорость сходимости в случае, когда задано «хорошее> начальнсе приближение,— отличает эти методы от рассмотренных в главе И двухслойных итерационных методов, жестко ориентированных на самое плохое начальное приближение.
5. Асимптотическое свойство градиентных методов в самосопряженном случае. Рассмотрим теперь асимптотическое свойство двухслойных градиентных методов, которым они обладают в случае самосопряженного оператора 0В-'А. Это свойство заключается в том, что последовательность (р„), определенная в (11), является возрастающей. Так как величина рь определяет скорость убывания нормы погрешности прн переходе от й к (й+1)-й итерации, то наличие указанного свойства приводит к уменьшению скорости убывания нормы погрешностей г„для больших и по сравнению с началом процесса итераций.
Причем для достаточно больших п скорость сходимости градиентных методов становится практически такой же, как и для метода простой итерации. Будет показано, что для больших номеров итераций погрешности, рассматриваемые через одну итерацию, становятся почти пропорциональными. Используя этот факт, мы построим приближенный метод нахождения постоянных у, н у, для неравенств (3), а в 9 5 построим процесс ускорения сходимости двухслойных градиентных методов.
Итак, пусть оператор ВВ 'А, а вместе с ннм н оператор С самосопряжены в Н. Покажем, что последовательность (р„) является возрастающей. Из (10) следуют равенства ((хь~,)= Р„+, ~ х„+,1, )хь+, (= Рь+, ) хь1. Вычислим норму разности ха~,— р~+,рь+,х„: ~ха+,— рь„р„+,хь)'=)хь+,)!' — 2рь+,р„~, (ха+„.к„)+ + р)~,рь„(х„)' = 2 (1х,~, (' — р„~,р„+, (хь+ „х„)). (21) Вычислим отдельно скалярное произведение (х„+„хь). Из уравнения (7) найдем хь+~ = хь+ — ть+~Схь+, хь =хь+г+ть+ Схм (22) Умножая последнее равенство скалярно на Схь н учитывая (9), получим (Схм х„) = (ха+» Схь) + ть+, (Схм Схь) = (хь+„Схь) + (Схь, х„).
Следовательно, для любого й имеет место равенство (х„,. „Сх ) = О, а в силу самосопряженностн оператора С вЂ” равенство (Схд+,, хь) =О, Из (22) и (23) получим (ха+„х„) = (ха+, — т„~,Сх„„хь) = (хд„, х„) = = (х „хь+, + та+,Сх„) =1х„, ~'. Подставляя полученное равенство в (21), найдем )х„„,— р„„рь+,х ('=2 (1 ~~'"')1хь+,~*. (24) Из (24) следует, что либо рь, ) р „, либо р +,— ра+,— р и х„„,=р'хм В последнем случае, очевидно, что для всех п~)й будут выполняться равенства р„+, — — р, х„+, — — р'х„, (25) т.
е. последовательность р„ выходит на предельное значение. Итак, показано, что последовательность (рэ) действительно является возрастающей. В п. 3 этого параграфа было показано, что эта последоватательность ограничена сверху и, следовательно, имеет предел.
Поэтому для достаточно больших номеров й будет иметь место приближенное равенство рь„! ж р„+, и, следовательно, ха~,жр„„р,х, т. е. погрешности будут почти пропорциональны через одну итерацию. Рассмотрим, что следует из выхода последовательности рь на предельное значение. В этом случае выполняются равенства (25), т. е. х„„,=р'х„. Пусть пространство Н конечномерно, а о„о„..., ом — система собственных функций оператора С. Разложим х„по собственным функциям х„= ~~~, и~"!ом (26) ь=! Из уравнения (7) получим х„, = (Š— т„+,С) (Š— т„.„С) х„= М = Х (1 — т„вЛь) (1 — т„+,Ла) с4"!о», ь=! Так как х„э,= р'х„, то это означает, что для всех номеров й, для которых аьм!~0, должно выполняться равенство (1 — т.+,М(1 — т.+!Ы =Р' Отсюда следует, что в разложении (26) присутствуют собственные функции, соответствующие только двум различным (каждое из которых может быть кратным) собственным значениям.
Пусть это будут Х! и Х, Тогда л! и Х есть корни уравнения (1 — т„+,7 ) (1 — т„+ !)!) = Р'. (27) Зная т„+„т„„и р, из этого уравнения можно найти собственные значения Х! и Х, Не останавливаясь на деталях, отметим, что если в разложении начальной погрешности х, присутствуют собственные функции, соответствующие минимальному собственному значению Х! оператора С и максимальному — Х!г, то в случае выхода на предельное значение последовательности р„в разложении (26) останутся только эти собственные функции. Поэтому, решая уравнение (27), мы найдем Х, и Х,г.
Выход последовательности (р„( на предельное значение при конечном и является исключительным случаем. В общем же 339 случае можно лишь утверждать, что при достаточно большом и Рл+1 Рл+$ и Хл+л Рл+лрл+1~л' Наличие приближенного равенства позволяет рассчитывать на то, что для достаточно большого и корни уравнения (1 — „л,) ) (1 — т„„,1 ) = Р„,Р„, (28) будут являться хорошими приближениями для Х, и ).,д, а следовательно, и для у, и ул из неравенств (3), Опишем этот метод нахождения приближенных значений для у, и у,. По итерационной схеме (2) с 1=0 проводится а+2 итерации с параметрами т„„, определенными в (!2).
Так как при Т=О решение уравнения (!) есть нуль (и=О), то з =у„и, следовательно, Р„, можно найти по формуле !~гь+1Ь 1ул+ Ь !! ль Ь ~!уь Ь ' Вычислив т„л„т„ем р„~, и Рлл„решают уравнение (28). Корни этого уравнения являются приближениями для у, сверху и для у, снизу. В 3 5 будет приведен пример, иллюстрирующий предложенный метод нахождения у, и у,. й 2. Примеры двухслойных градиентных методов 1.
Метод скорейшего спуска. В 5 1 были изучены общие свойства двухслойных итерационных методов варнационного типа, используемых для нахождения приближенного решения линейного операторного уравнения Аи =)- (1) с невырожденным оператором А. Итерационные приближения вычисляются по двухслойной схеме В~"" ~'+Ау„=~, й=О, 1, ..., хлЕН, (2) а итерационные параметры ть находятся по формуле (3) где ш„=В 'г„— попРавка, гь=АУь — 1" — невЯзка, а з„=ӄ— и— погрешность. Выбор параметра т „по формуле (3) обеспечивает минимум нормы погрешности г,„, в Но при переходе от уь к у„~,, Рассмотрим теперь частные случаи двухслойных градиентных методов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
