Horner's method

In mathematics and computer science, Horner's method is a smart way to work with special equations called polynomials. It helps computers and people solve these equations faster. The idea is named after William George Horner, but people used it long before him.

The method changes how we write a polynomial. Instead of doing each part separately, it puts the pieces inside each other. This makes the math easier and quicker. With this method, solving a polynomial takes only as many steps as the biggest number in the equation.

Besides helping with calculations, Horner's method also helps find answers to some kinds of equations. It was very useful before computers were common, and it is still a good example of clever problem-solving in math.

Polynomial evaluation and long division

Horner's method is a smart way to work out the value of polynomials. Polynomials are expressions made from numbers and variables, like ( a_0 + a_1x + a_2x^2 + a_3x^3 + \ldots + a_nx^n ).

This method rewrites the polynomial in a nested form: ( a_0 + x(a_1 + x(a_2 + x(a_3 + \ldots + x(a_n)\ldots))) ). You start from the inside and work out, which makes the calculation quicker and easier. Computers like this method because it uses fewer steps.

Horner's method can also help when dividing polynomials. If you divide a polynomial by ( x - x_0 ), the leftover part (remainder) is just the value of the polynomial when ( x = x_0 ). If this remainder is zero, it shows that ( x - x_0 ) is a part (factor) of the polynomial. This connects to a rule called the polynomial remainder theorem.

b n := a n b n − 1 := a n − 1 + b n x 0 ⋮ b 1 := a 1 + b 2 x 0 b 0 := a 0 + b 1 x 0 . {\displaystyle {\begin{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\&~~~\vdots \\b_{1}&:=a_{1}+b_{2}x_{0}\\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}}

p ( x ) = ( b 1 + b 2 x + b 3 x 2 + b 4 x 3 + ⋯ + b n − 1 x n − 2 + b n x n − 1 ) ( x − x 0 ) + b 0 {\displaystyle p(x)=\left(b_{1}+b_{2}x+b_{3}x^{2}+b_{4}x^{3}+\cdots +b_{n-1}x^{n-2}+b_{n}x^{n-1}\right)\left(x-x_{0}\right)+b_{0}}

Polynomial root finding

We can use a special math trick to guess where a polynomial equation might equal zero. This helps us find the answers, or "roots," of the equation.

For example, take this polynomial: (p_6(x) = (x + 8)(x + 5)(x + 3)(x - 2)(x - 3)(x - 7)). We know one of the roots is 7, so we start by guessing close to this number. Using a method called Newton's method, we find the exact root at 7. Then, we divide the polynomial by ((x - 7)) to get a new, simpler polynomial. We repeat this process, finding more roots step by step.

Divided difference of a polynomial

Horner's method can help find a special value called the divided difference for polynomials. This makes calculations more accurate, especially when the two points being compared are very close.

It can also help find the derivative of a polynomial, showing how the polynomial changes at a certain point. This is useful for solving equations using a method called Newton's method.

History

Qin Jiushao's algorithm for solving the quadratic polynomial equation − x 4 + 763200 x 2 − 40642560000 = 0 {\displaystyle -x^{4}+763200x^{2}-40642560000=0} result: x=840

Horner's method is a way to solve equations with many parts. It was first shared by William George Horner in 1819. But people used this method long before that! In China, Qin Jiushao and Jia Xian used it in the 1200s and 1100s. Even earlier, a Persian mathematician named Sharaf al-Dīn al-Ṭūsī used it in the 1100s.

The method was also known to Isaac Newton in the 1600s and Paolo Ruffini in 1809. Horner helped make it easier for everyone to understand and use, but he wasn’t the first to discover it.

Horner's method

Horner's method

Polynomial evaluation and long division

Polynomial root finding

Divided difference of a polynomial

History

Related articles