Let's say we want to find for some function, where solving explicitly is impossible. but you can evaluate and
You might come up with the clever idea of approximating by a tangent line, then finding where the line hits zero.
is the base because derivative is slope, which gives us the base
Intuitively , is converting some change in Y to the corresponding change in X. Using this we can now find using
Thus the general formula for improving our guess to a better guess is
Now lets have some fun! firstly lets see how to compute
we need to construct a function that is zero at , lets use
calculus tells us . we can use our formula now!
Awesome! lets try this in python
def improve(g, a): return g - (g - a/g) / 2 g = 1 # initial guess g = improve(g, 2) # g = 1.5 g = improve(g, 2) # g = 1.416666666666 g = improve(g, 2) # g = 1.414215686274 g = improve(g, 2) # g = 1.414213562374
After 4 iterations we're already correct to 12 decimal places! newton's method converges quickly, since as we approach the root our linear approximation becomes better and better. since is a line as you zoom in.