Logo Studenta

ANyP-11

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

Otros materiales