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.

Se eu te pedisse pra encontrar uma raíz da função f x = x ³ - x - 1 , no intervalo [ 1,2 ] você saberia me dizer com facilidade? Caso não saiba, fique tranquilo!! Iremos mostrar aqui um novo método para encontrar esse zero da função: o Método do Ponto Fixo.

Nem sempre é fácil achar os zeros de uma função, às vezes as técnicas que aprendemos são ineficientes e acabamos dando voltas e mais voltas sem conseguir resolver o problema e encontrar as raízes da função.

Muitas vezes quando nos deparamos com um problema difícil de resolver nós substituímos ele por outro equivalente mais fácil de resolver. E é exatamente isso que vamos fazer neste tópico! Substituir o problema de encontrar os zeros da função por outro problema: Encontrar o ponto fixo de uma outra função! Calma que já já vamos ver como funciona esse macete!

Ponto Fixo de uma função qualquer

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.

Por exemplo:

A função g ( x ) = 3 x tem como ponto fixo o ponto x = 0 porque g ( 0 ) = 3.0 = 0

A função g ( x ) = 2 x - 1 tem como ponto fixo x = 1   porque g ( 1 ) = 2.1 - 1 = 1

AAAAh, e nada impede de uma função ter mais de 1 ponto fixo. Por exemplo:

A função g ( x ) = 4 x ² tem como ponto fixo x = 0   e x = 1 4

Ok, mas o que isso tem a ver com os zeros de uma função? Vem comigo que já vou explicar...

Método do Ponto Fixo

Imagina que queremos encontrar as raízes de uma função f ( x ) , mas não conseguimos encontrar a resposta igualando a função a zero…

Para resolver esse problema podemos aplicar o Método do Ponto Fixo. O método simplesmente quer transformar a equação f x = 0   em uma equação equivalente x = g x .

Ok ... um pouco mais devagar... O que está acontecendo aqui? Vamos tentar entender aos poucos, beleza?!

A partir da expressão f ( x ) = 0 (que é nosso problema inicial) podemos determinar uma nova expressão g ( x ) = x e encontrar as raízes da equação.

Note que o x   que é raiz de f ( x ) e ponto fixo da g ( x ) !

Essa função g ( x ) é chamada de função de iteração! E ela tem essa cara:

x k + 1 = g x k

Ou seja, o valor do x atual ( x k + 1 ) depende do valor da função anterior g x k .

Mas como funciona na prática essa g ( x ) ? Vamos ver um exemplo:

Exemplo

Começando com x 0 = 1 , calcule a função g x = x + 1 3 e encontre os próximos valores aplicados no ponto.

Vamos começar calculando o x 0 = 1 da função:

g x = x + 1 3

x 1 = g x 0 = 1 + 1 3 = 1,25992105

Agora, utilize o valor que você encontrou para aplicar novamente na função

x 2 = g x 1 = x 1 + 1 3 = 1,312293873

x 3 = g x 2 = x 2 + 1 3 = 1,32235381

x 4 = g x 3 = x 3 + 1 3 = 1,324268745

Percebe que os valores cada vez mais estão se aproximando? Convergindo para um número? Você está observando o processo de convergência. Isso porque x = 1,324   é o ponto fixo dessa função.

Aí você pode me perguntar: Beleza, mas que que isso tudo tem haver com os zeros da função f x   que queríamos calcular desde o começo?

A resposta é que quanto mais próximo o valor de x em f ( x ) chegar no zero da função, mas próximo o valor de x chega do ponto fixo de g ( x ) !

Ou seja, quanto mais próximo a gente estiver de encontrar o ponto fixo de g ( x ) também estaremos mais próximos de encontrar o valor do zero da função.

Lindo, não?! hahaha

Tá, mas e como encontrar a função g ( x ) a partir da f ( x ) ?

Bom, existem infinitas funções de iteração g x para a equação f x = 0 . O que elas possuem em comum é a forma geral:

g x = x + A x f x

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

Vamos tentar um exemplo prático?!

Exemplo

Seja f x = x ³ - x - 1 . Queremos encontrar uma raiz no intervalo [ 1,2 ] . Tome x 0 = 1 .

Vamos lá! Precisamos encontrar nossa g x . Temos que f x = 0 , pois queremos uma raíz. Podemos isolar o x nessa equação :

x ³ - x - 1 = 0

x ³ = x + 1

x = x + 1 3

Lembra que a carinha da função de iteração é x k + 1 = g x k ?! Então conseguimos encontrar a nossa g x !!

Já calculamos seu ponto fixo anteriormente:

x 1 = g x 0 = 1 + 1 3 = 1,25992105

x 2 = g x 1 = x 1 + 1 3 = 1,312293873

x 3 = g x 2 = x 2 + 1 3 = 1,32235381

x 4 = g x 3 = x 3 + 1 3 = 1,324268745

Se o ponto fixo então é x = 1,324 , então encontramos a raíz procurada! Show de bola?!

Assim, a raiz de f x = x ³ - x - 1 no intervalo 1,2   é x = 1,324 .

Estudo da Convergência

Opa, ali em cima tava escrito infinitas funções?

Seria ótimo se todas as funções de interação funcionassem e convergissem para um ponto fixo né? BUT, infelizmente isso não acontece sempre.

O problema aqui é que nem toda g x vai convergir para a raíz, por mais que ela tenha a raíz como ponto fixo! Vou te dar um exemplo:

A equação x 3 + x - 10 = 0 tem como raiz x = 2 . Há duas funções de iteração possíveis para ela:

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

Vamos analisar primeiro 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 !

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. 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 raíz! 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 raíz!

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, belezinha?! ;)

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 < ε

Algoritmo

Chegamos na parte do Algoritmo novamente, onde eu escrevo o procedimento da maneira mais simples possível para ser passada para alguma linguagem. Vamos lá então:

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Aproximação inicial x 0

b. Precisão do resultado final ε 1 e ε 2

Passo 2. Definimos um contador de iterações k = 0 .

Passo 3. Se f x 0 < ε 1 , escolha x 0 como x _ e FIM. Caso contrário, continue para o Passo 4.

Passo 4. k = k + 1 , aumentamos uma iteração no contador.

Passo 5. x = g x 0

Passo 6. Se x - x 0 < ε 2 , escolha x como x _ e FIM. Caso contrário continue para o Passo 7.

Passo 7. x 0 = x

Passo 8. Voltamos para o Passo 3 .

Como sempre, um bom critério de parada para se adicionar também é um número máximo de iterações.

O chato aqui é que para cada função que formos encontrar o zero teremos que definí-la e definir também uma g x para ela no nosso programa, ou seja, mais trabalho pra gente... mas é a vida! ahahahaha

Agora vamos exercitar! Mas repito, o mais importante aqui é que o conceito tenha sido bem entendido!!! 😊

Expandir

Exercício Resolvido #1

Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 65, exercício 6 adaptado

Use o método do Ponto Fixo para determinar a solução com precisão de 10 - 3 para a equação x 3 - x - 1 = 0 no intervalo 1,2 . Use x 0 = 1

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Primeiro precisamos encontrar uma função de iteração g x = x convergente. Se liga:

x 3 - x - 1 = 0

x 3 = x + 1

x = x + 1 3

Como g x = x ,

g x = x + 1 3

Beleza, achamos uma função de iteração. Agora vamos testar se ela é convergente:

g x = x + 1 3

g ' x = 1 3 x + 1 2 3

g x é contínua em todo R e g ' x é contínua em todo R menos o - 1 .

g ' x = 1 3 x + 1 2 3 < 1 ⇒ 1 < 3 x + 1 2 3 ⇒ 1 3 3 2 < x + 1 ⇒ x > - 0.81

Como nossa raiz está no intervalo 1,2 , não será problema definir um intervalo I centralizado na raiz e que contenha x 0 = 1 obedecendo às condições acima. Logo, essa função converge para a nossa raiz.

Passo 2

x 0 = 1

ε 1 = ε 2 = 0 . 0 0 1

Iteração 1 :

x 1 = g x 0 = 1.2599

Critério de Parada:

x 1 - x 0 = 0.2 599 > 0.0 0 1

f x 1 = 0.2 599 > 0.0 0 1

Como não alcançamos o critério de parada continuamos as iterações.

x 1 = 1.2 599

ε 1 = ε 2 = 0 . 0 01

Iteração 2 :

x 2 = g x 1 = 1.312 3

Critério de Parada:

x 2 - x 1 = 0.052 4 > 0.0 0 1

f x 2 = 0.052 4 > 0.0 0 1

Como não alcançamos o critério de parada continuamos as iterações.

x 2 = 1.312 3

ε 1 = ε 2 = 0 . 0 0 1

Iteração 3 :

x 3 = g x 2 = 1.322 4

Critério de Parada:

x 3 - x 2 = 0.01 01 > 0.0 0 1

f x 3 = 0.01 01 > 0.0 0 1

Como não alcançamos o critério de parada continuamos as iterações.

x 3 = 1.3224

ε 1 = ε 2 = 0.001

Iteração 4 :

x 4 = g x 3 = 1.3243

Critério de Parada:

x 4 - x 3 = 0.0019 > 0.001

f x 4 = 0.0019 > 0.001

Como não alcançamos o critério de parada continuamos as iterações.

x 4 = 1.3243

ε 1 = ε 2 = 0.001

Iteração 5 :

x 5 = g x 4 = 1.3246

Critério de Parada:

x 5 - x 4 = 0.0004 < 0.001

f x 5 = 0.0004 < 0.001

Beleza, alcançamos o critério de parada! Então nossa aproximação é x - = 1.3246 .

Resposta

x - = 1.3246 .

Exercício Resolvido #2

Lista 2 – Professora Juliana – UFRJ – Questão 3 – Item i Adaptada

Seja f x = x 2 - 4 sin ⁡ x . Determine um intervalo onde se encontre uma raiz e encontre uma função de iteração convergente para qualquer x 0 no intervalo. Em seguida, aplique o método do ponto fixo para encontrar uma aproximação da raiz com precisão de 10 - 4 .

Obs.: Desconsidere a raiz x = 0 .

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Poxa, x = 0 tava molinho pra gente né? Mas não tem problema, vamos achar a outra raiz:

f 0 = 0

f 1 = 1 - 4 sin ⁡ 1 ≅ - 2.37

f 2 = 4 - 4 sin ⁡ 2 ≅ 0.36

Beleza, sabemos que existe uma raiz no intervalo 1,2 !

Passo 2

Agora vamos encontrar uma função de iteração g x = x convergente.

x 2 - 4 sin ⁡ x = 0

x 2 = 4 sin ⁡ x

x = 4 sin ⁡ x

x = 2 sin ⁡ x

Como g x = x ,

g x = 2 sin ⁡ x

Beleza, achamos uma função de iteração. Agora vamos testar se ela é convergente:

g x = 2 sin ⁡ x

g ' x = cos ⁡ x sin ⁡ x

g x é contínua para sin ⁡ x ≥ 0 , ou seja, x ∈ 2 n π , 2 n + 1 π , n ∈ R . O que quer dizer que ela é contínua em 0 , π , o que engloba nosso intervalo 1,2 .

g ' x é contínua para sin ⁡ x > 0 , ou seja, x ∈   ] 2 n π , ( 2 n + 1 ) π ] ,   n ∈ R . O que quer dizer que ela é contínua em ] 0 , π ] , o que engloba nosso intervalo 1,2 .

g ' x = cos ⁡ x sin ⁡ x < 1

A função g ' x é decrescente no intervalo 0 , π . Como g ' 1 ≅ 0.589 e g ' 2 ≅ - 0.436 , é seguro afirmar que em nenhum momento seu módulo é maior que 1 no intervalo 1,2 .

Logo, podemos ver que essa função de iteração converge.

Passo 3

Vamos tomar como estimativa inicial x 0 = 2

x 0 = 2

ε 1 = ε 2 = 0.0001

Iteração 1 :

x 1 = g x 0 = 1.90714

Critério de Parada:

x 1 - x 0 = 0.09285 > 0.0 0 01

f x 1 = 0.13868 > 0.00 0 1

Como não alcançamos o critério de parada continuamos as iterações.

x 1 = 1.90714

ε 1 = ε 2 = 0.0 0 01

Iteração 2 :

x 2 = g x 1 = 1.94316

Critério de Parada:

x 2 - x 1 = 0.03602 > 0.0 0 01

f x 2 = 0.04999 > 0.0 0 01

Como não alcançamos o critério de parada continuamos as iterações.

x 2 = 1.94316

ε 1 = ε 2 = 0.0 0 01

Iteração 3 :

x 3 = g x 2 = 1.93025

Critério de Parada:

x 3 - x 2 = 0.01291 > 0.0 0 01

f x 3 = 0.01847 > 0.0 0 01

Como não alcançamos o critério de parada continuamos as iterações.

x 3 = 1.93025

ε 1 = ε 2 = 0.0 0 01

Iteração 4 :

x 4 = g x 3 = 1.93503

Critério de Parada:

x 4 - x 3 = 0.00478 > 0.0 0 01

f x 4 = 0.00677 > 0.0 0 01

Como não alcançamos o critério de parada continuamos as iterações.

x 4 = 1.93503

ε 1 = ε 2 = 0.0 0 01

Iteração 5 :

x 5 = g x 4 = 1.93328

Critério de Parada: