Método de Bairstow

Em análise numérica, o método de Bairstow é um eficiente algoritmo para encontrar raízes de uma função polinomial real de grau arbitrário. O primeiro registro do algoritmo data de 1920, no livro Applied Aerodynamics de Leonard Bairstow. O algoritmo encontra raízes em pares de conjugados complexos usando apenas aritmética real.

A abordagem do método de Bairstow é usar o método de Newton para ajustar os coeficiente u e v na função quadrática ${\displaystyle x^{2}+ux+v}$ até que suas raízes também sejam as raízes do polinômio que se está resolvendo. As raízes da função quadrática podem então ser determinadas, e o polinômio pode ser dividido por esta para eliminar as raízes. Este processo é então iterado até que o polinômio se torne quadrático ou linear, e todas suas raízes estejam determinadas.

Divisão do polinômio a ser resolvido

${\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}$

por ${\displaystyle x^{2}+ux+v}$ resulta no quociente ${\displaystyle Q(x)=\sum _{i=0}^{n-2}b_{i}x^{i}}$ e no resto ${\displaystyle cx+d}$ tais que

${\displaystyle P(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-2}b_{i}x^{i}\right)+(cx+d).}$

Uma segunda divisão de ${\displaystyle Q(x)}$ por ${\displaystyle x^{2}+ux+v}$ é realizada para resultar no quociente ${\displaystyle R(x)=\sum _{i=0}^{n-4}f_{i}x^{i}}$ e no resto ${\displaystyle gx+h}$ de modo que

${\displaystyle Q(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-4}f_{i}x^{i}\right)+(gx+h).}$

As variáveis ${\displaystyle c,\,d,\,g,\,h}$ e os ${\displaystyle \{b_{i}\},\;\{f_{i}\}}$ são funções de ${\displaystyle u}$ e ${\displaystyle v}$. Eles podem ser encontrados de maneira recursiva do seguinte modo

${\displaystyle {\begin{aligned}b_{n}&=b_{n-1}=0,&f_{n}&=f_{n-1}=0,\\b_{i}&=a_{i+2}-ub_{i+1}-vb_{i+2}&f_{i}&=b_{i+2}-uf_{i+1}-vf_{i+2}\qquad (i=n-2,\ldots ,0),\\c&=a_{1}-ub_{0}-vb_{1},&g&=b_{1}-uf_{0}-vf_{1},\\d&=a_{0}-vb_{0},&h&=b_{0}-vf_{0}.\end{aligned}}}$

A função quadrática divide uniformemente o polinômio, ou seja, não há resto quando

${\displaystyle c(u,v)=d(u,v)=0.}$

Os valores de ${\displaystyle u}$ e ${\displaystyle v}$ para isso ocorrer podem ser encontrados arbitrando valores iniciais e iterando o método de Newton em duas dimensões

${\displaystyle {\begin{bmatrix}u\\v\end{bmatrix}}:={\begin{bmatrix}u\\v\end{bmatrix}}-{\begin{bmatrix}{\frac {\partial c}{\partial u}}&{\frac {\partial c}{\partial v}}\\[3pt]{\frac {\partial d}{\partial u}}&{\frac {\partial d}{\partial v}}\end{bmatrix}}^{-1}{\begin{bmatrix}c\\d\end{bmatrix}}:={\begin{bmatrix}u\\v\end{bmatrix}}-{\frac {1}{vg^{2}+h(h-ug)}}{\begin{bmatrix}-h&g\\[3pt]-gv&gu-h\end{bmatrix}}{\begin{bmatrix}c\\d\end{bmatrix}}}$

até convergir. Este método de encontrar zeros de polinômios pode então ser facilmente implementado com uma linguagem de programação ou até mesmo uma planilha.

A tarefa é determinar o par de raízes do polinômio

${\displaystyle f(x)=6\,x^{5}+11\,x^{4}-33\,x^{3}-33\,x^{2}+11\,x+6.}$

Como este é o primeiro polinômio quadrático, podemos escolher o polinômio normalizado formado pelos três principais coeficientes de f(x), assim,

${\displaystyle u={\frac {a_{n-1}}{a_{n}}}={\frac {11}{6}};\quad v={\frac {a_{n-2}}{a_{n}}}=-{\frac {33}{6}}.}$

A iteração produz a tabela

Após oito iterações o método produz um fator quadrático que contém as raízes -1/3 e -3 dentro da precisão representada. O comprimento do passo a partir da quarta iteração demonstra a velocidade superlinear de convergência.

O algoritmo de Bairstow herda a convergência quadrática local do método de Newton, exceto no caso de fatores quadráticos de multiplicidade maior que 1, quando a convergência para esse fator é linear. Um caso particular de instabilidade é observado quando o polinômio tem grau ímpar e apenas uma raiz real. Fatores quadráticos que têm um pequeno valor nessa raiz real tendem a divergir para infinito.

${\displaystyle f(x)=x^{5}-1}$	${\displaystyle f(x)=x^{6}-x}$	${\displaystyle {\begin{aligned}f(x)=&6x^{5}+11x^{4}-33x^{3}\\&-33x^{2}+11x+6\end{aligned}}}$

As imagens representam pares ${\displaystyle (s,t)\in [-3,3]^{2}}$. Pontos na metade superior do plano t>0 correspondem a um fator linear com raízes ${\displaystyle s\pm it}$, ou seja, ${\displaystyle x^{2}+ux+v=(x-s)^{2}+t^{2}}$. Pontos na metade inferior do plano t<0 correspondem a fatores quadráticos com raízes ${\displaystyle s\pm t}$, ou seja, ${\displaystyle x^{2}+ux+v=(x-s)^{2}-t^{2}}$, então em geral ${\displaystyle (u,\,v)=(-2s,\,s^{2}+t\,|t|)}$. Os pontos são coloridos de acordo com o ponto final da iteração de Bairstow, pontos pretos indicam comportamento divergente.

A primeira imagem é a demonstração do caso de um única raiz real. A segunda indica que é possível contornar o comportamento divergente introduzindo uma raiz real, ao custo de aumentar a velocidade de convergência. A terceira imagem corresponde ao exemplo da seção anterior.

Referências

• Bairstow, Leonard (1920). Applied Aerodynamics (em inglês). [S.l.]: Longmans, Green and Company. 565 páginas 
• Freund, Roland W; Hoppe, Ronald H. W (2007). Stoer/Bulirsch. Numerische Mathematik 1 (em alemão). [S.l.]: Springer London. 410 páginas. ISBN 978-3-540-45389-5 

• Algoritmo de Bairstow em Mathworld (em inglês)
• Exemplo de solver de polinômios de grau igual ao inferior a 10 usando o método de Bairstow (em inglês)
• Outro solver de polinômios que usa o método de Bairstow (em inglês)
• Implementação em C++ do método de Lin-Bairstow diponível na biblioteca VTK (em inglês)