Considere um método iterativo qualquer para sistemas lineares, definido pela sequência x^(k)k=0^+infty tal que
x^(k+1)=P x^(k)+c
Pode-se mostrar que, se |P|<1, então:
  • esta sequência converge para a solução x^* do sistema linear A x=b, partindo de qualquer ponto inicial x^(0).
  • |x^(k)-x^*| <= |P|^k1-|P||x^(1)-x^(0)| (star).
    (a) Utilizando a desigualdade (star), mostre que uma estimativa do número k de iterações necessárias para garantir que uma solução aproximada do sistema linear A x=b seja encontrada com uma tolerância varepsilon>0 é dada por
k>ln (1-|P|)+ln (varepsilon)-ln (|x^(1)-x^(0)|)ln (|P|)
(b) Considere o sistema linear
rlrl 10 x1+5 x2 & & & 6 5 x1+10 x2 & -4 x3 & & =25 -4 x2 & +8 x3- & x4 & = & -11 & -x3+5 x4 & = & -11
Encontre o número mínimo de iterações necessárias para garantir que o Método de Gauss-Jacobi encontre uma solução aproximada deste sistema com uma tolerância varepsilon=10^-6, partindo do ponto inicial x^(0)=[llll0 & 0 & 0 & 0]^T, usando a estimativa obtida no item (a).

Passo 1

Beleza, resumo rápido do que o exercício pede:
Temos um método iterativo para resolver x^(k+1)=P,x^(k)+c dado por
|x^(k)-x^*|;<=;|P|^k1-|P|,|x^(1)-x^(0)| (star)
e sabemos que, se k>ln(1-|P|)+ln(varepsilon)-lnl|x^(1)-x^(0)r|ln(|P|) , então a sequência converge e vale o “erro”
(a) A gente vai usar pra mostrar que, para chegar num erro , basta
(b) Depois aplicar isso ao Método de Gauss-Jacobi de um sistema 4×4, encontrando o , calculando e , e aí botar tudo na fórmula pra e .
Conteúdo: método iterativo, norma de matriz, desigualdade de erro, logaritmo e troca de sinal da desigualdade ao dividir por .

Passo 2

Derivando o item (a): queremos
|x^(k)-x^*|;<=;varepsilon
Pela desigualdade |P|^k1-|P|,|x^(1)-x^(0)|;<=;varepsilon ;Longrightarrow; |P|^k ;<=;(1-|P|),varepsilon|x^(1)-x^(0)| :
k,ln(|P|);<=;ln(1-|P|)+ln(varepsilon)-lnl|x^(1)-x^(0)r|
Agora tomamos log em ambos os lados:
boxed k>ln(1-|P|)+ln(varepsilon)-lnl|x^(1)-x^(0)r|ln(|P|)
Como , ao dividir por a desigualdade inverte, dando exatamente

Passo 3

Agora o sistema do Gauss-Jacobi:
10x1+5x2 =6, 5x1+10x2-4x3 =25, -4x2+8x3 -x4 =-11, -,x3+5x4 =-11
No Jacobi escrevemos P=-D^-1(L+U), c=D^-1b e P= 0 &-0.5 &0 &0 -0.5&0 &0.4 &0 0 &0.5 &0 &0.125 0 &0 &0.2 &0 , c=0.62.5-1.375-2.2 .
Isso dá
|P|infty=maxisumj|Pij| =max0.5,;0.9,;0.625,;0.2=0.9, |x^(1)-x^(0)|infty=|c|infty=2.5
Resolvendo equação a equação:
x₁: .
x₂: .
x₃: .
x₄: .
Logo
Como , temos .
Escolhendo a norma infinito,

Passo 4

Basta botar na fórmula de (a):
k>ln(1-0.9)+ln(10^-6)-ln(2.5)ln(0.9) =ln(0.1)-13.81551-0.91629-0.1053605 approx161.6
Como tem que ser inteiro, a gente arredonda para cima:

Resposta

O número mínimo de iterações é .

Exercícios relacionados