Newton's Method for Square Roots
You need to compute $\sqrt{c}$ for some positive number $c$ using Newton's iterative method.
Set up the root-finding problem: what function $f(x)$ do you solve, and what is the Newton update step? Starting from an initial guess $x_0 > 0$, write out the iteration formula and simplify it.
Then answer the following:
- What is the rate of convergence of this method (linear, quadratic, etc.), and why?
- Demonstrate the iteration numerically: compute $\sqrt{2}$ starting from $x_0 = 1$, showing at least 3 iterations.
- Does the method converge for any starting guess $x_0 > 0$? What about $x_0 < 0$?
Hints
- Start by writing down the function whose root gives you $\sqrt{c}$, and recall Newton's general update formula $x_{n+1} = x_n - f(x_n)/f'(x_n)$.
- After substituting $f(x) = x^2 - c$, simplify the update to see that each step averages $x_n$ with $c/x_n$ -- one is too big, the other too small.
- To prove quadratic convergence, compute the error $e_{n+1} = x_{n+1} - \sqrt{c}$ and show it equals $e_n^2 / (2x_n)$. For global convergence from any $x_0 > 0$, use the AM-GM inequality to show $x_1 \geq \sqrt{c}$.
Worked Solution
How to Think About It: Newton's method is the go-to tool for solving $f(x) = 0$ iteratively. The idea is dead simple: at your current guess $x_n$, approximate $f$ by its tangent line and step to where the tangent hits zero. For square roots, we want to solve $x^2 - c = 0$, and Newton's update turns into a beautiful formula that people have been using since ancient Babylon -- literally. The key insight is that each step averages your current guess with $c$ divided by your guess, which automatically corrects overshoots and undershoots.
Quick Estimate: Before deriving anything, let's build intuition. If you want $\sqrt{2}$ and guess $x_0 = 1$, that's too low. Then $c/x_0 = 2/1 = 2$ is too high. Averaging gives $1.5$ -- already within 6% of $\sqrt{2} \approx 1.4142$. One more step and you are within 0.2%. The convergence is shockingly fast.
Approach: Apply Newton's method to $f(x) = x^2 - c$ and simplify.
Formal Solution:
We want to find $\sqrt{c}$, i.e., the positive root of: $$f(x) = x^2 - c = 0$$
Newton's update formula is: $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
Here $f'(x) = 2x$, so: $$x_{n+1} = x_n - \frac{x_n^2 - c}{2x_n} = \frac{2x_n^2 - (x_n^2 - c)}{2x_n} = \frac{x_n^2 + c}{2x_n}$$
This simplifies to the elegant form: $$\boxed{x_{n+1} = \frac{1}{2}\left(x_n + \frac{c}{x_n}\right)}$$
This is the Babylonian method (or Heron's method). The geometric interpretation: if $x_n$ is your guess for $\sqrt{c}$, then $c/x_n$ is the "complementary" guess (since their product is $c$). If $x_n$ is too large, $c/x_n$ is too small, and vice versa. Averaging the two corrects in both directions.
Part 1 -- Convergence rate:
Newton's method converges quadratically near a simple root. To see why, define the error $e_n = x_n - \sqrt{c}$. Then: $$x_{n+1} = \frac{1}{2}\left(x_n + \frac{c}{x_n}\right) = \frac{x_n^2 + c}{2x_n}$$
The error at step $n+1$ is: $$e_{n+1} = x_{n+1} - \sqrt{c} = \frac{x_n^2 + c}{2x_n} - \sqrt{c} = \frac{x_n^2 - 2x_n\sqrt{c} + c}{2x_n} = \frac{(x_n - \sqrt{c})^2}{2x_n} = \frac{e_n^2}{2x_n}$$
So $e_{n+1} \approx \frac{e_n^2}{2\sqrt{c}}$ once $x_n \approx \sqrt{c}$. This means the number of correct digits roughly doubles with each iteration -- that is quadratic convergence.
Part 2 -- Numerical demonstration for $\sqrt{2}$:
Starting with $x_0 = 1$:
- $x_1 = \frac{1}{2}(1 + 2/1) = 1.5$
- $x_2 = \frac{1}{2}(1.5 + 2/1.5) = \frac{1}{2}(1.5 + 1.\overline{3}) = 1.41\overline{6}$
- $x_3 = \frac{1}{2}(1.41\overline{6} + 2/1.41\overline{6}) \approx 1.414216$
The true value is $\sqrt{2} = 1.414213\ldots$ Three iterations give 5 correct digits, and the error went $0.414 \to 0.086 \to 0.0025 \to 0.000003$ -- each step roughly squares the relative error.
Part 3 -- Convergence from any $x_0 > 0$:
Yes, the method converges for any $x_0 > 0$. To see why: after one step, $x_1 = \frac{1}{2}(x_0 + c/x_0) \geq \sqrt{c}$ by AM-GM (the arithmetic mean of two positive numbers exceeds their geometric mean $\sqrt{x_0 \cdot c/x_0} = \sqrt{c}$). So $x_n \geq \sqrt{c}$ for all $n \geq 1$, and from there the sequence is monotonically decreasing toward $\sqrt{c}$. Combined with the quadratic error bound, convergence is guaranteed.
For $x_0 < 0$, the iterates converge to $-\sqrt{c}$ instead (the negative root), by the same logic applied to $|x_n|$.
Answer: The Newton iteration for $\sqrt{c}$ is $x_{n+1} = \frac{1}{2}(x_n + c/x_n)$. Convergence is quadratic (digits of accuracy double each step). The method converges to $\sqrt{c}$ for any $x_0 > 0$, and to $-\sqrt{c}$ for any $x_0 < 0$.
Intuition
Newton's method for square roots is one of the oldest algorithms in mathematics -- the Babylonians were using it 4,000 years ago, long before anyone formalized calculus. The reason it works so well is the beautiful self-correcting structure: if your guess overshoots $\sqrt{c}$, then $c/x$ undershoots by a complementary amount, and averaging the two kills most of the error. The quadratic convergence means you go from a rough guess to machine precision in about 5 iterations, which is why this is the basis for how CPUs actually compute square roots.
In quant interviews, this problem tests whether you can apply Newton's method mechanically and whether you understand convergence analysis. The deeper lesson is about quadratic convergence as a property of Newton's method at simple roots -- it shows up whenever you are iteratively solving nonlinear equations in calibration (fitting vol surfaces, solving for implied vol, finding fixed points in equilibrium models). Knowing that convergence is quadratic tells you the iteration is reliable and fast, which matters when you need to price thousands of options in real time.