Problem
An old method of approximating the square root of a number $x$, is to find the largest integer $n$ such that $n^2 \leq x$. Then, $$\sqrt x \approx \frac n2 + \frac x{2n}$$
Find an optimal limit on the error, $M = \sqrt x - \left(\frac n2 + \frac x{2n}\right)$.
Caveat
This appears as part of a chapter on implicit differentiation, so I assume that's an intended strategy.
Thoughts
This reminds me of the expression we'd get by using Newton's method, although in this case, it's not iterative.
From what I can tell, it's going to be more and more erroneous (in absolute values) as $x\to\infty$, but in terms of percentages of the real value, I'm not sure.
The question asks for an "optimal limit" on the error, and I'm not entirely sure what that refers to. My current understanding is that it means that we want $M(x)$ to be as low as possible, and perhaps we want to solve $M'(x) = 0$ for that purpose?
But I'm not sure whether to treat $M$ as a function of $x$ or $n$ or both.
Multiple choice
The question is a multiple choice, with the following options:
- $-\frac{(x-n^2)^2}{8n^3} < M \leq 0$
- $0\leq M\leq\frac{(x-n^2)^2}{8n^3}$
- $-\frac{(x-n)^2}{8n^3} < M \leq 0$
- $0\leq M \leq \frac{(x-n)^2}{8n^3}$
- $-\frac{(x-n^2)^2}{4n^2} \leq M \leq 0$
- $0 \leq M \leq \frac{(x-n^2)^2}{4n^2}$
- $-\frac{(x-n^2)^2}{8x} < M \leq 0$
- $0 \leq M < \frac{(x-n^2)^2}{8x}$
- $-\frac{x-n^2}{8x} \leq M \leq 0$
- $0 \leq M \leq \frac{x-n^2}{8x}$
But note that I'm not asking for the answer. I'm more interested in the method.
EDIT: here is now the expected answer.
Posing the error $f(x)=\sqrt x - \frac 1 2 (n+\frac x n)$,
$f(x)=-\frac 1 2 (n-2\sqrt x + \frac x n)$
$= -\frac 1 2 (\sqrt {\frac x n} - \sqrt n)^2$
$= - \frac 1 {2n} (\sqrt x - n)^2$
As $x-n^2 = (\sqrt x-n)(\sqrt x+n)$,
$\sqrt x-n = \frac {x-n^2} {\sqrt x+n} \le \frac {x-n^2} {2n}$ (because $\sqrt x \ge n$)
So $f(x) = - \frac 1 {2n} (\sqrt x - n)^2 \ge -\frac 1 {2n} \frac {(x-n^2)^2} {4 n^2} = -\frac {(x-n^2)^2} {8n^3}$
As the error is always negative or null, and is null for $x=n^2$, the result is:
$-\frac {(x-n^2)^2} {8n^3} \le M \le 0$
This is the first choice in the multiple choice list, but they made a slight error: when $x=n^2$, $M$ is null, so the inequality $-\frac {(x-n^2)^2} {8n^3} \lt M$ cannot be strict, it must be $\le$.
Previous answer:
This is a puzzled answer. Puzzled, because no choice in the multiple choice seems to be optimal.
Let's take an example. For $4\le x \lt 9$, $n=2$. There is an exact solution for $x=4$, and the maximum error is for $x=9-\varepsilon$:
$M \gt \sqrt{9}-(\frac 2 2 + \frac 9 {2 \times 2}) = - \frac 1 4$
The trouble is, none of the proposed answers give this value $-\frac 1 4$ for $n=2$ and $x=9$ (well, $9-\varepsilon$).
This being said, here is another answer. In all what follows, $n = \lfloor \sqrt x \rfloor$.
$n^2 \le x \lt (n+1)^2$
$n \le \sqrt x \lt n+1$
$\sqrt x -1 \lt n \le \sqrt x$
$\frac 1 {\sqrt x -1} \gt \frac 1 n \ge \frac 1 {\sqrt x}$
The error is $f(x) = \sqrt x - \frac 1 2 (n+\frac x n)$
$f'(x) = \frac 1 2 (\frac 1 {\sqrt x} - \frac 1 n)$
As $\frac 1 n \ge \frac 1 {\sqrt x}$, $f'(x) \le 0$. $f'(x) = 0$ for $n = \sqrt x$.
So the maximum for $f$ is when $n = \sqrt x: f(x)=0$.
The minimum is attained at the other end of the interval for $n$ constant, i.e. for $\sqrt x=n+1-\varepsilon$.
So this minimum is $\sqrt x - \frac 1 2 (\sqrt x - 1 + \frac x {\sqrt x - 1})$
$= \frac 1 2 (\sqrt x + 1 - \frac x {\sqrt x - 1})$
$= - \frac 1 2 \frac 1 {\sqrt x - 1} = - \frac 1 {2n}$
In the example above, this gives the right solution: $-\frac 1 {2n} = - \frac 1 4$.
Perhaps the exercise is to get a bound for $M$ that is not optimal for all $x$ corresponding to some $n$, but tends to $0$ when $x \to n^2$? This is the case in all but one of the proposed answers.
I'll have a look in this direction later.