Gram-Schmidt y descomposición QR

Álgebra · Lección 7

L3 From scratch Fase F1 Libro MML §3.5 · §3.8 Prereqs Mínimos cuadrados · Producto interno

Objetivo

Al terminar esta lección se puede:

  1. Definir una base ortonormal y demostrar que con ella la proyección de la lección 5 se calcula sin resolver ningún sistema.
  2. Derivar el proceso de Gram-Schmidt y demostrar que produce la factorización QR, con R triangular superior por construcción.
  3. Demostrar que \operatorname{span}(a_1,\dots,a_k)=\operatorname{span}(q_1,\dots,q_k) para todo k: enderezar no cambia el espacio generado.
  4. Resolver mínimos cuadrados por QR sin formar nunca A^\top A, y explicar por qué el orden de las operaciones cambia la pérdida de ortogonalidad en punto flotante.

De dónde viene

  • Álgebra 4: el producto interno y la norma; una base ortonormal es la que hace que \langle q_i,q_j\rangle valga 1 o 0 y nada más.
  • Álgebra 5: la proyección ortogonal y su residuo perpendicular. Gram-Schmidt es esa proyección aplicada una y otra vez.
  • Álgebra 6: las ecuaciones normales y la advertencia de la Proposición 6.8, \kappa(A^\top A)=\kappa(A)^2. Esta lección es la alternativa que esa advertencia anunciaba.

Para qué sirve después

  • Álgebra 8 y 11: el determinante de A sale de la diagonal de R, y la SVD retoma la idea de cambiar a una base donde todo es más simple.
  • Estadística 13 y 14: cualquier ajuste por mínimos cuadrados que se use en serio pasa por aquí; lstsq factoriza en vez de invertir.
  • Aprendizaje automático: la ortonormalización aparece en PCA, en la inicialización de redes y en todo método iterativo que necesite una base estable.

Notación

Símbolo Se lee Significado
a_1,\dots,a_p a sub uno Las columnas de A, supuestas linealmente independientes
q_1,\dots,q_p cu sub uno Las columnas de Q: la base ortonormal que se construye
Q cu Matriz n\times p de columnas ortonormales: Q^\top Q = I_p. Aquí es eso; en Estadística 8 y 11, Q es una suma de cuadrados
R erre Matriz p\times p triangular superior con diagonal positiva. Aquí es eso; en Estadística 15, R era el indicador de respuesta
r_{ik} erre i ka La entrada (i,k) de R: el coeficiente de la sombra de a_k sobre q_i
v_k ve sub ka Lo que queda de a_k tras quitarle sus sombras sobre los q_i anteriores

1. Una base donde todo es más fácil

Definición 7.1 (base ortonormal). Una familia q_1,\dots,q_p es ortonormal si \langle q_i,q_j\rangle = 0 para i\ne j y \|q_i\|=1 para todo i. En forma matricial, con Q la matriz de esas columnas: Q^\top Q = I_p.

Proposición 7.2 (la proyección, gratis). Si las columnas de Q son ortonormales y generan el mismo subespacio que las de A, entonces la matriz de proyección de la Definición 5.6 es P = QQ^\top, y los coeficientes de la proyección de b son simplemente \langle q_i,b\rangle. No hay ningún sistema que resolver ni ninguna matriz que invertir.

Demostración. Por la Proposición 5.7, P = Q(Q^\top Q)^{-1}Q^\top para cualquier matriz de columnas independientes que genere el subespacio; con columnas ortonormales Q^\top Q = I, cuya inversa es ella misma, y queda P=QQ^\top. La proyección es entonces p = QQ^\top b = \sum_{i=1}^{p} q_i\,(q_i^\top b) = \sum_i \langle q_i,b\rangle\, q_i, que es la suma de las sombras de b sobre cada dirección de la base. ∎

El trabajo de la lección 6 consistía en resolver un sistema, y con una base ortonormal se reduce a p productos internos. Lo que falta es construir esa base sin cambiar el subespacio, y eso es Gram-Schmidt.

El visual construye la base ortonormal de dos vectores paso a paso.

En el caso «casi paralelos» se ve el problema que gobierna la sección 4: lo que queda de a_2 tras quitarle su sombra es muy pequeño, y normalizar algo muy pequeño amplifica cualquier error que traiga.

2. Gram-Schmidt, y por qué R sale triangular

Proposición 7.3 (factorización QR). Sea A de n\times p con columnas linealmente independientes. Entonces existen Q de columnas ortonormales y R triangular superior con diagonal positiva tales que A=QR, y se construyen así: r_{ik} = \langle q_i, a_k\rangle \ (i<k), \qquad v_k = a_k - \sum_{i<k} r_{ik}\,q_i, \qquad r_{kk}=\|v_k\|, \qquad q_k = \frac{v_k}{r_{kk}}.

Demostración. Por inducción sobre k. Para k=1 no hay nada que quitar: r_{11}=\|a_1\|>0 porque a_1\ne0, y q_1=a_1/r_{11} tiene norma 1.

Supóngase construidos q_1,\dots,q_{k-1} ortonormales. El vector v_k = a_k-\sum_{i<k}\langle q_i,a_k\rangle q_i es ortogonal a cada q_j con j<k: \langle q_j, v_k\rangle = \langle q_j,a_k\rangle - \sum_{i<k}\langle q_i,a_k\rangle\,\underbrace{\langle q_j,q_i\rangle}_{=\,\delta_{ji}} = \langle q_j,a_k\rangle - \langle q_j,a_k\rangle = 0, donde la suma se reduce a un solo término por ortonormalidad. Además v_k\ne0: si fuera cero, a_k sería combinación de q_1,\dots,q_{k-1} y por tanto de a_1,\dots,a_{k-1}, contra la independencia de las columnas. Entonces r_{kk}=\|v_k\|>0 y q_k=v_k/r_{kk} completa la familia ortonormal.

La triangularidad no se impone: se deduce. Despejando a_k de la definición de v_k, a_k = \sum_{i<k} r_{ik}\,q_i + r_{kk}\,q_k = \sum_{i\le k} r_{ik}\,q_i, es decir, la columna k de A es combinación de las primeras k columnas de Q y de ninguna posterior. Escrito matricialmente, A=QR con r_{ik}=0 siempre que i>k: eso es exactamente ser triangular superior. ∎

Corolario 7.4 (no cambia el subespacio). Para todo k, \operatorname{span}(a_1,\dots,a_k)=\operatorname{span}(q_1,\dots,q_k). En particular \operatorname{col}(A)=\operatorname{col}(Q), de modo que la Proposición 7.2 se aplica y la proyección es la misma que la de la lección 6.

Demostración. Una inclusión es la identidad a_k=\sum_{i\le k}r_{ik}q_i de la demostración anterior: cada a_k está en el span de los primeros k vectores q_i. La otra sale de la definición de v_k: cada q_k es un múltiplo de a_k menos una combinación de q_1,\dots,q_{k-1}, que por hipótesis de inducción están en el span de a_1,\dots,a_{k-1}. Los dos spans se contienen mutuamente. ∎

3. Mínimos cuadrados por QR

Proposición 7.5 (mínimos cuadrados sin A^\top A). Con A=QR de la Proposición 7.3, la solución de mínimos cuadrados cumple R\,\hat{x} = Q^\top b, un sistema triangular que se resuelve por sustitución hacia atrás. Nunca se forma A^\top A.

Demostración. Sustituyendo A=QR en las ecuaciones normales de la Proposición 6.2 y usando Q^\top Q=I: A^\top A\hat{x} = A^\top b \;\Longleftrightarrow\; R^\top\underbrace{Q^\top Q}_{I}R\,\hat{x} = R^\top Q^\top b \;\Longleftrightarrow\; R^\top R\,\hat{x} = R^\top Q^\top b. Como R es triangular con diagonal positiva, es invertible, y también lo es R^\top; multiplicando por (R^\top)^{-1} queda R\hat{x}=Q^\top b. ∎

La ventaja no es de aritmética sino de condicionamiento: resolver con R trabaja con el condicionamiento de A, mientras que formar A^\top A lo eleva al cuadrado, que es la Proposición 6.8. Y la proyección sale de paso, por la Proposición 7.2.

Los paréntesis de Q @ (Q.T @ b) no son decorativos: así son dos productos matriz-vector, y sin ellos se construye antes la matriz QQ^\top entera, de tamaño n\times n. Con n grande esa diferencia es la que decide si el cálculo cabe en memoria.

4. Clásico contra modificado: la misma fórmula, distinto orden

Las dos versiones de Gram-Schmidt calculan lo mismo en aritmética exacta y cosas distintas en punto flotante. La clásica resta todas las sombras contra el a_k original; la modificada las resta una a una, actualizando el vector después de cada resta. La diferencia aparece cuando las columnas están casi alineadas.

La tabla mide \|Q^\top Q-I\|, es decir cuánta ortogonalidad se perdió. Los dígitos concretos no son reproducibles entre máquinas, dependen de la biblioteca de álgebra lineal y del orden de las sumas, así que lo que se afirma aquí es la propiedad, no el número: al crecer el condicionamiento, el Gram-Schmidt clásico pierde la ortogonalidad por completo, el modificado la conserva razonablemente, y el método de Householder que usa NumPy por dentro se mantiene en el error de máquina en todos los casos. La misma fórmula, ejecutada en otro orden, da resultados incomparables.

Important

Esta lección se escribe «desde cero» y no se usa desde cero por un motivo: entender Gram-Schmidt es imprescindible para saber qué hace np.linalg.qr, y precisamente por eso conviene llamar a np.linalg.qr en vez de escribirlo uno mismo.

Ejercicios

Ejercicio 1, Gram-Schmidt modificado

Impleméntalo. Devuelve solo Q.

Dentro del bucle, en este orden: normaliza V[:, j] para obtener Q[:, j], y después réstale a cada columna posterior V[:, k] su sombra (Q[:, j] @ V[:, k]) * Q[:, j]. La clave del modificado es que restas sobre V, que ya viene actualizado, no sobre A.

Ejercicio 2, Mínimos cuadrados sin ecuaciones normales

Resuelve \min\|b - Ax\| usando QR. Nada de AᵀA, nada de lstsq.

Las ecuaciones normales colapsan a R\hat{x} = Q^\top b. Eso es un sistema triangular: np.linalg.solve(R, Q.T @ b).

Contraste con la librería

Esta lección es de nivel L3: promete implementar el resultado en NumPy puro y empatar con la librería. La celda siguiente enfrenta el Gram-Schmidt escrito arriba contra np.linalg.qr, y el primer intento no empata.

La primera comparación da una diferencia máxima de 0{,}869, que parecería un error de implementación. No lo es: la factorización QR no es única. Si Q y R la cumplen, también la cumplen QS y SR para cualquier matriz diagonal S de signos \pm1, porque (QS)(SR) = QS^2R = QR. Las dos salidas son correctas y describen la misma factorización.

La unicidad se recupera imponiendo una convención, y la natural es diagonal de R positiva. Gram-Schmidt la cumple por construcción, porque su R_{jj} es la norma del residuo y una norma no es negativa; la implementación por reflexiones de Householder que usa la librería no la impone. Fijado el signo, las dos coinciden a 10^{-15}.

Conviene retener la lección general, porque reaparece con la SVD y con los eigenvectores: cuando una descomposición está definida salvo signo o salvo orden, comparar dos implementaciones entrada a entrada no dice nada hasta haber fijado la convención. Lo que se compara no es la salida sino lo que la salida afirma.

Reto

En proyectos/notebooks/F1-retos.ipynb, sección Mat 7:

  1. Implementar las dos versiones de Gram-Schmidt, clásica y modificada, y reproducir la tabla de la sección 4 sobre matrices de Vandermonde de tamaño creciente. Graficar \|Q^\top Q-I\| contra el condicionamiento en escala logarítmica, y comprobar que la pendiente del clásico duplica a la del modificado.
  2. Escribir sustitucion_atras(R, y) que resuelva Rx=y con R triangular superior, sin np.linalg.solve, y con ella completar un ols(A, b) que factorice con np.linalg.qr y nunca forme A^\top A. Contrastarlo con lstsq en doscientos casos.
  3. Ajustar un polinomio de grado 15 a cuarenta puntos por dos caminos, ecuaciones normales y QR, y dibujar las dos curvas sobre los datos. Una de las dos se va a ver mal; explicar cuál y por qué con la Proposición 6.8 y con la tabla de la sección 4.

Del libro

Mathematics for Machine Learning define las bases ortonormales en §3.5 Orthonormal Basis y las proyecciones en §3.8 Orthogonal Projections, que es donde aparece la simplificación de la Proposición 7.2. El libro tiene copyright y no es descargable desde el entorno en que se escribió esta página, así que se cita número y título y no se le atribuye ninguna frase.

Preguntas para leer §3.5 y §3.8 con lápiz:

  1. ¿Qué forma toma la matriz de proyección cuando la base es ortonormal, según el libro, y coincide con la Proposición 7.2?
  2. MML construye bases ortonormales sin llamarlo QR. ¿Qué parte del proceso corresponde a R, y por qué el libro puede permitirse no nombrarla?
  3. La Proposición 7.3 exige columnas independientes. ¿Qué pasaría en el paso k si no lo fueran, y cómo se relaciona eso con el rango de la lección 3?

Para el Cerebro

Nota nueva en 10-Conceptos/qr.md, enlazada a [[proyeccion-ortogonal]], [[minimos-cuadrados]] y [[base-y-coordenadas]]. La Proposición 7.3 conviene hacerla a mano en \mathbb{R}^3 con tres vectores concretos: se ve de inmediato por qué R sale triangular y no por decreto.

¿Qué es una base ortonormal?::Vectores perpendiculares entre sí y de norma 1: QᵀQ = I
¿Cuánto vale la matriz de proyección con base ortonormal?::P = QQᵀ, sin invertir nada (Proposición 7.2)
¿Cuáles son los coeficientes de la proyección en esa base?::Los productos internos ⟨qᵢ, b⟩, uno por dirección
¿Qué hace Gram-Schmidt?::Quitarle a cada columna sus sombras sobre las anteriores y normalizar lo que queda
¿Por qué R sale triangular superior?::Porque aₖ solo usa q₁…qₖ y ninguna posterior: rᵢₖ = 0 para i > k
¿Qué garantiza el Corolario 7.4?::Que el span no cambia: col(A) = col(Q), así que la proyección es la misma
¿Cómo se resuelve mínimos cuadrados por QR?::Rx̂ = Qᵀb, un sistema triangular; nunca se forma AᵀA
¿Por qué QR es más estable que las ecuaciones normales?::Porque trabaja con κ(A) y no con κ(A)² (Proposición 6.8)
¿En qué se diferencian el Gram-Schmidt clásico y el modificado?::En el orden de las restas; en aritmética exacta dan lo mismo, en punto flotante no
¿Qué usa np.linalg.qr por dentro?::Reflexiones de Householder, más estables que cualquiera de las dos versiones de Gram-Schmidt

Fuentes

Lo que esta página demuestra sola. Las Proposiciones 7.2, 7.3 y 7.5 y el Corolario 7.4 se demuestran aquí, a partir del producto interno de la lección 4 y de la proyección de la lección 5. Se comprueban además numéricamente: Q^\top Q=I, A=QR y la triangularidad sobre una matriz de 40\times4; que la solución por QR coincide con lstsq; que QQ^\top es la misma matriz de proyección que la de la lección 6, con el residuo perpendicular y Pitágoras; y la pérdida de ortogonalidad de las dos versiones de Gram-Schmidt contra Householder.

Lo que se usa de otras lecciones sin repetir. El producto interno y la norma son la lección 4; la proyección y sus ecuaciones normales, las lecciones 5 y 6; la independencia de las columnas y el rango, la lección 3.

Lo que se enuncia sin demostrar. Que las reflexiones de Householder son numéricamente más estables que Gram-Schmidt: se observa en la tabla de la sección 4, no se demuestra. Y la Proposición 6.8 sobre el condicionamiento, que ya venía declarada como no demostrada en la lección 6.

Sobre los dígitos de la sección 4. Por la regla 7 de CLAUDE.md, los números de esa tabla no se citan en la prosa: salen de cálculos numéricamente inestables y dependen de la máquina y de la biblioteca de álgebra lineal. Lo que se afirma, y lo que verificar/afirmaciones.json comprueba, es la propiedad: que el clásico pierde la ortogonalidad mucho antes que el modificado, y que Householder se mantiene en el error de máquina.

Lo que viene de los libros.

  • Mathematics for Machine Learning (Deisenroth, Faisal & Ong, Cambridge University Press, 2020), §3.5 Orthonormal Basis y §3.8 Orthogonal Projections — citadas por número y título, sin transcribir texto.

Lo que es mío, no del libro. La demostración de la Proposición 7.3 por inducción con la triangularidad deducida en vez de impuesta, el Corolario 7.4 enunciado aparte porque es lo que justifica usar Q en lugar de A, y la lectura de la sección 4 como una advertencia sobre el orden de las operaciones más que sobre el algoritmo.

Índices verificados el 12-09-2026 contra el índice publicado del PDF oficial.

→ Siguiente: El determinante