E.N.S.P. . . . . . . . Niveau II 2016-17 / Session de Rattrapage . . . . . . .

ND/NG

***** U.E. MAT 227 « Analyse Numérique » : Examen Final (3H 00mn) *****

NB.1 : 1. Le correcteur appréciera le soin apporté à la rédaction et à la présentation du devoir.

2. TOUS DOCS INTERDITS/CALCULATRICES AUTORISEES, SAUF LES PROGRAMMABLES.
3. SOYEZ CLAIR ET PRECIS DANS LES REPONSES, mais CONCIS.
4. L’objectif ici ne doit pas être de chercher à traiter à tout prix toute l’épreuve, en sprintant
et en bâclant, mais, plutôt, d’en couvrir une part significative de manière convaincante.

**** EXERCICE 1 (3,5 POINTS) ****

On considère un ordinateur qui calcule en utilisant le système de réels-machine R = R (9, 7, −545, 544).
1◦ ) a) Quels sont les réels que cet ordinateur connaît et peut manipuler ?
b) Cela fait, en tout, combien de nombre réels ?
c) Quel est le plus grand > 0 parmi ces réels ? Et le plus petit > 0 parmi ces réels ?
◦
2 ) a) Le nombre 1 ∈ R . Comment le voit-on ?
b) Mais à quoi est égal succR (1), le successeur du nombre 1 dans R ?
c) Et à quoi est égal predR (1), le prédécesseur du nombre 1 dans R ?

**** EXERCICE 2 (7,5 POINTS) ****

1◦ ) a) Que dit le 1er point du Lemme d’Aitken-Neville à propos de pLx0 ··· xn f ?

b) Ce résultat relie 3 polynômes d’interpolation de Lagrange. Donner la définition de chacun d’entre eux.
2◦ ) a) Que dit le 2 ème point du Lemme d’Aitken-Neville ?
b) Ce résultat relie 3 coefficients particuliers. Donner la définition de chacun d’entre eux.
c) De l’un des résultats précédents, déduire (et avec des notations appropriées), ce qu’on appelle
formule de récurrence d’Aitken, puis expliquer son utilité pratique.
• Dans la suite de cet Exercice, on suppose que f est une fonction de IR −→ IR/ −1, 0, 1, 2, 3 ∈ Df .
3◦ ) Rappeler la définition de pL−1, 0, 1, 2, 3 f .
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, garder les points d’interpolation dans l’ordre donné.
a) Calculer pL−1, 0, 1, 2, 3 f , sous forme de Newton, pour ces données.
b) Calculer la valeur, en x = −2, de pL−1, 0, 1, 2, 3 f par l’algorithme d’Aitken.
◦
5 ) On décide d’approcher la fonction f par pL−1, 0, 1, 2, 3 f sur un intervalle [ a, b ]/ −1, 0, 1, 2, 3 ∈ ] a, b [.
a) Par quelle quantité mesure-t-on la qualité de l’approximation globale de f par pL−1, 0, 1, 2, 3 f sur [ a, b ] ?
Quelle est son interprétation pratique ? N.B. Avec un graphique clair pour illustrer l’argument .
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é ?

**** EXERCICE 3 (7 POINTS) ****

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◦ ) Qu’est-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 ?
b) du point de vue de l’exécution de l’algorithme de la méthode de Gauss par ordinateur ?
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.
Citer 2 types de matrices de ce genre et donner leurs définitions respectives.
b) Comment appelle-t-on la version de la méthode de Gauss adaptée pour ce type de systèmes linéaires ?
c) Quel(s) avantage(s) présente-t-elle par rapport à 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é).
3◦ ) Représenter l’aspect de la matrice A(k−1) en laquelle A a été transformée à ce stade.
4◦ ) On effectue maintenant l’élimination sur la colonne k de A(k−1) .
a) Alors seuls les coefficients d’une certaine sous-matrice M(k−1) de A(k−1) vont effectivement changer de
valeur. Donner la sous-matrice M(k−1) .
b) Mais, en réalité, seuls les coefficients d’une certaine sous-matrice H(k−1) de M(k−1) demandent un calcul
effectif de leur nouvelle valeur dans l’algorithme de la méthode de Gauss. Donner H(k−1) , et expliquer
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) .
◦
5 ) a) Dans cette méthode de Gauss, les 2 blocs d’instructions ci-après font la même chose. Mais quoi précisément ?
• 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 ;
b) Malgré les apparences, ces 2 blocs d’instructions ne sont pas du tout équivalents d’un point de vue al-
gorithmique : 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.

**** EXERCICE 4 (5,5 POINTS) ****

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 an−2,n−1 an−2,n  
 
an−1,n−1 an−1,n 
 

 
an,n
..................................................................................................................
1◦ ) a) Détailler les équations linéaires du système (S1 ).
b) En déduire les formules mathématiques permettant de calculer les inconnues du système (S1 ).
◦
2 ) Ecrire un algorithme SOLVE_1 résolvant le système (S1 ). Coût numérique de cet algorithme ?
• • • 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 stockage, D[i], l’élément n◦ i du tableau D, est égal à quel coefficient de A ? Et E[i] ? Et F[i] ?
b) Représenter A avec chaque coefficient utile remplacé par la coordonnée appropriée de D ou E ou F.
4◦ ) Ecrire une procédure algorithmique SOLVE_OPT résolvant (S1 ) sachant ce stockage de A dans le programme.
5◦ ) En passant de SOLVE_1 à SOLVE_OPT , qu’est-ce qu’on a gagné ? N.B. Illustrer avec la valeur n = 100.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . FIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .