résoudre Ax=b avec A matrice triangulaire inférieure

**Seshire** · 19/11/2010, 18h32

Bonjour,
je suis actuellement en L3 maths appliquées, je débute en C++ et j'ai un projet à faire dont la première question est de résoudre le système Ax=b avec A matrice triangulaire inférieure. j'ai fait le programme suivant mais il ne veut pas marcher, je ne comprend pas pourquoi, est ce que quelqu'un pourrait m'aider? merci.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
void AfficherMatrice(float **M, int n){ //affiche une matrice de taille n*n
     for (int i=0; i<n; i++){
         for (int j=0; j<n; j++){
             cout<< M[i][j] << "\t" ;
             }
             cout<< endl;
             }
             }
 
void AfficherVecteur (float *y, int n){ //affiche un vecteur de taille n
     for (int i=0; i<n; i++){
         cout<< y[i] << "\t";
         }
         cout<<endl;
         }
 
void MTI(float **M, int n){ // matrice triangulaire inférieure
                for(int i=0; i<n; i++){ 
             for (int j=0; j<=i; j++){
                 cout<<M[i][j]<< "\t";
                 }
                 cout<<endl;
                 }
                 }
 
float Somme(float **M, float *x, int i, int j){ // M.x
     float S=0;
     for (i=1; i<j;i++){
         S+=M[j][i]*x[i];
         }
         }
 
void SystMatTI (float **M, float *b, float *x, int n){ //trouver x tel que Mx=b avec M tiangulaire inférieure
     x[1]=b[1]/M[1][1];
     for (int j=2; j<=n; j++){
             x[j]=(b[j]- Somme(M,x,1,j-1))/M[j][j];
             }
             }
 
 
 
int main(int argc, char *argv[])
{
    int n;
    cout << "entrer la valeur de n" <<endl;
    cin>>n;
    float **A=NULL;
    A= new float*[n];
    for (int i=0; i<n; i++){
        A[i]= new float[i+1];
        }
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
   cout<< "Entrer A" <<i+1<<","<<j+1<<endl;
   cin>> A[i][j];
}
}
   AfficherMatrice(A,n);
   cout<<endl;
   MTI(A,n);
   float *x;
   x=new float [n];
   float *b=NULL;
   b= new float [n];
       for (int i=0; i<n; i++){
           cout<< "Entrer b" <<i+1<< endl;
           cin>>b[i];
           }
           AfficherVecteur(b,n);
           cout<<endl;
           SystMatTI(A,b,x,n);
           cout<<endl;
 
   for (int i=0; i<n; i++){
       delete []A[i];
       }
       delete []A;
       delete []b;
       delete []x;
       x=NULL;
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

**Steph_ng8** · 19/11/2010, 19h08

Oulà, c'est loin les calculs sur les matrices…

Je ne vais probablement pas pouvoir t'aider beaucoup sur le fond, juste sur le code.
Par contre, ce serait sympa de faire attention à l'indentation ; bien réalisée elle facilite (de beaucoup) la lecture et la compréhension du code.

Pour commencer, j'aimerais pointer un gros problème.
Tu construis ta matrice A comme une matrice triangulaire inférieure.
Jusque là, pas de souci.
Mais après, tu veux l'afficher avec ta fonction « AfficherMatrice() », qui s'attend à recevoir une matrice complète.
Et donc, à chaque fois que tu tentes d'accéder à M[i][j] alors que j > i, tu vas dans une zone mémoire qui n'a pas été réservée pour la ligne en cours.
Ça peut être n'importe quoi : une zone non initialisée, une case d'une autre ligne de ta matrice, une zone réservée pour une autre variable, une zone à laquelle tu n'es pas censée avoir accès…

Bon, ce n'est pas dramatique puisque tu ne fais qu'accéder à cette zone, tu n'essaies pas d'en modifier le contenu.
Au pire, ça affichera n'importe quoi.
Mais il faut bien que tu te rendes comptes que tu tentes d'accéder à une case qui finalement se trouve hors de ta matrice.
Cela peut être critique si tu essaies d'en modifier le contenu…

Ensuite, ta fonction « Somme() » est censée retourner un « float », mais ne retourne rien.
Je suppose que c'est un juste oubli de ta part, et que normalement tu retournes « S ».
Ceci dit, dans la boucle, la première valeur de «i » devrait être «0 », non ?

Voilà, après je n'ai pas vu d'autres choses importantes.
Bonne continuation !

**Seshire** · 19/11/2010, 19h35

ok merci j'ai fait quelques modifs mais en fait ce que je veux c'est qu'après exécution il me donne le vecteur x et ça marche pas (j'ai remplacé void par float dans ma fonction SystMTI), il affiche bien la matrice triangulaire inférieure et le vecteur b mais après il me met "a cessé de fonctionner" donc je pense que c'est ma fonction qui est fausse seulement je ne vois pas pourquoi.
désolée d'être aussi nulle

**Astraya** · 19/11/2010, 20h50

Évite un maximum les pointeurs. Ta matrice n'est pas obligé d'être une allocation dynamique.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
float **A=NULL;
A= new float*[n];
//peut être remplacer par
float A[n];
 
//Ainsi que 
float *x;
x=new float [n];
//peut être remplacer par
float x[n];

Il n'est pas plus efficace de passer une type de base (int, float, etc...) par pointeur que par valeur. Si tu dois la modifier, passe le par référence au pire.
Déjà ça éclaircira ton code.
A quel ligne plante-t-il exactement?

**Seshire** · 19/11/2010, 21h26

Le soucis c'est qu'on me demande d'utiliser les pointeurs justement!
à la compilation il ne me met aucun problème mais après il plante pour m'afficher le vecteur x.

**Joel F** · 19/11/2010, 21h56

1/ on alloue les tableaux 2D proprement:
http://codepad.org/K2WAwRBP

2/ tes boucles ont des bornes bizarres ...

**cs_ntd** · 19/11/2010, 23h12

Ca c'est du C Joel-F. Il vaut mieux utiliser les new/delete en C++, et éviter les cast sauvages du genre (type)var...

Sinon pour le code, j'ai relevé quelques erreurs, voici une version ou je pointe ce qui ne va pas (comentaires en gras) (les commentaires sur les index 0, c'est juste une hypothèse, j'ai pas vérifié l'algo) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdlib>
#include <iostream>

using namespace std;

void AfficherMatrice(float **M, int n)
{ //affiche une matrice de taille n*n
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            cout<< M[i][j] << "\t" ;
        }
        cout<< endl;
     }
}

void AfficherVecteur (float *y, int n)
{ //affiche un vecteur de taille n
    for (int i=0; i<n; i++)
    {
        cout<< y[i] << "\t";
    }
    cout<<endl;
}

void MTI(float **M, int n)
{ // matrice triangulaire inférieure
    for(int i=0; i<n; i++)
    {
        for (int j=0; j<=i; j++)
        {
            cout<<M[i][j]<< "\t";
        }
        cout<<endl;
    }
}

float Somme(float **M, float *x, int i, int j)
{ // M.x
    float S=0;
    //Toujours pas d'index 0 ?    for (i=1; i<j;i++)
    {
        S+=M[j][i]*x[i];
    }
    return S; 
    //Retourner quelque chose, je ne sais pas
    //si c'est S simplement;}

void SystMatTI (float **M, float *b, float *x, int n)
{ //trouver x tel que Mx=b avec M tiangulaire inférieure

    //Pourquoi jamais index 0 ?

    x[1]=b[1]/M[1][1];
    
    //!!! j<n !!! les plantages viennent de là !
    //Là, tu déborde de b, de la matrice, etc... des zones non allouées !!
    for (int j=2; j<n; j++)
    {
        x[j]=(b[j]- Somme(M,x,1,j-1))/M[j][j]; 
        //Est tu sûr que M[j][j] != 0 ?
        //Si jamais = 0 ça va planter 
        //du genre "a cesser de fonctionner..."
        //A toi de prévoir le cas...
    }
}



int main(int argc, char *argv[])
{
    int n;
    cout << "entrer la valeur de n" <<endl;
    cin>>n;

    float** A = new float* [n]; //Pas besoin de la macro NULL

    for (int i=0; i<n; i++)
    {
        A[i]= new float[n];
        //Problème : tu veux que A soit une vrai matrice (n*n), mais
        //tu n'alloue qu'une matrice triangulaire
    }

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            cout<< "Entrer A" <<i+1<<","<<j+1<<endl;
            cin>> A[i][j];
        }
    }

    AfficherMatrice(A,n);
    cout<<endl;
    MTI(A,n);
    //float *x = new float [n];
    //Pourquoi pas :
    float x[n];

    //float *b = new float [n];
    //Idem
    float b[n];

    for (int i=0; i<n; i++)
    {
        cout<< "Entrer b" <<i+1<< endl;
        cin>>b[i];
    }

    AfficherVecteur(b,n);
    cout<<endl;

    SystMatTI(A,b,x,n);
    cout<<endl;

    //Afficher le résultat peut-être ?
    AfficherVecteur(x,n);

    for (int i=0; i<n; i++)
    {
        delete[] A[i];
    }
    delete[] A;
    delete[] b;
    delete[] x;

    //OK, les desalloc sont bonnes

    //x=NULL; : Inutile...

    system("PAUSE");
    return EXIT_SUCCESS;
}

Normalement, ça ne plante plus. Quand à faire ce que tu veux (au niveau de l'algo), je n'ai pas vérifié.

Mais les plantages que tu a eu démontrent tout l'intéret de ne pas utiliser les tableaux bas-niveaux en C++ (qu'ils restent en C), mais d'utiliser des structures "toutes prêtes" venant de la STL, du genre std::vector, std::list, etc... qui prennent en charge les débordements d'index, et évitent de planter sauvagement...

**Joel F** · 20/11/2010, 08h45

Envoyé par cs_ntd

Ca c'est du C Joel-F. Il vaut mieux utiliser les new/delete en C++, et éviter les cast sauvages du genre (type)var...

Ouais je viens de voir que j'ai pas mit le bon lien. J'édite.
J'ai du etre trompé par le code initial :€

Le bon lien: http://codepad.org/nDy8z2iG

Sinon, il faut vraiment éviter les allcoations 2D disjointes, ce que vector< vector<> > propose, le cache n'aime vraiment, vraiment pas. L'allocation NRC n'ets pas plus dur à mettre en place.

**3DArchi** · 20/11/2010, 09h10

La problématique n'est pas justement de traiter une matrice triangulaire inférieur et donc de ne pas allouer la totalité ligne x colonne ?

**Seshire** · 20/11/2010, 10h29

merci pour vos réponse, j'ai enfin réussis à faire quelque chose qui marche avec le code suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
void AfficherMatrice(float **M, int n){ //affiche une matrice de taille n*n
     for (int i=0; i<n; i++){
         for (int j=0; j<n; j++){
             cout<< M[i][j] << "\t" ;
             }
             cout<< endl;
             }
             }
 
void AfficherVecteur (float *y, int n){ //affiche un vecteur de taille n
     for (int i=0; i<n; i++){
         cout<< y[i] << "\t";
         }
         cout<<endl;
         }
 
void MTI(float **M, int n){ // matrice triangulaire inférieure
                for(int i=0; i<n; i++){ 
             for (int j=0; j<=i; j++){
                 cout<<M[i][j]<< "\t";
                 }
                 cout<<endl;
                 }
                 }
 
float Somme(float **M, float *x, int i, int j){ // M.x
     float S=0;
     for (i=0; i<j;i++){
         S+=M[j][i]*x[i];
         }
         return S;
         }
 
float SystMatTI (float **M, float *b, float *x, int n){ //trouver x tel que Mx=b avec M tiangulaire inférieure
     x[0]=b[0]/M[0][0];
     for (int j=1; j<n; j++){
             x[j]=(b[j]- Somme(M,x,0,j))/M[j][j];
             }
             }
 
 
 
int main(int argc, char *argv[])
{
    int n;
    cout << "entrer la valeur de n" <<endl;
    cin>>n;
    float **A= new float *[n];
    for (int i=0; i<n; i++){
        A[i]= new float[n];
        }
        for (int i=0; i<n; i++){
            for (int j=0; j<=i; j++){
   cout<< "Entrer A" <<i+1<<","<<j+1<<endl;
   cin>> A[i][j];
}
}
   MTI(A,n);
   float *x= new float [n];
   float *b= new float [n];
       for (int i=0; i<n; i++){
           cout<< "Entrer b" <<i+1<< endl;
           cin>>b[i];
           }
           AfficherVecteur(b,n);
           cout<<endl;
           SystMatTI(A,b,x,n);
           cout<<endl;
           AfficherVecteur(x,n);
 
   for (int i=0; i<n; i++){
       delete []A[i];
       }
       delete []A;
       delete []b;
       delete []x;
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

**Aleph69** · 20/11/2010, 10h59

Bonjour,

Envoyé par 3DArchi

La problématique n'est pas justement de traiter une matrice triangulaire inférieur et donc de ne pas allouer la totalité ligne x colonne ?

Excellente question!

Peut-être qu'il faudrait mieux nommer les fonctions, comme par exemple
Somme -> produitMatriceVecteur
MTI -> afficherPartieTriangulaireInferieure
SystMatTI -> resoudreSystemeTriangulaireInferieur

J'ajouterais dans 'MTI' un petit test d'inversibilité" en vérifiant que le déterminant n'est pas nul, i.e. que tous les coefficients diagonaux sont non nuls. Par exemple, à la ligne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
x[j]=(b[j]- Somme(M,x,0,j))/M[j][j];

tu dois d'abord vérifier que M[j][j] est différent de zéro avant de diviser.

Pourquoi ne pas faire une classe pour les vecteurs et une classe pour les matrices triangulaires inférieures? Si tu as vu les classes en cours de C++, je pense que ton prof s'attend à ce que tu les fasses.

**Joel F** · 20/11/2010, 11h59

Envoyé par 3DArchi

La problématique n'est pas justement de traiter une matrice triangulaire inférieur et donc de ne pas allouer la totalité ligne x colonne ?

Ho, dans ce cas il suffit de modifier la fonction alloc pour allouer w - i éléments par lignes au lieu de w.

Le bloc reste continue avec une structure type LAPACK

[ a 0 0 0]
[ b c 0 0] => [a | b c | d e f | g h i j]
[ d e f 0]
[ g h i j ]

L'astuce NRC reste valable

résoudre Ax=b avec A matrice triangulaire inférieure

C++

Discussions similaires

Partager

Partager