METODO
PARA EL CALCULO DE VALORES Y VECTORES PROPIOS DOMINANTES
DE UNA MATRIZ - PARTE III
Continúa en PARTE
IV
Viene de
PARTE
I PARTE
II
Si
P es la matriz de dimensión r x r que diagonaliza
a S,tenemos (42) :
Y en (39) podemos hacer (43) :
Y la matriz W de dimensión n x r estará
formada por los r vectores propios asociados a los r valores
propios dominantes de A.
Para el cálculo de los valores propios de S deberá
aplicarse alguna técnica de las ya conocidas (téngase
en cuenta que el objetivo era obtener unos pocos valores
y vectores propios de A, por lo que la dimensión
de S es pequeña comparada con la de A), pero podemos
dar una expresión general para sus vectores propios
en función de los valores propios.
Siendo si un valor propio de S tenemos (44)
:
Tomando la coordenada xr = 1 resulta (45) :
Finalmente, agrupando denominadores, podemos expresar
la componente k-ésima del vector propio asociado
al valor propio si en la forma (46) :
Este segundo algoritmo es más rápido pero
también más inestable, debido a que entre
las operaciones a realizar está la de invertir
matrices de Vandermonde cuyo determinante es nulo si se
tiene  [12].
Los algoritmos según los métodos de Lanczos
y Arnoldi están también basados en iteraciones
sobre subespacios de Krilov.
CONVERGENCIA
Esta claro que, en general, se trata de alcanzar la convergencia
en un proceso iterativo de la forma (47) :
por lo que podemos tomar como parámetro de convergencia
el dado por (48) :
o, mejor (49) :
que es equivalente pero más ilustrativo.
Cuando el valor de 
sea menor que una tolerancia prefijada, se habrá
conseguido la convergencia.
Una ventaja fundamental de utilizar la ecuación
(49) como criterio de convergencia es la de evitar la
resolución del problema de valores propios en cada
iteración.
DESCRIPCION PRACTICA
DEL METODO
Los pasos a seguir para una aplicación práctica
inicial del método serían :
1.
Iniciar el proceso de iteración tomando un conjunto
de R vectores linealmente independientes.
2. Obtener la matriz  ,
multiplicando la matriz problema por  .
Aplicar el factor de escala.
3. Calcular las matrices  y,
a partir de ellas, obtener la matriz 
4. Determinar el valor del factor de convergencia, de
acuerdo con la ecuación (49).
5. Si el valor del parámetro de convergencia
es menor que la tolerancia establecida
Cerrar el proceso
En otro caso,
Volver al paso 2.
En
la práctica, el esquema expuesto, presenta dos
deficiencias que requieren su mejora :
Por una parte, aun en el caso de condiciones de convergencia
favorables  ,debido
a los errores de redondeo, es difícil llegar a
obtener una precisión superior a la sexta cifra
decimal con una implementación directa del mismo.
Por otra, cuando las condiciones de convergencia no son
favorables,
, el esquema no aprovecha adecuadamente la información
ofrecida por la evolución del factor de convergencia.
El primero de los problemas queda resuelto con la introducción
de un paso intermedio que mejora significativamente la
precisión alcanzada mediante la corrección,
cada cierto número de iteraciones, del grupo de
vectores de iteración, multiplicándolo por
un factor matricial deducido de la ecuación (25).
La segunda cuestión puede solventarse pasando a
extraer un número de valores propios para el que
se tenga una velocidad de convergencia mas favorable.
Así pues, un esquema más efectivo sería
:
1. Iniciar el proceso de iteración tomando un
conjunto de R vectores linealmente independientes.
2. Obtener la matriz
multiplicando la matriz problema por .
3. Calcular las matrices
y, a partir de ellas, obtener la matriz 
4. Determinar el valor del factor de convergencia, de
acuerdo con la ecuación (49).
5. Si el índice de iteración es múltiplo
del parámetro de reiniciación,
5.1. Corregir el grupo de vectores de iteración
transformándolo mediante un factor matricial
deducido de la ecuación (25) y tomar como siguiente
grupo de iteración el resultado obtenido.
5.2. Si a partir de un valor dado del índice
de iteración, la velocidad de convergencia
del proceso es menor que un límite dado,
5.2.1. Pasar a extraer p-1 valores propios.
En otro caso,
5.3. Tomar como siguiente grupo de vectores de iteración
el resultado de la iteración anterior.
6. Aplicar el factor de escala.
7. Si el valor del parámetro de convergencia
es menor que la tolerancia establecida,
Cerrar el proceso
En otro caso,
Volver al paso 2.
Mediante la implementación en Mathemática
[16] de un algoritmo que desarrolla el segundo de los
esquemas expuestos, puede obtenerse la representación
gráfica de la evolución de
y dos parámetros auxiliares (su valor mínimo
y su media acumulada) en función del número
de iteraciones, para el problema de la extracción
de un conjunto p de valores propios de diversas matrices.
ALGORITMO
Comentario : Extracción
de la matriz sigma que contiene los R valores propios
de mayor módulo de una matriz arbitraria A, reiniciando
cada q veces el grupo de vectores de iteración.
INICIAR ALGORITMO
Solicitar la matriz problema, A, de dimensión n
Solicitar el número de valores propios a extraer,
R (con R << n)
INICIAR
VARIABLES
Parámetro de tolerancia, (Tol) ;
Valor límite mínimo del índice de
iteración para pasar a extraer p-1 valores propios,
(VL);
Parámetro de reiniciación, (q)
Número de ciclos de iteración, (CL) ;
número máximo de iteraciones, (MXI)
Parámetro de convergencia, (X) ;
Valor mínimo de X, (MN)
Número de iteraciones que se mantiene un mínimo
local de X, (CMX)
Suma acumulada de X, (M) ; Valor medio de X, (MC)
Matriz inicial de iteración, (M0), formada por
R vectores linealmente independientes.
Matriz auxiliar (Mi) para la extracción de la matriz
Sigma que contiene los p valores propios dominantes, formada
por R vectores linealmente independientes.
Valor inicial de la matriz que contiene los p valores
propios dominantes, (S)
Listas para el almacenamiento de los valores de X, MC
y MN con objeto de su representación gráfica
frente al número de iteraciones, (TX), (TM), (TN)
Comentario
: Los vectores que forman M0 y Mi, son tomados aleatoriamente.
INICIAR ITERACIÓN
Almacenar en la variable (Esc) el máximo de los
valores absolutos de los elementos de (M0), para aplicarlo
como factor de escala para evitar desbordamientos,
Aplicar A sobre M0 y almacenar el resultado en M1,
Almacenar en una variable auxiliar, SInt, el valor actual
de la matriz S,
Obtener el valor de S por aplicación de la ecuación
(27),
Almacenar en X el valor dado por la ecuación (30)
Actualizar los valores de M y MC,
Si el valor actual de X es menor que MN,
igualar MN a X, poner a 1 el contador CMX,
En otro caso,
Incrementar en 1 el contador CMX,
Si el índice de iteración, I, es múltiplo
de q,
Reiniciar la matriz de iteración, poniendo M0 =
M1*Traspuesta[Base de Jordan asociada a los valores propios
de la matriz S, de acuerdo a la ecuación (25),
Actualizar las listas para las gráficas de X, M
y MN
Si I es igual o mayor que VL y el valor absoluto de la
diferencia entre la cota actual de MC y su valor en la
(10*q)-ésima iteración anterior es menor
o igual que 0.01,
Pasar a extraer p-1 valores propios
En otro caso,
Continuar
En otro caso,
Reiniciar la matriz de iteración poniendo M0
= M1
Reasignar a M0 el valor dado por Esc * M0.
Si MN se ha mantenido mas de 125 iteraciones y el valor
actual del parámetro de convergencia, X, es menor
que tol,
Calcular los valores propios de S y almacenarlos en
la variable auxiliar, ESO
Marcar que se ha alcanzado la convergencia exigida
Salir del proceso de iteración.
En otro caso,
Incrementar I en una unidad
Si el índice de iteración, I, es menor que
MXI
Volver a INICIAR ITERACION
En otro caso
Salir del proceso de iteración
CERRAR ITERACION
Representar gráficamente, frente al índice
de iteración, X, MC y MN
Si se ha alcanzado la convergencia exigida
Imprimir
la variable ESO que contiene los valores propios deseados
En otro caso
Indicar que no se ha alcanzado la convergencia deseada
(Opcionalmente) Calcular los valores propios de S e imprimirlos
|
|
