Discussion :

[soft001]

Bonjour,
j'ai une question qui concernent l'une des propriétés de la multiplication matricielle : l'associativité

Code :

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

1
2
3
4
5
6
N = 1000;                                             
 A = rand(N); B = rand(N); C = rand(N); D = rand(N);
 
for k=1:2, t1=A*B*C*D; end;
for k=1:2, t2=(A*(B*(C*D))); end;
max(max(t1-t2))

Résultat :

Code :

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

1
2
ans =
   8.9407e-08

Est ce que la virgule flottante est la responsable de cette différence ?

[shaiHulud]

Bonjour,

A priori oui.
rmq: ne vois pas l’intérêt des boucles
Peut être que redéfinir le produit comme la moyenne des produits calculés sur toutes les associations possibles réduira l'ordre de grandeur de l'erreur, mais de toutes façon, la comparaison de floats (quelle que soit la dimension) se heurte à des problèmes de précision

en passant, la norme euclidienne norm(t1-t2) est surement plus optimiste que ta norme sup

[soft001]

rmq: ne vois pas l’intérêt des boucles

En fait pour ces boucles là je les ai utilisées pour un autre test mais je les oubliées (je vous montre cet exemple mais par contre j'ai une autre question)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
clc
clear all
N = 1000;                                             
A = rand(N); B = rand(N); C = rand(N); D = rand(N,1);
 
tic
for k=1:20, t1=A*B*C*D; end; 
toc
tic
for k=1:20, t2=(A*(B*(C*D))); end;
toc

Résultat :

Code :

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

1
2
3
4
5
6
Elapsed time is 4.920143 seconds.
Elapsed time is 0.039373 seconds.
 
ans =
 
   2.5332e-07

Dans cet exemple, je pense que j'ai une explication :
Dans le premier boucle le calcul se fait de gauche à droite et dans les trois premières multiplications on a que des matrices, ce qui nécessite, forcément, un peux plus de temps que dans le deuxième boucle, là où on a que des multiplications : matrices vecteurs.
ça serai intéressant que ces deux codes nous donnaient les mêmes valeurs.
Ou bien, d'après vous, la quelle des ces deux lignes de code donne le bon résultat ?

[soft001]

je pense que le meilleur résultat est donné par le deuxième boucle, vu qu'on a moins d'opération

[Jerome Briot]

Fais attention, le calcul de la précision doit se faire en valeur absolue :

Code :

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

max(abs(t1(:)-t2(:)))

ce qui donne l'erreur maximale.

Pour le reste, tout ce que je dirais pour ma part, c'est que pour N=1000, la précision entre l'une ou l'autre des méthodes, est de moins de 10-6.

Maintenant, cela n'a rien à voir avec la précision par rapport à un résultat voulu.

Si par exemple, la méthode 1 donne comme résultat 10.1 et la méthode 2 donne comme résultat 10.0, la précision entre les deux méthodes est de 0.1.
Mais si le résultat théorique est par exemple 100, ben les deux méthodes sont loin de donner le bon résultat

Bref voici un code te permettant de mieux faire la comparaison entre les deux méthodes :

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
clc
clear all
 
Nmax = 1000;
k = 1;
 
for N = 100:100:Nmax
 
        A = rand(N); B = rand(N); C = rand(N); D = rand(N,1);
 
    tic
    for i = 1:20
        M1 = A*B*C*D;
    end
    t1(k) = toc;
 
    tic
    for i = 1:20
        M2 = A*(B*(C*D));
    end
    t2(k) = toc;
 
    err(k) = max(abs(M1(:)-M2(:)));
 
    k = k+1;
end
whos
N = 100:100:Nmax;
 
figure
% [ax,h1,h2]= plotyy([N;N].',[t1;t2].',N,err,'semilogy','plot');
[ax,h1,h2]= plotyy([N;N].',[t1;t2].',N,err,'plot','plot');
set([h1;h2],'linewidth',2)
ylabel(ax(1),'t (s)');
ylabel(ax(2), 'err');
xlabel(ax(1), 'N');
legend([h1;h2],{'t1' 't2' 'err (max)'},'Location','NorthWest')

[soft001]

Fais attention, le calcul de la précision doit se faire en valeur absolue :

Code :

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

max(abs(t1(:)-t2(:)))

ce qui donne l'erreur maximale.

Oui tu as raison, je demande comment ça m'a échappé de la tête.

Pour le reste, tout ce que je dirais pour ma part, c'est que pour N=1000, la précision entre l'une ou l'autre des méthodes, est de moins de 10-6.

Maintenant, cela n'a rien à voir avec la précision par rapport à un résultat voulu.

Si par exemple, la méthode 1 donne comme résultat 10.1 et la méthode 2 donne comme résultat 10.0, la précision entre les deux méthodes est de 0.1.
Mais si le résultat théorique est par exemple 100, ben les deux méthodes sont loin de donner le bon résultat

Oui je suis d'accord avec toi, DutMATLAB, que l'erreur mentionné précédemment représente l'erreur entre les deux méthodes mais ça nous donne aussi une idée sur l'erreur qui s'ajoute l'erreur par rapport au résultat théorique si on choisi la mauvaise méthode (la première, je pense ???).
Une autre chose je pense pas que l'erreur par rapport à la théorie soit très grand puisque on a des simples multiplications .
Je reviens au erreur entre les deux méthodes, j'ai pensé que le problème vient du fait quand manipule des réels alors j'ai fait le test avec des entiers mais vraiment c'est pire :

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
clc
clear all
 
Nmax = 1000;
k = 1;
 
for N = 100:100:Nmax
 
        A = randi(1000,N); B = randi(1000,N); C = randi(1000,N);
        D = randi(1000,N,1);
 
    tic
    for i = 1:20
        M1 = A*B*C*D;
    end
    t1(k) = toc;
 
    tic
    for i = 1:20
        M2 = A*(B*(C*D));
    end
    t2(k) = toc;
 
    err(k) = max(abs(M1(:)-M2(:)));
 
    k = k+1;
end
whos
N = 100:100:Nmax;
 
figure
% [ax,h1,h2]= plotyy([N;N].',[t1;t2].',N,err,'semilogy','plot');
[ax,h1,h2]= plotyy([N;N].',[t1;t2].',N,err,'plot','plot');
set([h1;h2],'linewidth',2)
ylabel(ax(1),'t (s)');
ylabel(ax(2), 'err');
xlabel(ax(1), 'N');
legend([h1;h2],{'t1' 't2' 'err (max)'},'Location','NorthWest')