Trouvez la solution de l'équation d'ordre n avec python

équation d'ordre n

x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 =0

Je suis tombé sur une situation que je voulais résoudre. Je pense que cela s'appelle généralement l'équation d'ordre n. (Est-ce aussi appelé une équation algébrique à une variable?) On sait qu'il n'y a pas de solution algébrique pour ceux de degré 5 et plus. Cependant, il semble que le 5ème ordre puisse être exprimé en utilisant diverses fonctions spéciales, et la solution approximative peut être calculée numériquement. Il semble qu'il soit normal d'utiliser le calcul numérique pour le 4ème ordre et plus. Il semble que Matlab a une fonction appelée roots qui effectue des calculs numériques d'équations algébriques, mais je n'ai pas trouvé de bibliothèque en python. C'est pourquoi j'ai décidé de le mettre en œuvre.

algorithme

Lorsqu'il s'agit de trouver une solution, la méthode de Newton semble être la première, mais il semble que la méthode DKA soit connue comme un algorithme similaire à la méthode de Newton pour trouver la solution d'une équation d'ordre n. Cependant, l'implémentation de cet algorithme est fastidieuse, et si vous regardez Matlab Implementation, vous pouvez utiliser une méthode qui aboutit à un calcul de valeur propre. Il semble y avoir. J'ai décidé de l'utiliser cette fois. Lors du calcul des valeurs propres selon la définition

 \mathrm{det}(sI-A)=0

Cependant, il s'agit d'une équation d'ordre n lorsque la matrice est d'ordre n. Il semble y avoir différentes méthodes pour calculer les valeurs propres, et numpy a également une fonction appelée np.linalg.eig. Par conséquent, il est seulement nécessaire de connaître une matrice qui a l'équation pour laquelle la solution doit être obtenue en tant que polynie propre, mais ce qui suit est appelé matrice compagnon.

A=
\left(
    \begin{array}{ccccc}
      0 & 1 & 0&\ldots&0  \\
      \vdots & \ddots & 1&\ddots&\vdots \\
      \vdots & \ldots & \ddots&\ddots&0\\
      0&\ldots&\ldots&0&1\\
-a_0&-a_1&\ldots&-a_{n-2}&-a_{n-1}
    \end{array}
  \right)

L'équation propre de ceci est

|sI-A| = s^n+a_{n-1}s^{n-1}+a_{n-2}s^{n-2}+\ldots+a_1s+a_0

Sera. Par conséquent, si toutes les valeurs propres de la matrice compagnon ci-dessus sont calculées pour l'équation d'ordre n avec un coefficient arbitraire, une solution peut être obtenue. Veuillez vous reporter à ici pour la méthode DKA introduite en premier. Mise en œuvre était également en panne.

la mise en oeuvre

n-poly.py

import numpy as np
def solve(vec,is_complex=False):
    dim =len(vec)
    if is_complex:
        A = np.zeros((dim,dim),dtype=complex)
    else:
        A = np.zeros((dim,dim))
    A[np.arange(dim-1),1+np.arange(dim-1)] =1
    A[-1,:] = -vec
    ans,vec = np.linalg.eig(A)
    return ans

vec0 =np.array([-120,274,-225,85,-15])
vec1 =np.array([1,0])
vec2 =np.array([-1,5,-10,10,-5])
print(solve(vec0))
print(solve(vec1))
print(solve(vec2))

[ 5.  4.  3.  2.  1.]
[ 0.+1.j  0.-1.j]
[ 1.00079742+0.00057977j  1.00079742-0.00057977j  0.99969502+0.00093688j
  0.99969502-0.00093688j  0.99901512+0.j        ]

Notez que si le coefficient contient un nombre imaginaire, le coefficient sera converti en un nombre réel sans définir is_complex sur True. Si dtype = complex est toujours défini, il semble que la valeur propre réelle soit difficile à calculer en tant que valeur propre réelle, elle est donc généralement calculée par float (l'algorithme est-il différent selon le dtype?)

Chaque exemple

(x-1)(x-2)(x-3)(x-4)(x-5)=x^5-15x^4+85x^3-225x^2+274x-120=0\\
x^2+1=(x-i)(x+i)=0\\
(x-1)^5=0

Est en cours de calcul. On peut voir que même les équations du cinquième ordre sans formule de solution sont calculées avec une précision raisonnable en incluant des solutions multiples.

Les références

Preuve de la relation entre la matrice compagnon et le polyma caractéristique