Algoritmos de localização de raízes - Root-finding algorithms

Em matemática e computação , um algoritmo de localização de raiz é um algoritmo para encontrar zeros , também chamado de "raízes", de funções contínuas . Um zero de uma função f , dos números reais aos números reais ou dos números complexos aos números complexos, é um número x tal que f ( x ) = 0 . Como, geralmente, os zeros de uma função não podem ser calculados exatamente nem expressos de forma fechada , os algoritmos de localização de raízes fornecem aproximações para zeros, expressos como números de ponto flutuante ou como pequenos intervalos de isolamento , ou discos para raízes complexas (um intervalo ou disco sendo a saída equivalente a uma saída aproximada junto com um limite de erro).

Resolver uma equação f ( x ) = g ( x ) é o mesmo que encontrar as raízes da função h ( x ) = f ( x ) - g ( x ) . Assim, os algoritmos de localização de raízes permitem resolver qualquer equação definida por funções contínuas. No entanto, a maioria dos algoritmos de localização de raízes não garante que eles encontrarão todas as raízes; em particular, se tal algoritmo não encontrar nenhuma raiz, isso não significa que nenhuma raiz existe.

A maioria dos métodos numéricos de localização de raiz usa iteração , produzindo uma sequência de números que, esperançosamente, converge para a raiz como um limite . Eles exigem uma ou mais suposições iniciais da raiz como valores iniciais, então cada iteração do algoritmo produz uma aproximação sucessivamente mais precisa da raiz. Como a iteração deve ser interrompida em algum ponto, esses métodos produzem uma aproximação da raiz, não uma solução exata. Muitos métodos calculam valores subsequentes avaliando uma função auxiliar nos valores anteriores. O limite é, portanto, um ponto fixo da função auxiliar, que é escolhido por ter as raízes da equação original como pontos fixos e por convergir rapidamente para esses pontos fixos.

O comportamento dos algoritmos gerais de localização de raízes é estudado na análise numérica . No entanto, para polinômios, o estudo de localização de raízes geralmente pertence à álgebra computacional , uma vez que as propriedades algébricas dos polinômios são fundamentais para os algoritmos mais eficientes. A eficiência de um algoritmo pode depender drasticamente das características das funções fornecidas. Por exemplo, muitos algoritmos usam a derivada da função de entrada, enquanto outros trabalham em todas as funções contínuas . Em geral, não é garantido que algoritmos numéricos encontrem todas as raízes de uma função, portanto, deixar de encontrar uma raiz não prova que não há raiz. No entanto, para polinômios , existem algoritmos específicos que usam propriedades algébricas para certificar que nenhuma raiz foi perdida e localizar as raízes em intervalos separados (ou discos para raízes complexas) que são pequenos o suficiente para garantir a convergência de métodos numéricos (normalmente o método de Newton ) para a raiz exclusiva assim localizada.

Métodos de agrupamento

Os métodos de colchetes determinam intervalos sucessivamente menores (colchetes) que contêm uma raiz. Quando o intervalo é pequeno o suficiente, uma raiz foi encontrada. Eles geralmente usam o teorema do valor intermediário , que afirma que se uma função contínua tem valores de sinais opostos nos pontos finais de um intervalo, então a função tem pelo menos uma raiz no intervalo. Portanto, eles precisam começar com um intervalo de forma que a função assuma sinais opostos nos pontos finais do intervalo. No entanto, no caso de polinômios, existem outros métodos ( regra dos sinais de Descartes , teorema de Budan e teorema de Sturm ) para obter informações sobre o número de raízes em um intervalo. Eles levam a algoritmos eficientes para o isolamento da raiz real de polinômios, que garantem a localização de todas as raízes reais com uma precisão garantida.

Método de bissecção

O algoritmo de localização de raiz mais simples é o método da bissecção . Deixe f ser uma função contínua , para o qual se sabe um intervalo [ a , b ] tal que f ( um ) e f ( b ) têm sinais opostos (um suporte). Seja c = ( a + b ) / 2 o meio do intervalo (o ponto médio ou o ponto que divide o intervalo). Então, ou f ( a ) e f ( c ) , ou f ( c ) e f ( b ) têm sinais opostos, e um dividiu por dois o tamanho do intervalo. Embora o método de bissecção seja robusto, ele ganha um e apenas um bit de precisão a cada iteração. Outros métodos, sob condições apropriadas, podem obter precisão mais rapidamente.

Posição falsa ( regula falsi )

O método da posição falsa , também chamado de método regulula falsi , é semelhante ao método da bissecção, mas em vez de usar a pesquisa da bissecção no meio do intervalo, ele usa o intercepto x da linha que conecta os valores da função plotados nos pontos finais do intervalo , isso é

${\ displaystyle c = {\ frac {af (b) -bf (a)} {f (b) -f (a)}}.}$

A posição falsa é semelhante ao método da secante , exceto que, em vez de reter os dois últimos pontos, garante manter um ponto em cada lado da raiz. O método da posição falsa pode ser mais rápido que o método da bissecção e nunca divergirá como o método da secante; no entanto, pode falhar em convergir em algumas implementações ingênuas devido a erros de arredondamento que podem levar a um sinal errado para f ( c ) ; normalmente, isso pode ocorrer se a taxa de variação de f for grande na vizinhança da raiz.

Método ITP

O método ITP é o único método conhecido para colocar a raiz entre parênteses com as mesmas garantias de pior caso do método da bissecção, enquanto garante uma convergência superlinear para a raiz de funções suaves como o método da secante. É também o único método conhecido com garantia de superar o método da bissecção em média para qualquer distribuição contínua na localização da raiz (consulte ITP Method # Analysis ). Ele faz isso acompanhando tanto o intervalo de bracketing quanto o intervalo minmax no qual qualquer ponto nele converge tão rápido quanto o método de bissecção. A construção do ponto c consultado segue três etapas: interpolação (semelhante à regra falsi), truncamento (ajuste da regra falsi semelhante à regra falsa § Melhorias na regra falsa ) e depois projeção no intervalo minmax. A combinação dessas etapas produz um método ideal minmax simultaneamente com garantias semelhantes aos métodos baseados em interpolação para funções suaves e, na prática, superará tanto o método de bissecção quanto os métodos baseados em interpolação em funções suaves e não suaves.

Interpolação

Muitos processos de localização de raízes funcionam por interpolação . Consiste em usar os últimos valores aproximados calculados da raiz para aproximar a função por um polinômio de baixo grau, que assume os mesmos valores nessas raízes aproximadas. Em seguida, a raiz do polinômio é calculada e usada como um novo valor aproximado da raiz da função, e o processo é iterado.

Dois valores permitem interpolar uma função por um polinômio de grau um (ou seja, aproximar o gráfico da função por uma reta). Esta é a base do método secante . Três valores definem uma função quadrática , que aproxima o gráfico da função por uma parábola . Este é o método de Muller .

Regula falsi é também um método de interpolação, que difere do método da secante por usar, para interpolar por uma linha, dois pontos que não são necessariamente os dois últimos pontos calculados.

Métodos iterativos

Embora todos os algoritmos de localização de raiz procedam por iteração , um método iterativo de localização de raiz geralmente usa um tipo específico de iteração, consistindo na definição de uma função auxiliar, que é aplicada às últimas aproximações computadas de uma raiz para obter uma nova aproximação. A iteração para quando um ponto fixo ( até a precisão desejada) da função auxiliar é atingido, ou seja, quando o novo valor calculado está suficientemente próximo dos anteriores.

Método de Newton (e métodos baseados em derivadas semelhantes)

O método de Newton assume que a função f tem uma derivada contínua . O método de Newton pode não convergir se iniciado muito longe de uma raiz. No entanto, quando converge, é mais rápido do que o método da bissecção e geralmente é quadrático. O método de Newton também é importante porque generaliza prontamente para problemas de dimensões superiores. Os métodos do tipo Newton com ordens superiores de convergência são os métodos de Household . O primeiro após o método de Newton é o método de Halley com ordem cúbica de convergência.

Método secante

Substituindo a derivada no método de Newton por uma diferença finita , obtemos o método da secante . Este método não requer o cálculo (nem a existência) de uma derivada, mas o preço é uma convergência mais lenta (a ordem é de aproximadamente 1,6 ( proporção áurea )). Uma generalização do método secante em dimensões superiores é o método de Broyden .

Método de Steffensen

Se usarmos um ajuste polinomial para remover a parte quadrática da diferença finita usada no método da Secante, para que se aproxime melhor da derivada, obtemos o método de Steffensen , que tem convergência quadrática, e cujo comportamento (bom e mau) é essencialmente o mesmo que o método de Newton, mas não requer uma derivada.

Interpolação inversa

O aparecimento de valores complexos em métodos de interpolação pode ser evitado interpolando o inverso de f , resultando no método de interpolação quadrática inversa . Novamente, a convergência é assintoticamente mais rápida do que o método da secante, mas a interpolação quadrática inversa geralmente se comporta mal quando as iterações não estão perto 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 da interpolação quadrática inversa . A cada iteração, o método de Brent decide qual dos três métodos provavelmente terá o melhor desempenho e prossegue executando uma etapa de acordo com esse método. Isso dá um método robusto e rápido, que, portanto, goza de considerável popularidade.

Método Ridders

O método Ridders é um método híbrido que usa o valor da função no ponto médio do intervalo para realizar uma interpolação exponencial para a raiz. Isso dá uma convergência rápida com uma convergência garantida de no máximo duas vezes o número de iterações do método da bissecção.

Raízes de polinômios

Encontrar raízes de polinômios é um problema antigo que tem sido objeto de muitas pesquisas ao longo da história. Uma prova disso é que até o século 19 a álgebra significava essencialmente teoria das equações polinomiais .

Encontrar a raiz de um polinômio linear (grau um) é fácil e requer apenas uma divisão. Para polinômios quadráticos (grau dois), a fórmula quadrática produz uma solução, mas sua avaliação numérica pode exigir alguns cuidados para garantir a estabilidade numérica . Para os graus três e quatro, existem soluções de forma fechada em termos de radicais , que geralmente não são convenientes para avaliação numérica, por serem muito complicadas e envolvendo o cálculo de várias n- ésimas raízes cujo cálculo não é mais fácil do que o cálculo direto do raízes do polinómio (por exemplo, a expressão das raízes reais de um polinómio cúbico pode envolver não reais raízes cúbicas ). Para polinômios de grau cinco ou superior , o teorema de Abel-Ruffini afirma que não há, em geral, nenhuma expressão radical das raízes.

Portanto, exceto para graus muito baixos, a descoberta de raízes de polinômios consiste em encontrar aproximações das raízes. Pelo teorema fundamental da álgebra , sabe-se que um polinômio de grau n tem no máximo n raízes reais ou complexas, e esse número é alcançado para quase todos os polinômios.

Segue-se que o problema de encontrar a raiz para polinômios pode ser dividido em três subproblemas diferentes;

• Encontrando uma raiz
• Encontrando todas as raízes
• Encontrar raízes em uma região específica do plano complexo , normalmente as raízes reais ou as raízes reais em um determinado intervalo (por exemplo, quando as raízes representam uma quantidade física, apenas as reais positivas são interessantes).

Para encontrar uma raiz, o método de Newton e outros métodos iterativos gerais funcionam geralmente bem.

Para encontrar todas as raízes, o método mais antigo é, quando uma raiz r foi encontrada, dividir o polinômio por x - r , e reiniciar iterativamente a busca de uma raiz do polinômio quociente. No entanto, exceto para graus baixos, isso não funciona bem por causa da instabilidade numérica : o polinômio de Wilkinson mostra que uma modificação muito pequena de um coeficiente pode mudar dramaticamente não apenas o valor das raízes, mas também sua natureza (real ou complexa). Além disso, mesmo com uma boa aproximação, quando se avalia um polinômio em uma raiz aproximada, pode-se obter um resultado muito próximo de zero. Por exemplo, se um polinômio de grau 20 (o grau do polinômio de Wilkinson) tem uma raiz próxima a 10, a derivada do polinômio na raiz pode ser da ordem deste implica que um erro de no valor da raiz pode produzir um valor do polinômio na raiz aproximada que é da ordem de${\ displaystyle 10 ^ {20};}$${\ displaystyle 10 ^ {- 10}}$${\ displaystyle 10 ^ {10}.}$

Para evitar esses problemas, foram elaborados métodos que calculam todas as raízes simultaneamente, com a precisão desejada. Atualmente, o método mais eficiente é o método de Aberth . Uma implementação gratuita está disponível com o nome de MPSolve . Esta é uma implementação de referência, que pode localizar rotineiramente as raízes de polinômios de grau maior que 1.000, com mais de 1.000 dígitos decimais significativos.

Os métodos para calcular todas as raízes podem ser usados ​​para calcular raízes reais. No entanto, pode ser difícil decidir se uma raiz com uma pequena parte imaginária é real ou não. Além disso, como o número de raízes reais é, em média, o logaritmo do grau, é um desperdício de recursos computacionais calcular as raízes não reais quando se está interessado em raízes reais.

O método mais antigo para calcular o número de raízes reais e o número de raízes em um intervalo resulta do teorema de Sturm , mas os métodos baseados na regra dos signos de Descartes e suas extensões - os teoremas de Budan e Vincent - são geralmente mais eficientes. Para a localização da raiz, todos procedem reduzindo o tamanho dos intervalos em que as raízes são pesquisadas até obter intervalos contendo zero ou uma raiz. Em seguida, os intervalos contendo uma raiz podem ser ainda mais reduzidos para se obter uma convergência quadrática do método de Newton para as raízes isoladas. Os principais sistemas de álgebra computacional ( Maple , Mathematica , SageMath , PARI / GP ) têm cada um uma variante deste método como o algoritmo padrão para as raízes reais de um polinômio.

Outra classe de métodos é baseada na conversão do problema de encontrar raízes polinomiais para o problema de encontrar autovalores da matriz companheira do polinômio. Em princípio, pode-se usar qualquer algoritmo de autovalor para encontrar as raízes do polinômio. No entanto, por razões de eficiência, prefere-se métodos que empreguem a estrutura da matriz, ou seja, podem ser implementados na forma livre de matriz. Entre esses métodos está o método da potência , cuja aplicação à transposta da matriz companheira é o método clássico de Bernoulli para encontrar a raiz de maior módulo. O método de potência inversa com deslocamentos, que encontra alguma raiz menor primeiro, é o que impulsiona a variante complexa ( cpoly ) do algoritmo Jenkins-Traub e dá a ele sua estabilidade numérica. Além disso, é insensível a raízes múltiplas e tem convergência rápida com a ordem (onde está a proporção áurea ) mesmo na presença de raízes agrupadas. Essa convergência rápida vem com um custo de três avaliações polinomiais por etapa, resultando em um resíduo de O (| f ( x ) | ^{2 + 3 φ} ) , que é uma convergência mais lenta do que com três etapas do método de Newton. ${\ displaystyle 1+ \ varphi \ approx 2.6}$${\ displaystyle \ varphi}$

Encontrando uma raiz

O método mais amplamente usado para calcular uma raiz é o método de Newton , que consiste nas iterações do cálculo de

${\ displaystyle x_ {n + 1} = x_ {n} - {\ frac {f (x_ {n})} {f '(x_ {n})}},}$

começando com um valor bem escolhido ${\ displaystyle x_ {0}.}$

Se f for um polinômio, o cálculo é mais rápido quando se usa o método de Horner ou avaliação com pré-processamento para calcular o polinômio e sua derivada a cada iteração.

A convergência é geralmente quadrática , pode convergir muito lentamente ou até mesmo não convergir. Em particular, se o polinômio não tem raiz real e é real, o método de Newton não pode convergir. No entanto, se o polinômio tem uma raiz real, que é maior do que a raiz real maior de sua derivada, o método de Newton converge quadraticamente para esta raiz maior se for maior que esta raiz maior (há maneiras fáceis de calcular um limite superior do raízes, consulte Propriedades das raízes polinomiais ). Este é o ponto de partida do método de Horner para calcular as raízes. ${\ displaystyle x_ {0}}$${\ displaystyle x_ {0}}$

Quando uma raiz r foi encontrada, pode-se usar a divisão euclidiana para remover o fator x - r do polinômio. Calcular uma raiz do quociente resultante e repetir o processo fornece, em princípio, uma maneira de calcular todas as raízes. No entanto, esse esquema iterativo é numericamente instável; os erros de aproximação se acumulam durante as fatorações sucessivas, de modo que as últimas raízes são determinadas com um polinômio que se desvia amplamente de um fator do polinômio original. Para reduzir este erro, pode-se, para cada raiz encontrada, reiniciar o método de Newton com o polinômio original, e esta raiz aproximada como valor inicial.

No entanto, não há garantia de que isso permitirá encontrar todas as raízes. Na verdade, o problema de encontrar as raízes de um polinômio a partir de seus coeficientes é, em geral, altamente mal condicionado . Isso é ilustrado pelo polinômio de Wilkinson : as raízes desse polinômio de grau 20 são os 20 primeiros inteiros positivos; alterar o último bit da representação de 32 bits de um de seus coeficientes (igual a –210) produz um polinômio com apenas 10 raízes reais e 10 raízes complexas com partes imaginárias maiores que 0,6.

Intimamente relacionado com o método de Newton são o método de Halley e o método de Laguerre . Ambos usam o polinômio e suas duas primeiras derivações para um processo iterativo que tem uma convergência cúbica . Combinando duas etapas consecutivas desses métodos em um único teste, obtém-se uma taxa de convergência de 9, ao custo de 6 avaliações polinomiais (com a regra de Horner). Por outro lado, a combinação de três etapas do método de Newtons dá uma taxa de convergência de 8 ao custo do mesmo número de avaliação polinomial. Isso dá uma pequena vantagem a esses métodos (menos claro para o método de Laguerre, pois uma raiz quadrada deve ser calculada em cada etapa).

Ao aplicar esses métodos a polinômios com coeficientes reais e pontos de partida reais, os métodos de Newton e Halley permanecem dentro da reta numérica real. É preciso escolher pontos de partida complexos para encontrar raízes complexas. Em contraste, o método de Laguerre com raiz quadrada em sua avaliação deixará o eixo real por conta própria.

Encontrando raízes em pares

Se o polinômio dado tiver apenas coeficientes reais, pode-se desejar evitar cálculos com números complexos. Para tanto, deve-se encontrar fatores quadráticos para pares de raízes complexas conjugadas. A aplicação do método multidimensional de Newton a esta tarefa resulta no método de Bairstow .

A verdadeira variante do algoritmo Jenkins-Traub é uma melhoria desse método.

Encontrando todas as raízes de uma vez

O método Durand-Kerner simples e o método Aberth um pouco mais complicado encontram simultaneamente todas as raízes usando apenas a aritmética de números complexos simples . Algoritmos acelerados para avaliação e interpolação multiponto semelhantes à transformada rápida de Fourier podem ajudar a acelerá-los para grandes graus do polinômio. É aconselhável escolher um conjunto de pontos iniciais assimétricos, mas uniformemente distribuídos. A implementação deste método no software livre MPSolve é uma referência pela sua eficiência e precisão.

Outro método com este estilo é o método Dandelin – Gräffe (às vezes também atribuído a Lobachevsky ), que usa transformações polinomiais para retificar repetidamente e implicitamente as raízes. Isso aumenta muito as variações nas raízes. Aplicando as fórmulas de Viète , obtém-se aproximações fáceis para o módulo das raízes e, com um pouco mais de esforço, para as próprias raízes.

Métodos de exclusão e confinamento

Existem vários testes rápidos que indicam se um segmento da linha real ou uma região do plano complexo não contém raízes. Limitando o módulo das raízes e subdividindo recursivamente a região inicial indicada por esses limites, pode-se isolar pequenas regiões que podem conter raízes e então aplicar outros métodos para localizá-las exatamente.

Todos esses métodos envolvem encontrar os coeficientes de versões deslocadas e escalonadas do polinômio. Para graus grandes, os métodos acelerados baseados em FFT tornam-se viáveis.

Para raízes reais, consulte as próximas seções.

O algoritmo Lehmer – Schur usa o teste de Schur – Cohn para círculos; uma variante, o algoritmo de bissecção global de Wilf usa um cálculo de número de enrolamento para regiões retangulares no plano complexo.

O método do círculo de divisão usa transformações polinomiais baseadas em FFT para encontrar fatores de grande grau correspondentes a grupos de raízes. A precisão da fatoração é maximizada usando uma iteração do tipo Newton. Este método é útil para encontrar as raízes de polinômios de alto grau com precisão arbitrária; tem uma complexidade quase ideal nesta configuração.

Isolamento de raiz real

Encontrar as raízes reais de um polinômio com coeficientes reais é um problema que tem recebido muita atenção desde o início do século 19, e ainda é um domínio ativo de pesquisa. A maioria dos algoritmos de localização de raízes pode encontrar algumas raízes reais, mas não pode certificar que encontrou todas as raízes. Métodos para localizar todas as raízes complexas, como o método de Aberth, podem fornecer as raízes reais. No entanto, devido à instabilidade numérica dos polinômios (consulte o polinômio de Wilkinson ), eles podem precisar de aritmética de precisão arbitrária para decidir quais raízes são reais. Além disso, eles calculam todas as raízes complexas quando apenas algumas são reais.

Segue-se que a maneira padrão de calcular raízes reais é calcular os primeiros intervalos disjuntos, chamados de intervalos de isolamento , de modo que cada um contenha exatamente uma raiz real e, juntos, eles contenham todas as raízes. Esse cálculo é chamado de isolamento de raiz real . Tendo intervalo de isolamento, pode-se usar métodos numéricos rápidos, como o método de Newton para melhorar a precisão do resultado.

O algoritmo completo mais antigo para o isolamento da raiz real resulta do teorema de Sturm . No entanto, parece ser muito menos eficiente do que os métodos baseados na regra dos signos de Descartes e no teorema de Vincent . Esses métodos se dividem em duas classes principais, uma usando frações contínuas e a outra usando bissecção. Ambos os métodos foram melhorados drasticamente desde o início do século XXI. Com essas melhorias, eles alcançam uma complexidade computacional semelhante à dos melhores algoritmos para calcular todas as raízes (mesmo quando todas as raízes são reais).

Esses algoritmos foram implementados e estão disponíveis no Mathematica (método da fração contínua) e no Maple (método da bissecção). Ambas as implementações podem encontrar rotineiramente as raízes reais de polinômios de grau superior a 1.000.

Encontrar várias raízes de polinômios

A maioria dos algoritmos de localização de raízes se comporta mal quando há raízes múltiplas ou raízes muito próximas. No entanto, para polinômios cujos coeficientes são dados exatamente como inteiros ou números racionais , existe um método eficiente para fatorá-los em fatores que têm apenas raízes simples e cujos coeficientes também são dados exatamente. Este método, denominado fatoração livre de quadrados , é baseado nas raízes múltiplas de um polinômio sendo as raízes do maior divisor comum do polinômio e sua derivada.

A fatoração livre de quadrados de um polinômio p é uma fatoração em que cada um é 1 ou um polinômio sem raízes múltiplas, e dois diferentes não têm nenhuma raiz comum. ${\ displaystyle p = p_ {1} p_ {2} ^ {2} \ cdots p_ {k} ^ {k}}$${\ displaystyle p_ {i}}$${\ displaystyle p_ {i}}$

Um método eficiente para calcular essa fatoração é o algoritmo de Yun .

Veja também

• Lista de algoritmos de localização de raiz
• Método de Broyden  - Método de localização de raiz quase Newton para o caso multivariável
• Gerador de números pseudo-aleatórios criptograficamente seguro
• Biblioteca Científica GNU
• Método de Graeffe  - Algoritmo para encontrar raízes polinomiais
• Método de Lill  - Método gráfico para as raízes reais de um polinômio
• MPSolve  - Software para aproximar as raízes de um polinômio com alta precisão arbitrária
• Multiplicidade (matemática)  - Número de vezes que um objeto deve ser contado para tornar verdadeira uma fórmula geral
• n º algoritmo de raiz
• Sistema de equações polinomiais  - algoritmos de localização de raízes para raízes comuns de vários polinômios multivariados
• Teorema de Kantorovich  - Condições iniciais que garantem a convergência do método de Newton

Referências