322. La borne de Cauchy (2/2)

Dans le prolongement d’un autre article consacré à la borne de Cauchy d’un polynôme, il sera donné ici un moyen de la calculer de façon approchée.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 321.

Dans toute la suite, $P$ désignera un polynôme à coefficients complexes, unitaire et non constant. Vous noterez $m$ son degré et vous supposerez que $P \neq X^m.$ Ainsi il existe un unique $m$-uplet $(a_{m-1},\dots,a_0)\in\C^m\setminus\{(0,\dots,0)\}$ tel que :

P(X) = X^m-a_{m-1}X^{m-1}-\cdots-a_1X-a_0.

Localisez la borne de Cauchy en utilisant la méthode de dichotomie

Rappels sur les outils

Vous considérez le polynôme $Q$ défini par :

Q(X) = X^m – \vert a_{m-1}\vert X^{m-1}-\cdots-\vert a_{1}\vert X-\vert a_{0}\vert.

Pour tout réel $x\in ]0,+\infty[$ vous posez :

f(x) = \frac{Q(x)}{x^m}.

Il a été vu dans l’article cité en introduction que la borne de Cauchy de $P$ est l’unique réel strictement positif noté $c(P)$ qui vérifie la double égalité $f(c(P))=0$ et $Q(c(P))=0.$ Il a été établi que la fonction $f$ est strictement croissante sur $]0,+\infty[.$

Soit $A$ le maximum du module de tous les coefficients de $P\comma$ sans tenir compte de son coefficient dominant. Autrement dit vous avez :

A = \max\{\vert a_i\vert, i\in\llbracket 0, m-1 \rrbracket\}.

Comme $P\neq X^m\comma$ l’un des coefficients $a_i$ est non nul, donc $A\gt0.$

Ce même article a montré que $c(P) \leq 1+A$ et que $Q(1+A)\geq 0\comma$ ce qui fournit en particulier :

c(P)\in[0, 1+A].

Une récurrence pour construire l’algorithme de dichotomie

Vous noterez $u_0 = 0$ et $v_0 =1+A\comma$ de sorte que $c(P)\in[u_0,v_0].$ Notez que $Q(u_0) = Q(0)=-\vert a_0\vert.$ Donc $Q(u_0)\leq 0.$ De plus, $Q(v_0) \geq 0.$ Notez que :

v_0 = u_0+\frac{1+A}{2^0}.

Soit maintenant $n$ un entier naturel et supposez construits des réels positifs $u_n$ et $v_n$ avec $v_n = u_n + \frac{1+A}{2^n}$ tels que $c(P)\in[u_n,v_n]\comma$ $Q(u_n)\leq 0$ et $Q(v_n)\geq 0.$

Considérez le réel positif $c_n=\frac{u_n+v_n}{2}.$

Premier cas. Si $Q(c_n)\lt 0\comma$ vous posez $u_{n+1} = c_n$ et $v_{n+1} = v_n.$ Les réels $u_{n+1}$ et $v_{n+1}$ sont alors positifs.

D’autre part :

\begin{align*} v_{n+1}-u_{n+1} &= v_n-c_n \\ &= \frac{2v_n}{2}-\frac{u_n+v_n}{2}\\ &=\frac{2v_n-u_n-v_n}{2}\\ &=\frac{v_n-u_n}{2}\\ &=\frac{\frac{1+A}{2^n}}{2}\\ &=\frac{1+A}{2^{n+1}}. \end{align*}

Vous avez bien $Q(u_{n+1}) = Q(c_n)$ et donc $Q(u_{n+1})\leq 0.$ De même, $Q(v_{n+1})=Q(v_n)$ donc $Q(v_{n+1})\geq 0.$

L’égalité $v_{n+1} = u_{n+1} + \frac{1+A}{2^{n+1}}$ montre que $v_{n+1}\gt0.$ Du coup $\frac{Q(v_{n+1})}{v_{n+1}^m }\geq 0$ et $f(v_{n+1})\geq 0$ soit $f(v_{n+1}) \geq f(c(P)).$

Supposez que $c(P) \gt v_{n+1}.$ Les nombres $c(P)$ et $v_{n+1}$ appartenant à $]0,+\infty[\comma$ intervalle où $f$ est strictement croissante, il vient $f(c(P))\gt f(v_{n+1})\comma$ ce qui est une contradiction. Donc $c(P) \leq v_{n+1}.$

De même, supposez que $u_{n+1} \gt c(P).$ Comme $c(P)$ et $u_{n+1}$ sont deux nombres appartenant à $]0,+\infty[\comma$ intervalle où $f$ est strictement croissante, vous déduisez $f(u_{n+1})\gt f(c(P))$ donc $\frac{Q(u_{n+1})}{u_{n+1}^m} \gt 0$ et donc $Q(u_{n+1})\gt0$ soit $Q(c_n)\gt 0\comma$ ce qui est une contradiction. Donc $u_{n+1} \leq c(P).$

Second cas. Si $Q(c_n)\geq 0\comma$ vous posez $u_{n+1} = u_n$ et $v_{n+1} = c_n.$ Les réels $u_{n+1}$ et $v_{n+1}$ sont encore positifs. D’autre part :

\begin{align*} v_{n+1}-u_{n+1} &= c_n-u_n \\ &= \frac{u_n+v_n}{2}-\frac{2u_n}{2}\\ &=\frac{u_n+v_n-2u_n}{2}\\ &=\frac{v_n-u_n}{2}\\ &=\frac{\frac{1+A}{2^n}}{2}\\ &=\frac{1+A}{2^{n+1}}. \end{align*}

Vous avez $Q(u_{n+1}) = Q(u_n)$ or $Q(u_n)\leq 0$ donc $Q(u_{n+1})\leq 0.$
De même, $Q(v_{n+1}) = Q(c_n)$ or $Q(c_n)\geq 0$ donc $Q(v_{n+1})\geq 0.$

Supposez que $c(P)\lt u_{n+1}.$ Le réel $c(P)$ étant strictement positif, vous déduisez que $c(P)$ et $u_{n+1}$ appartiennent à l’intervalle $]0,+\infty[.$ Par stricte croissance de la fonction $f$ sur cet intervalle, il vient $f(c(P))\lt f(u_{n+1})$ donc $0\lt\frac{Q(u_{n+1})}{u_{n+1}^m}$ donc $Q(u_{n+1})\gt 0\comma$ ce qui est une contradiction. Donc $u_{n+1}\leq c(P).$

Supposez que $v_{n+1}\lt c(P).$ Vous avez $v_{n+1} = u_{n+1}+\frac{1+A}{2^{n+1}}$ avec $A\gt0$ et $u_{n+1}$ positif, donc $v_{n+1}\gt0.$ Les réels $c(P)$ et $v_{n+1}$ appartiennent à l’intervalle $]0,+\infty[.$ Par stricte croissance de la fonction $f$ sur cet intervalle, il vient $ f(v_{n+1}) \lt f(c(P))$ donc $f(v_{n+1})\lt0$ d’où $\frac{Q(v_{n+1})}{v_{n+1}^m}\lt 0$ et donc $Q(v_{n+1})\lt0\comma$ ce qui est une contradiction. Donc $c(P)\leq v_{n+1}.$

Dans les deux cas, les réels $u_{n+1}$ et $v_{n+1}$ vérifient les mêmes propriétés que $u_n$ et $v_n\comma$ au rang $n+1.$ La construction par récurrence est donc terminée.

Explicitez l’algorithme de dichotomie

Vous posez $u_0 = 0$ et $v_0 = 1+A.$

Pour tout entier naturel $n$ vous calculez $c_n=\frac{u_n+v_n}{2}.$

Si $Q(c_n)\lt 0$ vous posez $u_{n+1} = c_n$ et $v_{n+1} = v_n.$
Si $Q(c_n)\geq 0$ vous posez $u_{n+1} = u_n$ et $v_{n+1} = c_n.$

Il a été démontré ci-dessus que :

\forall n\in\N, u_n\leq c(P) \leq v_n.

D’autre part il est aussi établi que :

\forall n\in\N, v_n = u_n + \frac{1+A}{2^n}.

Comme $2\gt1\comma$ vous avez $\lim_{n\to +\infty} 2^n = +\infty$ et par quotient $\lim_{n\to +\infty} \frac{1+A}{2^n} = 0.$
Ainsi, la suite $(v_n-u_n)_{n\geq 0}$ converge vers $0.$

Soit $n$ un entier naturel. Si $Q(c_n)\geq 0\comma$ alors $u_{n+1}-u_n = 0$ donc $u_{n+1}\geq u_n.$
Si $Q(c_n)\lt0\comma$ alors $u_{n+1}-u_n = c_n-u_n = \frac{1+A}{2^{n+1}}$ or $1+A\gt 0$ donc $u_{n+1}-u_n\geq 0.$
Vous en déduisez que la suite $(u_n)_{n\geq 0}$ est croissante.

Soit $n$ un entier naturel. Si $Q(c_n) \lt 0\comma$ alors $v_{n+1}-v_n = 0$ donc $v_{n+1}\leq v_n.$
Si $Q(c_n)\geq 0\comma$ alors $v_{n+1}-v_n = c_n-v_n = -\frac{1+A}{2^{n+1}}$ or $1+A\gt 0$ donc $v_{n+1}-v_n\leq 0.$
Vous en déduisez que la suite $(v_n)_{n\geq 0}$ est décroissante.

La suite $(u_n)_{n\geq 0}$ est croissante, la suite $(v_n)_{n\geq 0}$ est décroissante et leur différence tend vers zéro : ces deux suites sont adjacentes. Elles convergent donc vers une même limite $\ell \in\R.$

Comme $\forall n\in\N, u_n\leq c(P) \leq v_n$ le théorème des gendarmes fournit $c(P) = \ell.$

Concluez

En définitive, les suites $(u_n)_{n\geq 0}$ et $(v_n)_{n\geq 0}$ convergent vers la borne de Cauchy $c(P).$

Pour tout $n\in\N\comma$ les inégalités $u_n\leq c(P) \leq v_n$ fournissent un encadrement de $c(P)$ d’amplitude $\frac{1+A}{2^n}$ ce qui permet d’obtenir une valeur approchée de $c(P)$ à la précision souhaitée.

Un exemple

Soit $P$ le polynôme défini par :

P(X) = X^3+(-2+3i)X^2+(-3-5i)X+(6-2i).

Vous calculez les modules des coefficients de $P$ comme suit :

\begin{align*} \vert -2+3i\vert &= \sqrt{4+9} = \sqrt{13}\\ \vert -3-5i\vert &= \sqrt{9+25} = \sqrt{34}\\ \vert 6-2i\vert &= \sqrt{36+4} = \sqrt{40} = 2\sqrt{10}. \end{align*}

La borne de Cauchy $c(P)$ est l’unique racine réelle strictement positive du polynôme $Q$ défini par :

Q(X) = X^3-\sqrt{13}X^2-\sqrt{34}X-2\sqrt{10}.

Le maximum du module des coefficients de $P\comma$ excepté son coefficient dominant, vaut :

A = 2\sqrt{10}.

Pour trouver un encadrement de $c(P)$ d’amplitude $10^{-3}\comma$ vous posez :

\left\{\begin{align*} u_0 &= 0\\ v_0 &= 1+2\sqrt{10}. \end{align*} \right.

Pour tout entier naturel $n\comma$ vous posez $c_n=\frac{u_n+v_n}{2}.$ Puis vous posez :

u_{n+1} = \left\{\begin{align*} c_n &\text{ si } Q(c_n) \lt 0\\ u_n &\text{ sinon} \end{align*} \right.

v_{n+1} = \left\{\begin{align*} v_n &\text{ si } Q(c_n) \lt 0\\ c_n &\text{ sinon.} \end{align*} \right.

En notant $\log$ le logarithme décimal, l’amplitude de l’encadrement souhaité fournit :

\begin{align*} \frac{1+A}{2^n} &\leq 10^{-3} \\ 1000(1+A)&\leq 2^n\\ 3 + \log(1+A)&\leq n\log 2\\ \frac{3+\log(1+2\sqrt{10})}{\log 2} &\leq n. \end{align*}

Comme $\frac{3+\log(1+2\sqrt{10})}{\log 2}\approx 12{,}84$ et que $n$ est entier, il suffit de prendre $n\geq 13.$ Il suffit donc de faire tourner $13$ fois la boucle de l’algorithme ci-dessous.

from math import sqrt

def Q(x) :
    return x**3 - sqrt(13)*x**2 - sqrt(34)*x - 2*sqrt(10)

u = 0
v = 1 + 2*sqrt(10)

for i in range(13) :
    c = (u + v)/2
    if Q(c) < 0 :
        u = c
    else :
        v = c

print(u)
print(v)
print(v - u)

L’exécution de ce programme affiche successivement $u_{13}\comma$ $v_{13}$ puis leur différence.

5.017749567593981
5.018643678350858
0.0008941107568771756

Il vient :

u_{13}\leq c(P) \leq v_{13}.

En prenant la valeur approchée par défaut de $u_{13}$ à $10^{-4}$ près et celle par excès de $v_{13}$ à $10^{-4}$ près, il vient un encadrement correct :

\boxed{5{,}0177\leq c(P) \leq 5{,}0187.}

Note. La borne de Cauchy fournit un majorant du module de toutes les racines de $P.$ Cependant ce majorant est loin d’être optimal, même s’il peut arriver que certains polynômes aient une racine dont le module est égal à leur borne de Cauchy. Sur cet exemple, la plus grande racine de $P$ en module a un module voisin de $2{,}24\comma$ très inférieur à $5{,}02.$