MATH_SyslinSurdim [Algebre]
Par Marc Duc-Jacquet (Math4D v2)
Nouvelle recherche
Si (Faux)
` MATH_SyslinSurdim [Marc DUC-JACQUET 20/01/2003]
` ---------------------------------------------
` Source: Bibliothèque d'Analyse Numérique de Grenoble (BANG)
` dont l'élaboration est un travail d'équipe auquel l'auteur a participé
` ---------------------------------------------
` Rappels mathématiques :
` Un système linéaire de M équations à N+1 inconnues s'écrit:
` A01;X0 + A11;X1 + ;;; + AN1;XN = B1
` A02;X0 + A12;X1 + ;;; + AN2;XN = B2
` A03;X0 + A13;X1 + ;;; + AN3;XN = B3
` ; ; ;
` ; ; ;
` A0M;X0 + A1M;X1 + ;;; + ANM;XN = BM
` où M>=N+1 (plus d'équations que d'inconnues, cad plus de lignes
` que de colonnes (on dit que le système est sur-dimensionné)
` les AIJ , I=0 à N, J=1 à M (appelés coefficients du système )
` et les BI , I=1 à M ( appelés seconds membres car à droite du
` signe = ) sont connus ( c'est à dire donnés)
` X0,X1, ;;; XN sont les N+1 inconnues
` RESOUDRE ce système linéaire c'est chercher les valeurs des inconnues
` X0,X1, ;;; XN qui satisfont au mieux les M équations;
` Si on prend le parti de chercher les valeurs des X0,X1, ;;;; XN
` pour lesquelles la somme des carrés des écarts
` Somme [ Bi - (A0i X0+A1i X1+ ;;; + ANi XN)] ^2 (somme pour i=1,2, M)
` est minimum, on dit que l'on résoud le système linéaire initial,
` au sens des MOINDRES CARRES
` Nous conviendrons que l'ensemble des données ( les coefficients AIJ
` sont rangés dans le tableau bidimensionnel A)
` | A01 A11 ;;;; AN1 |
` | A02 A12 ;;;; AN2 |
` A= | A03 A13 ;;;; AN3 |
` | ;;;;
` | A0M A1M ;;;; ANM |
` ce tableau à M lignes et N+1 colonnes, devra être déclaré dans 4D comme
` TABLEAU REEL A {M} {N}
` Mathématiquement A est une matrice à M lignes et N+1 colonnes
` Le second membre est représenté par le tableau unidimensionel B
` | B1 |
` | B2 |
` B= | B3 |
` | ;;;;
` | BM |
` matrice à M lignes et 1 colonne;
` La théorie mathématique montre que si on note
` | X0 |
` | X1 |
` X= | ;;;;
` | XN |
` X vecteur de dimension N+1, la solution du problème est obtenue en
` résolvant au sens ordinaire le système de N+1 équations à N+1 inconnues suiva
` àAX = àB
` où à est la matrice TRANSPOSEE de la matrice A
` (à est obtenue à partir de A en échangeant les lignes et les colonnes)
` ---------------------------------------------
` MATHERROR:= MATH_SyslinSurDim(->A;-> B;-> X;N; M; EPSILON)
` le premier paramètre est un pointeur sur le tableau bidimensionnel A
` le second paramètre est un pointeur sur le tableau unidimensionnel B
` le troisième paramètre est un pointeur sur le tableau unidimensionnel X
` X contient en sortie la solution
` M représente donc le nombre d'équations
` N+1 représente le nombre d'inconnues
` EPSILON numérique
` ---------------------------------------------
` MATHERROR (valeur renvoyée par la méthode)
` 0 -> La méthode a été conduite à son terme
` +1 -> La méthode est avortée
` On arrête en effet les calculs si la somme des carrés des éléments
` d'une ligne de A est inférieure à la constante EPSILON
`
Fin de si
C_ENTIER LONG(MATHERROR)
C_POINTEUR($1;$2;$3)
C_ENTIER($4;$5;$0)
C_REEL($6)
`variables locales
C_ENTIER($M;$N;$J;$J1$K;$K1;$KP1;$L)
C_REEL($AKJ;$AKK;$BETA;$BK;$S1;$S2;$EPSILON)
`Passage des paramètres
$M:=$4 ` $4 équations numérotées de 1 à $M
$N:=$5-1 ` $5 inconnues numérotées de 0 à $N-1
$EPSILON:=$6
`tableaux locaux
TABLEAU REEL($A;$N;$M) `on utilisera $A{0}
TABLEAU REEL($B;$M)
TABLEAU REEL($X;$N) `on utilisera $X{0}
`passage des tableaux
`$1 est le tableau des coefficients du système à résoudre
Boucle ($I;0;$N)
Boucle ($J;1;$M)
$A{$I}{$J}:=$1->{$J}{$I+1} `noter que le tableau local $A est le transposé du tableau passé dans $1
Fin de boucle
Fin de boucle
Boucle ($I;1;$M)
$B{$I}:=$2->{$I}
Fin de boucle
$0:=0 `à priori tout se passera bien
Boucle ($K;0;$N)
$KP1:=$K+1
$AKK:=$A{$K}{$KP1}
$K1:=$KP1+1
$S1:=$AKK*$AKK
Boucle ($L;$K1;$M)
$S1:=$S1+($A{$K}{$L}*$A{$K}{$L})
Fin de boucle
Si ($S1<$EPSILON)
$0:=1
Fin de si
Si ($0=0) ` on peut continuer
$S1:=Racine carree($S1)
Si ($AKK<0,0001)
$S1:=-$S1
Fin de si
$BETA:=1/($S1*($S1+$AKK))
$A{$K}{$KP1}:=-$S1
Boucle ($J;$KP1;$N)
$AKJ:=$A{$J}{$KP1}
$S2:=0
Boucle ($L;$K1;$M)
$S2:=$S2+($A{$K}{$L}*$A{$J}{$L})
Fin de boucle
$A{$J}{$KP1}:=-($AKK*$AKJ+$S2)/$S1
Boucle ($L;$K1;$M)
$A{$J}{$L}:=$A{$J}{$L}-($A{$K}{$L}*($AKJ/$S1+($BETA*$S2)))
Fin de boucle
Fin de boucle
$S2:=0
Boucle ($L;$K1;$M)
$S2:=$S2+($A{$K}{$L}*$B{$L})
Fin de boucle
$BK:=$B{$KP1}
$B{$KP1}:=-($AKK*$BK+$S2)/$S1
Boucle ($L;$K1;$M)
$B{$L}:=$B{$L}-($A{$K}{$L}*($BK/$S1+($BETA*$S2)))
Fin de boucle
Fin de si
Fin de boucle
Si ($0=0) `la méthode n'est pas avortée;
`Résolution système triangulaire
$X{$N}:=$B{$N+1}/$A{$N}{$N+1}
Boucle ($K;1;$N)
$K1:=$N-$K
$J1:=$K1+1
$S1:=0
Boucle ($J;$J1;$N)
$S1:=$S1+($A{$J}{$J1}*$X{$J})
Fin de boucle
$X{$K1}:=($B{$J1}-$S1)/$A{$K1}{$J1}
Fin de boucle
`restitution de la solution dans $3
$N:=$N+1
Boucle ($I;1;$N)
$3->{$I}:=$X{$I-1}
Fin de boucle
`Calcul de la somme des carrés des écarts restituée dans $3->{0}
$S:=0
Boucle ($i;1;$M)
$Ecart:=0
Boucle ($j;1;$N)
$Ecart:=$Ecart+($1->{$i}{$j}*$3->{$j})
$S1:=$S1+($Ecart*$Ecart)
Fin de boucle
$Ecart:=$Ecart-$2->{$i}
$Ecart:=$Ecart*$Ecart
$S:=$S+$Ecart
Fin de boucle
$3->{0}:=$S
Fin de si
MATHERROR:=$0