Nichtlineare Gleichungen

Ein wichtiges Problem in der Praxis ist die Bestimmung einer Lösung x der Gleichung
f(x)  = 0   ,
(1)
d.h. das Aufsuchen einer Nullstelle x einer (nicht notwendig linearen) Funktion f. Ist f(x) ein Polynom, so heißt die Gleichung (1) algebraisch , ansonsten transzendent . Da man nur selten eine Lösung von (1) in endlich vielen Schritten explizit berechnen kann, ist man im allg. auf Näherungsmethoden (Einschlußverfahren, Iterationsverfahren ) angewiesen.


Das Bisektionsverfahren (Intervallhalbierung)

Ist f stetig auf [a,b] und haben f(a) und f(b) entgegengesetzte Vorzeichen (f(a) f(b) < 0), so existiert nach dem Zwischenwertsatz mindestens ein x (a,b) mit f(x) = 0. Man halbiert nun das Intervall [a,b] und stellt über das Vorzeichen von f am Mittelpunkt fest, ob die gesuchte Nullstelle in der linken oder in der rechten Hälfte des Ausgangsintervalls zu finden ist. Man behält jene Hälfte, auf der das Vorzeichen von f wechselt. Dieses Verfahren wird fortgesetzt, bis eine Nullstelle im Inneren eines hinreichend kleinen Intervalls liegt:

1. xi+1  := [(ai + bi)/2] :i = 0, 1, 2, und a0 = a,   b0 = b
2. falls   f(ai) f(xi+1) < 0 :setze ai+1 = ai und bi+1 = xi+1
andernfalls :setze ai+1 = xi+1 und bi+1 = bi
3. falls | bi+1 - ai+1 |    tol :Abbruch
andernfalls :gehe zu Schritt 1


Nach n Halbierungen liegt eine Nullstelle x sicher in einem Intervall der Länge (b - a) / 2n, und man erhält die Fehlerabschätzung
en  := | xn - x|    (b - a) / 2n   .
Damit ist en+1 [ 1/2] en. Pro Iterationsschritt verkleinert sich der Fehler um einen konstanten Faktor. Es werden also stets etwa gleich viele Iterationsschritte benötigt, um den Fehler auf einen bestimmten Bruchteil zu reduzieren: Man sagt, das Verfahren sei linear konvergent . Wegen 1/210 = 1 / 1024 10-3 gilt die Faustregel, daß man mit je 10 Halbierungsschritten etwa 3 Dezimalstellen an Genauigkeit für die Lösung gewinnt.

Vorteile :Konvergenz ist garantiert
nur 1 Funktionsauswertung pro Iteration
Nachteile:relativ langsame Konvergenz
funktioniert nur für 1D-Probleme


bisect.png

Abbildung 1: Bisektionsverfahren.


Fixpunktiteration (Methode der sukzessiven Approximation)

Hier wird das Nullstellenproblem f(x) = 0 in ein äquivalentes Fixpunktproblem
x  = j(x)
(2)
mit einer geeigneten Iterationsfunktion j umformuliert. Jede Nullstelle x von f(x) ist dann ein Fixpunkt von j(x), also eine Stelle x, welche durch j auf sich selbst abgebildet wird (fix bleibt). Anschaulich beschreibt (2) die Schnittpunkte von y(x) = x mit j(x). Bei der Wahl von j hat man gewisse Freiheiten, eine kann zum Erfolg, eine andere zum Scheitern führen. Ausgehend von einem geeigneten Startwert x0 wird mit der Iterationsvorschrift
xi+1  := j(xi)
(3)
für i = 0, 1, 2, eine Folge {xi} von Näherungswerten berechnet, von der man hofft, daß sie gegen die gesuchte Lösung x konvergiert.



Beispiel: Ist etwa die Gleichung f(x) : = x - cosx = 0 zu lösen, so liegt es nahe, die Iterationsvorschrift xi+1 = cosxi, also j(x) : = cosx zu verwenden. Man erhält eine alternierend konvergente Folge {xi} von Näherungswerten an x (die Iteration verläuft in einem ``Käfig''). Diese Iteration läßt sich leicht auf einem Taschenrechner durch wiederholtes Drücken der cos-Taste erzeugen: Egal, mit welchem Wert man beginnt, nach einigen Schritten erscheint immer die gleiche Zahl.

fpicos.png

Abbildung 2: Iterationskäfig für j(x) = cosx.



Bezüglich der Konvergenz des Iterationsverfahrens liefert der folgende Kontraktionssatz eine hinreichende Konvergenzbedingung:

Kontraktionssatz (Fixpunktsatz von Banach)
Ist j: I I eine kontrahierende Selbstabbildung eines abgeschlossenen Intervalls I in sich mit
| j(x) - j(y)|    L  |x - y|        " x, y I
und einer Kontraktionskonstante (Lipschitz-Konstante) 0 L < 1, so gilt:
(a) j besitzt in I genau einen Fixpunkt x = j(x).
(b) Die Iterationsfolge xi+1 = j(xi) konvergiert für jeden Startwert x0 I
gegen x.
(c) Es gilt die (a priori) Fehlerabschätzung
|xn - x|    [(Ln)/(1 - L)]  |x1 - x0| .
(d) Das Verfahren konvergiert zumindest linear, d.h.
en+1    L  en.


Anmerkungen:

fpimk.png

Abbildung 3: Monotone Konvergenz.

fpimd.png

Abbildung 4: Monotone Divergenz.

fpiad.png

Abbildung 5: Alternierende Divergenz.


Das Newton-Verfahren

Die Funktion f sei genügend oft stetig differenzierbar und besitze im Intervall (a,b) eine einfache Nullstelle x, d.h. f(x) = 0 und f(x) 0. Sei xi schon eine gute Näherung für eine Nullstelle x. Um zu einer besseren Näherung zu gelangen, ersetzt man die (nichtlineare) Funktion f durch ihre Tangente im Punkt (xi, f(xi)),
t(x)  := f(xi) + f(xi) (x - xi)   ,
(4)
und nimmt die Nullstelle von t(x) als neue Näherung xi+1 für x (Abbildung 6):
0 = f(xi) + f(xi) (xi+1 - xi)   .
Dies führt für i = 0, 1, 2, auf die Iterationsvorschrift (Newton-Raphson-Verfahren )
xi+1  := xi -  f(xi)

f(xi)
    .
(5)

newton.png

Abbildung 6: Newton-Verfahren.

t(x) in Gleichung (4) ist nichts anderes als der lineare Anteil der Taylor-Entwicklung von f um xi. Diese Linearisierung ist der entscheidende Schritt des Newton-Verfahrens: Die Lösung einer nichtlinearen Gleichung f(x) = 0 wird durch eine Folge von Lösungen linearer Gleichungen ersetzt bzw. approximiert.

Formal gehört das Newton-Verfahren zur Klasse der Fixpunktiterationen mit
j(x)  := x -  f(x)

f(x)
    .
(6)
Falls der Startwert x0 in (5) eine hinreichend gute Anfangsnäherung für x ist, so ist das Verfahren (lokal) mindestens quadratisch konvergent, d.h.
en+1    C  e2n     .
Ist der Fehler en = | xn - x| von der Größenordnung 10-k, so ist der nächste Fehler en+1 = | xn+1 - x| von der Größenordnung 10-2k (falls C von der Größenordnung 1 ist). Bei jedem Iterationsschritt wird also die Anzahl der mit x übereinstimmenden Dezimalstellen ungefähr verdoppelt. Diese rasche Konvergenz ist der Grund für die große Beliebtheit des Newton-Verfahrens. Die Konvergenz des Verfahrens hängt jedoch empfindlich von der Wahl eines guten Startwertes x0 ab, insbesondere reagiert das Verfahren empfindlich auf lokale Extrema von f, da die Iterationsfunktion j(x) (Gleichung (6)) dort singulär wird. Bei mehrfachen Nullstellen konvergiert das Newton-Verfahren nur noch linear .

Vorteile :rasche (mind. quadratische) Konvergenz bei einfachen Nullstellen
läßt sich auf Systeme nichtlinearer Gleichungen übertragen
Nachteile:in jedem Schritt muß f und f berechnet werden
das Verfahren muß nicht konvergieren



Beispiel: Die m-te Wurzel a1/m aus einer positiven reellen Zahl a > 0 ist Lösung der Gleichung
xm - a  = 0     .
Das Newton-Verfahren ergibt mit f(x) = xm - a , f(x) = m xm-1 die Vorschrift (i = 0, 1, 2, )
xi+1  = xi -  xmi - a

m xm-1i
 =   a + (m-1)xmi

m xm-1
    ,

xi+1  :=   1

m


 a

xm-1i
 +  (m - 1)  xi

    .
(7)
Daraus leiten sich folgende Spezialfälle ab:

(a) m = 2 : xi+1 = [ 1/2] ( [ a/(xi)] + xi ) ,Quadratwurzel von a .
(b) m = -1 : xi+1 = ( 2 - a xi )  xi ,Kehrwert von a .
Die Iteration (a) ist das (schon den Babyloniern bekannte) Heron-Verfahren zur Quadratwurzelbestimmung. Die Iteration (b) ermöglichte für die ersten Computer ohne eingebaute Division die Zurückführung dieser Operation auf Multiplikationen und Subtraktionen.


File translated from TEX by TTH, version 3.06.
On 18 Jun 2004, 19:43.