Método da Bisseção

Teoria Completa

Introdução aos Métodos Iterativos

Faaaaaala meus consagrados, já vimos algumas coisinhas sobre isolamento de raízes de funções simples ou malucas. Mas essa forma de determinar raízes nos dá aproximações grosseiras e muitas vezes só temos uma precisão de uma unidade, ou seja, a raiz está num intervalo de uma unidade, que é uma precisão muito baixa! Do tipo que pode derrubar sua ponte, afundar seu navio, etc. E não queremos isso né?

Basicamente o que vamos fazer agora consiste em determinar valores aproximados para as soluções (encontrar raízes) de diferentes funções com aquela cara conhecida de f x = 0 .

Veja bem, no que estamos interessados ? Nós queremos apenas os zeros reais da função (nada de números imaginários por aqui hehe) que são basicamente pontos onde uma curva intercepta o eixo x.

Dá uma olhadinha no gráfico abaixo: Existe um teorema que diz que se f x é contínua no intervalo [a,b] e se f a . f b < 0 existe PELO MENOS UMA raíz dentro do intervalo (Isso vem lá da teoria do valor intermediário).

Belê, mas como vamos fazer isso? Primeiro damos uma aproximação inicial para a raiz dentro de um intervalo, aí nós vamos refinando através de processos iterativos. Parace bastante coisa né, mas você já vai ver como é molezinha ! E esse processo todo geralmente acontece em 2 fases:

1º) Localização/ isolamento das raízes: Nesse passo nós podemos fazer análises gráficas e daremos um intervalo que contém a raíz (que será nosso pontapé inicial). Esse intervalo costuma ser uma estimativa bem grosseira, que vai passar pelo processo de refinamento pra diminuir e ficar bem pequenininho.

2º) Refinamento: Depois que escolhemos as aproximações iniciais para o intervalo na primeira fase, começamos o processo de iterações (onde cada bateria de cálculo conta como uma iteração) para melhorarmos varias vezes até encontrar uma aproximação próxima da raíz real.

E para isso utilizamos métodos iterativos, que é só um nome bonito para “fazer a mesma conta um monte de vezes até chegar numa precisão boa o suficiente para você”. A forma como se efetua o refinamento é que diferencia os diferentes métodos iterativos. E como eu sei que estou próximo o suficiente do valor real ? Aí que entram os critérios de parada.

Critérios de Parada

Critério de parada é simplemente uma inequação que você vai testar a cada iteração, cada ciclo de contas. É nele que você vai usar aquele ε , a precisão da sua aproximação que é dada no começo dos exercícios. Existem inúmeros critérios de parada possíveis, então vou citar os mais comuns aqui:

  • Seja a , b o intervalo obtido em alguma iteração, paramos se b - a ≤ ε .
  • Seja x - uma aproximação da raiz encontrada em alguma iteração, paramos se f x - ≤ ε .
  • Seja x k a aproximação da raiz na iteração k , paramos se x k - x k - 1 ≤ ε .

Alguns critérios de parada são mais comuns em alguns métodos, mas na prática você pode usar qualquer critério desses, tendo cuidado em alguns casos especiais.

Pra ficar mais claro como essa teoria toda funciona vamos ver na prática com o método da bisseção.

Método da Bisseção

Seguinte, vamos pensar nesses métodos como máquinas. Você dá algumas instruções para ela, ela executa passo a passo e repete em ciclos cada iteração, refina osresultado e te cospe ele bonitinho! Mais ou menos assim:

O que essa máquina precisa?

Ela precisa de um intervalo a , b que contenha a raiz que se deseja obter, de tal forma que f a ∙ f b < 0 . Isso já sabemos como obter pelo isolamento de raízes!

E ela também precisa de um erro ε , que vai definir quando essa máquina vai parar de trabalhar e nos dar o resultado! Isso quem define é você (ou seu professor na prova). Quando menor esse erro mais trabalho você vai ter mas é menos provável que sua ponte caia ;)

Próxima pergunta: Como ela vai refinar o resultado?

Lembra que eu falei que a técnica de refinamento é que diferencia o método ? Aqui no método da bisseção o algoritmo é o seguinte:

Tiramos a média entre os dois pontos do intervalo e vemos onde está a raiz. Bem simples né?

Por exemplo, se temos um intervalo a , b , fazemos:

a + b 2 =   x k

Agora ficamos com dois intervalos de tamanhos iguais, a , x e x , b . Para descobrirmos qual deles tem a raiz é só fazermos f a ∙ f x e analisar se o valor é maior ou menor que zero. Lá em cima eu falei que o objetivo das iterações era refinar para diminuir o tamanho do intervalo né?

Se o resultado desse produto for menor que zero, a raiz está aí a , x ! Se for maior, a raiz ta no intervalo x , b . Então, esse nosso novo (e menor) intervalo vai passar a ser o novo a , b e vamos repetindo o processo!

Da uma olhada nesse macete:

Po, mas quando paramos isso? É aí que entra o nosso critério de parada! Normalmente o critério de parada usado nesse método é parar quando b - a ≤ ε , mas seu professor pode mandar você usar qualquer um dos outros, então fique atento!

Pra ficar tudo cristalino vamos resolver um exercício de um jeito que você vai ficar craque no assunto!

Exemplo:

“Em um intervalo de [1,2], utilize como critério de parada b - a ≤ ε , onde ε = 10 -3 .Encontre a raíz f x = ( x - 2 ) 2 - ln ⁡ x = 0

Vamos lá?

A primeira coisa que podemos fazer é montar uma tabelinha show de bola com toooodas as informações que precisamos: o número k de iterações (que vai de 0 até n), o valor de a e b para cada iteração, os valores de x k , e o valor da nossa função f x aplicada em : a, b e x k . E por último e não menos importante: o critério de parada. Fica mais ou menos assim:

Agora, vou ensinar como se completa a tabela: Sempre começamos em k=0, já que não foi feita nenhuma iteração antes dessa.

Primeiro: podemos calcular o valor da função nos pontos a e b do intervalo [1,2].

Se nossa função é:

f x = ( x - 2 ) 2 - ln ⁡ x

No ponto a = 1:

f x = ( 1 - 2 ) 2 - ln ⁡ 1 = 1

No ponto b = 2:

f x = ( 2 - 2 ) 2 - ln ⁡ 2 = - 0,6931

Segundo: Agora vamos calcular o nosso x k + 1

a + b 2 =   x k + 1

1 + 2 2 =   x k + 1 = 1,5

Bom, só falta calcular o valor de x k + 1 no ponto e colocar os valores na tabela. Vamos lá?

f x k + 1 = ( 1,5 - 2 ) 2 - ln ⁡ 1,5 = - 0,1554

Terceiro: Agora vemos o primeiro critério de parada, você lembra qual é ? Isso mesmo, é só comparar com o erro:

b - a ≤ ε

2 - 1 ≤ ε

2 - 1 > ( 10 ) - 3

Como b - a é maior que o critério de parada, continuamos interagindo. Mas quem eu vou substituir: a ou b?

Quarto e último passo: Passar saber se vamos reduzir o intervalo substituindo o valor de a ou b, usamos aquele macete:

f 1 ∙ f - 0,1554 < 0

Opa, já achamos um intervalo! Como o valor deu negativo, substituímos b. Então vamos dar para a nossa máquina o intervalo 1 ; 1,5 com erro ε = 0,1 .

Agora a gente começa a parte cíclica da coisa! Vamos fazer iterações até chegarmos em um resultado legal! Ah, outra coisa importante é numerar as iterações! Normalmente é pedido isso de vocês.

Vamos jogar os valores na tabela e ver como fica?

Da uma olhadinha nas cores da tabela, e perceba que a cada valor negativo em f a . f ( x ) nós substituímos o valor de b, caso desse positivo substituímos em a. Até chegarmos em um ponto onde b - a < ε :

1,414 - 1,406 < ε

Opaa, percebeu o que aconteceu aqui? Nos iteragimos até chegar em um intervalo de [1,406; 1,414] que é o valor mais próximo que encontramos da nossa raíz aplicada na função!

Percebeu que é bem trabalhoso né? Relaxa que vamos estudar outros métodos mais vantajosos que convergem com muito menos iterações! Show de bola.

Algoritmo

É um trabalho bem chatinho né? Agora imagina se você quisesse um erro de 0.0000001 ? Aí que ferrou tudo, ia ficar pra sempre fazendo conta! Isso pode te levar a pensar que esse método é meio inútil e não serve pra nada, mas por sorte ele não foi feito pra gente!

O principal objetivo desse método e de todos os outros que vamos ver é programar as máquinas para fazerem as contas pra gente! Você provavelmente vai ter que escrever um código no computador que faça tudo isso que eu fiz aqui na mão (apesar de que na sua prova você também vai ter que fazerna munheca D=). Para isso vou escrever o algoritmo aqui bonitinho pra facilitar sua vida:

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

a. Intervalo inicial a , b contendo a raiz

b. Precisão do resultado final ε

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

Passo 3. Se b - a < ε , então seu intervalo já está ótimo. Escolha um x qualquer entre a , b (normalmente se escolhe o ponto médio) e FIM. Caso contrário, continue para o Passo 4.

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

Passo 5. x = a + b 2

Passo 6. Se f a ∙ f x > 0 , fazemos a = x . Caso contrário, fazemos b = x .

Passo 7. Voltamos para o Passo 3 . Repare que o a e o b que utilizaremos nesse novo ciclo já não são mais os mesmos e representam um intervalo menor.

E pronto, ficamos nesse ciclo até que seu programa fique na precisão desejada! Terminado o processo teremos um intervalo a , b contendo a raiz e uma aproximação dela.

Um critério de parada interessante para seu programa e que é normalmente pedido é um número máximo de iterações! Dessa forma se tiver algum erro no seu programa ou sua função não satisfizer as condições do método você não corre risco de ficar preso em um loop infinito ;)

Estudo da Convergência

É bem intuitivo pensarmos que se a função f x for contínua no intervalo a , b que você encontrou, o método da bisseção vai gerar intervalos cada vez menores, se aproximando cada vez mais da raiz né?E não só é intuitivo como é verdade! Se f x for contínua em a , b e f a ∙ f b < 0 , esse método sempre vai convergir para uma raiz!

Mais que isso, podemos fazer uma estimativa do número de iterações necessárias! Sabemos que o intervalo que obtemos em cada iteração k terá metade da amplitude do intervalo da iteração k - 1 . Isso nos diz que:

b k - a k = b k - 1 - a k - 1 2 = b k - 2 - a k - 2 2 2 = b 0 - a 0 2 k

E queremos que b k - a k < ε , logo:

b 0 - a 0 2 k < ε ⇒ 2 k > b 0 - a 0 ε ⇒ ln ⁡ 2 k > ln ⁡ b 0 - a 0 ε ⇒ k ∙ ln ⁡ 2 > ln ⁡ b 0 - a 0 - ln ⁡ ε

Então,

k > ln ⁡ b 0 - a 0 - ln ⁡ ε ln ⁡ 2

Usando nosso intervalo - 1,0 com ε = 0,01 , nós obtemos:

k > ln ⁡ 1 - ln ⁡ 0.01 ln ⁡ 2 ≅ 6,64 ⇒ k = 7

Ou seja, precisaríamos de no mínimo 7 iterações para chegar no resultado.Que foi exatamente o número de iterações que nós fizemos.

Bem legal né? Terminamos por aqui, bora fazer os exercícios!!

Expandir

Exercício Resolvido #1

Elaboração Própria

Dê um exemplo de função f x , que tenha pelo menos uma raiz que não pode ser determinada pelo método da Bisseção.

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Essa eu dei um exemplo na teoria né? A função x 2 não pode ter sua raiz determinada por esse método já que a função não atravessa o eixo x . Qualquer outra função com essa característica também pode ser usada como exemplo, como 7 x 4 = 0 .

Resposta

Qualquer função que toque o eixo x sem atravessá-lo, como por exemplo x 2 = 0 , 7 x 4 = 0 , etc.

Exercício Resolvido #2

Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 55, exercício 11a e 11d.

Seja f x = x + 2 x + 1 x x - 1 3 x - 2 . Para qual zero de f o método da bisseção converge quando aplicado nos seguintes intervalos:

a - 3,2.5

b - 1.5,1.75

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

A primeira coisa é vermos quais são os zeros dessa função que tá bem tranquilo né? Temos x = - 2 ,   - 1 ,   0 ,   1   e 2 como zeros da nossa função. Agora é só aplicar o método da bisseção nesses intervalos até acharmos pra qual desses zeros ele converge:

a   a 0 , b 0 = - 3,2.5

Temos as 5 raízes dentro desse intervalo, então não podemos afirmar para qual delas ele vai convergir.

Iteração 1 :

x 1 = a 0 + b 0 2 = - 0.25

f x 1 = f - 0.25 ≅ - 1.44

f a 0 ∙ f x 1 = - 1920 ∙ - 1.44 > 0

Logo, nosso novo intervalo será formado por x 1 e b 0 . Temos então que:

a 1 , b 1 = x 1 , b 0 = - 0.25 , 2.5

Ainda temos as raízes 0 , 1 e 2 nesse intervalo então não podemos dizer para qual raiz ele vai convergir.

a 1 , b 1 = - 0.25,2.5

Iteração 2 :

x 2 = a 1 + b 1 2 = 1.125

f x 2 = f 1.125 = - 0.01276

f a 1 ∙ f x 2 = - 1.44 ∙ - 0.01276 > 0

Logo, nosso novo intervalo será formado por x 2 e b 1 . Temos então que:

a 2 , b 2 = x 2 , b 1 = 1.125 , 2.5

Opa, repara que a única raiz nesse intervalo é o 2 ! Então já sabemos que ele vai convergir para o 2 .

Passo 2

b   a 0 , b 0 = - 1.5,1.75