Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 31
Текст из файла (страница 31)
Тем не менее задача решена: рациональные перестановки итерационных параметров, приводящие к устойчивому итерационному процессу, были получены почти одновременно В. И. Лебедевым и В. Н. Финогеновым, а также А. А. Самарским и Е. С. Николаевым. Рецепт построения этих устойчивых перестановок достаточно прост в случае 1 = 2". Нужная перестановка получается рекуррентно. Пусть имеется перестановка для 1 = 2": (л()Н7-к к ...,г'.
Тогда перестановка для Р = 2"+' получается заменой каждого л(7) парой п(У), 2'+' + 1 — и(2). Этот рецепт дает г=1, 1=2: л=(1,2] г = 2, 1 = 4: п = (1, 4, 2, 3), г = 3, 1 = 8: л = (1, 8, 4, 5, 2, 7, 3, 6] 1ч.1 ОСНОВЫ ВЫЧИСЛИТЕЛЫ«ТЙ МАТЕМАТИКИ 158 и т.д.
Если теперь 1/т1 (/ = 1, 2, ..., ! = 2") — корни полинома Чебышева на [1, Ц степени 1, расположенные в естественном порядке: т, ) т > ..., а (и(/)) (1= 1, 2, ..., 1) — «устойчивая» перестановка, то итерационный процесс и/" = и/+ т„'0+1>(/уи/-/), /=0,1, ...,1-1, сходится в соответствии с теорией, не учитывающей погрешностей округления.
Процесс устойчив, и погрешности округления не оказывают существенного влияния. При вышеизложенном порядке использования итерационных параметров получаем процесс со следующими характеристиками: 11И111 ж 11ьл11 ехр(-21ТЯ/Е",). Такая же формула имеет место и для невязкн; ЙТ1й — Йг'~~ ехр( — 21т/77Е). В нашем случае имеем /. ='ЗИ1з, 1= 2из, т.е. ехр ( — 21 Л/Х) = ехр ( — 1х/Ф) и, например, за л/ итераций погрешность убывает в 20 раз. Это не так уж быстро, но в методе простой итерации за то же время погрешность умножится лишь иа 0.95 (при Ф =!00).
Отметим, что метод простой итерации и чебышевское ускорение имеют широкую сферу применения при решении систем линейных уравнений вида Аи /. Изложенное выше основано на таких свойствах оператора А: а) самосопряженностьс А' = А (отсюда следует вещественность спектра А и ортонормированность базиса собственных векторов); б) положительность спектра А: 0 с 1 ж Х«:а /; в) для организации расчетов нужно иметь только оценки для границ спектра 1, /.
(снизу для 1, сверху для /.). В заключение приведем два полезных замечания. 3 а и еч а н не 1. Обычно ход итерационного процесса контролируют, выводя на экран РС, например, норму невязки (она вычисляется по коду работы алгоритма, так как основная расчетная формула имеет вид и/ ' = ит+ тг/). В методе простой итерации 11т/'й' монотонно убывает. При чебышевском ускорении 11г'11 меняется немонотонно; она убывает только за полный цикл из 1' итераций. На промежуточных итерациях возможен сильный рост ~~г/]~. Так как г = В 1э, то йг)~ м 11и11/А". Замечание 2, Выбор длины цикла 1 (степени полинома Чебышева) не совсем прост.
Можно, задав погрешность е, рассчитать 1, !59 6!41 вешания эллиптических злдлч мятодом сеток используя приведенные выше оценки. Анализ показывает, что более эффективным является другой способ: использовать полиномы степени ! »Х// Ф, повторяя цикл итераций длиной г/Х/1 до получения нужной точности. Метод переменных направлений. Эффект чебышевского ускорения недостаточен. Имеются и более быстрые итерационные методы. В частности, большие успехи были получены на основе метода переменных направлений, в котором используется так называемый лринцигг установления.
Решение стационарного уравнения Ьи = /, и!ао = р является пределом при ! -» м решения и(г, х) уравнения теплопроводности и, = Аи — /. Метод простой итерации, как нетрудно заметить, есть просто решение этого уравнения по явной схеме, а условие т„= 2/(й + 1) ж 2/8/г!г — 0.256г похоже на условие Куранта. Таким малым шагом трудно получить достаточно большие г, отсюда и большое число итераций. Как известно, метод переменных направлений, допускает счет с произвольным шагом т. Кажется, можно получить сколь угодно большие ! за один шаг1 К сожалению, дело не так просто, так как при этом теряется аппроксимация. Тем не менее метод переменных направлений при достаточно аккуратном его оформлении действительно приводит к существенно более эффективным итерационным процессам.
(Полезно оценить оптимальный эффект в процессе, использующем схему «ромб»; см. й 12.) Одна стандартная итерация (переход и! в иг+') метода переменных направлений состоит из двух «полуитераций». 1. Сначала по известной и' находится промежуточная функция и* из уравнения «' — ' а и аг«' г ° = —,+ —,— /, (к, гп) внутри ах' агг и' = и' = чг, (/!, гл) на границе Функция и' находится серией раздельных прогонок по горизонтальным линиям сетки, и это требует О(А!г) операций.
2. Затем по известной й находится функция и! ' из уравнения и'~! — и' д и агы'+! = — + — — /, (й, ггг) внутри, дхг ах~ и'+ ! = и' = ч, (й, лг) на границе (серией прогонок по вертикальным линиям сетки за О(А!г) опера- ций), ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ 1ч,д Анализ сходимости. Здесь точный результат дает спектральный метод исследования, уравнения для погрешности получаются известным способом — вычитанием из формул итераций тождества для решения и (системы разностных уравнений): и-и ди ди 2 2 — = — + — — У. т дх2 ду2 Очевидно, й — и~ д2и" дуи' и'Ч1 — и' д2и' д2и'Ч1 = — + дх2 ду' 2 д»' ду' Рассмотрим эффект одной итерации в терминах коэффициентов Фурье.
Разложим О' в сумму: О' = ~~ С' гр Ч. С Р,Ч вч Легко проверить, что гР ч суть собственные векторы разностных операторов д2/дхэ, дзуду2, которые действуют в пространстве двумерных сеточных функций, обращающихся в нуль на границе квадрата: (О < 1а Хр, Л" и Е; здесь 1ж и2, Е = 42т'). Разложим в сумму н О': «'=~ С' 2Р Т. РЯ РЯ представим связь между О' н ьз в виде Е Т 2 Ю Е+Т 2 Ю~. В терминах рядов Фурье имеем < Š— Т вЂ” Х~, С' ВР Ч = Е+ Т вЂ” ~Х' С' ЕР Т. дх ду Р,и РЧ Вводя операторы под знак суммы, получаем ~Р с'„(1 + т Ъ' )гр т = ~' с2 (1 — 2 уь")гр ч. В силу единственности разложения функций по базису (хр«) приходим к соотношению для коэФфициентов с" 1 —.
Ву Р,Ч:2+,2, Р Ч' $ 14! гашение эллиптических злддч методом сеток Точно так же анализируется вторая «полуитерация», и для коэффициентов с'+' получается соотношение Р. 9 1 — тк 1 — тХ' ! — тХ" с!+' = — ~ с' = — ~ — ~ с! Л Ф !.!.„К Л 4 1,ЬтХ !.!.,Х Я Ч Р Введем функцию я(т) =игах ), ). !кхкс Очевидно, !с!+~~~ «аг(т) )с' 4~, Ч р, аа следовательно, Цо1+'Ц ~ а Зг(т)Ци!Ц, и наконец, Ци!Ц к уг!ЦиеЦ, Теперь осталось найти наилучшее значение для параметра т, т.е. ппп З(т).
т Итак, нужно решить задачу: найти Задача решается по знакомой схеме. Соотношение шах ~, ',~ =шах (~ —' ,™~, ! —,' ' )~ !кхчх проверяется простым анализом графика при разных т. Построим график функции я(т) = пшх ~~, ~~ ~, ~, ~ ~(~. Минимум я(т) достигается в ситуации ! — т! г =» 1 — т(+тЬ вЂ” т П,= 1+т 1 1+т Ь = тг12, — 1 — х(+ тЬ 2тгИ, = 2. Оптимальное значение итерационного параметра т,„, = 1Ихт.
Вычислим теперь я „,: лппт = в(т~~т) = ! Т2р~у' ! 2т!~~'~~ т.е. за одну. сдвоенную итерацию погрешность уменьшается в у~ 1 — 4т!)/Ь раз. Таким образом, эффективность метода переменных направлений при едином оптимальном значении параметра оказывается примерно такой же, как при чебышевском ускорении: для получения Ци!Ц ч еЦьаЦ требуется 1(е) ~471)т 1п е ! итераций. 6 — 1ЗЗЗ 1б2 1ч.
! основы вычислитвльиои млтвмлтики Метод переменных направлений с серией параметров. Естественно, возникает идея перейти от одного параметра т,„, к серии итераций со своим значением т на каждой. Действительно, эта идея оказывается весьма плодотворной. Очевцдным образом обобшдя проделанные выше выкладки, получаем соотношение между коэффициентами Фурье »1 и оо; 1 — т ь' 1 — т.Х" нв ьь 1+т У 1+т 2" Р'« 1=1 ~Г ~« Выбор «оптимальной» серии т'„т2, ..., т,' приводит к минимаксной задаче ' Это уже достаточно сложная задача. Она была решена в !966 г. Е. Вашпрессом, однако в дальнейшем было обнаружено, что еще в начале века решение было получено по другому поводу Е. И. Золотаревым.
Тем не менее оптимальные итерационные параметры называют параметрами Вашпресса. Мы не будем здесь излагать точное решение задачи и следующий из него алгоритм расчета оптимальной серии параметров. Существует достаточно простой рецепт выбора параметров, дающий эффект, близкий к оптимальному. Эта конструкция хорошо иллюстрирует характерную в таких вопросах идею «равномерного подавления компонент погрешности».
Имеется в виду, что каждая итерация со своим значением т эффективно гасит свою часть фурье-разложения погрешности; итерация эффективна на своей "части спектра, А в совокупности полный набор параметров обеспечивает погашение всей погрешности, Та же идея, очевидно, лежит и в основе метода чебышевского ускорения простых итераций. Введем функцию зД) = (1 — Ц)21(! + $)2 и переформулируем минимаксную задачу: 8 ппп ~ шах П «(т12) .
тг ..., ~, ( 1«Х«Ь1 Если приближенное решение задачи даст оценку ! П д(т.х) < д1 для всех х е 11, Ц, 2 1 мы получим 11о'11 и адов)~„а «средняя эффективность» одной итерации будет, очевидно, (д)П1. !бз $ !4! гвшеииз зллиптичвских з!тдлч мптодом свток Выберем некоторое 8 < 1 и выделим интервал, на котором д($) а О. Его границы обозначим через Л(8) и П(0). Итак, дД) ч 0 при $ Е [Л(6), П(0)1 н д(с) < 1 на остальной части положительной полуоси. Параметр т, выберем так, чтобы левая граница 0-ннтервала функции «(т! Х) совпала с 1: т,1 = Л(О), нли т, = Л(0)/1. Тогда правая граница О-ннтервала функции я( т, Х) определяется соотношением т!Х = П(6), т.е.
Х = П(8)/т! = 1П(8)/Л(8). Утверждение 2, Пусть т, выбрано так, как указано выше, а остальные т, ..., т,. произвольные (положительные). Тогда П З(т/Х) ч 0 при 1< 1 < 1г, где г=П(0)/Л(6) > 1. т=! Для доказательства достаточно заметить, что все множители д(т Х), ... не превосходят единицы. Итак, выделен тот «участок спектра», за который отвечает параметр ти Выберем тз так, чтобы левая граница О-интервала для д(ттХ) совпала с правой для д(т!Х): тз1г = Л(6), или тт —— Л(6)/1г = т,/г. Тогда правая граница 6-интервала функции у(т Х) определится соотношением т,д = П(6), т.е.
Х = П(6)/т = 1г'.. Утверждение 3. Пусть т, и т выбраны так, как указано выше, остальные т, ..., т! произвольные (положительные). Тогда ! П в(т х) < 0 при 1 ~ " и 1г ° Продолжая строить последовательность примыкающих друг к другу 6-интервалов для функций д(т Х), ..., получаем, очевидно, последовательность параметров; т, = 1/и, т — т,/г, ..., т, т /г т,/г!. Так продолжаем до тех пор, пока очередная правая граница 6-интервала не выйдет за пределы правой границы спектра 4., т.е. в качестве 1 следует взять наименьшее целое, при котором 1г' и 1., т.е. !(О) ='"""'+1 !и г Теорема 2. Проделав !(6) итераций метода переменных направлений с указанным выше выбором параметров т„т, ..., т!, получим оценку для погрешности !!и!!! а 6 !!„о!! 1ч.г основы вычислительной мАтвмлтнкн 1бв Для достижения нужной погрешности в мы имеем два пути: либо сразу назначить 8 = в, либо использовать найденную послещ>ватель- ность циклически и за к1(8) итераций получить в оценке множитель Вв в.
Выясним, что же выгоднее, т.е. оптимизируем процесс за счет рационального выбора 8. Задачу решаем, используя «среднюю эффективность» одной итерации, т.е. вводя характеристику у(8) = — 1п 8 ~дв> = —.,'„1п 8- . В этих терминах имеем оценку нос~~ Н ооон в-ндв) Конечно, это соотношение не следует понимать буквально, оно выполняется только после каждой серии из 1(8) итераций. Очевидно, у(8) и есть та характеристика итерационного процесса, которую следует сделать максимальной. Итак, для выбора 8 получаем задачу: найти м в ' ы 1П(вИл (вц нв) = — — ь-,~;; —- в в ,' „шах ( 8-'1 (П(8)/Л(8)И. Обратим внимание на то, что наилучшее значение 8 определяется независимо от границ спектра 1, Ь, т.е. один раз для всех задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
