Clase 1: Valores Propios y Vectores Propios =========================================== .. topic:: Bibliografía de la Clase: * Numerical Linear Algebra. L.N. Trefethen. Chapter 5, Lecture 24: ``Eigenvalue Problems`` * Introduction to Linear Algebra. Gilbert Strang. Chapter 6 ``Eigenvalues and Eigenvectors`` * Guía Profesor Luis Salinas Introducción ------------ Un breve recordatorio de valores y vectores propios: Sea `A \in \mathbb{C}^{m\times m}` una matriz cuadrada. Un vector `0 \neq x \in \mathbb{C}^m` es un **vector propio** (eigenvector) de `A`, y `\lambda \in \mathbb{C}` es su **valor propio** (eigenvalue) correspondiente, si: .. math:: Ax=\lambda x * La idea principal es que la transformación que aplica la matriz `A` en el subespacio `S` de `\mathbb{C}^m` puede algunas veces imitar una multiplicación por un escalar. * Cuando lo anterior sucede, el subespacio `S` es llamado **espacio propio** (eigenspace), y cualquier vector `0 \neq x \in S` es un vector propio. * El conjunto de valores propios de la matriz `A` se denomina **spectrum** de `A`, y es un subconjunto de `\mathbb{C}` y se denota `\Lambda(A)`. * Los valores y vectores propios son útiles por dos razones: algorítmica y física. * Algorítmicamente, el análisis de valores propios puede simplificar soluciones de ciertos problemas reduciendo un sistema acoplado a una colección de problemas escalares (por ej., encontrar la potencia `A^{100}`). * Físicamente, en análisis de valores propios puede ayudar a la resolución de sistemas que evolucionan que se rigen por ecuaciones lineales (por ej., estudio de la resonancia). Mayor detalle en `Valores y Vectores Propios `_ Ejercicio en clases 1.1 ~~~~~~~~~~~~~~~~~~~~~~~ Sea `A=\begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix}`. Obtener `A^{100}`. .. math:: \mathop{\begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix}}_{A} \rightarrow \mathop{\begin{bmatrix} 0.7 & 0.45 \\ 0.30 & 0.55 \end{bmatrix}}_{A^2} \rightarrow \mathop{\begin{bmatrix} 0.650 & 0.525 \\ 0.350 & 0.475 \end{bmatrix}}_{A^3} \ldots * El valor de `A^{100}` se puede encontrar usando los valores propios y no haciendo 100 multiplicaciones. * Primeramente, se deben encontrar los valores y vectores propios de `A`: `\lambda_1=1, \lambda_2=0.5` y `v_1=[0.6 \quad 0.4]^T, v_2=[1 \quad -1]^T`, son respectivamente sus valores y vectores propios. * Si se multiplica `Ax_{1}=x_{1}`, y con cada potencia de `A` se obtendrá `A^{n}x_1=x_1`. Al multiplicar `Ax_2=\frac{1}{2}x_2` y si se sigue multiplicando se obtiene `(\frac{1}{2})^2 \text{ veces } x_{2}`. * **Debido a que** `A` **tiene** `m` **valores propios distintos, por lo tanto,** `m` **vectores propios lindealmente independientes**, se puede encontrar la primera columna de `A^{100}` mediante una combinación lineal de los vectores propios: .. math:: A^{99}\begin{bmatrix} 0,8 \\ 0,2 \end{bmatrix} \equiv x_1 +(0,2) (\frac{1}{2})^{99}x_2 = \begin{bmatrix} 0,6 \\ 0,4 \end{bmatrix} + \begin{bmatrix} 0,000 \ldots \\ 0,000 \ldots \end{bmatrix} Lo mismo para la segunda columna de `A^{100}`, por lo tanto: .. math:: A^{100} = \begin{bmatrix} 0,6 & 0,6\\ 0,4 &0,4 \end{bmatrix} .. note:: La matriz `A` anterior es una **Matriz de Markov**. Todas sus entradas son positivas y los elementos de cada columna suman 1. Esto garantiza que el mayor valor propio es 1 lo que indica que el el vector propio no cambia su estado (porque `\lambda=1`) y por lo tanto el otro vector propio decae, hasta desaparecer, mientras mayor sea la potencia de `A`. Revisar `Ejercicio Propuesto `_ Descomposición de Valores Propios --------------------------------- La descomposición de valores propios de una matriz cuadrada `A`, es la factorización: .. math:: A=X \Lambda X^{-1} Esta factorización, no siempre existe. `X` es no singular y `\Lambda` es diagonal. Esta factorización puede también ser escrita como: .. math:: \begin{bmatrix} \quad & \quad & \quad\\ \quad & A & \quad\\ \quad & \quad & \quad \end{bmatrix} \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ x_1 & x_2 & \cdots & x_m \\ \, & \, & \, & \, \end{array} \right]= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ x_1 & x_2 & \cdots & x_m \\ \, & \, & \, & \, \end{array} \right] \begin{bmatrix} \lambda_1 & \, & \, & \, \\ \, & \lambda_2 & \, & \, \\ \, & \, & \ddots & \, \\ \, & \, & \, & \lambda_m \end{bmatrix} En una notación más resumida: .. math:: A X = X \Lambda Transformación de Similitud ---------------------------- Si `X \in \mathbb{C}^{m\times m}` es no singular, entonces la transformación `A \rightarrow X^{-1}AX` se denomina **transformación de similitud** de `A`. Se dice que dos matrices `A` y `B` son similares si hay una transformación de similitud que las relacione, es decir, si existe una matriz `X \in \mathbb{C}^{m\times m}` no singular tal que: .. math:: B=X^{-1}AX Matrices Deficientes y Diagonalización -------------------------------------- En general, una matriz tiene multiplicidades geométrica y algebraica iguales, pero no ocurre **para todas** las matrices. Si se consideran las siguientes matrices: .. math:: A=\begin{bmatrix} 2 & & \\ &2 & \\ & &2 \end{bmatrix}, \ \ B=\begin{bmatrix} 2 &1 & \\ &2 &1 \\ & &2 \end{bmatrix} Ambas matrices tienen polinomios característicos `(z-2)^3`, por lo tanto, hay un solo valor propio `\lambda=2` que tiene multiplicidad algebraica 3. Para la matriz `A` se pueden escoger tres vectores propios independientes, por ejemplo, `e_1, e_2` y `e_3`, por lo tanto la multiplicidad geométrica también es 3. Para la matriz `B`, se puede encontrar solo un vector propio independiente (`e_1`), por lo tanto la multiplicidad geométrica del valor propio es 1. Un valor propio cuya multiplicidad algebraica excede su multiplicidad geométrica se dice que es un **valor propio deficiente**. Una matriz que tiene uno o más valores propios deficientes se denomina **matriz deficiente**. Toda matriz diagonal es **no deficiente**. En estas matrices, la multiplicidad algebraica y geométrica de un valor propio `\lambda` son iguales al número de ocurrencias en la diagonal. La clase de matrices no deficientes son precisamente la clase de matrices que tienen una descomposición de valores propios. En otras palabras las matrices no deficientes son **diagonalizables**. La `diagonalización de matrices `_ corresponde a una transformación de similitud. .. note:: De CC1: La **multiplicidad geométrica** corresponde a la dimensión del subespacio propio generado por el valor propio `\lambda` (o al número de vectores propios l.i. asociado a `\lambda`). La **multiplicidad algebraica** corresponde al número de veces que aparece el valor propio `\lambda` como raíz de la ecuación característica de A. **¿Para que es útil la diagonalización?** Nuevamente consideremos `A^k`: .. math:: Ax = \lambda x \ \ /\times A A^x = \lambda^2 x \ldots A^k = X \Lambda^k X^{-1} Ejercicio 1.2. Números de Fibonacci ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1. Hallar el número de Fibonacci `F_{100}`. Los números de Fibonacci está formada por los números: `0,1,1,2,3,5,8,13,21 \ldots`. Se definen recursivamente como: .. math:: F_{k+2} = F_{k+1} + F_{k} Pero se quisiera lograr una ecuación de la forma: .. math:: u_{k+1}= A u_{k} para usar las ventajas de los valores y vectores propios. Como `A` tiene `m` valores propios distintos (por lo tanto `m` vectores propios, `x_i,` l.i.) y `u_{0}` **es conocido** (condición inicial): .. math:: u_0= c_1 x_1 + \ldots c_n x_n \ \ \ /\times A A u_0 = c_1 A x_1 + \ldots c_n A x_n A u_0 = c_1 \lambda_1 x_1 + \ldots c_n \lambda_n x_n \ldots A^k u_{0} = c_1 \lambda_1^k x_1 + \ldots c_n \lambda_n^k x_n A^k u_{0} = \Lambda X c \ , \ \ \ c=\begin{bmatrix} c_1 \\ \ldots \\ c_n \end{bmatrix} Tomando en cuenta lo anterior, se puede usar el ``truco``: `u_{k}=\begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix}`. Con esta definición se puede construir el siguiente sistema: .. math:: \begin{array}{lll} F_{k+2} &= &F_{k+1} +F_{k} \\ F_{k+1} & =&F_{k+1} \end{array} u_{k+1}=A u_{k} \Leftrightarrow u_{k+1} = A \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix}=\begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix} por lo tanto `A` es: .. math:: A= \begin{bmatrix} 1 &1\\ 1 &0 \end{bmatrix} \Rightarrow u_{k+1}=\begin{bmatrix} 1 &1\\ 1 &0 \end{bmatrix} u_{k} Si se calculan los valores y vectores propios: .. math:: \lambda_1 = \frac{1+\sqrt{5}}{2}, \ \ \lambda_2 = \frac{1-\sqrt{5}}{2} x_{1} = \begin{bmatrix} \lambda_{1} \\ 1 \end{bmatrix}, \ \ x_{2} = \begin{bmatrix} \lambda_{2} \\ 1 \end{bmatrix} Recapitulando, si se usa la ecuación `u_{k}=A^k u_{0}`: .. math:: u_1 = A u_{0} \ \ u_2= A u_1 = A^2 u_0 \ldots u_k= A^k u_0 para encontrar `F_{100}`: .. math:: u_{100} = A^{100} u_0, \text{ y } u_{0}=\begin{bmatrix} 1 \\ 0 \end{bmatrix} = c_1 x_1 + c_2 x_2= \frac{1}{\lambda_1 - \lambda_2} x_1 - \frac{1}{\lambda_1 - \lambda_2} x_2 = \frac{x_1 - x_2}{\lambda_1 - \lambda_2} por lo tanto, .. math:: u_{100} = A^{100} \frac{x_1 - x_2}{\lambda_1 - \lambda_2} = \frac{\lambda_{1}^{100} x_1- \lambda_{2}^{100} x_2}{\lambda_1 - \lambda_2} = \begin{bmatrix}F_{101} \\ F_{100} \end{bmatrix} Interesa el segundo componente de `u_{100}`: .. math:: u_{100}=& \begin{bmatrix} \frac{\lambda_{1}^{100} x_1}{\lambda_1 - \lambda_2} - \frac{\lambda_{2}^{100} x_2}{\lambda_1 - \lambda_2} \end{bmatrix} \\ =& \ldots \rightarrow F_{100} = \frac{1}{\sqrt{5}} \left[\left( \frac{1 + \sqrt{5}}{2} \right)^{100} - \left( \frac{1 - \sqrt{5}}{2} \right)^{100}\right] \approx 3,54 \times 10^{20} Factorizaciones que Revelan Valores Propios ------------------------------------------- .. math:: A \text{ no deficiente } \Leftrightarrow A \text{ diagonalizable, i.e. } \exists X \text{ invertible con } A = X \Lambda X^{-1} A \text{ es normal } \Leftrightarrow A \text{ unitariamente diagonalizable, i.e. } \exists U \text{ unitaria con } A = U \Lambda U^{*} A \text{ arbitraria } \Leftrightarrow A \text{ unitariamente triangularizale, i.e. } \exists U \text{ unitaria con } A = U T U^{*} .. note:: Sea `A \in \mathbb{C}^{m\times m}` una matriz **normal**, es decir, `AA^* = A^*A`, donde `A^*` denota la matriz hermitiana adjunta de `A`. Las matrices normales poseen un sistema completo de valores y vectores propios, es decir, tienen `n` valores propios `\lambda_i \in \mathbb{C}`, a cada valor propio `\lambda_i` le corresponde exactamente un vector propio `V_i`, y el sistema de los `n` vectores propios es un sistema ortogonal completo, i.e., constituye una base ortogonal de `\mathbb{C}^{n}`. Teorema de Gerschgorin ---------------------- El teorema de Gerschgorin es un resultado muy útil que permite estimar bastante bien los valores propios de una matriz simétrica o no simétrica. .. topic:: Teorema: Sea `A=[a_{ij}] \in C^{n \times n}`, una matriz cualquiera. Entonces todo valor propio de `A` está en a lo menos un disco del plano complejo `\mathbb{C}` centrado en `a_{ii}` y con radio `R_i=\sum_{j=1, \ j\neq i}^{n} | a_{ij}|, \ i=1\ldots n`: .. math:: \{\lambda \in \mathbb{C}: \lambda \text{ es un valor propio de } A \subseteq \cup \{ z \in \mathbb{C}: | z - a_{ii} | \leq R_i \} Además, Si `k` de estos `n` discos forman un dominio **conexo disjunto** de los restantes `n-k` discos, entonces hay precisamente `k` valores propios en ese dominio conexo. .. note:: Un dominio es conexo si cualquier par de puntos en el dominio puede ser conectado por una curva que está completamente contenida en el dominio. **Ejemplo** Para `A=\begin{bmatrix} 1 &2 &3 \\ 3 &4 &9 \\ 1 &1 &1 \end{bmatrix}` .. image:: _static/test.png :scale: 50 :alt: Gerschgorin :align: center Demostración ~~~~~~~~~~~~ Sea `\lambda` un valor propio de `A` y `x \neq 0` su correspondiente vector propio, i.e., `Ax=\lambda x`. .. math:: x \neq 0 \rightarrow \text{ sea } x_{p} \text{ la componente de mayor valor absoluto:} |x_p| \geq |x_i| \forall i=1 \ldots n, \ x_p\neq 0 Entonces la p-ésima ecuación del sistema `Ax=\lambda x` se puede escribir de la forma: .. math:: Ax=\lambda x \Rightarrow \lambda x_p = \sum_{j=1}^{n}a_{pj}x_j = a_{pp}x_{p} + \sum_{j=1,j\neq p}^{n} a_{pj}x_j \Rightarrow x_p(\lambda - a_{pp}) = \sum_{j=1,j\neq p}^{n} a_{pj}x_j \Rightarrow |x_p|\ | (\lambda - a_{pp}) | = | \sum_{j=1,j\neq p}^{n} a_{pj}x_j | = | a_{p1}x_1 + \ldots + a_{pn}x_n| \leq | a_{p1}x_1 | + \ldots + | a_{pn}x_n| = \sum_{j=1,j\neq p}^{n} | a_{pj}x_j | por lo tanto: .. math:: |x_p|\ | (\lambda - a_{pp}) | \leq \sum_{j=1,j\neq p}^{n} | a_{pj}| \ | x_j | y si dividimos por `|x_p|` y utilizamos la consideración `\ |x_p| \geq |x_i| \ \forall j=1 \ldots n`: .. math:: | (\lambda - a_{pp}) | \leq \sum_{j=1,j\neq p}^{n} | a_{pj}| \ | x_j | / | x_p| \leq \sum_{j=1,j\neq p}^{n} | a_{pj}| = R_{p} \Rightarrow | (\lambda - a_{pp}) | \leq R_{p} Luego `\lambda` está contenido en el disco `\{ \lambda: | \lambda - a_pp| \leq R_p\}`. Ejercicio en Clases 1.3 ~~~~~~~~~~~~~~~~~~~~~~~ * Sea `A= \begin{bmatrix} 2 &1/2 &0 &0 \\ -1/2 &3 &i/2 &0 \\ 0 &-i/2 &4-5i &e^{i\theta}/4 \\ 0 & 0 &e^{-i\theta}/4 &5+5i \end{bmatrix}`. Determinar gráficamente los valores propios. Se debe calcular los centros y radios de los discos de Gerschgorin: .. math:: a_{11} = 2 + 0i \ \ \ a_{22}=3 +0i \ \ \ a_{33}=4-5i \ \ \ a_{44}=5+5i R_1= \frac{1}{2} \ \ \ R_2= | \frac{-1}{2} | + | \frac{-i}{2} | =1 \ \ \ R_3=\frac{3}{4} \ \ \ R_{4}= \frac{1}{4} Ejercicio Propuesto ################### 1. Sea `Q=\begin{bmatrix} 0 &1 \\ -1 &0 \end{bmatrix}` una matriz de rotación. Calcular valores y vectores propios y explicar claramente que ocurre en esta situación. **Hint:** Revisar Ejemplo 5, Capítulo 6: Eigenvalues and Eigenvectors, del libro "Introduction to Linear Algebra", Gilbert Strang, Fourth Edition.