Ce fichier a été fait en Maple
3
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
3
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Niveau: Supérieur, Master, Bac+4
Ce fichier a été fait en Maple 8 Gauss sans fraction Voici une version classique de l'algorithme de Gauss. On commence par charger la librairie d'algèbre linéaire : > with(LinearAlgebra): > GaussClassique:=proc(M0) local M,n,etape,c,ligne,m,colonne; M:=copy(M0); n:=RowDimension(M); for etape from 1 to n-1 do c:=M[etape,etape]; for ligne from etape+1 to n do m:=M[ligne,etape]/c;M[ligne,etape]:=0; for colonne from etape+1 to n do M[ligne,colonne]:=M[ligne,colonne]-m*M[etape,colonne] end do end do; end do; M end proc: On fait une copie de la matrice passée en paramètre car elle est modifiée par la procédure. On tire une matrice au hasard : > M1:=RandomMatrix(5,5): et on teste notre procédure : > GaussClassique(M1); ? ? ???????????????????????? ? ? ???????????????????????? -66 -65 20 -90 30 0 -295 6 29 3 -96 87 0 0 118168 3245 -43316 295 -14693 295 0 0 0 -1142260 14771 -6513621 29542 0 0 0 0 344319363 652720 Les horribles fractions ! • Changer la procédure en multipliant les lignes pour éviter les fractions et rester en nombres entiers > GaussMod1:=proc(M0) local
Voir
Ce fichier a été fait en Maple 8 Gauss sans fraction Voici une version classique de l'algorithme de Gauss. On commence par charger la librairie d'algèbre linéaire : > with(LinearAlgebra): > GaussClassique:=proc(M0) local M,n,etape,c,ligne,m,colonne; M:=copy(M0); n:=RowDimension(M); for etape from 1 to n-1 do c:=M[etape,etape]; for ligne from etape+1 to n do m:=M[ligne,etape]/c;M[ligne,etape]:=0; for colonne from etape+1 to n do M[ligne,colonne]:=M[ligne,colonne]-m*M[etape,colonne] end do end do; end do; M end proc: On fait une copie de la matrice passée en paramètre car elle est modifiée par la procédure. On tire une matrice au hasard : > M1:=RandomMatrix(5,5): et on teste notre procédure : > GaussClassique(M1); ? ? ???????????????????????? ? ? ???????????????????????? -66 -65 20 -90 30 0 -295 6 29 3 -96 87 0 0 118168 3245 -43316 295 -14693 295 0 0 0 -1142260 14771 -6513621 29542 0 0 0 0 344319363 652720 Les horribles fractions ! • Changer la procédure en multipliant les lignes pour éviter les fractions et rester en nombres entiers > GaussMod1:=proc(M0) local
- librairie d'algèbre linéaire
- gauss sans fraction
- version classique de l'algorithme de gauss
- gaussmod1:=proc
- taille des entiers
- c0 end
Ce fichier a été fait en Maple 8
Gauss sans fraction
Voici une version classique de l’algorithme de Gauss.
On commence par charger la librairie d’algèbre linéaire :
>
with(LinearAlgebra):
>
GaussClassique:=proc(M0)
local M,n,etape,c,ligne,m,colonne;
M:=copy(M0);
n:=RowDimension(M);
for etape from 1 to n-1 do
c:=M[etape,etape];
for ligne from etape+1 to n do
m:=M[ligne,etape]/c;M[ligne,etape]:=0;
for colonne from etape+1 to n do
M[ligne,colonne]:=M[ligne,colonne]-m*M[etape,colonne]
end do
end do;
end do;
M
end proc:
On fait une copie de la matrice passée en paramètre car elle est modifiée par la procédure.
On tire une matrice au hasard :
>
M1:=RandomMatrix(5,5):
et on teste notre procédure :
>
GaussClassique(M1);
-66
-65
20
-90
30
0
-295
6
29
3
-96
87
0
0
118168
3245
-43316
295
-14693
295
0
0
0
-1142260
14771
-6513621
29542
0
0
0
0
344319363
652720
Les horribles fractions !
•
Changer la procédure en multipliant les lignes pour éviter les fractions et rester en nombres
entiers
>
GaussMod1:=proc(M0)
local M,n,etape,c,ligne,m,colonne;
M:=copy(M0);
n:=RowDimension(M);
for etape from 1 to n-1 do
c:=M[etape,etape];
for ligne from etape+1 to n do
m:=M[ligne,etape];M[ligne,etape]:=0;
for colonne from etape+1 to n do
M[ligne,colonne]:=c*M[ligne,colonne]-m*M[etape,colonne]
end do
end do;
end do;
M
end proc:
•
Remarquer en faisant plusieurs essais que les entiers de la troisième ligne sont divisibles par le
pivot de la première étape
>
M1:=RandomMatrix(5,5);
:=
M1
61
22
-41
-82
5
96
-81
24
59
-75
53
-99
65
-69
38
61
-2
1
23
97
-70
-98
-42
25
-82
>
GaussMod1(M1);
61
22
-41
-82
5
0
-7053
5400
11471
-5055
0
0
-4384314
81682294
-50901084
0
0
0
954664898395878
-311384437939440
0
0
0
0
1288750964289655464238797458280
>
-4384314/61,81682294/61,-50901084/61;
,
,
-71874 1339054 -834444
Pour le corrigé un seul essai suffira : ça n’a vraiment pas l’air d’un hasard.
On voit que la taille des entiers augmente à une vitesse impressionante. Laquelle ?
Croissance des entiers
L’opération M[ligne,colonne]:=c*M[ligne,colonne]-m*M[etape,colonne] double la taille des
entiers à chaque étape !
C’est évident sur l’exemple. Quelle catastrophe !
•
Une démonstration ?
Que les entiers de la troisième ligne sont divisibles par le pivot de la première étape
>
M:=Matrix(3,3,(i,j)->m[i,j]);
:=
M
m
,
1 1
m
,
1 2
m
,
1 3
m
,
2 1
m
,
2 2
m
,
2 3
m
,
3 1
m
,
3 2
m
,
3 3
>
M1:=GaussMod1(M);
M1
:=
[
,
,
]
m
,
1 1
m
,
1 2
m
,
1 3
[
,
,
]
0
-
m
,
1 1
m
,
2 2
m
,
2 1
m
,
1 2
-
m
,
1 1
m
,
2 3
m
,
2 1
m
,
1 3
0
0
(
)
-
m
,
1 1
m
,
2 2
m
,
2 1
m
,
1 2
(
)
-
m
,
1 1
m
,
3 3
m
,
3 1
m
,
1 3
[
,
,
(
)
-
m
,
1 1
m
,
3 2
m
,
3 1
m
,
1 2
(
)
-
m
,
1 1
m
,
2 3
m
,
2 1
m
,
1 3
-
]
>
factor(M1[3,3]);
m
,
1 1
m
,
1 1
m
,
3 2
m
,
2 3
m
,
1 1
m
,
2 2
m
,
3 3
m
,
3 2
m
,
2 1
m
,
1 3
m
,
2 2
m
,
3 1
m
,
1 3
m
,
2 1
m
,
1 2
m
,
3 3
-
+
+
-
-
(
m
,
3 1
m
,
1 2
m
,
2 3
+
)
•
Modifier en conséquence votre procédure pour réduire la taille des entiers.
>
GaussMod2:=proc(M0)
local M,n,etape,c0,c1,ligne,m,colonne;
M:=copy(M0);
n:=RowDimension(M);c0:=1;
for etape from 1 to n-1 do
c1:=M[etape,etape];
for ligne from etape+1 to n do
m:=M[ligne,etape];M[ligne,etape]:=0;
for colonne from etape+1 to n do
M[ligne,colonne]:=(c1*M[ligne,colonne]-m*M[etape,colonne])/c0
end do
end do;
c0:=c1
end do;
M
end proc:
>
GaussMod2(M1);
61
22
-41
-82
5
0
-7053
5400
11471
-5055
0
0
-71874
1339054
-834444
0
0
0
-36376206
11864880
0
0
0
0
-26033351380
C’est mieux.
