Rationale Approximationen
Eine reelle Zahl x kann beliebig genau durch Brüche p/q ∈ ℚ approximiert werden, d. h. für alle ε ∈ ℝ+ existieren p ∈ ℤ und q ∈ ℕ+, mit |x − p/q| < ε. Wir finden ein solches p/q leicht wie folgt: Sei q derart, dass 1/q ≤ ε, und sei p ∈ ℤ maximal mit p/q ≤ x. Dann ist |x − p/q| < 1/q ≤ ε. Eine natürliche informale Frage ist nun: Welche reellen Zahlen lassen sich mit geringem Aufwand relativ gut durch rationale Zahlen approximieren?
in Dieudonne (1985):
„Eine ernsthafte Untersuchung dieses Problems begann um die Mitte des achtzehnten Jahrhunderts, als sich die Mathematiker für die numerische Auflösung von Gleichungen und die Geschwindigkeit der Konvergenz der Näherungswerte für Wurzeln interessierten. Aus der einfachen Suche nach einer praktischen Methode zur Annäherung einer reellen Zahl ist ein ganzer technischer und spezialisierter Zweig der Zahlentheorie hervorgegangen [ die Theorie der rationalen oder diophantischen Approximationen ].“
Ein gutes Maß für den betriebenen Approximations-Aufwand ist die Größe des Nenners des approximierenden Bruchs. „Relativ gut“ interpretieren wir dann durch eine Funktion, die einem Nenner eine Approximationsgüte α zuordnet.
Definition (Approximationsfunktion)
Sei α : ℕ+ → ℝ+ eine monoton fallende Funktion.
Dann heißt α auch eine Approximationsfunktion.
Der Leser, der den zunächst immer recht dunklen Himmel abstrakter Definitionen gerne mit einem Polarstern versieht, denke im Folgenden zuerst an die Funktion α mit α(n) = 1/n2 für n ∈ ℕ+.
Definition (α-approximierbare reelle Zahlen)
Sei x ∈ ℝ, und sei α eine Approximationsfunktion. Dann setzen wir:
Sα(x) = { p/q | q ∈ ℕ+, p ∈ ℤ, |x − p/q| < α(q) }.
x heißt α-approximierbar, falls Sα(x) unendlich ist.
Im Folgenden gilt für Bruchdarstellungen p/q von rationalen Zahlen immer p ∈ ℤ und q ∈ ℕ+, wenn nichts anderes angegeben ist.
Sei p/q = p′/q′, q ≤ q′, und sei |x − p′/q′| < α(q′). Da die Funktion α monoton fällt, ist |x − p/q| = |x − p′/q′| < α(q′) ≤ α(q). Insbesondere können wir uns also beim Testen, ob ein Bruch p/q ein Element von Sα(x) ist oder nicht, auf gekürzte Brüche beschränken.
Die folgende einfache Äquivalenz zur α-Approximierbarkeit ist an vielen Stellen nützlich:
Satz
Für alle x ∈ ℝ und alle Approximationsfunktionen α sind äquivalent:
(i) | x ist α-approximierbar. |
(ii) | { q | q ∈ ℕ+ und es gibt ein p ∈ ℤ mit: p und q sind relativ prim und |x − p/q| < α(q) } ist unendlich. |
Beweis
zu (i) ↷ (ii): Für jedes q ∈ ℕ+ ist Sq endlich, wobei
Sq = { p/q | p ∈ ℤ, p, q relativ prim, |x − p/q| < α(q) }.
Aber Sα(x) = ⋃q ≥ 1 Sq nach der Überlegung oben, und somit ist Sq ≠ ∅ für beliebig große q ∈ ℕ+.
zu (ii) ↷ (i): ist klar.
Eine Folgerung des Satzes ist: Ist x α-approximierbar, so existieren gekürzte Brüche p/q mit |x − p/q| < α(q) und einem beliebig großen Nenner q.
Wir konzentrieren uns im Folgenden auf Funktionen α mit α(q) = c/qk für alle q ∈ ℕ+, wobei c ∈ ℝ+ und k ∈ ℕ gewisse feste Größen sind. Ist α in einer solchen Form gegeben, so sprechen wir etwa von „x ist c/qk-approximierbar“, indem wir die Funktion α mit einem ihre Werte definierenden Term identifizieren. In diesem Fall ist immer q die Variable des Terms, und wir schreiben dann weiter Sc/qk(x) für Sα(x).
Übung
Jedes x ∈ ℝ ist 1/q-approximierbar.
Für Approximationsfunktionen der Form 1/qk ist die Zahl k ein Maß für die Güte der Approximation. Ist x 1/qk-approximierbar für ein großes k, so kann x aus polynomieller Sicht sehr gut mit geringem Aufwand durch eine rationale Zahl angenähert werden. Wir werden sehen, dass sich Zahlen wie und allgemeiner die Quadratwurzeln in dieser Hinsicht überraschend schlecht approximieren lassen.
Für c/qk-Funktionen haben wir folgendes Kriterium für die Nicht-Approximierbarkeit:
Satz
Für alle x ∈ ℝ und k ∈ ℕ sind die folgenden Aussagen äquivalent:
(i) | Es gibt ein c ∈ ℝ+ mit: x ist nicht c/qk-approximierbar. |
(ii) | Es gibt ein c ∈ ℝ+ mit: |x − p/q| ≥ c/qk für alle p/q ≠ x. |
Beweis
zu (i) ↷ (ii): Sei c ∈ ℝ+ derart, dass S = Sc/qk(x) endlich ist.
Ist S = { x }, so ist c bereits wie in (ii). Andernfalls sei d = min({ |x − p/q| | p/q ∈ S, p/q ≠ x }), und es sei c′ = min(c, d).
Dann ist c′ > 0 und es gilt |x − p/q| ≥ c′/qk für alle p/q ≠ x.
zu (ii) ↷ (i): ist trivial.
Vielfache Verwendung findet:
Korollar (Transferlemma)
Sei x ∈ ℝ nicht c/qk-approximierbar für ein c ∈ ℝ+ und ein k ∈ ℕ.
Dann gilt für alle d ∈ ℝ+: x ist nicht d/qk + 1-approximierbar.
Beweis
Annahme doch für ein d ∈ ℝ+. Nach Voraussetzung und dem Satz oben existiert ein c ∈ ℝ+ mit |x − p/q| ≥ c/qk für alle p/q ≠ x.
Nach Annahme existiert p/q ≠ x mit:
(i) | d/q < c, |
(ii) | |x − p/q| < d/qk + 1. |
Dann ist aber
|x − p/q| < d/qk + 1 = d/q · 1/qk < c/qk,
im Widerspruch zur Wahl von c.
Wir untersuchen nun verschiedene Typen von reellen Zahlen auf bestmögliche Approximierbarkeit durch Funktionen c/qk. Ein einfaches Bruchrechnen liefert sofort ein limitierendes Ergebnis für die rationalen Zahlen:
Satz (Approximation rationaler Zahlen durch rationale Zahlen)
Sei x ∈ ℚ. Dann existiert ein c ∈ ℝ+ mit
|x − p/q| > c/q für alle p/q ≠ x.
Insbesondere ist eine rationale Zahl nicht d/q2-approximierbar für d ∈ ℝ+.
Beweis
Sei x = r/s, und sei p/q ∈ ℚ, p/q ≠ r/s. Dann gilt rq − sp ≠ 0 und
|r/s − p/q| = |(rq − sp)/(sq)| ≥ 1/(sq).
Sei also c ∈ ℝ+ derart, dass c < 1/s gilt. Dann ist c wie gewünscht.
Aus dem Transferlemma folgt der Zusatz.
Später werden wir mit dem Satz von Liouville von 1844/1851 den großen Bruder dieses Satzes kennen lernen.
Erstaunlicherweise charakterisiert nun die fehlende 1/q2-Approximierbarkeit die rationalen Zahlen, denn irrationale Zahlen sind in der Tat 1/q2-approximierbar. Dies folgt leicht aus dem folgenden klassischen Satz von Dirichlet, dessen Beweis das Dirichletsche-Schubfach- oder Taubenschlagprinzip populär gemacht hat: Verteilt man n Tauben auf k Schläge, und gilt k < n, so gibt es mindestens einen Schlag, der mit mindestens zwei Tauben besetzt ist. (Das Prinzip wurde in [ Dirichlet 1834 ] zuerst angewandt.)
Satz (Satz von Dirichlet)
Sei x irrational und sei n ∈ ℕ+. Dann existieren p ∈ ℤ und q ∈ ℕ+ mit:
(i) | |x − p/q| < 1/(q · n). |
(ii) | q ≤ n. |
Beweis
Für eine reelle Zahl y sei
Z(y) = „das größte z ∈ ℤ mit z ≤ y“.
Für 0 ≤ i ≤ n sei weiter
xi = „der Nachkommaanteil von x · i“.
Dann ist x0 = 0 und 0 < xi < 1 für 0 < i ≤ n.
Wegen x irrational sind die xi paarweise verschieden (!).
Für 0 ≤ j < n definieren wir schließlich Intervalle Ij der Länge 1/n durch
Ij = [ j/n, (j + 1)/n [.
Nach dem Taubenschlagprinzip existieren ein j und i0 < i1 mit xi0, xi1 ∈ Ij, denn jede der (n + 1)-vielen „Tauben“ xi sitzt in einem der n-vielen „Schläge“ Ij, 0 ≤ j < n. Es gilt dann:
|x · (i1 − i0) − (Z(x · i1) − Z(x · i0))| = |xi1 − xi0| < 1/n.
Also sind q = i1 − i0 und p = Z(x · i1) − Z(x · i0) wie gewünscht.
Korollar (1/q2-Approximation irrationaler Zahlen)
Sei x irrational. Dann ist x 1/q2-approximierbar.
Beweis
Für n, p, q wie im Satz von Dirichlet gilt |x − p/q| < 1/(q n) ≤ 1/q2.
Andererseits gilt |x − p/q| < 1/(q n) ≤ 1/n.
Da n beliebig groß gewählt werden kann, existieren also unendlich viele Werte p/q mit |x − p/q| < 1/q2.
Das Korollar war bereits vor dem Satz von Dirichlet innerhalb der von Fermat, Lagrange und Legendre weiterentwickelten Theorie der Kettenbrüche bekannt. Dirichlets Beweis lieferte aber eine einfache neue Methode, die sich zudem auch auf die simultane Approximation von mehreren reellen Zahlen anwenden lässt.
Eine Verschärfung des Ergebnisses bringt später dann der Satz von Hurwitz von 1891: Jede irrationale Zahl ist 1/( · q2)-approximierbar. Einige Beweise dieses Resultats verwenden wieder Kettenbrüche, was den Leser, dem die Wurzel aus 5 aufgefallen ist, nicht überraschen dürfte. Die Konstante im Satz von Hurwitz ist in der Tat dann auch bestmöglich: Der goldene Schnitt (1 + )/2 ist nicht 1/(δ · q2)-approximierbar, falls δ > . Für einen Beweis des Satzes von Hurwitz siehe etwa [ Niven / Zuckerman 1976 ].
Wir notieren das Ergebnis noch einmal in einer anderen Form:
Korollar (Darstellungssatz für irrationale Zahlen)
Sei x irrational, und sei m ∈ ℕ. Dann existieren p ∈ ℤ, q ∈ ℕ+, δ ∈ ℝ mit:
(i) | x = p/q + δ/q2, |
(ii) | q > m, |δ| < 1. |
Wir werden später zeigen, dass für alle x ∈ ℝ die Quadratwurzel von x nicht 1/q3-approximierbar ist.
Übung
Für alle k ≥ 2 existiert ein x ∈ ℝ, das 1/qk-approximierbar ist.