Se necesitan algunos datos sobre el método iterativo Newton-Schulz y su aplicación a matrices dispersas

Question

Estoy estudiando Newton-Schulz método iterativo para la obtención de la inversa aproximada , la cual está dada por

$V_{k+1}=V_{k}(2I-AV_{k})$,

en $I$ es la matriz identidad y converge, cuando los autovalores de a $AV_0$ son de menos de uno.

Quiero saber si el método de Newton funcionan bien para matrices dispersas? Además, si la de la matriz dispersa $A$, su inverso $V_k$ por el método de Newton conserva dispersión? Si no, ¿cuál podría ser el camino para que la inversa de la matriz $V_k$ conserva dispersión para las $A$? Cualquier referencia relacionada con esta discusión también será útil para mí.

Muchas gracias por su ayuda.

Answer 1

A veces ocurre que alguien re-inventa la rueda. Está en la página 1-3 de este documento:

• Multigrilla Cálculo

Lo escribió hace más de 10 años; no se puede juzgar tan bien ya que si el texto puede ser útil de alguna manera. Pero de todos modos, aquí es una suerte relevantes resumen de la primera parte del documento.

Newton-Raphson algoritmo

El de Newton-Raphson método es un algoritmo numérico para hallar ceros $p$ de un la función $f(x)$. La esencia del método es dibujar sucesivas de la tangente a las líneas y determinar donde estas líneas se cruzan el eje x (véase la figura siguiente): $$ y - f(p_n) = f'(p_n).(x - p_n) \quad \mbox{donde} \quad y = 0 \quad \mbox{y} \quad x = p_{n+1} \quad \Longrightarrow $$ $$ p_{n+1} = p_n - \frac{f(p_n)}{f'(p_n)} $$ Así, suponiendo que todo el proceso será convergente.
El método puede ser utilizado para la realización de una división sin realizar realmente un de la división. La ecuación que se va a buscar sus raíces, en este caso, está dada por: $$ \frac{1}{x} = a $$ Sustituto $f(x) = 1/x - a$ en el algoritmo anterior. Lo que resulta en: $$ p_{n+1} = p_n - \frac{1/p_n-a}{-1.1/p_n^2} = p_n - (- p_n + a.p_n^2) \quad \Longrightarrow \quad p_{n+1} = 2.p_n - un.p_n^2 $$ Es bien sabido que el método de Newton-Raphson método, si converge, entonces no así cuadráticamente, lo que significa que el inverso $1/a$ se puede encontrar con bastante rapidez. El algoritmo ha sido utilizado en los viejos tiempos, en los equipos que no tenía flotante punto de división de clases.

Así, empleando el método de Newton-Raphson algoritmo, el inverso de un número puede ser se encontró con cuadrática de la velocidad, realizando únicamente las adiciones y multiplicaciones. Armado con este conocimiento, vamos a hacer la transición de los números con las matrices. La determinación de la inversa de una matriz, lleno de muchos números, parece ser mucho más como un reto de todos modos.
Deje que el proceso iterativo para matrices se define por: $$ P_0 = I \quad \mbox{y} \quad P_{n+1} = 2.P_n - A. P_n.P_n $$ Aquí $I$ es la unidad de la matriz, $A$ es la matriz para ser invertida y $P_n$ las sucesivas iterands, que deben converger a la inversa de la matriz $A^{-1}$.
Teorema. $$ \mbox{Vamos a} \quad M = (I - A) \quad \mbox{o} \quad A = (I - M) \quad \mbox{a continuación:} \quad P_n = (I - M^{2^n}) . A^{-1} $$ Prueba por inducción: $$ \begin{array}{lll} P_0 &=& I = A . A^{-1} = (I - M) . A^{-1} \\ P_{n+1} &=& \left(I - M^{2^{n+1}} \right) . A^{-1} \\ &=& \left(I - M^{2^n.2} \right) . A^{-1} \\ &=& \left[I - (M^{2^n})^2 \right] . A^{-1} \\ &=& \left(I - M^{2^n} \right) . \left(I + M^{2^n} \right) . A^{-1} \\ &=& \mbox{because all matrices are mutually commutative:} \\ &=& \left(I - M^{2^n} \right) . A^{-1} . \left[ 2.I - A.\left( I - M^{2^n} \right).A^{-1} \right] \\ &=& P_n.(2.I - A.P_n) = 2.P_n - A.P_n.P_n \end{array} $$ Deje $m = 2^n$, entonces: $$ P_n = (I - M^m) . (I-M)^{-1} $$ Para los números, esta sería la suma de una serie Geométrica: $$ (I - M^m).(I - M)^{-1} = (I + M + M^2 + M^3 + M^4 + M^5 + M^6 + ... + M^{m-1}) $$ Para matrices, esta Serie Geométrica resulta ser equivalente a un proceso iterativo "incremental Jacobi" método de solución, como no va a ser más explicado aquí.
Pero también existe un producto de términos, llamado el de Euler de expansión (no recuerdo de donde el nombre proviene de; una referencia sería muy bienvenido): $$ (I - M^m).(I - M)^{-1} = \\ (I + M^{m/2}).(I - M^{m/2}).(I - M)^{-1} = \\ (I + M^{m/2}).(I + M^{m/4}).(I - M^{m/4}).(I - M)^{-1} = \\ (I + M^{m/2}).(I + M^{m/4}). \, ... \, (I+M^2).(I+M).(I-M).(I-M)^{-1} = \\ (I + M^{m/2}).(I + M^{m/4}). \, ... \, (I + M^8).(I + M^4).(I + M^2).(I + M) $$ Deje que el sistema de ecuaciones a resolver dado por $A.w = b$. Utilizando la anterior secuencias, podemos escribir: $$ P_n = (I - M^{2^n}) . A^{-1} \quad \Longrightarrow \quad A^{-1} b = (I - M^{2^n})^{-1} . P_n b $$ $$ = (I - M^{2^n})^{-1} . (I + M^{m/2}).(I + M^{m/4}). \, ... \, (I + M^8).(I + M^4).(I + M^2).(I + M) b $$ Otra manera de ver esto es la siguiente: $$ (I-M)^{-1} = (I-M)^{-1}.(I+M)^{-1}.(I+M) = (I-M^2)^{-1}.(I+M) = \\ (I-M^2)^{-1}.(I+M^2)^{-1}.(I+M^2).(I+M) = (I-M^4)^{-1}.(I+M^2).(I+M) $$ Con otras palabras: $$ w = (I-M)^{-1}.b = (I-M)^{-1}.(I+M)^{-1}.(I+M).b = (I-M^2)^{-1}.(I+M).b $$ Definir $b := (I + M).b$$M := M^2$. Luego, de nuevo: $$ w = (I-M)^{-1}.b = (I-M)^{-1}.(I+M)^{-1}.(I+M).b = (I-M^2)^{-1}.(I+M).b $$ Y este proceso se puede repetir hasta que encontremos una manera de determinar $(I-M)^{-1}$, preferiblemente sin continuar las iteraciones ad infinitum.

La actualización. Muy en general, la inversa de una matriz dispersa es que no se dispersa en todas. Y esto, por supuesto, será se refleja en la iterands de la Newton-Schulz método para la obtención de un aproximado inversa. El común remedio es simplemente para no calcular la inversa de una gran matriz dispersa y use, por ejemplo,
Descomposición LU lugar.
Pero, como se ha argumentado en la citada referencia, el método de Newton-Schulz método puede ser considerado como un Ansatz para Multigrilla métodos. Y que es muy diferente de la historia, de no ser elaborados aquí.