Apunte TP3 (Métodos Numéricos)

Factorizacion QR

A = QR
QQ' = I
R triangular superior

Ax = b <=> QRx = b <=> Rx = Q'b

Metodo de Givens

Se definen las matrices $Q'_{ij}$ igual a la identidad salvo los elementos en posiciones i o j:

$a_{ii}=cos\theta \,$
$a_{jj}=cos\theta \,$
$a_{ij}=sen\theta \,$
$a_{ji}=-sen\theta \,$

$Q'_{n-1,n}*\dots *Q'_{1,n}*\dots *Q'_{1,3}*Q'_{1,2}=Q\vee Q*R=A$

Implementacion

Se puede aprovechar que una iteracion del metodo de Givens afecta solamente dos filas de la matriz original para hacer cada producto en orden lineal, no usando el algoritmo general.

Para calcular la factorizacion QR de la matriz con MatLab, se puede usar la funcion

[Q,R] = qr(A);

Algoritmo QR para el calculo de autovalores

Algoritmo iterativo que, al converger, devuelve todos los autovalores de la matriz.

Matrices semejantes

Sean A,B matrices pertenecientes al espacio real de n*n, se dice que son semejantes si existe una matriz P tal que $A=P*B*P^{-1}\,$ y se nota A churunflo B.

Si A y B son semejantes, entonces sus autovalores son iguales. No vale la reciproca.

Algoritmo

Entrada: matriz A cuyos autovalores se desean calcular, y M cantidad maxima de iteraciones

Sea A[i] la matriz en la i-esima iteracion

A[1] = A
For k = 1 to M
    Q[k] * R[k] = A[k]
    A[k+1] = R[k] * Q[k]

En notacion MatLab...

    [Q,R] = qr(A)
     A = R * Q

Si los autovalores son reales, en A_M se retorna una matriz triangular superior donde en la matriz se encuentran los autovalores de la matriz ordenados en modulo. Si la matriz ademas es simetrica, la matriz resultante es diagonal. Una vez la matriz es triangular superior, se puede cortar el algoritmo.

Si los autovalores son complejos, entonces la matriz resultante es triangular superior de a bloques de a lo sumo 2x2. Es decir, en la diagonal hay o bien elementos o bien submatrices de 2x2; si son elementos son los autovalores reales; si son submatrices (se distinguen xq el elemento debajo la diagonal es distinto de cero), se calculan los autovalores de esa submatriz y resultan un autovalor complejo y su conjugado (que tambien es autovalor). La condicion de corte en este caso puede ser que la banda de la matriz se mantenga realtivamente igual.

Si hay algun autovalor repetido, entonces aparece esa cantidad de veces en la matriz.

Para optimizar la factorizacion QR, se puede trabajar con la matriz de Hessenberg de A que es semejante (tiene los mismos autovalores) y es triangulas superior salvo porque la subdiagonal inmediata inferior a la diagonal ppal es distinta de cero. Se calcula al conmienzo la matriz de Hessenberg y las transformaciones de Givens no alteran la estructura, con lo cual no es necesario realcularla, se hace solo al principio.

Vale que son semejantes y tienen los mismos autovalores pues
$A_{k}=Q_{k}*R_{k}=Q_{k}*R_{k}*I=Q_{k}*R_{k}*Q_{k}*Q_{k}^{-1}=Q_{k}*A_{k+1}*Q_{k}^{-1}$.

Singular Value Descomposition

Sea la matriz A real de m*n, no necesariamente cuadrada. Se buscan las matrices reales ortonormales U y V de m*m y n*n respectivamente; y una matriz real diagonal $\Sigma$ de las mismas dimensiones que A, tal que $\sigma _{1}\leq \sigma _{2}\leq \dots \leq \sigma _{r}\leq 0\,$.

$A=U*\Sigma *V^{t}\,$

La matriz A se puede escribir como la suma del sigma i, por la columna i de U, por la fila i de V. $\sum _{i=1}^{r}\sigma _{i}*col(U,i)*fila(V,i)$

Para hallar U se usa que
$A*A^{t}=(U*\Sigma *V^{t})*(U*\Sigma *V^{t})^{t}=U*\Sigma *I*\Sigma ^{t}*U^{t}=U*\Sigma ^{2}*U^{t}\,$

El U es la matriz de autovectores (los autovectores de AA' son las columnas de U), se pueden obtener del algoritmo QR; sigma cuadrado son los autovalores de AA' (ver que AA' tiene todos sus autovalores reales mayores o iguales que cero, por ser semidefinida positiva). Se toma raiz de sigma cuadrado y se modifica la dimension (truncando) para obtener el sigma original.

La cuenta para hallar V es analoga pero usando el algoritmo QR sobre A'A, se llega a que
$A*A^{t}=V*\Sigma ^{2}*V^{t}\,$