Newton's method

We are offering this class in video format so you can watch it as many times as necessary to understand all the concepts. We hope it is useful for you.

In the first section we will make a brief introduction on this numerical method: what is it used for? Which mathematical knowledges is it based on? We will also explain how it works graphically. The second section will present the Stop Criteria of this iterative method, as well as the conditions for convergence needed for it to work correctly.

Finally in the last section we will see possible examples on the application of the Newton Method, calculus of square roots, calculus of inverses and the solution of transcendental equations, that is those equations that cannot be solved algebraically.

As you can see, the class is addressed to Engineering students from ESUP that are currently taking Calculus, but we would like this to be useful for more people.

Even though it is not compulsory and, therefore, it will have no effects on the evaluation of the class, at the end of each section we have prepared some brief exercises with the aim of testing whether you have understood the concepts well.

As always, you can send us an email to set an appointment to solve any doubts you might still have. The main aim of the Newton Method is to FIND THE ZEROS OR ROOTS OF A FUNCTION, and a zero or a root of a function is defined f: D C R -> R as a point x0 E D if f(x0) = 0.

In other words, the points of the function are voided. Even if you are not aware, you might have had to calculate the roots of a function many times, some examples are: to simplify fractions, to know where a specific function cuts the X axis, that is when it goes from having positive values to having negative values or vice versa, or to find its stationary point.

Specifically, equaling the derivative of a function to zero allows you to find the stationary points but also, as you know, some of these can be maximums or minimums of the function, and, therefore, for optimization problems (where you try to maximize or minimize a variable dependent on another one) it is essential to know how to calculate the roots or zeros of the functions.

It is easy for you to think about other cases where this is applied too, as in economics, biology or even sports.

It is also true that you already know how to find zeros or roots of some simple functions, like lines and second degree equations by algebraic tools. But how do you think more complex functions are solved, how would a seventh degree equation or the equation sin(x) = log(x)? To solve complex functions there are numerical methods that try to approximate a solution in the most precise and fastest way possible.

The Newton Method is the most commonly used because of its simplicity and its rapidity, even though there are more accurate ones.

To understand the Newton Method you have to understand two concepts that must already be familiar to you: on the one hand, the solution of linear equations, and, on the other hand, the lineation of a derivative function in any x0 point by its tangent line.

Remember that this equation coincides with the degree 1 Taylor polynomial of the function. If you think you still cannot deduce it from a graphic, practice it.

Newton based the formula of his method to calculate the zeros of a function on these two concepts. In a logical way, Newton thought that if he could not calculate the root of a function in an algebraic way, but instead took the tangent line he would be close enough to the zero of the function we are looking for. Let’s see the graphics of this simple idea.

Additionally, Newton proved that if this process is iterated, so that the first zero of the first tangent line would be used to define a new point of the function where a second tangent line would be drawn that it would give us a second zero, which at the same time would be used to define a third point of the function where we would draw a third tangent line that would give us a third zero and so on, every new zero would be closer to the solution we are looking for, and, therefore, the more iterations of the Method the better the approximation of the root of the function.

From the graphic you can see that it is not a very complicated idea and that it makes sense. Now we only have to see how solve our problems with this method.

To do so, we will deduce the general formula of the method based on the formulas we have seen before. Our aim is to find how the root we find in iteration (Xk) is related to the solution obtained in the iteration before (Xk-1), as in any iterative method. Usually we will define the root we are looking for as X*, and the zeros we are finding are X1, X2, etc. X0 will be the initial point from which we will start iterating the method, which we should choose ourselves.

Equaling the function of the tangent line in X0 [insert tangent line formula] we can find X1, and, therefore, the formula of X1 based on X0 will be x1 equals x0 minus the function in x0 divided by the derivative of the function in x0.

In the same way, if we equal the tangent line in X1 to zero we will be able to find X2, and, if we isolate it like we have before, we will find that x2 equals x1 minus the function in x1 divided by the derivative of the function in x1.

Therefore, generally we can say that xk+1 = xk – f(xk)/f’(xk)

Let’s see how this formula would work applied to the function f(x)=x^3-x+1 and we will take X0= -1,5

We calculate f’(x)= 3x^2-1

We calculate X1 as -1,5 – (-0,875)/5,75 = -1,34783

We calculate X2 as

We calculate X3 as

As you can see, the difference between X3-X2 is smaller than between X2-X1, and this is smaller than X1-x0 and this means that the method tends towards x* more quickly every time.

The questions you should be asking yourselves now are: when can I consider that the obtained solution is good enough? Or, on another side, how many iterations will I need to run?

Why have we chosen x0=-1,5? Or how could we choose an X0 near to an X* if we do not know the value of X*?

We will answer these last two in the next video. For now we will lay out a couple of questions so you can evaluate your knowledge about what has been explained above.

In the next video, we will answer these questions since they will be of use to program the Newton Method on software such as Matlab. Obviously, nowadays nobody applies the Newton Method manually, but we think it is important to explain the process for you to understand what the computer does when you program it in practice.

In addition, the graphic description of the method is pretty simple for everyone to understand and be able to explain it. We hope this video was interesting and we hope to see you again for the next one.