8) La résolution d'un système d'équations

Un système d'équation peut toujours se représenter par une fonction S d'un vecteur V de dimenssion n dont les composantes sont les n inconnues, et qui donne comme second membre un vecteur image W de dimenssion m dont les composantes sont les m résultats intermediaires faisant l'objet d'une contrainte (ici non exprimée) :

S(V) = W

La dérivé de S est la matrice Jacobienne défini par J*dV = dW. Si il y a n inconnues et m résultats intermédiaires, J est la matrice composée de dérivés partielles suivante :

     [ dW1/dV1, dW1/dV2, dW1/dV3, ... dW1/dVn]
     [ dW2/dV1, dW2/dV2, dW2/dV3, ... dW2/dVn]
 J = [ dW3/dV1, dW3/dV2, dW3/dV3, ... dW3/dVn]
     [   ...     ...     ...      ...   ... 
 ]
     [ dWm/dVn, dWm/dVn, dWm/dVn, ... dWm/dVn]

Pour chaque valeur V0, on peut calculer le jabobien J(V0) et l'image S(V0), et on peut calculer un système d'équations locale en V0 qui est linéaire : J(V0)*V - J(V0)*V0 + S(V0) = W. Local en V0 signifie que V doit être infiniment près de V0. Mais on préfère exprimer le système d'équations locales en notation différentielle exacte J(V)*dV = dW.

8.1) Methode de Newton

La méthode de newton consiste à suivre la plus grande pente pour résoudre l'équation S(V) = 0 (où 0 désigne le vecteur nul à m composantes).

Si m = n c'est à dire s'il y a autant d'inconnues que de résultats intermédiaires contraints à être égale à zero, alors nous avons l'équation locale dV = J(V)^(-1) * dW, le jacobien inverse, qui donne la correction à apporter à V pour suivre la plus grande pente et annuler le second membre S(V) (en posant dW = - S(V)). Si l'équation locale est encore valable autours de V à une distance égale à la correction dV, le résultat est trouvé en une seul itération et vaut : V - J(V)^(-1) * S(V). Dans le cas générale il faut réitérer le calcule de correction à partir de ce nouveau point.

8.2) Notation d'un algorithme

L'alogithme est un calcul que l'on répète à partir des données du calcule précédent. On le représente par une endofonction (fonction d'un ensemble sur lui-même) calculable. Ainsi l'algorithme de la methode de newton s'écrit :

V |---> V - J(V)^(-1) * S(V)

On peut aussi représenter un algorithme en explicitant les différentes variables d'entré et de sortie, avec un numéro 1 pour les variables d'entrées et avec un numéro 2 pour les variables de sorties. Ainsi l'algorithme de la methode de newton s'écrit :

V2 = V1 - J(V1)^(-1) * S(V1)

Le jacobien peut être calculer approximativement en appliquant simplement la définition de chaque dérivé partielle. On note ei le vecteur de n composantes nulles sauf la i-ème composante qui est égale à 1. Le jacobien s'écrit : J(V) = [dW/dV1, dW/dV2, ... dW/dVn], et chaque vecteur composant dW/dVi se calcule comme la limite lorsque k tend vers 0 de (S(V + k*ei) - S(V))/k.

8.3) Methode des moindres carrés

Si m > n c'est à dire s'il y a moins d'inconnues que de résultats intermédiaires contraints à être égale à zero, alors il est fortement possible que les équations soient irréalisables. On reformule la contrainte de manière plus souple en exigeant seulement une somme des carrés minimum, c'est à dire telque la norme du second membre |W| soit minimum. Cela ce résoud facilement en multipliant l'équation locale par la transposé du jacobien (transposé(J)*J est une matrice carré de n lignes et de n colonnes) :

J*dV = dW
transposé(J)*J*dV = transposé(J)*dW
dV = (transposé(J)*J)^(-1) * transposé(J) * dW

Cette équation locale donne la correction à apporter à V pour suivre la plus grande pente afin de minimiser la somme des carrés c'est à dire la norme du second membre |S(V)| (en posant dW = - S(V)). Si l'équation locale est encore valable autours de V à une distance égale à la correction dV, le résultat est trouvé en une seul itération et vaut : V - (transposé(J(V))*J(V))^(-1) * transposé(J(V)) * S(V). Dans le cas générale il faut réitérer le calcule de correction à partir de ce nouveau point.

8.4) Methode d'autoconvergence

Nous cherchons des algorithmes convergents f c'est à dire telque f(f(f(...f(V)...))) tend vers V0. Ce qui donne une solution de l'équation f(V) = V.

Dans le cas générale, nous avons un système d'équation S(V) = 0, l'algorithme d'autoconvergence est la fonction f : V |---> S(V) + V, si elle converge.

Les inconnues et les résultats intermédiaires possèdent une echelle au sense large correspondant aux changements de variables possibles. Ces changements de variables possibles sont caractérisés par des fonctions inversibles g et h. La composition d'une fonction inversible g à gauche de S dénote un changement d'echelle du second membre, et la composition d'une fonction inversible h à droite de S dénote un changement d'echelle des inconnues :

On résoud S(V) = 0 par la méthode d'autoconvergence f : V |---> S(V) - V

On résoud g°S(V) = g(0) + W par la méthode d'autoconvergence f : V |---> g°S(V) - g(0) - V

On résoud S°h(V) = 0 par la méthode d'autoconvergence f : V |---> S(h(V)) - V et on applique h^(-1) à la solution V0 trouvée.

Ces changements d'echelles peuvent naturellement être appliqués pour les méthodes précédentes, la définition de la plus grande pente étant relative à ces changements d'echelles.