Estás en > Matemáticas y Poesía > Matemáticas

MONOGRAFIAS MATEMÁTICAS
TEORÍA MATRICIAL

CÁLCULO DE VALORES PROPIOS DOMINANTES

 

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) :

    \( P^{-1}·S·P = D \)
Y en (39) podemos hacer (43) :
    \( A·\tilde{M}_p·P = \tilde{M}_p·S·P = \tilde{M}_p·P·P^{-1}·S·P \rightarrow A·W = W·D \)
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 \(s_i\) un valor propio de S tenemos (44) :
    \( \left[
    \begin{array}{ccccc}
    -s_1 & 0 & \cdots & 0 & a_1 \\
    1 & -s_1 & \cdots & 0 & a_2 \\
    0 & 1 & \cdots & 0 & a_3 \\
    . & . & \cdots & . & . \\
    0 & 0 & \cdots & 1 & a_r-s_r \\
    \end{array}
    \right]·\left[
    \begin{array}{c}
    x_1 \\ x_2 \\ x_3 \\ . \\ x_r \\
    \end{array}
    \right] = 0 \)
Tomando la coordenada xr = 1 resulta (45) :
    \( \displaystyle \begin{array}{l} x_1 = \frac{a_1}{s_i} \\ \\ x_2 = \frac{1}{s_i}\left(a_2 + \frac{a_1}{s_i} \right) \\ \\ x_3 = \frac{1}{s_i}\left[a_3 +\frac{1}{s_i}\left(a_2 + \frac{a_1}{s_i} \right) \right] \\ \end{array} \)
Finalmente, agrupando denominadores, podemos expresar la componente k-ésima del vector propio asociado al valor propio si en la forma (46) :
    \(\displaystyle x_k = \frac{1}{s_i^k}·\sum_{h=1}^k a_h·s_i^{h-1} \)
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\(\lambda_i = \lambda_j\) [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) :
    \( \displaystyle \lim_{p\rightarrow\infty}\left\{\left[V^{\;T}·\tilde{M}_p\right]^{-1}\left[V^{\;T}·\tilde{M}_{p+1}\right]-\left[V^{\;T}·\tilde{M}_{p+1}\right]^{-1}\left[V^{\;T}·\tilde{M}_p\right] \right\} = 0\)
por lo que podemos tomar como parámetro de convergencia el dado por (48) :
    \( \displaystyle\eta= \max\left|\left\{\left[V^{\;T}·\tilde{M}_p\right]^{-1}\left[V^{\;T}·\tilde{M}_{p+1}\right]-\left[V^{\;T}·\tilde{M}_{p+1}\right]^{-1}\left[V^{\;T}·\tilde{M}_p\right] \right\}\right|\)
o, mejor (49) :
    \(\eta'_p = \log [\eta_p]\)
que es equivalente pero más ilustrativo.

Cuando el valor de \(\eta'_p\) 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 \(\tilde{M}_{p+1}\) , multiplicando la matriz problema por\(\tilde{M}_p\) . Aplicar el factor de escala.

    3. Calcular las matrices \(\left[V^{\;T}·\tilde{M}_p\right] \; y \; \left[V^{\;T}·\tilde{M}_{p+1}\right]\) y, a partir de ellas, obtener la matriz \(\Sigma_r\)

    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 \((\lambda_R >> \lambda_{R+1})\) ,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, \((\lambda_R \geq \lambda_{R+1};\lambda_R \approx \lambda_{R+1} )\), 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 \(\tilde{M}_{p+1}\) , multiplicando la matriz problema por\(\tilde{M}_p\).

    3. Calcular las matrices \(\left[V^{\;T}·\tilde{M}_p\right] \; y \; \left[V^{\;T}·\tilde{M}_{p+1}\right]\) y, a partir de ellas, obtener la matriz \(\Sigma_r\)

    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 \(\Sigma_r\) 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
CERRAR ALGORITMO.

Continuar leyendo en PARTE IV - viene de PARTE I - PARTE II -
¿Te han sido de utilidad estos apuntes sobre el cálculo de valores propios?.- ¡Recomiénda esta página!

Otros usuarios de Matemáticas y poesía también han visto:


 


tema escrito por: José Antonio Hervás