next up previous contents
Next: Implementation Up: Laguerre method Previous: Laguerre method   Contents

Mathematical background

Let $P(x)$ be an univariate polynomial of degree $n$:

P(x)= a_0 x^n + a_{1} x^{n-1}+.....a_n=0

with $a_0a_n \not=0$, $a_0>0$. Let's define the sequence :

f_0=a_0, f_1=xf_0+a_1,
\ldots,f_i =xf_{i-1}+a_i,\ldots,f_n=f_{n-1}+a_n=P

If it exists a real $c$ such that $f_i(c)\ge 0$ for all $i$ in [0,$n$], then $P(x)>0$ for all $x>c$. Consequently all the roots of $P$ are lower than $c$ [13]. To find $c$ the following scheme can be used:
  1. let $c$ be such that $f_1(c) \ge 0$
  2. let $k$ the smallest integer such that either $k=n+1$ or $k\le
n$ and $f_k(c) \le 0$
  3. if $k\le
n$ then substitute $c$ by $c^\prime$ such that $f_k(c^\prime) \ge 0$ and go to 2
  4. return $c$
A consequence of Laguerre theorem is that the best bound cannot be lower than $-a_1/a_0$.

Jean-Pierre Merlet 2012-12-20