Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 30
Текст из файла (страница 30)
Тогда для сеточных функций и, равных нулю на границе, имеем и'+.1 = (Е + ХР)О1. Тем самым проблема свелась к оценке нормы итерационного оператора Е+ ТР, так как ЦО1+1Ц И ЦЕ+ ТРЦЦО1Ц и, следовательно, Ц О1Ц и ЦЕ+»РЦ1 ЦООЦ. Этой оценкой мы и займемся. Наиболее эффективным аппаратом подобных оценок является, метод Фурье или, что то же самое, спектральный анализ оператора. Задача простая и известны аналитические выражения для собственных векторов и чисел.
Л е м м а 2. Сеточные функции рЦ = зш (хрл/О1) суть собственныс векторы разностного оператора дз/дхз, которым соответствуют собственные значения ДР = (4//»з) з!пз (/Рл/2/т). Здесь р — номер собственной функции (р = 1, 2, ..., А/ — 1), /с — номер узла. Доказательство состоит в простой проверке, которая опускается.
Заметим только, что нам удобно ввести спектр формулой с ддЧР') т»Р — 1 'Р1 т»т! ДР дхз/ Аз Введем собственные векторы оператора дз/ду~: ~рч Ри зш (Ривх/,А/) (д = 1, 2, ..., О1 — 1). Очевидно, (дзот/дуз) = — )14 ~рч. Отметим, что на границах (Ри = А О, Ри = /с = А1) эти функции обрап»аются в нуль, что нам и нужно. Лемма 3. Собственными функциями оператора Р являются' функции »1 4 = рЦ ~рт, Им соответствуют собственные значения л =л +м. Доказательство состоит в прямом вычислении (Рг» 4) .
В дальнейшем особую роль будут играть границы спектров: Ои/'иАРиХ.', р=1,2,...,Ж вЂ” 1, 1ч. 1 ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ !52 где р = Х1 = — з!пг — ж хг (так как 1Т1м.1) 4 ° в ЪЧ Е'= А = — зш Р — з1п -= — 4л-. я 1 4 . 2(А1 — 1)я 4 . 2Е 4 221 42 2 Очевидно, для И 4 имеем 'АР,Т 1- $1 2,$ где 1 2х2 г Рй2 ВЯ2. Будем использовать следующие факты нз теории дискретных рядов Фурье.
Всякая функция О „„равная нулю на границе, имеет представление ОЛ =Х~,С „214. ВТ При атом Пг !12 ЦО$$= Х(О,.)' = Х(с„)' Теперь все готово для анализа сходнмости итераций. Разлагая в ряд Фурье начальную погрешность ОО, имеем О1 = (.Е+ 21Р)ОВ = (Е+ ТВ)~~» с гР 4 = Р,4 = ~~' с (Е+ 222)гР 4 ~ с (! — т ХР 4)гР"1. Обозначим д(т) = шах $1 — ТХ$. Тогда 14 2 4 С $$О Ц = ~ф (с ) (1 — т ХР 4)~~ < я(т)ф (с )21$ = я(т)$$О~$$. Точно так лке: $$О1$$ ~ Я1(т) $$ООЦ.
Выберем итерационный параметр т так, чтобы сходимость была максимально быстрой. Получаем типичную задачу: найти шгп ( пшх $1 — ТЛ $ ). 1ЕЛНС Начнем ее решение с внутренней операции: пшх $1 — ТХ$ = пзах ($1 — 21$, $1 — ТЕ$). 142чс 153 РЕШЕИИЕ ЭЛЛИПТИЧЕСКИХ ЗАДАЧ МЕТОДОМ СЕТОК 1 141 Почти очевидно, что шах ~ 1 — т)1 ~ достигается на правой или левой границе интервала [!, С].
Таким образом, нужно найти ш1п (шах (11 — т!~, !! — ТЦЦ. Из простого анализа графиков функций ~ 1 — ЗЬ!, ) 1 — т! ~ и шах (11 — т/,1, !! — т!1) видно (рнс. 14), что оптимальное значение т,„, находится из соотношения 1 — Т„„1= — (1 — т п,Ь), т.е. т,=2/(/ + !). Оценим скорость сходимости: 2! Е-! 2! д 1 т !=! — = ~~! —— ппт ппт Т.+! е (так как ! тк /). При ! = 2кз, /.
=.ВФ~ получаем характеристику оптимальной сходимостн метода простой итерации: дпп = 1 — 2(к//1!)~. Для Ф = 100 показатель сходимости д,„, = 0.9995. Полезна будет н формула для числа итераций, необходимых для уменьшения по- грешности начального приближения в е ' раз. При этом 1(е) нахо- дится из соотношения 1!И!11 = е 'див!1, т.е. 1и т !и т !. 1 пп= ° . =Па-'зпи тпт Рип. 14 Число т! = /./! — важная характеристика матрицы системы разностных уравнений (так называемое число обусловленности). Чем больше т1, тем «хуже» матрица, тем труднее проводить вычисления. В данном случае обусловленность существенно повлияла 1, на число итераций. В примере с /1! = 100 прн еж 10 5 число ите- 1/т 1/! раций порядка 1О«.
Учитывая, что каждая итерация «стоит» порядка 10/т/2 операций, оцениваем необходимое для решения задачи число операций в 1О«; для БЭСМ-б зто около часа работы. Ясно, что с таким методом нельзя браться за серьезную вычислительную работу. Большие усилия были затрачены иа разработку методов ускорения итерационных процессов, на создание новых, существенно более эффективных. Наиболее быстрые современные методы решения разностного уравне- ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ !54 1ч.! ния Пуассона на сетке 100 х100 требуют 1-ь 10 сехунд работы БЭСМ-6, Ниже мы опишем некоторые из таких методов.
Метод же простой итерации послужил нам удобным поводом ввести читателя в суть проблемы и определить основные объекты и термины. Чебыщевское ускорение простых итераций. В методе простой итерации мы получили такое выражение для погрешности: и! = ~х' с (1 — ! Лг 4)' зг 4. ИТ Из него видно, что погашение фурье-компонент погрешности происходит неравномерно: в средней части спектра (при Л Ы2) сущесп!енно быстрее, чем на его краях, и результат определяется именно скоростью погашения на краях спектра. Возникает идея сделать погашение более нли менее равномерным по всему спектру.
Зто достигается простым видоизменением итераций. Параметр ! выбирается своим на каждой итерации: и'+' = и'+ 11+, (тзи1 — У). Для погрешности имеем соотношение О1+' = (Е+ Т1+гВ)С', следовательно, с! = П (Е+ т Р)ОВ. В фурье-представлении: 1 1 Стремясь получить наиболее эффективный процесс, приходим к следующей характерной задаче: найти а=ш!и ~шах П11 — тЦ Тг...,т, [!ВХ КЬ1 Зто есть классическая задача о полиноме, наименее уклоняющемся от нуля на интервале 11, Ц (нормировка: полипом равен единице при Л = О). Она иам уже известна (см.
й 3), известно и ее решение. Параметры т! — величины, обратные значениям корней полинома Чебышева степени й Полиномы Чебышева хорошо изучены, поэтому можно оценить среднюю эффективность одной итерации. Опуская выкладки, полу- !55 З !41 еешение»ллилтических злдлч методом сеток чаем следующую оценку (напомннм, что «1 = Е//)! ~~о!~~ ж (1 — 2/!/д)! ~)о~8, т.е.
яж1 — 2!/77Е, что существенно лучше метода простой итерации. Для числа итераций имеем !(е) ~0.5 !/~ 1и (!/е), При А!=100, е= 10 5 значения 8--0.968, !(«) -360. Однако попытки применения метода чебышевского ускорения привели к парадоксальному результату; не было не только ускорения сходимости, пропала даже та медленная сходимость, которая была в методе простой итерации! Метод стал расходящимся: даже при умеренных ! 20 —: 30 величины и! выходили в «машинную бесконечность». Ниже мы проведем анализ причин этого неприятного явления.
Он позволил разработать алгоритмически несложную модификацию метода, работающую так, как предсказывает теория. Анализ вычислительной устойчивости. Устойчивая форма алгоритма. Причиной неустойчивости является наличие погрешностей округления в расчетах и некоторые свойства полинома Чебышева. Посмотрим, какие последствия имеют погрешности округления. Дело в том, что в действительности итерация имеет вид о/+! = (Е+ т + Р)с/ + е/+!, где «2+' — погрешность округления, «случайная» сеточная функция, которая имеет порядок е ~ и1+' ~.
Это есть очевидное следствие того, что любая величина а в машинном представлении становится величиной а" = а(1 + е), где е — «случайная» величина порядка 1О 'з или 10 ! в зависимости от длины мантиссы в машинном представлении чисел. Ради простоты предполо:ким, что все вычисления в итерационном процессе делаются точно и только на /!-й итерации вносится погрешность: »4 = П (Е+ т',Р)со+ е, Йей 10» Йи«8. После полною цикла из ! итераций ! о'= П (Е+ т'Р)и~ =П (Е+ т!Р)ьд+ П (Е+ т!Р)е. /=»+1 ! /=«+! Первое слагаемое оценивается так, как это делалось выше, а вот второе, порожденное малой погрешностью, оказывается очень неприятным. 1ч.! ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ !56 Чтобы понять, в чем тут дело, рассмотрим представление поли- нома Чебышева в виде произведения двух «частичных» полиномов: т,(Л) = РЬ(а) Д„Р), 0Ь(1Ь)= П (1 !1") ! В+! На рнс.
15 изобра;кены графики этих полиномов на интервале [1, Ц, содер:кащем спектр оператора Р. Полипом Р (А) — очень малая величина в левой. части спектра и очень большая в правой, причем не просто очень большая, а очень-очень большая„и Риа.
!5 в этом все дело. Полипом 9 (Х) — величина порядка единицы в левой части спектра и очень-очень маленькая в правой. В целом произведение Т, =Рь ЯВ(Х) — малая величина на всем интервале [1, Ц. Что же такое ОВ (к-е приблилсенне в чебышевском итерационном процессе)? Это есть О'=Х, сг ВРВ( в Я)"'В+ 1,с„,РВ( г ч)" ч+' где первая сумма (по АВ т в левой части [1, Ц) очень мала, вторая же сумма (по Лг т в правой части [1, Ц), напротив, очень велика.
Таким образом, [[иь[[ж !!Ол!!ОВ.)[ОО[[, но функция иь имеет специальный спектральный состав: последующие итерации к + 1, к + 2, ..., ! ее погасят. Теперь оценим погрешность В. Она имеет порядок 1О В[[ИВ [[ и оказывается по модулю достаточно большой. Однако погрешность округления — величина практически случайная, она более или менее равномерно распределена по всему спектру. Другими словами, В = ~~Р е г!Ат, и все коэффициенты фурье е — величины одного порядка. 157 $!41 гвшвнив эллиптичвских злдлч методом сеток Проделаем оставшиеся итерации: и' = [[ (Е+ т;'Р) и' = Ъ(Юи'. 7=«+1 В пространстве коэффициентов Фурье получаем Р с Дь(Л»'«)Рь(Л» «)х» «+ ,'~~ с Ць(Л» «)Рь(Л» «)х» «+ +~ е Ц (Л» «)х» «+Х~' е» «Д„(Л» «)х» «. ! Первые два слагаемых малы, так как Я„(Л)Р (Л) = Т,(Л) — малая величина на всем интервале [1, Ц, четвертое слагаемое тоже мало, так как полипом Ць(Л) мал на правой части [1, Ц, а вот третье слагаемое не мало, так как полипом Дв(Л) ж 1 на левой части [1, Ц.
Таков качественный механизм неустойчивости метода чебышевских итераций. Поняв его, можно понять и то, чтб нужно изменить, чтобы метод стал устойчивым. Достаточно очевидно, что нужно перебирать параметры т, < тз « ... т, не в их естественном порядке (и не в обратном), а как-то «в разбивку», с тем чтобы частичные произведения Р,(Л) =][(1-.„„.,Л), Ц,(Л) = Т] (1-.„.3Л) 7 ! 7-ь~~ были при любом й более или менее равномерно ограниченными на всем интервале [1, х.]. здесь последовательность параметров т„сов та же самая, но как-то переставленная. Но это наводящие соображения, а точная постановка задачи и ее решение достаточно сложны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
