Horner's method

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

The method changes the way we write a polynomial. Instead of calculating each part separately, it nests the pieces inside each other. This makes the math easier and quicker. With this method, solving a polynomial of any size needs only as many steps as the highest number in the equation, making it very efficient.

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

Polynomial evaluation and long division

Horner's method is a clever way to evaluate polynomials, which are expressions made up of numbers and variables. Imagine you have a polynomial like ( a_0 + a_1x + a_2x^2 + a_3x^3 + \ldots + a_nx^n ). To find out what this equals when ( x ) is a specific number, Horner's method makes the job easier and faster.

The method works by rewriting the polynomial in a nested form: ( a_0 + x(a_1 + x(a_2 + x(a_3 + \ldots + x(a_n)\ldots))) ). By calculating from the inside out, you can find the result with fewer steps than usual. This approach is especially handy for computers, as it reduces the number of operations needed.

Horner's method is also useful for dividing polynomials. When you divide a polynomial by ( x - x_0 ), the remainder is simply the value of the polynomial when ( x = x_0 ). If this remainder is zero, it means ( x - x_0 ) is a factor of the polynomial. This ties into a rule called the polynomial remainder theorem, which helps in understanding the roots of polynomials.

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 along with another method 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)). By expanding it, we get (p_6(x) = x^6 + 4x^5 - 72x^4 - 214x^3 + 1127x^2 + 1602x - 5040). 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 until all the answers are discovered.

Divided difference of a polynomial

Horner's method can also help find a special value called the divided difference for polynomials. This is useful because it makes calculations more accurate, especially when the two points we are comparing are very close together.

When we want to find the derivative of a polynomial, which tells us how the polynomial is changing at a certain point, Horner's method can help with that too. This is important 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, and it was first shared by William George Horner in 1819. But this method was used long before that! People in China, like 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.

Polynomial evaluation and long division

Polynomial root finding

Divided difference of a polynomial

History

Related articles