Итеративное уточнение - Iterative refinement

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

При решении линейной системы ${displaystyle, mathrm {A}, mathbf {x} = mathbf {b} ,,}$ из-за совокупного накопления ошибки округления, вычисленное решение ${Displaystyle {шляпа {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} ,,}$ когда выполняются определенные предположения.

Описание

За ${displaystyle m = 1,2,3, ... ,,}$ то митерация итеративного уточнения состоит из трех шагов:

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

Ключевым аргументом в пользу алгоритма уточнения является то, что хотя решение для c_м на шаге (ii) действительно могут возникать ошибки, аналогичные ошибкам первого решения, ${Displaystyle {шляпа {mathbf {x}}}}$, расчет невязки р_м на шаге (i), для сравнения, численно почти точен: вы можете не очень хорошо знать правильный ответ, но вы довольно точно знаете, насколько далеко решение, которое у вас есть, до получения правильного результата (б). Если невязка в каком-то смысле мала, то поправка также должна быть небольшой и должна, по крайней мере, направлять текущую оценку ответа, Икс_м, ближе к желаемому, ${displaystyle mathbf {x} _ {star} ,.}$

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

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

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

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

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

куда ‖F_м‖_∞ < 1, то относительная ошибка в м-я итерация итеративного уточнения удовлетворяет

${displaystyle {frac {lVert mathbf {x} _ {m} -mathbf {x} _ {star} Vert _ {infty}} {lVert mathbf {x} _ {star} Vert _ {infty}}} leq {igl ( } сигма, каппа (mathrm {A}), varepsilon _ {1} {igr)} ^ {m} + mu _ {1}, varepsilon _ {1} + n, kappa (mathrm {A}), mu _ { 2}, варепсилон _ {2}}$

куда

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

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

0 < σ κ(А) ε₁ ≪ 1

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

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

Рекомендации

Этот Информатика статья - это заглушка. Вы можете помочь Википедии расширяя это.