Preacondicionador

Método de acondicionamiento de un sistema de ecuaciones en una forma que sea más adecuada para los métodos de resolución numérica.

El "preacondicionamiento" vuelve a dirigir aquí. Para otros usos, consulte Acondicionamiento previo (desambiguación) .

Este artículo incluye una lista de referencias generales , pero permanece en gran parte sin verificar porque carece de suficientes citas en línea correspondientes . Ayude a mejorar este artículo introduciendo citas más precisas. ( Febrero de 2013 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

En matemáticas , el preacondicionamiento es la aplicación de una transformación, llamada preacondicionador , que condiciona un problema dado en una forma más adecuada para los 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 preacondicionado 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 preacondicionador, en lugar de , ya que en sí mismo rara vez está explícitamente disponible. En el preacondicionamiento moderno, la aplicación de , es decir, la multiplicación de un vector de columna, o un bloque de vectores de columna, por , se realiza comúnmente mediante paquetes de software informático bastante sofisticados sin matrices , es decir, donde ni , ni (ya menudo ni siquiera ) están explícitamente disponibles en forma de matriz.${\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}$

Precondicionadores son útiles en métodos iterativos para resolver un sistema lineal de desde la tasa de convergencia para la mayoría de iterativos solucionadores lineales aumenta debido a que el número de condición de una matriz disminuye como resultado de preacondicionamiento. Los solucionadores iterativos preacondicionados 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, se convierten en la única opción si la matriz de coeficientes no se almacena explícitamente, sino que se accede mediante la evaluación de productos matriz-vector.${\displaystyle Ax=b}$${\displaystyle x}$${\displaystyle A}$

Descripción

En lugar de resolver el sistema lineal original anterior, se puede considerar el sistema preacondicionado correcto

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

y resolver

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

para y${\displaystyle y}$

${\displaystyle Px=y}$

para .${\displaystyle x}$

Alternativamente, se puede resolver el sistema preacondicionado izquierdo

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

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

El sistema preacondicionado de dos caras

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

puede ser beneficioso, por ejemplo, para preservar la simetría de la matriz: si la matriz original es simétrica real y los preacondicionadores reales y satisfacen, entonces la matriz preacondicionada también es simétrica. El preacondicionamiento de dos caras es común para el escalado diagonal donde los preacondicionadores y son diagonales y el escalado se aplica tanto a las columnas como a las filas de la matriz original , por ejemplo, para disminuir el rango dinámico de entradas de la matriz.${\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 izquierda o derecha 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 preacondicionada o rara vez se forma explícitamente. Solo puede ser necesario calcular la acción de aplicar la operación de resolución del preacondicionador a un vector dado.${\displaystyle P^{-1}A}$${\displaystyle AP^{-1}}$${\displaystyle P^{-1}}$

Por lo general, existe 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. El preacondicionador más barato sería, por tanto, 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 el número de condición óptimo de 1, requiriendo una sola iteración para la convergencia; sin embargo, en este caso, aplicar el preacondicionador es tan difícil como resolver el sistema original. Uno por tanto elige ${\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}$ como en algún lugar 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 típicos de preacondicionamiento.${\displaystyle P^{-1}}$

Métodos iterativos preacondicionados

Los métodos iterativos preacondicionados son, en la mayoría de los casos, matemáticamente equivalentes a los métodos iterativos estándar aplicados al sistema preacondicionado.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 preacondicionados populares para sistemas lineales incluyen el método de gradiente conjugado preacondicionado , el método de gradiente biconjugado y el método de residuo 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 matriz

Un método iterativo estacionario se determina mediante 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á acotado 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 preacondicionador se elige típicamente para que también sea definido positivo simétrico. El operador preacondicionado es entonces también simétrico positivo definido, pero con respecto al producto escalar basado en- . En este caso, el efecto deseado al aplicar un preacondicionador es hacer que la forma cuadrática del operador preacondicionado 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 preacondicionamiento se implementa prácticamente como multiplicar algún vector por , es decir, calcular el producto. En muchas aplicaciones, no se da como una matriz, sino como un operador que actúa sobre el vector . Sin embargo, algunos preacondicionadores populares cambian y la dependencia puede no ser lineal. Los ejemplos típicos implican el uso de métodos iterativos no lineales , por ejemplo, el método de gradiente conjugado , como parte de la construcción del preacondicionador. Dichos preacondicionadores pueden ser prácticamente muy eficientes, 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}$

Preacondicionamiento aleatorio

Un caso particular interesante de preacondicionamiento variable es el preacondicionamiento aleatorio, por ejemplo, preacondicionamiento de redes múltiples en cuadrículas de rumbo aleatorias. ^[2] Si se utiliza en métodos de descenso de gradiente , el preacondicionamiento 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 preacondicionamiento fijo, ya que rompe el patrón asintótico en "zig-zag" del descenso de gradiente .

Preacondicionamiento espectralmente equivalente

El uso más común del preacondicionamiento es para la solución iterativa de sistemas lineales que resultan 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 preacondicionamiento óptimo es, por un lado, hacer que el número de condición espectral de esté delimitado desde arriba por una constante independiente del tamaño de la matriz, que D'yakonov denomina preacondicionamiento espectralmente equivalente . Por otro lado, el costo de aplicación de debería ser idealmente proporcional (también independiente del tamaño de la matriz) al costo de multiplicación de por un vector.${\displaystyle P^{-1}A}$${\displaystyle P^{-1}}$${\displaystyle A}$

Ejemplos de

Preacondicionador Jacobi (o diagonal)

El preacondicionador de Jacobi es una de las formas más simples de preacondicionamiento, en la que se elige el preacondicionador para que sea la diagonal de la matriz. Suponiendo que obtenemos que es eficiente para matrices diagonalmente dominantes .${\displaystyle P=\mathrm {diag} (A).}$${\displaystyle A_{ii}\neq 0,\forall i}$${\displaystyle P_{ij}^{-1}={\frac {\delta _{ij}}{A_{ij}}}.}$ ${\displaystyle A}$

SPAI

El preacondicionador 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 deben estar restringidas a algún patrón de escasez o el problema seguirá siendo tan difícil y lento 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 preacondicionadores

• Factorización incompleta de Cholesky
• Factorización de LU incompleta
• Relajación excesiva sucesiva
  • Relajación excesiva sucesiva simétrica
• Preacondicionamiento de redes múltiples

enlaces externos

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

Preacondicionamiento para problemas de valores propios

Los problemas de valores propios pueden enmarcarse de varias formas alternativas, cada una de las cuales conduce a su propio preacondicionamiento. El preacondicionamiento tradicional se basa en las denominadas 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 preacondicionamiento para el sistema lineal. Finalmente, formular el problema de los valores propios como optimización del cociente de Rayleigh trae a la escena técnicas de optimización preacondicionadas. ^[4]

Transformaciones espectrales

Por analogía con los sistemas lineales, para un problema de valores propios , uno puede tener la tentación de reemplazar la matriz con la matriz utilizando un preacondicionador . 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 denominada transformación de desplazamiento e inversión , en la que para un escalar determinado , denominado desplazamiento , el problema de valor propio original se reemplaza por el problema de desplazamiento e inversión . 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 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 para 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, que se convierte en el principal cuello de botella para grandes problemas.

Preacondicionamiento general

Para establecer una conexión cercana con los sistemas lineales, supongamos que el valor propio objetivo se conoce (aproximadamente). Entonces se puede calcular el vector propio correspondiente del sistema lineal homogéneo . Usando el concepto de preacondicionamiento izquierdo para sistemas lineales, obtenemos , donde es el preacondicionador, 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 preacondicionamiento ideal ^[4]

El pseudoinverso de Moore-Penrose es el preacondicionador, 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. Primero, en realidad no se conoce, aunque puede reemplazarse con su aproximación . En segundo lugar, el pseudoinverso exacto de Moore-Penrose requiere el conocimiento del vector propio, que estamos tratando de encontrar. Esto se puede eludir de alguna manera mediante el uso del preacondicionador Jacobi-Davidson , donde se aproxima${\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 }}$. Por último, pero no menos importante, este enfoque requiere una solución numérica precisa del sistema lineal con la matriz del sistema , que se vuelve 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 ser redundante.${\displaystyle (A-{\tilde {\lambda }}_{\star }I)}$

Preacondicionamiento 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 de cociente de Rayleigh . El preacondicionamiento 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 amplia variedad de preacondicionadores desarrollados para sistemas lineales.${\displaystyle \lambda _{n}=\rho (x_{n})}$${\displaystyle \rho (\cdot )}$${\displaystyle T=(diag(A))^{-1}}$${\displaystyle T=(diag(A-\lambda _{n}I))^{-1}.}$${\displaystyle T\approx A^{-1}}$${\displaystyle T\approx A^{-1}}$

Debido al valor cambiante , un análisis de convergencia teórico completo 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 de valores propios algebraicos: una guía práctica

Preacondicionamiento en optimización

Ilustración de descenso de gradiente

En optimización , el preacondicionamiento 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 preacondicionado 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} )={\frac {1}{2}}\mathbf {x} ^{T}A\mathbf {x} -\mathbf {x} ^{T}\mathbf {b} }$,

donde y son vectores columna reales y es una matriz definida positiva simétrica real , es exactamente la solución de la ecuación lineal . Dado que , el método de descenso de gradiente preacondicionado para minimizar es${\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.}$

Ésta es la iteración de Richardson preacondicionada 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} }},}$

donde es un vector de columna real distinto de cero y es una matriz simétrica positiva definida real , es el valor propio más pequeño de , mientras que el minimizador es el vector propio correspondiente . Dado que es proporcional a , el método de descenso de gradiente preacondicionado para minimizar es${\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 preacondicionada para resolver problemas de valores propios.

Preacondicionamiento variable

En muchos casos, puede ser beneficioso cambiar el preacondicionador 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, se debe tener en cuenta que la construcción de un preacondicionador eficiente suele ser computacionalmente costosa. El mayor costo de actualización del preacondicionador puede anular fácilmente el efecto positivo de una convergencia más rápida.

Referencias

1. Shewchuk, Jonathan Richard (4 de agosto de 1994). "Una introducción al método de gradiente conjugado sin el dolor agonizante" (PDF) .
2. Henricus Bouwmeester, Andrew Dougherty, Andrew V Knyazev. Preacondicionamiento 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). "Eigensolvers preacondicionados - ¿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, Owe (1996). Métodos de solución iterativa . 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-Press. 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 de ciencia de Elsevier . §8 Métodos de preacondicionamiento, 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.
• Ke Chen: "Técnicas y aplicaciones de preacondicionamiento de matrices", Cambridge University Press, ISBN 978-0521838283 (2005).