Return to Computer Vision Notebooks

Numerical Root Finding



Overview and implementation of some numerical methods for root finding.

[PT-BR content]

Na matemática, a raiz (ou "zero") de uma função polinomial $f(x)$ é todo valor de $x$ em que a mesma função intercepta o eixo das abscissas no plano cartesiano, ou seja: $f(x)=0$. Geralmente encontramos os valores das raízes de forma analítica (ou método direto). Por exemplo, dada uma função do primeiro grau $f(x)=2x-2$, podemos obter a equação $2x-2=0$ e determinar que a raíz é $1$, já que:

$$ f(1)=2 \cdot 1-2=2-2=0 $$

Se a função for do segundo grau, é possível encontrar (ou não) suas raízes por meio de fatoração ou pela fórmula de Bhaskara. Uma função quadrática pode ter até 2 raízes. Ou seja, em polinômios, o número de raízes possíveis está ligado ao grau ou ordem de uma função. Uma função do segundo grau é um polinômio de grau 2 e, desta forma, pode possuir até 2 raízes. Um polinômio de grau 3 terá até 3 raízes, um de 4 terá 4 e assim por diante. Nem sempre é fácil encontrar o valor de uma raiz de forma analítica, pois elas podem não ser exatas. Para isso são utilizados métodos numéricos, que visam encontrar o valor da raiz por meio de convergência. Para os exemplos a seguir, utilizaremos a função:

$$ \large f(x)=\frac{x^3}{4}+\frac{3x^2}{4}-\frac{3x}{2}-2 $$

Apesar de a função ser de facil solução analítica ou seja, suas raízes serem fáceis de serem encontradas de forma direta, iremos utilizá-la para fins de estudo e verificação do funcionamento dos métodos. A função possui 3 raízes reais, como podem ser verificados a seguir.

root-finding analytical

1. Método da bissecão


O método da bisseção funciona com o particionamento de um intervalo inicial $[a,b]$ e seguido da seleção do subintervalo que contenha a raiz, tornando-o o próximo intervalo a ser bisseccionado. Os valores para a e b serão redefinidos com as extremidades do subintervalo e o processo irá se repetir até que o valor de uma das extremidades aplicado à função ou tamanho do intervalo seja menor que o parâmetro de erro $\large \epsilon$. A bisseção é determinada pelo ponto médio entre o intervalo, de forma que:

$$ \large x_n=\frac{a+b}{2}, \quad \textrm{para} \quad n=1,2,3 \ldots $$

O intervalo $[a,b]$ será válido apenas se houver apenas um número ímpar de raízes entre ele, caso contrário o algorítmo não irá convergir. A verificação da existência de uma raiz entre um intervalo qualquer é dada com a verificação da troca de sinais entre o mesmo, de forma que:

$$ \large f(a) \cdot f(b) \geq 0 $$

Caso intervalo seja válido, a seleção do subintervalo particionado é dada por:

$$ \textrm{Se} \quad f(a) \cdot f(x_n) < 0, \quad \textrm{então} \quad b=x_n \quad \textrm{senão} \quad a=x_n $$

root-finding bisection method

2. Método da falsa posição


O método da falsa posição é bastante semelhante ao da bisseção. Ele particiona o intervalo e seleciona subintervalos, até que o um intervalo selecionado tenha o valor de uma das extremidades menor que o erro $\large \epsilon$. A diferença é que, na bisseção, o particionamento do intervalo era dado por uma média aritimética simples. Já no método da falsa posição a média será ponderada com base na extremidade que tiver valor mais próximo à raiz. Ou seja, a extremidade que tiver o menor valor. A média aritimética ponderada pode ser entendida por:

$$ \large x_n=a-\frac{(b-a) \cdot f(a)}{f(b)-f(a)}, \quad \textrm{para} \quad n=1,2,3 \ldots $$

Note que a extremidade que irá convergir será a de menor valor e não necessariamente a mais próxima, assim como acontece no exemplo a seguir. O critério de escolha da extremidade pode ser entendido por:

$$ \textrm{Se} \quad f(a) \cdot f(x_n) < 0, \quad \textrm{então} \quad b=x_n \quad \textrm{senão} \quad a=x_n $$

root-finding false position method

3. Método Newton-Raphson


O método newton-raphson (ou método das tangentes) é sem dúvida o método que converge mais rápido, porém existe um preço a se pagar por isso. O primeiro, assim como nos outros métodos, é necessário saber se no intervalo existe uma raiz. O segundo é que, para se obter a tangente da função, deve-se ter o conhecimento analítico da primeira derivada de $f(x)$, de forma que:

$$ \large x_n=x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})}, \quad \textrm{para} \quad n=1,2,3 \ldots $$

Um passo bastante importante para o bom funcionamento do método é escolher a melhor extremidade do intervalo $[a,b]$ para iniciar o processo. Para isso, faremos uso da segunda derivada, de forma que:

$$ f(x_i) \cdot f''(x_i) > 0, \quad \textrm{Para} \quad i=\{ \textrm{Extremos do intervalo} \} $$

A representação de $f'(x)$ e $f''(x)$ podem ser entendidas, respectivamente:

$$ f'(x)=\frac{d}{dx}f(x)=\frac{3x^2}{4}+\frac{3x}{2}-\frac{3}{2} \quad ; \quad f''(x)=\frac{d}{dx}f'(x)=\frac{d}{dx}\frac{d}{dx}f(x)=\frac{3x}{2}+\frac{3}{2} $$

root-finding newton-raphson method

4. Método das secantes


O método das secantes é uma opção que geralmente converge mais rapido que o da bisseção e não necessita da aquisição analítica da derivada, assim como no newton-raphson. Ao invés disso, semelhantemente ao método da falsa posição, é utilizado o quociente da diferença no lugar de $f'(x)$, de forma que:

$$ \large x_{n+1}=x_n-\frac{f(x_n)}{\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}}=x_n-\frac{(x_n-x_{n-1}) \cdot f(x_n)}{f(x_n)-f(x_{n-1})}, \quad \textrm{para} \quad n=1,2,3 \ldots $$

root-finding secant method