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^*varepsilon|<= |P|^k1-|P|| x^(1)-x^(0) |
    (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|)

Passo 1

Beleza, então o enunciado diz que temos um método iterativo para resolver x^(k+1) = P,x^(k) + c, , dado por
|x^(k)-x^*|;<=;|P|^k1-|P|,l|x^(1)-x^(0)r|
e que, se , o erro satisfaz
O que a gente quer agora é descobrir quantas iterações são necessárias para que .
Matéria envolvida: convergência de métodos iterativos para sistemas lineares e manipulação de desigualdades usando logaritmo.

Passo 2

Começando pela desigualdade de erro que já temos (vou chamar de |x^(k)-x^*|;<=;|P|^k1-|P|,l|x^(1)-x^(0)r| ):

Passo 3

Impondo a tolerância, a gente quer
|x^(k)-x^*|;<=;varepsilon
Então, usando |P|^k1-|P|,l|x^(1)-x^(0)r|;<=;varepsilon , fica

Passo 4

Isolando |P|^k ;<=; (1-|P|),varepsilonl|x^(1)-x^(0)r| , multiplicamos ambos os lados por :

Passo 5

Agora tá na hora do logaritmo, porque lnl(|P|^kr) ;<=; ln!l((1-|P|),varepsilon|x^(1)-x^(0)|r) vira k,ln(|P|);<=;ln(1-|P|) + ln(varepsilon);-;lnl|x^(1)-x^(0)r| . Aplicando nos dois lados:
Como , isso dá

Passo 6

Importante: k ;>=; ln(1-|P|) + ln(varepsilon);-;lnl|x^(1)-x^(0)r|ln(|P|) porque k ;>; ln(1-|P|) + ln(varepsilon);-;lnl|x^(1)-x^(0)r|ln(|P|) . Quando a gente divide pela , o sinal da desigualdade inverte. Logo
E, como queremos um número de iterações estritamente maior para garantir a tolerância, escrevemos

Resposta

Uma estimativa para o número de iterações boxedk>ln(1-|P|)+ln(varepsilon)-lnl|x^(1)-x^(0)r|ln(|P|) necessárias é

Exercícios relacionados