Solution la plus rapide numérique d'un polynôme réel cube?

Question

R question: Vous recherchez le meilleur moyen de résoudre numériquement un tas de cubics arbitraires connus pour avoir de véritables coeffs et trois racines réelles. La fonction POLYROOT en R est rapporté à utiliser l'algorithme de Jenkins-Traub 419 pour les polynômes complexes, mais pour les vrais polynômes, les auteurs renvoient à leur travail plus tôt. Quelles sont les plus rapides des options pour un vrai cube, ou plus généralement pour un polynôme réel?

Answer 1

Concrétiser la réponse de Arietta ci-dessus:

> a <- c(1,3,-4)
> m <- matrix(c(0,0,-a[1],1,0,-a[2],0,1,-a[3]), byrow=T, nrow=3)
> roots <- eigen(m, symm=F, only.values=T)$values

Que ce soit plus rapide ou plus lent que d'utiliser le solveur cube dans le paquet GSL (comme suggéré par knguyen ci-dessus) est une question de l'analyse comparative sur votre système.

Answer 2

La solution numérique pour faire cela plusieurs fois de manière fiable, stable, impliquent: (1) former la matrice d'accompagnement, (2) trouver les valeurs propres de la matrice compagnon

.

Vous pouvez penser que cela est un problème plus difficile à résoudre que l'original, mais c'est comment est mis en œuvre la solution dans la plupart du code de production (par exemple, Matlab).

Pour le polynôme:

p(t) = c0 + c1 * t + c2 * t^2 + t^3

la matrice compagnon est:

[[0 0 -c0],[1 0 -c1],[0 1 -c2]]

Trouver les valeurs propres de cette matrice; ils correspondent aux racines du polynôme d'origine.

Pour faire cela très vite, télécharger les sous-routines de valeurs singulières de LAPACK, les compiler et de les relier à votre code. Pour ce faire, en parallèle si vous avez trop grand nombre (environ un million) ensembles de coefficients.

Notez que le coefficient de t^3 est l'un, si ce n'est pas le cas dans votre polynômes, vous devez diviser le tout par le coefficient, puis procéder.

Bonne chance.

Edit: Numpy et octave dépendent également de cette méthode de calcul des racines de polynômes. Voir, par exemple, ce lien .

Answer 3

La façon la plus rapide connue (que je connais) pour trouver les solutions réelles d'un système de polynômes arbitraires dans n variables est polyédrique homotopie. Une explication détaillée est probablement au-delà d'une réponse StackOverflow, mais essentiellement, il est un algorithme de chemin qui exploite la structure de chaque équation à l'aide des géométries Toric. Google vous donnera un certain nombre de documents .

Peut-être que cette question est mieux adapté pour mathoverflow ?

Answer 4

Avez-vous besoin tous les 3 racines ou un seul? Si un seul, je pense que la méthode de Newton fonctionnerait bien. Si tous les trois alors il pourrait être problématique dans des circonstances où deux sont proches.

Answer 5

1) Résoudre pour le polynôme dérivé P » pour localiser vos trois racines. Voir il pour savoir comment le faire correctement. Appelez les racines a et b (avec

2) Pour la racine du milieu, utilisez quelques pas de bijection entre a et b, et quand vous êtes assez proche, en finir avec la méthode de Newton.

3) Pour la racine min et max, "chasser" la solution. Pour la racine max:

• Commencez par x0 = b, x1 = b + (b - a) * lambda, où lambda est un nombre modéré (par exemple 1,6)
• faire x_n = b + (x_ {n - 1} - a) * lambda jusqu'à P (x_n) et P (b) ont des signes différents
• Effectuer bissectrice + newton entre x_ {n - 1} et x_n

Answer 6

Les méthodes communes sont disponibles. Méthode de Newton, Méthode Bisection, Sécante, itération de point fixe, etc. Google un d'entre eux

Si vous avez un non-linéaire système d'autre part (par exemple un système sur de N polynôme de EQN inconnues N), une méthode telle que haute pour Newton peut être utilisé.

Answer 7

Avez-vous essayé de regarder dans le paquet GSL http: // Cran .R-project.org / web / packages / GSL / index.html ?