- Prove que o algoritmo iterativo
Passo 1
Enunciado (o que temos e o que pedem): temos o processo iterativo
ou seja, definimos
por
O que nos pedem (vou assumir a formulação natural dada a um algoritmo iterativo): provar que a sequência
gerada por
converge para um ponto fixo de
, isto é, existe
tal que
e que essa convergência é global (para qualquer
) e com uma taxa que podemos estimar. Informação adicional útil que vem do enunciado: a função
tem imagem
, logo
. A partir daqui começo a resolver.
Passo 2
Plano de ataque e ideia principal (sem formalidade excessiva): uma maneira padrão de provar que iterações
convergem é mostrar que
é uma contração (ou seja, que existe
tal que
para todos
). Se
for contração em
(que é um espaço completo), então o Teorema do Ponto Fixo de Banach garante que existe um único ponto fixo
e que, para qualquer
, a sequência
converge geometricamente para
. Vou explicar por que isso funciona e depois calcular um
para o nosso
.
Passo 3
Lembrete útil (fórmula/teorema usado): se
é diferenciável e
é limitada por
em um intervalo (ou em
), então pelo Teorema do Valor Médio temos
Ou seja, um majorante de
é um candidato a constante de Lipschitz. Vou calcular
e encontrar esse majorante.
Passo 4
Cálculo da derivada (passo a passo, explicando a regra da cadeia): definimos
. A derivada de
em relação a
é
. Aqui
e
. Aplicando a regra da cadeia,
Podemos escrever isso de forma um pouco mais organizada:
Passo 5
Encontrar um
e concluir que
é contração: observe que
para todo
, portanto
O máximo absoluto de
em
ocorre em
, onde
. Assim podemos escolher
e garantir que, para todos
,
Portanto
é uma contração global com constante de Lipschitz
.
Passo 6
Aplicar o Teorema do Ponto Fixo de Banach (explicando de forma intuitiva): como
é um espaço completo e
é contração com constante
, o Teorema do Ponto Fixo de Banach garante:
- existe um único ponto fixo
tal que ; - para qualquer condição inicial
, a sequência definida por converge para .
Intuição do porquê: a desigualdade de contração dá
Iterando essa desigualdade obtemos o controle explícito do erro.
Passo 7
Estimativa explícita do erro e da taxa de convergência (útil na prova e na prova prática): a desigualdade do passo anterior, aplicada repetidamente, dá
Isto mostra que a convergência é linear (geométrica) com razão (constante assintótica) no máximo
. Em particular, após
iterações o erro é reduzido por um fator
em relação ao erro inicial.
Passo 8
Comentários finais didáticos e um exemplo numérico rápido (para intuição): como
a sequência fica rapidamente contida nesse intervalo; e pela constante
já sabemos que poucos passos reduzem bastante o erro. Exemplo: se
,
e a partir daí os valores se aproximam rapidamente do ponto fixo
. (Aqui só fiz uma conta para sentir como a iteração se comporta; a prova acima é geral.)
Resposta
A função
satisfaz
para todo
, logo é uma contração com constante
. Pelo Teorema do Ponto Fixo de Banach existe um único ponto fixo
tal que
e, para qualquer
, a sequência definida por
converge para
com erro satisfeito por
.