Дж. Деммель - Вычислительная линейная алгебра (1156793), страница 80
Текст из файла (страница 80)
Поэтому имеет смысл выполнять подряд лишь несколько итераций типа о'. Глава б. Итерационные методы для лииейиык систем Погрешность Решение после 0 шагов 1.5 Олб 0.5 32 1.5 Погрешность 0.5 0 32 64 ' 0 Погрешность 0.5 0.5 0 !.5 0 32 64 0 32 64 0 Н 0.9!76 орма = Рис. 6.15. Иллюстрация сходимости взвешенного метода Якоби. -!.5 0 ешенае после первого шага 05 -1.5 О ешенне после 2 шаюв 0.5 32 Норма = 1.65 32 Норма = 1.055 Погрешность в частотных компонентах 0.5 Погрешность в частотных компонентах 0.5 Погрешность в частотных компонентах 6.9. Многосеточные методы Пример 6.16 )т(ее12, й=4 иизкаи частота, поскольку й <— яш -)за для 1 < у < 11 Мелкая сетка ))т=б, й=4 высокая частота, поскольку й >— и вш е дли1< у<5 Грубая сетка На следующей, еще более грубой сетке подавляется правая половина оставшихся частот, и так далее, пока не дойдем до решаемой точно задачи Р(') (с одним неизвестным).
Это показано схематически на рис. 6.16. Назначение операторов сужения и интерполяции — в том, чтобы преобразовать приближенное решение с данной сетки на соседнюю, более грубую или более мелкую. Схематическое описание миотосеточиотс метода Компонента погрешности (хтеО)1 Частота) Р()) Првмя Правая половина половина частот в частот в задаче Р(т) задаче Р()) Правая половина частот в задаче Р(Е) Рнс.
6.16. Схематическое описание подавления компонент погрешности в многосвточном методе. Рекурсивная структура многосеточного метода Используя введенную терминологию, можно дать следующее описание рекурсивной структуры многосеточного метода. На самой мелкой сетке Р(") метод подавляет правую половину частотных компонент погрешности приближенного решения. Это достигается применением только что описанного оператора сглаживания Я.
На следующей сетке с вдвое меньшим числом узлов подавляется правая половина остальных частотных компонент погрешности. Так происходит потому, что двойное уменьшение числа узлов на более грубой сетке имеет видимый эффект удвоения частот. Это иллюстрируется приводимым ниже примером. 356 Глава б. Итерационные методы для линейных систем Оператор сужеиия в одномерном случае Обратимся теперь к оператору сужения В. Он аппроксимирует правую часть гб> задачи Р16 на соседней, более грубой сетке, в результате чего получаем гб 41.
Простейшим способом вычисления вектора тб П был бы простой отбор значений т61 в общих узлах грубой и мелкой сеток. Однако к лучшим результатам приводит вычисление тб П путем усреднения значений т61 в соседних узлах мелкой сетки: значение в узле грубой сетки есть линейная комбинация значения в том же узле для мелкой сетки (с коэффициентом -') и значений в соседних узлах мелкой сетки (с коэффициентом 4). Этот способ вычисления будем называть усреднением. Оба метода иллюстрируются иа рис.
6.17. Суммируя, мы можем дать следующее описание оператора сужения: тб 1 = В(т16) рт-1 6) 1 1 1 4 2 4 1 4 1 1 й 4 1 1 1 г 4 т61. (6.55) 1 1 1 4 2 4 Верхний индекс т' — 1 и нижний индекс т матрицы Р,' ' указывают, что она действует с сетки, состоящей из 2' — 1 узлов, в сетку с 2' ' — 1 узлами. Сухеняе посредством отбора О г 4 Е В тв тг тв тв Сужение посредством усреднения о г 4 е в ю тг 44 1в Рис. 6.17. Сужение с сетки с 2" — 1 = 15 узлами нв сетку с 2 — 1 = 7 узлами. (Показаны также граничные узлы с нулевыми значениями.) 357 блй Многоссточныс методы В двумерном случае сужение означало бы усреднение с участием восьми ближайших соседей данного узла сетки: значение в самом этом узле берется с коэффициентом 1, значения в соседних узлах слева, справа, сверху и снизу берутся с коэффициентом — ' и значения в четырех оставшихся соседних узлах 8 (сверху слева, снизу слева, сверху справа, снизу справа) — с коэффициеитом —,В .
Оператор иитерполяции в одномерном случае Оператор интерполяции 7п отображает приближенное решение 4111 1) иа грубой сетке в функцию Ф> иа соседней, более мелкой сетке. Решение 1111 ') иитерполируется иа мелкую сетку, как показано иа рис. 6.18: значения иа мелкой Сеточная функция иа грубой сепсе о. В 10 12 14 1В 0 2 Иитероалирояаииая функция иа мелкой сепсе 4 В В 1О 12 14 1В Рис. 6.18.
Интерполяция с сетки с 2 — 1 = 7 узлами на сетку с 2 — 1 = 15 узлами. (Показаны также граничные узлы с нулевыми значениями.) сетке восполняются посредством простой линейной интерполяции (при этом используются граничные узлы, в которых значения функции равны нулю). Математически зто можно описать соотношением 1 2 1 1 1 2 2 )6) =7п(16-'>) =Р.* .аО-1> = 1-1 (6.56) 1 .
1 2 ' 2 358 Глава 6. Итерационные методы для линейных систем Верхний индекс 1 и нижний индекс 1 — 1 матрицы Рг, указывают, что она действует с сетки, состоящей из 2' ' — 1 узлов, в сетку с 2' — 1 узлами. Заметим, что Р,' = 2(Рг ~)т. Другими словами, интерполирование и сужение по существу являются транспонированными друг к другу операциями. Этот факт буде важен для проводимого ниже анализа сходимости. В двумерном случае интерполяция также связана с усреднением по узлам грубой сетки, соседствующим с данным узлом мелкой сетки (интерполяция тривиальна, если узел мелкой сетки принадлежит и грубой; в интерполяцию вовлечены два узла, если у узла мелкой сетки лишь два соседа на грубой (слева и справа или сверху и снизу), и четыре узла, в противном случае). Точноерешение 1 Правая часть 0.6 О.6 -1 0 -1 0 ~гш+ЩгяД 1 1г„Л !О 0.8 10 0.6 1О 0.4 0.2 1О 0 2 4 6 Номер итерации ш 2 4 6 8 Номер итерации вг Рнс.
6.19а. Решение одномерной модельной задачи многосеточным методом. Соберем все вместе Проведем восемь итераций только что описанного алгоритма для задачи, представленной на двух графиках рис. 6.19а. На них показаны точное решение х (левый график) и правая часть Ь (правый график). Число неизвестных равно 2т — 1 = 127. Сходимость многосеточного метода иллюстрируют три графика на рис. 6.19Ь.
На левом графике нижнего ряда рис. 6.19а показано отношение последовательных невязок 9г +г)и)г ф индекс т есть номер итерации многосеточного метода (т. е. номер обращения к РМ0; см. алгоритм 6.17). Эти 360 Глава 6. Итерационные методы для линейных систем отношения равны приблизительно 0.15, что означает: на каждой итерации многосеточного метода невязка убывает более чем в 6 раз. Быстрая сходнмость видна и из правого графика того же ряда, представляющего собой полулогарифмнческий график величины 3т,„)! как функции от тп.
Как и следовало ожцдать, зто прямая линия с угловым коэффициентом 1ойш(0.15). Наконец, на графике рис. 6.19Ь изображены все восемь векторов ошибки х„— х. Из этого полулогарифмического графика видно,что векторы постепенно сглаживаются и становятся параллельными, получаясь один нз другого умножением на постоянный коэффициент ~ 1об,е(0.15) ~. На рис. 6.20 показан аналогичный пример для двумерной модельной задачи. Доказательство сходимости В заключение, мы дадим набросок доказательства сходимости, показывающего, что общая погрешность за один гМС У-цикл умножается на константу, меньшую, чем 1, и не зависяшую от размера сетки Юа = 2" — 1. Это означает, что число гМС Ч-циклов, необходимых для того, чтобы снизить погрешность в любое число раз, большее 1, не зависит от й. Поэтому суммарная работа пропорциональна стоимости одного и'МС Ч-цикла, т.
е. пропорциональна числу неизвестных п. Мы упростим доказательство, анализируя лишь один Ч-цикл и предполагая по ицдукции, что задача на грубой сетке решается гпочпо (43]. В действительности, она не решается вполне точно, однако нашего грубого анализа достаточно, чтобы понять смысл доказательства: низкочастотная погрешность ослабляется на более грубой сетке, а высокочастотная погрешность исключается на мелкой. Выпишем теперь все формулы, определяющие Ч-цикл, и объединим их в одну формулу типа «новый ебй = М е®», где ебй = хбй — х есть вектор ошибки, а М вЂ” матрица, собственные значения которой определяют скорость сходимостн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
