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
[editar | editar código-fonte]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 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
por resulta no quociente e no resto tais que
Uma segunda divisão de por é realizada para resultar no quociente e no resto de modo que
As variáveis e os são funções de e . Eles podem ser encontrados de maneira recursiva do seguinte modo
A função quadrática divide uniformemente o polinômio, ou seja, não há resto quando
Os valores de e para isso ocorrer podem ser encontrados arbitrando valores iniciais e iterando o método de Newton em duas dimensões
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
[editar | editar código-fonte]A tarefa é determinar o par de raízes do polinômio
Como este é o primeiro polinômio quadrático, podemos escolher o polinômio normalizado formado pelos três principais coeficientes de f(x), assim,
A iteração produz a tabela
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
[editar | editar código-fonte]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.
![]() |
![]() |
![]() |
As imagens representam pares . Pontos na metade superior do plano t>0 correspondem a um fator linear com raízes , ou seja, . Pontos na metade inferior do plano t<0 correspondem a fatores quadráticos com raízes , ou seja, , então em geral . 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
Bibliografia
[editar | editar código-fonte]- 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
[editar | editar código-fonte]- 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)