40
2 Les fondements du calcul scientifique
autre possibilit´ e est de r´ esoudre F (x, p) = x
2 − 2px + 1 = 0 par la m´ ethode de
Newton (pr´ esent´ ee dans l’Exemple 2.5)
x0 donn´ e, xn = fn(p) = xn−1 − (x
2
n−1 − 2pxn−1 + 1)/(2xn−1 − 2p), n ≥ 1.
Appliquer (2.19) pour p > 1 conduit `
a Kn(p) |p|/|xn − p|. Pour calculer K
num (p)
nous remarquons que, dans le cas o` u l’algorithme converge, la solution xn doit
converger vers l’une des racines x+ ou x− ; par cons´ equent, |xn − p| →
p 2 − 1
et donc Kn(p) → K
num (p) |p|/
p 2 − 1, en parfait accord avec la valeur (2.8) du
conditionnement du probl` eme exact.
Nous pouvons conclure que la m´ ethode de Newton pour la recherche des racines
simples d’une ´ equation alg´ ebrique du second ordre est mal conditionn´ ee si |p| est
tr` es proche de 1, tandis qu’elle est bien conditionn´ ee dans les autres cas.
•
Le but ultime de l’approximation num´ erique est naturellement de construire, au moyen de probl` emes du type (2.12), des solutions x n qui se “rapprochent” de la solution du probl` eme (2.1) quand n devient grand. Cette notion
est pr´ ecis´ ee dans la d´ efinition suivante :
D´ efinition 2.2 La m´ ethode num´ erique (2.12) est dite convergente ssi
∀ε > 0, ∃n 0 = n 0 (ε), ∃δ = δ(n 0 , ε) > 0 tels que
∀n > n 0 (ε), ∀δd n : δd n ≤ δ ⇒ ⇒x(d) − x n (d + δd n ) ≤ ε,
(2.20)
o` u d est une donn´ ee admissible du probl` eme (2.1), x(d) est la solution correspondante et x n (d + δd n ) est la solution du probl` eme num´ erique (2.12) avec la
donn´ ee d + δd n .
Pour v´ erifier (2.20), il suffit d’´ etablir que, sous les mˆ emes hypoth` eses,
+ δd n ) − x n (d + δd n ) ≤
ε
2
.
(2.21)
En effet, grˆ ace ` a (2.3), on a alors
− x n (d + δd n ) ≤ ≤x(d) − x(d + δd n )
+x(d + δd n ) − x n (d + δd n ) ≤ K 0 δd n +
ε
2 .
En choisissant δ = min {η 0 , ε/(2K 0 )}, on obtient (2.20).
Des “mesures” de la convergence de x n vers x sont donn´ ees par l’erreur
absolue et l’erreur relative, d´ efinies respectivement par
E(x n ) = |x − x n |,
E rel (x n ) =
|x − x n |
|x|
si x = 0 .
(2.22)
Dans les cas o` u x et x n sont des matrices ou des vecteurs, les valeurs absolues
dans (2.22) sont remplac´ ees par des normes ad´ equates, et il est quelquefois
utile d’introduire l’erreur par composantes :
E
c
rel (x n ) = max
i,j
|(x − x n ) ij |
|x ij |
.
(2.23)
2 Les fondements du calcul scientifique
autre possibilit´ e est de r´ esoudre F (x, p) = x
2 − 2px + 1 = 0 par la m´ ethode de
Newton (pr´ esent´ ee dans l’Exemple 2.5)
x0 donn´ e, xn = fn(p) = xn−1 − (x
2
n−1 − 2pxn−1 + 1)/(2xn−1 − 2p), n ≥ 1.
Appliquer (2.19) pour p > 1 conduit `
a Kn(p) |p|/|xn − p|. Pour calculer K
num (p)
nous remarquons que, dans le cas o` u l’algorithme converge, la solution xn doit
converger vers l’une des racines x+ ou x− ; par cons´ equent, |xn − p| →
p 2 − 1
et donc Kn(p) → K
num (p) |p|/
p 2 − 1, en parfait accord avec la valeur (2.8) du
conditionnement du probl` eme exact.
Nous pouvons conclure que la m´ ethode de Newton pour la recherche des racines
simples d’une ´ equation alg´ ebrique du second ordre est mal conditionn´ ee si |p| est
tr` es proche de 1, tandis qu’elle est bien conditionn´ ee dans les autres cas.
•
Le but ultime de l’approximation num´ erique est naturellement de construire, au moyen de probl` emes du type (2.12), des solutions x n qui se “rapprochent” de la solution du probl` eme (2.1) quand n devient grand. Cette notion
est pr´ ecis´ ee dans la d´ efinition suivante :
D´ efinition 2.2 La m´ ethode num´ erique (2.12) est dite convergente ssi
∀ε > 0, ∃n 0 = n 0 (ε), ∃δ = δ(n 0 , ε) > 0 tels que
∀n > n 0 (ε), ∀δd n : δd n ≤ δ ⇒ ⇒x(d) − x n (d + δd n ) ≤ ε,
(2.20)
o` u d est une donn´ ee admissible du probl` eme (2.1), x(d) est la solution correspondante et x n (d + δd n ) est la solution du probl` eme num´ erique (2.12) avec la
donn´ ee d + δd n .
Pour v´ erifier (2.20), il suffit d’´ etablir que, sous les mˆ emes hypoth` eses,
+ δd n ) − x n (d + δd n ) ≤
ε
2
.
(2.21)
En effet, grˆ ace ` a (2.3), on a alors
− x n (d + δd n ) ≤ ≤x(d) − x(d + δd n )
+x(d + δd n ) − x n (d + δd n ) ≤ K 0 δd n +
ε
2 .
En choisissant δ = min {η 0 , ε/(2K 0 )}, on obtient (2.20).
Des “mesures” de la convergence de x n vers x sont donn´ ees par l’erreur
absolue et l’erreur relative, d´ efinies respectivement par
E(x n ) = |x − x n |,
E rel (x n ) =
|x − x n |
|x|
si x = 0 .
(2.22)
Dans les cas o` u x et x n sont des matrices ou des vecteurs, les valeurs absolues
dans (2.22) sont remplac´ ees par des normes ad´ equates, et il est quelquefois
utile d’introduire l’erreur par composantes :
E
c
rel (x n ) = max
i,j
|(x − x n ) ij |
|x ij |
.
(2.23)