Dago:Numérico:Prova20122-A2

__MATHJAX_DOLLAR__ 1.(15 pontos) Considere os vetores $x=[-1, 0, 1, 2]^T$ e $y=[1, 3, 3, 4]^T$.

1. Qual sistema numérico deve ser resolvido para ajustar uma reta a esses pontos?
2. Qual a reta que melhor se ajusta a esses pontos?
3. Encontre a curva na forma $y(x)=1+a x^2$ que melhor se ajusta aos pontos dados.

2.(20 pontos) Sendo o conjunto de pontos $\mathcal{A}=\{(0,1), (1,2), (3,16)\}$ no plano cartesiano, interpole os dados e estime o valor em $x=2$.

 1. N = 100;     // Jacobi
 2. f(1:N) = 1;
 3. x(1:N) = 1;
 4. c(1:N) = 1:N;
 5. for it =1:3000
 6.   xnew(1)=( f(1) + 4*x(N)-5*x(2))/3;
 7.   xnew(2)=( f(2) + 4*x(1)-5*x(3))/3;
 8.   for i=3:N-1
 9.     xnew(i)=( f(i) +c(i)*x(i-2)+4*x(i-1)-5*x(i+1))/3;
10.   end
11.   xnew(N)=( f(N) + 4*x(N-1)-5*x(1))/3;
12.   x = xnew;
13. end

3.(20 pontos) Considerando o código em scilab/matlab acima, responda:

1. Sendo 1 flop uma operação de ponto flutuante básica ($+$,$-$,$*$ ou $/$), quantos flops são necessários na linha 9?
2. Quantos flops são necessários para o cálculo do loop interno (linhas 8-10)?
3. Quantos flops são necessários para o algoritmo?
4. Qual deve ser o valor máximo de $it$ (linha 5) para que o método de Jacobi acima tenha um custo menor que a solução do sistema via fatoração LU (assuma que a solução do sistema via fatoração LU é $O( \frac{4}{3}n^3 )$) ?

4.(30 pontos) O código acima realiza o método de Jacobi conforme a equação $$ \vec{x}^{new}= G \vec{x} + \vec{g}$$

1. Qual o valor de $x^{new}(4)$ na primeira iteração?
2. Qual é a matriz $G$ do algoritmo acima? (descreva pelo menos as 3 primeiras e as 3 últimas linhas de $G$)
3. Se o método convergir, o vetor $\vec{x}^{new}$ será solução de um sistema $A\vec{x}=\vec{b}$. Qual a matriz $A$ do sistema acima? (descreva pelo menos as 3 primeiras e as 3 últimas linhas de $A$);
4. O método é convergente para a matriz $A$ do item anterior? justifique.
5. Qual o vetor $\vec{b}$?
6. Qual alteração deve ser feita no algoritmo para implementar o método de Gauss-Seidel?

5.(15 pontos) Sendo $A = \left[\begin{array}{cc} 5 & 1 \\ 1 & 2 \end{array}\right]$ e $A^{-1} \approx \left[\begin{array}{cc} 0.22 & -0.11 \\ -0.11 & 0.56 \end{array}\right]$:

1. Esboce no plano complexo os discos de Gershgorin.
2. Considerando $A$ e $z^{(3)}=[ -1, 3]^T$, calcule duas iterações do método da potência e forneça uma estimativa para o autovalor encontrado.
3. Qual um valor apropriado de $\sigma $ para utilizar o método da potência com translação para calcular o menor autovalor de $A^{-1}+E$? Justifique a resposta.

Prova e respostas

1.(15 pontos) Considere os vetores $x=[-1, 0, 1, 2]^T$ e $y=[1, 3, 3, 4]^T$.

1. Qual sistema numérico deve ser resolvido para ajustar uma reta a esses pontos?

   $A = \left[\begin{array}{cc} 4 & 2 \\ 2 & 6 \end{array}\right], b = [11, 10]^T$

2. Qual a reta que melhor se ajusta a esses pontos?

   $y=2.3 + 0.9 x$

3. Encontre a curva na forma $y(x)=1+a x^2$ que melhor se ajusta aos pontos dados.

   Um coeficiente, portanto sistema 1x1. $[\sum x^4_k] a= [\sum (y_k-1)x^2_k]$

   $a=14/18$

2.(20 pontos) Sendo o conjunto de pontos $\mathcal{A}=\{(0,1), (1,2), (3,16)\}$ no plano cartesiano, interpole os dados e estime o valor em $x=2$.

Usando diferenças divididas, por ex., $p(x)=1+x+2x(x-1)$, assim $p(2)=7$.

 1. N = 100;     // Jacobi
 2. f(1:N) = 1;
 3. x(1:N) = 1;
 4. c(1:N) = 1:N;
 5. for it =1:3000
 6.   xnew(1)=( f(1) + 4*x(N)-5*x(2))/3;
 7.   xnew(2)=( f(2) + 4*x(1)-5*x(3))/3;
 8.   for i=3:N-1
 9.     xnew(i)=( f(i) +c(i)*x(i-2)+4*x(i-1)-5*x(i+1))/3;
10.   end
11.   xnew(N)=( f(N) + 4*x(N-1)-5*x(1))/3;
12.   x = xnew;
13. end

3.(20 pontos) Considerando o código em scilab/matlab acima, responda:

1. Sendo 1 flop uma operação de ponto flutuante básica ($+$,$-$,$*$ ou $/$), quantos flops são necessários na linha 9?

   7 flops (incluindo os índices teriam 10 flops)

2. Quantos flops são necessários para o cálculo do loop interno (linhas 8-10)?

   7*(N-3)=679 flops (pois N=100)

3. Quantos flops são necessários para o algoritmo?

   nas linhas 6,7 e 11 temos 5 flops por linha, totalizando 15 flops. Das linhas 6-11: 7*(N-3)+15=7N-6=694 que multiplicando por 3000 fornece 2082000 flops

4. Qual deve ser o valor máximo de $it$ (linha 5) para que o método de Jacobi acima tenha um custo menor que a solução do sistema via fatoração LU (assuma que a solução do sistema via fatoração LU é $O( \frac{4}{3}n^3 )$) ?

   $ it*694 < \frac{4}{3}100^3 $, ou $it < 1921. $

4.(30 pontos) O código acima realiza o método de Jacobi conforme a equação $$ \vec{x}^{new}= G \vec{x} + \vec{g}$$

1. Qual o valor de $x^{new}(4)$ na primeira iteração?

   4/3

2. Qual é a matriz $G$ do algoritmo acima? (descreva pelo menos as 3 primeiras e as 3 últimas linhas de $G$)

   $G=\frac{1}{3}\left[\begin{array}{cccccc}

0 & -5 & & & & 4\\ 4 & 0 & -5 & & & \\ c_3 & 4 & 0 & -5 & & \\

  &   &    &    &  &   \\
  & c_{98} &  4 & 0 & -5 &   \\
  &  & c_{99} & 4 & 0  & -5 \\

-5 & & & & 4 & 0 \end{array}\right]$

1. Se o método convergir, o vetor $\vec{x}^{new}$ será solução de um sistema $A\vec{x}=\vec{b}$. Qual a matriz $A$ do sistema acima? (descreva pelo menos as 3 primeiras e as 3 últimas linhas de $A$);

   Uma possível resposta é $A=\left[\begin{array}{cccccc}

3 & 5 & & & & -4\\ -4 & 3 & 5 & & & \\ -c_3 & -4 & 3 & 5 & & \\

  &   &    &    &  &   \\
  & -c_{98} &  -4 & 3 & 5 &   \\
  &  & -c_{99} & -4 & 3  & 5 \\

5 & & & & -4 & 3 \end{array}\right]$

1. O método é convergente para a matriz $A$ do item anterior? justifique.

   Não. A matriz não é diagonal dominante. Ex. na linha 1, $3 < 5 + 4 =9$.

2. Qual o vetor $\vec{b}$?

   $b=3*\vec{f}=[3,3,3...,3,3,3]^T$

3. Qual alteração deve ser feita no algoritmo para implementar o método de Gauss-Seidel?

   Veja abaixo o algoritmo de Gauss-Seidel

 1. N = 100;     // Gauss-Seidel
 2. f(1:N) = 1;
 3. x(1:N) = 1;
 4. c(1:N) = 1:N;
 5. for it =1:3000
 6.   xnew(1)=( f(1) + 4*x(N)   -5*x(2))/3;
 7.   xnew(2)=( f(2) + 4*xnew(1)-5*x(3))/3;
 8.   for i=3:N-1
 9.     xnew(i)=( f(i) +c(i)*xnew(i-2)+4*xnew(i-1)-5*x(i+1))/3;
10.   end
11.   xnew(N)=( f(N) + 4*xnew(N-1)-5*xnew(1))/3;
12.   x = xnew;
13. end

5.(15 pontos) Sendo $A = \left[\begin{array}{cc} 5 & 1 \\ 1 & 2 \end{array}\right]$ e $A^{-1} \approx \left[\begin{array}{cc} 0.22 & -0.11 \\ -0.11 & 0.56 \end{array}\right]$:

1. Esboce no plano complexo os discos de Gershgorin.

   Dois discos de raio 1 com centro em $x=5$ e $x=2$.

2. Considerando $A$ e $z^{(3)}=[ -1, 3]^T$, calcule duas iterações do método da potência e forneça uma estimativa para o autovalor encontrado.

   $z^4=[-2,5]^T, z^5=[-5 ,8]^T \approx =[-0.52, 0.84]^T$ onde $\lambda = (z^5)^TAz^5= 1.94382$

3. Qual um valor apropriado de $\sigma $ para utilizar o método da potência com translação para calcular o menor autovalor de $A^{-1}+E$? Justifique a resposta.

   $A^{-1}+E = \left[\begin{array}{cc} 1.22 & -0.11 \\ -0.11 & 1.56 \end{array}\right]$

   O menor autovalor está no disco centrado em 1.22, assim $\sigma > 1.38$