# 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.