CHAPTER 03.04: NEWTON-RAPHSON METHOD: Derivation of Newton-Raphson Method
In this segment, we're going to talk about the Newton-Raphson method of finding the root of a nonlinear equation, and we're going to discuss the algorithm for the Newton-Raphson method. So, again, we are trying to find the root of the nonlinear equation f of x equal to 0, that's the main thing to understand.
So, what Newton-Raphson method is based on is the following principle, that, let's suppose you are trying to find the root of this equation, f of x equal to 0. If you plot the function f of x as a function of x, you start with some initial guess right here. If you're going to start with some initial guess here and you draw the tangent at that particular point, you're going to find out that it crosses the x-axis right there. Once you see that it crosses the x-axis there, you go back to the function, and you draw the tangent at that particular point, and you find out that it crosses the x-axis there. And as you keep on doing this, you can see that your tangent line which you are drawing is eventually going to pass very close to the root of the equation f of x equal to 0, or to the zero of the function. And that's what the basis of the Newton-Raphson method is, that you continually draw the tangent, see where it crosses the x-axis, and use that as your new estimate of the root.
Let's go ahead and see how we can develop this formula for the Newton-Raphson method. So I have this function f of x as a function of x, and what I want to do is I'm going to start this as my initial guess, which I'll call xi, let's suppose, I'm going to draw the tangent at that particular point, and it crosses the x-axis at the point x-sub-i-plus-1. So this tangent line, if this is the tangent line to the function, then I know, let's suppose if this angle is phi, then the tangent of phi will be rise over run, and the rise will be the value of the function, so this particular point is nothing but xi, comma, f of xi, those are the x and the y coordinates of that particular point. So I know that the rise will be the value of the function at xi, minus the value of the function here, which is 0, because that's where . . . checking where the tangent line is crossing the x-axis, so it's 0, divided by the run, which would be xi minus x-sub-i-plus-1, because that's the run, the difference between these two points, that's the rise, and this is the run between the two points. And we know that if we're going to find out what the tangent of phi is, that, hey, this is nothing but f prime of xi, because that's what we mean by drawing the tangent, is same as the value . . . or the tangent of the angle of this tangent line will be same as the value of the derivative of the function at that particular point. So, from here, we get f prime of xi is equal to f of xi, divided by xi minus x-sub-i-plus-1. And in this particular equation, the only thing which is not known to us is x-sub-i-plus-1, so I'm going to write down x-sub-i-plus-1 in terms of the other unknown quantities, and I'm going to get this. This formula here is the Newton-Raphson method formula.
This formula here is the Newton- Raphson formula for finding the root of an equation, that's what we're getting. So one of the things which you should do at home is to figure out how the tangent lines are being drawn . . . how the tangent lines are being drawn in this figure here, because I find out that many a time students do not know that if I give them a graph paper and a protractor, that how will they be able to draw the tangent line going from here to here, so go through that exercise of drawing the tangent from this point to this point by using some graph paper on some function which is of your choice, and see whether you are able to do that, that's extremely important. So let's go ahead and look at what the algorithm for the Newton-Raphson method is, that I want to write down the algorithm for finding the root of the equation f of x equal to 0, that's what I want to be able to do. So, the first step which I have to do is I have to calculate . . . I have to calculate f prime of x, because in the formula itself, in the denominator it requires me to find out the derivative of the function, so I've got to calculate f prime of x, symbolically, so that's what I have to do.
Once I have done that, I choose an initial guess . . . I choose an initial guess, so let's suppose I call it x0. Then what I do is I find out my x1 from the formula. x1 would be x0 minus f of x0 divided by f prime of x0. So it's very easy to calculate the next guess, because all it requires is the initial guess which you chose, the value of the function at that initial guess, the value of the derivative of the function at the initial guess, and then what you're going to do is you're going to find the relative approximate error, which will be present value minus previous value, divided by present value, times 100. And check if epsilon-a is less than epsilon-s, which means that you're going to check whether the absolute relative approximate error which you are getting is less than some pre-specified tolerance. If it is less than or equal to pre-specified tolerance, then you're going to stop the program, if not, then you're going to continue doing this. So the general form, which I should have written . . . I wrote down for i equal to 0, so the general form, I will write it to here, the general form of step three should have been this, that x-sub-i-plus-1 is equal to xi minus the value of the function at xi, divided by f prime of xi, so you're going to calculate that. Then you're going to calculate, you're going to find epsilon-a, which is your relative approximate error to be x-sub-i-plus-1 minus xi, divided by x-sub-i-plus-1, times 100, which basically means is the current approximation minus the previous approximation, divided by current approximation, and you're going to check if the absolute relative approximate error is less than or equal to the pre-specified tolerance. So once that is done, then you're going to, if that's the case, if it turns out to be less than the pre-specified tolerance, you're going to stop, if it is not, then you're going to continue the process of putting the new value back into here, finding out the new guess, finding the relative approximate error, check again whether the pre-specified tolerance has been met. Now it's quite possible that this particular method will not converge, because it's an open method. Why is it called an open method? Because you only need one guess to start the process. So it is . . . you're not bracketing the root at all, you're simply starting with some . . . one initial guess, which is x0, and use that to find out better and better approximation of the root of the equation, so in that case, what you may have to do is you may have to limit the number of iterations so that it doesn't go into an infinite loop if it starts diverging. And that's the end of this segment. |