WikiDer > Итеративное уточнение
Итеративное уточнение является итерационный метод предложенный Джеймсом Х. Уилкинсоном для повышения точности численных решений системы линейных уравнений.[1][2]
При решении линейной системы из-за совокупного накопления ошибки округления, вычисленное решение иногда может отклоняться от точного решения Начиная с итеративное уточнение вычисляет последовательность который сходится к когда выполняются определенные предположения.
Описание
За то митерация итеративного уточнения состоит из трех шагов:
(я)
Вычислить остаток
ошибка рм
(ii)
Решите систему для исправления,
cм, что устраняет остаточную ошибку
(iii)
Добавьте поправку, чтобы получить
исправленное следующее решение Иксм+1
Ключевым аргументом в пользу алгоритма уточнения является то, что хотя решение для cм на шаге (ii) действительно могут возникать ошибки, аналогичные ошибкам первого решения, , расчет невязки рм на шаге (i), для сравнения, численно почти точен: вы можете не очень хорошо знать правильный ответ, но вы довольно точно знаете, насколько далеко решение, которое у вас есть, до получения правильного результата (б). Если невязка в каком-то смысле мала, то поправка также должна быть небольшой и должна, по крайней мере, направлять текущую оценку ответа, Иксм, ближе к желаемому,
Итерации прекратятся сами по себе, когда остаточная рм равен нулю или достаточно близок к нулю, чтобы соответствующая поправка cм слишком мало, чтобы изменить решение Иксм кто его произвел; в качестве альтернативы алгоритм останавливается, когда рм слишком мала, чтобы убедить наблюдающего за прогрессом линейного алгебраиста в том, что стоит продолжить любые дальнейшие уточнения.
Анализ ошибок
Как показывает практика, итеративное уточнение для Гауссово исключение дает решение, верное с рабочей точностью, если удвоенная рабочая точность используется при вычислении р, например используя четырехъядерный или же двойной расширенный точность IEEE 754 плавающая точка, и если А не слишком плохо обусловлен (а итерация и скорость сходимости определяются числом обусловленности А).[3]
Более формально, если предположить, что каждый шаг (ii) может быть решен достаточно точно, то есть математически, для каждого м, у нас есть
куда ‖Fм‖∞ < 1, то относительная ошибка в м-я итерация итеративного уточнения удовлетворяет
куда
- ‖·‖∞ обозначает ∞-норма вектора,
- κ(А) это ∞-номер условия из А,
- п это порядок А,
- ε1 и ε2 находятся округление единиц из плавающая точка арифметические операции,
- σ, μ1 и μ2 константы, зависящие от А, ε1 и ε2
если А «не слишком плохо обусловлено», что в данном контексте означает
- 0 < σ κ(А) ε1 ≪ 1
и означает, что μ1 и μ2 имеют порядок единства.
Различие ε1 и ε2 предназначен для оценки смешанной точности рм где промежуточные результаты вычисляются с единичным округлением ε2 до того, как окончательный результат будет округлен (или усечен) с округлением единиц ε1. Предполагается, что все остальные вычисления выполняются с единичным округлением. ε1.
Рекомендации
- ^ Уилкинсон, Джеймс Х. (1963). Ошибки округления в алгебраических процессах. Энглвуд Клиффс, Нью-Джерси: Prentice Hall.
- ^ Молер, Клив Б. (апрель 1967 г.). «Итерационное уточнение с плавающей запятой». Журнал ACM. Нью-Йорк, штат Нью-Йорк: Ассоциация вычислительной техники. 14 (2): 316–321. Дои:10.1145/321386.321394.
- ^ Хайэм, Николас (2002). Точность и стабильность численных алгоритмов (2-е изд.). СИАМ. п. 232.
Этот Информатика статья - это заглушка. Вы можете помочь Википедии расширяя это. |