8.2 Fixpunktverfahren
Das Fixpunktverfahren benötigt nur einen Startwert. Die nichtlineare Gleichung, deren Nullstelle gesucht werden soll, muss zunächst in eine Fixpunktgleichung
umgeformt werden. Ihre Lösungen, also x* mit F(x*) = x*, heißen Fixpunkte [Knorrenschild: 19].
Diese Fixpunktgleichung wird in eine Iterationsgleichung umgeformt und rekursiv gelöst:
Die Funktion F wird auch als Schrittfunktion bezeichnet [Engeln-Müllges: 33]. Die Rekursion wird so oft ausgeführt, bis für eine festgelegte Genauigkeit 𝜀 der Wert links vom Zuweisungsoperator xn+1 dem Funktionswert der Iterationsgleichung F(xn) auf der rechten Seite vom Zuweisungsoperator entspricht.
Zusammen mit dem Startwert x0 kann das algorithmische Schema des Fixpunktverfahrens mit den Iterationsschritten
Für das Beispiel der beiden Wachstumsfunktionen
kann durch logarithmieren die Fixpunktgleichung
aufgestellt werden. Anstatt die Nullstelle zu berechnen, wird beim Fixpunktverfahren der Schnittpunkt der Funktion y1 = x (Winkelhalbierende) mit der Funktion y2 = F(x) bestimmt. Fixpunkte sind genau die Stellen, wo der Funktionsgraph die Winkelhalbierende des I. und II. Quadranten schneidet.
Das Nullstellenproblem wird also in ein Fixpunktproblem umgewandelt. Die x-Koordinate des Schnittpunktes entspricht genau der Nullstelle der Funktionsgleichung
Abbildung 8.3 zeigt die Funktionsgraphen der Funktionen y1 = x und der Funktion y2 = 4 ⋅ ln(5x + 1) mit dem markierten Fixpunkt.
Der Schnittpunkt liegt zwischen x1 = 17 und x2 = 20. Einer der beiden Werte kann als Startwert verwendet werden. Im Schnittpunkt von y1 und y2 haben das Argument x* (die Nullstelle) und die beiden Funktionswerte den gleichen Wert. Es gilt also, wie oben behauptet: F(x*) = x*.
Aus Abbildung 8.3 kann abgelesen werden, dass die Steigung in der Umgebung des Schnittpunktes nicht 1 (45°) sein darf. Hätte die Steigung von F in der Umgebung des Schnittpunktes eine Steigung von m = 1, würde der Funktionsgraph von F parallel zur Geraden verlaufen, und es gäbe keinen Schnittpunkt.
Ob das Fixpunktverfahren konvergiert, können Sie mit der sogenannten Kontraktionsbedingung
überprüfen. K ist die Kontraktionskonstante. Sie muss kleiner 1 sein, d. h., der Abstand zwischen F(a) und F(b) muss kleiner sein als der Abstand zwischen a und b. Je kleiner die Kontraktionskonstante ist, desto besser konvergiert das Verfahren gegen den Fixpunkt. Sie kann mit
grob geschätzt werden. Einen genaueren Wert erhält man mit
Abbildung 8.3 Veranschaulichung des Fixpunktverfahrens mit dem Startwert 1
Wenn die Kontraktionskonstante bekannt ist, können die Fehlerschranken berechnet werden. Für die A-priori-Fehlerabschätzung gilt:
Auf der linken Seite der Ungleichung steht die geforderte Genauigkeit 𝜀. Diese obere Fehlerschranke wird aus dem Startwert x0 und dem zweiten Wert der Iteration x1 = F(x0) berechnet.
Mit der A-priori-Abschätzung kann man berechnen, wie viele Iterationen höchstens benötigt werden, um eine vorgegebene Fehlertoleranz 𝜀 zu erreichen. Die Anzahl n der Iterationen wird mit
näherungsweise bestimmt. Für diese Fehlerabschätzung werden nur die Anzahl n sowie der erste und zweite Wert aus der Iteration benötigt. Sie kann also vor der vollständigen Berechnung durchgeführt werden.
Für die Berechnung der A-posteriori-Fehlerabschätzung
werden der letzte xn und der vorletzte Wert xn-1 aus der Iteration benötigt. Diese Fehlerabschätzung kann erst durchgeführt werden, nachdem die Berechnung des Fixpunktes mit der geforderten Genauigkeit abgeschlossen ist. Die rechte Seite der Ungleichung kann als Abbruchkriterium genutzt werden.
Für die unabhängige Variable x werden Werte festgelegt und in die Fixpunktgleichung eingesetzt (Tabelle 8.2). Der Vorgang wird so oft wiederholt, bis in beiden Spalten der Wertetabelle die Werte für eine zuvor festgelegte Genauigkeit übereinstimmen.
|
x |
F(x) = ln(5x + 1) |
|---|---|
|
17 |
17,817389185014 |
|
18 |
18,043438026067 |
|
18,055650172064 |
18,055650172064 |
|
19 |
18,257392765871 |
|
20 |
18,460482067365 |
Tabelle 8.2 Wertetabelle für die Fixpunktiteration
Für das Fixpunktproblem kann mit der vereinfachten Abbruchbedingung |xn-1 – xn| folgender Algorithmus in Pseudocode entwickelt werden:
Funktionsdefinition F(x)
Eingabe x=Startwert, 𝜀 = Genauigkeit
solange |xn-1-xn| > 𝜀:
xn+1=F(xn)
Ausgabe xn
Listing 8.2 berechnet die Nullstelle und die Fehlerschranken der Testfunktion mit dem Fixpunktverfahren. In Zeile 10 können Sie die Genauigkeit der Berechnung vorgeben, und in Zeile 15 können Sie den Startwert ändern.
01 #02_fixpunkt_while.py
02 from math import *
03 #Fixpunktgleichung
04 def F(x):
05 return 4*log(5*x+1)
06 #1. Ableitung
07 def diff1(x):
08 return 20/(5*x + 1)
09 #Hauptprogramm
10 d=6
11 x=18
12 eps=10**-d
13 a,b=17,19
14 m=9
15 x1=F(x)
16 K=round(max(abs(diff1(a)),abs(diff1(b))),4)
17 Ev=K**m*abs(x-x1)/(1-K)
18 xa=n=0
19 print("%2s %8s %15s" %("n","x","F(x)"))
20 while abs(xa-x) > eps and n < 100:
21 xa=x
22 x=F(x)
23 print("%2d %.10f %.10f" %(n,x,F(x)))
24 n=n+1
25 #Fehlerabschätzung
26 En=K/(1.- K)*abs(xa-x)
27 print(" 18.05565017206474 genau")
28 print("A-priori-Fehlerabschätzung ",round(Ev,d+2))
29 print("A-posteriori-Fehlerabschätzung",round(En,d+2))
30 print("Kontraktionskonstante K =",K)
Listing 8.2 Fixpunktverfahren
Ausgabe
n x F(x)
0 18.0434380261 18.0529734704
1 18.0529734704 18.0550636363
2 18.0550636363 18.0555216540
3 18.0555216540 18.0556220123
4 18.0556220123 18.0556440020
5 18.0556440020 18.0556488201
6 18.0556488201 18.0556498758
7 18.0556498758 18.0556501072
8 18.0556501072 18.0556501578
18.05565017206474 genau
A-priori-Fehlerabschätzung 1.1e-07
A-posteriori-Fehlerabschätzung 7e-08
Kontraktionskonstante K = 0.2326
Analyse
In den Zeilen 04 und 05 steht die Fixpunktgleichung. Mit der 1. Ableitung (Zeilen 07 und 08) wird in Zeile 16 die Kontraktionskonstante K berechnet.
Zeile 11 legt den Startwert x fest. Die Anweisungen im Schleifenrumpf werden so lange ausgeführt, wie die Abbruchbedingung abs(xa-x)>eps zutrifft und die Zählvariable n noch nicht den vorgegebenen Wert von 100 erreicht hat. Mit der Konstanten 100 soll eine Endlosschleife verhindert werden.
In der Variablen xa wird jeweils der letzte Wert von x gespeichert (Zeile 21). In Zeile 22 wird der Funktionswert der Fixpunktgleichung F(x) der Variablen x so lange zugewiesen, bis die Abbruchbedingung in Zeile 20 erfüllt ist. In Zeile 24 wird bei jedem neuen Schleifendurchlauf der Wert der Zählvariablen n um 1 erhöht.
Nach neun Iterationen wird die Nullstelle mit der vorgegebenen Toleranz von 𝜀 = 10–6 berechnet. Das Ergebnis stimmt auf sieben Nachkommastellen mit dem genauen Wert überein. Es entspricht also der Voraussage der A-priori-Fehlerabschätzung.
Testen Sie, welchen Einfluss der Startwert (Zeile 11) auf die Anzahl der Iterationen hat. Wählen Sie z. B. Startwerte zwischen 1 und 200.
Bei welchem Exponenten d (Zeile 10) erzeugt das Fixpunktverfahren eine Genauigkeit von acht Nachkommastellen? Vergleichen Sie die Anzahl der Iterationen mit dem Bisektionsverfahren.
Das Fixpunktverfahren konvergiert zwar schneller als das Bisektionsverfahren. Es hat aber auch nur eine lineare Konvergenzgeschwindigkeit. Das wirft die Frage auf, ob es ein Verfahren gibt, das schneller konvergiert.