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.

Descrição do método

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 $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

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

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

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

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

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

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

${\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

$c(u,v)=d(u,v)=0.$

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

${\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.

Exemplo

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

$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,

$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

Passos da iteração do método de Bairstow

N°	u	v	compr. do passo	raízes
0	1,833333333333	-5,500000000000	5,579008780071	-0,916666666667±2,517990821623
1	2,979026068546	-0,039896784438	2,048558558641	-1,489513034273±1,502845921479
2	3,635306053091	1,900693009946	1,799922838287	-1,817653026545±1,184554563945
3	3,064938039761	0,193530875538	1,256481376254	-1,532469019881±1,467968126819
4	3,461834191232	1,385679731101	0,428931413521	-1,730917095616±1,269013105052
5	3,326244386565	0,978742927192	0,022431883898	-1,663122193282±1,336874153612
6	3,333340909351	1,000022701147	0,000023931927	-1,666670454676±1,333329555414
7	3,333333333340	1,000000000020	0,000000000021	-1,666666666670±1,333333333330
8	3,333333333333	1,000000000000	0,000000000000	-1,666666666667±1,333333333333

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.

Desempenho

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.

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

As imagens representam pares $(s,t)\in [-3,3]^{2}$. Pontos na metade superior do plano t>0 correspondem a um fator linear com raízes $s\pm it$, ou seja, $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 $s\pm t$, ou seja, $x^{2}+ux+v=(x-s)^{2}-t^{2}$, então em geral $(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.

Bibliografia

• 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 

Ligações externas

• 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)