Exercício 16 (Teórico) - Convergência linear do Ponto Fixo
Seja \varphi:[a, b] \rightarrow[a, b] diferenciável com \left|\varphi^{\prime}(x)\right| \leq L<1 para todo x \in[a, b].
(a) Prove que \varphi possui exatamente um ponto fixo \xi \in[a, b].
(b) Usando o Teorema do Valor Médio, prove que \left|x_{k+1}-\xi\right| \leq L\left|x_{k}-\xi\right| e conclua que \left|x_{k}-\xi\right| \leq L^{k}\left|x_{0}-\xi\right|.
(c) Deduza a estimativa do número mínimo de iterações para garantir \left|x_{k}-\xi\right|< \varepsilon :
k \geq \frac{\ln \left(\frac{(1-L) \varepsilon}{\left|x_{1}-x_{0}\right|}\right)}{\ln L} .
(d) Mostre que f(x)=0 se e somente se \varphi(\xi)=\xi, para \varphi(x)=x-\lambda f(x), \lambda \neq 0.
Passo 1
Vou listar claramente o que o enunciado nos dá e o que pede (sem resolver nada ainda).
Dados do enunciado:
\varphi:[a,b]\to[a,b] é diferenciável.
Existe L com 0\le L<1 tal que \left|\varphi'(x)\right|\le L para todo x\in[a,b].
Considera-se a iteração de ponto fixo x_{k+1}=\varphi(x_k) com um x_0\in[a,b] qualquer (isso é usado na parte (b)).
O enunciado pede:
(a) Provar que \varphi possui exatamente um ponto fixo \xi\in[a,b].
(b) Usando o Teorema do Valor Médio, provar que \left|x_{k+1}-\xi\right|\le L\left|x_k-\xi\right| e concluir que \left|x_k-\xi\right|\le L^{k}\left|x_0-\xi\right|.
(c) Deduzir a estimativa do número mínimo de iterações para garantir \left|x_k-\xi\right|<\varepsilon:
k \geq \frac{\ln\!\left(\dfrac{(1-L)\varepsilon}{\left|x_1-x_0\right|}\right)}{\ln L}.
(d) Mostrar que, para \varphi(x)=x-\lambda f(x) com \lambda\neq0, vale f(x)=0 se e somente se \varphi(\xi)=\xi.
Passo 2
Explicar o Teorema do Valor Médio (MVT) e como ele será usado.
Enunciado do Teorema do Valor Médio (versão que usaremos): se g é contínua em [u,v] e diferenciável em (u,v), então existe \eta\in(u,v) tal que
g(v)-g(u)=g'(\eta)\,(v-u).
Interpretação simples: a diferença média no valor de g entre dois pontos é igual à derivada em algum ponto intermediário multiplicada pela diferença dos abscissas. Isso permite relacionar diferenças de função com a derivada, o que é perfeito para obter desigualdades do tipo Lipschitz.
Passo 3
Usar o MVT para mostrar que \varphi é Lipschitz com constante L: para quaisquer x,y\in[a,b] existe \eta entre x e y tal que
\varphi(y)-\varphi(x)=\varphi'(\eta)\,(y-x).
Tomando valor absoluto e usando \left|\varphi'(\eta)\right|\le L obtemos
Como 0\le L<1, o termo \dfrac{L^{m}}{1-L}\left|x_1-x_0\right| tende a 0 quando m\to\infty. Assim (x_k) é Cauchy. Como [a,b]\subset\mathbb{R} é completo, (x_k) converge para algum \xi\in[a,b].
Passar ao limite na relação x_{k+1}=\varphi(x_k) e usar continuidade de \varphi (decorrente da diferenciabilidade) dá
\xi=\varphi(\xi),
ou seja, \xi é um ponto fixo.
Passo 5
Provar unicidade do ponto fixo (argumento direto usando contracção).
Suponha que existem dois pontos fixos \xi_1,\xi_2\in[a,b] com \varphi(\xi_1)=\xi_1 e \varphi(\xi_2)=\xi_2.
Interpretação didática: isso mostra convergência do tipo geométrico (linear) com fator de redução por iteração igual a L. Ou seja, a cada iteração o erro é reduzido (no máximo) por um fator L.
Passo 7
Derivar a estimativa mais prática usada na parte (c): ligar o erro ao tamanho do primeiro passo e obter a condição sobre k.
Dos passos anteriores já temos que as diferenças sucessivas satisfazem
\left|x_{j+1}-x_j\right|\le L^{j}\left|x_1-x_0\right|\quad\text{para todo }j\ge0.
(Isto vem de aplicar recursivamente \left|x_{j+1}-x_j\right|=\left|\varphi(x_j)-\varphi(x_{j-1})\right|\le L\left|x_j-x_{j-1}\right|.)
Escrevemos o erro como soma do resto da série das diferenças:
Esta desigualdade é frequentemente mais útil na prática porque usa \left|x_1-x_0\right|, um dado computável, em vez de \left|x_0-\xi\right| que depende do ponto fixo desconhecido.
Queremos garantir \left|x_k-\xi\right|<\varepsilon. Uma condição suficiente é
Tomando logaritmo natural dos dois lados (note que \ln L<0 porque 0\le L<1) obtemos
k\ln L < \ln\!\left(\frac{(1-L)\varepsilon}{\left|x_1-x_0\right|}\right).
Dividindo por \ln L (número negativo) inverte-se a desigualdade, resultando
k > \frac{\ln\!\left(\dfrac{(1-L)\varepsilon}{\left|x_1-x_0\right|}\right)}{\ln L}.
Portanto, para garantir \left|x_k-\xi\right|<\varepsilon basta tomar qualquer inteiro k que satisfaça
k \ge \frac{\ln\!\left(\dfrac{(1-L)\varepsilon}{\left|x_1-x_0\right|}\right)}{\ln L},
lembrando que na prática toma-se o teto (ceiling) desse número para obter um k inteiro. Observação: se \left|x_1-x_0\right|=0 então x_1=x_0 e necessariamente x_0 é ponto fixo (porque x_1=\varphi(x_0)=x_0), caso em que já se tem erro zero e não é necessário iterar.
Passo 8
Provar a equivalência pedida na parte (d) para \varphi(x)=x-\lambda f(x) com \lambda\neq0.
(c) Usando a estimativa \left|x_k-\xi\right|\le \dfrac{L^{k}}{1-L}\left|x_1-x_0\right|, para garantir \left|x_k-\xi\right|<\varepsilon basta escolher k satisfazendo
k \ge \frac{\ln\!\left(\dfrac{(1-L)\varepsilon}{\left|x_1-x_0\right|}\right)}{\ln L}.
(d) Para \varphi(x)=x-\lambda f(x) com \lambda\neq0 tem-se \varphi(\xi)=\xi \iff f(\xi)=0.