Ver el código de «Primer Parcial 9/05/2008 (Métodos Numéricos)»

{{Back|Métodos Numéricos}}

== Ejercicio 1 ==
Para los algoritmos <math>\frac{x}{x-1}</math> y <math>\frac{1}{1 - 1/x}</math>:

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

b) Analizar condición y estabilidad.


== Ejercicio 2 ==
Sea <math>n \geq 1</math>. Decimos que <math>A \in \mathbb{R}^{n \times n}</math> 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: <math>n \leq 2</math> si y sólo si todas las matrices de <math>\mathbb{R}^{n \times n}</math> que tienen todos los elementos diagonales distintos de cero tienen factorización ''LU''.

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

<math>||A||_F = \sqrt{\sum_{i=1}^n \sum_{j=1}^{n} a_{ij}^2}</math>, <math>||A||_2 = sup_{||x||_2=1}||Ax||_2</math> y <math>||A||_M = max_{i,j} |a_{ij}|</math>. Probar

a) <math>||A||_F \leq \sqrt{n}||A||_2</math>

b) <math>||A||_F \leq n ||A||_M</math>, y si <math>||A||_F = ||A||_M</math> entonces A no es inversible.


== Ejercicio 4 ==
Hallar la primera matriz de transformación <math>R_1</math> 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 <math>R_1</math> y verificar que <math>R_1A</math> hace cero los elementos de la primera columna por debajo de la diagonal.

<math>A = \begin{bmatrix}
  0 & -20 & -14 \\
  3 & 27  & -4  \\ 
  4 & 11  &  -2
\end{bmatrix}</math>

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

== Ejercicio 5 ==
Sea <math>A \in \mathbb{R}^{n \times n}</math> una matriz simétrica definida positiva, con <math>\lambda_i</math> autovalores de A tal que<math> 1 < \lambda_1 \leq ... \leq \lambda_n</math> y sea <math>\omega</math> una constante positiva. Se define el siguiente algoritmo iterativo, para <math>i = 1,...,n</math>:

<math>
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)}</math>

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 <math>\lambda</math> es autovalor de A y <math>\alpha, \beta \in \mathbb{R}</math>, hallar los autovalores de <math>\alpha I + \beta A</math>. Justifique.

c) Determinar los valores de <math>\omega</math> para los cuales el algoritmo iterativo planteado converge para cualquier <math>x^{(0)}</math> 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:
<math>
x^{k+1} = (I - \omega D)x^k + (\omega L + \omega U) x^k + \omega b =</math>

<math>= (I+ \omega (-D+L+U))x^k + \omega b =</math>

<math>= (I - \omega (D-L-U))x^k + \omega b =</math>

<math>= (I - \omega A)x^k + \omega b </math>

Sea <math>T = (I- \omega A)</math>
<math>
x^0 = 0</math>

<math>x^1 = Tx^0 + \omega b</math>

<math>x^2 =  T(Tx^0 + \omega b) + \omega b = T^2 x^0 + T \omega b + \omega b</math>

<math>x^k = T^k x^0 +T^{k-1} \omega b + ... + T \omega b + \omega b =</math>

<math>= T^k x^0 + (I + T + T^2 + ... + T^k) \omega b</math>

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

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

<math>\omega b  = \omega A x</math>

b = Ax

Entonces converge al resultado deseado.

'''b)'''
<math>det (\alpha I + \beta A - I\delta) = 0</math>  por definición de autovalor

<math>det (\beta A - I(\delta - \alpha)= = 0 \Leftrightarrow</math>

<math>\beta det(A - I(\frac{ \delta - \alpha}{\beta})) = 0</math>

Entonces si <math>\lambda</math> es autovalor de A

<math>\frac{ \delta - \alpha}{\beta} = \lambda</math>

<math>\delta = (\beta \lambda + \alpha)</math> serán los autovalores de <math>\alpha I + \beta A</math>.

'''c)'''
<math>\rho (I- \omega A)</math> debe ser < 1.

Sabemos <math>\rho (I- \omega A) = - \omega \rho (A) + 1</math>

<math>|-\omega \rho (A) + 1| < 1 \Leftrightarrow -1 < 1 - \omega \lambda_i < 1</math>

Despejando <math>\omega < \frac{2}{\lambda n}</math>


[[Category:Parciales]]