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
\left|\varphi(y)-\varphi(x)\right|\le L\,\left|y-x\right|.
Isso significa que \varphi é uma contracção (ou, mais precisamente, é L-Lipschitz) sobre [a,b].

Passo 4

Provar existência de um ponto fixo \xi\in[a,b] (construção pela iteração e convergência).
  • Como \varphi:[a,b]\to[a,b], a sequência definida por x_{k+1}=\varphi(x_k) com x_0\in[a,b] fica totalmente em [a,b].
  • Mostrar que a sequência (x_k) é Cauchy: pelas desigualdades do passo anterior, para quaisquer n\ge m,
\left|x_n-x_m\right| \le \sum_{j=m}^{n-1} \left|x_{j+1}-x_j\right|.
Mas usando a propriedade Lipschitz aplicada a pares consecutivos:
\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|.
Iterando essa desigualdade,
\left|x_{j+1}-x_j\right|\le L^{j}\left|x_1-x_0\right|.
Portanto, para n>m,
\left|x_n-x_m\right|\le \sum_{j=m}^{n-1} L^{j}\left|x_1-x_0\right| \le \sum_{j=m}^{\infty} L^{j}\left|x_1-x_0\right| = \frac{L^{m}}{1-L}\left|x_1-x_0\right|.
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.
  • Aplicando a propriedade Lipschitz:
\left|\xi_1-\xi_2\right| = \left|\varphi(\xi_1)-\varphi(\xi_2)\right| \le L\left|\xi_1-\xi_2\right|.
  • Como 0\le L<1, isto implica (1-L)\left|\xi_1-\xi_2\right|\le 0, logo \left|\xi_1-\xi_2\right|=0 e \xi_1=\xi_2.
  • Conclusão da parte (a): existe exatamente um ponto fixo \xi\in[a,b].

Passo 6

Provar a desigualdade da parte (b) usando o Teorema do Valor Médio e concluir a convergência linear com razão L.
  • Para cada k, aplicar o MVT à função \varphi entre x_k e \xi: existe \eta_k entre x_k e \xi tal que
\varphi(x_k)-\varphi(\xi)=\varphi'(\eta_k)\,(x_k-\xi).
  • Como \varphi(\xi)=\xi e x_{k+1}=\varphi(x_k), obtemos
x_{k+1}-\xi=\varphi'(\eta_k)\,(x_k-\xi).
Tomando valor absoluto e usando \left|\varphi'(\eta_k)\right|\le L:
\left|x_{k+1}-\xi\right|\le L\left|x_k-\xi\right|.
  • Iterando essa desigualdade k vezes (pela recorrência) dá
\left|x_k-\xi\right|\le L^{k}\left|x_0-\xi\right|.
  • 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:
\left|x_k-\xi\right| = \left|\sum_{j=k}^{\infty} (x_{j+1}-x_j)\right| \le \sum_{j=k}^{\infty} \left|x_{j+1}-x_j\right| \le \sum_{j=k}^{\infty} L^{j}\left|x_1-x_0\right|.
  • Somando a série geométrica,
\left|x_k-\xi\right|\le \frac{L^{k}}{1-L}\left|x_1-x_0\right|.
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 é
\frac{L^{k}}{1-L}\left|x_1-x_0\right|<\varepsilon.
Isto equivale a
L^{k} < \frac{(1-L)\varepsilon}{\left|x_1-x_0\right|}.
  • 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.
  • Se f(\xi)=0 então
\varphi(\xi)=\xi-\lambda f(\xi)=\xi-\lambda\cdot 0=\xi,
logo \xi é ponto fixo de \varphi.
  • Recíproco: se \varphi(\xi)=\xi então
\xi=\varphi(\xi)=\xi-\lambda f(\xi).
Subtraindo \xi dos dois lados obtém-se -\lambda f(\xi)=0. Como \lambda\neq0, conclui-se f(\xi)=0.
  • Conclusão: para \varphi(x)=x-\lambda f(x) com \lambda\neq0 vale \varphi(\xi)=\xi se e somente se f(\xi)=0.

Resposta

(a) Existe exatamente um ponto fixo \xi\in[a,b] de \varphi.
(b) Para a sequência x_{k+1}=\varphi(x_k) vale
\left|x_{k+1}-\xi\right|\le L\left|x_k-\xi\right|
e por iteração
\left|x_k-\xi\right|\le L^{k}\left|x_0-\xi\right|.
(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.

Exercícios relacionados