Navegación

Contenidos

Tema anterior

Clase 9: Más de SVD

Próximo tema

Clase 11: Más sobre Factorización QR

Esta página

Clase 10: Factorización QR

Bibliografía de la Clase

  • Numerical Linear Algebra.L.N. Trefethen. Chapter 1: Lecture 7 QR Factorization
  • Introduction to Linear Algebra. Gilbert Strang. Chapter 4, Sec. 4.4 Orthogonal Bases and Gram-Schmidt
  • Guía profesor Luis Salinas

Idea Ortogonalización de Gram-Schmidt

Recordar:

  1. Ortogonalidad
  2. Matrices Unitarias
  3. Proyecciones

Propiedades de la Ortogonalidad:

Preserva la estructura geométrica en el espacio Euclideano se preserva el producto interno:

(Qx)^{*}(Qy)= x^{*}Q^{*}Qy= x^{*}y

Por lo tanto, el tamaño de los vectores se preserva:

||Qx|| = ||x|| \ \ \ /()^{2} ||Qx||^{2}= (Qx)^{*}(Qx)= x^{*}Q^{*}Qx= x^{*}x=||x||^{2}

Q aplica una transformación a x, que no afecta al tamaño del vector.

Gram-Schmidt

El método de Gram-Schimdt permite realizar la ortogonalización de vectores.

caption

1. Para construir el vector B, ortogonal al vector a (a partir del vector b) se debe quitar al vector b su proyección sobre a, es decir:

B = b-p = b - \frac{a^* b}{a^* a}a

Importante:

p es un vector que corresponde a la proyección del vector b sobre el vector a: p=\hat{x}a = \frac{a^{*}b}{a^{*}a}a.

\hat{x} es un escalar y se obtiene de la siguiente manera:

e=b - \hat{x}a a^{*}(b - \hat{x}a) = 0 \equiv a^{*}b - \hat{x}a^{*}a=0 \hat{x}=\frac{a^{*}b}{a^{*}a}

  1. Verificar que el vector B es ortogonal con el vector A.
  2. Construir el vector C ortogonal a B y A = a.

C=c-\frac{A^{*}c}{A^{*}A}A - \frac{B^{*}c}{B^{*}B}B

  1. Para obtener vectores ortonormales, simplemente se debe dividir por su norma:

q_1= \frac{A}{||A||} \ \ \ q_2= \frac{B}{||B||} \ \ \ q_3= \frac{C}{||C||}

Por lo tanto, la idea de Gram-Schmidt es restar de cada nuevo vector, sus proyecciones de los vectores ya ortonormalizados.

Ejercicio en clases:

  1. Dados los sgtes. vectores l.i., realizar ortogonalización de Gram-Schmidt:

a=\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}, \ b=\begin{bmatrix}2 \\ 0 \\-2 \end{bmatrix}, \ c=\begin{bmatrix}3 \\ -3 \\ 3 \end{bmatrix}

Nota:

Si S=\{v_1, v_2, \ldots , v_k \} es un conjunto de vectores no nulos, ortogonales de a pares, entonces S es linealmente independiente (l.i.). Pero esta implicancia no es hacia el otro lado, i.e., si son l.i, no son necesariamente ortogonales.

Factorización QR Reducida

Sean

a_{1},a_{2}, \ldots, a_{p} \text{ vectores distintos de cero } \in \mathbb{C}^{m}

Los espacios generados por estos vectores se denotan:

\langle a_{1}, \ldots, a_{p} \rangle := \{ \sum_{i=1}^{p}\lambda_{i}a_{i}: \lambda_{1}, \ldots, \lambda_{p} \in \mathbb{C}\} \subseteq \mathbb{C}^{m}

A menudo nos interesa los espacios de columnas (sucesivos) genereado por las columnas de A:

\langle a_{1}\rangle \ \subseteq \ \langle a_{1},a_{2}\rangle \ \subseteq \ \langle a_{1},a_{2},a_{3}\rangle \ \subseteq \ldots

La idea de la factorización QR es la construcción de una secuencia ortonormal de vectores q_1, q_2, \ldots que genera estos subespacios sucesivos.

Sea A \in \mathbb{C}^{m\times n} (m\geq n) de full rank n. Se busca la secuencia q_1, q_2, \ldots con la propiedad:

\langle q_{1},q_2, \ldots q_{j} \rangle = \langle a_{1},a_2, \ldots a_{j} \rangle , \ \ j=1,\ldots ,n

lo que corresponde a:

\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}

como ecuaciones queda:

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}

matricialmente:

A = \hat{Q} \hat{R} \ \ \ \rightarrow \text{ Factorización QR Reducida}

y gráficamente:

caption

donde \hat{Q} \in \mathbb{C}^{m\times n} con columnas ortonormales y \hat{R} \in \mathbb{C}^{n\times n}, triangular superior.

Factorización QR Completa

\langle a_{1},\ldots,a_{n} \rangle = \langle q_{1},\ldots,q_{n} \rangle

las columnas q_{n+1}, \ldots, q_{m} deben ser ortogonales al Col(A).

Si A es de full rank n, estos vectores forman una base ortonormal de Col(A)^{\perp} (espacio ortogonal al Col(A), que corresponde al Null(A^{*})).

caption

Ortogonalización de Gram-Schmidt

Ya se sabe cual es la idea de la ortogonalización de Gram-Schmidt, más formalmente:

Gram-Scmidt Clásico:

En la iteración j-ésima, encontrar el vector q_j \in \langle a_1 , \ldots , a_{j} \rangle que sea ortogonal a q_{1}, q_{2}, i\ldots , q_{j-1}:

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}

v_j corresponde al tipo de vector requerido, pero todavía no está normalizado, por lo que simplemente v_j debe ser dividido por su norma, ||v_j||_2.

Por lo tanto:

q_{1} = \frac{a_{1}}{r_{11}} q_{2} = \frac{a_2 - r_{12}q_{1}}{r_{22}} q_{3} = \frac{a_3 - r_{13}q_1 - r_{23}q_{2}}{r_{33}} \vdots q_n = \frac{a_n - \sum_{i=1}^{n-1}r_{in}q_{i}}{r_{nn}}

donde

r_{ij}=q_{i}^* a_j | r_{jj}| = ||a_{j} - \sum_{i=1}^{j-1}r_{ij}q_{i}||_2

Algoritmo de Gram-Schmidt Clásico

A continuación, el algoritmo de Gram-Schmidt Clásico, el cual númericamente no es muy estable debido a errores de redondeo (que analizaremos en las siguientes clases):

caption

Ejercicio en clases:

Obtener factorización QR para A=\begin{bmatrix}3 &-6\\ 4 &-8\\ 0 &1\end{bmatrix}.

Navegación

© Copyright 2012, CTI-HPC. Creado con Sphinx 1.1.3.