Annäherung einer reellen Zahl um einen Bruchteil von einer Seite

Question

Annäherung einer reellen Zahl um einen Bruchteil von einer Seite

Ungleichheit
Mathematik
Zahlentheorie
diophantische Näherung

Mischa Lawrow

Der Approximationssatz von Dirichlet sagt uns das für jede reelle Zahl $\alpha$ , haben wir eine Folge von rationalen Approximationen von $\alpha$ die gut dafür sind, wie groß ihr Nenner ist. Genauer: gegeben eine ganze Zahl $N \ge 1$ , gibt es eine rationale Zahl $\frac pq$ mit $1 \le q \le N$ so dass

| a - \frac{P}{Q} | < \frac{1}{Q N} .

$\left|\alpha - \frac pq\right| < \frac1{qN}.$

(Dieser Fehler ist kleiner als $\frac1{q^2}$ , und der Satz von Roth sagt uns, dass für algebraische Zahlen der Exponent hier am besten möglich ist.)

Die absoluten Werte sagen uns, dass der Bruch $\frac pq$ wird entweder etwas kleiner oder etwas größer sein als $\alpha$ . Was ist, wenn ich angeben möchte, um welches es sich handelt? Angenommen, ich möchte finden $\frac pq$ so dass

\frac{P}{Q} < a < \frac{P}{Q} + ϵ .

$\frac pq < \alpha < \frac pq + \epsilon.$ Wie klein kann ich machen

ϵ

$\epsilon$ (bezüglich

q

$q$ , oder möglicherweise einige zusätzliche Parameter

N

$N$ wie oben)?

Ich mache mir ein bisschen Sorgen, wenn es um Zahlen wie die Liouville-Konstante geht $L = \sum_{k=1}^\infty 10^{-k!}$ , die extrem gute Annäherungen hat (durch Abschneiden der Reihe), aber alle von unten; ähnlich, $1-L$ wird sehr gute Annäherungen haben, aber alle von oben.

Peter

Wenn „große“ Einträge in der einfachen Kettenbruchzerlegung nur an geraden oder nur an ungeraden Stellen vorkommen, haben wir keine „sehr guten“ Näherungen von beiden Seiten.

Peter

Aber man kann von beiden Seiten beliebig nahe an die Zahl herankommen, wenn man sich nicht darum kümmert, wie gut diese Näherung im Vergleich zur Größe des Nenners ist.

Mischa Lawrow

Beides gute Punkte, aber ich möchte quantifizieren, wie gut die Annäherungen sind, die wir erhalten können. So zum Beispiel der naive Ansatz des Sagens

α \approx \frac{⌊ q α ⌋}{q}

$\alpha \approx \frac{\lfloor q\alpha \rfloor}{q}$ sagt uns, dass wir immer Annäherungen mit höchstens Fehlern erhalten können

\frac{1}{q}

$\frac1q$ .

Peter

Vielleicht ist das hilfreich: en.wikipedia.org/wiki/Hurwitz%27s_theorem_(number_theory)

Mischa Lawrow

Können Sie das näher erläutern? Ich verstehe nicht, wie die Grenze die Möglichkeit ausschließt, dass es unendlich viele Brüche darüber gibt

α

$\alpha$ mit Fehler

O (\frac{1}{q^{2}})

$O(\frac1{q^2})$ , aber keine oder nur wenige darunter

α

$\alpha$ .

Peter

Ein guter Punkt, an den ich nicht gedacht habe! Aber wenn Sie mit einem Fehler kleiner als sicher sind

\frac{1}{q^{2}}

$\frac{1}{q^2}$ , dann erledigt jede Konvergente die Arbeit. Diese Grenze kann also definitiv von beiden Seiten erreicht werden. Intuitiv würde ich sagen, dass die Hurwitz-Grenze von beiden Seiten unendlich oft erreicht werden kann, aber ich gebe zu, dass ich es nicht beweisen kann.

Aravind

Sagen

p > q

$p>q$ , Und

g c d (p, q) = 1

$gcd(p,q)=1$ (wir können dies nicht garantieren) und

p / q < α

$p/q<\alpha$ . Schreibe jetzt

q r - p s = 1

$qr-ps=1$ mit

r, s

$r,s$ klein Dann

\frac{r}{s} - \frac{p}{q} = \frac{1}{q s}

$\dfrac{r}{s}-\dfrac{p}{q}=\dfrac{1}{qs}$ Und

r / s

$r/s$ könnte mit einem kleinen Fehler als Obergrenze funktionieren.

Aravind

Eine andere Idee besteht darin, zuerst mit einem sehr großen Nenner (in Bezug auf das ursprüngliche N) zu approximieren und ihn dann auf beiden Seiten zu verkleinern.

Peter

@Aravind Die Kettenbruchmethode findet solche Brüche tatsächlich quetschend

α

$\alpha$ und die Baugarantien

g c d (p, q) = 1

$gcd(p,q)=1$ . Also ein Fehler kleiner als

\frac{1}{q^{2}}

$\frac{1}{q^2}$ von beiden Seiten kann immer für jede irrationale Zahl erreicht werden. Außerdem gibt es unendlich viele solcher Brüche für beide Seiten, weil die Brüche abwechselnd unten und oben sind

α

$\alpha$ .

Aravind

@Peter, ja Konvergente fortgesetzter Brüche wechseln sich auf beiden Seiten ab. Ich habe nur versucht, eine Annäherung an eine andere zu bekommen. Kommt der Satz von Hurwitz auch aus Kettenbrüchen?

Peter

@Aravind Ja, das tut es. Aus

3

$3$ aufeinanderfolgende Konvektionen, mindestens eine hat einen Fehler kleiner als

\frac{1}{\sqrt{5} q^{2}}

$\frac{1}{\sqrt{5}q^2}$ . Wenn wir nur zwei aufeinanderfolgende Konvergenten haben, hat mindestens einer einen Fehler kleiner als

\frac{1}{2 q^{2}}

$\frac{1}{2q^2}$ , aber das bedeutet nicht notwendigerweise, dass wir solche Annäherungen von unten UND oben haben.

Antworten (1)

Annäherung einer reellen Zahl um einen Bruchteil von einer Seite

Wenn „große“ Einträge in der einfachen Kettenbruchzerlegung nur an geraden oder nur an ungeraden Stellen vorkommen, haben wir keine „sehr guten“ Näherungen von beiden Seiten.
Aber man kann von beiden Seiten beliebig nahe an die Zahl herankommen, wenn man sich nicht darum kümmert, wie gut diese Näherung im Vergleich zur Größe des Nenners ist.
Beides gute Punkte, aber ich möchte quantifizieren, wie gut die Annäherungen sind, die wir erhalten können. So zum Beispiel der naive Ansatz des Sagens $\alpha \approx \frac{\lfloor q\alpha \rfloor}{q}$ sagt uns, dass wir immer Annäherungen mit höchstens Fehlern erhalten können $\frac1q$ .
Vielleicht ist das hilfreich: en.wikipedia.org/wiki/Hurwitz%27s_theorem_(number_theory)
Können Sie das näher erläutern? Ich verstehe nicht, wie die Grenze die Möglichkeit ausschließt, dass es unendlich viele Brüche darüber gibt $\alpha$ mit Fehler $O(\frac1{q^2})$ , aber keine oder nur wenige darunter $\alpha$ .
Ein guter Punkt, an den ich nicht gedacht habe! Aber wenn Sie mit einem Fehler kleiner als sicher sind $\frac{1}{q^2}$ , dann erledigt jede Konvergente die Arbeit. Diese Grenze kann also definitiv von beiden Seiten erreicht werden. Intuitiv würde ich sagen, dass die Hurwitz-Grenze von beiden Seiten unendlich oft erreicht werden kann, aber ich gebe zu, dass ich es nicht beweisen kann.
Sagen $p>q$ , Und $gcd(p,q)=1$ (wir können dies nicht garantieren) und $p/q<\alpha$ . Schreibe jetzt $qr-ps=1$ mit $r,s$ klein Dann $\dfrac{r}{s}-\dfrac{p}{q}=\dfrac{1}{qs}$ Und $r/s$ könnte mit einem kleinen Fehler als Obergrenze funktionieren.
Eine andere Idee besteht darin, zuerst mit einem sehr großen Nenner (in Bezug auf das ursprüngliche N) zu approximieren und ihn dann auf beiden Seiten zu verkleinern.
@Aravind Die Kettenbruchmethode findet solche Brüche tatsächlich quetschend $\alpha$ und die Baugarantien $gcd(p,q)=1$ . Also ein Fehler kleiner als $\frac{1}{q^2}$ von beiden Seiten kann immer für jede irrationale Zahl erreicht werden. Außerdem gibt es unendlich viele solcher Brüche für beide Seiten, weil die Brüche abwechselnd unten und oben sind $\alpha$ .
@Peter, ja Konvergente fortgesetzter Brüche wechseln sich auf beiden Seiten ab. Ich habe nur versucht, eine Annäherung an eine andere zu bekommen. Kommt der Satz von Hurwitz auch aus Kettenbrüchen?
@Aravind Ja, das tut es. Aus $3$ aufeinanderfolgende Konvektionen, mindestens eine hat einen Fehler kleiner als $\frac{1}{\sqrt{5}q^2}$ . Wenn wir nur zwei aufeinanderfolgende Konvergenten haben, hat mindestens einer einen Fehler kleiner als $\frac{1}{2q^2}$ , aber das bedeutet nicht notwendigerweise, dass wir solche Annäherungen von unten UND oben haben.

Mischa Lawrow · Answer 1

Um die Antworten in den Kommentaren zusammenzufassen:

Eine quantitativere Version des Näherungssatzes von Dirichlet ist der Satz von Hurwitz ( Wikipedia-Link ), der die Existenz unendlich vieler Näherungen garantiert $\frac pq$ so dass

| a - \frac{P}{Q} | < \frac{1}{\sqrt{5} Q^{2}},

$\left|\alpha - \frac{p}{q}\right| < \frac1{\sqrt 5\,q^2},$ das ist eng: für einige

α

$\alpha$ , gibt es keine bessere Näherung. Darüber hinaus können diese Annäherungen durch Abschneiden der fortgesetzten Brucherweiterung von gefunden werden

α

$\alpha$ .

Dies allein garantiert uns noch nicht, auf welcher Seite sich die Annäherung befindet. Allerdings konvergiert der Kettenbruch $\frac{h_n}{k_n}$ erfüllen

\frac{H_{2 N}}{k_{2 N}} < a < \frac{H_{2 N + 1}}{k_{2 N + 1}}

$\frac{h_{2n}}{k_{2n}} < \alpha < \frac{h_{2n+1}}{k_{2n+1}}$ und auch

| a - \frac{H_{N}}{k_{N}} | < \frac{1}{k_{N} k_{N + 1}} .

$\left|\alpha - \frac{h_n}{k_n}\right| < \frac1{k_n k_{n+1}}.$ (Siehe zB diesen Link .) Die geraden Konvergenten geben uns also eine enge Annäherung von unten:

\frac{H_{2 N}}{k_{2 N}} < a < \frac{H_{2 N}}{k_{2 N}} + \frac{1}{k_{2 N}^{2}} .

$\frac{h_{2n}}{k_{2n}} < \alpha < \frac{h_{2n}}{k_{2n}} + \frac1{k_{2n}^2}.$ In ähnlicher Weise geben uns die ungeraden Konvergenten eine enge Annäherung von oben.

Asymptotisch ist dies der beste Fehler, auf den wir hoffen können. Wir könnten hoffen, die Konstante weiter zu verbessern $\frac{1}{q^2}$ um es dem Satz von Hurwitz näher zu bringen. Experimentell scheint es jedoch die Konstante von zu sein $1$ ist eigentlich am besten möglich. Wenn ich nehme $\alpha$ der unendliche fortgesetzte Bruch sein

a = 1 + \frac{1}{100 + \frac{1}{1 + \frac{1}{100 + \frac{1}{⋱}}}} = \frac{5 + \sqrt{26}}{10}

$\alpha = 1 + \frac{1}{100 + \frac1{1 + \frac1{100 + \frac1{\ddots}}}} = \frac{5 + \sqrt{26}}{10}$ dann ergeben die konvergenten Kettenbrüche Fehler von

\approx \frac{0.98}{q^{2}}

$\approx \frac{0.98}{q^2}$ von einer Seite u

\approx \frac{0.0098}{q^{2}}

$\approx \frac{0.0098}{q^2}$ zum anderen: Wir bezahlen gute Annäherungen von unten mit schlechten Annäherungen von oben.

Dies ist kein Beweis, weil ich nichts über die Qualität anderer, nicht kontinuierlicher Bruchnäherungen gesagt habe $\frac{5 + \sqrt{26}}{10}$ . Aber es deutet sehr darauf hin, wie die Antwort lauten könnte, nicht wahr?

Annäherung einer reellen Zahl um einen Bruchteil von einer Seite

Mischa Lawrow

Peter

Peter

Mischa Lawrow

Peter

Mischa Lawrow

Peter

Aravind

Aravind

Peter

Aravind

Peter

Antworten (1)

Mischa Lawrow

Beziehung zwischen Dirichlets Approximationssatz und Konvergenten

Welche Mindestzahl (A) kann genommen werden, damit (A)^N größer ist als das Produkt von N Zahlen?

Primitiver pythagoreischer Dreifachgenerator

Beweisen Sie diese Identität mit der Triple Product Identity von Jacobi

Gibt es beliebig lange Primzahllücken, in denen jede Zahl mindestens drei verschiedene Primfaktoren hat?

Ist diese Intervallnotation zur Lösung eines Ungleichungsproblems korrekt?

Einfacher Beweis basierend auf Ungleichungen [geschlossen]

Beweis eines geringfügigen Anspruchs im Zusammenhang mit der Twin Primes-Vermutung

Grenzen für ein unendliches Produkt beweisen

Ein Beweis, dass Zweierpotenzen nicht als Summe mehrerer aufeinanderfolgender positiver Ganzzahlen ausgedrückt werden können, die binäre Darstellungen verwenden?