Método de Brent

O método de Brent, conhecido como Brent-Dekker, é um método misto que tem como intuito combinar abordagens de enquadramento e busca. Criado por Richard Peirce Brent, ele tem como objetivo encontrar raízes de funções a partir da associação de três métodos. O algoritmo hibrido combina o método da bissecção, o método das secantes e a interpolação quadrática inversa.

Método de Dekker

A ideia de combinar o método de bisseção com o método secante remonta a Dekker (1969).

Suponha que queremos resolver a equação f(x) = 0. Assim como no método de bisseção, precisamos inicializar o método de Dekker com dois pontos, digamos a₀ e b₀, de tal forma que f(a₀) e f(b₀) têm sinais opostos. Se f for contínuo em [a₀, b₀], o teorema do valor intermediário garante a existência de uma solução entre 0 e b₀.

Três pontos estão envolvidos em cada iteração:

• b_k é o iterado atual, ou seja, o palpite atual para a raiz de f.
• a_k é o "contraponto", ou seja, um ponto de tal forma que f(a_k) e f(b_k) têm sinais opostos, de modo que o intervalo [a_k, b_k] contém a solução. Além disso, | f(b_k)| deve ser menor ou igual a | f(a_k)|, de modo que b_k é um palpite melhor para a solução desconhecida do que a_k.
• b_k−1 é o iterado anterior (para a primeira iteração, definimos b_k−1 = a₀).

Dois valores provisórios para o próximo iterado são computados. O primeiro é dado pela interpolação linear, também conhecido como método secante:

$s={\begin{cases}bk-{\tfrac {bk-bk-1}{f(bk)-f(bk-1)}}f(bk),&{\text{se }}f(bk){\text{≠ f(bk-1) }}\\m,&{\text{caso contrário }}{\text{ }}\end{cases}}$

e o segundo é dado pelo método de bisseção

$m={\frac {ak+bk}{2}}$

Se o resultado do método secante, s, fica estritamente entre b_k e m, então ele se torna o próximo iterado (b_k+1 = s), caso contrário o ponto médio é usado (b_k+1 = m).

Em seguida, o valor do novo contraponto é escolhido de tal forma que f(a_k+1) e f(b_k+1) têm sinais opostos. Se f(a_k) e f(b_k+1) têm sinais opostos, então o contraponto permanece o mesmo: a_k+1 = a_k. Caso contrário, f(b_k+1) e f(b_k) têm sinais opostos, de modo que o novo contraponto se torna um_k+1 = b_k.

Finalmente, se | f(a_k+1)| < | f(b_k+1)|, então um_k+1 é provavelmente um palpite melhor para a solução do que b_k+1, e, portanto, os valores de um_k+1 e b_k+1 são trocados.

Isso termina a descrição de uma única iteração do método de Dekker.

O método de Dekker funciona bem se a função f for razoavelmente bem comportada. No entanto, há circunstâncias em que cada iteração emprega o método secante, mas os iterados b_k convergem muito lentamente (em particular, | b_k − b_k−1| pode ser arbitrariamente pequeno). O método de Dekker requer muito mais iterações do que o método de bisseção neste caso.

Método de Brent

1.   MÉTODO DA BISSEÇÃO

• Garante a convergência desde que no intervalo escolhido [A,B] exista uma raiz.

• Calcula-se o ponto médio do intervalo, analisando o sinal do novo $F(C)$.

$C=(A+B)/2$

• A partir do sinal de $F(C)$, avalia-se o novo intervalo, podendo ser [A,C] ou [C,B].

• Repete-se o processo até que o erro seja menor que a precisão desejada

$Erro=(A-B)/10^{\mathbb {N} }$

2.    MÉTODO DA SECANTE

• Uma vez determinado o intervalo inicial, é calculada uma reta secante que passa por esses pontos.

• A partir da equação de recorrência, encontra-se um novo x que será utilizado na próxima iteração

• O erro pode ser calculado pela diferença entre o x encontrado e o anterior.

3.    MÉTODO DA INTERPOLAÇÃO QUADRÁTICA INVERSA

• Baseia-se na fórmula de Lagrange, onde é preciso de três valores iniciais:
• Igualando-se a equação encontrada a zero, a raiz pode ser obtida.

O terceiro método foi inserido como um teste adicional que deve ser satisfeito antes que o resultado do método secante seja aceito como próximo. Duas desigualdades devem ser simultaneamente satisfeitas:

• Se na etapa anterior utilizar o método de bisseção, a desigualdade deve permanecer para que seja possível fazer a interpolação, caso contrario o método de bisseção é realizado e seu resultado usado para a próxima iteração

$|\delta |<|B_{k}-B_{k-1}|$

• Se na etapa anterior utilizar o método interpolação, então a desigualdade é utilizado em vez de realizar a próxima ação. Quando a desigualdade é verdadeira utiliza-se o método da interpolação, quando a desigualdade é falsa, utiliza-se o método da bisseção.

$|\delta |<|B_{k-1}-B_{k-2}|$

• Se a etapa anterior utilizar o método de bisseção, a desigualdade deve existir, caso contrário, o método é realizado e seu resultado é utilizado para a próxima iteração.

$|S-B_{k}|<1/2|B_{k}-B_{k-1}|$

• Se a etapa anterior realizou a interpolação, então a desigualdade é utilizada.

$|S-B_{k}|<1/2|B_{k-1}-B_{k-2}|$

Algoritmo

input a, b, and (a pointer to) a function for f
calculate f(a)
calculate f(b)
if f(a)f(b) ≥ 0 then 
    exit function because the root is not bracketed.
end if
if |f(a)| < |f(b)| then
    swap (a,b)
end if
c := a
set mflag
repeat until f(b or s) = 0 or |b − a| is small enough (convergence)
    if f(a) ≠ f(c) and f(b) ≠ f(c) then
         (inverse quadratic interpolation)
    else
         (secant method)
    end if
    if (condition 1) s is not between  and b or
       (condition 2) (mflag is set and |s−b| ≥ |b−c|/2) or
       (condition 3) (mflag is cleared and |s−b| ≥ |c−d|/2) or
       (condition 4) (mflag is set and |b−c| < |δ|) or
       (condition 5) (mflag is cleared and |c−d| < |δ|) then
         (bisection method)
        set mflag
    else
        clear mflag
    end if
    calculate f(s)
    d := c  (d is assigned for the first time here; it won't be used above on the first iteration because mflag is set)
    c := b
    if f(a)f(s) < 0 then
        b := s 
    else
        a := s 
    end if
    if |f(a)| < |f(b)| then
        swap (a,b) 
    end if
end repeat 

output b or s (return the root).

Principais características

O método de Brent se destaca pelas seguintes vantagens:

• Convergir rapidamente se as condições iniciais forem "favoráveis".
• Não é necessário o cálculo da derivada.
• Na maioria dos casos o método converge para a solução.

A sua principal desvantagem é que o algoritmo exige que a raiz procurada esteja no intervalo inicialmente fornecido.