1. Problèmes numériques
25
polynôme en un point { 0 . La méthode usuelle qui consiste à calculer d’abord
{
2
puis {
3
, ..., puis {
q
nécessite (2q1) multiplications et q additions. Pour
calculer le polynôme
S ({ 0 )=d q {
q
0 + d q1 {
q1
0
+ === + d 1 { 0 + d 0
Horner propose de factoriser S ({) sous la forme :
S ({)=d 0 + {(d 1 + {(d 2 + === + {(d q1 + {d q )===))
et d’évaluer successivement les quantités
e q = d q
e q1 = d q1 + { 0 e q
===
e 1 = d 1 + { 0 e 2
e 0 = d 0 + { 0 e 1
A ut e r m ed ec ec a l c u le 0 donne la valeur du polynôme S au point { 0 .À
chaque étape, on eectue une multiplication et une addition, de sorte que
la méthode de Horner pour évaluer la valeur d’un polynôme de degré q
en un point donné nécessite q multiplications et q additions, ce qui réalise
une économie par rapport à la méthode usuelle et par conséquent un gain
de temps si le degré du polynôme est élevé. On démontre que la méthode
de Horner est optimale et que c’est la seule méthode optimale. L’extension
de la règle de Horner à des systèmes de polynômes ou à des polynômes de
plusieurs variables est aussi optimale.
1.6 Problèmes bien posés, problèmes raides
Les équations diérentielles orent des exemples variés de problèmes numériques. Nous adopterons les définitions suivantes : Un problème (S )e s t
mathématiquement bien posé si le problème (S ) admet une solution unique
qui est stable au sens de Hadamard, c’est-à-dire qui dépend continûment
des données initiales. Un problème numérique est dit numériquement bien
posé si la continuité de la solution est su!samment bonne par rapport
aux conditions initiales pour que la solution ne soit pas perturbée par une
erreur initiale ou de petites erreurs d’arrondi.
Exemple 1. Le problème de Neumann pour une fonction x({) définie sur
un intervalle [d> e] :
;
?
=
x
00 ({)=0
x
0 (d)=x 0
x
0 (e)=y 0
25
polynôme en un point { 0 . La méthode usuelle qui consiste à calculer d’abord
{
2
puis {
3
, ..., puis {
q
nécessite (2q1) multiplications et q additions. Pour
calculer le polynôme
S ({ 0 )=d q {
q
0 + d q1 {
q1
0
+ === + d 1 { 0 + d 0
Horner propose de factoriser S ({) sous la forme :
S ({)=d 0 + {(d 1 + {(d 2 + === + {(d q1 + {d q )===))
et d’évaluer successivement les quantités
e q = d q
e q1 = d q1 + { 0 e q
===
e 1 = d 1 + { 0 e 2
e 0 = d 0 + { 0 e 1
A ut e r m ed ec ec a l c u le 0 donne la valeur du polynôme S au point { 0 .À
chaque étape, on eectue une multiplication et une addition, de sorte que
la méthode de Horner pour évaluer la valeur d’un polynôme de degré q
en un point donné nécessite q multiplications et q additions, ce qui réalise
une économie par rapport à la méthode usuelle et par conséquent un gain
de temps si le degré du polynôme est élevé. On démontre que la méthode
de Horner est optimale et que c’est la seule méthode optimale. L’extension
de la règle de Horner à des systèmes de polynômes ou à des polynômes de
plusieurs variables est aussi optimale.
1.6 Problèmes bien posés, problèmes raides
Les équations diérentielles orent des exemples variés de problèmes numériques. Nous adopterons les définitions suivantes : Un problème (S )e s t
mathématiquement bien posé si le problème (S ) admet une solution unique
qui est stable au sens de Hadamard, c’est-à-dire qui dépend continûment
des données initiales. Un problème numérique est dit numériquement bien
posé si la continuité de la solution est su!samment bonne par rapport
aux conditions initiales pour que la solution ne soit pas perturbée par une
erreur initiale ou de petites erreurs d’arrondi.
Exemple 1. Le problème de Neumann pour une fonction x({) définie sur
un intervalle [d> e] :
;
?
=
x
00 ({)=0
x
0 (d)=x 0
x
0 (e)=y 0