1
Download Álgebra Lineal Ma1010
Document related concepts
Transcript
Álgebra Lineal Ma1010 Factorización QR Departamento de Matemáticas ITESM Factorización QR Álgebra Lineal - p. 1/16 Introducción En esta lectura veremos el proceso para obtener la factorización QR de una matriz. Esta factorización es utilizada para la solución por mínimos cuadrados y da un algoritmo numérico para determinar los valores propios de una matriz cuadrada. Factorización QR Introducción Factorización QR Algoritmo QR Álgebra Lineal - p. 2/16 Factorización QR Teorema Introducción Factorización QR Algoritmo QR Si A es una matriz m × n con columnas linealmente independientes, entonces A puede factorizarse en la forma A = QR en la que Q es una matriz con columnas ortonormales y R es una matriz triangular superior. Factorización QR Álgebra Lineal - p. 3/16 Factorización QR Teorema Introducción Factorización QR Algoritmo QR Si A es una matriz m × n con columnas linealmente independientes, entonces A puede factorizarse en la forma A = QR en la que Q es una matriz con columnas ortonormales y R es una matriz triangular superior. Demostración Sean a1 ,a2 ,. . . ,an las columnas de A y sean q1 ,q2 ,. . . ,qn los vectores obtenidos al ortonormalizarlas según el proceso de Gram-Schmidt. Así, Gen(a1 , a2 , . . . , an ) = Gen(q1 , q2 , . . . , qn ) Factorización QR Álgebra Lineal - p. 3/16 Definamos Q = [q1 q2 · · · qn ] Introducción Factorización QR Algoritmo QR Como cada ai es combinación lineal de q1 ,. . . ,qn deben existir escalares rij tales que r1i .. ai = r1i q1 +· · ·+rni qn = Q . para i = 1, . . . , n rni siendo rji = 0 para j = i + 1, . . . , n y para i = 1, . . . n, de acuerdo al proceso de Gram-Schmidt. Factorización QR Álgebra Lineal - p. 4/16 Definamos Introducción Factorización QR Algoritmo QR Q = [q1 q2 · · · qn ] Como cada ai es combinación lineal de q1 ,. . . ,qn deben existir escalares rij tales que r1i .. ai = r1i q1 +· · ·+rni qn = Q . para i = 1, . . . , n rni siendo rji = 0 para j = i + 1, . . . , n y para i = 1, . . . n, de acuerdo al proceso de Gram-Schmidt. Así, r1n r11 A = [a1 · · · an ] = Q ... · · · Q ... = QR 0 Factorización QR rnm Álgebra Lineal - p. 4/16 donde R es la matriz cuyo elemento (i, j) es rij . Las matrices buscadas son las matrices Q y R: Q tiene sus columnas ortonormales y R es triangular superior. Asimismo R debe ser invertible pues en caso contrario Rx = 0 tendría infinitas soluciones y por ende también QRx = Ax = 0 contradiciendo el hecho de que las columnas de A son linealmente independientes. Factorización QR Introducción Factorización QR Algoritmo QR Álgebra Lineal - p. 5/16 donde R es la matriz cuyo elemento (i, j) es rij . Las matrices buscadas son las matrices Q y R: Q tiene sus columnas ortonormales y R es triangular superior. Asimismo R debe ser invertible pues en caso contrario Rx = 0 tendría infinitas soluciones y por ende también QRx = Ax = 0 contradiciendo el hecho de que las columnas de A son linealmente independientes. Introducción Factorización QR Algoritmo QR Nota En la práctica la matriz R se calcula mediante la fórmula: R = QT · A Factorización QR Álgebra Lineal - p. 5/16 Ejemplo Determine una factorización QR para la matriz 1 −2 1 A = −1 3 2 1 −1 −4 Factorización QR Introducción Factorización QR Algoritmo QR Álgebra Lineal - p. 6/16 Ejemplo Determine una factorización QR para la matriz 1 −2 1 A = −1 3 2 1 −1 −4 Introducción Factorización QR Algoritmo QR Solución Al aplicarle el proceso de Gram-Schmidt a las columnas de A obtenemos: 2 1 √ √ 0 3 6 √1 √1 √1 q1 = − 3 , q2 = 2 , q3 = 6 √1 √1 √1 − 2 3 6 Factorización QR Álgebra Lineal - p. 6/16 Por tanto Q= Factorización QR √1 3 − √13 √1 3 0 √1 2 √1 2 √2 6 √1 6 − √16 Introducción Factorización QR Algoritmo QR Álgebra Lineal - p. 7/16 Por tanto Q= y √1 3 − √13 √1 3 √ R = QT · A = Factorización QR 0 √1 2 √1 2 √2 6 √1 6 − √16 Introducción Factorización QR Algoritmo QR √ √ 5 3 −2 3 − 3 3 √ √ 2 −2 3 0 √ 1 0 0 3 96 Álgebra Lineal - p. 7/16 Los cálculos anteriores pueden hacerse en la calculadora TI. Si seleccionamos el modo exacto, definimos la matriz A y aplicamos la rutina de factorización QR tendremos la salida de la figura 1 Introducción Factorización QR Algoritmo QR Figura 1: Ejemplo 1: cálculo de la factorización QR de A. Factorización QR Álgebra Lineal - p. 8/16 La figura 2 despliega la matriz Q calculada. Introducción Factorización QR Algoritmo QR Figura 2: Ejemplo 1: Matriz Q de la factorización QR de A. Factorización QR Álgebra Lineal - p. 9/16 La figura 3 despliega la matriz R calculada. y la comprobación de que el producto efectivamente da A. Introducción Factorización QR Algoritmo QR Figura 3: Ejemplo 1: Matriz R de la factorización QR de A. Factorización QR Álgebra Lineal - p. 10/16 La figura 4 muestra la comprobación de que el producto efectivamente da A. Introducción Factorización QR Algoritmo QR Figura 4: Ejemplo 1: Comprobación de la factorización QR de A. Factorización QR Álgebra Lineal - p. 11/16 Algoritmo QR Para una matriz A n × n invertible, cuyos valores propios λ1 , . . . , λn son tales que Introducción Factorización QR Algoritmo QR |λ1 | < |λ2 | < · · · < |λn | Hacer: 1. Tomar A0 = A. 2. Para i = 0, 1, 2, . . . , k − 1 hacer: a) Determinar la descomposición QR de A i = Q i Ri . b) Tomar Ai+1 = Ri Qi Resultado: Ak se aproxima a una matriz triangular cuyos elementos diagonales son todos los valores propios de A. Factorización QR Álgebra Lineal - p. 12/16 Ejemplo Aplique el algoritmo QR a la matriz: " # 8 7 A= 1 2 Factorización QR Introducción Factorización QR Algoritmo QR Álgebra Lineal - p. 13/16 Ejemplo Introducción Factorización QR Algoritmo QR Aplique el algoritmo QR a la matriz: " # 8 7 A= 1 2 Solución Tomamos A0 = A. Determinamos una factorización QR de A0 : 0.9922 −0.1240 8.0622 7.1940 · A 0 = Q 0 R0 = 0.1240 0.9922 0.0000 1.1163 A 1 = R0 Q 0 = Factorización QR 8.8923 0.1384 6.1384 1.1076 Álgebra Lineal - p. 13/16 Determinamos una factorización QR de A1 : 8.8933 0.9998 −0.1556 · A 1 = Q 1 R1 = 0.0155 0.9998 0.0000 A 2 = R1 Q 1 = Factorización QR 8.9881 0.0157 6.0157 1.0118 6.1549 1.0119 Introducción Factorización QR Algoritmo QR Álgebra Lineal - p. 14/16 Determinamos una factorización QR de A1 : 8.8933 0.9998 −0.1556 · A 1 = Q 1 R1 = 0.0155 0.9998 0.0000 A 2 = R1 Q 1 = 8.9881 0.0157 6.0157 1.0118 A 3 = R2 Q 2 = 8.9986 0.0017 6.0107 1.0013 1.0119 6.0175 1.0013 Determinamos una factorización QR de A2 : 0.9999 −0.0017 8.9881 A 2 = Q 2 R2 = · 0.0017 0.9999 0.0000 6.1549 Introducción Factorización QR Algoritmo QR Concluimos que los valores propios de A son aproximadamente 9 y 1. Factorización QR Álgebra Lineal - p. 14/16 Las figuras 5,6 y 7 muestran la sucesión de cálculos del algorimto QR para aproximar los valores propios de A. Introducción Factorización QR Algoritmo QR Figura 5: Ejemplo 2: Iteración 1 del algoritmo QR. Factorización QR Álgebra Lineal - p. 15/16 Introducción Factorización QR Algoritmo QR Figura 6: Ejemplo 2: Iteraciones 2 y 3 del algoritmo QR. Factorización QR Álgebra Lineal - p. 16/16
