Итеративное уточнение

Для более широкого освещения этой темы см. Итерационный метод .

Эта статья об итеративном уточнении в математике. Информацию об итеративном усовершенствовании разработки программного обеспечения см. в разделе Итеративная и инкрементальная разработка .

Итеративное уточнение — итерационный метод, предложенный Джеймсом Х. Уилкинсоном для повышения точности численных решений систем линейных уравнений .

При решении линейной системы $A\mathbf {x} =\mathbf {b} \,,$ из-за совокупного накопления ошибок округления вычисленное решение ${\hat {\mathbf {x} }}$ иногда может отклоняться от точного решения $\mathbf {x} _{\star }\,.$ Начиная с $\mathbf {x} _{1}={\hat {\mathbf {x} }}\,,$ итеративное уточнение вычисляет последовательность $\{\mathbf {x} _{1},\,\mathbf {x} _{2},\,\mathbf {x} _{3},\dots \}$ который сходится к $\mathbf {x} _{\star }\,,$ когда выполняются определенные предположения.

Описание

Для $m=1,2,3,\dots \,,$ -я итерация m итеративного уточнения состоит из трех шагов:

1. Вычислить остаточную ошибку r _m $$\mathbf {r} _{m}=\mathbf {b} -A\mathbf {x} _{m}\,.$$
2. Решите систему коррекции c _m , которая удаляет остаточную ошибку. $$A\mathbf {c} _{m}=\mathbf {r} _{m}\,.$$
3. Добавьте исправление, чтобы получить исправленное следующее решение x _{m +1.} $$\mathbf {x} _{m+1}=\mathbf {x} _{m}+\mathbf {c} _{m}\,.$$

хотя решение для cm _{Важнейшим аргументом в пользу алгоритма уточнения является то, что ,} на этапе (ii) действительно может содержать те же ошибки, что и первое решение, ${\hat {\mathbf {x} }}$, расчет остатка r _m на этапе (i) для сравнения численно почти точен: вы можете не очень хорошо знать правильный ответ, но вы достаточно точно знаете, насколько далеко имеющееся у вас решение находится от получения правильный результат ( б ). Если невязка в каком-то смысле мала, то поправка также должна быть небольшой и должна, по крайней мере, приближать текущую оценку ответа x _m к желаемой, $\mathbf {x} _{\star }\,.$

Итерации остановятся сами по себе, когда невязка r _m равна нулю или достаточно близка к нулю, чтобы соответствующая поправка c _m была слишком мала, чтобы изменить решение x _m , которое ее создало; в качестве альтернативы алгоритм останавливается, когда r _m становится слишком мал, чтобы убедить линейного алгебраиста, наблюдающего за ходом работы, что стоит продолжать дальнейшие уточнения.

Обратите внимание, что матричное уравнение, решенное на этапе (ii), использует ту же матрицу $A$ для каждой итерации. Если матричное уравнение решено прямым методом, например Холецкого или LU Разложение , численная дорогостоящая факторизация $A$ выполняется один раз и повторно используется для относительно недорогой прямой и обратной замены для вычисления на _cm каждой итерации.

Анализ ошибок

Как правило, итеративное уточнение для исключения Гаусса дает решение, правильное к рабочей точности, если при вычислении r используется удвоенная рабочая точность , например, с использованием учетверенной или двойной расширенной точности IEEE 754 с плавающей запятой , и если A не слишком плохо обусловлен (а итерация и скорость сходимости определяются числом обусловленности A ).

Более формально, предполагая, что каждый шаг (ii) может быть решен достаточно точно, т. е. в математических терминах, для каждого m мы имеем $$A\left(I+F_{m}\right)\mathbf {c} _{m}=\mathbf {r} _{m}$$

где ‖F _m ‖ _∞ < 1 , относительная ошибка на m -й итерации итеративного уточнения удовлетворяет условию $${\frac {\lVert \mathbf {x} _{m}-\mathbf {x} _{\star }\rVert _{\infty }}{\lVert \mathbf {x} _{\star }\rVert _{\infty }}}\leq {\bigl (}\sigma \,\kappa (A)\,\varepsilon _{1}{\bigr )}^{m}+\mu _{1}\,\varepsilon _{1}+n\,\kappa (A)\,\mu _{2}\,\varepsilon _{2}$$

где

• ‖·‖ _∞ обозначает ∞ -норму вектора,
• κ (A) ∞ - число обусловленности A — ,
• n — порядок A ,
• ε ₁ и ε ₂ — единичные округления арифметических операций с плавающей запятой ,
• σ , µ ₁ и µ ₂ — константы, зависящие от A , ε ₁ и ε _2.

если A «не слишком плохо обусловлено», что в данном контексте означает

0 < σ κ (A) ε ₁ ≪ 1

и означает, что µ ₁ и µ ₂ имеют порядок единицы.

Различие ε ₁ и ε ₂ предназначено для обеспечения оценки r _m со смешанной точностью , когда промежуточные результаты вычисляются с единичным округлением ε ₂ перед тем, как конечный результат округляется (или усекается) с единичным округлением ε ₁ . Предполагается, что все остальные вычисления выполняются с единичным округлением ε ₁ .