Zahlentheorie: Kettenbrüche, Konvergenz, beste Näherung

20.03.2019, 11:42

Hosenschlange

Zahlentheorie: Kettenbrüche, Konvergenz, beste Näherung

Mahlzeit,

gegeben sei eine nicht quadratische ganze Zahl N > 1, deren Wurzel durch einen Bruch angenähert werden soll. Hierzu ist weiterhin gegeben der größtmögliche Nenner D.

Ich habe mich dem ganzen über reguläre Kettenbrüche genähert. Als Beispiel ist N = 101, D = 50. Dann ist die Kettenbruchentwicklung für N = [10; 20, 20, 20, 20, 20, ..., 20, ...]. Diese Kettenbruchentwicklung treibe ich für das Beispiel so weit, bis der Nenner des zugehörigen Bruchs > D wird. In diesem Beispielfall führt die Entwicklung also zu [10; 20, 20], was in dem Bruch $\begin{eqnarray*} \frac{4030}{401} \end{eqnarray*}$ resultiert. Um das alles nun D anzunähern, durchlaufe ich für den letzten Index in der Kettenbruchentwicklung eine Schleife von 1 bis < (Zahl beim Index), hier also von 1 bis 19. Die ersten daraus resultierenden Brüche sind dann $\begin{eqnarray*} \frac{211}{21}, \frac{412}{41}, \frac{613}{61}, \frac{814}{81}, \frac{1015}{101}, ... \end{eqnarray*}$

Die beste Näherung der Wurzel aus 101, mit dem größtmöglichen Nenner 50, ist also $\begin{eqnarray*} \frac{412}{41} \end{eqnarray*}$ .

Ist das so ungefähr richtig?

20.03.2019, 12:13

HAL 9000

Auf diesen Beitrag antworten »

Es ist ganz klar $\begin{eqnarray*} \left| \frac{201}{20}-\sqrt{101} \right| < \left| \frac{412}{41}-\sqrt{101} \right| \end{eqnarray*}$ . Ich verstehe generell nicht, wieso deine Methode funktionieren soll. verwirrt

20.03.2019, 13:03

Hosenschlange

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Es ist ganz klar $\begin{eqnarray*} \left| \frac{201}{20}-\sqrt{101} \right| < \left| \frac{412}{41}-\sqrt{101} \right| \end{eqnarray*}$ . Ich verstehe generell nicht, wieso deine Methode funktionieren soll. verwirrt

Inwiefern?

Ich hatte diese Methode letztlich aus meinem Wahnsinn heraus probiert Big Laugh

ob sie aber gängig ist und sich generell anwenden lässt, kann ich nicht sagen. Ich hab auch noch keine andere Methode probiert, um sagen zu können, ob 412/41 tatsächlich die beste Näherung in Anbetracht der Vorgaben ist.

20.03.2019, 13:12

HAL 9000

Auf diesen Beitrag antworten »

Was "inwiefern" ? Bestreitest du $\begin{eqnarray*} \left| \frac{201}{20}-\sqrt{101} \right| < \left| \frac{412}{41}-\sqrt{101} \right| \end{eqnarray*}$ und die Konsequenz, dass $\begin{eqnarray*} \frac{201}{20} \end{eqnarray*}$ ein besserer Näherungsbruch als dein $\begin{eqnarray*} \frac{412}{41} \end{eqnarray*}$ ist? Erstaunt1

20.03.2019, 13:15

Hosenschlange

Auf diesen Beitrag antworten »

Keinesfalls. Ich fragte wegen "[...] wieso deine Methode funktionieren soll [...]". Aber ich sehe, worauf du hinaus willst.

20.03.2019, 13:17

HAL 9000

Auf diesen Beitrag antworten »

Naja, wenn ich ein Gegenbeispiel angebe, welches zeigt, dass deine Methode nicht die gesuchte optimale Lösung findet, dann bist du doch in der Erklärungsnot. Sowas beantwortet man doch nicht mit Gegenfragen. Augenzwinkern

EDIT: Achso, du hattest oben was nachträglich ergänzt.

OK, die Kettenbruchnäherungsbrüche seien $\begin{eqnarray*} \frac{p_n}{q_n} \end{eqnarray*}$ . Du suchst nun zu gegebenem $\begin{eqnarray*} D \end{eqnarray*}$ den bestmöglichen Näherungsbruch $\begin{eqnarray*} \frac{p}{q} \end{eqnarray*}$ mit $\begin{eqnarray*} q\leq D \end{eqnarray*}$ . Deine Annahme ist nun die folgende:

Sei $\begin{eqnarray*} \frac{p_n}{q_n} \end{eqnarray*}$ der letzte Näherungsbruch mit $\begin{eqnarray*} q_n\leq D \end{eqnarray*}$ , während für $\begin{eqnarray*} \frac{p_{n+1}}{q_{n+1}} = \frac{a_np_n+p_{n-1}}{a_nq_n+q_{n-1}} \end{eqnarray*}$ bereits $\begin{eqnarray*} q_{n+1}>D \end{eqnarray*}$ gilt. Du nimmst nun von allen Werten $\begin{eqnarray*} \frac{kp_n+p_{n-1}}{kq_n+q_{n-1}} \end{eqnarray*}$ mit $\begin{eqnarray*} k=1,2,\ldots,a_n-1 \end{eqnarray*}$ denjenigen mit der besten Annäherung, der zugleich $\begin{eqnarray*} kq_n+q_{n-1}\leq D \end{eqnarray*}$ erfüllt?

Klingt soweit nicht schlecht, aber das ist nur die beste Annäherung innerhalb dieser $\begin{eqnarray*} k \end{eqnarray*}$ , und das ist nicht notwendig besser als der Ausgangspunkt $\begin{eqnarray*} \frac{p_n}{q_n} \end{eqnarray*}$ dieser Suche - mit dem sollte also auch noch verglichen werden, wie das Beispiel oben zeigt. Wenn ich mich nicht irre dann reicht der Vergleich zwischen eben jenem $\begin{eqnarray*} \frac{p_n}{q_n} \end{eqnarray*}$ mit $\begin{eqnarray*} \frac{kp_n+p_{n-1}}{kq_n+q_{n-1}} \end{eqnarray*}$ für das größtmögliche $\begin{eqnarray*} k \end{eqnarray*}$ , d.h. welches gerade noch $\begin{eqnarray*} kq_n+q_{n-1}\leq D \end{eqnarray*}$ erfüllt, das wäre dann $\begin{eqnarray*} k=\left\lfloor \frac{D-q_{n-1}}{q_n}\right\rfloor \end{eqnarray*}$ .

Nehmen wir für dein Beispiel $\begin{eqnarray*} \sqrt{101} \end{eqnarray*}$ oben die Kettenbrüche $\begin{eqnarray*} \frac{p_1}{q_1}=\frac{10}{1} \end{eqnarray*}$ , $\begin{eqnarray*} \frac{p_2}{q_2}=\frac{201}{20} \end{eqnarray*}$ und $\begin{eqnarray*} \frac{p_3}{q_3}=\frac{4030}{401} \end{eqnarray*}$ als perfekte Näherungsbrüche jeweils für die Fälle $\begin{eqnarray*} D=q_n \end{eqnarray*}$ .

Für $\begin{eqnarray*} D>20 \end{eqnarray*}$ haben wir "neue" Minima für $\begin{eqnarray*} \left| \frac{p}{q}-\sqrt{101}\right| \end{eqnarray*}$ bei $\begin{eqnarray*} q=221,241,261,\ldots,381,401 \end{eqnarray*}$ . Sie alle folgen dem o.g. Schema $\begin{eqnarray*} q = 20k+1 = kq_n+q_{n-1} \end{eqnarray*}$ , aber eben nicht gleich von Start $\begin{eqnarray*} k=1 \end{eqnarray*}$ weg, sondern erst für $\begin{eqnarray*} k\geq 11 \end{eqnarray*}$ . Für $\begin{eqnarray*} k\leq 10 \end{eqnarray*}$ ist also tatsächlich noch der "alte" Wert $\begin{eqnarray*} \frac{p_2}{q_2}=\frac{201}{20} \end{eqnarray*}$ besser. Wenn du diese Modifikation in deinen "Algorithmus" einbaust, dann könnte das ganze aufgehen.

20.03.2019, 14:02

Hosenschlange

Auf diesen Beitrag antworten »

Wow, danke. Das ist ausführlich smile

damit werde ich zweifellos versuchen, mein gesuchtes Ergebnis zu finden und in einen Algorithmus zu quetschen.

Neue Frage »

Antworten »

Zahlentheorie: Kettenbrüche, Konvergenz, beste Näherung

Verwandte Themen