Contenidos

Tema anterior

Clase 12: Proyectores

Próximo tema

Clase 14: Triangularización de Householder

Esta página

Clase 13: Ortogonalización de Gram-Schmidt

Bibliografía de la Clase:

  • Numerical Linear Algebra.L.N. Trefethen. Chapter 2: Lecture 8 Gram-Schmidt

Proyecciones de Gram-Schmidt

La factorización QR nos permite descomponer A como:

\left[ \begin{array}{c|c|c|c}
    \, & \, & \, & \, \\
    \, & \, & \, & \, \\
    a_1 & a_2 & \cdots & a_n \\
    \, & \, & \, & \, \\
    \, & \, & \, & \,
 \end{array} \right]=
 \left[ \begin{array}{c|c|c|c}
 \, & \, & \, & \, \\
 \, & \, & \, & \, \\
 q_1 & q_2 & \cdots & q_n \\
 \, & \, & \, & \, \\
 \, & \, & \, & \,
 \end{array} \right]
 \begin{bmatrix}
 r_{11} & r_{12} & \ldots & r_{1n} \\
 \, & r_{22} & \, & \, \\
 \, & \, & \ddots & \, \\
 \, & \, & \, & r_{nn}
 \end{bmatrix}

Análogamente, podemos ver que cada columna de A puede expresarse como combinación lineal de las columnas de Q de la siguiente manera:

a_{1}&=r_{11}q_{1}\\
a_{2}&=r_{12}q_{1}+r_{22}q_{2}\\
\vdots \\
a_{n}&=r_{1n}q_{1} + r_{2n}q_{2}+ \ldots + r_{nn}q_{n}

El algoritmo clásico que permite encontrar esta descomposición es el siguiente:

caption

en el cual, en cada iteración se realiza la siguiente operación sobre los vectores v_i:

v_1 &= a_1 \\
v_2 &= a_2 - (q_1^* a_2)q_1 \\
v_3 &= a_3 - (q_1^* a_3)q_1 - (q_2^* a_3)q_2 \\
\vdots \\
v_{j} &= a_{j} - (q_1^* a_j)q_1 - (q_2^* a_j)q_2 - \ldots - (q_{j-1}^* a_{j})q_{j-1}

La expresión anterior puede reescribirse como:

v_1 &= a_1 = I a_1\\
v_2 &= a_2 - q_1(q_1^* a_2) = (I - q_1 q_1 ^*) a_2\\
v_3 &= a_3 - q_1(q_1^* a_3) - q_2(q_2^* a_3) = (I - q_1 q_1 ^* - q_2 q_2 ^*) a_3\\
\vdots \\
v_{j} &= a_{j} - q_1(q_1^* a_j) - q_2(q_2^* a_j) - \ldots - q_{j-1}(q_{j-1}^* a_{j})\\
v_{j} &= (I - q_1 q_1 ^* - q_2 q_2 ^* - \ldots - q_{j-1}q_{j-1}^*) a_j

donde la matriz (I - q_1 q_1 ^* - q_2 q_2 ^* - \ldots - q_{j-1} q_{j-1}^*) corresponde al proyector ortogonal complementario a los vectores <q_1,q_2,\ldots,q_{j-1}>. Si definimos

P_{\perp q_j}&=(I - q_j(q_j^*)) \\
P_1 &= I \\
P_j &= P_{\perp q_1} \ldots  P_{\perp q_{j-1}}=(I - q_1 q_1 ^* - q_2 q_2 ^* - \ldots - q_{j-1} q_{j-1}^*) \quad \forall j=2:n

podemos reescribir los vectores como:

v_1 &= P_1 a_1\\
v_2 &= P_{\perp q_1} a_2 = P_2 a_2\\
v_3 &= P_{\perp q_2} P_{\perp q_1} a_3 = P_3 a_3\\
\vdots \\
v_j &= P_{\perp q_{j-1}} \ldots P_1 = P_j a_j\\

Algortimo de Gram-Schmidt modificado

En base al enfoque basado en proyectores anterior, podemos ver que es posible aplicar la proyección P_{\perp q_{j}} a todos los vectores: v_{j+1}, \ldots, v_n. El algoritmo siguiente muestra este enfoque:

caption