Best approximation of a fraction to a given number

Question

Given a number $q \in \mathbb{R}$. Find two numbers $n,m \in \mathbb{N}$ with $m \leq N$ such that $\left|\frac{n}{m} - q\right|$ becomes minimal.

Quick info: I have no idea which subject area is best for this type of task. I just set myself this task because I find it interesting.

I first had the idea to work with the approach ||Ax - b||, but the problem is not linear. I had then looked in a few books and always it was directly about polynomials or functions to which one could build an orthonormal basis. Therefore my question: How do I solve this problem? Can it be solved analytically at all?

---

Okay, I have now looked at the procedure mentioned in the first answers and it is actually quite simple:

Split the number $q_0 = q$:

$$q_0 = ⌊q_0⌋ + \tilde{q}_0,$$

where $\tilde{q}_0 < 1$. Subsequently, we find a $q_1$ with

$$q_1 = \frac{1}{\tilde{q}_0}.$$

Then the procedure repeats. Finally, the algorithm is:

(1) $q_k = ⌊q_k⌋ + \tilde{q}_k$

(2) $q_{k+1} = \frac{1}{\tilde{q}_k}$

The bestapprixmation is then

$$q = ⌊q_0⌋ + \frac{1}{⌊q_1⌋ + \frac{1}{⌊q_2⌋ \,+ \,\ldots}}$$

Example: $3.1415926...$

$$q_0 = 3 + 0.1415926...$$

$$q_1 = \frac{1}{0.1415926...} = 7.0625... = 7 + 0.0625...$$

$$q_2 = \frac{1}{0.0625...} = 15.996... = 15 + 0.996...$$

$$q_3 = \frac{1}{0.996...} = 1.003... = 1 + 0.003...$$

We then find the following approximations:

$$ q = \left\{3, \frac{22}{7}, \frac{333}{106},\frac{335}{113},\ldots \right\} $$

But what bothers me a lot here are the big denominators. Already the third fraction is over 100. Is there no fraction $\frac{n}{m}$ with $m \leq 100$, which better approximates the number $\pi$ as $\frac{22}{7}$?

---

Okay, I have now found a better approximation. It holds:

$$\left|\frac{22}{7} - \pi\right| = 0.0012644892$$

$$\left|\frac{311}{99} - \pi\right| = 0.00017851$$

So the algorithm is only partially suitable.

Answer 1

You can try to do a continued fraction and truncate it after some terms. For example, this way, you can find the following approximations for $\pi$, by truncating at various places: $\frac{22}{7}$, $\frac{355}{113}$...

Edit

If you don't mind testing all the possibilities, you can also simply compute$$\min_{m=1}^N\left|q-\frac{[mq]}m\right|$$ where $[x]$ is the closest integer to $x$. This is an algo in $O(N)$ so it's not too bad either - it's linear in $N$. The solution is $q\sim\frac{[mq]}m$.

Answer 2

To answer your exact question, if $q$ is rational, then it is exactly a ratio of integers. If it’s irrational, then there is some infinite sequence of rational approximations that converge to your number, so there is no one approximation where the difference is minimal.

What you probably want are numbers with small denominator that approximate your number. In particular, an approximation $n/m$ could be considered the best if it’s closer to $q$ than all other rational numbers with denominator at most $m$.

The standard way to accomplish this uses continued fractions. You can cut off the infinite fraction series to get a rational approximation and it’s possible to prove that this procedure gives all the best rational approximation. See Best Rational Approximations here for more details: https://en.m.wikipedia.org/wiki/Continued_fraction