Use o botão abaixo para reportar erros ou dar sugestões.

Cálculo Numérico - Versão Python

3.2 Método da bisseção


O método da bisseção explora o fato de que uma função contínua f : [a,b] com f(a) f(b) < 0 tem um zero no intervalo (a,b) (veja o teorema de Bolzano 3.1.1). Assim, a ideia para aproximar o zero de uma tal função f(x) é tomar, como primeira aproximação, o ponto médio do intervalo [a,b], isto é:

x(0) = (a + b) 2 . (3.4)

Pode ocorrer de f(x(0)) = 0 e, neste caso, o zero de f(x) é x* = x(0). Caso contrário, se f(a) f(x(0)) < 0, então x* (a,x(0)). Neste caso, tomamos como segunda aproximação do zero de f(x) o ponto médio do intervalo [a,x(0)], isto é, x(1) = (a + x(0))2. No outro caso, temos f(x(0)) f(b) < 0 e, então, tomamos x(1) = (x(0) + b)2. Repetimos este procedimento até obtermos a aproximação desejada (veja Figura 3.2).


PIC

Figura 3.2: Método da bisseção.


De forma mais precisa, suponha que queiramos calcular uma aproximação com uma certa precisão TOL para um zero x* de uma dada função contínua f : [a,b] tal que f(a) f(b) < 0. Iniciamos, tomando n = 0 e:

a(n) = a,b(n) = bex(n) = a(n) + b(n) 2 . (3.5)

Verificamos o critério de parada, isto é, se f(x(n)) = 0 ou:

|b(n) - a(n)| 2 < TOL, (3.6)

então x(n) é a aproximação desejada. Caso contrário, preparamos a próxima iteração n + 1 da seguinte forma: se f(a(n)) f(x(n)) < 0, então definimos a(n+1) = a(n) e b(n+1) = x(n); no outro caso, se f(x(n)) f(b(n)) < 0, então definimos a(n+1) = x(n) e b(n+1) = b(n). Trocando n por n + 1, temos a nova aproximação do zero de f(x) dada por:

x(n+1) = a(n+1) + b(n+1) 2 . (3.7)

Voltamos a verificar o critério de parada acima e, caso não satisfeito, iteramos novamente. Iteramos até obtermos a aproximação desejada ou o número máximo de iterações ter sido atingido.

Exemplo 3.2.1. Use o método da bisseção para calcular uma solução de ex = x + 2 no intervalo [-2, 0] com precisão TOL = 10-1.

Solução. Primeiramente, observamos que resolver a equação dada é equivalente a calcular o zero de f(x) = ex - x - 2. Além disso, temos f(-2) f(0) < 0. Desta forma, podemos iniciar o método da bisseção tomando o intervalo inicial [a(0),b(0)] = [-2, 0] e:

x(0) = a(0) + b(0) 2 = -1. (3.8)

Apresentamos as iterações na Tabela 3.1. Observamos que a precisão TOL = 10-1 foi obtida na quarta iteração com o zero de f(x) sendo aproximado por x(4) = -1,8125.


Tabela 3.1: Iteração do método da bisseção para o Exemplo 3.2.1.






n a(n) b(n) x(n) f(a(n))f(x(n)) |b(n) - a(n)| 2






0 - 2 0 - 1 < 0 1
1 - 2 - 1 - 1,5 < 0 0,5
2 - 2 - 1,5 - 1,75 < 0 0,25
3 - 2 - 1,75 - 1,875 > 0 0,125
4 - 1,875 - 1,75 - 1,8125 < 0 0,0625







Usando Python neste exemplos, temos:

>>> def f(x): return np.exp(x) - x - 2  
...  
>>> a=-2; b=0; x = (a+b)/2; [a,b,x]  
[-2, 0, -1.0]  
>>> [(b-a)/2, np.sign(f(a)*f(x))]  
[1.0, -1.0]  
>>> b=x; x=(a+b)/2; [a,b,x]  
[-2, -1.0, -1.5]  
>>> [(b-a)/2, np.sign(f(a)*f(x))]

e, assim, sucessivamente. Veja o código completo na Seção 3.2.1.

Vamos agora discutir sobre a convergência do método da bisseção, que é garantida pelo Teorema 3.2.1.

Teorema 3.2.1 (Convergência do método da bisseção). Sejam f : [a,b] uma função contínua tal que f(a) f(b) < 0 e x* o único zero de f(x) no intervalo (a,b). Então, a sequência {x(n)} n0 do método da bisseção satisfaz:

|x(n) - x*| < b - a 2n+1 ,n 0, (3.9)

isto é, x(n) x* quando n .

Demonstração. Notemos que, a cada iteração, a distância entre a aproximação x(n) e o zero x* da função é menor ou igual que a metade do tamanho do intervalo [a(n),b(n)] (veja Figura 3.2), isto é:
|x(n) - x*| b(n) - a(n) 2 . (3.10)

Por construção do método, temos [a(n),b(n)] [a(n-1),b(n-1)] e:

b(n) - a(n) = b(n-1) - a(n-1) 2 . (3.11)

Desta forma:

|x(n) - x*| b(n) - a(n) 2 = b(n-1) - a(n-1) 22 = = b(0) - a(0) 2n+1 ,n 1. (3.12)

Logo, vemos que:

|x(n) - x*| b - a 2n+1 ,n 0. (3.13)

Observamos que a hipótese de que f(x) tenha um único zero no intervalo não é realmente necessária. Se a função tiver mais de um zero no intervalo inicial, as iterações ainda convergem para um dos zeros. Veja o Exercício 3.2.3.

Observação 3.2.1. O Teorema 3.2.1 nos fornece uma estimativa para a convergência do método da bisseção. Aproximadamente, temos:

|x(n+1) - x*| 1 2|x(n) - x*|. (3.14)

Isto nos leva a concluir que o método da bisseção tem taxa de convergência linear.

Exemplo 3.2.2. No Exemplo 3.2.1, precisamos de 4 iterações do método da bisseção para computar uma aproximação com precisão de 10-1 do zero de f(x) = ex - x - 2 tomando como intervalo inicial [a,b] = [-2, 0]. Poderíamos ter estimado o número de iterações a priori, pois, como vimos acima:

|x(n) - x*| b - a 2n+1 ,n 0. (3.15)

Logo, temos: |x(n) - x*| < b - a 2n+1 = 2 2n+1 (3.16) = 2-n < 10-1 n > - log 210-1 3,32. (3.17)

O que está de acordo com o experimento numérico realizado naquele exemplo.

O método da bisseção tem a boa propriedade de garantia de convergência, bem como de fornecer uma simples estimativa do erro na aproximação calculada. Entretanto, a taxa de convergência linear é superada por outros métodos. A construção de tais métodos está, normalmente, associada à iteração do ponto fixo, a qual exploramos na próxima seção.

3.2.1 Código Python: método da bisseção


O seguinte código é uma implementação em Python do algoritmo da bisseção. As variáveis de entrada são:

  • f - função objetivo
  • a - extremo esquerdo do intervalo de inspeção [a,b]
  • b - extremo direito do intervalo de inspeção [a,b]
  • TOL - tolerância (critério de parada)
  • N - número máximo de iterações

A variável de saída é:

  • p - aproximação da raiz de f, isto é, f(p) 0.
from __future__ import division  
 
def bissecao(f, a, b, TOL, N):  
    i = 1  
    fa = f(a)  
    while (i <= N):  
        #iteracao da bissecao  
        p = a + (b-a)/2  
        fp = f(p)  
        #condicao de parada  
        if ((fp == 0) or ((b-a)/2 < TOL)):  
            return p  
        #bissecta o intervalo  
        i = i+1  
        if (fa * fp > 0):  
            a = p  
            fa = fp  
        else:  
            b = p  
 
    raise NameError(Num. max. de iter. excedido!);

Exercícios


E 3.2.1. Considere a equação x = cos(x). Use o método da bisseção com intervalo inicial [a,b] = [0, 1] e x(1) = (a + b)2 para calcular a aproximação x(4) da solução desta equação.

Resposta. 0,6875

E 3.2.2. Trace o gráfico e isole as três primeiras raízes positivas da função:

f(x) = 5 sen (x2) - exp x 10 (3.18)

em intervalos de comprimento 0,1. Então, use o método da bisseção para obter aproximações dos zeros desta função com precisão de 10-5.

Resposta. Intervalo (0,4, 0,5), zero 0,45931. Intervalo (1,7, 1,8), zero 1,7036. Intervalo (2,5, 2,6), zero 2,5582.

E 3.2.3. O polinômio p(x) = -4 + 8x - 5x2 + x3 tem raízes x1 = 1 e x2 = x3 = 2 no intervalo [12, 3].

  • Se o método da bisseção for usando com o intervalo inicial [12, 3], para qual raiz as iterações convergem?
  • É possível usar o método da bisseção para a raiz x = 2? Justifique sua resposta.

Resposta. a) x1 = 1. b) Dica: como x2 = 2 é raiz dupla, tem-se que p(x 2) = 0.

E 3.2.4. O polinômio f(x) = x4 - 4x2 + 4 possui raízes duplas em 2 e -2. O método da bisseção pode ser aplicado a f? Explique.

E 3.2.5. Mostre que a equação do Problema 3.1.7 possui uma solução no intervalo [1,v + 1] para todo v positivo. Dica: defina f(x) = ln(x) + x - 1 x - v e considere a seguinte estimativa:

f(v + 1) = f(1) +1v+1f(x)dx -v +1v+1dx = 0. (3.19)

Use esta estimativa para iniciar o método de bisseção e obtenha o valor da raiz com pelo menos 6 algarismos significativos para v = 1, 2, 3, 4 e 5.

Resposta. 1,390054; 1,8913954; 2,4895673; 3,1641544; 3,8965468

E 3.2.6. (Estática) Considere o seguinte problema físico: uma plataforma está fixa a uma parede através de uma dobradiça cujo momento é dado por:

τ = kθ, (3.20)

onde θ é angulo da plataforma com a horizontal e k é uma constante positiva. A plataforma é feita de material homogêneo, seu peso é P e sua largura é l. Modele a relação entre o ângulo θ e o peso P próprio da plataforma. Encontre o valor de θ quando l = 1m, P = 200N, k = 50Nmrad, sabendo que o sistema está em equilíbrio. Use o método da bisseção e expresse o resultado com 4 algarismos significativos.

Resposta. kθ = lP 2 cos(θ) com θ (0,π2); 1,030.

E 3.2.7. Considere a equação de Lambert dada por:

xex = t, (3.21)

onde t é um número real positivo. Mostre que esta equação possui uma única solução x* que pertence ao intervalo [0,t]. Usando esta estimativa como intervalo inicial, quantos passos são necessário para obter o valor numérico de x* com erro absoluto inferior a 10-6 quando t = 1, t = 10 e t = 100 através do método da bisseção? Obtenha esses valores.

Resposta. 19; 23; 26; 0,567143; 1,745528; 3,385630

E 3.2.8. (Eletrônica) O desenho abaixo mostra um circuito não linear envolvendo uma fonte de tensão constante, um diodo retificador e um resistor. Sabendo que a relação entre a corrente (Id) e a tensão (vd) no diodo é dada pela seguinte expressão:

Id = IR exp vd vt - 1 , (3.22)

onde IR é a corrente de condução reversa e vt, a tensão térmica dada por vt = kT q com k, a constante de Boltzmann, T a temperatura de operação e q, a carga do elétron. Aqui IR = 1pA = 10-12A, T = 300K. Escreva o problema como uma equação na incógnita vd e, usando o método da bisseção, resolva este problema com 3 algarismos significativos para os seguintes casos:

  • V = 30V e R = 1kΩ.
  • V = 3V e R = 1kΩ.
  • V = 3V e R = 10kΩ.
  • V = 300mV e R = 1kΩ.
  • V = -300mV e R = 1kΩ.
  • V = -30V e R = 1kΩ.
  • V = -30V e R = 10kΩ.
PIC

Dica: V = RId + vd.
Resposta. a) 0,623; b) 0,559; c) 0,500; d) 0,300; e) - 0,3; f) - 30; g) - 30

E 3.2.9. (Propagação de erros) Obtenha os valores de Id no Problema 3.2.8. Lembre que existem duas expressões disponíveis:

Id = IR exp vd vt - 1 (3.23)

e

Id = v - vd R (3.24)

Faça o estudo da propagação do erro e decida qual a melhor expressão em cada caso.

Resposta. a) 0,0294; b) 2.44e - 3; c) 2.50e - 4; d) 1.09 10-7; e) - 10-12; f) - 10-12; g) - 10-12

Creative Commons License Este texto é disponibilizado nos termos da licença Creative Commons Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC-BY-SA 3.0). Página gerada em 15/5/2019 às 15:24:50.

Informe erros ou edite você mesmo!