I’m creating a program for finding the square root of a number, and I came across the Newton-Raphson method, an algorithm that solves my task.
I only saw the pseudocode for the algorithm, but I never really understood why it worked. Can someone explain to me why it works without all the heavy math?
In: Mathematics
There is a [neat animation on the Wikipedia page](https://en.wikipedia.org/wiki/File:NewtonIteration_Ani.gif) which gives an idea of how this works.
Essentially you are pretending that your function is a straight line, not a curve, and then finding where the 0 would be.
You then assume that your new point is closer than your earlier one and try again – finding the new line (tangent to the curve at this point) and finding where that crosses the x-axis. And you repeat.
It doesn’t always work, but when it does, it tends to work fairly quickly.
It’s using the derivative as an approximation of the line between the current guess and the zero of the function.
If you think of a line representing a function, square root in your example, and a current guess (X), then the derivative of the function represents the slope at X. This slope is a line that crosses the zero axis, and since it’s a straight line the crossing point is easy to calculate. That zero point is a better guess for the zero than X, so if you start from that point and iteratively repeat the process you can get very close to the actual zero very quickly.
Let’s say we’re looking for X, and we have A that is smaller then X and B that’s bigger then X.
In which case A+B / 2 will be a good approximation of X (even though A, or B can be closer to X in certain cases). Think middle of the road, of which A and B are boundaries.
Now in case of a square root:
1. Assume N = sqrt(M). We don’t know what N is.
2. Let’s say X0 is our best guess as what N is. It can be either bigger then N or smaller. But at the same time A / X0 will be either smaller, or bigger then N.
3. That means that N is between X0 and M/X0. We can use the fact above and say A = N and B = M/X0
4. So X1 = (X0 + N/X0) / 2
5. Repeat 2-4 enough time, that you get close enough 🙂
Example. We’re looking for root of 10
1. A = 5
B = 10/5 = 2
X1 = (2 + 5) / 2 = 2.5
2. A = 2.5
B = 10 / 2.5 = 4
X2 = (2.5 + 4) / 2 = 3.25
3. A = 3.25
B = 10 / 3.25 ~= 3.07
X3 = (3.25 + 3.07) / 2 = 3.16
As you can see after 3 steps by narrowing down the left and right side we’re reached the result with 2 significant digits which is 3.16.
What’s important is always choosing a correct functions so that outcome always lies between A and B.
Latest Answers