Analysis 1 || Numerische Lösung von Gleichungen

192

§ 17 Numerische Losung von Gleichungen

Wir beschaftigen uns jetzt mit der Losung von Gleichungen f (x) = 0, wobei f ei-ne auf einem Intervall vorgegebene Funktion ist. Nicht immer kann man die Losun-gen, wie dies etwa bei quadratischen Polynomen der Fall ist, durch einen explizitenAusdruck angeben. Es sind Naherungsmethoden notwendig, bei denen die Losungenals Grenzwerte von Folgen dargestellt werden, deren einzelne Glieder berechnet wer-den konnen. Fur die Brauchbarkeit eines Naherungsverfahrens ist es wichtig, Fehler-abschatzungen zu haben, damit man weiß, wann man bei vorgegebener Fehlerschrankedas Verfahren abbrechen darf.

Ein Fixpunktsatz

Es tritt haufig das Problem auf, eine Gleichung der Form f (x) = x losen zumussen, wo f : [a,b]→ R eine stetige Funktion ist. Hier bietet sich folgendesNaherungsverfahren an. Sei x0 ein Naherungswert und

xn := f (xn−1) fur n � 1 .

Falls die Folge (xn) wohldefiniert ist (d.h. jedes xn wieder im Definitionsbe-reich von f liegt) und gegen ein ξ ∈ [a,b] konvergiert, so ist ξ eine Losung derGleichung, denn aus der Stetigkeit von f folgt

ξ = limn→∞

xn = limn→∞

f (xn−1) = f (ξ) .

Einen wichtigen Fall, in dem das Verfahren konvergiert, enthalt der folgendeSatz. Bild 17.1 veranschaulicht das Iterationsverfahren am Graphen von f .

x

y

x0x1 x2

y = x

y = f (x)f (x0)

f (x1)

Bild 17.1

O. Forster, Analysis 1, Grundkurs Mathematik DOI 10.1007/978-3-658-00317-3_17, © Springer Fachmedien Wiesbaden 2013

§ 17 Numerische Losung von Gleichungen 193

Satz 1. Sei D ⊂ R ein abgeschlossenes Intervall und f :D→ R eine differen-zierbare Funktion mit f (D)⊂D. Es gebe ein q < 1, so dass | f ′(x)|� q fur allex ∈ D. Sei x0 ∈ D beliebig und

xn := f (xn−1) fur n � 1 .

Dann konvergiert die Folge (xn) gegen die eindeutige Losung ξ ∈ D der Glei-chung f (ξ) = ξ. Es gilt die Fehlerabschatzung

|ξ− xn|� q1−q

|xn− xn−1|� qn

1−q|x1− x0| .

Bemerkung. Wie die Fehlerabschatzung zeigt, kann man aus der Differenzzweier aufeinanderfolgender Naherungswerte auf die Genauigkeit der Nahe-rung schließen. Fur q � 1

2 etwa ist der Fehler der n-ten Naherung nicht großerals der Unterschied zwischen der (n−1)-ten und der n-ten Naherung.

Das Verfahren konvergiert umso schneller, je kleiner q ist. Dies kann manmanchmal durch geeignete Umformungen erreichen. Es sei etwa die Glei-chung F(x) = 0 zu losen, wo F eine stetig differenzierbare Funktion ist. Fureinen Naherungswert x∗ der Losung sei F ′(x∗) =: c = 0. Setzt man f (x) :=x− 1

cF(x), so ist die Gleichung F(ξ) = 0 aquivalent mit f (ξ) = ξ. Es gilt

f ′(x∗) = 0, also ist | f ′(x)| klein, falls x hinreichend nahe bei x∗ liegt.

Beweis von Satz 1

a) Aus dem Mittelwertsatz erhalt man

| f (x)− f (y)|� q|x− y| fur alle x,y ∈ D .

Daraus folgt insbesondere

|xn+1− xn|= | f (xn)− f (xn−1)|� q|xn− xn−1|und durch Induktion uber n

|xn+1− xn|� qn|x1− x0| fur alle n ∈ N .

Da

xn+1 = x0 +n

∑k=0

(xk+1− xk) ,

und die Reihe ∑∞k=0(xk+1 − xk) nach dem Majorantenkriterium konvergiert,

existiert

ξ := limn→∞

xn .

194 § 17 Numerische Losung von Gleichungen

Weil D ein abgeschlossenes Intervall ist, liegt ξ in D und genugt nach demeingangs Bemerkten der Gleichung ξ = f (ξ).

b) Zur Eindeutigkeit. Ist η eine weitere Losung der Gleichung η = f (η), sogilt

|ξ−η|= | f (ξ)− f (η)|� q|ξ−η| ,woraus wegen q < 1 folgt |ξ−η|= 0, also ξ = η.

c) Fehlerabschatzung. Fur alle n � 1 und k � 1 gilt

|xn+k− xn+k−1|� qk|xn− xn−1| .Da ξ− xn = ∑∞

k=1(xn+k− xn+k−1), folgt daraus

|ξ− xn|�∞

∑k=1

qk|xn− xn−1|= q1−q

|xn− xn−1|� qn

1−q|x1− x0| .

(17.1) Als Beispiel wollen wir das Maximum der Funktion F:R∗+ → R,

F(x) :=1

x5(e1/x−1

)bestimmen, vgl. Bild 17.2.

�x

�y

0.5 1

10

20

y =1

x5(e1/x−1)

��

Bild 17.2 Die Plancksche Strahlungsfunktion

Die Funktion F hangt eng mit der Planckschen Strahlungsfunktion

J(λ) =c2h

λ5(exp(

chλkT

)−1)


zusammen, welche die Strahlungsintensitat eines schwarzen Korpers bei derabsoluten Temperatur T in Abhangigkeit von der Wellenlange λ angibt; da-bei ist c die Lichtgeschwindigkeit, h die Plancksche und k die BoltzmannscheKonstante. Setzt man x = kT

ch λ, so ist

J(λ) =k5T 5

c3h4 F(x) .

Fur x > 0 ist

F ′(x) =−5x4(

e1/x−1)− x3e1/x

x10(e1/x−1

)2 ,

also F ′(x) = 0 genau dann, wenn

5x(

e1/x−1)− e1/x = 0 .

Substituiert man t := 1/x, so ist dies aquivalent mit

5(1− e−t)= t .

Mit f (t) := 5(1− e−t) hat man also die Gleichung f (t) = t zu losen. Wir zei-gen zunachst, dass die Gleichung in R∗+ genau eine Losung t∗ besitzt, die imIntervall [4,5] liegt. Es ist f ′(t) = 5e−t , also f ′(t) > 1 fur t < log5. Im Inter-vall [0, log5] ist also die Funktion f (t)− t streng monoton wachsend. Wegenf (0) = 0 gilt f (t) > t fur alle t ∈ ]0, log5]. Fur t > log5 gilt f ′(t) < 1, alsoist die Funktion f (t)− t im Intervall [log5,∞[ streng monoton fallend, hat alsodort hochstens eine Nullstelle. Wegen

f (4) = 4.90 . . . > 4 ,

f (5) = 4.96 . . . < 5

gibt es nach dem Zwischenwertsatz tatsachlich eine Nullstelle t ∗ von f (t)− tim Intervall [4,5]. Es ist

q := supt∈[4,5]

| f ′(t)|= f ′(4) = 5e−4 = 0.09157 . . . ,

q1−q

= 0.1008 . . . ,

also konvergiert die Folge t0 := 5, tn+1 := f (tn), gegen t∗ und man hat dieFehlerabschatzung

|t∗ − tn|� 0.101 |tn− tn−1| .


Man braucht also nur solange zu rechnen, bis die Differenz aufeinander fol-gender Glieder eine vorgegebene Fehlerschranke ε unterschreitet. Fuhren wirdies in ARIBAS fur ε = 10−6 mit folgender Programmschleife durch

==> t := 5.0;eps := 10**-6; delta := 1;while delta > eps do

writeln(t);t0 := t;t := 5*(1 - exp(-t0));delta := abs(t-t0);

end;t.

so erhalten wir die Ausgabe

5.000000004.966310264.965155934.965115694.96511428-: 4.96511423

Also ist t∗ = 4.965114 . . . . Fur das ursprungliche Problem bedeutet das, dassdie Gleichung F ′(x) = 0 in R∗+ genau eine Losung hat und zwar

x∗ =1t∗

= 0.2014052±10−7.

Da limx↘0 F(x) = 0 und limx→∞ F(x) = 0, hat die Funktion F an der Stellex∗ ihr einziges Maximum. Die maximale Strahlungsintensitat eines schwarzenKorpers der Temperatur T liegt also bei der Wellenlange

λmax = 0.2014chkT

.

Das Newtonsche Verfahren

Das Newtonsche Verfahren zur Losung der Gleichung f (x) = 0 besteht darin,bei einem Naherungswert x0 den Graphen von f durch die Tangente zu erset-zen und deren Schnittpunkt mit der x-Achse als neuen Naherungswert x1 zubenutzen und dann das Verfahren zu iterieren, vgl. Bild 17.3.


x

yy = f (x)

x1x2 x0Bild 17.3

Formelmaßig ausgedruckt bedeutet das

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

, (n ∈N).

Sei f in dem abgeschlossenen Intervall D definiert und stetig differenzierbarmit f ′(x) = 0 fur alle x ∈ D. Falls die durch die obige Iterationsvorschrift ge-bildete Folge (xn) wohldefiniert ist und gegen ein ξ ∈ D konvergiert, so folgtaus Stetigkeitsgrunden

ξ = ξ− f (ξ)f ′(ξ)

, also f (ξ) = 0 .

Im Allgemeinen braucht das Verfahren jedoch nicht zu konvergieren (Bild17.4).

x

y

y = f (x)

x1 x2

x0

Bild 17.4

Einen wichtigen Fall, in dem Konvergenz auftritt, enthalt der folgende Satz.

Satz 2. Es sei f : [a,b]→R eine zweimal differenzierbare konvexe Funktion mitf (a) < 0 und f (b) > 0. Dann gilt:

a) Es gibt genau ein ξ ∈ ]a,b[ mit f (ξ) = 0.

b) Ist x0 ∈ [a,b] ein beliebiger Punkt mit f (x0) � 0, so ist die Folge


, (n ∈ N),


wohldefiniert und konvergiert monoton fallend gegen ξ.

c) Gilt f ′(ξ) � C > 0 und f ′′(x) � K fur alle x ∈ ]ξ,b[, so hat man fur jedesn � 1 die Abschatzungen

|xn+1− xn|� |ξ− xn|� K2C|xn− xn−1|2 .

Bemerkungen

1) Analoge Aussagen gelten naturlich auch, falls f konkav ist oder f (a) > 0und f (b) < 0 gilt.

2) Die Fehlerabschatzung sagt, dass beim Newtonschen Verfahren sogenann-te quadratische Konvergenz vorliegt. Ist etwa K

2C großenordnungsmaßig gleich1 und stimmen xn−1 und xn auf k Dezimalen uberein, so ist der Naherungs-wert xn auf 2k Dezimalstellen genau und bei jedem weiteren Iterationsschrittverdoppelt sich die Zahl der gultigen Stellen.

Beweis von Satz 2

a) Da f ′′(x) � 0 fur alle x ∈ ]a,b[, ist die Funktion f ′ im ganzen Intervall [a,b]monoton wachsend. Nach §11, Satz 2, existiert ein q ∈ [a,b] mit

f (q) = inf{ f (x) : x ∈ [a,b]}< 0 .

Falls q = a, gilt f ′(q) = 0, also f ′(x) � 0 fur x � q. Die Funktion f ist also imIntervall [a,q] monoton fallend und kann dort keine Nullstelle haben.

In jedem Fall liegen alle Nullstellen von f : [a,b]→ R im Intervall ]q,b[ undnach dem Zwischenwertsatz gibt es dort mindestens eine Nullstelle. Ange-nommen, es gabe zwei Nullstellen ξ1 < ξ2. Nach dem Mittelwertsatz existiertein t ∈ ]q,ξ1[ mit

f ′(t) =f (ξ1)− f (q)

ξ1−q=− f (q)ξ1−q

> 0 ,

also gilt auch f ′(x) > 0 fur alle x � ξ1. Die Funktion f ist also im Intervall[ξ1,b] streng monoton wachsend und kann keine zweite Nullstelle ξ2 > ξ1

besitzen.

b) Sei x0 ∈ [a,b] mit f (x0) � 0. Dann ist notwendig x0 � ξ. Wir beweisen durchInduktion, dass fur die durch



definierte Folge gilt f (xn) � 0 und ξ � xn � xn−1 fur alle n.

Induktionsschritt n→ n+1. Aus xn � ξ folgt f ′(xn) � f ′(ξ) > 0, also f (xn)f ′(xn)

� 0

und daher xn+1 � xn. Als nachstes zeigen wir f (xn+1) � 0.

Dazu betrachten wir die Hilfsfunktion

ϕ(x) := f (x)− f (xn)− f ′(xn)(x− xn) .

Wegen der Monotonie von f ′ gilt

ϕ′(x) = f ′(x)− f ′(xn) � 0 fur x � xn .

Da ϕ(xn) = 0, ist ϕ(x) � 0 fur x � xn, also insbesondere

0 � ϕ(xn+1) = f (xn+1)− f (xn)− f ′(xn)(xn+1− xn) = f (xn+1) .

Wegen f (xn+1) � 0 muss aber xn+1 � ξ gelten, da man sonst einen Wider-spruch zum Zwischenwertsatz erhielte.

Wir haben damit bewiesen, dass die Folge (xn) monoton fallt und durch ξ nachunten beschrankt ist. Also existiert limxn =: x∗. Nach dem eingangs Bemerktengilt dann f (x∗) = 0 und wegen der Eindeutigkeit der Nullstelle ist x∗ = ξ.

c) Da f ′ monoton wachst und f ′(ξ) � C, gilt f ′(x) � C fur alle x � ξ. Darausfolgt f (x) � C(x−ξ) fur alle x � ξ, insbesondere

|ξ− xn|� f (xn)C

.

Um f (xn) abzuschatzen, betrachten wir die Hilfsfunktion

ψ(x) := f (x)− f (xn−1)− f ′(xn−1)(x− xn−1)− K2

(x− xn−1)2.

Differentiation ergibt

ψ′(x) = f ′(x)− f ′(xn−1)−K(x− xn−1) ,

ψ′′(x) = f ′′(x)−K � 0 fur alle x ∈ ]ξ,b[ .

Die Funktion ψ′ ist also im Intervall [ξ,b] monoton fallend. Da ψ′(xn−1) = 0,folgt ψ′(x) � 0 fur x ∈ [ξ,xn−1]. Da auch ψ(xn−1) = 0, folgt weiter ψ(x) � 0fur x ∈ [ξ,xn−1], insbesondere ψ(xn) � 0, d.h.

f (xn) � K2

(xn− xn−1)2, also

|ξ− xn|� f (xn)C

� K2C

(xn− xn−1)2.

Damit ist Satz 2 vollstandig bewiesen.


(17.2) Beispiel. Sei k eine naturliche Zahl � 2 und a ∈R∗+. Wir betrachten dieFunktion

f :R+ → R , f (x) := xk−a .

Es ist f ′(x) = kxk−1 und f ′′(x) = k(k− 1)xk−2 � 0 fur x � 0, also f konvex.Das Newtonsche Verfahren zur Nullstellenberechnung ist daher anwendbar. Esgilt

x− f (x)f ′(x)

= x− xk−a

kxk−1 =1k

((k−1)x+

a

xk−1

).

Fur beliebiges x0 mit xk0 > a konvergiert deshalb die Folge

xn+1 :=1k

((k−1)xn +

a

xk−1n

), (n ∈N) ,

gegen k√

a. (Falls xk0 < a, ist xk

1 > a und das Verfahren konvergiert dann eben-falls.) Wir haben somit das in §6 beschriebene Verfahren zur Wurzelberech-nung als Spezialfall des Newton-Verfahrens wiedergefunden.

AUFGABEN

17.1. Sei k > 0 eine naturliche Zahl. Man zeige, dass die Gleichung x = tanxim Intervall (k− 1

2)π < x < (k + 12)π genau eine Losung ξ besitzt und dass die

Folge

x0 :=(k + 1

2

)π

xn+1 := kπ+ arctanxn , (n ∈N),

gegen ξ konvergiert. Man berechne ξ mit einer Genauigkeit von 10−6 fur dieFalle k = 1,2,3.

17.2. Man zeige, dass die Gleichung

(∗) log(1− x) =−2x

im Intervall 0 < x < 1 genau eine Losung x∗ besitzt und berechne sie mit einerGenauigkeit von 10−6.

Hinweis. Die Gleichung (∗) ist aquivalent mit der Fixpunktgleichung

x = 1− e−2x.


17.3. Man berechne alle reellen Nullstellen des Polynoms f (x) = x5− x− 15

mit einer Genauigkeit von 10−6.

17.4. a) Nach Beispiel (17.2) wird das Newtonsche Verfahren zur Berechnungder 3. Wurzel von a ∈ R∗+ durch die Iterationsvorschrift xn+1 = 1

3(2xn +a/x2n)

mit beliebigem Anfangswert x0 > 0 gegeben.

Man zeige, dass auch die durch

xn+1 = 12

(xn +

ax2

n

)rekursiv definierte Folge gegen 3

√a konvergiert und vergleiche die Konver-

genzgeschwindigkeit beider Verfahren.

b) Man untersuche das Konvergenzverhalten der durch

xn+1 = 12

(xn +

ax3

n

)bzw. xn+1 = 1

2

(xn +

ax4

n

)rekursiv definierten Folgen.

17.5. Man leite ein weitere hinreichende Bedingung fur die Konvergenz desNewton-Verfahrens zur Losung von f (x) = 0 her, indem man auf die Funktion

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

den Satz 1 anwende.

17.6. Sei a > 0 vorgegeben. Die Folge (an)n∈N werde rekursiv definiert durch

a0 := a und an+1 := aan fur alle n � 0.

a) Man zeige: Die Folge (an)n∈N konvergiert fur 1 � a � e1/e und divergiertfur a > e1/e.

Hinweis. Ein moglicher Grenzwert ist Fixpunkt der Abbildung x �→ ax.

b) Man bestimme den (exakten) Wert von limn→∞ an fur a = e1/e und einenumerische Naherung (mit einer Genauigkeit von 10−6) von limn→∞ an fura = 6/5.

c) Wie ist das Konvergenzverhalten der Folge fur einen Anfangswerta ∈ ]0,1[?

Documents

Analysis 1 || Numerische Lösung von Gleichungen