В чем заключается принцип сходимости подпространственных методов Крылова для решения линейных систем уравнений?

Насколько я понимаю, существует две основные категории итерационных методов решения линейных систем уравнений:

Стационарные методы (Якоби, Гаусс-Зайдель, СОР, Мультисетка)
Методы подпространства Крылова (Conjugate Gradient, GMRES и др.)

Я понимаю, что большинство стационарных методов работают путем итеративного ослабления (сглаживания) мод Фурье ошибки. Насколько я понимаю, метод сопряженных градиентов (метод подпространств Крылова) работает, «шагая» через оптимальный набор направлений поиска по степеням матрицы, примененной к му остатку. Является ли этот принцип общим для всех методов подпространства Крылова? Если нет, то как в целом охарактеризовать принцип сходимости подпространственных методов Крылова? $n$

linear-algebra convergence krylov-method conjugate-gradient Пол
источник

Ваш анализ стационарных методов смещен простыми модельными проблемами, потому что они могут быть проанализированы с точки зрения мод Фурье. Он также игнорирует неявное переменное направление (ADI) и многие другие методы. Смысл большинства «стационарных методов» состоит в том, чтобы объединить множество простых «приближенных частичных» решателей в один итерационный решатель. Смысл методов Крылова состоит в том, чтобы ускорить (или даже навязать) сходимость данной стационарной линейной итерации.

Томас Климпел

Я думаю, что статья, написанная для ответа на ваши вопросы, - это Ипсен и Мейер. Идея методов Крылова, амер. Математика Ежемесячно 105 (1998), стр. 889-899. Это чудесно хорошо написанная и разъясняющая статья, доступная здесь .

Эндрю Т. Баркер

@ AndrewT.Barker: Круто! Спасибо Андрей! :)

Павел

Ответы:

В общем, все методы Крылова, по сути, ищут многочлен, который мал при оценке по спектру матрицы. В частности, й остаток метода Крылова (с нулевым начальным предположением) можно записать в виде $n$

r_{n} = P_{n} (A) b

$r_n = P_n (A) b$

где - некоторый монический многочлен степени . $P_n$ $n$

Если диагонализуем, с , мы имеем $A$ $A=V\Lambda V^{-1}$

\begin{array}{rcl} ‖ r_{n} ‖ & \leq & ‖ V ‖ \cdot ‖ P_{n} (Λ) ‖ \cdot ‖ V^{- 1} ‖ \cdot ‖ b ‖ \\ = & κ (V) \cdot ‖ P_{n} (Λ) ‖ \cdot ‖ b ‖ . \end{array}

$\begin{eqnarray*} \|r_n\| &\leq& \|V\|\cdot \|P_n(\Lambda)\|\cdot \|V^{-1}\|\cdot \|b\|\\ &=& \kappa(V) \cdot \|P_n(\Lambda)\| \cdot \|b\|. \end{eqnarray*}$

В том случае, если нормально (например, симметричный или унитарный) мы знаем , что GMRes конструктов такой многочлена через Арнольди итерацию, в то время как CG строит многочлен с использованием другого внутреннего продукта (см этого ответа для подробностей ). Точно так же BiCG строит свой полином через несимметричный процесс Ланцоша, в то время как чебышевская итерация использует предварительную информацию о спектре (обычно оценки наибольшего и наименьшего собственных значений для симметричных определенных матриц). $A$ $\kappa(V) = 1.$

В качестве классного примера (мотивированного Trefethen + Bau) рассмотрим матрицу, спектр которой таков:

Спектр матрицы

В MATLAB я построил это с помощью:

A = rand(200,200);
[Q R] = qr(A);
A = (1/2)*Q + eye(200,200);

Если мы рассмотрим GMRES, который строит многочлены, которые фактически минимизируют остаток по всем моническим многочленам степени , мы можем легко предсказать историю остатков, посмотрев на многочлен-кандидат $n$

P_{n} (z) = (1 - z)^{n}

$P_n (z) = (1-z)^n$

который в нашем случае дает

| P_{n} (z) | = \frac{1}{2^{n}}

$|P_n(z)| = \frac{1}{2^n}$

для в спектре . $z$ $A$

Теперь, если мы запустим GMRES на случайной RHS и сравним остаточную историю с этим полиномом, они должны быть очень похожими (возможные значения полинома меньше, чем остаточный GMRES, потому что ): $\|b\|_2 > 1$

Остаточная история

Reid.Atcheson
источник

Не могли бы вы уточнить, что вы подразумеваете под «малым по спектру матрицы»?

Павел

Взятый как комплексный многочлен, многочлен имеет малый модуль в области комплексной плоскости , которая включает в себя спектр . Представьте контурную диаграмму, наложенную на точечную диаграмму собственных значений. Насколько маленький маленький? Это зависит от проблемы, является ли нормальным, и правая частьОсновная идея заключается в том, что последовательности полиномов стремятся постепенно уменьшаться и уменьшаться в спектре, так что остаточная оценка в моем ответе стремится к .

P_{n}

$P_n$

A

$A$

A

$A$

b .

$b.$

(P_{n})

$(P_n)$

0

$0$

Reid.Atcheson

@ Reid.Atcheson: Очень хорошо. Могу ли я порекомендовать написатькак и упомянуть, что это один для нормальных матриц?

‖ V ‖ ‖ V^{- 1} ‖

$\|V\|\|V^{-1}\|$

κ (V)

$\kappa(V)$

Джек Поулсон

Лапласиан, обусловленный оптимальным SOR, имеет спектр, очень похожий на матрицу этого примера. Подробности здесь: scicomp.stackexchange.com/a/852/119

Джед Браун

Строго говоря, CGNE не зависит от спектра, поскольку зависит только от сингулярных значений.

Джед Браун

По нормам

В качестве дополнения к ответу Reid.Atcheson, я хотел бы прояснить некоторые вопросы, касающиеся норм. На итерации GMRES находит многочлен который минимизирует норму невязки $n^{\mathrm{th}}$ $P_n$ $2$

r_{n} = A x_{n} - b = (P_{n} (A) - 1) b - b = P_{n} (A) b .

$r_n = A x_n - b = \big(P_n(A) - 1 \big)b - b = P_n(A) b .$

Предположим, что является SPD, поэтому индуцирует норму и . затем $A$ $A$ $A^{-1}$

\begin{aligned} ‖ r_{n} ‖_{A^{- 1}} & = r_{n}^{T} A^{- 1} r_{n} \\ = (A e_{n})^{T} A^{- 1} A e_{n} \\ = e_{n}^{T} A e_{n} \\ = ‖ e_{n} ‖_{A} \end{aligned}

$\begin{align*} \lVert r_n \rVert_{A^{-1}} &= r_n^T A^{-1} r_n \\ &= (A e_n)^T A^{-1} A e_n \\ &= e_n^T A e_n \\ &= \lVert e_n \rVert_{A} \end{align*}$

где мы использовали ошибку

e_{n} = x_{n} - x_{*} = x_{n} - A^{- 1} b = A^{- 1} r_{n}

$e_n = x_n - x_* = x_n - A^{-1} b = A^{-1} r_n$

Таким образом, норма ошибки эквивалентна норме невязки. Сопряженные градиенты сводят к минимуму норму ошибки, что делает ее относительно более точной при разрешении низкоэнергетических мод. -норм остаточных, который минимизирует GMRES, подобно -норме ошибки, и , следовательно , слабее в том смысле , что режимы с низким потреблением энергии менее хорошо решены. Обратите внимание, что норма остатка по существу бесполезна, потому что она еще слабее на модах с низкой энергией. $A$ $A^{-1}$ $A$ $2$ $A^T A$ $A$

Резкость границ сходимости

Наконец, есть интересная литература о различных методах Крылова и тонкостях сходимости GMRES, особенно для ненормальных операторов.

Nachtigal, Reddy и Trefethen (1992). Насколько быстры несимметричные матричные итерации? (авторский pdf) приводит примеры матриц, для которых один метод значительно превосходит все остальные (по крайней мере, квадратный корень из размера матрицы).
Эмбри (1999). Насколько наглядны границы сходимости GMRES? дает глубокое обсуждение в терминах псевдоспектров, которые дают более четкие границы, а также относится к недиагонализируемым матрицам.
Эмбри (2003) Черепаха и заяц перезапускают GMRES (автор pdf)
Greenbaum, Pták, Strakoš (1996) Любая нерастущая кривая сходимости возможна для GMRES

Джед браун
источник

Вы остановились на превосходной книге Олави Неванлинны: books.google.com/…

Мэтт Кнепли

Итерационные методы в двух словах:

$Ax=b$ $C$
$x = x + C b - C A x$ $x = x + Cb- CAx$ $\|I-CA\|<1$ $C$ $C=D^{-1}$ $D$ является диагональной матрицей, содержащей диагональные элементы ). $A$
Крылов метода методы подпространственная в сущности проекционных методов : Вы выбираете подпространства и искать такие , что остаточный ортогонален . Для методов Крылова конечно, является пространством, охватываемым степенями примененными к начальному остатку. Различные методы соответствуют конкретному выбору (например, для CG и для GMRES). $U,V\subset \mathbb{C}^n$ $\tilde x \in U$ $b-A\tilde x$ $V$ $U$ $A$ $V$ $V=U$ $V=AU$

Свойства сходимости этих методов (и проекционные методы в целом) следует из того , что благодаря соответствующему выбору , то являются оптимальным над (например, они минимизируют ошибку в энергетической норме для CG или остаточного для GMRES). Если вы увеличиваете размерность на каждой итерации, вы гарантированно (в точной арифметике) найдете решение после конечного числа шагов. $V$ $\tilde x$ $U$ $U$

Как отметил Reid Atcheson, используя крыловские пространства для позволяет доказать скорости сходимости в терминах собственных (и , следовательно , число обусловленности) от . Кроме того, они имеют решающее значение для выведения эффективных алгоритмов для вычисления проекции . $U$ $A$ $\tilde x$

Это хорошо объясняется в книге Юсефа Саада об итерационных методах .

Кристиан Клэйсон
источник