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

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

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

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

Описание

Для в м - й итерации итерационного уточнения состоит из трех этапов: ${\ Displaystyle м = 1,2,3,... \,,}$

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

Ключевым аргументом в пользу алгоритма уточнения является то, что, хотя решение для 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 слишком мало, чтобы убедить линейного алгебраиста, наблюдающего за прогрессом, в том, что стоит продолжить любые дальнейшие уточнения.

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

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

Более формально, предполагая, что каждый шаг (ii) может быть решен достаточно точно, то есть математически, для каждого m, мы имеем

${\ displaystyle \ mathrm {A} \, \ left (\ mathrm {I + F} _ {m} \ right) \ mathbf {c} _ {m} = \ mathbf {r} _ {m}}$

где ‖F m ‖ ∞ lt;1, относительная ошибка в m- й итерации итерационного уточнения удовлетворяет условию

${\ displaystyle {\ frac {\ lVert \ mathbf {x} _ {m} - \ mathbf {x} _ {\ star} \ rVert _ {\ infty}} {\ lVert \ mathbf {x} _ {\ star} \ rVert _ {\ infty}}} \ leq {\ bigl (} \ sigma \, \ kappa (\ mathrm {A}) \, \ varepsilon _ {1} {\ bigr)} ^ {m} + \ mu _ {1} \, \ varepsilon _ {1} + n \, \ kappa (\ mathrm {A}) \, \ mu _ {2} \, \ varepsilon _ {2}}$

куда

• ‖ ‖ ∞ обозначает ∞ -норму вектора,
• κ (А) является ∞ - условие число из A,
• n - порядок A,
• ε 1 и ε 2 являются единичным круглым-офф из плавающей запятой арифметических операций,
• σ, μ 1 и μ 2 - константы, зависящие от A, ε 1 и ε 2

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

0 lt; σ κ (A) ε 1 ≪ 1

и означает, что μ 1 и μ 2 имеют порядок единицы.

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

использованная литература