EPFL Logo
fr|en
Login
Concept

Horner's method

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.
Related courses (2)
MATH-251(c): Numerical analysis
Le cours présente des méthodes numériques pour la résolution de problèmes mathématiques comme des systèmes d'équations linéaires ou non linéaires, approximation de fonctions, intégration et dérivation
MATH-251(a): Numerical analysis
This course presents numerical methods for the solution of mathematical problems such as systems of linear and non-linear equations, functions approximation, integration and differentiation, and diffe
Related lectures (8)
Characteristic Polynomials and Solutions
Covers characteristic polynomials, roots, and associated solutions for differential equations.
Complexity of Algorithms: Examples + Q&A
Explores examples of algorithm complexity, sorting, and polynomial computations.
Taylor Series: Revision Session
Covers a revision session on Taylor series and limits, including exercises on developing limited orders and calculating global extrema.
Show more
Related publications (18)
Show more
Related people (1)
Related concepts (9)
Polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2 − yz + 1. Polynomials appear in many areas of mathematics and science.
Polynomial evaluation
In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values. In other words, evaluating the polynomial at consists of computing See also For evaluating the univariate polynomial the most naive method would use multiplications to compute , use multiplications to compute and so on for a total of multiplications and additions. Using better methods, such as Horner's rule, this can be reduced to multiplications and additions.
Polynomial long division
In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, because it separates an otherwise complex division problem into smaller ones. Sometimes using a shorthand version called synthetic division is faster, with less writing and fewer calculations. Another abbreviated method is polynomial short division (Blomqvist's method).
Show more

Copyright © 2025 EPFL, all rights reserved

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.