Um algoritmo para encontrar raízes é um método numérico para encontrar um valor de x tal que f(x) = 0, para uma dada função f. Tal x é chamado de raiz da função f.
Este artigo está voltado para encontrar raízes escalares, reais ou complexas, aproximadas por números de ponto flutuante. Encontrar raízes inteiras ou raízes algébricas exatas são problemas distintos, cujos algoritmos têm pouco em comum com aqueles discutidos aqui.
Encontrar uma raiz de f(x) − g(x) = 0 é o mesmo que resolver a equação f(x) = g(x). Aqui, x é chamada de desconhecida na equação. Por outro lado, qualquer equação pode tomar a forma canônica f(x) = 0. Então resolver uma equação é a mesma coisa que encontrar uma raiz de uma função.
Métodos para encontrar as raízes numéricas utilizam iteração, produzindo uma sequência de números que esperamos que converjam no sentido de um limite (o chamado "ponto fixo"), que é uma raiz. Os primeiros valores desta série são estimativas. O método calcula os valores subsequentes com base nos antigos e na função f em estudo.
O comportamento de algoritmos para encontrar raízes é estudado em análise numérica. Algoritmos funcionam melhor quando eles se utilizam características conhecidas da função dada. Então, um algoritmo para encontrar raízes reais isoladas de um polinômio de baixo grau em uma variável podem ter pouca semelhança com um algoritmo para as raízes complexas de uma função de "caixa-preta", que nem sequer é conhecido por ser diferenciável. Os pontos de discussão a respeito do método variam e incluem capacidade de separar as raízes próximas, robustez em conseguir respostas confiáveis apesar de erros numéricos inevitáveis, e taxa de convergência.
Métodos
Método da Bissecção
O algoritmo mais simples é o Método da Bissecção. Ele funciona quando f é uma função contínua e requer o conhecimento prévio de duas estimativas iniciais, a e b, de tal forma que f (a) e f (b) tenham sinais opostos. Embora seja confiável, ela converge lentamente, ganhando um bit de precisão com cada iteração.
Falsa Posição (Regula Falsi)
O método da falsa posição, também chamado de "método regula falsa", é como o método da secante. No entanto, em vez de reter os últimos dois pontos, ele garante a manutenção de um ponto de cada lado da raiz. O método da falsa posição é mais rápido do que o método da bissecção e mais robusto do que o método secante, mas exige dois pontos de partida para suporte a raiz. O método de Ridders é uma variante do método de falsa posição que também avalia a função no ponto médio do intervalo de tempo, dando mais rápida convergência com robustez semelhante.
Métodos abertos
Método de Newton (e métodos similares baseados em derivadas)
O método de Newton assume que a função de f deve ter uma derivada contínua. Esse método pode não convergir se iniciado muito longe de uma raiz. No entanto, quando converge é mais rápido do que o método da bisseção e tem ordem quadrática de convergência. O método de Newton também é importante porque se generaliza prontamente para problemas de dimensão superior. Métodos de Newton com ordens superiores de convergência são os "Métodos de Householder". O método seguinte ao método de Newton é o "método de Halley" com ordem cúbica de convergência.
Método da Secante
Substituindo a derivada no método de Newton por uma diferencial finita temos o "Método da Secante". Esse método não exige o cálculo nem a existência de uma derivação, mas por isso apresenta convergência mais lenta (da ordem de, aproximadamente, 1,6). A generalização do método secante em dimensões maiores é método de Broyden.
Interpolação
O método da secante também surge da aproximação de uma função desconhecida f por interpolação linear. Quando a interpolação quadrática é usada em vez disso, chega-se a "método de Muller." Ela converge mais rapidamente do que o método da secante. Uma característica particular deste método é que as iterações Xn pode tornar-se um número complexo.
O método de Sidi permite a interpolação com um alto grau polinomial. Quanto maior for o grau do polinômio interpolador, mais rápida a convergência. O método de Sidi permite a convergência com uma ordem arbitrariamente próximo a 2.
Interpolação inversa
Isto pode ser evitado pela interpolação d inversa de f, resultando no método de interpolação da inversa quadrático. Mais uma vez, a convergência é assintoticamente mais rápida do que o método da secante, mas muitas vezes se comporta mal quando as iterações não estão próximas da raiz.
Combinações de métodos
Método de Brent
O Método de Brent é uma combinação do método da bissecção, do método da secante e do método da interpolação quadrática inversa. Em cada iteração, o método de Brent decide qual método destes três é vai produzir um resultado melhor, e assim prossegue, fazendo um passo de acordo com esse método. Isso dá um método robusto e rápido, que, devido a isso, se faz muito popular.
Encontrar raízes de polinômios
Tem sido dada muita atenção para o caso especial que a função de f é um polinômio; existem algoritmos que exploram a natureza polinomial de f em busca de suas raízes. Para um polinômio univariante de grau inferior a cinco, existem soluções de forma fechada, como a fórmula quadrática, que produz todas as raízes. No entanto, até mesmo este solução de grau dois deve ser usado com cautela para garantir a estabilidade numérica. Ainda mais cuidado deve ser tomado com as soluções de graus três e quatro, devido à sua complexidade. Polinômios de alto grau não têm essa solução geral, de acordo com a teoria de Abel-Ruffini (1824, 1799).
O método de Birge - Vieta combina o método de Horner de avaliação polinomial com Newton - Raphson para proporcionar um método computacional acelerado.
Para raízes reais, o "teorema de Sturm" e a regra dos sinais de Descartes fornecem caminhos para localizar e separar raízes. Isso somado com intervalo de aritmética combinado com o Método de Newton produz algoritmos robustos e rápidos.
O algoritmo para isolar as raízes, usando a regra dos sinais de Descartes e e o teorema de Vincent, era originalmente chamado de algoritmo de Uspensky modificado pelos seus inventores Collins e Akritas. Depois de passar por nomes como "método Collins- Akritas" e "Método de Descartes ", foi François Boulier, da Universidade de Lille, que lhe deu o nome "teorema de Vincent- Collins- Akritas" (com base no fato de que "o método de Uspensky" não existe e nem o "método de Descartes". Este algoritmo foi melhorado por Rouillier e Zimmerman e a implementação resultante é, até agora, o método de bissecção mais rápido. Ele tem o mesmo pior caso de complexidade do algoritmo Sturm, mas é quase sempre muito mais rápido. É o algoritmo padrão de [ [maple (software) | bordo ]]. de encontrar a função fsolve Outro método que se baseia no teorema de Vincent é o método de Vincent- Akritas-Strzeboński (VAS). Foi demonstrado que o método VAS (frações contínuas) é mais rápido que até a mais rápida implementação do método VCA (bisseção). Mais precisamente, para os polinômios de alto grau Mignotte, o método VAS é de cerca de 50 mil vezes mais rápido do que a implementação mais rápida da VCA. Veja o teorema de Bundan (Budan's theorem) para uma descrição do contexto histórico desses métodos. Para comparar o método VAS com o Sturm, use as funções realroot(poly) e time(realroot(poly)) no Xcas. O método padrão utilizado para isolar raízes é o método VAS; para usar o método de escrever realroot (sturm, poly).
Uma possibilidade é a de formar a matriz do polinômio. Já que os valores próprios desta matriz coincidem com as raízes do polinômio, podem-se utilizar diversos algoritmos para encontrar as raízes do polinômio. Por exemplo, o método de Bernoulli para localizar a raiz de maior módulo, se essa existe, acaba por ser o método da potência aplicado à matriz. O método de potência inverso, que encontra a menor raiz em primeiro lugar, é o que origina o método de Jenkins-Traub e a sua estabilidade numérica e convergência rápida, mesmo na presença de cluster ou múltiplas raízes.
Método de Laguerre, assim como o método de Halley, utilizam derivadas de segunda ordem e aritmética complexa, incluindo a raiz quadrada complexa, para expor convergência de ordem cúbica de raízes simples, dominando a convergência quadrática exibida pelo método de Newton.
O método de Bairstow utiliza o método de Newton para encontrar fatores quadrático de um polinômio com coeficientes reais. Ele pode determinar ambas as raízes reais e complexas de um polinômio real sem usar aritmética complexa.
O simples método de Durand-Kerner e o método de Aberth (um pouco mais complicado) encontram simultaneamente todas as raízes usando apenas simples aritmética de números complexos.
O "método da divisão de círculo" é útil para encontrar as raízes de polinômios de alto grau de precisão arbitrária, que tem quase ideal complexidade neste cenário. Outro método com esse estilo é o método de Dandelin – graffe (na verdade, devido a Lobachevsky), que fatora o polinômio.
Polinômio de Wilkinson mostra que a alta precisão aritmética pode ser necessária no cálculo das raízes de um polinômio cujos coeficientes são conhecidos: o problema de encontrar as raízes dos coeficientes é, em geral mal condicionado.
Encontrar múltiplas raízes de polinômios
A maioria dos algoritmos para encontrar raízes se comportam mal quando há raízes múltiplas ou raízes muito próximas. No entanto, para polinômios cujos coeficientes são exatamente dadas como inteiros ou números racionais, existe um método eficiente para fatorá-los em fatores que têm somente raízes simples e cujos coeficientes também são determinados. Este método, denominado fatoração livre do quadrado, baseia-se no fato de que as raízes múltiplas de um polinômio são raízes de um denominador comum do polinomial de seu derivado.
Essa fatoração de um polinômio p é uma fatoração 
, onde cada 
é 1 ou um polinômio sem raiz múltipla, e dois 's diferentes não apresentam nenhuma raiz comum.
Um método eficiente para calcular esta fatoração é o algoritmo de Yun.
Ver também
Referências
Ligações externas
