Resolution de polynôme de degrès n (cad de n'importe quel degrès)

Soyez le premier à donner votre avis sur cette source.

Vue 24 959 fois - Téléchargée 1 129 fois

Télécharger le projet
Commenter

Description

Voici une source assez sympa qui permet de trouver les racines réelles d'un polynôme de degrès n ( cad de n'importe quel degrès :D ) Donc en gros ce petit algo ( à peine 30 lignes de code pour la fonction ResolvePoly() ) permet très simplement de résoudre ce genre d'équation ::

Polynôme de degrès 15 ::

7X^15-8X^14-6X^13+4X^12-4X^11-6X^10+2X^9+X^8+7X^7+2X^6-2X^5-2X^4-9X^3+9X^2+5X-2 = 0

5 racines dans l'intervalle [ -2,2 ]

Racine N°1 :: -0,978867466913167
Racine N°2 :: -0,603002164541593
Racine N°3 :: 0,293669976482321
Racine N°4 :: 0,968125129970291
Racine N°5 :: 1,63964850956609

La convergence est assez rapide et la précision dépend de la variable Epsilon qui est modifiable, par défaut Epsilon = 10 ^ -10

La méthode est simple, on décompose la courbe en segments de droite, puis on verifi pour chaque segment si il y'a intersection avec la droite Y=0, si oui, on coupe en 2 le segment de droite et on réitère l'opération, jusqu'a ce que la longueur en abscisse du segment soit <=Epsilon.

La source est commentée
Dans le zip se trouve également une feuille permettant de paramétrer très facilement le polynôme, de tracer la courbe, et d'afficher les racines sur le graphe
=> voir la capture d'écran

Ci dessous le code de la procédure ResolvePoly()

Source / Exemple : 


'* -------------------------------------------------------------
'| La procédure magique :D
'|
'|Cette procédure permet de résoudre le polynôme
'|F = 0 de n'importe quel degrès tel que ::
'|          i
'| F = S[ Coef(i) * X ^ i ] = 0
'|         0
'|i = nombre de coefficents , S[] représente la somme
'|
'|Coef()      est le tableau regroupant tous les coefficient du
'|polynôme, Coef(0) est la constante
'|mini         est la borne inférieur de l'intervalle de la recherche
'|maxi        est la borne supérieur de l'intervalle de la recherche
'|Resultat() est le tableau regroupant toutes les racines
'|
'| [ X(0),Y(0) ] - [ X(1),Y(1) ] représente un bout de segment (D)
'|de la courbe (C)
'|Pas       est la taille de l'intervalle de recherche divisé par 1000
'|dPas     est un intervalle de recherche de plus en plus petit
'|Epsilon  est la longueur minimale de l'intervalle de recherche, c'est donc la précision de l'approximation

Dim X(1), Y(1), Pas, dPas, Epsilon, I, min, max As Double
Dim K, J As Byte

ReDim Resultat(0)

min = mini
max = maxi
'|On définit Epsilon, la précision est donc de 0.00000000001
Epsilon = 10 ^ -10
'|On calcule le Pas de la recherche
Pas = (max - min) / 1000

Debut:
'|On place le point gauche du segment D sur la borne minimale de recherche
'|(Attention min<>mini, sauf au début)
X(1) = min
'|On définit Y(1) = F(X(1))
For J = 0 To UBound(Coef): Y(1) = Y(1) + Coef(J) * X(1) ^ J: Next
'|On scan la courbe sur l'intervalle
For I = min To max Step Pas
'|On définit dPas comme la moitié de Pas, on a ainsi 2 segment
dPas = Pas / 2
    For K = 1 To 2
        '|On positionne les points du segment D
        X(0) = X(1)
        X(1) = X(0) + K * dPas
        Y(0) = Y(1): Y(1) = 0
        '|On calcule la position Y du polynôme au point X(1)
        For J = 0 To UBound(Coef): Y(1) = Y(1) + Coef(J) * X(1) ^ J: Next
        '|On calcule l'interserction entre la droite passant par le
        '|segment D et la droite Y=0
        Resultat(n) = IIf((Y(1) / Y(0) - 1) <> 0, X(0) - (X(1) - X(0)) / (Y(1) / Y(0) - 1), mini - 1)
        '|Si l'intersection se situe dans la zone de recherche dPas
        '|( en effet X(1)-X(0) = dPas )
        If Resultat(n) >= X(0) And Resultat(n) <= X(1) Then
            '|Si dPas a atteint la valeur minimale de l'intervalle, cad
            '| si la valeur de Résultat(n) est proche à Epsilon près
            If dPas <= Epsilon Then
                '|Le nouveau minimum de recherche se situe à
                '|la nouvelle racine trouvée
                min = Resultat(n)
                '|On agrandit le tableau de recherche de racine
                n = n + 1
                ReDim Preserve Resultat(n)
                '|On retourne au début et on refait un scan
                '|mais dans l'intervalle [ Resultat(n),max ]
                GoTo Debut
            Else
                '|dPas n'est pas assez précis, donc on le divise par 2 et
                '|on recommence car on sait qu'il y'a une racine dans le coin
                dPas = dPas / 2
                X(1) = X(0): Y(1) = Y(0)
                K = 1
            End If
        End If
    Next
Next
End Sub
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Signaler
Cyberdevil
Messages postés
483
Date d'inscription
mardi 10 juillet 2001
Statut
Membre
Dernière intervention
12 juillet 2006
 -
sympa mais la méthode de Newton est surement beaucoup plus rapide ! Il suffit justre de dévlopper un alog pour faire les dérivée après ça converge encore plus vite que ta fonction !
8/10
Signaler
cs_Geff
Messages postés
192
Date d'inscription
vendredi 2 mars 2001
Statut
Membre
Dernière intervention
10 janvier 2006
 -
Tout a fait, Newton converge bien plus vite en théorie (il faut quand meme effectuer un scan de la fonction dans l'intervalle de recherche) D'ailleurs je vais poster d'ici quelques temps la Fonction ResolvePolyNewton() :D
Je pense que cette facon de trouver les racines vaut le coup d'etre vu, si j'ai le temps je ferais un benchmark entre les 2 fonctions!
Signaler
Cyberdevil
Messages postés
483
Date d'inscription
mardi 10 juillet 2001
Statut
Membre
Dernière intervention
12 juillet 2006
 -
J'attend de voir ça ;)

A+
Signaler
elmeiche
Messages postés
2
Date d'inscription
jeudi 26 décembre 2002
Statut
Membre
Dernière intervention
1 juin 2004
 -
salut

c'est un grand travail , mais si tu ésaye de calculer les racinnes avec la méthode de NewtonRavsonne c'est encore mieux.

faite une aperçu à mon source "RÉSOLUTION D'ÉQUATION DE 3 ÉME DEGRÉ AVEC LA MÉTHODE DE NEWTON"

c'est un trés bon travail

elmeiche.noury@caramail.com

je vous remercier monsieur.
Signaler
cs_Geff
Messages postés
192
Date d'inscription
vendredi 2 mars 2001
Statut
Membre
Dernière intervention
10 janvier 2006
 -
Merci elmeiche, comme je l'ai dis la fonction Resolvepoly est prête masi je ne l'ai pas encore commentée/postée par manque de temps mais ca ne tardera pas, en plus Resolvepoly est beaucoup plus courte et plus rapide!
Afficher les 6 commentaires
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_Geff)