Mudanças entre as edições de "Dago:Numérico:Lista 2"
m (→Custo) |
m |
||
(42 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
Linha 4: | Linha 4: | ||
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: | 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} | + | C = \matddd{4}{3}{1}{-2}{1}{2}{1}{-1}{-1} , d = \vetddd{2}{1}{-1} , b = \vetddd{6}{7}{4} $$ |
==Custo== | ==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: | 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: | ||
− | # Calcular o produto escalar | + | # Calcular o produto escalar <math>u·v = \Sigma_{i=1}^n u_i v_i</math>; |
− | # Multiplicação matriz-vetor | + | # Multiplicação matriz-vetor <math>u = A b</math>; |
− | # Calcular a norma- | + | # 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. |
# Custo para resolver um sistema triangular inferior por substituição; | # Custo para resolver um sistema triangular inferior por substituição; | ||
# Custo para resolver um sistema triangular superior por retro-substituição; | # Custo para resolver um sistema triangular superior por retro-substituição; | ||
− | # Custo da fatoração | + | # Custo da fatoração LU; |
− | # Custo para resolver um sistema usando fatoração | + | # Custo para resolver um sistema usando fatoração LU; |
− | # Custo para resolver $n$ sistemas diferentes usando fatoração | + | # Custo para resolver $n$ sistemas diferentes usando fatoração LU; |
− | # Custo para calcular | + | # Custo para calcular <math>A^{-1}</math>, via resolução de ''n'' sistemas; |
− | # Custo para calcular a norma de Frobenius | + | # 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== | ==Álgebra Matricial== | ||
− | # Resolva o sistema | + | # Resolva o sistema <math>Ax=b</math> usando fatoração LU com e sem pivotamento parcial. |
− | # Resolva o sistema | + | # 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? |
# Calcule: | # Calcule: | ||
## <math>\|b\|_1,\|b\|_2,\|b\|_3,\|b\|_{\infty}</math> | ## <math>\|b\|_1,\|b\|_2,\|b\|_3,\|b\|_{\infty}</math> | ||
Linha 28: | Linha 28: | ||
# Dê as seguintes definições: | # Dê as seguintes definições: | ||
## Norma vetorial; | ## Norma vetorial; | ||
− | ## Número de condição de uma matriz | + | ## Número de condição de uma matriz <math>\kappa(A)</math>; |
## Matriz mal-condicionada e bem-condicionada; | ## Matriz mal-condicionada e bem-condicionada; | ||
− | ## Determinante normalizado da matriz | + | ## Determinante normalizado da matriz <math>norm |A|</math>; |
## Uma matriz diagonal dominante; dê exemplos. | ## Uma matriz diagonal dominante; dê exemplos. | ||
− | # Qual a condição para que o método iterativo | + | # 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? |
# Defina o método de refinamento iterativo. Qual a condição para o método de refinamento iterativo convergir? | # Defina o método de refinamento iterativo. Qual a condição para o método de refinamento iterativo convergir? | ||
# 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? | # 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? | ||
# 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? | # 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== | ==Autovalores== | ||
− | # Para a matriz $A$ no começo dessa lista, descreva e represente graficamente os discos de Gershgorin. Calcule os | + | # 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? |
− | autovalores e represente-os no mesmo gráfico. O que se pode concluir? | ||
# Repita o exercício anterior para a matriz $C$. | # Repita o exercício anterior para a matriz $C$. | ||
− | # Escolha uma matriz rândomica com $5 ×5$ elementos. Represente graficamente os discos de Gershgorin. Se puder, usando | + | # 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. |
− | MATLAB ou sua calculadora, calcule os autovalores e represente-os graficamente. | ||
# 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. | # 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. | ||
# Defina quociente de Rayleigh. | # Defina quociente de Rayleigh. | ||
# Descreva o método da potência, como ele funciona e para que serve. Quando este método nâo funciona? | # Descreva o método da potência, como ele funciona e para que serve. Quando este método nâo funciona? | ||
− | # Calcule via método da potência o maior autovalor de | + | # Calcule via método da potência o maior autovalor de ''A''. |
− | # Calcule via método da potência o maior autovalor de | + | # Calcule via método da potência o maior autovalor de ''C''. |
− | # Considere a matriz | + | # 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>. |
− | # Considere a matriz | + | # 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. |
− | # Utilize o método de iteração inversa com o quociente de Rayleigh e calcule um autovalor de | + | # Utilize o método de iteração inversa com o quociente de Rayleigh e calcule um autovalor de ''A''. O que se pode concluir. |
− | # Considere a matriz | + | # Considere a matriz ''C'' e repita o três exercícios anteriores. |
==Interpolação== | ==Interpolação== | ||
# Defina uma matriz de Vandermonde. Qual o problema desta matriz. Dê um exemplo. | # Defina uma matriz de Vandermonde. Qual o problema desta matriz. Dê um exemplo. | ||
# Para a seguinte tabela de valores, utilize interpolação polinomial e calcule o polinômio interpolador de ordem $2$. | # Para a seguinte tabela de valores, utilize interpolação polinomial e calcule o polinômio interpolador de ordem $2$. | ||
− | x & 2 & 4 & 5 | + | x & 2 & 4 & 5 |
− | y(x) & 0 & 3 & 1 | + | y(x) & 0 & 3 & 1 |
Desenhe o gráfico do polinômio interpolador e os pontos da tabela. | Desenhe o gráfico do polinômio interpolador e os pontos da tabela. | ||
Linha 62: | Linha 61: | ||
# Repita o exercício anterior usando a forma de Lagrange. | # Repita o exercício anterior usando a forma de Lagrange. | ||
# Usando uma calculadora ou MATLAB, calcule o polinômio interpolador de ordem $4$. | # Usando uma calculadora ou MATLAB, calcule o polinômio interpolador de ordem $4$. | ||
− | x & 2 & 4 & 5 & 5.5 & 8 | + | x & 2 & 4 & 5 & 5.5 & 8 |
− | y(x) & 0 & 3 & 1 & -1 & 2 | + | 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. | Desenhe o gráfico do polinômio interpolador e os pontos da tabela. O que se pode concluir. | ||
# 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$. | # 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$. | ||
# Repita o exercício anterior usando a forma de Lagrange. | # Repita o exercício anterior usando a forma de Lagrange. | ||
# Usando a forma de Newton e diferenças simples, calcule o polinômio interpolador da seguinte tabela | # Usando a forma de Newton e diferenças simples, calcule o polinômio interpolador da seguinte tabela | ||
− | x & 2 & 3 & 4 & 5 & 6 | + | x & 2 & 3 & 4 & 5 & 6 |
− | y(x) & 0 & 3 & 1 & -1& 2 | + | 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$. | 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$. | ||
# Para a seguinte tabela de valores, utilize uma interpolação por splines cúbicas: | # Para a seguinte tabela de valores, utilize uma interpolação por splines cúbicas: | ||
− | x & 2 & 4 & 5 | + | x & 2 & 4 & 5 |
− | y(x) & 0 & 3 & 1 | + | 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. | Desenhe o gráfico do polinômio interpolador e os pontos da tabela. Utilize as fórmulas para Splines do livro. |
Edição atual tal como às 11h02min de 16 de novembro de 2012
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:
- Calcular o produto escalar <math>u·v = \Sigma_{i=1}^n u_i v_i</math>;
- Multiplicação matriz-vetor <math>u = A b</math>;
- 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.
- Custo para resolver um sistema triangular inferior por substituição;
- Custo para resolver um sistema triangular superior por retro-substituição;
- Custo da fatoração LU;
- Custo para resolver um sistema usando fatoração LU;
- Custo para resolver $n$ sistemas diferentes usando fatoração LU;
- Custo para calcular <math>A^{-1}</math>, via resolução de n sistemas;
- 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
- Resolva o sistema <math>Ax=b</math> usando fatoração LU com e sem pivotamento parcial.
- 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?
- Calcule:
- <math>\|b\|_1,\|b\|_2,\|b\|_3,\|b\|_{\infty}</math>
- <math>\|A\|_1,\|A\|_{\infty},\kappa_1(A)=\|A\|\|A^{-1}\|_1,\kappa_\infty(A)=\|A\|_\infty\|A^{-1}\|</math>
- Dê as seguintes definições:
- Norma vetorial;
- Número de condição de uma matriz <math>\kappa(A)</math>;
- Matriz mal-condicionada e bem-condicionada;
- Determinante normalizado da matriz <math>norm |A|</math>;
- Uma matriz diagonal dominante; dê exemplos.
- 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?
- Defina o método de refinamento iterativo. Qual a condição para o método de refinamento iterativo convergir?
- 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?
- 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
- 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?
- Repita o exercício anterior para a matriz $C$.
- 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.
- 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.
- Defina quociente de Rayleigh.
- Descreva o método da potência, como ele funciona e para que serve. Quando este método nâo funciona?
- Calcule via método da potência o maior autovalor de A.
- Calcule via método da potência o maior autovalor de C.
- 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>.
- 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.
- Utilize o método de iteração inversa com o quociente de Rayleigh e calcule um autovalor de A. O que se pode concluir.
- Considere a matriz C e repita o três exercícios anteriores.
Interpolação
- Defina uma matriz de Vandermonde. Qual o problema desta matriz. Dê um exemplo.
- 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.
- 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$.
- Repita o exercício anterior usando a forma de Lagrange.
- 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.
- 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$.
- Repita o exercício anterior usando a forma de Lagrange.
- 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$.
- 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.