4. RÉSOLUTION DES É QUATIONS NUMÉRIQUES
expressions calculées au point (5k-1, Yk-r)
xk+l = xk ~ ~
a2 + bz
bd&
!/k+l = yk - ~
aa + bz
expressions calculées au point (xk, yk). La convergence n’est plus systématiquement assurée
comme dans le cas linéaire. Dans certains calculs, elle a retenu notre attention pour sa grande
stabilité, et nous avons pu accélérer la vitesse de convergence au moyen de l’epsilon-algorithme.
Le lecteur trouvera sur le Web(*) 1 e programme kacmarz. c permettant l’usage de cette
procédure.
3. Racines d’un polynôme
3.1. Méthode de Bairstow (1914)
Ici encore, nous allons limiter nos préoccupations à l’étude des polynômes à coefficients réels
que l’on notera de la façon suivante :
P,(x) = aOxn + alx n-l + a2xnp2 +. . + an-lx + a,
avec comme condition quasi évidente ao # 0. Nous savons qu’un polynôme de degré n admet
n racines réelles ou complexes et nous allons étudier une méthode très élégante pour obtenir
lesdites racines.
L’idée générale du calcul repose sur le schéma suivant : dans le cas où n est supérieur à deux
on peut diviser P,(x) par un trinôme T(z) de la forme :
T(x) = x2 + ux + u
ce qui nous permet d’obtenir une expression nouvelle de P,(x) à savoir :
P,(x) = T(x)Q,-2(x) + Ax + B
où Qn-z(x) est un polynôme de degré (n - 2) et (Ax + B) un monôme exprimant le reste de la
division. Nous allons faire en sorte que A et B qui sont des fonctions implicites de u et ‘u soient
nulles ; on réalisera cela en ajustant convenablement les valeurs de u et u apparaissant dans le
trinôme. Lorsque nous y serons parvenus, le polynôme s’écrira sous la forme d’un produit strict
d’un trinôme et d’un polynôme de degré (n ~ 2). Ainsi, les racines du trinôme seront également
les racines du polynôme P,(x), et l’on sait qu’il n’y a pas de difficultés particulières à calculer
les racines d’un trinôme.
Rien ne nous empêche de faire subir le même traitement au polynôme Q+2(2), et ainsi de
suite jusqu’à ce que Q,(z) soit un polynôme de degré 1 ou 2. En définitive, tout le problème
repose sur la détermination des paramètres u et v qui annulent simultanément A et B. Nous
avons donc à résoudre un système non linéaire de deux équations à deux inconnues que nous
écrivons :
A(~U) = 0
B(u,v) = 0
expressions calculées au point (5k-1, Yk-r)
xk+l = xk ~ ~
a2 + bz
bd&
!/k+l = yk - ~
aa + bz
expressions calculées au point (xk, yk). La convergence n’est plus systématiquement assurée
comme dans le cas linéaire. Dans certains calculs, elle a retenu notre attention pour sa grande
stabilité, et nous avons pu accélérer la vitesse de convergence au moyen de l’epsilon-algorithme.
Le lecteur trouvera sur le Web(*) 1 e programme kacmarz. c permettant l’usage de cette
procédure.
3. Racines d’un polynôme
3.1. Méthode de Bairstow (1914)
Ici encore, nous allons limiter nos préoccupations à l’étude des polynômes à coefficients réels
que l’on notera de la façon suivante :
P,(x) = aOxn + alx n-l + a2xnp2 +. . + an-lx + a,
avec comme condition quasi évidente ao # 0. Nous savons qu’un polynôme de degré n admet
n racines réelles ou complexes et nous allons étudier une méthode très élégante pour obtenir
lesdites racines.
L’idée générale du calcul repose sur le schéma suivant : dans le cas où n est supérieur à deux
on peut diviser P,(x) par un trinôme T(z) de la forme :
T(x) = x2 + ux + u
ce qui nous permet d’obtenir une expression nouvelle de P,(x) à savoir :
P,(x) = T(x)Q,-2(x) + Ax + B
où Qn-z(x) est un polynôme de degré (n - 2) et (Ax + B) un monôme exprimant le reste de la
division. Nous allons faire en sorte que A et B qui sont des fonctions implicites de u et ‘u soient
nulles ; on réalisera cela en ajustant convenablement les valeurs de u et u apparaissant dans le
trinôme. Lorsque nous y serons parvenus, le polynôme s’écrira sous la forme d’un produit strict
d’un trinôme et d’un polynôme de degré (n ~ 2). Ainsi, les racines du trinôme seront également
les racines du polynôme P,(x), et l’on sait qu’il n’y a pas de difficultés particulières à calculer
les racines d’un trinôme.
Rien ne nous empêche de faire subir le même traitement au polynôme Q+2(2), et ainsi de
suite jusqu’à ce que Q,(z) soit un polynôme de degré 1 ou 2. En définitive, tout le problème
repose sur la détermination des paramètres u et v qui annulent simultanément A et B. Nous
avons donc à résoudre un système non linéaire de deux équations à deux inconnues que nous
écrivons :
A(~U) = 0
B(u,v) = 0