Bisektion mit Medianten

31.08.2022, 18:25

Finn_

Bisektion mit Medianten

Heute habe ich ein wenig klamüsert, wie sich rationale Nullstellen ermitteln lassen. Da bin ich auf einen Glücksfall gestoßen.

Definition (Mediante). Seien $\begin{eqnarray*} a,b \end{eqnarray*}$ mit $\begin{eqnarray*} a<b \end{eqnarray*}$ rationale Zahlen. Seien $\begin{eqnarray*} p_1/q_1=a \end{eqnarray*}$ und $\begin{eqnarray*} p_2/q_2=b \end{eqnarray*}$ ihre gekürzten Darstellungen. Die Mediante von $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ ist definiert als die Zahl

$\begin{eqnarray*} \frac{p_1+p_2}{q_1+q_2}. \end{eqnarray*}$

Vermutung. Es seien $\begin{eqnarray*} a,b \end{eqnarray*}$ mit $\begin{eqnarray*} a<b \end{eqnarray*}$ rationale Zahlen. Die Funktion $\begin{eqnarray*} f \end{eqnarray*}$ sei streng monoton auf dem Intervall $\begin{eqnarray*} [a,b] \end{eqnarray*}$ und besitze in diesem eine rationale Nullstelle. Modifiziert man das Bisektionsverfahren dergestalt, dass anstelle des arithmetischen Mittels die Mediante berechnet wird, dann erreicht das Verfahren nach einer endlichen Anzahl von Schritten den exakten Wert der Nullstelle.

31.08.2022, 18:54

URL

Auf diesen Beitrag antworten »

RE: Bisektion mit Medianten
Das erinnert mich an Stern-Brocot. Jörn Loviscach hat dazu ein schönes, wenn auch etwas langatmiges Video gemacht.

31.08.2022, 18:59

G310822

Auf diesen Beitrag antworten »

RE: Bisektion mit Medianten

Zitat:

. Jörn Loviscach hat dazu ein schönes,

Das Mann hat die schlimmste Sauklaue bei seinen Schmiereien, die
ich im Netz je gesehen habe. Ein Zumutung!
Zudem wirkt er sehr selbstverliebt.

02.09.2022, 13:02

Finn_

Auf diesen Beitrag antworten »

Umsetzung des Verfahrens. Das Programm ran.py findet rationale Nullstellen rationaler Funktionen. Zur Aufspürung von Nullstellen ohne Vorzeichenwechsel werden zusätzlich die Nullstellen der ersten Ableitung in Betracht gezogen, die vermittels dualer Zahlen berechnet wird.

[attach]55892[/attach]

02.09.2022, 14:06

HAL 9000

Auf diesen Beitrag antworten »

Klingt interessant, auch wenn ich keine Ahnung hab, wie man das beweisen könnte. Da du von "Vermutung" sprichst gehe ich mal davon aus, dass deine Versuche bisher auch zu keinem Erfolg geführt haben, oder?

Klar ist mir bisher nur, dass die Struktur der Funktion selbst an sich völlig egal ist, nur deren Nullstelle zählt - was angesichts des Verfahrens ja offensichtlich ist.

02.09.2022, 16:42

Finn_

Auf diesen Beitrag antworten »

Nun ja, mehr oder weniger prokrastiniert. Es geht ja darum, dass die binäre Suche im Stern-Brocot-Baum in einer endlichen Zahl von Schritten zum Ende kommt, oder anders ausgedrückt dass der Stern-Brocot-Baum jede rationale Zahl zwischen den Grenzen genau einmal enthält. Die Untersuchung dazu ist offenbar bereits allgemein bekannt, wobei allerdings nur der Spezialfall des Intervalls $\begin{eqnarray*} (0,\infty) \end{eqnarray*}$ oder $\begin{eqnarray*} (0,1) \end{eqnarray*}$ betrachtet wird. Ich musste überraschend feststellen, dass die Untersuchung auch in Concrete Mathematics auf S. 116 (zweite Auflage) im Abschnitt Relative Primality aufgeführt ist. Die Erläuterung findet man, wie von URL angemerkt, auch bei Loviscach im Gastbeitrag Zahlen mit möglichst einfachen Brüchen nähern, nach Stern-Brocot von Harald Bögeholz und im Artikel Stern-Brocot Tree in Cut The Knot.

Es findet sich der Ansatz, dass die Mediante eine Art von Mittelwert darstellt und konsekutive rationale Zahlen $\begin{eqnarray*} m/n \end{eqnarray*}$ und $\begin{eqnarray*} m'/n' \end{eqnarray*}$ die Invariante $\begin{eqnarray*} m'n-mn'=1 \end{eqnarray*}$ erfüllen. Der anschließende Trick zeigt dann sogar, dass jede positive rationale Zahl in gekürzter Darstellung $\begin{eqnarray*} a/b \end{eqnarray*}$ in maximal $\begin{eqnarray*} a+b \end{eqnarray*}$ Schritten erreicht wird.

Kleiner Notationskonflikt, es bezeichne $\begin{eqnarray*} (a,b) \end{eqnarray*}$ wieder ein Intervall mit rationalen Grenzen. Man kann sich ja mit der Transformation $\begin{eqnarray*} (a,b)\to (0,1) \end{eqnarray*}$ mit $\begin{eqnarray*} x\mapsto\tfrac{x-a}{b-a} \end{eqnarray*}$ aus der Affäre ziehen. Meine Erwägung wäre, die Transformation im Verfahren rückgängig zu machen. Eventuell gelingt es zu zeigen, dass sich dies nicht pathologisch verhält.

02.09.2022, 17:47

HAL 9000

Auf diesen Beitrag antworten »

Danke für die Links. Damit ist der Beweis auch für deine Vermutung, wo ja zunächst nur $\begin{eqnarray*} p_2q_1-p_1q_2\geq 1 \end{eqnarray*}$ statt $\begin{eqnarray*} p_2q_1-p_1q_2=1 \end{eqnarray*}$ gilt, kein größeres Problem mehr.

Neue Frage »

Antworten »

Bisektion mit Medianten

Verwandte Themen