Definition:Ruffini-Horner Method

From ProofWiki
Jump to navigation Jump to search

Definition

The Ruffini-Horner method is a technique for finding the roots of polynomial equations in $1$ real variable.

Let $E_0$ be the polynomial equation in $x$:

$\map p x = 0$

Suppose that a root $x_0$ being sought is the positive real number expressed as the decimal expansion:

$x_0 = \sqbrk {abc.def}$

The process begins by finding $a$ by inspection.

We then form a new equation $E_1$ whose roots are $100 a$ less than those of $E_0$.

This will have a root $x_1$ in the form:

$x_1 = \sqbrk {bc.def}$

Similarly, $b$ is found by inspection.

We then form a new equation $E_2$ whose roots are $10 b$ less than those of $E_1$.

The process continues for as many digits accuracy as required.


Also known as

The Ruffini-Horner method is also known just as Horner's method.

However, that name is also given to Horner's rule, so to avoid ambiguity and misunderstanding it is deprecated on $\mathsf{Pr} \infty \mathsf{fWiki}$.


Examples

Arbitrary Example

Consider the polynomial equation:

$\map f x = x^2 - x - 1 = 0$

We have that:

\(\ds \map f 1\) \(=\) \(\ds -1\)
\(\ds \map f 2\) \(=\) \(\ds 1\)

so we observe there is a root between $x = 1$ and $x = 2$.

Then:

\(\ds \map {f_1} x\) \(=\) \(\ds \map f {x - 1}\)
\(\ds \) \(=\) \(\ds \paren {x - 1}^2 - \paren {x - 1} - 1\)
\(\ds \) \(=\) \(\ds x^2 - 3 x + 1\)

We then identify a root between $x = 0.6$ and $x = 0.7$.

This leads to calculating:

$\map {f_2} x = \map {f_1} {x - 0.6}$

Hence and so, until the required accuracy is achieved.


Also see

  • Results about the Ruffini-Horner method can be found here.


Source of Name

This entry was named for Paolo Ruffini and William George Horner.


Historical Note

The Ruffini-Horner method was given by Paolo Ruffini in $1804$.

It was later given independently in $1819$ by William George Horner.

However, a similar iterative method had previously been devised by Qin Jiushao in the $13$th century.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Ruffini-Horner_Method&oldid=687139"