Descomposicion Qr

Descomposici´n QR de matrices con columnas linealmente independientes o Notas para los cursos 21 y 22 (J.L. Mancilla Aguilar) En lo que sigue veremos que toda matriz A ∈ Kn×m (K = R ´ C) con rango(A) = m, es decir, cuo yas columnas forman un conjunto linealmente independiente, se puede factorizar como producto de dos matrices, una de n × m cuyas columnas forman un conjunto ortonormal y otra de m× m que es triangular superior e inversible. Tal factorizaci´n, que se denomina descomposici´n QR, o o es muy utilizada en la resoluci´n num´rica de ecuaciones lineales y en el c´lculo de autovalores. o e a Definici´n. Dada A ∈ Kn×m con rango(A) = m, una descomposici´n QR de A es una faco o torizaci´n o A = QR con Q ∈ Kn×m y R ∈ Km×m tales que QH Q = I y R es triangular superior e inversible.Teorema 1. Sea A ∈ Kn×m con rango(A) = m. Supongamos que A = QR es una descomposici´n QR de A entonces o 1. Las columnas de Q forman una base ortonormal de col(A); 2. P = QQH es la matriz de proyecci´n sobre col(A). o Demostraci´n. Como el punto 2. es consecuencia directa del o visto sobre matrices de proyecci´n, s´lo probaremos 1. o o Sean q1 , q2 , . . . , qm las columnas de Q. Como  H   H H q1 q1q1 q1 q2  qH   q H q1 q H q2 2  2   2 QH Q =  .  [q1 q2 · · · qm ] =  . . .  .   . . . .
H qm H H qm q1 qm q2

punto 1. por lo que ya hemos

H · · · q1 qm H · · · q2 qm . .. . . . Hq · · · qm m

   , 

H y por lo tanto qi qj es el elemento ij del producto QH Q, tenemos que H QH Q = I ⇐⇒ qi qj =

0 si i = j 1 si i = j

⇐⇒ {q1 , q2 , . . . , qm } es un conjuntoortonormal.

Entonces, claramente, {q1 , q2 , . . . , qm } es una b.o.n. de col(Q). Si probamos que col(Q) = col(A) tendremos probado el punto 1. Para ello usaremos el siguiente resultado: si A, B y C son matrices tales que A = BC entonces col(A) ⊂ col(B). La demostraci´n de este resultado es la siguiente: si y ∈ col(A) entonces existe x tal que o y = Ax = BCx. Llamando z = Cx, tenemos que y = Bz, conlo cual y ∈ col(B). Por lo tanto elemento de col(A) es a su vez elemento de col(B) con lo cual col(A) ⊂ col(B). Entonces, dado que A = QR tenemos que col(A) ⊂ col(Q). Como R es inversible por la definici´n de descomposici´n QR, tenemos que Q = AR−1 , con lo cual col(Q) ⊂ col(A). Por lo o o tanto col(A) ⊂ col(Q) y col(Q) ⊂ col(A) =⇒ col(A) = col(Q).

1

En lo que sigue veremos que toda matriz Ade n × m con rango m admite una descomposici´n QR. o Teorema 2. Sea A ∈ Kn×m con rango(A) = m. Entonces existe una descomposici´n QR o de A. Demostraci´n. Denominemos v1 , v2 , . . . , vm a las columnas de A. Por hip´tesis B = {v1 , v2 , . . . , vm } o o es un conjunto linealmente independiente. Aplicando el procedimiento de Gram-Schmidt (G-S) al conjunto B obtenemos una base ortogonal {u1 , u2 ,. . . , um } de col(A) que satisface las igualdades: u1 u2 u3 . . . uj . . . = v1 = v2 − α12 u1 = v3 − α13 u1 − α23 u2 . . . . . . = vj − α1j u1 − α2j u2 − · · · − α(j−1) j uj−1 . . . . . .

con αij =

uH vj i ui 2

1 ≤ i < j.

um = vm − α1m u1 − α2m u2 − · · · − α(m−1) m um−1 Entonces, despejando cada vi obtenemos la serie de igualdades v1 v2 v3 . . . vj . . . = u1 = α12 u1 + u2 = α13 u1+ α23 u2 + u3 . . . . . . = α1j u1 + α2j u2 + · · · + α(j−1) j uj−1 + uj . . . . . .

.

vm = α1m u1 + α2m u2 + · · · + α(m−1) m um−1 + um que pueden escribirse en forma matricial     [v1 v2 · · · vm ] = [u1 u2 · · · um ]    1 α12 α13 0 1 α23 0 0 1 . . . . . . . . . 0 0 0 · · · α1m · · · α2m · · · α3m . .. . . . ··· 1     .  

Llamando Q0 = [u1 u2 · · · um ] y R0 a la matriztriangular superior que aparece arriba, tenemos que A = Q0 R0 , que es casi la factorizaci´n que estamos buscando, ya que las columnas de Q0 o forman un conjunto ortogonal y R0 es tringular superior e inversible. Lo que hacemos ahora es normalizar cada columna de Q0 , es decir, definimos Q = [q1 q2 · · · qm ] con qi = ui ui

y modificamos R0 de modo tal que su producto con Q siga dando A, para...