Документация Engee

Перезапускаемый метод GMRES

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

Использование

gmres(A, b; kwargs...) -> x, [history]

То же, что и gmres!, но выделяет вектор решений x, инициализированный нулями.

gmres!(x, A, b; kwargs...) -> x, [history]

Решает задачу с помощью перезапускаемого GMRES.

Аргументы

  • x: начальное предположение, будет обновляться на месте;

  • A: линейный оператор;

  • b: правая часть.

Ключевые слова

  • initially_zero::Bool: если true предполагает iszero(x) так, чтобы одно произведение матрицы на вектор могло быть сохранено при вычислении начального вектора невязки;

  • abstol::Real = zero(real(eltype(b))), reltol::Real = sqrt(eps(real(eltype(b)))): абсолютный и относительный допуски для условия остановки |r_k| ≤ max(reltol * |r_0|, abstol), где r_k = A * x_k - b

  • restart::Int = min(20, size(A, 2)): перезапускает GMRES после указанного количества итераций;

  • maxiter::Int = size(A, 2): максимальное количество внутренних итераций GMRES;

  • Pl: левый предобуславливатель;

  • Pr: правый предобуславливатель;

  • log::Bool: отслеживание нормы невязки в каждой итерации;

  • verbose::Bool: вывод информации о сходимости во время итераций.

  • orth_meth::OrthogonalizationMethod = ModifiedGramSchmidt(): метод ортогонализации (ModifiedGramSchmidt(), ClassicalGramSchmidt(), DGKS())

Возвращаемые значения

если log имеет значение false

  • x: приближенное решение.

если log имеет значение true

  • x: приближенное решение;

  • history: история сходимости.

Сведения о реализации

Реализация предварительно выделяет матрицу размером n путем перезапуска restart. Столбцы матрицы образуют ортонормальный базис для подпространства Крылова. Это позволяет выполнять операции BLAS2 при обновлении вектора решения . Матрица Хессенберга также выделяется предварительно.

По умолчанию для ортогонализации столбцов используется измененный метод Грама-Шмидта, поскольку численно он более устойчив, чем классический метод Грама-Шмидта. Однако измененный метод Грама-Шмидта по своей сути является последовательным, и если стабильность не вызывает опасений, можно использовать классический метод Грама-Шмидта, который реализуется с помощью операций BLAS2. В качестве компромисса можно использовать «критерий DGKS», который условно многократно применяет классический метод Грама-Шмидта для стабилизации и обычно в один-два раза медленнее классического метода Грама-Шмидта.

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

GMRES можно использовать как итератор. Это позволяет получить доступ к матрице Хессенберга и базисным векторам Крылова во время итераций.