А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 64
Текст из файла (страница 64)
Начальное приближение у, есть произвольная сеточная функ- ция в !э, приним!(ющая на у заданные значения у,~ =й!. Подсчитаем число арифметических действий. Если вычисление разностных производных проводить по формуле ! и;, +и-, „= — „,(и,+, у+и,,ы+ииу+,+и!,! ! — 4и, ), и,(е)= —, р= —, 1пе ! — $ у1 1пр 1+$ уе где у, и у, в случае явной схемы есть границы оператора А: у,Е<А(у,Е. Для рассматриваемого примера у, и у, совпадают с минимальным 6 и максимальным о собственными значениями разностного оператора Лапласа Л. Известно, что 8 . иа 8 еа 6 = — з)п' — б = — соз' —. /Р 2 ' Ье 2 ' Поэтому 1 — $ .
иа р= —,=1 — 261п'— 1'-6 2 6 яа (йа Ь 2 ' и, следовательно, если й((1, то 1 21а— и, (е) —,„, 0,2 У'1п —. ~РЬ~ 8 Если считать эквивалентными операции сложения, умнонсения и деления, то на одну итерацию затрачивается примерно 20М' действий. Поэтому для общего числа арифметических операций будет справедлива оценка Я (е) ж 4Ш'1п —. 34н то для вычисления г„потребуется 6(Л' — 1)' сложений и 2(У вЂ”.!)' умножений и делений. Для вычисления (гм гь) — (й! — 1)' сложений и (У вЂ” 1)' умножений, (Аг„, ге) — 6(У вЂ” 1)' сложений и 2(М вЂ” 1)' умножений, у ~,— (У вЂ” 1)' сложений и (М вЂ” 1)' умножений. Всего потребуется ! 4(У вЂ” 1)' сложений и 6(й! — 1)' умножений и делений. Ровно половина от этого общего числа действий требуется для вычисления скалярных произведений, т.
е. для вычисления итерационного параметра т~„о Следовательно, один шаг метода скорейшего спуска примерно вдвое более трудоемок по сравнению с шагом метода простой итерации или чебышевского метода, где параметры ть, известны априори. Для неявных методов это различие будет меньшим, так как для вычисления скалярных произведений потребуется такое же число действий, как и для явного метода, а к общему числу действий добавятся арифметические операции, затрачиваемые на обращение оператора В. Подсчитаем теперь общее число арифметических действий 9(е), которое нужно выполнить, чтобы получить относительную точность е. Для этого нужно оценить число итераций и, (е).
В п. ! была получена следующая оценка: $3. Трехслойные методы сопряженных направлений 1. Постановка задачи о выборе итерационных параметров. Оценка скорости сходимости. Для нахождения приближенного решения линейного операторного уравнения Аи =)". с невырожденным оператором А в з 1 мы рассмотрели двухслойные итерационные методы вариационного типа. Итерационная схема для этих методов имеет вид В~"+' ~~+Ау =~, Й=О, 1, ..., у, ЕН, (2) тл+4 а итерационные параметры та+, выбираются из условия минимума нормы погрешности г„„в энергетическом пространстве Нр.
Напомним, что на последовательности у„, построенной по формуле (2), осуществляется пошаговая минимизация функционала 1(у) =(О(а — и), у — и), минимум которого достигается на решении уравнения (1), т. е. при у=и. Такая стратегия локальной минимизации, однако, не является оптимальной, так как в конечном счете нас интересует глобальный минимум функционала 1(у), и, если задано некоторое значение этого функционала, достичь искомого минимума мы должны за минимальное число итераций.
Локальная же минимизация на каждом итерационном шаге приводит к решению этой задачи не самым коротким путем. Естественно попытаться выбрать параметры тл из условия минимума нормы погрешности г„в Но сразу за и шагов, т. е. при переходе от у, к у„. С аналогичной ситуацией мы уже встречались в главе ч'1 при изучении чебышевского метода и метода простой итерации. Оказалось, что более быстро сходится тот метод, итерационные параметры для которого выбираются из условия минимума нормы разрешающего оператора, а не оператора перехода от итерации к итерации. Это свойство имеет место и для итерационных методов вариационного типа. Будет показано, что рассматриваемые в этом параграфе итерационные методы, параметры т для которых выбираются из указанного выше условия, сходятся значительно быстрее, чем двухслойные градиентные методы.
Более того, в случае конечномерного пространства Н эти методы являются методами конечных итераций при любом начальном приближении, т. е. точное решение уравнения (1) может быть получено за конечное число итераций. Переходим к построению метода сопряженных направлений. Будем предполагать, что оператор 1".1В 'А самосопряжен и положительно определен в Н. Выполним по схеме (2) и итераций. Переходя от задачи для погрешности г„=у„— и к задаче для 347 !; = О!мг», получим, как и раньше, х»+,— — В»+,х», й== О, 1, ..., п — 1, В» = Š— т,С, С = РО*В 'АР-»~'. Отсюда найдем х„= Т„х„Т„= Д (Š— т,С).
!=! Разрешающий оператор Т„представляет собой операторный полипом степени и относительно оператора С с коэффициентами, зависящими от параметров т„т„..., т„ п Т„=Р„(С) =Е+ ~ а'"!С~, а„'"'ФО. (4) !=! В силу равенства Цх„Ц=Цг„Цо поставленная выше задача о выборе итерационных параметров т„формулируется следующим образом: среди всех полиномов вида (4) выбрать тот, для которого норма х„=Р„(С)х, минимальна, другими словами †выбра коэффициенты а',"', а',"', ..., а„'"' полинома Р„(С) из условия минимума нормы х„ в Н.
Эта задача будет решена в следующем пункте, а сначала пояучим оценку скорости сходимости метода сопряженных направлений, построенного на основе сформулированного выше принципа выбора параметров. Эту оценку получим, используя априорную информацию об операторах схемы в виде у, и у,— постоянных энергетической эквивалентности самосопряженных операторов 0 и РВ-'А: у»0(РВ-»А (у,Р, у, ) О, РВ-'А=(РВ-»А)'. (5) Пусть Р„(С) является искомым полиномом. Тогда из (3), (4) следует оценка для х„: Цх„Ц=ЦР„(С)х,Ц=ш(пЦЯ„(С)х,Ц ='ш)пЦЯ„(С)ЦЦх,Ц, (е) " (е) где минимум ищется среди полиномов Я„(С), нормированных в силу (4) условием Я„(0)=Е.
Оценим минимум нормы полинома Я„(С). Из (5) следует, что оператор С=О-ы'(РВ 'А) 0-!~' самосопряжен в Н, а у, и у,— его границы: С = С*, у,Е (С ( у!Е, у, ) О. Поэтому имеет место оценка и!1пЦЯ„(С)Ц(щ)п щах Ц Я„((Ц. (я„) (ч„) т1<!<т* Из результатов 8 2 гл. Ч! следует, что задачу о построении нормированного условием ()„(0) =1 полинома,.максимум модуля 348 котоРого на отРезке 17!а Уа1 минимален, Решает полипом Чебышева 1-го рода, для которого шах ) я„(/)~ = о„, //„= — '.,„, р, =, $ = т'.
Следовательно, длЯ ха имеет место оценка (х„1(//„(ха1. Итак, доказана Теорема 2. Если выполнены условия (5), то итерационньсй метод сопряженных направлений сходится в Нр, и для погрешности г„при любом и справедлива оценка 1г„Ц(//„)г,~)р. При этом оценка для числа итераций имеет вид п ) и, (е) = 1п (О,бе)/1п р„ гдв р, = (1 — )/ $)((1+ )/ 9), $ = у,/у,.
2. Формулы для итерационных параметров. Трехслойная итерационная схема. Переходим теперь к построению полинома Р„(С). Используя (3) и (4), вычислим норму х„: (х„')а = (Р„(С) х„, Р„(С) х,) = а а а =!)ха1а+2 ~~.", а~/"'(С/ха, ха)+ Х Х а~"'а~!а'(С/ха, С ха) /=1 / !!=! Норма х„есть функция параметров ам', а',"', ..., а'„"'. Приравнивая частные производные от 1х„(а по а!/"! ~',„",~' =2~ а,'"'(С/х„С/х,)+2(С/х„х,), /=1, 2, ..., и, да/ю нулю, получим систему линейных алгебраических уравнений л ~ а)"'(С/х„С'х,)+(С/х„х,)=0, /=1,2, ..., п. (6) !=! Для самосопряженного и положительно определенного в Н оператора С система (6) дает условия минимума нормы х„ в Н. Итак, задача построения оптимального полинома Р„(С) в принципе решена.
Коэффициенты полинома а,'"', а',"', ..., а'„"' найдем, решая систему (6). Но сначала построим формулы для вычисления итерационного приближения д„. Первый путь состоит в использовании итерационной схемы (2). Однако для этого потребуется найти корни полинома Р„(/) н затем в качестве т„ взять обратные к корням значения. Такой способ не является экономичным.
Второй путь заключается в использовании для вычисления у„ коэффициентов полинома. Из (3), (4) и замены х„=Ем/'гы где га=уа — и, получим у„— и=0-а/аР„(С) Ва/а (уа — и). (7) 649 Используя (4) и равенство Р-о!оС/Ро!о=(В-оА)~, найдем о Р- ! Р (С) Ро!о =Е+ '~~ ао~ ' (В-оА)/, о=! Подставляя это равенство в (7), получим п о у„=у,+ ~~.", а;'"'(В 'А)У(у,— и) =у + ~~а'"'(В 'А)/-'ио„(8) !'= ! /= ! где шо — поправка, и!,=В 'А(у,— и) =В 'г„г,=Ау,— 1.
Этот путь также является не оптимальным. Для каждого нового и приходится заново решать систему (6). Сейчас мы покажем, что последовательность у„у„..., уд,..., построенная согласно (6), (8) для и=1, 2, ..., может быть найдена по следующей трехслойной схеме: Ву д,=ад„,( — т +,А) уд+(1 — ох +,) Вуд,+ад+,т оД й =- 1, 2, ..., (9) Ву, = ! — т,А) уо+ то~, уо Е Н Для этого нужно указать набор параметров (тд) и (ад), при котором норма эквивалентной погрешности хд была бы минимальной для любого й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
