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

Iterative refinement

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

При решении линейной системы из-за совокупного накопления ошибки округления, вычисленное решение иногда может отклоняться от точного решения Начиная с итеративное уточнение вычисляет последовательность который сходится к когда выполняются определенные предположения.

Описание

За то митерация итеративного уточнения состоит из трех шагов:

(я)
 
Вычислить остаток
ошибка рм
   
 
(ii)
 
Решите систему для исправления,
cм, что устраняет остаточную ошибку
   
 
(iii)
 
Добавьте поправку, чтобы получить
исправленное следующее решение Иксм+1  
   
 

Ключевым аргументом в пользу алгоритма уточнения является то, что хотя решение для cм на шаге (ii) действительно могут возникать ошибки, аналогичные ошибкам первого решения, , расчет невязки рм на шаге (i), для сравнения, численно почти точен: вы можете не очень хорошо знать правильный ответ, но вы довольно точно знаете, насколько далеко решение, которое у вас есть, до получения правильного результата (б). Если невязка в каком-то смысле мала, то поправка также должна быть небольшой и должна, по крайней мере, направлять текущую оценку ответа, Иксм, ближе к желаемому,

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

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

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

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

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

куда

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

0 < σ κ(А) ε1 ≪ 1

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

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

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

  1. ^ Уилкинсон, Джеймс Х. (1963). Ошибки округления в алгебраических процессах. Энглвуд Клиффс, Нью-Джерси: Prentice Hall.
  2. ^ Молер, Клив Б. (апрель 1967 г.). «Итерационное уточнение с плавающей запятой». Журнал ACM. Нью-Йорк, штат Нью-Йорк: Ассоциация вычислительной техники. 14 (2): 316–321. Дои:10.1145/321386.321394.
  3. ^ Хайэм, Николас (2002). Точность и стабильность численных алгоритмов (2-е изд.). СИАМ. п. 232.