Primer Parcial 9/05/2008 (Métodos Numéricos)

Ejercicio 1

Para los algoritmos ${\frac {x}{x-1}}$ y ${\frac {1}{1-1/x}}$:

a) Hallar los coeficientes de condición y estabilidad de ambos.

b) Analizar condición y estabilidad.

Ejercicio 2

Sea $n\geq 1$. Decimos que $A\in \mathbb {R} ^{n\times n}$ tiene factorización LU si existe L triangular inferior con unos en la diagonal y U triangular superior tales que A = LU, o equivalentemente, si A se puede traingular sin pivoteo de filas mediante el método de Gauss.

Probar: $n\leq 2$ si y sólo si todas las matrices de $\mathbb {R} ^{n\times n}$ que tienen todos los elementos diagonales distintos de cero tienen factorización LU.

Ejercicio 3

Sea $n\geq 2$. Considere las siguientes normas matriciales definidas para toda matriz $A=(a_{ij})\in \mathbb {R} ^{n\times n}$:

$||A||_{F}={\sqrt {\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}^{2}}}$, $||A||_{2}=sup_{||x||_{2}=1}||Ax||_{2}$ y $||A||_{M}=max_{i,j}|a_{ij}|$. Probar

a) $||A||_{F}\leq {\sqrt {n}}||A||_{2}$

b) $||A||_{F}\leq n||A||_{M}$, y si $||A||_{F}=||A||_{M}$ entonces A no es inversible.

Ejercicio 4

Hallar la primera matriz de transformación $R_{1}$ utilizada para encontrar la factorización QR de A, por el método de Householder. Indicar claramente cuál fue el vector u utilizado para construir la matriz $R_{1}$ y verificar que $R_{1}A$ hace cero los elementos de la primera columna por debajo de la diagonal.

$A={\begin{bmatrix}0&-20&-14\\3&27&-4\\4&11&-2\end{bmatrix}}$

Recordar que la expresión para un reflector es: $R=I-2{\frac {u.u^{t}}{u^{t}.u}}=I-2{\frac {u.u^{t}}{||u||^{2}}}$

Ejercicio 5

Sea $A\in \mathbb {R} ^{n\times n}$ una matriz simétrica definida positiva, con $\lambda _{i}$ autovalores de A tal que$1<\lambda _{1}\leq ...\leq \lambda _{n}$ y sea $\omega$ una constante positiva. Se define el siguiente algoritmo iterativo, para $i=1,...,n$:

$x_{i}^{(k+1)}=\omega b_{i}+(1-\omega a_{ii})x_{i}^{(k)}-\sum _{j=1,j\neq i}^{n}\omega a_{ij}x_{j}^{(k)}$

a) Hallar el esquema de iteración de forma matricial y verificar que si el sistema iterativo converge, entonces lo hace a una solución del sistema Ax = b.

b) Si $\lambda$ es autovalor de A y $\alpha ,\beta \in \mathbb {R}$, hallar los autovalores de $\alpha I+\beta A$. Justifique.

c) Determinar los valores de $\omega$ para los cuales el algoritmo iterativo planteado converge para cualquier $x^{(0)}$ inicial. (ayuda: usar los resultados anteriores).

Respuesta a) Sea A = (D-L-U) con D los elementos de la diagonal de A, -L la parte estrictamente triangular inferior de A y -U la parte estrictamente triangular superior de A.

La forma matricial es: $x^{k+1}=(I-\omega D)x^{k}+(\omega L+\omega U)x^{k}+\omega b=$

$=(I+\omega (-D+L+U))x^{k}+\omega b=$

$=(I-\omega (D-L-U))x^{k}+\omega b=$

$=(I-\omega A)x^{k}+\omega b$

Sea $T=(I-\omega A)$ $x^{0}=0$

$x^{1}=Tx^{0}+\omega b$

$x^{2}=T(Tx^{0}+\omega b)+\omega b=T^{2}x^{0}+T\omega b+\omega b$

$x^{k}=T^{k}x^{0}+T^{k-1}\omega b+...+T\omega b+\omega b=$

$=T^{k}x^{0}+(I+T+T^{2}+...+T^{k})\omega b$

Si $\rho (T)<1$ existe $(I-T)^{-1}=I+T+T^{2}+...$

Si $k\to \infty ,(I-T)^{-1}\omega b=x$ $\omega b=(I-T)x$ $\omega b=(I-(I-\omega A))x$

$\omega b=\omega Ax$

b = Ax

Entonces converge al resultado deseado.

b) $det(\alpha I+\beta A-I\delta )=0$ por definición de autovalor

$det(\beta A-I(\delta -\alpha )==0\Leftrightarrow$

$\beta det(A-I({\frac {\delta -\alpha }{\beta }}))=0$

Entonces si $\lambda$ es autovalor de A

${\frac {\delta -\alpha }{\beta }}=\lambda$

$\delta =(\beta \lambda +\alpha )$ serán los autovalores de $\alpha I+\beta A$.

c) $\rho (I-\omega A)$ debe ser < 1.

Sabemos $\rho (I-\omega A)=-\omega \rho (A)+1$

$|-\omega \rho (A)+1|<1\Leftrightarrow -1<1-\omega \lambda _{i}<1$

Despejando $\omega <{\frac {2}{\lambda n}}$