************************************************************** Clase 2: Algoritmos de Valores propios ************************************************************** .. topic:: Bibliografía de la Clase: * Numerical Linear Algebra.L.N. Trefethen. Chapter 5: Lecture 25 ``Overview of Eigenvalue Algorithms`` * Introduction to Linear Algebra. Gilbert Strang. Chapter 6 ``Eigenvalues and Eigenvectors`` * Guía profesor Luis Salinas Alternativa 1: Polinomio característico ####################################### La primera idea para el cálculo de los valores y vectores propios de una matriz `A` es encontrar su polinomio característico, cuyas raíces son los valores propios, para luego proceder a encontrar sus respectivos vectores propios. La imagen mostrada corresponde a el polinomio cuyas raíces son `\lambda_i=i , \quad \forall i=1:20`. Se ve claramente que es un problema mal condicionado, debido a que el polinomio encontrado es muy sensible a sus coeficientes. Es decir, hemos transformado un problema bien condicionado, en uno mal condicionado. .. image:: _static/Wilkinson_polynomial.png :align: center :scale: 30 :alt: caption .. topic:: Problema La búsqueda de raíces en un polinomio, es un problema mal condicionado (ver `Clase Condicionamiento CC1 `_). Por otro lado, se sabe del Algebra que no existe una fórmula para determinar los ceros de un polinomio arbitrario de grado `m \geq 5` a partir de sus coeficientes. Lo anterior muestra que no es posible expresar las raíces de un polinomio como una expresión algebraica y por lo tanto la única forma de obtenerlos es de forma iterativa (con un número infinito de pasos). .. note:: La fórmula para resolver ecuaciones de segundo grado ya era conocida por los antiguos babilonios. Fibonacci a principios del siglo XIII encontró solución a la ecuación de tercer grado `x^3 + 2x^2 +10x =20` y Scipione del Ferro, Niccolò Tartaglia y Gerolamo Cardano generalizaron la formulación. Ludovico Ferrari, discípulo de Cardano en el siglo XVI expresó la solución para ecuaciones de cuarto grado. Alternativa 2: Método de Iteración de Potencia ############################################## Este método consiste en construir una secuencia que converge al vector propio `\mathbf{v}_1` que corresponde al mayor valor propio en valor absoluto `\lambda_1`. La secuencia es la siguiente: .. math:: \frac{\mathbf{x}}{\|\mathbf{x}\|}, \; \frac{\mathbf{Ax}}{\|\mathbf{Ax}\|}, \; \frac{\mathbf{A}^2\mathbf{x}}{\|\mathbf{A}^2\mathbf{x}\|}, \; \frac{\mathbf{A}^3\mathbf{x}}{\|\mathbf{A}^3\mathbf{x}\|}, \dots \approx \mathbf{v}_1 **¿Porqué funciona?** Si escribimos `\mathbf{x}` como una combinación lineal de los vectores propios se tiene: .. math:: \mathbf{x} = \alpha_1 \mathbf{v}_1 + \dots + \alpha_m \mathbf{v}_m Al multiplicar sucesivamente por `\mathbf{A}` se tiene que el vector propio `\mathbf{v}_1` es el que predomina la sucesión y por lo tanto la sucesión converge a él: .. math:: \mathbf{A} \mathbf{x} =& \alpha_1 \mathbf{A} \mathbf{v}_1 + \dots + \alpha_m \mathbf{A} \mathbf{v}_m \\ =& \alpha_1 \lambda_1 \mathbf{v}_1 + \dots + \alpha_m \lambda_m \mathbf{v}_m \\ \mathbf{A^2} \mathbf{x} =& \alpha_1 \lambda_1 \mathbf{A} \mathbf{v}_1 + \dots + \alpha_m \lambda_m \mathbf{A} \mathbf{v}_m \\ =& \alpha_1 \lambda_1^2 \mathbf{v}_1 + \dots + \alpha_m \lambda_m^2 \mathbf{v}_m \\ \vdots \\ \mathbf{A^k} \mathbf{x} =& \alpha_1 \lambda_1^k \mathbf{v}_1 + \dots + \alpha_m \lambda_m^k \mathbf{v}_m .. topic:: Problemas El método es muy lento y presenta problemas cuando hay más de un valor propio con módulo máximo (ej: números complejos `1+i,1-i`). Hay problemas también si se elige un vector de partida `x` que no sea combinación lineal del vector `v_1`. Otras Alternativas ################## Los mejores algoritmos para valores propios están basados en un principio distinto: **calcular factorizaciones de A que revelen sus factores propios**. Una de las factorizaciones que revelan valores propios (ver `Clase 1 `_ ) es llamada la **Descomposición de Schur**, que existe para toda matriz y permite encontrar una triangularización unitaria. La estrategia para construir estas factorizaciones consiste en aplicar una secuencia de transformaciones a `\mathbf{A}` para introducir ceros donde se requiera. Descomposición de Schur ####################### La descomposición de Schur de una matriz `\mathbf{A}` tiene la siguiente definición: .. topic:: Factorización de Schur `\mathbf{A}=\mathbf{QTQ}^*` donde `\mathbf{Q}` es unitaria y `\mathbf{T}` es una matriz triangular superior. Teorema ------- Toda matriz `A` tiene una descomposición de Schur, incluso las matrices deficientes. Demostración ------------ Digamos que `\mathbf{x}` es un vector propio cualquiera de la matriz `\mathbf{A}` con `\lambda` como su correspondiente valor propio. Definir la matriz unitaria `\mathbf{U}` tenga como primera columna el vector `\mathbf{x}`. .. math:: \mathbf{U} = \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ x & u_2 & \cdots & u_m \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] Si ahora construimos `\mathbf{U}^* \mathbf{A} \mathbf{U}` se tiene: .. math:: \mathbf{U}^* \mathbf{A} \mathbf{U} = \left[ \begin{array}{ccc} \, & \mathbf{x}^* & \, \\ \hline \, & \mathbf{u}_2^* & \, \\ \hline \, & \vdots & \, \\ \hline \, & \mathbf{u}_m^* & \, \end{array} \right] \left[ \begin{array}{c|c|c} \, & \, & \, \\ \, & \, & \, \\ a_1 & \cdots & a_m \\ \, & \, & \, \\ \, & \, & \, \end{array} \right] \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ x & u_2 & \cdots & u_m \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] Al multiplicar se tiene: .. math:: \mathbf{U}^* \mathbf{A} \mathbf{U} = \left[ \begin{array}{c|ccc} \lambda & x^*.A.u_2 & \dots & x^*.A.u_m \\ \hline 0 & u_2^*.A.u_2 & \dots & u_2^*.A.u_m \\ \vdots & \vdots & & \vdots \\ 0 & u_m^*.A.u_2 & \dots & u_m^*.A.u_m \end{array} \right] = \left[ \begin{array}{c|c} \lambda & \mathbf{B} \\ \hline \mathbf{0} & \mathbf{C} \end{array} \right] Por hipótesis inductiva, la matriz `\mathbf{C}` también tiene descomposición de Schur, por lo tanto: .. math:: \mathbf{C} = \mathbf{V} \mathbf{T} \mathbf{V}^* Entonces, como: .. math:: \mathbf{U}^* \mathbf{A} \mathbf{U} =& \left[ \begin{array}{c|c} \lambda & \mathbf{B} \\ \hline \mathbf{0} & \mathbf{C} \end{array} \right] \\ =& \left[ \begin{array}{c|c} \lambda & \mathbf{B} \\ \hline \mathbf{0} & \mathbf{V} \mathbf{T} \mathbf{V}^* \end{array} \right] =& \left[ \begin{array}{c|c} 1 & \mathbf{0} \\ \hline \mathbf{0} & \mathbf{V} \end{array} \right] \left[ \begin{array}{c|c} \lambda & \mathbf{BV} \\ \hline \mathbf{0} & \mathbf{T} \end{array} \right] \left[ \begin{array}{c|c} 1 & \mathbf{0} \\ \hline \mathbf{0} & \mathbf{V}^* \end{array} \right] \\ equivalentemente se tiene que: .. math:: \left[ \begin{array}{c|c} 1 & \mathbf{0} \\ \hline \mathbf{0} & \mathbf{V}^* \end{array} \right] \mathbf{U}^* \mathbf{A} \mathbf{U} \left[ \begin{array}{c|c} 1 & \mathbf{0} \\ \hline \mathbf{0} & \mathbf{V} \end{array} \right] =\left[ \begin{array}{c|c} \lambda & \mathbf{BV} \\ \hline \mathbf{0} & \mathbf{T} \end{array} \right] Ahora sólo basta definir `\mathbf{Q}` como: .. math:: \mathbf{Q}=\mathbf{U} \left[ \begin{array}{c|c} 1 & \mathbf{0} \\ \hline \mathbf{0} & \mathbf{V} \end{array} \right] Finalmente se tiene que: .. math:: \mathbf{Q}^* \mathbf{A} \mathbf{Q} = \left[ \begin{array}{c|c} \lambda & \mathbf{BV} \\ \hline \mathbf{0} & \mathbf{T} \end{array} \right] que es de forma triangular superior. De manera más general la descomposición de Schur se obtiene transformando `\mathbf{A}` con una secuencia de transformaciones del tipo `\mathbf{X} \to \mathbf{Q}_j^*\mathbf{X}\mathbf{Q}_j` de manera que el producto .. math:: \mathbf{Q}_j^* \dots \mathbf{Q}_2^*\mathbf{Q}_1^*\mathbf{X}\mathbf{Q}_1\mathbf{Q}_2 \dots \mathbf{Q}_j converge a una matriz triangular superior `\mathbf{T}` cuando `j \to \infty`. Dos fases para la factorización de Schur ######################################## El procedimiento anterior se realiza generalmente en dos fases: 1. Primero se produce una matriz de Hessenberg `\mathbf{H}` que contiene ceros debajo de la primera subdiagonal. 2. Luego se realiza una iteración infinita de matrices de Hessenber para converger a una matriz triangular superior. .. math:: \mathop{\left[ \begin{array}{ccccc} \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \end{array} \right]}_{\mathbf{A}} \mathop{\xrightarrow{\hspace*{1cm}}}^{Fase 1} \mathop{\left[ \begin{array}{c c c c c} \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \, & \times & \times & \times & \times \\ \, & \, & \times & \times & \times \\ \, & \, & \, & \times & \times \\ \end{array} \right]}_{\mathbf{H}} \mathop{\xrightarrow{\hspace*{1cm}}}^{Fase 2} \mathop{\left[ \begin{array}{c c c c c} \times & \times & \times & \times & \times \\ \, & \times & \times & \times & \times \\ \, & \, & \times & \times & \times \\ \, & \, & \, & \times & \times \\ \, & \, & \, & \, & \times \\ \end{array} \right]}_{\mathbf{T}} Si a es hermitiana, la matriz de Hessenberg resulta tridiagonal y el resultado final es una matriz diagonal que contiene los valores propios: .. math:: \mathop{\left[ \begin{array}{ccccc} \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ \end{array} \right]}_{\mathbf{A}=\mathbf{A}^*} \mathop{\xrightarrow{\hspace*{1cm}}}^{Fase 1} \mathop{\left[ \begin{array}{c c c c c} \times & \times & \, & \, & \, \\ \times & \times & \times & \, & \, \\ \, & \times & \times & \times & \, \\ \, & \, & \times & \times & \times \\ \, & \, & \, & \times & \times \\ \end{array} \right]}_{\mathbf{H}} \mathop{\xrightarrow{\hspace*{1cm}}}^{Fase 2} \mathop{\left[ \begin{array}{c c c c c} \times & \, & \, & \, & \, \\ \, & \times & \, & \, & \, \\ \, & \, & \times & \, & \, \\ \, & \, & \, & \times & \, \\ \, & \, & \, & \, & \times \\ \end{array} \right]}_{\mathbf{T}} Ejercicio propuesto ------------------- 1. Encontrar la descomposición de Schur de la siguiente matriz: .. math:: \begin{bmatrix} 7 & -2 \\ 12 & -3 \end{bmatrix} .. 1. Demostrar que los valores propios de una matriz hermitiana son números .. reales y que sus vectores propios correspondientes a dos valores propios .. distintos son ortogonales entre si.