Par analogie avec (2.1), le système (5.1) peut être représenté sous la forme équivalente suivante :

où g(x) est une fonction vectorielle itérative de l'argument vectoriel. Les systèmes d'équations non linéaires apparaissent souvent directement sous la forme (5.2) (par exemple, dans les schémas numériques d'équations différentielles, dans ce cas, aucun effort supplémentaire n'est requis pour transformer les équations (5.1) en système (5.2) ; Si nous poursuivons l'analogie avec la méthode d'itération simple pour une équation, alors le processus d'itération basé sur l'équation (5.2) peut être organisé comme suit :

• 1) un vecteur initial x ((,) e 5 o (x 0, UN)(on suppose que x* e 5„(x 0, UN));
• 2) les approximations ultérieures sont calculées à l'aide de la formule

alors le processus d'itération est terminé et

Comme auparavant, nous devons découvrir dans quelles conditions

Discutons de ce problème en effectuant une analyse simple. Nous introduisons d’abord l’erreur de la ième approximation sous la forme e(^ = x(i) - x*. Ensuite, nous pouvons écrire

Remplaçons ces expressions dans (5.3) et développons g(x* + e (/i)) en puissances e(k> au voisinage de x* en fonction de l'argument vectoriel (en supposant que toutes les dérivées partielles de la fonction g(x) sont continues). En tenant compte également du fait que x* = g(x*), on obtient

ou sous forme matricielle

B = (bnm)= I (x*)1 - matrice d'itération.

Si le taux d'erreur ||e®|| est suffisamment petit, alors le deuxième terme du côté droit de l’expression (5.4) peut être négligé, et alors il coïncide avec l’expression (2.16). Par conséquent, la condition de convergence du processus itératif (5.3) vers la solution exacte est décrite par le théorème 3.1.

Convergence de la méthode d'itération simple. Condition nécessaire et suffisante pour la convergence du processus itératif (5.3) :

et une condition suffisante :

Ces conditions ont une importance théorique plutôt que pratique, puisque nous ne connaissons pas x'. Par analogie avec (1.11), on obtient une condition qui peut être utile. Soit x* e 5 o (x 0, UN) et la matrice jacobienne pour la fonction g(x)

existe pour tout x e S n (x 0 , une) (notez que C(x*) = B). Si les éléments de la matrice C(x) satisfont l'inégalité

pour tout x e 5"(x 0, UN), alors la condition suffisante (5.5) est également satisfaite pour toute norme matricielle.

Exemple 5.1 (méthode d'itération simple) Considérons le système d'équations suivant :

Une possibilité de représenter ce système sous une forme équivalente (5.2) est d’exprimer X de la première équation et x2à partir de la deuxième équation :

Alors le schéma d’itération a la forme

La solution exacte est x* e 5„((2, 2), 1). Choisissons le vecteur initial x (0) = (2,2) et ? p = CT 5. Les résultats du calcul sont présentés dans le tableau. 5.1.

Tableau 5.1

Ces résultats montrent que la convergence est assez lente. Afin d’obtenir une caractéristique quantitative de convergence, nous effectuons une analyse simple, en considérant x (1/) comme une solution exacte. La matrice jacobienne C(x) pour notre fonction itérative a la forme

alors la matrice B est approximativement estimée comme

Il est facile de vérifier que ni la condition (5.5) ni la condition (5.6) ne sont satisfaites, mais une convergence a lieu puisque 5(B) ~ 0,8.

Il est souvent possible d’accélérer la convergence de la méthode d’itération simple en modifiant légèrement le processus de calcul. L'idée de cette modification est très simple : calculer nème composantes vectorielles x (A+1) peut être utilisé non seulement (t = n,..., N), mais aussi les composantes déjà calculées du prochain vecteur d'approximation xk^ (/= 1,p - 1). Ainsi, la méthode d’itération simple modifiée peut être représentée comme le schéma d’itération suivant :

Si les approximations générées par le processus itératif (5.3) convergent, alors le processus itératif (5.8) a tendance à converger plus rapidement en raison d'une utilisation plus complète de l'information.

Exemple 5.2 (méthode d'itération simple modifiée) L'itération simple modifiée pour le système (5.7) est représentée par

Comme précédemment, on choisit le vecteur initial x (0) = (2, 2) et g r = = 10-5. Les résultats du calcul sont présentés dans le tableau. 5.2.

Tableau 5.2

I Le grand changement dans l'ordre des calculs a conduit à une réduction de moitié du nombre d'itérations, et donc à une réduction de moitié du nombre d'opérations.

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 également 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).

, .

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. Sur la fig. 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.

Méthodes itératives

Dans les méthodes itératives, les trois étapes suivantes sont supposées : construction pour calculer des approximations successives d'un processus itératif convergeant vers une solution exacte (c'est-à-dire construction d'une séquence de vecteurs convergeant vers une solution exacte ; déterminer le critère de convergence de ce processus, qui permet de déterminer le moment où la précision requise est atteinte ; étude de la vitesse de convergence et optimisation du processus itératif afin de réduire le nombre d'opérations nécessaires pour atteindre la précision requise.

Les méthodes itératives permettent d'obtenir une solution avec une précision prédéterminée si la convergence de la méthode est prouvée. Les méthodes itératives ne fournissent pas une solution strictement précise, puisqu’elle est obtenue comme limite d’une séquence de vecteurs. La méthode directe, en général, donne une solution exacte, mais en raison des erreurs d'arrondi qui se produisent sur tous les ordinateurs, elle ne peut pas être obtenue, et a priori Il est même difficile d’évaluer à quel point cette solution diffère de la solution exacte. En lien avec ce qui précède, les méthodes itératives permettent parfois d'obtenir une solution avec plus de précision que les méthodes directes.

Considérons plusieurs méthodes itératives pour résoudre des équations linéaires.

Méthode d'itération simple

Dans la méthode d'itération simple, le système (2.1) d'équations algébriques linéaires Hache = b se réduit à un système équivalent de la forme

La solution du système (2.9) et, par conséquent, la solution du système original (2.1) est recherchée comme limite d'une séquence de vecteurs à :

k = 0, 1, 2,…,(2.10)

où est l'approximation initiale du vecteur solution.

La condition suffisante pour la convergence de la méthode d’itération simple est déterminée par le théorème suivant.

THÉORÈME 1. Si une norme de la matrice , cohérente avec la norme du vecteur considéré, est inférieure à un (), alors la séquence dans la méthode d'itération simple converge vers la solution exacte du système (2.9) à une vitesse d'au moins que la vitesse de la progression géométrique au dénominateur pour toute première approximation .

PREUVE. Pour prouver le théorème, nous introduisons une erreur. En soustrayant l'égalité (2.10) de la relation, nous obtenons . En ce qui concerne les normes, nous avons

Notez que l'inégalité de l'expression précédente est la condition de cohérence de la norme de la matrice et du vecteur. Si , alors pour tout vecteur d'erreur initiale (ou sinon, pour tout vecteur initial), la norme d'erreur ne tend vers zéro pas plus lentement qu'une progression géométrique de dénominateur .

Si on choisit la norme comme norme de la matrice ou alors pour résoudre la question de la convergence de la méthode d'itération simple, vous pouvez utiliser le corollaire du théorème 1 : la méthode d'itération simple converge si l'une des conditions suivantes est satisfaite pour la matrice :

, je =1,2, …, n,

, j = 1, 2, …, n.(2.11)

La manière la plus simple et la plus courante d'amener un système Hache=bà la forme (2.9), pratique pour les itérations, consiste à sélectionner des éléments diagonaux, avec chacun je-ème l'équation est résolue par rapport à je-ème inconnu:

, je = 1, 2, …, n, (2.12)

et la méthode d’itération simple s’écrira sous la forme

La matrice a alors la forme

.

Un élément de cette matrice peut s'écrire où est le symbole Kronecker. Dans ce cas, la condition suffisante pour la convergence de la méthode d'itération simple peut être formulée comme la condition de prédominance des éléments diagonaux de la matrice UN, qui découle de (2.11) et de la notation de la matrice, soit

je = 1, 2, …, n.

Soulignons encore une fois que les formes considérées de la condition de convergence pour la méthode d'itération sont seulement suffisantes. Leur réalisation garantit la convergence de la méthode, mais leur échec dans le cas général ne signifie pas que la méthode d'itération simple diverge. Une condition nécessaire et suffisante pour la convergence de la méthode d'itération simple est la condition que la partie entière (où est la valeur propre modulo maximale de la matrice UN); cette condition est rarement utilisée dans la pratique informatique.

Passons à la question de l'estimation de l'erreur de solution. Deux relations d'estimation de l'erreur de solution sont intéressantes : la première relie la norme d'erreur à la norme de la différence entre deux approximations successives et ne peut être utilisée pour estimer l'erreur que dans le processus de calculs ; la seconde relie la norme d'erreur aux normes du vecteur d'approximation initiale et au vecteur du terme libre dans le système (2.9). Les relations nécessaires sont données par les deux théorèmes suivants.

THÉORÈME 2. Si une norme de la matrice est cohérente avec la norme du vecteur considéré X

. (2.13)

PREUVE. Soustrayons l'égalité (2.10) de l'égalité :

En soustrayant la valeur d'approximation des deux côtés, nous transformons cette relation sous la forme

En passant aux normes, on obtient

Puisque d'après les conditions du théorème, alors

En utilisant la relation dont il résulte que on obtient finalement :

THÉORÈME 3. Si une norme de la matrice est cohérente avec la norme du vecteur considéré X, est inférieur à un (), alors l'estimation d'erreur suivante a lieu :

Faisons deux commentaires. Premièrement, la relation (2.13) peut s’écrire sous la forme

nous permettant d'obtenir une estimation d'erreur basée sur les résultats des deux premières itérations. Premièrement, lors de l'utilisation de la méthode itérative, il est parfois recommandé d'utiliser la norme de la différence entre deux approximations successives comme estimation de l'erreur de calcul. Il ressort des relations d’erreur que, dans le cas général, cela n’est pas vrai. Si la norme est proche de l'unité, alors le coefficient at peut être assez grand.

Les erreurs des itérations successives sont liées par la relation

ceux. l'erreur change linéairement au cours de l'étape. On dit que la méthode a convergence linéaire ou premier ordre de convergence. Cependant, le nombre d'itérations nécessaires pour obtenir la précision requise dépend de la valeur et de l'approximation initiale.

Ainsi, en utilisant la méthode d'itération simple comme exemple, trois étapes de méthodes itératives sont démontrées : construction d'une séquence de vecteurs générée par la formule (1.10) ; déterminer la condition de convergence à l'aide du théorème 1 et estimer le taux de convergence à l'aide des théorèmes 2 et 3.

Méthode Seidel

La méthode d'itération simple n'utilise pas la possibilité apparemment évidente d'améliorer la convergence du processus itératif - l'introduction immédiate de composantes vectorielles nouvellement calculées dans le calcul. Cette fonctionnalité est utilisée dans la méthode itérative Seidel. Le processus itératif pour le système (2.9) est réalisé selon la relation

je = 1, 2, …, n (2.14)

ou pour le système (1.1)

Sans entrer dans les détails, notons que la méthode d’itération de Seidel conduit souvent à une convergence plus rapide que la méthode d’itération simple. Cependant, il peut y avoir des cas où la méthode d'itération de Seidel converge plus lentement que la méthode d'itération simple, et même des cas où la méthode d'itération simple converge, mais la méthode d'itération de Seidel diverge.

Noter que La méthode de Seidel converge si matrice UN positif défini et symétrique.

Montrons que la méthode d'itération de Seidel est équivalente à une méthode d'itération simple avec une matrice et un vecteur spécialement construits en relation (2.10). Pour ce faire, on écrit le système (2.14) sous la forme où F est la matrice triangulaire supérieure des coefficients de la matrice, et on réécrit le système sous la forme où E est la matrice identité. Matrice (EN)- matrice triangulaire inférieure avec des éléments diagonaux égaux à un. Par conséquent, le déterminant de cette matrice est non nul (égal à un) et il a une matrice inverse. Alors

En comparant cette relation avec la solution (2.10), on peut conclure que la méthode d'itération de Seidel est bien équivalente à la méthode d'itération simple dans le sens où pour établir la condition et le critère de convergence de la méthode d'itération de Seidel, on peut utiliser les théorèmes donné pour la méthode d’itération simple, si l’on met Le processus itératif du système (2.12) est également écrit sous une forme plus générale, à savoir

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 cyclisme 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) entre dans la 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 d'itération 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.