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

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

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

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

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

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

Обратите внимание, что матричное уравнение, решенное на шаге (ii), использует одну и ту же матрицу для каждой итерации. Если матричное уравнение решается с использованием прямого метода, такого как разложение Холецкого или LU , численная затратная факторизация выполняется один раз и повторно используется для относительно недорогой прямой и обратной подстановки для решения для c _m на каждой итерации. ^[2]${\displaystyle А}$ ${\displaystyle А}$

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

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

где ‖F _m ‖ _∞ < 1 , относительная ошибка в m -й итерации итеративного уточнения удовлетворяет условию$${\displaystyle {\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}\,\варепсилон _{2}}$$

где

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

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

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

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