Horner's method confusion

  • B
  • Thread starter John3509
  • Start date
  • #1
48
3

Main Question or Discussion Point

So I was trying to understand Horner's method. I understand that you can take a polynomial and factor out the x's and re write it as multiple linear functions recursively plugged into each other and that this makes evaluating a polynomial easier because you just evaluate a linear function multiple times. But
I was reading the Wikipedia page and I do not understand:
-What does this have to do with synthetic division? I know what synthetic division is, I just don't see the conection.
-What does this that to do with Newtons method for calculating the root of a function? I know that newtons method also involves recursive evaluation where the previous result is the new input. Newtons method comes from the linearization, but besides that similarity, I also do not see the connection here.
-After the words Now, it can be proven that; under the Description of the algorithm section, I do not understand where it gets that equation from? If b_0 is p(x_0) then if you rearrange the terms you have slope equals that polynomial of b's , which I don't understand why they would set that equal to the slope?
-And why replace the coefficient a with b ?
Also I was watching this video on Horner's method. At 2:47 , the last bullet point, the representation as a piece wise defined function I do not understand.
And finally, I don't get why I don't get this, its all just elementary operations!
 

Answers and Replies

  • #2
Delta2
Homework Helper
Insights Author
Gold Member
2,423
683
Sorry if I am not much of help here as my current background on Horner's method is vague and blurry , however I want to answer your very last question.
When you encounter something totally new, whether it is elementary or not (horner's method is not so elementary allow me to say), it is absolutely natural to have questions and be puzzled about certain things.
Don't be afraid to ask your teacher, ask your fellow students or ask here at physics forums for everything that puzzles you or confuses you, cause that's the way to go and learn new things!
 
  • #3
mathman
Science Advisor
7,743
409
The point of synthetic division for polynomials is that each division by a linear factor defined by a root of the polynomial results in a polynomial one degree lower, which may be easier to solve. This is especially useful when you know one root of a cubic. The division results in a quadratic - easily solved to get the other two roots of the cubic.
 
  • #4
Stephen Tashi
Science Advisor
6,930
1,187
-What does this that to do with Newtons method for calculating the root of a function?
The section "Polynomial root finding" in https://en.wikipedia.org/wiki/Horner's_method says Horner's method is relevant to finding additional zeroes of the polynomial after you have used Newton's method to find a zero. That process involves considering the zeros of a new polynomial formed by dividing the original polynomial by ##(x-x_0)## where ##x_0## is the root found by Newton's method. From that point of view, Horner's method isn't directly related to Newton's method.

And finally, I don't get why I don't get this, its all just elementary operations!
The problem with results based on detailed algebraic manipulations is that if you learn one such thing, it is an isolated fact. A person with an excellent memory for such facts can do amazing things. I, myself, can't stomach that approach. I want a general pattern. For example, some people approach the problem of finding the closed form expression for ##\sum_{i=1}^k x^n## as a different problem for ##n = 1,2,...##. The only way I can bear to think of getting the answer is as an application of the Calculus of Finite Differences.

-After the words Now, it can be proven that; under the Description of the algorithm section, I do not understand where it gets that equation from?
If I can figure out a good general way to think about that result, I'll tell you.
 
  • #5
pbuk
Science Advisor
Gold Member
1,240
267
Probably worth mentioning that in the age of digital computing, Horner's method is no longer relevant because it does not offer any material improvement in computing time and is almost always a lot less accurate than other methods. There is a note to that effect in the Wikipedia talk page under "More numerical efficiency" which I see was added in 2007 - it is about time this point made its way into the main entry, I'll do it sometime.
 
  • #6
48
3
The point of synthetic division for polynomials is that each division by a linear factor defined by a root of the polynomial results in a polynomial one degree lower, which may be easier to solve. This is especially useful when you know one root of a cubic. The division results in a quadratic - easily solved to get the other two roots of the cubic.
I know what synthetic division is and what its point is, its an algorithm that allows you to do polynomial division in a more compact way, by not having to write the variable and its powers. Its how it relates to Horner's method, the reformatting a polynomial into a recursive nest of linier terms, that confused me.
 
  • #7
48
3
The section "Polynomial root finding" in https://en.wikipedia.org/wiki/Horner's_method says Horner's method is relevant to finding additional zeroes of the polynomial after you have used Newton's method to find a zero. That process involves considering the zeros of a new polynomial formed by dividing the original polynomial by ##(x-x_0)## where ##x_0## is the root found by Newton's method. From that point of view, Horner's method isn't directly related to Newton's method.


But that's just the
polynomial remainder theorem
, which involves polynomial division, horners method just reformats a polynomial into a nest of linear terms. In that section it says "
Using Horner's method, divide out ( x − z 1 ) {\displaystyle (x-z_{1})}
(x-z_{1})
to obtain
p n − 1 {\displaystyle p_{n-1}}
p_{n-1}
.
It makes it sound as if horners method is some kind of method for diving polynomials?​


If I can figure out a good general way to think about that result, I'll tell you.
But do you even understand what it means or why its there? To me it looks like (strangely written slope) = (polynomial)
 
  • #8
Stephen Tashi
Science Advisor
6,930
1,187
But do you even understand what it means or why its there? To me it looks like (strangely written slope) = (polynomial)
In the case that ##x_0## is a root of the equation ##P(x) = 0##, we have ##b_0 = 0## and the "reduced" equation is given by ## q(x) = b_1 + b_2 x + ... b_nx^{n-1} ## So, yes, I understand the application of computing of computing the ##b_i## when ##x_0## is known to be a root. (No thanks to the Wikipedia article, which isn't clearly written.)
 

Related Threads for: Horner's method confusion

  • Last Post
Replies
4
Views
15K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
13
Views
970
  • Last Post
Replies
2
Views
544
  • Last Post
Replies
3
Views
745
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
8
Views
2K
Top