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:

Nach n Halbierungen liegt eine Nullstelle x sicher in einem Intervall der Länge (b - a) / 2ⁿ, und man erhält die Fehlerabschätzung

en  := | xn - x|   £  (b - a) / 2n   .

Damit ist e_n+1 » [ 1/2] e_n. 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/2¹⁰ = 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

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 x₀ wird mit der Iterationsvorschrift

xi+1  := j(xi)

(3)

für i = 0, 1, 2, ¼ eine Folge {x_i} 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 x_i+1 = cosx_i, also j(x) : = cosx zu verwenden. Man erhält eine alternierend konvergente Folge {x_i} 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.

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.

• Da I sehr klein sein kann, hat der Kontraktionssatz oft nur lokalen Charakter, d.h. für eine Konvergenz des Verfahrens muß der Startwert x₀ hinreichend nahe bei der Lösung x liegen.
• j ist auf I genau dann eine Kontraktion, wenn |j¢(x)| < 1 für alle x Î I gilt (Mittelwertsatz der Differentialrechnung):
  

  0 £ j¢ < 1 :	{xi} konvergiert monoton (Abbildung 3).
  -1 < j¢ < 0 :	{xi} konvergiert alternierend (Abbildung 2).

• Das Iterationsverfahren kann leicht auf n-dimensionale Probleme (d.h. auf Systeme von nichtlinearen Gleichungen) verallgemeinert werden.
• Rundungsfehler werden beim Iterationsverfahren nicht akkumuliert. Das Verfahren ``vergißt'' die früheren Rundungsfehler, da jeder Schritt als ein erster Schritt angesehen werden kann.

Abbildung 3: Monotone Konvergenz.

Abbildung 4: Monotone Divergenz.

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 x_i 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 (x_i, f(x_i)),

t(x)  := f(xi) + f¢(xi) (x - xi)   ,

(4)

und nimmt die Nullstelle von t(x) als neue Näherung x_i+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)

Abbildung 6: Newton-Verfahren.

t(x) in Gleichung (4) ist nichts anderes als der lineare Anteil der Taylor-Entwicklung von f um x_i. 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 x₀ 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 e_n = | x_n - x| von der Größenordnung 10^-k, so ist der nächste Fehler e_n+1 = | x_n+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 x₀ 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 a^1/m aus einer positiven reellen Zahl a > 0 ist Lösung der Gleichung

xm - a  = 0     .

Das Newton-Verfahren ergibt mit f(x) = x^m - a , f¢(x) = m x^m-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: