1.1.2 Raízes de Equações — Métodos Intervalares — Regula Falsi

1. Introdução

Semelhante ao Método da Bissecção, a técnica Regula Falsi é um Método Intervalar usado para buscar raízes de funções, aproximando um intervalo \(\left[ x_{l}, x_{r} \right] \) e \( \left[ F(x_{l}), F(x_{r}) \right] \) por uma reta. A interseção da reta com o eixo das abcissas consiste em uma aproximação da raiz.

Esta técnica apresenta, em alguns casos, alguma melhoria na eficiência da busca pela raiz, pois é um método inteligente na seleção dos limites dos subintervalos, diferentemente do Método da Bissecção, que utiliza de uma abordagem de força bruta para convergir ao resultado.

A deficiência no Método da Bissecção, contornada pelo Regula Falsi, está na divisão do intervalo em dois subintervalos iguais, sem levar em conta os valores de \(F(x_{l}) \) e \(F(x_{r}) \) . Sendo assim, o algoritmo da Bissecção não considera a probabilidade de que se uma imagem \(F(x_{r}) \) está mais próxima de zero do que outra imagem \(F(x_{l}) \) , provavelmente \(x_{r} \) está mais próxima da raiz que \(x_{l} \) , e vice-versa. Para esse método, a distância da raiz \(x \) até \(x_{r} \) e \(x_{l} \) têm a mesma probabilidade de ocorrer, o que em muitos casos não é verdade.

2. Desenvolvimento do Método

O método consiste em aproximar uma curva por uma reta até que esta intercepte o eixo \(x \) , permitindo estimar o valor da raiz. O valor tomado como sendo a aproximação da raiz vêm da interceptação por esta reta, que não pertence a curva. Daí o nome “Regula Falsi”, ou “Falsa Posição”. Este processo pode ser visualizado na Figura 1.



fig141

Podemos criar dois triângulos a partir dos pontos usados na geração da reta usada na aproximação, conforme ilustrado na Figura 2. Por essa imagem, observamos que os triângulos serão sempre semelhantes, uma vez que estarão sempre separados pelo vértice formado pela raiz aproximada.



fig142

Usando as propriedades de semelhança de triângulos para este caso, podemos obter a seguinte relação:

\( \dfrac{f(x_{l})}{x – x_{l}} = \dfrac{f(x_{r})}{x-x_{r}}\)

multiplicando a Equação 1 por \((x-x_{l})(x-x_{r}) \) ,
\( f(x_{l}) \left( x – x_{r} \right) = f(x_{r}) \left( x – x_{l} \right) \)

agrupando termos, esta equação fica melhor escrita como

\( x \left( f(x_{l}) – f(x_{r}) \right) = x_{r} f(x_{l}) – x_{l} f(x_{r}) \)

Dividindo ambos lados da equação por \(f(xl) – f(xr) \) ,

\( x = \dfrac{ x_{r} f(x_{l}) – x_{l} f(x_{r}) }{ f(x_{l}) – f(x_{r}) }\)

esta é uma forma de expressar a função de iteração para o Regula Falsi. Ela permite o cálculo da raiz \(x \) em função dos limites \(x_{l} \) e \(x_{r}\).

Utilizar a Equação 4 para aproximar raízes funciona perfeitamente. Contudo, é possível melhorá-la para que ela utilize menos operações de cálculo. Para isso, vamos separar a subtração dos numeradores em duas frações:

\( x = \dfrac{ x_{r} f(x_{l}) }{ f(x_{l}) – f(x_{r}) } – \dfrac{ x_{l} f(x_{r}) }{ f(x_{l}) – f(x_{r}) } \)

somando e subtraindo \(x_{r} \) na Fórmula 5,

\( x = \dfrac{ x_{r} f(x_{l}) }{ f(x_{l}) – f(x_{r}) } – \dfrac{ x_{l} f(x_{r}) }{ f(x_{l}) – f(x_{r}) } + (x_{r} – x_{r}) = \dfrac{ x_{r} f(x_{l}) }{ f(x_{l}) – f(x_{r}) } + x_{r} – \dfrac{ x_{l} f(x_{r}) }{ f(x_{l}) – f(x_{r}) } – x_{r} \)

ajustando o termo independente \(x_{r}\),

\( x = \left(\dfrac{ x_{r} f(x_{l}) }{ f(x_{l}) – f(x_{r}) } – x_{r} \right) + \left( \dfrac{ x_{l} f(x_{r}) }{ f(x_{l}) – f(x_{r}) } + x_{r}\right) \)

substituindo \(x \) pela Equação 4 na Equação 7,

\( x – x_{r} = \dfrac{ x_{r} f(x_{l}) }{ f(x_{l}) – f(x_{r}) } – \dfrac{ x_{r} f(x_{l}) – x_{r} f(x_{r}) }{ f(x_{l}) – f(x_{r}) } \)

\(\Downarrow \)


\( x = x_{r} + \dfrac{ x_{r} f(x_{r}) }{ f(x_{l}) – f(x_{r}) } – \dfrac{x_{l} f(x_{r}) }{ f(x_{l}) – f(x_{r}) } \)

finalmente,

\( x = x_{r} – \dfrac{ f(x_{r}) \left( x_{l} – x_{r} \right) }{ f(x_{l}) – f(x_{r}) } \)

A função acima utiliza uma chamada a menos de função — não chama \(f(x_{l}) \) — e possui uma multiplicação a menos. Isto significa uma pequena diminuição no overhead, ao ser implementada computacionalmente.

O método da falsa posição possui um algoritmo semelhante ao do Método da Bissecção, com a diferença que, ao invés de dividir o intervalo sempre pela metade, a fim de se obter a aproximação da raiz a partir do ponto médio, utiliza-se a expressão acima para aproximar a raiz.

Os passos seguidos pelo Regulsa Falsi podem ser sumarizados da seguinte forma:

  1. Escolhemos os limites do intervalo que deve incorporar a raiz, chamando os limites de \(x_{l} \) e \(x_{r} \) . Como uma raiz significa um ponto onde a função muda de sinal, o intervalo contém a raiz se \(F(x_{r})F(x_{l}) < 0 \).
  2. Uma estimativa da raiz pode ser aproximada como \(x = x_{r} – \dfrac{F(x_{r})~(x_{l} – x_{r})}{F(x_{l}) – F(x_{r})} \), sendo a única expressão que difere do Método da Bissecção.
  3. Verificamos para saber em qual subintervalo a raiz está
    1. se \(F(x)F(x_{l}) < 0 \) , a raiz está no intervalo da esquerda. Faça \(x_{r} = x \) e volte ao passo \(2\).
    2. se \(F(x)F(x_{l}) > 0 \) , a raiz não esta no intervalo da esquerda, logo, está no da direita, então faça \(x_{l} = x \) e volte ao passo \(2 \) .
    3. se \(F(x)F(x_{l}) = 0 \) , a raiz foi encontrada e é \(x \) .

3. Implementação

def RegulaFalsi(F, xl, xr, errto=0.01, imax=1000):
    """
    Return the root of a function using Regula Falsi
 
    RegulaFalsi(fun, xl, xr, imax, errto)
 
    * fun: Function where find the roots
    * xl: left bound of interval
    * xr: right bound of interval
    * imax: max of iterations allowed
    * errto: tolerated error
 
    Author: Pedro Garcia [sawp@sawp.com.br]
    License: Creative Commons
 
    """
    x = 0
    iterCount = 0
    errno = 1
    fl = F(xl)
    while errno &gt; errto and iterCount &lt; imax:
        xold = x
        iterCount = iterCount + 1
        fr = F(xr)
        x = xr - fr * (xl - xr) / (fl - fr)
        fx = F(x)
        if x != 0:
            errno = fabs((x - xold) / x)
        test = fl * fx
        if test < 0:
            xr = x         
        elif test > 0:
            xl = x
            fl = fx
        else:
            errno = 0
    return x

Esta função está presente no arquivo: http://www.sawp.com.br/code/rootfind/regulafalsi.py

4. Otimizando o Regula Falsi

Embora o Método Regula Falsi possa parecer superior ao da Bissecção, há casos em que seu desempenho é deficiente. Isto ocorre porque sua natureza é unilateral. Ou seja, conforme o programa executa e as iterações continuam, uma das extremidades do intervalo tende à permanecer fixa. Esse comportamento pode levar a uma redução na velocidade de convergência. Normalmente este problema acontece quando se está buscando raízes de uma função com curvatura muito brusca.

Uma maneira de otimizar este problema na convergência é fazer com que o programa perceba que uma extremidade está “presa”. Se estiver, o valor desta extremidade fixa é dividido pela metade, bis-seccionando o intervalo.

Esta abordagem, que consiste em aplicar o comportamento do Método da Bisseção no Regula Falsi, chamaremos de “Método da Falsa Posição Modificado” ou “Regula Falsi Otimizado”.

Os códigos abaixo implementam esse recurso. Os contadores leftCount e rightCount são aplicados para determinar quando uma extremidade está presa por mais de duas iterações. Quando isto ocorre, a função que está fixa é dividida pela metade.

As alterações feitas com base no código demonstrado anteriormente, foram demarcadas com o comentário “\#O2” ao lado. A implementação é:

def RegulaFalsi_O2(F, xl, xr, errto=0.01, imax=1000):
    """
    Return the root of a function using Regula Falsi
 
    RegulaFalsi_O2(fun, xl, xr, imax, errto)
 
    * fun: Function where find the roots
    * xl: left bound of interval
    * xr: right bound of interval
    * imax: max of iterations allowed
    * errto: tolerated error ( for aprox. ), in percents
 
    Author: Pedro Garcia [sawp@sawp.com.br]
    License: Creative Commons
 
    """
    x = 0
    iterCount = 0
    errno = 1
    fl = F(xl)
    leftCount = 0 # O2
    rightCount = 0 # O2
    while errno >= errto and iterCount < = imax:
        xold = x
        iterCount = iterCount + 1
        fr = F(xr)
        # x = (xl+xr)/2.l ponto onde modifica a Bisseccao
        x = xr - fr * (xl - xr) / (fl - fr)
        fx = F(x)
        if x != 0:
            errno = fabs((x - xold) / x)
        test = fl * fx
        if test < 0: 
            xr = x 
            fr = fx # O2
            rightCount = 0 # O2
            leftCount += 1 # O2
            if leftCount >= 2:
                fl = fl / 2 # O2
        elif test > 0:
            xl = x
            fl = fx
            fl = F(xl) # O2
            leftCount = 0 # O2
            rightCount += 1 #O2
            if rightCount >= 2:
                fr = fr / 2 # O2
        else:
            errno = 0
    return x

Um exemplo de utilização desta função pode ser encontrado em: http://www.sawp.com.br/code/rootfind/regulafalsi_modificado.py

5. Copyright

Este documento está disponível sob a licença Creative Commons. As regras dos direitos de cópia deste conteúdo estão acessíveis em http://creativecommons.org/licenses/by-nc-nd/2.5/br/.

References

[1] Ralston, Anthony and Rabinowitz, Philip, A First Course in Numerical Analysis.(2nd ed.) McGraw-Hill and Dover, (2001), 338.

[2] N.B Franco, Cálculo Numérico Pearson Prentice Hall, (2006), 83.