Refinamiento iterativo

Método para mejorar la precisión de las soluciones numéricas de sistemas de ecuaciones lineales

El refinamiento iterativo es un método iterativo propuesto por James H. Wilkinson para mejorar la precisión de las soluciones numéricas de sistemas de ecuaciones lineales . ^{[1] [2]}

Al resolver un sistema lineal debido a la acumulación compuesta de errores de redondeo , la solución calculada a veces puede desviarse de la solución exacta. Comenzando con el refinamiento iterativo se calcula una secuencia que converge cuando se cumplen ciertos supuestos. ${\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},\dots \}}$ ${\displaystyle \mathbf {x} _{\star }\,,}$

Descripción

Para la iteración m , el refinamiento iterativo consta de tres pasos: ${\displaystyle m=1,2,3,\dots \,,}$

1. Calcular el error residual r _m $${\displaystyle \mathbf {r} _{m}=\mathbf {b} -A\mathbf {x} _{m}\,.}$$
2. Resuelva el sistema para la corrección, c _m , que elimina el error residual $${\displaystyle A\mathbf {c} _{m}=\mathbf {r} _{m}\,.}$$
3. Agregue la corrección para obtener la siguiente solución revisada x _{m +1} $${\displaystyle \mathbf {x} _{m+1}=\mathbf {x} _{m}+\mathbf {c} _{m}\,.}$$

El razonamiento crucial para el algoritmo de refinamiento es que, aunque la solución para c _m en el paso (ii) puede de hecho estar plagada de errores similares a los de la primera solución, , el cálculo del residuo r _m en el paso (i), en comparación, es numéricamente casi exacto: Puede que no conozca muy bien la respuesta correcta, pero sabe con bastante exactitud qué tan lejos está la solución que tiene en la mano de producir el resultado correcto ( b ). Si el residuo es pequeño en algún sentido, entonces la corrección también debe ser pequeña, y debería, como mínimo, acercar la estimación actual de la respuesta, x _m , a la deseada. ${\displaystyle {\hat {\mathbf {x} }}}$ ${\displaystyle \mathbf {x} _{\star }\,.}$

Las iteraciones se detendrán por sí solas cuando el residuo r _m sea cero, o lo suficientemente cercano a cero como para que la corrección correspondiente c _m sea demasiado pequeña para cambiar la solución x _m que lo produjo; alternativamente, el algoritmo se detiene cuando r _m sea demasiado pequeño para convencer al algebrista lineal que monitorea el progreso de que vale la pena continuar con más refinamientos.

Obsérvese que la ecuación matricial resuelta en el paso (ii) utiliza la misma matriz para cada iteración. Si la ecuación matricial se resuelve utilizando un método directo, como la descomposición de Cholesky o LU , la factorización numéricamente costosa de se realiza una vez y se reutiliza para la sustitución hacia adelante y hacia atrás relativamente económica para resolver c _m en cada iteración. ^[2] ${\displaystyle A}$ ${\displaystyle A}$

Análisis de errores

Como regla general, el refinamiento iterativo para la eliminación gaussiana produce una solución correcta para la precisión de trabajo si se utiliza el doble de la precisión de trabajo en el cálculo de r , por ejemplo, utilizando precisión extendida cuádruple o doble IEEE 754 de punto flotante , y si A no está demasiado mal condicionado (y la iteración y la tasa de convergencia están determinadas por el número de condición de A ). ^[3]

De manera más formal, suponiendo que cada paso (ii) se puede resolver con razonable precisión, es decir, en términos matemáticos, para cada m , tenemos $${\displaystyle A\left(I+F_{m}\right)\mathbf {c} _{m}=\mathbf {r} _{m}}$$

donde ‖F _m ‖ _∞ < 1 , el error relativo en la iteración m -ésima del refinamiento iterativo satisface $${\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}\,\varepsilon _{2}}$$

dónde

• ‖·‖ _∞ denota la ∞ -norma de un vector,
• κ (A) es el número de condición ∞ de A ,
• n es el orden de A ,
• ε ₁ y ε ₂ son redondeos unitarios de operaciones aritméticas de punto flotante ,
• σ , μ ₁ y μ ₂ son constantes que dependen de A , ε ₁ y ε ₂

si A "no está muy mal condicionado", lo que en este contexto significa

0 < σκ (A) ε ₁ ≪ 1

e implica que μ ₁ y μ ₂ son de orden unidad.

La distinción entre ε ₁ y ε ₂ tiene como finalidad permitir la evaluación de precisión mixta de r _m donde los resultados intermedios se calculan con redondeo unitario ε ₂ antes de que el resultado final se redondee (o trunque) con redondeo unitario ε ₁ . Se supone que todos los demás cálculos se llevan a cabo con redondeo unitario ε ₁ .

Referencias

1. Wilkinson, James H. (1963). Errores de redondeo en procesos algebraicos . Englewood Cliffs, Nueva Jersey: Prentice Hall .
2. Moler, Cleve B. (abril de 1967). "Refinamiento iterativo en coma flotante". Revista de la ACM . 14 (2). Nueva York, NY: Association for Computing Machinery : 316–321. doi : 10.1145/321386.321394 .
3. Higham, Nicholas (2002). Precisión y estabilidad de algoritmos numéricos (2.ª ed.). SIAM. pág. 232.