Многосеточный метод - Multigrid method

В численном анализе , A многосеточный метод ( метод МГ ) представляет собой алгоритм для решения дифференциальных уравнений с использованием иерархии из дискретизаций . Они являются примером класса техник, называемых методами с несколькими разрешениями , которые очень полезны в задачах, демонстрирующих несколько масштабов поведения. Например, многие базовые методы релаксации демонстрируют разные скорости сходимости для коротковолновых и длинноволновых компонентов, предполагая, что эти разные масштабы следует рассматривать по-разному, как в подходе анализа Фурье к многосеточной сети. Методы MG могут использоваться как решатели, так и как предобуславливатели .

Основная идея многосеточного решения заключается в ускорении сходимости базового итерационного метода (известного как релаксация, который обычно уменьшает коротковолновую погрешность) путем глобальной корректировки приближения решения с мелкой сеткой время от времени, выполняемой путем решения грубой задачи . Грубая задача, хотя и дешевле в решении, похожа на задачу с мелкой сеткой в том, что она также имеет коротковолновые и длинноволновые ошибки. Это также можно решить, сочетая расслабление и обращение к еще более грубым сеткам. Этот рекурсивный процесс повторяется до тех пор, пока не будет достигнута сетка, в которой стоимость прямого решения ничтожна по сравнению со стоимостью одной развертки релаксации на мелкой сетке. Этот многосеточный цикл обычно уменьшает все компоненты ошибки на фиксированную величину, значительно меньшую единицы, независимо от размера ячеек мелкой сетки. Типичное применение многосеточных систем - численное решение эллиптических уравнений в частных производных в двух или более измерениях.

Многосеточные методы могут применяться в сочетании с любыми обычными методами дискретизации. Например, метод конечных элементов может быть преобразован в многосеточный метод. В этих случаях многосеточные методы являются одними из самых быстрых методов решения, известных сегодня. В отличие от других методов, многосеточные методы являются общими тем, что они могут обрабатывать произвольные области и граничные условия . Они не зависят от разделимости уравнений или других специальных свойств уравнения. Они также широко используются для более-сложных несимметричных и нелинейных систем уравнений, как уравнения Ламе в упругости или уравнений Навье-Стокса .

Алгоритм

Визуализация итеративного многосеточного алгоритма для быстрой O (n) сходимости.

Существует множество вариаций многосеточных алгоритмов, но их объединяет то, что учитывается иерархия дискретизаций (сеток). Важные шаги:

Сглаживание - уменьшение высокочастотных ошибок, например, с использованием нескольких итераций метода Гаусса – Зейделя .
Остаточное вычисление - вычисление остаточной ошибки после операции (операций) сглаживания.
Ограничение - уменьшение остаточной ошибки до более грубой сетки.
Интерполяция или удлинение - интерполяция поправки, вычисленной на более грубой сетке, в более мелкую сетку.
Корректировка - добавление расширенной более крупной сетки на более мелкую сетку.

Существует множество вариантов многосеточных методов с различными компромиссами между скоростью решения одной итерации и скоростью сходимости с указанной итерацией. Три основных типа - это 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 :

function phi = V_Cycle(phi,f,h)
    % Recursive V-Cycle Multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-Smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = V_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Post-Smoothing
    phi = smoothing(phi,f,h);
end

Следующее представляет многосетку с F-циклом . Этот многосеточный цикл медленнее, чем V-Cycle на итерацию, но приводит к более быстрой сходимости.

function phi = F_Cycle(phi,f,h)
    % Recursive F-cycle multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = F_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Re-smoothing
    phi = smoothing(phi,f,h);

    % Compute residual errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = V_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Post-smoothing
    phi = smoothing(phi,f,h);
end

Точно так же процедуры могут быть изменены, как показано в псевдокоде стиля MATLAB для 1 итерации многосеточного W-цикла для даже более высокой скорости сходимости в некоторых случаях:

function phi = W_cycle(phi,f,h)
    % Recursive W-cycle multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = W_cycle(eps,rhs,2*h);
    end

    % Prolongation and correction
    phi = phi + prolongation(eps);

    % Re-smoothing
    phi = smoothing(phi,f,h);

    % Compute residual errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = W_cycle(eps,rhs,2*h);
    end

    % Prolongation and correction
    phi = phi + prolongation(eps);

    % Post-smoothing
    phi = smoothing(phi,f,h);
end

Вычислительная стоимость

Предполагая двумерную постановку задачи, вычисления перемещаются по иерархии сетки по-разному для разных многосеточных циклов.

Этот подход имеет преимущество перед другими методами в том, что он часто линейно масштабируется с количеством используемых дискретных узлов. Другими словами, он может решить эти проблемы с заданной точностью за количество операций, пропорциональное количеству неизвестных.

Предположим, что имеется дифференциальное уравнение, которое можно решить приближенно (с заданной точностью) на сетке с заданной плотностью точек сетки . Предположим, кроме того, что решение на любой сетке может быть получено с заданным усилием из решения на более грубой сетке . Здесь - отношение точек сетки на «соседних» сетках, которое предполагается постоянным по всей иерархии сетки, и представляет собой некоторую постоянную величину, моделирующую усилия по вычислению результата для одной точки сетки. ${\ displaystyle i}$ ${\ displaystyle N_ {i}}$ ${\ displaystyle N_ {i}}$ ${\ displaystyle W_ {i} = \ rho KN_ {i}}$ ${\ displaystyle i + 1}$ ${\ Displaystyle \ rho = N_ {я + 1} / N_ {я} <1}$ ${\ displaystyle K}$

Затем для попытки получения решения на сетке получается следующее рекуррентное соотношение : ${\ displaystyle k}$

{\ Displaystyle W_ {k} = W_ {k + 1} + \ rho KN_ {k}}

Пример скорости сходимости многосеточных циклов по сравнению с другими операторами сглаживания.

В частности, для самой тонкой сетки мы находим, что ${\ displaystyle N_ {1}}$

{\ Displaystyle W_ {1} = W_ {2} + \ rho KN_ {1}}

Объединение этих двух выражений (и использование ) дает ${\ Displaystyle N_ {k} = \ rho ^ {k-1} N_ {1}}$

{\ Displaystyle W_ {1} = KN_ {1} \ sum _ {p = 0} ^ {n} \ rho ^ {p}}

Затем, используя геометрический ряд , находим (для конечных ) ${\ displaystyle n}$

{\ displaystyle W_ {1} <KN_ {1} {\ frac {1} {1- \ rho}}}

то есть решение может быть получено вовремя. Следует отметить, что есть одно исключение из многосеточной сети с W-циклом, используемой для решения одномерной задачи; это привело бы к сложности. ${\ Displaystyle О (Н)}$ ${\ Displaystyle О (Н)}$ ${\ Displaystyle O (Nlog (N))}$

Предварительное кондиционирование многосеточных сетей

Многосеточный метод с намеренно сниженным допуском может использоваться в качестве эффективного средства предварительной обработки для внешнего итеративного решателя, например, решение все еще может быть получено вовремя, а также в случае, когда многосеточный метод используется в качестве решателя. Многосеточная предварительная подготовка используется на практике даже для линейных систем, обычно с одним циклом на итерацию, например, в Hypre . Его главное преимущество по сравнению с чисто многосеточным решателем особенно очевидно для нелинейных задач, например, для задач на собственные значения . ${\ Displaystyle О (Н)}$

Если матрица исходного уравнения или задачи на собственные значения является симметричной положительно определенной (SPD), предварительное кондиционирование также обычно строится так, чтобы быть SPD, так что стандартные итерационные методы сопряженного градиента (CG) все еще могут использоваться. Такие наложенные ограничения SPD могут усложнить построение модуля предварительной обработки, например, требуя скоординированного предварительного и последующего сглаживания. Однако методы наискорейшего спуска с предварительным условием и гибкие методы CG для линейных систем SPD и LOBPCG для задач с симметричными собственными значениями являются устойчивыми, если предварительное кондиционирование не является SPD.

Предварительный кондиционер Bramble – Pasciak – Xu

Первоначально описано в Ph.D. Сюй. диссертации и позже опубликованной в Bramble-Pasciak-Xu, BPX-preconditioner является одним из двух основных многосеточных подходов (другой - классический многосеточный алгоритм, такой как V-цикл) для решения крупномасштабных алгебраических систем, возникающих в результате дискретизации модели в науке и технике, описываемые уравнениями в частных производных. С точки зрения структуры коррекции подпространства, блок предварительной обработки BPX представляет собой метод коррекции параллельного подпространства, тогда как классический V-цикл является методом последовательной коррекции подпространства. Предобуславливатель BPX, как известно, является более параллельным и в некоторых приложениях более надежным, чем классический многосеточный метод V-цикла. Метод широко используется исследователями и практиками с 1990 года.

Обобщенные многосеточные методы

Многосеточные методы можно обобщить по-разному. Они могут применяться естественным образом в пошаговом решении параболических уравнений в частных производных или могут применяться непосредственно к уравнениям в частных производных, зависящих от времени . Исследования многоуровневых методов для уравнений в частных производных гиперболического типа продолжаются. Многосеточные методы также могут применяться к интегральным уравнениям или для задач статистической физики .

Другой набор методов множественного разрешения основан на вейвлетах . Эти вейвлет-методы можно комбинировать с многосеточными методами. Например, одним из видов использования вейвлетов является переформулировка подхода конечных элементов в терминах многоуровневого метода.

Адаптивная многосеточная сеть демонстрирует адаптивное уточнение сетки , то есть регулирует сетку по мере выполнения вычислений способом, зависящим от самого вычисления. Идея состоит в том, чтобы увеличивать разрешение сетки только в тех областях решения, где это необходимо.

Алгебраическая многосетка (AMG)

Практически важные расширения многосеточных методов включают методы, в которых для построения многоуровневой иерархии не используются уравнения в частных производных или геометрические проблемы. Такие алгебраические многосеточные методы (AMG) строят свою иерархию операторов непосредственно из системной матрицы. В классическом AMG уровни иерархии - это просто подмножества неизвестных без какой-либо геометрической интерпретации. (В более общем смысле, неизвестные с крупной сеткой могут быть конкретными линейными комбинациями неизвестных с мелкой сеткой.) Таким образом, методы AMG становятся решателями черного ящика для определенных классов разреженных матриц . AMG считается выгодным в основном там, где геометрическая многосеточная технология слишком сложна для применения, но часто используется просто потому, что избегает кодирования, необходимого для истинной многосеточной реализации. Хотя классический AMG был разработан первым, родственный алгебраический метод известен как сглаженное агрегирование (SA).

В обзорной статье Цзиньчао Сю и Людмила Зикатанова «алгебраические многосеточные» методы рассматриваются с абстрактной точки зрения. Они разработали единую структуру, и существующие алгебраические многосеточные методы могут быть последовательно выведены. Была получена абстрактная теория о том, как построить оптимальное грубое пространство, а также квазиоптимальные пространства. Кроме того, они доказали, что при соответствующих предположениях абстрактный двухуровневый метод AMG сходится равномерно относительно размера линейной системы, вариации коэффициентов и анизотропии. Их абстрактная структура охватывает большинство существующих методов AMG, таких как классический AMG, AMG с минимизацией энергии, AMG без сглаживания и сглаживания агрегации и спектральный AMGe.

Многосеточные по времени методы

Многосеточные методы также были приняты для решения задач начального значения . Особый интерес здесь представляют многосеточные параллельные во времени методы: в отличие от классических методов Рунге – Кутты или линейных многоступенчатых методов, они могут предлагать параллелизм во временном направлении. Хорошо известный метод параллельной интеграции Parareal во времени также можно переформулировать как двухуровневую многосетку во времени.

Multigrid для почти особых проблем

Практически единичные проблемы возникают в ряде важных физических и технических приложений. Простой, но важный пример почти сингулярных задач можно найти в формулировке линейной упругости смещения для почти несжимаемых материалов. Как правило, основная проблема при решении таких почти сингулярных систем сводится к тому, чтобы обработать почти сингулярный оператор, задаваемый с помощью робастного отношения к положительному, но небольшому параметру . Здесь симметричный полуопределенный оператор с большим нулевым пространством , а - симметричный положительно определенный оператор. Было проведено множество работ, направленных на создание надежного и быстрого многосеточного метода для решения таких почти исключительных проблем. Общее руководство было предоставлено в качестве принципа проектирования для достижения параметров (например, размера ячейки и физических параметров, таких как коэффициент Пуассона, которые появляются в почти сингулярном операторе), независимой скорости сходимости многосеточного метода, применяемого к таким почти сингулярным системам, т. Е. В каждая сетка, пространственная декомпозиция, на основе которой применяется сглаживание, должна быть построена так, чтобы нулевое пространство особой части почти сингулярного оператора было включено в сумму локальных нулевых пространств, пересечение нулевого пространство и локальные пространства, полученные в результате пространственных разложений. ${\ displaystyle A + \ varepsilon M}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle A}$ ${\ displaystyle M}$

Примечания

использованная литература

Г. П. Астрачанцев (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.

Languages

In other projects