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

В вычислительной науке мы часто сталкиваемся с большими линейными системами, которые мы должны решать некоторыми (эффективными) способами, например, прямыми или итерационными методами. Если сосредоточиться на последнем, как мы можем установить, что итерационный метод решения больших линейных систем сходится на практике?

Ясно, что мы можем проводить анализ методом проб и ошибок (см. Почему мой итерационный линейный решатель не сходится? ) И полагаться на итерационные методы, которые гарантируют сходимость по доказательствам или имеют хорошую базу опыта (например, методы подпространства Крылова, такие как CG и GMRES). для симметричной и несимметричной систем соответственно).

Но что можно сделать для установления конвергенции на практике? и что сделано?

linear-algebra iterative-method convergence krylov-method Аллан П. Энгсиг-Каруп
источник

Отличный вопрос! Когда вы говорите «установить конвергенцию», вы имеете в виду «установить, что решение сходится» или «установить, что конвергенция произойдет»? Я знаю, например, что у объекта PETSc KSP есть несколько методов по умолчанию для проверки сходимости (норма ошибки уменьшается, максимальное количество итераций). Это тот ответ, который вы ищете?

Арон Ахмадиа

@aron: Думаю, будет интересно увидеть ответы на оба вопроса.

Аллан П. Энгсиг-Каруп

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

PETSc использует объект, называемый KSPMonitor, для контроля за ходом итерационного решателя и принятия решения о том, сходится ли или расходится решатель. Монитор использует четыре различных критерия, чтобы решить, стоит ли останавливаться. Более подробную информацию об обсуждении можно найти на странице руководства для KSPGetConvergedReason () .

$x$

A x = b

$Ax=b$

\hat{x}

$\hat{x}$

\hat{r}

$\hat{r}$

$\left(P^{-1}(Ax − b) \right)$
$\hat{r} = P^{- 1} (A \hat{x} - b)$ $\hat{r}=P^{-1}(A\hat{x}-b)$
$\left(AP^{-1}Px = b \right)$
$\hat{r} = A \hat{x} - b$ $\hat{r}=A\hat{x}-b$

Критерии конвергенции

$a_{tol}$ $‖ \hat{r} ‖ \leq a_{t o l}$ $\|\hat{r}\| \le a_{tol}$
Относительный допуск - критерий относительного допуска выполняется, когда норма остатка меньше нормы правой части на коэффициент предварительно определенной константы : $r_{tol}$ $‖ \hat{r} ‖ \leq r_{t o l} \cdot ‖ b ‖$ $\|\hat{r}\| \le r_{tol}\cdot \|b\|$
Другие критерии - итеративное решение также может сходиться из-за обнаружения небольшой длины шага или отрицательной кривизны.

Критерии расхождения

Максимум итераций - количество итераций, которые может выполнить решатель, ограничено максимальными итерациями. Если ни один из других критериев не был достигнут при достижении максимального числа итераций, монитор возвращается как отклоненный.
Остаточный NaN - если в любой точке остаток оценивается как NaN, решатель возвращается как отклоненный.
Расхождение остаточной нормы Монитор возвращается как отклоненный, если в любой точке норма остатка больше, чем норма правой части, на коэффициент предопределенной константы : $d_{tol}$
$‖ \hat{r} ‖ \geq d_{t o l} \cdot ‖ b ‖$ $\|\hat{r}\| \ge d_{tol}\cdot \|b\|$
Разбивка решателя Сам метод Крылова может сигнализировать о расхождении, если он обнаруживает особую матрицу или предобусловливатель.

Арон Ахмадия
источник

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

Ответы: