next up previous contents
Next: Implementation Up: Newton method Previous: Newton 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$. Newton theorem state that if it exists $c$ such that $P(c)>0$ and for all the derivative $P^{(i)}$ of $P$, with $i \in [1,n]$, then $c$ is an upper bound of the positive roots of $P$. To find $c$ the following scheme can be used:
  1. let $c$ be such that $P^{(n-1)}(c) \ge 0$
  2. let $k$ the smallest integer such that either $k=n+1$ or $k\le
n$ and $P^{(n-k)}(c) \le 0$
  3. if $k\le
n$ then substitute $c$ by $c^\prime$ such that $P^{n-k)}(c^\prime) \ge 0$ and go to 2
  4. return $c$
A consequence of Newton theorem is that the best bound cannot be lower than $-a_1/(a_0~n)$.

Jean-Pierre Merlet 2012-12-20