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