¿Explicación intuitiva de por qué el Gram-Schmidt modificado es más estable que el clásico?

Question

Puede que esta sea una pregunta antigua, y ciertamente hay algunos posts relacionados que mencionaré a continuación. Sin embargo, todavía no me parece que haya una respuesta clara. La pregunta es: ¿hay una forma intuitiva de explicar por qué el proceso de Gram-Schmidt modificado (MGS) para hacer la factorización QR de una matriz $A\in\mathbb{C} ^{m\times n}$ da una $Q$ ¿una matriz "más ortogonal" que la del proceso clásico de Gram-Schmidt (CGS)? Por "intuitivo", espero que la explicación pueda relacionarse con la diferencia de procedimiento entre MGS y CGS de forma transparente.

En Trefethen's Álgebra lineal numérica La distinción entre el CGS y el MGS es la siguiente:

En el $j$ paso, ambos procesos de GS calculan $q_j$ como $$ q_j=\frac{P_j a_j }{\|| P_j a_j \|| } $$ mientras que para CGS, $$ P_j=I-Q_{j-1}Q_{j-1}^* $$ pero para MGS, $$ P_j=(I-q_{j-1}q_{j-1}^* )...(I-q_2q_2^* )(I-q_1q_1^* ) $$

Trefethen no discute por qué esta diferencia de procedimiento conduce a la mejor estabilidad numérica de MGS.

@AlgebraicPavel ha dado límites cuantitativos aquí en los factores de ortogonalidad: $\||I-Q^* Q\||\leq O(\epsilon \kappa(A))$ para MGS, mientras que $\||I-Q^* Q\||\leq O(\epsilon \kappa^2(A))$ para CGS. Estos resultados son suficientemente cuantitativos. Sin embargo, como se mencionó anteriormente, me gustaría un razonamiento más intuitivo de cómo se obtiene.

@Ian dijo aquí eso:

"El Gram-Schmidt clásico, en el que se restan las proyecciones del (k+1)º vector sobre los primeros k vectores, es bastante inestable, especialmente en dimensiones altas, porque esencialmente se asegura que el nuevo vector es ortogonal al vector de entrada en cuestión, pero no se asegura que los vectores que se obtienen al final del proceso sean ortogonales entre sí. Combina eso con el hecho de que puedes terminar restando números casi iguales y obtienes una mala situación".

Esto parece una explicación intuitiva y cualitativa del problema de la CGS. Sin embargo, al entrar en detalles, no me siento cómodo con esta línea de razonamiento. En concreto, decir que el "nuevo vector es ortogonal al vector de entrada en cuestión" no parece estar de acuerdo con lo que hace CGS. Tanto para CGS como para MGS, el nuevo vector ( $a_j$ ) se resta en un intento de hacerla ortogonal a la existente $q_i, i=1,...,j-1$ . Puede que no sea apropiado llamar a estos $q_i$ "vector de entrada", y esto no aborda la principal diferencia de procedimiento entre MGS y CGS.

En este puesto, el $4\times 3$ La matriz de Lauchli se utiliza como ejemplo para demostrar los diferentes resultados entre MGS y CGS. Aunque tampoco hay una explicación intuitiva a la cuestión, observo que para este ejemplo de Lauchli, el resultado que $q_3^{CGS}$ no es ortogonal a $q_2^{CGS}$ es porque el $r_{23}^{CGS}$ se calcula erróneamente, con un error relativo del 100%. Sin embargo, no consigo entender por qué el procedimiento MGS puede aliviar este problema de forma significativa.

Agradezco mucho cualquier comentario.

Answer 1

Tanto en el CGS como en el MGS, el paso de ortogonalización de restar las proyecciones en las columnas de $Q$ que ya han sido calculados introduce errores a debido a la aritmética de precisión finita. Cada columna $\mathbf{q}_i$ de $Q$ por lo tanto, tiene algún componente de error en la dirección de las columnas previamente calculadas $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$ . El error se acumula al aumentar el número de columnas $i$ , que es una debilidad inherente a ambos algoritmos.

En CGS, la ortogonalización de una columna $n$ contra columna $\mathbf{q}_{i}$ ( $i<n$ ) se realiza proyectando la columna original de $A$ (Llama a esto $\mathbf{a}_n$ ) en $\mathbf{q}_{i}$ y restando. $$ \begin{split} \mathbf{p}_{n} &\equiv \mathbf{a_n} - \sum_{i=1}^{n-1}(\mathbf{q_i^T}\cdot \mathbf{a_n})\mathbf{q_i} \\ \mathbf{q}_{n} &= \frac{\mathbf{p}_{n}}{\|\mathbf{p}_{n}\|} \end{split} $$ En cambio, en el SGR, los componentes a lo largo de cada $\mathbf{q}_i$ se restan inmediatamente del resto de las columnas a la derecha de la columna $i$ tan pronto como el $\mathbf{q}_i$ se calculan. Por lo tanto, la ortogonalización de la columna $n$ contra $\mathbf{q}_{i}$ no se realiza proyectando $\mathbf{q}_{i}$ contra la columna original de $A$ como en CGS, sino contra un vector obtenido al restar de esa columna de $A$ los componentes en span( $\mathbf{q}_1….\mathbf{q}_{i-1}$ ). Esto es importante debido a los componentes de error de $\mathbf{q}_i$ que abarcan $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$ .

Más concretamente, en MGS la ortogonalización de la columna $n$ contra $\mathbf{q}_{i}$ se realiza restando el componente de $\mathbf{q}_{i}$ del vector $\mathbf{v}_n^{i-1}$ , donde $\mathbf{v}_n^0\equiv \mathbf{a}_n$ y $\mathbf{v}_n^i$ ( $0<i<n$ ) se define como $$ \begin{split} \mathbf{v}_n^{i}&\equiv \mathbf{v}_n^{i-1} -(\mathbf{q}_{i}^T\cdot \mathbf{v}_n^{i-1})\mathbf{q}_{i}, \\ \mathbf{q}_n &= \frac{\mathbf{v}_n^{n-1}}{\|\mathbf{v}_n^{n-1}\|} \end{split} $$ Obsérvese la diferencia de los factores de proyección entre paréntesis en la expresión anterior, $(\mathbf{q}_{i}^T\cdot \mathbf{v}_n^{i-1})$ y el correspondiente a CGS, ( $\mathbf{q_i^T}\cdot \mathbf{a_n}$ ). El vector $\mathbf{q}_i$ tiene componentes de error en span( $\mathbf{q}_1….\mathbf{q}_{i-1}$ ) que será la que introduzca el error en este factor de proyección. Mientras que el vector $\mathbf{a}_n$ puede tener en general grandes componentes en span( $\mathbf{q}_1….\mathbf{q}_{i-1}$ ), el vector $\mathbf{v}_n^{i-1}$ sólo tiene componentes de error en span( $\mathbf{q}_1….\mathbf{q}_{i-1}$ ) porque en el cálculo $\mathbf{v}_n^{i-1}$ aquellos componentes de $\mathbf{a}_n$ en span( $\mathbf{q}_1….\mathbf{q}_{i-1}$ ) ya se han restado. En consecuencia, el error en este factor multiplicativo debido a la ortogonalidad imperfecta entre $\mathbf{q}_i$ y $\{\mathbf{q}_1...\mathbf{q}_{i-1}\}$ es mucho menor en MGS que en CGS.

Debido al error mucho menor en este factor de proyección, el MGS introduce menos error de ortogonalización en cada paso de sustracción que el CGS.