Dans le prolongement du contenu écrit dans l'article 321, il sera donné des moyens de calculer la borne de Cauchy d’un polynôme.
Dans toute la suite, $P$ désignera un polynôme à coefficients complexes 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 le contenu rédigé dans l'article 321 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$, sans tenir compte de son coefficient dominant. Autrement dit vous avez:
A = \max\{\vert a_i\vert, i\in\llbracket 0, m-1 \rrbracket\}.Le contenu rédigé dans l'article 321 a montré que $c(P) \leq 1+A$, que $Q(1+A)\geq 0$ et que :
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$, 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]$, $Q(u_n)\leq 0$ et $Q(v_n)\geq 0.$
Considérez le réel positif $c_n=\frac{a_n+b_n}{2}.$
1er cas. $Q(c_n)< 0.$ 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}>0$ 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)).$
Si vous avez $c(P) > v_{n+1}$, notez d’abord que $c(P)$ et $v_{n+1}$ sont deux nombres appartenant à $]0,+\infty[$, intervalle où $f$ est strictement croissante, alors $f(c(P))>f(v_{n+1})$, contradiction. Donc $c(P) \leq v_{n+1}.$
De même, supposez que $u_{n+1} > c(P).$ Comme $c(P)$ et $u_{n+1}$ sont deux nombres appartenant à $]0,+\infty[$, intervalle où $f$ est strictement croissante, vous déduisez $f(u_{n+1})>f(c(P))$ donc $\frac{Q(u_{n+1})}{u_{n+1}^m} > 0$ et donc $Q(u_{n+1})>0$ soit $Q(c_n)> 0.$ Contradiction. Donc $u_{n+1} \leq c(P).$
2ème cas. $Q(c_n)\geq 0.$ 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.
\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)<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))< f(u_{n+1})$ donc $0<\frac{Q(u_{n+1})}{u_{n+1}^m}$ donc $Q(u_{n+1})> 0$, contradiction. Donc $u_{n+1}\leq c(P).$
Supposez que $v_{n+1}<c(P).$ Vous avez $v_{n+1} = u_{n+1}+\frac{1+A}{2^{n+1}}$ avec $A>0$ et $u_{n+1}$ positif, donc $v_{n+1}>0.$ 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}) < f(c(P))$ donc $f(v_{n+1})<0$ d’où $\frac{Q(v_{n+1})}{v_{n+1}^m}< 0$ et donc $Q(v_{n+1})<0$ contradiction. Donc $c(P)\leq v_{n+1}.$
La 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)< 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>1$, 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$, $u_{n+1}-u_n = 0$ donc $u_{n+1}\geq u_n.$
Si $Q(c_n)<0$, il vient : $u_{n+1}-u_n = c_n-u_n = \frac{1+A}{2^{n+1}}$ or $1+A> 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) < 0$, $v_{n+1}-v_n = 0$ donc $v_{n+1}\leq v_n.$
Si $Q(c_n)\geq 0$, il vient : $v_{n+1}-v_n = v_n-c_n = \frac{1+A}{2^{n+1}}$ or $1+A> 0$ donc $v_{n+1}-v_n\geq 0.$
Vous en déduisez que la suite $(v_n)_{n\geq 0}$ est décroissante.
Etant donné que les suites $(u_n)_{n\geq 0}$ et $(v_n)_{n\geq 0}$ sont adjacentes, elles convergent vers la 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$, 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 que l’on souhaite.
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$ :
\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$, excepté son coefficient dominant, vaut :
A = 2\sqrt{10}.Pour trouver un encadrement de $c(P)$ d’amplitude $10^{-3}$, vous posez :
\left\{\begin{align*}
u_0 &= 0\\
v_0 &= 1+2\sqrt{10}.
\end{align*}
\right.Pour tout entier naturel $n$, 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) < 0\\
u_n &\text{ sinon}
\end{align*}
\right.v_{n+1} = \left\{\begin{align*}
v_n &\text{ si } Q(c_n) < 0\\
c_n &\text{ sinon.}
\end{align*}
\right.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\\
12,8&\leq n\\
13&\leq n.
\end{align*}Il suffit de faire tourner la boucle de l’algorithme ci-dessous $13$ fois.
Il vient :
\begin{align*}
u_{13}\leq c(P) \leq v_{13}.
\end{align*}En prenant la valeur approchée par défaut de $u_{13}$ à $10^{-4}$ et celle par excès de $v_{13}$ à $10^{-4}$, 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 l’ensemble des racines de $P.$ Cependant ce dernier est loin d’être optimal, même s’il peut arriver que certains polynômes aient une racine égale à leur borne de Cauchy.
