El álgebra lineal numérica , a veces llamada álgebra lineal aplicada , es el estudio de cómo se pueden utilizar las operaciones matriciales para crear algoritmos informáticos que proporcionen de manera eficiente y precisa respuestas aproximadas a preguntas en matemáticas continuas . Es un subcampo del análisis numérico y un tipo de álgebra lineal . Las computadoras utilizan aritmética de punto flotante y no pueden representar exactamente datos irracionales , por lo que cuando se aplica un algoritmo informático a una matriz de datos, a veces puede aumentar la diferencia entre un número almacenado en la computadora y el número verdadero del que es una aproximación. El álgebra lineal numérica utiliza propiedades de vectores y matrices para desarrollar algoritmos informáticos que minimicen el error introducido por la computadora, y también se ocupa de 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 amplias como las aplicaciones de las matemáticas continuas. A menudo es una parte fundamental de los problemas de ingeniería y ciencia computacional , como el procesamiento de imágenes y señales , las telecomunicaciones , las finanzas computacionales , las simulaciones de la ciencia de los materiales , la biología estructural , la minería de datos , la bioinformática y la dinámica de fluidos . Los métodos matriciales se utilizan particularmente en los métodos de diferencias finitas , los métodos de elementos finitos y el modelado de ecuaciones diferenciales . Al notar 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 a pesar de que es un campo comparativamente 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 los algoritmos prácticos. [1] : ix
Los problemas comunes en el álgebra lineal numérica incluyen la obtención de descomposiciones matriciales como la descomposición en valores singulares , la factorización QR , la factorización LU o la descomposición propia , que luego se pueden usar para responder problemas algebraicos lineales comunes como la resolución de sistemas lineales de ecuaciones, la localización de valores propios o la optimización por mínimos cuadrados. La preocupación central del álgebra lineal numérica es desarrollar algoritmos que no introduzcan errores cuando se aplican a datos reales en una computadora de precisión finita. A menudo se logra mediante métodos iterativos en lugar de métodos directos.
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 las soluciones a sistemas de ecuaciones diferenciales parciales . [2] El primer intento serio de minimizar el error informático 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 extremadamente grandes de alta precisión, 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]
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 , en lugar de entender x como el producto de 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 matriciales. Esto se debe a que los algoritmos matriciales contienen con frecuencia dos bucles anidados: uno sobre las columnas de una matriz A , y otro sobre las filas de A . Por ejemplo, para matrices y vectores y , 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 La descomposición en valores singulares de una matriz es donde U y V son unitarios y es diagonal . Las entradas diagonales de se denominan valores singulares de A. Debido a que los valores singulares son las raíces cuadradas de los valores propios de , existe una estrecha conexión entre la descomposición en valores singulares y las descomposiciones 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 implica procedimientos Householder . [1] : 253
La factorización QR de una matriz es una matriz y una matriz tal 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 utiliza a menudo para resolver problemas de mínimos cuadrados lineales y problemas de valores propios (por medio del algoritmo QR iterativo ).
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 encuentra mediante un procedimiento de triangularización superior que implica multiplicar por la izquierda A por una serie de matrices para formar el producto , de modo que, equivalentemente . [1] : 147 [4] : 96
La descomposición en valores propios de una matriz es , donde las columnas de X son los vectores propios de A , y es una matriz diagonal cuyas entradas diagonales son los valores propios correspondientes de A . [1] : 33 No existe un método directo para encontrar la descomposición en valores propios de una matriz arbitraria. Debido a que no es posible escribir un programa que encuentre las raíces exactas de un polinomio arbitrario en tiempo finito, cualquier solucionador general de valores propios debe ser necesariamente iterativo. [1] : 192
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 , que la eliminación gaussiana logra multiplicando por la izquierda A por una sucesión de matrices hasta que U sea triangular superior y L sea triangular inferior, donde . [1] : 148 Los programas ingenuos para la eliminación gaussiana son notoriamente altamente inestables y producen enormes errores cuando se aplican a matrices con muchos dígitos significativos. [2] La solución más simple es introducir pivoteo , que produce un algoritmo de eliminación gaussiana modificado que es estable. [1] : 151
El álgebra lineal numérica se caracteriza por abordar las matrices como una concatenación de vectores de columnas. Para resolver el sistema lineal , el enfoque algebraico tradicional consiste en entender x como el producto de b . El álgebra lineal numérica, en cambio, 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 . Esto es tan fácil de calcular como una factorización matricial. [1] : 54 Si es una descomposición propia A , y buscamos encontrar b de modo que b = Ax , con y , entonces tenemos . [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 valores propios, que también son equivalentes a las raíces cuadradas de los valores absolutos de los valores propios de la matriz de Gram . Y si A = LU es una factorización LU de A , entonces Ax = b se puede resolver utilizando las matrices triangulares Ly = b y Ux = y . [1] : 147 [4] : 99
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 reordenando para obtener . Este sistema triangular superior puede entonces resolverse para x . La SVD también sugiere un algoritmo para obtener mínimos cuadrados lineales. Al calcular la descomposición SVD reducida y luego calcular el vector , reducimos el problema de mínimos cuadrados a un sistema diagonal simple. [1] : 84 El hecho de que las soluciones de mínimos cuadrados puedan producirse 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 pueden resolverse mediante métodos que incluyen el algoritmo de Gram-Schmidt y los métodos de Householder.
Supongamos que un problema es una función , donde X es un espacio vectorial normalizado de datos e Y es un espacio vectorial normalizado de soluciones. Para algún punto de datos , se dice que el 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
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 muchos dígitos significativos , muchos algoritmos para resolver problemas como sistemas lineales de ecuaciones u optimización por mínimos cuadrados pueden producir resultados altamente inexactos. 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 matricial como el uso de la descomposición en valores singulares. Algunos métodos de descomposición matricial pueden ser inestables, pero tienen modificaciones sencillas que los hacen estables; un ejemplo es el inestable Gram-Schmidt, que se puede cambiar fácilmente para producir el estable Gram-Schmidt modificado . [1] : 140 Otro problema clásico en el álgebra lineal numérica es el hallazgo de que la eliminación gaussiana es inestable, pero se vuelve estable con la introducción del pivote.
Hay dos razones por las que los algoritmos iterativos son una parte importante del álgebra lineal numérica. En primer lugar, muchos problemas numéricos importantes no tienen una solución directa; para encontrar los valores y vectores propios de una matriz arbitraria, solo podemos adoptar un enfoque iterativo. En segundo lugar, los algoritmos no iterativos para una matriz arbitraria requieren tiempo, que es un límite sorprendentemente alto dado que las matrices solo contienen 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 necesariamente seguiría, 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 dimensión inferior , que permite aproximar las características de una matriz de dimensión superior calculando iterativamente las características equivalentes de matrices similares comenzando en un espacio de dimensión inferior y avanzando hacia dimensiones sucesivamente superiores. Cuando A es simétrico 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étrico, entonces ejemplos de soluciones iterativas al problema lineal son el método del residuo mínimo generalizado y CGN . Si A es simétrico, entonces para resolver el problema del valor propio y el vector propio podemos utilizar el algoritmo de Lanczos , y si A no es simétrico, entonces podemos utilizar la iteración de Arnoldi .
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 se basan en estas bibliotecas más fundamentales como LAPACK . [5] Se pueden encontrar más bibliotecas en la Lista de bibliotecas numéricas .
