Approximation des fonctions

Préparation agrégation, option C

05/06

Ce texte présente quelques méthodes d'approximation de fonctions qui servent

en particulier à calculer les fonctions classiques en utilisant des fonctions plus
simples (addition, multiplication, division, évaluation de polynômes).

1 La méthode de Newton
Pour calculer F (a), on résoud une équation du type f (x) = 0 dont x = F (a)
est solution, et telle que le calcul de g soit possible (ou plus ecace). Par exemple
pour calculer la racine n-ième d'un réel positif a, on prend f (x) = xn a.
On utilise souvent des fonctions dont la convexité est connue, pour pouvoir
appliquer le

Theorem 1 Soit f de classe C 2 telle que f (r) = 0; f 0 (r) > 0 et f 00  0 sur

[r; b]. Alors pour tout u0 2 [r; b] la suite de la méthode de Newton

f (un )
un+1 = un ;
f 0 (un )
est dénie, décroissante, minorée par r et converge vers r.
Le théorème des accroissements nis permet alors de calculer la précision de la
racine approchée trouvée en fonction de l'image de cette racine :

0  un r  ff 0urn ( )

( )

Typiquement le nombre de chires signicatifs corrects est multiplié par 2 à

chaque itération. C'est par exemple cette méthode qui permet de calculer la
racine carrée de a > 1 :
a
un+1 = un +
1

un
( )
2

Le calcul de la valeur initiale u0 de la suite a une grande importance pour le

nombre d'itérations à eectuer, on utilise diverses méthodes, par exemple une
des méthodes présentées ci-dessous, la méthode de Newton pouvant servir à
améliorer la précision (en particulier dans le cadre des ottants multiprécision).

1
2 Les polynomes
2.1 Les séries entières.
A l'intérieur du rayon de convergence d'une fonction analytique, on peut
utiliser le développement en séries entières de la fonction. On calcule une majo-
ration à priori du reste sur la zone considérée, puis on cherche le rang à partir
duquel ce reste est plus petit que la précision souhaitée. Il y a trois grandes
méthodes de majoration : le reste de Taylor (lorsque la dérivée n-ième de la
fonction est facile à calculer et majorer), les séries alternées ou l'utilisation de
la majoration suivante : s'il existe un point x0 tel que jan xn0 j est borné par M ,
alors pour jxj < jx0 j on peut majorer le reste de la série au rang n par
j xx0 jn
jRn j  M 1 j xx0 j
Le calcul de f à la précision souhaitée se ramène ainsi à une évaluation de
polynome.
Certaines séries se pretent bien à cette méthode, par exemples les fonctions
transcendantes directes (exp, sin, cos), d'autres moins bien (atan, ln) car la
convergence est un peu plus lente (pour calculer n bits de mantisse, il faut
O(n) termes du développement au lieu de O(n= ln(n)) termes). Les systèmes
de calcul en ottant multiprécision utilisent les séries entières (aprés réduction
d'argument) pour l'exponentielle ou le calcul de ln(2). Richard Brent a montré en
1976 qu'on pouvait évaluer les fonctions usuelles en O(M (n) ln(n)) opérations,
où M (n) désigne la complexité de la multiplication des entiers de taille n (par
exemple M (n) = O(n ln(n) ln(ln(n))) pour la méthode de Schönhage-Strassen).
Cela fait intervenir

2.2 Interpolation polynomiale (Lagrange, ...)

Cette fois, on approche f par un polynôme qui est égal à f en certains points
(on peut aussi imposer que les dérivées de f et P soient égales en certains points).
C'est la méthode d'interpolation de Lagrange, pour laquelle on a une majoration
de la diérence entre f et P : Soit f une fonction n + 1 fois dérivable sur un
intervalle I = [a; b] de R, x0 ; :::; xn des réels distincts de I . Soit P le polynome
de Lagrange donné par les xj et yj = f (xj ). Pour tout réel x 2 I , il existe un
réel x 2 [a; b] (qui dépend de x) tel que :

f (x) P (x) =
f [n+1] (x ) n
(x
Y
xj )
(n + 1)!
j =0

Le choix des points xi (à n xé) rendant la majoration ci-dessus optimale dépend

de l'utilisation que l'on veut faire de P . On peut prendre des points équirépartis
sur l'intervalle, puis s'en servir pour calculer une valeur approchée d'intégrale,
ce sont les méthodes de Newton-Cotes. Ce choix n'est pas optimal pour l'ordre
de la méthode de quadrature, si on laisse le choix des xi libres, on montre qu'il

2
existe un choix rendant la méthode d'intégration exacte pour tous les polynômes
de degré plus petit que 2n + 1 (méthodes de Gauss).
On peut aussi souhaiter qu'une norme issue d'un produit scalaire (par exemple
la norme L2 avec un poids) de f P soit minimale, ce qui revient à projeter f
sur un sous-espace engendré par des polynômes de degré plus petit qu'un degré
xé, il s'agit alors d'en calculer une base (de polynomes orthogonaux). Le même
principe permet de construire les séries de Fourier en prenant des polynômes
trigonométriques.

3 Les approximants de Padé

Pour approcher f on utilise une fraction rationnelle (dont le degré du numé-
rateur et du dénominateur sont bornés) à la place de polynomes. Le calcul du
numérateur et du dénominateur fait intervenir l'algorithme de Bézout.
Plus précisément, on cherche une fraction ayant même développement de
Taylor que f en un point donné, 0 pour xer les idées, à un ordre xé. On doit
donc résoudre
N
P = + O(xp+1 ) (1)
D
où P est donné de degré inférieur ou égal à p, N et D sont les inconnues de
degré inférieur ou égal à n et d, avec n + d = p et D premier avec x. D admet
donc un inverse modulo xp , si on multiplie par D, on obtient :

DP = Nxp+1 )
(mod

On eectue l'algorithme de Bézout pour A = xp+1 et B = P :

AUk + BVk = Rk ; U0 = 1 = V1 ; U1 = 0 = V0 ; R0 = xp+1 ; R1 = P

et on s'arrête au premier rang k tel que le degré de Rk soit inférieur ou égal à
n. On montre ensuite que :
deg(Vk ) + deg(Rk 1 ) = ::: = deg(V1 ) + deg(R0 ) = deg(A) = p + 1
ce qui entraine que le degré de Vk est inférieur ou égal à p + 1 (n + 1) = d.
On obtient ainsi une solution de DP = N (mod xp+1 ) (D = Vk et N = Rk ).
Si Vk est premier avec x, on conclut. On peut montrer que si Vk et Rk ne sont
pas premiers entre eux, alors (1) n'admet pas de solutions avec ces conditions
de degré.
Par exemple pour ex en prenant p = 6 et n = 3, on trouve (x3 + 12x2 + 60 
x + 120)=( x3 + 12x2 60x + 120).
On peut montrer qu'il existe un " > 0 tel que l'erreur absolue entre f et
son approximant de Padé sur [ "; "] est atteint aux bornes de l'intervalle, et on
peut calculer explicitement une valeur de ".
Cette méthode est très utile en pratique, par exemple pour le calcul de la
fonction exponentielle en précision machine, car elle nécessite d'une part moins
d'opérations (à cause de la symétrie numérateur/dénominateur) et fournit de

3
plus une approximation de meilleure qualité que le développement de Taylor de
ex (à l'ordre 6 ici).
On peut aussi approcher une fonction par une fraction rationnelle interpolant
la fonction en certains points (comme pour les polynômes de Lagrange mais avec
une fraction au lieu d'un polynôme). Le problème à résoudre est analogue mais
modulo un produit de x xi au lieu de xt+1 . On parle d'approximant de Cauchy.

4 Méthodes mixtes
Pour le calcul des fonctions usuelles, on utilise la plupart du temps une
combinaison des méthodes ci-dessus et des propriétés de ces fonctions.
Par exemple, pour calculer le logarithme d'un ottant en base 2, on calcule
une fois pour toutes ln(2) à la précision souhaitée, puis on utilise la représen-
tation a = 2e (1 + m), donc ln(a) = e ln(2) + ln(1 + m) avec m 2 [0; 1[. On
peut alors utiliser le développement en séries de 1 + m mais si m est proche de
1, la convergence sera très lente (controlée par la nature de série alternée). On
peut alors décider de calculer une approximation en prenant le développement
à l'ordre disons 9, puis on eectue quelques itérations de Newton de l'équation
ex a = 0 en prenant comme valeur initiale cette valeur (par excès) de ln(a).
Cette méthode pourrait en particulier être utilisée pour calculer le logarithme
multi-précision à partir d'une valeur approchée par excès en simple précision
(en réalité, on utilise la moyenne arithmético-géométrique qui est utilisée, elle
fait intervenir un encadrement d'une intégrale elliptique par ln(x) en utilisant
les valeurs de ln(2) et  ).
On peut aussi utiliser des méthodes ad hoc pour calculer la valeur initiale,
par exemple pour la fonction arctangeante sur un microprocesseur calculant en
base 10, on stocke les valeurs de arctan(10 k ) pour les premières valeurs de k .
Soit a l'angle dont on veut calculer l'arctangente, on se ramène d'abord à a
dans l'intervalle [0; 1]. Soit = arctan(a). On pose alors x = a et y = 1. Soit
= arctan(10
1 ). On calcule

x=y 1=10 x y=10

= x=y y + x=10
tan( ) = =
1 + 1 10

Si ce nombre est positif, on pose x0 = x y=10 et y0 = y + x=10, et on se

ramène au calcul de arctan(x0 =y 0 ). Si ce nombre est négatif, cela signie que
le développement décimal de arctan(x=y ) a comme première décimale 0. On
calcule ainsi la première décimale du développement de arctan(a) en eectuant
uniquement des additions, des soustractions et des décalages (une division par
10 étant un décalage). On continue alors de la même manière pour les décimales
suivantes qui sont dans la table des arctangentes. On termine en eectuant la
méthode de Newton.

4
5 Suggestions de développement
 Complexité des opérations de base sur les ottants multiprécision, cas de
la racine carrée, de l'exponentielle en utilisant le développement en séries.
 Approximation polynomiale par intervalles avec recollement C 1 , C 2 , etc.
 Calcul des fonctions usuelles (discussion sur les méthodes, leur ecacité...)
 Interpolation de Lagrange, calcul eectif (diérences divisées), applica-
tions (par exemple pour des algorithmes ecaces : polynome caractéris-
tique, PGCD à plusieurs variables,...)
 Calcul d'approximants de Padé ou de Cauchy.
 Comparaison entre diérentes méthodes d'approximation pour une même
fonction (par exemple le logarithme nepérien, la fonction sinus), dans l'op-
tique du calcul en simple et multi-précision.