Nous cherchons a créer un programme C++ qui donne les solutions d'un système de type :
la méthode la plus facile pour résoudre ce type de systèmes est la méthode de Gauss , cette méthode consiste a faire des opérations - addition , multiplication , permutation - sur les lignes du système affin d'obtenir un système triangulaire supérieur équivalent de la forme :
( les ${ a }_{ ii }$ ne sont pas les mêmes du premier système ,on montre juste la forme )
notre système linéaire sera représenté comme un tableau de réels a 2 dimensions contenant N lignes et N+1 colonnes ( une colonne de plus pour les ${ b }_{ ii }$ ) .
on donne la fonction creerSys qui crée le tableau , elle est définit comme indiqué suivant :
Question 1 : définir une fonction de prototype void afficher( double ** sys , int N ) qui permet de faire l'affichage du système . (Solution )
on peut même faire des combinaisons entre ces opérations , par exemple on peut remplacer la ligne ${ L }_{ i }$ par ${ L }_{ i } + x { L }_{ j } $ .
Question 3 : définir une fonction de prototype void sommerLigns(double** sys, int N, int i, double x, int j) qui permet de réaliser cette opération dans le système sys . ( Solution )
Question 4 : définir une fonction de prototype int nbr0avantPivot( double** sys , int N , int i ) qui compte et renvoie le nombre des 0 situé avant le pivot dans la ligne ${ L }_{ i }$ . ( Solution )
par exemple : si on a le système suivant ( on a mis juste la représentation matricielle pour simplifier )
pour la première ligne , le pivot est le nombre 2 .
le résultat serait donc :
Question 5 : définir une fonction de prototype void annulerSousPivots( double** sys , int N ) qui annule les coefficients sous touts les pivot du système sys . ( Solution )
Question 6 : définir une fonction de prototype void arrangerLigns( double** sys , int N ) qui rend le système triangulaire . ( Solution )
il est facile de déterminer les ${ x }_{ i }$ .
en démarre de la dernière ligne :
Question : pourquoi quand ${ a }_{ nn }$ on a mis ${ x }_{ n } = 0$ et on a pas mis autres valeurs ?
bonne question , un système linéaire peut avoir plusieurs solutions ,une infinité .
notre programme ne va pas donner toutes ces solutions , il vas nous donne juste
une seule , la solution la plus facile est c'elle qui contient plus de 0 , c'est pour cela qu'en impose au quelque inconnus la valeur 0 .
Question 7 : définir une fonction de prototype double * resoudre( double ** sys , int N ) qui renvoie un tableau de N réels contenant les valeurs des ${ x }_{ i }$ , c'est a dire qui renvoie la solution du système . ( Solution )
$\left\{ \begin{matrix} { a }_{ 11 }{ x }_{ 1 }\quad +\quad { a }_{ 12 }{ x }_{ 2 }\quad +\quad ....\quad +\quad { a }_{ 1n }{ x }_{ n }\quad =\quad { b }_{ 1 } \\ { a }_{ 21 }{ x }_{ 1 }\quad +\quad { a }_{ 22 }{ x }_{ 2 }\quad +\quad ....\quad +\quad { a }_{ 2n }{ x }_{ n }\quad =\quad { b }_{ 2 } \\ : \\ { a }_{ n1 }{ x }_{ 1 }\quad +\quad { a }_{ n2 }{ x }_{ 2 }\quad +\quad ....\quad +\quad { a }_{ nn }{ x }_{ n }\quad =\quad { b }_{ n } \end{matrix} \right.$
c'est un système de n équation et de n inconnus .la méthode la plus facile pour résoudre ce type de systèmes est la méthode de Gauss , cette méthode consiste a faire des opérations - addition , multiplication , permutation - sur les lignes du système affin d'obtenir un système triangulaire supérieur équivalent de la forme :
$\left\{ \begin{matrix} { a }_{ 11 }{ x }_{ 1 }\quad +\quad { a }_{ 12 }{ x }_{ 2 }\quad +\quad ....\quad +\quad a_{ 1n }{ x }_{ n }\quad =\quad { b }_{ 1 } \\ \quad \quad \quad \quad \quad \quad { a }_{ 22 }{ x }_{ 2 }\quad +\quad ....\quad +\quad { a }_{ 2n }{ x }_{ n }\quad =\quad { b }_{ 2 } \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad : \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad { a }_{ nn }{ x }_{ n }\quad =\quad { b }_{ n } \end{matrix} \right. $
( les ${ a }_{ ii }$ ne sont pas les mêmes du premier système ,on montre juste la forme )
notre système linéaire sera représenté comme un tableau de réels a 2 dimensions contenant N lignes et N+1 colonnes ( une colonne de plus pour les ${ b }_{ ii }$ ) .
on donne la fonction creerSys qui crée le tableau , elle est définit comme indiqué suivant :
double ** creerSys(int N){
double ** sys;
sys = new double*[N];
int i,j;
for(i=0;i<N;i++)
sys[i] = new double[N+1];
//remplissage
for(i=0;i<N;i++){
for(j=0;j<N+1;j++){
if ( j == N ) cout << "= ";
cin >> sys[i][j];
}
cout << "--------------------------" << endl;
}
return sys;
}
l’accès a une valeur dans le tableau est donc donné par sys[ i ][ j ] avec 0 $\le $ i $\le $ N-1 , 0 $\le $ j $\le $ N .Question 1 : définir une fonction de prototype void afficher( double ** sys , int N ) qui permet de faire l'affichage du système . (Solution )
void afficher(double** sys,int N){
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N+1;j++){
if ( j == N ) cout << "= ";
cout << sys[i][j] << "\t";
}
cout << endl;
}
}
Question 2 : définir une fonction de prototype void permuterLigns(double** sys , int N , int i , int j ) qui permute les valeurs de la ligne ${ L }_{ i }$ avec les valeurs de la ligne ${ L }_{ j }$ dans le système sys . ( Solution )void permuterLigns(double** sys,int N,int i,int j){
if ( i != j ) {
double x; int k;
for(k=0;k<N+1;k++){
x = sys[i][k] ; sys[i][k] = sys[j][k]; sys[j][k] = x;
}
}
}
les opérations que nous pouvons faire pour l'obtention d'un système linéaire équivalent sont , la multiplication d'une ligne par un scalaire , remplacer une ligne par sa somme avec une autre ligne .on peut même faire des combinaisons entre ces opérations , par exemple on peut remplacer la ligne ${ L }_{ i }$ par ${ L }_{ i } + x { L }_{ j } $ .
Question 3 : définir une fonction de prototype void sommerLigns(double** sys, int N, int i, double x, int j) qui permet de réaliser cette opération dans le système sys . ( Solution )
void sommerLigns(double** sys, int N, int i,double x,int j){
int k;
for(k=0;k<N+1;k++) sys[i][k] += x*sys[j][k];
}
A connaitre : le pivot de la ligne ${ L }_{ i }$ et le premier coefficient non nul dans cette ligne .Question 4 : définir une fonction de prototype int nbr0avantPivot( double** sys , int N , int i ) qui compte et renvoie le nombre des 0 situé avant le pivot dans la ligne ${ L }_{ i }$ . ( Solution )
int nbr0avantPivot(double** sys,int N,int i){
int nbr=0;
while( sys[i][nbr] == 0 && nbr < N+1 ) nbr++;
return nbr;
}
le premier pas pour rendre le système triangulaire supérieur est annuler tout les coefficient au dessous de chaque pivot :par exemple : si on a le système suivant ( on a mis juste la représentation matricielle pour simplifier )
$\begin{bmatrix} 0 & 2 & 4 & 9 & \quad \quad 0 \\ 5 & 8 & 0 & 9 & \quad \quad 2 \\ 1 & -6 & 0 & 0 & \quad \quad 0 \\ 5 & 0 & -7 & 9 & \quad \quad 0 \end{bmatrix}$
pour la première ligne , le pivot est le nombre 2 .
on peut annuler tous les coefficients au dessous de 2 en faisant les opérations :
- remplacer la ligne ${ L }_{ 2 }$ par ${ L }_{ 2 } -\frac { 8 }{ 2 } { L }_{ 1 }$ .
- remplacer la ligne ${ L }_{ 3 }$ par ${ L }_{ 3 } +\frac { 6 }{ 2 } { L }_{ 1 }$ .
- remplacer la ligne ${ L }_{ 4 }$ par ${ L }_{ 4 } -\frac { 0 }{ 2 } { L }_{ 1 }$ .
le résultat serait donc :
$\begin{bmatrix} 0\quad & 2\quad & 4 & \quad 9 & \quad \quad 0 \\ 5\quad & 0\quad & -16 & \quad -27 & \quad \quad 2 \\ 1\quad & 0\quad & 12 & \quad 27 & \quad \quad 0 \\ 5\quad & 0\quad & -7 & \quad 9 & \quad \quad 0 \end{bmatrix}$
Question 5 : définir une fonction de prototype void annulerSousPivots( double** sys , int N ) qui annule les coefficients sous touts les pivot du système sys . ( Solution )
void annulerSousPivots(double** sys,int N){
int i,j;
for (i=0;i<N-1;i++)
for(j=i+1;j<N;j++)
if ( nbr0avantPivot(sys,N,i) != N )
sommerLigns(sys,N,j,-(sys[j][nbr0avantPivot(sys,N,i)]/sys[i][nbr0avantPivot(sys,N,i)]),i);
}
après l'appelle de cette fonction , il suffit d'arranger les lignes en faisant des permutations pour triangulariser le système .Question 6 : définir une fonction de prototype void arrangerLigns( double** sys , int N ) qui rend le système triangulaire . ( Solution )
void arrangerLigns(double** sys,int N){
int i,j;
for ( i = 0 ; i<N-1 ; i++ )
for ( j = i+1 ; j<N ; j++ )
if ( nbr0avantPivot(sys,N,i) > nbr0avantPivot(sys,N,j) ) permuterLigns(sys,N,i,j);
}
Maintenant puisque le système est triangulaire
$\left\{ \begin{matrix} { a }_{ 11 }{ x }_{ 1 }\quad +\quad { a }_{ 12 }{ x }_{ 2 }\quad +\quad ....\quad +\quad a_{ 1n }{ x }_{ n }\quad =\quad { b }_{ 1 } \\ \quad \quad \quad \quad \quad \quad { a }_{ 22 }{ x }_{ 2 }\quad +\quad ....\quad +\quad { a }_{ 2n }{ x }_{ n }\quad =\quad { b }_{ 2 } \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad : \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad { a }_{ nn }{ x }_{ n }\quad =\quad { b }_{ n } \end{matrix} \right. $
il est facile de déterminer les ${ x }_{ i }$ .
en démarre de la dernière ligne :
si ${ a }_{nn} \neq 0 $ on trouve donc ${ x }_{ n } = \frac { { b }_{ n } }{ { a }_{ nn } } $
si ${ a }_{nn} = 0 $ et on met tous simplement ${ x }_{ n } = 0$ .
et d’après l'avant dernière ligne : ${ a }_{ n-1,n-1 }{ x }_{ n-1 } + { a }_{ n-1,n }{ x }_{ n } = { b }_{ n-1 }$ avec ${ x }_{ n }$ est connu , on calcule ${ x }_{ n-1 }$ et en passe a la ligne précédente .
avec cette procédure on trouve toutes les ${ x }_{ i }$
cette méthode nous donne toujours une solution pour tous système , mais il y a des systèmes qui n’admettent pas de solutions , pour cela il faut toujours vérifier que le résultat trouvé s'agit vraiment d'une solution .
lorsque le résultat n'est pas une solution , le système et donc n'admet pas de solution .
et d’après l'avant dernière ligne : ${ a }_{ n-1,n-1 }{ x }_{ n-1 } + { a }_{ n-1,n }{ x }_{ n } = { b }_{ n-1 }$ avec ${ x }_{ n }$ est connu , on calcule ${ x }_{ n-1 }$ et en passe a la ligne précédente .
avec cette procédure on trouve toutes les ${ x }_{ i }$
cette méthode nous donne toujours une solution pour tous système , mais il y a des systèmes qui n’admettent pas de solutions , pour cela il faut toujours vérifier que le résultat trouvé s'agit vraiment d'une solution .
lorsque le résultat n'est pas une solution , le système et donc n'admet pas de solution .
Question : pourquoi quand ${ a }_{ nn }$ on a mis ${ x }_{ n } = 0$ et on a pas mis autres valeurs ?
bonne question , un système linéaire peut avoir plusieurs solutions ,une infinité .
notre programme ne va pas donner toutes ces solutions , il vas nous donne juste
une seule , la solution la plus facile est c'elle qui contient plus de 0 , c'est pour cela qu'en impose au quelque inconnus la valeur 0 .
Question 7 : définir une fonction de prototype double * resoudre( double ** sys , int N ) qui renvoie un tableau de N réels contenant les valeurs des ${ x }_{ i }$ , c'est a dire qui renvoie la solution du système . ( Solution )
double * resoudre(double ** sys,int N){
double * solution;
solution = new double[N];
annulerSousPivots(sys,N);
arrangerLigns(sys,N);
int i,j;
for( i=N-1; i >= 0 ; i-- ){
if ( sys[i][i] == 0 ) solution[i] = 0;
else {
solution[i] = sys[i][N];
for(j=N-1;j>i;j--) solution[i] -= sys[i][j] * solution[j];
solution[i] /= sys[i][i];
}
}
}
Question 8 : définir une fonction de prototype bool verifierResultat( double ** sys , int N , double * sol ) qui vérifie le résultat s'il est une solution ou non . ( Solution )bool verifierResultat( double ** sys , int N , double sol ){
int i,j;
double x=0;
for(i=0;i<N;i++) {
for(j=0;j<N;j++ ) x += sys[i][j]*sol[j];
if ( x != sys[i][N] ) return false;
x=0;
}
return true;
}
Question 9 : écrire un programme qui permet a l'utilisateur de saisir les coefficients et l'ordre d'un système linéaire , et affiche la solution de ce système s'elle existe . ( Solution )
Aucun commentaire :
Enregistrer un commentaire