Método da bisseção

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] \to ℝ$ com $f (a) \cdot 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)} = \frac{(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) \cdot f (x^{(0)}) < 0$ , então $x^{*} \in (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)}) \cdot 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).

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

De forma mais precisa, suponha que queiramos calcular uma aproximação com uma certa precisão $T O L$ para um zero $x^{*}$ de uma dada função contínua $f : [a, b] \to ℝ$ tal que $f (a) \cdot f (b) < 0$ . Iniciamos, tomando $n = 0$ e:

a^{(n)} = a, b^{(n)} = b e x^{(n)} = \frac{a^{(n)} + b^{(n)}}{2} .

(3.5)

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

\frac{| b^{(n)} - a^{(n)} |}{2} < T O L,

(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)}) \cdot 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)}) \cdot 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)} = \frac{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 $e^{x} = x + 2$ no intervalo $[- 2, 0]$ com precisão $T O L = 1 0^{- 1}$ .

Solução. Primeiramente, observamos que resolver a equação dada é equivalente a calcular o zero de $f (x) = e^{x} - x - 2$ . Além disso, temos $f (- 2) \cdot 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)} = \frac{a^{(0)} + b^{(0)}}{2} = - 1 .

(3.8)

Apresentamos as iterações na Tabela 3.1. Observamos que a precisão $T O L = 1 0^{- 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)})$	$\frac{\| 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] \to ℝ$ uma função contínua tal que $f (a) \cdot f (b) < 0$ e $x^{*}$ o único zero de $f (x)$ no intervalo $(a, b)$ . Então, a sequência ${x^{(n)}}_{n \geq 0}$ do método da bisseção satisfaz:

| x^{(n)} - x^{*} | < \frac{b - a}{2^{n + 1}}, \forall n \geq 0,

(3.9)

isto é, $x^{(n)} \to x^{*}$ quando $n \to \infty$ .

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^{*} | \leq \frac{b^{(n)} - a^{(n)}}{2} .

(3.10)

Por construção do método, temos $[a^{(n)}, b^{(n)}] \subset [a^{(n - 1)}, b^{(n - 1)}]$ e:

b^{(n)} - a^{(n)} = \frac{b^{(n - 1)} - a^{(n - 1)}}{2} .

(3.11)

Desta forma:

| x^{(n)} - x^{*} | \leq \frac{b^{(n)} - a^{(n)}}{2} = \frac{b^{(n - 1)} - a^{(n - 1)}}{2^{2}} = \dots = \frac{b^{(0)} - a^{(0)}}{2^{n + 1}}, \forall n \geq 1 .

(3.12)

Logo, vemos que:

| x^{(n)} - x^{*} | \leq \frac{b - a}{2^{n + 1}}, \forall n \geq 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^{*} | ≲ \frac{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 $1 0^{- 1}$ do zero de $f (x) = e^{x} - 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^{*} | \leq \frac{b - a}{2^{n + 1}}, n \geq 0 .

(3.15)

Logo, temos: $\begin{array}{rcl} | x^{(n)} - x^{*} | & < & \frac{b - a}{2^{n + 1}} = \frac{2}{2^{n + 1}} & (3.16) \\ = & 2^{- n} < 1 0^{- 1} \Rightarrow n > - {log}_{2} 1 0^{- 1} \approx 3, 32 . & (3.17) \end{array}$

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) \approx 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 $\sqrt{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 (x^{2}) - exp (\frac{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 $1 0^{- 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 + 8 x - 5 x^{2} + x^{3}$ tem raízes $x_{1} = 1$ e $x_{2} = x_{3} = 2$ no intervalo $[1 ∕ 2, 3]$ .

Se o método da bisseção for usando com o intervalo inicial $[1 ∕ 2, 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)

x_{1} = 1

. b) Dica: como

x_{2} = 2

é raiz dupla, tem-se que

p^{'} (x_{2}) = 0

E 3.2.4. O polinômio $f (x) = x^{4} - 4 x^{2} + 4$ possui raízes duplas em $\sqrt{2}$ e $- \sqrt{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 - \frac{1}{x} - v$ e considere a seguinte estimativa:

f (v + 1) = f (1) + \int_{1}^{v + 1} f^{'} (x) d x \geq - v + \int_{1}^{v + 1} d x = 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 = 1 m$ , $P = 200 N$ , $k = 50 Nm ∕ rad$ , 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 θ = \frac{l P}{2} cos (θ)

com

θ \in (0, π ∕ 2)

;

1, 030

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

x e^{x} = 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 $1 0^{- 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 ( $I_{d})$ e a tensão ( $v_{d}$ ) no diodo é dada pela seguinte expressão:

I_{d} = I_{R} (exp (\frac{v_{d}}{v_{t}}) - 1),

(3.22)

onde $I_{R}$ é a corrente de condução reversa e $v_{t}$ , a tensão térmica dada por $v_{t} = \frac{k T}{q}$ com $k$ , a constante de Boltzmann, $T$ a temperatura de operação e $q$ , a carga do elétron. Aqui $I_{R} = 1 p A = 1 0^{- 12} A$ , $T = 300 K$ . Escreva o problema como uma equação na incógnita $v_{d}$ e, usando o método da bisseção, resolva este problema com 3 algarismos significativos para os seguintes casos:

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

Dica:

V = R I_{d} + v_{d}

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 $I_{d}$ no Problema 3.2.8. Lembre que existem duas expressões disponíveis:

I_{d} = I_{R} (exp (\frac{v_{d}}{v_{t}}) - 1)

(3.23)

I_{d} = \frac{v - v_{d}}{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.44 e - 3

; c)

2.50 e - 4

; d)

1.09 \cdot 1 0^{- 7}

; e)

- 1 0^{- 12}

; f)

- 1 0^{- 12}

; g)

- 1 0^{- 12}

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 19/8/2020 às 17:36:36.

Recursos

Projeto

IME - UFRGS
- Página do IME
- Página da UFRGS

UFRGS - IME - Recursos Educacionais Abertos de Matemática. Contato: reamat@ufrgs.br.

Informe erros ou edite você mesmo!