Dérivation de la formule de calcul pour la méthode d'itération simple. Méthode d'itération simple

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 signification 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 P.è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.

Remplaçons l'équation d'origine par une équation équivalente et construisons des itérations selon la règle . Ainsi, la méthode d’itération simple est un processus itératif en une seule étape. Afin de démarrer ce processus, vous devez connaître la première approximation. Découvrons les conditions de convergence de la méthode et le choix de l'approximation initiale.

Billet n°29

Méthode Seidel

La méthode Seidel (parfois appelée méthode de Gauss-Seidel) est une modification de la méthode d'itération simple, qui consiste dans le fait que lors du calcul de la prochaine approximation x (k+1) (voir formules (1.13), (1.14)) son les composants déjà obtenus x 1 ( k+1) , ...,x i - 1 (k+1) sont immédiatement utilisés pour calculer x i (k+1) .

Sous forme de notation de coordonnées, la méthode Seidel a la forme :

X 1 (k+1) = c 11 x 1 (k) + c 12 x 2 (k) + ... + c 1n-1 x n-1 (k) + c 1n x n (k) + d 1
x 2 (k+1) = c 21 x 1 (k+1) + c 22 x 2 (k) + ... + c 2n-1 x n-1 (k) + c 2n x n (k) + d 2
...
x n (k+1) = c n1 x 1 (k+1) + c n2 x 2 (k+1) + ... + c nn-1 x n-1 (k+1) + c nn x n (k ) + DN
où x (0) est une première approximation de la solution.

Ainsi, la ième composante de la (k+1)-ième approximation est calculée par la formule

La condition de fin du processus itératif de Seidel lorsque la précision ε est atteinte sous une forme simplifiée a la forme :

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

Billet n°30

Méthode de réussite

Pour résoudre des systèmes A x = b avec une matrice tridiagonale, on utilise le plus souvent la méthode du balayage, qui est une adaptation de la méthode de Gauss à ce cas.

Écrivons le système d'équations

d 1 x 1 + e 1 x 2 = b 1
c 2 x 1 + d 2 x 2 + e 2 x 3 = b 2
c 3 x 2 + d 3 x 3 + e 3 x 4 = b 3
... ... ...
c n-1 x n-2 + d n-1 x n-1 + e n-1 x n = b n-1
c n x n-1 + d n x n = b n

sous forme matricielle : A x = b où

UNE =

Écrivons les formules de la méthode du balayage dans l'ordre de leur application.

1. Course directe de la méthode de balayage (calcul des grandeurs auxiliaires) :

2. Inversez la méthode de balayage (trouver une solution) :

Billet n°31

Méthode d'itération simple

L’essence de la méthode d’itération simple est de passer de l’équation

f(x)= 0 (*)

à l'équation équivalente

X=φ(x). (**)

Cette transition peut s'effectuer de différentes manières, selon le type f(x). Par exemple, vous pouvez mettre

φ(x) = X+petit ami(x),(***)

Où b= const, alors que les racines de l'équation originale ne changeront pas.

Si l'approximation initiale de la racine est connue x0, alors la nouvelle approximation

x1=φx(0),

ceux. schéma général du processus itératif :

xk+1=φ(xk).(****)

Le critère le plus simple pour mettre fin au processus

|x k +1 -x k |<ε.

Critère de convergence méthode d'itération simple :

si près de la racine | φ/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого X, alors les itérations convergent pour toute approximation initiale.

Explorons le choix de la constante b du point de vue d’assurer une vitesse de convergence maximale. Conformément au critère de convergence, la vitesse de convergence la plus élevée est obtenue lorsque |φ / (x)| = 0. Parallèlement, sur la base de (***), b = –1/f / (x), et la formule d'itération (****) entre dans x je =x i-1 -f(x i-1)/f/ (x i-1).- ceux. dans la formule de la méthode de Newton. Ainsi, la méthode de Newton est un cas particulier de la méthode d'itération simple, offrant la vitesse de convergence la plus élevée de toutes les options possibles pour choisir une fonction φ(x).

Billet n°32

La méthode de Newton

L'idée principale de la méthode est la suivante : une première approximation est spécifiée à proximité de la racine hypothétique, après quoi une tangente à la fonction étudiée est construite au point d'approximation, pour laquelle l'intersection avec l'axe des abscisses est trouvée. Ce point est considéré comme la prochaine approximation. Et ainsi de suite jusqu'à ce que la précision requise soit atteinte.

Soit une fonction à valeur réelle définie sur un intervalle et différentiable sur celui-ci. Ensuite, la formule du calcul d’approximation itératif peut être dérivée comme suit :

où α est l'angle d'inclinaison de la tangente au point.

Par conséquent, l’expression requise pour a la forme :

Billet n°33

Méthode du nombre d'or
La méthode du nombre d'or vous permet d'éliminer les intervalles en calculant une seule valeur de fonction à chaque itération. À la suite des deux valeurs de fonction considérées, l'intervalle qui devra être utilisé à l'avenir est déterminé. Cet intervalle contiendra l'un des points précédents et le point suivant placé symétriquement par rapport à lui. Le point divise l'intervalle en deux parties de sorte que le rapport du tout à la plus grande partie soit égal au rapport de la plus grande partie à la plus petite, c'est-à-dire égal au soi-disant « nombre d'or ».

Diviser l'intervalle en parties inégales permet de trouver une méthode encore plus efficace. Calculons la fonction aux extrémités du segment [ un,b] et met un=X 1 , b=X 2. Calculons également la fonction en deux points intérieurs X 3 , X 4 . Comparons les quatre valeurs de la fonction et choisissons la plus petite d'entre elles. Supposons, par exemple, que le plus petit soit F(x3). Évidemment, le minimum doit être dans l'un des segments qui lui sont adjacents. Donc le segment [ X 4 ,b] peut être rejeté et quitter le segment.

Le premier pas a été franchi. Sur le segment, vous devez à nouveau sélectionner deux points internes, calculer les valeurs de fonction sur eux et aux extrémités et passer à l'étape suivante. Mais à l'étape précédente des calculs, nous avions déjà trouvé la fonction aux extrémités du nouveau segment et à l'un de ses points internes X 4 . Par conséquent, il suffit de sélectionner un point supplémentaire à l'intérieur x5 déterminer la valeur de la fonction qu'il contient et faire les comparaisons nécessaires. Cela quadruple la quantité de calcul requise par étape du processus. Quelle est la meilleure façon de placer les points ? Chaque fois, le segment restant est divisé en trois parties, puis l'un des segments extérieurs est supprimé.
Notons l'intervalle d'incertitude initial par D.

Puisque dans le cas général, n'importe lequel des segments peut être ignoré X1, X3 ou X4, X2 puis sélectionnez les points X3 Et X4 de sorte que les longueurs de ces segments sont les mêmes :

x 3 -x 1 =x 4 -x 2.

Après suppression, nous obtenons un nouvel intervalle d'incertitude de longueur D'.
Notons la relation D/D' avec la lettre φ :

c'est-à-dire, fixons où est le prochain intervalle d'incertitude. Mais

de longueur égale au segment rejeté à l'étape précédente, c'est-à-dire

On obtient donc :

.
Cela conduit à l'équation ou, de manière équivalente
.

La racine positive de cette équation donne

.

Billet n°34

interpolation de fonctions, c'est-à-dire Utiliser une fonction donnée, construire une autre fonction (généralement plus simple) dont les valeurs coïncident avec les valeurs de la fonction donnée en un certain nombre de points. De plus, l’interpolation a une signification à la fois pratique et théorique.

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 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 :

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 :