Méthode d'itération pour les systèmes d'équations non linéaires. Méthodes numériques : résolution d'équations non linéaires

L'étude de divers phénomènes ou processus à l'aide de méthodes mathématiques est réalisée à l'aide d'un modèle mathématique . Un modèle mathématique est une description formalisée de l'objet étudié à travers des systèmes d'équations linéaires, non linéaires ou différentielles, des systèmes d'inégalités, une intégrale définie, un polynôme à coefficients inconnus, etc. Le modèle mathématique doit couvrir les caractéristiques les plus importantes de l'objet. à l’étude et reflètent les liens entre eux.

Une fois le modèle mathématique compilé, procédez à la formulation du problème informatique . Dans le même temps, il est établi quelles caractéristiques du modèle mathématique sont les données initiales (d'entrée). , lequel - paramètres du modèle , et qui - données de sortie. Le problème résultant est analysé du point de vue de l'existence et de l'unicité d'une solution.

À l'étape suivante, une méthode pour résoudre le problème est sélectionnée. Dans de nombreux cas spécifiques, il n’est pas possible de trouver une solution au problème sous forme explicite, car celui-ci ne s’exprime pas à travers des fonctions élémentaires. De tels problèmes ne peuvent être résolus qu’approximativement. Les méthodes informatiques (numériques) désignent des procédures approximatives qui permettent d'obtenir une solution sous la forme de valeurs numériques spécifiques. Les méthodes informatiques sont généralement mises en œuvre sur un ordinateur. Pour résoudre le même problème, diverses méthodes de calcul peuvent être utilisées. Vous devez donc être capable d'évaluer la qualité des différentes méthodes et l'efficacité de leur utilisation pour un problème donné.

Ensuite, pour mettre en œuvre la méthode de calcul sélectionnée, un algorithme et un programme informatique sont compilés. . Il est important qu'un ingénieur moderne soit capable de transformer un problème en une forme pratique à mettre en œuvre sur un ordinateur et de construire un algorithme pour résoudre un tel problème.

Actuellement, ils sont largement utilisés comme packages implémentant les méthodes les plus générales pour résoudre un large éventail de problèmes (par exemple, Mathcad,
MatLAB), ainsi que des packages qui implémentent des méthodes pour résoudre des problèmes particuliers.

Les résultats des calculs sont analysés et interprétés. Si nécessaire, les paramètres de la méthode, et parfois le modèle mathématique, sont ajustés et un nouveau cycle de résolution du problème commence.

1.1. Formulation du problème

Laissez une fonction être donnée et vous devez trouver tout ou partie des valeurs pour lesquelles .

La valeur à laquelle , est appelé racine(ou décision) équations. Une fonction est souvent supposée être deux fois continuellement différentiable au voisinage de la racine.

La racine de l'équation s'appelle simple, si la dérivée première de la fonction en un point n'est pas égale à zéro, c'est-à-dire . Si , alors la racine s'appelle racine multiple.

Géométriquement, la racine de l'équation est le point d'intersection du graphique de la fonction avec l'axe des abscisses. En figue. La figure 1 montre le graphique d'une fonction qui a quatre racines : deux simples et deux multiples.

La plupart des méthodes de résolution d’équations se concentrent sur la recherche de racines simples.

1.2. Principales étapes pour trouver une solution

Dans le processus de recherche approximative des racines d'une équation, on distingue généralement deux étapes : localisation(ou séparation) de la racine Et clarification des racines.

La localisation de racine consiste à définir un segment contenant une et une seule racine. Il n’existe pas d’algorithme universel de localisation de racine. Parfois, il est pratique de localiser la racine en construisant un graphique ou un tableau de valeurs de fonction. La présence d'une racine sur un segment est indiquée par la différence des signes de la fonction aux extrémités du segment. La base de ceci est le théorème suivant.

Théorème . Si une fonction est continue sur un segment et prend des valeurs de signes différents à ses extrémités pour que , alors le segment contient au moins une racine de l'équation.

Cependant, une racine de multiplicité paire ne peut pas être localisée de cette manière, car au voisinage d'une telle racine la fonction a un signe constant. Au stade du raffinement de la racine, la valeur approximative de la racine est calculée avec une précision donnée. La valeur approximative de la racine est affinée à l'aide de diverses méthodes itératives. L'essence de ces méthodes est de calculer séquentiellement des valeurs qui sont des approximations de la racine.

1.3. Méthode de demi-division

La demi-méthode est la manière la plus simple et la plus fiable de résoudre une équation non linéaire. Faites savoir par une analyse préliminaire que la racine de l'équation est sur le segment , c'est-à-dire de telle sorte que . Soit la fonction continue sur un segment et prend des valeurs de différents signes aux extrémités du segment, c'est-à-dire .

Divisez le segment en deux. Mettons un point sur un point. Calculons la valeur de la fonction à ce stade : . Si , alors est la racine souhaitée et le problème est résolu. Si , alors - un certain nombre d'un certain signe : soit. Alors soit aux extrémités du segment, soit aux extrémités du segment les valeurs de la fonction ont des signes différents. Désignons un tel segment. Évidemment, la longueur du segment est deux fois inférieure à la longueur du segment . Faisons de même avec le segment. En conséquence, nous obtenons soit une racine, soit un nouveau segment, etc. (Fig. 2).

Le milieu du ème segment. Évidemment, la longueur du segment sera égale à , et puisque , alors

Critère de fin. De la relation (1), il résulte que pour une précision d'approximation donnée le calcul se termine lorsque l'inégalité ou l'inégalité est satisfaite. Ainsi, le nombre d’itérations peut être déterminé à l’avance. La valeur est considérée comme la valeur approximative de la racine.

Exemple. Trouvons-le approximativement avec précision. Ce problème équivaut à résoudre une équation ou à trouver le zéro d’une fonction. Prenons le segment comme segment initial. Aux extrémités de ce segment, la fonction prend des valeurs avec des signes différents : . Trouvons le nombre de divisions du segment nécessaire pour atteindre la précision requise. Nous avons:

Par conséquent, au plus tard en 6ème division, nous trouverons avec la précision requise . Les résultats du calcul sont présentés dans le tableau 1.

Tableau 1

1.4. Méthode d'itération simple

Laissez l'équation être remplacée par son équation équivalente

Choisissons en quelque sorte l’approximation initiale. Calculons la valeur de la fonction à et trouvons la valeur raffinée. Remplaçons maintenant dans l'équation (1) et obtenons une nouvelle approximation, etc. En poursuivant ce processus indéfiniment, nous obtenons une séquence d'approximations de la racine :

La formule (3) est formule de calcul méthode d'itération simple.

Si la suite converge vers , c'est à dire existe

et la fonction est continue, alors, en passant à la limite en (3) et en tenant compte de (4), on obtient : .

Ainsi est la racine de l’équation (2).

Convergence de la méthode. La convergence de la méthode d’itération simple est établie par le théorème suivant.

Théorème. Laissez la fonction être définie et différentiable sur l'intervalle, et laissez toutes ses valeurs être . Alors, si la condition est satisfaite :

1) le processus d'itération converge quelle que soit la valeur initiale ;

2) la valeur limite est la seule racine de l'équation sur l'intervalle.

Preuve. Depuis et , on peut écrire

D'après le théorème de la valeur moyenne (il stipule que si la dérivée d'une fonction est continue sur un certain intervalle, alors la tangente de l'angle d'inclinaison de la corde tracée entre les points et , (c'est-à-dire est égale à la dérivée de la fonction à un point intermédiaire situé entre et ), le quotient dans la dernière expression sera égal à , où est un point intermédiaire dans l'intervalle de recherche racine. Par conséquent, .

Si nous introduisons une notation pour tout l’intervalle de recherche, alors l’égalité précédente peut être réécrite comme suit :

De même. Alors l'inégalité sera vraie pour : etc. En poursuivant ces calculs plus loin, le résultat est , où est un nombre naturel. Ainsi, pour que la méthode converge, l'inégalité suivante doit être satisfaite : .

Il s'ensuit qu'il doit être inférieur à un. A son tour, pour toutes les autres valeurs inférieures à , on peut écrire : . Nous déterminons le nombre à partir de la relation. Alors l’inégalité suivante est vraie (voir la dérivation ci-dessous) : . Si nous posons la condition selon laquelle la vraie valeur de la racine doit différer de la valeur approximative du montant , c'est-à-dire , alors les approximations doivent être calculées jusqu'à ce que l'inégalité soit satisfaite

ou et puis.

Dérivation de l'inégalité. Considérons deux approximations successives : et . D'ici.

En utilisant le théorème de la valeur moyenne, on obtient :

alors, à partir de la condition, on peut écrire :

D'un autre côté, laissez . Il est évident que . De là, en tenant compte de cela, on obtient

Alors ou.

En utilisant la formule précédente, vous pouvez obtenir :

Passons à la limite de l'égalité (3), du fait de la continuité de la fonction que nous obtenons , c'est-à-dire la racine de l'équation (2). Il n’y a pas d’autres racines, puisque si , alors , alors , où . L'égalité à zéro sera atteinte si . Autrement dit, il n’y a qu’une seule racine.

Le théorème a été prouvé.

Réduire l'équation pour former
pour assurer la réalisation des inégalités

Dans le cas général, il est possible d'obtenir une forme itérative adaptée en effectuant une transformation équivalente de l'équation d'origine, par exemple en la multipliant par le coefficient : . En ajoutant ensuite les deux côtés de l’équation et en dénotant, nous pouvons exiger la réalisation d’une condition suffisante. À partir de là, la valeur requise est déterminée. Puisque la condition doit être satisfaite sur tout le segment, la plus grande valeur sur ce segment doit être utilisée pour la sélection, c'est-à-dire

Ce rapport détermine la plage de valeurs des coefficients, en modifiant la valeur dans les limites.

Habituellement accepté.

En figue. 3 à 6 montrent quatre cas de positions relatives de lignes et les processus itératifs correspondants. Riz. Les figures 3 et 4 correspondent au cas , et le processus itératif converge. Dans ce cas, si (Fig. 3), la convergence est unilatérale, et si (Fig. 4), la convergence est bilatérale, oscillatoire. Riz. 5 et 6 correspondent au cas - le processus d'itération diverge. Dans ce cas, il peut y avoir une divergence unilatérale (Fig. 5) ou bilatérale (Fig. 6).

Erreur de méthode. L'estimation de l'erreur a été prouvée (5).

Critère de fin. De l'estimation (5), il s'ensuit que les calculs doivent être poursuivis jusqu'à ce que l'inégalité soit satisfaite. Si , alors l'estimation est simplifiée : .

Exemple 1. Nous utilisons la méthode d’itération simple pour résoudre l’équation avec une précision de . Transformons l'équation sous la forme :

, c'est à dire. .

Il est facile de vérifier que la racine de l’équation est sur le segment. Après avoir calculé les valeurs aux extrémités du segment, on obtient : , a , c'est-à-dire la fonction aux extrémités du segment a des signes différents,

il y a donc une racine à l'intérieur du segment. L'emplacement de la racine est clairement illustré sur la Fig. 7.

Calculons les dérivées première et seconde de la fonction :

Puisque sur le segment , la dérivée augmente de façon monotone sur ce segment et prend sa valeur maximale à l'extrémité droite du segment, c'est-à-dire au point . L’évaluation suivante est donc juste :

Ainsi, la condition est satisfaite, et on peut utiliser le critère pour terminer les calculs. Dans le tableau La figure 2 montre les approximations obtenues à l'aide de la formule de calcul. La valeur choisie comme première approximation est .

Tableau 2

Le critère de terminaison est satisfait lorsque , . La convergence est bidirectionnelle ; la nature qualitative d’une telle convergence est illustrée à la Fig. 4. Valeur approximative de la racine avec la précision requise.

Exemple 2. Résolvez l'équation sur un segment en utilisant une méthode d'itération simple avec une précision de 0,025. Pour résoudre, l’équation originale est réduite à la forme . Pour sélectionner une valeur, nous utilisons la formule ci-dessus. La formule de calcul ressemble alors à . En première approximation, vous pouvez choisir la limite supérieure d'un segment donné.

Depuis lors.

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

La méthode de Newton est la méthode la plus efficace pour résoudre des équations non linéaires. Laissez la racine , c'est-à-dire . Nous supposons que la fonction est continue sur l'intervalle et deux fois continûment dérivable sur l'intervalle. Mettons . Traçons une tangente au graphique de la fonction en un point (Fig. 8).

L'équation tangente ressemblera à : .

On obtient la première intersection en prenant l'abscisse du point d'intersection de cette tangente avec l'axe, soit en mettant : .

On fera de même avec le point, puis avec le point, etc., on obtient ainsi une suite d'approximations, et

La formule (6) est formule de calcul de la méthode de Newton.

La méthode de Newton peut être considérée comme un cas particulier de la méthode d'itération simple, pour laquelle .

Convergence de la méthode. La convergence de la méthode de Newton est établie par le théorème suivant.

Théorème. Soit une racine simple de l'équation et dans un certain voisinage de cette racine, la fonction est deux fois continûment différentiable. Il existe alors un voisinage de la racine si petit que, avec un choix arbitraire de l'approximation initiale à partir de ce voisinage, la séquence d'itérations définie par la formule (6) ne dépasse pas ce voisinage et l'estimation est valide :

La convergence de la méthode de Newton dépend de la proximité de la racine avec laquelle la supposition initiale est choisie.

Choix de première approximation. Soit un segment contenant la racine. Si l'on choisit comme première approximation la fin du segment pour laquelle , alors les itérations (6) convergent de manière monotone. Riz. La figure 8 correspond au cas où l'extrémité droite du segment a été choisie comme première approximation : (Ici).

Erreur de méthode. L’estimation (7) n’est pas pratique pour une utilisation pratique. En pratique, les estimations d'erreur suivantes sont utilisées :

Critères de fin . L’estimation (8) permet de formuler le critère suivant pour la fin des itérations de la méthode de Newton. Pour une précision donnée, les calculs doivent être effectués jusqu'à ce que l'inégalité soit satisfaite

Exemple. Calculez la racine négative de l'équation en utilisant la méthode de Newton avec une précision de 0,0001. En séparant la racine, vous pouvez vous assurer que la racine est localisée sur l'intervalle. Dans cet intervalle et . Depuis et , alors nous pouvons prendre .

. C'est pourquoi . Donc, en conséquence, nous obtenons ce qui suit, et sur , donc .

Depuis lors

La solution est rédigée au format Word.

Règles de saisie d'une fonction

L’un des moyens les plus efficaces de résoudre numériquement des équations est méthode d'itération. L'essence de cette méthode est la suivante. Soit l'équation f(x)=0.
Remplaçons-le par l'équation équivalente
Choisissons l'approximation initiale de la racine x 0 et substituons-la dans le côté droit de l'équation (1). Ensuite, nous obtenons un numéro

x 1 =φ(x 0). (2)

x n =φ(x n-1) (n=1,2..). (3)

Ou ξ=φ(ξ).
Ainsi, la limite ξ est la racine de l’équation (1) et peut être calculée à l’aide de la formule (3) avec n’importe quel degré de précision.

Riz. 1a Fig. 1b

Riz. 2.

|φ′(x)|>1 - processus divergent

Sur les figures 1a, 1b, au voisinage de la racine |φ′(x)|<1 и процесс итерации сходится. Однако, если рассмотреть случай |φ′(x)|>1, alors le processus d'itération peut être divergent (voir Fig. 2).

Conditions suffisantes pour la convergence de la méthode d'itération

φ′(x n)(x n -x n-1)

Où x n ∈
Ensuite, nous obtenons

|x n+1 -x n |≤φ′(x n)|x n -x n-1 |≤q|x n -x n-1 |

|x 2 -x 1 |≤q|x 1 -x 0 |
|x 3 -x 2 |≤q|x 2 -x 1 |≤q²|x 1 -x 0 |
|x n+1 -x n ≤q n |x 1 -x 0 | (4)

ξ-x n = φ′(c 1)(ξ-x n-1)+φ′(c)(x n -x n-1)
ou
|ξ-x n |≤q|ξ-x n |+q|x n -x n-1 |

, (5)

. (6)

|x n -x n -1 |<ε

Convergence de la méthode d'itération linéaire avec coefficient de convergence α=q. En effet, nous avons
ξ-x n =φ(ξ)-φ n-1 = φ′(c)·(ξ-x n-1), donc |ξ-x n |≤q·|ξ-x n-1 |.

Commentaire. Soit dans un voisinage de la racine ξ∈(a,b) de l'équation x= φ(x) la dérivée φ'(x) conserve un signe constant et l'inégalité |φ'(x)|≤q<1. Тогда, если φ’(x) положительна, то последовательные приближения x n = φ(x n -1) сходятся к корню монотонно.
Si φ’(x) est négatif, alors les approximations successives oscillent autour de la racine.
Considérons une manière de représenter l'équation f(x)=0 sous la forme x= φ(x).
La fonction φ(x) doit être spécifiée telle que |φ’(x)| était petite au voisinage de la racine.
Soit m 1 et M 1 - les valeurs les plus petites et les plus grandes de la dérivée f'(x)
0Remplaçons l'équation f(x)=0 par son équation équivalente
x = x - λf(x).
Posons φ(x) = x- λf(x). Sélectionnons le paramètre λ de telle sorte qu'au voisinage de la racine ξ l'inégalité

0≤|φ′(x)|=|1-λ·f′(x)|≤q≤1

0≤|1-λM 1 |≤|1-λm 1 |≤q

x n = x n -1 – f(x n)/f’(x).

Méthode d'itération dans Excel

Le processus de recherche des zéros d'une fonction à l'aide de la méthode d'itération comprend les étapes suivantes :

1. Obtenez un modèle en utilisant ce service.
2. Spécifiez les intervalles dans les cellules B2, B3.
3. Copiez les lignes d'itération avec la précision requise (colonne D).

Exemple. Trouver la racine de l'équation e -x -x=0, x=∈, ε=0,001 (8)
Solution.
Représentons l'équation (8) sous la forme x=x-λ(e -x -x)
Trouvons la valeur maximale de la dérivée de la fonction f(x)= e - x -x.
max f′(x)=max(-(e -x +1)) ≈ -1,37. Signification . Ainsi, nous résolvons l’équation suivante
x=x+0,73(e-x-x)
Les valeurs des approximations successives sont données dans le tableau.

Résolution d'équations non linéaires

Supposons que nous devions résoudre l'équation

Où
– fonction continue non linéaire.

Les méthodes de résolution d'équations sont divisées en méthodes directes et itératives. Les méthodes directes sont des méthodes qui vous permettent de calculer une solution à l'aide d'une formule (par exemple, trouver les racines d'une équation quadratique).

Les méthodes itératives sont des méthodes dans lesquelles une approximation initiale est spécifiée et une séquence convergente d'approximations vers la solution exacte est construite, chaque approximation suivante étant calculée en utilisant les précédentes.

La solution complète au problème peut être divisée en 3 étapes :

Établir le nombre, la nature et l'emplacement des racines de l'équation (1).

Trouver les valeurs approximatives des racines, c'est-à-dire

indiquer les intervalles dans lesquels les racines pousseront (séparez les racines).

Trouvez la valeur des racines avec la précision requise (précisez les racines).
Il existe différentes méthodes graphiques et analytiques pour résoudre les deux premiers problèmes. La méthode la plus évidente pour séparer les racines de l'équation (1) consiste à déterminer les coordonnées des points d'intersection du graphique de la fonction
avec l'axe des abscisses. Abscisses
points d'intersection du graphique

avec essieu

sont les racines de l'équation (1)
Les intervalles d'isolement pour les racines de l'équation (1) peuvent être obtenus analytiquement, sur la base de théorèmes sur les propriétés des fonctions continues sur un intervalle.
Si par exemple la fonction
continu sur le segment
il existe au moins une racine de l’équation (1) (un nombre impair de racines).

Si la fonction
satisfait les conditions du théorème de Bolzano-Cauchy et est monotone sur cet intervalle, puis sur
il n'y a qu'une seule racine de l'équation (1). Ainsi, l'équation (1) a.
une seule racine si les conditions suivantes sont remplies :

Si une fonction est continûment différentiable sur un intervalle donné, alors on peut utiliser un corollaire du théorème de Rolle, selon lequel il y a toujours au moins un point stationnaire entre une paire de racines. L'algorithme pour résoudre le problème dans ce cas sera le suivant :

Un outil utile pour séparer les racines est également l'utilisation du théorème de Sturm.

La solution du troisième problème est réalisée par différentes méthodes itératives (numériques) : la méthode des dichotomies, la méthode des itérations simples, la méthode de Newton, la méthode des accords, etc.

Exemple Résolvons l'équation
méthode itération simple. Mettons
. Construisons un graphique de la fonction.

Le graphique montre que la racine de notre équation appartient au segment
, c'est à dire.
est le segment d'isolement de la racine de notre équation. Vérifions cela analytiquement, c'est-à-dire réalisation des conditions (2) :

Rappelons que l'équation originale (1) dans la méthode d'itération simple est transformée sous la forme
et les itérations sont effectuées selon la formule :

(3)

Effectuer des calculs à l’aide de la formule (3) s’appelle une itération. Les itérations s'arrêtent lorsque la condition est remplie
, Où - erreur absolue dans la recherche de la racine, ou
, Où -erreur relative.

La méthode d'itération simple converge si la condition est satisfaite
Pour
. Sélection d'une fonction
dans la formule (3) pour les itérations, vous pouvez influencer la convergence de la méthode. Dans le cas le plus simple
avec un signe plus ou moins.

En pratique, on exprime souvent
directement à partir de l’équation (1). Si la condition de convergence n'est pas remplie, transformez-la sous la forme (3) et sélectionnez-la. Représentons notre équation sous la forme
(exprimer x à partir de l'équation). Vérifions la condition de convergence de la méthode :

Pour
. Attention, la condition de convergence n'est pas satisfaite
, nous prenons donc un segment d'isolation racine
. Notons au passage qu'en présentant notre équation sous la forme
, la condition de convergence de la méthode n’est pas remplie :
sur le segment
. Le graphique montre que
augmente plus vite que la fonction
(|tg| angle d'inclinaison de la tangente à
sur le segment
)

Choisissons
. On organise les itérations selon la formule :

Nous organisons par programme le processus d'itération avec une précision donnée :

> fv:=proc(f1,x0,eps)

> k:=0 :

x:=x1+1 :

tandis que abs(x1-x)> eps le fait

x1:=f1(x):

print(evalf(x1,8)):

imprimer(abs(x1-x)) :

:printf("Nombre d'itère.=%d ",k):

fin:

À l'itération 19, nous avons obtenu la racine de notre équation

avec erreur absolue

Résolvons notre équation La méthode de Newton. Les itérations dans la méthode de Newton sont effectuées selon la formule :

La méthode de Newton peut être considérée comme une méthode d'itération simple avec une fonction, alors la condition de convergence de la méthode de Newton s'écrira comme :

.

Dans notre notation
et la condition de convergence est satisfaite sur le segment
, comme on peut le voir sur le graphique :

Rappelons que la méthode de Newton converge à un rythme quadratique et que l'approximation initiale doit être choisie suffisamment proche de la racine. Faisons les calculs :
, première approximation, . On organise les itérations selon la formule :

Nous organisons par programme le processus d'itération avec une précision donnée. A l'itération 4 on obtient la racine de l'équation

Avec
Nous avons examiné les méthodes de résolution d'équations non linéaires en utilisant les équations cubiques comme exemple. Naturellement, ces méthodes résolvent différents types d'équations non linéaires. Par exemple, résoudre l'équation

La méthode de Newton avec
, trouvez la racine de l'équation en [-1.5;-1] :

Exercice: Résoudre des équations non linéaires avec précision

0.

diviser un segment en deux (dichotomie)

itération simple.

Newton (tangentes)

sécantes – accords.

Les options de tâches sont calculées comme suit : le nombre sur la liste est divisé par 5 (
), la partie entière correspond au numéro de l’équation, le reste – au numéro de la méthode.

Exercice:

1) En utilisant la méthode d'itération, résolvez le système

2) En utilisant la méthode de Newton, résolvez le système

équations non linéaires avec une précision de 0,001.

Tâche n°1 À l'aide de la méthode d'itération, résoudre un système d'équations non linéaires avec une précision de 0,001.

Partie théorique.

Méthode d'itération c'est une méthode de résolution numérique de problèmes mathématiques. Son essence est de trouver un algorithme de recherche basé sur une approximation connue (valeur approximative) de la valeur souhaitée pour l'approximation suivante, plus précise. Il est utilisé dans le cas où la séquence d'approximations selon l'algorithme spécifié converge.

Cette méthode est aussi appelée méthode des approximations successives, méthode des substitutions répétées, méthode des itérations simples, etc.

La 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 (1643-1727). La recherche d'une solution s'effectue par construction d'approximations successives et repose sur les principes d'itération simple. La méthode a une convergence quadratique. Une amélioration de la méthode est la méthode des accords et des tangentes. La méthode de Newton peut également être utilisée pour résoudre des problèmes d'optimisation dans lesquels il est nécessaire de déterminer le zéro de la dérivée première ou du gradient dans le cas d'un espace multidimensionnel. Raisonnement

Pour résoudre l'équation numériquement en utilisant la méthode d'itération simple, elle doit être réduite à la forme suivante : , où est la cartographie de contraction.

Pour la meilleure convergence de la méthode, la condition doit être satisfaite au point de la prochaine approximation. La solution de cette équation est recherchée sous la forme , alors :

En supposant que le point d'approximation est "assez proche" de la racine et que la fonction donnée est continue, la formule finale pour est :

Compte tenu de cela, la fonction est définie par l'expression :

Cette fonction au voisinage de la racine effectue une cartographie compressive, et l'algorithme pour trouver une solution numérique à l'équation se réduit à une procédure de calcul itérative :

.

Options de tâche

№1. 1)
2)

№2. 1)
2)

№3. 1)
2)

№4. 1)
2)

№5. 1)
2)

№6. 1)
2)

№7. 1)
2)

№8. 1)
2)

№9. 1)
2)

№10.1)
2)

№11.1)
2)

№12.1)
2)

№13.1)
2)

№14.1)
2)

№15.1)
2)

№16.1)
2)

№17.1)
2)

№18.1)
2)

№19.1)
2)

№20.1)
2)

№21. 1)
2)

№22. 1)
2)

№23. 1)
2)

№24. 1)
2)

№25. 1)
2)

№26. 1)
2)

№27. 1)
2)

№28. 1)
2)

№29. 1)
2)

№30. 1)
2)

Exemple de devoir

№1. 1)
2)

Un exemple de résolution d'un système d'équations non linéaires à l'aide de la méthode d'itération

Réécrivons ce système sous la forme :

Nous séparons graphiquement les racines (Fig. 1). Sur le graphique, nous voyons que le système a une solution, contenue dans la région D: 0<X<0,3;-2,2<oui<-1,8.

Assurons-nous que la méthode d'itération est applicable pour affiner la solution du système, pour laquelle nous l'écrivons sous la forme suivante :

Depuis , alors nous avons dans la région D

+ = ;

+ =

Les conditions de convergence sont donc satisfaites.

Tableau n°2

P.
	0,15	-2	-0,45	-0,4350	-0,4161	-0,1384
	0,1616	-2,035	-0,4384	-0,4245	-0,4477	-0,1492
	0,1508	-2.0245	-0,4492	-0,4342	-0,4382	-0,1461
	0.1539	-2,0342.	-0,4461	-0.4313	-0,4470	-0,1490
	0.1510	-2,0313	-0,4490	-0,4341	-0,4444	-0.1481
	0,1519	-2,0341	-0,4481	-0,4333	-0,4469	-0,1490
	0,1510	-2.0333	-0.449	-0,4341	-0.4462	-0,1487
	0.1513	-2.0341	-0,4487	-0,4340	-0,4469	-0.1490
	0.1510	-2,0340

Nous prenons comme premières approximations xo=0,15, oui 0 =-2.

(Tableau n°2). Alors la réponse s'écrira :

Un exemple de résolution d'un système d'équations non linéaires à l'aide de la méthode de Newton

Nous séparons graphiquement les racines (Fig. 2). Pour créer des graphiques de fonctions, créons un tableau de valeurs de fonctions et inclus dans les première et deuxième équations (tableau I).

Les valeurs de x peuvent être prises en fonction des conditions suivantes : à partir de la première équation 1≤1,2х+0,4≤1, c'est à dire. 1,16≤х≤0,5; à partir de la deuxième équation, c'est-à-dire . Ainsi, .

Le système a deux solutions. Précisons l'un d'eux, appartenant à la région D : 0,4<X<0,5;

0,76<oui<0,73. За начальное приближение примем Имеем:

Tableau n°3

Nous affinons les racines en utilisant la méthode de Newton :

Où ; ;

;
;

Tous les calculs sont effectués selon le tableau 3

Questions de contrôle

1) Présenter sur le graphique des cas possibles de résolution d'un système de deux équations non linéaires.

2) Formuler l'énoncé du problème de résolution d'un système d'équations n-linéaires.

3) Donner les formules d'itération de la méthode d'itération simple dans le cas d'un système de deux équations non linéaires.

4) Formuler un théorème sur la convergence locale de la méthode de Newton.

5) Énumérez les difficultés qui surviennent lors de l'utilisation pratique de la méthode de Newton.

6) Expliquez comment la méthode de Newton peut être modifiée.

7) Dessiner sous forme de schémas fonctionnels un algorithme de résolution de systèmes de deux équations non linéaires en utilisant des méthodes d'itération simple et de Newton.

Travail de laboratoire n°3

La méthode des itérations simples, également appelée méthode d'approximation successive, est un algorithme mathématique permettant de trouver la valeur d'une quantité inconnue en l'affinant progressivement. L'essence de cette méthode est que, comme son nom l'indique, en exprimant progressivement les résultats suivants à partir de l'approximation initiale, des résultats de plus en plus raffinés sont obtenus. Cette méthode est utilisée pour trouver la valeur d'une variable dans une fonction donnée, ainsi que pour résoudre des systèmes d'équations, à la fois linéaires et non linéaires.

Voyons comment cette méthode est implémentée lors de la résolution des SLAE. La méthode d'itération simple a l'algorithme suivant :

1. Vérification du respect de la condition de convergence dans la matrice d'origine. Théorème de convergence : si la matrice originale du système a une dominance diagonale (c'est-à-dire que dans chaque ligne, les éléments de la diagonale principale doivent être supérieurs en valeur absolue à la somme des éléments des diagonales secondaires en valeur absolue), alors le simple la méthode d’itération est convergente.

2. La matrice du système d'origine n'a pas toujours une prédominance diagonale. Dans de tels cas, le système peut être converti. Les équations qui satisfont à la condition de convergence ne sont pas touchées et des combinaisons linéaires sont faites avec celles qui ne le font pas, c'est-à-dire multiplier, soustraire, ajouter des équations les unes aux autres jusqu'à obtenir le résultat souhaité.

Si dans le système résultant il y a des coefficients gênants sur la diagonale principale, alors des termes de la forme avec i * x i sont ajoutés aux deux côtés d'une telle équation, dont les signes doivent coïncider avec les signes des éléments diagonaux.

3. Transformation du système résultant sous forme normale :

x - =β - +α*x -

Cela peut être fait de plusieurs manières, par exemple comme ceci : à partir de la première équation, exprimer x 1 en termes d'autres inconnues, à partir de la seconde - x 2, à partir de la troisième - x 3, etc. Dans ce cas on utilise les formules :

α ij = -(une ij / une ii)

je = b je /une ii
Vous devez à nouveau vous assurer que le système de forme normale résultant répond à la condition de convergence :

∑ (j=1) |α ij |≤ 1, tandis que i= 1,2,...n

4. Commençons par appliquer, en fait, la méthode des approximations successives elle-même.

x (0) est l'approximation initiale, nous exprimerons x (1) à travers elle, puis nous exprimerons x (2) à travers x (1). La formule générale sous forme matricielle ressemble à ceci :

x (n) = β - +α*x (n-1)

Nous calculons jusqu'à ce que nous obtenions la précision requise :

max |x je (k)-x je (k+1) ≤ ε

Alors, mettons en pratique la méthode d’itération simple. Exemple:
Résoudre SLAE :

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 avec précision ε=10 -3

Voyons si les éléments diagonaux prédominent en module.

On voit que seule la troisième équation satisfait à la condition de convergence. On transforme le premier et le second, et on ajoute le second à la première équation :

7,6x1+0,6x2+2,4x3=3

Du troisième on soustrait le premier :

2,7x1+4,2x2+1,2x3=2

Nous avons converti le système d'origine en un système équivalent :

7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4

Ramenons maintenant le système à sa forme normale :

x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3 = 0,8511-0,383x1-0,5319x2

On vérifie la convergence du processus itératif :

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, soit la condition est remplie.

0,3947
Supposition initiale x(0) = 0,4762
0,8511

En substituant ces valeurs dans l'équation de forme normale, nous obtenons les valeurs suivantes :

0,08835
x(1) = 0,486793
0,446639

En substituant de nouvelles valeurs, nous obtenons :

0,215243
x(2) = 0,405396
0,558336

Nous continuons les calculs jusqu'à ce que nous approchions des valeurs qui satisfont à la condition donnée.

x(7) = 0,441091

Vérifions l'exactitude des résultats obtenus :

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

Les résultats obtenus en substituant les valeurs trouvées dans les équations d'origine satisfont pleinement aux conditions de l'équation.

Comme nous pouvons le constater, la méthode d'itération simple donne des résultats assez précis, mais pour résoudre cette équation, nous avons dû consacrer beaucoup de temps et effectuer des calculs fastidieux.