Quiero encontrar la solución por mínimos cuadrados de $\boldsymbol{Ax}=\boldsymbol{b}$ donde $\boldsymbol{A}$ es una matriz cuadrada muy dispersa.
He encontrado dos métodos que parecen llevarme a una solución: Factorización QR y descomposición del valor singular . Por desgracia, aún no he cursado álgebra lineal, así que no puedo entender la mayor parte de lo que dicen esas páginas. Sin embargo, puedo calcular ambos en Matlab, y parece que el SVD me dio un error cuadrático menor. ¿Por qué ocurre eso? ¿Cómo puedo saber cuál debería usar en el futuro?
Respuesta
¿Demasiados anuncios?Todo depende del número de condición de 2-normas de su matriz (la relación entre el valor singular más grande y el más pequeño); como una buena regla general, si el logaritmo de base 10 del recíproco del número de condición es mucho menor que el número de dígitos que su ordenador utiliza para almacenar los números, QR (y tal vez incluso las ecuaciones normales) podría ser suficiente. De lo contrario, SVD es una "apuesta más segura": siempre funciona, pero es mucho más lento que los otros métodos para resolver problemas de mínimos cuadrados.
Unas buenas referencias serían el clásico "Solving Least Squares Problems" de Lawson y Hanson, y el más reciente "Numerical Methods for Least Squares Problems" de Björck.
Para añadir a la respuesta que di anteriormente, una forma de proceder para una matriz A cuyo condicionamiento desconoces sería la siguiente:
- Calcula la descomposición QR de A.
- Estimar el número de condición de R.
- Si R está bien condicionado (el número de condición es "suficientemente pequeño"), deténgase; si no
- Calcula la descomposición del valor singular de R=U∑V T
- Multiplica Q y U para obtener el SVD de A.
La ventaja de proceder de esta manera es que si su matriz está lo suficientemente mal condicionada como para necesitar el uso de la SVD, el algoritmo para calcular la SVD tiene que manejar sólo una matriz triangular en lugar de la matriz original (que puede tener más filas que columnas como es habitual en las aplicaciones de mínimos cuadrados).