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 tal que tiene un número de condición menor que. También es común llamar el preacondicionador, en lugar de , desde 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 columna, o un bloque de vectores columna, por , se realiza comúnmente mediante paquetes de software de computadora bastante sofisticados de una manera libre de matrices , es decir, donde ninguno, ni (y a menudo ni siquiera ) están disponibles explícitamente en forma de matriz.
Los preacondicionadores son útiles en métodos iterativos para resolver un sistema lineal por dado 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 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, convertirse en la única opción si la matriz de coeficientes no se almacena explícitamente, pero se accede mediante la evaluación de productos de matriz-vector.
Descripción
En lugar de resolver el sistema lineal original anterior, se puede considerar el sistema preacondicionado correcto
y resolver
por y
por .
Alternativamente, se puede resolver el sistema preacondicionado izquierdo
Ambos sistemas dan la misma solución que el sistema original siempre que la matriz del preacondicionador no es singular . El preacondicionamiento izquierdo es más tradicional.
El sistema preacondicionado de dos caras
puede ser beneficioso, por ejemplo, para preservar la simetría de la matriz: si la matriz original es real simétrico y preacondicionadores reales y satisfacer luego la matriz preacondicionada también es simétrico. El preacondicionamiento de dos caras es común para el escalado diagonal donde los preacondicionadores y son diagonales y la escala 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.
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 .
La matriz preacondicionada o rara vez se forma explícitamente. Solo la acción de aplicar la operación de resolución del preacondicionador a un vector dado puede necesitar ser calculado.
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, debe tener un pequeño costo (tiempo de cálculo) de aplicar el operación. Por 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 que tiene un número de condición óptimo de 1, que requiere una única iteración para la convergencia; sin embargo en este casoy aplicar el preacondicionador es tan difícil como resolver el sistema original. Uno por tanto elige 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 sencillo posible. A continuación se detallan algunos ejemplos de enfoques típicos de preacondicionamiento.
Métodos iterativos preacondicionados
Métodos iterativos preacondicionados para 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
Aplicado al sistema preacondicionado se convierte en un método preacondicionado
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 por
División de matriz
Un método iterativo estacionario está determinado por la división de la matriz y la matriz de iteración . Asumiendo que
- la matriz del sistema es simétrico positivo-definido ,
- la matriz de división es simétrico positivo-definido ,
- el método iterativo estacionario es convergente, según lo determinado por ,
el número de condición está delimitado por encima de
Interpretación geométrica
Para una matriz definida positiva simétrica el preacondicionador típicamente también se elige para ser simétrico positivo definido. El operador preacondicionado es entonces también simétrico positivo definido, pero con respecto a la -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 respeto a -producto escalar basado en ser casi esférico. [1]
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 actuando sobre el vector . Algunos preacondicionadores populares, sin embargo, cambian con y la dependencia de 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.
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 "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 la condición espectral sea el número deestar 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 del idealmente debería ser proporcional (también independiente del tamaño de la matriz) al costo de multiplicación de por un vector.
Ejemplos de
Preacondicionador Jacobi (o diagonal)
El preacondicionador Jacobi es una de las formas más sencillas de preacondicionamiento, en la que se elige el preacondicionador para que sea la diagonal de la matriz. Asumiendo , obtenemos Es eficiente para matrices diagonalmente dominantes. .
SPAI
El preacondicionador Sparse Approximate Inverse minimiza dónde es la norma de Frobenius yproviene 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 debe restringirse 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]
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 usando un preacondicionador . Sin embargo, esto tiene sentido solo si los autovectores buscadores de y 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, llamado cambio , el problema de valores propios originales se reemplaza con el problema de cambiar e invertir . 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.
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 estrecha conexión 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, dónde es el precondicionador, que podemos intentar resolver utilizando la iteración de Richardson
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, desde , denotado por , es el proyector ortogonal en el espacio propio, correspondiente a . La elecciónno es práctico por tres razones independientes. Primero, en realidad no se conoce, aunque se puede reemplazar 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 puede evitarse de alguna manera mediante el uso del preacondicionador Jacobi-Davidson , dónde aproxima . 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.
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
Una opción popular es usando la función de cociente de Rayleigh. El preacondicionamiento práctico puede ser tan trivial como usar o Para algunas clases de problemas de valores propios, la eficiencia de ha sido demostrado, 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.
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 .
enlaces externos
- Plantillas para la solución de problemas de valores propios algebraicos: una guía práctica
Preacondicionamiento en optimización
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 realusando el descenso de gradiente , se toman pasos proporcionales al negativo del gradiente (o del gradiente aproximado) de la función en el punto actual:
El preacondicionador se aplica al gradiente:
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
- ,
dónde y son vectores columna reales y es una matriz simétrica positiva definida real , es exactamente la solución de la ecuación lineal. Desde, el método de descenso de gradiente preacondicionado para minimizar es
É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
dónde es un vector 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 . Desde es proporcional a , el método de descenso de gradiente preacondicionado para minimizar es
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
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
- ^ Shewchuk, Jonathan Richard (4 de agosto de 1994). "Una introducción al método de gradiente conjugado sin el dolor agonizante" (PDF) .
- ^ 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
- ^ 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 .
- ^ a b Knyazev, Andrew V. (1998). "Eigensolvers preacondicionados - ¿un oxímoron?" . Transacciones electrónicas sobre análisis numérico . 7 : 104-123.
- ^ 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).