MATH_Syslin [Algebre]
Par Marc Duc-Jacquet (Math4D v1)
Nouvelle recherche
Si (Faux)
` MATH_SYSLIN [Marc DUC-JACQUET 11/09/2002]
` ----------------------------------
` Un système linéaire de N équations à N inconnues s'écrit:
` A11;X1 + A12;X2 + A13 X3 + ;;; + A1N;XN = B1
` A21;X1 + A22;X2 + ;;; + A2N;XN = B2
` A31;X1 + A32;X2 + ;;; + A3N;XN = B3
` ; ; ;
` ; ; ;
` AN1;X1 + AN2;X2 + ;;; + ANN;XN = BN
` où
` les AIJ , I=1 à N, J=1 à N ( appelés coefficients du système)
` et les BI , I=1 à N ( appelés seconds membres car à droite du
` signe = ) sont connus ( c'est à dire donnés)
`
` et où X1,X2, ;;; XN ont des valeurs inconnues
` le tableau suivant est appelé matrice des coefficients
` | A11 A12 A13 ;;;; A1N |
` | A21 A22 A23 ;;;; A2N |
` | A31 A32 A33 ;;;; A3N |
` | ;;;;
` | AN1 AN2 AN3 ;;;; ANN |
` RESOUDRE ce système linéaire c'est chercher les valeurs des inconnues
` X1,X2, ;;; XN qui satisfont les N équations;
` La théorie mathématique montre qu'un tel système
` - soit a une solution unique
` - soit n'a pas de solution (système impossible)
` - soit a une infinité de solutions
` Nous conviendrons que l'ensemble des données ( les coefficients AIJ ainsi que
` les seconds membres BI ) sont rangés dans le tableau bidimensionnel A
`
` | A11 A12 A13 ;;;; A1N B1 |
` | A21 A22 A23 ;;;; A2N B2 |
` A= | A31 A32 A33 ;;;; A3N B3 |
` | ;;;;
` | AN1 AN2 AN3 ;;;; ANN BN |
` ce tableau à N lignes et N+1 colonnes, devra être déclaré dans 4D comme
` TABLEAU REEL A {N} {N+1}
` Mathématiquement A est une matrice à N lignes, et N+1 colonnes
`Plus généralement on peut résoudre simultanément ce problème
`pour plusieurs vecteurs seconds membres; Si l'on a P tels
`seconds membres on devra considérer un tableau A (matrice) à N lignes et N+P
`colonnes : TABLEAU REEL A {N} {N+P}
`En prenant P=N et avec un choix judicieux des vecteurs seconds membres
`on peut trouver l'INVERSE -lorsqu'elle existe- de la matrice des coefficients;
`La méthode MATH_SYSLIN , est en théorie mathématique dénommée
`méthode de GAUSS avec recherche du meilleur pivôt sur les colonnes;
`La méthode permet au passage de calculer le déterminant (DET) de la
`matrice des coefficients; Lorsqu'il y a solution unique, celà correspond
`au cas DET # 0
`DESCRIPTION DES PARAMETRES DE LA FONCTION:
` MATHERROR:= MATH_SYSLIN (->A;N; P; TOPIVO;->DET)
` N représente la taille de la matrice cad le nombre
`de colonnes égal au nombre de lignes
` P représente le nombre de colonnes "seconds membres"
` ces colonnes sont des vecteurs de taille N
`P=0 si on veut seulement calculer le déterminant
`P=1 si on veut en outre résoudre un seul système linéaire
`P=N si on veut inverser la matrice des coefficients
` TOPIVO est la valeur minimum (positive) que peut prendre la
` valeur absolue d'un pivôt; (TOlérance PIVOt) :
` Si un pivôt prend une valeur inférieure à TOPIVO
` la méthode est avortée;
` Le dernier paramètre est un pointeur vers la variable DET (déterminant)
` MATHERROR (valeur renvoyée par la méthode)
` MATHERROR = 0 si la méthode a été conduite à
` son terme (auquel cas DET est égal à la valeur du déterminant),
` MATHERROR = 1 si la méthode est avortée
` On est alors soit dans le cas où il y a 0 solution ou une infinité
` de solutions; ou encore dans le cas où le déterminant quoique non nul,
` est très petit, situation où il est très difficile de calculer avec pr
` la solution;
` ----------------------------------
` La méthode MATH_SYSLIN opère sur un tableau A bidimensionnel
` d'au moins N lignes et d'au moins N+P colonnes ( TABLEAU REEL(A {N} {N+P} )
` La matrice est stockée dans les éléments A{I]{J] pour I,J = 1,;;;,N
` les seconds membres sont rangés dans A{I]{J] pour I = 1,;;;,N J= N+1,;;; N+P
` A l'issue des calculs, et si la méthode n'est pas avortée,
`les N premières colonnes de A contiennent la décomposition LR de
`la matrice des coefficients et
` les P dernières colonnes contiennent les P solutions cherchées
` ----------------------------------
Fin de si
C_ENTIER LONG(MATHERROR)
`paramètres
C_POINTEUR($1;$5)
C_ENTIER($2;$3;$0)
C_REEL($4)
`Passage des paramètres
$N:=$2
$P:=$3
$TOPIVO:=$4
TABLEAU REEL($A;$N;$N+$P)
`autres variables locales
C_REEL($Pivot;$S)
C_ENTIER($I;$J;$H;$K;$INDIC)
`passage du paramètre tableau
Boucle ($I;1;$N)
Boucle ($J;1;$N+$P)
$A{$I}{$J}:=$1->{$I}{$J}
Fin de boucle
Fin de boucle
TABLEAU ENTIER($PER;$N) `tableau des permutations de lignes
Boucle ($J;1;$N)
$PER{$J}:=$J `à priori pas de permutations de lignes
Fin de boucle
$INDIC:=0 `à priori tout se passera bien
$DET:=1
Boucle ($J;1;$N-1)
Si ($INDIC=0) ` la méthode n'est pas avortée
`Recherche du pivot max, enregistrement position
$S:=Abs($A{$J}{$J})
$K:=$J
Boucle ($H;$J+1;$N)
Si (Abs($A{$H}{$J})>$S)
$S:=Abs($A{$H}{$J})
$K:=$H
Fin de si
Fin de boucle
Si ($K#$J) `permutation de lignes si $K # $J
$H:=$PER{$K}
$PER{$K}:=$PER{$J}
$PER{$J}:=$H
Boucle ($I;$J;$N+$P)
$S:=$A{$K}{$I}
$A{$K}{$I}:=$A{$J}{$I}
$A{$J}{$I}:=$S
Fin de boucle
$DET:=-$DET `car permutation de deux lignes
Fin de si
$DET:=$DET*$A{$J}{$J}
Si (Abs($A{$J}{$J})<=$TOPIVO)
$Pivot:=Abs($A{$J}{$J})
$INDIC:=1 `on avorte la méthode
Fin de si
Si ($INDIC=0)
Boucle ($K;$J+1;$N)
$A{$K}{$J}:=$A{$K}{$J}/$A{$J}{$J}
Boucle ($I;$J+1;$N+$P)
$A{$K}{$I}:=$A{$K}{$I}-($A{$K}{$J}*$A{$J}{$I})
Fin de boucle
Fin de boucle
Fin de si
Fin de si `$INDIC=0
Fin de boucle `sur $J
$DET:=$DET*$A{$N}{$N}
Si ($P>0) & (Abs($A{$N}{$N})<=$TOPIVO)
$Pivot:=Abs($A{$N}{$N})
$INDIC:=1
Fin de si
`calcul des solutions si la méthode n'est pas avortée;
Si ($INDIC=0)
Boucle ($I;$N+1;$N+$P)
$A{$N}{$I}:=$A{$N}{$I}/$A{$N}{$N}
Boucle ($J;$N-1;1;-1)
$S:=$A{$J}{$I}
Boucle ($K;$J+1;$N)
$S:=$S-($A{$J}{$K}*$A{$K}{$I})
$A{$J}{$I}:=$S/$A{$J}{$J}
Fin de boucle
Fin de boucle
Fin de boucle
`restitution du tableau modifié
`passage du paramètre tableau
Boucle ($I;1;$N)
Boucle ($J;1;$N+$P)
$1->{$I}{$J}:=$A{$I}{$J}
Fin de boucle
Fin de boucle
Fin de si
$5->:=$DET
$0:=$INDIC
MATHERROR:=$0