Método do Ponto Fixo (MPF)

Teoria Completa

Introdução

Opa, chega mais! Vamos começar mais um tópico da disciplina de Cálculo Numérico, Esse método não é importante por causa da sua eficiência em si mas sim pela sua importância teórica e conceitual.

Os métodos que veremos a seguir usarão como base a teoria exposta aqui então eu vou explicar da melhor forma possível pra ficar tudo cristalino beleza?

Primeiro vamos entender o que é o tal do Ponto Fixo de uma função. O ponto fixo p de uma função g x é simplesmente um ponto tal que g p = p . Ou seja, é um ponto onde a função g x encontra a reta x = y , de modo que o valor da função em um ponto vale ele mesmo.

O método simplesmente quer transformar a equação f x = 0   em uma equação equivalente x = g x .

Vamos começar com uma brincadeirinha, pega sua calculadora aí!!!

Começando com x0=1, calcule a função f x = cos ⁡ ( x ) e encontre o valor aplicado no ponto. Agora, utilize o valor que você encontrou para aplicar novamente na função. Mais ou menos assim:

f x = cos ⁡ ( x )

x 1 = cos ⁡ 1 = 0,54 0302305

x 2 = cos ⁡ x 1 = 0,857553215

...

x n = cos ⁡ x n - 1

Pra facilitar sua vida, você pode passar a apertar a tecla “igual” da sua calculadora sucessivas vezes, o que acontece? Você está observando o processo de convergência de uma máquina!!!!

Nesse caso, quando chegar em: x 20 = cos ⁡ x 19 = 0,739184399

Provavelmente a sua calculadora vai parar de computar os dados e se fixar nesse valor. Sabe o que isso significa? Que esse ponto E é um ponto fixo de g(x) =cos(x).

Até aqui tudo bem né? Mas para que raios nós usaremos g x ? Essa é a nossa função de iteração. A ideia é aplicarmos essa função na nossa aproximação de modo que ela vá se aproximando cada vez mais da raiz. Teríamos algo do tipo:

x k + 1 = g x k

SHOOOOOW! é agora que esse négocio fica louco. Essa função é uma bela de uma gambiarra.... ops, adaptada g x em que o ponto fixo o zero da nossa f x ! Quando estivermos bem pertinho da raiz, a nossa g x vai começar a nos entregar o mesmo valor já que é o ponto fixo dela!

Ou seja, a partir de um chute inicial x 0 , nós vamos aplicando a função g x até chegarmos numa aproximação boa da nossa raiz.

O problema então deixa de ser encontrar um zero de f x para encontrar um ponto fixo de g x . Vamos ver um exemplo disso então.

Existem exceções, vamos ver? Saca só. Vamos fazer aquele lance da calculadora com a função f x = e x . Vamos comigo, digita aí:

f x = e x

x 1 = e 1 = 2,71828

x 2 = e 2,71828 = 15,15426

x 3 = e 15,15426 = 3814279,11

x 4 = e 3814279,11 = M a t h   E R R O R

EITA! Deu ruim né?

Se sua calculadora é uma científica normalzinha igual a minha é bem provável que tenha aparecido uma mensagem como “Math ERROR”, nesse caso foi porque após 4 iterações acontece aquele fenômeno que vimos no capítulo de erros: overflow.

Ou seja, NEM TODAS AS FUNÇÕES TEM UM PONTO FIXO.

Agora vamos pra um exemplo mais pratico ? Ache um ponto fixo da função g x = - x 2 + 2 .

Sabemos que o ponto fixo p tem a seguinte propriedade:

g p = - p 2 + 2 = p

p 2 + p - 2 = 0

p + 2 p - 1 = 0

Então, como podemos ver, g x possu i como ponto fixo p = - 2 e p = 1 , que é exatamente onde g x cruza a reta x = y :

Se ainda não acredita em mim vamos testar:

g - 2 = - - 2 2 + 2 = - 4 + 2 = - 2

g 1 = - 1 2 + 2 = 1

Show? Até aqui tudo bem? Se não entendeu grita que a gente ajuda haha. Beleza, mas como achamos essa g x aí?

Bom, existem infinitas funções de iteração g x para a equação f x = 0 , que possuem como forma geral:

g x = x + A x f x

onde, seja x * raiz de f , f x * = 0 e A x * ≠ 0 .

Estudo da Convergência

Opa, infinitas funções? Então é tranquilo né? É só achar uma bem fácil e mandar bala? Só que não...Infelizmente não é bem assim não cara. O problema aqui é que nem toda g x vai convergir para a raiz por mais que ela tenha a raiz como ponto fixo! Vou te dar um exemplo:

A equação x 3 + x - 10 = 0 tem como raiz 2 . Duas funções de iteração possíveis para ela são g 1 x = 10 - x 3 e g 2 x = 10 - x 3 (testa aí).

Vamos começar com g 1 x = 10 - x 3 usando chute inicial x 0 = 1.5 .

x 1 = g x 0 = 6.625

x 2 = g x 1 = - 280.775

x 3 = g x 2 = 22134887.375

Bom, definitivamente não está convergindo para o 2 né?

Agora vamos ver com g 2 x = 10 - x 3 e novamente x 0 = 1.5 .

x 1 = g x 0 = 2.04083

x 2 = g x 1 = 1.99659

x 3 = g x 2 = 2.00028

x 4 = g x 3 = 1.99998

Agora sim né? Estamos claramente convergindo para o 2 !

Cacete, e agora? Como vamos saber se escolhemos certo? Temos que começar a testar? Não! Por sorte alguém inventou um teorema que nos dá condições suficientes para que o processo seja convergente xD. Precisamos do seguinte:

Seja x * uma raiz da equação f x = 0 , isolada num intervalo I centrado em x * . E seja g x uma função de iteração para a equação f x = 0 .

Se

g x e g ' x são contínuas em I ;

g ' x ≤ k < 1 , para todo x ∈ I ,

então o processo iterativo x k + 1 = g x k converge para x * .

Outro detalhe interessante é que, satisfeitas as condições acima, quanto menor for g ' x no ponto fixo de g x mais rápido esse método irá convergir para a raiz! Então a melhor função de iteração será a que tiver o menor g ' p , onde p é ponto fixo de g x .Vamos verificar esse teorema? Vamos testar a g 1 x do nosso exemplo:

g 1 x = 10 - x 3

g 1 ' x = - 3 x 2

Ambas são contínuas em R então não teríamos problemas com algum intervalo I .

g 1 ' x < 1 ⇒ 3 x 2 < 1 ⇒ x 2 < 1 3 ⇒ - 1 3 < x < 1 3

Opa, repare que é impossível termos um intervalo I centrado em 2 com g 1 ' x < 1 . Por isso ela não convergiu para a raiz!

Vamos verificar a g 2 x :

g 2 x = 10 - x 3

g 2 ' x = - 1 3 10 - x 2 3

Temos que g 2 x é contínua em R e g 2 ' x é contínua em todos os reais menos o 10 . Então ainda é possível termos um intervalo I centrado em 2 , basta que não englobe o 10 .

g 2 ' x < 1 ⇒ 1 3 10 - x 2 3 < 1 ⇒ 1 < 3 10 - x 2 3 ⇒ 1 3 3 2 < 10 - x ⇒ x < 9.8

Aqui nossa única restrição é que x < 9.8 e x ≠ 10 . Então existem vários intervalos centrados em 2 possíveis que contenham x 0 = 1.5 e satisfaçam as condições acima, como por exemplo 1,3 . E foi por isso que ela convergiu ;)

Critério de Parada

Repare que esse método não usa mais um intervalo, mas um chute inicial! Ou seja, não faria mais sentido usarmos b - a < ε como critério de parada! O que usaremos agora será a variação do valor de x entre duas iterações. Dessa forma, nosso critério de parada será:

x k + 1 - x k < ε

Isso normalmente indica que estamos bem perto da raiz. No entanto em alguns casos esse critério pode ser “enganado” pelo comportamento da função, então é bom ficar de olho também no valor da função f x k . Esse inclusive é outro critério de parada usado nesse método:

f x k < ε