Preacondicionador

En lugar de resolver el sistema lineal original${\displaystyle Ax=b}$para${\displaystyle x}$, uno puede considerar el sistema preacondicionado adecuado$${\displaystyle AP^{-1}(Px)=b}$$ y resolver $${\displaystyle AP^{-1}y=b}$$ para${\displaystyle y}$y $${\displaystyle Px=y}$$ para${\displaystyle x}$.

Alternativamente, se puede resolver el sistema precondicionado de la izquierda.$${\displaystyle P^{-1}(Ax-b)=0.}$$

Ambos sistemas dan la misma solución que el sistema original siempre que la matriz de preacondicionamiento sea${\displaystyle P}$es no singular . El preacondicionamiento izquierdo es más tradicional.

El sistema preacondicionado de doble cara$${\displaystyle QAP^{-1}(Px)=Qb}$$ puede ser beneficioso, por ejemplo, para preservar la simetría de la matriz: si la matriz original${\displaystyle A}$es real simétrico y precondicionadores reales${\displaystyle Q}$y${\displaystyle P}$satisfacer ${\displaystyle Q^{T}=P^{-1}}$luego la matriz precondicionada${\displaystyle QAP^{-1}}$También es simétrico. El preacondicionamiento bilateral es común para el escalado diagonal donde los preacondicionadores${\displaystyle Q}$y${\displaystyle P}$son diagonales y el escalado se aplica tanto a las columnas como a las filas de la matriz original.${\displaystyle A}$, por ejemplo, para disminuir el rango dinámico de las entradas de la matriz.

El objetivo del preacondicionamiento es reducir el número de condición , por ejemplo, de la matriz del sistema preacondicionado izquierdo o derecho.${\displaystyle P^{-1}A}$o${\displaystyle AP^{-1}}$Los números de condición pequeños favorecen la convergencia rápida de los solucionadores iterativos y mejoran la estabilidad de la solución con respecto a las perturbaciones en la matriz del sistema y el lado derecho, por ejemplo, permitiendo una cuantización más agresiva de las entradas de la matriz utilizando una precisión de computadora menor .

La matriz preacondicionada${\displaystyle P^{-1}A}$o${\displaystyle AP^{-1}}$Rara vez se forma explícitamente. Solo la acción de aplicar el precondicionador resuelve la operación. ${\displaystyle P^{-1}}$Puede que sea necesario calcularlo para un vector dado.

Por lo general, existe una compensación en la elección de${\displaystyle P}$Dado que el operador${\displaystyle P^{-1}}$debe aplicarse en cada paso del solucionador lineal iterativo, debe tener un pequeño costo (tiempo de cálculo) de aplicación. ${\displaystyle P^{-1}}$operación. Por lo tanto, el preacondicionador más barato sería${\displaystyle P=I}$Desde entonces${\displaystyle P^{-1}=I.}$Claramente, esto da como resultado el sistema lineal original y el precondicionador no hace nada. En el otro extremo, la elección ${\displaystyle P=A}$da${\displaystyle P^{-1}A=AP^{-1}=I,}$que tiene un número de condición óptimo de 1, que requiere una sola iteración para la convergencia; sin embargo, en este caso${\displaystyle P^{-1}=A^{-1},}$y aplicar el preacondicionador es tan difícil como resolver el sistema original. Por lo tanto, se elige ${\displaystyle P}$ como en algún punto intermedio entre estos dos extremos, en un intento de lograr un número mínimo de iteraciones lineales manteniendo el operador ${\displaystyle P^{-1}}$ lo más sencillo posible. A continuación se detallan algunos ejemplos de enfoques típicos de preacondicionamiento.

Métodos iterativos precondicionados para${\displaystyle Ax-b=0}$son, en la mayoría de los casos, matemáticamente equivalentes a los métodos iterativos estándar aplicados al sistema precondicionado.${\displaystyle P^{-1}(Ax-b)=0.}$Por ejemplo, la iteración estándar de Richardson para resolver${\displaystyle Ax-b=0}$es $${\displaystyle \mathbf {x} _ {n+1}=\mathbf {x} _ {n}-\gamma _ {n}(A\mathbf {x} _ {n}-\mathbf {b} ),\ n\geq 0.}$$

Aplicado al sistema preacondicionado${\displaystyle P^{-1}(Ax-b)=0,}$se convierte en un método precondicionado $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

Ejemplos de métodos iterativos precondicionados populares para sistemas lineales incluyen el método del gradiente conjugado precondicionado , el método del gradiente biconjugado y el método generalizado de residuos mínimos . Los métodos iterativos, que utilizan productos escalares para calcular los parámetros iterativos, requieren cambios correspondientes en el producto escalar junto con la sustitución.${\displaystyle P^{-1}(Ax-b)=0}$para${\displaystyle Ax-b=0.}$

Para una matriz simétrica definida positiva${\displaystyle A}$el preacondicionador${\displaystyle P}$También se suele elegir que sea simétrica definida positiva. El operador precondicionado${\displaystyle P^{-1}A}$es entonces también simétrica definida positiva, pero con respecto a la${\displaystyle P}$producto escalar basado en . En este caso, el efecto deseado al aplicar un precondicionador es hacer que la forma cuadrática del operador precondicionado sea${\displaystyle P^{-1}A}$con respecto a la${\displaystyle P}$Producto escalar basado en para ser casi esférico. ^{[ 1 ]}

Denotando${\displaystyle T=P^{-1}}$, destacamos que el preacondicionamiento se implementa prácticamente como multiplicar algún vector${\displaystyle r}$por${\displaystyle T}$, es decir, calcular el producto${\displaystyle Tr.}$En muchas aplicaciones,${\displaystyle T}$no se da como una matriz, sino como un operador${\displaystyle T(r)}$actuando sobre el vector${\displaystyle r}$Sin embargo, algunos preacondicionadores populares cambian con${\displaystyle r}$y la dependencia de${\displaystyle r}$Puede que no sea lineal. Ejemplos típicos implican el uso de métodos iterativos no lineales , como el método del gradiente conjugado , como parte de la construcción del precondicionador. Dichos precondicionadores pueden ser muy eficientes en la práctica; sin embargo, su comportamiento es difícil de predecir teóricamente.

Un caso particular interesante de precondicionamiento variable es el precondicionamiento aleatorio, por ejemplo, el precondicionamiento multigrid en cuadrículas gruesas aleatorias. ^{[ 2 ]} Si se utiliza en métodos de descenso de gradiente , el precondicionamiento aleatorio puede verse como una implementación del descenso de gradiente estocástico y puede conducir a una convergencia más rápida, en comparación con el precondicionamiento fijo, ya que rompe el patrón asintótico de "zig-zag" del descenso de gradiente .

El uso más común del precondicionamiento es para la solución iterativa de sistemas lineales resultantes de aproximaciones de ecuaciones diferenciales parciales . Cuanto mejor sea la calidad de la aproximación, mayor será el tamaño de la matriz. En tal caso, el objetivo del precondicionamiento óptimo es, por un lado, hacer que el número de condición espectral de${\displaystyle P^{-1}A}$estar acotado superiormente por una constante independiente del tamaño de la matriz, lo que D'yakonov denomina precondicionamiento espectralmente equivalente . Por otro lado, el coste de aplicación del ${\displaystyle P^{-1}}$Idealmente debería ser proporcional (también independiente del tamaño de la matriz) al costo de multiplicación de${\displaystyle A}$mediante un vector.

• Gradiente conjugado precondicionado – math-linux.com
• Plantillas para la solución de sistemas lineales: bloques de construcción para métodos iterativos

Por analogía con los sistemas lineales, para un problema de valores propios${\displaystyle Ax=\lambda x}$uno puede verse tentado a reemplazar la matriz${\displaystyle A}$con la matriz${\displaystyle P^{-1}A}$utilizando un preacondicionador${\displaystyle P}$Sin embargo, esto solo tiene sentido si los autovectores de búsqueda de ${\displaystyle A}$y${\displaystyle P^{-1}A}$son lo mismo. Este es el caso de las transformaciones espectrales.

La transformación espectral más popular es la llamada transformación de desplazamiento e inversión , donde para un escalar dado${\displaystyle \alpha }$, llamado el desplazamiento , el problema de valores propios original${\displaystyle Ax=\lambda x}$se reemplaza con el problema de desplazamiento e inversión${\displaystyle (A-\alpha I)^{-1}x=\mu x}$Los autovectores se conservan y se puede resolver el problema de desplazamiento e inversión mediante un solucionador iterativo, por ejemplo, la iteración de potencia . Esto da como resultado la iteración inversa , que normalmente converge al autovector correspondiente al autovalor más cercano al desplazamiento.${\displaystyle \alpha }$La iteración del cociente de Rayleigh es un método de desplazamiento e inversión con un desplazamiento variable.

Las transformaciones espectrales son específicas para problemas de valores propios y no tienen análogos para sistemas lineales. Requieren un cálculo numérico preciso de la transformación involucrada, lo que se convierte en el principal obstáculo para problemas de gran tamaño.

Para establecer una conexión estrecha con los sistemas lineales, supongamos que el valor propio objetivo es${\displaystyle \lambda _ {\star }}$se conoce (aproximadamente). Entonces se puede calcular el vector propio correspondiente a partir del sistema lineal homogéneo.${\displaystyle (A-\lambda _{\star }I)x=0}$. Utilizando el concepto de precondicionamiento izquierdo para sistemas lineales, obtenemos${\displaystyle T(A-\lambda _{\star }I)x=0}$, dónde ${\displaystyle T}$es el precondicionador, que podemos intentar resolver utilizando la iteración de Richardson.

$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}T(A-\lambda _{\star }I)\mathbf {x} _{n},\ n\geq 0.}$$

• Plantillas para la solución de problemas algebraicos de valores propios: una guía práctica

Por ejemplo, para encontrar un mínimo local de una función de valor real.${\displaystyle F(\mathbf {x} )}$Utilizando el descenso de gradiente , se dan pasos proporcionales al negativo del gradiente.${\displaystyle -\nabla F(\mathbf {a} )}$ (o del gradiente aproximado) de la función en el punto actual: $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

El preacondicionador se aplica al gradiente: $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

El preacondicionamiento aquí puede verse como un cambio en la geometría del espacio vectorial con el objetivo de que los conjuntos de nivel se asemejen a círculos. ^{[ 5 ]} En este caso, el gradiente preacondicionado apunta más cerca del punto de los extremos, como se muestra en la figura, lo que acelera la convergencia.

El mínimo de una función cuadrática $${\displaystyle F(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{T}A\mathbf {x} -\mathbf {x} ^{T}\mathbf {b} ,}$$ dónde${\displaystyle \mathbf {x} }$y${\displaystyle \mathbf {b} }$son vectores columna reales y${\displaystyle A}$es una matriz real simétrica definida positiva , es exactamente la solución de la ecuación lineal${\displaystyle A\mathbf {x} =\mathbf {b} }$. Desde${\displaystyle \nabla F(\mathbf {x} )=A\mathbf {x} -\mathbf {b} }$, el método de descenso de gradiente precondicionado de minimización ${\displaystyle F(\mathbf {x} )}$es $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

Esta es la iteración de Richardson precondicionada para resolver un sistema de ecuaciones lineales .

El mínimo del cociente de Rayleigh$${\displaystyle \rho (\mathbf {x} )={\frac {\mathbf {x} ^{T}A\mathbf {x} }{\mathbf {x} ^{T}\mathbf {x} }},}$$ dónde${\displaystyle \mathbf {x} }$es un vector columna real distinto de cero y${\displaystyle A}$es una matriz real simétrica definida positiva , es el valor propio más pequeño de${\displaystyle A}$, mientras que el minimizador es el vector propio correspondiente . Dado que${\displaystyle \nabla \rho (\mathbf {x} )}$es proporcional a${\displaystyle A\mathbf {x} -\rho (\mathbf {x} )\mathbf {x} }$, el método de descenso de gradiente precondicionado de minimización ${\displaystyle \rho (\mathbf {x} )}$es $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\rho (\mathbf {x_{n}} )\mathbf {x_{n}} ),\ n\geq 0.}$$

Este método es análogo a la iteración de Richardson precondicionada para resolver problemas de valores propios.

En muchos casos, puede ser beneficioso cambiar el precondicionador en algún paso o incluso en cada paso de un algoritmo iterativo para adaptarse a una forma cambiante de los conjuntos de nivel, como en $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P_{n}^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

Sin embargo, hay que tener en cuenta que construir un precondicionador eficiente suele ser computacionalmente costoso. El mayor coste de actualizar el precondicionador puede fácilmente anular el efecto positivo de una convergencia más rápida. Si${\displaystyle P_{n}^{-1}=H_{n}}$, una aproximación BFGS de la matriz hessiana inversa, este método se conoce como método cuasi-Newton .