В численном анализе , A многосеточный метод ( метод МГ ) представляет собой алгоритм для решения дифференциальных уравнений с использованием иерархии из дискретизаций . Они являются примером класса техник, называемых методами с несколькими разрешениями , которые очень полезны в задачах, демонстрирующих несколько масштабов поведения. Например, многие базовые методы релаксации демонстрируют разные скорости сходимости для коротковолновых и длинноволновых компонентов, что предполагает, что эти разные масштабы следует рассматривать по-разному, как в подходе анализа Фурье к многосеточной сети. [1]Методы MG могут использоваться как решатели, так и как предобуславливатели .
Основная идея многосеточного решения заключается в ускорении сходимости базового итерационного метода (известного как релаксация, который обычно снижает коротковолновую ошибку) путем глобальной корректировки приближения решения с мелкой сеткой время от времени, выполняемой путем решения грубой задачи . Грубая задача, хотя и дешевле в решении, похожа на задачу с мелкой сеткой в том, что она также имеет коротковолновые и длинноволновые ошибки. Это также можно решить, сочетая расслабление и обращение к еще более грубым сеткам. Этот рекурсивный процесс повторяется до тех пор, пока не будет достигнута сетка, в которой стоимость прямого решения ничтожна по сравнению со стоимостью одной развертки релаксации на мелкой сетке. Этот многосеточный цикл обычно уменьшает все компоненты ошибки на фиксированную величину, значительно меньшую единицы, независимо от размера ячеек с мелкой сеткой. Типичное применение многосеточной системы - численное решение эллиптических уравнений в частных производных в двух или более измерениях. [2]
Многосеточные методы могут применяться в сочетании с любыми обычными методами дискретизации. Например, метод конечных элементов может быть преобразован в многосеточный метод. [3] В этих случаях многосеточные методы являются одними из самых быстрых методов решения, известных сегодня. В отличие от других методов, многосеточные методы являются общими тем, что они могут обрабатывать произвольные области и граничные условия . Они не зависят от разделимости уравнений или других специальных свойств уравнения. Они также широко используются для более-сложных несимметричных и нелинейных систем уравнений, как уравнения Ламе в упругости или уравнений Навье-Стокса . [4]
Алгоритм
Существует множество вариаций многосеточных алгоритмов, но их объединяет то, что учитывается иерархия дискретизаций (сеток). Важные шаги: [5] [6]
- Сглаживание - уменьшение высокочастотных ошибок, например, с использованием нескольких итераций метода Гаусса – Зейделя .
- Остаточное вычисление - вычисление остаточной ошибки после операции (операций) сглаживания.
- Ограничение - уменьшение остаточной ошибки до более грубой сетки.
- Интерполяция или удлинение - интерполяция поправки, вычисленной на более грубой сетке, в более мелкую сетку.
- Корректировка - добавление расширенной более крупной сетки на более мелкую сетку.
Существует множество вариантов многосеточных методов с различными компромиссами между скоростью решения одной итерации и скоростью сходимости с указанной итерацией. Три основных типа - это V-цикл, F-цикл и W-цикл. Для дискретной 2D-задачи F-Cycle требует на 83% больше времени для вычисления, чем итерация V-Cycle, а итерация W-Cycle занимает на 125% больше. Если проблема возникает в трехмерной области, то итерация F-цикла и итерация W-цикла занимают примерно на 64% и 75% больше времени соответственно, чем итерация V-цикла без учета накладных расходов . Обычно W-Cycle дает сходство с F-Cycle. Однако в случаях проблем конвекции-диффузии с высокими числами Пекле W-Cycle может показать превосходство по скорости сходимости на итерацию над F-Cycle. Выбор сглаживающих операторов чрезвычайно разнообразен, так как они включают методы подпространства Крылова и могут быть предварительно обусловлены .
Любая итерация геометрического многосеточного цикла выполняется на иерархии сеток и, следовательно, может быть закодирована с использованием рекурсии. Поскольку функция вызывает себя с параметрами меньшего размера (грубее), самая грубая сетка - это то место, где рекурсия останавливается. В случаях, когда система имеет высокое число условий , процедура коррекции модифицируется таким образом, что только часть продолженного решения с более крупной сеткой добавляется на более мелкую сетку.
Эти шаги могут использоваться, как показано в псевдокоде стиля MATLAB для 1 итерации V-Cycle Multigrid : функция phi = V_Cycle ( phi, f, h ) % Рекурсивный V-Cycle Multigrid для решения уравнения Пуассона (\ nabla ^ 2 phi = f) на равномерной сетке с шагом h% Предварительного сглаживанияphi = сглаживание ( phi , f , h ); % Остаточных ошибок вычисленийr = остаток ( phi , f , h ); % Ограничениеrhs = ограничение ( r ); eps = нули ( размер ( справа )); % остановить рекурсию при наименьшем размере сетки, в противном случае продолжить рекурсиюесли smallest_grid_size_is_achaught eps = сглаживание ( eps , rhs , 2 * h ); иначе eps = V_Cycle ( eps , rhs , 2 * h ); конец % Продление и коррекцияфи = фи + продолжение ( eps ); % Пост-сглаживанияphi = сглаживание ( phi , f , h ); конец | Следующее представляет многосетку с F-циклом . Этот многосеточный цикл медленнее, чем V-Cycle на итерацию, но приводит к более быстрой сходимости. функция phi = F_Cycle ( phi, f, h ) % Рекурсивная многосетка с F-циклами для решения уравнения Пуассона (\ nabla ^ 2 phi = f) на равномерной сетке с шагом h% Предварительное сглаживаниеphi = сглаживание ( phi , f , h ); % Остаточных ошибок вычисленийr = остаток ( phi , f , h ); % Ограничениеrhs = ограничение ( r ); eps = нули ( размер ( справа )); % остановить рекурсию при наименьшем размере сетки, в противном случае продолжить рекурсиюесли smallest_grid_size_is_achaught eps = сглаживание ( eps , rhs , 2 * h ); иначе eps = F_Cycle ( eps , rhs , 2 * h ); конец % Продление и коррекцияфи = фи + продолжение ( eps ); % Повторное сглаживаниеphi = сглаживание ( phi , f , h ); % Расчет остаточных ошибокr = остаток ( phi , f , h ); % Ограничениеrhs = ограничение ( r ); % остановить рекурсию при наименьшем размере сетки, в противном случае продолжить рекурсиюесли smallest_grid_size_is_achaught eps = сглаживание ( eps , rhs , 2 * h ); иначе eps = V_Cycle ( eps , rhs , 2 * h ); конец % Продление и коррекцияфи = фи + продолжение ( eps ); % Пост-сглаживаниеphi = сглаживание ( phi , f , h ); конец | Точно так же процедуры могут быть изменены, как показано в псевдокоде стиля MATLAB для 1 итерации многосеточного W-цикла для даже более высокой скорости сходимости в некоторых случаях: функция phi = W_cycle ( phi, f, h ) % Рекурсивная многосетка с W-циклами для решения уравнения Пуассона (\ nabla ^ 2 phi = f) на равномерной сетке с шагом h% Предварительное сглаживаниеphi = сглаживание ( phi , f , h ); % Остаточных ошибок вычисленийr = остаток ( phi , f , h ); % Ограничениеrhs = ограничение ( r ); eps = нули ( размер ( справа )); % остановить рекурсию при наименьшем размере сетки, в противном случае продолжить рекурсиюесли smallest_grid_size_is_achaught eps = сглаживание ( eps , rhs , 2 * h ); иначе eps = W_cycle ( eps , rhs , 2 * h ); конец % Продление и коррекцияфи = фи + продолжение ( eps ); % Повторное сглаживаниеphi = сглаживание ( phi , f , h ); % Расчет остаточных ошибокr = остаток ( phi , f , h ); % Ограничениеrhs = ограничение ( r ); % остановить рекурсию при наименьшем размере сетки, в противном случае продолжить рекурсиюесли smallest_grid_size_is_achaught eps = сглаживание ( eps , rhs , 2 * h ); иначе eps = W_cycle ( eps , rhs , 2 * h ); конец % Продление и коррекцияфи = фи + продолжение ( eps ); % Пост-сглаживаниеphi = сглаживание ( phi , f , h ); конец |
Вычислительная стоимость
Этот подход имеет преимущество перед другими методами в том, что он часто линейно масштабируется с количеством используемых дискретных узлов. Другими словами, он может решить эти проблемы с заданной точностью за количество операций, пропорциональное количеству неизвестных.
Предположим, что имеется дифференциальное уравнение, которое можно решить приближенно (с заданной точностью) на сетке с заданной плотностью точек сетки . Предположим, кроме того, что решение на любой сетке можно получить с заданными усилиями из раствора на более крупной сетке . Здесь, - отношение узлов сетки на "соседних" сетках, которое предполагается постоянным по всей иерархии сетки, и представляет собой некоторое постоянное моделирование усилий по вычислению результата для одной точки сетки.
Затем получается следующее рекуррентное соотношение для попытки получить решение на сетке :
И, в частности, мы находим для самой тонкой сетки что
Комбинируя эти два выражения (и используя ) дает
Затем, используя геометрический ряд , находим (для конечных)
то есть решение может быть получено в время. Следует отметить, что есть одно исключение изт.е. многосеточный W-цикл, используемый для решения одномерной задачи; это приведет ксложность.
Предварительное кондиционирование многосеточных сетей
Многосеточный метод с намеренно сниженным допуском может использоваться в качестве эффективного средства предварительной обработки для внешнего итеративного решателя, например, [7] Решение все еще может быть получено ввремя, а также в случае, когда в качестве решателя используется многосеточный метод. Многосеточная предварительная подготовка используется на практике даже для линейных систем, обычно с одним циклом на итерацию, например, в Hypre . Его главное преимущество по сравнению с чисто многосеточным решателем особенно очевидно для нелинейных задач, например, для задач на собственные значения .
Если матрица исходного уравнения или задачи на собственные значения является симметричной положительно определенной (SPD), предварительное кондиционирование также обычно строится так, чтобы быть SPD, так что стандартные итерационные методы сопряженного градиента (CG) все еще могут использоваться. Такие наложенные ограничения SPD могут усложнить построение модуля предварительной обработки, например, требуя скоординированного предварительного и последующего сглаживания. Однако методы наискорейшего спуска с предварительным условием и гибкие методы CG для линейных систем SPD и LOBPCG для задач симметричных собственных значений, как показано [8], являются устойчивыми, если предварительное кондиционирование не является SPD.
Предварительный кондиционер Bramble – Pasciak – Xu
Первоначально описано в Ph.D. Сюй. тезис [9] и позже опубликованный в Bramble-Pasciak-Xu, [10] предварительное кондиционирование BPX является одним из двух основных многосеточных подходов (другой - классический многосеточный алгоритм, такой как V-цикл) для решения крупномасштабных алгебраических систем. которые возникают в результате дискретизации моделей в науке и технике, описываемых уравнениями в частных производных. Принимая во внимание структуру коррекции подпространства, [11] блок предварительной обработки BPX представляет собой метод коррекции параллельного подпространства, тогда как классический V-цикл является методом последовательной коррекции подпространства. Предобуславливатель BPX, как известно, является более параллельным и в некоторых приложениях более надежным, чем классический многосеточный метод V-цикла. Метод широко используется исследователями и практиками с 1990 года.
Обобщенные многосеточные методы
Многосеточные методы можно обобщить по-разному. Они могут применяться естественным образом в пошаговом решении параболических уравнений в частных производных или могут применяться непосредственно к уравнениям в частных производных, зависящих от времени . [12] Исследования многоуровневых методов для уравнений в частных производных гиперболического типа продолжаются. [13] Многосеточные методы также могут применяться к интегральным уравнениям или для задач статистической физики . [14]
Другой набор методов множественного разрешения основан на вейвлетах . Эти вейвлет-методы можно комбинировать с многосеточными методами. [15] [16] Например, одним из видов использования вейвлетов является переформулировка подхода конечных элементов в терминах многоуровневого метода. [17]
Адаптивная многосеточная сеть демонстрирует адаптивное уточнение сетки , то есть она регулирует сетку по мере выполнения вычислений способом, зависящим от самого вычисления. [18] Идея состоит в том, чтобы увеличить разрешение сетки только в тех областях решения, где это необходимо.
Алгебраическая многосетка (AMG)
Практически важные расширения многосеточных методов включают методы, в которых для построения многоуровневой иерархии не используются уравнения в частных производных или геометрические проблемы. [19] Такие алгебраические многосеточные методы (AMG) строят свою иерархию операторов непосредственно из системной матрицы. В классическом AMG уровни иерархии - это просто подмножества неизвестных без какой-либо геометрической интерпретации. (В более общем смысле, неизвестные с крупной сеткой могут быть конкретными линейными комбинациями неизвестных с мелкой сеткой.) Таким образом, методы AMG становятся решателями черного ящика для определенных классов разреженных матриц . AMG считается выгодным в основном там, где геометрическая многосеточная технология слишком сложна для применения [20], но часто используется просто потому, что позволяет избежать кодирования, необходимого для истинной многосеточной реализации. Хотя классический AMG был разработан первым, родственный алгебраический метод известен как сглаженное агрегирование (SA).
В обзорной статье [21] Цзиньчао Сю и Людмила Зикатанова «алгебраические многосеточные» методы понимаются с абстрактной точки зрения. Они разработали единую структуру, и существующие алгебраические многосеточные методы могут быть последовательно выведены. Была получена абстрактная теория о том, как построить оптимальное грубое пространство, а также квазиоптимальные пространства. Кроме того, они доказали, что при соответствующих предположениях абстрактный двухуровневый метод AMG сходится равномерно относительно размера линейной системы, вариации коэффициентов и анизотропии. Их абстрактная структура охватывает большинство существующих методов AMG, таких как классический AMG, AMG с минимизацией энергии, AMG без сглаживания и сглаживания агрегации и спектральный AMGe.
Многосеточные методы по времени
Многосеточные методы также были приняты для решения задач начального значения . [22] Особый интерес здесь представляют многосеточные методы с параллельным временем: [23] в отличие от классических методов Рунге – Кутты или линейных многоступенчатых методов, они могут предлагать параллелизм во временном направлении. Хорошо известный метод параллельной интеграции Parareal во времени также можно переформулировать как двухуровневую многосетку во времени.
Multigrid для почти особых проблем
Практически единичные проблемы возникают в ряде важных физических и технических приложений. Простой, но важный пример почти сингулярных задач можно найти в формулировке линейной упругости смещения для почти несжимаемых материалов. Как правило, основная проблема для решения таких почти сингулярных систем сводится к рассмотрению почти сингулярного оператора, задаваемого формулой робастно по положительному, но малому параметру . Здесьявляется симметричным полуопределенным оператором с большим нулевым пространством , а- симметричный положительно определенный оператор. Было проведено множество работ, направленных на создание надежного и быстрого многосеточного метода для решения таких почти исключительных проблем. Общее руководство было предоставлено в качестве принципа проектирования для достижения параметров (например, размера ячейки и физических параметров, таких как коэффициент Пуассона, которые появляются в почти сингулярном операторе) независимой скорости сходимости многосеточного метода, применяемого к таким почти сингулярным системам [24]. т.е. в каждой сетке пространственное разложение, на основе которого применяется сглаживание, должно быть построено так, чтобы нулевое пространство особой части почти сингулярного оператора было включено в сумму локальных нулевых пространств, пересечение нулевого пространства и локальных пространств, полученных в результате пространственных разложений.
Заметки
- ^ Роман Винандс; Вольфганг Йоппих (2005). Практический анализ Фурье для многосеточных методов . CRC Press. п. 17. ISBN 978-1-58488-492-7.
- ^ У. Троттенберг; CW Oosterlee; А. Шюллер (2001). Многосеточный . Академическая пресса. ISBN 978-0-12-701070-0.
- ^ Ю Чжу; Андреас К. Канжелларис (2006). Многосеточные методы конечных элементов для моделирования электромагнитного поля . Вайли. п. 132 сл . ISBN 978-0-471-74110-7.
- ^ Шах, Тасним Мохаммад (1989). Анализ многосеточного метода (Диссертация). Оксфордский университет. Bibcode : 1989STIN ... 9123418S .
- ^ MT Heath (2002). «Раздел 11.5.7 Многосеточные методы» . Научные вычисления: вводный обзор . Макгроу-Хилл Высшее образование. п. 478 сл . ISBN 978-0-07-112229-0.
- ^ П. Весселинг (1992). Введение в многосеточные методы . Вайли. ISBN 978-0-471-93083-9.
- ^ Андрей В Князев, Клаус Неймейр. Эффективное решение симметричных задач на собственные значения с использованием многосеточных предобуславливателей в локально оптимальном блочном методе сопряженных градиентов . Электронные транзакции по численному анализу, 15, 38–55, 2003.
- ^ Хенрикус Bouwmeester, Эндрю Догерти, Andrew V Князев. Несимметричное предварительное кондиционирование для методов сопряженного градиента и наискорейшего спуска . Процедуры информатики, том 51, страницы 276–285, Elsevier, 2015. doi : 10.1016 / j.procs.2015.05.241
- ^ Сюй, Цзиньчао. Теория многоуровневых методов. Vol. 8924558. Итака, Нью-Йорк: Корнельский университет, 1989.
- ^ Bramble, Джеймс Х., Джозеф Е. Pasciak и Jinchao Сие. «Параллельные многоуровневые прекондиционеры». Математика вычислений 55, вып. 191 (1990): 1-22.
- ^ Сюй, Цзиньчао. «Итерационные методы декомпозиции пространства и коррекции подпространства». SIAM обзор 34, нет. 4 (1992): 581-613.
- ^ Ф. Хюльземанн; М. Коварщик; М. Мор; У. Рюде (2006). «Параллельно-геометрическая многосетка» . В Аре Магнус Брузет; Аслак Твейто (ред.). Численное решение дифференциальных уравнений в частных производных на параллельных компьютерах . Birkhäuser. п. 165. ISBN 978-3-540-29076-6.
- ^ Например, Я. Блажек (2001). Вычислительная гидродинамика: принципы и приложения . Эльзевир. п. 305. ISBN 978-0-08-043009-6. а также Ачи Брандт и Рима Гандлин (2003). "Multigrid для ассимиляции атмосферных данных: анализ" . В Томас Ю. Хоу; Эйтан Тадмор (ред.). Гиперболические: теория, Числовые, приложения: Труды IX Международной конференции по проблемам гиперболических 2002 года . Springer. п. 369. ISBN. 978-3-540-44333-9.
- ^ Ачи Брандт (2002). «Мультимасштабные научные вычисления: обзор» . У Тимоти Дж. Барта; Тони Чан; Роберт Хеймс (ред.). Мультимасштабные и многомасштабные методы: теория и приложения . Springer. п. 53. ISBN 978-3-540-42420-8.
- ^ Бьорн Энгквист; Улоф Рунборг (2002). «Численное усреднение на основе вейвлетов с приложениями» . У Тимоти Дж. Барта; Тони Чан; Роберт Хеймс (ред.). Мультимасштабные и множественные методы разрешения . Vol. 20 конспектов лекций по вычислительным наукам и технике. Springer. п. 140 сл . ISBN 978-3-540-42420-8.
|volume=
есть дополнительный текст ( справка ) - ^ У. Троттенберг; CW Oosterlee; А. Шюллер (2001). Многосеточный . ISBN 978-0-12-701070-0.
- ^ Альберт Коэн (2003). Численный анализ вейвлет-методов . Эльзевир. п. 44. ISBN 978-0-444-51124-9.
- ^ У. Троттенберг; CW Oosterlee; А. Шюллер (2001). «Глава 9: Адаптивная многосеточная сеть» . Многосеточный . п. 356. ISBN. 978-0-12-701070-0.
- ^ Яир Шапира (2003). «Алгебраическая многосетка» . Матричная многосетка: теория и приложения . Springer. п. 66. ISBN 978-1-4020-7485-1.
- ^ У. Троттенберг; CW Oosterlee; А. Шюллер (2001). Многосеточный . п. 417. ISBN 978-0-12-701070-0.
- ^ Сюй, Дж. И Зикатанов, Л., 2017. Алгебраические многосеточные методы. Acta Numerica, 26, стр. 591-721.
- ^ Хакбуш, Вольфганг (1985). «Параболические многосеточные методы» . Вычислительные методы в прикладных науках и технике, VI : 189–197 . Проверено 1 августа 2015 года .
- ^ Хортон, Грэм (1992). «Параллельный во времени многосеточный метод». Коммуникации в прикладных численных методах . 8 (9): 585–595. DOI : 10.1002 / cnm.1630080906 .
- ^ Юн-Джу Ли, Цзиньбяо Ву, Цзиньчао Сю и Людмил Зикатанов, Робастные методы коррекции подпространства для почти сингулярных систем, математические модели и методы в прикладных науках, Vol. 17, No 11, стр. 1937-1963 (2007)
Рекомендации
- Г. П. Астрачанцев (1971), Итерационный метод решения задач эллиптической сети . СССР Comp. Математика. Математика. Phys. 11, 171–182.
- Н. С. Бахвалов (1966), О сходимости релаксационного метода с естественными ограничениями на эллиптический оператор . СССР Comp. Математика. Математика. Phys. 6, 101–13.
- Ачи Брандт (апрель 1977 г.), « Многоуровневые адаптивные решения краевых задач », « Математика вычислений» , 31 : 333–90.
- Уильям Л. Бриггс, Ван Эмден Хенсон и Стив Ф. Маккормик (2000), Многосеточное учебное пособие (2-е изд.), Филадельфия: Общество промышленной и прикладной математики , ISBN 0-89871-462-1 .
- Р. П. Федоренко (1961) . Релаксационный метод решения эллиптических разностных уравнений . СССР вычисл. Математика. Математика. Phys. 1, стр. 1092.
- Р. П. Федоренко (1964), Скорость сходимости одного итерационного процесса. СССР вычисл. Математика. Математика. Phys. 4, стр. 227.
- Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, ВР (2007). «Раздел 20.6. Многосеточные методы решения краевых задач» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
Внешние ссылки
- Репозиторий для многосеточных, многоуровневых, многомасштабных методов, агрегации, исправления дефектов и декомпозиции доменов
- Многосеточный учебник
- Алгебраический многосеточный учебник
- Ссылки на презентации AMG