My idea is like this: since Horner's synthetic division method gives you the remainder you get on dividing a polynomial $p(x)$ by $(x – a)$( of course, I know that it will be $p(a)$), can we use the remainder to tune the divisor and thus obtain the other zeroes (at least one of them) of that polynomial ?
Here's the algorithm I suggested:
- Take the initial divisor as $\frac{-b}{na}$($n$ = degree of the polynomial)
- Using Horner's method, find the remainder obtained on dividing the polynomial by $(x – \frac{-b}{na})$
- Taking the remainder you get as the error in the divisor, subtract the error from the divisor (which is $\frac{-b}{na}$) and take the result as the new divisor.
- Loop through steps 1 to 3 till the remainder obtained becomes $0$.
NB:The initial divisor we take in the whole loop (till the remainder is $0$) will be the arithmetic mean of the roots.
Edit – 1: I have decided to add the degree of the polynomial plus one to the error we take in every iteration. That seemed to work , but later seemed to be of no use. But still I would like to know if I have made an error anywhere.
Best Answer
What you are suggesting is an iterative refinement algorithm for finding the root of a polynomial. The concept is that we find the remainder, or simply the value of $p(a)$, and then wish to adjust $a$ so that the result is closer to the true root.
First, I will point out that knowing the value of $p(a)$ is insufficient, since it does not given any information concerning which direction or by how much you should adjust the estimate of your root. There are several techniques for deducing this, the simplest of the two being:
Newton's method (requires calculus): Compute the derivative (slope) of $p$ at $a$, notated $p'(a)$. The resulting formula for the next estimate is given by $a-[p(a)/p'(a)]$.
Secant method (no calculus): Add another point $(b,p(b))$ and estimate the derivative using the slope between this point and $(a,p(a))$. The formula is the same as Newton's method except $[p(b)-p(a)]/(b-a)$ is used instead of $p'(a)$.
Intuitively you can understand your method as the case of approximating $p'(a)$ by $1$, so how well it works near the root depends on how well it estimates the real derivative. For example, if the slope is negative at the root your method actually goes in the opposite direction of the root. In fact a sufficient condition for convergence with your method is $0<p'(a)<2$ at the root.
Additional remark: It should not be expected the aforementioned methods above will converge from everywhere, even if there exists a real root. To guarantee convergence you either have to start close to the root (sometimes very close) or use a bracketing method, such as bisection.