Существуют ли эвристики для оптимизации метода последовательной избыточной релаксации (SOR)?

10

Насколько я понимаю, последовательная релаксация работает путем выбора параметра 0≤ω≤2 и использования линейной комбинации (квази) итерации Гаусса-Зейделя и значения на предыдущем временном шаге ... то есть

UК+1знак равно(ω)UгsК+1+(1-ω)UК

Я состояние «квази» , потому что UгsК+1 включает в себя последнюю информацию обновленное в соответствии с этим правилом, в любом временном шаге. (заметьте, что при ωзнак равно1 это точно гаусс-сейдель).

В любом случае я читал, что при оптимальном выборе для ω (так что итерация сходится быстрее, чем в любой другой) приближается к 2 для задачи Пуассона, когда пространственное разрешение приближается к нулю. Существует ли подобная тенденция для других симметричных, диагонально доминирующих задач? То есть есть ли способ выбрать омега оптимально, не встраивая его в схему адаптивной оптимизации? Существуют ли другие эвристики для других типов проблем? Какие виды проблем были бы недостаточной релаксации ( ω<1 ) было бы оптимальным?

linear-algebra optimization iterative-method Пол
источник
Не совсем твой вопрос, но см. Салахутдинов и Ровейс, Адаптивные методы чрезмерно релаксирующих границ 2003, 8с. (У адаптивных ускорений высокая отдача за доллар, но на самом деле их невозможно проанализировать, поэтому не по теме здесь.)
Денис

Ответы:

12

Затухший якоби

Пусть матрица имеет диагональ D . Если спектр D - 1 A лежит в интервале [ a , b ] положительной вещественной оси, то итерационная матрица Якоби с коэффициентом затухания ω B Jacobi = I - ω D - 1 A имеет спектр в диапазоне [ 1 - ω b , 1 - ω a ] , поэтому минимизируем спектральный радиус при ω opt = 2ADD-1A[a,б]ω

ВЯкобизнак равноя-ωD-1A
[1-ωб,1-ωa] дает коэффициент сходимости ρopt=1-2a
ωвыбиратьзнак равно2a+б
Еслиa≪b, то этот коэффициент сходимости очень плохой, как и ожидалось. Обратите внимание, что сравнительно легко оценитьbс помощью метода Крылова, но довольно дорого оценитьa.
ρвыбиратьзнак равно1-2aa+бзнак равноб-aa+б,
a«ббa

Последовательная чрезмерная релаксация (SOR)

D-1AμМаксимумя-D-1AμМаксимум<1

ωвыбиратьзнак равно1+(μМаксимум1+1-μМаксимум2)2
ρвыбиратьзнак равноωвыбирать-1.
ωвыбиратьμМаксимум→1

Комментарии

ωзнак равно1ω<1

D-1A

ВSORзнак равно1-(1ωD+L)-1A
(1ωD+L)-1A
Джед браун
источник
4
Я согласен, что это уже не 1950 год: о), однако я не согласен с тем, что больше нет смысла использовать стационарные итеративные решатели. Мы можем добиться многосеточной эффективности учебника, используя стационарный итерационный решатель для решения прикладных задач инженерного характера, основанный на нелинейных решателях со свободной поверхностью высокого порядка (как потенциального потока, так и уравнения Эйлера). Эффективность была такой же хорошей, как и у заранее подготовленного метода подпространства Крылова GMRES с достижимой точностью (наш недавний паб находится здесь: onlinelibrary.wiley.com/doi/10.1002/fld.2675/abstract, служащий в качестве подтверждения концепции).
Аллан П. Энгсиг-Каруп
1
Вы используете Gauss-Seidel в качестве сглаживающего средства для многосетки (к которой относятся такие методы, как SOR). Если многосетка работает хорошо, внешний метод Крылова также не нужен (хотя в вашей статье эти сравнения не показаны). Как только многосетка начинает терять эффективность (например, более 5 итераций для достижения ошибки дискретизации), обычно стоит обернуть метод Крылова вокруг многосеточного цикла.
Джед Браун
Весь метод представляет собой p-многосетку со сглаживанием типа GS, однако полный метод можно записать как стационарный итерационный метод, поскольку все операторы постоянны. Вы можете рассматривать его как предобусловленный метод Ричардсона, а M - предобусловливатель, построенный из многосеточного метода. Анализ был сделан, но еще не опубликован. На самом деле, эта работа пошла в другом направлении, которое вы предлагаете. Метод Крылова в этой работе (GMRES) был отброшен, а затем он был превращен в многосеточный метод высокого порядка, поскольку мы обнаружили, что он был столь же эффективным (и с уменьшенными требованиями к памяти).
Аллан П. Энгсиг-Каруп
пчасп
Обратите внимание, что в многосеточных сглаживателях иногда предпочтительно (если позволяет архитектура) сделать мультипликативную связь высокого порядка / низкого порядка. Это также расширяет формулировку «Ричардсон». (На прошлой неделе у меня была дискуссия на конференции с парнем, который хотел рассмотреть практически все методы как предварительно подготовленные Ричардсона с вложенной итерацией, что, я не думаю, является особым преимуществом по сравнению с другими утверждениями состава решателя. Я не знаю, является ли это имеет отношение к вам, но ваши замечания напомнили мне о дискуссии.)
Джед Браун