Borne de Knuth

Hoeg

Bonjour,


Est-ce que quelqu'un aurait des références (ou une idée de preuve) concernant la borne de Knuth qui donne le rayon d'inclusion des racines d'un polynome $p(z)=a_nz^n+a_{n-1}z^{n-1}+\dots +a_0$ :
$$\rho=\max\{2\times \left| \frac{a_i}{a_n}\right|^{\frac{1}{n-i}},~~0\leq i\leq n-1 \}$$

Je sais montrer la borne de Cauchy mais pour la borne de Knuth je n'ai aucune idée et mes recherches sur le oueb sont restees infructueuses...

Par ailleurs, si quelqu'un a une référence intéressante sur la méthode de Durand-Kerner pour la recherche des zéros d'un polynôme, je suis aussi preneur.


Merci d'avance

Hoeg

borde

<!--latex-->Une preuve se trouve dans le livre de Jean Dieudonné : <I>Calcul infinitésimal</I> (Hermann), page 66.
<BR>
<BR>Borde.<BR>

Zantac

Faudrait te procurer ça (pour la méthode de Durand-Kerner) :

<http://catalogue-bibliotheque.imag.fr/Document.htm&numrec=031390868957260&gt;

Zantac

(pour la méthode de Durand-Kerner)

Hoeg

<!--latex-->merci beaucoup pour vos réponses rapides !
<BR>Malheureusement le <I>Calcul infinitésimal</I> de Dieudonné n'est pas disponible dans ma BU... serait-il possible d'avoir l' "idée'' de preuve ou (mais c'est pousser le vice un peu loin peut-etre) un scan de la preuve en question (mon mail eventuellement : helblinm@insa-rouen.fr) ?
<BR>Pour l'article de Fraigniaud j'avais vu cette ref mais je ne crois pas qu'on ait ce périodique non plus :-((...m'enfin je vais tenter par mail directement a l'auteur et on verra bien...
<BR>Encore merci !<BR><BR><BR>

borde

Je n'ai malheureusement pas de scanner...

Dieudonné "donne" sa preuve sous forme d'exercice : soit $\displaystyle {P(z) = z^n + \sum_{k=1}^n a_k z^{n-k}}$ un polynôme unitaire de degré $n$ à coefficients complexes. On note $\displaystyle {P(z) = \prod_{j=1}^n \left (z - z_j \right )}$ sa décomposition en facteurs du premier degré et $r_0 = \sup_{j} |z_j|$.

1°. Montrer que, si $r > 0$ est tel que $r^n \geq |a_1|r^{n-1} + ... + |a_{n-1}|r + a_n$, alors $r_0 \leq r$. En déduire que $$r_0 \leq \sup \left (1 \, , \, \sum_{k=1}^n |a_k| \right )$$

2°. Soit $(\lambda_j)$ une suite finie de $n$ nombres $> 0$ tels que $\displaystyle {\sum_{j=1}^{n} \frac {1}{\lambda_j} = 1}$. Utiliser 1° pour montrer que $$r_0 \leq \sup_{1 \leq j \leq n} (\lambda_j |a_j|)^{1/j}$$

3°. En déduire la relation cherchée si tous les coefficients sont $\not = 0$

Bon courage,

Borde.

Hoeg

Merci beaucoup Borde d'avoir pris le temps de recopier l'énoncé ! Je vais essayer de montrer ca (mais si quelqu'un a une reference autre avec une demonstration complete je suis toujours preneur...).

Par contre un point m'étonne. La question 3. laisse sous-entendre que tous les coefficients doivent etre non nuls or là ou j'avais vu cette borne cette condition n'etait pas specifiée. J'aimerais savoir si elle est juste liee a cette demonstration ou si elle est nécessaire pour pouvoir utiliser la borne de Knuth (désolé si cette question est bete !)....d'autant que mon etude va vraisemblablement porter sur des polynomes de grand degre mais relativement "creux"...

borde

Non, c'est une erreur de ma part.

Borde.