Критерии остановки для итерационных линейных решателей, применяемые к почти сингулярным системам

Рассмотрим $Ax=b$ где $A$ почти особенное, что означает, что есть собственное значение $\lambda_0$ в $A$ , которое очень мало. Обычный критерий остановки итерационного метода основан на остаточном $r_n:=b-Ax_n$ и рассматривает итерации можно остановить , когда $\|r_n\|/\|r_0\|<tol$ с $n$ числа итераций. Но в случае, который мы рассматриваем, может быть большая ошибка $v$живя в собственном пространстве, связанном с малым собственным значением $\lambda_0$ которое дает малую невязку $Av=\lambda_0v$ . Предположим , что начальная остаточная $r_0$ велико, то это может произойти , мы останавливаемся на $\|r_n\|/\|r_0\|<tol$ но ошибка $x_n-x$ по - прежнему велика. Что является лучшим индикатором ошибки в этом случае? Is $\|x_{n}-x_{n-1}\|$ хороший кандидат?

Пожалуйста, никогда не используйте разницу между последовательными итерациями для определения критериев остановки. Это неправильно диагностирует стагнацию конвергенции. Большинство несимметричных итераций матрицы не являются монотонными, и даже GMRES в точной арифметике без перезапусков может стагнировать в течение произвольного числа итераций (вплоть до размерности матрицы) перед тем, как сойтись внезапно. Смотрите примеры в Nachtigal, Reddy и Trefethen (1993) .

Лучший способ определить сходимость

Нас обычно интересует точность нашего решения больше, чем размер остатка. В частности, мы могли бы гарантировать, что разность между приближенным решением и точным решением x удовлетворяет | х н - х | < c для некоторого указанного пользователем c . Оказывается, что можно добиться этого, найдя x n такой, что | A x n - b | < c ϵ где ϵ - наименьшее единственное значение A , обусловленное$x_n$$x$

где мы использовали, что является наибольшим единичным значением A - 1 (вторая строка) и что x точно решает A x = $1/\epsilon$$A^{-1}$$x$$A x = b$ (третья строка).

Оценка наименьшего единственного значения $\epsilon$

Точная оценка наименьшего сингулярного значения обычно не доступна непосредственно из задачи, но ее можно оценить как побочный продукт сопряженного градиента или итерации GMRES. Следует отметить , что хотя оценки наибольших собственных и сингулярных значений, как правило , довольно хорошо после нескольких итераций, точная оценка наималейшего собственному / сингулярных обычно получается только один раз сходимость достигнута. До конвергенции оценка, как правило, будет значительно больше, чем истинное значение. Это говорит о том, что вы должны решить уравнения прежде, чем сможете определить правильный допуск c ϵ . Автоматический допуск сходимости, который принимает заданную пользователем точность $\epsilon$$c\epsilon$$c$для решения и оценки наименьшее сингулярное значение с текущим состоянием метода Крылова может сходиться слишком рано, потому что оценка ϵ была намного больше истинного значения.$\epsilon$$\epsilon$

Примечания

1. Выше обсуждение также работает с заменено левым-выдержано оператором P - 1 A и выдержано остаточный P - 1 ( х п - б ) или с правым выдержано оператором P - 1 и ошибками Р ( х п - х ) . Если П - $A$$P^{-1}A$$P^{-1} (A x^n - b)$$A P^{-1}$$P (x_n - x)$$P^{-1}$является хорошим предобусловливателем, предобусловленный оператор будет хорошо подготовлен. Для левого предварительного кондиционирования это означает, что предварительно обработанный остаток может быть сделан небольшим, но истинный остаток может не быть. Для правильной предварительной обработки, легко сделать маленьким, но истинная ошибка | х н - х | может не быть. Это объясняет, почему левое предварительное кондиционирование лучше для уменьшения ошибок, в то время как правильное предварительное кондиционирование лучше для уменьшения остатка (и для отладки нестабильных предварительных кондиционеров).$|P(x_n - x)|$$|x_n-x|$
2. Смотрите этот ответ для более подробного обсуждения норм, минимизированных GMRES и CG.
3. Оценки экстремальных сингулярных значений можно отслеживать с -ksp_monitor_singular_valueпомощью любой программы PETSc. См. KSPComputeExtremeSingularValues ​​() для вычисления особых значений из кода.
4. При использовании GMRES для оценки единичных значений крайне важно, чтобы перезапуски не использовались (например, -ksp_gmres_restart 1000в PETSc).

Другой способ взглянуть на эту проблему - рассмотреть инструменты из дискретных обратных задач, то есть задач, которые включают решение или min | | A x - b | | 2, где A очень плохо обусловлен (то есть отношение между первым и последним единственным значением σ 1 / σ n велико).$Ax=b$$\min ||Ax-b||_2$$A$$\sigma_1/\sigma_n$

Здесь у нас есть несколько методов для выбора критерия остановки, и для итерационного метода я бы рекомендовал критерий L-кривой, поскольку он включает только те количества, которые уже доступны (ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Мой консультант впервые применил этот метод, поэтому я определенно склонен к Это). Я использовал это с успехом в итеративном методе.

$\rho_k=||Ax_k-b||_2$$\eta_k=||x_k||_2$$x_k$$k$

$(\rho_k,\eta_k)$

$abs(\frac{\log(\eta_k)-\log(\eta_{k-1})}{\log(\rho_k)-\log(\rho_{k-1})})$

Существуют также более подробные методы поиска угла, и они работают лучше, но требуют хранения значительного числа итераций. Поиграйте с этим немного. Если вы находитесь в Matlab, вы можете использовать панель инструментов Regularization Tools, которая реализует некоторые из этих функций (в частности, применима «угловая» функция).

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