Parte III: Uma Introdução ao Cálculo Numérico

Raízes de Funções Reais

Encontrar raízes de funções tem diversas aplicações práticas, como por exemplo, encontrar aproximações para números irracionais ou achar máximo de funções. Nessa semana vamos estudar um método numérico para encontrar aproximações de raízes: o Método da Bisseção. Existem ainda outros métodos que não serão apresentados nesse curso, como por exemplo, Método de Newton-Raphson, Método do Ponto Fixo e Método da Secante.

Conceitos Básicos

Primeiro vale lembrar o que é a raiz de uma função real.

Definição: Seja \(f: \mathbb{R} \to \mathbb{R}\) uma função real. Dizemos que \(x\in\mathbb{R}\) é raiz de \(f\) quando \(f(x) = 0\).

O problema de encontrar raízes de uma função real muitas vezes é bem fácil. Sabemos, por exemplo, achar facilmente as raízes das funções \(f(x) = x + 3\), \(f(x) = x^2-4\), \(f(x) = 1 - e^x\), \(f(x) = ln(x+1)\). Mas dependendo da expressão da função \(f\) encontrar suas raízes pode ser uma tarefa muito difícil, como por exemplo para as funções \(f(x) = x^3 + 2x^2-x + 1\), \(f(x) = x + ln(x)\), \(f(x) = e^x + x^2-2\). Nesses casos o problema será resolvido de forma aproximada a partir de métodos numéricos, como veremos nessa semana.

A base do Método da Bisseção está no Teorema de Bolzano, apresentado a seguir.

Teorema de Bolzano: Seja \(f\) uma função contínua em um intervalo \([a,b]\), tal que, \(f(a)f(b)<0\) (isto é, o sinal de \(f(a)\) e \(f(b)\) são diferentes). Então a função \(f\) possui pelo menos uma raiz no intervalo \((a,b)\).

Veja que, segundo o teorema, conhecendo um intervalo \((a,b)\) tal que \(f(a)\) e \(f(b)\) tenham sinais diferentes nos garante a existência de pelo menos uma raíz dentro do intervalo. Por isso o primeiro passo do método será a busca por um intervalo qualquer com essa característica.

A busca por esse intervalo pode ser feita de várias maneiras. Pode ser simplesmente por um “chute” inicial ou então podemos fazer uma análise gráfica. A análise gráfica tem a vantagem de que as vezes podemos saber exatamente quantas raízes a função tem. Veja a seguir dois exemplos em que o gráfico de \(f\) é usado para encontrar um intervalo \((a,b)\) em que \(f\) possui pelo menos uma raiz.

Método da Bisseção

Para que o método da Bisseção seja aplicado é preciso primeiro conhecer um intervalo \((a,b)\) tal que \(f(a)\) e \(f(b)\) tenham sinais opostos, isto é, tal que \(f(a)f(b)<0\). Dessa forma, de acordo com o Teorema de Bolzano, podemos garantir que existe pelo menos uma raiz dentro desse intervalo. O que o método vai fazer é retornar uma aproximação para uma dessas raízes.

A ideia do método é dividir o intervalo \((a,b)\) ao meio e, usando o resultado do Teorema de Bolzano, decidir em qual dos dois lados a raiz está. Ou seja, começamos com \((a,b)\) tal que \(f(a)f(b)<0\) e depois de um passo chegamos em dois outros intervalos: \((a,m)\) e \((m,b)\), sendo \(m=\frac{a+b}{2}\) o ponto médio do intervalo. Veja que nesse momento podemos garantir que \(m\) é uma aproximação para a raiz de \(f\) com erro menor que \(b-m\), que é o raio do intervalo \((a,b)\).

Calculando o valor de \(f(m)\) e comparando o seu sinal com os sinais de \(f(a)\) e \(f(b)\) podemos determinar em qual dos dois subintervalos a raiz está: se \(f(a)f(m)<0\) sabemos que a raiz está no intervalo \((a,m)\), caso contrário, temos \(f(b)f(m)<0\) e a raiz está no intervalo \((m,b)\). Veja que dessa forma chegamos em um intervalo menor tal que a função \(f\) avaliada nos pontos extremos desse intervalo tem sinais opostos.

O processo é repetido e em cada iteração encontramos um intervalo e o ponto médio desse intervalo é uma aproximação para uma raiz de \(f\) com erro menor que o raio do intervalo.

Exemplo:

Seja \(f(x) = e^x + x^2 - 2\). Queremos encontrar alguma raiz dessa função. Para iniciar o processo precisamos encontrar um intervalo \((a,b)\) tal que \(f(a)f(b)<0\).

Veja que nesse caso é possível afirmar que \(f(x) = g(x)-h(x)\), com \(g(x) = e^x\) e \(h(x) = 2-x^2\). Logo, \(f(x) = 0\) se e somente se \(g(x) = h(x)\). Não sabemos ainda resolver a equação, mas sabemos esboçar os gráficos de \(g\) e \(h\). As raízes de \(f\) serão as abcissas dos pontos de intercessão da curva de \(g\) com \(h\).

Gráficos das curvas $g(x) = e^x$ e $h(x) = 2-x^2$.

Gráficos das curvas \(g(x) = e^x\) e \(h(x) = 2-x^2\).

Logo, podemos afirmar que existe uma raiz de \(f\) no intervalo \((-2,-1)\) e outra no intervalo \((0,1)\). Vamos procurar uma aproximação para a raiz dentro do intervalo \((0,1)\). Nesse exemplo estou assumindo que sabemos calcular \(f(x)\) para qualquer \(x \in \mathbb{R}\), o que pode ser feito assim:

f = function(x){
  exp(x) + x^2 - 2
}

ou, como aprendemos no capítulo anterior.

AproxExp = function(x,delta=0.00001){
  aprox = 1
  for(i in 1:10){
    aprox = aprox + (x^i)/factorial(i)
  }
  n = 11
  incr = (x^n)/factorial(n)
  repeat{
    aprox = aprox + incr
    if(abs(incr)<delta){
      return(aprox)
    }
    n = n + 1
    incr = incr*x/n
  }
}
f = function(x){
  AproxExp(x) + x^2 - 2
}

Veja que \(f(0) < 0\) e \(f(1) > 0\):

f(0)
## [1] -1
f(1)
## [1] 1.718282

Então podemos usar \(a=0\) e \(b=1\) para iniciar o Método da Bisseção. A partir de \(a\) e \(b\) calculamos o ponto médio: \(m = \frac{a+b}{2} = \frac{1}{2} = 0,5\). Essa pode ser considarada a nossa primeira estimativa para a raiz de \(f\) com erro menor que \(0,5\).

Vamos agora avaliar a função em \(m\), ou seja, encontrar o valor de \(f(m)\).

m = 0.5
f(m)
## [1] -0.1012787

Como \(f(0,5) < 0\) e \(f(1) > 0\) podemos afirmar que a raiz que buscamos está no intervalo \((0,5 \ , \ 1)\). Vamos agora encontrar o ponto médio desse intervalo, que será a nossa segunda aproximação: \(m = \frac{0,5 + 1}{2} = 0,75\). Veja que \(m=0,75\) é uma aproximação para a raiz de \(f\) com erro menor que o raio do intervalo \((0,5 \ , \ 1)\), isto é, com erro menor que \(1 - 0,75 = 0,25\). O próximo passo é calcular \(f(m)\) para saber em qual lado desse intervalo a raiz está, antes ou depois de \(m\).

m = 0.75
f(m)
## [1] 0.6795

Como \(f(0,75) > 0\) e \(f(0,5) < 0\) sabemos que a raiz está no intervalo \((0,5 \ , \ 0,75)\). Vamos agora encontrar o ponto médio desse último intervalo, que será a nossa terceira aproximação, mais precisa que a seguda: \(m = \frac{0,5 + 0,75}{2} = 0,625\). Veja que \(m=0,625\) é uma aproximação para a raiz com erro menor que o raio do intervalo \((0,5 \ , \ 0,75)\), isto é, com erro menor que \(0,75-0,625 = 0,125\). O próximo passo é calcular \(f(m)\) para saber em qual parte desse intervalo a raiz está, antes ou depois de \(m\).

m = 0.625
f(m)
## [1] 0.258871

Como \(f(0,625) > 0\) e \(f(0,5) < 0\) sabemos que a raiz está no intervalo \((0,5 \ , \ 0,625)\). Vamos agora encontrar o ponto médio desse último intervalo, que será a nossa quarta aproximação: \(m = \frac{0,5 + 0,625}{2} = 0,5625\). Veja que \(m\) é uma aproximação para a raiz com erro menor que o raio do intervalo \((0,5 \ , \ 0,625)\), isto é, com erro menor que \(0,625-0,5625 = 0,0625\). O próximo passo é calcular \(f(m)\) para saber em qual parte desse intervalo a raiz está, antes ou depois de \(m\).

m = 0.5625
f(m)
## [1] 0.07146091

Como \(f(0,5625) > 0\) e \(f(0,5) < 0\) sabemos que a raiz está no intervalo \((0,5 \ , \ 0,5625)\). Vamos agora encontrar o ponto médio desse último intervalo, que será a nossa próxima aproximação, mais precisa que a seguda: \(m = \frac{0,5 + 0,5625}{2} = 0,53125\). Veja que \(m\) é uma aproximação para a raiz com erro menor que o raio do intervalo \((0,5 \ , \ 0,5625)\), isto é, com erro menor que \(0,5625-0,53125 = 0,03125\). O próximo passo é calcular \(f(m)\) para saber em qual parte desse intervalo a raiz está, antes ou depois de \(m\).

m = 0.53125
f(m)
## [1] -0.01671614

Como \(f(0,53125) < 0\) e \(f(0,5625) > 0\) sabemos que a raiz está no intervalo \((0,53125 \ , \ 0,5625)\). Vamos agora encontrar o ponto médio desse último intervalo, que será a nossa próxima aproximação, mais precisa que a seguda: \(m = \frac{0,53125 + 0,5625}{2} = 0,546875\). Veja que \(m\) é uma aproximação para a raiz com erro menor que o raio do intervalo \((0,53125 \ , \ 0,5625)\), isto é, com erro menor que \(0,5625 - 0,546875= 0,015625\).

E quando paramos? Já encontramos 5 aproximações, lembrando que cada valor de \(m\) encontrado foi uma aproximação. Como sabemos se já está bom?

Critério de Parada

O Método da Bisseção é um método que conseguimos controlar o erro da aproximação encontrada, como vimos no exemplo. Podemos repetri o processo até encontrar uma aproximação com um erro tão pequeno quanto a gente queira. Ou seja o usuário indica um erro \(\varepsilon\) e quando o algoritmo chegar em um intervalo \((a,b)\) de raio menor que \(\varepsilon\), isto é \(b - m < \varepsilon\), podemos afirmar que o ponto médio desse intervalo é uma aproximação para a raiz de \(f\) com erro menor que \(\varepsilon\).

Pseudocódigo

Veja a seguir o pseudocódigo de uma função que encontra a raiz a partir do Método da Bisseção.

Entrada: a, b, f e e.

Saída: uma aproximação para uma raiz de \(f\) dentro do intervalo \((a,b)\) com erro menor que e.

Nome: RaizBissecao

1. Se f(a)*f(b) >= 0, retorne erro. 
2. Defina m = (a+b)/2.
3. Se f(m) = 0 ou |b - m| < e, retorne m.
4. Se f(a)*f(m) < 0, faça b = m e volte para a linha 2. 
5. Faça a = m e volte para a linha 2.

O pseudocódigo acima será mais facilmente implementado se for usado o repeat. Mas acho que ainda mais simples é a sua versão recursiva.

Entrada: a, b, f e e.

Saída: uma aproximação para uma raiz de \(f\) dentro do intervalo \((a,b)\) com erro menor que e.

Nome: RaizBissecaoRec

1. Se f(a)*f(b) >= 0, retorne erro.
2. Defina m = (a+b)/2. 
3. Se f(m) = 0 ou |b - m| < e, retorne m.
4. Se f(a)*f(m) < 0, retorne RaizBissecaoRec(a,m,f,e)
5. retorne RaizBissecaoRec(m,b,f,e)

Algumas vantagens desse método:

  • método de fácil compreensão;
  • se conseguimos um intervalo \([a,b]\) tal que \(f(a)\) e \(f(b)\) têm sinais opostos, temos a garantia de que o método converge para uma raiz de \(f\);
  • ao final do método sabemos que chegamos em uma aproximação com precisão \(\varepsilon\), ou seja, o valor \(x\) fornecido pelo método é tal que \(|x - \alpha| < \varepsilon\), onde \(\alpha\) é a raiz procurada e desconhecida.

Algumas desvantagens desse método:

  • é necessário conhecer um intervalo \([a,b]\) tal que \(f(a)f(b) < 0\), as vezes esse intervalo nem existe;
  • o processo de convergência não é dos mais rápidos.

Algumas Aplicações:

Os métodos para encontrar raiz de uma função também podem servir resolver outros problemas. Vejamos alguns exemplos. Para os exemplos abaixo vamos supor já implementada no R a função RaizBissecaoRec.

Exemplo:

Encontre uma solução para a expressão \(\ln(x) = 2 - x\). Esse não é um problema direto de encontrar raiz, mas rapidamente pode ser transformado em um. Basta perceber que a solução dessa experssão é a raiz da função \(f(x) = \ln(x) - 2 + x\). E para solucionar esse problema o primeiro passso é encontrar valores de \(a\) e \(b\) tais que \(f(a)f(b) < 0\). Veja que como sabemos fazer um esboço de \(g(x) = \ln(x)\) e também de \(h(x) = 2 - x\) fica masi fácil encontrar valores viáveis de \(a\) e \(b\).

Gráficos das curvas $g(x) = ln(x)$ e $h(x) = 2-x$.

Gráficos das curvas \(g(x) = ln(x)\) e \(h(x) = 2-x\).

Assim podemos afirmar que a única raiz de \(f\) está dentro do intervalo \((1,2)\). Usando a função RaizBissecaoRec podemos encontrar o que procuramos:

(r = RaizBissecaoRec(1,2,f=function(x){log(x)-2+x}))
## [1] 1.557145
log(r)-2+r
## [1] -7.887232e-07
log(r)
## [1] 0.4428541
2-r
## [1] 0.4428549
curve(log(x),ylim=c(-2,2),xlim=c(0,4),ylab="",xlab="")
curve(-x+2,add=T)
grid()
abline(h=0)
points(r,log(r),pch=20,col="red")
Gráficos das curvas $g(x) = ln(x)$ e $h(x) = 2-x$ e seu ponto de interseção.

Gráficos das curvas \(g(x) = ln(x)\) e \(h(x) = 2-x\) e seu ponto de interseção.

Exemplo:

No capítulo passado vimos como avaliar algumas funções usando apenas operações básicas. Ou seja, sabemos encontrar uma aproximação para \(\ln(5)\), \(e^{-3}\) ou \(\mathrm{sen}(10)\) usando apenas lápis e papel. E se quisermos avaliar, usando apenas operações básicas, a função raiz quadrada, ou seja, encontrar o valor de \(\sqrt{x_0}\) para um dado \(x_0 \ge 0\)? Podemos usar o Método da Bisseção para isso.

Veja que para um dado \(x_0\), \(\sqrt{x_0}\) é a raiz da função \(f(x) = x^2 - x_0\). Ou seja, basta aplicar o Método da Bisseção nessa função. Precisamos então escolher quais valores de \(a\) e \(b\) começar. Veja que, supondo \(x_0 \ge 0\), sempre podemos usar \(a = 0\) e temos \(f(a)=f(0)<0\). Se \(x_0 > 1\), podemos usar \(b=x_0\) pois nesse caso \(f(b) = f(x_0) = x_0^2 - x_0 = x_0(x_0 - 1) > 0\). Se \(x_0 < 1\) usamos \(b=1\), pois \(f(b) = f(1) = 1 - x_0 > 0\).

Vejamos então o pseudocódigo de uma função que recebe como entrada \(x>0\) e um erro e retorna uma aproximação para \(\sqrt{x}\).

Entrada: x0 e e.

Saída: uma aproximação para \(\sqrt{x_0}\) com erro menor que e.

Nome: AproxRaiz

1. Se x0 < 0, retorne erro. 
2. Se x0 = 1 ou x0 = 0, retorne x0.
3. Se x0 > 1, faça b = x0. Caso contrário faça b = 1. 
4. retorna RaizBissecaoRec(0,b,f(x)=x^2-x0,e)

Veja como fica o código dessa função, supondo já feita a função RaizBissecaoRec.

AproxRaizQuad = function(x0,e=0.00000001){
  if(x0<0)
    stop("Erro")
  if( x0 == 1 || x0 == 0 )
    return(x0)
  if(x0>1){
    b = x0
  } else {
    b = 1
  }
  RaizBissecaoRec(0,b,f = function(x){x^2-x0},e)
}
AproxRaizQuad(4)
## [1] 2
AproxRaizQuad(2)
## [1] 1.414214
a = AproxRaizQuad(2)
a*a
## [1] 2
AproxRaizQuad(0.5)
## [1] 0.7071068
a = AproxRaizQuad(0.5)
a*a
## [1] 0.5