Can someone explain the Newton-Raphson method for calculating the square root of a number.
Printable View
Can someone explain the Newton-Raphson method for calculating the square root of a number.
I ignored this Thread for a while because I thought somebody else would post.
The Newton-Raphson method uses successive approximations to arrive at the square root of a number. It is a general purpose method for finding the zeros of a function. First, a mild digression which works because square root is a very special case. Suppose you did not know that ten is the square root of one hundred. Suppose you started with 20 as a guess. Next note that 100 / 20 = 5. Since the guess is too big, quotient is too small (vice versa for low guess). Try the average of 5 and 20 for next guess. Average is 12.5. Keep this process up as follows (Successive approximations bolded).I am sure you get the idea. Even though you do not know what the answer is, you can tell when to stop because the successive approximations do not change much when you get close to the correct square root.
- 100 / 20 = 5 and (20 + 5 ) / 2 = 12.5
- 100 / 12.5 = 8 and (12.5 + 8) / 2 = 10.25
- 100 / 10.25 = 9.756 and (10.25 + 9.756) / 2 = 10.00304878
- 100 / 10.00304878 = 9.996352149 and (10.00304878 + 9.996352149) / 2 = 10.0000004646
(N + 1) / 2 is a not bad first guess. When N is greater than one, the square root is smaller than N. When N is less than one, the square root is bigger than N. (N + 1) / 2 always gets you started in the right direction. There might be better methods for the first guess, but the method gets there so fast, the first guess does not have to be good. The following are iteration formulae for other roots (N is the number you want the root of).The general formula for the method is.
- Square root: Next = Last /2 + N / 2 * Last
- Cube root: Next = 2 * Last / 3 + N / 3 *Last^2
- 4th root: Next = 3 * Last / 4 + N / 4 * Last^3
- 5th root: Next = 4 * Last / 5 + N / 5 * Last^4
If you know how to determine derivatives, you can find the zeros for many different functions.Code:Next = Last - F(Last) / Derivative(Last)
NoteFrom the above, you can derive the iteration formulae with just a little algebraic manipulation.
- Square root: F(X) = X^2 - N and Derivative(X) = 2*X
- Cube root: F(X) = X^3 - N and Derivative(X) = 3 * X^2
- 4th root: F(X) = X^4 - N and Derivative = 4 * X^3
- 5th root: F(X) = X^5 - N and Derivative = 5 * X^4
I hope the above helps without being too simple. If there are typo’s I am sorry.
Thanks Guv, it helped a lot.
Well, everyone else ignored this thread as we were waiting for you to post! :DQuote:
I ignored this Thread for a while because I thought somebody else would post.
Please don't do that again...
If Everyone starts Ignoring...this forum will become useless. :(
I was only joking. :p
Although I understand the general idea of the Newton-Raphson method, I am unaware (I have no interest) of the details.
You may or may not have noticed that by and large, my posts in this forum are generally concerned with the more abstract mathematical concepts and not with the nitty gritty of the actual processes involved. If I have to learn them for a particular job I am doing then that is a different matter.