Newton's method

Hi, in the last video we introduced the Newton’s Method, pointing out that it is used to calculate the zeros of complex functions, explaining how it works in a graphic, and deducing its general formula. However, there were some important questions left to solve, for example, how many iterations were needed to obtain a good result or which X0 value we should choose. But before continuing with these questions we will solve the questions we made at the end of section 1.

What does the Newton’s Method consist of? It is an iterative numerical method that approximates the roots of complex functions by the lineation of these functions near points at the root.

Draw a complex function that cuts the X axis at approximately x=1, and taking x0=3 iterate the Newton’s Method graphically three times. Is X3 closer to X* than to X0?

This is an example in which we can see that, as we iterate the method, the root is better approximated every time.

Calculate three iteration of the Newton’s Method (numerically) of the function f(x)=x^3+x+1 taking x0=-0,5.

In this case, the numerical application would be the following:

X1 = 2 – f(2)/f`(2) = 2,1000000

X2 = 2,1 – f(2,1)/f’(2,1) = 2,0945691211

X3 = 2,094551482

What do you think that would happen if f’(x)=0 in any x? It is as if there was a stationary point in the range near the root. As you can see in the general formula, the derivative is found in the denominator, and therefore if it was equal to 0, the Xk that were being calculated would not exist and therefore the Newton’s Method would stop working. This will be another situation to take into account when defining the Convergence Condition of the Method.

Before getting into detail to explain the Convergence Condition, we will see the Stop Criteria of the Method. In other words, we can define how many times we will have to iterate the general formula deduced from the prior video. We have already seen that if we do it manually we will stop iterating when we see that the Xk has the desired accuracy, for instance based on the decimals that vary between xk and Xk-1. However, the Newton’s Method is usually programmed on the computer, and, therefore, a way to limit the recurrence of the method is needed.

To do so, firstly, we have to understand what the Relative Error and the Absolute Error are.

Definition: the absolute error and the relative error between two Xk-1 successive iterations and xk are, respectively:

ek = |xk-Xk-1| and Ek = ek/|xk| = | (xk-xk-1)/xk| For some of the iterations, Ek0 is a prefixed tolerance by the user. An alternative to this criterion would be ek

For some of the iterations, |f(Xk)|

If, we are basically looking for a zero of f, we can stop the calculus when f(Xk) is close enough to 0. Having arrived to K = Kmax, where Kmax is a maximum number of iterations prefixed by the user. This criterion is used almost always at the beginning if, in a specific case, the recurrence did not converge to any solution and therefore the algorithm entered an infinite loop. However, a number of prefixed iterations can be set systematically, without having to check any other criterion for each of the iterations.

Let’s now see the part where the Newton’s Method gives you more headaches. Like choosing a suitable X0 and which conditions must be adhered for the Newton’s Method to converge in the search interval [a, b].

First of all you have to understand that the search interval [a, b] corresponds to all the possible values of x that the Xk can have. As we have seen until now, as the iterations increase, if the Method works correctly, Xk will get closer to X*, and therefore X0 could be one of the extremes of this interval. Review the previous graphics if you do not understand this part since it is quite important.

On the other hand, it is important to take into account that if in the search interval [a, b] there has to be a zero, this means that if f(a)>0 then f(b)<0 or the other way round if f(a) is negative, f(b) will have to be positive. Graphically, for there to be a point where the function crosses the X axis, there must be a point on the function above the X axis on a side, and a point of the function below on the other side. Think about it! In reality, this idea that can seem trivial, but sometimes we forget to take into account, is precisely (what) the Bolzano’s theorem.

F:[a,b] ? R continuous if f(a)*f(b) < 0. Then, f has a zero on (a,b), in other words, x0 E (a,b) exists if f(x0)=0.

And this is what we will apply at the beginning of any application of the Newton’s Method to define the search interval [a,b] where X* is.

If we go back to the function that you had as “homework” from the previous video, I asked you to take X0=2, but why? The function was f(x)= x^3-2x-5. If I had not given you X0, you would have had to choose one yourselves, and if we apply Bolzano’s theorem we see that:

f(0)<0, f(1)<0, f(2)<0, and f(3)>0 since between x=2 and x=3 there is a change of the function sign, we can say that [2,3] will be our searching interval. It makes sense to take X0=2, but we could also have taken any other value between 2 and 3.

Now let’s suppose we want to approximate a zero of f(x)=6x^3 -2x^2 – 2x-1. The first thing we do is to look for the search interval applying Bolzano’s theorem, like we have done before.

f(0)<0, and f(1)>1 therefore we could say that X* E [0,1]. In this case if we take X0=0,5 (remember that if the interval is well defined, x0 can be any value in this interval) and calculate X1

X1= 0,5 – f(0,5)/f’(0,5) = 4 In this case, X1 is out of the search interval and therefore it means something is wrong. Indeed, f(4)= 343, and it is really far from 0. This example shows that applying only Bolzano’s Theorem the search interval we define might not be small enough to guarantee that the Newton’s Method converges in all of it. For this to be true the following must be fulfilled:

Being [a,b] a search interval of x* (typically an interval for which f(a)*f(b)<0) and f:[a,b] ? R a derivable function twice if f’(x)!= 0 for everything x E [a,b]. If

|x*-x0| < 2/max |f’’(x)/f’x)| llavors lim k->inf Xk = x*

This formula can be deduced by the Lagrange remainder, but since this (course) has not been explained in class, those who are interested can find where it comes from on the noted posted on Moodle.

Let’s see how we will apply this formula from the previous example that had caused us problems. Firstly we will look if there is any point in [0,1] that makes f’(x)=0.

F’(x)=18x^2- 4x-2 =0 if we solve the second degree equation, thus we will have f’(0,46) = 0, therefore we have to define a new search interval that does not include this point.

Remember that f(1)=1 and f(0)=-1, if we make x=0,5 we have f(0,5)=-1,75 <0, therefore our new interval could be [0,5 , 1]. If we apply the formula of the Convergence Condition, we have |X*-x0| < 2/f’’(1)/f’(0,5) Sine f’ and f’’ are increasing monotonically, the value that maximizes the second derivative is the superior extreme of the interval, and the value that minimizes the first derivative is the inferior extreme of the interval. Therefore f’(x)= 18x^2-4x-2 and f’(0,5)= 0,5 and f’’(x)= 36x-4 and f’’(1)=32 To guarantee the convergence of the method we need the interval |x*-x0|< 0,03125. Since our interval is [0,5 , 1] we can easily see that the condition is not adhered, and therefore if we took x0=0,5 we could have values out of the interval again. This could be due to 0,5 being too close to x=0,46, where the derivative is void.

Let’s try to adjust the interval better. If we take x=0,75, f(0,75) = -1,09 <0 it is still smaller than zero and therefore a possible interval would be [0,75, 1]. In this case if you apply the Convergence Condition you will see that it is fulfilled.

Summarizing this video, we have seen the three most relevant stop criteria, and we have analyzed how to choose the value of x0 suitably applying the Bolzano’s Theorem and the formula of the Convergence Condition. In the next video we will see the three applications of the Newton’s Method that we are sure will be interesting and surprising.

Before playing the last of the three videos we have prepared, we ask you to do the following exercises:

1. Make the calculus that proves [0,75,1] is a search interval that guarantees the convergence of the Newton’s Method for the function f(x)= 6x^3-2x^2-2x-1 and choose the possible values for X0.

2. Find a search interval that guarantees the convergence of the Newton’s Method for the function f(x)=x^3-2x-5

3. Number the three stop criteria we have explained and explain them in your own words.

4. We want the Newton’s Method to solve the square root of a number (which is not trivial). How would you set out the general equation? And in case this number was pi, would you know how to choose a suitable x0?