¿Cómo funciona el Gram Schmidt modificado? Quiero utilizarlo, pero estoy confundido por las notaciones y no pude encontrar ningún ejemplo en línea.
Respuesta
¿Demasiados anuncios?
En primer lugar, establezcamos la Gram Schmidt (a veces llamada GS Clásica) para que quede claro.
Utilizamos GS porque deseamos resolver el sistema $A \overrightarrow{x} = \overrightarrow{b}$ . Queremos calcular $\overrightarrow{x}$ s.t. $||\overrightarrow{r}||_2$ se minimiza cuando $\overrightarrow{r} = A\overrightarrow{x} - \overrightarrow{b}$ .
Una forma es GS, donde definimos $A =QR$ s.t. $Q^TQ=I$ donde $I$ es la matriz identidad de tamaño n x n y $R$ es una matriz triangular superior derecha de tamaño n x n.
Nuestro objetivo es encontrar $$\{ \overrightarrow{q}_1 , \overrightarrow{q}_2 , \cdots, \overrightarrow{q}_n \}$$ s.t. $$span \{ \overrightarrow{q}_1 , \overrightarrow{q}_2 , \cdots, \overrightarrow{q}_n \} = span \{\overrightarrow{a}_1 , \overrightarrow{a}_2 , \cdots, \overrightarrow{a}_n \}$$
Además, definamos el producto punto como, $$<a,b>$$
Entonces queremos
$$<\overrightarrow{q}_i , \overrightarrow{q}_j > \quad = 0 \quad if \quad i \not=j$$
$$<\overrightarrow{q}_i , \overrightarrow{q}_j > \quad = 1 \quad if \quad i = j$$
Supongamos que $\{ \overrightarrow{q}_1 , \overrightarrow{q}_2 , \cdots, \overrightarrow{q}_r \}$ ya se han encontrado, entonces podemos encontrar $\overrightarrow{q}_{r+1}$ mediante
$$\overrightarrow{q}_{r+1} = \overrightarrow{a}_{r+1} - <\overrightarrow{a}_{r+1},\overrightarrow{q}_1>\overrightarrow{q}_1 - <\overrightarrow{a}_{r+1},\overrightarrow{q}_2>\overrightarrow{q}_2 - \cdots - <\overrightarrow{a}_{r+1},\overrightarrow{q}_r>\overrightarrow{q}_r$$
En otras palabras, lo anterior es nuestro caso genérico sobre cómo resolver para $\overrightarrow{q}_i$ .
Veamos un ejemplo:
$$ \overrightarrow{a}_1 = \begin{pmatrix} 1 \\ 2 \\ 2 \end{pmatrix}$$
$$ \overrightarrow{a}_2 = \begin{pmatrix} -1 \\ 0 \\ 2 \end{pmatrix}$$
$$ \overrightarrow{a}_3 = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}$$
Es importante señalar que este proceso sólo funciona si nuestras columnas son linealmente independientes. Puedes comprobarlo tomando el determinante de nuestra matriz A. Si es $\not= 0$ es linealmente independiente.
$$det \begin{pmatrix} 1 & -1 & 0 \\ 2 & 0 & 0 \\ 2 & 2 & 1 \end{pmatrix} = 3$$
Estamos bien, así que continuemos.
$$r_{11} = ||\overrightarrow{a}_1 ||_2 = (1^2 + 2^2 +2^2)^{\frac{1}{2}} = 3$$
$$\overrightarrow{q}_1 = \frac{\overrightarrow{a}_1}{r_{11}} = \frac{1}{2} \begin{pmatrix} 1 \\ 2\\ 2 \end{pmatrix}$$
$$\overrightarrow{q}_2 = \overrightarrow{a}_2 - <\overrightarrow{a}_2, \overrightarrow{q}_1> \overrightarrow{q}_1$$
$$\overrightarrow{q}_2 = \begin{pmatrix} -1 \\ 0 \\ 2 \end{pmatrix} - \left(\frac{-1}{3} + (2) \left( \frac{2}{3} \right) \right) \frac{1}{3} \begin{pmatrix} 1 \\ 2 \\ 2 \end{pmatrix}$$
$$\overrightarrow{q}_2 = \begin{pmatrix} \frac{-4}{3} \\ \frac{-2}{3} \\ \frac{4}{3} \end{pmatrix}$$
Ahora $\overrightarrow{q}_2$ debe normalizarse.
$$\overrightarrow{q}_2 = \frac{\overrightarrow{q}_2}{||\overrightarrow{q}_2||_2} = \begin{pmatrix} \frac{-2}{3} \\ \frac{-1/3} \\ \frac{2}{3} \end{pmatrix}$$
Nuestro lado izquierdo $\overrightarrow{q}_2$ es nuestro nuevo $\overrightarrow{q}_2$ valor.
Ahora tenemos que resolver para $\overrightarrow{q}_3$ .
$$\overrightarrow{q}_3 = \overrightarrow{a}_3 - < \overrightarrow{a}_3 , \overrightarrow{q}_1 > \overrightarrow{q}_1 - <\overrightarrow{a}_3 , \overrightarrow{q}_2> \overrightarrow{q}_2$$
$$\overrightarrow{q}_3 = \begin{pmatrix} 0 \\ 0\\ 1 \end{pmatrix} - \frac{2}{3} \begin{pmatrix} \frac{1}{3} \\ \frac{2}{3} \\ \frac{2}{3} \end{pmatrix} - \begin{pmatrix} \frac{-2}{3} \\ \frac{-1}{3} \\ \frac{2}{3} \end{pmatrix} $$
$$\overrightarrow{q}_3 = \begin{pmatrix} \frac{2}{9} \\ \frac{-2}{9} \\ \frac{1}{9} \end{pmatrix}$$
Una vez más, hay que normalizarlo. $\overrightarrow{q}_3$ se convierte en
$$\overrightarrow{q}_3 = \frac{\overrightarrow{q}_3}{||\overrightarrow{q}_3||_2} = \begin{pmatrix} \frac{2}{3} \\ \frac{-2}{3} \\ \frac{1}{3} \end{pmatrix}$$
Ahora $r_{ij} = < \overrightarrow{a}_j , \overrightarrow{q}_i>$ cuando $i \not=j$ y $r_{ii} = || \overrightarrow{a}||_2$
Con este conocimiento encontramos $r_{12} = 1$ , $r_{22} = 2$ , $r_{13} = \frac{2}{3}$ , $r_{23} = \frac{2}{3}$ y $r_{33} = \frac{1}{3}$
Ahora tenemos todas las piezas y partes.
$$ Q = \begin{pmatrix} = \frac{1}{3} & \frac{-2}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{-1}{3} & \frac{-2}{3} \\ \frac{2}{3} & \frac{2}{3} & \frac{1}{3} \end{pmatrix}$$
y
$$ R = \begin{pmatrix} = 3 & 1 & \frac{2}{3} \\ 0 & 2 & \frac{2}{3} \\ 0 & 0 & \frac{1}{3} \end{pmatrix}$$
Recuerda que queríamos $A = QR$ por lo que ahora tenemos
$$ A = \begin{pmatrix} = \frac{1}{3} & \frac{-2}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{-1}{3} & \frac{-2}{3} \\ \frac{2}{3} & \frac{2}{3} & \frac{1}{3} \end{pmatrix} \begin{pmatrix} = 3 & 1 & \frac{2}{3} \\ 0 & 2 & \frac{2}{3} \\ 0 & 0 & \frac{1}{3} \end{pmatrix}$$
No obstante, conviene comprobar si $QR$ en realidad es igual a $A$ (el nuestro sí). En este punto se puede utilizar la factorización QR para resolver.
Sin embargo, ese no es el objetivo de esta solución.
Versión modificada de Gram Schmidt:
En la GS clásica resolvemos para $\overrightarrow{q}_j$ directamente. En la GS modificada damos múltiples pasos para llegar a $\overrightarrow{q}_j$ . Esto se ocupa de errores como los de coma flotante al resolver por ordenador $$\overrightarrow{q}_j^0 = \overrightarrow{a}_j$$
$$\overrightarrow{q}_j^1 = \overrightarrow{q}_j^0 - <\overrightarrow{q}_j^0 , \overrightarrow{q}_1> \overrightarrow{q}_1$$
$$\overrightarrow{q}_j^2 = \overrightarrow{q}_j^1 - <\overrightarrow{q}_j^1 , \overrightarrow{q}_2> \overrightarrow{q}_2$$
$$ \cdots$$
$$\overrightarrow{q}_j^{j-1} = \overrightarrow{q}_j^{j-2} - <\overrightarrow{q}_j^{j-2} , \overrightarrow{q}_{j-1}> \overrightarrow{q}_{j-1}$$
Y como en el caso de la GS clásica, hay que normalizarla para obtener un resultado final de
$$\overrightarrow{q}_j = \frac{\overrightarrow{q}_j^{j-1}}{||\overrightarrow{q}_j^{j-1}||_2}$$
La clave de la GS Modificada es cada $\overrightarrow{q}_i$ debe resolverse de esta manera. Los valores de $r_{ij}$ y $\overrightarrow{q}_i$ (nota esto es $\overrightarrow{q}$ sin superíndice) se siguen resolviendo igual que en la GS clásica. Una vez más, hay que resolver $Q$ y $R$ y luego resolver por Factorización QR.
