Solution numérique d'équations et leurs systèmes consistent en une détermination approximative des racines d'une équation ou d'un système d'équations et sont utilisés dans les cas où la méthode de solution exacte est inconnue ou demande beaucoup de travail.
Formulation du problème[ | ]
Considérons les méthodes de résolution numérique d'équations et de systèmes d'équations :
f (x 1 , x 2 , … , x n) = 0 (\displaystyle f(x_(1),x_(2),\ldots,x_(n))=0)( f 1 (x 1 , x 2 , … , x n) = 0 … f n (x 1 , x 2 , … , x n) = 0 (\displaystyle \left\((\begin(array)(lcr)f_(1 )(x_(1),x_(2),\ldots ,x_(n))&=&0\\\ldots &&\\f_(n)(x_(1),x_(2),\ldots ,x_( n))&=&0\end(array))\right.)
Méthodes numériques pour résoudre des équations[ | ]
Montrons comment vous pouvez résoudre le système d'équations d'origine sans recourir à des méthodes d'optimisation. Si notre système est un SLAE, il convient de recourir à des méthodes telles que la méthode Gaussienne ou la méthode Richardson. Cependant, nous partirons toujours de l'hypothèse que la forme de la fonction nous est inconnue, et nous utiliserons l'une des méthodes itératives de solution numérique. Parmi la grande variété de celles-ci, nous choisirons l’une des plus connues : la méthode de Newton. Cette méthode, quant à elle, est basée sur le principe de la cartographie compressive. C’est pourquoi l’essence de cette dernière sera d’abord exposée.
Cartographie compressive[ | ]
Définissons la terminologie :
On dit que la fonction remplit cartographie compressive sur si
Alors le théorème principal suivant est valide :
| Théorème de Banach (principe des cartographies de contraction). Si φ (\ displaystyle \ varphi)- affichage compressé activé [ une , b ] (\style d'affichage), Que: |
Il résulte du dernier point du théorème que le taux de convergence de toute méthode basée sur des applications de contraction n'est rien de moins que linéaire.
Expliquons la signification du paramètre α (\ displaystyle \ alpha) pour le cas d'une variable. D'après le théorème de Lagrange on a :
φ (x) ∈ C 1 [ une , b ] .< x 2 ∃ ξ ∈ (x 1 , x 2) : φ ′ (ξ) (x 2 − x 1) = φ (x 2) − φ (x 1) {\displaystyle \varphi (x)\in C^{1}.\quad \forall x_{1},x_{2}\in (a,\;b),\quad x_{1}∀ x 1 , x 2 ∈ (une , b) , x 1 Il s'ensuit queα ≈ | φ ′ (ξ) |
(\displaystyle \alpha \approx |\varphi "(\xi)|)[ | ]
. Ainsi, pour que la méthode converge, il suffit que méthode d'approximations successives ou par méthode d'itération simple. Cependant, l’équation peut être transformée en une carte de contraction ayant la même racine de différentes manières. Cela donne lieu à un certain nombre de méthodes particulières qui présentent des taux de convergence à la fois linéaires et plus élevés.
En relation avec SLAU[ | ]
Considérez le système :
( une 11 x 1 + … + une 1 n x n = b 1 … une n 1 x 1 + … + une n n x n = b n (\displaystyle \left\((\begin(array)(ccc)a_(11)x_(1)+ \ldots +a_(1n)x_(n)&=&b_(1)\\\ldots &&\\a_(n1)x_(1)+\ldots +a_(nn)x_(n)&=&b_(n) \end(array))\right.)
Pour cela, le calcul itératif ressemblera à ceci :
(x 1 x 2 ⋮ x n) je + 1 = (une 11 + 1 une 12 … une 1 n une 21 une 22 + 1 … une 2 n ⋮ ⋮ ⋱ ⋮ une n 1 une n 2 … une n n + 1) (x 1 x 2 ⋮ x n) je − (b 1 b 2 ⋮ b n) (\displaystyle \left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end (tableau))\right)^(i+1)=\left((\begin(array)(cccc)a_(11)+1&a_(12)&\ldots &a_(1n)\\a_(21)&a_( 22)+1&\ldots &a_(2n)\\\vdots &\vdots &\ddots &\vdots \\a_(n1)&a_(n2)&\ldots &a_(nn)+1\end(array))\right )\left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end(array))\right)^(i)-\left( (\begin(array)(c)b_(1)\\b_(2)\\\vdots \\b_(n)\end(array))\right))
La méthode convergera avec la vitesse linéaire si ‖ une 11 + 1 … une 1 n ⋮ ⋱ ⋮ une n 1 … une n n + 1 ‖< 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}
Les doubles barres verticales indiquent une certaine norme de la matrice.
Solution de l'équation f(x)=0 par la méthode de Newton, première approximation : x 1 =a.
Méthode de Newton (méthode de la tangente)[ | ]
Cas unidimensionnel[ | ]
Optimiser la transformation de l'équation d'origine f (x) = 0 (\ displaystyle f (x) = 0) dans un affichage compressif x = φ (x) (\displaystyle x=\varphi (x)) permet d'obtenir une méthode avec un taux de convergence quadratique.
Pour que la cartographie soit la plus efficace possible, il est nécessaire qu'au moment de la prochaine itération x ∗ (\displaystyle x^(*)) effectué φ ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=0). Nous chercherons une solution à cette équation sous la forme φ (x) = x + α (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), Alors:
φ ′ (x ∗) = 1 + α ′ (x ∗) f (x ∗) + α (x ∗) f ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=1+ \alpha "(x^(*))f(x^(*))+\alpha (x^(*))f"(x^(*))=0)Utilisons le fait que f (x) = 0 (\ displaystyle f (x) = 0), et nous obtenons la formule finale pour α (x) (\ displaystyle \ alpha (x)):
α (x) = − 1 f ′ (x) (\displaystyle \alpha (x)=-(\frac (1)(f"(x))))En tenant compte de cela, la fonction de compression prendra la forme :
φ (x) = x − f (x) f ′ (x) (\displaystyle \varphi (x)=x-(\frac (f(x))(f"(x))))Puis l'algorithme pour trouver une solution numérique à l'équation f (x) = 0 (\ displaystyle f (x) = 0) se réduit à une procédure de calcul itérative :
x je + 1 = x je − f (x je) f ′ (x je) (\displaystyle x_(i+1)=x_(i)-(\frac (f(x_(i)))(f"(x_(i) ))))1. Soit un segment contenant une racine de l'équation f(x) = 0. La fonction f est une fonction continûment différentiable sur ce segment (f(x)ОC 1 ). Si ces conditions sont remplies, la méthode d’itération simple peut être utilisée.
2. A l'aide de la fonction f(x), on construit une fonction j(x) qui satisfait trois conditions : elle doit être continûment dérivable (j(x)ОC 1 ), telle que l'équation x = j(x) est équivalent à l'équation f(x)=0 ; devrait aussi traduire un segment en toi.
On dira que la fonction j ( X ) traduit le segment [ un , b ] en toi, si pour quelqu'un X Î [ un , b ], oui = j ( X ) appartient également[ un , b ] ( oui Î [ un , b ]).
La troisième condition est imposée à la fonction j(x) :
Formule de méthode : x n +1 = j(xn).
3. Si ces trois conditions sont remplies pour toute première approximation x 0 О séquence d'itérations x n +1 = j(x n) converge vers la racine de l'équation : x = j(x) sur le segment ().
En règle générale, comme x 0 l'une des extrémités est sélectionnée.
,
où e est la précision spécifiée
Nombre x n +1 lorsque la condition d'arrêt du processus itératif est remplie, il est valeur approximative de la racine de l'équation f(x) = 0 sur le segment , trouvé par une méthode d'itération simple avec précision e .
Construire un algorithme pour clarifier la racine de l'équation : x 3 + 5x – 1 = 0 sur un segment en utilisant la méthode d'itération simple avec une précision e .
1. Fonction f(x) = x3 +5x-1 est continûment différentiable sur l'intervalle contenant une racine de l'équation.
2. La plus grande difficulté de la méthode d'itération simple est la construction d'une fonction j(x) qui satisfait toutes les conditions :
Considérer: 
.
Équation x = j 1 (x) est équivalent à l'équation f(x) = 0, mais la fonction j 1 (x) n'est pas continûment dérivable sur l'intervalle.
Riz. 2.4. Graphique de la fonction j 2 (x)
D’un autre côté donc, . Par conséquent : est une fonction continûment différentiable. Notez que l'équation : x = j 2 (x) est équivalente à l'équation f(x) = 0 . D'après le graphique (Fig. 2.4), il est clair que la fonction j 2 (x) transforme le segment en lui-même.
La condition selon laquelle la fonction j(x) prend le segment en elle-même peut être reformulée ainsi : soit le domaine de définition de la fonction j(x), et soit le domaine de variation de j(x).
Si le segment appartient au segment , alors la fonction j(x) prend le segment pour lui-même.
, 
.
Toutes les conditions pour la fonction j(x) sont satisfaites.
Formule de processus itératif : x n +1 = j 2(xn).
3. Première approximation : x 0 = 0.
4. Condition d'arrêt du processus itératif :
Riz. 2.5. Signification géométrique de la méthode d'itération simple
.
Si cette condition est remplie x n +1 – valeur approximative de la racine sur le segment, trouvé par simple itération avec précision e. En figue. 2.5. L'application de la méthode d'itération simple est illustrée.
Théorème de convergence et estimation de l'erreur
Laissez le segment contient une racine de l'équation x = j(x), fonction j(x ) est continûment différentiable sur l'intervalle , traduit le segment en lui-même, et la condition est remplie:
.
Alors pour toute première approximation x 0 О sous-séquence converge vers la racine de l'équation oui = j(x ) sur le segment et l'estimation de l'erreur est juste:
.
Stabilité de la méthode d'itération simple. Lorsque les conditions du théorème de convergence sont remplies, l’algorithme de la méthode d’itération simple est stable.
Complexité de la méthode d'itération simple. La quantité de mémoire informatique requise pour mettre en œuvre la méthode d’itération simple est insignifiante. A chaque étape, vous devez stocker x n , xn+1 , q Et e.
Estimons le nombre d'opérations arithmétiques nécessaires pour mettre en œuvre la méthode d'itération simple. Écrivons une estimation du nombre n 0 = n 0 (e) telle que pour tout n ³ n 0 l'inégalité est vraie : 
De cette estimation, il s’ensuit que plus q est proche de un, plus la méthode converge lentement.
Commentaire. Il n’existe pas de règle générale pour construire j(x) à partir de f(x) de manière à ce que toutes les conditions du théorème de convergence soient satisfaites. L'approche suivante est souvent utilisée : la fonction j(x) = x + k× f(x) est choisie comme fonction j, où k – constante.
Lors de la programmation de la méthode d'itération simple, l'arrêt du processus itératif nécessite souvent la réalisation simultanée de deux conditions :
Et .
Toutes les autres méthodes itératives que nous considérerons sont des cas particuliers de la méthode d’itération simple. Par exemple, quand 
La méthode de Newton est un cas particulier de la méthode des itérations simples.
La méthode d'itération simple consiste à remplacer l'équation d'origine par une équation équivalente :
Que l'approximation initiale de la racine soit connue x = x0. En le substituant au côté droit de l'équation (2.7), nous obtenons une nouvelle approximation 
, alors de la même manière on obtient 
etc.:
. (2.8)
 |
Dans toutes les conditions, le processus itératif ne converge pas vers la racine de l'équation X. Examinons de plus près ce processus. La figure 2.6 montre une interprétation graphique d’un processus convergent et divergent à sens unique. La figure 2.7 montre des processus convergents et divergents bidirectionnels. Un processus divergent se caractérise par une augmentation rapide des valeurs de l'argument et de la fonction et la fin anormale du programme correspondant.
 |
Avec un processus bidirectionnel, le cycle est possible, c'est-à-dire la répétition sans fin des mêmes valeurs de fonction et d'argument. Le bouclage sépare un processus divergent d’un processus convergent.
Il ressort clairement des graphiques que pour les processus unilatéraux et bilatéraux, la convergence vers la racine est déterminée par la pente de la courbe près de la racine. Plus la pente est faible, meilleure est la convergence. Comme on le sait, la tangente de la pente d'une courbe est égale à la dérivée de la courbe en un point donné.
Par conséquent, plus le nombre près de la racine est petit, plus le processus converge rapidement.
Pour que le processus d’itération soit convergent, l’inégalité suivante doit être satisfaite au voisinage de la racine :
Le passage de l'équation (2.1) à l'équation (2.7) peut s'effectuer de diverses manières selon le type de fonction f(x). Dans une telle transition, il est nécessaire de construire la fonction de manière à ce que la condition de convergence (2.9) soit satisfaite.
Considérons l'un des algorithmes généraux de transition de l'équation (2.1) à l'équation (2.7).
Multiplions les côtés gauche et droit de l'équation (2.1) par une constante arbitraire b et ajoutez l'inconnu aux deux parties X. Dans ce cas, les racines de l'équation d'origine ne changeront pas :
Introduisons la notation 
et passons de la relation (2.10) à l'équation (2.8).
 |
Choix arbitraire de constante b assurera la réalisation de la condition de convergence (2.9). Le critère de fin du processus itératif sera la condition (2.2). La figure 2.8 montre une interprétation graphique de la méthode des itérations simples utilisant la méthode de représentation décrite (les échelles le long des axes X et Y sont différentes).
Si une fonction est choisie sous la forme , alors la dérivée de cette fonction sera . La vitesse de convergence la plus élevée sera à , alors 
et la formule d'itération (2.11) se transforme en formule de Newton. Ainsi, la méthode de Newton présente le plus haut degré de convergence de tous les processus itératifs.
L'implémentation logicielle de la méthode d'itération simple est réalisée sous la forme d'une procédure de sous-programme Itéras(PROGRAMME 2.1).
L'ensemble de la procédure consiste pratiquement en un cycle Répéter... Jusqu'à, mettant en œuvre la formule (2.11) prenant en compte la condition d'arrêt du processus itératif (formule (2.2)).
La procédure dispose d'une protection intégrée contre les boucles en comptant le nombre de boucles à l'aide de la variable Niter. Dans les cours pratiques, vous devez vous assurer, en exécutant le programme, comment le choix du coefficient affecte b et première approximation dans le processus de recherche de la racine. Lors du changement du coefficient b la nature du processus itératif pour la fonction étudiée change. Il devient d'abord bilatéral, puis boucle (Fig. 2.9). Échelles des axes X Et Oui sont différents. Une valeur encore plus grande du module b conduit à un processus divergent.
Comparaison des méthodes de solution approximative d'équations
Une comparaison des méthodes décrites ci-dessus pour la résolution numérique d'équations a été réalisée à l'aide d'un programme qui permet d'observer le processus de recherche de la racine sous forme graphique sur l'écran du PC. Les procédures incluses dans ce programme et mettant en œuvre les méthodes comparées sont données ci-dessous (PROGRAMME 2.1).
Riz. 2.3-2.5, 2.8, 2.9 sont des copies de l'écran du PC à la fin du processus d'itération.
Dans tous les cas, l'équation quadratique x 2 -x-6 = 0 a été prise comme fonction étudiée, ayant une solution analytique x 1 = -2 et x 2 = 3. L'erreur et les approximations initiales ont été supposées égales pour toutes les méthodes. Résultats de recherche racine x= 3, présentés sur les figures, sont les suivants. La méthode de dichotomie converge la plus lentement - 22 itérations, la plus rapide est la méthode d'itération simple avec b = -0,2 - 5 itérations. Il n'y a ici aucune contradiction avec l'affirmation selon laquelle la méthode de Newton est la plus rapide.
Dérivée de la fonction étudiée au point X= 3 est égal à -0,2, c'est-à-dire que le calcul dans ce cas a été effectué pratiquement par la méthode de Newton avec la valeur de la dérivée au point de la racine de l'équation. Lors du changement du coefficient b le taux de convergence diminue et le processus progressivement convergent se déroule d'abord par cycles puis devient divergent.
