А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 65
Текст из файла (страница 65)
Действительно, из уравнения для погрешности хд в случае схемы (9) хдэ, — — адо ! (Š— тд,С) хд+ (1 — ад+,) хд „й = 1, 2, ..., х, = (Š— тоС) хо (10) получим, что хд — — Рд(С)х„где полинам Рд(С) имеет вид (4) (и =й). Поэтому, если параметры (т„) и (ад) в (9) будут выбраны так, чтобы для любого и=1, 2, ... выполнялись условия (6), то построенные согласно (9) итерационные приближения у„будут совпадать с приближениями, построенными по формулам (6), (8) для любого и. Построим искомый набор параметров (тд) и (ид). Для этого нам потребуется Л е м м а.
Необходимыми и достаточными условиями мини- мума нормь! х„в Н для любого и) 1 являются условия (Схм х„)=0, 1=0, 1, ..., и — 1. (! 1) Действительно, нз (4), (6) следует, что условия (6), являю- щиеся условиями минимума нормы х„, эквивалентны следующим: (Ох„х„)=0, 1=-1, 2, ..., и, (12) для любого и=1, 2, ... Отсюда получим для 1(и — 1 !+! (Сх„х„) + ~ аУ'„(Сох„х„) = (Сх, х„) = О, о=о т. е. условия (11) необходимы. 350 Докажем теперь достаточность условий (11). Пусть выполнены условия (! 1). Покажем, что тогда выполнены и условия (!2). Из (1!) при 1=0 получаем, что равенства (12) верны для 1=1.
Справедливость (!2) для 1) 2 докажем по индукции. Пусть для 1( й условия (! 2) уже выполнены, т. е. (Стх„х„) =О, 1=1, 2,..., й. Покажем, что они выполнены н при )=1+1, если выполнены условия (11). Действительно, из (!1) при 1=й получим 0=(Сх„, х„) =(СР»(С)х„х„) = = (Сх„х„) + ~~.", а!»' (СУ+ 'х„х„) = а»' ~~(С»+ рх„х„) . р=1 Следовательно, (С"+'х„х„) =О. Лемма доказана.
Воспользуемся теперь леммой для построения набора параметров (т ) и !а») для схемы (9). Для сокращения выкладок будем считать, что у, в схеме (9) находится по общей формуле (9) при а,=1. Рассмотрим схему (10). Так как х, находится по двухслойной схеме, то из $! следует выбор оптимального параметра т, по формуле (Сх,, х,) (Схр, Схр)' Построение параметров т„т„...
и а„а„... будем осуществлять постепенно. Пусть йтерационные параметры т„т„...„ т» и а„а„..., а„уже выбраны оптимальным образом. Так как эти параметры определяют приближения у„у„..., у„, то из леммы следует, что выполнены условия (Сх, х;)=О, у=О, 1, ...,1 — 1, !'=1, 2, ..., А. (13) Выберем теперь параметры т»+, и а»+„определяющие приближение у»+,. Из леммы следует, что норма х„+, будет минимальна, если выполнены условия (Сх, х„,)=0, 1=0, 1, ..., й. Из этих условий найдем параметры т»+„и а»+,. Покажем сначала, что из (13) следует выполнение условий (14) для ! ( й — 2, а затем из оставшихся двух условий (14) для ! =й — 1 и 1=й получим формулы для т»+, и а„+,.
Итак, пусть 1(й — 2. Из (10) и (13) найдем (х»„, Сх ) =а „(х», Сх ) — а „т„„,(Сх„, Сх-)+ + (1 — а»»,) (х„„Сх.) = — а»„т»„, (Сх», Сху). Покажем, что (Сх„, Сх,) = 0 для 1(й — 2. Действительно, из (10) 35! при Й=!' получим С«7 — хт — [х)рд — (1 — а „) х д1, !') О. (15) 1 1 тт+д т р.дад„.д трд /-д Используя самосонряжеиность оператора С и условия (13), отсюда получим для 1'~й — 2 (Сх„, Сх)) = = — (Сх,, хх) — а [(Сх,х„х„) — (1 — а,) (Сх „х„)] = О, 1 ! Следовательно, (ххр.д, Схт) = 0 для )с й — 2.
Найдем теперь тррд и ах+д. Полагая в (14) )=й — 1 и 1'=й, получим из (10) и (!3) 0 = (Схх, ха+ ) = = — а„+дтх~д(Схх, Сх„,)+(1 — а„„,) (Схр „хр д), (16) 0=(Схы хх рд) =ар+д[(С«х, хр) — г„р,(Схм Сх„Ц. Из второго уравнения сразу найдем параметр т„,: (Схр, хр) "+' (Сх, Схр) ' (17) Из первого уравнения исключим выражение (Сх„, Сх,). Для этого положим в (15) 1=)г — 1 и умножим скалярно левую и правую части (15) на Схх.
Учитывая самосопряженность оператора С из условия (13), получим (Сх„, Схх-д)= — (Схх „х,» — — (Схр,х„)+ —,, а (Схр „х,)= 1 = — — (Сх, х ). тра» р' р ' Подставляя это выражение в (16), получим ах+ дтр+д (С«др «х) + (1 а ) артх (Схр д, «х д) Из этого равенства найдем рекуррентную формулу для параМвтРа ар„р ах+ д — — (1 — — + тр+д (Схы хр) 1 ~-д (! 8) (Схр д, хр д) ах) Итак, предполагая, что итерационные параметры т„т„..., т„ н а,а„..., ах были уже выбраны ранее, мы получим формулы для параметров т„~д и а„„.
Так как а, =! и т, = — ".й'-хз-, (Схр, Схр) ' то формулы (17), (18) определяют параметры тхх, и ах+, для любого й. Подставляя х„= Оч*гр в (!7) и (!8) и учитывая, что С=В-и (0В 'А) ()-ч* и Аг„=г,, В дг,=де„, зз« получим следующие формулы для итерационных параметров т„+, и и„+,. (Овм хь) т„~,= ',, й=О, 1, ( мю мл) я = — 1, 2, ..., а, = 1. (19) (20) Итак, метод сопряженных направлений описывается трехслойной схемой (9), итерационные параметры ть, и а„+, для которой выбираются по формулам (19), (20). Для этого метода справедлива доказанная ранее теорема 2. Из формул (19), (20) следует, что итерационные параметры т +, в методе сопряженных направлений и в двухслойных градиентных методах выбираются по одним и тем же формулам, а для вычисления параметров аь,~ никаких дополнительных скалярных произведений считать йе нужно.
Поэтому на вычисление итерационных параметров в двухслойных и трехслойных методах вариационного типа затрачивается практически одинаковое число арифметических операций. В то же время из теорем 1 и 2 следует, что методы сопряженных направлений сходятся существенно быстрее, чем градиентные методы. Покажем теперь, что если Н вЂ” конечномерное пространство (Н = Нм), то методы сопряженных направлений сходятся за конечное число итераций, не превышающее размерность пространства.
Действительно, из леммы следует, что для эквивалентных погрешностей х„метода сопряженных направлений должны выполняться равенства (Сх,-, х„)=(х, х„)с=О, 1=0, 1, ..., п. Следовательно, система векторов х„х„..., х„для любого и должна быть ортогональной системой в Нс. А так как в Н~ нельзя построить больше чем У ортогональных векторов, то отсюда следует, что х~=О и г„,=у~ — и=О. Таким образом, на классе произвольных начальиых приближений у, методы сопряженных направлений сходятся за У итераций к точному решению уравнения (1).
Для специальных начальных приближений у, эти методы сходятся за меньшее число итераций. Действительно, пусть у, таково, что в разложении х, по собственным функциям опера. тора С присутствуют У,< У функций, т. е. х, принадлежит иивариантному относительно оператора С подпространству Нл,. Тогда очевидно, что и все х Е Н~,. Поэтому в этом случае итерационный процесс сойдется за У, итераций. Из сказанного выше не следует, что оценка сходимости метода, полученная в теореме 2, является очень грубой и равенство )г„()о= д„)г,()р никогда не достигаетсЯ.
Можно постРоить пРимер уравнения (1) и указать для любого п ( У такое начальное приближение у„что указанное равенство будет выполняться. 12 А. А. свмарский, в. с. иыкмаев 363 3. Варианты расчетных формул. Приведем теперь некоторые способы реализации трехслойных методов сопряженных направлений. Из (9), (19) и (20) получим следующий алгоритм: 1) по заданному у вычисляется невязка го=Ауо — Д 2) РешаетсЯ УРавнение длЯ попРавки Вюо= го1 3) вычисляется параметр тг по формуле (19); 4) пРиближение Ут находитсЯ по фоРмУле Ут =Уо — тгюо. Далее для»=1, 2, ... последовательно выполняются следующие действия: 5) вычисляется невязка г»= Ау» — 1 и решается уравнение для поправки Вю»= г», 6) по формулам (19), (20) вычисляются параметры т»+, и а»+»1 7) прнблвженне у»о, находится по формуле У»ох=а»езу» 1- (1 — а»ог) У»-т а»о от»+гш».
Таким образом, в описанном алгоритме для нахожхения у»+, используются у» т, у» и ю», которые необходвмо запоминать. Ниже будет указан внд формул (19) н (20) для некоторых конкретных выборов оператора Р. Здесь мы ограничимся замечанием, что в этн формулы, помимо хранимой величины и», может входить невязка г», которую мы не запоминаем. Для ее вычисления можно воспользоваться либо равенством г»=Ваш еслн вычисление значения Вш» не является трудоемким процессом, либо определением невяэки г»= Ау» — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
