Giansalvo EXIN CirrincioneGiansalvo EXIN Cirrincione
unité #3unité #3
rappelsrappels
Définition : la fonction T(n) est dite « grand grand OO » de f(n) que l’on
note T(n)=O(f(n)), s’il existe deux constantes C et n0
telles que 0 ( ) ( )n n T n C f n
32 132493log14 xxxx O
Problème : fonction f : X Y de l’espace vectoriel normé
X des entrées à l’espace vectoriel normé Y des solutions.
Algorithme :f X Y
Axiom fondamental de l’arithmétique en virgule flottante
, , avec telle que 1machinex y F x y x y
rappelsrappels
Problème : fonction f : X Y de l’espace vectoriel normé
X des entrées à l’espace vectoriel normé Y des solutions.
Algorithme :f X Y
Stabilité d’un algorithmeStabilité d’un algorithme
est stable si , telle que
machine
machine
f x X x
f x f xO
f x
x xO
x
A stable algorithm gives nearly the right A stable algorithm gives nearly the right answer to nearly the right question.answer to nearly the right question.
rappelsrappels
Stabilité d’un algorithmeStabilité d’un algorithme
est stable si , telle que
machine
machine
f x X x
f x f xO
f x
x xO
x
A stable algorithm gives nearly the right A stable algorithm gives nearly the right answer to nearly the right question.answer to nearly the right question.
x
x f
f fx
rappelsrappels
Stabilité Stabilité backwardbackward d’un algorithme d’un algorithme
est stable backward si , telle que
machine
f x X
f x f x
xO
x
x
x
A backward stable algorithm gives exactly the right A backward stable algorithm gives exactly the right answer to nearly the right question.answer to nearly the right question.
x
x f
f fx fx
xx f
f
fxfx
Résolution de systèmes linéairesRésolution de systèmes linéaires
x
1 21
, ,
range span , , ,
rang rang
m n m n
n
j j nj
A b x
a x b b A a
A b
a a
Ax b
A Théorème de Théorème de Rouché-CapelliRouché-Capelli
La solution d’un système linéaire (A carrée inversible n x n) ne s’obtient pas en calculant l’inverse de A. Le calcul de A-1 est équivalent à la résolution des n systèmes linéaires :
1j jAu e j n
où uj est le j-ème vecteur de la base de Kn.
On ne change pas la solution lorsque l’on :
1. permute 2 lignes
2. permute 2 colonnes
3. divise par un même terme non nul les éléments d’une ligne
4. ajoute ou retranche à une ligne un certain nombre de fois une autre ligne
4 principes fondamentaux4 principes fondamentaux
Résolution de systèmes linéaires par des Résolution de systèmes linéaires par des méthodes directesméthodes directes
StratégieStratégie : transformer le système linéaire transformer le système linéaire en un système équivalent … facile à résoudreen un système équivalent … facile à résoudre
triangulaire !triangulaire !
Résolution de systèmes linéaires par des Résolution de systèmes linéaires par des méthodes directesméthodes directes
Algorithme
fait
àjusqu' 1pour
ii
ii a
bx
ni
Fonction x = diago(A,b)
11 11 0 0 0
0 0
0 0 0 0
0 0
0 0 0
i i
n n
ii
nn
a
a
bx
x b
x ba
problèmeproblème
nia
bx
ii
ii ,1 ,
solution
AA matrice diagonale matrice diagonale
Résolution de systèmes linéaires par des Résolution de systèmes linéaires par des méthodes directesméthodes directes
A triangulaire inférieureproblèmeproblème
11
1
1
1
10 0 0
0
0 0
0
i ii
n ni nn
i
n
i
n
bx
x b
x b
a
a a
a a a
1
1
1
1
11
i
jjiji
iii xab
ax
ab
x
ommes
solution
Algorithme
Fonction x = trianginf(A,b)
fait
omme
fait ommeomme
1 àjusqu' 1pour
omme
àjusqu' 2pour
11
11
iii
jij
i
as
x
xassij
bs
ni
ab
x
Résolution de systèmes linéaires par des Résolution de systèmes linéaires par des méthodes directesméthodes directes
A triangulaire inférieureproblèmeproblème
11
1
1
1
10 0 0
0
0 0
0
i ii
n ni nn
i
n
i
n
bx
x b
x b
a
a a
a a a
1
1
1
1
11
i
jjiji
iii xab
ax
ab
x
ommes
solution 2 flopsO n 2 flopsO n
1
det( )n
iii
A a
Résolution de systèmes linéaires par des Résolution de systèmes linéaires par des méthodes directesméthodes directes
A triangulaire supérieureproblèmeproblème11 1 111
0
0 0
0
0 0 0
i
i n
ii i
n
n
n nn
i
bx
x b
x b
a a a
a a
a
solution
1
1
n
ijjiji
iii
n
nn
xaba
x
a
bx
ommes
Algorithme
Fonction x = triang(A,b)
fait
omme
fait ommeomme
àjusqu' 1pour
omme
1 àjusqu' 1pour
iii
jij
i
nn
nn
as
x
xassnij
bs
ni
a
bx
2 flopsO n 2 flopsO n
Résolution de systèmes linéaires par des Résolution de systèmes linéaires par des méthodes directesméthodes directes
A triangulaire supérieureproblèmeproblème11 1 111
0
0 0
0
0 0 0
i
i n
ii i
n
n
n nn
i
bx
x b
x b
a a a
a a
a
solution
1
1
n
ijjiji
iii
n
nn
xaba
x
a
bx
ommes
Chaque composante xi apparaissant comme une fonction linéaire de bi , bi+1 , … , bn , ceci montre que l’inverse d’une matrice triangulaire est une matrice triangulaire du même type.
Méthode de remontée
x et triangulaire supérieure telle
BACKWARD S
s que
TABLE
n n
machine
n
A A x b
AO
A
x A
La méthode de GaussLa méthode de Gauss
AuAu = = bb , , AA : matrice inversible : matrice inversible
I.I. Une procédure d’Une procédure d’éliminationélimination qui équivaut à déterminer une qui équivaut à déterminer une matrice inversible matrice inversible MM telle que telle que M AM A soit triangulaire supérieure. soit triangulaire supérieure.
II.II. On calcule simultanément le vecteur On calcule simultanément le vecteur M bM b..III.III. On résout le système linéaire On résout le système linéaire M A uM A u = = M b M b
par lapar la méthode de la méthode de la remontéeremontée..
En pratique, on ne calcule pas explicitement la matrice En pratique, on ne calcule pas explicitement la matrice MM, mais seulement la matrice , mais seulement la matrice M AM A et le vecteur et le vecteur M bM b. .
6 2
8 2 3
0 3
6242
432
4321
421
321
xxx
xxxx
xxx
xxx
La méthode de GaussLa méthode de Gauss
exempleexemple
pivot (1)
6 2
8 2 3
0 3
6242
432
4321
421
321
xxx
xxxx
xxx
xxx
(2) = (2) - (a(2) = (2) - (a2121/pivot(1)) (1)/pivot(1)) (1)
La méthode de GaussLa méthode de Gauss
exempleexemple
6 2
8 2 3
0 3
6242
432
4321
421
321
xxx
xxxx
xxx
xxx
6 2
8 2 3
3 0
6242
432
4321
432
321
xxx
xxxx
xxx
xxx
La méthode de GaussLa méthode de Gauss
exempleexemple
(2) = (2) - (a(2) = (2) - (a2121/pivot(1)) (1)/pivot(1)) (1)
6 2
8 2 3
0 3
6242
432
4321
421
321
xxx
xxxx
xxx
xxx
6 2
71 2 4 7 0
3 0
6242
432
432
432
321
xxx
xxx
xxx
xxx
Le première variable à été éliminée de toutes les équations sauf une.
La méthode de GaussLa méthode de Gauss
exempleexemple
(3) = (3) - (a(3) = (3) - (a3131/pivot(1)) (1)/pivot(1)) (1)
La méthode de GaussLa méthode de Gauss
exempleexemple
pivot (2)
6 2
71 2 4 7 0
3 0
6242
432
432
432
321
xxx
xxx
xxx
xxx
fait problème""sinon fait
fait
àjusqu' 1pour
àjusqu' 1pour
alors 0 si
*)pivot de stratégie (*
1 àjusqu' 1pour
kjik
ijij
kik
ii
kk
apivot
aaa
nkj
bpivot
abb
nki
pivot
apivot
nk
Fonction Fonction A,bA,b = descent ( = descent (A,bA,b))
TriangularisationTriangularisation
La méthode de GaussLa méthode de Gauss
La méthode de GaussLa méthode de Gauss
U, c = descent (A,b)
x = triang (U,c)
Fonction Fonction xx = Gauss( = Gauss( A,b A,b ) )
La méthode de GaussLa méthode de GaussPremière étape de l’éliminationPremière étape de l’éliminationL’un au moins des éléments de la première colonne est différent de zéro, sans quoi la matrice serait singulière. On choisit alors l’un des coefficients non nuls (premier pivotpremier pivot) de la première colonne de A. Ensuite, on échange la ligne du pivot avec la première ligne, ce qui revient à multiplier A à gauche par une matrice de permutation matrice de permutation PP. Pour l’échange des i-ème et j-ème lignes, on multiplie à gauche par la matrice P suivante.
1
1
1
1
0 1
1
1
1
1
1 0
i jP P
11
det 1
si est le pivot
P
P I a
ii
jj
ii jj
1ij ijP P
La méthode de GaussLa méthode de GaussPremière étape de l’éliminationPremière étape de l’éliminationL’un au moins des éléments de la première colonne est différent de zéro, sans quoi la matrice serait singulière. On choisit alors l’un des coefficients non nuls (premier pivotpremier pivot) de la première colonne de A. Ensuite, on échange la ligne du pivot avec la première ligne, ce qui revient à multiplier A à gauche par une matrice de permutation matrice de permutation PP. Pour l’échange des i-ème et j-ème lignes, on multiplie à gauche par la matrice P suivante.
1ij ijP P
La méthode de GaussLa méthode de GaussPremière étape de l’éliminationPremière étape de l’élimination
11 avec 0ijPA
Par des combinaisons linéaires appropriées de la première ligne et des autres lignes de la matrice PA, on annule tous les éléments de la première colonne de PA situés sous la diagonale, la première ligne restant inchangée.
B EPA
det 1
det det det det det
est inversible
E
B E P A A
B
La méthode de GaussLa méthode de GaussSeconde étape de l’éliminationSeconde étape de l’éliminationElle consiste à effectuer les mêmes opérations que précédemment, mais seulement sur la sous-matrice ( bij ) , 2 i, j n , en laissant inchangée la première ligne, et ainsi de suite …
( ( kk--1 1 )-ème étape de l’élimination ()-ème étape de l’élimination (22 kk nn )
1 1 2 2 1 1 1k k kA E P E P E P A
La méthode de GaussLa méthode de Gausskk-ème étape de l’élimination (-ème étape de l’élimination (22 k k nn )
det det est inversible 0 , pivotkk k i kA A A a k i n
avec 0k kk k i j k kP A
1k k k kA E P A
La méthode de GaussLa méthode de Gauss
( ( nn--1 1 )-ème étape de l’élimination)-ème étape de l’élimination
1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A
1 1 2 2 1 1 inversible n nM E P E P E P
-ème pivotnnn n n n
A n
La méthode de GaussLa méthode de Gauss
La méthode de GaussLa méthode de Gaussexempleexemple
4 110 1
21 1x
Trouver Trouver xx en ne gardant en ne gardant que que 33 chiffres significatifs chiffres significatifs après la virguleaprès la virgule
représentation: 0. 10eddd
1.00010... 1
0.99990... 1exactex
pivotpivot
44
4
2 101 1
110
0 0
1x
4
44 1
110 01
0 1 100x x
Que se passe t’il si on prend le système à l’envers…?Que se passe t’il si on prend le système à l’envers…?
La méthode de GaussLa méthode de Gaussexempleexemple
4 110 1
21 1x
Trouver Trouver xx en ne gardant en ne gardant que que 33 chiffres significatifs chiffres significatifs après la virguleaprès la virgule
représentation: 0. 10eddd
1.00010... 1
0.99990... 1exactex
4
1 1 2
10 1 1x
pivotpivot
4 41 10
1 1
00 1 2 1
2x
1 2
0 1
1 1
11xx
effet de la division par un pivot trop petiteffet de la division par un pivot trop petit
Gaussian elimination Gaussian elimination without pivotingwithout pivoting is is neither backward stable neither backward stable nor stablenor stable. Additionally, the triangular matrices it generates have . Additionally, the triangular matrices it generates have condition numbers that may be arbitrarily greater than those of A condition numbers that may be arbitrarily greater than those of A itself, leading to additional sources of instability in the forward itself, leading to additional sources of instability in the forward and back substitution phases of the solution of and back substitution phases of the solution of A xA x = = bb . .
si un pivot est nul, on permute deux lignessi un pivot est nul, on permute deux lignes si tous les pivots restant sont nuls, la matrice est singulièresi tous les pivots restant sont nuls, la matrice est singulière (i.e. le système d’équations n’admet pas de solution unique) stratégie pour minimiser les erreurs d’arrondis.stratégie pour minimiser les erreurs d’arrondis. on choisi le plus grand pivot possible (en valeur absolue) et donc on permute les lignes (voir les colonnes associées) c’est la stratégie du pivot maximal (partiel (lignes) ou total)
Choix du pivotChoix du pivot
Choix du pivotChoix du pivot
kk-ème étape de l’élimination (-ème étape de l’élimination (22 k k nn )
Stratégie du pivot partielStratégie du pivot partiel
Le pivot est l'un des éléments , , vérifiant
maxk krk ik
k
k
kr
i n
a k r
a
n
a
O( n2 ) flops
Choix du pivotChoix du pivot
kk-ème étape de l’élimination (-ème étape de l’élimination (22 k k nn )
Stratégie du pivot totalStratégie du pivot total
,
Le pivot est l'un des éléments , , , vérifiant
maxk krs ik
k i j n
krka k r s n
a a
O( n3 ) flops
Il faut aussi effectuer Il faut aussi effectuer un un échange de échange de colonnescolonnes qui equivaut qui equivaut a multiplier la a multiplier la matrice matrice AAkk à droiteà droite
par une matrice de par une matrice de permutation.permutation.
FLOPSFLOPS
32 flops
3O n
FLOPSFLOPS
32 flops
3O n
Formules de CramerFormules de CramerFormules de CramerFormules de Cramer
111 1, 1 1, 1 1
21 2, 1 2, 1 2
, 1 ,
2
1 1
det
det ,
i i n
i i ni
n n i n i
ii
n nn
a a a a
a a a aB
a a a
Bx
A
b
b
ab
1 ! additions
2 ! multiplications
divisions
n
n
n
Pour n = 10 par exemple, on obtient environ :Pour n = 10 par exemple, on obtient environ :• 700 opérations pour Gauss700 opérations pour Gauss• 400 000 000 opérations pour Cramer !400 000 000 opérations pour Cramer !
Pour n = 10 par exemple, on obtient environ :Pour n = 10 par exemple, on obtient environ :• 700 opérations pour Gauss700 opérations pour Gauss• 400 000 000 opérations pour Cramer !400 000 000 opérations pour Cramer !
Gauss-JordanGauss-Jordan
Gauss-JordanGauss-Jordan
La méthode de Gauss-Jordan est utilisée pour le calcul de l’inverse d’une matrice donnée : on résout simultanément les n systèmes linéaires :
La méthode de Gauss-Jordan est utilisée pour le calcul de l’inverse d’une matrice donnée : on résout simultanément les n systèmes linéaires :
, 1j jAu e j n
, 1n j jA u Me j n
diagonalediagonale
La factorisation LU d’une matriceLa factorisation LU d’une matrice
1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A 1 1 111 12 1
2 222 2
n
n
n
n
nn
a a a
a a
a
U A
1
,
,
,
1
1 , 1
1
1
1kik
k k
n k
k kk
k
ik
E k
a
n
k i na
1,
,
0
0k
k k
n k
*
*
*
* * *
1 *
0k k
k k k k
k k k
k
k k k k
k k
e
I e I e I e e I
E I e
E I e
1,
,
1
1
1
1
1
k k
n k
kE
La factorisation LU d’une matriceLa factorisation LU d’une matrice
1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A
1,
,
1
1
1
1
1
k k
n k
kE
11 2 1 2 1n nE E E PU AP P
1 11 1 1 1knk k k nEP P P PE
permutations seulement sur k
1
1,
,
1
1
1
1
k k
n k
kE
La factorisation LU d’une matriceLa factorisation LU d’une matrice
1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A
11 2 1 2 1n nE E E PU AP P
1,
,
0
0k
k k
n k
1 1 *
*
*1 1
*
1 *
1
* *1 11
0
k k k k
k k
k k k
k k
k
k
k k k
kk
e
E I e
E I e
E E I e eI e I e
1
1,
,
1
1
1
1
k k
n k
kE
21
31 3
1 1 1 11 2 1 2
1 2
2
1
1
,
1
1
1
1
1n n n n
n nL E E E E E E
1 2 1nP P P P PA LU
La factorisation LU d’une matriceLa factorisation LU d’une matrice
PA LU
, : , :
,1: 1 ,1: 1
,: ,:
, ,
for 1 to 1
select to maximize (* stratégie du pivot partiel
p
*)
(* *)
ermutationik
k k n i k n
k k i k
k i
U A L I P I
k n
i k u
u u
p p
, : , : , :
for 1 to
jkj k
kk
j k n j k n j k k k n
j k n
u
u
u u u
Fonction P,L,U = décompose (A)
La factorisation LU d’une matriceLa factorisation LU d’une matrice
1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A 1 1 111 12 1
2 222 2
n
n
n
n
nn
a a a
a a
a
U A
1
,
,
,
1
1 , 1
1
1
1kik
k k
n k
k kk
k
ik
E k
a
n
k i na
1,
,
0
0k
k k
n k
*
*
*
* * *
1 *
0k k
k k k k
k k k
k
k k k k
k k
e
I e I e I e e I
E I e
E I e
1,
,
1
1
1
1
1
k k
n k
kE
La factorisation LU d’une matriceLa factorisation LU d’une matrice
1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A
1,
,
1
1
1
1
1
k k
n k
kE
11 2 1 2 1n nE E E PU AP P
1 11 1 1 1knk k k nEP P P PE
permutations seulement sur k
1
1,
,
1
1
1
1
k k
n k
kE
La factorisation LU d’une matriceLa factorisation LU d’une matrice
1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A
11 2 1 2 1n nE E E PU AP P
1,
,
0
0k
k k
n k
1 1 *
*
*1 1
*
1 *
1
* *1 11
0
k k k k
k k
k k k
k k
k
k
k k k
kk
e
E I e
E I e
E E I e eI e I e
1
1,
,
1
1
1
1
k k
n k
kE
21
31 3
1 1 1 11 2 1 2
1 2
2
1
1
,
1
1
1
1
1n n n n
n nL E E E E E E
1 2 1nP P P P PA LU
La factorisation LU d’une matriceLa factorisation LU d’une matrice
PA LU
, : , :
,1: 1 ,1: 1
,: ,:
, ,
for 1 to 1
select to maximize (* stratégie du pivot partiel
p
*)
(* *)
ermutationik
k k n i k n
k k i k
k i
U A L I P I
k n
i k u
u u
p p
, : , : , :
for 1 to
jkj k
kk
j k n j k n j k k k n
j k n
u
u
u u u
Fonction P,L,U = décompose (A)
La factorisation LU d’une matriceLa factorisation LU d’une matrice
PA LU
Ax b PA x Pb LU x PLy Pb
Ux yb
LL
00
00
UUAAPP ==
P,L,UP,L,U = décompose ( = décompose (AA))
yy = triang ( = triang (L, P*bL, P*b) )
xx = triang ( = triang (U, yU, y) )
Fonction Fonction xx = LU( = LU(A,bA,b) )
P = 1P = 1A LU
11 1
1
, 1k
k
k kk
a a
k n
a a
Soit Soit AA = ( = ( aaij ij ) une matrice ) une matrice
carrée d’ordre carrée d’ordre nn telle que les telle que les n n sous-matrices diagonalessous-matrices diagonales
soient soient inversiblesinversibles. Alors il . Alors il existeexiste une matrice triangulaire inférieure une matrice triangulaire inférieure LL et une matrice triangulaire et une matrice triangulaire supérieure supérieure U U telles que telles que AA = = LL UU . . De plus, une telle factorisation est De plus, une telle factorisation est uniqueunique..
P = 1P = 1A LU
Matrices spécialesMatrices spéciales((pas de stratégie de pivoting dans la factorisation LUpas de stratégie de pivoting dans la factorisation LU) )
1
1, ,n
ii ijjj i
a a i n
AA est diagonalement est diagonalement dominantedominante
1
0 , 1, , ,
0 , 1, ,
i j
i j
a i j n i j
A i j n
AA est une est une
MM-matrice-matrice
AA est une matrice symétrique définie positive est une matrice symétrique définie positive
Stabilité de la factorisation Stabilité de la factorisation LULU
Let the factorization P A = L U of a matrix A be computed by Gaussian elimination with partial pivoting. Then the computed matrices P, L and U satisfy :
~ ~ ~
, machine
ALU PA A O
L U
backward stable
backward unst
Gaussian elimination is
Gaussian elimination ei abls
L U O A
L U O A
For Gaussian elimination without pivoting, both L and U can be unboundedly large.
Pivoting, ensures that L and U are not too large.
1L O
backward
stable
U O A
Stabilité de la factorisation Stabilité de la factorisation LULU
For Gaussian elimination without pivoting, both L and U can be unboundedly large.
Pivoting, ensures that L and U are not too large.
1L O
backward
stable
U O A
, machine
ALU PA A O
L U
,
,
max
max
growth factor
iji j
iji j
u
a
U O A
,
if there are no ties in the pivot selection
machine
ALU PA A O
P
A
P
Stabilité de la factorisation Stabilité de la factorisation LULU
,
,
max
max
growth factor
iji j
iji j
u
a
,
if there are no ties in the pivot selection
machine
ALU PA A O
P
A
P
3 23
1machine
x An n
AxA
A
1
0.25ln
définie positive
stratégie du pivot partiel
stratégie du pivot tot
1
2
1.8 al
n
nn
A
Stabilité de la factorisation Stabilité de la factorisation LULU
,
,
max
max
growth factor
iji j
iji j
u
a
,
if there are no ties in the pivot selection
machine
ALU PA A O
P
A
P
3 23
1machine
x An n
AxA
A
1
0.25ln
définie positive
stratégie du pivot partiel
stratégie du pivot tot
1
2
1.8 al
n
nn
A
Gauss elimination is backward stablebackward stable if = = OO((11)) uniformly for all matrices of a given dimension n
Stabilité de la factorisation Stabilité de la factorisation LULU
,
,
max
max
growth factor
iji j
iji j
u
a
exempleexemple 1 0 0 0 1 1 0 0 0
1 1 0 0 1 0 1 0 0
1 1 1 0 1 0 0 1 0
1 1 1 1 1 0 0 0 1
1 1 1 1 1 0 0
1
2
4
8
10 60
A U
1 1
1 1 1
1 1 1 1
1 1 1 1 1
1 1 1 1
1 1
1 1 1
1 1 1 1
1 1 1
1
2
4
1
1 1 8
161 1 1 1 1
12 16n
A growth factor of order 2n corresponds to a loss of the order of n bits of precision.
Stabilité de la factorisation Stabilité de la factorisation LULU
Despite this example, Gaussian elimination with partial pivoting is utterly stable in practice. Large factors U never seem to appear in real applications.
Random matrix : each entry is an independent sample from the real normal distribution of mean 0 and standard deviation n -1/2 .
A = randn(n,n)/sqrt(n)A = randn(n,n)/sqrt(n)
Stabilité de la factorisation Stabilité de la factorisation LULU
Despite this example, Gaussian elimination with partial pivoting is utterly stable in practice. Large factors U never seem to appear in real applications.
Random matrix : each entry is an independent sample from the real normal distribution of mean 0 and standard deviation n -1/2 .
A = randn(n,n)/sqrt(n)A = randn(n,n)/sqrt(n)
La factorisation LU d’une matrice La factorisation LU d’une matrice tridiagonaletridiagonale
La factorisation LU d’une matrice La factorisation LU d’une matrice tridiagonaletridiagonale
, tridiagonaleAv d A
1
diag i
i
1
11
22
21
1
1
1
1n
nn
n
c
zz
ca
zz
ca
z
A L U
111
1
, , 2kk k
k
cz z c k n
b
11
1
111 1
1 1
1
1
2,3, ,
2,3, ,
1, 2, ,1
k k k kk k k k
k
n n k
k k
kk
k k
k
k k k
k
ccz z
b b a z
z d a wdw w d a w
b c
v
b a
w v w z v
k n
k n
k n
z
n
suite
L w d 1Uv w
3 1 additions
3 1 multiplications
2 divisions
n
n
n
328 vs.
3 O n O n
La factorisation LU d’une matrice-bandeLa factorisation LU d’une matrice-bande
no no pivotingpivoting
pivotingpivoting
FINEFINE