Álgebra lineal numérica

El álgebra lineal numérica , también conocida como álgebra lineal aplicada , estudia cómo se pueden utilizar las operaciones matriciales para crear algoritmos informáticos que proporcionen respuestas aproximadas, eficientes y precisas a problemas de matemáticas continuas . Es un subcampo del análisis numérico y un tipo de álgebra lineal . Los ordenadores utilizan aritmética de punto flotante y no pueden representar con exactitud datos irracionales ; por lo tanto, cuando se aplica un algoritmo informático a una matriz de datos, a veces puede aumentar la diferencia entre un número almacenado en el ordenador y el número real del que se aproxima. El álgebra lineal numérica utiliza las propiedades de los vectores y las matrices para desarrollar algoritmos informáticos que minimicen el error introducido por el ordenador, y también se preocupa por garantizar que el algoritmo sea lo más eficiente posible.

El álgebra lineal numérica tiene como objetivo resolver problemas de matemáticas continuas utilizando computadoras de precisión finita, por lo que sus aplicaciones a las ciencias naturales y sociales son tan vastas como las aplicaciones de las matemáticas continuas. A menudo es una parte fundamental de problemas de ingeniería y ciencias computacionales , como el procesamiento de imágenes y señales , telecomunicaciones , finanzas computacionales , simulaciones de ciencia de materiales , biología estructural , minería de datos , bioinformática , dinámica de fluidos y estadística computacional . Los métodos matriciales se utilizan particularmente en métodos de diferencias finitas , métodos de elementos finitos y el modelado de ecuaciones diferenciales . Al observar las amplias aplicaciones del álgebra lineal numérica, Lloyd N. Trefethen y David Bau, III argumentan que es "tan fundamental para las ciencias matemáticas como el cálculo y las ecuaciones diferenciales", ^{[ 1 ]}^{: x} aunque sea un campo relativamente pequeño. ^{[ 2 ]} Debido a que muchas propiedades de matrices y vectores también se aplican a funciones y operadores, el álgebra lineal numérica también puede verse como un tipo de análisis funcional que tiene un énfasis particular en algoritmos prácticos. ^{[ 1 ]}^{: ix}

En álgebra lineal numérica, es común obtener descomposiciones de matrices como la descomposición en valores singulares , la factorización QR , la factorización LU o la descomposición en valores propios , las cuales pueden utilizarse para resolver problemas algebraicos lineales comunes, como sistemas de ecuaciones lineales, la localización de valores propios o la optimización por mínimos cuadrados. El objetivo principal del álgebra lineal numérica, que consiste en desarrollar algoritmos que no introduzcan errores al aplicarse a datos reales en un ordenador de precisión finita, se suele lograr mediante métodos iterativos en lugar de métodos directos.

Historia

El álgebra lineal numérica fue desarrollada por pioneros de la informática como John von Neumann , Alan Turing , James H. Wilkinson , Alston Scott Householder , George Forsythe y Heinz Rutishauser , con el fin de aplicar las primeras computadoras a problemas de matemáticas continuas, como problemas de balística y soluciones de sistemas de ecuaciones diferenciales parciales . ^{[ 2 ]} El primer intento serio de minimizar el error computacional en la aplicación de algoritmos a datos reales es el trabajo de John von Neumann y Herman Goldstine en 1947. ^{[ 3 ]} El campo ha crecido a medida que la tecnología ha permitido cada vez más a los investigadores resolver problemas complejos en matrices de alta precisión extremadamente grandes, y algunos algoritmos numéricos han ganado prominencia a medida que tecnologías como la computación paralela los han convertido en enfoques prácticos para problemas científicos. ^{[ 2 ]}

Descomposiciones matriciales

Matrices particionadas

Para muchos problemas de álgebra lineal aplicada, es útil adoptar la perspectiva de una matriz como una concatenación de vectores columna. Por ejemplo, al resolver el sistema lineal $x=A^{-1}b$ , en lugar de entender x como el producto de $A^{-1}$ Con b , es útil pensar en x como el vector de coeficientes en la expansión lineal de b en la base formada por las columnas de A. ^{[ 1} ] ^{: 8 Pensar en las matrices como una concatenación de columnas también es un enfoque práctico para los propósitos de los algoritmos de matrices. Esto se debe a que los algoritmos}^de matrices frecuentemente contienen dos bucles anidados: uno sobre las columnas de una matriz A y otro sobre las filas de A. Por ejemplo, para matrices $A^{m\times n}$ y vectores $x^{n\times 1}$ y $y^{m\times 1}$ , podríamos usar la perspectiva de partición de columnas para calcular y := Ax + y como

para q = 1 : n para p = 1 : m y ( p ) = A ( p , q ) * x ( q ) + y ( p ) fin fin

Descomposición en valores singulares

La descomposición en valores singulares de una matriz $A^{m\times n}$ es $A=U\Sigma V^{\ast }$ donde U y V son unitarias y $\Sigma$ es diagonal . Las entradas diagonales de $\Sigma$ se denominan valores singulares de A. Porque los valores singulares son las raíces cuadradas de los valores propios de $AA^{\ast }$ Existe una estrecha relación entre la descomposición en valores singulares y la descomposición en valores propios. Esto significa que la mayoría de los métodos para calcular la descomposición en valores singulares son similares a los métodos de valores propios; ^{[ 1 ]}^{: 36} quizás el método más común involucre los procedimientos de Householder . ^{[ 1 ]}^{: 253}

factorización QR

La factorización QR de una matriz $A^{m\times n}$ es una matriz $Q^{m\times m}$ y una matriz $R^{m\times n}$ de modo que A = QR , donde Q es ortogonal y R es triangular superior . ^{[ 1 ]}^{: 50}^{[ 4 ]}^{: 223} Los dos algoritmos principales para calcular factorizaciones QR son el proceso de Gram-Schmidt y la transformación de Householder . La factorización QR se usa a menudo para resolver problemas de mínimos cuadrados lineales y problemas de valores propios (a través del algoritmo QR iterativo ).

factorización LU

Una factorización LU de una matriz A consiste en una matriz triangular inferior L y una matriz triangular superior U de modo que A = LU . La matriz U se obtiene mediante un procedimiento de triangularización superior que implica multiplicar por la izquierda A por una serie de matrices. $M_{1},\ldots ,M_{n-1}$ para formar el producto $M_{n-1}\cdots M_{1}A=U$ , de modo que equivalentemente $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ . ^{[ 1 ]}^{: 147}^{[ 4 ]}^{: 96}

descomposición en valores propios

La descomposición en valores propios de una matriz $A^{m\times m}$ es $A=X\Lambda X^{-1}$ , donde las columnas de X son los vectores propios de A y $\Lambda$ es una matriz diagonal cuyas entradas diagonales son los autovalores correspondientes de A. ^{[ 1 ]}^{: 33} No existe un método directo para hallar la descomposición en autovalores de una matriz arbitraria. Dado que no es posible escribir un programa que encuentre las raíces exactas de un polinomio arbitrario en tiempo finito, cualquier solucionador general de autovalores debe ser necesariamente iterativo. ^{[ 1 ]}^{: 192}

Algoritmos

eliminación gaussiana

Desde la perspectiva del álgebra lineal numérica, la eliminación gaussiana es un procedimiento para factorizar una matriz A en su factorización LU , lo cual la eliminación gaussiana logra multiplicando por la izquierda A por una sucesión de matrices. $L_{m-1}\cdots L_{2}L_{1}A=U$ hasta que U sea triangular superior y L sea triangular inferior, donde $L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1}$ . ^{[ 1 ]}^{: 148} Los programas ingenuos para la eliminación gaussiana son notoriamente inestables y producen errores enormes cuando se aplican a matrices con muchos dígitos significativos. ^{[ 2 ]} La solución más simple es introducir el pivoteo , que produce un algoritmo de eliminación gaussiana modificado que es estable. ^{[ 1 ]}^{: 151}

Soluciones de sistemas lineales

El álgebra lineal numérica se caracteriza por abordar las matrices como una concatenación de vectores columna. Para resolver el sistema lineal $x=A^{-1}b$ , el enfoque algebraico tradicional es entender x como el producto de $A^{-1}$ con b . El álgebra lineal numérica interpreta x como el vector de coeficientes de la expansión lineal de ^b en la base formada por las columnas de A. ^{[ 1} ] ^{: 8}

Se pueden utilizar muchas descomposiciones diferentes para resolver el problema lineal, dependiendo de las características de la matriz A y los vectores x y b , lo que puede hacer que una factorización sea mucho más fácil de obtener que otras. Si A = QR es una factorización QR de A , entonces equivalentemente $Rx=Q^{\ast }b$ Esto es tan fácil de calcular como una factorización matricial. ^{[ 1 ]}^{: 54} Si $A=X\Lambda X^{-1}$ es una descomposición en valores propios A , y buscamos encontrar b de modo que b = Ax , con $b'=X^{-1}b$ y $x'=X^{-1}x$ , entonces tenemos $b'=\Lambda x'$ . ^{[ 1 ]}^{: 33} Esto está estrechamente relacionado con la solución del sistema lineal utilizando la descomposición en valores singulares, porque los valores singulares de una matriz son los valores absolutos de sus autovalores, que también son equivalentes a las raíces cuadradas de los valores absolutos de los autovalores de la matriz de Gram. $X^{*}X$ Y si A = LU es una factorización LU de A , entonces Ax = b se puede resolver usando las matrices triangulares Ly = b y Ux = y . ^{[ 1 ]}^{: 147}^{[ 4 ]}^{: 99}

Optimización por mínimos cuadrados

Las descomposiciones matriciales sugieren varias formas de resolver el sistema lineal r = b − Ax donde buscamos minimizar r , como en el problema de regresión . El algoritmo QR resuelve este problema calculando la factorización QR reducida de A y reordenándola para obtener ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ Este sistema triangular superior se puede resolver para x . La SVD también sugiere un algoritmo para obtener mínimos cuadrados lineales. Al calcular la descomposición SVD reducida $A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }$ y luego calculando el vector ${\widehat {U}}^{\ast }b$ , reducimos el problema de mínimos cuadrados a un sistema diagonal simple. ^{[ 1 ]}^{: 84} El hecho de que las soluciones de mínimos cuadrados se puedan producir mediante las factorizaciones QR y SVD significa que, además del método clásico de ecuaciones normales para resolver problemas de mínimos cuadrados, estos problemas también se pueden resolver mediante métodos que incluyen el algoritmo de Gram-Schmidt y los métodos de Householder.

Acondicionamiento y estabilidad

Supongamos que un problema es una función. $f:X\to Y$ donde X es un espacio vectorial normado de datos e Y es un espacio vectorial normado de soluciones. Para algún punto de datos $x\in X$ Se dice que un problema está mal condicionado si una pequeña perturbación en x produce un gran cambio en el valor de f ( x ). Podemos cuantificar esto definiendo un número de condición que representa qué tan bien condicionado está un problema, definido como ${\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}.$

La inestabilidad es la tendencia de los algoritmos informáticos, que dependen de la aritmética de punto flotante , a producir resultados que difieren drásticamente de la solución matemática exacta de un problema. Cuando una matriz contiene datos reales con muchas cifras significativas , muchos algoritmos para resolver problemas como sistemas de ecuaciones lineales u optimización por mínimos cuadrados pueden producir resultados muy imprecisos. La creación de algoritmos estables para problemas mal condicionados es una preocupación central en el álgebra lineal numérica. Un ejemplo es que la estabilidad de la triangularización de Householder la convierte en un método de solución particularmente robusto para sistemas lineales, mientras que la inestabilidad del método de ecuaciones normales para resolver problemas de mínimos cuadrados es una razón para favorecer los métodos de descomposición de matrices, como el uso de la descomposición en valores singulares. Algunos métodos de descomposición de matrices pueden ser inestables, pero tienen modificaciones sencillas que los hacen estables; un ejemplo es el método inestable de Gram-Schmidt, que se puede cambiar fácilmente para producir el método estable de Gram-Schmidt modificado . ^{[ 1 ]}^{: 140} Otro problema clásico en álgebra lineal numérica es el hallazgo de que la eliminación gaussiana es inestable, pero se vuelve estable con la introducción del pivoteo.

Métodos iterativos

Hay dos razones por las que los algoritmos iterativos son una parte importante del álgebra lineal numérica. Primero, muchos problemas numéricos importantes no tienen solución directa; para encontrar los valores propios y los vectores propios de una matriz arbitraria, solo podemos adoptar un enfoque iterativo. Segundo, los algoritmos no iterativos para una matriz arbitraria $m\times m$ Requiere matriz $O(m^{3})$ tiempo, que es un piso sorprendentemente alto dado que las matrices contienen solo $m^{2}$ números. Los enfoques iterativos pueden aprovechar varias características de algunas matrices para reducir este tiempo. Por ejemplo, cuando una matriz es dispersa , un algoritmo iterativo puede omitir muchos de los pasos que un enfoque directo seguiría necesariamente, incluso si son pasos redundantes dada una matriz altamente estructurada.

El núcleo de muchos métodos iterativos en álgebra lineal numérica es la proyección de una matriz sobre un subespacio de Krylov de menor dimensión , lo que permite aproximar las características de una matriz de alta dimensión calculando iterativamente las características equivalentes de matrices similares, comenzando en un espacio de baja dimensión y avanzando sucesivamente a dimensiones superiores. Cuando A es simétrica y deseamos resolver el problema lineal Ax = b , el enfoque iterativo clásico es el método del gradiente conjugado . Si A no es simétrica, entonces ejemplos de soluciones iterativas al problema lineal son el método generalizado de residuos mínimos y CGN . Si A es simétrica, entonces para resolver el problema de valores y vectores propios podemos usar el algoritmo de Lanczos , y si A no es simétrica, entonces podemos usar la iteración de Arnoldi .

Software

Varios lenguajes de programación utilizan técnicas de optimización de álgebra lineal numérica y están diseñados para implementar algoritmos de álgebra lineal numérica. Estos lenguajes incluyen MATLAB , Analytica , Maple y Mathematica . Otros lenguajes de programación que no están diseñados explícitamente para álgebra lineal numérica tienen bibliotecas que proporcionan rutinas y optimización de álgebra lineal numérica; C y Fortran tienen paquetes como Basic Linear Algebra Subprograms y LAPACK , Python tiene la biblioteca NumPy y Perl tiene Perl Data Language . Muchos comandos de álgebra lineal numérica en R dependen de estas bibliotecas más fundamentales como LAPACK . ^{[ 5 ]} Se pueden encontrar más bibliotecas en la Lista de bibliotecas numéricas .

Referencias

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Trefethen, Lloyd; Bau III, David (1997). Álgebra lineal numérica (1.ª ed.). Filadelfia: SIAM. ISBN 978-0-89871-361-9.
1 2 3 4 Golub, Gene H. "Una historia del álgebra lineal numérica moderna" (PDF) . Departamento de Estadística de la Universidad de Chicago . Recuperado el 17 de febrero de 2019 .
↑ von Neumann, John; Goldstine, Herman H. (1947). "Inversión numérica de matrices de alto orden" . Boletín de la Sociedad Matemática Americana . 53 (11): 1021– 1099. doi : 10.1090/s0002-9904-1947-08909-6 . S2CID 16174165 .
1 2 3 Golub, Gene H.; Van Loan, Charles F. (1996). Computación matricial (3.ª ed.). Baltimore: The Johns Hopkins University Press. ISBN 0-8018-5413-X.
↑ Rickert, Joseph (29 de agosto de 2013). "R y álgebra lineal" . R-bloggers . Consultado el 17 de febrero de 2019 .

Lecturas adicionales

Dongarra, Jack ; Hammarling, Sven (1990). «Evolución del software numérico para álgebra lineal densa». En Cox, MG; Hammarling, S. (eds.). Computación numérica fiable . Oxford: Clarendon Press. pp. 297–327 . ISBN 0-19-853564-3.
Claude Brezinski, Gérard Meurant y Michela Redivo-Zaglia (2022): Un viaje por la historia del álgebra lineal numérica , SIAM, ISBN 978-1-61197-722-6.

Demmel, JW (1997): Álgebra lineal numérica aplicada , SIAM.
Ciarlet, PG , Miara, B., & Thomas, JM (1989): Introducción al álgebra lineal numérica y optimización , Cambridge Univ. Press.
Trefethen, Lloyd; Bau III, David (1997): Álgebra lineal numérica (1.ª ed.), SIAM, ISBN 978-0-89871-361-9
Golub, Gene H.; Van Loan, Charles F. (1996): Matrix Computations (3.ª ed.), The Johns Hopkins University Press. ISBN 978-0-8018-5413-2
GW Stewart (1998): Algoritmos matriciales Vol. I: Descomposiciones básicas , SIAM, ISBN 978-0-89871-414-2
GW Stewart (2001): Algoritmos matriciales Vol II: Sistemas propios , SIAM, ISBN 978-0-89871-503-3
Varga, Richard S. (2000): Análisis iterativo de matrices , Springer.
Yousef Saad (2003) : Métodos iterativos para sistemas lineales dispersos , 2.ª ed., SIAM, ISBN 978-0-89871534-7
Raf Vandebril, Marc Van Barel y Nicola Mastronardi (2008): Computaciones matriciales y matrices semiseparables, Volumen 1: Sistemas lineales , Johns Hopkins Univ. Press, ISBN 978-0-8018-8714-7
Raf Vandebril, Marc Van Barel y Nicola Mastronardi (2008): Matrix Computations and Semiseparable Matrices, Volume 2: Eigenvalue and Singular Value Methods , Johns Hopkins Univ. Press, ISBN 978-0-8018-9052-9
Higham, NJ (2002): Precisión y estabilidad de los algoritmos numéricos , SIAM.
Higham, NJ (2008): Funciones de matrices: teoría y computación , SIAM.
David S. Watkins (2008): El problema de los valores propios de la matriz: métodos GR y de subespacio de Krylov , SIAM.
Liesen, J., y Strakos, Z. (2012): Métodos de subespacios de Krylov: Principios y análisis , Oxford Univ. Press.

Enlaces externos

Software gratuito disponible en la web para álgebra numérica , creado por Jack Dongarra y Hatem Ltaief, de la Universidad de Tennessee.
Biblioteca NAG de rutinas de álgebra lineal numérica
Grupo de Álgebra Lineal Numérica en X (Grupo de investigación en el Reino Unido)
siagla en X (Grupo de actividad sobre álgebra lineal numérica en la Sociedad de Matemáticas Industriales y Aplicadas )
El Grupo de Actividades de GAMM sobre Álgebra Lineal Aplicada y Numérica

[tb397-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Trefethen, Lloyd; Bau III, David (1997). Álgebra lineal numérica (1.ª ed.). Filadelfia: SIAM. ISBN 978-0-89871-361-9.

[golubhist-2] 1 2 3 4 Golub, Gene H. "Una historia del álgebra lineal numérica moderna" (PDF) . Departamento de Estadística de la Universidad de Chicago . Recuperado el 17 de febrero de 2019 .

[3] von Neumann, John; Goldstine, Herman H. (1947). "Inversión numérica de matrices de alto orden" . Boletín de la Sociedad Matemática Americana . 53 (11): 1021– 1099. doi : 10.1090/s0002-9904-1947-08909-6 . S2CID 16174165 .

[gvl96-4] 1 2 3 Golub, Gene H.; Van Loan, Charles F. (1996). Computación matricial (3.ª ed.). Baltimore: The Johns Hopkins University Press. ISBN 0-8018-5413-X.

[5] Rickert, Joseph (29 de agosto de 2013). "R y álgebra lineal" . R-bloggers . Consultado el 17 de febrero de 2019 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]