• Author / Uploaded
• Kevin Manuel Runza Lombana

Citation preview

´ QR FACTORIZACION Martha C. Moreno

Departamento de Matem´ aticas Universidad Nacional de Colombia

Martha C. Moreno

´ QR FACTORIZACION

Factorizaci´on QR En muchas aplicaciones de las matrices en diferentes ciencias, se presentan con frecuencia c´ alculos matriciales complejos, la idea es encontrar procedimientos que los simplifiquen a´ un cuando estos sean realizados por m´etodos inform´ aticos. Uno de tales procedimientos est´a basado en la aplicaci´ on del proceso de Gram-Schmidt y es conocido como la Factorizaci´on QR.

Martha C. Moreno

´ QR FACTORIZACION

Factorizaci´on QR En muchas aplicaciones de las matrices en diferentes ciencias, se presentan con frecuencia c´ alculos matriciales complejos, la idea es encontrar procedimientos que los simplifiquen a´ un cuando estos sean realizados por m´etodos inform´ aticos. Uno de tales procedimientos est´a basado en la aplicaci´ on del proceso de Gram-Schmidt y es conocido como la Factorizaci´on QR. Teorema Si A es una matriz m × n con columnas l.i, entonces A puede factorizarse en la forma: Am×n = Qm×n Rn×n En la que Q es una matriz con columnas ortonormales y R es una matriz triangular superior no singular.

Martha C. Moreno

´ QR FACTORIZACION

Sea A una matriz m × n con columnas l.i A = (C1

C2

Martha C. Moreno

···

Cn )

´ QR FACTORIZACION

Sea A una matriz m × n con columnas l.i A = (C1

C2

···

Cn )

{C1 , C2 , · · · , Cn } es una base del espacio columna de A (espacio generado por las columnas de A).

Martha C. Moreno

´ QR FACTORIZACION

Sea A una matriz m × n con columnas l.i A = (C1

C2

···

Cn )

{C1 , C2 , · · · , Cn } es una base del espacio columna de A (espacio generado por las columnas de A). Aplicando el proceso de Gram-Schmidt podemos construir a partir de esta una base ortonormal {Q1 , Q2 , · · · , Qn } del espacio columna.

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

Martha C. Moreno

{C1 , C2 , · · · , Cn }

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1 v2 = C2 − proyv1 C2

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1 v2 = C2 − proyv1 C2 v3 = C3 − proyv1 C3 − proyv2 C3

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1 v2 = C2 − proyv1 C2 v3 = C3 − proyv1 C3 − proyv2 C3 .. .

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1 v2 = C2 − proyv1 C2 v3 = C3 − proyv1 C3 − proyv2 C3 .. . vn = Cn − proyv1 Cn − proyv2 Cn − · · · − proyvn−1 Cn

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1 v2 = C2 − proyv1 C2 v3 = C3 − proyv1 C3 − proyv2 C3 .. . vn = Cn − proyv1 Cn − proyv2 Cn − · · · − proyvn−1 Cn As´ı el conjunto {v1 , v2 , · · · , vn } es una base ortogonal del espacio columna.

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1 v2 = C2 − proyv1 C2 v3 = C3 − proyv1 C3 − proyv2 C3 .. . vn = Cn − proyv1 Cn − proyv2 Cn − · · · − proyvn−1 Cn As´ı el conjunto {v1 , v2 , · · · , vn } es una base ortogonal del espacio columna. Normalizando cada vector se obtiene:

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1 v2 = C2 − proyv1 C2 v3 = C3 − proyv1 C3 − proyv2 C3 .. . vn = Cn − proyv1 Cn − proyv2 Cn − · · · − proyvn−1 Cn As´ı el conjunto {v1 , v2 , · · · , vn } es una base ortogonal del espacio columna. Normalizando cada vector se obtiene: { kvv11 k , kvv22 k , · · · , kvvnn k } = {Q1 , Q2 , · · · Qn }

Martha C. Moreno

´ QR FACTORIZACION

La base de la que partimos es:

{C1 , C2 , · · · , Cn }

v1 = C1 v2 = C2 − proyv1 C2 v3 = C3 − proyv1 C3 − proyv2 C3 .. . vn = Cn − proyv1 Cn − proyv2 Cn − · · · − proyvn−1 Cn As´ı el conjunto {v1 , v2 , · · · , vn } es una base ortogonal del espacio columna. Normalizando cada vector se obtiene: { kvv11 k , kvv22 k , · · · , kvvnn k } = {Q1 , Q2 , · · · Qn } Que es una base ortonormal del espacio columna.

Martha C. Moreno

´ QR FACTORIZACION

Como {Q1 , Q2 , · · · , Qn } es una base del espacio columna de A, entonces cada columna de A se puede expresar de manera u ´nica como una c.l de sus elementos, es decir:

Martha C. Moreno

´ QR FACTORIZACION

Como {Q1 , Q2 , · · · , Qn } es una base del espacio columna de A, entonces cada columna de A se puede expresar de manera u ´nica como una c.l de sus elementos, es decir: C1 = r11 Q1 + r21 Q2 + · · · + rn1 Qn

Martha C. Moreno

´ QR FACTORIZACION

Como {Q1 , Q2 , · · · , Qn } es una base del espacio columna de A, entonces cada columna de A se puede expresar de manera u ´nica como una c.l de sus elementos, es decir:

.. .

C1 = r11 Q1 + r21 Q2 + · · · + rn1 Qn C2 = r12 Q1 + r22 Q2 + · · · + rn2 Qn

Martha C. Moreno

´ QR FACTORIZACION

Como {Q1 , Q2 , · · · , Qn } es una base del espacio columna de A, entonces cada columna de A se puede expresar de manera u ´nica como una c.l de sus elementos, es decir:

.. .

C1 = r11 Q1 + r21 Q2 + · · · + rn1 Qn C2 = r12 Q1 + r22 Q2 + · · · + rn2 Qn Cn = r1n Q1 + r2n Q2 + · · · + rnn Qn

Martha C. Moreno

´ QR FACTORIZACION

Como {Q1 , Q2 , · · · , Qn } es una base del espacio columna de A, entonces cada columna de A se puede expresar de manera u ´nica como una c.l de sus elementos, es decir:

.. .

C1 = r11 Q1 + r21 Q2 + · · · + rn1 Qn C2 = r12 Q1 + r22 Q2 + · · · + rn2 Qn Cn = r1n Q1 + r2n Q2 + · · · + rnn Qn

De donde:

Martha C. Moreno

´ QR FACTORIZACION

Martha C. Moreno

´ QR FACTORIZACION

A = (C1

C2

···

Cn )

Martha C. Moreno

´ QR FACTORIZACION

A = (C1 A = (Q1

C2 Q2

··· ···

Cn )    Qn )  

r11 r12 · · · r21 r22 · · · .. .. .. . . . rn1 rn2 · · ·

Martha C. Moreno

r1n r2n .. . rnn

    

´ QR FACTORIZACION

A = (C1

C2

A = (Q1 A=Q

Q2 R

··· ···

Cn )    Qn )  

r11 r12 · · · r21 r22 · · · .. .. .. . . . rn1 rn2 · · ·

Martha C. Moreno

r1n r2n .. . rnn

    

´ QR FACTORIZACION

A = (C1 A = (Q1

C2 Q2

··· ···

Cn )    Qn )  

r11 r12 · · · r21 r22 · · · .. .. .. . . . rn1 rn2 · · ·

A=Q R Como la base es ortonormal entonces:  C1 • Q1 C2 • Q1 · · ·  C1 • Q2 C2 • Q2 · · ·  R= .. .. ..  . . . C1 • Qn C2 • Qn · · ·

Martha C. Moreno

r1n r2n .. . rnn

    

Cn • Q1 Cn • Q2 .. . Cn • Qn

´ QR FACTORIZACION

    

Como Ci • Qj = 0 si i < j, pues cada Qj es ortogonal a C1 , C2 , · · · , Cj−1 , entonces:

Martha C. Moreno

´ QR FACTORIZACION

Como Ci • Qj = 0 si i < j, pues cada Qj es ortogonal a C1 , C2 , · · · , Cj−1 , entonces: 

  R = 

C1 • Q1 C2 • Q1 · · · 0 C2 • Q2 · · · .. .. .. . . . 0 0 ···

Martha C. Moreno

Cn • Q1 Cn • Q2 .. . Cn • Qn

    

´ QR FACTORIZACION

Como Ci • Qj = 0 si i < j, pues cada Qj es ortogonal a C1 , C2 , · · · , Cj−1 , entonces: 

  R = 

C1 • Q1 C2 • Q1 · · · 0 C2 • Q2 · · · .. .. .. . . . 0 0 ···

Cn • Q1 Cn • Q2 .. . Cn • Qn

    

Matriz Triangular superior y no singular ¿Porqu´e?

Martha C. Moreno

´ QR FACTORIZACION

Como Ci • Qj = 0 si i < j, pues cada Qj es ortogonal a C1 , C2 , · · · , Cj−1 , entonces: 

  R = 

C1 • Q1 C2 • Q1 · · · 0 C2 • Q2 · · · .. .. .. . . . 0 0 ···

Cn • Q1 Cn • Q2 .. . Cn • Qn

    

Matriz Triangular superior y no singular ¿Porqu´e?

Note que: rij = Qi • Cj

Martha C. Moreno

´ QR FACTORIZACION

Nota Recuerde que: Para poder aplicar el proceso de factorizaci´on QR, la matriz debe tener columnas linealmente independientes.

Martha C. Moreno

´ QR FACTORIZACION

Nota Recuerde que: Para poder aplicar el proceso de factorizaci´on QR, la matriz debe tener columnas linealmente independientes. Es posible factorizar matrices no cuadradas.

Martha C. Moreno

´ QR FACTORIZACION

Nota Recuerde que: Para poder aplicar el proceso de factorizaci´on QR, la matriz debe tener columnas linealmente independientes. Es posible factorizar matrices no cuadradas. Teorema Si A es cuadrada no singular, entonces es factorizable QR, y la matriz Q es ortogonal.

Martha C. Moreno

´ QR FACTORIZACION

Ejemplo Sea A =



1 2 −1 3



Martha C. Moreno

´ QR FACTORIZACION

Ejemplo Sea A =



1 2 −1 3

Como las columnas es factorizable QR.





1 −1



y



Martha C. Moreno

2 3



son l.i, entonces la matriz

´ QR FACTORIZACION

Ejemplo Sea A =



1 2 −1 3

Como las columnas es factorizable QR.





1 −1



y



2 3



son l.i, entonces la matriz

Construimosuna base  ortonormal  a partir de la base: 1 2 B = {C1 = , C2 = } −1 3

Martha C. Moreno

´ QR FACTORIZACION

v1 = C1 =



1 −1



Martha C. Moreno

´ QR FACTORIZACION

v1 = C1 =



1 −1



v2 = C2 − proyv1 C2 =



2 3



−

Martha C. Moreno

−1 2



1 −1



=



´ QR FACTORIZACION

5 2 5 2



v1 = C1 =



1 −1



v2 = C2 − proyv1 C2 =



2 3



−

−1 2



1 −1



=



Normalizando: 

Q1 =



1 −1 √

2

 

=

√1 2 −1 √ 2

!

Martha C. Moreno

´ QR FACTORIZACION

5 2 5 2



v1 = C1 =



1 −1



v2 = C2 − proyv1 C2 =



2 3



−

−1 2



1 −1



=



Normalizando: 

Q1 =

 

Q2 =

1 −1 √

 

2 

5  2  5 2 √ 5 2 2

=

=

√1 2 −1 √ 2 √1 2 √1 2

!

!

Martha C. Moreno

´ QR FACTORIZACION

5 2 5 2



Entonces: Q=

Martha C. Moreno

√1 2 −1 √ 2

√1 2 √1 2

!

´ QR FACTORIZACION

Entonces: √1 2 −1 √ 2

Q=

R=



Q1 • C1 Q1 • C2 Q2 • C1 Q2 • C2



=

Martha C. Moreno

√1 2 √1 2

√ 2 0

!

√ − 2 2 √ 5 2 2

!

´ QR FACTORIZACION

Entonces: √1 2 −1 √ 2

Q=

R=

A=



Q1 • C1 Q1 • C2 Q2 • C1 Q2 • C2 √1 2 −1 √ 2

√1 2 √1 2

!

√ 2 0



=

√ − 2 2 √ 5 2 2

Martha C. Moreno

√1 2 √1 2

√ 2 0

!

√ − 2 2 √ 5 2 2

!

!

´ QR FACTORIZACION