Can someone explain Newton's method to me?

Question

I was wondering whether anyone can explain in a simple manner the math I'm being asked to do below.

PROBLEM STATEMENT:
We require a program that will show the way that Newton’s Method is dependent on the initial guess chosen.
The functions will always be polynomials, up to degree 4 with lower degree polynomials simply having their leading coefficients set to 0.
A degree 4 polynomial F(x) = a.x4 + b.x3 + c.x2 + d.x + e is defined by the 5 coefficients for the powers of x. F’(x) is therefore 4.a.x3 + 3.b.x2 + 2.c.x + d.

TASKS:
Your program should have the following steps:
3.The first thing you should do is to test whether the initial guess has stumbled on a root of the polynomial (so Newton’s Method is not needed).
4.Run Newton’s method until either a root is found, or one of the following error conditions is discovered. Errors that will cause the method not to converge are:
a.Division by zero: F'(x)= 0, or
b.Overshooting or Divergence: If F'(x) ≈ 0, then |xi+1| → ∞. This will affect convergence.
c.Cycling: xi+1 oscillates between two regions of the graph, never converging to a root.
d.Cases (a) and (b) are best discovered by testing whether F'(x) is “close to zero” – in our case this should be within 0.000005 of 0. Case (c) is assumed to have occurred when 50 iterations have been attempted.

Answer 1

Newton's method is a method to find the roots of a given function. In this case you have the function $F$, a polynomial. So what you are asked to do is numerically find the value of $x$ for which: $$F(x)=0.$$ The method of Newton starts by choosing an initial guess, say $x=x_0$. If you're lucky you immediately have $F(x_0)=0$, in which case you're done, but let's assume $F(x_0)=F_0\neq0$. The next step is computing the slope of the tangent line at $(x_0,F_0)$ and calculating where it intersects with the horizontal axis. This point, $x_1$, will be your next approximation for the root. Since your function value is $F_0$ and your slope is $F^\prime(x_0)=F^\prime_0$ this new approximation is $F_0/F^\prime_0$ away from $x_0$, i.e.: $$x_1 = x_0 - \frac{F_0}{F^\prime_0}.$$ This proces is repeated until the root is found, or when $F_n$ is small enough ($F_n<\varepsilon$). Unfortunately this method doesn't always converge, but this is demonstrated in your assignment.

Answer 2

Because you say you don't know how to find the derivative of the 4th order polynomial, I'll show you how to come up with it. The rest of Newton's method is covered in SPK's answer. Consider the function $f(x)=kx^n$. This is an $n$^th order polynomial. The derivative (per it's definition) yields $$f'(x)=\lim_{h\to 0}\frac{f(x+h)-f(x)}{h}=\lim_{h\to 0}\frac{c(x+h)^n-cx^n}{h}$$ We can expand this using binomial theorem, which states that $$(a+b)^n=a^n+c_1a^{n-1}b+c_2a^{n-2}b^2+\cdots+c_{n-2}a^2b^{n-2}+c_{n-1}ab^{n-1}+b^n$$ where the $c_i$ are constants determined by the combination $\binom{n}{i}$. The value of them is not important for reasons that will become apparent in a second. Going back to our derivative $$f'(x)=\lim_{h\to 0}k\frac{x^n+c_1x^{n-1}h+c_2x^{n-2}h^2+\cdots+c_{n-2}x^2h^{n-2}+c_{n-1}xh^{n-1}+h^n-x^n}{h}$$ We can cross out the $x^n-x^n$ term on the top and cancel the $h$ on the bottom with the $h$ in each remaining term on top to get $$f'(x)=\lim_{h\to 0}k(c_1x^{n-1}+c_2x^{n-2}h+\cdots+c_{n-2}x^2h^{n-3}+c_{n-1}xh^{n-2}+h^{n-1})$$ Now note that each term except the first has an $h$ in it, which means when we take the limit as we go to $0$ these terms will disappear. $$f'(x)=kc_1x^{n-1}$$ Where $c_1=\binom{n}{1}=n$. And we have $$f'(x)=knx^{n-1}$$ So, we drop down the exponent (the $n$ out front), keep our coefficient, and decrease the degree of the exponent. One thing that we know about derivatives is that the derivative of the sum is the sum of the derivative. So $$\frac{\mathrm d}{\mathrm dx}(f(x)+g(x))=\frac{\mathrm d}{\mathrm dx}f(x)+\frac{\mathrm d}{\mathrm dx}g(x)$$ So if we string two polynomial terms together we get $$\frac{\mathrm d}{\mathrm dx}(ax^n+bx^{n-1})=\frac{\mathrm d}{\mathrm dx}(ax^n)+\frac{\mathrm d}{\mathrm dx}(bx^{n-1})$$ And we just showed how to get each of these individually. Putting these two together yields $$\frac{\mathrm d}{\mathrm dx}(ax^n+bx^{n-1})=anx^{n-1}+b(n-1)x^{n-2}$$ And we can put as many terms we want in addition and take our derivative the same way.

---

So, let's consider a general 4th order polynomial

$$P(x)=ax^4+bx^3+cx^2+dx+e=ax^4+bx^3+cx^2+dx^1+e$$

We show the derivative is

$$P'(x)=4ax^{4-1}+3bx^{3-1}+2cx^{2-1}+1dx^{1-1}+0$$

For the last term we just remember that the derivative of a constant is 0. Ultimately the derivative is $$P'(x)=4ax^3+3bx^2+2cx+d$$

---

So for Newtons method:

$$x_{n+1}=x_{n}-\frac{P(x_n)}{P'(x_n)}=x_{n}-\frac{ax_n^4+bx_n^3+cx_n^2+dx_n+e}{4ax_n^3+3bx_n^2+2cx_n+d}$$

I hope this helps!

---

And to explain steps 3 and 4:

Step 3 is basically just asking you to find $P(x_0)$ the evaluation of the polynomial at the initial guess and see if $P(x_0)=0$ Because if you guessed the $x$ value that is already a root, there is no point in using any method to find a root because you've already found it!

Step 4 is saying to use the formula we derived above over and over until you hit a particular error. The errors that you might hit are

a. $P'(x_n)=0$. That is the denominator of the right most fraction in our equation which would cause us to divide by zero. This is the same thing as drawing a horizontal line and trying to find the intersection between it and the x-axis. It won't happen. So we stop at that point and say that initial guess failed.

b. $P'(x_n)\approx0$. This means that we're going to jump to a REALLY large $x_{n+1}$ value. When you take a number and divide by a really small number, it gets much bigger. So we want to avoid this as well. Call this initial guess a failure and move on. The instructions say $\left|P'(x_n)\right|<0.000005$ is too small. This actually catches the error in (a.) as well.

c. The cycling is when you get stuck in a loop. Basically, if $x_{n+1}=x_k$ for any $k<n+1$. So if you get to an $x$ value you've already tried, you'll keep going in that same loop. Call it quits here, too. However, it appears that you aren't to keep track of all of the $x$ values you hit. You can just assume that if you run it more than $50$ times, that it got stuck in a loop somewhere.

---

One final note. There were end error conditions from step 4. But if at any point your value for $P(x_n)$ becomes within a tolerance of $0$, you should call it quits, too. But not in error, in success. Because that means that you're at or really close to a zero and you've found one! The process worked.

Answer 3

I can try to explain Newton's Method, but you say in the comments that you don't know what the derivative of a degree four polynomial is. That might be make things hard. In any case let's try. If the given (degree four) polynomial is

$$ F(x) = ax^4 + bx^3 + cx^2 + dx + e,$$

then its derivative is $$ F'(x) = 4ax^3 + 3bx^2 + 2cx + d.$$

So far so good.

Newton's Method is a way to approximate a solution for the equation $F(x)=0$. It's done by first making a guess, then iterating a particular procedure that takes as input your guess, and outputs another guess that's perhaps closer to the actual solution. If you do it enough times, you might approximate the solution very well. Your assignment is try this process with various guesses and test how well the method works.

Here's the geometric idea behind Newton's method. Suppose your guess, i.e. the initial value for the process, is $x_0$. Then probably $F(x_0)$ is not zero (if it were, you'd be done). Geometrically, this means that if you draw the graph of $F(x)=y$, then the point $(x_0,F(x_0))$ is not on the $x$-axis. Now Newton's method is to draw the tangent line to the curve $F(x)=y$ at the point $(x_0,F(x_0))$ and see where it intersects the $x$-axis. That value of $x$ is the 'next' guess, i.e. $x_1$. Then you do the process again for $x_1$ instead of $x_0$ and you get $x_2$, and so on. The idea is that unless something goes wrong these numbers will converge to a solution. Here's a picture I found by google imaging 'Newton's method'.

You can see how $x_0$, $x_1$ and $x_2$ are creeping closer to the point where the graph intersects the $x$-axis.

Alright so what's the formula for this process? If $y_0 = F(x_0)$, the line tangent to the curve at $F(x)=y$ at $(x_0,y_0)$ will have slope $F'(x_0)$, almost by definition of what the derivative is. So the equation of the tangent line is:

$$\frac{Y-y_0}{X-x_0} = F'(x_0).$$

Now we are looking for where this line crosses the $x$-axis, i.e. the point $(x_1,0)$, so we solve

$$\frac{-y_0}{x_1-x_0} = F'(x_0) \Longrightarrow x_1 - x_0 = \frac{-y_0}{F'(x_0)}$$

$$ \Longrightarrow x_1 = x_0 - \frac{y_0}{F'(x_0)},$$

so that $$x_1= x_0 - \frac{F(x_0)}{F'(x_0)}.$$

This is the iteration formula we want. In general we will have:

$$x_{i+1} = x_i - \frac{F(x_i)}{F'(x_i)}.$$

So in principle one does this over and over until the answers start to get closer and closer, i.e. until $\left|x_{i+1} - x_i\right| = \left|\frac{F(x_i)}{F'(x_i)}\right|$ starts to become very small, in which case we have an approximation for the root of $F(x)=0$.

In reality a couple of things could go wrong. One is that you might hit on a value of $x_i$ that makes $F'(x_i)$ zero. Then the iteration formula is dividing by zero, and so it fails. Geometrically this translates to when the tangent line at $(x_i,F(x_i))$ is flat, so it never hits the $x$-axis. If this happens, one needs to start over with a new value of $x_0$. In your assignment you're asked to just record this fact and move on. Note that in practice since everything is an approximation, e.g. for you when you write the program, $F(x_i)=0$ means $F(x_i)$ is very very close to zero (how close is enough is described for you in the statement of the problem.)

There's another way things could go wrong and that's if the values $x_1,x_2,x_3,...$ don't converge to some fixed value at all. They could for example oscillate back and forth between $-1$ and $1$ and keep going that way. In this case you'd also have to stop and try another initial value guess. In your problem it says do this after 50 iterations doesn't give you an approximation.

That's about it. I hope it's helpful.