Newton-Raphson Iteration Not Converging for Dummies

calculusnewton raphson

Background

While this comes from my attempts at a computer program, I think this is more of a mathematics problem. I took Algebra 2 in High School 8 years ago, dropped out of a College Calculus class 6 years ago, and am currently making another attempt at college and am in a College Trigonometry class. Therefore, I have to ask that anyone who provides an answer, please try to avoid using mathematical terminology or if you do, please explain the concepts behind what you are saying.
Anyway, over the summer I began teaching myself about bare-metal computer programming. This lead to my taking a closer look at the question of how a computer preforms various non-obvious function like Square Roots, Variable Roots, the various Trigonometric Functions, Logarithms, etc…

I decided to start with solving/approximating a square root. My understanding of what a root is in mathematics is the zero crossing of a function(where is crosses the x-axis). Correct me if I am wrong. I did not want to just take someone else's formula without first understanding how it worked. So After a few days of research online and some trial and error on paper I came up with this:

I will use the variables:
G: The New Guess
g: The starting guess/unknown square root
N: The value we are trying to find the square root of
I: This is defined in the formulas below, but it's simply the reciprocal of N

The starting problem: $$g^2 = N$$
Zero the root: $$g^2 – N = 0$$
Convert to function: $$f(g) = g^2 – N$$
Find the derivative: $$f'(g) = 2g$$
The Newton–Raphson method Formula: $$G = g – \frac{f(g)}{f'(g)}$$
Subsitute our functions into the Newton–Raphson method formula: $$G = g – \frac{g^2 – N}{2g}$$
This can be rewritten in the more common form of: $$G = \frac{1}{2}(g + \frac{N}{g})$$
This gives us a formula that can be used to iterate to a root. However, it was mentioned in my research that dividing a floating point number by an arbitrary value is one of the slowest operations that can be requested of the FPU. So instead, it was suggested to use a different formula. I found that I could find this formula using this starting problem:
$$\frac{1}{g^2} = \frac{1}{N}$$
This can then be rewritten as:
$$g^{-2} = I$$ AND $$I = \frac{1}{N}$$
So in this case our function becomes: $$f(g) = g^{-2} – I$$

The Problem

I'm going to skip rewriting and repeating all of the steps above for this new function, but it comes out to eventually yield an iteration formula, to find a square root, that looks like this: $$G = \frac{g(3 – Ig^{2})}{2}$$
Variable I is simply the reciprocal of the value we want to find the square root of. This means that the difficult floating point division only needs to be done once in the program to find it. Division by 2 is easy enough since it's just a bit-shift in binary. I thought I had solved the problem was happy. However, I just found the time to do more work on my custom math library and I have found a problem with my solution that I do not understand. In my current implementation, I always start with a guess of 1. If, however, you send my iteration formula a value that is less than $\frac{1}{3}$, it will result in a negative number being computed when the reciprocal of that is multiplied by the square of 1 and then subtracted from 3. This sends the iteration flying off into la-la land and not converging on the root. I don't understand what I did wrong so I don't want to try to start writing in some kind of catch for this situation since I don't know if I might have missed something else. Can anyone help me understand this?

Best Answer

This is just a way Newton's method works for some functions.

In general, the only promise Newton's method gives you is "if the iteration converges to something, it will be a root". For nice functions, there is an additional promise: "if you start sufficiently close to the right answer, you'll converge to the answer".

With the iteration $g \mapsto \frac12 g(3 - g^2 N^{-1})$ that you're doing, we can work out that if $0 < g < \sqrt N$, then $\frac12 g(3 - g^2 N^{-1})$ will be between $g$ and $\sqrt N$, so we'll be on our way to the square root. This is done in two steps:

  • If $0 < g < \sqrt N$, then $\frac12 (3 - g^2 N^{-1}) > \frac13(3 - (\sqrt{N})^2 N^{-1}) = 1$, so $\frac12 g(3 - g^2 N^{-1})$ is bigger than $g$.
  • If $0 < g < \sqrt N$, then $$ N - \left(\frac12g(3 - g^2 N^{-1})\right)^2 = \frac{(4N - g^2)(N - g^2)^2}{4N^2} > 0, $$so $\frac12 g(3 - g^2 N^{-1})$ is less than $\sqrt N$. (This would actually still be true for any $g$ such that $-2\sqrt N < g < 2\sqrt N$, where the factor $4N-g^2$ is positive.)

If we can make sure to always start at a guess between $0$ and $\sqrt N$, then our sequence will keep increasing towards $\sqrt N$, and that guarantees that we'll converge.

One way to do this is to make your initial guess be $\min\{1, N\}$ rather than always start at $1$.

Related Question