Ortogonalización de Gram-Schmidt

Elige cuánto se acercan las columnas y lee ambas cuadrículas: muestran el ángulo entre cada par de vectores que devuelven las dos versiones.

Ejemplo resuelto — Ortogonalización de Gram-Schmidt

Número de condición de A	1,7321 × 10⁸
Lo que queda de la columna 3	1,4142 × 10⁻⁸
Lo que q₂ extrae de la columna 3	0
Mayor producto escalar entre dos de ellos	0,5000
Ángulo entre q₂ y q₃	60,00°
Pérdida de ortogonalidad, clásico	0,7071
Pérdida de ortogonalidad, modificado	1,1547 × 10⁻⁸
Precisión con la que QR reproduce A	0

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Gram-Schmidt clásico devuelve dos vectores separados por 60° 🖖

Pulsa ε = 10⁻⁸, clásico. En la cuadrícula clásica, dos celdas marcan 60,00°, el par q₂ y q₃ en ambas esquinas, y cualquier otro ángulo en ambas cuadrículas indica 90,00°. El producto escalar que hay detrás de ellas es 0,5000: un medio, con un margen de error de una unidad en la última posición de un valor de doble precisión.

La matriz consta de tres columnas, cada una de ellas el vector (1, 0, 0, 0) con un único 10⁻⁸ insertado en una posición diferente. Peter Läuchli la utilizó en 1961 y lleva su nombre desde entonces. Las columnas que casi se repiten suponen el caso problemático para cualquier ajuste por mínimos cuadrados. Aparecen siempre que dos de tus mediciones son casi idénticas.

Gram-Schmidt modificado recibe las mismas tres columnas y cada ángulo que devuelve es de 90,00°, realizando exactamente el mismo número de multiplicaciones.

Retrocede la separación una marca, a 10⁻⁷, y esa celda marcará 89,24°. Un solo clic del deslizador marca la diferencia entre equivocarse por tres cuartos de grado y equivocarse por treinta.

Las dos versiones leen un número de forma distinta 🖖

Ajusta el recorrido a la columna 3 y pulsa Clásico, luego Modificado. La fila Lo que q₂ extrae de la columna 3 pasa de 0 a 7,0711 × 10⁻⁹. Con tres columnas, ese es el único coeficiente que los dos algoritmos calculan de forma distinta. La entrada diagonal que está justo debajo, y cada ángulo de la cuadrícula, se derivan de él.

El método clásico evalúa ese coeficiente como q₂ᵀa₃, frente a la columna que recibió. El modificado evalúa q₂ᵀv, frente a lo que queda de la columna una vez restada la parte de q₁. Sobre el papel ambas cifras son idénticas, ya que v solo difiere de a₃ en un múltiplo de q₁ y q₂ es perpendicular a q₁. En aritmética finita q₂ no es del todo perpendicular a q₁, y a₃ aún mantiene un 7,0711 × 10⁻⁹ de sí misma apuntando en la dirección de q₂. El método clásico jamás mira ahí, así que q₃ se lo queda. De ahí salen los 60°.

Arrastra el deslizador desde 10⁻¹ hasta 10⁻⁸ y observa cómo se separan las dos curvas en el panel inferior. Tras ajustar el modelo sobre 113 puntos a lo largo de ese intervalo, la pérdida de ortogonalidad del método clásico crece como κ^1,98 en estas tres columnas, mientras que la del modificado lo hace como κ^0,98. El panel recalcula el ajuste sin importar la cantidad de columnas que elijas, de modo que esos dos exponentes varían conforme ensanchas la matriz. Alterar el orden de una sola resta vale por toda una potencia del número de condición.

La base está arruinada y la factorización es exacta 🖖

La última fila de la tabla de resultados es ‖A − QR‖ / ‖A‖. Para ε = 10⁻⁸, el método Clásico marca 0. Multiplica esa Q estropeada por la R que apareció a su lado y regresará la matriz original, término a término, sin que sobre nada.

Al barrer todos los estados a los que llegan los controles (cuatro cantidades de columnas, diez separaciones y ambos algoritmos), ese residuo relativo nunca supera los 5,5511 × 10⁻¹⁷. La distancia entre 1 y el siguiente double es de 2,2204 × 10⁻¹⁶, así que el residuo se mantiene en un cuarto de unidad de la última posición.

El proceso de Gram-Schmidt sí escribió A como el producto de los vectores que devolvió y los coeficientes que registró. Lo que dejó de hacer fue entregar vectores en ángulo recto entre sí. Cuál de las dos propiedades necesitas es una cuestión que atañe a tu propio código: proyectar un vector mediante Qᵀb se apoya en la que falló, mientras que reconstruir A a partir de Q y R depende de la que resistió.

Problema resuelto al detalle

Dónde el Gram-Schmidt clásico pierde su ángulo recto 8 pasos
La herramienta muestra tres columnas separadas por 10⁻⁸ y la respuesta del Gram-Schmidt clásico para ellas. Resuelve el algoritmo a mano, encuentra el redondeo concreto que le cuesta treinta grados y luego indica hasta dónde se puede forzar cada versión antes de que deje de valer la pena ejecutarla.

Abre este problema en la herramienta
1. Cada columna es el vector (1, 0, 0, 0) con un ε insertado en una posición distinta. AᵀA es la matriz de 3 × 3 llena de unos más ε²I, cuyos valores propios son 3 + ε² una vez y ε² dos veces. Por tanto, los valores singulares son √(3 + ε²) y ε, y el número de condición es exacto en lugar de estimado. La fila superior de la tabla marca 1,7321 × 10⁸.
  
  $A = 1 ε 00 10 ε 0 100 ε, ε = 1 0^{- 8}, κ (A) = \frac{3 + ε ^{2}}{ε} = 1.7321 \times 1 0^{8}$
2. ‖a₁‖² es 1 + ε², y ε² es 10⁻¹⁶. Un valor de doble precisión puede almacenar un 1, y el siguiente número que puede retener está 2,2204 × 10⁻¹⁶ más allá, de modo que cualquier cantidad por debajo de la mitad de esa distancia, 1,1102 × 10⁻¹⁶, desaparece cuando se suma a 1. Diez a la menos dieciséis queda por debajo. La raíz cuadrada es 1, dividir entre ella no cambia nada y q₁ sale como la columna misma con el ε² borrado del registro. Cualquier otro redondeo en este problema vale una unidad en la última posición. Este en particular cuesta treinta grados.
  
  $∥ a_{1} ∥^{2} = 1 + ε^{2} = 1 + 1 0^{- 16}, 1 0^{- 16} < 1.1102 \times 1 0^{- 16} ⟹ fl (1 + ε^{2}) = 1, q_{1} = a_{1}$
3. Sigue la columna 2. Aquí ambas versiones coinciden porque solo tienen un vector detrás. El coeficiente de proyección es q₁ᵀa₂ = 1. Al restarlo queda (0, −ε, ε, 0), que tiene una longitud de ε√2 = 1,4142 × 10⁻⁸. La columna 2 llegó con longitud 1 hasta donde un valor doble puede distinguir, y todo menos 1,4142 × 10⁻⁸ de ella ya estaba cubierto por q₁.
  
  $r_{12} = q_{1}^{T} a_{2} = 1, v_{2} = a_{2} - q_{1} = (0, - ε, ε, 0)^{T}, ∥ v_{2} ∥ = ε 2 = 1.4142 \times 1 0^{- 8}$
4. Pasamos a la columna 3, en el método clásico. El coeficiente frente a q₁ vuelve a ser 1. El coeficiente frente a q₂ es q₂ᵀa₃. Como q₂ reside por completo en las posiciones 2 y 3, mientras que a₃ mantiene su ε en la posición 4, ese producto escalar es 0. Eso es precisamente lo que indica la fila Lo que q₂ extrae de la columna 3. Al restar solo q₁ queda (0, −ε, 0, ε), de nuevo con longitud ε√2, por lo que Lo que queda de la columna 3 también marca 1,4142 × 10⁻⁸.
  
  $r_{13} = q_{1}^{T} a_{3} = 1, r_{23} = q_{2}^{T} a_{3} = 0, v_{3} = a_{3} - q_{1} = (0, - ε, 0, ε)^{T}, q_{3} = \frac{1}{2} (0, - 1, 0, 1)^{T}$
5. Tanto q₂ como q₃ se construyeron restando q₁ a una columna que comparte su 1 inicial, por lo que ambas llevan −1/√2 en la posición 2 y no tienen nada más en común. Su producto escalar es un medio. La herramienta imprime 0,5000 y 60,00°, y el valor que almacena internamente es 0,4999999999999999, a una unidad en la última posición del medio exacto que dicta el álgebra. Esto sucede porque ±1/√2 no es una fracción binaria, y representa el tamaño de error del que es capaz esta aritmética. Los treinta grados no vienen de ahí. La fila de pérdida del clásico marca 0,7071, que equivale a √(2 × 0,5²): el mismo medio contado una vez en cada esquina de QᵀQ.
  
  $q_{2}^{T} q_{3} = \frac{1}{2} [(- 1) (- 1) + (1) (0)] = \frac{1}{2}, arccos \frac{1}{2} = 6 0^{\circ}, 2 \cdot 0 . 5^{2} = 0.7071$
6. Veamos el método modificado, sobre la misma columna. Una vez que se resta la parte de q₁, el resto es (0, −ε, 0, ε), y esta versión mide frente a este resto en lugar de frente a a₃. Al hacer el producto escalar con q₂ da ε/√2 = 7,0711 × 10⁻⁹, y no cero. Si restas eso, lo que queda es (0, −ε/2, −ε/2, ε), de longitud ε√(3/2) = 1,2247 × 10⁻⁸, por lo que q₂ᵀq₃ sale a 1,1102 × 10⁻¹⁶ en vez de a un medio. La fila de pérdida del modificado marca 1,1547 × 10⁻⁸, y lo único que queda en ella es lo que q₁ no pudo quitar: la resta deja un −ε² a lo largo de q₁, y al dividir por un resto de longitud de solo ε√2, eso se vuelve a convertir en ε/√2.
  
  $r_{23} = q_{2}^{T} v_{3} = \frac{ε}{2} = 7.0711 \times 1 0^{- 9}, v_{3} \mapsto (0, - \frac{ε}{2}, - \frac{ε}{2}, ε)^{T}, ∥ v_{3} ∥ = ε \frac{3}{2} = 1.2247 \times 1 0^{- 8}, q_{2}^{T} q_{3} = 0$
7. El mismo razonamiento se aplica a cualquier cantidad de columnas que ofrezca la herramienta. El método clásico construye cada q posterior restando q₁ a una columna que comparte su 1 inicial, por lo que cada par entre ellos sale a 60°: (n − 1)(n − 2)/2 pares, y una pérdida de ortogonalidad igual a la raíz cuadrada de la mitad de ese recuento. Con dos columnas no existen tales pares, y lo que queda es la inclinación de tamaño ε que comparten ambas versiones.
  
  $n 2345 κ (A) 1.4142 \times 1 0^{8} 1.7321 \times 1 0^{8} 2.0000 \times 1 0^{8} 2.2361 \times 1 0^{8} # {6 0^{\circ}} 0136 ∥ Q_{C}^{T} Q_{C} - I ∥_{F} 1.0000 \times 1 0^{- 8} 0.7071 1.2247 1.7321 ∥ Q_{M}^{T} Q_{M} - I ∥_{F} 1.0000 \times 1 0^{- 8} 1.1547 \times 1 0^{- 8} 1.2247 \times 1 0^{- 8} 1.2649 \times 1 0^{- 8}$
8. La línea ajustada del método clásico alcanza una pérdida de 1 en κ = 2,35 × 10⁸. Por este motivo, la curva clásica ya es plana en el extremo derecho del panel. El método modificado obtiene un límite medido en lugar de uno extrapolado. Su propia curva se estabiliza más allá de 10⁻⁸, y una línea ajustada que se prolongara hasta ese punto quedaría refutada por el panel que tiene debajo: a lo largo de los 724 puntos del barrido, su pérdida nunca superó 1,25 veces el épsilon de máquina por κ. Ese límite solo llega a 1 en κ = 3,60 × 10¹⁵. El inverso del épsilon de máquina es 4,50 × 10¹⁵.
  
  $lo g_{10} κ = \frac{16 . 5755}{1 . 9801} 1.25 \cdot (2.2204 \times 1 0^{- 16}) κ (2.2204 \times 1 0^{- 16})^{- 1} = = = 8.3710 ⟹ κ = 2.35 \times 1 0^{8} 1 ⟹ κ = 3.60 \times 1 0^{15} 4.50 \times 1 0^{15}$
Respuesta

Los treinta grados surgen de una sola línea. El clásico lee q₂ᵀa₃ = 0 donde el modificado lee q₂ᵀv₃ = 7,0711 × 10⁻⁹, y sobre el papel esos son el mismo número.

La separación de 10⁻⁸ es la primera marca en la que ε² desaparece de 1 + ε², ya que √(la mitad del épsilon de máquina) es 1,0537 × 10⁻⁸. De ahí hacia abajo, la celda marca 60,00° por mucho más que arrastres; una marca hacia atrás, en 10⁻⁷, marca 89,24° y el clásico ya ha perdido 1,88 × 10⁻² de ortogonalidad. El colapso comienza mucho antes de que el deslizador alcance la marca que lo hace evidente.

Åke Björck publicó el análisis de la versión modificada en 1967, y esa reordenación ha sido la opción predeterminada desde entonces. Los dos algoritmos ejecutan el mismo número de multiplicaciones. Con esta separación, la pérdida de ortogonalidad entre ellos difiere por un factor de 6,1 × 10⁷. El modificado conserva sus ángulos rectos hasta casi el punto donde un valor doble deja por completo de poder distinguir las columnas; el clásico los abandona siete órdenes de magnitud antes.

$q_{2}^{T} a_{3} = 0 \neq = q_{2}^{T} v_{3} = \frac{ε}{2} = 7.0711 \times 1 0^{- 9}$

Referencias (5)

The matrix the tool is built on, and the name it carries: P. Läuchli, "Jordan-Elimination und Ausgleichung nach kleinsten Quadraten", Numerische Mathematik 3(1), 226–240, 1961. doi:10.1007/BF01386022
The analysis of the modified variant that made it the default: Åke Björck, "Solving linear least squares problems by Gram-Schmidt orthogonalization", BIT 7(1), 1–21, 1967. doi:10.1007/BF01934122
The corresponding rounding-error analysis of the classical variant: Luc Giraud, Julien Langou, Miroslav Rozložník and Jasper van den Eshof, "Rounding error analysis of the classical Gram-Schmidt orthogonalization process", Numerische Mathematik 101(1), 87–100, 2005. doi:10.1007/s00211-005-0615-4
Gram's paper of 1883, where the process is set out for least squares: J. P. Gram, "Ueber die Entwickelung reeller Functionen in Reihen mittelst der Methode der kleinsten Quadrate", Journal für die reine und angewandte Mathematik 1883(94), 41–73. doi:10.1515/crll.1883.94.41
And Schmidt's of 1907, where the form used today appears: Erhard Schmidt, "Zur Theorie der linearen und nichtlinearen Integralgleichungen", Mathematische Annalen 63, 433–476, 1907. doi:10.1007/BF01449770

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.