Algorithmensammlung: Zahlentheorie: Goldener Schnitt

Definition des Goldenen Schnittes

Gesucht werden zwei Zahlen für die folgende Gleichung gilt:

$\frac{a}{b}=\frac{(a+b)}{a}$

Das Verhältnis der beiden Zahlen ist der Vorlage:W. Das Verhältnis beider Zahlen ist ein konstanter Wert, der ungefähr 1,6 beträgt. Die größere Zahl ist etwa 1,6 mal so groß wie die kleinere Zahl.

Durch Umformung und Einsetzen von $\mathrm{\Phi }=\frac{a}{b}$ erhält man

$\mathrm{\Phi }=\frac{a}{b}=1+\frac{b}{a}=1+\frac{1}{\mathrm{\Phi }}$.

Damit ist

${\mathrm{\Phi }}^2-\mathrm{\Phi }-1=0$.

Die Goldene Zahl $\mathrm{\Phi }$ kann also als positive Lösung dieser quadratische Gleichung angesehen werden:

$\frac{a}{b}=\mathrm{\Phi }=\frac{1+\sqrt{5}}{2}\approx 1,61803399$.

Der Vorlage:W hat einige besondere Eigenschaften und findet sich beispielsweise im gleichseitigen Vorlage:W.

Konstruktion des Fünfecks mit dem Goldenen Schnitt

Zur Berechnung kann das Newtonverfahren auf die obengenannte quadratische Gleichung angewandt werden, bis die gewünschte Genauigkeit erreicht ist:

$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}=x_n-\frac{x_n^2-x_n-1}{2x_n-1}$; dabei wird als Startwert $x_0$ ein Schätzwert genommen, z.B. $x_0=1,6$.

Pseudocode:

x = 1.6
while |x^2 - x - 1| > 1e-10
    x = x - (x^2 - x - 1)/(2*x - 1)

Python

# Getestet unter Python 3.6, sollte aber unter allen 3.x-Versionen laufen

# Berechnung der goldenen Zahl mit dem Newtonverfahren 
def golden_ratio(epsilon=1e-10):
    x = 1.6
    y = 1
    while abs(y) > epsilon:
        y = (x**2 - x - 1)/(2*x - 1)
        x -= y
    return x