- Demostre convergência do algoritmo iterativo com a função de iteração
. Qual equação resolve este algoritmo?
- Dado sistema linear
Passo 1
Enunciado e o que se pede:
- Item 3: temos a função de iteração
. Pede-se demonstrar a convergência do algoritmo iterativo (isto é, da sequência definida por ) e responder qual equação esse algoritmo resolve. - Item 4: resolve o sistema linear
Essas são todas as informações fornecidas; agora vamos passo a passo demonstrar, ensinar o que é necessário e resolver.
Passo 2
O que é o algoritmo iterativo e o que significa convergência aqui:
- O algoritmo iterativo de ponto fixo gera uma sequência
pela regra
- O objetivo é encontrar um ponto
tal que . Esse é chamado de ponto fixo de . - “Demonstrar convergência” significa provar que, para qualquer chute inicial (ou para chutes num certo intervalo), a sequência
tende a um limite que satisfaz . - A equação que o algoritmo resolve é justamente a equação do ponto fixo
No nosso caso, a equação será escrita explicitamente mais adiante.
Passo 3
Estratégia para provar convergência (intuição e ferramenta): contração e derivada
- Uma maneira prática e comum de provar convergência de
é mostrar que é uma contração: existe com tal que
para todos
em um certo intervalo (ou globalmente). Se
é uma contração, o Teorema do Ponto Fixo de Banach garante existência e unicidade do ponto fixo e convergência da iteração para esse ponto fixo, para qualquer chute inicial no intervalo.
- Uma forma prática de obter esse
é usar a derivada de : se é diferenciável e para todo no intervalo, então é Lipschitz com constante (isto é, a desigualdade acima vale).
Passo 4
Calcular a derivada de
e obter o fator de contração
- Primeiro calculemos a derivada de
. Usando a regra da cadeia:
- Agora observamos o valor absoluto:
- Como para qualquer número
vale , temos
- Logo podemos escolher
. Como , tem derivada com módulo no máximo em toda a reta, portanto é Lipschitz com constante em .
Passo 5
Aplicar o argumento da contração (explicado de modo simples)
- Pelo Lema do valor médio (ou pela propriedade da derivada limitada), para quaisquer
existe entre e tal que
Tomando valores absolutos e usando o limite da derivada, obtemos
- Portanto
é uma contração global com constante . Pelo Teorema do Ponto Fixo de Banach:- Existe exatamente um ponto
tal que . - Para qualquer chute inicial
, a sequência definida por converge para esse único .
- Existe exatamente um ponto
- Em palavras mais amigas: a função “puxa” distâncias pela metade no máximo a cada iteração, então os termos vão ficando cada vez mais próximos e convergem para um ponto fixo único.
Passo 6
Escrever explicitamente a equação que o algoritmo resolve e comentar sobre solução numérica
- A equação do ponto fixo é
- Essa é a equação que o algoritmo iterativo resolve: qualquer limite
satisfaz
- Observação prática: não existe uma fórmula fechada elementar para resolver
, por isso usamos iteração numérica (o próprio método de ponto fixo) ou outros métodos numéricos para obter uma aproximação do valor de . Como é contração com , a convergência é linear e rápida, e há também estimativas de erro do tipo
que permitem controlar quantas iterações precisar para atingir uma precisão desejada.
Passo 7
Resolver o sistema linear (método de eliminação simples, passo a passo)
- Sistema:
- Soma as duas equações para eliminar
: somando membro a membro,
- No lado esquerdo, os termos em
se anulam: . No lado direito, . Logo,
- Divide ambos os lados por
:
- Agora substitua
em uma das equações para encontrar . Usando a segunda equação :
- Isolando
:
- Conclusão: a solução do sistema é
e . Sempre é bom checar substituindo na primeira equação: (ok).
Resposta
- O algoritmo converge globalmente (para qualquer
) porque tem ; a equação que ele resolve é . -
.