Федоренко Р.П. Введение в вычислительную физику (1185915), страница 33
Текст из файла (страница 33)
Введем функцию зД) = (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, Ь, т.е. один раз для всех задач. Вычислив 8„„найдем универсальные характеристики: г„Л /Пв, уз= 1п 8 ' 1п г,,', 1„= 1/1п г . В конкрепюй задаче, имея оценки границ спектра 1, Ь, рассчитываем длину итерационного цикла г' = 1р!и (И/) + 1, среднюю эффективносп итерации у = у Л(п (А/!) и набор итерационных параметров т< — — Л /1, тз= т,/г, тз тфв, ... Для уменьшения нормы погрешности в в ' раз в конкретной задаче потребуется 1(в, 1/Е.) ж ув ' 1и (//1) 1п е ', ув- 3.2, итераций.
Значение Вьы находится по табл. 10, из которой видно, что 8, ж0.16-~-0.2 (ббльшая точность, очевидно, здесь не нужна) и /в = 5 ' 4 соответственно. Значения П, Л„, гв предоставим вычислить читателю. Для задачи на сетке 100 х 100 (1 = нз, А = 4й8) получаем убывание норм погрешности и невязки в процессе итераций со скоростью воюя ~1ов~1в-взм ягбан ~~гвЦв-вэвв !65 к 141 гкшкиик эллиитичкских элалч методом соток Таким образом, для того чтобы уменьшить погрешность начального приближения в 105 раз, потребуется около 30 итераций метода переменных направлений. Важно отметить, что, хотя эти формулы Таблица 10 нужно понимать «в среднем», в данном случае убывание норм погрешности и невязки происходит монотонно: ~)о'+'~~ < 'ао'() при любом порядке использования итерационных параметров. Проблемы устойчивости здесь, в отличие от метода чебышевского ускорения, не возникает.
Величины а о«~) и 8г«8, фигурирующие в формулах, легко оцениваются при самом простом выборе начального приближения: внутри, ио = р на границе. ио =0 кт В этом случае и, ои оил лгои и «и + и, огьзм (где и — решение разностной задачи, 11 ~р~! ж (ф рг сЬ) пг), и содержательный смысл достигнутой в расчете точности ))о'~) = 11и" — иа н < 10 «)~оо8 в 1О 511иа очевиден. Если же в этом примере использовать оптимальные параметры Вашпресса, результат будет такой: за 16 итераций получается оценка ао'~0 ж 0.3 10 «11и~а.
В формулеэффективного убывания погрешности множитель 3.2 меняется на 9, т.е. оптимальный вариант примерно в 2.8 раза эффективнее упрощенного. Обсудим вопрос о возможности применения метода переменных направлений в более общей ситуации. Проанализировав весь ход рассуждений, легко убедимся в том, что были использованы следующие факторы. 1. Уравнение Юи = у имеет форму .О,и + гг и = у. 2.
Уравнения «на верхнем слое» для схем суть и-и' — 2ги+д, т ! где и', 9 известны; они легко (т.е. «экономно») разрешаются отно- сительно и. |ч. 1 |ьь ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИХЯ 3. Операторы Р! самосопряженные с положительным (отрица- тельным) спектром. Для границ спектра есть достаточно эффектив- ные оценки 1|, г'.| 4.
Операторы (разностные) Р,, Р. имеют общую систему собст- венных функций, что, как известно, эквивалентно нх перестановоч- ности: Р,Рг — -Р Ри Этот важный факт существенно определяет возможность обобщения приведенной выше теории. Если перевести приведенные формальные признаки на содер- жательный язык применительно к эллиптическим уравнениям второго порядка, то мы получим следующий класс уравнений, простейшие разностные аппроксимации которых имеют нужные свойства: а) уравнение з а,(х) д„+Ь|(х) и+В аг(у) з +Ьг(у) И=У(х, у), б) область — прямоугольник, аи в) достаточно общие краевые условия: а — + Ви = р; здесь ив дЛ внешняя нормаль, и, р — постоянные, свои на каждой стороне пря- моугольника, В сущности это — случай, когда работает разделение перемен- ных.
Мы не обсуждаем известных в теории эллиптических задач ус- ловий на а|, Ьи обеспечивающих знакоопределенность операторов Р,=~ а|з» +Ь!, Рг=з аг~ +Ьг. Мы применили грубую теорию, в которой границы спектров Р,, Р взяты в виде 1= пни (1,,1), В=шах (1,|, г'.). В точной теории Золотарева — Вашпресса используются свои границы спект- ров для Р,, Р.
Первое собственное число разиостного оператора часто уже при не очень больших Н почти совпадает с соответствующим собствен- ным числом аппроксимируемого дифференциального оператора. Для его приближенного вычисления можно привлечь весь арсенал ана- литических оценок. В частности, можно заменить переменные коэф- фициенты дифференциального оператора на средние значения и вы- числить аналитически первое собственное число оператора с посто- янными коэффициентами.
При оценке верхней границы Р используется другое соображе- ние. Известно, что для любой матрицы (а! 1) оценкой любого соб- ственного числа сверху является шах~ ~|а| !. В нашем случае в ! каждом узле схемы следует просуммировать модули коэффициентов разностной схемы и взять наибольшее (по узлам сетки) значение $ )41 гвшенив эллиптических злдлч мвгодом свток такой суммы. Для оператора Лапласа, аппроксимированного по пятиточечной схеме, получим значение Ь = 8/л», почти не отличающееся от точного: Ь = (8//г~) соз (п(Ю вЂ” 1)/2Ф). Величину Ь можно оценить и снизу, используя известное соотношение Рэлея для самосопряженных матриц Р (операторов). Для любого собственного числа А имеем (Пи, и) (Ои, и) ппп ' а)жшах ( ').
(и, и) (и,и) ' Эти соотношения часто применяют для оценок границ спектра. Оии эффективно работают в том случае, когда имеется априорная информация о том, какую форму имеют собственные функции, соответствующие крайним точкам спектра. В частности, максимальному (по модулю) собственному числу разностной аппроксимации оператора /( (и других аналогичных операторов) соответствует сеточная функция типа и« „, = ( — 1)"» . Для оценки можно взять даже функцию, равную — 1 в одном узле сетки и +1 в четырех соседних узлах, в соответствии с шаблоном пятиточечной схемы.
Предоставим читателю проверить, насколько близко к верхней оценке Ь = 8/лз будет отношение Рэлея на такой пробной функции. Как было указано выше, теория выбора итерационных параметров н оценка эффективности работают лишь в случае разделения переменных. Однако сама схема формально применима н в более общей ситуации, например при уравнении вида эх и!(х У) у~ + э «~2(х У) з + с(х У) и /(х У) Для краевых условий первого рода (задано и на границе области) форма области более или менее безразлична: простейшие разностные аппроксимации операторов Р„ /)з включают точки только одной горизонтали (вертикалн) и краевые условия этого обстоятельства не нарушают. Если область — прямоугольник (или объединение прямоугольников), допустимы краевые условия третьего рода: в них входит нормальная производная, а при ее аппроксимации используются точки той же горизонтали (вертикали) сетки (если опустить тонкую проблему аппроксимации в угловой точке границы).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
