M ANUEL DE CALCUL NUMÉ RIQUE APPLIQUÉ
Le nombre de racines positives est donné par :
Nz = N(0) - N(+~O).
Il faut, pour calculer Nz, connaître les coefficients des termes de degré zéro dans chacun des
polynômes (il s’agit de la constante). Nous pouvons donc en déduire que, pour qu’un polynôme
de degré n possède n racines réelles, il faut que les coefficients de degré le plus élevé soient
positifs pour chacun des polynômes de la suite de Sturm. Par ailleurs, pour qu’un polynôme
n’ait que des racines positives, il faut en plus que les termes de degré zéro aient des signes
alternés. Insistons sur le fait que le théorème de Sturm peut se révéler très efficace pour localiser
une racine ou pour vérifier qu’il existe ou non une racine dans un domaine choisi à l’avance (fini
ou infini).
5. Disposition des calculs, schéma de Routh (1831-1907)
Le but de cet algorithme (1905) est avant tout d’éviter les nombres fractionnaires résultant de
la division de deux polynômes consécutifs. À cette fin, il suffit de multiplier tous les coefficients
du dividende et tous les coefficients du diviseur par deux nombres tels que le reste et le quotient
n’aient pas de nombres fractionnaires comme coefficients. On dispose sur deux rangées les
coefficients de Q~(z) et de &I(X) selon les puissances décroissantes.
a0
a1 CL2
a3 u4
. .
G-1
a,
b. bl bz b3 b4 . . b,+l b,.
On calcule une troisième rangée de termes appelés cj possédant (n - 1) termes et que l’on
exprime facilement à partir des uj et des bj au moyen de la relation :
c3-1 = boa, - aobj
avec
j = l...n.
Cette ligne correspond au reste partiel de la division de Q~(z) et QI(Z), on obtient le reste
définitif en calculant une quatrième rangée de termes dj exprimée au moyen d’une combinaison
linéaire des b.j et des cj :
dj-i = cobj - bocj.
La rangée des dk est donc l’ensemble des coefficients, disposés selon les puissances décroissantes, du polynôme &z(~). On recommence rigoureusement les mêmes opérations en utilisant
les polynômes QI(Z) et Q~(x) ; on p oursuit jusqu’à parvenir à Qn(x).
6. Quelques exemples de suites de Sturm
Chaque suite de polynômes orthogonaux constitue une suite de Sturm. L’étude des zéros de ces
polynômes peut être envisagée par ce moyen.
7. Mise en œuvre du théorème de Sturm
Sur le Web (*), nous proposons le programme sturm. c qui dénombre les racines réelles d’un
polynôme quelconque à coefficients réels. Afin de limiter la taille très rapidement croissante des
nombres calculés par la méthode de Routh, à chaque calcul de la suite des dj, nous effectuons
la recherche du PGCD de tous les nombres d,, puis, le cas échéant, nous procédons à la
simplification, c’est-à-dire à la division par le PGCD.
*http://www.edpsciences.com/guilpin/
386
Le nombre de racines positives est donné par :
Nz = N(0) - N(+~O).
Il faut, pour calculer Nz, connaître les coefficients des termes de degré zéro dans chacun des
polynômes (il s’agit de la constante). Nous pouvons donc en déduire que, pour qu’un polynôme
de degré n possède n racines réelles, il faut que les coefficients de degré le plus élevé soient
positifs pour chacun des polynômes de la suite de Sturm. Par ailleurs, pour qu’un polynôme
n’ait que des racines positives, il faut en plus que les termes de degré zéro aient des signes
alternés. Insistons sur le fait que le théorème de Sturm peut se révéler très efficace pour localiser
une racine ou pour vérifier qu’il existe ou non une racine dans un domaine choisi à l’avance (fini
ou infini).
5. Disposition des calculs, schéma de Routh (1831-1907)
Le but de cet algorithme (1905) est avant tout d’éviter les nombres fractionnaires résultant de
la division de deux polynômes consécutifs. À cette fin, il suffit de multiplier tous les coefficients
du dividende et tous les coefficients du diviseur par deux nombres tels que le reste et le quotient
n’aient pas de nombres fractionnaires comme coefficients. On dispose sur deux rangées les
coefficients de Q~(z) et de &I(X) selon les puissances décroissantes.
a0
a1 CL2
a3 u4
. .
G-1
a,
b. bl bz b3 b4 . . b,+l b,.
On calcule une troisième rangée de termes appelés cj possédant (n - 1) termes et que l’on
exprime facilement à partir des uj et des bj au moyen de la relation :
c3-1 = boa, - aobj
avec
j = l...n.
Cette ligne correspond au reste partiel de la division de Q~(z) et QI(Z), on obtient le reste
définitif en calculant une quatrième rangée de termes dj exprimée au moyen d’une combinaison
linéaire des b.j et des cj :
dj-i = cobj - bocj.
La rangée des dk est donc l’ensemble des coefficients, disposés selon les puissances décroissantes, du polynôme &z(~). On recommence rigoureusement les mêmes opérations en utilisant
les polynômes QI(Z) et Q~(x) ; on p oursuit jusqu’à parvenir à Qn(x).
6. Quelques exemples de suites de Sturm
Chaque suite de polynômes orthogonaux constitue une suite de Sturm. L’étude des zéros de ces
polynômes peut être envisagée par ce moyen.
7. Mise en œuvre du théorème de Sturm
Sur le Web (*), nous proposons le programme sturm. c qui dénombre les racines réelles d’un
polynôme quelconque à coefficients réels. Afin de limiter la taille très rapidement croissante des
nombres calculés par la méthode de Routh, à chaque calcul de la suite des dj, nous effectuons
la recherche du PGCD de tous les nombres d,, puis, le cas échéant, nous procédons à la
simplification, c’est-à-dire à la division par le PGCD.
*http://www.edpsciences.com/guilpin/
386