Apunte TP3 (Métodos Numéricos)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Factorizacion QR[editar]

A = QR
QQ' = I
R triangular superior

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

Metodo de Givens[editar]

Se definen las matrices Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Q'_{ij}} igual a la identidad salvo los elementos en posiciones i o j:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a_{ii} = cos \theta \,}
Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a_{jj} = cos \theta \,}
Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a_{ij} = sen \theta \,}
Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle a_{ji} = -sen \theta \,}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Q'_{n-1,n} * \dots * Q'_{1,n} * \dots * Q'_{1,3} * Q'_{1,2} = Q \vee Q * R = A}

Implementacion[editar]

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[editar]

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

Matrices semejantes[editar]

Sean A,B matrices pertenecientes al espacio real de n*n, se dice que son semejantes si existe una matriz P tal que Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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[editar]

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
Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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[editar]

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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma} de las mismas dimensiones que A, tal que Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \sigma _1 \geq \sigma _2 \geq \dots \geq \sigma _r \geq 0\,} .

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \sum _{i=1}^r \sigma _i * col(U,i) * fila(V,i)}

Para hallar U se usa que
Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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
Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A^t*A = V * \Sigma ^2 * V^t \,}