Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Horner's method
Summary
In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Horner himself, and can be traced back many hundreds of years to Chinese and Persian mathematicians. After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials.
The algorithm is based on Horner's rule, in which a polynomial is written in nested form:
This allows the evaluation of a polynomial of degree n with only multiplications and additions. This is optimal, since there are polynomials of degree n that cannot be evaluated with fewer arithmetic operations.
Alternatively, Horner's method also refers to a method for approximating the roots of polynomials, described by Horner in 1819. It is a variant of the Newton–Raphson method made more efficient for hand calculation by the application of Horner's rule. It was widely used until computers came into general use around 1970.
Given the polynomial
where are constant coefficients, the problem is to evaluate the polynomial at a specific value of
For this, a new sequence of constants is defined recursively as follows:
Then is the value of .
To see why this works, the polynomial can be written in the form
Thus, by iteratively substituting the into the expression,
Now, it can be proven that;
This expression constitutes Horner's practical application, as it offers a very quick way of determining the outcome of;
with (which is equal to ) being the division's remainder, as is demonstrated by the examples below. If is a root of , then (meaning the remainder is ), which means you can factor as .
To finding the consecutive -values, you start with determining , which is simply equal to . Then you then work recursively using the formula;
till you arrive at .
Evaluate for .
We use synthetic division as follows:
│
3 │ 2 −6 2 −1
│ 6 0 6
└────────────────────────
2 0 2 5
The entries in the third row are the sum of those in the first two.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.