¿Cómo MATLAB, por ejemplo, calcula la SVD de una matriz dada? Supongo que la respuesta probablemente implica calcular los vectores propios y los valores propios de A*A'. Si ese es el caso, también me gustaría saber cómo los calcula.
linear-algebra
matrix
olamundo
fuente
fuente
Respuestas:
Ver
GH Golub y C. Reinsch. Descomposición de valor singular y soluciones de mínimos cuadrados. Numerische Mathematik 14: 403-420, 1970.
Este material se discute en muchos libros de texto sobre álgebra lineal numérica.
fuente
Además del papel (ahora clásico) de Golub-Reinsch que Brian señala en su respuesta (me he vinculado a la versión del Manual del documento), así como el papel predecesor (también ahora clásico) de Golub-Kahan , ha habido un número de desarrollos importantes en el cálculo de la SVD desde entonces. Primero, tengo que resumir cómo funciona el método habitual.
La idea de calcular la SVD de una matriz es cualitativamente similar al método utilizado para calcular la descomposición propia de una matriz simétrica (y, como se observa en el OP, existe una relación íntima entre ellas). En particular, se procede en dos etapas: la transformación a una matriz bidiagonal , y luego encontrar la SVD de una matriz bidiagonal. Esto es completamente análogo al procedimiento de reducir primero una matriz simétrica a una forma tridiagonal, y luego calcular la descomposición propia del tridiagonal resultante.
Para calcular la SVD de una matriz bidiagonal, un avance particularmente interesante fue el artículo de Jim Demmel y Velvel Kahan , que demostró que uno puede calcular incluso los pequeños valores singulares de una matriz bidiagonal con buena precisión, modificando adecuadamente el método inicialmente propuesto en Golub-Reinsch. Esto fue seguido por la (re?) Descubrimiento de la DQD algoritmo , que es un descendiente de la antigua algoritmo cociente de diferencias de Rutishauser. (Beresford Parlett da una buena discusión aquí.) Si la memoria sirve, este es el método preferido utilizado internamente por LAPACK. Aparte de esto, siempre ha sido posible derivar versiones SVD de desarrollos en la solución de problemas propios simétricos; Por ejemplo, hay una versión SVD de divide y vencerás, así como una versión SVD del antiguo algoritmo de Jacobi (que puede ser más preciso en algunas circunstancias).
En cuanto a la bidiagonalización, se describió un método mejorado en el artículo de Barlow , que requiere un poco más de trabajo que el procedimiento original de Golub y Reincsh, pero produce matrices bidiagonales más precisas.
fuente