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
Et

, puis d'après le théorème de Bolzano-Cauchy, 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
. 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.

TRAVAUX DE LABORATOIRE N° 3-4.

Option n°5.

Objectif du travail : apprendre à résoudre des systèmes d'équations non linéaires (SNE) en utilisant la méthode d'itération simple (SI) et la méthode de Newton à l'aide d'un ordinateur.

1. Étudiez le MPI et la méthode de Newton pour résoudre des systèmes d’équations non linéaires.

2. À l’aide d’un exemple précis, apprenez la procédure de résolution de systèmes d’équations non linéaires avec le MPI et la méthode de Newton à l’aide d’un ordinateur.

3. Créez un programme et utilisez-le pour résoudre un système d’équations avec une précision de .

EXEMPLE DE PERFORMANCE DE TRAVAIL

Exercice.

1. Résolvez analytiquement le SNE :

2. Construire des formules de travail de la méthode MPI et de Newton pour la solution numérique du système en première approximation : .

3. Composez un programme dans n'importe quel langage de programmation qui implémente le processus itératif construit.

Solution.

Méthode analytique.

La solution analytique du SDE est constituée des points et .

Méthode d'itérations simples (SIM).

Pour construire des formules MPI fonctionnelles pour la solution numérique du système, il faut d'abord la mettre sous la forme :

Pour ce faire, multipliez la première équation du système par une constante inconnue, la seconde par , puis additionnez-les et ajoutez-les aux deux côtés de l'équation. On obtient la première équation du système transformé :

Nous déterminons les constantes inconnues à partir de conditions suffisantes pour la convergence du processus itératif :

Écrivons ces conditions plus en détail :

En supposant que les expressions sous le signe du module sont égales à zéro, on obtient un système d'équations algébriques linéaires (SLAE) d'ordre 4 à 4 inconnues :

Pour résoudre le système, il faut calculer les dérivées partielles :

Alors le SLAE s’écrira ainsi :

A noter que si les dérivées partielles changent peu au voisinage de l'approximation initiale, alors :

Alors le SLAE s’écrira ainsi :

La solution à ce système réside dans les points , , , . Ensuite, les formules de travail du MPI pour résoudre le SNL prendront la forme :

Pour une mise en œuvre sur ordinateur, les formules de travail peuvent être réécrites comme suit :

Le processus itératif peut être démarré en définissant l'approximation initiale x 0 =-2, y 0 =-4. Le processus se termine lorsque deux conditions sont remplies simultanément : et . Dans ce cas, les valeurs et sont une valeur approximative d'une des solutions du SNL.

La méthode de Newton.

Construire des formules de travail pour la méthode de Newton sous la forme

où , il faut :

1. Trouvez la matrice des dérivées partielles :

2. Trouvez le déterminant de cette matrice :

3. Définissez la matrice inverse :

Après avoir effectué la transformation :

On obtient la formule de travail de la méthode de Newton pour l’implémentation sur ordinateur :

Schéma fonctionnel Le MPI et la méthode de Newton pour résoudre le SLE sont présentés à la figure 1.

Fig.1 Schémas de MPI et méthode de Newton.

Textes du programme :

Programme P3_4 ; (Itérations)

utilise Crt;

var n : entier ;

clrscr;

xn:=x-(x-y+2)+(1/2)*(x*y-3);

yn:=y+(2/3)*(x-y+2)+(1/6)*(x*y-3);

écrire (n:3, x:9:5, xn:9:5, (xn-x):9:5, y:9:5, yn:9:5, (yn-y):9:5) ;

n:=n+1;

jusqu'à (abdos (x-zx)<=eps) and (abs(y-zy)<=eps);

lire;

2) Méthode de Newton :

Programme P3_4 ; (Newton)

utilise Crt;

var n : entier ;

x0,x,xn,y0,y,yn,eps,zx,zy:réel ;

clrscr;

n:=0; x0:=-2; x:=x0; y0:=-4; y:=y0; eps :=0,001 ;

writeln(" n x(i) x(i+1) x(i+1)-x(i) y(i) y(i+1) y(i+1)-y(i) ");

xn:=x-(1/(x+y))*(x*x-x*y+2*x+x-y+2);

yn:=y-(1/(x+y))*(x*y*(-y)-3*(-y)+x*y-3);

écrire (n:3, x:9:5, xn:9:5, abs(xn-x):9:5, y:9:5, yn:9:5, abs(yn-y):9 : 5);

n:=n+1;

jusqu'à (abdos (x-zx)<=eps) and (abs(y-zy)<=eps);

Résultats de l'exécution du programme :

· Fig. 2 – un programme fonctionnant selon la méthode des itérations simples ;

· Fig. 3 – un programme fonctionnant selon la méthode de Newton.

Fig.2 Réponse : x(16)≈-3,00023, y(16)≈-1,00001

Fig.3 Réponse : x(8)≈-3,00000, y(8)≈-1,00000

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 ont des signes différents. 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 , à laquelle 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

L'équation tangente sous forme générale a la représentation suivante :

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 trouver les racines d'équations très 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 comment cela 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. Le programme, comme il se doit, 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 .

Étant donné que 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), une plus grande précision peut être obtenue 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 méthode 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.

Département de chimie physique SFU (RSU)
METHODES NUMERIQUES ET PROGRAMMATION
Matériel pour le cours magistral
Conférencier – Art. Tour. Chtcherbakov I.N.

Systèmes d'équations non linéaires

Lors de la résolution de problèmes de modélisation du comportement de systèmes chimiques, il est souvent nécessaire de résoudre des systèmes d'équations non linéaires par rapport aux variables. Systèmes n

Les équations linéaires à n inconnues x 1, x 2, ..., x n s'écrivent généralement comme suit :

où F 1, F 2,…, F n sont des fonctions de variables indépendantes, y compris les fonctions non linéaires par rapport aux inconnues.

Comme dans le cas des systèmes d'équations linéaires, la solution du système est un vecteur (ou des vecteurs) (X *), qui, lors de la substitution, transforme simultanément toutes les équations du système en identités.

Un système d'équations peut n'avoir aucune solution, une solution unique, un nombre fini ou infini de solutions. La question du nombre de solutions doit être résolue pour chaque problème spécifique séparément.

Considérons plusieurs des méthodes itératives les plus simples pour résoudre des systèmes d'équations non linéaires, à savoir la méthode d'itération simple, la méthode Seidel et la méthode de Newton.

Méthode d'itération simple

Pour mettre en œuvre cette méthode, le système d'équations à résoudre doit être amené à la forme suivante par transformations algébriques, exprimant une variable de chaque équation comme suit :

remplacez-le dans le système d’équations transformé.

De la première équation, une nouvelle approximation de la première variable est obtenue, de la seconde - la seconde, etc. La valeur raffinée résultante des variables est à nouveau substituée dans ces équations, etc. Ainsi, à la (i+1)ème étape de la procédure itérative que nous avons

Méthode Seidel

La modification par Seidel de l'algorithme d'itération simple consiste à utiliser des valeurs raffinées de variables déjà à l'étape d'itération en cours.

Ainsi, pour clarifier les valeurs de la première variable, seules les valeurs de l'étape précédente sont utilisées, pour la deuxième variable - la valeur x 1 de l'étape en cours, et le reste - de la précédente, etc. : Méthode Newton-Raphson 1 , Méthode Newton-Raphson 2 , La base mathématique de la méthode est la linéarisation des fonctions F Fn(les côtés gauches des équations se formant) en développant une série de Taylor au voisinage du point d'approche initiale de la solution et en négligeant tous les termes de la série sauf les termes linéaires par rapport à

incréments

variables. Méthode Newton-Raphson 1 , Méthode Newton-Raphson 2 Considérons la méthode en utilisant l'exemple d'un système de deux équations à deux inconnues :

Linéarisons les fonctions

en développant une série de Taylor près d'un certain point (approximation initiale) et en négligeant tous les termes de la série sauf ceux linéaires par rapport aux incréments de variables.

Rappelons que pour une fonction d'une variable, le développement de la série de Taylor au voisinage d'un point x 0 a la forme suivante :

après avoir négligé tous les termes sauf celui linéaire :

Pour une fonction à plusieurs variables, le développement s'effectue de la même manière. Méthode Newton-Raphson Pour trouver une solution au système d’équations, choisissons une première approximation

Écrivons pour la fonction

1 Partie linéaire à 2 variables du développement de la série de Taylor au voisinage d'un point sélectionné x 1 pour la deuxième équation, de même x 2 Si les valeurs des variables

Et

sont une solution, alors les deux équations du système doivent disparaître, nous assimilons donc les développements résultants à zéro.

Par souci de concision, nous introduisons la notation suivante : Méthode Newton-Raphson Incrément de la i-ième variable

La valeur de la première dérivée partielle de la fonction

j par variable x i à la valeur des variables

– la valeur de la j-ème fonction avec les valeurs correspondantes des variables, c'est-à-dire l'écart de la j-ème équation.

On obtient un système d'équations linéaires 2 x 2 par rapport à l'incrément des variables Ou, sous forme matricielle, où la matrice des valeurs des dérivées partielles est appelée matrice de Jacobi (ou

Jacobien

). La solution de ce système donne un vecteur de corrections à l'approximation initiale.

1. Une première approximation est sélectionnée, le système est réduit à sa forme normale et les dérivées partielles des membres droits des équations du système par rapport à toutes les variables sont trouvées sous forme analytique.

2. La matrice jacobienne des valeurs des dérivées partielles au point de première approximation est calculée

3. Un système d'équations linéaires est résolu pour des incréments de variables.

4. le vecteur d'incrément est ajouté au vecteur d'approximation initial

5. La condition de convergence est vérifiée et, si elle n'est pas réalisée, la procédure est répétée à partir de l'étape 2.

La méthode est facilement généralisable à un système d’équations de n’importe quelle dimension.

Pour la fonction F 1 n variables partie linéaire du développement de la série de Taylor au voisinage d'un point écrit comme ça

Après avoir décomposé toutes les équations du système et utilisé la notation introduite précédemment, après la transformation on obtient un système d'équations linéaires d'ordre n par rapport à l'incrément des variables Δ x i

– la valeur de la j-ème fonction avec les valeurs correspondantes des variables, c'est-à-dire l'écart de la j-ème équation.

Sous forme abrégée, on peut l'écrire ainsi - (F" )(Δ x ) = - (F ) , où la matrice des valeurs des dérivées partielles - (F" ) - est appelée Matrice jacobienne ou Ou, sous forme matricielle, systèmes d'équations.

La solution de ce système donne un vecteur de corrections à l'approximation initiale. L'ajouter au vecteur d'approximation initial donne de nouvelles valeurs affinées des variables.

Dérivées partielles nécessaires au calcul Matrices jacobiennes, peut être calculé analytiquement ou, si cela est impossible ou difficile, obtenu à l'aide de formules de différenciation approximative, par exemple, comme le rapport de l'incrément d'une fonction à l'incrément de l'argument

Où épsilon– un nombre assez restreint.

Méthodes de contrôle de la convergence des méthodes itératives
solutions systèmes

La convergence du processus itératif de résolution d'un système d'équations non linéaires peut être contrôlée de plusieurs manières, par exemple :

1. Norme (euclidienne ou -maximum) du vecteur résiduel

2. Norme euclidienne du vecteur des écarts relatifs des variables

3. Vecteur norme-maximum des écarts relatifs

Appliquons la méthode de Newton pour résoudre le système d'équations

Matrice des dérivées partielles (sous forme analytique)

Système d'équations linéaires

Peut être résolu analytiquement ou par la méthode de Cramer ou la méthode d'inversion matricielle. Prenons l'approximation initiale x = 0,15, y = 0,17

Première itération :

Matrice de Jacobi - vecteur de valeurs de fonction Vecteur de corrections calculé Nouvelle approximation x = 0,15 + 0,028704 = 0,178704, y = 0,17 + 0,090926 = 0,260926 Deuxième itération : Vecteur de correction calculé Nouvelle approximation x = 0,196656, y = 0,293359 Troisième itération : Vecteur de correction calculé Nouvelle approximation x = 0,199867, y = 0,299739 Déjà à la 6ème itération, la norme euclidienne du vecteur résiduel est 2,8∙10 -13, la variation relative maximale des variables est 1,6∙10 -12 et la solution converge vers x = 0,2 , y = 0,3 avec une erreur absolue inférieure à 5∙10 -7. La méthode d'itération simple dans les mêmes conditions initiales converge avec une telle précision à la 33ème étape, la modification Seidel - à la 31ème étape. La figure ci-dessous montre un exemple d'organisation des calculs lors de la résolution du système considéré dans MS Excel.
Explications : Les cellules B3 et B4 contiennent les premières approximations de la solution du système (valeurs x 0 et y 0, respectivement). Dans la plage de cellules D3:E4, il existe des formules pour calculer la matrice jacobienne, à condition que x se trouve dans la cellule B3 et y dans la cellule B4 (les formules sont présentées dans la figure ci-dessous). Dans les cellules G3:G4, la valeur du vecteur des résidus de signe négatif est calculée.
Dans la cellule H3, la norme euclidienne du vecteur résiduel est calculée. Dans les cellules I3:I4, un système d'équations linéaires est résolu et le vecteur de corrections de la solution est calculé. Pour ce faire, la matrice des coefficients du système (matrice de Jacobi) est inversée et multipliée par le vecteur colonne des termes libres (vecteur négatif des résidus). La formule dans cette plage de cellules est saisie sous forme de formule matricielle. A proximité - dans la cellule J3 - la norme du vecteur de correction est calculée pour contrôler la convergence (voir les formules dans la figure ci-dessous).
Les valeurs de correction obtenues dans les cellules I3:I4 lors du deuxième cycle d'itération sont ajoutées à l'approximation initiale (dans les cellules B6:B7), puis les calculs sont répétés de la même manière qu'au premier cycle. Les formules saisies aux lignes 6 et 7 de la feuille de calcul peuvent être copiées jusqu'à ce que la précision requise soit atteinte.

Problèmes qui se réduisent à la résolution d'un système d'équations non linéaires

Un exemple de problème utilisant la solution de systèmes d'équations non linéaires est l'approximation d'une fonction spécifiée dans un tableau par des modèles mathématiques non linéaires par rapport aux paramètres. Cela a été décrit en détail plus tôt. Si la fonction d'approximation et ses paramètres de définition un je désigner comme suit Un autre exemple est la recherche d'un extremum (minimum ou maximum) d'une fonction de plusieurs variables. La condition d'un extremum est l'égalité simultanée à zéro de toutes les dérivées partielles de la fonction. Ainsi, il faut résoudre le système d’équations de la forme suivante, qui, dans le cas général, sera non linéaire

La méthode des itérations simples, également appelée méthode des approximations successives, 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. Transformons le premier et le second, et ajoutons 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 originales 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.