Dago:Numérico:Lista 2

Lista de Exercícios 2a

MAT 01169 - Cálculo Numérico

Prof. Dagoberto Adriano Rizzotto Justo

Instruções gerais para a lista: Considere o número de iterações máximas igual a $kmax=10$ e tolerância $tol=10^{-3}$ e as seguintes matrizes para os próximos exercícios: $$ A = \matddd{1}{2}{3}{4}{1}{2}{0}{1}{3} , I = \matddd{1}{0}{0}{0}{1}{0}{0}{0}{1} ,

C = \matddd{4}{3}{1}{-2}{1}{2}{1}{-1}{-1} ,  d =  \vetddd{2}{1}{-1} ,  b = \vetddd{6}{7}{4} $$

Custo

Seja <math>u,v,b,x\in\R^n,A\in\R^{n\times n}</math>. Considerando que o custo de uma operação de multiplicação ou divisão é um flop (floating operation) e que adições e subtrações tem um custo desprezível se comparados a esse custo, calcule o 'custo' das seguintes operações:

1. Calcular o produto escalar <math>u·v = \Sigma_{i=1}^n u_i v_i</math>;
2. Multiplicação matriz-vetor <math>u = A b</math>;
3. Calcular a norma-2 de um vetor <math>\|x\|_2= \sqrt{\sum_{i=1}^n x_i^2}</math>, onde o custo de calcular uma raiz é de 2 flops.
4. Custo para resolver um sistema triangular inferior por substituição;
5. Custo para resolver um sistema triangular superior por retro-substituição;
6. Custo da fatoração LU;
7. Custo para resolver um sistema usando fatoração LU;
8. Custo para resolver $n$ sistemas diferentes usando fatoração LU;
9. Custo para calcular <math>A^{-1}</math>, via resolução de n sistemas;
10. Custo para calcular a norma de Frobenius <math>†A†_F = \sqrt{\sum_{i=1}^n \sum_{j=1}^n a^2_{ij}}</math>.

Álgebra Matricial

1. Resolva o sistema <math>Ax=b</math> usando fatoração LU com e sem pivotamento parcial.
2. Resolva o sistema <math>Ax=b</math> utilizando os métodos de Jacobi e Gauss-Seidel com uma tolerância de <math>10^{-2}</math> e um máximo de 10 iterações. Calcule em cada iteração <math>k</math> o resíduo <math>r_k=b-Ax_k</math> e a norma-<math>\infty</math> do resíduo. O que se pode concluir?
3. Calcule:
   1. <math>\|b\|_1,\|b\|_2,\|b\|_3,\|b\|_{\infty}</math>
   2. <math>\|A\|_1,\|A\|_{\infty},\kappa_1(A)=\|A\|\|A^{-1}\|_1,\kappa_\infty(A)=\|A\|_\infty\|A^{-1}\|</math>
4. Dê as seguintes definições:
   1. Norma vetorial;
   2. Número de condição de uma matriz <math>\kappa(A)</math>;
   3. Matriz mal-condicionada e bem-condicionada;
   4. Determinante normalizado da matriz <math>norm |A|</math>;
   5. Uma matriz diagonal dominante; dê exemplos.
5. Qual a condição para que o método iterativo <math>x_k = (I - Q^{-1}A)x_{k-1} + Q^{-1}b</math> seja convergente?
6. Defina o método de refinamento iterativo. Qual a condição para o método de refinamento iterativo convergir?
7. Descreva o método de Jacobi. Como ele pode ser representado matricialmente? Qual a condição para que o método de Jacobi seja convergente?
8. Descreva o método de Gauss-Seidel. Como ele pode ser representado matricialmente? Qual a condição para que o método de Gauss-Seidel seja convergente?

Autovalores

1. Para a matriz $A$ no começo dessa lista, descreva e represente graficamente os discos de Gershgorin. Calcule os autovalores e represente-os no mesmo gráfico. O que se pode concluir?
2. Repita o exercício anterior para a matriz $C$.
3. Escolha uma matriz rândomica com $5 ×5$ elementos. Represente graficamente os discos de Gershgorin. Se puder, usando MATLAB ou sua calculadora, calcule os autovalores e represente-os graficamente.
4. Explique por que nâo devemos usar o cálculo de autovalores via determinantes, do ponto de vista numérico. Um gráfico poderia ajudar na explicação.
5. Defina quociente de Rayleigh.
6. Descreva o método da potência, como ele funciona e para que serve. Quando este método nâo funciona?
7. Calcule via método da potência o maior autovalor de A.
8. Calcule via método da potência o maior autovalor de C.
9. Considere a matriz A. Usando os discos de Gershgorin, selecione um possível valor para \sigma e use como translação para o Método da Potência. Repita o exercício para três valores diferentes de \sigma. (Calcule a cada iteração k o valor de <math>\lambda_k = x_k^TAx_k</math>.
10. Considere a matriz A e o resultado do exercício anterior. Utilize o método da iteração inversa com translação usando como \sigma o valor aproximado do autovalor anterior. O que se pode concluir.
11. Utilize o método de iteração inversa com o quociente de Rayleigh e calcule um autovalor de A. O que se pode concluir.
12. Considere a matriz C e repita o três exercícios anteriores.

Interpolação

1. Defina uma matriz de Vandermonde. Qual o problema desta matriz. Dê um exemplo.
2. Para a seguinte tabela de valores, utilize interpolação polinomial e calcule o polinômio interpolador de ordem $2$.

 x    & 2 & 4 & 5 
 y(x) & 0 & 3 & 1 

Desenhe o gráfico do polinômio interpolador e os pontos da tabela.

1. Repita o exercício anterior usando a forma de Newton e diferenças divididas. Estime o erro na interpolação para o ponto $x=3$.
2. Repita o exercício anterior usando a forma de Lagrange.
3. Usando uma calculadora ou MATLAB, calcule o polinômio interpolador de ordem $4$.

 x    & 2 & 4 & 5 & 5.5 & 8
 y(x) & 0 & 3 & 1 & -1   & 2

Desenhe o gráfico do polinômio interpolador e os pontos da tabela. O que se pode concluir.

1. Repita o exercício anterior usando a forma de Newton e diferenças divididas. Estime o erro na interpolação para o ponto $x=3$.
2. Repita o exercício anterior usando a forma de Lagrange.
3. Usando a forma de Newton e diferenças simples, calcule o polinômio interpolador da seguinte tabela

 x    & 2 & 3 & 4 & 5 & 6
 y(x) & 0 & 3 & 1 & -1& 2

Desenhe o gráfico do polinômio interpolador e os pontos da tabela. O que se pode concluir. Estime o erro na interpolação para o ponto $x=3.5$.

1. Para a seguinte tabela de valores, utilize uma interpolação por splines cúbicas:

 x    & 2 & 4 & 5
 y(x) & 0 & 3 & 1

Desenhe o gráfico do polinômio interpolador e os pontos da tabela. Utilize as fórmulas para Splines do livro.

Questões Área 2

\begin{enumerate}

 \item (15 pontos) Considere os vetores $x=[-1, 0, 1, 2]^T$ e $y=[1, 3, 3, 4]^T$.
 \begin{enumerate}
  \item Qual sistema num{\'e}rico deve ser resolvido para ajustar uma reta a esses pontos?
  \item Qual a reta que melhor se ajusta a esses pontos?
  \item Encontre a curva na forma $y(x)=1+a x^2$ que melhor se ajusta aos pontos dados.
 \end{enumerate}
 \item (10 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$.

\begin{verbatim}

1. N = 100;
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. end \end{verbatim} \item (20 pontos) Considerando o código em scilab/matlab acima, responda: \begin{enumerate}

 \item Sendo 1 flop uma operação de ponto flutuante básica ($+$,$-$,$*$ ou $/$), quantos flops são necessários na linha 9?
 \item Quantos flops são necessários para o cálculo do loop interno (linhas 8-10)?
 \item Quantos flops são necessários para o algoritmo?
 \item Qual deve ser o valor máximo de \verb#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 )$) ?

\end{enumerate} \item (30 pontos) O código acima realiza o método de Jacobi conforme a equação $$ \vec{x}^{new}= G \vec{x} + \vec{g}$$ \begin{enumerate} \item Qual o valor de $x^{new}(4)$ na primeira iteração? \item Qual é a matriz $G$ do algoritmo acima? (descreva pelo menos as 3 primeiras e as 3 últimas linhas de $G$) \item 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$); \item O método é convergente para a matriz $A$ do item anterior? justifique. \item Qual o vetor $\vec{b}$? \item Qual alteração deve ser feita no algoritmo para implementar o método de Gauss-Seidel? \end{enumerate} \item (15 pontos) Sendo $A = \matdd{5}{1}{1}{2}$ e $A^{-1} \approx \matdd{0.22}{-0.11}{-0.11}{0.56}$: \begin{enumerate}

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

\end{enumerate} \end{enumerate}