Algorithmensammlung: Zahlentheorie: Goldener Schnitt

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 Goldene Schnitt. 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 $\Phi ={\frac {a}{b}}$ erhält man

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

Damit ist

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

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

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

Der Goldene Schnitt hat einige besondere Eigenschaften und findet sich beispielsweise im gleichseitigen Fünfeck.

**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'(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[Bearbeiten]

# 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