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{array}{cccc}{b}_n& =b_{n-1}=0,& f_n& =f_{n-1}=0,\\ b_i& =a_{i+2}-u{b}_{i+1}-v{b}_{i+2}& f_i& =b_{i+2}-u{f}_{i+1}-v{f}_{i+2}(i=n-2,\dots ,0),\\ c& =a_1-u{b}_0-v{b}_1,& g& =b_1-u{f}_0-v{f}_1,\\ d& =a_0-v{b}_0,& h& =b_0-v{f}_0.\end{array}$

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

$\left[\begin{array}{c}u\\ v\end{array}\right]:=\left[\begin{array}{c}u\\ v\end{array}\right]-{\left[\begin{array}{cc}\frac{\partial c}{\partial u}& \frac{\partial c}{\partial v}\\ \frac{\partial d}{\partial u}& \frac{\partial d}{\partial v}\end{array}\right]}^{-1}\left[\begin{array}{c}c\\ d\end{array}\right]:=\left[\begin{array}{c}u\\ v\end{array}\right]-\frac{1}{v{g}^2+h(h-ug)}\left[\begin{array}{cc}-h& g\\ -gv& gu-h\end{array}\right]\left[\begin{array}{c}c\\ d\end{array}\right]$

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)=6x^5+11x^4-33x^3-33x^2+11x+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};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{array}{cc}f(x)=& 6x^5+11x^4-33x^3\\ & -33x^2+11x+6\end{array}$

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

• Predefinição:Citar livro
• Predefinição:Citar livro

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)