Problème : Résolution d'un système linéaire ( Méthode de Gauss )

Nous cherchons a créer un programme C++ qui donne les solutions d'un système de type :

$\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 .

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 )