MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 1 : p.

1/1

**** EXERCICE 1 ****

On considère un ordinateur qui calcule en utilisant le système de réels-machine R = R (9, 7, −545, 544).
1◦ ) a) Réels que connaît et peut manipuler cet ordinateur.
Comme R = R (b, L, emin , emax ), avec b = 9, L = 7, emin = −545 et emax = 544, alors les réels connus de cet
ordinateur sont ceux de la forme
x = ∗M × be ,
avec :
1. b = 9 , la base utilisée par cet ordinateur pour représenter les nombres réels ;

2. ∗ = signe(x) ∈ { +, −} , le signe du réel x ;

9
3. M = mantR (x) = 0, c1 c2 c3 c4 c5 c6 c7 , la mantisse (normalisée) du réel x en base b = 9, où :

c1 ∈ [ 1 (1) 8 ] et ∀ i = 2 (1) 7, ci ∈ [ 0 (1) 8 ] ;

4. e = expoR (x) ∈ [ − 545 (1) 544 ] , l’exposant du réel x dans la base b = 9.

• Cependant, signalons aussi que 0 ∈ R , avec :

9
signe(0) = + , mantR (0) = 0, 000 000 0 , expoR (0) = −545 .

b) Nombre réels que cela fait en tout.

D’une part, 0 ∈ R , ce qui fait déjà un réel, plus, pour chacun des autres réels x ∈ R :
1. 2 possibilités pour le signe ∗ de x ;
2. 8 valeurs possibles pour le chiffre c1 et 9 valeurs possibles pour chacun des 6 chiffres ci , i = 2 (1) 7,
=⇒ 8 × 96 = 4 251 528 valeurs possibles pour la mantisse M de x ;
3. 544 − (−545) + 1 = 1090 valeurs possibles pour l’exposant e de x ;

=⇒ card(R ) = 1 + 2 × 8 × 96 × 1090 = 9 268 331 041 ≃ 9, 268 × 109 .

c) Plus grand > 0 et plus petit > 0 parmi ces réels.

9
1. le plus grand réel > 0 de R est max(R∗+ ) = 0, 888 888 8 × 9544 ;

9
2. le plus petit réel > 0 de R est min(R∗+ ) = 0, 100 000 0 × 9−545 .

2◦ ) a) Le nombre 1 ∈ R . On le voit comme suit :

9
On a : 1 = 90 = 9−1+1 = 9−1 × 91 = +0, 100 000 0 × 91 ,
9
=⇒ 1 ∈ R , avec signe(1) = + , mantR (1) = 0, 100 000 0 , expoR (1) = 1 ∈ [ − 545 (1) 544 ] .

9
b) Le successeur du nombre 1 dans R est : succR (1) = 0, 100 000 1 × 91 .

9
c) Le prédécesseur du nombre 1 dans R est : predR (1) = 0, 888 888 8 × 90 .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fin de la Correction de l’EXERCICE 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 2 : p.1/3

**** EXERCICE 2 ****

1◦ ) a) Le 1er point du Lemme d’Aitken-Neville dit, à propos de pLx0 ··· xn f , que :

(x − x0 ) · (pLx1 ··· xn f )(x) − (x − xn ) · (pLx0 ··· xn−1 f )(x)

∀ x ∈ IR, (pLx0 ··· xn f )(x) = . (E2.1 )
xn − x0

b) Ce résultat relie 3 polynômes d’interpolation de Lagrange. Définition de chacun d’entre eux.

• • Pour pLx0 ··· xn f , l’une ou l’autre des définitions suivantes est valable :
• Définition 1 :
pLx0 ··· xn f est l’unique polynôme de degré 6 n qui coïncide avec la fonction f en x0 , · · · , xn .

• Définition 1’ :
pLx0 ··· xn f est l’unique polynôme de degré 6 n qui prend les mêmes valeurs que f en x0 , · · · , xn .

• Définition 1” :
pLx0 ··· xn f est l’unique polynôme P ∈ IRn [x] vérifiant : ∀ t ∈ { x0 , · · · , xn }, P (t) = f (t) .

• Définition 1” ’ :
pLx0 ··· xn f est l’unique polynôme de degré 6 n qui interpole la fonction f en x0 , · · · , xn .

• • Pour pLx1 ··· xn f , l’une ou l’autre des définitions suivantes est valable :
• Définition 2 :
pLx1 ··· xn f est l’unique polynôme de degré 6 n − 1 qui coïncide avec la fonction f en x1 , · · · , xn .

• Définition 2’ :
pLx1 ··· xn f est l’unique polynôme de degré 6 n − 1 qui prend les mêmes valeurs que f en x1 , · · · , xn .

• Définition 2” :
pLx1 ··· xn f est l’unique polynôme P ∈ IRn−1 [x] vérifiant : ∀ t ∈ { x1 , · · · , xn }, P (t) = f (t) .

• Définition 2” ’ :
pLx1 ··· xn f est l’unique polynôme de degré 6 n − 1 qui interpole la fonction f en x1 , · · · , xn .

• • Pour pLx0 ··· xn−1 f , l’une ou l’autre des définitions suivantes est valable :
• Définition 3 :
pLx0 ··· xn−1 f est l’unique polynôme de degré 6 n − 1 qui coïncide avec la fonction f en x0 , · · · , xn−1 .

• Définition 3’ :
pLx0 ··· xn−1 f est l’unique polynôme de degré 6 n − 1 qui prend les mêmes valeurs que f en x0 , · · · , xn−1 .

• Définition 3” :
pLx0 ··· xn−1 f est l’unique polynôme P ∈ IRn−1 [x] vérifiant : ∀ t ∈ { x0 , · · · , xn−1 }, P (t) = f (t) .

• Définition 3” ’ :
pLx0 ··· xn−1 f est l’unique polynôme de degré 6 n − 1 qui interpole la fonction f en x0 , · · · , xn−1 .

2◦ ) a) Le 2 ème point du Lemme d’Aitken-Neville dit que :

f [ x1 , · · · , xn ] − f [ x0 , · · · , xn−1 ]
f [ x0 , · · · , xn ] = .
xn − x0
MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 2 : p.2/3

b) Ce résultat relie 3 coefficients particuliers. Définition de chacun d’entre eux.

1. f [ x0 , · · · , xn ] est le coefficient de xn dans (pLx0 ··· xn f )(x) ;

2. f [ x1 , · · · , xn ] est le coefficient de xn−1 dans (pLx1 ··· xn f )(x) ;

3. f [ x0 , · · · , xn−1 ] est le coefficient de xn−1 dans (pLx0 ··· xn−1 f )(x) .

c) De l’un des résultats précédents, déduisons (et avec des notations appropriées) ce qu’on appelle
formule de récurrence d’Aitken, puis expliquons son utilité pratique.
Pour une valeur numérique réelle x = t donnée, posons :
1. ∀ i1 , · · · , ik ∈ [ 0 (1) n ], 2 à 2 distincts, y i1 , ··· , ik = (pLxi ···xik f )(t) ;
1
2. ∀ i ∈ [ 0 (1) n ], δi = t − xi .
δ0 · y1 ··· n − δn · y0 ··· n−1
Alors l’égalité (E2.1 ) =⇒ y0 ··· n = (formule de récurrence d’Aitken).
xn − x0
1. Utilité pratique :
Cette formule de récurrence est à la base de l’algorithme d’Aitken qui permet de calculer directement
la valeur du p.i.L. pLx0 ···xn f au point x = t, une fois donnée la valeur numérique de t, et ce sans passer par
la détermination préalable d’une expression générale de (pLx0 ···xn f )(x) qui serait valable ∀ x ∈ IR.
• Dans la suite de cet Exercice, on suppose que f est une fonction de IR −→ IR/ −1, 0, 1, 2, 3 ∈ Df .
3◦ ) Rappel de la définition de pL−1, 0, 1, 2, 3 f .
L’une ou l’autre des définitions suivantes est valable :
• Définition 4 :
pL−1, 0, 1, 2, 3 f est l’unique polynôme de degré 6 4 qui prend les mêmes valeurs que f en −1, 0, 1, 2 et 3 .

• Définition 4’ :
pL−1, 0, 1, 2, 3 f est l’unique polynôme de degré 6 4 qui coïncide avec la fonction f en −1, 0, 1, 2 et 3 .

• Définition 4” :
pL−1, 0, 1, 2, 3 f est l’unique polynôme de degré 6 4 qui interpole la fonction f en −1, 0, 1, 2 et 3 .

• Définition 4” ’ :
pL−1, 0, 1, 2, 3 f est l’unique polynôme P ∈ IR4 [x] vérifiant : ∀ t ∈ { −1, 0, 1, 2, 3}, P (t) = f (t) .

4◦ ) a) et b) : Cf. Dernière page de la Correction de cet Exercice.

5◦ ) On approche la fonction f par pL−1, 0, 1, 2, 3 f sur un intervalle [ a, b ]/ −1, 0, 1, 2, 3 ∈ ] a, b [.
a) Quantité par laquelle on mesure la qualité de l’approximation globale de f par pL−1, 0, 1, 2, 3 f sur
[ a, b ] et son interprétation pratique ? N.B. Avec un graphique clair pour illustrer l’argument .
On mesure la qualité de l’approximation globale de f par pL−1, 0, 1, 2, 3 f sur [ a, b ] par la quantité :
E[ a,b ] (pL−1, 0, 1, 2, 3 f | f ) = sup | f (x) − (pL−1, 0, 1, 2, 3 f )(x) | .
x ∈ [ a,b ]

Celle ci représente le plus grand écart entre les valeurs respectives de f et de pL−1, 0, 1, 2, 3 f en un point de [ a, b ].
b) Sous une hypothèse à préciser, que permet de dire le Corollaire sur la majoration de l’erreur
d’interpolation au sujet de cette quantité ?
Le p.i.L. pL−1, 0, 1, 2, 3 f comporte 5 points d’interpolation. Supposons donc f de classe C 5 sur [ a, b ]. Alors,
d’après le Corollaire sur la majoration de l’erreur d’interpolation, on a :
M5
∀ x ∈ [ a, b ], E[ a,b ] (pL−1, 0, 1, 2, 3 f | f ) 6 · sup | π4 (x) | ,
5 ! x ∈ [ a,b ]

avec M5 = sup | f (5) (x) | < +∞ et π4 (x) = (x + 1) x (x − 1) (x − 2) (x − 3) .

x∈ [ a,b ]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fin de la Correction de l’EXERCICE 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction

4◦ ) On suppose qu’on a les données : f (−1) = 3, f (0) = 0, f (1) = −2, f (2) = −2, f (3) = −7.
N.B. Pour les 2 calculs demandés ci-après, on garde les points d’interpolation dans l’ordre donné.
a) Calcul du polynôme pL−1, 0, 1, 2, 3 f , sous forme de Newton, pour ces données.
Pour ces données et cet ordre des points d’interpolation, on a, par la forme de Newton, ∀ x ∈ IR :

(pL−1, 0, 1, 2, 3 f )(x) = f (−1) + f [ − 1, 0 ] · (x + 1) + f [ − 1, 0, 1 ] · (x + 1) x

+ f [ − 1, 0, 1, 2 ] · (x + 1) x (x − 1) + f [ − 1, 0, 1, 2, 3 ] · (x + 1) x (x − 1) (x − 2).

Calculons alors les coefficients f [ − 1, 0 ], f [ − 1, 0, 1 ], f [ − 1, 0, 1, 2 ] et f [ − 1, 0, 1, 2, 3 ] par le tableau :

x0 = −1 : f (−1) = 3
ց
x1 = 0 : f (0) = 0 −→ f [ − 1, 0 ] = −3
ց ց
1
x2 = 1 : f (1) = −2 −→ f [ 0, 1 ] = −2 −→ f [ − 1, 0, 1 ] =
2
ց ց ց
1
x3 = 2 : f (2) = −2 −→ f [ 1, 2 ] = 0 −→ f [ 0, 1, 2 ] = 1 −→ f [ − 1, 0, 1, 2 ] =
6
ց ց ց ց
5 7 1
x4 = 3 : f (3) = −7 −→ f [ 2, 3 ] = −5 −→ f [ 1, 2, 3 ] = − −→ f [ 0, 1, 2, 3 ] = − −→ f [ − 1, 0, 1, 2, 3 ] = −
2 6 3

• Conclusion : ∀ x ∈ IR,
1 1 1
(pL−1, 0, 1, 2, 3 f )(x) = 3 − 3 (x + 1) + (x + 1) x + (x + 1) x (x − 1) − (x + 1) x (x − 1) (x − 2) .
2 6 3
b) Calcul de la valeur, en x = −2, de pL−1, 0, 1, 2, 3 f par l’algorithme d’Aitken.

x0 = −1 : δ0 = −1 : y0 = 3
ց
x1 = 0 : δ1 = −2 : y1 = 0 −→ y01 = 6
ց ց
x2 = 1 : δ2 = −3 : y2 = −2 −→ y12 = 4 −→ y012 = 7
ց ց ց

Exo. 2 : p.3/3
x3 = 2 : δ3 = −4 : y3 = −2 −→ y23 = −2 −→ y123 = 10 −→ y0123 = 6
ց ց ց ց
x4 = 3 : δ4 = −5 : y4 = −7 −→ y34 = 18 −→ y234 = −32 −→ y1234 = 38 −→ y01234 = −2

• Conclusion : (pL−1, 0, 1, 2, 3 f )(−2) = y01234 = −2 .

MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 3 : p.1/3

**** EXERCICE 3 ****

On s’intéresse ici à la méthode de Gauss pour résoudre un système de Cramer dans IRn : A.X = b (S).
1◦ ) Ce qui oblige, souvent, à effectuer des permutations d’équations pendant l’élimination de Gauss :
a) Du point de vue de la théorie de l’Algèbre Linéaire :
L’élimination de Gauss dans le système (S) s’opère colonne après colonne dans la matrice A, de la colonne
k = 1 à la colonne k = n − 1. Or, du point de vue de la théorie de l’Algèbre Linéaire, lorsqu’on arrive pour effectuer
l’élimination sur une colonne k, il est impératif que le coefficient en position (k, k) dans la matrice soit non nul
à ce stade là, i.e. après l’élimination dans les colonnes 1 à k − 1. Si, à ce stade là, ce coefficient est effectivement
non nul, alors on l’adopte comme pivot pour l’élimination sur la colonne k, i.e. annulation de tous les coefficients
en dessous de lui sur cette colonne k. Par contre, s’il est nul, alors on est obligé de le remplacer par un autre non
nul, pris en dessous de lui dans la matrice, sur la même colonne k, pour jouer ce rôle de pivot. Pour ramener celui
ci en position (k, k) dans la matrice, s’il a été trouvé en position (i, k), avec i 6= k, on est alors obligé de permuter
l’équation i et l’équation k du système, ceci afin de préserver le vecteur-solution X du système linéaire (S).
b) Du point de vue de l’exécution de l’algorithme de la méthode de Gauss par ordinateur :
Si on utilise des pivots trop petits pendant l’élimination de Gauss dans le système (S), notamment comparés
aux coefficients en dessous d’eux sur la même colonne, cela provoquera une propagation désastreuse des erreurs
d’arrondi lors de l’exécution de l’algorithme de la méthode de Gauss par ordinateur. Ceci pourra faire en sorte
que le vecteur X, e renvoyé par l’ordinateur en guise de résultat à la sortie de cette exécution, soit très éloigné
du vrai vecteur-solution X du système linéaire (S). Pour éviter ce cas de figure, on doit s’arranger à toujours
prendre, comme pivot pour l’élimination sur une colonne k, un coefficient qui, une fois mis en position (k, k) dans
la matrice, n’aura aucun coefficient plus grand que lui (en valeur absolue) parmi ceux en dessous de lui sur cette
colonne k. Si le coefficient initialement en position (k, k), au début de l’élimination sur la colonne k, ne vérifie pas
cette propriété, alors (par la stratégie du pivot partiel ), il faut repérer le plus grand (en valeur absolue) en dessous
de lui. Si cet autre coefficient est trouvé en position (i, k), avec i 6= k, alors on est également obligé d’opérer
comme indiqué en a) ci-dessus.
2◦ ) a) Mais il y a des systèmes dont la matrice est telle qu’il est garanti d’avance qu’il n’y aura
aucune nécessité d’effectuer des permutations d’équations pendant l’élimination de Gauss.
Deux types de matrices de ce genre sont :
1. A matrice à diagonale strictement dominante (en abrégé : DSD), i.e. les coefficients de A vérifient :
n
X
∀ i ∈ [ 1 (1) n ], | aii | > | aij | ;
j =1
j 6= i

autrement dit : sur chaque ligne de la matrice A, la valeur absolue du coefficient diagonal est
plus grande que la somme des valeurs absolues des autres coefficients de la ligne.
2. A matrice symétrique et définie positive, i.e. A symétrique et ∀ u ∈ IRn \ { 0IRn }, h A.u , u i > 0,
n
X
n
où h u , v i désigne le produit scalaire canonique de 2 vecteurs u, v ∈ IR : h u , v i = ui vi .
i=1
b) Version de la méthode de Gauss adaptée pour ce type de systèmes linéaires.

Il s’agit de la méthode de Gauss sans permutation .

c) Avantage(s) présente-t-elle par rapport à la version générale de la méthode de Gauss.

N’ayant pas à consacrer du temps à rechercher des pivots, ni à effectuer des permutations d’équations et/ou de
colonnes dans A, la méthode de Gauss sans permutation est de conception algorithmique plus simple et un peu
plus rapide à l’exécution par ordinateur que la version générale de la méthode de Gauss.
• Dans la suite de cet Exercice, on se place dans la situation où on peut résoudre le système (S)
par la version de la méthode de Gauss mise évidence en 2◦ )b) ci-dessus. On suppose alors ici
avoir déjà effectué l’élimination des colonnes 1 à k − 1, pour un indice k ∈ [ 1 (1) n − 1 ] donné
(N.B. Pour k = 1, ceci signifie simplement que l’élimination n’a pas encore commencé).
 MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 3 : p.2/3

3◦ ) Aspect de la matrice A(k−1) en laquelle A a été transformée à ce stade :


a11 a12 a13 · · · a1,k−1 a1,k a1,k+1 · · · a1,n 

 a22 a23 · · · a2,k−1 a2,k a2,k+1 · · · a2,n  

 a33 · · · a3,k−1 a3,k a3,k+1 · · · a3,n  
 
 . . . .. 
.. .. . . . ..
 

 ak−1,k−1 ak−1,k ak−1,k+1 · · · ak−1,n 

 ak,k ak,k+1 · · · ak,n 
A(k−1) =   .
 a a · · · a 
 k+1,k k+1,k+1 k+1,n 
 
 .. ..  ... ..
 
 ai,k ai,k+1 · · · ai,n 
 
 
 .. ..  ... ..
an,k an,k+1 ··· an,n

4◦ ) On effectue maintenant l’élimination sur la colonne k de A(k−1) .

a) Sous-matrice M(k−1) de A(k−1) dont les coefficients vont effectivement changer de valeur :
 
 ak+1,k ak+1,k+1 · · · ak+1,n 
 
 .. ..  . . . ..
 
 
M(k−1) 
=  ai,k · · · ai,n 
ai,k+1  .
 
 .. ..  . . . ..
 
 
an,k an,k+1 · · · an,n
b) Mais, en réalité, seuls les coefficients de la sous-matrice H(k−1) ci-après de M(k−1) demandent
un calcul effectif de leur nouvelle valeur dans l’algorithme de la méthode de Gauss. Expliquons
pourquoi cela n’apporterait concrètement rien (pour la suite de l’algorithme) de modifier les
valeurs des autres coefficients de M(k−1) pendant cette élimination sur la colonne k de A(k−1) .

 
 ak+1,k+1 ak+1,k+2 ··· ak+1,n 
 
 .. .. . . . .. 
 
 
H(k−1) = 
 ai,k+1 ai,k+2 ··· ai,n   .
 
 .. .. . . . .. 
 
 
an,k+1 an,k+2 ··· an,n

Après l’élimnation sur la colonne k, les valeurs de tous les autres coefficients de M(k−1) (i.e. les coefficients
aik , i = k + 1 (1) n) seront nulles, donc connues d’avance, qu’elles soient ou pas effectivement affectées à ces
coefficients. Il suffit d’en tenir compte dans toute instruction où l’un de ces coefficients interviendrait par la suite.
D’autre part, et plus fondamentalement, ces coefficients se trouvent en dessous de la diagonale de A, donc dans
la « zone inutile » d’une matrice sup-triangulaire, ce qui est la forme finale en laquelle l’élimination de Gauss va
transformer A. Par conséquent, ces coefficients ne seront, en fait, plus jamais utilisés dans la suite de l’algorithme.
Ainsi, que leurs valeurs soient ou pas changées à ce stade n’a aucune importance pour le déroulement ultérieur de
cet algorithme.
5◦ ) a) Dans cette méthode de Gauss, les 2 blocs d’instructions ci-après font la même chose.
 MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 3 : p.3/3

• Bloc d’instructions 1.
• Bloc d’instructions 2.
Pour i = k + 1 (1) n faire
Pour i = k + 1 (1) n faire
ℓik ←− A[i, k]/A[k, k] ;
Pour j = k + 1 (1) n faire
Pour j = k + 1 (1) n faire
A[i, j] ←− A[i, j] − (A[i, k]/A[k, k]) ∗ A[k, j] ;
A[i, j] ←− A[i, j] − ℓik ∗ A[k, j] ;
finPour ;
finPour ;
b[i] ←− b[i] − (A[i, k]/A[k, k])∗b[k] ;
b[i] ←− b[i] − ℓik ∗b[k] ;
finPour ;
finPour ;

Ils font, tous les deux, le

travail algorithmique pour l’élimination sur la colonne k de la matrice

dans la méthode de Gauss sans permutation.

b) Malgré les apparences, ces 2 blocs d’instructions ne sont pas du tout équivalents d’un point de
vue algorithmique : dans ce qu’ils font, il y en a un qui est nettement plus efficace que l’autre.
Identifier le plus efficace, expliquer pourquoi et quantifier précisément le degré d’inefficacité
de l’autre par rapport à celui ci.
1. Le Bloc d’instructions 1 est nettement plus efficace que le Bloc d’instructions 2 .

2. Raison :
Les 2 blocs font les mêmes nombres respectifs de soustractions et de multiplications. La différence se
situe au niveau des divisions effectuées. Le Bloc d’instructions 2 en effectue un nombre incomparablement
plus élevée que le Bloc d’instructions 1 . En effet, pour chaque valeur de l’indice i = k + 1 (1) n, le Bloc
d’instructions 1 effectue la seule division (A[i, k]/A[k, k]). Par contre, pour chacune des valeurs de cet
indice, le Bloc d’instructions 2 répéte cette même division plusieurs fois, soit, en fait, n − k + 1 fois.
3. Degré d’inefficacité du Bloc d’instructions 2 par rapport au Bloc d’instructions 1 :
Comme cela venait d’être dit, la différence se situe au niveau du nombre de divisions :
3.1. le Bloc d’instructions 1 effectue : n − k (/) ;

3.2. le Bloc d’instructions 2 en effectue : (n − k)(n − k + 1) (/) ;

3.3. soit un coût numérique supplémentaire pour ce dernier de (n − k)2 o.v.f. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fin de la Correction de l’EXERCICE 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 4 : p.1/3

**** EXERCICE 4 ****

On veut résoudre ici un système de Cramer dans IRn , (S1 ) : A.X = b, avec A de la forme :
 
a11 a12 a13 
 
 a22 a23 a24 
 
 
 a33 a34 a35 
 
 
A =   ... ... ... 

 
 
 an−2,n−2 a a
n−2,n−1 n−2,n 
 
 
 a n−1,n−1 an−1,n 
 
an,n
..................................................................................................................

1◦ ) a) Détailler les équations linéaires du système (S1 ).



 a11 x1 + a12 x2 + a13 x3 = b1

 a22 x2 + a23 x3 + a24 x4 = b2





 a33 x3 + a34 x4 + a35 x5 = b3
(S1 ) ... ... ...



 an−2,n−2 xn−2 + an−2,n−1 xn−1 + an−2,n xn = bn−2



 an−1,n−1 xn−1 + an−1,n xn = bn−1


an,n xn = bn

b) En déduire les formules mathématiques permettant de calculer les inconnues du système (S1 ).
D’après le détail des équations ci-dessus, on calcule successivement :

1. xn = bn /an,n ;
2. xn−1 = (bn−1 − an−1,n xn )/an−1,n−1 ;
3. Pour i = n − 2 (−1) 1, xi = (bi − ai,i+1 xi+1 − ai,i+2 xi+2 )/ai,i .

2◦ ) Ecrire un algorithme SOLVE_1 résolvant le système (S1 ). Coût numérique de cet algorithme ?
• • Version 1 de SOLVE_1 : En conservant les notations mathématiques des termes des suites.

• Données :
A ∈ Mn (IR) ; /* A = (aij )1 6 i,j 6 n */
n
b ∈ IR ; /* b = (bi)1 6 i 6 n */
• Résultat attendu :
X ∈ IRn ; /* X = (xi)1 6 i 6 n */
Début
xn ←− bn/an,n ;
xn−1 ←− (bn−1 − an−1,n ∗ xn)/an−1,n−1 ;
Pour i = n − 2 (−1) 1 faire
xi ←− (bi − ai,i+1 ∗ xi+1 − ai,i+2 ∗ xi+2 )/ai,i ;
finPour ;
Renvoyer (X) ;

STOP
MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 4 : p.2/3

• • Version 2 de SOLVE_1 : Avec des notations informatiques standard des éléments de tableaux.

• Données :
A ∈ Mn (IR) ; /* matrice du système (S1 ) */
n
b ∈ IR ; /* vecteur-2nd membre du système (S1 ) */
• Résultat attendu :
X ∈ IRn ; /* vecteur-solution membre du système (S1 ) */
Début
X[n] ←− b[n]/A[n, n] ;


X[n − 1] ←− b[n − 1] − A[n − 1, n]∗ X[n] /A[n − 1, n − 1] ;
Pour i = n − 2 (−1) 1 faire


X[i] ←− b[i] − A[i, i + 1]∗ X[i + 1] − A[i, i + 2]∗ X[i + 2] /A[i, i] ;
finPour ;
Renvoyer (X) ;

STOP

∗∗∗ Coût numérique de l’algorithme SOLVE_1 .

Dans l’algorithme ci-dessus (pour ses 2 versions), avant la boucle Pour, on fait : 1 (−), 1 (×), 2 (/).
A chaque passage dans la boucle Pour, soit, pour chaque i = n − 2 (−1) 1, on fait, comme calculs sur les réels :
2 (−), 2 (×), 1 (/).
Il y a n − 2 entiers i ∈ [ n − 2 (−1) 1 ], et comme 2(n − 2) + 1 = 2n − 3, alors le bilan de l’algorithme est :
2n − 3 (−), 2n − 3 (×), n (/) , soit, au total, 5n − 6 o.v.f. .

• • • Utiliser un tableau n × n de réels pour stocker la matrice A dans un algorithme représente clairement un
très grossier gaspillage de la mémoire de l’ordinateur. Pour une telle matrice, il suffit de stocker sa partie utile. Or,
cette dernière peut tenir dans 3 tableaux D, E et F du type vecteur (celui utilisé en Cours pour b et X). On
admet ainsi, ici, que les tableaux D, E, F ont déjà été remplis, au début du programme, comme suit :
1 D contient la diagonale principale de A ; 2 E contient la diagonale secondaire au-dessus de la
diagonale principale de A ; 3 F contient la diagonale secondaire juste au-dessus de E.
3◦ ) a) Avec ce mode de stockage de la matrice A, on a :

∀ i = 1 (1) n, D[i] = aii ; ∀ i = 1 (1) n − 1, E[i] = ai,i+1 ; ∀ i = 1 (1) n − 2, F[i] = ai,i+2 .

b) Voici A avec chaque coefficient utile remplacé par la coordonnée appropriée de D ou E ou F :

 
D[1] E[1] F[1] 
 
 
 D[2] E[2] F[2] 
 
 
 D[3] E[3] F[3] 
 
 
 
A =  ... ... ...  .
 
 
 
 D[n − 2] E[n − 2] F[n − 2]
 
 
 D[n − 1] E[n − 1]
 
 
D[n]
 MAT 227–Analyse Numérique, Rattrapage 2016-17 : Eléments sur la Correction Exo. 4 : p.3/3

∗∗∗ Remarque/Commentaire n◦1. :

Même si E et F ont été déclarés de type vecteur au début du programme, donc sont 2 tableaux de
réels avec un indice prenant des valeurs allant de 1 à n, il faut, cependant, noter que les 3 éléments E[n],
F[n − 1] et E[n] n’ont pas reçu de valeur. Et il n’est pas indispensable qu’ils en reçoivent, car on n’est
pas obligé d’utiliser tous les éléments d’un tableau déclaré dans un programme. Mathématiquement, en
fait, E ∈ IRn−1 et F ∈ IRn−2 . De ce fait, dans le tableau de type vecteur qui a été déclaré pour le
représenter dans le programme, E n’utilise que les n − 1 premiers éléments (le dernier restant vide),
tandis que F n’utilise que les n − 2 premiers éléments de son tableau (les 2 derniers restant inutilisés).

4◦ ) Procédure algorithmique SOLVE_OPT résolvant (S1 ) avec ce stockage de A dans le programme :

Procédure SOLVE_OPT ( D, E, F, b : vecteur ; var X : vecteur) ;

/* Objectif : Résolution de (S1 ) : A.X = b, système de Cramer dans IRn , avec la
matrice A stockée optimalement (dans 3 vecteurs). */
/* Paramètre(s) entrant(s) :
− D ∈ IRn , diagonale principale de A ;
− E ∈ IRn−1 , diagonale secondaire au-dessus de la diagonale principale de A ;
− F ∈ IRn−2 , diagonale secondaire juste au-dessus de E dans A ;
− b ∈ IRn , vecteur-2nd membre du système. */
/* Paramètre(s) sortant(s) :
− X ∈ IRn , vecteur-solution de A.X = b. */
Variable locale :
i : entier ;

/* ** Corps de la procédure ***/

début /* SOLVE_OPT */
X[n] ←− b[n]/ D[n] ;


X[n − 1] ←− b[n − 1] − E[n − 1]∗ X[n] / D[n − 1] ;
Pour i = n − 2 (−1) 1 faire


X[i] ←− b[i] − E[i]∗ X[i + 1] − F[i]∗ X[i + 2] / D[i] ;
finPour ;
Renvoyer (X) ;
fin ; /* SOLVE_OPT */

5◦ ) Gain en passant de SOLVE_1 à SOLVE_OPT , en illustrant avec la valeur n = 100.

Ce qu’on a gagné, c’est qu’au lieu de bloquer l’espace requis en mémoire d’ordinateur pour stocker n × n = n2
réels-machine (pour tous les coefficients d’une matrice carrée quelconque d’ordre n), on bloque seulement l’espace-
mémoire requis pour 3n réels-machine (pour les coefficients des 3 diagonales utiles de A). Ceci fait, par exemple,
pour n = 100, 3n = 300 au lieu de n2 = 10 000. Le gain en espace-mémoire occupé par l’algorithme, pendant son
exécution par ordinateur, est donc considérable !!!

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fin de la Correction de l’EXERCICE 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . FIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .