Méthode d'accord (méthode également connue sous le nom Méthode sécante ) l'une des méthodes de résolution d'équations non linéaires et est basée sur le rétrécissement séquentiel de l'intervalle contenant la seule racine de l'équation. Le processus itératif est effectué jusqu'à ce que la précision spécifiée soit atteinte.

Contrairement à la méthode de la demi-division, la méthode des accords suggère que la division de l'intervalle considéré ne sera pas effectuée en son milieu, mais au point d'intersection de la corde avec l'axe des abscisses (axe X). Il est à noter qu'une corde s'entend comme un segment tracé passant par les points de la fonction considérée aux extrémités de l'intervalle considéré. La méthode considérée permet de trouver la racine plus rapidement que la méthode des moitiés, à condition que le même intervalle considéré soit spécifié.

Géométriquement, la méthode des accords équivaut à la remplacer par une corde courbe passant par les points et (voir Fig. 1.).

Fig. 1. Construction d'un segment (accord) à une fonction.

L'équation d'une droite (corde) qui passe par les points A et B a la forme suivante :

Cette équation est une équation typique pour décrire une ligne droite dans un système de coordonnées cartésiennes. La pente de la courbe est précisée en ordonnée et en abscisse en utilisant respectivement les valeurs du dénominateur et .

Pour le point d'intersection de la droite avec l'axe des abscisses, l'équation écrite ci-dessus sera réécrite sous la forme suivante :

Comme nouvel intervalle pour parcourir le processus itératif, nous sélectionnons l'un des deux ou , aux extrémités desquels la fonction prend des valeurs de signes différents. Les signes opposés des valeurs de fonction aux extrémités d'un segment peuvent être déterminés de plusieurs manières. L'une de ces méthodes consiste à multiplier les valeurs de la fonction aux extrémités du segment et à déterminer le signe du produit en comparant le résultat de la multiplication avec zéro :

ou .

Le processus itératif d'affinement de la racine se termine lorsque la condition de proximité de deux approximations successives devient inférieure à la précision spécifiée, c'est-à-dire

Fig.2. Explication de la définition de l'erreur de calcul.

Il est à noter que la convergence de la méthode des cordes est linéaire, mais plus rapide que la convergence de la méthode des bissections.

Algorithme pour trouver la racine d'une équation non linéaire à l'aide de la méthode des accords

1. Trouvez l'intervalle d'incertitude initial en utilisant l'une des méthodes de séparation des racines. Zdonner l'erreur de calcul (petit nombre positif) Et étape d'itération initiale () .

2. Trouver le point d'intersection de la corde avec l'axe des abscisses :

3. Il faut trouver la valeur de la fonction aux points , et . Ensuite, vous devez vérifier deux conditions :

Si la condition est remplie , alors la racine souhaitée est située à l'intérieur du segment gauche put, ;

Si la condition est remplie , alors la racine souhaitée se trouve à l'intérieur du segment droit accepter , .

En conséquence, un nouvel intervalle d'incertitude est trouvé, sur lequel se trouve la racine souhaitée de l'équation :

4. Nous vérifions la valeur approximative de la racine de l'équation pour la précision spécifiée, dans le cas de :

Si la différence entre deux approximations successives devient inférieure à la précision spécifiée, alors le processus itératif se termine. La valeur approximative de la racine est déterminée par la formule :

Si l’écart entre deux approximations successives n’atteint pas la précision requise, alors il faut poursuivre le processus itératif et passer à l’étape 2 de l’algorithme considéré.

Un exemple de résolution d'équations à l'aide de la méthode des accords

À titre d'exemple, envisageons de résoudre une équation non linéaire à l'aide de la méthode des accords. La racine doit être trouvée dans la plage considérée avec une précision de .

Option pour résoudre une équation non linéaire dans un progicielMathCAD.

Les résultats du calcul, à savoir la dynamique des changements de la valeur approximative de la racine, ainsi que les erreurs de calcul en fonction du pas d'itération, sont présentés sous forme graphique (voir Fig. 1).

Fig. 1. Résultats du calcul à l'aide de la méthode des accords

Pour garantir la précision spécifiée lors de la recherche d'une équation dans une plage, il est nécessaire d'effectuer 6 itérations. Lors de la dernière étape d'itération, la valeur approximative de la racine de l'équation non linéaire sera déterminée par la valeur : .

Note:

Une modification de cette méthode est méthode de fausse position(Méthode de fausse position), qui diffère de la méthode sécante uniquement en ce qu'à chaque fois, ce ne sont pas les 2 derniers points qui sont pris, mais les points qui sont situés autour de la racine.

Il convient de noter que si la dérivée seconde peut être extraite d'une fonction non linéaire, l'algorithme de recherche peut être simplifié. Supposons que la dérivée seconde conserve un signe constant et considérons deux cas :

Cas 1:

De la première condition il s’avère que le côté fixe du segment est le côté un.

Cas n°2 :

Instructions. Entrez l'expression F(x) , cliquez sur Suivant. La solution résultante est enregistrée dans un fichier Word. Un modèle de solution est également créé dans Excel. Vous trouverez ci-dessous une instruction vidéo.

Règles de saisie d'une fonction

Considérons un moyen plus rapide de trouver la racine de l'intervalle, en supposant que f(a)f(b)<0.
f''(x)>0 f''(x)<0
f(b)f''(b)>0 f(a)f''(a)>0


Fig.1a Fig. 1b

Regardons la figure 1a. Traçons une corde passant par les points A et B. Équation d'accord
.
Au point x=x 1 , y=0, on obtient ainsi la première approximation de la racine
. (3.8)
Vérification des conditions
(une) f(x 1)f(b)<0,
(b) f(x1)f(a)<0.
Si la condition (a) est satisfaite, alors dans la formule (3.8) on remplace le point a par x 1, on obtient

.

En poursuivant ce processus, on obtient pour la nième approximation
. (3.9)
Ici, la fin a est mobile, c'est-à-dire f(x i)f(b)<0. Аналогичная ситуация на рис 2а.
Considérons le cas où la fin a est fixe.
f''(x)<0 f’’(x)>0
f(b)f’’(b)<0 f(a)f’’(a)<0


Fig.2a Fig.2b

Sur la figure 1b, 2b f(x i)f(a) est exécuté<0. Записав уравнение хорды, мы на первом шаге итерационного процесса получим x 1 (см. (3.8)). Здесь выполняется f(x 1)f(a)<0. Затем вводим b 1 =x 1 (в формуле (3.8) точку b заменяем на x 1), получим
.

En continuant le processus, nous arrivons à la formule
. (3.10)
Arrêter le processus

|x n – x n-1 |<ε; ξ≈x n

Riz. 3
Sur la figure 3, f''(x) change de signe, les deux extrémités seront donc mobiles.
Avant d'aborder la question de la convergence du processus itératif de la méthode des accords, introduisons la notion de fonction convexe.

Définition. Une fonction continue est dite convexe (concave) si pour deux points quelconques x 1 ,x 2 satisfaisant a≤x 1 f(αx 1 + (1-α)x 2) ≤ αf(x 1) + (1-α)f(x 2) - convexe.
f(αx 1 + (1-α)x 2) ≥ αf(x 1) + (1-α)f(x 2) - concave
Pour une fonction convexe f’’(x)≥0.
Pour une fonction concave f’’(x)≤0

Théorème 3. Si la fonction f(x) est convexe (concave) sur le segment , alors sur n'importe quel segment le graphique de la fonction f(x) n'est pas plus haut (ni plus bas) que la corde passant par les points du graphique d'abscisses x 1 et x 2.

Preuve:

Considérons une fonction convexe. L'équation de la corde : passant par x 1 et x 2 a la forme :
.
Considérons le point c= αx 1 + (1-α)x 2 , où aО

En revanche, par définition d'une fonction convexe on a f(αx 1 + (1-α)x 2) ≤ αf 1 + (1-α)f 2 ; donc f(c) ≤ g(c) etc.

Pour une fonction concave, la preuve est similaire.
Nous considérerons la preuve de la convergence du processus itératif pour le cas d'une fonction convexe (concave).

Théorème 4. Soit une fonction continue f(x) deux fois différentiable et soit f(a)f(b)<0, а f’(x) и f’’(x) сохраняют свои знаки на (см. рис 1а,1б и рис 2а,2б). Тогда итерационный процесс метода хорд сходится к корню ξ с любой наперед заданной точностью ε.
Preuve: Considérons par exemple le cas f(a)f’’(a)<0 (см рис 1а и 2а). Из формулы (9) следует, что x n >x n -1 puisque (b-x n -1)>0, et f n -1 /(f b -f n -1)<0. Это справедливо для любого n, то есть получаем возрастающую последовательность чисел
a≤x 0 Montrons maintenant que toutes les approximations x n< ξ, где ξ - корень. Пусть x n -1 < ξ. Покажем, что x n тоже меньше ξ. Введем
. (3.11)
Nous avons
(3.12)
(c'est-à-dire que la valeur de la fonction y(x) au point x n sur la corde coïncide avec f(ξ)).
Puisque , alors de (3.12) il résulte
ou
. (3.13)
Pour la fig. 1a, donc
ou
veut dire que, etc. (voir (3.11)).
Pour la figure 2a. Par conséquent, de (3.12) on obtient
Moyens
parce que etc.
Preuve similaire pour les figures 1b et 2b. Ainsi, nous avons prouvé que la suite des nombres est convergente.
a≤x 0 une≤ξ Cela signifie que pour tout ε, on peut spécifier un n tel que |x n - ξ |<ε. Теорема доказана.
La convergence de la méthode des accords est linéaire avec le coefficient .
, (3.14)
où m 1 =min|f’(x)|, M 1 =max|f’(x)|.
Cela découle des formules suivantes. Considérons le cas d'une extrémité fixe b et f(b)>0.
On a de (3.9) . D'ici
. Compte tenu de cela, nous pouvons écrire ou
.
Remplacer (ξ-x n -1) au dénominateur du membre de droite par (b-x n -1) et prendre en compte que (ξ-x n -1)< (b-x n -1), получим , ce qui devait être prouvé (voir inégalité (3.14)).
La preuve de convergence pour le cas de la figure 3 (f''(x) change de signe ; dans le cas général, f' et f'' peuvent changer de signe) est plus complexe et n'est pas donnée ici.

Dans les problèmes, déterminez le nombre de racines réelles de l'équation f(x) = 0, séparez ces racines et, à l'aide de la méthode des cordes et des tangentes, trouvez leurs valeurs approximatives avec une précision de 0,001.

La méthode considérée, comme la méthode des moitiés, vise à clarifier la racine sur l'intervalle

prend des valeurs de signes différents. Contrairement à la méthode des moitiés, nous prenons l'approximation suivante non pas au milieu du segment, mais au point , où une ligne droite (corde) tracée à travers les points coupe l'axe des x UN Et DANS(Fig. 2.6).

Écrivons l'équation de la droite passant par les points UN Et DANS:

.

Pour le point d'intersection de la droite avec l'axe des abscisses (
) on obtient l'équation

. (2.13)

Comme nouvel intervalle pour poursuivre le processus itératif, nous sélectionnons l'un des deux
Et
, aux extrémités duquel la fonction
prend des valeurs de signes différents. Pour le cas considéré (Fig. 2.6), nous sélectionnons le segment
, parce que
. La prochaine itération consiste à définir une nouvelle approximation comme les points d'intersection d'une corde
avec l'axe des x, etc.

Nous terminons le processus d'affinement de la racine lorsque la distance entre les approximations successives devient inférieure à la précision spécifiée, c'est-à-dire

(2.14)

ou lorsque la condition (2.12) est satisfaite.

Ø Commentaire. La méthode des bissections et la méthode des accords sont très similaires, notamment dans la procédure de vérification des signes de la fonction aux extrémités du segment. De plus, le second d'entre eux permet dans certains cas une convergence plus rapide du processus itératif. Cependant, dans certains cas, la méthode des accords peut converger beaucoup plus lentement que la méthode des bissections. Cette situation est illustrée sur la Fig. 2.7. Les deux méthodes considérées ne nécessitent pas de connaissance d'informations supplémentaires sur la fonction
. Par exemple, il n’est pas nécessaire que la fonction soit différentiable. Même pour des fonctions discontinues, les méthodes considérées garantissent la convergence. Des méthodes de raffinement de racine plus complexes utilisent des informations supplémentaires sur la fonction
, tout d'abord, la propriété de différentiabilité. En conséquence, ils ont généralement une convergence plus rapide, mais en même temps, ils sont applicables à une classe de fonctions plus restreinte et leur convergence n'est pas toujours garantie. Un exemple d’une telle méthode est la méthode de Newton.<

1. Méthode de Newton (méthode de la tangente)

Faites-nous connaître la première approximation de la racine (la question du choix d'une première approximation sera discutée en détail ci-dessous). Traçons une tangente à la courbe en ce point
(Fig. 2.8). Cette tangente coupera l'axe des x au point , que nous considérerons comme la prochaine approximation. Signification facile à trouver sur la photo :

,

s'exprimer d'ici , on a

.

Les approximations suivantes peuvent être trouvées de la même manière. Formule pour k La +1ère approximation a la forme

,
(2.15)

De la formule (2.15) découle la condition d'applicabilité de la méthode : fonction
doit être différenciable et
au voisinage de la racine ne doit pas changer de signe.

Pour terminer le processus itératif, les conditions (2.12) ou (2.14) peuvent être utilisées.

ØRemarque 1. Dans la méthode de Newton, contrairement aux méthodes précédentes, il n'est pas nécessaire de spécifier un segment
, contenant la racine de l'équation, et il suffit de trouver une première approximation de la racine .<

Ø Remarque 2. La formule de la méthode de Newton peut être obtenue à partir d'autres considérations. Fixons une première approximation de la racine
. Remplaçons la fonction F(X) à proximité du point un segment de la série Taylor :

et au lieu de l'équation non linéaire
résoudre l'équation linéarisée

considérant sa solution comme la prochaine (première) approximation de la valeur souhaitée de la racine. La solution de cette équation est évidente :

En répétant ce processus, nous arrivons à la formule de Newton (2.15).<

Convergence de la méthode de Newton. Découvrons les principales conditions de convergence d'une séquence de valeurs
, calculé à l'aide de la formule (2.15), à la racine de l'équation (2.1). En admettant que
deux fois différenciable en continu, nous développons
dans une série Taylor dans le quartier k l'approche

En divisant le dernier rapport par
et en transférant quelques termes du côté gauche vers la droite, on obtient :

.

Considérant que l’expression entre crochets selon (2.15) est égale à
, on réécrit cette relation sous la forme

.

. (2.16)

De (2.16) il résulte que

, (2.17)

Où
,
.

Évidemment, l’erreur diminue si

. (2.18)

La condition résultante signifie que la convergence dépend du choix de l’approximation initiale.

L’estimation (2.17) caractérise le taux de diminution de l’erreur pour la méthode de Newton : à chaque étape l’erreur est proportionnelle au carré de l’erreur à l’étape précédente. La méthode de Newton a donc une convergence quadratique.

DANS choix de l'approximation initiale dans la méthode de Newton. Comme il ressort de la condition (2.18), la convergence de la séquence d’itérations obtenue dans la méthode de Newton dépend du choix de l’approximation initiale . Cela ressort également de l’interprétation géométrique de la méthode. Donc, si l'on prend le point comme première approximation (Fig. 2.9), alors on ne peut pas compter sur la convergence du processus itératif.

Si l'on choisit le point comme première approximation , alors on obtient une suite convergente.

En général, si un segment est donné
, contenant la racine, et on sait que la fonction
est monotone sur ce segment, alors en première approximation vous pouvez sélectionner cette limite de segment
, où les signes de la fonction coïncident
et la dérivée seconde
. Ce choix d'approximation initiale garantit la convergence de la méthode de Newton à condition que la fonction soit monotone sur le segment de localisation racine.

3. Méthode d'accord

Soit l'équation f(x) = 0, où f(x) est une fonction continue qui a des dérivées du premier et du second ordre dans l'intervalle (a, b). La racine est considérée comme séparée et se situe sur le segment.

L'idée de la méthode des accords est que sur un intervalle suffisamment petit l'arc de courbe y = f(x) peut être remplacé par une corde et le point d'intersection avec l'axe des abscisses peut être pris comme valeur approximative de la racine. Considérons le cas (Fig. 1) où les dérivées première et seconde ont les mêmes signes, c'est-à-dire f "(x)f ²(x) > 0. Alors l'équation de la corde passant par les points A0 et B a la forme

L'approximation racine x = x1 pour laquelle y = 0 est définie comme

.

De même, pour la corde passant par les points A1 et B, on calcule l'approximation suivante de la racine

.

En général, la formule de la méthode des accords a la forme :

. (2)

Si les dérivées première et seconde ont des signes différents, c'est-à-dire

f "(x)f "(x)< 0,

alors toutes les approximations de la racine x* sont faites à partir du bord droit du segment, comme le montre la Fig. 2, et sont calculés par la formule :

. (3)

Le choix de la formule dans chaque cas particulier dépend du type de fonction f(x) et s'effectue selon la règle : la limite du segment d'isolement racine pour lequel le signe de la fonction coïncide avec le signe de la dérivée seconde est fixé. La formule (2) est utilisée dans le cas où f(b)f "(b) > 0. Si l'inégalité f(a)f "(a) > 0 est vraie, alors il est conseillé d'utiliser la formule (3).

Riz. 1 fig. 2

Riz. 3 Fig. 4

Le processus itératif de la méthode des accords se poursuit jusqu'à ce qu'une racine approximative soit obtenue avec un degré de précision donné. Lors de l'estimation de l'erreur d'approximation, vous pouvez utiliser la relation suivante :

.

Alors la condition pour terminer les calculs s’écrit :

où e est l'erreur de calcul spécifiée. Il convient de noter que lors de la recherche d'une racine, la méthode des accords permet souvent une convergence plus rapide que la méthode de la bissection.

4. Méthode de Newton (tangentes)

Soit l'équation (1) avoir une racine sur l'intervalle, et f "(x) et f "(x) sont continus et conservent des signes constants sur tout l'intervalle.

La signification géométrique de la méthode de Newton est que l'arc de courbe y = f(x) est remplacé par une tangente. Pour ce faire, sélectionnez une première approximation de la racine x0 sur l'intervalle et tracez une tangente au point C0(x0, f(x0)) à la courbe y = f(x) jusqu'à ce qu'elle coupe l'axe des x (Fig. 3). L'équation tangente au point C0 a la forme

Ensuite, une tangente est tracée passant par le nouveau point C1(x1, f(x1)) et le point x2 de son intersection avec l'axe 0x est déterminé, etc. En général, la formule de la méthode tangente est la suivante :

À la suite des calculs, une séquence de valeurs approximatives x1, x2, ..., xi, ... est obtenue, dont chaque membre suivant est plus proche de la racine x* que le précédent. Le processus itératif s'arrête généralement lorsque la condition (4) est remplie.

L’approximation initiale x0 doit satisfaire la condition :

f(x0) f ¢¢(x0) > 0. (6)

Sinon, la convergence de la méthode de Newton n'est pas garantie, puisque la tangente coupera l'axe des x en un point n'appartenant pas au segment. En pratique, l'une des limites de l'intervalle est généralement choisie comme première approximation de la racine x0, c'est-à-dire x0 = a ou x0 = b, pour lesquels le signe de la fonction coïncide avec le signe de la dérivée seconde.

La méthode de Newton offre une vitesse de convergence élevée lors de la résolution d'équations pour lesquelles le module de la dérivée ½f ¢(x)½ près de la racine est assez grand, c'est-à-dire le graphique de la fonction y = f(x) au voisinage de la racine a une grande pente. Si la courbe y = f(x) dans l'intervalle est presque horizontale, alors l'utilisation de la méthode tangente n'est pas recommandée.

Un inconvénient important de la méthode considérée est la nécessité de calculer les dérivées de la fonction pour organiser le processus itératif. Si la valeur f ¢(x) change peu au cours de l'intervalle, alors pour simplifier les calculs, vous pouvez utiliser la formule

, (7)

ceux. il suffit de calculer la valeur dérivée une seule fois au point de départ. Géométriquement, cela signifie que les tangentes aux points Ci(xi, f(xi)), où i = 1, 2, ..., sont remplacées par des droites parallèles à la tangente tracée à la courbe y = f(x) au point initial C0(x0 , f(x0)), comme le montre la Fig. 4.

En conclusion, il convient de noter que tout ce qui précède est vrai dans le cas où l’approximation initiale x0 est choisie suffisamment proche de la vraie racine x* de l’équation. Cependant, cela n’est pas toujours facile à réaliser. Par conséquent, la méthode de Newton est souvent utilisée au stade final de la résolution d'équations après l'exécution d'un algorithme convergent fiable, par exemple la méthode de bissection.

5. Méthode d'itération simple

Pour appliquer cette méthode pour résoudre l’équation (1), il est nécessaire de la transformer sous la forme . Ensuite, une première approximation est sélectionnée et x1 est calculé, puis x2, etc. :

x1 = j(x0); x2 = j(x1); ... ; xk = j(xk-1); ...

racine d'une équation algébrique non linéaire

La séquence résultante converge vers la racine si les conditions suivantes sont remplies :

1) la fonction j(x) est dérivable sur l'intervalle.

2) en tout point de cet intervalle j¢(x) satisfait l'inégalité :

0 £ q 1 £. (8)

Dans de telles conditions, le taux de convergence est linéaire et des itérations doivent être effectuées jusqu'à ce que la condition devienne vraie :

.

Critère de type

ne peut être utilisé qu'à 0 £ q £ ½. Sinon, les itérations se terminent prématurément, sans atteindre la précision spécifiée. Si le calcul de q est difficile, alors vous pouvez utiliser un critère de fin de la forme

; .

Il existe différentes manières de transformer l’équation (1) sous la forme . Il faut en choisir un qui satisfait à la condition (8), qui génère un processus itératif convergent, comme le montre par exemple la Fig. 5, 6. Sinon, notamment lorsque ½j¢(x)½>1, le processus d'itération diverge et ne permet pas d'obtenir de solution (Fig. 7).

Riz. 5

Riz. 6

Riz. 7

Conclusion

Le problème de l'amélioration de la qualité des calculs d'équations non linéaires à l'aide de diverses méthodes, comme l'écart entre le souhaité et le réel, existe et existera dans le futur. Sa solution sera facilitée par le développement des technologies de l'information, qui consiste à la fois à améliorer les méthodes d'organisation des processus d'information et à leur mise en œuvre à l'aide d'outils spécifiques - environnements et langages de programmation.

Liste des sources utilisées

1. Alekseev V. E., Vaulin A. S., Petrova G. B. - Technologie informatique et programmation. Atelier de programmation : Manuel pratique/ -M. : Supérieur. école , 1991. - 400 p.

2. Abramov S.A., Zima E.V. - Début de la programmation en Pascal. - M. : Nauka, 1987. -112 p.

3. Technologie informatique et programmation : Proc. pour la technologie. universités/ A.V. Petrov, V.E. Alekseev, A.S. Vaulin et autres - M. : Supérieur. école, 1990 - 479 p.

4. Gusev V.A., Mordkovitch A.G. - Mathématiques : Référence. matériaux : Livre. pour les étudiants. - 2e éd. - M. : Éducation, 1990. - 416 p.

Le point de la solution approchée, c'est-à-dire Les approximations successives (4) sont construites selon les formules : , (9) où est l'approximation initiale de la solution exacte. 4.5 Méthode Seidel basée sur une équation linéarisée La formule itérative pour construire une solution approximative de l'équation non linéaire (2) basée sur l'équation linéarisée (7) a la forme : 4.6 Méthode de descente la plus raide Méthodes...

Méthode d'itération

Méthode d'itération simple pour l'équation F(X) = 0 est la suivante :

1) L'équation originale est transformée sous une forme pratique pour les itérations :

X = φ (X). (2.2)

2) Sélectionnez l'approximation initiale X 0 et calculer les approximations suivantes à l'aide de la formule itérative
xk = φ (xk -1), k =1,2, ... (2.3)

S'il y a une limite à la séquence d'itérations, c'est la racine de l'équation F(X) = 0, c'est-à-dire F(ξ ) =0.

oui = φ (X)

un x 0 X 1 X 2 ξ b

Riz. 2. Processus d'itération convergent

En figue. La figure 2 montre le processus d'obtention de l'approximation suivante à l'aide de la méthode d'itération. La séquence d'approximations converge vers la racine ξ .

La base théorique pour appliquer la méthode d’itération est donnée par le théorème suivant.

Théorème 2.3. Que les conditions soient remplies :

1) racine de l'équation X= φ(x) appartient au segment [ UN, b];

2) toutes les valeurs de fonction φ (X) appartiennent au segment [ UN, b],T. e. UN ≤ φ (X)≤b;

3) il y a un nombre tellement positif q< 1, quelle est la dérivée φ "(X) en tous points du segment [ UN, b] satisfait l'inégalité | φ "(X) | ≤ q.

1) séquence d'itérations xn= φ (xp- 1)(n = 1, 2, 3, ...) converge pour tout X 0 Î [ UN, b];

2) la limite de la séquence d'itérations est la racine de l'équation

x = φ(X), c'est-à-dire si xk= ξ, alors ξ= φ (ξ);

3) l'inégalité caractérisant le taux de convergence de la séquence d'itérations est vraie

| ξ -x k | ≤ (b-a)×q k .(2.4)

Évidemment, ce théorème pose des conditions assez strictes qui doivent être vérifiées avant d’appliquer la méthode d’itération. Si la dérivée de la fonction φ (X) est supérieur à un en valeur absolue, alors le processus d'itération diverge (Fig. 3).

oui = φ (X) oui = X

Riz. 3. Processus d'itération divergent

Comme condition de convergence des méthodes itératives, l’inégalité

|x k - x k - 1 | ≤ ε . (2.5)

Méthode d'accord est de remplacer la courbe à = F(X) un segment de droite passant par des points ( UN, F(un)) Et ( b, F(b)) riz. 4). Abscisse du point d'intersection de la droite avec l'axe OH est considérée comme l’approche suivante.

Pour obtenir la formule de calcul de la méthode des accords, on écrit l'équation de la droite passant par les points ( un, F(un)) Et ( b, F(b)) et, ce qui équivaut àà zéro, nous trouverons X:

Þ

Algorithme de méthode d'accord :

1) laissez k = 0;

2) calculer le numéro d'itération suivant : k = k + 1.

Trouvons le prochain k-e approximation à l'aide de la formule :

xk= un- F(un)(b - un)/(F(b) - F(un)).

Calculons F(xk);

3) si F(xk)= 0 (la racine est trouvée), puis passez à l'étape 5.

Si F(xk) × F(b)>0, alors b= xk, sinon un = xk;

4) si |xk – xk -1 | > ε , puis passez à l'étape 2 ;

5) afficher la valeur de la racine xk ;

Commentaire. Les actions du troisième paragraphe sont similaires aux actions de la méthode de division en moitiés. Cependant, dans la méthode des accords, à chaque étape la même extrémité du segment (droite ou gauche) peut être décalée si le graphique de la fonction au voisinage de la racine est convexe vers le haut (Fig. 4, UN) ou concave vers le bas (Fig. 4, b).Par conséquent, la différence entre les approximations voisines est utilisée dans le critère de convergence.

Riz. 4. Méthode d'accord

4. La méthode de Newton(tangentes)

Laissez la valeur approximative de la racine de l'équation être trouvée F(X)= 0, et notez-le xn.Formule de calcul La méthode de Newton pour déterminer la prochaine approche xn+1 peut être obtenu de deux manières.

La première méthode exprime la signification géométrique La méthode de Newton et consiste dans le fait qu'au lieu du point d'intersection du graphique de la fonction à= F(X)avec essieu Oh chercher le point d'intersection avec l'axe Oh tangente tracée au graphique de la fonction au point ( xn,F(xn)), comme le montre la fig. 5. L'équation tangente a la forme o - f(xn)= F"(xn)(X- xn).

Riz. 5. Méthode de Newton (tangentes)

Au point d'intersection de la tangente avec l'axe Oh variable à= 0. Équivalence àà zéro, on exprime X et on obtient la formule méthode tangente :

(2.6)

Deuxième méthode : étendre la fonction F(X) dans une série de Taylor au voisinage d'un point x = xn:

Limitons-nous aux termes linéaires par rapport à ( X- xn), mis à zéro F(X) et, exprimant l'inconnue de l'équation résultante X, le désignant par xn+1 on obtient la formule (2.6).

Présentons des conditions suffisantes pour la convergence de la méthode de Newton.

Théorème 2.4. Laissez le segment [ UN, b]les conditions sont remplies :

1) fonction F(X) et ses dérivés F"(X)Et F ""(X)continu;

2) dérivés F"(x)et F""(X) sont différents de zéro et conservent certains signes constants ;

3) F(un)×f(b) < 0 (fonction F(X)change de signe sur le segment).
Ensuite il y a un segment [ α , β ], contenant la racine souhaitée de l'équation F(X) = 0, auquel la séquence d’itérations (2.6) converge. Si comme approximation zéro X 0 sélectionnez ce point limite [ α , β ], dans laquelle le signe de la fonction coïncide avec le signe de la dérivée seconde,

ceux. F(X 0)× F"(X 0)>0, alors la séquence d'itérations converge de manière monotone

Commentaire. Notez que la méthode des accords vient de la direction opposée et que ces deux méthodes peuvent se compléter. Une combinaison est également possible méthode corde-tangente.

5. Méthode sécante

La méthode sécante peut être obtenue à partir de la méthode de Newton en remplaçant la dérivée par une expression approximative - la formule de différence :

, ,

. (2.7)

La formule (2.7) utilise deux approximations précédentes xn Et xn- 1. Par conséquent, pour une première approximation donnée X 0 il faut calculer la prochaine approximation X 1 , par exemple, par la méthode de Newton avec remplacement approximatif de la dérivée selon la formule

,

Algorithme de la méthode sécante:

1) la valeur initiale est définie X 0 et erreur ε . Calculons

;

2) pour n = 1, 2, ... alors que la condition est remplie | xn – xn -1 | > ε , calculer xn+ 1 selon la formule (2.7).