Horner's Method

Uses nesting requires $n$ multiplications and $n$ additions to evaluate any $n^{th}$ degree polynomial

Theorem Horner's : Let $P(x)=a_n x^n+a_{n-1}x^{n-1}+\cdots a_1 x+a_0$ and $b_n=a_n$. Set $b_k=a_k+b_{k+1}x_0$ for $k=n-1, n-2, \cdots 1,0$, then $b_0=P(x_0)$. Moreover, if

$$\begin{eqnarray*} Q(x)=b_n x^{n-1}+b_{n-1}x^{n-2}\cdots b_2x+b_1\\ \Rightarrow P(x)=(x-x_0)Q(x)+b_0 \end{eqnarray*}$$

Proof: Direct Calculation$\Box$

Example $4x^4+13x^3-x+8$    at $x_0=-3$
here $n=4$     $b_n = a_n = 4$
Remember $b_k=a_k+b_{k+1}x_0$

Using this formula we can calculate the coefficients $b_i$ by induction.

$$\begin{eqnarray*} b_3&=&a_3+b_4x_0=13+4(-3)=1 \\ b_2&=&a_2+b_3x_0=0+1(-3)=-3 \\... ...1+b_2x_0=-1+-3(-3)=8 \\ b_0&=& P(x_0)=a_0+b_1x_0=8+8(-3)=-16\\ \end{eqnarray*}$$

This gives us the following polynomial:

$$\begin{eqnarray*} P(x)&=&(x-x_0)Q(x)+b_0=(x+3)Q(x)-16 \\ Q(x)&=&b_nx^{n-1}+b_{n... ...b_3x^2+b_2x+b_1=4x^3+x^2-3x+8 \\ P(x)&=&(x+3)(4x^3+x^2-3x+8)-16 \end{eqnarray*}$$

$\Box$

Algorithm: Think of ``Synthetic Division'' table:

	Coeff of	Coeff	Coeff	Coeff	Coeff
	$x^4$	$x^3$	$x^2$	$x^1$	$x^0$
$x_0=-3$	$a_4=4$	$a_{3}=13$	$a_2=0$	$a_1=-1$	$a_0=8$
		$b_4x_0=-12$	$b_3x_0=-3$	$b_2x_0=9$	$b_1x_0=-24$
	$b_4=4$	$b_3=1$	$b_2=-3$	$b_1=8$	$b_0=-16$

An additional advantage of Horner's:

$$\begin{eqnarray*} \mbox {Since }P(x)=(x-x_0)Q(x)+b_0\\ \mbox {where } Q(x)=b_nx^{n-1}+b_{n-1}x^{n-2}\cdots b_2x+b_1 \end{eqnarray*}$$

differentiate

$$P'(x)=Q(x)+(x-x_0)Q'(x)$$

$\therefore$

Algorithm:

To find $P(x_0)$ and $p'(x_0)$:

$$\begin{array}{lll} \mbox {input:} & \mbox {degree }n; \mbox... ...x{Step 4} &\mbox {output } (y,z)\\ & \mbox {END.} \end{array}$$

$\Box$

Example Find an approximation to one of the zeros of

$$P(x)=4x^4+13x^3-x+8$$

using Newton-Raphson (see 5.3) procedure and synthetic division to evaluate $P(x_n), P'(x_n)$ for each iterate $x_n$. With $x_0=-3$ as initial guess, we obtained previously $P(-3)$ in previous example.

$$\begin{tabular}{c\vert ccccc} &$a_4$\ & $a_3$\ & $a_2$\ & $... ..._3=1$\ & $b_2=-3$\ & $b_1=8$\ & $b_0=16=P(-3)$\\ \end{tabular}$$

$$Q(x)=4x^3+x^2-3x+8\mbox { and } P'(-3)=Q(-3)$$

So $P'(-3)$ can be found by evaluating $Q(-3)$:

$$\begin{tabular}{c\vert cccc} $x_0=-3$\ & $4$\ & $1$\ & $-3$\... ...$b'_3=-11$\ & $b'_2=30$\ & $b'_1=-82=Q(-3)=P'(-3)$\end{tabular}$$

$$x_1=x_0-\frac{P(x_0)}{P'(x_0)}=-3-\frac{16}{-82}\approx -3.1951$$

Repeating procedure to find $x_2$:

$$\begin{tabular}{c\vert ccccc} $x_1=-3.1951$\ & $4$\ &$13$\ &... ...10$\ & $39.4326$\ & $-124.7513=Q(x_1)=P'(x_1)$\par\end{tabular}$$

So $P(-3.1951)\approx 4.0354, P'(-3.1951)\approx -124.7513$

$$x_2=-3.1951-\frac{4.0354}{-124.7513}\approx -3.1628$$

and keep going. The root is $-3.16171$ to 5 decimal places. $\Box$

Note that $Q$ depends on approximation and changes from iterate to iterate

If the $N^{th}$-iterate $x_n$, in the Newton-Raphson procedure is the $N^{th}$ approximation of $Q$ for $P$ then

$$\begin{eqnarray*} P(x)=(x-x_n)Q(x)+b_0=(x-x_n)Q(x)+P(x_n)\approx (x-x_n)Q(x)\\ \mbox {so } x-x_n \mbox { is an approximate factor of } P. \end{eqnarray*}$$

let $x_n=\widehat x$, be the approximate zero of $P$ and $Q_1$ the approx factor then

$$P(x)\approx (x-\widehat x_1)Q_1(x)$$

We can find a second approximate zero of $P$ by applying Newton-Raphson to $Q_1$. If $P$ is an $n^{th}$ degree polynomial with $n$ real zeros, repeating procedure will eventually load to $(n-z)$ approximate zeros of $P$ and an approximate quadratic factor $Q_{n-2}(x)$. $Q_{n-2}(x) =0$ can be solved using quadratic formula to find the remaining 2 roots.

THIS IS CALLED DEFLATION!

$$P(x)=(x-{\widehat x}_1)(x{-\widehat x}_2)\cdots (x-\widehat x_k)Q_k(x)$$

the difficulty is that Newton-Raphson applied repetitively compounds errors. The larger $k$, the more poorly $\widehat x_{k+1}$, which is a root of $Q_k(x)=0$, will approximate a root of $P(x)=0$. One way to eliminate these errors is to use the reduced equations to find $\widehat x_2, \widehat x_3, \cdots \widehat x_k$ approximate zeros of $P$ and then use these in a Newton Raphson procedure on $P(x)$ with these approximations as initial guesses.

Also we could exploit the sign of $P(x)$ in a neighborhood of $\widehat x_i$'s to define the $[a,b]$.

What can you do if roots are complex? The algorithm still makes sense with complex values, however, if you consider what the operations in the algorithm are, you will see that real initial guesses, with polynomials with real coefficients will never yield complex roots from Newton-Raphson. Also, there is the problem of manipulating complex floating point numbers on the computer. In MATLAB this is not a problem since it takes care of complex vs. real automatically. In Fortran or C$^++$ there is support for complex arithmetic. In C, you need to explicitly code up the complex arithmetic. In any case, you can express $P(x)=P_R(x)+iP_I(x)$ and roots $x=\alpha_{+}i\beta$ and solve this problem as a vector equation with 2 components. We'll address the problem of systems of nonlinear equations later. We will see below, that Muller's method will naturally lead to complex roots even starting from real initial data.