Tópico 4
Gram-Schmidt e decomposição QR
Pedro Aladar Tonelli
Família ortonormal
Vamos fixar os espaços vetoriais $V=\mathbb{R}^n$ e $W=\mathbb{R}^m$, cada um deles
munido de um produto interno, vamos por simplicidade, considerar o produto interno:
$$\langle \mathbf{x},\mathbf{y}\rangle =\mathbf{x}^{T}\mathbf{y} = \sum x_iy_i$$
Uma família de vetores $\{\vec{e_1}, \dots, \vec{e_k} \}$ é ortonormal quando
$$\langle \vec{e_i},\vec{e_j} \rangle = \delta_{ij}$$
Base Ortonormal
Em particular se $\{\vec{e_1}, \dots, \vec{e_n} \}$ for uma base ortonormal e
$$ \mathbf{x} = x_1\vec{e_1} + \cdots + x_n\vec{e_n} $$
então
$$ x_i = \langle \mathbf{x} , \vec{e_i} \rangle $$
Ortonormalização de uma família LI
Problema: A partir de uma família de vetores LI $\{\mathbf{x_1},\dots, \mathbf{x_k}\}$,
obter uma família ortonormal $\{\mathbf{h_1}, \dots, \mathbf{h_k}\}$ tal que para cada $i\in\{1,\dots,k\}$
temos
$$ \left[ \mathbf{x_1},\dots,\mathbf{x_i} \right]_{ev}=\left[ \mathbf{h_1},\dots,\mathbf{h_i} \right]_{ev} $$
Algoritmo de Gram-Schmidt
$$
\begin{gather}
\mathbf{h_1} = \frac{\mathbf{x_1}}{\|\mathbf{x_1}\|} \\
\text{ para } i \in 2:k \\
\mathbf{a_i} = \mathbf{x_i} - \sum_{l=1}^{i-1}\langle \mathbf{x_i} , \mathbf{h_l}\rangle \mathbf{h_l}\\
\mathbf{h_i} = \frac{\mathbf{a_i}}{\|\mathbf{a_i}\|}
\end{gather}
$$
Exemplo
\begin{equation}
\left[
\begin{array}{ccc}
\mathbf{x_1} & \mathbf{x_2} & \mathbf{x_3} \\ \hline
1 & 2 & 0 \\
1 & 3 & 2 \\
0 & -1 & 0 \\
\end{array}
\right]
\end{equation}
\begin{equation}
\left[
\begin{array}{ccc}
\mathbf{x_1} & \mathbf{x_2} & \mathbf{x_3} \\ \hline
1 & 2 & 0 \\
1 & 3 & 2 \\
0 & -1 & 0 \\
\end{array}
\right]\left[
\begin{array}{ccc}
& & \\ \hline
0.70710 & 0.0 & 0.0 \\
0.0 & 1.0 & 0.0 \\
0.0 & 0.0 & 1.0 \\
\end{array}\right] \end{equation}
\begin{equation} \left[
\begin{array}{ccc}
\mathbf{h_1} & \mathbf{x_2} & \mathbf{x_3} \\ \hline
0.70710 & 2.0 & 0.0 \\
0.70710 & 3.0 & 2.0 \\
0.0 & -1.0 & 0.0 \\
\end{array}
\right]
\end{equation}
\begin{equation}= \left[
\begin{array}{ccc}
\mathbf{h_1} & \mathbf{x_2} & \mathbf{x_3} \\ \hline
0.70710 & 2.0 & 0.0 \\
0.70710 & 3.0 & 2.0 \\
0.0 & -1.0 & 0.0 \\
\end{array}
\right]\left[
\begin{array}{ccc}
& & \\ \hline
1.0 & -3.53553 & 0.0 \\
0.0 & 1.0 & 0.0 \\
0.0 & 0.0 & 1.0 \\
\end{array}
\right]
\end{equation}
\begin{equation}
\left[
\begin{array}{ccc}
\mathbf{h_1} & \mathbf{a_2} & \mathbf{x_3} \\ \hline
0.70710 & -0.5 & 0.0 \\
0.70710 & 0.5 & 2.0 \\
0.0 & -1.0 & 0.0 \\
\end{array}
\right]*\left[
\begin{array}{ccc}
& & \\ \hline
1.0 & 0.0 & 0.0 \\
0.0 & 0.8165 & 0.0 \\
0.0 & 0.0 & 1.0 \\
\end{array}
\right]
\end{equation}
\begin{equation}
\left[
\begin{array}{ccc}
\mathbf{h_1} & \mathbf{h_2} & \mathbf{x_3} \\ \hline
0.707107 & -0.4082483 & 0.0 \\
0.707107 & 0.4082483 & 2.0 \\
0.0 & -0.8164966 & 0.0 \\
\end{array}
\right]*\left[
\begin{array}{ccc}
& & \\ \hline
1.0 & 0.0 & -1.41421 \\
0.0 & 1.0 & -0.81649 \\
0.0 & 0.0 & 1.0 \\
\end{array}
\right]
\end{equation}
\begin{equation}
\left[
\begin{array}{ccc}
\mathbf{h_1} & \mathbf{h_2} & \mathbf{a_3} \\ \hline
0.70710 & -0.40824 & -0.66666 \\
0.70710 & 0.40824 & 0.66666 \\
0.0 & -0.81650 & 0.66666 \\
\end{array}
\right]*\left[
\begin{array}{ccc}
& & \\ \hline
1.0 & 0.0 & 0.0 \\
0.0 & 1.0 & 0.0 \\
0.0 & 0.0 & 0.86602 \\
\end{array}
\right]
\end{equation}
\begin{equation}
\left[
\begin{array}{ccc}
\mathbf{h_1} & \mathbf{h_2} & \mathbf{h_3} \\ \hline
0.70710 & -0.40824 & -0.57735 \\
0.70710 & 0.40824 & 0.57735 \\
0.0 & -0.8164966 & 0.57735 \\
\end{array}
\right]
\end{equation}
\begin{equation}
\left[
\begin{array}{ccc}
0.7071067811865475 & -2.041241452319315 & 0.5773502691896276 \\
0.0 & 0.8164965809277261 & -0.5773502691896265 \\
0.0 & 0.0 & 0.8660254037844387 \\
\end{array}
\right]
\end{equation}
\begin{equation}
\left[
\begin{array}{ccc}
1.4142135623730951 & 3.5355339059327378 & 1.4142135623730951 \\
0.0 & 1.224744871391589 & 0.816496580927727 \\
0.0 & 0.0 & 1.1547005383792515 \\
\end{array}
\right]
\end{equation}
A decomposição $QR$
Seja $A$ uma matriz $n \times k$ de posto $k$, vamos representar esta
matriz destacando as colunas que são $LI$.
$$ A = \left[
\begin{array}{cccc}
\mathbf{x_1} & \mathbf{x_2} & \cdots & \mathbf{x_k}
\end{array}\right] $$
O primeiro passo do processo de Gram-Schmidt é dividir $\mathbf{x_1}$ por
sua norma, e isto é obtido pela mutiplicação de matrizes:
$$ \left[
\begin{array}{cccc}
\mathbf{h_1} & \mathbf{x_2} & \cdots & \mathbf{x_k}
\end{array}\right]=\left[
\begin{array}{cccc}
\mathbf{x_1} & \mathbf{x_2} & \cdots & \mathbf{x_k}
\end{array}\right]\left[
\begin{array}{cccc}
\frac{1}{\| \mathbf{x_1}\|} & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & & & \vdots \\
0 & 0 & \cdots & 1
\end{array}\right] $$
O segundo passo começa com $\mathbf{a_2} = \mathbf{x_2} - \langle \mathbf{x_2},\mathbf{h_1}\rangle \mathbf{h_1}$
que pode ser escrito matricialmente
$$
\left[
\begin{array}{cccc}
\mathbf{h_1} & \mathbf{a_2} & \cdots & \mathbf{x_k}
\end{array}\right]=\left[
\begin{array}{cccc}
\mathbf{h_1} & \mathbf{x_2} & \cdots & \mathbf{x_k}
\end{array}\right]\left[
\begin{array}{cccc}
1 & \alpha & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots& & \ddots & \vdots \\
0 & 0& \cdots & 1
\end{array}\right]
$$
$\alpha = -\langle \mathbf{x_2},\mathbf{h_1}\rangle$
$$
\begin{gather}
\left[
\begin{array}{cccc}
\mathbf{h_1} & \mathbf{h_2} & \cdots & \mathbf{x_k}
\end{array}\right]= \\
\left[
\begin{array}{cccc}
\mathbf{h_1} & \mathbf{a_2} & \cdots & \mathbf{x_k}
\end{array}\right]\left[
\begin{array}{cccc}
1 & 0 & \cdots & 0 \\
0 & \frac{1}{\|\mathbf{a_2}\|} & \cdots & 0 \\
\vdots& & \ddots & \vdots \\
0 & 0& \cdots & 1
\end{array}\right]
\end{gather}$$
No fim teremos:
$$\left[
\begin{array}{ccc}
\mathbf{h_1} & \cdots & \mathbf{h_k}
\end{array}\right]=\left[
\begin{array}{ccc}
\mathbf{x_1} & \cdots & \mathbf{x_k}
\end{array}\right]\left[
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1k} \\
0 & a_{22} & \cdots & a_{2k} \\
\vdots & & \ddots & \vdots \\
0 & 0 & \cdots & a_{kk}
\end{array}\right]$$