# Newton-Horner Method Example

I'm struggling to understand Newton-Horner's method and to find information about it so pardon me if I seem a bit lost in expressing my question, my goal is to implement it in racket as a learning exercise.

Given a polynomial $P(x)$ of $n$ degree and that has $\bar x_n$ roots it is used to find said roots.

$$x_{i + 1} = x_i - \frac{\frac{f(x_i)}{f'(x_i)}}{1 - \frac{f(x_i)}{f'(x_i)} \sum_{j=1}^{n}(\frac{1}{x_i - \bar x_j})}$$

I can identify Newton's Method, however I'm a bit lost in how exactly the whole method is applied.

I know that for the first iteration it is the result if using Newton's method with a supplied first guess value (because the Sum part is $0$). I've evaluated a sample polynomial $P(x) = 4x^5 - 3x^4 - 2x^2 +12x + 4$ for $x_0 = 0$ but on subsequent iterations the sum part is always zero.

I've searched quite extensively but all I find are the descriptions of Newton's Method and Horner's Method used in an independent manner I've also found lots of old homework exercises implemented in Mathematica or matlab, but none that describes the method thoroughly. If anyone has links to resources or can explain it I'd appreciate it a lot.

-
Maybe you can work through this example (if you have mathematica, you can actually run the example and change it). math.fullerton.edu/mathews/n2003/horner/HornerMod/Links/… – Amzoti Nov 22 '12 at 22:13
I correct the most glaring error in the formula so that it looks like Newtons method. The sum is still wrong, j=i needs to be excluded. If the sum is over the most recent approximations, under consideration of $j\ne i$, then this is the Aberth-Ehrlich method for the simultaneous approximation of the roots. en.wikipedia.org/wiki/Aberth_method – LutzL May 13 '14 at 15:45

Okay lets give it a try. First of all i think there need to be some corrections in your formula. NH Method is used to calculate the roots of a polynomial. We will use Newton to calcluate a root $x^*_j$ of the polynomial and divide the polynomial by $(x-x^*_j)$ and restart Newton. Therefore, this methods calculates the root $x_{k+1}$ if you already got the roots $x_1...x_k$. So I dont think the sum in your formula iterates over all roots, but rather goes from $i=1..k$ if we are calculating the root $x_{k+1}$. Thats why I would also suggest to add another index $k$ for the number of the root.

So in my notation, $i$ describes the iteration of Newton and $k$ the root we want to find. Assuming we already know the first $k$ roots. We now want to find the roots of the polynomial \begin{align} P^{k+1}(x) = P(x) \cdot \frac{1}{\prod_{j=1}^{k} (x-x^*_j)} \end{align} So we apply Newton to this polynomial: \begin{align} x^{k+1}_{i+1} = x^{k+1}_{i} - \frac{P^{k+1}(x^{k+1}_{i})}{(P^{k+1}(x^{k+1}_{i}))'} \end{align} We obtain $P^{k+1}(x)'$ by chainrule: \begin{align} P^{k+1}(x)' &=(P(x) \cdot \frac{1}{\prod_{j=1}^{k} (x-x^*_j)})' \\ &=P'(x)\cdot \frac{1}{\prod_{j=1}^{k} (x-x^*_j)} +(P(x)\sum_{m=1}^k \{ \frac{-1}{(x-x^*_m)}\prod_{j=1}^k\frac{1}{ (x-x^*_j)} \}) \\ &= \prod_{j=1}^k\frac{1}{ (x-x^*_j)}\{P'(x) -P(x) \sum_{m=1}^k\frac{1}{ (x-x^*_m)}\} \end{align}
Using this and the definition of $P^{k+1}$ we get \begin{align} \frac{P^{k+1}(x)}{(P^{k+1}(x))'} &= \frac{P(x)}{P'(x)-P(x)\sum_{m=1}^k \frac{1}{x-x^*_m}} \\ &= \frac{\frac{P(x)}{P'(x)}}{1-\frac{P(x)}{P'(x)}\sum_{m=1}^k \frac{1}{x-x^*_m}} \end{align} So if we finally write the complete Newton iteration we get: \begin{align} x^{k+1}_{i+1} = x^{k+1}_i -{\frac{P(x^{k+1}_i)}{P'(x^{k+1}_i)}}\frac{1}{1-\frac{P(x^{k+1}_i)}{P'(x^{k+1}_i)}\sum_{m=1}^k \frac{1}{x^{k+1}_i-x^*_m}} \end{align} Which differs from your formula. I am not sure whether or where I made a mistake, but I think this gives an overview over the background of the Newton Horners Method.

-

Methods of Horner and Newton-Raphson combined

Let $x = r$ be an approximation to a root of a polynomial $f(x)$, Dividing $f(x)$ by the linear factor $x-r$ using Horner method we get $$f(x) = g(x)(x-r) + a$$ from which $f(r)=a$. On differentiating follows $$f'(x) = g'(x)(x-r) + g(x)$$ so that $f'(r) = g(r)$. Now $g(r)$ can be found as before by dividing it by the linear factor $x-r$: $$g(x) = h(x)(x-r) + b$$ giving $g(r) = b$.

The new Newton-Raphson approximation $r'$ is now found as $$r' = r - f(r)/f'(r) = r - a/b.$$

-