Preacondicionador

Transforms equations for numerical solution

En matemáticas , el precondicionamiento es la aplicación de una transformación, llamada precondicionador , que condiciona un problema dado a una forma que sea más adecuada para métodos de resolución numérica . El preacondicionamiento suele estar relacionado con la reducción de un número de condición del problema. El problema precondicionado generalmente se resuelve mediante un método iterativo .

Preacondicionamiento para sistemas lineales

En álgebra lineal y análisis numérico , un precondicionador de una matriz es una matriz que tiene un número de condición menor que . También es común llamar al precondicionador, en lugar de a , ya que él mismo rara vez está disponible explícitamente. En el precondicionamiento moderno, la aplicación de , es decir, la multiplicación de un vector columna, o un bloque de vectores columna, por , se realiza comúnmente sin matrices , es decir, donde ni , ni (y a menudo ni siquiera ) están disponibles explícitamente. en forma matricial. ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle P^{-1}A}$ ${\displaystyle A}$ ${\displaystyle T=P^{-1}}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle T=P^{-1}}$ ${\displaystyle T=P^{-1}}$ ${\displaystyle P}$ ${\displaystyle T=P^{-1}}$ ${\displaystyle A}$

Los precondicionadores son útiles en métodos iterativos para resolver un sistema lineal , ya que la tasa de convergencia para la mayoría de los solucionadores lineales iterativos aumenta porque el número de condición de una matriz disminuye como resultado del precondicionamiento. Los solucionadores iterativos precondicionados suelen superar a los solucionadores directos, por ejemplo, la eliminación gaussiana , para matrices grandes, especialmente para matrices dispersas . Los solucionadores iterativos se pueden utilizar como métodos sin matrices , es decir, convertirse en la única opción si la matriz de coeficientes no se almacena explícitamente, sino que se accede a ella evaluando productos matriz-vector. ${\displaystyle Ax=b}$ ${\displaystyle x}$ ${\displaystyle A}$

Descripción

En lugar de resolver el sistema lineal original para , se puede considerar el sistema precondicionado correcto ${\displaystyle Ax=b}$ ${\displaystyle x}$

$${\displaystyle AP^{-1}(Px)=b}$$

$${\displaystyle AP^{-1}y=b}$$

${\displaystyle y}$

$${\displaystyle Px=y}$$

${\displaystyle x}$

Alternativamente, se puede resolver el sistema precondicionado izquierdo

$${\displaystyle P^{-1}(Ax-b)=0.}$$

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

El sistema preacondicionado de dos caras.

$${\displaystyle QAP^{-1}(Px)=Qb}$$

el escalado diagonal ${\displaystyle A}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle Q^{T}=P^{-1}}$ ${\displaystyle QAP^{-1}}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle A}$

El objetivo del preacondicionamiento es reducir el número de condición , por ejemplo, de la matriz del sistema preacondicionado izquierdo o derecho o . Los números de condición pequeños benefician la rápida convergencia 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 cuantificación más agresiva de las entradas de la matriz utilizando una menor precisión informática . ${\displaystyle P^{-1}A}$ ${\displaystyle AP^{-1}}$

La matriz precondicionada o rara vez se forma explícitamente. Es posible que sólo sea necesario calcular la acción de aplicar la operación de resolución del precondicionador a un vector dado. ${\displaystyle P^{-1}A}$ ${\displaystyle AP^{-1}}$ ${\displaystyle P^{-1}}$

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

Métodos iterativos precondicionados.

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

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

Aplicado al sistema preacondicionado se convierte en un método preacondicionado. ${\displaystyle P^{-1}(Ax-b)=0,}$

$${\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 residual mínimo generalizado . 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 de ${\displaystyle P^{-1}(Ax-b)=0}$ ${\displaystyle Ax-b=0.}$

División de matrices

Un método iterativo estacionario está determinado por la división de la matriz y la matriz de iteración . Asumiendo que ${\displaystyle A=M-N}$ ${\displaystyle C=I-M^{-1}A}$

• la matriz del sistema es simétrica positiva-definida , ${\displaystyle A}$
• la matriz de división es simétrica positiva-definida , ${\displaystyle M}$
• el método iterativo estacionario es convergente, según lo determinado por , ${\displaystyle \rho (C)<1}$

el número de condición está limitado arriba por ${\displaystyle \kappa (M^{-1}A)}$

$${\displaystyle \kappa (M^{-1}A)\leq {\frac {1+\rho (C)}{1-\rho (C)}}\,.}$$

Interpretación geométrica

Para una matriz definida positiva simétrica, el precondicionador normalmente se elige para que también sea definido positivo simétrico. El operador precondicionado también es definido positivo simétrico, pero con respecto al producto escalar basado en . En este caso, el efecto deseado al aplicar un precondicionador es hacer que la forma cuadrática del operador precondicionado con respecto al producto escalar basado en - sea casi esférica. ^[1] ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle P^{-1}A}$ ${\displaystyle P}$ ${\displaystyle P^{-1}A}$ ${\displaystyle P}$

Preacondicionamiento variable y no lineal

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

Precondicionamiento aleatorio

Un caso particular interesante de preacondicionamiento variable es el preacondicionamiento aleatorio, por ejemplo, preacondicionamiento de múltiples redes en redes aleatorias gruesas. ^[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 .

Precondicionamiento espectralmente equivalente

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 esté limitado desde arriba por una constante independiente del tamaño de la matriz, lo que D'yakonov llama precondicionamiento espectralmente equivalente . Por otro lado, el coste de aplicación de debería idealmente ser proporcional (también independiente del tamaño de la matriz) al coste de multiplicación de por un vector. ${\displaystyle P^{-1}A}$ ${\displaystyle P^{-1}}$ ${\displaystyle A}$

Ejemplos

Precondicionador Jacobi (o diagonal)

El precondicionador de Jacobi es una de las formas más simples de precondicionamiento, en la que el precondicionador se elige para que sea la diagonal de la matriz. Suponiendo que obtenemos que es eficiente para matrices diagonalmente dominantes . Se utiliza en softwares de análisis para problemas de vigas o problemas 1-D (EX: -STAAD.Pro ) ${\displaystyle P=\mathrm {diag} (A).}$ ${\displaystyle A_{ii}\neq 0,\forall i}$ ${\displaystyle P_{ij}^{-1}={\frac {\delta _{ij}}{A_{ij}}}.}$ ${\displaystyle A}$

ESPAÑA

El precondicionador inverso aproximado disperso minimiza dónde está la norma de Frobenius y proviene de algún conjunto adecuadamente restringido de matrices dispersas . Según la norma de Frobenius, esto se reduce a resolver numerosos problemas de mínimos cuadrados independientes (uno para cada columna). Las entradas en deben restringirse a algún patrón de escasez o el problema sigue siendo tan difícil y requiere tanto tiempo como encontrar el inverso exacto de . El método fue introducido por MJ Grote y T. Huckle junto con un enfoque para seleccionar patrones de escasez. ^[3] ${\displaystyle \|AT-I\|_{F},}$ ${\displaystyle \|\cdot \|_{F}}$ ${\displaystyle T=P^{-1}}$ ${\displaystyle T}$ ${\displaystyle A}$

Otros precondicionadores

• Factorización de Cholesky incompleta
• Factorización LU incompleta
• Sobrerelajación sucesiva
  • Sobrerelajación sucesiva simétrica
• Preacondicionamiento multired

enlaces externos

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

Precondicionamiento para problemas de valores propios

Los problemas de valores propios pueden plantearse de varias maneras alternativas, cada una de las cuales conduce a su propio condicionamiento previo. El precondicionamiento tradicional se basa en las llamadas transformaciones espectrales. Conociendo (aproximadamente) el valor propio objetivo, se puede calcular el vector propio correspondiente resolviendo el sistema lineal homogéneo relacionado, lo que permite utilizar el precondicionamiento para el sistema lineal. Finalmente, formular el problema de valores propios como optimización del cociente de Rayleigh trae a escena técnicas de optimización precondicionadas. ^[4]

Transformaciones espectrales

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

La transformación espectral más popular es la llamada transformación de desplazamiento e inversión , donde para un escalar dado , llamado desplazamiento , el problema de valores propios original se reemplaza por el problema de desplazamiento e inversión . Los vectores propios 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 la iteración inversa , que normalmente converge al vector propio, correspondiente al valor propio más cercano al desplazamiento . La iteración del cociente de Rayleigh es un método de desplazamiento e inversión con un desplazamiento variable. ${\displaystyle \alpha }$ ${\displaystyle Ax=\lambda x}$ ${\displaystyle (A-\alpha I)^{-1}x=\mu x}$ ${\displaystyle \alpha }$

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

Preacondicionamiento general

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

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

El precondicionamiento ideal ^[4]

El pseudoinverso de Moore-Penrose es el precondicionador, lo que hace que la iteración de Richardson anterior converja en un paso con , ya que , denotado por , es el proyector ortogonal en el espacio propio, correspondiente a . La elección no es práctica por tres razones independientes. En primer lugar, en realidad no se conoce, aunque se puede sustituir por su aproximación . En segundo lugar, la pseudoinversa exacta de Moore-Penrose requiere el conocimiento del vector propio, que estamos tratando de encontrar. Esto puede evitarse en cierto modo mediante el uso del precondicionador de Jacobi-Davidson , donde se aproxima . Por último, pero no menos importante, este enfoque requiere una solución numérica precisa del sistema lineal con la matriz del sistema , lo que resulta tan costoso para problemas grandes como el método de desplazamiento e inversión anterior. Si la solución no es lo suficientemente precisa, el paso dos puede resultar redundante. ${\displaystyle T=(A-\lambda _{\star }I)^{+}}$ ${\displaystyle \gamma _{n}=1}$ ${\displaystyle I-(A-\lambda _{\star }I)^{+}(A-\lambda _{\star }I)}$ ${\displaystyle P_{\star }}$ ${\displaystyle \lambda _{\star }}$ ${\displaystyle T=(A-\lambda _{\star }I)^{+}}$ ${\displaystyle \lambda _{\star }}$ ${\displaystyle {\tilde {\lambda }}_{\star }}$ ${\displaystyle T=(I-{\tilde {P}}_{\star })(A-{\tilde {\lambda }}_{\star }I)^{-1}(I-{\tilde {P}}_{\star })}$ ${\displaystyle {\tilde {P}}_{\star }}$ ${\displaystyle P_{\star }}$ ${\displaystyle (A-{\tilde {\lambda }}_{\star }I)}$

Precondicionamiento práctico

Primero reemplacemos el valor teórico en la iteración de Richardson anterior con su aproximación actual para obtener un algoritmo práctico. ${\displaystyle \lambda _{\star }}$ ${\displaystyle \lambda _{n}}$

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

Una opción popular es utilizar la función del cociente de Rayleigh . El precondicionamiento práctico puede ser tan trivial como simplemente usar o. Para algunas clases de problemas de valores propios , se ha demostrado la eficiencia de , tanto numérica como teóricamente. La elección permite utilizar fácilmente para problemas de valores propios la gran variedad de precondicionadores desarrollados para sistemas lineales. ${\displaystyle \lambda _{n}=\rho (x_{n})}$ ${\displaystyle \rho (\cdot )}$ ${\displaystyle T=(\operatorname {diag} (A))^{-1}}$ ${\displaystyle T=(\operatorname {diag} (A-\lambda _{n}I))^{-1}.}$ ${\displaystyle T\approx A^{-1}}$ ${\displaystyle T\approx A^{-1}}$

Debido al valor cambiante , un análisis teórico exhaustivo de la convergencia es mucho más difícil, en comparación con el caso de los sistemas lineales, incluso para los métodos más simples, como la iteración de Richardson . ${\displaystyle \lambda _{n}}$

enlaces externos

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

Preacondicionamiento en optimización

Ilustración del descenso de gradiente

En optimización , el precondicionamiento se utiliza normalmente para acelerar los algoritmos de optimización de primer orden .

Descripción

Por ejemplo, para encontrar un mínimo local de una función de valor real usando el descenso de gradiente , se toman pasos proporcionales al negativo del gradiente (o del gradiente aproximado) de la función en el punto actual: ${\displaystyle F(\mathbf {x} )}$ ${\displaystyle -\nabla F(\mathbf {a} )}$

$${\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 de la geometría del espacio vectorial con el objetivo de hacer que los conjuntos de niveles parezcan círculos. ^[5] En este caso, el gradiente precondicionado apunta más cerca del punto de los extremos como en la figura, lo que acelera la convergencia.

Conexión a sistemas lineales.

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} ,}$$

matriz definida positiva simétrica realdescenso de gradiente ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {b} }$ ${\displaystyle A}$ ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle \nabla F(\mathbf {x} )=A\mathbf {x} -\mathbf {b} }$ ${\displaystyle F(\mathbf {x} )}$

$${\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 .

Conexión con problemas de valores propios

El mínimo del cociente de Rayleigh

$${\displaystyle \rho (\mathbf {x} )={\frac {\mathbf {x} ^{T}A\mathbf {x} }{\mathbf {x} ^{T}\mathbf {x} }},}$$

matriz definida positiva simétrica realvalor propiovector propiodescenso de gradiente ${\displaystyle \mathbf {x} }$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \nabla \rho (\mathbf {x} )}$ ${\displaystyle A\mathbf {x} -\rho (\mathbf {x} )\mathbf {x} }$ ${\displaystyle \rho (\mathbf {x} )}$

$${\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 es un análogo de la iteración de Richardson precondicionada para resolver problemas de valores propios.

Precondicionamiento variable

En muchos casos, puede ser beneficioso cambiar el precondicionador en algunos o incluso en cada paso de un algoritmo iterativo para adaptarse a una forma cambiante de los conjuntos de niveles, 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 la construcción de un preacondicionador eficiente suele ser computacionalmente costosa. El mayor costo de actualizar el preacondicionador puede anular fácilmente el efecto positivo de una convergencia más rápida. Si es una aproximación BFGS de la matriz de arpillera inversa, este método se denomina método Quasi-Newton . ${\displaystyle P_{n}^{-1}=H_{n}}$

Referencias

1. Shewchuk, Jonathan Richard (4 de agosto de 1994). "Una introducción al método del gradiente conjugado sin el dolor agonizante" (PDF) .
2. Henricus Bouwmeester, Andrew Dougherty, Andrew V Knyazev. Precondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado. Procedia Computer Science, volumen 51, páginas 276-285, Elsevier, 2015. https://doi.org/10.1016/j.procs.2015.05.241
3. Grote, MJ y Huckle, T. (1997). "Preacondicionamiento paralelo con inversas aproximadas escasas". Revista SIAM de Computación Científica . 18 (3): 838–53. doi :10.1137/S1064827594276552.
4. Knyazev, Andrew V. (1998). "Solucionadores propios precondicionados: ¿un oxímoron?". Transacciones Electrónicas sobre Análisis Numérico . 7 : 104-123.
5. Himmelblau, David M. (1972). Programación no lineal aplicada . Nueva York: McGraw-Hill. págs. 78–83. ISBN 0-07-028921-2.

Fuentes

• Axelsson, Deber (1996). Métodos de solución iterativos . Prensa de la Universidad de Cambridge. pag. 6722.ISBN​ 978-0-521-55569-2.
• D'yakonov, EG (1996). Optimización en la resolución de problemas elípticos. CRC-Prensa. pag. 592.ISBN​ 978-0-8493-2872-5.
• Saad, Yousef y van der Vorst, Henk (2001). "Solución iterativa de sistemas lineales en el siglo XX". En Brezinski, C. y Wuytack, L. (eds.). Análisis numérico: desarrollos históricos en el siglo XX . Editores científicos de Elsevier . §8 Métodos de precondicionamiento, págs. 193–8. ISBN 0-444-50617-9.
• van der Vorst, HA (2003). Métodos iterativos de Krylov para grandes sistemas lineales . Prensa de la Universidad de Cambridge, Cambridge. ISBN 0-521-81828-1.
• Chen, Ke (2005). Técnicas y aplicaciones de precondicionamiento de matrices. Cambridge: Prensa de la Universidad de Cambridge. ISBN 978-0521838283. OCLC  61410324.