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