Considere um método iterativo qualquer para sistemas lineares, definido pela sequência tal que
Pode-se mostrar que, se , então:
esta sequência converge para a solução do sistema linear , partindo de qualquer ponto inicial .
(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
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 é