I've already received a lot of help with this problem (thank you all), and I've written up an answer with all of the information I've got in it as to why these approximations are so good.
My question is why the following rational function is such a good approximation for the square root of $x$?
$$\sqrt{x}\approx\frac{256+1792x+1120 x^{2}+112 x^{3}+x^{4}}{1024+1792x+448 x^{2}+16 x^{3}}$$
The following image illustrates that for $3\leqslant x\leqslant 7$ the two curves are almost identical:
More generally why does the following formula hold with such accuracy?:
$$\sqrt{n}\approx\frac{m^{8}+28 m^{6}n+70 m^{4}n^{2}+28 m^{2}n^{3}+n^{4}}{8 m^{7}+56 m^{5}n+56m^{3}n^{2}+8m n^{3}}$$
for any real number (not just integer) $n\geqslant 1$ and:
$$m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$$
The following graph shows that for $0\leqslant n\leqslant10000$ the two curves cannot be separated by eye:
And this is the logarithm of the error in that approximation which decreases cyclically (presumably due to the floor in the definition of $m$) but then starts to become slightly less accurate stepwise as $n$ increases:
(Edit: Several people have mentioned Pade approximants below and that the first formula is a Pade approximant, which explains why it is such a good approximation. I would really especially like to know why the second formula is such a good approximation on the wide range I have shown in the second graph (is it related to Pade approximants also?), and I would really love to know why the process I outline in the section below of how I got these functions gives Pade approximants at all from ratios of binomial coefficients. At first glance, it seems as if there might be something deep going on here?)
How I found these and what I already know:
While messing around with maths once I noticed that $(3+\sqrt{8})^{8}\approx1331714$ with very good accuracy. Since the binomial theorem gives that $(3+\sqrt{8})^{8}=665857+235416\sqrt{8}$ and since $1331714=2\times665857$ I saw that that gave the approximation:
$$\sqrt{8}\approx\frac{665857}{235416}$$
which is quite accurate. I found this intriguing, but exploring further I found that similar near integer results were produced by:
$$(1+\sqrt{2})^{8}\approx1154$$
$$(2+\sqrt{3})^{8}\approx37634$$
$$(2+\sqrt{4})^{8}=65536$$
$$(2+\sqrt{5})^{8}\approx103682$$
$$(2+\sqrt{6})^{8}\approx153632$$
$$(3+\sqrt{7})^{8}\approx1032224$$
and so on, and I found that in general I could get a very accurate near integer from any (at least small) expression of the form $(m+\sqrt{n})^{8}$ where as $n$ increased over the integers $m$ increased as:
$$m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$$
When these expressions were expanded out they were all in the form $a+b\sqrt{n}\approx2a$ where:
$$a=m^{8}+28 m^{6}n+70 m^{4}n^{2}+28 m^{2}n^{3}+n^{4}$$
$$b=8 m^{7}+56 m^{5}n+56m^{3}n^{2}+8m n^{3}$$
From this you get my original equations that I posted.
Now there is nothing particularly interesting about the eighth powers I have been working with; ninth powers work as well (slightly more accurately) and seventh powers are slightly less accurate, giving a similar formula:
$$\sqrt{n}\approx\frac{m^{7}+21 m^{5}n+35 m^{3} n^{2}+7m n^{3}}{7 m^{6}n+35 m^{4} n^{2}+21 m^{2} n^{3}+n^{4}}$$
Thus some of the reason behind these formulae must be the fact that the $m+\sqrt{n}$ have powers tending to integers, and just about the only thing I have been able to find out about why this might work is that some of these numbers are Pisot-Vijayaraghavan numbers (i.e. their powers tend towards integers).
However, this does not explain the phenomenon, since I do not know why the effect would be greatest for $m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$ or importantly why the convergence should be of the form $(m+\sqrt{n})^{c}=a+b\sqrt{n}\approx 2a$ (which is where the approximation comes from) or why the formula derived should also hold for non-integral $n$. Rather the important part seems to lie in the formulation as:
$$\left(\frac{Even Binomial Terms}{Odd Binomial Terms}\right)^{\pm 1}$$
and perhaps in the expression $m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$.
So my question is: why do these formulae work?
Answer
From the many good answers and comments to this question, especially those of Peter and Barry Cipra, I think I’ve come to understand the answers to most of my questions. Since none of the answers by other users here has all of the information in one place, and someone else might want to see in one place what helped me at least, I thought I’d write it all up into one answer (I've accepted the answer to make it obvious, I hope that's not considered rude). The main thing I'm answering is my question about why powers of $(m+\sqrt{n})$ give good approximations of $\sqrt{n}$, and also finding the error of the approximation.
When $(m+\sqrt{n})^c$ is expanded binomially for $m,c\in\mathbb{N}$ and real $n>0$, we get:
$$(m+\sqrt{n})^c=\sum_{k=0}^{c}\binom{c}{k}m^k n^{\frac{c-k}{2}}$$
$$=\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}$$
Now if $c$ is even then a factor of $\sqrt{n}$ can be taken out of the second sum as follows:
$$\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}\\=\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}+\sqrt{n}\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k}{2}}$$
such that the powers of $n$ in each sum are all integers, and if $c$ is odd then the same factor can be taken out of the first sum so that all powers of $n$ in the sums are integers:
$$\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}\\=\sqrt{n}\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k-1}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}$$
This gives us the following:
$$(m+\sqrt{n})^c=a_{m,c}(n)+b_{m,c}(n)\sqrt{n}\tag{1}$$
Where $a_{m,c}$ and $b_{m,c}$ are polynomials in $n$ given by:
$$a_{m,c}(n)=\begin{cases}\sum_\limits{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}&c\text{ even}\\\sum_\limits{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}&c\text{ odd}\end{cases}$$
$$b_{m,c}(n)=\begin{cases}\sum_\limits{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k}{2}}&c\text{ even}\\\sum_\limits{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k-1}{2}}&c\text{ odd}\end{cases}$$
(Note that these polynomials are the polynomials found in the rational approximation in the question). Now an analogous argument will show that:
$$(m-\sqrt{n})^c=\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}(-1)^{\frac{c-2k}{2}}m^{2k}n^{\frac{c-2k}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}(-1)^{\frac{c-2k+1}{2}}m^{2k-1}n^{\frac{c-2k+1}{2}}$$
And if $c$ is even then we have:
$$(m-\sqrt{n})^c=\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k}{2}}-\sqrt{n}\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k}{2}}$$
And if $c$ is odd then we have:
$$(m-\sqrt{n})^c=-\sqrt{n}\sum_{k=0}^{\left\lfloor\frac{c}{2}\right\rfloor}\binom{c}{2k}m^{2k}n^{\frac{c-2k-1}{2}}+\sum_{k=1}^{\left\lceil\frac{c}{2}\right\rceil}\binom{c}{2k-1}m^{2k-1}n^{\frac{c-2k+1}{2}}$$
So that we must have:
$$(m-\sqrt{n})^c=a_{m,c}(n)-b_{m,c}(n)\sqrt{n}\tag{2}$$
Thus we can add $(1)$ and $(2)$ together to obtain:
$$(m+\sqrt{n})^c+(m-\sqrt{n})^c=2 a_{m,c}(n)$$
$$\therefore 2 a_{m,c}(n)=a_{m,c}(n)+b_{m,c}(n)\sqrt{n}+(m-\sqrt{n})^c$$
$$\therefore b_{m,c}(n)\sqrt{n}=a_{m,c}(n)-(m-\sqrt{n})^c$$
$$\therefore \sqrt{n}=\frac{a_{m,c}(n)-(m-\sqrt{n})^c}{b_{m,c}(n)}$$
Thus we have proved that the following approximation:
$$\sqrt{n}\approx\frac{a_{m,c}(n)}{b_{m,c}(n)}$$
(which is exactly the form of the approximations in the question) will for any positive real number $n$ have an error $E$ of precisely:
$$E=\frac{|m-\sqrt{n}|^c}{b_{m,c}(n)}$$
since $b_{m,c}$ is positive. If $m$ is constrained to be an integer near $\sqrt{n}$ then it is easy to see that this will be small, especially for large $c$ (for which $b_{m,c}$ will also increase).
Now a quick check shows that the formula for $m$ in the question never differs from $\sqrt{n}$ by more than around $0.75$ for $n>1$ so the error for $c=8$ will be always less then around $\frac{1}{10 b_{m,c}(n)}$ which will grow as $b_{m,c}$ grows (indeed as $n$ increases the bound on the error appears to decrease towards $\frac{1}{256 b_{m,c}(n)}$ although I haven't proved this). This explains why the following formula for instance:
$$\sqrt{n}\approx\frac{m^{8}+28 m^{6}n+70 m^{4}n^{2}+28 m^{2}n^{3}+n^{4}}{8 m^{7}+56 m^{5}n+56m^{3}n^{2}+8m n^{3}}$$
$$m=\left\lfloor\frac{1+\sqrt{4n-3}}{2}\right\rfloor$$
is such a good approximation.
Indeed if we constrain $m$ to be an integer then the closest to $\sqrt{n}$ we could choose is $\left\lfloor\frac{1}{2}+\sqrt{n}\right\rfloor$ in which case the error of the approximation would be always less than $\frac{1}{2^{c}b_{m,c}(n)}$ which will be very small. This appears to explain the accuracy of the formulae shown.
No comments:
Post a Comment