Tous les êtres humains aspirent par nature à la connaissance. (Aristote. Métaphysique)

Méthodes numériques : résolution d'équations non linéaires

Des problèmes de résolution d'équations se posent constamment dans la pratique, par exemple, en économie, lors du développement d'une entreprise, on veut savoir quand les bénéfices atteindront une certaine valeur, en médecine, lors de l'étude des effets des médicaments, il est important de savoir quand la concentration d'une substance atteindra un niveau donné, etc.

Dans les problèmes d'optimisation, il est souvent nécessaire de déterminer les points auxquels la dérivée d'une fonction devient 0, ce qui est une condition nécessaire locale extrême.

En statistiques, lors de la construction d’estimations à l’aide de la méthode des moindres carrés ou du maximum de vraisemblance, vous devez également résoudre des équations non linéaires et des systèmes d’équations.

Ainsi, toute une classe de problèmes se pose liés à la recherche de solutions non linéaire des équations, telles que des équations ou des équations, etc.

Dans le cas le plus simple, on a une fonction définie sur l'intervalle ( un, b ) et en prenant certaines valeurs.

Chaque valeur X à partir de ce segment, nous pouvons comparer le nombre, c'est fonctionnel la dépendance, un concept clé en mathématiques.

Nous devons trouver une valeur à laquelle celles-ci sont appelées racines de la fonction

Visuellement, nous devons déterminer le point d'intersection du graphique de fonctionavec l'axe des abscisses.

Méthode de réduction de moitié

La méthode la plus simple pour trouver les racines d’une équation est la méthode de réduction de moitié, ou dichotomie.

Cette méthode est intuitive et tout le monde agirait de la même manière lors de la résolution d’un problème.

L'algorithme est le suivant.

Supposons que nous trouvons deux points et , tels qu'ils ont différent signes, alors entre ces points il y a au moins une racine de la fonction.

Divisons le segment en deux et entrons moyenne indiquer .

Alors soit , ou .

Laissons cette moitié du segment pour laquelle les valeurs aux extrémités sont différents signes. Maintenant, nous divisons à nouveau ce segment en deux et laissons la partie aux limites de laquelle la fonction a des signes différents, et ainsi de suite, pour obtenir la précision requise.

Évidemment, nous rétrécirons progressivement la zone où se trouve la racine de la fonction et, par conséquent, nous la déterminerons avec un certain degré de précision.

Notez que l’algorithme décrit est applicable à toute fonction continue.

Les avantages de la méthode de réduction de moitié incluent sa grande fiabilité et sa simplicité.

L'inconvénient de la méthode est le fait qu'avant de commencer à l'utiliser, vous devez trouver deux points où les valeurs de la fonction ont des signes différents. Il est évident que la méthode n’est pas applicable aux racines de multiplicité paire et ne peut pas non plus être généralisée au cas de racines complexes et aux systèmes d’équations.

L'ordre de convergence de la méthode est linéaire, à chaque étape la précision double ; plus on fait d'itérations, plus la racine est déterminée avec précision.

Méthode de Newton : fondements théoriques

La méthode classique de Newton ou tangentes est-ce que si c'est une approximation de la racine de l'équation , alors l'approximation suivante est définie comme la racine de la tangente à la fonction tracée au point .

L'équation tangente à une fonction en un point a la forme :

Dans l’équation tangente, nous mettons et .

Ensuite, l’algorithme pour les calculs séquentiels dans la méthode de Newton est le suivant :

La convergence de la méthode tangente est quadratique, l'ordre de convergence est 2.

Ainsi, la convergence de la méthode tangente de Newton est très rapide.

Souvenez-vous de ce fait merveilleux !

Sans aucune modification, la méthode est généralisée au cas complexe.

Si la racine est une racine de seconde multiplicité ou supérieure, alors l'ordre de convergence diminue et devient linéaire.

Exercice 1. En utilisant la méthode de la tangente, trouvez une solution à l'équation sur le segment (0, 2).

Exercice 2. En utilisant la méthode de la tangente, trouvez une solution à l'équation sur le segment (1, 3).

Les inconvénients de la méthode de Newton incluent sa localité, car elle est garantie de converger pour une approximation de départ arbitraire uniquement si la condition est satisfaite partout , dans la situation inverse, la convergence ne se produit que dans un certain voisinage de la racine.

L'inconvénient de la méthode de Newton est la nécessité de calculer les dérivées à chaque étape.

Visualisation de la méthode de Newton

La méthode de Newton (méthode de la tangente) est utilisée si l'équation F(X) = 0 a une racine et les conditions suivantes sont remplies :

1) fonction oui= F(X) défini et continu à ;

2) F(un)· F(b) < 0 (la fonction prend des valeurs de signes différents aux extrémités du segment [ un; b]);

3) dérivés F"(X) Et F""(X) conserver le signe sur l'intervalle [ un; b] (c'est-à-dire la fonction F(X) soit augmente ou diminue sur le segment [ un; b], tout en conservant la direction de la convexité) ;

L'idée principale de la méthode est la suivante : sur le segment [ un; b] un tel numéro est sélectionné X 0 , auquel F(X 0 ) a le même signe que F"" (X 0 ), c'est-à-dire que la condition est satisfaite F(X 0 )· F"" (X) > 0 . Ainsi, le point en abscisse est sélectionné X 0 , dans lequel la tangente à la courbe oui= F(X) sur le segment [ un; b] coupe l'axe Bœuf. Par point X 0 Tout d'abord, il est pratique de sélectionner l'une des extrémités du segment.

Considérons la méthode de Newton à l'aide d'un exemple spécifique.

Donnons-nous une fonction croissante y = f(x) =x 2 -2, continue sur le segment (0;2), et ayant F"(x) = 2 X > 0 Et F "" (x) = 2 > 0 .

Dessin1 . f(x) =x 2 -2

Équation tangente dans vue générale a une idée :

y-y 0 = f" (x 0) · (x-x 0).

Dans notre cas: y-y 0 =2x 0 ·(x-x 0). Pour le point x 0 on choisit le point B 1 (b; f(b)) = (2,2). Tracer une tangente à la fonction y = f(x) au point B 1, et désignent le point d'intersection de la tangente et de l'axe Bœuf point x1. On obtient l'équation de la première tangente : y-2=2·2(x-2), y=4x-6.

Buffle : x 1 =

Dessin2. Résultat de la première itération

y=f(x) Bœufà travers le point x1, nous comprenons le point B2 =(1,5 ; 0,25). Dessinez à nouveau une tangente à la fonction y = f(x) au point B 2, et désignent le point d'intersection de la tangente et de l'axe Bœuf point x2.

Équation de la deuxième tangente : oui-0.25=2*1.5(X-1.5), oui = 3 X - 4.25.

Point d'intersection de la tangente et de l'axe Buffle : x 2 =.

Dessin3. Deuxième itération de la méthode de Newton

On trouve ensuite le point d'intersection de la fonction y=f(x) et une perpendiculaire tracée à l'axe Bœuf par le point x 2, on obtient le point B 3 et ainsi de suite.

Dessin4. Troisième étape de la méthode tangente

La première approximation de la racine est déterminée par la formule :

= 1.5.

La deuxième approximation de la racine est déterminée par la formule :

=

La troisième approximation de la racine est déterminée par la formule :

Ainsi , je La ième approximation de la racine est déterminée par la formule :

Les calculs sont effectués jusqu'à ce que les décimales nécessaires dans la réponse correspondent ou que la précision spécifiée e soit atteinte - jusqu'à ce que l'inégalité soit satisfaite. | xi- xi-1 | < e.

Dans notre cas, comparons l’approximation obtenue à la troisième étape avec la réponse réelle calculée sur une calculatrice :

Figure 5. Racine de 2, calculée sur une calculatrice

Comme vous pouvez le constater, dès la troisième étape, nous avons reçu une erreur inférieure à 0,000002.

De cette façon, vous pouvez calculer la valeur de la « racine carrée de 2 » avec n’importe quel degré de précision. Cette méthode remarquable a été inventée par Newton et permet de retrouver des racines très équations complexes.

Méthode de Newton : application en C++

Dans cet article, nous allons automatiser le processus de calcul des racines des équations en écrivant une application console en C++. Nous le développerons dans Visual C++ 2010 Express, il s'agit d'un environnement de développement C++ gratuit et très pratique.

Commençons par lancer Visual C++ 2010 Express. La fenêtre de démarrage du programme apparaîtra. Dans le coin gauche, cliquez sur « Créer un projet ».

Riz. 1. Page d'accueil de Visual C++ 2010 Express

Dans le menu qui apparaît, sélectionnez « Application console Win32 » et entrez le nom de l'application « Newton_Method ».

Riz. 2. Créez un projet

// Méthode Newton.cpp : définit le point d'entrée de l'application console #include "stdafx.h" #inclure en utilisant l'espace de noms std ; float f(double x) //renvoie la valeur de la fonction f(x) = x^2-2 float df(float x) //renvoie la valeur dérivée float d2f(float x) // valeur de la dérivée seconde int _tmain(int argc, _TCHAR* argv) int exit = 0, i=0;//variables pour la sortie et la boucle double x0,xn;//approximations calculées pour la racine double a, b, eps ; // limites du segment et précision requise cout<<"Please input \n=>"; cin>>a>>b; // entrez les limites du segment sur lequel on va chercher la racine cout<<"\nPlease input epsilon\n=>"; cin>>eps; // entrez la précision de calcul requise if (a > b) // si l'utilisateur a mélangé les limites du segment, échangez-les if (f(a)*f(b)>0) // si les signes de la fonction aux bords du segment sont les mêmes, alors il n'y a pas de racine ici cout<<"\nError! No roots in this interval\n"; si (f(a)*d2f(a)>0) x0 = a; // pour sélectionner le point de départ, vérifiez f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // considère la première approximation cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // continuera à calculer jusqu'à ce que nous atteignions la précision requise xn = x0-f(x0)/df(x0); // directement la formule de Newton cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; ) while (sortie!=1); // jusqu'à ce que l'utilisateur entre exit = 1

Voyons voir comment ça fonctionne. Cliquez sur le triangle vert dans le coin supérieur gauche de l'écran ou appuyez sur F5.

Si une erreur de compilation se produit « Erreur LNK1123 : échec de conversion en COFF : le fichier est invalide ou endommagé », alors cela peut être corrigé soit en installant le premier Service pack 1, soit dans les paramètres du projet Propriétés -> Linker désactivant la liaison incrémentielle.

Riz. 4. Résoudre l'erreur de compilation du projet

Nous chercherons les racines de la fonction F(x) =x2-2.

Tout d'abord, vérifions les performances de l'application sur les « mauvaises » données d'entrée. Il n'y a pas de racines sur le segment, notre programme devrait afficher un message d'erreur.

Nous avons maintenant une fenêtre d'application :

Riz. 5. Saisie des données d'entrée

Introduisons les limites des segments 3 et 5, et la précision est de 0,05. Comme prévu, le programme a généré un message d'erreur indiquant qu'il n'y avait pas de racine sur ce segment.

Riz. 6. Erreur « Il n'y a pas de racines sur ce segment ! »

Nous n’allons pas encore partir, alors qu’en est-il du message « Sortie ? » entrez « 0 ».

Vérifions maintenant l'application en utilisant les données d'entrée correctes. Entrons le segment et la précision 0,0001.

Riz. 7. Calcul de la racine avec la précision requise

Comme nous pouvons le constater, la précision requise a été atteinte dès la 4ème itération.

Pour quitter l'application, saisissez « Quitter ? » => 1.

Méthode sécante

Pour éviter de calculer la dérivée, la méthode de Newton peut être simplifiée en remplaçant la dérivée par une approximation calculée à partir des deux points précédents :

Le processus itératif ressemble à :

Il s’agit d’un processus itératif en deux étapes car il utilise les deux précédentes pour trouver l’approximation suivante.

L'ordre de convergence de la méthode sécante est inférieur à celui de la méthode tangente et est égal dans le cas d'une racine unique.

Cette quantité remarquable est appelée le nombre d’or :

Vérifions cela, en supposant par commodité que .

Ainsi, jusqu’aux infinitésimaux d’ordre supérieur

En écartant le terme restant, on obtient une relation de récurrence dont la solution est naturellement recherchée sous la forme .

Après substitution on a : et

Pour la convergence, il faut qu'elle soit positive, donc .

Puisque la connaissance de la dérivée n'est pas requise, avec le même nombre de calculs dans la méthode sécante (malgré l'ordre de convergence inférieur), on peut obtenir une plus grande précision que dans la méthode tangente.

Notez qu'à proximité de la racine, vous devez diviser par un petit nombre, ce qui entraîne une perte de précision (surtout dans le cas de racines multiples), donc, après avoir choisi un nombre relativement petit, effectuez des calculs avant d'effectuer et continuez-les jusqu'à ce que le module de la différence entre approximations voisines diminue.

Dès que la croissance commence, les calculs sont arrêtés et la dernière itération n'est pas utilisée.

Cette procédure permettant de déterminer la fin des itérations est appelée la technique Garvika.

Méthode parabole

Considérons une méthode en trois étapes dans laquelle l'approximation est déterminée par les trois points précédents , et .

Pour ce faire, on remplace, à l'instar de la méthode sécante, la fonction par une parabole d'interpolation passant par les points , et .

Sous la forme de Newton, cela ressemble à :

Un point est défini comme celle des racines de ce polynôme la plus proche en valeur absolue du point.

L'ordre de convergence de la méthode parabolique est supérieur à celui de la méthode sécante, mais inférieur à celui de la méthode de Newton.

Une différence importante par rapport aux méthodes considérées précédemment est le fait que même si réel pour réel et que les approximations de départ sont choisies comme étant réelles, la méthode parabolique peut conduire à une racine complexe du problème d'origine.

Cette méthode est très pratique pour trouver les racines de polynômes de haut degré.

Méthode d'itération simple

Le problème de trouver des solutions à des équations peut être formulé comme un problème de recherche de racines : , ou comme un problème de recherche d'un point fixe.

Laisser et - compression : (en particulier, le fait que - compression, comme il est facile de le voir, signifie cela).

D'après le théorème de Banach, il existe un unique point fixe

On peut le trouver comme la limite d'une simple procédure itérative

où l'approximation initiale est un point arbitraire dans l'intervalle.

Si la fonction est différentiable, alors un critère de compression pratique est le nombre . En effet, d’après le théorème de Lagrange

Ainsi, si la dérivée est inférieure à un, alors il s’agit d’une compression.

Condition est essentiel, car si, par exemple, sur , alors il n'y a pas de point fixe, bien que la dérivée soit égale à zéro. La vitesse de convergence dépend de la valeur de . Plus la valeur est petite, plus la convergence est rapide.

Soit la racine de l'équation f(x)=0 séparée sur le segment , avec les dérivées première et seconde f'(x) et f""(x) sont continues et de signe constant pour xÎ.

Supposons qu'à une étape du raffinement de la racine, la prochaine approximation de la racine x n soit obtenue (sélectionnée) . Supposons alors que la prochaine approximation obtenue en utilisant la correction h n , conduit à la valeur exacte de la racine

x = xn + hn. (1.2.3-6)

Compte h n petite valeur, on représente f(х n + h n) sous la forme d'une série de Taylor, en se limitant aux termes linéaires

f(x n + h n) »f(x n) + h n f’(x n). (1.2.3-7)

En considérant que f(x) = f(x n + h n) = 0, on obtient f(x n) + h n f ’(x n) » 0.

D’où h n » - f(x n)/ f’(x n). Remplaçons la valeur h n dans (1.2.3-6) et à la place de la valeur exacte de la racine X nous obtenons une autre approximation

La formule (1.2.3-8) permet d'obtenir une séquence d'approximations x 1, x 2, x 3..., qui, sous certaines conditions, converge vers la valeur exacte de la racine X, c'est

Interprétation géométrique de la méthode de Newton est comme suit
(Fig.1.2.3-6). Prenons l'extrémité droite du segment b comme approximation initiale x 0 et construisons une tangente au point correspondant B 0 sur le graphique de la fonction y = f(x). Le point d'intersection de la tangente avec l'axe des x est considéré comme une nouvelle approximation plus précise x 1. Répéter cette procédure plusieurs fois permet d'obtenir une séquence d'approximations x 0, x 1, x 2 , . . ., qui tend vers la valeur exacte de la racine X.

La formule de calcul de la méthode de Newton (1.2.3-8) peut être obtenue à partir d'une construction géométrique. Donc dans un triangle rectangle x 0 B 0 x 1 jambe
x 0 x 1 = x 0 V 0 /tga. Considérant que le point B 0 est sur le graphique de la fonction f(x), et l'hypoténuse est formée par la tangente au graphe f(x) au point B 0, on obtient

(1.2.3-9)

(1.2.3-10)

Cette formule coïncide avec (1.2.3-8) pour la nième approximation.

D'après la Fig. 1.2.3-6, il est clair que le choix du point a comme approximation initiale peut conduire au fait que la prochaine approximation x 1 sera en dehors du segment sur lequel la racine est séparée X. Dans ce cas, la convergence du processus n’est pas garantie. Dans le cas général, le choix de l'approximation initiale se fait selon la règle suivante : l'approximation initiale doit être prise comme un point x 0 О, auquel f(x 0)×f''(x 0)>0 , c'est-à-dire que les signes de la fonction et de sa dérivée seconde correspondent.

Les conditions de convergence de la méthode de Newton sont formulées dans le théorème suivant.

Si la racine de l'équation est séparée sur le segment, et f'(x 0) et f''(x) sont différents de zéro et conservent leurs signes lorsque xО, alors si nous choisissons un point tel que l'approximation initiale x 0 О , Quoi f(x 0).f¢¢(x 0)>0 , alors la racine de l'équation f(x)=0 peut être calculé avec n’importe quel degré de précision.

L'estimation de l'erreur de la méthode de Newton est déterminée par l'expression suivante :

(1.2.3-11)

où est la plus petite valeur à

Valeur la plus élevée à

Le processus de calcul s'arrête si ,

où est la précision spécifiée.

De plus, les expressions suivantes peuvent servir de condition pour atteindre une précision donnée lors du raffinement de la racine à l'aide de la méthode de Newton :

Le diagramme de l'algorithme de la méthode de Newton est présenté sur la Fig. 1.2.3-7.

Le côté gauche de l’équation originale f(x) et sa dérivée f’(x) dans l’algorithme sont conçus comme des modules logiciels distincts.

Riz. 1.2.3-7. Diagramme de l'algorithme de la méthode Newton

Exemple 1.2.3-3. Affiner les racines de l'équation x-ln(x+2) = 0 par la méthode de Newton, à condition que les racines de cette équation soient séparées sur les segments x 1 О[-1.9;-1.1] et x 2 О [-0,9;2 ].

La dérivée première f’(x) = 1 – 1/(x+2) conserve son signe sur chacun des segments :

f'(x)<0 при хÎ [-1.9; -1.1],

f'(x)>0 à xО [-0,9; 2].

La dérivée seconde f"(x) = 1/(x+2) 2 > 0 pour tout x.

Les conditions de convergence sont donc satisfaites. Puisque f""(x)>0 sur toute la plage de valeurs admissibles, alors pour clarifier la racine de l'approximation initiale x1 choisissez x 0 = -1,9 (puisque f(-1,9)×f”(-1,9)>0). On obtient une séquence d’approximations :

En poursuivant les calculs, nous obtenons la séquence suivante des quatre premières approximations : -1,9 ; –1,8552, -1,8421 ; -1.8414 . La valeur de la fonction f(x) au point x=-1,8414 est égale à f(-1,8414)=-0,00003 .

Pour clarifier la racine x 2 О[-0.9;2] nous choisissons 0 =2 (f(2)×f”(2)>0) comme approximation initiale. Sur la base de x 0 = 2, nous obtenons une séquence d'approximations : 2,0 ; 1,1817 ; 1,1462 ; 1.1461. La valeur de la fonction f(x) au point x=1,1461 est égale à f(1,1461)= -0,00006.

La méthode de Newton a un taux de convergence élevé, mais à chaque étape elle nécessite de calculer non seulement la valeur de la fonction, mais aussi sa dérivée.

Méthode d'accord

Interprétation géométrique de la méthode des accords est comme suit
(Fig.1.2.3-8).

Traçons un segment de droite passant par les points A et B. L'approximation suivante x 1 est l'abscisse du point d'intersection de la corde avec l'axe 0x. Construisons l'équation d'un segment de droite :

Posons y=0 et trouvons la valeur x=x 1 (prochaine approximation) :

Répétons le processus de calcul pour obtenir la prochaine approximation de la racine - x 2 :

Dans notre cas (Fig. 1.2.11) et la formule de calcul pour la méthode des accords ressemblera à

Cette formule est valable lorsque le point b est pris comme point fixe et que le point a fait office de première approximation.

Considérons un autre cas (Fig. 1.2.3-9), où .

L'équation de la droite dans ce cas a la forme

Prochaine approximation x 1 à y = 0

Alors la formule récurrente de la méthode des accords pour ce cas a la forme

Il est à noter que le point fixe dans la méthode des accords est choisi comme étant la fin du segment pour lequel la condition f (x)∙f¢¢ (x)>0 est satisfaite.

Ainsi, si le point a est pris comme point fixe , alors x 0 = b fait office d'approximation initiale, et vice versa.

Les conditions suffisantes qui assurent le calcul de la racine de l'équation f(x) = 0 à l'aide de la formule d'accord seront les mêmes que pour la méthode de la tangente (méthode de Newton), seulement au lieu de l'approximation initiale, un point fixe est choisi. La méthode des accords est une modification de la méthode de Newton. La différence est que l'approximation suivante dans la méthode de Newton est le point d'intersection de la tangente avec l'axe 0X, et dans la méthode des accords - le point d'intersection de la corde avec l'axe 0X - les approximations convergent vers la racine de différents côtés .

L'estimation de l'erreur pour la méthode des accords est donnée par l'expression

(1.2.3-15)

Condition pour terminer le processus d'itération à l'aide de la méthode des accords

(1.2.3-16)

Dans le cas M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Exemple 1.2.3-4. Clarifiez la racine de l'équation e x – 3x = 0, séparée sur le segment avec une précision de 10 -4.

Vérifions la condition de convergence :

Par conséquent, a=0 doit être choisi comme point fixe, et x 0 =1 doit être pris comme approximation initiale, puisque f(0)=1>0 et f(0)*f"(0)>0.

Méthode de Newton (tangentes) pour trouver des racines

Il s'agit d'une méthode itérative inventée Isaac Newton(Isaak Newton) vers 1664. Cependant, cette méthode est parfois appelée méthode de Newton-Raphson, car Raphson a inventé le même algorithme plusieurs années plus tard que Newton, mais son article a été publié beaucoup plus tôt.

La tâche est la suivante. Étant donné l'équation :

Il faut résoudre cette équation, ou plus précisément trouver une de ses racines (en supposant que la racine existe). On suppose qu’elle est continue et différentiable sur l’intervalle.

Algorithme

Le paramètre d'entrée de l'algorithme, en plus de la fonction, est également première approximation— certains , à partir desquels l'algorithme commence à partir.

Calculons déjà, calculons-le comme suit. Traçons une tangente au graphique de la fonction au point , et trouvons le point d'intersection de cette tangente avec l'axe des abscisses. fixons-le égal au point trouvé et répétons tout le processus depuis le début.

Il est facile d'obtenir la formule suivante :

Il est intuitivement clair que si la fonction est suffisamment « bonne » (fluide) et est située suffisamment près de la racine, alors elle sera encore plus proche de la racine souhaitée.

Le taux de convergence est quadratique, ce qui, relativement parlant, signifie que le nombre de chiffres exacts dans la valeur approximative double à chaque itération.

Application pour calculer la racine carrée

Considérons la méthode de Newton en utilisant l'exemple du calcul de la racine carrée.

Si nous substituons , alors après avoir simplifié l'expression, nous obtenons :

La première version typique du problème est lorsqu'elle est donnée un nombre fractionnaire, et vous devez calculer sa racine avec une certaine précision :

double n; cin >> n; const double EPS = 1E-15 ; double x = 1 ; pour (;; ) ( double nx = (x + n / x) / 2 ; si (abs (x - nx)< EPS) break ; x = nx; } printf ("%.15lf" , x) ;

Une autre version courante du problème est lorsque vous devez calculer une racine entière (pour une racine donnée, trouvez la plus grande telle que ). Ici, nous devons modifier légèrement la condition d'arrêt de l'algorithme, car il peut arriver qu'il commence à « sauter » près de la réponse. Par conséquent, nous ajoutons une condition selon laquelle si la valeur à l'étape précédente a diminué, mais qu'à l'étape actuelle tente d'augmenter, alors l'algorithme doit être arrêté.

entier n; cin >> n; entier x = 1 ; bool diminué = faux ; for (;; ) ( int nx = (x + n / x) >> 1 ; if (x == nx || nx > x && diminué) break ; diminué = nx< x; x = nx; } cout << x;

Enfin, nous présentons une troisième option – pour le cas de l’arithmétique longue. Puisque le nombre peut être assez grand, il est logique de prêter attention à la première approximation. Évidemment, plus on se rapproche de la racine, plus le résultat sera obtenu rapidement. Il sera assez simple et efficace de prendre le nombre comme première approximation, où est le nombre de bits du nombre. Voici le code Java illustrant cette option :

GrosEntier n; // des données d'entrée BigInteger a = BigInteger.ONE.shiftLeft(n.bitLength()/2); booléen p_dec = false ; pour (;; ) ( BigInteger b = n.divide (a) .add (a) .shiftRight (1 ) ; if (a.compareTo (b) == 0 || a.compareTo (b)< 0 && p_dec) break ; p_dec = a.compareTo (b) >0 ; une = b; )

Par exemple, cette version du code s'exécute pendant un nombre en millisecondes, mais si nous supprimons le choix amélioré de l'approximation initiale (il suffit de commencer par ), elle s'exécutera en quelques millisecondes.

Alors qu'ils luttent à l'école pour résoudre des équations dans les cours de mathématiques, de nombreux élèves sont souvent convaincus qu'ils perdent leur temps complètement en vain, et pourtant une telle compétence sera utile dans la vie non seulement à ceux qui décident de suivre les traces de Descartes, Euler ou Lobatchevski.

Dans la pratique, par exemple en médecine ou en économie, il arrive souvent qu'un spécialiste ait besoin de savoir à quel moment la concentration substance active d’un médicament particulier atteindra le niveau requis dans le sang du patient, ou il est nécessaire de calculer le temps nécessaire pour qu’une entreprise particulière devienne rentable.

Plus souvent nous parlons de sur la résolution d'équations non linéaires de différents types. Les méthodes numériques permettent de le faire le plus rapidement possible, notamment à l'aide d'un ordinateur. Ils ont été bien étudiés et ont prouvé depuis longtemps leur efficacité. Il s'agit notamment de la méthode tangente de Newton, qui fait l'objet de cet article.

Formulation du problème

Dans ce cas, il existe une fonction g, qui est définie sur le segment (a, b) et y prend certaines valeurs, c'est-à-dire que chaque x appartenant à (a, b) peut être associé à un nombre spécifique g (X).

Il est nécessaire d'établir toutes les racines de l'équation à partir de l'intervalle entre les points a et b (y compris les extrémités), pour lequel la fonction est mise à zéro. Évidemment, ce seront les points d'intersection de y = g(x) avec OX.

Dans certains cas, il est plus pratique de remplacer g(x)=0 par un autre similaire, comme g 1 (x) = g 2 (x). Dans ce cas, les abscisses (valeur x) des points d'intersection des graphiques g 1 (x) et g 2 (x) font office de racines.

La solution d'une équation non linéaire est également importante pour les problèmes d'optimisation pour lesquels la condition d'un extremum local est que la dérivée de la fonction tourne vers 0. En d’autres termes, un tel problème peut se réduire à trouver les racines de l’équation p(x) = 0, où p(x) est identique à g"(x).

Méthodes de résolution

Pour certains types d'équations non linéaires, telles que les équations quadratiques ou trigonométriques simples, les racines peuvent être trouvées de manière assez simple. En particulier, chaque écolier connaît des formules qui peuvent être utilisées pour trouver facilement les valeurs de l'argument des points où le trinôme quadratique disparaît.

Les méthodes d'extraction des racines d'équations non linéaires sont généralement divisées en méthodes analytiques (directes) et itératives. Dans le premier cas, la solution souhaitée se présente sous la forme d'une formule, à l'aide de laquelle pour un certain nombre opérations arithmétiques vous pouvez trouver la signification des racines que vous recherchez. Des méthodes similaires ont été développées pour les calculs exponentiels, trigonométriques, logarithmiques et simples. équations algébriques. Pour le reste, il faut utiliser des méthodes numériques particulières. Ils sont faciles à mettre en œuvre grâce à des ordinateurs, qui permettent de retrouver les racines avec la précision requise.

Il s'agit notamment de la méthode dite numérique de la tangente, cette dernière a été proposée par le grand scientifique Isaac Newton à la fin du XVIIe siècle. Au cours des siècles suivants, la méthode a été améliorée à plusieurs reprises.

Localisation

Les méthodes numériques de résolution d'équations complexes qui n'ont pas de solutions analytiques sont généralement réalisées en 2 étapes. Vous devez d’abord les localiser. Cette opération consiste à trouver sur OX les segments sur lesquels se trouve une racine de l'équation à résoudre.

Considérons le segment. Si g(x) n'a pas de discontinuités et prend des valeurs de signes différents aux extrémités, alors entre a et b ou en eux il y a au moins 1 racine de l'équation g(x) = 0. Pour que pour être unique, il faut que g(x) ne soit pas monotone. Comme on le sait, il aura cette propriété à condition que le signe de g’(x) soit constant.

En d'autres termes, si g(x) n'a pas de discontinuités et augmente ou diminue de manière monotone, et que ses valeurs aux extrémités n'ont pas les mêmes signes, alors il y a 1 et seulement 1 racine de g(x).

Cependant, sachez que ce critère ne s’appliquera pas aux racines d’équations multiples.

Résoudre une équation en la divisant par deux

Avant d'envisager des tangentes numériques plus complexes et leurs variétés, il convient de se familiariser avec les tangentes numériques les plus complexes. d'une manière simple identifier les racines. C'est ce qu'on appelle la dichotomie et fait référence à la manière intuitive de trouver des racines, basée sur le théorème selon lequel si pour g(x), continu, la condition de différents signes est satisfaite, alors sur le segment considéré il y a au moins 1 racine g( x) = 0.

Pour le trouver, vous devez diviser le segment en deux et désigner le point médian par x 2. Alors deux options sont possibles : g(x 0) * g(x 2) ou g(x 2) * g(x 1) sont égaux ou inférieurs à 0. On choisit celle pour laquelle une de ces inégalités est vraie. Nous répétons la procédure décrite ci-dessus jusqu'à ce que la longueur devienne inférieure à une certaine valeur présélectionnée qui détermine la précision de la détermination de la racine de l'équation sur .

Les avantages de la méthode incluent sa fiabilité et sa simplicité, mais l'inconvénient est la nécessité d'identifier initialement les points auxquels g(x) prend des signes différents, de sorte qu'elle ne peut pas être utilisée pour des racines même multiplicités. De plus, cela ne se généralise pas au cas d’un système d’équations ou s’il s’agit de racines complexes.

Exemple 1

Voyons résoudre l'équation g(x) = 2x 5 + x - 1 = 0. Afin de ne pas passer beaucoup de temps à chercher un segment approprié, nous construisons un graphique en utilisant, par exemple, le programme Excel bien connu . On voit qu'il vaut mieux prendre les valeurs de l'intervalle comme segment pour localiser la racine. Nous pouvons être sûrs qu’il existe au moins une racine de l’équation requise.

g"(x) = 10x 4 + 1, c'est-à-dire que c'est une fonction croissante de façon monotone, il n'y a donc qu'une seule racine sur le segment sélectionné.

Nous substituons les points finaux dans l'équation. Nous avons respectivement 0 et 1. Dans un premier temps, nous prenons le point 0,5 comme solution. Alors g(0,5) = -0,4375. Cela signifie que le prochain segment à diviser par deux sera . Son point médian est de 0,75. Dans celui-ci, la valeur de la fonction est de 0,226. Nous prenons en considération le segment et son milieu, qui se situe au point 0,625. Nous calculons que la valeur de g(x) est de 0,625. Il est égal à -0,11, c'est à dire négatif. Sur la base de ce résultat, nous sélectionnons le segment. On obtient x = 0,6875. Alors g(x) = -0,00532. Si la précision de la solution est de 0,01, alors nous pouvons supposer que le résultat souhaité est de 0,6875.

Base théorique

Cette méthode de recherche de racines utilisant la méthode tangente de Newton est populaire en raison de sa convergence très rapide.

Il est basé sur le fait prouvé que si x n est une approximation de la racine f(x) = 0, telle que f" C 1, alors la prochaine approximation sera au point où l'équation de la tangente à f(x) est remis à zéro, c'est-à-dire

Remplacez x = x n+1 et définissez y sur zéro.

Les tangentes ressemblent alors à ceci :

Exemple 2

Essayons d'utiliser la méthode tangente classique de Newton et de trouver une solution à une équation non linéaire difficile, voire impossible, à trouver analytiquement.

Supposons qu'il soit nécessaire d'identifier les racines de x 3 + 4x - 3 = 0 avec une certaine précision, par exemple 0,001. Comme on le sait, le graphique de toute fonction sous la forme d'un polynôme de degré impair doit couper l'axe OX au moins une fois, c'est-à-dire qu'il n'y a aucun doute sur l'existence de racines.

Avant de résoudre notre exemple en utilisant la méthode de la tangente, nous construisons un graphe f(x) = x 3 + 4x - 3 par points. Cela est très simple à faire, par exemple en utilisant un tableur Excel. À partir du graphique résultant, il sera clair qu'il ne coupe pas l'axe OX et que la fonction y = x 3 + 4x - 3 augmente de manière monotone. Nous pouvons être sûrs que l'équation x 3 + 4x - 3 = 0 a une solution et qu'elle est unique.

Algorithme

Toute solution d'équations par la méthode tangente commence par le calcul de f" (x). On a :

Alors la dérivée seconde sera x * 6.

À l'aide de ces expressions, nous pouvons écrire une formule pour identifier les racines d'une équation en utilisant la méthode de la tangente sous la forme :

Ensuite, vous devez choisir une première approximation, c'est-à-dire décider quel point considérer comme point de départ (volume x 0) pour le processus itératif. Nous considérons les extrémités du segment. Nous utiliserons celui pour lequel la condition selon laquelle la fonction et sa dérivée 2e en x 0 sont de signes différents est vraie. Comme nous pouvons le voir, lors de la substitution de x 0 = 0, il est cassé, mais x 0 = 1 convient tout à fait.

alors si nous souhaitons résoudre la méthode tangente avec précision e, alors la valeur x n peut être considérée comme satisfaisant aux exigences du problème, à condition que l'inégalité |f(x n) / f'(x n)|< e.

Au premier pas tangentiel nous avons :

• x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1- 0,2857 = 0,71429 ;
• puisque la condition n’est pas remplie, on passe à autre chose ;
• on obtient une nouvelle valeur pour x 2, qui est égale à 0,674 ;
• on remarque que le rapport de la valeur de la fonction à sa dérivée en x 2 est inférieur à 0,0063, on arrête le processus.

Méthode tangente dans Excel

Vous pouvez résoudre l'exemple précédent beaucoup plus facilement et plus rapidement si vous n'effectuez pas de calculs manuellement (sur une calculatrice), mais utilisez les capacités processeur de table de Microsoft.

Pour ce faire, vous devez créer une nouvelle page dans Excel et remplir ses cellules avec les formules suivantes :

• en C7 on écrit « = DEGRÉ (B7;3) + 4 * B7 - 3 » ;
• dans D7 on entre « = 4 + 3 * DEGRÉ (B7;2) » ;
• en E7 on écrit « = (DEGRÉ (B7;3)- 3 + 4 * B7) / (3* DEGRÉ (B7;2) + 4) » ;
• en D7 on entre l'expression « =B7 - E7 » ;
• dans B8 nous entrons la formule de condition « =IF(E7< 0,001;"Завершение итераций"; D7)».

Dans un problème spécifique, l'inscription « Terminaison des itérations » apparaîtra dans la cellule B10, et pour résoudre le problème, vous devrez prendre le numéro écrit dans la cellule située une ligne au-dessus. Vous pouvez également lui sélectionner une colonne « extensible » distincte en y entrant une formule-condition, selon laquelle le résultat y sera écrit si le contenu de l'une ou l'autre cellule de la colonne B prend la forme « Achèvement des itérations ».

Implémentation en Pascal

Essayons d'obtenir une solution à l'équation non linéaire y = x 4 - 4 - 2 * x en utilisant la méthode de la tangente en Pascal.

Nous utilisons une fonction auxiliaire qui permettra d'effectuer un calcul approximatif f"(x) = (f(x + delta) - f(x)) / delta. Comme condition pour terminer le processus itératif, nous choisissons la réalisation de l'inégalité |x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

Le programme se distingue par le fait qu'il ne nécessite pas de calcul manuel de la dérivée.

Méthode d'accord

Considérons une autre façon d'identifier les racines des équations non linéaires. Le processus d'itération consiste dans le fait qu'à titre d'approximations successives de la racine souhaitée pour f(x) = 0, on prend les valeurs des points d'intersection de la corde avec l'abscisse des points d'extrémité a et b avec OX, noté x 1, ..., x n. Nous avons:

Pour le point où la corde coupe l'axe OX, l'expression s'écrira comme suit :

Soit la dérivée seconde positive pour x £ (le cas inverse se ramènera à celui considéré si l'on écrit f(x) = 0). Dans ce cas, le graphe y = f(x) est une courbe convexe en bas et située en dessous de la corde UN B. Il peut y avoir 2 cas : lorsque la fonction a une valeur positive au point a ou qu'elle est négative au point b.

Dans le premier cas, nous choisissons l’extrémité a comme fixe et prenons le point b comme x 0. Puis des approximations successives selon la formule présentée ci-dessus forment une séquence qui décroît de façon monotone.

Dans le deuxième cas, la fin b est fixée à x 0 = a. Les valeurs x obtenues à chaque étape d'itération forment une séquence qui augmente de façon monotone.

Ainsi, nous pouvons affirmer que :

• dans la méthode des accords, l'extrémité fixe du segment est celle où les signes de la fonction et de sa dérivée seconde ne coïncident pas ;
• les approximations de la racine x - x m - se situent du côté où f(x) a un signe qui ne coïncide pas avec le signe de f"" (x).

Les itérations peuvent être poursuivies jusqu'à ce que les conditions de proximité des racines soient remplies à cette étape et à l'itération précédente modulo abs(x m - x m - 1)< e.

Méthode modifiée

La méthode combinée des accords et des tangentes permet d'établir les racines d'une équation en les approchant par différents côtés. Cette valeur, à laquelle le graphique f(x) coupe OX, permet d'affiner la solution beaucoup plus rapidement que d'utiliser chacune des méthodes séparément.

Supposons que nous devions trouver les racines de f(x)=0, si elles existent sur . Vous pouvez appliquer l'une des méthodes décrites ci-dessus. Cependant, il est préférable d’en essayer une combinaison, ce qui améliorera considérablement la précision de la racine.

Nous considérons le cas avec une première approximation correspondant à la condition que les dérivées première et seconde soient de signes différents en un point x précis.

Dans de telles conditions, la résolution d'équations non linéaires par la méthode de la tangente permet de trouver une racine avec un excès si x 0 =b, et la méthode utilisant des accords avec une extrémité fixe b conduit à trouver une racine approchée avec un déficit.

Formules utilisées :

Maintenant, la racine x requise doit être recherchée dans l'intervalle. À l'étape suivante, vous devez appliquer la méthode combinée à ce segment. En procédant ainsi, on obtient des formules de la forme :

Si les dérivées première et seconde ont des signes différents, alors, en raisonnant de la même manière, pour clarifier la racine on obtient les formules récurrentes suivantes :

La condition utilisée est l'inégalité estimée | b n +1 - une n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

Si l'inégalité ci-dessus est vraie, alors comme racine de l'équation non linéaire sur un segment donné, prenez le point qui est exactement à mi-chemin entre les solutions trouvées à une étape d'itération spécifique.

La méthode combinée est facilement implémentable dans l’environnement TURBO PASCAL. Si vous le souhaitez vraiment, vous pouvez essayer d'effectuer tous les calculs en utilisant la méthode tabulaire dans Excel.

Dans ce dernier cas, plusieurs colonnes sont allouées pour résoudre le problème à l'aide d'accords et séparément pour la méthode proposée par Isaac Newton.

Dans ce cas, chaque ligne est utilisée pour enregistrer les calculs à une étape d'itération spécifique en utilisant deux méthodes. Ensuite, sur le côté gauche de la zone de solution, une colonne est mise en surbrillance sur la page de travail active, dans laquelle est saisi le résultat du calcul du module de la différence de valeurs de l'étape itérative suivante pour chacune des méthodes. Un autre peut être utilisé pour saisir les résultats de calculs basés sur la formule de calcul de la construction logique « SI », utilisée pour savoir si une condition est vraie ou non.

Vous savez maintenant comment résoudre des équations complexes. La méthode tangente, comme vous l'avez déjà vu, est implémentée assez simplement, aussi bien en Pascal qu'en Excel. Par conséquent, vous pouvez toujours déterminer les racines d’une équation difficile ou impossible à résoudre à l’aide de formules.

Identique à l'approximation. Le terme P. est parfois utilisé dans le sens de rapprocher un objet (par exemple, P. initial)... Encyclopédie mathématique

La méthode de Newton- Méthode de Newton, l'algorithme de Newton (également connu sous le nom de méthode tangente) est une méthode numérique itérative permettant de trouver la racine (zéro) d'une fonction donnée. La méthode a été proposée pour la première fois par le physicien, mathématicien et astronome anglais Isaac Newton... ... Wikipedia

Une méthode tangente

Méthode de Gauss-Newton- La méthode de Newton (également connue sous le nom de méthode tangente) est une méthode numérique itérative permettant de trouver la racine (zéro) d'une fonction donnée. La méthode a été proposée pour la première fois par le physicien, mathématicien et astronome anglais Isaac Newton (1643 1727), sous le nom ... ... Wikipedia

Méthode Newton-Raphson- La méthode de Newton (également connue sous le nom de méthode tangente) est une méthode numérique itérative permettant de trouver la racine (zéro) d'une fonction donnée. La méthode a été proposée pour la première fois par le physicien, mathématicien et astronome anglais Isaac Newton (1643 1727), sous le nom ... ... Wikipedia

Méthode Newton-Raphson- La méthode de Newton (également connue sous le nom de méthode tangente) est une méthode numérique itérative permettant de trouver la racine (zéro) d'une fonction donnée. La méthode a été proposée pour la première fois par le physicien, mathématicien et astronome anglais Isaac Newton (1643 1727), sous le nom ... ... Wikipedia

Méthode tangente- La méthode de Newton (également connue sous le nom de méthode tangente) est une méthode numérique itérative permettant de trouver la racine (zéro) d'une fonction donnée. La méthode a été proposée pour la première fois par le physicien, mathématicien et astronome anglais Isaac Newton (1643 1727), sous le nom ... ... Wikipedia

Méthode tangente (méthode de Newton)- La méthode de Newton (également connue sous le nom de méthode tangente) est une méthode numérique itérative permettant de trouver la racine (zéro) d'une fonction donnée. La méthode a été proposée pour la première fois par le physicien, mathématicien et astronome anglais Isaac Newton (1643 1727), sous le nom ... ... Wikipedia

Méthode tangente- La méthode de Newton (également connue sous le nom de méthode tangente) est une méthode numérique itérative permettant de trouver la racine (zéro) d'une fonction donnée. La méthode a été proposée pour la première fois par le physicien, mathématicien et astronome anglais Isaac Newton (1643 1727), sous le nom ... ... Wikipedia

Solution numérique d'équations- et leurs systèmes consistent en une détermination approximative de la ou des racines d'une équation ou d'un système d'équations et sont utilisés dans les cas où il est impossible ou très laborieux de calculer la valeur exacte. Contenu 1 Énoncé du problème 2 Méthodes numériques ... Wikipédia

Méthode d'approximation successive- une méthode de résolution de problèmes mathématiques utilisant une séquence d'approximations qui converge vers une solution et est construite de manière récursive (c'est-à-dire que chaque nouvelle approximation est calculée sur la base de la précédente ; l'approximation initiale est choisie dans ... ... Grande Encyclopédie Soviétique