Download pdf - Kapitel 17 Numerisches L¨osen von Gleichungenweth0002/buecher/mathe/downloads/kap17.pdf · 17.1 Intervallhalbierungs-Methode 5 17.1 Intervallhalbierungs-Methode 17.1 Grundlage fur¨

17Kapitel 17

Numerisches Losen von Gleichungen

(C) Thomas Westermann Mathematik für Ingenieure (Springer-Verlag) 2018

17

17 Numerisches Losen von Gleichungen . . . . . . . . . . . . . . . . . 5

17.1 Intervallhalbierungs-Methode .................................. 5

17.2 Pegasus-Verfahren ............................................... 12

17.3 Banachsches Iterationsverfahren .............................. 16

17.4 Anwendung des Banach-Verfahrens .......................... 24

17.4.1 1-dimensionaler Fall.............................................. 26

17.4.2 2-dimensionales 2-Federn-Masse-Problem .................. 27

17.5 Newton-Verfahren ................................................ 29

17.6 Regula falsi ........................................................ 34

17.7 Bestimmung von Polynom-Nullstellen........................ 35

17.8 Zusammenstellung der MAPLE-Prozeduren ................. 38

17.9 Aufgaben zum numerischen Losen von Gleichungen ...... 39


17 Numerisches Losen von Gleichungen

Dieses Kapitel behandelt numerische Aspekte der Mathematik. Eines der zentralen

Probleme in der angewandten Mathematik ist das Losen von nichtlinearen Glei-

chungen der Form

f (x) = 0.

Obwohl dieses Problem in Maple durch einen Befehl

> fsolve (f(x) = 0, x);

gelost wird, stellen wir dennoch Methoden und Algorithmen zur Losung vor, da die

Interpretation der numerischen Ergebnisse einen tieferen Einblick in die Mathema-

tik der naherungsweisen Berechnung von Nullstellen liefert. Nachdem die Verfahren

eingefuhrt und die Algorithmen angegeben sind, wird auch auf die Realisierung mit

Maple eingegangen. Die Intention dieses Kapitels ist, ein Verstandnis fur die nume-

rische Rechnung mit dem Rechner herzustellen.

Hinweis: Auf der CD-Rom befinden sich samtliche Maple-Prozeduren.

Anwendungsbeispiel CD.1 (Kettenkarussell).

Ein Kettenkarussell mit einer Tragstange von r =

Abb. 17.1. Kettenkarussell

2 m und einer Kettenlange von l = 4 m benotigt

fur einen Umlauf T = 5 s. Wie groß ist die Winkel-

auslenkung α der Kette?

Fur die Gleichgewichtslage gilt, dass die resultie-

rende Gesamtkraft, bestehend aus Zentrifugalkraft

FZ und Gewichtskraft FG, nur in Richtung der Ket-

te wirkt und keine Komponente senkrecht dazu be-

sitzt. α ist somit bestimmt durch die Bedingung

tanα =FZ

FG. (1)

Die Formeln fur die Krafte sind

FZ = m ω2 R = m ω2 (r + l sinα) (Zentrifugalkraft)

FG = m g (Gewichtskraft)


4 17. Numerisches Losen von Gleichungen

mit der Kreisfrequenz ω = 2πT . Wenden wir die trigonometrische Identitat

tanα =sinα

cos α=

sinα√1− sin2 α

(2)

an, folgt durch Gleichsetzen von (1) und (2)

sinα√1− sin2 α

= tan α =FZ

FG=

m ω2 (r + l sinα)m g

. (3)

Folglich ist

sin2 α =ω4

g2(r + l sinα)2

(1− sin2 α

)und nach Umformung

sin4 α + 2r

lsin3 α +

(r2

l2+

g2

ω4 l2− 1)

sin2 α− 2 r

lsinα− r2

l2= 0.

Einsetzen der Zahlenwerte liefert

sin4 α + sin3 α + 1.6620 sin2 α− sinα− 0.25 = 0.

Setzt man sinα = x, so erhalt man eine Gleichung der Form

x4 + x3 + 1.6620x2 − x− 0, 25 = 0.

Gesucht ist eine Nullstelle x0 ∈ [0, 1] .

Beispiel CD.2. Gesucht wird die Losung der transzendenten Gleichung

x2 + 2 = ex .

Definiert man die Funktion f (x) := x2+2−ex, ist eine Nullstelle der Funktion

f(x) zu berechnen.

Beispiel CD.3. Das Losen von linearen Differenzialgleichungen mit konstan-

ten Koeffizienten reduziert man auf das Finden von Nullstellen des sog. cha-

rakteristischen Polynoms. Auch das Losen von Eigenwertproblemen lasst sich

reduzieren auf das Finden von Nullstellen des zugehorigen charakteristischen

Polynoms.

In diesem Kapitel werden mehrere numerische Verfahren beschrieben, die zur

Losung des Nullstellenproblems f(x) = 0 herangezogen werden konnen.


17.1 Intervallhalbierungs-Methode 5

17.117.1 Intervallhalbierungs-MethodeGrundlage fur eine einfache numerische Methode zur Bestimmung von Null-

stellen einer Funktion bildet der anschauliche Satz, der besagt, dass jede stetige

Funktion, die auf einem Intervall [a, b] einen Vorzeichenwechsel hat, in diesem

Intervall eine Nullstelle besitzt (siehe Abb. 17.2):

Abb. 17.2. Intervallhalbierung

Zwischenwertsatz. Sei f : [a, b] → IR eine stetige Funktion mit (f (a) <

0 und f (b) > 0) oder (f (a) > 0 und f (b) < 0). Dann existiert eine

Zwischenstelle ξ ∈ (a, b) mit der Eigenschaft

f (ξ) = 0.

Beweis: (Intervallhalbierung). Da dieser Beweis direkt auf einen Algorithmus

fuhrt, geben wir ihn im Detail an. Ohne Einschrankung nehmen wir an, dass

f (a) < 0 und f (b) > 0.

Im ersten Teil definieren wir induktiv eine Folge von Intervallen [an, bn] ⊂ [a, b]mit den Eigenschaften

(1) [an, bn] ⊂ [an−1, bn−1] n ≥ 1(2) bn − an = 2−n (b− a)(3) f (an) ≤ 0 und f (bn) ≥ 0.

Diese Intervalle haben dann die Eigenschaft, dass sie die Nullstelle immer enger

einschließen.

Abb. 17.3. Einschließung der Nullstelle durch Intervallhalbierung



Induktionsanfang: [a0, b0] := [a, b] .Induktionsschluss: Sei [an, bn] gegeben mit den Eigenschaften (1) - (3). Dann

berechne man die Intervallmitte

m =12

(an + bn) .

Nun konnen 2 Falle auftreten: Entweder ist f (m) ≥ 0 oder f (m) < 0. Im

ersten Fall ersetzen wir die rechte Grenze bn durch m, andernfalls die linke

Grenze an durch m:

Falls f (m) ≥ 0, dann setze man [an+1, bn+1] := [an, m] .Falls f (m) < 0, dann setze man [an+1, bn+1] := [m, bn] .

Offenbar sind damit die Bedingungen (1) - (3) auch fur n + 1 erfullt und der

Induktionsbeweis beendet.

Wir zeigen in einem zweiten Schritt, dass die beiden Intervallgrenzen gegen

den gleichen Grenzwert konvergieren: Die Folge an ist monoton wachsend und

durch b nach oben beschrankt. Damit konvergiert sie gegen einen Grenzwert

ga := limn→∞

an. Die Folge bn ist monoton fallend und durch a nach unten be-

schrankt. Damit konvergiert bn gegen einen Grenzwert gb := limn→∞

bn.

Nach Eigenschaft (2) gilt

limn→∞

(bn − an) = limn→∞

2−n (b− a) = 0

und somit ist

ga = gb =: ξ.

Die Folgen (an) und (bn) konvergieren also gegen den gleichen Grenzwert ξ.

Dieser Grenzwert ist die gesuchte Nullstelle, denn aufgrund der Stetigkeit von

f ist

0 ≤ limn→∞

f (bn) = f (ξ) = limn→∞

f (an) ≤ 0,

womit insgesamt folgt

f (ξ) = 0.

Das oben beschriebene Verfahren liefert direkt einen Algorithmus, um eine

Nullstelle im Intervall [a, b] zu berechnen:



Algorithmus (Bisektion, Intervallhalbierung)

(1) Initialisierung: x1 := a ; x2 := b ; f1 := f (x1) ; f2 := f (x2) ; δ := 10−5.

(2) Iteration:

(a) Berechnung der Intervallmitte: x3 := 12 (x2 + x1)

(b) Berechnung des Funktionswertes: f3 := f (x3)

(c) Festlegung des neuen Intervalls:

i. Falls f3 · f2 ≤ 0 (d.h. Nullstelle zwischen x3 und x2),

dann x1 := x3 ; f1 := f3

ii. Falls f3 · f2 > 0 (d.h. Nullstelle zwischen x1 und x3),

dann x2 := x3 ; f2 := f3

(d) Abbruchbedingung:

i. Falls |x2 − x1| ≤ δ , dann ξ := x3. Stop.

ii. Falls |x2 − x1| > δ , dann weiter mit (a).

Bemerkungen:

(1) Die Funktion f kann mehrere Nullstellen im Intervall [a, b] besitzen. Die

Bisektionsmethode liefert aber nur eine.

(2) Man nennt Algorithmen, welche die Nullstelle in einem immer kleiner wer-

denden Intervall einschließen, auch Einschließungsalgorithmen. Ausgehend

von einem Startintervall, wird dieses Intervall systematisch durch den glei-

chen Algorithmus verkleinert. Man nennt einen solchen Prozess Iteration.

(3) Bei der programmtechnischen Realisierung ist darauf zu achten, dass der

Algorithmus nach einer gewissen Anzahl von Rechenschritten abbricht. Da-

her das sog. Abbruchkriterium. δ spezifiziert die maximale Intervallbreite

des einschließenden Intervalls. Ublicherweise wahlt man δ zwischen 10−5

und 10−6. δ sollte aber nicht kleiner als die Rechengenauigkeit gewahlt

werden, da sonst eine Endlos-Schleife entsteht und das Programm nicht

selbst abbricht. Die Rechengenauigkeit kann man z.B. mit folgendem klei-

nen Programm ermitteln:

fmach := 1.

WHILE (1. < 1. + fmach)

DO fmach := fmach ∗ 0.5

fmach := 2. ∗ fmach

(4) Die Intervallhalbierungs-Methode lasst sich einfach programmieren. Die

Konvergenz der Folgen (an) und (bn) gegen die Nullstelle ist zwar recht



langsam, doch fuhrt das Verfahren bei jeder stetigen Funktion mit Vor-

zeichenwechsel zum Ziel. Die Methode ist auch unanfallig gegenuber Run-

dungsfehlern.

(5) Die Anzahl der benotigten Iterationen kann vor der Rechnung abgeschatzt

werden, denn es gilt fur den Abstand der Nullstelle von der linken Inter-

vallgrenze

|an − ξ| ≤ b− a

2nfur n = 1, 2, 3, . . . .

Ist f eine stetige Funktion auf [0, 1] mit Vorzeichenwechsel und soll die

Nullstelle ξ ∈ (0, 1) bis auf 4 Dezimalstellen genau bestimmt werden, darf

der Abstand von |an − ξ| nicht großer sein als 9 · 10−5. n muss also so ge-

wahlt werden, dass b−a2n ≤ 9 · 10−5 ⇒ n = 14.

(Bei einer Genauigkeit von 6 Dezimalstellen ist n immerhin schon 21.)

Beispiel CD.4 (Mit Maple-Worksheet). Gegeben ist die Funktion

f (x) = x3 −√

x2 + 1 .

Gesucht ist die Nullstelle im Intervall [1, 2] . Da die Funktionswerte an den

Intervallgrenzen unterschiedliches Vorzeichen besitzen (f (1) = −0.4142 und

f (2) = 5.7639), erhalt man mit dem Bisektionsverfahren die Nullstelle:

n a b f(a+b2 )

1.0 2.0 1.57221 1.0 1.5 0.35232 1.0 1.25 −0.08133 1.125 1.25 0.12204 1.125 1.1875 0.01715 1.125 1.1562 −0.03296 1.1406 1.1562 −0.00817 1.1484 1.1562 0.00448 1.1484 1.1523 0.00189 1.1503 1.1523 0.0012

10 1.1503 1.1513 −2 · 10−4

11 1.1508 1.1513 5 · 10−4

12 1.1508 1.1511 1 · 10−4

13 1.1508 1.1510 −7 · 10−5

⇒ ξ ≈ 1.1509



Umsetzung mit Maple

Bei der Realisierung der Intervallhalbierungs-Methode mit Maple wird der

Algorithmus direkt ubernommen. Der Aufruf der Prozedur bise erfolgt wie

der plot-Aufruf fur einen Ausdruck.

> bise := proc()

> local iter, x1, x2, x3, f1, f2, f3, delta,

> f, func, x;

>

> func := args[1]: x := op(1, args[2]);

> f := unapply (func, x):

> x1 := op(1, op(2, args[2]));

> x2 := op(2, op(2, args[2]));

> f1 := f(x1): f2 := f(x2):

>

> iter := 0: delta := 1e-4:

> while x2 - x1 > delta

> do iter := iter + 1:

> x3 := (x2 + x1)/2.:

> f3 := f(x3):

> if (evalf (f3 ∗ f2) <= 0) then x1 := x3: f1 := f3:

> else x2 := x3: f2 := f3:

> fi;

> lprint (’[’, x1, ’, ’, x2, ’]’):

> od;

> print (’Die Nullstelle liegt nach ’, iter; ’Iterationen bei xi = ’, x3);

> end:

Visualisierung mit Maple: Auf der CD-Rom befindet sich eine

erweiterte Maple-Prozedur, bise ext, die den Konvergenzprozess in

Form einer Animation visualisiert.



Beispiel M.1 (Mit Maple).

> bise (xˆ3 - sqrt(xˆ2 + 1), x = 1..2);

[ 1. , 1.500000000 ][ 1. , 1.250000000 ][ 1.125000000 , 1.250000000 ][ 1.125000000 , 1.187500000 ][ 1.125000000 , 1.156250000 ][ 1.140625000 , 1.156250000 ][ 1.148437500 , 1.156250000 ][ 1.148437500 , 1.152343750 ][ 1.150390625 , 1.152343750 ][ 1.150390625 , 1.151367188 ][ 1.150878907 , 1.151367188 ][ 1.150878907 , 1.151123048 ][ 1.150878907 , 1.151000978 ][ 1.150939943 , 1.151000978 ]

Die Nullstelle liegt nach 14 Iterationen bei xi = 1.150939943.

Bestimmung der Rechengenauigkeit mit Maple

Die Rechengenauigkeit wird mit dem folgenden Algorithmus bestimmt.

> Digits := 15:

> fmach := 1.:

> while 1. < 1. + fmach do fmach := 0.5 ∗ fmach: od:

> fmach := 2. ∗ fmach;

fmach := 0.710542735760120 10−14

Die Rechengenauigkeit stimmt mit der zuvor mit Digits spezifizierten Genau-

igkeit uberein.

Intervallschachtelung von Wurzeln

Das Prinzip der Intervallschachtelung von Wurzeln beruht auf der Bisektions-

methode. Denn die Berechnung der n-ten Wurzel einer positiven Zahl a

x = n√

a

lasst sich durch Potenzieren zum aquivalenten Problem der Bestimmung der

positiven Nullstelle der Funktion

f(x) = xn − a = 0

umformulieren.



Um das Bisektionsverfahren anwenden zu konnen, muss ein Einschließungsin-

tervall angegeben werden. Die linke Intervallgrenze ist dabei immer Null, denn

f (0) = −a < 0. Als rechte Intervallgrenze setzt man 1, falls a < 1 (denn dann

ist f (1) = 1 − a > 0) oder a, falls a > 1 (denn dann ist f (a) = an − a > 0).

Im Falle a = 1 ist x = n√

1 = 1 ; so dass dieser Spezialfall nicht mit der Bisek-

tionsmethode berechnet werden muss.

Beispiel M.2 (Mit Maple). Berechnung von 5√

8> bise (xˆ5 - 8, x = 0..8)

[ 0 , 4.000000000 ][ 0 , 2.000000000 ][ 1.000000000 , 2.000000000 ][ 1.500000000 , 2.000000000 ][ 1.500000000 , 1.750000000 ][ 1.500000000 , 1.625000000 ][ 1.500000000 , 1.562500000 ][ 1.500000000 , 1.531250000 ][ 1.515625000 , 1.531250000 ][ 1.515625000 , 1.523437500 ][ 1.515625000 , 1.519531250 ][ 1.515625000 , 1.517578125 ][ 1.515625000 , 1.516601563 ][ 1.515625000 , 1.516113282 ][ 1.515625000 , 1.515869141 ][ 1.515625000 , 1.515747071 ][ 1.515686036 , 1.515747071 ]

DieNullstelle liegt nach , 17, Iterationen bei xi =, 1.515686036

5√

8 ist bis auf 5 Dezimalstellen genau im Intervall [1.5156, 1.5157] eingeschlos-

sen.



17.2 17.2 Pegasus-VerfahrenBei der Intervallhalbierungs-Methode wird in jedem Iterationsschritt das Ein-

schließungsintervall halbiert. Selbst wenn die Nullstelle sehr nahe an einer In-

tervallgrenze liegt, muss fur die Bestimmung dieser Nullstelle bis auf 6 De-

zimalstellen 21-mal iteriert werden. Eine verbesserte Methode stellt das sog.

Pegasus-Verfahren dar, welches statt der Intervallmitte den Sekantenschnitt-

punkt wahlt:

Abb. 17.4. Berechnung der Sekantenschnittpunkte mit der x-Achse

Gegeben sei eine Funktion f , die auf dem Intervall [a, b] einen Vorzeichenwech-

sel hat. Wir nehmen an, dass f1 = f (a) < 0 und f2 = f (b) > 0 und setzen

x1 = a bzw. x2 = b. Entsprechend Abb. 17.4 wird die Sekantensteigung durch

die Punkte (x1, f1) , (x2, f2) berechnet

s12 =y − f1

x− x1=

f2 − f1

x2 − x1

und anschließend der Schnittpunkt mit der x-Achse bestimmt

x3 = x1 −f1

s12.

Nimmt man stets nur den Sekantenschnittpunkt als neuen Iterationswert, so

nahert sich zwar x3 der Nullstelle an, aber das Einschlussintervall konvergiert

nicht notwendigerweise gegen Null. Deshalb versucht man durch eine geometri-

sche Modifikation auch auf die ”andere Seite der Nullstelle” zu kommen. Dazu

skaliert man den Funktionswert f1 gemaß dem Strahlensatz durch folgenden

Konstruktion:

Abb. 17.5. Geometrische Konstruktion zum Pegasus-Verfahren


17.2 Pegasus-Verfahren 13

Man bildet die Verbindungsgerade der Punkte (x2, f2 + f3), (x1, f1) sowie

(x2, f2), (x1, f∗1 ) , wenn f3 = f (x3) und setzt

f∗1 = f1 ·f2

f2 + f3(Strahlensatz).

Dann ersetzt man f1 durch f∗1 . Iteriert man nun mit f∗1 weiter, wird die Stei-

gung der nachfolgenden Sekante kleiner als mit f1. Somit liegt der entspre-

chende Schnittpunkt naher an der Nullstelle bzw. nachfolgend auf der ”anderen

Seite” der Nullstelle. Man erhalt den folgenden

Algorithmus (Pegasus-Verfahren)

(1) Initialisierung: x1 := a ; x2 := b ; f1 := f (x1) ; f2 := f (x2) ; δ := 10−5.

(2) Iteration:

(a) Berechnung der Sekantensteigung: s12 :=f2 − f1

x2 − x1

(b) Berechnung des Schnittpunktes: x3 := x1 −f1

s12

(c) Berechnung des Funktionswertes: f3 := f (x3)

(d) Festlegung des Einschließungsintervalls und Modifikation von f1

i. Falls f3 · f2 ≤ 0 (d.h. Nullstelle zwischen x3 und x2),

dann x1 := x2 ; f1 := f2 ; x2 := x3 ; f2 := f3

ii. Falls f3 · f2 > 0 (d.h. Nullstelle zwischen x1 und x3),

dann f1 := f1 ·f2

f2 + f3; x2 := x3 ; f2 := f3

(e) Abbruchbedingung:

i. Falls |x2 − x1| ≤ δ , dann ξ :={

x2 fur |f2| ≤ |f1|x1 sonst

.

ii. Falls |x2 − x1| > δ , dann weiter mit (a).

Beispiel CD.5 (Mit Maple). Gegeben sei die Funktion f (x) = x3−√

x2 + 1aus Beispiel CD.4. Das Pegasus-Verfahren liefert als Ergebnis:

a b x3 f3

1.0 2.0 1.0670 −0.24741 2.0 1.0670 1.1054 −0.13972 2.0 1.1054 1.1381 −0.04713 2.0 1.1381 1.1502 −0.00224 2.0 1.1502 1.1509 2 · 10−5

5 1.1502 1.1509 1.1509 −1.487 · 10−8



Bemerkungen:

(1) Beispiel CD.5 zeigt, dass die Konvergenzgeschwindigkeit des Pegasus-Verfahrens

deutlich hoher als die der Bisektionsmethode ist. Nach 5 Iterationen hat

man in diesem Fall eine Genauigkeit von 10−6 erreicht!

(2) Die Vorteile des Pegasus-Verfahrens als auch der Bisektionsmethode lie-

gen darin, dass sie fur jede stetige Funktion mit Vorzeichenwechsel kon-

vergieren. In Fallen von mehrfachen Nullstellen konnen beide Verfahren

verwendet werden, wenn man sie statt auf f auf die Funktion g mit

g (x) =f (x)f ′ (x)

anwendet. Denn ist ξ eine k-fache Nullstelle von f , dann ist ξ eine einfache

Nullstelle von g.

(3) Der Nachteil der beiden Verfahren liegt darin, dass sie nicht auf Probleme

bei Funktionen mit mehreren Variablen anwendbar sind.

(4) Die Realisierung des Pegasus-Verfahrens mit Maple erfolgt analog dem

Bisektionsverfahren.

Beispiel CD.6 (Kettenkarussell). Fur die Nullstelle der Funktion

f (x) = x4 + x3 + 1.6620x2 − x− 0.25 = 0

im Intervall [0, 1] erhalten wir mit dem Bisektionsverfahren bzw. dem Pega-

susverfahren Iterationsintervalle, die in nebenstehenden Tabellen (links Bisek-

tionsverfahren, rechts Pegasusverfahren) angegeben sind.


17.2 Pegasus-Verfahren 15

n a b f(

a+b2

)0 0.00000 1.00000 −0.1470001 0.50000 1.00000 0.6731562 0.50000 0.75000 0.1709473 0.50000 0.62500 −0.0085414 0.56250 0.62500 0.0757745 0.56250 0.59375 0.0322976 0.56250 0.57813 0.0115537 0.56250 0.57031 0.0014258 0.56250 0.56641 −0.0035789 0.56445 0.56641 −0.001082

10 0.56543 0.56641 0.00017111 0.56543 0.56592 −0.00045612 0.56567 0.56592 −0.00014313 0.56580 0.56592 0.00001414 0.56580 0.56586 −0.00006415 0.56583 0.56586 −0.00002516 0.56584 0.56586 −0.000006

n a b

0 0.00000 1.000001 1.00000 0.093912 1.00000 0.202483 1.00000 0.401344 0.40134 0.590955 0.59095 0.555336 0.59095 0.565327 0.59095 0.565858 0.56585 0.56585

Bei einer Genauigkeit von 5 Dezimalstellen liefert das Bisektionsverfahren nach

16 Iterationen und das Pegasusverfahren nach 8 Iterationen die Nullstelle bei

ξ = 0.56585. Da in Beispiel CD.1

sinα = x

gesetzt ist, folgt durch Auflosen der Gleichung mit dem Arkussinus der Aus-

lenkungswinkel des Kettenkarussells α = 34.46◦ .

Die beiden nachfolgenden Verfahren, Banachsches Iterationsverfahren und New-

ton-Verfahren, besitzen die Eigenschaft, dass sie auf den mehrdimensionalen

Fall ubertragbar sind und dass sie - wenn sie konvergieren - sehr schnell kon-

vergieren.



17.3 17.3 Banachsches IterationsverfahrenEinfuhrung: Bisher war die Aufgabenstellung zu gegebener Funktion f eine

Nullstelle x0 zu finden:

f (x0) = 0.

Dies ist das sog. Nullstellenproblem. Ein einfaches iteratives Verfahren erhalt

man, wenn man auf beiden Seiten x addiert und stattdessen die Gleichung

x = f (x) + x =: F (x)

betrachtet. Eine Losung x0 dieser Gleichung

F (x) = x

wird Fixpunkt genannt, da die Funktion F, auf x0 angewendet, als Funkti-

onswert wieder x0 liefert. x0 bleibt unter der Abbildung F fixiert. Es gilt

x0 ist ein Fixpunkt von F (x) = x genau dann, wenn x0 Nullstelle von

f (x) = 0.

Beispiel CD.7. Gegeben sei die Gleichung

x = 0.1x + 100.

Ohne Rechnung erhalt man sofort eine Naherung fur die Losung: Da der x-

Term auf der rechten Seite der Gleichung mit dem Faktor 0.1 im Vergleich zu

100 eingeht, setzt man naherungsweise

x(0) = 100.

Um einen genaueren Wert x(1) fur die Losung zu erhalten, berucksichtigen wir

nun den Term 0.1x:

x(1) = 0.1 · x(0) + 100 = 10 + 100 = 110.

Damit haben wir den Startwert x(0) korrigiert und eine genauere Schatzung

fur die Losung erhalten. Einen noch genaueren Wert x(2) erhalt man, wenn

x(1) = 110 in die rechte Seite der Gleichung eingesetzt wird:

x(2) = 0.1x(1) + 100 = 111

und weiter fortfahrt

x(3) = 0.1x(2) + 100 = 111.1x(4) = 0.1x(3) + 100 = 111.11

...


17.3 Banachsches Iterationsverfahren 17

Je weiter man fortschreitet (iteriert), um so genauer wird die Losung angena-

hert. Die exakte Losung ist x = 111.1.

Man nennt ein solches Verfahren ein Iterationsverfahren, da ausgehend von

einem Startwert x(0) die Losung des Problems iterativ gefunden wird. Um al-

lerdings iterieren zu konnen, muss der jeweilige Funktionswert F (x(i)) wieder

im Definitionsbereich der Funktion liegen! Damit kommen wir zur allgemeinen

Formulierung des Problems:

Allgemeines Problem: Gesucht ist eine Losung des Problems

F (x) = x, (∗)

wenn F : I → I das Intervall I auf sich selbst abbildet. Jede Losung x von (∗)heißt Fixpunkt von F . Die Gleichung selbst wird Fixpunktgleichung ge-

nannt. Geometrisch entsprechen die Fixpunkte den Schnittpunkten der Funk-

tion F (x) mit der Winkelhalbierenden (siehe Abb. 17.6).

Abb. 17.6. Fixpunkt x

Um eine Losung von (∗) numerisch zu berechnen, wahlen wir folgenden Algo-

rithmus:

Algorithmus (Banachsches Iterationsverfahren)

(1) Initialisierung: Wahle Startwert x0 ; δ := 10−5.

(2) Iteration:

(a) xn+1 := F (xn)

(b) Abbruchbedingung

i. Falls |xn+1 − xn| ≤ δ , dann x = xn+1. Stop.

ii. Falls |xn+1 − xn| > δ , dann weiter mit (a).



Durch diese Iteration wird eine Folge

x1 = F (x0)x2 = F (x1)x3 = F (x2)

...

xn+1 = F (xn) n = 0, 1, 2, . . .

definiert, die, falls sie konvergiert, gegen den Fixpunkt strebt.

Beispiel CD.8. Gesucht ist eine Nullstelle der Funktion

f (x) = 0.5− x + 0.2 sin(x)

im Intervall [0. 3 ; 0.5] mit einer Genauigkeit von 10−5.

1. Schritt: Umformung der Nullstellengleichung in eine Fixpunktgleichung:

0.5− x + 0.2 sin(x) = 0 |+x

⇒ 0.5 + 0.2 sin(x) = x

2. Schritt: Iterationsverfahren nach Banach

x0 = 0.5xn+1 = F (xn) = 0.5 + 0.2 sin(xn) n = 0, 1, 2, 3, . . .

Ergebnis:

n xn xn − xn−1

0 0.5000 −1 0.5958 0.09582 0.6122 0.01633 0.6149 0.00294 0.6153 0.00045 0.6154 0.00016 0.6154 0.0000

Nach 6 Iterationen hat man eine Genauigkeit von 4 Dezimalstellen.

Beispiel CD.9 (Mit Maple). Gesucht ist eine Nullstelle der Funktion

f (x) = 0.5− x + 2 · sin(x) (∗)

im Intervall [0, π] mit einer Genauigkeit von 10−5. Wir formen (∗) in eine

Fixpunktgleichung um, indem wir auf beiden Seiten x addieren

F (x) = 0.5 + 2 sin(x) = x



und iterieren gemaß der Banach-Iteration.

x0 = 0.5xn+1 = F (xn) = 0.5 + 2 sin (xn) n = 0, 1, 2, 3, . . . .

4! Achtung: In diesem Fall erhalt man eine divergente Folge xn, obwohl ein

Fixpunkt existiert! Sowohl Bisektions- als auch das Pegasus-Verfahren liefern

als Nullstelle (= Fixpunkt) 2.16130 . Im Gegensatz also zur Bisektionsme-

thode und zum Pegasusverfahren konvergiert die Banach-Iteration

nicht in jedem Fall!

Die Antwort auf die Frage, unter welchen Voraussetzungen die Iterationsfolge

xn gegen einen Fixpunkt x von F (x) = x konvergiert, liefert der Banachsche

Fixpunktsatz:

Satz: Banachscher Fixpunktsatz. Sei F : I → I eine stetige Funktion

und fur alle x1, x2 ∈ I gelte die Ungleichung

|F (x1)− F (x2)| ≤ K |x1 − x2|

mit einer Konstanten K < 1. Dann folgt: F hat genau einen Fixpunkt x

in I und die Iterationsfolge

xn+1 = F (xn)

konvergiert gegen x fur jeden beliebigen Startwert x0 ∈ I .

Anschaulich besagt die Bedingung K < 1, dass die Funktionswerte F (x1) und

F (x2) stets dichter zusammen liegen als die Punkte x1 und x2. Man nennt die-

ses Verhalten Kontraktion, da die Funktion sich zusammenzieht. Der Graph

der Funktion F steigt bzw. fallt flacher als die Winkelhalbierende ansteigt bzw.

abfallt. Die Steigung des Graphen ist aber durch die erste Ableitung der Funk-

tion bestimmt:

Ist |F ′ (x)| < 1 fur alle x aus dem Intervall I, dann sind die Bedingungen aus

dem Banachschen Fixpunktsatz erfullt, indem

K =maxx∈I

|F ′ (x)|

gesetzt wird. Es gilt also



Satz: Ist F : I → I stetig differenzierbar mit |F ′ (x)| < 1 fur alle x ∈ I,

dann hat F einen Fixpunkt x in I und die Iterationsfolge

xn+1 = F (xn)

konvergiert gegen x fur jeden Startwert x0 ∈ I .

Abb. 17.7. Zur geometrischen Interpretation des Banachverfahrens

Geometrische Interpretation:

Ist |F ′ (x)| < 1 fur alle x ∈ I, dann liegen die Funktionswerte naher beisam-

men als die x-Werte. In Abb. 17.7 (a), (b) ist dieser Fall graphisch dargestellt.

In Abb. 17.7 (a) ist die Steigung der Funktion positiv; in 17.7 (b) negativ.

Fur beide Funktionen konvergiert die Iterationsfolge gegen den Fixpunkt. Ist

|F ′ (x)| > 1 fur den Fixpunkt x wie in Abb. 17.7 (c) und 17.7 (d), dann diver-

giert die Iterationsfolge, selbst wenn man den Startwert x0 beliebig nahe am

Fixpunkt wahlt.



Fehlerabschatzungen.

Zu den Iterationsverfahren gelten fur alle n = 0, 1, 2, 3, . . . die Fehlerabschat-

zungen:

|xn − x| ≤ Kn

1−K|x1 − x0| (a priori)

|xn − x| ≤ 11−K

|xn+1 − xn| (a posteriori),

Beispiele CD.10:©1 Aufgrund des Banachschen Fixpunktsatzes ist klar, dass die Iterationsfolge

aus Beispiel CD.8 gegen den Fixpunkt konvergiert, denn mit

F (x) = 0.5 + 0.2 sinx

⇒ F ′ (x) = 0.2 cosx und damit |F ′ (x)| ≤ 0.2 < 1.

Nach der Fehlerabschatzung kann man die notige Anzahl von Iterationen

auch vor der Rechnung feststellen: Mit K = max |F ′ (x)| = 0.2 gilt nach

der a-priori-Fehlerabschatzung fur eine Genauigkeit mit 4 Stellen:

n =ln 0.8 · 10−5 / 0.0958

ln 0.2≈ 6.

©2 Da in Beispiel CD.9 F (x) = 0.5 + 2 · sin (x) und F ′ (x) = 2 · cos x, folgt

fur den Fixpunkt x = 2.16130: |F ′ (x)| = 1.1 > 1. Daher divergiert das

Banachverfahren.

Erganzungen zur Banach-Iteration:

Gesucht ist die positive Nullstelle (x = 1) der Funktion

f (x) = x2 − x.

Um die Losung numerisch mit dem Banachverfahren zu berechnen, kann man

die Nullstellengleichung auf 2 Arten zu einer Fixpunktgleichung umformen.

(i) Die Gleichung

x2 − x = 0 (∗)

wird durch Addition des Terms x in eine Fixpunktgleichung(x2 − x

)+ x = x

umgewandelt. Mit F (x) := f (x) + x = x2 erhalt man das Problem

F (x) = x.



Allerdings ist F ′ (x) = 2x, so dass fur die positive Nullstelle x = 1 gilt

F ′ (x) = 2 > 1. D.h. das Banachverfahren konvergiert fur keinen Startwert

x0 gegen x = 1 (vgl. Abb. 17.8 (a)). Fur x0 = 1.001 folgt nach 15 Itera-

tionen ein Overflow. Fur x0 = 0.999 konvergiert die Banachfolge gegen die

zweite Nullstelle x = 0 (x16 = 2 · 10−6).

Abb. 17.8. Zum Banachverfahren

(ii) Die Gleichung

x2 − x = 0

wird zunachst in die aquivalente Gleichung

−(x2 − x) = 0

umgeformt und dann erst durch Addition von x in eine Fixpunktgleichung

−(x2 − x

)+ x = x.

Fur F (x) := −x2 + 2x gilt (vgl. Abb. 17.8 (b))

F (x) = x

mit F ′ (x) = −2x + 2. Damit ist

|F ′ (x)| < 1 fur 12 < x < 3

2 .

Nach dem Banachschen Fixpunktsatz konvergiert die Banachfolge fur alle

Startwerte x0 ∈(

12 , 3

2

).

Folgerung: In manchen Fallen ist es gunstiger, statt der Gleichung f (x) =0 die aquivalente Gleichung −f (x) = 0 zu betrachten und erst dann zur

Fixpunktgleichung uberzugehen. Welche der beiden Gleichungen geeignet ist,

hangt vom Vorzeichen der Ableitung der Funktion f(x) ab.



Beispiel CD.11. Gesucht ist die positive Nullstelle

der Funktion

f(x) = x3 − 100x.

Die positive Nullstelle liegt bei x = 10 und die Stei-

gung der Funktion f bei x ist f ′ (x) = 3x2 − 100 =200. Egal, ob man nun zur Gleichung −f(x) + x = x

oder f(x)+x = x ubergeht, die Funktion F (x) hat in

x in beiden Fallen eine Steigung betragsmaßig großer

als 1. Damit konvergiert das Banachverfahren nicht gegen x. Um dennoch die

Banach-Iteration erfolgreich auf dieses Problem anzuwenden, gehen wir von

f(x) = 0

zur aquivalenten Gleichung

−f (x)250

= 0

uber. Die Nullstellen der Funktion f(x) und − f(x)250 stimmen uberein. Die Stei-

gung der Funktion − f(x)250 ist nun im Punkte x kleiner als bei f(x). Es gilt

mit

F (x) := −f (x)250

+ x!= x,

dass F ′(x) = − 3x2−100250 + 1 = − 200

250 + 1 = 15 < 1 fur x = 10 und damit konver-

giert das Banachverfahren.

Um die Abhangigkeit der Konvergenz von dem Nor-

mierungsfaktor zu demonstrieren, setzen wir

F (x) := −f (x)a

+ x ,

wahlen als Startwert x0 = 1, δ = 10−6, und prufen fur verschiedene Werte von

a nach, ob Konvergenz vorliegt oder nicht.

a = 1 Divergenz: Overflow nach 2 Iterationen

a = 100 Divergenz: 2 Haufungspunkte

a = 150 Konvergenz nach 18 Iterationen




a = 1000 Konvergenz nach 87 Iterationen.

Die Banachfolge konvergiert am schnellsten fur einen Wert von a der vergleich-

bar zu f ′(x) ist.



Zusammenfassung: Ist die Nullstelle einer Funktion f(x) in einem Intervall

I gesucht,

f(x) != 0,

so formt man diese Gleichung um in

f (x)a

!= 0

und geht anschließend erst zur Fixpunktgleichung

F (x) = x mit F (x) =f (x)

a+ x

uber. Ist K :=maxx∈I

|f ′ (x)| , dann setzt man

a := −max {K, 1}, falls 0 ≤ f ′ (x) im Intervall I

a := max{K, 1}, falls 0 ≥ f ′ (x) im Intervall I.

Mit dieser Wahl von a erzwingt man die Konvergenz des Banachverfahrens fur

einen Startwert nahe x.

17.4 17.4 Anwendung des Banach-Verfahrens

Anwendungsbeispiel CD.12 (2-Federn-Masse-System).

Am Ende zweier entgegengesetzt eingespannter Federn mit Federkonstanten

D1 und D2 ist eine Masse m angebracht. Die Ruheauslenkung der Federn sei

l0. Auf die Masse wirkt eine Kraft−→F , welche die Masse auslenkt. Welche

Koordinaten (x, y) besitzt der Massenpunkt, wenn die Kraft−→F den Betrag

F0 = 1N hat und wenn der Winkel zwischen der Kraft und der x-Achse α ist?

Abb. 17.9. 2-Federn-Masse-System


17.4 Anwendung des Banach-Verfahrens 25

Losungsansatz: Die Koordinaten (x, y) des Massenpunktes sind bestimmt

durch die Gleichgewichtslage. Diese Gleichgewichtslage ist realisiert, wenn die

Summe aller angreifenden Krafte gleich Null ist (Summe aller in x-Richtung

wirkenden Krafte = 0; Summe aller in y-Richtung wirkenden Krafte = 0).

Angreifende Krafte:

−→F 1 : Ruckstellkraft der ersten Feder−→F 2 : Ruckstellkraft der zweiten Feder−→F G : Gewichtskraft−→F : Zugkraft

Kraft in x-Richtung =

x-Komponente der Ruckstellkraft von D1

+x-Komponente der Ruckstellkraft von D2

+x-Komponente der Zugkraft

Kraft in y-Richtung =

y-Komponente der Ruckstellkraft von D1

+y-Komponente der Ruckstellkraft von D2

+y-Komponente der Zugkraft + Gewichtskraft

Fx = FD1 sinϕ1 + FD2 sinϕ2 + F0 cos α

= −D1 (s1 − l0) sin ϕ1 −D2 (s2 − l0) sin ϕ2 + F0 cos α

= −D1 (s1 − l0)x

s1−D2 (s2 − l0)

x

s2+ F0 cos α (1)

Fy = FD1 cos ϕ1 + FD2 cos ϕ2 + F0 sinα−m g

= D1 (s1 − l0)L/2−y

s1−D2 (s2 − l0)

L/2+ys2

+ F0 sinα−m g (2)

mit

s1 =√

x2 + (L/2− y)2 und s2 =√

x2 + (L/2 + y)2 .

Die Gleichgewichtslage ist dadurch bestimmt, dass Fx = 0 und Fy = 0 ⇒Nichtlineares Gleichungssystem fur x und y.



17.4.1 1-dimensionaler Fall

Sei α = 0, m = 0 und D1 = D2 = D. Dann ist aufgrund der Symmetrie y = 0und s1 = s2. Man erhalt fur x das Problem

−D (s− l0)x

s−D (s− l0)

x

s+ F0 = 0

mit s =√

x2 + (L/2)2. Gesucht ist also die Auslenkung x, so dass

f(x) = 0 mit f(x) = −2D x

√x2 + (L/2)2 − l0√

x2 + (L/2)2+ F0 .

Da die Banach-Iteration nur fur das Fixpunktproblem F (x) = x anwendbar

ist, mussen wir von

f(x) = 0 (∗)

zum entsprechenden Fixpunktproblem ubergehen. Formal wurde man nun auf

beiden Seiten der Gleichung x addieren, um zur Fixpunktgleichung

f(x) + x = x (∗∗)

zu gelangen. Aber man erkennt, dass f und x unterschiedliche physikalische Di-

mensionen besitzen. Lasst man dies unberucksichtigt und wendet auf (∗∗) die

Banach-Iteration an, so divergiert die Folge. Deshalb skaliert man die Nullstel-

lengleichung (∗), indem man zu charakteristischen Kraften und Langen uber-

geht und die zu (∗) aquivalente Gleichung

f (x)Fch

· lch = 0

betrachtet mit Fch = max (1N, F0) und lch = min (l0, 0.01m). (Dies entspricht

genau dem Vorgehen aus CD-Beispiel CD.11). Nun hat die linke Seite der Glei-

chung die Dimension einer Lange und man kann auf beiden Seiten x addieren.

Man erhalt schließlich folgende Fixpunktgleichung

F (x) :=

−2D x

Fch

√x2 + (L/2)2 − l0√

x2 + (L/2)2+

F0

Fch

lch + x!= x.

Die zugehorige Iteration lautet

(1) Initialisierung: x0 = 0

(2) Iteration: xn+1 = F (xn) n = 0, 1, 2, . . . .


17.4 Anwendung des Banach-Verfahrens 27

Beispiel CD.13. Das Ergebnis der Rechnung fur D = 3Nm , l0 = 0.01m, L =

1m und F0 = 1N ist in der folgenden Tabelle aufgelistet.

n xn

1 0.141172 0.158103 0.165044 0.167905 0.169076 0.169557 0.169748 0.169829 0.1698610 0.16987

Nach 10 Iterationen erhalt man fur die Auslenkung in x-Richtung x ≈ 0.16987m.

17.4.2 2-dimensionales 2-Federn-Masse-Problem

Wir betrachten jetzt das nichtlineare Gleichungssystem (1), (2)

Fx (x, y) = 0Fy (x, y) = 0

fur die Auslenkung in x- und y-Richtung. Fuhren wir den Kraftvektor−→F =(

Fx

Fy

)ein, ist eine Losung der Vektorgleichung

−→F (x, y) =

−→0 (∗)

gesucht. Um die Banachiteration anwenden zu konnen, muss auf beiden Sei-

ten der Gleichung der Vektor −→x =(

x

y

)addiert werden. Aus den gleichen

Grunden wie im eindimensionalen Fall wird die Gleichung (∗) skaliert:

−→F (x, y) · lch

Fch=−→0 .

Nach Addition des Vektors −→x ist

−→F (−→x ) · lch

Fch+−→x = −→x

bzw. in Komponenten



Gx (x, y) = [−D1 (s1 − l0)x

s1−D2 (s2 − l0)

x

s2+ F0 cos α]

/ Fch · lch + x!= x

Gy (x, y) = [D1 (s1 − l0)L/2− y

s1−D2 (s2 − l0)

L/2 + y

s2

+F0 sinα−m g] / Fch · lch + y!= y

mit

s1 =√

x2 + (L/2− y)2 und s2 =√

x2 + (L/2 + y)2 .

Das zugehorige Iterationsverfahren lautet:

Algorithmus (Banachverfahren auf 2-D Problem)

(1) Initialisierung: x0 := 0 ; y0 := 0 ; δ := 10−4.

(2) Iteration:

(a) xn+1 := Gx (xn, yn)yn+1 := Gy (xn, yn)

(b) Abbruchbedingung:

i. Falls |xn+1 − xn| ≤ δ und |yn+1 − yn| ≤ δ,

dann (x, y) = (xn+1, yn+1). Stop.

ii. Falls |xn+1 − xn| ≥ δ oder |yn+1 − yn| ≥ δ,

dann weiter mit (a).

Beispiel CD.14. Mit den Parametern m = 0.125kg, D1 = 3Nm , D2 = 3N

m , l0 =0.01m, L = 1m, F0 = 1N und α = 45◦ erhalt man das folgende Ergebnis:

n xn yn

1 0.0998 −0.07262 0.1118 −0.08103 0.1167 −0.08434 0.1188 −0.08575 0.1196 −0.08626 0.1200 −0.08647 0.1201 −0.08658 0.1202 −0.08659

Die Auslenkung des Massenpunktes in x-Richtung betragt 0.1202m und in

y-Richtung −0.08659m.


17.5 Newton-Verfahren 29

17.517.5 Newton-VerfahrenDas Banachsche Fixpunktverfahren ist sehr einfach anwendbar und hat den

Vorteil, dass es direkt auf den mehrdimensionalen Fall ubertragen werden kann.

Nachteilig ist, dass - falls die Funktion F im Fixpunkt zu steil ansteigt - die

Konvergenz nur uber eine Normierung des Problems gewahrleistet ist und das

Verfahren sehr langsam konvergiert. Das im Folgenden beschriebene Newton-

Verfahren zur Bestimmung einer Nullstelle konvergiert immer, wenn man nahe

genug an der Nullstelle startet. Die Konvergenz des Verfahrens ist sehr schnell.

Gesucht ist eine einfache Nullstelle der Funktion f,

f(x) = 0,

im Intervall [a, b] .

Das Verfahren. Das Newton-Verfahren ist ein iteratives Verfahren. Man star-

tet mit einer Anfangsschatzung x0 fur die Nullstelle und verbessert in weiteren

Iterationsschritten diesen Wert: Man berechnet dazu im Punkt x0 die Tangen-

te an f und bestimmt den Schnittpunkt der Tangente mit der x-Achse. Dieser

Wert sei x1. In der Regel liegt x1 naher an der Nullstelle als x0. Nun berechnet

man in x1 die Tangente der Funktion und bestimmt den Achsenschnittpunkt

x2. Durch Fortfuhrung des Verfahrens nahert man sich der Nullstelle an (siehe

Abb. 17.10).

Abb. 17.10. Geometrische Interpretation des Newton-Verfahrens

Aufstellen der Formeln: Die Tangentengleichung in x0 hat die Form

y = f (x0) + f ′ (x0) (x− x0)

und der Schnittpunkt x1 mit der x-Achse ist definiert durch y = 0:

0 = f(x0) + f ′ (x0) (x1 − x0) .



Damit ist

x1 = x0 −f (x0)f ′ (x0)

.

Durch Iteration erhalt man folgenden

Algorithmus (Newton-Verfahren)

(1) Initialisierung: Wahle Startwert x0; δ := 10−5.

(2) Iteration:

(a) Iteration: xn+1 = xn −f (xn)f ′ (xn)

n = 0, 1, 2, 3, . . .

(a) Abbruchbedingung:

i. Falls |xn+1 − xn| < δ, dann ξ = xn+1. Stop.

ii. Falls |xn+1 − xn| ≥ δ, dann weiter mit (a).

Eigenschaften des Verfahrens

(1) Sehr schnelle Konvergenz (nur wenige Iterationsschritte sind notig).

(2) Das Verfahren kann divergieren, falls der Startwert nicht nahe genug an

der Losung liegt.

(3) Fur das Newton-Verfahren gilt die Fehlerabschatzung

|xn+1 − x∗| ≤ Ln |xn+1 − x1| ≤ Ln (b− a) ,

wenn |f ′ (x)| ≤ L fur alle x ∈ I = [a, b].

(4) Die analytische Berechnung der Ableitung muss vorliegen.

(5) Das Newton-Verfahren konvergiert immer fur eine auf IR konvexe oder

konkave Funktion, die eine Nullstelle mit f ′ (x0) 6= 0 besitzt.

(6) Die Konvergenz des Newton-Verfahrens kann man auch sicherstellen, wenn

f eine 3-mal stetig differenzierbare Funktion ist mit der Eigenschaft

f ′ (x) 6= 0 fur alle x ∈ I und

∣∣∣∣∣f (x) f ′′ (x)f ′ (x)2

∣∣∣∣∣ ≤ K < 1 fur alle x ∈ I.

Je kleiner die Konstante K, desto besser ist die Konvergenz.

Falls man eine schlechte Schatzung fur den Startwert hat, sollte man sich zu-

nachst mit dem Bisektionsverfahren eine gute Startnaherung verschaffen

und anschließend das Newton-Verfahren verwenden. Oftmals kann man durch

Zeichnen des Funktionsgraphen einen guten Startwert x0 finden.



Beispiele CD.15 (Mit Maple-Worksheet):

©1 Gesucht ist die Nullstelle der Funktion

f (x) = 0.5− x + 0.2 sin(x)

im Intervall [0, 1] (vgl. Beispiel CD.8). Mit

f ′ (x) = −1 + 0.2 cos(x)

lautet die Newtonfolge

xn+1 = xn −0.5− xn + 0.2 sin (xn)−1 + 0.2 cos (xn)

mit dem Ergebnis

n xn f (xn)0 0.5 0.09581 0.6169 −6 · 10−4

2 0.6154 0

Nach 2 Iterationen hat man eine Genauigkeit von 4 Dezimalstellen, im

Vergleich zu 6 Iterationen mit dem Banachverfahren.

©2 Gesucht ist die Nullstelle der Funktion

f (x) = x3 −√

x2 + 1

im Intervall [1, 2] (vgl. Beispiel CD.4). Mit

f ′ (x) = 3x2 − x√x2 + 1

stellt man die entsprechende Newtonfolge auf. Ergebnis:

n xn f (xn)0 1.5 1.57221 1.2343 0.29202 1.1573 0.02073 1.1510 0.00014 1.1509 0.6 · 10−8

Nach 4 Iterationen hat man eine Genauigkeit von 8 Dezimalstellen.



Realisierung des Newton-Verfahrens mit Maple

Der Algorithmus des Newton-Verfahrens wird direkt in die Prozedur new-

ton ubernommen. Der Aufruf der Prozedur newton erfolgt durch Angabe

des Funktionsausdrucks und des Startwertes x0. Durch Verwendung des D-

Operators in der Maple-Prozedur newton muss die Ableitung dieser Funktion

nicht explizit bestimmt werden.

> newton := proc ()

> #Berechnung einer Nullstelle mit dem Newton-Verfahren

> #Der Aufruf erfolgt durch newton (ausdruck, var = startwert)

> local iter, x0, xna, xnn, delta, func, f, x;

> func := args[1]: x := op(1, args[2]); x0 := op(2, args[2]);

> f := unapply (func, x):

> iter := 0: delta := 1e-9:

> xna := evalf (x0):

> xnn := xna - f(xna)/D(f)(xna):

> while abs(xna - xnn) > delta

> do iter := iter + 1:

> print (iter, xna, f(xna));

> xna := xnn:

> xnn := xna - f(xna)/D(f)(xna):

> od;

> print (’Die Nullstelle liegt nach ’, iter,’Iterationen bei xi = ’,xnn);

> end:

Visualisierung mit Maple: Auf der CD-Rom befindet sich eine er-

weiterte Maple-Prozedur, newton ext, die den Konvergenzprozess

in Form einer Animation visualisiert.

Beispiel CD.16 (Mit Maple). Gesucht ist eine Nullstelle der Funktion

f (x) = −6x

√x2 +

(12

)2 − 0.01√x2 +

(12

)2 + 1

im Intervall [0, 0.5].> y := -6 ∗ x ∗ (sqrt(xˆ2 + (1/2)ˆ2) - 1/100) / sqrt(xˆ2 + (1/2)ˆ2) + 1:

> newton (y, x = 0.5);

1, 0 .5, −1.9575735932, 0.1714142824, −0.0090276863, 0.1698837573, −0.219 10−6

DieNullstelle liegt nach , 3, Iterationen bei xi =, 0.1698837202

Nach 3 Iterationen ist die Losung bis auf 6 Dezimalstellen genau berechnet.



Anwendung des Newton-Verfahrens: Berechnung von Wurzeln.

Gesucht ist die Quadratwurzel√

a einer positiven Zahl a. Wir interpretieren√a als die einzige positive Nullstelle der Funktion

f(x) = x2 − a.

Zur numerischen Berechnung wenden wir das Newton-Verfahren auf diese Funk-

tion an. Mit

f ′(x) = 2x

erhalt man die Newtonfolge

xn+1 = xn −f (xn)f ′ (xn)

= xn −x2

n − a

2 xn=

2 x2n − x2

n + a

2 xn=

12

(xn +

a

xn

).

Setzt man x0 := a und iteriert gemaß

xn+1 :=12

(xn +

a

xn

)fur n = 0, 1, 2, . . . , hat man eine schnell konvergierende Folge (vgl. Beispiel

??.??: Babylonisches Wurzelziehen).

Beispiel CD.17. Berechnung von√

3 mit obigem Schema

n 0 1 2 3 4 5xn 3.00000 2.00000 1.75000 1.73214 1.73205 1.73205

Die angegebene Methode ist eine der besten zur Berechnung von Quadratwur-

zeln. Die meisten Computerprogramme beruhen darauf.

Bemerkung: Dieses Verfahren ist nicht nur auf die Berechnung von Quadrat-

wurzeln beschrankt, sondern kann auch zur Berechnung von k-ten Wurzeln

herangezogen werden. Denn k√

a ist die positive Nullstelle von

f(x) = xk − a.

Mit f ′ (x) = k xk−1 lautet die Newtonfolge

xn+1 =1k

((k − 1) xn −

a

xk−1n

)n = 0, 1, 2, 3, . . . .



17.6 17.6 Regula falsiZur naherungsweisen Bestimmung der Nullstelle ξ einer Funktion mit dem

Newton-Verfahren ist die Berechnung der Ableitung f ′ erforderlich, so dass die

Differenzierbarkeit von f vorausgesetzt werden muss. Auch die Berechnung von

f ′ kann in praktischen Fallen mit Schwierigkeiten verbunden sein. Die regula

falsi ist ein Iterationsverfahren, das nicht auf Ableitungen zuruckgreift, dafur

aber zwei Startwerte x0 und x1 benotigt.

Geometrisch erhalt man die regula falsi, indem die Tangente des Newton-

Verfahrens durch die Sekante der Punkte (x0, f (x0)) , (x1, f (x1)) ersetzt wird

(siehe Abb. 17.11).

Abb. 17.11. Geometrische Interpretation der regula falsi

Aufstellen der Formeln. Die Sekantengleichung durch die Punkte (x0, f (x0)),(x1, f (x1)) lautet

f (x1)− f (x0)x1 − x0

=y − f (x0)

x− x0

und der Schnittpunkt x2 mit der x-Achse (y = 0) ist

x2 = x0 − f (x0)x1 − x0

f (x1)− f (x0).

Durch Iteration erhalt man den folgenden Algorithmus:

Algorithmus (regula falsi)

(1) Initialisierung: Wahle zwei Startwerte x0 und x1; δ := 10−6.

(2) Iteration:

(a) Iterationsvorschrift: xn+1 = xn−1 − f (xn−1)xn − xn−1

f (xn)− f (xn−1)


17.7 Bestimmung von Polynom-Nullstellen 35

(b) Abbruchbedingung

i. Falls |xn+1 − xn| < δ, dann ξ = xn+1. Stop.

ii. Falls |xn+1 − xn| ≥ δ, dann weiter mit (a).

Die Konvergenz des Verfahrens ist in der Regel etwas langsamer als die des

Newton-Verfahrens. Wesentlich fur die Konvergenz ist, dass die Startwerte x0

und x1 nahe an der Nullstelle ξ liegen.

Beispiel CD.18. Gesucht ist eine Nullstelle der Funktion

f (x) = −6x

√x2 +

(12

)2 − 0.01√x2 +

(12

)2 + 1

im Intervall [0, 0.5] (vgl. Beispiel CD.16). Mit den Startwerten x0 = 0.2 und

x1 = 0.4 erhalten wir folgende Iterationsfolge

n xn

1 1.7000002 1.6988373 1.698837

Der Funktionswert von x3 ist f (x3) ≈ 10−12.

17.717.7 Bestimmung von Polynom-NullstellenBisher haben wir uns dem allgemeinen Problem zugewandt, Nullstellen einer

Funktion numerisch zu bestimmen. Oftmals sind die Nullstellenprobleme auf

Polynome beschrankt. Dann kann man zwar die allgemeinen Verfahren an-

wenden, die Rechenzeiten konnen aber erheblich verringert werden, wenn zur

Funktionsauswertung der Polynomfunktion f das Horner-Schema (→ ??)

benutzt wird:

f (x) = ak xk + ak−1 xk−1 + . . . + a1 x + a0

= {. . . [[(ak x + ak−1) x + ak−2] x + ak−3] x + . . .}x + a0

= (x− x1)[bk xk−1 + bk−1 xk−2 + . . . + b2 x + b1

]+ b0

mit bk = ak , bk−1 = ak−1 + bk x , . . . , b2 = a2 + b3 x , b1 = a1 + b2 x und

b0 = f (x1). Die Vorteile des Horner-Schemas sind, dass es sehr schnell ist und

dass Rundungsfehler vermieden werden.



Algorithmus zur Berechnung von f(x1):bk := ak

bi−1 := ai−1 + bi x1 i = k, k − 1, . . . , 1f (x1) = b0.

Das Horner-Schema kann auch zur Berechnung von f ′(x1) herangezogen wer-

den, denn mit der Produktregel folgt fur die Ableitung der Funktion

f (x) = (x− x1)[bk xk−1 + bk−1 xk−2 + . . . + b2 x + b1

]+ b0

f ′ (x) =[bk xk−1 + bk−1 xk−2 + . . . + b2 x + b1

]+

+(x− x1)[(k − 1) bk xk−2 + (k − 2) bk−1 xk−3 + . . . + b2

]⇒ f ′ (x1) = g (x1) = bk xk−1

1 + bk−1 xk−21 + . . . + b2 x1 + b1.

Mit den durch das Horner-Schema berechneten Koeffizienten bi gilt

ck = bk

ci−1 = bi−1 + ci x1 i = k, k − 1, . . . , 2−

⇒ f ′ (x1) = c1.

Beispiel CD.19. Berechnung der Ableitung des Polynoms

f (x) = 4x3 − 5x2 + 2x + 1

im Punkte x1 = 2 mit dem doppelten Horner-Schema:

4 −5 2 1x1 = 2 : + 8 6 16

4 3 8 17 = f(2)

x1 = 2 : + 8 224 11 30 = f

′(2)

Wenn das Newton-Verfahren auf die Polynomfunktion

f (x) = ak xk + ak−1 xk−1 + . . . + a1 x + a0

angewendet wird, muss bei jedem Iterationsschritt sowohl f(xn) als auch f ′ (xn)berechnet werden. Mit dem doppelten Horner-Schema erhalt man den Algo-

rithmus von Newton-Rhapson:


17.7 Bestimmung von Polynom-Nullstellen 37

Algorithmus (Newton-Rhapson) Polynomauswertung an der Stelle xn}p := a[k] ∗ xn + a[k − 1]ps := a[k]DO i := k − 2, 0, −1 {Schleife von k − 2 bis 0 in Schritten −1}

ps := p + ps ∗ xn

p := a[k] + p ∗ xn

ENDDO

p gibt den Wert des Polynoms und ps den Wert der Ableitung an der Stelle xn

an. Die Newton-Iteration lautet dann

xn+1 := xn −p

psn = 0, 1, 2, . . . .

Bei diesem Algorithmus wird davon ausgegangen, dass die Koeffizienten des

Polynoms p(x) als Array deklariert sind.

MAPLE-Worksheets zu Kapitel 17

Die folgenden elektronischen Arbeitsblatter stehen fur Kapitel 17 mit

Maple zur Verfugung.

Bisektionsmethode

Pegasusverfahren

Newton-Verfahren

Banach-Verfahren

Sekantenverfahren / Regula falsi



17.8 17.8 Zusammenstellung der MAPLE-Prozeduren

fsolve(f(x)=0, x, x0..x1) Maple-Befehl zum numerisches Losen der

Gleichung f(x) = 0 im Bereich zwischen x0

und x1.

bise(f(x), x = x0..x1) Numerisches Losen der Gleichung f(x) = 0im Bereich zwischen x0 und x1 mit dem Bi-

sektionsverfahren.

bise ext(f(x), x = x0..x1) Bisektionsverfahren fur f(x)=0

und Visualisierung des Iterationsprozesses

durch eine Animation.

Pegasus(f(x), x = x0..x1) Numerisches Losen der Gleichung f(x) = 0im Bereich zwischen x0 und x1 mit dem

Pegasusverfahren.

banach(f(x), x = x0) Numerisches Losen der Gleichung f(x) = x

mit dem Startwert x = x0 durch das Banach-

Verfahren.

newton(f(x), x = x0) Numerisches Losen der Gleichung f(x) = 0mit dem Startwert x = x0 durch das

Newton-Verfahren.

newton ext(f(x),x=a..b,x0) Newton-Verfahren bei der Gleichung f(x)=0

mit dem Startwert x = x0 und Visualisierung

des Iterationsprozesses durch eine Animation.

refa(f(x), x = a..b, x0, x1) Numerisches Losen der Gleichung f(x) = 0mit den Startwerten x0 und x1 durch das

Sekantenverfahren (regula falsi) und Visuali-

sierung des Iterationsprozesses.


17.9 Aufgaben zum numerischen Losen von Gleichungen 39

17.917.9 Aufgaben zum numerischen Losen von Gleichungen

17.1 Bestimmen Sie mit dem Bisektionsverfahren die Nullstelle der Funktion f (x) =

(ln x)3− ln(√

x2 + 1)

im Intervall [1, 4] bis auf 5 Dezimalstellen genau. Wie

viele Iterationen werden benotigt?

17.2 Erstellen Sie in Maple eine Prozedur fur das Pegasus-Verfahren und bestim-

men Sie mit dieser Prozedur die Nullstelle der Funktion aus Aufgabe 17.1.

Vergleichen Sie die Anzahl der Iterationen.

17.3 Gesucht wird die Losung der transzendenten Gleichung x = cos x im

Intervall[0, π

4

]. Man berechne die Losung mit dem Banachschen Iterations-

verfahren fur die Startwerte x0 = 1 und x0 = 0.4.

17.4 Gegeben ist die Gleichung 2 ex = 3 x2. Man lose diese Gleichung numerisch

mit dem Newton-Verfahren. (Setze x0 = 1, x0 = −1 als Startwert).

17.5 Man gebe ein Verfahren zur Berechnung von 3√

a an. Man berechne anschlie-

ßend 3√

a fur a = 2, a = 4, a = 8.

17.6 Bestimmen Sie eine Nullstelle der Funktion f (x) = x5 + 3 x3 + 1 mit dem

Algorithmus von Newton-Rhapson und dem Startwert x0 = 1.5.

17.7 Man bestimme mit Maple alle Nullstellen von f (x) = x5 + 3 x3 + 1.

17.8 Bestimmen Sie die Nullstelle der folgenden Funktionen im Intervall [0, 4]

a) f (x) = 53

exp( 15

(x + 1)13 )− x b) f (x) = sin(ln

(x2 + 2

)2).

17.9 Wie lautet die Losung der folgenden Gleichungen im Intervall [0, 4]?

a)(e−x

)4= sin x + cos x + 1 b) (ex)4 = sin x + cos x + 1.

17.10 Kettenkarussell: Ein Kettenkarussell mit einer Tragstange von r = 2 m

und einer Kettenlange von l = 4 m benotigt fur einen Umlauf T = 5 s. Wie

groß ist die Winkelauslenkung α der Kette, wenn die Gleichgewichtslage

durch tan α = ω2

g(r + l sin α) bestimmt ist?

17.11 Strahlung eines schwarzen Korpers: Ein schwarzer Korper sendet bei

der absoluten Temperatur T Strahlung aus. Mit steigender Temperatur ver-

schiebt sich das Maximum der Strahlungsintensitat zu kurzeren Wellenlangen

hin. Es gilt λmax (T ) = αz·T mit α = 14.3881 · 10−3m K. Die Konstante z ist

die Losung von e−z = 1− 15

z. Man bestimme z.

17.12 Balkenschwingung: Die Schwingungsformen eines Balkens der Lange L,

der an beiden Seiten fest eingespannt ist, sind gegeben durch die Eigenwert-

gleichung

cosh (K L) cos (K L) = 1

wenn cosh (x) := 12

(ex + e−x

). Bestimmen Sie fur L = 1 die ersten 3

Schwingungsformen K1, K2, K3 6= 0, welche die obige Gleichung erfullen.

