La Factorización QR (o Descomposición QR) es un proceso por el cual una matriz \(A\) se expresa como el producto de dos matrices especiales: una matriz ortogonal \(Q\) y una matriz triangular superior \(R\).
Formalmente, para una matriz \(A\) de tamaño \(m \times n\) (donde asumimos que las columnas de \(A\) son linealmente independientes, y usualmente \(m \ge n\)), la descomposición es:
\[ A = QR \]
La matriz \(Q\) es una matriz de tamaño \(m \times n\) cuyas columnas \(\{\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_n\}\) forman un conjunto ortonormal. Esto significa que:
- Normalidad: Cada columna es un vector unitario, es decir, tiene norma 1:
\[ \| \mathbf{q}_i \| = 1 \] - Ortogonalidad: El producto escalar de cualquier par de columnas distintas es cero:
\[ \mathbf{q}_i \cdot \mathbf{q}_j = 0 \quad \text{si } i \ne j \]
La matriz \(R\) es una matriz triangular superior de tamaño \(n \times n\). Esto quiere decir que todos los elementos situados debajo de su diagonal principal son cero.
\[ R = \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} \]
Veamos el procedimiento para obtener la factorización. Pero antes, refresquemos un concepto, el de componente escalar. Dados dos vectores de \(\mathbf{v},\mathbf{u}\in\mathbb{R}^n\) definimos la componente escalar de \(\mathbf{u}\) sobre \(\mathbf{v}\) como
\[\mathbf{comp}_\mathbf{v}\mathbf{u}=\frac{\mathbf{v}\bullet\mathbf{u}}{\|\mathbf{v}\|}\]
En el caso de que \(\mathbf{v}\) sea normal, entonces
\[\mathbf{comp}_\mathbf{v}\mathbf{u}=\mathbf{v}\bullet\mathbf{u}\]
Recordemos que la proyección de \(\mathbf{u}\) sobre \(\mathbf{v}\) es
\[
\mathbf{proy}_\mathbf{v}\mathbf{u}=(\mathbf{v}\bullet\mathbf{u})\cdot \mathbf{v}
\]
cuando \(\|\mathbf{v}\|=1\).
Comencemos ahora con el proceso para obtener la factorización \(QR\). Este proceso toma las columnas de \(A:[a_{ij}]\), \(\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n\), y las transforma en las columnas ortonormales \(\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_n\) de la matriz \(Q\).
El vector \(\mathbf{a}_k\) se expresa como una combinación lineal de los vectores ortonormales \(\mathbf{q}_1, \ldots, \mathbf{q}_k\) que abarcan el mismo subespacio que \(\mathbf{a}_1, \ldots, \mathbf{a}_k\):
\[ \mathbf{a}_k = r_{1k} \mathbf{q}_1 + r_{2k} \mathbf{q}_2 + \ldots + r_{kk} \mathbf{q}_k \]
Donde los coeficientes \(r_{ik}\) son las entradas de la matriz \(R\).
Los elementos \(r_{ik}\) se obtienen mediante
\[ r_{ik}=\mathbf{comp}_{\mathbf{q}_i}\mathbf{a}_k= \mathbf{a}_k \bullet \mathbf{q}_i \]
Y dado que \(R\) es triangular superior, los coeficientes para \(i > k\) son cero:
\[ r_{ik} = 0, \quad \text{para } i > k \]
Ejemplo Práctico de la Factorización QR
Consideremos la siguiente matriz \(A\). Notarás que sus columnas son linealmente independientes, lo cual es un requisito para este tipo de factorización (cuando \(R\) es invertible).
Sea la matriz \(A\) de tamaño \(3 \times 2\):
\[ A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} \]
Sean \(\mathbf{a}_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}\) y \(\mathbf{a}_2 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}\) sus vectores columna.
Paso 1: Obtener el primer vector ortonormal \(\mathbf{q}_1\)
Aplicamos Gram-Schmidt al primer vector \(\mathbf{a}_1\):
- Definimos \(\mathbf{v}_1 = \mathbf{a}_1\).
- Calculamos la norma de \(\mathbf{v}_1\):
\[ \|\mathbf{v}_1\| = \sqrt{1^2 + 1^2 + 0^2} = \sqrt{2} \] - Normalizamos para obtener \(\mathbf{q}_1\):
\[ \mathbf{q}_1 = \frac{\mathbf{v}_1}{\|\mathbf{v}_1\|} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \\ 0 \end{bmatrix} \] - Obtenemos el primer elemento de la matriz \(R\), \(r_{11}\).
\[ r_{11} = \mathbf{a}_1 \bullet \mathbf{q}_1=\sqrt{2} \]
Paso 2: Obtener el segundo vector ortonormal \(\mathbf{q}_2\)
Ortogonalizamos el vector \(\mathbf{a}_2\) respecto a \(\mathbf{q}_1\):
- Calculamos la componente de \(\mathbf{a}_2\) sobre \(\mathbf{q}_1\). El resultado de este producto escalar es el elemento \(r_{12}\) de \(R\):
\[ r_{12} = \mathbf{a}_2 \bullet \mathbf{q}_1 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}^t \cdot \begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \\ 0 \end{bmatrix} = 0 \cdot \frac{1}{\sqrt{2}} + 1 \cdot \frac{1}{\sqrt{2}} + 1 \cdot 0 = \frac{1}{\sqrt{2}} \] - Restamos la proyección de \(\mathbf{a}_2\) sobre \(\mathbf{q}_1\) para obtener el vector ortogonal \(\mathbf{v}_2\):
\[ \mathbf{v}_2 = \mathbf{a}_2 – r_{12} \mathbf{q}_1 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} – \frac{1}{\sqrt{2}} \begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} – \begin{bmatrix} 1/2 \\ 1/2 \\ 0 \end{bmatrix} = \begin{bmatrix} -1/2 \\ 1/2 \\ 1 \end{bmatrix} \] - Normalizamos para obtener \(\mathbf{q}_2\). Para ello, calculamos
\[ \|\mathbf{v}_2\| = \sqrt{(-1/2)^2 + (1/2)^2 + 1^2} = \sqrt{1/4 + 1/4 + 1} = \sqrt{3/2}, \]luego
\[ \mathbf{q}_2 = \frac{\mathbf{v}_2}{\|\mathbf{v}_2\|} = \frac{1}{\sqrt{3/2}} \begin{bmatrix} -1/2 \\ 1/2 \\ 1 \end{bmatrix} = \begin{bmatrix} -1/\sqrt{6} \\ 1/\sqrt{6} \\ 2/\sqrt{6} \end{bmatrix} \]
- Calculamos el elemento \(r_{22}\) de \(R\):
\[ r_{22} = \mathbf{a}_2 \bullet \mathbf{q}_2 =\|\mathbf{v}_2\| = \sqrt{(-1/2)^2 + (1/2)^2 + 1^2} = \sqrt{1/4 + 1/4 + 1} = \sqrt{3/2} \]
Observar, que
\[
\begin{align}
r_{ii} &= \mathbf{a}_i \bullet \mathbf{q}_i\\
&= \mathbf{a}_i \bullet \frac{\mathbf{v}_i}{\|\mathbf{v}_i\|}\\
&(\mbox{recordemos que }\, \mathbf{v}_i=\mathbf{a}_i-\sum_{k=1}^{i-1}r_{ki} \mathbf{q}_{k},) \\
&=\left( \mathbf{v}_i + \sum_{k=1}^{i-1}r_{ki} \mathbf{q}_{k}\right) \bullet \frac{\mathbf{v}_i}{\|\mathbf{v}_i\|}\\
&=\frac{1}{\|\mathbf{v}_i\|}\left( \mathbf{v}_i \bullet\mathbf{v}_i+ \sum_{k=1}^{i-1}r_{ki} (\mathbf{q}_{k}\bullet\mathbf{v}_i)\right) \\
&(\mbox{como}\,\mathbf{q}_{k}\bullet\mathbf{v}_i=0\,\forall k)\\
&=\frac{1}{\|\mathbf{v}_i\|}( \mathbf{v}_i \bullet\mathbf{v}_i)\\
&=\|\mathbf{v}_i\| \\
\end{align}
\]
Paso 3: Construir las matrices \(Q\) y \(R\)
La matriz \(Q\) está formada por los vectores \(\mathbf{q}_1\) y \(\mathbf{q}_2\):
\[ Q = [\mathbf{q}_1 \mid \mathbf{q}_2] = \begin{bmatrix} 1/\sqrt{2} & -1/\sqrt{6} \\ 1/\sqrt{2} & 1/\sqrt{6} \\ 0 & 2/\sqrt{6} \end{bmatrix} \]
La matriz \(R\) está formada por los valores \(r_{ik}\) que calculamos:
\[ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix} = \begin{bmatrix} \sqrt{2} & 1/\sqrt{2} \\ 0 & \sqrt{3/2} \end{bmatrix} \]
Paso 4: La Factorización QR
Hemos descompuesto la matriz \(A\) en el producto de \(Q\) y \(R\):
\[ A = QR \]
\[ \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1/\sqrt{2} & -1/\sqrt{6} \\ 1/\sqrt{2} & 1/\sqrt{6} \\ 0 & 2/\sqrt{6} \end{bmatrix} \begin{bmatrix} \sqrt{2} & 1/\sqrt{2} \\ 0 & \sqrt{3/2} \end{bmatrix} \]
Ejemplo: Determina la factorización QR de la matriz \(\begin{bmatrix}1&2\\ 2&1\end{bmatrix}\).
Ejemplo: Determina la factorización QR de la matriz \(\begin{bmatrix}1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1\end{bmatrix}\).
Ejemplo: Determina la factorización QR de la matriz \(\begin{bmatrix}
1 & 2 \\
1 & 0 \\
0 & 1
\end{bmatrix}\).
Unicidad de la Factorización QR
La unicidad de la factorización QR depende de dos condiciones cruciales: el rango de la matriz \(A\) y la restricción de los signos en la matriz \(R\).
La factorización QR es única si y solo si se cumplen dos condiciones:
- La matriz \(A\) tiene columnas linealmente independientes (es decir, \(\text{rango}(A) = n\) si \(A\) es \(m \times n\) con \(m \ge n\)).
- Todos los elementos de la diagonal de la matriz triangular superior \(R\), \(r_{ii}\), son positivos: \( r_{ii} > 0 \)
Si estas dos condiciones se satisfacen, la factorización $A = QR$ es única. Esta es la forma en que el Algoritmo QR y las implementaciones de bibliotecas numéricas suelen requerirla.
Aplicaciones Clave en Ingeniería Informática
La factorización QR es fundamental para:
- Mínimos Cuadrados: Permite resolver sistemas de ecuaciones sobredeterminados de la forma \(A\mathbf{x} = \mathbf{b}\) de una manera computacionalmente eficiente y estable. La solución \(\mathbf{x}\) se obtiene resolviendo el sistema más simple \(R\mathbf{x} = Q^t\mathbf{b}\).
- Cálculo de Autovalores: El Algoritmo QR itera esta descomposición para converger a los autovalores de una matriz. Es el método más utilizado en la práctica para este fin.
- Bases Orthonormales: Proporciona un método directo para construir bases ortonormales para subespacios vectoriales (mediante las columnas de \(Q\)), lo cual es importante en gráficos por computadora y procesamiento de señales.
Método QR para mínimos cuadrados
Para resolver un problema de mínimos cuadrados mediante factorización QR con la matriz 3×2 anterior, consideramos el sistema sobredeterminado \( A \mathbf{x} = \mathbf{b} \), donde la solución \( \mathbf{x} \) minimiza \( \| A\mathbf{x} – \mathbf{b} \|_2 \).
Datos del problema
\[
A = \begin{bmatrix}
1 & 2 \\
1 & 0 \\
0 & 1
\end{bmatrix}, \quad
\mathbf{b} = \begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix}.
\]
Usamos la factorización QR ya calculada («delgada»):
\[
Q = \begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{3}} \\
0 & \frac{1}{\sqrt{3}}
\end{bmatrix}, \quad
R = \begin{bmatrix}
\sqrt{2} & \sqrt{2} \\
0 & \sqrt{3}
\end{bmatrix}.
\]
Método QR para mínimos cuadrados
El problema \( \min \| A\mathbf{x} – \mathbf{b} \|_2 \) se resuelve así:
1. Sistema transformado: Como \( A = QR \), entonces \( \| A\mathbf{x} – \mathbf{b} \|_2 = \| QR\mathbf{x} – \mathbf{b} \|_2 = \| R\mathbf{x} – Q^t \mathbf{b} \|_2 \) (por ortogonalidad de Q).
2. Proyección: Definimos \( \mathbf{c} = Q^t \mathbf{b} \), entonces resolvemos el sistema triangular \( R\mathbf{x} = \mathbf{c} \) (sustitución hacia atrás).
Paso 1: Calcular \( \mathbf{c} = Q^t \mathbf{b} \)
\[
\mathbf{c} = Q^t \mathbf{b} = \begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\
\frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}}
\end{bmatrix}
\begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix}
= \begin{bmatrix}
\frac{1}{\sqrt{2}}(3+1+0) \\
\frac{1}{\sqrt{3}}(3-1+2)
\end{bmatrix}
= \begin{bmatrix}
\frac{4}{\sqrt{2}}\\
\frac{4}{\sqrt{3}}
\end{bmatrix}.
\]
Paso 2: Resolver \( R\mathbf{x} = \mathbf{c} \)
Sistema triangular superior:
\[
\begin{bmatrix}
\sqrt{2} & \sqrt{2} \\
0 & \sqrt{3}
\end{bmatrix}
\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}
= \begin{bmatrix} \frac{4}{\sqrt{2}} \\ \frac{4}{\sqrt{3}} \end{bmatrix}.
\]
Sustitución hacia atrás:
– De la segunda ecuación: \( \sqrt{3} x_2 = \frac{4}{\sqrt{3}} \Rightarrow x_2 = \frac{4}{3} \).
– Primera ecuación: \( \sqrt{2} x_1 + \sqrt{2} \cdot \frac{4}{3} = \frac{4}{\sqrt{2}} \Rightarrow \sqrt{2} x_1 = \frac{4}{\sqrt{2}} – \frac{4\sqrt{2}}{3} = \sqrt{2} \left(2 – \frac{4}{3}\right) = \sqrt{2} \cdot \frac{2}{3} \Rightarrow x_1 = \frac{2}{3} \).
Solución: \( \mathbf{x} = \begin{bmatrix} \frac{2}{3} \\ \frac{4}{3} \end{bmatrix} \).
Verificación
– \( A\mathbf{x} = \begin{bmatrix} 1 & 2 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{2}{3} \\ \frac{4}{3} \end{bmatrix} = \begin{bmatrix} \frac{10}{3} \\ \frac{2}{3} \\ \frac{4}{3} \end{bmatrix} \).
– Residuo: \( \| A\mathbf{x} – \mathbf{b} \|_2 = \sqrt{ \left(\frac{10}{3}-3\right)^2 + \left(\frac{2}{3}-1\right)^2 + \left(\frac{4}{3}-2\right)^2 } = \sqrt{ \frac{1}{9} + \frac{1}{9} + \frac{1}{9} } = \frac{1}{\sqrt{3}} \), que coincide con el componente de \( \mathbf{b} \) ortogonal al rango de A (tercera fila de Q).
Este método es numéricamente estable porque solo requiere resolver un sistema triangular.
|
Ejercicio: ¿De cuantos grados es el giro que proporciona la matriz \(\begin{bmatrix}0&-1\\ 1&0\end{bmatrix}\)? |