Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
Análisis Numérico y Programación (2022) PRACTICA 11 Cálculo numérico de autovalores y autovectores. Teorema de Gerschgorin. De acuerdo al teorema de Gerschgorin, los autovalores de una matriz A de n× n están contenidos en la unión de los círculos del plano complejo C dados por |z − aii| ≤ ri, donde ri = n∑ j=1 j 6=i |aij |, para i = 1, 2, . . . , n. Además, la unión de cualesquiera k de estos círculos que no intersecten a los (n − k) restantes, debe contener precisamente k (contando multiplicidades) autovalores. Ejercicio 1. Utilizar el teorema de Gerschgorin para localizar los autovalores de las siguientes matrices y determinar una cota del radio espectral ρ(A) = max1≤i≤n {|λi|}, 4 1 10 2 1 −2 0 9 , 5 1 10 6 1 1 0 −5 , 3 2 12 3 0 1 0 3 . Métodos de factorización. Los algoritmos que proveen aproximaciones a todos los autovalores de una matriz constan, en general, de tres pasos: (1) transformar la matriz original (densa) a una forma condensada por transformaciones de semejanza orto- gonales (y por lo tanto, con los mismos autovalores). Típicamente, una matriz simétrica es reducida a una matriz tridiagonal, y una matriz general a una matriz de Hessenberg superior ; (2) solución del problema de autovalores para la matriz condensada; (3) obtención de los autovectores de la matriz original aplicando la transformación inversa a los autovectores de la matriz condensada. Para el paso (1) existen métodos que efectúan la transformación en un número finito de pasos. Para el paso (2) los métodos de factorización, como el método QR, son métodos iterativos eficien- tes para resolver el problema. La utilidad de esta estrategia resulta del hecho de que la manipulación computacional de una matriz condensada requiere de mucha menos operaciones que las correspondientes a una matriz densa. En vez de programar nuestras propias subrutinas utilizaremos una biblioteca o librería de rutinas cono- cida como lapack junto con su interface lapack95, la cual explota las características propias del For- tran 95 (asignación dinámica de memoria, arreglos de tamaño ajustable en la lista de argumentos y argumen- tos opcionales). lapack es una colección de rutinas para resolver numéricamente problemas matemáticos que se enmarcan en el campo del álgebra lineal. En particular para el problema de autovalores incluye diversas rutinas aunque aquí sólo consideraremos dos subrutinas de propósito general proporcionadas por lapack95. A saber, la_syev y la_geev, para ma- trices simétricas reales y generales, respectivamente. Tales subrutinas implementan todos los pasos men- cionados anteriormente en la solución del problema de autovalores. La cuestión de utilizar las rutinas de lapack95 consta de dos partes: cómo llamar a las subrutinas en nuestro programa, y como compilar el mismo. A continuación discutimos éstos dos puntos. La invocación de las rutinas de lapack95 requie- re de la invocación de dos módulos a través de la sentencia use: • iso_fortran_env, quien define la precisión de los tipos de datos reales, ya sea de simple o doble precisión, via el parámetro wp cuya asignación será sp ó dp, respectivamente. Por ejemplo, si (como haremos) trabajamos en doble precisión, la sentencia apropiada es use iso_fortran_env, only: wp => dp • f95_lapack, quien define las interfaces explícitas de las subrutinas a utilizar. Por ejemplo, si vamos a utilizar la subrutina la_syev, la sentencia apropiada es use f95_lapack, only: la_syev Una discusión completa de los argumentos necesarios para invocar cada subrutina de lapack95 está dada en el manual de usuario, el cual puede ser consultado on-line en http://www.netlib.org/lapack95/ lug95/. A continuación describiremos como proceder en el caso de una matriz simétrica real (recordemos que, en tal caso, los autovectores son reales y sus autovectores pueden escogerse ortonormales). En su forma más simple, la invocación a la subrutina la_syev procede con la sentencia call la_syev(a,w,JOBZ=’V’), donde • a es una arreglo bidimensional que contiene, como entrada, a la matriz del problema, mientras que, a la salida, contiene en sus columnas a los autovectores ortonormales (si JOBZ es asignado a ’V’) en el orden dado por los autovalores. • w es un arreglo unidimensional cuyo tamaño es igual al número de filas (o columnas) de la matriz del problema, el cual contiene como salida los autovalores del problema, ordenados de menor a mayor. • JOBZ=’V’. Este argumento opcional es una varia- ble carácter, el cual cuando es asignada a ’V’ indica que deben calcularse tanto los autovalores como los autovectores, mientras que, si es asignada a ’N’ sólo se calculan los autovalores. El código 1, presentado al final de la práctica, imple- menta la determinación de los autovectores y autova- lores de una matriz simétrica real haciendo uso de la subrutina descripta. Aquí los tamaños de los arreglos son asignados dinámicamente. La matriz es leída de Práctica 11 1 http://www.netlib.org/lapack95/lug95/ http://www.netlib.org/lapack95/lug95/ Análisis Numérico y Programación (2022) un archivo con un formato que consta de una línea indicando su dimensión, seguida de sus elementos escritos fila por fila en la forma matemática usual. Para compilar el programa fuente debemos infor- mar explicitamente al compilador que utilizaremos la librería lapack y su interface lapack95 como sigue1: $ gfortran -Wall -o programa programa.f90 \ -I/usr/local/include/lapack95 \ -llapack -llapack95 Ejercicio 2. Encontrar aproximaciones para los au- tovalores de las siguientes matrices simétricas, (a) 12 10 410 8 −5 4 −5 3 , (b) 2 0 10 3 −2 1 −2 −1 , (c) 4 −1 −1 0 −1 4 0 −1 −1 0 4 −1 0 −1 −1 4 , (d) 4 2 0 0 0 2 4 2 0 0 0 2 4 2 0 0 0 2 4 2 0 0 0 2 4 . En el caso de una matriz real general, los autovecto- res pueden ser complejos. Debido a esto la subrutina la_geev requiere ahora de dos arreglos unidimensio- nales, uno para guardar la parte real y otro la parte imaginaria de los autovalores. Nótese que para una matriz real, si λ es un autovalor con autovector x entonces también λ es un autovalor con autovector x. La subrutina la_geev aprovecha esta situación para almacenar los autovectores (en general complejos) en una matriz del mismo tamaño que el de la matriz del problema. Para ello el autovector correspondiente a un autovalor complejo es guardado tomando sepa- radamente su parte real e imaginaria en columnas sucesivas de tal matriz. El código 2, presentado al final de la práctica, implementa, con ayuda de la subrutina la_geev la resolución del problema de autovalores para una matriz genérica. Ejercicio 3. Encontrar aproximaciones a los autova- lores de las siguientes matrices,5 2 01 4 −1 0 3 7 , 6 −2 0 0 3 4 −1 0 0 0 5 −1 0 0 2 3 . Ejercicio 4. Determinar estimaciones para los auto- valores de las siguientes matrices,−149 −50 −154537 180 546 −27 −9 −25 , −149 −50 −154537 180.01 546 −27 −9 −25 . ¿Qué puede concluirse de los resultados? 1Para quienes utilicen slack edición fortran el comando es levemente distinto: $ gfortran -o programa programa.f90 -I/usr/include/lapack95 -llapack -llapack95 Aplicación a las ecuaciones algebraicas. Los métodos numéricos para calcular autovalores no invo- lucran al polinomio característico, pues, en general, la resolución de la ecuación característica por algún método numérico para ecuaciones algebraicas es nu- méricamente inestable. De hecho, podemos utilizar los métodos numéricos de cálculo de autovalores para obtener los ceros de una ecuación algebraica de la forma xn + an−1xn−1 + · · ·+ a1x+ a0 = 0 notando que ellos son las raíces del polinomio característico de la siguiente matriz acompañante, 0 0 · · · 0 −a0 1 0 · · · 0 −a1 0 1 · · · 0 −a2 ... ... . . . ... ... 0 0 · · · 1 −an−1 . Ejercicio 5. Determinar los ceros de la ecuación 2x5 − 12x4 + 24x3 − 24x2 + 22x− 12 = 0 utilizando el procedimiento descrito. Práctica 11 2 Análisis Numérico y Programación (2022) Código 1. Cálculonumérico de autovalores de una matriz real simétrica program eigen_sym !-------------------------------------------------------- ! Calculo de autovalores y autovectores de una matriz ! simétrica real. !-------------------------------------------------------- ! Cargar módulos para lapack95: ! * definir precisión ! * indicar subrutina se utilizará !-------------------------------------------------------- use iso_fortran_env, only: wp => REAL64 use f95_lapack, only: la_syev !-------------------------------------------------------- ! Declarar variables !-------------------------------------------------------- implicit none integer :: n, i, j real(wp), allocatable :: a(:,:) ! Matriz del problema real(wp), allocatable :: w(:) ! Autovalores !-------------------------------------------------------- ! Leer la matriz y asignar memoria !--------------------------------------------------------- open(8,file='matriz.dat') read(8,*) n allocate(a(n,n),w(n)) read(8,*) ((a(i,j),j=1,n),i=1,n) close(8) !-------------------------------------------------------- ! Calcular autovalores y autovectores !-------------------------------------------------------- call la_syev(a,w,'V') !-------------------------------------------------------- ! Imprimir autovalores !-------------------------------------------------------- do i=1,n write(*,*) w(i) end do !-------------------------------------------------------- write(*,*) !-------------------------------------------------------- ! Imprimir los autovectores ortonormales !-------------------------------------------------------- do i=1,n write(*,*) (a(i,j),j=1,n) end do !-------------------------------------------------------- ! Liberar memoria !-------------------------------------------------------- deallocate(a,w) !-------------------------------------------------------- end program eigen_sym Práctica 11 3 Análisis Numérico y Programación (2022) Código 2. Cálculo numérico de autovalores de una matriz real general program eigen !-------------------------------------------------------- ! Calculo de autovalores y autovectores de una matriz ! genérica real !-------------------------------------------------------- ! Cargar modulos para lapack95: ! * definir precisión ! * indicar subrutina se utilizará !-------------------------------------------------------- use iso_fortran_env, only: wp => REAL64 use f95_lapack, only: la_geev !-------------------------------------------------------- ! Declarar variables !-------------------------------------------------------- implicit none integer :: n, i, j real(wp), allocatable :: a(:,:) ! Matriz del problema real(wp), allocatable :: wr(:) ! Parte real de los autovalores real(wp), allocatable :: wi(:) ! Parte imaginaria de los autovalores real(wp), allocatable :: p(:,:) ! Matriz de autovectores !-------------------------------------------------------- ! Leer la matriz y asignar memoria !--------------------------------------------------------- open(8,file='matriz.dat') read(8,*) n allocate(a(n,n),wr(n),wi(n),p(n,n)) read(8,*) ((a(i,j),j=1,n),i=1,n) close(8) !-------------------------------------------------------- ! Calcular autovalores y autovectores !-------------------------------------------------------- call la_geev(a,wr,wi,vr=p) !-------------------------------------------------------- ! Imprimir autovalores !-------------------------------------------------------- do i=1,n write(*,*) wr(i),wi(i) end do !-------------------------------------------------------- write(*,*) !-------------------------------------------------------- ! Imprimir matriz p para determinar los autovectores !-------------------------------------------------------- do i=1,n write(*,*) (p(i,j),j=1,n) end do !-------------------------------------------------------- ! Liberar memoria !-------------------------------------------------------- deallocate(a,wr,wi,p) !-------------------------------------------------------- end program eigen Práctica 11 4
Compartir