Vorlesungs-Skript Mathematik fu¨r...

Vorlesungs-Skript

Mathematik furWirtschaftsinformatiker

Rudiger Seydel

Universitat zu Koln

Mathematisches Institut

Version 2009

c© R. Seydel, Koln 2009

www.mi.uni-koeln.de/∼seydel

Vorwort

Dies ist das Skript zu meiner Vorlesung Mathematik fur Wirtschaftsinformatiker,

gelesen im Wintersemester 2008/2009 und im Sommersemester 2009. Im ersten Semester

ist die Vorlesung vierstundig, im zweiten Semester zweistundig. Dazu gehoren jeweils

Ubungen, welche ein wichtiger Teil der Veranstaltung sind.

Das Skript gibt nur den wesentlichen Inhalt der Vorlesung wieder. Zusatzliche

Erklarungen und Erganzungen werden wahrend der Vorlesung gegeben; das Skript ersetzt

nicht den Besuch der Vorlesung!

Fur Korrekturlesen bin ich Herrn Markus Lucking dankbar.

Koln, Juli 2009

Seydel: Mathematik I, Inhalt, WS 2008/09

Inhalt

Prolog 1

Kapitel 1: Elemente Praktischer Mathematik

1.1 Messen in der Ebene 3

1.2 Gleichungen, Ungleichungen 5

1.3 Mengen in der Ebene 6

1.4 Zahlen 7

1.5 Fehler 10

Kapitel 2: Lineare Algebra

2.1 Vektoren, Matrizen, Gleichungssysteme 17

2.2 Der Algorithmus von Gauß 22

2.3 Arbeiten mit Matrizen 23

2.4 Vektorraume 26

2.5 Dimension und Basis von Vektorraumen 28

2.6 Determinanten 31

2.7 Eigenwerte 33

2.8 Normen 35

2.9 Householder Matrizen 37

Kapitel 3: Analysis

3.1 Vollstandige Induktion 41

3.2 Komplexe Zahlen 42

3.3 Polynome und Rationale Funktionen 45

3.4 Der Euklidische Algorithmus; Kettenoperationen 49

3.5 Funktionen 50

3.6 Spezielle Funktionen 55

3.7 Grenzwert 59

3.8 Differentialrechnung 63

3.9 Integrale 69

3.10 Logarithmus und Exponentialfunktion 73

3.11 Reihen und Potenzreihen 74

3.12 Funktionen von mehreren Veranderlichen 79

Seydel: Mathematik II, Inhalt, SoSe 2009

Kapitel 4: Approximation mit Kurven

4.1 Approximation und Interpolation 81

4.2 Interpolation mit Polynomen 82

4.3 Interpolation mit Splines 87

4.4 Bezier-Kurven 91

4.5 Integration mit Trapezsummen; Extrapolation 93

4.6 Diskrete Fourier-Transformation 96

4.7 Fast Fourier-Transformation 99

4.8 Ausgleichsprobleme, data fit 103

Kapitel 5: Nichtlineare Gleichungssysteme und Iterationen

5.1 Losen einer skalaren Gleichung 107

5.2 Zur Konvergenz 108

5.3 Das allgemeine Newtonverfahren 110

5.4 Approximation der Jacobi-Matrix 111

Kapitel 6: Optimierung

6.1 Optimierungsprobleme 113

6.2 Methoden der Analysis 114

6.3 Lineare Optimierung 116

6.4 Konvexe Optimierung 120

Seydel: Mathematik II, Inhalt, SoSe 2009

Literatur

Als weiterfuhrende Literatur sind unter anderem fast alle Titel mit Hoherer Mathe-matik oder auch Ingenieurmathematik geeignet. Es ist nicht moglich, der Vielzahl hervor-

ragender Werke gerecht zu werden. Deswegen hier nur exemplarisch drei Werke:

R. Ansorge, H.J. Oberle: Mathematik fur Ingenieure I. Wiley-VCH

K. Meyberg, P. Vachenauer: Hohere Mathematik. Band 1. Springer-Verlag, Berlin

R. Sauer: Ingenieurmathematik. Springer-Verlag

Eine Formelsammlung ist nutzlich.

Seydel: Mathematik I, Kap. 1, WS 2008/09

Prolog

Charakterisierung Wissenschaftlicher Arbeit:

Modellierung & Simulation

Interpretation

Modellierung

Experimentklassisches

Simulation

PrognoseZustands−

Lösung

(Gleichung)Modell

‘‘Wirklichkeit’’

⋆ Modellierung = Beschreibung von Vorgangen in Natur, Wirtschaft und Technik durch

Gleichungen

⋆ Simulation = Anwendung mathematisch/numerischer Methoden zur Losung der Glei-

chungen

→ “mathware”

Der Doppelschritt “Modellierung & Simulation” ist zwingend!

Beispiele “Experiment unmoglich” da

- zu gefahrlich (Umweltrisiken, Wirtschaftsentwicklung)

- zu groß, experimentelle Restriktionen (Ozeanstromungen)

- zu lange Zeitraume (Bevolkerungsentwicklung, Klima)

- zu teuer (Windkanal wird durch Computer–Simulationen ersetzt.)

- existiert nicht (Saurier etc. im Kino)

Mathematik: Sprache unserer wissenschaftlich-technischen Welt, Schlusseldisziplin der

Hochtechnologie!

1


2


Kapitel 1 Elemente Praktischer Mathematik

1.1 Messen in der Ebene

die Ebene: der Ort aller mathematischen Erklarungen.

einfache mathematische Objekte:

Punkt, Gerade(nstuck), Kurve, Kreis, “Winkel” (Haken), Flachenstuck.

A. Messung / Zahlen

Charakterisierung obiger Objekte:

Punkt: Lage (zu einem Referenzpunkt)

Kurve, Geradenstuck: Lange, Neigung

Kreis: Durchmesser, Umfang

Schnitt von Geraden: Winkel

Flachenstuck: Inhalt

Zur Quantifizierung sind Zahlen erforderlich.

historisch: z.B. 2 Fuß, 3 Fingerbreit: Korpersystem, mit Anzahl der Wiederholungen.

−→ “Naturliche Zahlen” 1,2,3,... Bezeichnung: IN

Verhaltnisse: z.B. beim Kreis: π :=Umfang

Durchmesser

Hinweis: := meint: die “linke Seite” wird durch die “rechte Seite” definiert. Obiges πdefiniert die Kreiszahl.

Frage: Ist π ∈ IN ? (Antwort: nein! IN reicht nicht. Hierzu und zu Zahlen vgl.

spateren Abschnitt 1.4)

B. Große eines Winkels

1.) Messung in Grad: Teilung des Kreises in 360 Teile (willkurlich).

Ein Teil wird als Grad bezeichnet, 1◦,

Grad/Min/Sek: 1◦ = 60′, 1′ = 60′′

z.B. 40◦36′12′′

2.) im Bogenmaß (naturliches Maß)

1

r

ϕBogenlänge

Kreisbögen

ϕb = rBogenlänge

ϕ

3


Winkel im Bogenmaß=am Radius r ausgeschnittene Bogenlange b

r

dimensionslos, unabhangig vom Maßstab.

Umfang Vollkreis mit Radius r ist 2rπ ⇒ (“daraus folgt”)

im Gradmaß 360◦ 180◦ 90◦ 60◦ 45◦ 30◦ 1◦

im Bogenmaß 2π π π2

π3

π4

π6

π180 ≈ 0.01745 . . .

(Dezimal-Punkt !)

Orientierung:

math. posit. Sinn math. neg. Sinn

b > 0 b < 0

C. Koordinaten

1.) Kartesische Koordinaten eines Punktes P0

Vorgabe eines Punktes O und einer (x-)Achse; positive Drehung um 90◦ um O erzeugt

y-Achse (Schnittpunkt O). Lote von P0 auf die Achsen −→ Fußpunkte bestimmen x-

und y-Koordinate x0, y0

y

x

y

Lot auf x−Achse

oP

o

o

0 x

Man schreibt P0 = (x0, y0); O = (0, 0) heißt “Nullpunkt”.

Eindeutige Zuordnung zwischen der Ebene und allen Zahlenpaaren.

2.) Polarkoordinaten

Jeder Punkt 6= O kann eindeutig durch den Abstand r zum Nullpunkt und den Winkel

zwischen der positiven x-Achse und dieser Geraden dargestellt werden.

y

Lotϕ

r

P

x0

��

Zusammenhang zu kartesischen Koordinaten

x = r cos ϕ , y = r sin ϕ ,

r =√

x2 + y2 , ϕ =

{arccosx

rfalls y ≥ 0

2π − arccosxr

falls y < 0

4


1.2 Gleichungen, Ungleichungen

“=” seit dem spaten 16. Jahrhundert

Arten von Gleichungen

1. Identitat: z.B. 3 − 4x + 5x = 3 + x oder: 1 + 2 + . . . + n = 12n(n + 1)

2. Abbildungsgleichung: z.B. y = f(x) := (x + 3)2 − 4

Jedem x in einem gewissen Bereich wird ein y zugeordnet: “Funktion”.

3. Bestimmungsgleichung: z.B. x2 − 4 + 2x = 0 oder |x| − x2 = 0.

Hier heißt x “Unbekannte”.

Def. Absolutbetrag:

|x| ={

x falls x ≥ 0

−x falls x < 0

(Fallunterscheidungen notwendig, interessant oft dann, wenn komplizierter Ausdruck

|A(x)|)

4. Differentialgleichungen:

z.B. dydx

= −2y (oder y′ = −2y)

ist Gleichung fur eine Funktion y(x). In der Gleichung tritt y mit der ersten oder

hoheren Ableitungen auf.

(Losung: y(x) = ce−2x fur beliebige Konstanten c)(Probe: ...)

Ungleichungen

Großenvergleich x < y (x ist kleiner y und nicht gleich y)

x ≤ y (x ist “kleiner gleich” y) bzw. x > y , x ≥ yDie Ungleichung x < y gibt eine Abschatzung der Zahl x nach oben durch y an; y ist

Schranke (obere) zu x.

Beispiel (fur Ungleichungen, Abschatzungen, untere und obere Schranken)

Zeige: π ist keine naturliche Zahl!

Beweis:

umschreibendes Viereck mit Umfang 8 (Figur ...)

inneres 8-Eck mit Umfang d

“Einheitskreis” mit Radius 1 und Umfang c.

Offenbar gilt: c < 8 (8 ist obere Schranke zu c)

und: d < c (d ist untere Schranke); leicht zu zeigen: d > 6.

Beide Ungleichungen zusammengefaßt:

6 < d < c < 8 , es folgt:

6 < c < 8

π =c

2r=

c

2⇒ c = 2π ⇒

6 < 2π < 8 ⇒ 3 < π < 4

Also: π ist keine naturliche Zahl.

Def. Intervall: Durch das Ungleichungspaar a ≤ x ≤ b ist ein “Intervall” definiert als

die Menge aller x fur welche sowohl a ≤ x und x ≤ b gilt (gleichzeitig!). Das Intervall ist

nicht-leer, wenn a ≤ b.

5


Mengen-Schreibweise:

[a, b] := {x|a ≤ x ≤ b}

Bei Einschluß der Randpunkte spricht man von abgeschlossenem Intervall. Sonst:

offenes Intervall: {x|a < x < b}; Bezeichnung auch ]a, b[ oder (a, b).

Varianten: “halboffen”, a ≤ x < b, a < x ≤ b, falls nur ein Endpunkt zum Intervall

gehort.

Rechenregeln zu Betrag und Ungleichungen

x ≤ y , a ≤ b ⇒ x + a ≤ y + b

x ≤ y , 0 ≤ a ⇒ ax ≤ ay

x ≤ y , a < 0 ⇒ ax ≥ ay !

x ≤ y ⇒ −y ≤ −x

0 < x ≤ y ⇔ 0 <1

y≤

1

x

− |a| ≤ a ≤ |a| ,

| − a| = |a| ,

|ab| = |a| |b| , |a

b| =

|a|

|b|(falls b 6= 0)

|a| ≤ |b| ⇔ −b ≤ a ≤ b !

weiter gilt die “Dreiecksungleichung”

|a + b| ≤ |a| + |b|

Beweis:−|a| ≤ a ≤ |a|−|b| ≤ b ≤ |b|

Addition:

−(|a| + |b|) ≤ a + b︸︷︷︸

(Abk.)=:A

≤ |a| + |b|︸︷︷︸

=:B

Also −B ≤ A ≤ B ;

⇔ |A| ≤ B ⇔ |a + b| ≤ |a| + |b|

1.3 Mengen in der Ebene

geometrische Bedeutung von Gleichungen und Ungleichungen, wenn sowohl x als auch yvariabel sind.

Beispiele:

1.) a ≤ x ≤ b{(x, y) | a ≤ x ≤ b}, d.h. y bleibt frei

(Hinweis: In 3-dim. (x, y, z)-Raum ware durch a ≤ x ≤ b eine Scheibe definiert.

Also: Angabe (x, y) des einbettenden Raumes wichtig!)

2.) {(x, y) | a ≤ x ≤ b , y = −2}

6


3.) x ≥ −4 und 0 ≤ y ≤ 6 d.h. 3 Ungleichungen gleichzeitig!

(Hinweis zur Vorgehensweise: zuerst die Gleichungen aufmalen (ergibt potentielle

Rander), dann die richtige Seite feststellen (z.B. mit Testpunkten).

Halbstreifen als Schnitt von drei Halbebenen.

4.) 0 = x − y + 1 ist eine Gerade, y = x + 1

5.) y = −x2 + 1 und −1 ≤ x ≤ 3

6.) y2 ≤ x < 4 sind 3 Ungleichungen x < 4, −√

x ≤ y, y ≤ +√

x7.) x2 + y2 ≤ 1 (⇔ r2 ≤ 1)

8.) (x − 2)2 + (y + 1)2 = 4 , y ≥ −x + 1

x′ := x − 2, y′ := y + 1

Allgemein: Kreisgleichung

(x − a)2 + (y − b)2 = r2 ist Kreis mit Mittelpunkt (x, y) = (a, b)((Vorsicht: Vorzeichen!))

Schnitt von 2 Geraden

allg. Gerade in der Ebene:

ax + by + c = 0

Also: eine Gleichung in 2 Unbekannten x und y. x und y treten “linear” auf; lineare

Gleichung in x und y;

zwei Geraden in der Ebene:

a1x + b1y + c1 = 0 1. Gerade

a2x + b2y + c2 = 0 2. Gerade

2 Moglichkeiten:

1.) Die Geraden schneiden sich in einem Punkt

2.) Die Geraden sind “parallel” (sie schneiden sich nicht oder sind identisch)

Berechnung des Schnittpunktes

Addiere geeignete Vielfache der Gleichungen.

“geeignet”: so dass eine Gleichung mit nur einer Unbekannten entsteht.

allgemeines Verfahren: Gaußscher Eliminations-Algorithmus

1.4 Zahlen

A.) Naturliche Zahlen 1, 2, 3, 4, . . .(IN ist “abgeschlossen” bzgl. Addition und Multiplikation.)

Abschließung bzgl. der Subtraktion fuhrt zu:

B.) Ganze Zahlen

ZZ := IN ∪ 0 ∪ negative naturliche Zahlen

= {. . . ,−4,−3,−2,−1, 0, 1, 2, 3, . . .}

C.) Rationale Zahlen

IQ := { Bruche } ={m

n| m ∈ ZZ , n ∈ IN

}

7


Division (außer durch 0) in IQ unbeschrankt ausfuhrbar.

Satz: IQ ist abzahlbar! Denn: alle q ∈ IQ sind enthalten im Schema...

D.) Irrationale Zahlen = Zahlen, die nicht rational sind.

Satz: Es gibt irrationale Zahlen!

“Indirekter Beweis”: Annahme des Gegenteils;

hieraus Herleitung eines Widerspruchs zu den Annahmen.

Prinzip (A ⇒ B) ⇔ (¬B ⇒ ¬A)

Hier: Annahme s = mn

, ohne Einschrankung m und n teilerfremd (sonst kurzen)

(vgl. Ubung)

E.) Reelle Zahlen

Exponenten-Schreibweise (n ∈ IN): an = a · a · . . . · a︸︷︷︸

n mal

a−n =1

an, ao = 1

Motiv./Bsp.: 3.907 = 3 + 910

+ 71000

= 3 · 100 + 9 · 10−1 + 7 · 10−3 ist “endlicher”

Dezimalbruch, d.h. bricht nach endlich vielen Stellen ab.

reelle Zahlen:

IR := { alle endlichen und unendlichen Dezimalbruche}

= {p110k−1 + p210k−2 + . . . + pk100 + q110−1 + q210−2 + . . . | pi, qi ∈ {0, 1, 2, . . . , 9}}

= {p1p2 . . . pk . q1q2q3 . . .} “Positionssystem”

Beschrankung auf p, q ≤ 9 wegen der Eindeutigkeit der Darstellung.

geometrisch auf der Zahlengerade:

Intervallschachtelung: bricht man eine Zahl nach der m-ten Stelle hinter Dezimalpunkt

ab, so liegt die Zahl im Intervall der Breite 10−m. Hinzufugen der nachsten Ziffer ((m+1)-

te Ziffer) −→ Breite des Intervalles 10−m−1 u.s.w.

Intervall-Langen werden beliebig klein. −→ konvergiert gegen Punkt.

Damit aquivalente Definition von IR: alle Punkte auf der Zahlengerade −→ IR.

Bei den Dezimalzahlen ist 10 die “Basis”. Die reellen Zahlen konnen auch mit jeder anderen

Basis aufgebaut werden.

F.) Komplexe Zahlen

Der Zahlenbereich IR kann erweitert werden zu den Komplexen Zahlen, in denen auch

i :=√−1 etc. moglich ist. (−→ spater in Abschnitt 3.2)

G.) Maschinenzahlen

Def.: Gleitpunktdarstellung (floating-point representation):x = σ · m · BE

σ: Vorzeichen

m: Mantisse

B: Basis

E: Exponent

8


Def.: Normalisierte Gleitpunktzahl ( 6= 0): Gleitpunktzahl mit Eigenschaft B−1 ≤

m < 1.

Darstellung der Mantisse:

m = d1B−1 + d2B

−2 + d3B−3 + . . .

mit Ziffern (digits) di ∈ {0, 1, . . . , B − 1} und d1 6= 0 fur normalisierte Zahl.

Beispiel: 18.5 als Dezimalzahl [= (18.5)10], umrechnen in Dualzahl:

18.5 = 16 + 2 +1

2

= 1 ·24 + 0 ·23 + 0 · 22 + 1 · 21 + 0 · 20+ 1 · 2−1

↑ ↑ ↑

Ziffern Binarpunkt

= 10010.1

Schreibweise mit Basis gekennzeichnet:

(18.5)10 = (10010.1)2

normalisiert:

0.185 · 102 = 0.100101 · 25

Bemerkung: Bei diesem Beispiel wurden sowohl bei B = 10 als auch bei B = 2 nur

endlich viele Ziffern benotigt. Im Allgemeinen gibt es keine derartige Entsprechung!

Im Rechner stehen nur endlich viele Stellen zur Verfugung!

Definition: Die Zahlen, die in einem Rechner dargestellt werden konnen, heißen

Maschinenzahlen.

“Genauigkeit” misst letztlich den Abstand von Zahlen.

Frage: Was ist der kleinste Abstand zwischen zwei Maschinenzahlen?

Gedankenexperiment: mit 53 bit-Mantisse

0.1111 . . . . . 11 = 1/2 + . . . + 2−53 = 1 − 2−53 = 1 − 2−k

1.0000 . . . . . 00 = 1

(Die Binar-Ziffern heißen bit = binary digit.)

Definition: Es sei k die Anzahl der bit der Mantisse. Die Zahl 2−k heißt relative

Maschinengenauigkeit des Binar-Rechners.

Bezeichnung: ǫmach (oder eps, oder ǫ0) Bedeutung: ǫmach ist der kleinste relative

Abstand zwischen zwei Maschinenzahlen, und damit unterste Schranke fur alle mit

einem Rechner erreichbaren (rel.) Genauigkeiten!

Beispiel: von oben:

ǫmach = 2−53 = exp(−53 log 2)

= 1.11 . . ∗ 10−16

d.h., bei k = 53 ist eine relative Genauigkeit von maximal ca. 16 dezimalen Stellen

moglich.

9


Die Maschinenzahlen sind ungleichmaßig verteilt. Schematisch:

kleinste positive M.Z.0

Zahlengerade

größte positive M.Z.

Jede Zahl (Eingabe oder Resultat einer Rechnung) muss im Rechner durch eine Maschi-

nenzahl ersetzt werden:

x → fl(x)

Der Einfluss der dabei entstehenden Fehler kann groß sein.

1.5 Fehler

A.) relativer / absoluter Fehler

Motivation: Berechne f(x) =1 − cos x

xfur x = 0.0001

Taschenrechner: f(x) = 0.00004900000000...

exakt: f(x) = 0.00004999999995...

Definition/Bezeichnung: Es bezeichne x eine Naherung zum exakten x (oder f zu f ,

usw.)

x − x (oder x − x oder |x − x|) heißt absoluter Fehler.x−x

x(oder ...) heißt relativer Fehler.

Praxis: x (exakt) ist unbekannt, bekannt ist nur x, und eine Schatzung ξ fur den absoluten

Fehler. Dann: Schatzung fur den relativen Fehler ist | ξx|

Hinweis: Nur die Großenordnung des Fehlers ist von Interesse.

obiges Beispiel: maximal 2 Stellen sind exakt.

|f − f | = 0.00000099... ≈ 10−6

∣∣∣∣

f − f

f

∣∣∣∣= 2 · 10−2

Sprechweise (Dezimalsystem):

“Genauigkeit von j (dezimalen) Stellen” heißt:

| relativer Fehler | < 10−j

(im Sinne von maximalem ganzzahligem j)j “significant digits”

10


Beispiel: Aquatorumfang

x = 40000000 m

x = 40075161 m

⇒ relativer Fehler 7540075

≈ 0.0019 ≈ 10−3, d.h. knapp 3 Stellen genau. Absoluter

Fehler hier: 75161, gibt keinen Hinweis auf Genauigkeit. Schlimmer noch: Ubergang

zu anderer Skalierung (z.B. km) andert nicht die Genauigkeit, und auch nicht den

relativen Fehler, leider aber den absoluten Fehler.

Merke:

Der absolute Fehler ist nicht skalierungsunabhangig und kann leicht ma-

nipuliert werden. Zur Beschreibung der Genauigkeit ist i.A. (nur) der

relative Fehler von Bedeutung.

Problem: Grenzen des relativen Fehlers, wenn exaktes Resultat = 0.

B.) Erzeugen einer Maschinenzahl x → fl(x)

Beispiel: (k = 4 Dezimalstellen)

π = 3.1415926 . . .

↓ Normalisieren

0.31415926 · 101

ւ ց

0.3141 · 101 0.3142 · 101 benachbarte

Abschneiden Runden Maschinenzahlen

(round to zero) (round to nearest)

Satz 1:

∣∣∣∣

fl(x) − x

x

∣∣∣∣≤ ǫmach

(falls kein

overflow/underflow)

(folgt aus Definition von ǫmach)

Dabei gilt ǫmach = B1−k beim Abbrechen und ǫmach = 12B1−k beim Runden.

Kommentar: Bereits bei der Eingabe muss man einen Fehler der Große ǫmach erwarten!

C.) Grundrechenarten: + − ∗ ÷ Symbol : ◦

Satz 2:

Es seien x und y Maschinenzahlen. (!)

Falls kein overflow/underflow:

Der relative Fehler bei jeder der 4 Grundrechenarten

ist durch ǫmach beschrankt.

(folgt aus Satz 1: zuerst x ◦ y exakt als Zwischenresultat, danach fl(x ◦ y))

11


Das heißt ∣∣∣∣

fl(x ◦ y) − (x ◦ y)

x ◦ y

∣∣∣∣≤ ǫmach

Im Rechner gelten einige grundlegende mathematische Gesetze nicht! So gibt es Maschi-

nenzahlen x und y 6= 0 mit fl(x + y) = x. (z.B. x = 1, |y| < ǫmach).

Die Gesetze (a+b)+c = a+(b+c) (Assoziativitat) und a(b+c) = ab+ac (Distributivitat)gelten im Rechner i.A. nicht.

Merke:

Algebraisch aquivalente Umformungen konnen im

Rechner zu verschiedenen Resultaten fuhren!

D.) Spezielle Funktionen Auch bei der Berechnung der speziellen Funktion wie z.B.

√x, sin x, ex, arctan x

werden im Rechner durch Anwendung scharfsinniger Algorithmen der Mathematik meist

die gleichen Genauigkeiten (wie oben ǫmach) erreicht.

Gelegentlich ist allerdings nur der absolute Fehler beschrankt.

Zum Beispiel ist fur x ≈ 1 die Version ln(1 + x) (mit x ≈ 0) besser als ln(x).

E.) Algorithmen

Im Allgemeinen ist jede eingegebene Zahl x1, x2, . . . , xn fehlerbehaftet. (zumindest Run-

dungsfehler; Fehler meist noch großer wegen Mess- und Modellfehlern!)

Die Resultate y1, y2, . . . , ym hangen von der Eingabe ab:

x1

x2...

xn

Zuordnung

−−−−−−−→

ϕ

y1

y2...

ym

Frage: Wie pflanzen sich Fehler in der Eingabe (oder in den Zwischenschritten) bis zum

Resultat fort?

Beispiel: Berechne a2 − b2

Eingabe x1 = a, x2 = b, d.h. n = 2, y(= y1) = x21 − x2

2, d.h. m = 1

1. Moglichkeit: y = x21 − x2

2 =: ϕ(x1, x2)

2. Moglichkeit: y = (x1 − x2) · (x1 + x2) =: ϕ(x1, x2)

12


Zahlenbeispiel: a = .3237, b = .3134 (B = 10, k = 4)

1. Moglichkeit liefert: 0.6580 ∗ 10−2

2. Moglichkeit liefert: 0.6562 ∗ 10−2

exaktes Resultat: 0.656213 ∗ 10−2

Definition: Ein Algorithmus ist eine der Reihenfolge nach eindeutig festgelegte Sequenz

von endlich oder unendlich vielen “elementaren” Operationen.

Frage: Was sind “gute” Algorithmen, wie lasst sich die “Gute” verbessern?

Vorbemerkungen:

1. Eine bequeme aquivalente Schreibweise fur den relativen Fehler

ǫ =x − x

x

ist x = x(1 + ǫ).2. ∆ als Symbol fur absoluten Fehler: z.B. ∆x = x − x3. Vernachlassigen kleiner Terme:

a + bǫ + cǫ2=a + bǫ

wenn nur |ǫ| klein genug ist.

(Schreibweise = fur “in 1. Naherung”)

analog z.B.

a + bǫ + cǫ1ǫ2=a + bǫ

Schreibweise fur Terme hoherer Ordnung:

O(ǫ2) , oder T.h.O.

F.) Ausloschung

Analyse der Subtraktion positiver Zahlen: y = x1 − x2

y = fl(x1 − x2) mit x1 = x1(1 + ǫ1)

x2 = x2(1 + ǫ2)

ǫ1, ǫ2 sind die relativen Fehler von x1, x2, ǫ3 fur Subtraktion.

|ǫ3| ist klein (Satz 2 in A.3), aber ǫ1 und ǫ2 konnen großer sein!

y = (x1(1 + ǫ1) − x2(1 + ǫ2))(1 + ǫ3)

= (x1 − x2 + x1ǫ1 − x2ǫ2)(1 + ǫ3)

= x1 − x2︸︷︷︸

y

+x1ǫ1 − x2ǫ2 + (x1 − x2)ǫ3 + O(ǫiǫmach)

.= y(1 + ǫ3 +

x1

x1 − x2ǫ1 −

x2

x1 − x2ǫ2) = y(1 + ǫsub)

Der relative Fehler im Resultat der Subtraktion, verursacht durch Eingangsfehler

ǫ1, ǫ2 ist1

x1 − x2(x1ǫ1 − x2ǫ2)

also abhangig von x1 und x2.

13


Folgerung: Wenn x1 ≈ x2, dann ist wenigstens einer der Faktoren | x1

x1−x2|, | x2

x1−x2| sehr

groß und verstarkt ǫ1, ǫ2.Damit ist der relative Fehler im Ergebnis der Subtraktion ≫ ǫmach

Bezeichnung: Bei Subtraktion von 2 Zahlen x1, x2 gleichen Vorzeichens (Addition bei

verschiedenen Vorzeichen!) passiert Ausloschung, wenn x1 ≈ x2.

Merke:

Versuche, gefahrliche Subtraktion

durch Umformung zu vermeiden!

Beispiel: 1 − cos x fur x ≈ 0. modellhafte Uberlegung:

x1 = 1 : 1.0000000000000 mit ǫ1 = 0

−x2 = − cos x, z.B. : −0. 9999998391︸︷︷︸

korrekt

234︸︷︷︸

falsch

mit ǫ2 = 10−10

= .0000001608766 ǫx1−x2= 10−4

normalisiert = 0. 1608︸︷︷︸

korrekt

766 . . . . . .︸︷︷︸

“Schmutz”

vollig falsch!

(wird als Resultat mit ausgedruckt und

leider haufig geglaubt.)

Abhilfe: einige Terme der Taylorentwicklung von cosx (Ubung!).

G.) Kondition

Vorbemerkung: “Linearisierung” als Approximation einer Funktion, d.h. Ersetzen der

Funktion durch Tangente. (Figur ...)

Allgemein: y = ϕ(x)

y = ϕ(x)

} Linearisierung/Taylorentwicklung

y = ϕ(x) = ϕ(x + ∆x) = ϕ(x) +dϕ(x)

dx∆x + T.h.O.

↓

y

⇒ y − y = ϕ(x) − ϕ(x) =dϕ(x)

dx· (x − x) + O((x − x)2)

︸︷︷︸

T.h.O.

Hinweis:dϕ(x)

dxist eine symbolische Schreibweise fur die erste Ableitung.

Kurzfassung fur den skalaren Fall (n = m = 1): ∆y.=

dϕ(x)dx

∆x . Das beschreibt die

Verstarkung des absoluten Eingangsfehlers ∆x.

Es folgt fur den relativen Eingangsfehler

∆y

y

.=

dϕ(x)

dx

x

y

∆x

x(∗)

Die Konditionszahl des relativen Fehlers istdϕ(x)

dxxy, diejenige des absoluten Fehlers

istdϕ(x)

dx.

14


Definition: Ein Problem heißt schlecht konditioniert, wenn die |Konditionszahlen|

“groß” sind, sonst gut konditioniert. (“groß” heißt z.B. > 10).

Fur den Vektorfall

y1 = ϕ1(x1, . . . , xn)

...

ym = ϕm(x1, . . . , xn)

heißt das in erster Naherung:

∆y1.=

∂ϕ1(x)

∂x1∆x1 + . . . +

∂ϕ1(x)

∂xn

∆xn

...

∆ym.=

∂ϕm(x)

∂x1∆x1 + . . . +

∂ϕm(x)

∂xn

∆xn

(∗∗)

Dabei steht ∂ als Symbol fur (erste) partielle Ableitungen (siehe z.B. Abschnitt 3.12). Die

hier benotigten Vektoren, Matrizen, partiellen Ableitungen, Taylorentwicklung werden in

den folgenden beiden Kapiteln der Vorlesung eingefuhrt und diskutiert.

Beispiel: y = ϕ(x1, x2), d.h. m = 1, n = 2

∂ϕ(x1, x2)

∂x1ist die Ableitung nach x1, wobei fur diese

Ableitung x2 als Konstante angesehen wird;

∂ϕ(x1, x2)

∂x2ist die Ableitung nach x2, wobei fur diese

Ableitung x1 als Konstante angesehen wird.

(∗∗) in Summenschreibweise:

∆yi.=

n∑

j=1

∂ϕi(x)

∂xj︸︷︷︸

∆xj

messen Einfluss des absoluten

Fehlers ∆xj auf yi

Relativer Fehler analog wie in (∗) (fur xj , yi 6= 0):

∆yi

yi

.=

n∑

j=1

∂ϕi(x)

∂xj

xj

yi︸︷︷︸

“Konditionszahlen” des

relativen Fehlers

∆xj

xj

Die Konditionszahlen des relativen Fehlers geben an, wie stark der (relative) Eingangsfehler

ǫxj=

∆xj

xj

den (relativen) Resultatfehler

ǫyi=

∆yi

yi

beeinflusst. (Fehler von Zwischenoperationen sind hierin noch nicht enthalten!)

15


Beispiel: (Ubungen, sowie:)√

x ist gut konditioniert! Denn fur y = ϕ(x) =√

x ergibt sich

dϕ(x)

dx·x

y=

1

2√

x

x√

x=

1

2

Merke: Die “Kondition” dϕdx

bzw. dϕdx

xy

hangt nicht vom Algorithmus ab, der das Prob-

lem losen soll: Der Beitrag ungenauer Eingabedaten lasst sich durch keine noch so

scharfsinnige Wahl eines Algorithmus beeinflussen!

(zu Rundungsfehlern siehe Abschnitt 2.9)

16


Kapitel 2 Lineare Algebra

2.1 Vektoren, Matrizen, Gleichungssysteme

Ein rechteckiges Schema, in welches in “Zeilen” und “Spalten” Variablen oder Zahlen

eingetragen sind, heißt Matrix.

A.) Beispiele

Beispiel 1

Lineares Gleichungssystem, z.B.

{

7x − 3y = −5

2x + 4y = 3 .

Die Koeffizienten, mit denen die Unbekannten x und y in die Gleichungen eingehen, lassen

sich in einer (2 × 2)-Matrix darstellen:

(7 −3

2 4

)

(2 Zeilen, 2 Spalten)

Spezialfalle: Eine Matrix, die nur aus einer Zeile besteht, heißt Zeilenvektor. Eine

Matrix, die nur aus einer Spalte besteht, heißt Spaltenvektor.

Konvention: Wenn man von “Vektor” spricht, meint man Spaltenvektor.

obiges Beispiel:(−5

3

)

ist der Vektor der “rechten Seite”

(xy

)

ist der Vektor der Unbekannten

Beispiel 2 (vgl. Kondition im Abschnitt 1.5G)

∂ϕ1

∂x1. . . ∂ϕ1

∂xn

......

∂ϕm

∂x1. . . ∂ϕm

∂xn

Mit m Zeilen und n Spalten ist dies eine m × n-Matrix.

Die drei Teile eines Gleichungssystems:

1.) Vektor der Unbekannten

2.) Matrix der Koeffizienten (Faktoren der Unbekannten)

3.) Vektor der “rechten Seite”

17


Hinweis: Die Reihenfolge der Unbekannten und Gleichungen spiegelt sich in der Koeffizienten-

Matrix bzw. im Vektor der rechten Seite wider!

Bem.: Ein Term wie 7x ist “linear” in x, Terme wie x2, sin x, 1x

sind nichtlinear in x.

Allgemein ist ein additver Term

αx1 (= αx)

ein linearer Term (linear in x).

Bsp.: xy2 ist linear in x und nichtlinear in y, und xy ist nichtlinear, wenn x und y Un-

bekannte sind.

Die Gleichungen von Bsp. 1 und Bsp. 2 sind Systeme linearer Gleichungen (linear in allen

Variablen, hier x und y).

B.) Allgemeine Schreibweise

1.) Vektor der Unbekannten:

x1

x2...

xn

=: ~x =: x

Die Anzahl n der Unbekannten heißt die “Dimension” des Gleichungssystems.

Im Beispiel 1 gilt n = 2.

2.) Matrix der Koeffizienten:

a11 a12 . . . a1n

a21 a22 . . . a2n...

...

an1 an2 . . . ann

=: A

aij ist das “Element” in der i-ten Zeile, j-ten Spalte. (ij ist hier kein Produkt, sondern

zwei nebeneinandergestellte Indices)

3.) Vektor der “rechten Seite”:

b1

b2...

bn

=: ~b =: b

Definition: Ein Skalar ist eine einzelne Zahl, kein Vektor.

(schoner) Brauch:

Schreibe Matrizen als große Buchstaben (A, B, C, . . .) und Vektoren als kleine Buchstaben

(x, y, c, b, . . .), evtl. mit “Pfeil” (~x,~b), und Skalare mit griechischen Buchstaben (α, β, γ, . . .).

Bezeichnung: Die Elemente eines Vektors heißen Komponenten.

Hierarchie: Skalar, Vektor, Matrix (0-dim. / 1-dim. / 2-dim. “Feld”)

18


C.) Rechnen mit Vektoren

Es seien ~a =

a1

a2...

an

, ~b =

b1

b2...

bn

zwei Vektoren.

Addition: a + b = ~a +~b :=

a1 + b1

a2 + b2...

an + bn

, also komponentenweise.

analog: Subtraktion ~a −~b

Vektor ∗ Skalar Es sei α ein Skalar.

αa = α~a :=

αa1

αa2...

αar

, also wiederum komponentenweise

Vektor ∗ Vektor : geht das ?

Definition: Skalarprodukt ~a ·~b := a1b1 + a2b2 + . . . + anbn

klar: Das Skalarprodukt ist ein Skalar!

andere Bezeichnungen: atrb, < a, b >, . . .

1. Hinweis: Division durch einen Vektor gibt es nicht!

2. Hinweis: Aufwand: n + (n − 1) = 2n − 1 = O(n) Operationen

3. Hinweis: Fur den Spezialfall n = 3 gibt es auch ein anderes Produkt von Vektoren, das

einen Vektor liefert (“Vektorprodukt”).

Aus jedem Zeilenvektor entsteht ein Spaltenvektor durch “Kippen”, und umgekehrt. Diesen

Prozess des “Kippens” nennt man Transponieren. Schreibweise z.B.

~a′, ~aT , ~atr sind Zeilenvektoren;

~a (ohne Transponierungsmarkierung) ist immer ein Spaltenvektor.

D.) Langen und Winkel

geometrische Bedeutung von Vektoren: Jedem Vektor u entspricht ein “Pfeil” (gerichtetes

Geradenstuck) mit Fußpunkt im Koordinatenursprung und Spitze im Punkt mit den Ko-

ordinaten u (Illustration fur n = 2 in der (x1, x2)-Ebene ...). So macht es Sinn, nach

Langen von Vektoren und Winkeln zwischen Vektoren zu fragen.

Definition: (Euklidische) Lange eines Vektors ||v|| :=√

vtrv (“Norm”, Bezeich-

nung auch ||v||2 im Unterschied zu anderen Normen)

Definition: Einheitsvektor ||u|| = 1 Beispiele: v =

(1

0

)

, v := u||u||

Definition: Winkel ϕ zwischen v und w:

cos ϕ =vtrw

||v|| ||w||

19


Kriterium fur aufeinander senkrecht stehende Vektoren (ϕ = π/2):

utrv = 0 ⇔ u und v orthogonal

Schwarz’sche Ungleichung |vtrw| ≤ ||v|| ||w||

E.) Matrizen sind aus Vektoren aufgebaut

Jede Matrix kann man sich aus Zeilen- oder Spaltenvektoren aufgebaut denken:

a11 . . . a1n...

...

an1 . . . ann

= ( ~s1 ~s2 . . . ~sn ) =

~z1tr

~z2tr

...

~zntr

n Spaltenvektoren n Zeilenvektoren

z.B. ~s2 =

a12

a22

a32...

an2

(nur der “Zeilenindex lauft”), oder ~z6tr = (a61, a62, . . . , a6n).

F.) lineares Gleichungssystem in Matrizenschreibweise:

a11x1 + a12x2 + . . . + a1nxn = b1

a21x1 + a22x2 + . . . + a2nxn = b2...

an1x1 + an2x2 + . . . + annxn = bn

(1)

Das sind n skalare Gleichungen.

Nach obigen Rechenregeln gibt es zwei aquivalente Schreibweisen:

a11

a21...

an1

x1 +

a12

a22...

an2

x2 + . . . +

a1n

a2n...

ann

xn =

b1

b2...

bn

(2)

(eine Vektorgleichung; Summe von Spaltenvektoren), oder, da jede skalare Gleichung in

(1) ein Skalarprodukt beinhaltet:

(a11, a12, . . . , a1n) · ~x = b1

(a21, a22, . . . , a2n) · ~x = b2

...

(an1, an2, . . . , ann) · ~x = bn

(3)

(n skalare Gleichungen)

20


Definiton: Matrix ∗ Spaltenvektor

Ax :=

a11

a21...

an1

x1 + . . . +

a1n

a2n...

ann

xn

(also uber Version (2), oder, aquivalent, uber Version (3))

Mit diesen Konventionen lassen sich lineare Gleichungssysteme so schreiben: A~x = ~b oder

Ax = b (4)

(oder andere Buchstaben, oder Angabe von Zahlen wie im Ubungsblatt)

Die “Matrix-Vektor-Schreibweise” (4) dominiert die Literatur. Inhaltlich identisch wie (1),

(2) oder (3). In Literatur meist Fettdruck statt Pfeilen

Ax = b

(Fettdruck fur Matrizen und Vektoren, Normaldruck fur Skalare).

weiteres Beispiel fur Matrix ∗ Vektor (vgl. Abschnitt 1.5G):

∆y

.=

∂ϕ1

∂x1. . . ∂ϕ1

∂xn

......

∂ϕm

∂x1. . . ∂ϕm

∂xn

︸︷︷︸

=:Dϕ

∆x

Definition: transponierte Matrix: Vertauscht man die Zeilen mit den Spalten von A,

dann erhalt man Atr.

Beispiele:

1.) A =

2 5

3 −1

0 1

, Atr =

(2 3 0

5 −1 1

)

2.) Vektor a ⇒ atr ist Zeile

Definition: symmetrische Matrix, wenn A = Atr (d.h. aij = aji fur alle i, j)

Definition: Nullmatrix 0: enthalt nur Nullen

Definition: Einheitsmatrix:

I :=

1 0 . . . 0

0 1 0...

.... . .

...

0 0 . . . 1

21


2.2 Der Algorithmus von GaußGegeben: n skalare, lineare Gleichungen fur n Unbekannte x1, . . ., xn:

a11 . . . a1n...

...

an1 . . . ann

x1...

xn

=

b1...

bn

oder Ax = b

Die i-te Gleichung lautet

n∑

j=1

aijxj = bi

Idee: Addiere geeignete Vielfache von Zeile k auf Zeile i, derart, dass Nullen entstehen.

Strategie der Wahl von i, k, so dass ein mit Ax = b aquivalentes Gleichungsys-

tem Ax = b entsteht, bei dem A obere “Dreiecksmatrix” ist. Dies geschieht i.A.

“vorwarts”, vgl. Algorithmus unten. Resultat dieser ersten Phase:

. . . . . .. . . . .

. . . .. . .

0 . ..

x = b

Danach 2. Phase: Ruckwartselimination:

xn =bn

ann

⇒ xn−1 =1

an−1,n−1(bn−1 − xnan−1,n)

u.s.w. erhalt man xn−2, . . . , bis x2, x1

Kosten der ersten Phase: O(n3) Operation, s.u.

Kosten der zweiten Phase: in jeder Zeile i.W. ein Skalarprodukt (von zunehmender

Lange), also jeweils O(n) Operationen. Macht zusammen O(n2) Operationen fur die

Ruckwartselimination.

Fur die Zusammenfassung lasse die Tilde ( ˜ ) weg. Die Restmatrizen werden jeweils

verandert; aktuelle Version mit hochgestellten Indices:

j-ter Hauptschritt:

a

a..

Ziel: =0!

.

.

a

b...

b0

(j)jj

(j)j+1,j

(j)n,j

(j)j+1

(j)n

.

bj(j)

j-1

22


Algorithmus

Fur k = 1, 2, . . . , n − 1:

Annahme akk 6= 0 (anderenfalls Zeilenver-

tauschung von Zeile k mit Zeile

“unterhalb”: Pivotstrategie)

fur i = k + 1, k + 2, . . . , n:

fur j = k + 1, k + 2, . . . , n:

aij := aij −aik

akkakj

bi := bi −aik

akkbk

xn := bn

ann

Fur i = n − 1, n − 2, . . . , 1:

xi := (bi −∑n

j=i+1 aijxj)/aii

Hinweis: Die ursprungliche Matrix A wird dabei uberschrieben.

Pivotstrategie: Wichtige Klassen von Matrizen brauchen keine Pivotstrategie, da akk 6=

0 jeweils garantiert werden kann. Solche Matrizen sind z.B.

(1) die diagonal-dominanten Matrizen (|akk| >∑n

i6=k |aki| fur alle k)

(2) die positiv-definiten Matrizen (Atr = A und xtrAx > 0 fur x 6= 0)

Kosten: Drei ineinandergeschachtelte Schleifen deuten auf O(n3) hin. Konkret: 23n3 +

O(n2) Operationen (+,−, ·, /). Ein kompaktes Programm ist moglich mit ai,n+1 :=

bi, d.h. Anhangen von b an A. Es konnen auch mehrere Vektoren b gleichzeitig

bearbeitet werden.

Warnung: Fur n > 3 nicht die Cramersche Regel benutzen, da viel zu teuer bzw. nicht

durchfuhrbar!

2.3 Arbeiten mit MatrizenBezeichnung der Elemente der Matrizen A, B, C:

A = ((aij)) , B = ((bij)) , C = ((cij))

A.) Addition von Matrizen

erfolgt komponentenweise: C = A + B mit

cij := aij + bij fur alle i, j .

Voraussetzung: Die Matrizen mussen gleich groß sein. Analog: Subtraktion.

Regeln:A + B = B + A

(A + B) + C = A + (B + C)

B.) Multiplikation von Matrizen

Matrizen A und B mussen fur das Produkt AB wie folgt zusammenpassen:

A sei m × n und B sei n × l .

23


Dann ist C := AB definiert uber

cij :=

n∑

k=1

aikbkj fur i = 1, . . . , m , j = 1, . . . , l .

Also: Skalarprodukt der i-ten Zeile der Matrix A mit der j-ten Spalte von B.

Vorsicht mit der Bezeichnung: In dieser Formel steht A fur den linken Faktor und B fur

den rechten Faktor. (gegebenenfalls an andere Bezeichnungen anpassen)

Die Produktmatrix C ist also m × l.

Spezialfall m = l = 1: Zeile ∗ Vektor, d.h. Skalarprodukt, z.B. utrv

Rechenregeln:

A(BC) = (AB)C = ABC (Klammern hier unnotig)

C(A + B) = CA + CB

(AB)tr = BtrAtr

aber: i.A. AB 6= BA !

moglich ist:

Matrix ∗ Spaltenvektor (z.B. Ax)

Zeilenvektor ∗ Matrix (z.B. ytrA)

ytrAx ist Skalar

nicht moglich:

Matrix ∗ Zeile , Spalte ∗ Matrix ,

Division durch Matrix.

C.) Inverse Matrix

Voraussetzung: A ist quadratisch: n × n.

Falls es eine Matrix B gibt mit AB = I, dann heißt B inverse Matrix von A.

Bezeichnung: A−1

Dann gilt

AA−1 = I = A−1A

Vorsicht: Die Inverse existiert nicht zu jeder Matrix! Matrizen, zu denen es keine Inverse

gibt, heißen singular.

Notwendiges und hinreichendes Kriterium fur Singularitat von A:

Es gibt Vektor x 6= 0 mit Ax = 0 .

Die nichtsingularen Matrizen heißen auch regular.

Spezialfall 2 × 2 Matrix:

(a bc d

)−1

=1

ad − bc

(d −b−c a

)

ad − bc heißt die Determinante von

(a bc d

)

.

24


A invertierbar ⇔ Determinate 6= 0.

Rechenregeln:

(AB)−1 = B−1A−1

(A−1)tr = (Atr)−1

Falls A−1 exisitiert (A nichtsingular), dann muss A n Pivotelemente 6= 0 haben.

D.) Permutationsmatrizen

Definition: Eine n × n-Matrix P heißt Permutationsmatrix, wenn in jeder Zeile und

in jeder Spalte von P genau eine 1 steht und sonst nur Nullen.

(Beispiel einer Permutationsmatrix...)

Anwendung::

PA vertauscht Zeilen von A,

AP vertauscht Spalten von A.

E.) Orthogonale Matrizen

Eine quadratische Matrix Q mit der Eigenschaft QtrQ = I heißt orthogonal. Es gilt also

Qtr = Q−1. Die Spalten von Q sind “orthonormal”, d.h. orthogonal mit Einheitslange.

Beispiel 1: Drehmatrix

(cos ϕ − sin ϕsin ϕ cos ϕ

)

Die Multiplikation(

cos ϕ − sin ϕsin ϕ cos ϕ

) (u1

u2

)

bewirkt eine Drehung des Vektors

(u1

u2

)

um den Winkel ϕ im mathematisch pos-

itiven Sinn (d.h. gegen den Uhrzeigersinn).

Illustration am Beispiel mit u =

(1

2

)

, ϕ = π2 .

Beispiel 2: Jede Permutationsmatrix, weil die Spalten orthonormal sind.

Beispiel 3: Reflexionen, Householder-Matrizen, vgl. §2.9, z.B.

Q :=

1 0 0

0 1 0

0 0 −1

Qx vermittelt eine Spiegelung an der Ebene x3 = 0.

F.) LU-Zerlegung: Falls A faktorisiert ist in A = LU ,

wobei L =

1. 1 0. . 1. . . 1. . . . 1. . . . . 1. . . . . . 1

, U =

. . . . . . .. . . . . .. . . . .. . . .. . .0 . ..

,

dann ist das Losen von Ax = b einfach: Wegen

Ax = LUx︸︷︷︸

=y

= b = Ly

1. Schritt: Lose Ly = b: “Vorwartssubstitution”

2. Schritt: Lose Ux = y: “Ruckwartselimination”

(Haufige Bezeichnung R statt U , dann also LR-Zerlegung.)

25


Frage: Existiert eine Zerlegung A = LU immer?

Antwort: Nur wenn A nichtsingular (also “regular”) ist und man Zeilenvertauschungen

von A zulasst. Zur Formalisierung benutze Permutationsmatrizen.

Satz: Fur jede nichtsingulare (= regulare) Matrix A gibt es eine Permutationsmatrix Psowie Dreiecksmatrizen L und U von obigem Typ, so dass

PA = LU

Ausfuhrung der LU -Zerlegung ist aquivalent zum Gaußschen Algorithmus.

G.) Qualitat der Losung

Definition: Residuum: Es sei x eine berechnete “Losung”, dann heißt der Vektor

r := b − Ax das Residuum von Ax = b.

Das Residuum ist durch Zeilenskalierung DAx = Db beliebig manipulierbar (D: Diago-

nalmatrix). Denn: neues Residuum = Db − DAx = Dr .

Warnung: kleines Residuum 6⇒ genaue Losung

2.4 Vektorraume

IRn := { Spaltenvektoren mit n Komponenten}

Definition: Ein Vektorraum ist eine Menge, deren Elemente durch zwei Operationen

verknupft werden konnen, hier Addition und Multiplikation. Dabei gelten die ublichen

(Vektor-)Rechenregeln, und Addition u + v und Multiplikation mit Skalaren αu fuhren

nicht aus dem Raum heraus.

D.h. das Ergebnis gehort zu dem gleichen Raum. “Reeller” Vektorraum, weil α ∈ IR.

Beispiele:

1.) IRn

2.) der Raum aller reellen Funktionen.

Unterraume von Vektorraumen enthalten immer die 0, u + v und αu.

Beispiele:

1.)

x1...

xn−1

0

| xi ∈ IR

2.) Spaltenraum einer Matrix (“Bild einer Matrix”)

:= {Ax | x ∈ IRn}

= { Linearkombinationen der Spalten von A}

Nachweis: A · 0 = 0, u, v im Spaltenraum ⇒ ∃x, y mit u = Ax, v = Ay (usw.)

26


2a) speziell mit A =

1 0

4 3

2 3

Ebene, aufgespannt von den Spalten: u = α

1

4

2

+ β

0

3

3

Bemerkung: Wenn A eine m× n-Matrix ist (m Zeilen, n Spalten) und x ∈ IRn, dann ist

Ax ∈ IRm. Das Ergebnis Ax kann man als “Bild” von x ansehen. (Illustration Urbildraum,

Bildraum . . .) Wie das Beispiel 2a) mit m = 3 zeigt, muss der Bildraum nicht der “volle”

IRm sein.

3.) Kern von AKern(A) := {Losung x von Ax = 0}

Fur alle invertierbaren Matrizen ist dies nur der Nullvektor.

Kern(A) ist Unterraum, denn: Es gelte Ax = 0 und Ay = 0.

dann folgt

{A(x + y) = Ax + Ay = 0

A(αx) = αAx = 0

3a) x + 2y + 3z = 0 im IR3 beschreibt Ebene durch Koordinaten-Ursprung.

A = ( 1 2 3 )

x + 2y + 3z = 6 ist auch Ebene, aber kein Unterraum, weil die 0 nicht enthalten ist.

Zuruck zu Ax = b: Frage: Zahlen identische Gleichungen oder 0 = 0 mit?

Definition: Rang einer Matrix ist die Anzahl ihrer Pivotelemente ( 6= 0).

Bezeichnung: r

Definition: Treppenmatrix, auch “Zeilenstufenform”

U =

∗

0 ∗ ∗

0 0 0 0 ∗

0 0 0 0 0 ∗

0 0 0 0 0 0 0 0 0

Diese Beispiel-(5 × 9)-Matrix hat 4 Pivotelmente. ∗ bedeutet: Zahl 6= 0; der Rest der

Zeilen ist mit beliebigen Zahlen gefullt.

Auftreten: Wie beim Gaußschen Algorithmus gezeigt, lassen sich Treppenmatrizen durch

Zeilenoperationen aus jeder Matrix A erzeugen! (einschließlich Zeilenvertauschungen)

Beispiel: Bei obiger 5 × 9-Matrix U ist r = 4.

Spaltenraum:

α

1

0

0

0

0

+ β

0

1

0

0

0

+ γ

0

0

1

0

0

+ δ

0

0

0

1

0

=

αβγδ0

⊂ IR5

27


Kern(U): “Pivotvariablen” sind diejenigen xj , bei denen Pivotelemente stehen, also

hier x1, x2, x5, x6. “Freie Variablen”: alle anderen, hier also:

x3, x4, x7, x8, x9 .

Die freien Variablen konnen beliebig gesetzt werden! (Z.B. mit Nullen und Einsen.)

Anschließend erhalt man die Pivotvariablen durch Losen von Ux = 0.

Jede Setzung der freien Variablen fuhrt auf eine “spezielle Losung”. Z.B. setze

willkurlich x3 = 1, x4 = x7 = x8 = x9 = 0.

Vereinbarung: In jeder speziellen Losung der Gleichung Ax = 0 bzw. Ux = 0 wird eine

der freien Variablen auf 1, die anderen auf 0 gesetzt.

Zahlenbeispiel [Strang] U =

(1 5 7

0 0 9

)

freie Variable: x2 (z.B. setze x2 = 1)

allgemeine Losung von Ux = 0:

x3 = 0 ⇒ x1 + 5x2 + 0 = 0

⇒

x1

x2

x3

=

−5x2

x2

0

= x2

−5

1

0

(Gerade im (x, y, z)− Raum)

spezielle Losung:

−5

1

0

Bei jeder m × n-Matrix gilt Rang ≤ m und Rang ≤ n.

Man sagt, der Rang ist “voll”, wenn er maximal ist, d.h. r = min(n, m).

Losungen von Ax = b:

Fur Ax = 0 gibt es n − Rang(A) viele spezielle Losungen.

Homogene Losung xh lost Ax = 0. (Ax = 0 heißt auch “homogenes Gleichungssystem”.)

Eine partikulare Losung xp erhalt man, wenn alle freien Variablen = 0 gesetzt werden:

Axp = b.

allgemeine Losung: x = xh + xp (denn: Ax = 0 + Axp = b)

2.5 Dimension und Basis von Vektorraumen

Definition: Die Spalten einer Matrix heißen linear unabhangig, wenn x = 0 die einzige

Losung von Ax = 0 ist. (d.h. A ist regular)

Noch allgemeiner (nicht nur bei Matrizen):

n Vektoren ~v1, . . . , ~vn heißen linear unabhangig, wenn

x1~v1 + . . . + xn~vn = ~0 ⇒ x1 = . . . = xn = 0 .

28


(D.h. der Nullvektor lasst sich nur durch die triviale Kombination 0 · ~v1 + . . . + 0 · ~vn

darstellen.)

Anderenfalls heißen die Vektoren linear abhangig.

Beispiel im IR2:(

1

0

)

und

(0

1

)

sind linear unabhangig

(1

1

)

und

(0

1.01

)

sind linear unabhangig

(1

1

)

und

(2

2

)

sind linear abhangig

(1

1

)

und

(0

0

)

sind linear abhangig

Im IRn gibt es maximal n linear unabhangige Vektoren.

Beispiel: Sind die Vektoren v1 =

1

−2

3

, v2 =

5

6

−1

, v3 =

3

2

1

linear unabhangig?

→ x1v1 + x2v2 + x3v3 = 0

⇔ x1

1

−2

3

+ x2

5

6

−1

+ x3

3

2

1

=

0

0

0

⇔

1 5 3

−2 6 2

3 −1 1

︸︷︷︸

=:A

x1

x2

x3

=

0

0

0

allgemeine Losung von Ax = 0:

x =

−12c

−12c

c

, c ∈ IR beliebig

Insbesondere ist x1 = −12, x2 = −1

2, x3 = 1 eine Losung.

⇒ v1, v2, v3 sind linear abhangig.

Definition: Eine Menge von Vektoren erzeugt einen Raum, wenn die Menge der Linear-

kombinationen den Raum genau ausfullt. (auch “aufspannen” statt “erzeugen”)

Menge der Linearkombinationen von n Vektoren ~v1, . . . , ~vn:

{n∑

i=1

αi~vi | αi ∈ IR

}

Bezeichung: span(~v1, . . . , ~vn) oder “lineare Hulle”

29


Beispiel: Der Spaltenraum einer Matrix A wird von den Spalten erzeugt.

Defintion: Eine Basis eines Vektorraumes ist eine Menge von Vektoren mit den beidenEigenschaften:

1.) Die Vektoren sind linear unabhangig.

2.) Die Vektoren erzeugen den Vektorraum.

Beispiel:

1

0

0

,

0

1

0

,

0

0

1

bilden die sogenannte “Standard-Basis” des IR3 (analog

IRn)

Beispiel: Die Spalten jeder invertierbaren n × n-Matrix bilden eine Basis des IRn.

Sind ~v1, . . . , ~vm und ~w1, . . . , ~wn zwei Basen desselben Vektorraumes, so gilt m = n.

Defintion: Die Dimension eines Vektorraumes ist durch die Anzahl der Vektoren in

jeder Basis des Raums definiert.

Beispiel: IRn ist n-dimensional.

Beispiel: {1, x, x2} ist Basis des Raumes aller Polynome vom Grad ≤ 2

{α0 + α1x + α2x2 | αi ∈ IR}

Beispiel: Der Kern von A hat die Dimension n − Rang(A), und die speziellen Losungen

bilden eine Basis von Kern(A).

Beispiel: Matrix vom Rang 1:

A = uvtr = Spalte ∗ Zeile

Wichtige Eigenschaften:

Satz: Es sei A eine reelle m × n Matrix (m Zeilen, n Spalten). Dann gelten die Eigen-

schaften:

1.) Rang(A) = Rang(Atr)

2.) dim(Bild(A)) + dim(Kern(A)) = n3.) dim(Bild(Atr)) + dim(Kern(Atr)) = m4.) Rang(A) = dim(Bild(A))

Beispiel: lineares Gleichungssystem

x1 + 2x2 + 3x3 = 6

x2 + 2x4 = 3

3x1 − x4 = 2

x1 + 3x2 + 3x3 + 2x4 = 9

⇔ Ax = b mit A =

1 2 3 0

0 1 0 2

3 0 0 −1

1 3 3 2

, b =

6

3

2

9

30


Anwendung des Gaußschen Algorithmus liefert:

1 2 3 0 6

0 1 0 2 3

3 0 0 −1 2

1 3 3 2 9

→ . . . →

1 2 3 0 6

0 1 0 2 3

0 0 −9 11 2

0 0 0 0 0

→ Rang(A) = 3,

Kern(A) = {x ∈ IR4|x4 = a , x3 = 119

a , x2 = −2a , x1 = 13a , a ∈ IR}

=

a ·

13−21191

∣∣a ∈ IR

= span

13−21191

→ Losungsmenge des homogenen Gleichungssystems

x4 ist freie Variable, dim(Kern(A)) = 1.

partikulare Losung von Ax = b :

xp =

233

−29

0

⇒ allgemeine Losung von Ax = b:

x = xh + xp =

23 + 1

3c3 − 2c

−29 + 11

9 cc

, c ∈ IR

2.6 Determinanten

• A ∈ IR2×2: det(A) = det

(a11 a12

a21 a22

)

= a11a22 − a12a21

Schema: siehe Vorlesung

• A ∈ IR3×3:

det(A) = det

a11 a12 a13

a21 a22 a23

a31 a32 a33

= a11a22a33 + a12a23a31 + a13a21a32

− a13a22a31 − a11a23a32 − a12a21a33

Schema: siehe Vorlesung (Regel von Sarrus)

31


Definition: Sei A ∈ IRn×n. Der Minor Mij des Elements aij ist als Determinate derjeni-

gen Untermatrix definiert, die sich durch Streichen der i-ten Zeile und j-ten Spalte aus Aergibt. Die Zahl Cij := (−1)i+jMij heißt Kofaktor des Elements aij.

Beispiel:

A =

3 1 −4

2 5 6

1 4 8

M32 = det

(3 −4

2 6

)

= 26 , C32 = (−1)3+2M32 = −26

Vorzeichen fur Cij aus Schema:

+ − + − . . .− + − + . . .+ − + − . . .− + − + . . ....

Satz: Sei A ∈ IRn×n. Dann gilt fur jedes 1 ≤ i ≤ n und jedes 1 ≤ j ≤ n:

det(A) = a1jC1j + a2jC2j + · · · + anjCnj =

n∑

k=1

akjCkj

(Entwicklung nach der j-ten Spalte)

und

det(A) = ai1Ci1 + ai2Ci2 + · · · + ainCin =

n∑

k=1

aikCik

(Entwicklung nach der i-ten Zeile)

Beispiel: Entwicklung nach der 1. Zeile

det

3 1 0

−2 −4 3

5 4 −2

= 3 · det

(−4 3

4 −2

)

− 1 · det

(−2 3

5 −2

)

+ 0 · det

(−2 −4

5 4

)

= . . . = −1

Beispiel: Entwicklung nach der 1. Spalte

det

0 2 −1 1

1 3 4 2

0 −1 1 −3

1 0 3 −2

= −1 · det

2 −1 1

−1 1 −3

0 3 −2

− 1 · det

2 −1 1

3 4 2

−1 1 −3

= . . . = 15

32


Satz: Es seien A ∈ IRn×n und b ∈ IRn. Dann sind folgende Aussagen aquivalent:

(1) Ax = b ist eindeutig losbar.

(2) A ist regular.

(3) Kern(A) = {0} .

(4) det(A) 6= 0 .

Satz:

(1) det(AB) = det(A) det(B)

(2) det(Atr) = det(A)

Orthogonale Matrizen Q haben die Determinante +1 oder −1, denn:

1 = det(I) = det(QtrQ) = det(Qtr)det(Q) = det(Q) det(Q) = (det(Q))2

2.7 Eigenwerte

A n × n Matrix, A = ((aij))i=1,...,n, j=1,...,n

x n-Vektor (Komponenten evtl. komplexe Zahlen; vgl. spateren Abschnitt 3.2)

Definition: Falls es ein x 6= 0 gibt mit einem λ, so dass

Ax = λx

gilt, dann heißt x Eigenvektor und λ Eigenwert (wiederum evtl. komplexe Zahlen).

Erste Eigenschaften:

(1) A hat hochstens n verschiedene Eigenwerte.

(2) Wenn A symmetrisch (akj = ajk) ist, dann sind die Eigenwerte reell.

(3) Eigenvektoren zu verschiedenen Eigenwerten sind linear unabhangig.

(Hinweis: Jeder n-Vektor y kann eindeutig durch n linear unabhangige Vektoren

x(1), . . . , x(n) dargestellt werden: y =

n∑

k=1

ckx(k). Insbesondere wenn A n ver-

schiedene Eigenwerte hat, konnen die x(k) als Eigenvektoren gewahlt werden.)

(4) Eigenwerte sind Nullstellen des charakteristischen Polynoms

ϕ(λ) := det(A − λI) ,

wobei I die Einheitsmatrix ist.

[denn:

∃ x 6= 0 : Ax = λx ⇔ ∃ x 6= 0 : (A − λI)x = 0

⇔ det(A − λI) = 0]

Definition: Mehrfacher Eigenwert: λk ist ein mehrfacher Eigenwert, wenn es eine

mehrfache Nullstelle des charakteristischen Polynoms ϕ(λ) ist.

(entsprechend: “einfacher Eigenwert”)

33


Beispiel: A =

−7 13 −16

13 −10 13

−16 13 −7

charakteristisches Polynom ϕ(λ) =

det

−7 − λ 13 −16

13 −10 − λ 13

−16 13 −7 − λ

(entwickelt nach erster Zeile:)

= − (7 + λ){(10 + λ)(7 + λ) − 132} − 13{−13(7 + λ) + 13 · 16} − 16{132 − 16(10 + λ)}

= . . . = −λ3 − 24λ2 + 405λ − 972

= − (λ − 3)(λ − 9)(λ + 36)

⇒ λ1 = 3, λ2 = 9, λ3 = −36 sind die Eigenwerte

Berechnung der Eigenvektoren uber lineare Gleichungssysteme:

z.B. fur λ3:

(A − λ3I)x = (A + 36I)x =

29 13 −16

13 26 13

−16 13 29

x1

x2

x3

!= 0

Bemerkung:

(1) Wegen der Singularitat von (A − λI) ist wenigstens eine der drei skalaren Glei-

chungen redundant.

(2) Falls x Eigenvektor ist, dann auch αx fur alle Faktoren α 6= 0. Also ist x so

normierbar, dass eine Komponente = 1 ist.

obiges Beispiel: Versuch mit 1. Komponente:

x1 = 0 ⇒ x2 = x3 = 0,

also: x1 6= 0. Setze x1 = 1.

Es bleibt:13x2 − 16x3 = −29

26x2 + 13x3 = −13

13x2 + 29x3 = 16

→ 3. Gleich. – 1. Gleich.

45x3 = 45 ⇒ x3 = 1 ⇒ x2 =−13

13= −1

Also:

x(3) =

1

−1

1

ist Eigenvektor zum Eigenwert λ3 = 36;

analoges Vorgehen fur λ1, λ2.

34


2.8 Normen

Abstand von skalaren Zahlen |x − x|;

Ziel: Verallgemeinern auf Vektoren und Matrizen.

A.) Matrix-Normen:

Vektor-Normen ‖x‖ haben die “Norm-Eigenschaften”

(V 1) ‖x‖ ≥ 0

(V 2) ‖x‖ = 0 ⇔ x = 0

(V 3) ‖αx‖ = |α|‖x‖ fur Skalar α

(V 4) ‖x + y‖ ≤ ‖x‖ + ‖y‖ (Dreiecksungleichung)

(geometrische Bedeutung der Dreiecksungleichung im IR2 ...)

Beispiele:

‖x‖2 :=

√√√√

n∑

i=1

x2i “Euklidische Norm”, Lange, “2-Norm”

(Folgerung: ‖x‖22 = xtrx)

‖x‖∞ := max1≤i≤n

|xi| “Maximum-Norm”, “Unendlich-Norm”

x x2 2

1x x

11

1

1

1

‖x‖2 ≤ 1 ‖x‖∞ ≤ 1

(Erklarung der Indices 2,∞ uber p-Norm...)

Die zur Vektornorm ‖x‖ passende “naturliche” Matrixnorm ist definiert als

‖A‖ := maxx6=0

‖Ax‖

‖x‖

(Von der ursprunglichen Definition als “supremum” auch der Name least upper bound;

heißt auch “lub-Norm”.) Es gilt wegen (V3)

‖A‖ = max‖y‖=1

‖Ay‖, weil y :=x

‖x‖.

Die naturliche Matrixnorm hat die vier Eigenschaften analog zu den Vektornormen, und

zusatzlich die Eigenschaften

(M5) ‖AB‖ ≤ ‖A‖‖B‖ (Submultiplikativitat)

(M6) ‖Ax‖ ≤ ‖A‖‖x‖ (Vertraglichkeit)

(M7) ‖I‖ = 1 .

35


Vorbemerkungen zur Herleitung von ‖A‖2:

Bx = λx Eigenwertproblem mit x 6= 0 (x Eigenvektor, λ Eigenwert)

Bx = λx ⇒ λ = xtr

Bx

xtr

x. Dieser Quotient heißt Rayleigh-Quotient.

B := AtrA ist symmetrisch. (weil wegen (CD)tr = DtrCtr gilt: Btr = B)

B symmetrisch ⇒ max. Rayleigh-Quotient ist der maximale Eigenwert

Beispiele:

‖A‖2 :=maxx6=0

‖Ax‖2

‖x‖2=max

√

xtrAtrAx

xtrx=

√

λmax(AtrA) =

√

großter Eigenwert von AtrA

Folgerung: ‖H‖2 = 1 fur orthogonale Matrizen H. (H orthogonal :⇔ Htr = H−1)

‖A‖∞ := max‖y‖∞=1

‖Ay‖∞=maxi

n∑

k=1

|aik| = großte Zeilensumme

B.) Storungen in b:

Im Folgenden sei die Matrixnorm immer die zur Vektornorm passende.

Frage: Was ist die Auswirkung ∆x auf die Losung x von Ax = b, wenn b um ∆b verandert

wird?

A(x + ∆x) = b + ∆b ⇒ A∆x = ∆b

⇒ ‖∆x‖ = ‖A−1∆b‖ ≤ ‖A−1‖‖∆b‖

andererseits: b = Ax ⇒ ‖b‖ ≤ ‖A‖‖x‖ ⇒1

‖x‖≤

‖A‖

‖b‖

zusammen:‖∆x‖

‖x‖≤ ‖A‖‖A−1‖

‖∆b‖

‖b‖

Definition: Konditionszahl einer Matrix

cond(A) := ‖A‖‖A−1‖

Also ist der Einfluss relativer Fehler in b auf den relativen Fehler in x durch den Faktor

cond(A) beschrankt. (relative Fehler in obigem Sinne, nicht komponentenweise)

Es gilt: cond(A) ≥ 1, denn

1 = ‖I‖ = ‖AA−1‖ ≤ ‖A‖‖A−1‖ = condA

Also: Fur eine gut-konditionierte Matrix gilt: cond(A) “nahe” bei 1 (z.B. < 10).

C.) Anderungen in A:

A → A + ∆A

Man kann zeigen: Falls die Storung ∆A klein ist im Sinne ‖A−1‖‖∆A‖ < 1, dann gilt

‖∆x‖

‖x‖≤

cond(A)

1 − cond(A)‖∆A‖

‖A‖

‖∆A‖

‖A‖,

also ist auch hier die Konditionszahl cond(A) entscheidend.

36


2.9 Householder-Matrizen

Wie wirken sich Rundungsfehler aus? Die Rundungsfehler jedes Zwischenschrittes

wirken sich auf den gesamten restlichen Algorithmus aus!

20 r

...

1 ...elementare Operationen

Rundungsfehler

Datenfehler

Wenn ϕi die einzelnen Operationen sind, kann ein Algorithmus y = ϕ(x) mir r Oper-

ationen dargestellt werden als

x → ϕ0(x) → ϕ1(ϕ0(x)) → . . . → y = ϕ(x)

Die jeweiligen Rundungsfehler konnen als Eingangsfehler des Rest-Algorithmus ange-

sehen werden. Sie werden mit der Kondition der jeweiligen Restabbildung verstarkt.

(vgl. Abschnitt 2.8 C.)

Definition: Ein Algorithmus I heißt stabiler als Algorithmus II, wenn der Rundungs-

fehlereinfluss bei Algorithmus I kleiner ist.

Ein Algorithmus heißt numerisch stabil oder gutartig, wenn die Rundungsfehler

das Ergebnis nicht starker als die Eingangsfehler beeinflussen.

Frage: Gibt es eine bessere Alternative zur Losung von Ax = b als den Gaußschen

Algorithmus?

(Bemerkung zur Bezeichnung: Bei Ax = b sind A und b die Daten und x ist das Resultat.)

Situation beim Gauß-Algorithmus: Die Transformation der Matrix A auf Dreiecksform Umit Zeilenoperationen erzeugt eine Kette von Zwischenmatrizen:

A =: A(0) → A(1) → A(2) → . . . → A(n−1) = U.

Rundungsfehler der Zwischenschritte (bei der Berechnung von A(j)) wirken sich als Storungen

∆A auf das Ergebnis aus, sie werden mit den Faktoren cond(A(j)) verstarkt.

Forderung/gesucht: Alternative zum Gauß-Algorithmus derart, dass

(1) cond(A(j)) = cond(A(j−1)) fur alle j(2) A(n−1) = obere Dreicksmatrix.

[(1) ⇒ Verfahren ist gutartig, d.h. stabil fur alle Matrizen A.] Zur Ausfuhrung verwende

geeignete Matrizen H(j) und A(j) := H(j)A(j−1).

1. Idee: Man nehme orthogonale Matrizen H (d.h. HtrH = I). Folgerung fur ‖ · ‖2:

‖A‖2 = ‖HtrHA‖2 ≤ ‖Htr‖2︸︷︷︸

=1

‖HA‖2 ≤ ‖H‖2‖A‖2 = ‖A‖2

⇒ ‖HA‖2 = ‖A‖2 . Analog: ‖A−1‖2 = ‖A−1Htr‖2 .

⇒ cond(A) = ‖A‖2‖A−1‖2 = ‖HA‖2‖A−1Htr

︸︷︷︸

(HA)−1

‖2 = cond(HA)

A(j) = H(j)A(j−1) ⇒ Forderung (1) ist erfullt.

37


2. Idee: Definition der Householder-Matrix: H := I − 2wwtr mit beliebigem

Einheitsvektor w, d.h. wtrw = 1

zur Erinnerung:

wwtr ist Matrix (vom Rang 1)!

(AB)tr = BtrAtr

Eigenschaften von H:

1. H ist symmetrisch, denn: Htr = Itr − 2(wwtr)tr = I − 2wwtr = H2. H ist orthogonal, denn: HtrH = HH = I − 2wwtr − 2wwtr + 4w wtrw

︸︷︷︸

=1

wtr = I

3. y = Hx ist Spiegelung an der (Hyper-)Ebene, die senkrecht zu w ist und den

Nullpunkt enthalt. (−→ Illustration...)

4. ‖Hx‖2 = ‖x‖2 (denn ‖Hx‖2 =√

(Hx)trHx = . . .)

Hinweis: H = I − uutr

κmit κ = 1

2utru, u beliebig 6= 0 ist Householder-Matrix.

3. Idee: Man wahle w so, dass Ha!= γe1 =

γ0...

0

(Anwendung z.B. a die 1. Spalte von A = A(0))

Konstruktion von w (bzw. u): Eigenschaft 4. ⇒ ‖Ha‖22 = γ2 = ‖a‖2

2, also γ = ±‖a‖2. Es

folgt

±‖a‖2e1!= Ha = a −

1

κu(utra)

⇒ uutra

κ= a ∓ ‖a‖2e1

und also

u = const · (a ± ‖a‖2e1).

Da bei u nur die Richtung wichtig ist, setze const := 1. Wahle Vorzeichen so, dass keine

Ausloschung auftritt.

Resultat: fur gegebenen Vektor a 6= 0 setze

u := a +a1

|a1|‖a‖2e1 =

a1 + a1

|a1|‖a‖2

a2...

an

(falls a1 = 0, setzea1

|a1|= 1)

κ := ‖a‖2(‖a‖2 + |a1|)

H := I −uutr

κ

38


Anwendung auf Ax = b: Es sei a die erste Spalte von A, H(1) wie oben konstruiert.

(1) (1)A )( )b : = H

(1) ( A b(0)

=

Restmatrix

(0) *0

0

2. Schritt

T (2)

(2)

: = 1 0

0

H

wobei H(2) diejenige Householder-Matrix der Große (n − 1) × (n − 1) ist, welche die 1.

Spalte der Restmatrix “behandelt” wie oben erklart. (A(2)|b(2)) = T (2)(A(1)|b(1))

usw.

T : = 1

10

(j)

(j)

H0

00

Die T (j) sind orthogonal und symmetrisch. Allgemein:

A( )b ( A b )(j) (j): = T

(j) (j-1) (j-1)

am Ende:(R =)U =T (n−1) · . . . · T (2)H(1)A

⇒ H(1)T (2) · . . . · T (n−1)︸︷︷︸

=: Q orthogonal und vollbesetzt

U = A

Diese Zerlegung heißt auch QR-Zerlegung, A = QR . Wegen Ax = QRx = b gilt

Rx = Qtrb = b(n−1).

Losen von Rx = b(n−1) wie beim Gauß-Algorithmus.

Praxis: Keine Matrizen H(j) speichern, sondern nur die Vektoren u; sie passen in das

untere Dreieck hinein (siehe Pfeil), bis auf die Diagonalelemente.

−→

. . . . . . .. . . . . .. . . . .R = U. . .. ..

Aufwand der QR-Zerlegung: O( 43n3) Operationen, also zweimal so teuer wie die Gauß-

Elimination.

39



Kapitel 3 Analysis

3.1 Vollstandige Induktion

Haufig in der Mathematik:

Aussagen, die fur eine beliebige naturliche Zahl gelten.

Beispiel: 13 + 23 + . . .+ n3 =[n(n+1)

2

]2ist die Aussage A(n) fur beliebige n ∈ IN.

Beweisverfahren hierfur: “Vollstandige Induktion”

1. Schritt: Beweis der Aussage fur eine kleinste naturliche Zahl, meist fur n = 1 (“In-

duktionsanfang” - “Verankerung”). D.h. Nachprufen von A(1).

2. Schritt: Nachweis der Gultigkeit fur n + 1, falls Aussage fur n richtig ist. (“Induk-

tionsschluss”) Schluss von n auf n+ 1.

Folgerung aus beiden Schritten:

gilt fur n = 1, fur n = 2, n = 3, . . . gilt also fur alle n ∈ IN.

obiges Beispiel:

1. Schritt: n = 1: 13 =[

1·(1+1)2

]2

: O.K.

2. Schritt:{13 + 23 + . . .+ n3} + (n+ 1)3

durch Benutzung der Induktionsannahme A(n)

=

{[n(n+ 1)

2

]2}

+ (n+ 1)3

=

(n+ 1

2

)2

·[

n2 + 4(n+ 1)︸︷︷︸

(n+2)2

]

=[ (n+ 1)(n+ 2)

2

]2

das ist die Aussage A(n+ 1)

Bemerkungen:

1.) kein konstruktiver Beweis

2.) haufiger Fehler: in der Aussage statt n einfach n+ 1 setzen; das ist kein Beweis.

Weitere Formeln, die sich z.B. mit vollstandiger Induktion beweisen lassen:

1 + 2 + 3 + . . .+ n =1

2n(n+ 1)

1 + x+ x2 + . . .+ xn =1 − xn+1

1 − x(abgebrochene geometrische Reihe)

(n+ 1

k + 1

)

=

(nk

)

+

(n

k + 1

)

fur die Binomialkoeffizienten

(nk

)

:=n!

k!(n− k)!mit

(n0

)

:= 1 ; Fakultat n! := 1 · 2 · . . . · n

41


3.2 Komplexe Zahlen

In Abschnitt 1.4 hatten wir die Erweiterung der Zahlenbereiche

IN → ZZ → IQ → IR

(naturliche Zahlen → ganze Zahlen → rationale Zahlen → reelle Zahlen) betrachtet.

Erneute Erweiterung des Zahlenbereichs:

Die Gleichung x2 + 1 = 0 (z.B.) besitzt im Bereich der reellen Zahlen keine Losung. Wir

fuhren neue, kunstliche Zahlen ein, welche diese Gleichung (per definitionem) losen sollen.

Zunachst ist formal/symbolisch

x = ±√−1 (sinnlos im Bereich der reellen Zahlen)

neues Symbol

x = ±i

dann isti2 + 1 = 0

(−i)2 + 1 = 0 ,

worausi2 = (−i)2 = −1

symbolisch: i =√−1

Definition: Sind a und b zwei beliebige reelle Zahlen, so definiert das Zahlenpaar (a, b)die komplexe Zahl z = a+ ib

a heißt Realteil von z , a = Re{z}b heißt Imaginarteil von z , b = Im{z}, b ∈ IR

i heißt imaginare Einheit. Es gilt:

i1 = i

i2 = −1

i3 = ii2 = −i

i4 = i2i2 = 1

i5 = i

i6 = −1

i7 = −i

i8 = 1

Rechenregeln fur komplexe Zahlen z1 = a1 + ib1 und z2 = a2 + ib2 :

Addition: z1 + z2 = (a1 + a2) + i(b1 + b2)Subtraktion: z1 − z2 = (a1 − a2) + i(b1 − b2)Multiplikation:

z1z2 = a1a2 + a1ib2 + ib1a2 + i2b1b2

= (a1a2 − b1b2) + i(a1b2 + a2b1)

Division:z1z2

=a1 + ib1a2 + ib2

=(a1 + ib1)(a2 − ib2)

(a2 + ib2)(a2 − ib2)

=a1a2 + b1b2 + i(a2b1 − a1b2)

a22 + b22

; a22 + b22 > 0

42


Falls in z = a+ ib der Imaginarteil b = 0 ist, dann z = a (Reduktion der komplexen Zahlen

auf reelle Zahlen). D.h. die reellen Zahlen sind in den komplexen Zahlen enthalten.

Falls a = 0, dann z = ib (Reduktion auf rein imaginare Zahlen).

Speziell ist i eine komplexe Zahl (a = 0, b = 1).

Definition Fur z = a+ ib heißt z := a− ib konjugiert zu z. Es gilt

zz = a2 + b2 ≥ 0 .

(zz ist also reell.)

Gleichung zwischen komplexen Zahlen:

z1 = z2

ist aquivalent zu zwei reellen Gleichungen:

a1 + ib1 = a2 + ib2 ⇔

{a1 = a2 und

b1 = b2

Insbesondere:

z = a+ ib = 0 (komplexe Null) ⇔ a = 0 und b = 0

Symbol fur Menge der komplexen Zahlen: IC := {z = a+ ib | a, b ∈ IR}

Geometrische Darstellung der komplexen Zahlen

z = x+ iy , x ∈ IR, y ∈ IR

z ↔ reelles Zahlenpaar (x, y) ↔ Punkt in Ebene

Definiton: (Gaußsche) Zahlenebene der komplexen Zahlen: eindeutige Zuordnung zwi-

schen allen komplexen Zahlen z und allen Punkten (x, y) der Ebene durch x = Re(z),y = Im(z).

z

− z

x

z

− z

Im (z)

Re (z)r cos ϕ

r sin ϕ

r=IzI

−y

ϕ

y

Folgerung:

1.) z = x− iy entsteht aus z durch Spiegelung an x-Achse.

2.) −z durch Spiegelung am Nullpunkt.

3.) komplexe Zahlen auch mit Polarkoordinaten darstellbar:

z = r(cosϕ+ i sinϕ)

Bezeichnung: |z| := r =√

x2 + y2 ist der Betrag einer komplexen Zahl.

arg(z) = arc(z) = ϕ = arccosx

r= arcsin

y

r= arctan

y

x

(je nach Vorzeichen; vgl. Abschnitt 1.1C oder Formelsammlung) ist das Argument oder

der Arcus von z.

43


Deutung der Rechenregeln: Addition: Parallelogramm: z1 + z2 durch Parallelver-

schiebung von z2 oder z1

y

x

2+ zz1

2z

z1

Subtraktion: z1 − z2 = z1 + (−z2)

Vektoren lassen sich parallel verschieben. Verabredung: Alle durch Parallelverschiebung

ineinander uberfuhrbare Vektoren (d.h. gleiche Lange und Richtung) sind identisch. Der

“Ortsvektor” ist der spezielle Vektor, dessen Fußpunkt in 0 ist.

Also: Die Addition von komplexen Zahlen ist geometrisch als Hintereinandersetzen von

Vektoren deutbar.

32

3

+ z+ z

+ z

3

2

z1

z

z

z11z

(geometrische Darstellung der) Multiplikation:

z1 = r1(cosϕ1 + i sinϕ1) , z2 = r2(cosϕ2 + i sinϕ2)

z1z2 = r1(cosϕ1 + i sinϕ1) · r2(cosϕ2 + i sinϕ2)

= r1r2 · [cosϕ1 cosϕ2 − sinϕ1 sinϕ2 + i(sinϕ1 cosϕ2 + sinϕ2 cosϕ1)]

= r1r2 · [cos(ϕ1 + ϕ2) + i sin(ϕ1 + ϕ2)]

Es folgt:

|z1z2| = r1r2 = |z1| |z2|

arc(z1z2) = ϕ1 + ϕ2 = arc(z1) + arc(z2)

D.h. bei der Multiplikation werden die Betrage multipliziert und die Winkel addiert:

1 2

z2r

ϕ11

x

r1

z1

ϕ1ϕ 2

y

2

ϕ + ϕ

��

��

��

z z1 2

1r r

2.

44


Hinweis: Insbesondere bei grafischen Darstellungen macht ein Winkel nur Sinn im Bereich

0 ≤ ϕ ≤ 2π, daruberhinaus fangt der Winkel wieder bei 0 an. Deswegen wird bei ϕ1+ϕ2 >2π die Zahl 2π subtrahiert.

Spezialfalle: |z2| = |z|2, arc(z2) = 2 arc(z); |zm| = |z|m , arc(zm) = m arc(z)

zur Division: Fur Quotienten ergibt sich:

z1z2

=r1r2

·[cos(ϕ1 − ϕ2) + i sin(ϕ1 − ϕ2)

], (r2 6= 0)

also:

|z1z2

| =|z1|

|z2|, arc

(z1z2

)

= arc(z1) − arc(z2)

Anwendung/Folgerungen fur z = i: wegen |i| = 1, arc(i) = π2

vermittelt iz eine Drehung um +π2 bzw. 90◦, denn iz = −y + ix.

Dreiecksungleichung gilt auch in IC:

‖z1| − |z2‖ ≤ |z1 ± z2| ≤ |z1| + |z2|

3.3 Polynome und Rationale Funktionen

A.) Polynome (im Reellen)

Definition: Polynom vom Grad m ist die Funktion

a0 + a1x+ a2x2 + . . .+ amx

m =

m∑

k=0

akxk , mit am 6= 0

Polynome sind von großter Wichtigkeit. In Abschnitt 2.7 traten sie auf als charakte-

ristisches Polynom von Matrizen. Wichtig sind Polynome auch zur Approximation von

Funktionen, z.B. cosx ≈ 1 − x2

2fur x ≈ 0 (vgl. u.a. Abschnitt 3.11).

Bezeichnung: Pm(x) :=m∑

k=0

akxk. Die ak heißen “Koeffizienten”.

Gleichheit von Polynomen:

m∑

k=0

akxk =

m∑

k=0

bkxk fur alle x ⇔ ak = bk fur alle k

(Beweis: x = 0 ⇒ a0 = b0. Dividiere durch x. x konnen beliebig klein werden ⇒ a1 =

b1 ⇒ . . .)

Folgerung: Koeffizentenvergleich

z.B.: x3 + ax2 + bx+ c =

[Suche Beziehung zwischen (angenommenen) Nullstellen x1, x2, x3. Falls solche Nullstellen

existieren (s.u.), ist dies von der Form]

= (x− x1)(x− x2)(x− x3)

45


Ausmultiplizieren ⇒ . . . = x3 − (x1 + x2 + x3)x2 + (x1x2 + x2x3 + x3x1)x− x1x2x3

Koeffizientenvergleich ⇒

a = −x1 − x2 − x3

b = x1x2 + x2x3 + x3x1

c = −x1x2x3

Satz von Vieta, hier fur m = 3

Auswertung von Polynomen mit “Horner-Schema”

Pm(x) = (. . . ((am · x+ am−1) · x+ am−2) · x+ . . .+ a1) · x+ a0 .

(m Multiplikationen, m Additionen)

B.) Nullstellen von Polynomen

Pm(x) = 0 heißt eine “algebraische Gleichung”, und Nullstellen heißen auch ”Wurzeln”.

Annahme: Pm(x) = 0 fur x = x1, also: Pm(x1) = 0

⇒ Pm(x) = Pm(x) − Pm(x1) = a0 + a1x+ . . .+ amxm − a0 − a1x1 − . . .− amx

m1

= a1(x− x1) + a2(x2 − x2

1) + . . .+ am(xm − xm1 )

= a1(x− x1) + a2(x− x1)(x+ x1) + a3(x− x1)(x2 + xx1 + x2

1)+

+ . . .+ am(x− x1)(xm−1 + xm−2x1 + . . .)

= (x− x1) ·{a1 + a2(x+ x1) + a3(x

2 + xx1 + x21) + . . .

}

= (x− x1){c0 + c1x+ c2x

2 + . . .+ cm−1xm−1

}mit cm−1 = am 6= 0

D.h. das Polynom Pm(x) kann ohne Rest durch x−xk dividiert werden, wenn xk Nullstelle

ist.

Definition: Der Faktor x− xk heißt Linearfaktor.

Die Berechnung von Pm−1(x) =Pm(x)x−x1

heißt Abdividieren.

Falls auch Pm−1 eine Nullstelle hat, fur x = x2, dann kann der Linearfaktor (x − x2)

abgespalten werden, und es entsteht Pm−2(x).

u.s.w. ...

Dieser Prozess kann fortgefuhrt werden, solange das jeweils entstehende Polynom niederen

Grades eine Nullstelle hat, langstens also bis

Pm(x) = (x− x1)(x− x2) · . . . · (x− xm) · am

Damit haben wir gezeigt: Ein Polynom m-ten Grades kann hochstens m Nullstellen haben.

Also gilt:

Satz: Hat ein Polynom Pm(x) mehr als m Nullstellen, so muss Pm(x) ≡ 0 gelten, also

a0 = a1 = . . . = am = 0.

x1 heißt k-fache Nullstelle, wenn Pn(x) ohne Rest durch (x−x1)k teilbar ist, nicht aber

durch (x− x1)k+1.

C.) Zur Existenz von Losungen algebraischer Gleichungen

Uber den reellen Zahlen, d.h. x ∈ IR, ist eine Zerlegung von Pm(x) in Linearfaktoren nicht

immer moglich.

46


Beispiel: 1 + x2 = 0 hat keine Losung fur x ∈ IR.

Aber: Uber den komplexen Zahlen, d.h. x ∈ IC, ist jede algebraische Gleichung losbar!

Fundamentalsatz der Algebra: Ein Polynom vom Grad m hat genau m Wurzeln ∈ IC,

wobei k-fache Nullstellen k mal gezahlt werden.

Beispiel:

x4 + 1 = 0 keine Losung in IR .

x4 + 1 = 0 in IC :

Erste Uberlegung: (z2)2 = −1 ⇒ z2 = ±i ergibt 4 Losungen mit√i.

Was ist√i?

andere Uberlegung mit dem Argument “Drehung”:

zzzz = −1

Die Zahl z1 := 1√

2(1 + i) mit |z1| = 1, ϕ = arc(z1) = π/4 ergibt z2

1 = i, z31 = 1

√

2(−1 + i),

z41 = −1 mit 2ϕ, 3ϕ, 4ϕ. Fur 4ϕ = π wird −1 erreicht. Analog:

z2 :=1√

2(−1 + i) mit arc(z2) =

3

4π

z3 :=1√

2(−1 − i) mit arc(z3) =

5

4π

z4 :=1√

2(1 − i) mit arc(z4) =

7

4π

Illustration: jeweils Drehungen; alle 4 Nullstellen liegen auf dem Einheitskreis;

arc(z42) = 3π entspricht π



Fur Winkel > 2π werden ganzzahlige Vielfache von 2π abgezogen.

Satz: Wenn eine algebraische Gleichung reelle Koeffizienten hat und z1 = x1 + iy1 Wurzel

ist, dann ist auch z1 = x1 − iy1 Wurzel.

Anwendung: Eigenwerte von reellen Matrizen als Nullstellen des charakteristischen Poly-

noms. Die Linearfaktoren (z−z1) und (z−z1) konnen jeweils zu einem quadratischen

Faktor mit reellen Koeeffizienten zusammengefasst werden.

obiges Beispiel: z4 = z1, z3 = z2, und

z4 + 1 = (z − z1)(z − z1)(z − z2)(z − z2)

Produkt der ersten beiden Linearfaktoren:

(z −1√

2(1 + i))(z −

1√

2(1 − i))

=((z −1√

2)2 −

i2

2)

=(z2 −2√

2z +

1

2+

1

2)

=(z2 −√

2z + 1)

47


insgesamt

z4 + 1 = (z2 −√

2z + 1)(z2 +√

2z + 1)

Zusammenfassend: Die folgende reelle Darstellung ist moglich:

Jedes Polynom mit reellen Koeffizienten lasst sich in reelle lineare und reelle quadratische

Faktoren (bzw. ihre Potenzen) zerlegen. Dabei haben die quadratischen Faktoren keine

reelle Nullstelle.

D.) Rationale Funktionen

Quotienten zweier Polynome

f(x) =Pm(x)

Qn(x)=amx

m + . . .+ a1x+ a0

bnxn + . . .+ b1x+ b0, am 6= 0, bn 6= 0

heißen rationale Funktionen.

Polynome ergeben sich als Spezialfall fur n = 0 und heißen auch “ganze” rationale

Funktionen. n > 0: “gebrochen” rationale Funktionen.

Ohne Einschrankung: Pm und Qn seien teilerfremd. Anderenfalls Zahler und Nenner durch

gemeinsames Teilerpolynom kurzen.

Methode: Euklidischer Algorithmus (−→ Abschnitt 3.4)

Nach Kurzen: keine gemeinsamen Nullstellen mehr. Die Nullstellen des Zahlers sind die

Nullstellen von f(x). Die Nullstellen des Nenners sind die Unendlichkeitsstellen. (“ver-

tikale Asymptoten” oder “Polstellen”)

asymptotisches Verhalten (fur x→ +∞ und x→ −∞)

f(x) =Pm(x)

Qn(x)=am

bn

xm

xn·(1 +

am−1

am

1x

+ . . .+ a0

am

1xm )

1 +bn−1

bn

1x

+ . . .+ b0bn

1xn )

Der zweite Faktor geht gegen 1 fur |x| → ∞. Der erste Faktor beschreibt das asymptotische

Verhalten.

Falle:

m < n ⇒ f(x) → 0

m = n ⇒ f(x) → am

bn

m > n ⇒ f(x) → ∞

Weitere Untersuchungen zu m > n:

Durch Ausdividieren ist stets eine Zerlegung in Summe von einer ganzrationalen

Funktion plus einer gebrochenen rationalen Funktion moglich.

Beispiel:2x3 + 5x2 + x− 7

x2 + x− 2= 2x+ 3 +

2x− 1

x2 + x− 2

Durch 2x+ 3 ist eine schrage Asymptote definiert. Der Bruch auf der rechten Seite

hat als Nenner (x− 1)(x+ 2) und damit gibt es senkrechte Asymptoten bei x1 = 1

und x2 = −2. Illustration siehe Vorlesung.

48


3.4 Der Euklidische Algorithmus; Kettenoperationen

In diesem Abschnitt: Fast alle Zahlen seien ∈ IN, z.B. a, b, c, s ∈ IN.

a und b heißen Teiler von c, wenn c = ab

weitere Anwendung: Polynomdivision.

Kettendivision: a > b, teile a durch b ...

a = bs0 + r1 (mit r1 < b)b = r1s1 + r2 (mit r2 < r1)r1 = r2s2 + r3

......

rn−3 = rn−2sn−2 + rn−1

rn−2 = rn−1sn−1 + rnrn−1 = rnsn (+0)

Ruckwarts-Folgerung:

rn teilt rn−1 ⇒ rn teilt rn−2 ⇒ . . .

⇒ rn teilt b und rn teilt a

rn ist also gemeinsamer Teiler von a und b.

Frage: Gibt es einen großeren Teiler?

Vorwarts-Folgerung:

t teile a und b ⇒ t teilt r1 ⇒ t teilt r2 ⇒

. . . ⇒ t teilt rn ⇒ t ≤ rn

Also: Die mit obiger Kettendivision berechnete Zahl rn ist der großte gemeinsame

Teiler von a und b.

Euklidischer Algorithmus fur naturliche Zahlen (iterierte Division, Kettendivision)

r0 := a , r1 := b,fur j = 1, 2 . . .:

rj−1 = rj · sj + rj+1 mit 0 ≤ rj+1 < rj

Der Algorithmus bricht ab bei k mit rk+1 = 0. Resultat:

rk = ggT(a, b)

Wegen ggT (a, b) · kgV (a, b) = a · b gilt:

kgV (a, b) =a · b

rk

(vgl. Vorlesung uber Informatik)

Obige Kettendivision ist auf Polynome anwendbar.

Beispiel:

f(x) =P3(x)

Q3(x)=

x3 − x2 − x+ 1

x3 + 2x2 − x− 2

Was ist der großte gemeinsame Teiler?

49


Bei der Polynomdivision kommt es auf Zahlenfaktoren nicht an.

P3 : Q3 = 1 mit Rest r1 = −3x2 + 3 = −3(x2 − 1)

Also:

P3 = Q3 · 1 − 3x2 + 3

Der Rest kann durch Multiplikation mit beliebiger Zahl vereinfacht werden zu r1. (hier:

r1 = x2 − 1)

Q3 = (x2 − 1) · (x+ 2) + 0

Folgerung: x2 − 1 ist großtes gemeinsames Teilerpolynom.

Kurzen ⇒P3(x)

Q3(x)=x− 1

x+ 2

Es bleibt eine senkrechte Asymptote fur x = −2. In der ursprunglichen Version hatte der

Nenner die weiteren Nullstellen x = +1 und x = −1. Da diese beiden auch Nullstellen des

Zahlers waren, ist f(x) durch das Kurzen an den Stellen x = ±1 “repariert”.

3.5 Funktionen

A.) Der Funktionsbegriff

Wird jeder Zahl x ∈ IR eines vorgegebenen Bereiches eindeutig eine Zahl y ∈ IR zugeordnet,

so heißt y eine Funktion der “Veranderlichen” x. Schreibweise

y = f(x) (oder y = y(x)) ,

dabei: y: “abhangige” Variable, x: “unabhangige” Variable, “Argument der Funktion”

Vorsicht: auch andere Bezeichnungen! z.B. ψ = sinϕ oder r = cos t.

Die Menge derjenigen x, fur die f(x) definiert ist, heißt Definitionsbereich. Die Menge

der zugehorigen Werte f(x), fur x im Definitionsbereich, heißt Wertebereich. Fasst man

x und y als Koordinaten auf, dann ist eine graphische Darstellung moglich. Jedem Paar

x, y entspricht ein Punkt in der (x, y)-Ebene. Fur alle x im Definitionsbereich beschreibt

der Punkt (x, y(x)) typischerweise ein Kurvenstuck. Die Punktmenge {(x, f(x))|x ∈

Definitionsbereich} heißt Graph der Funktion f(x).y

Definitionsbereichx

Werte−bereich

Die Definitionsbereiche sind meist

“offene” Intervalle a < x < b oder

“abgeschlossene” Intervalle a ≤ x ≤ b oder

“halboffene” Intervalle a ≤ x < b oder a < x ≤ b oder

“unendliche” Intervalle −∞ < x <∞ oder

“einseitig unendliche” Intervalle z.B. a ≤ x <∞

50


Bemerkung: Nicht jede Kurve entspricht einer Funktion!

x

nicht eindeutigkeine Funktion, weil

z.B.y

Beispiele:

f(x) = sinx fur −∞ < x <∞

f(x) = +√x fur 0 ≤ x <∞

f(x) = +√

r2 − x2 fur − r ≤ x ≤ r

f(x) ={

1 fur x > 0

−1 fur x < 0

f(x) = x fur x ∈ IN (kein Kurvenstuck, sondern diskrete Punkte)

f(x) = log x fur x > 0

Hintereinanderausfuhrung oder “Verkettung” von Funktionen: Falls der Wertebereich

von f im Definitionsbereich von g enthalten ist, dann ist

h(x) = g(f(x))

eine Funktion. Beispiel: h(x) :=√

1 + x2, mit f(x) = 1 + x2 und g(y) =√y.

B.) Umkehrfunktionen, Monotonie

Wenn auch jedem Funktionswert y = f(x) eindeutig ein Urbild x entspricht, dann kann xals Funktion von y betrachtet werden:

x = g(y).

Dann heißt x = g(y) die Umkehrfunktion von y = f(x).Bezeichnet man bei der Umkehrfunktion x = g(y) die unabhangige Veranderliche mit

x und die abhangige Veranderliche mit y, dann spricht man von der inversen Funktion

y = g(x) = f−1(x). (Vorsicht: Die symbolische Schreibweise f−1 bedeutet hier nichtDivision, sondern Inversion einer Funktion.)

Umkehrfunktionen gibt es also, wenn in beiden Richtungen x↔ y Eindeutigkeit vorliegt.

Zuordnung x→ y eindeutig ⇔ jede Parallele zur y-Achse wird von f(x) genau einmal

geschnitten.

Zuordnung y → x eindeutig ⇔ jede Parallele zur x-Achse wird von g(y) genau

einmal geschnitten.

Hinreichend fur die Existenz einer Umkehrfunktion ist strenge Monotonie von f .

Definition:

f(x) (streng) monoton wachsend auf einem Intervall, wenn x1 < x2 ⇒ f(x1) < f(x2)

fur alle x1, x2 in dem Intervall.

51


f(x) monoton fallend auf Intervall, wenn x1 < x2 ⇒ f(x1) > f(x2)

f(x) monoton auf einem Intervall, wenn f auf dem gesamten Intervall entweder monoton

wachsend oder monoton fallend ist (ausschließlich).

Beispiel

β

α

f(x)

xcba

aufa ≤ x ≤ b : f monoton wachsend

b ≤ x ≤ c : f monoton fallend

a ≤ x ≤ c : f ist nicht monoton

α ≤ y ≤ β : keine eindeutige Zuordnung y → x

also: Fur f(x) auf a ≤ x ≤ c gibt es keine Umkehrfunktion! Umkehrfunktionen

existieren aber stuckweise, d.h. fur Teilintervalle. Die genaue Angabe der jeweiligen

(Teil-)Intervalle ist also bei Monotonie-Angaben wichtig.

Definition: Eine Funktion f(x), fur die auch die Zuordnung y → x eindeutig ist, heißt

eineindeutig oder injektiv.

Zusammen: Die folgenden Kriterien fur eine Funktion f(x) sind aquivalent zur Injek-

tivitat:

(a) Die Gleichung f(x) = y hat fur alle y hochstens eine Losung.

(b) fur alle x1, x2 ∈ Definitionsbereich: f(x1) = f(x2) ⇒ x1 = x2

(c) fur alle x1, x2 ∈ Definitionsbereich: x1 6= x2 ⇒ f(x1) 6= f(x2)

(d) f ist uber dem Definitionsbereich umkehrbar.

Geometrische Konstruktion: Die Kurven y = f(x) und y = f−1(x) gehen durch Spiegelung

an der Winkelhalbierenden auseinander hervor.

y= f(x)

xa

a

y

��

��

−1 (x)y=g(x)=f

−1(y) g(y)=x = f

Nach Definition der Umkehrfunktion gilt die Identitat f(f−1(y)) = y fur alle y ∈Wertebereich,

und f−1(f(x)) = x fur alle x ∈Definitionsbereich.

52


Implizite Darstellung von Funktionen:

Bisher: nach y aufgeloste Gleichungen y = f(x).

Beispiele: y = sinx oder y = 11−x

.

Falls nach x aufgelost: x = g(y) oder x = f−1(y).

Derartige Darstellungen von Funktionen nennt man explizit.

Alternative: Funktionen konnen implizit definiert werden durch eine Gleichung F (x, y) =

0. Durch Auflosen der Gleichung F (x, y) = 0 nach x oder nach y konnen in vielen Fallenexplizite Funktionen hergeleitet werden. Umgekehrt kann eine explizite Darstellung y =

f(x) immer als F (x, y) = 0 geschrieben werden: F = y − f(x).

Beispiel: F (x, y) = x2 + y2 − 1 = 0

Auflosen z.B. nach y liefert zwei Funktionen:

y1(x) := +√

1 − x2

y2(x) := −√

1 − x2

Stuckweise existieren Umkehrfunktionen:

x1(y) := +√

1 − y2 , x2(y) := −√

1 − y2

(Abbildungen vgl. Vorlesung)

Beachte: Eine Gleichung F (x, y) = 0 definiert implizit entweder

(1) keine Funktion (Beispiel F (x, y) = x2 + y2 + 1 = 0), oder

(2) eine eindeutige Funktion (Beispiel F (x, y) = y − ex = 0), oder

(3) mehrere Funktionen (Beispiel Kreis).

Parameterdarstellung

Eine weitere Alternative zur Definition von Kurven (außer mit expliziten oder impliziten

Funktionen) ist die Parameterdarstellung: Dabei werden zwei Funktionen x(t) und y(t)als Komponenten zu einem Vektor (

x(t)y(t)

)

zusammengefasst. Die den beiden Komponenten gemeinsame unabhangige Variable t heißt

hier Parameter.

Beispiel:

(r cos tr sin t

)

beschreibt fur wachsende t den Weg eines Punktes in der (x, y)-Ebene,

der einen Kreis mit Radius r entlangwandert. Fur 0 ≤ t ≤ 2π wird dieser Kreis genau

einmal durchlaufen. (vgl. Polarkoordinaten in Abschnitt 1.1B.)

C.) Stetigkeit

Anschaulich: Eine Funktion ist “stetig”, wenn man sie zeichnen kann, ohne den Stift

abzusetzen.

53


Beispiele fur unstetige Funktionen:

1.)

yf(x)

"stückweise stetig"hier noch

a b

Sprungstelle

x

2.) Rationale Funktionen mit Nullstellen des Nenners: Pol-Verhalten, vgl. Abschnitt

3.3D.

3.)

y ={

0 fur rationale x1 fur irrationale x

Definition: “Umgebung” Eine ǫ-Umgebung von x0 ist die Menge aller x ∈ IR mit

|x− x0| < ǫ, fur ǫ > 0.

0ε+x

0x0 ε − x

meist: kleine Umgebungen, d.h. ε ist ein kleiner “Radius”.

Stetigkeit: Die Funktionswerte f(x) in einer Umgebung von x0 andern sich beliebig

wenig, wenn die Umgebung genugend klein ist.

ε

ε

δ δ00

y

x

0

0

0

x −

0

x +

y +

y −

y

x

Fur jeden beliebig schmalen Streifen um y0 = f(x0) gibt es eine Umgebung um x0, so dass

der Graph von f(x) fur das Intervall x0 − δ ≤ x ≤ x0 + δ in dem horizontalen Streifen

liegt.

formale Definition: f(x) ist stetig an der Stelle x0, wenn man zu jedem ε > 0 eine

Zahl δ > 0 angeben kann, so dass

|x− x0| < δ ⇒ |f(x) − f(x0)| < ε .

Und: f ist stetig in einem Intervall, wenn f(x) fur ∀ x ∈Intervall stetig ist.

Bemerkung: δ hangt i.A. ab von ε und von x0: δ = δ(ε, x0)

Bedeutung stetiger Funktionen: Fur sie gelten wichtige Eigenschaften!

1.) Zwischenwertsatz: Ist f(x) stetig fur a ≤ x ≤ b, und f(a) < c < f(b), so gibt es

ein x∗ in a < x∗ < b mit f(x∗) = c.

(analog f(a) > c > f(b))

54


Weitere Eigenschaften stetiger Funktionen:

Fur jede auf einem abgeschlossenen Intervall a ≤ x ≤ b stetige Funktion f(x) gilt:

2.) f ist auf dem Intervall beschrankt, d.h. es gibt eine Schranke K, so dass |f(x)| < Kfur a ≤ x ≤ b .

3.) f nimmt auf a ≤ x ≤ b ein Maximum und ein Minimum an, d.h.

∃ x1, x2 in a ≤ x ≤ b so dass f(x1) ≤ f(x) ≤ f(x2) fur alle a ≤ x ≤ b .

Zur Wichtigkeit der Abgeschlossenheit: f(x) = 1x

auf dem offenen Intervall 0 < x <∞ ist

nicht beschrankt.

Fur allgemeine Intervalle gilt:

Sind f und g stetig, dann sind auch f ±g, α ·f , f · g stetig, sowie fg

in jedem Teilintervall

von x, auf dem g(x) 6= 0, und ebenso die Hintereinanderausfuhrung h(x) := f(g(x)) stetig.

Beispiel: p(x) = anxn + · · ·+ a1x+ a0 (Polynom) ist stetig.

Praktische Abkurzungen (zur Erinnerung):

∃ fur: “es existieren”, z.B. ∃ x∗

∀ fur: “Fur alle”, z.B. ∀ x

3.6 Spezielle Funktionen

A.) Kreisfunktionen

(auch Trigonometrische Funktionen)

sin, cos, tan, cot

(in der Geometrie zunachst nur Seitenverhaltnisse im rechtwinkligem Dreieck, dann Aus-

dehnung uber den Kreis, schließlich fur ganz IR.)

ϕsin < 0

y

x

P

ϕϕ

r

ϕ

cos < 0

y

sin > 0

cos >0

ϕ cos > 0ϕ

x

sinϕ > 0

cos < 0

ϕsin < 0

ϕ

Definitionen:

sinϕ :=y

r(“Gegenkathete zu Hypothenuse”) y = r sinϕ

cosϕ :=x

r(“Ankathete zu Hypothenuse”) x = r cosϕ

tanϕ :=sinϕ

cosϕ=y

x(“Steigung”)

cotϕ :=1

tanϕ=

cosϕ

sinϕ=x

y

55


(Fur Illustrationen sei auf die Vorlesung verwiesen, oder auf Literatur wie Formelsamm-

lungen.)

Vorzeichen von cosϕ = Vorzeichen von x

Vorzeichen von sinϕ = Vorzeichen von y

Nach Erweiterung der trigonometrischen Funktionen auf den Kreis als nachster Schritt

periodische Fortsetzung auf ganz IR:

cos(ϕ+ n · 2π) = cosϕ fur ∀ n ∈ ZZ

sin(ϕ+ n · 2π) = sinϕ fur ∀ n ∈ ZZ .

Damit sind sin, cos uberall definiert. Bezeichnung fur die unabhangige Variable: ϕ oder toder x (anderes x als oben!!): z.B. sinx, cosx, fur x ∈ IR.

einige Eigenschaften der Kreisfunktionen

cos(−ϕ) = cosϕ , cos(π − ϕ) = − cosϕsin(−ϕ) = − sinϕ , sin(π − ϕ) = sinϕcos(ϕ+ π) = − cosϕ , cos(π

2 − ϕ) = sinϕsin(ϕ+ π) = − sinϕ , sin(π

2− ϕ) = cosϕ ,

cos(ϕ+ π2 ) = − sinϕ

sin(ϕ+ π2 ) = +cosϕ , cos2 ϕ+ sin2 ϕ = 1 (Pythagoras) .

cosx und sinx sind stetig fur alle x;| cosx| ≤ 1 , | sinx| ≤ 1

cosx = 0 fur x = (2n+ 1)π2 , n ∈ ZZ

sinx = 0 fur x = n · π , n ∈ ZZ.

(Additionstheoreme, z.B. sin(x+ y) = . . .: s.u. bzw. Formelsammlung)

tan(ϕ± nπ) = tanϕ

cot(ϕ± nπ) = cotϕ

}

n = 0, 1, 2 . . .

tan(−ϕ) = − tanϕcot(−ϕ) = − cotϕtanx und cot x sind nur stuckweise stetig!

Exkurs: Bezeichnungen/Definitionen

∗ Eine Funktion f(x) heißt periodisch mit Periode p, wenn fur jedes x und jedes

n ∈ ZZ gilt:

f(x+ np) = f(x)

Beispiele:

sinx, cosx : Periode 2π

tanx, cotx : Periode π

∗ Eine Funktion f(x) heißt gerade, wenn f(−x) = f(x)Beispiele: cosx, x2. geometrische Bedeutung: Symmetrie zur y-Achse.

∗ Eine Funktion f(x) heißt ungerade, wenn f(−x) = −f(x)Beispiele: sinx, tanx, cotx, x3. geometrische Bedeutung: Symmetrie zum Nullpunkt.

Weitere Beispiele fur gerade Funktionen:

f(x) := sin |x|, denn: f(−x) = sin | − x| = sin |x| = f(x)f(x) := | sinx|, denn: f(−x) = | sin(−x)| = | − sinx| = | sinx| = f(x)

56


B.) Weitere Formeln zu trigonometrischen Funktionen

Multiplikation von komplexen Zahlen (vgl. Abschnitt 3.2) z1 und z2 ∈ IC mit |z1| = |z2| = 1:

(cosϕ+ i sinϕ) · (cosψ + i sinψ) = cos(ϕ+ ψ) + i sin(ϕ+ ψ)

Andererseits, mit Ausmultiplizieren erhalte

(cosϕ cosψ − sinϕ sinψ) + i(sinϕ cosψ + cosϕ sinψ)

Folgerung mit “Koeffizientenvergleich”:

sin(ϕ+ ψ) = sinϕ cosψ + cosϕ sinψ

cos(ϕ+ ψ) = cosϕ cosψ − sinϕ sinψ

Diese Formeln heißen Additionstheoreme.

Hieraus folgen andere wichtige Formeln, siehe Formelsammlung!

z.B. fursin(ϕ− ψ), cos(ϕ− ψ), tan(ϕ± ψ) ;

sin(2ϕ), cos(2ϕ), sinα± sinβ, cosα± cosβ

C.) Anwendungen trigonometrischer Funktionen:

1.) uberall im Alltag (vom Regenbogen zum Farbfernsehen)

2.) Losungen einfacher Schwingungsgleichungen

3.) Fourier: Fur periodische Funktionen y(t) mit Periode T

y(t) =a0

2+

∞∑

k=1

(ak cos(k 2πTt) + bk sin(k 2π

Tt))

Fourier-Koeffizienten:

ak =2

T

T∫

0

y(t) cos(k 2πTt)dt

bk =2

T

T∫

0

y(t) sin(k 2πTt)dt

y −→ ak, bk : Fourier-Analyse

ak, bk −→ y : Fourier-Synthese

D.) Potenzen und Wurzeln von reellen Zahlen (≥ 0)

Schulstoff: x0 := 1 fur x 6= 0, xn := x · x · . . . · x︸︷︷︸

n−mal

, x−n := 1xn

⇒ xnxm = xn+m , xmn = (xm)n = (xn)m fur n,m ∈ ZZ , x ∈ IR

Es seien x > 0, y > 0 reelle Zahlen, n ∈ ZZ.

57


Die Funktion x = yn ist fur x ≥ 0 monoton und stetig ⇒ Dann existiert Umkehrfunktion

(vgl. Abschnitt 3.4.B). D.h. fur jedes x > 0 gibt es genau ein y > 0 so dass x = yn.

Schreibweisen: y = (x)1/n = x1/n = n√x “n-te Wurzel”

Sei nun q ∈ IQ, q = mn

. Dann gilt fur x ≥ 0:

xq := xmn =

n√xm = ( n

√x)m

⇒ xqxp = xq+p auch fur rationale Exponenten.

Potenzen mit reellen Exponenten: → SPATER

Funktionen y = xq: alle gehen durch den Punkt (1, 1).

qq = + infty

(q=1)−y = x

1

1x

Bsp. y = x0.5

(q=0)

4Bsp. y = x Bsp. y = 1x = x−1

0<q<1

1<q< infty

q < 0

Die Kurven von y = xq, x ≥ 0, q ∈ IQ “uberdecken” den Quadranten.

E.) Weitere spezielle Funktionen

Umkehrfunktionen der trigonometrischen Funktionen:

arcsin, arccos, arctan, arcot

vgl. Formelsammlungen.

Exponentialfunktion exp(x) := ex und log(x) werden in Abschnitt 3.10 formal definiert.

Sie sind Umkehrfunktionen zueinander (Verlauf und Achsenschnittpunkte: vgl. Figur)

weitere wichtige Eigenschaften:

ex1ex2 = ex1+x2 ; log x1 + log x2 = log(x1x2)

F.) Kurvendiskussionen

zu diskutieren: y = f(x)

Programm:

1.) Feststellung des Definitionsbereiches und des Wertebereiches

2.) Bestimmung der Achsenschnittpunkte x = αi, wo

f(αi) = 0 ,

58


sowie f(0).

3.) Bei rationalen Funktionen:

Teiler-Fremdheit herstellen (Euklidischer Algorithmus), und bei m ≥ n Ausdividieren

4.) Asymptotisches Verhalten fur x→ ±∞; Bestimmung von Unendlichkeitsstellen x = βi

(f(x) → ±∞ fur y → βi)

mit Bestimmung des Vorzeichens von f(x) fur β+i , β−

i

5.) Auffinden evtl. Symmetrien (f gerade oder ungerade?)

6.) Monotonie, Maxima, Minima, Wendepunkte (Schule, bzw. Abschnitt 3.8)

7.) evtl. weitere Kurvenpunkte berechnen.

8.) (qualitative) Skizze

Bemerkung: Es sind nicht immer alle Punkte des obigen Programms sinnvoll oder mach-

bar.

3.7 Grenzwert

A.) Folgen und Reihen

Eine Folge von Zahlen a1, a2, a3, . . . , aν , . . . nennt man (Zahlen-)Folge. Dargestellt auf

der Zahlengerade entspricht dies einer Punktfolge.

Beispiele:

(a) 1, 2, 3, 4, . . . d.h. aν = ν(b) 1,−1

2, 1

3,−1

4, . . . d.h. aν = (−1)ν−1 1

ν

(c) 12 ,

23 ,

34 ,

45 , . . . d.h. aν = ν

1+ν

(d) 0.2, 0.22, 0.222, . . . d.h. aν =ν∑

k=1

2 · 10−k

Bemerkung: Der Index ν kann z.B. auch bei 0 loslaufen. Abkurzende Bezeichnung fur

Folgen: {aν} oder {aν}∞

ν=1 oder evtl. {aν}∞

ν=0

Definition: Eine Folge heißt beschrankt, wenn es eine Zahl M gibt, so dass |aν | ≤ Mfur alle ν; oder aquivalent: M1 ≤ aν ≤M2 (M1 =“untere Schranke”, M2 =“obere

Schranke”)

M “Schranke”

obige Beispiele:

(b), (c) beschrankt durch jede Zahl M ≥ 1

(d) z.B. M = 29 (kleinste aller oberen Schranken)

(a) ubeschrankt

Definition: Monotonie einer Folge: Eine Folge heißt monoton, wenn eine der folgenden

Bedingungen fur alle ν zutrifft:

aν+1 > aν : monoton wachsend

aν+1 < aν : monoton abnehmend oder fallend

aν+1 ≥ aν : monoton nicht abnehmend

aν+1 ≤ aν : monoton nicht wachsend

59


Beispiel:

(a), (c), (d): monoton wachsend

(b): nicht monoton (aber |aν | ist monoton abnehmend)

Definition: h heißt Haufungspunkt oder Haufungsstelle der Folge {aν}, wenn in

jeder noch so kleinen Umgebung von h unendliche viele aν liegen.

d.h.: fur alle ε > 0 gilt |h− aν | < ε fur unendlich viele aν .

obige Beispiele:

(b) : Haufungsstelle: h = 0

(c) : Haufungsstelle: h = 1

(d) : Haufungsstelle: h = 2/9

Das Beispiel (−1)ν−1 ν1+ν

hat 2 Haufungstellen: h = +1 und h = −1.

Satz [Bolzano & Weierstraß]

Jede beschrankte Folge hat mindestens eine Haufungsstelle.

(unendliche Folgen, d.h. ν → ∞)

Beweis: |aν | ≤M definiert ein Intervall I1 der Lange 2M mit unendlich vielen aν .

Intervallhalbierung ⇒ in wenigstens einem Teilintervall liegen ∞-viele aν : Intervall

I2. (usw.) → “Intervallschachtelung”: I1 ⊃ I2 ⊃ I3 ⊃ . . ., Breite der Ik geht gegen 0.

In jedem Ik liegen ∞-viele aν .

Ik konvergieren gegen einen Punkt, der die Voraussetzungen des Haufungspunktes

erfullt.

Definition: Reihe: Es sei {aν} eine Zahlenfolge. Die Folge der Partialsummen {sν},

definiert durch s1 := a1, s2 := a1 + a2, . . . , sν :=ν∑

k=1

ak, . . . , heißt unendliche Reihe.

Bezeichnung:∞∑

ν=1aν .

B.) Konvergenz von Folgen

Definition: a heißt Grenzwert der Folge {aν}, wenn in jeder noch so kleinen Umgebung

von a alle aν mit Ausnahme von endlich vielen liegen.

D.h. fur alle ε > 0 gibt es N = N(ε) ∈ IN, so dass |a− aν | < ε fur alle ν > N(ε).

Folgerungen:

1.) Jeder Grenzwert ist Haufungspunkt.

2.) Falls 2 Haufungspunkte existieren, gibt es keinen Grenzwert.

3.) Also ist nicht jeder Haufungspunkt auch Grenzwert. (Beispiel: 1,−1, 1,−1, . . .)

Definition: Hat eine Folge {aν} einen Grenzwert a, so heißt sie konvergent.

Bezeichnung: limν→∞

aν = a (“limes”)

oder: aν −→ a fur ν → ∞

Definition: Nichtkonvergente Folgen heißen divergent.

Konvergenzkriterium von Cauchy

Eine Folge {aν} ist “dann und nur dann” (d.h. ⇔) konvergent, wenn fur alle hinreichend

großen n ∈ IN und beliebige m ∈ IN die Differenzbetrage |an+m−an| beliebig klein werden.

60


D.h. aquivalent zur Konvergenz der {aν} ist:

∀ ε > 0 ∃ N(ε) so dass ∀ n > N(ε) und ∀ m ∈ IN gilt |am+n − an| < ε

Bemerkung: Der Grenzwert a wird hier nicht explizit benotigt!

Beispiele:

1.) 0.2, 0.22, . . . , aν =ν∑

k=1

2 · 10−k ⇒

am+n − an =

n+m∑

k=n+1

2 · 10−k

︸︷︷︸

m Terme

= 2 · 10−(n+1) · ( 1 +1

10+

1

100+ . . .+ 10−(m−1)

︸︷︷︸

Mit x:= 110

ist dies eine Partialsumme1+x+x2+...+xm−1=:sm

)

Herleitung einer Formel fur sm:

xsm = x+ x2 + . . .+ xm ⇒

xsm − sm = xm − 1 ⇒ sm =1 − xm

1 − x

Es folgt fur das Beispiel:

sm <1

1 − 110

=10

9⇒

am+n − an < 2 · 10−n 1

10

10

9< 10−n

Fur genugend großes n wird dies kleiner als jedes ε > 0.

2.) sm := 1 + x+ x2 + . . .+ xm−1 heißt endliche geometrische Reihe.

sm = 1−xm

1−x

Fur |x| < 1 ⇒ xm −→ 0 fur m→ ∞

⇒ sm → 11−x

fur m→ ∞

⇒∞∑

ν=0xν = 1

1−xfur |x| < 1

heißt (unendliche) geometrische Reihe.

Regeln

aν → a, bν → b ⇒

(aν ± bν) → (a± b)(aν · bν) → (a · b)(

aν

bν

)

→(

ab

)falls bν 6= 0 und b 6= 0

aν → a ⇒ |aν | → |a|

aν → a ⇒ αaν → αa

aν → a, bν → b, aν < bν ⇒ a ≤ b !!

(Beispiel: aν = 1(ν+1)2

, bν = 1ν+1

, a = b = 0)

einfaches hinreichendes Kriterium: {aν} monoton und beschrankt ⇒ Konvergenz

61


C.) Grenzwert einer Funktion; Stetigkeit

Definition: g ist Grenzwert der Funktion f(x) an der Stelle x = x0, wenn fur jede

Folge xν → x0, fur die f(x) definiert ist, die Folge {f(xν)} gegen g konvergiert.

Schreibweise: limx→x0

f(x) = g.

→ alternative Definition der Stetigkeit von f in x0 (g = f(x0)):

Die Funktion f(x) ist an x = x0 stetig, wenn

f(x) → f(x0) fur x→ x0

(im Sinne: fur alle Folgen xν → x0)

Folgerung: f stetig ⇒ f und Limes vertauschbar:

limx→x0

f(x) = f( limx→x0

x) (= f(x0))

z.B.√

lim aν = lim√aν

Beispiel:

f(x) =

{1 fur x = 0

sin xx

fur x 6= 0

}

ist stetig, denn:

zu zeigen ist: sinxx

→ 1 fur x→ 0.

1

1

x

Kreis mit Radius 1. x im Bogenmaß ⇒ Flache des Kreissektors ist x2.

Vergleich mit den Flachen des “inneren” und des “außeren” Dreiecks:

1

2sinx cosx <

x

2<

1

2tanx ⇒ cosx <

x

sinx<

1

cosx

Also: x→ 0 ⇒ cosx→ 1

62


3.8 Differentialrechnung

A.) Differentialquotient

y = f(x) Funktion. Es sei |h| eine kleine Anderung von x.

Wie verhalt sich f(x+ h) ?

praktische Bezeichnung: h = ∆x (“Inkrement”. Dies ist kein Produkt, sondern Symbol

fur “kleine” Anderungen.)

Definition: Differenzenquotient

∆y

∆x:=

f(x+ ∆x) − f(x)

∆x= tanσ

x

y

dy

Sehne durch (x,f(x)) und

(’’Sekante’’)

x+

∆y

(x+ , f(x+ ))

Tangente in (x,f(x))

x

σ τ

∆x

∆x x∆

Bemerkung: f(x) stetig ⇒ ∆y → 0 fur ∆x→ 0

Definition: Falls der Grenzwert lim∆x→0

∆y∆x

“existiert” (d.h. ∆y∆x

konvergiert fur ∆x → 0

gegen einen endlichen Grenzwert), nennen wir ihn Differentialquotienten, oder

Ableitung, und bezeichnen ihn mit

y′(x) oderdy

dx

geometrisch: Die Sekante strebt gegen die Tangente mit Steigung

y′(x) = tan τ .

Beispiele:

1.)

y = f(x) = a+ bx+ cx2 ⇒

∆y = a+ b(x+ ∆x) + c(x+ ∆x)2 − a− bx− cx2

= b∆x+ c∆x2 + 2c∆x · x ⇒

∆y

∆x= b+ 2cx+ c∆x ⇒ lim

∆x→0

∆y

∆x= b+ 2cx

63


2.) y = sinx∆y = sin(x+ ∆x) − sinx = 2 sin ∆x

2cos(x+ ∆x

2)

⇒ ∆y∆x

=sin ∆x

2∆x2

· cos(x+ ∆x2 ) −→ cosx fur ∆x→ 0,

da limξ→0

sin ξξ

= 1.

B.) Differenzierbare Funktionen

Falls lim∆x→0

f(x+∆x)−f(x)∆x

existiert (d.h. Konvergenz fur ∆x → 0), nennen wir f in x

differenzierbar.

Folgerung: lim∆x→0

f(x+ ∆x) = f(x), d.h. f ist stetig.

Also ist Differenzierbarkeit eine starkere Forderung:

f differenzierbar in x⇒ f stetig in x

Gilt die Umkehrung? Nein!

1. Beispiel: y =√x an x = 0:

Differenzenquotient:

√0 + ∆x−

√0

∆x=

√∆x

∆x=

1√

∆x−→ ∞ fur ∆x→ 0+

also in x = 0 nicht differenzierbar (Bezeichnung 0+: siehe unten).

fur x > 0:

√x+ ∆x−

√x

∆x=

∆x

∆x(√x+ ∆x+

√x)

−→1

2√x

fur ∆x→ 0

d.h. differenzierbar in x > 0.

2. Beispiel: f(x) = |x| an x = 0:

⇒ Differenzenquotient

|0 + ∆x| − |0|

∆x=

|∆x|

∆x=

{

+1 fur ∆x→ 0+

−1 fur ∆x→ 0−

Hinter dem ∆x → 0 konnen wir uns eine beliebige Folge xν → 0 vorstellen. Da also

nicht fur alle Folgen xν → 0 ein einheitlicher Grenzwert existiert, ist |x| in x = 0 nicht

differenzierbar.

Aber: Man kann einseitige Grenzwerte definieren, wenn man in der Definition zu Beginn

von Abschnitt 3.7C das “jede Folge xν → x0” einschrankt durch xν < x0 oder xν > x0.

Schreibweise:

limx→x

−

0

(. . .) bzw. limx→x

+0

(. . .)

Bei Beispiel 2 gibt es sowohl einen linksseitigen wie einen rechtsseitigen Grenzwert.

64


Bemerkung: Es gibt sogar stetige Funktionen, die nirgends differenzierbar sind (z.B.

Aktienkurse).

Die meisten praktisch auftretenden Funktionen sind stuckweise differenzierbar. D.h. f(x)ist differenzierbar bis auf endlich viele Ausnahmepunkte x1, x2, x3, . . . , xn.

(Illustration an Figur)

Allgemein gilt: f(x) nicht stetig an x0 ⇒ f(x) nicht differenzierbar an x0.

C.) Hohere Ableitung (fur Funktionen y(x))

y′(x) ist wiederum Funktion, v(x) := y′(x)

v(x) existiert fur diejenigen x, fur die y(x) differenzierbar ist.

Auch fur v(x) = y′(x) konnen der Differenzen- und der Differentialquotient betrachtet

werden. Existiert letzterer, so nennen wir v′(x) = dvdx

=dy′(x)

dxdie 2. Ableitung von y(x).

Schreibweisen: y′′(x) , d2ydx2

(Diese “2” bedeutet keine Quadratur! d2

dx2 ist Symbol fur die 2. Ableitung nach x.)

Definition: y(x) heißt glatt (oder stetig differenzierbar), wenn y(x) differenzierbar ist

und y′(x) stetig ist.

(Dann hat y(x) keinen “Knick”; die Tangente an die Kurve variiert stetig.)

[Hinweis fur Spezialisten: Es gibt Funktionen, welche in x differenzierbar sind, aber y′(x)ist nicht stetig. (z.B. y(x) = x2 sin 1

xfur x 6= 0, y(0) := 0)]

Auch y′′(x) ist Funktion, deren Ableitung analog definiert werden kann −→

y′′′(x) (3. Ableitung).

u.s.w. n-te Ableitung

Bezeichnung y(n) = dnydxn := d

dxy(n−1) (“rekursiv” definiert).

praktische

Definition: Eine Funktion f(x) heißt Ck-Funktion auf [a, b], wenn f(x) auf [a, b] k-mal

“stetig differenzierbar” ist. D.h. die Ableitungen f ′, . . . , f (k) existieren und f (k)

ist stetig fur a ≤ x ≤ b.

d.h. y(x) Ck-Funktion ⇔ y(x), y′(x), . . . , y(k)(x) stetig.

C0 bezeichnet die Menge aller stetigen Funktionen.

f ∈ C0 heißt : f ist stetig.

f ∈ C2 heißt : f, f ′ und f ′′ existieren und sind stetig.

f(x) ist “glatt”, wenn f wenigstens C1 ist.

D.) Ableitungsregeln

elementare Regeln:

y(x) = cu(x) mit c konstant ⇒ y′ = cu′

y(x) = u(x) ± v(x) ⇒ y′ = u′ ± v′

y(x) = u(x)v(x) ⇒ y′ = u′v + uv′

65


y =u(x)

v(x)⇒ y′ =

u′v − uv′

v2

y = y(x), Umkehrfunktion x = x(y) ⇒ dxdy

= 1dy

dx

= 1y′

falls y′ 6= 0 (d.h. monoton!)

Kettenregel: Hintereinanderausfuhrung von Funktionen

y = y(x), x = x(t), y(x(t)) ⇒dy

dt=dy

dx

dx

dt

Beispiel: h(x) = (x4 + 6x+ 5)3 Anwenden der Kettenregel:

Definition: f(x) = x4 + 6x+ 5 und g(x) = x3 ⇒ h(x) = (f(x))3 = g(f(x))

h′(x) =dg(f(x))

df·df(x)

dx= 3(f(x))2(4x3 + 6)

= 3(4x3 + 6)(x4 + 6x+ 5)2

(“Nachdifferenzieren”. Hinweis zu dem Beispiel: Ergebnis kann man sofort hinschreiben.)

Beispiel: f(x) = sin(ax+ b)

f ′(x) = cos(ax+ b) · a = a cos(ax+ b) (a vom Nachdifferenzieren)

E.) Mittelwertsatz

y(x)

ξx

ba

��

Mittelwertsatz der Differentialrechnung (fur eine Funktion):

Falls y(x) stetig in a ≤ x ≤ b und differenzierbar in a < x < b ist, dann gibt es

(mindestens) ein ξ in a < ξ < b, so dass y′(ξ) =y(b)−y(a)

b−a.

Folgerung fur Fehlerrechnung

y = f(x) , x : Eingangsgroße, y : Ausgangsgroße.

Es sei ∆x Fehler in x, was ist ∆y? Mit Mittelwertsatz, falls Voraussetzung erfullt ist:

∆y = f ′(ξ)∆x⇒ |∆y| ≤M |∆x|, wobei M Schranke fur f ′(x) im jeweiligen x-Bereich ist.

Folgerungen bzgl. Monotonie

Es sei y′(x) > 0 in a ≤ x ≤ b und x1 < x2 beliebig im Intervall.

Mittelwertsatz ⇒ ∃ ξ mit x1 < ξ < x2, so dassy(x2)−y(x1)

x2−x1= y′(ξ) > 0 ⇒ y(x2) > y(x1)

Also gilt der Satz: (Die Voraussetzungen des Mittelwertsatzes seien erfullt.) y′(x) > 0 ⇒ ystreng monoton wachsend (jeweils auf dem ganzen Intervall)

analog: y′(x) < 0 ⇒ y monoton fallend.

66


(mit jeweiliger Intervall-Angabe)

abgeschwacht:y′(x) ≥ 0 ⇔ monoton wachsend

y′(x) = 0 ⇔ y ist konstant

F.) Regeln nach l’Hospital

Fur Ausdrucke in unbestimmter Form

Beispiel: limx→0

sin xx

ist von der Form “ 00”

Schreibe f(x) fur den Zahler und g(x) fur den Nenner.

Es gelte entweder

Voraussetzung (1): limx→a

f(x) = limx→a

g(x) = 0 (d.h. von der Form “ 00”)

Voraussetzung (2): limx→a

f(x) = limx→a

g(x) = ∞ (d.h. Form “∞

∞”)

Bei jeder der beiden Voraussetzungen gilt die Aussage

limx→a

f(x)

g(x)= lim

x→a

f ′(x)

g′(x)

(sofern der rechte Grenzwert existiert).

Beispiel: limx→0

sin xx

Ho= lim

x→0

cos x1

= 1 (Typ 00)

Ausdrucke der Form “0 · ∞” und “∞−∞” lassen sich in obige Ausdrucke umformen!

Beispiel:

limx→0

(x cot x) = limx→0

xtan x

Ho= lim

x→0

11

cos2 x

= 1

(Typ “0 · ∞”) (Typ 00)

G.) Maxima und Minima

Gegeben: Funktion y = f(x) auf einem Intervall I : a ≤ x ≤ b.

Definition: f(x0) ist ein Maximum von f(x), wenn es eine Umgebung U um x0 gibt,

so dass fur alle x 6= x0 in I und in U gilt: f(x) < f(x0).

Analog: Minimum. (Beide heißen Extremum)

b

yMax

MaxMin

MinMin

Max

xa

Satz: Es sei x0 im Inneren eines Teil-Intervalls, auf dem f(x) differenzierbar ist, und

f(x0) ein Extremum. Dann gilt f ′(x0) = 0.

67


Bemerkung: Der Satz sagt nichts uber Extrema an Intervallenden und Stellen, an

welchen f(x) nicht glatt ist.

Folgerung: Kandidaten fur Extrema in I sind

1.) die Randpunkte des Intervalls,

2.) die Punkte x, an denen f nicht glatt ist,

3.) die Stellen x mit f ′(x) = 0.

Test, ob Maximum oder Minimum:

Es sei x in einer (kleinen) Umgebung von x0.

1. Kriterium: Gilt f ′(x) > 0 fur x < x0 und f ′(x) < 0 fur x > 0, dann ist f(x0) ein

lokales Maximum.

f ’ > 0 f ’ < 0

y

0x

Umgebung

x

Gilt f ′(x) < 0 fur x < x0 und f ′(x) > 0 fur x > x0, dann ist f(x0) ein lokales Minimum.

(Dieses Kriterium kann an Randextrema angepasst werden.)

2. Kriterium: Es sei x0 im Inneren und f ′(x0) = 0. Fur f ∈ C2 gilt:

f ′′(x0) < 0 ⇒ f(x0) lokales Maximum

f ′′(x0) > 0 ⇒ f(x0) lokales Minimum

Zur Kurvendiskussion (vgl. Abschnitt 3.6F) hinzufugen:

Stetigkeit und Differenzierbarkeit prufen, eventuell Monotonie-Bereiche feststellen.

68


3.9 Integrale

A.) Bestimmtes Integral; Flacheninhalt

Es sei f(x) stetig auf a ≤ x ≤ b.

xa x xξ1 21

b . . .

f(x)

y

Fur f > 0 betrachten wir den Flacheninhalt, der durch

y = 0, x = a, x = b, y = f(x) (∗)

begrenzt wird.

Naherung durch Flache von Rechtecken:

Einteilung des Intervalles [a, b] in n Teilintervalle durch Zwischenpunkte

a := x0 < x1 < x2 < . . . < xn−1 < xn := b

Dies definiert parallele Streifen der Breiten

xi − xi−1

Das i-te Rechteck habe die Lange f(ξi) fur ein ξi in xi−1 ≤ x ≤ xi.

⇒ Gesamtflache der Rechtecke:

Sn :=

n∑

i=1

f(ξi)(xi − xi−1)

Fur n = 1, 2, 3, . . . ist Sn eine Folge von Zahlen. Was ist, wenn n → ∞ und gleichzeitigxi − xi−1 → 0?

(z.B. xi = a+ i b−an

)

Satz: Fur alle stetigen f(x) (auch negativ) hat die Folge Sn einen Grenzwert, egal wie

die Teilintervalle und die ξi darin gewahlt werden.

Definiton:∫ b

af(x)dx := lim

n→∞

n∑

i=1f(ξi)(xi − xi−1) (heißt auch “Riemann-Integral”)

Der Beweis des Satzes verwendet

mi := Min von f auf xi−1 ≤ x ≤ xi

Mi := Max von f auf xi−1 ≤ x ≤ xi

und

“Obersumme” Sn :=n∑

i=1Mi(xi − xi−1)

“Untersumme” Sn :=n∑

i=1

mi(xi − xi−1)

Klar ist Sn ≤ Sn ≤ Sn. Es folgen Konvergenz-Betrachtungen fur n → ∞, die hier

nicht durchgefuhrt werden.

69


Bemerkung:

1.)∫ b

af(x)dx heißt bestimmtes Integral, a und b heißen Integrationsgrenzen, f(x) heißt

Integrand.

2.) Die “Integrationsvariable” ist intern und kann beliebig bezeichnet werden:

b∫

a

f(x)dx =

b∫

a

f(α)dα = . . .

3.) Das obige bestimmte Integral ist eine Zahl, keine Funktion.

4.)∫ b

af(x)dx ist nur dann der (positive) Flacheninhalt des Bereiches (*), wenn f(x) ≥ 0

fur a ≤ x ≤ b. Falls f(x) ≤ 0 fur alle a ≤ x ≤ b ware der Flacheninhalt −∫ b

af(x)dx.

Bei verschiedenen Vorzeichen von f : Nullstellen aufsuchen und Teilintegrale berech-

nen!

ba

+

y

−

α β

f(x)

x

+

Gesamtflache =∫ α

af(x)dx−

∫ β

αf(x)dx+

∫ b

βf(x)dx

5.) Aus der Definition des Integrals folgen diverse einfache Regeln, wie

b∫

a

1 dx = b− a , usw. (s.u.)

B.) Mittelwertsatz der Integralrechnung

Es seien f und g stetig und g(x) ≥ 0 auf a ≤ x ≤ b. Dann ∃ ein ξ mit a ≤ ξ ≤ b, so dass

b∫

a

f(x)g(x)dx = f(ξ)

b∫

a

g(x)dx

Speziell fur g = 1:b∫

a

f(x)dx = f(ξ)(b− a)

Integrations-Regelnb∫

a

dx = b− a

f(x) ≤ g(x) fur a ≤ x ≤ b ⇒

b∫

a

f(x)dx ≤

b∫

a

g(x)dx (∗)

70


(Spezialfalle f = 0 oder g = 0!)

α konstant ⇒

b∫

a

αy(x)dx = α

b∫

a

y(x)dx

b∫

a

(f(x) ± g(x))dx =

b∫

a

f(x)dx±

b∫

a

g(x)dx

(“Linearitat des Integrations-Operators”)

b∫

a

y(x)dx+

c∫

b

y(x)dx =

c∫

a

y(x)dx fur a ≤ b ≤ c

b∫

a

y(x)dx = −

a∫

b

y(x)dx

m ≤ f(x) ≤M ⇒(∗)

m(b− a) ≤

b∫

a

f(x)dx ≤M(b− a)

(rechtes “≤”: wegen g := M undb∫

a

dx = b− a)

∣∣∣∣∣∣

b∫

a

f(x)dx

∣∣∣∣∣∣

≤

b∫

a

|f(x)|dx (fur a ≤ b)

(folgt mit −|f(x)| ≤ f(x) ≤ |f(x)| aus (∗))

C.) Unbestimmtes Integral und Differentiation

jetzt: Integration als “Umkehrung” der Differentiation. In

b∫

a

f(t)dt

fasse b als variabel auf: F (b) :=b∫

a

f(t)dt.

schreibe b→ x, d.h.

F (x) :=

x∫

a

f(t)dt

mit Mittelwertsatz:

F (x+ ∆x) − F (x) =

x+∆x∫

a

f(t)dt−

x∫

a

f(t)dt =

=

x+∆x∫

x

f(t)dt = f(ξ)

x+∆x∫

x

dt = f(ξ)∆x

⇒F (x+ ∆x) − F (x)

∆x= f(ξ) mit x ≤ ξ ≤ x+ ∆x

71


Das ist der

Hauptsatz der Differential- und Integralrechnung: Die Integralfunktion F (x) einer

stetigen Funktion f(x) ist differenzierbar, und es gilt

dF (x)

dx=

d

dx

x∫

a

f(t)dt

= f(x)

undb∫

a

f(x)dx = F (b) − F (a) .

(zum 2.Teil der Aussage:)

Ubergang zu einer anderen Konstanten a statt a andert F (x) nur um einen konstanten

Wert.

Man schreibt deshalb auch

∫

f(x)dx = F (x) + const.

Bezeichnung:∫f(x)dx heißt unbestimmtes Integral und ist eine Funktion! Jede

Funktion F (x) mitdF (x)

dx= f(x) heißt Stammfunktion von f(x).

D.) Uneigentliche Integrale

Beispiel:∞∫

a

f(x)dx := limb→∞

b∫

a

f(x)dx

Integrale mit unendlichen Integrationsintervallen oder Unendlichkeitsstellen der Integranden

heißen uneigentlich.

Hinweis: Integrations-Methoden wie partielle Integration oder Substitution: Schulstoff

bzw. Literatur.

72


3.10 Logarithmus und Exponentialfunktionen

A.) Der naturliche Logarithmus

Integriere 1x

: Die Stammfunktion ist:

Definition: lnx :=x∫

1

1tdt fur x > 0 heißt “naturlicher Logarithmus”.

Folgerungen:

1.) Definition ⇒ Ableitung ddx

(lnx) = 1x

fur x > 0.

2.) lnx ist nur fur x > 0 definiert.

im Folgenden seien x, x1, x2 > 0

3.)

ln(x1 · x2) =

x1x2∫

1

dt

t=

x1∫

1

dt

t+

x1x2∫

x1

du

u(Substitution: u = x1t,

du

u=x1dt

x1t)

= lnx1 + lnx2

4.)

ln

(1

x

)

=

1/x∫

1

dt

t(Substitution u =

1

t) =

x∫

1

u

(

−1

u2

)

du = −

x∫

1

dt

t= − lnx

5.) ln(xq) = q lnx fur x > 0 und rationales q (folgt aus 3.), 4.)) (gilt auch fur q ∈ IR)

B.) Exponentialfunktionen

lnx streng monoton ⇒ Umkehrfunktion existiert, nenne sie exp(x)

(sehr grobe Skizze)

exp (x)

ln x

y

x1

1

x = ln y ⇔ y = exp(x)

Besondere Zahl: e := exp(1) = 2.71828...

In Abschnitt 3.6D: xq mit q = mn

rational.

Setze speziell x = e.

Was ist eq? Aus den ln-Eigenschaften folgt

ln eq = q ln e = q

73


Umkehrfunktion exp anwenden ergibt:

exp(q) ≡ eq (Synonyme)

Als Umkehrung von lnx ist ex jetzt auch fur nichtrationale x definiert.

Eigenschaften

1.) e0 = 1; negative x-Achse ist waagerechte Asymptote;

ex ≥ 1 + x ; ex > 0

2.) Ableitung: x = ln y ⇒ dxdy

= 1y

= 1ex , also

dy

dx=

d

dxex = ex

Die Exponentialfunktion ist die einzige Funktion mit der Eigenschaft y′ = y.3.) ex+y = exey ; e−x = 1

ex

4.) e−x ist exponentiell abfallender Prozeß.

5.) Wegen 3.) (ean∆t = ea(n−1)∆t · ea∆t) gilt fur exponentielles Wachstum/Abnahme:

Der Wert nach gleichen Zeitabstanden ergibt sich durch Multiplikation mit immer

dem gleichen problemabhangigen Faktor.

Halbwertszeit: dasjenige ∆t, fur das ea∆t = 12 .

C.) Allgemeine Exponentialfunktionen und Logarithmen

Analog wie ex auch ax mit a > 0.

ln(ax) = x lna ⇒ exp(lnax) = ax = ex ln a

D.h. ax wird (zum Ausrechnen) auf exp und ln zuruckgefuhrt. Mit y := ax ist ln y = x ln a.Es folgt

x =ln y

ln aUmkehrfunktion fur 0 < a < 1 und 1 < a

Definition/Bezeichnung: a log x, oder

loga x :=lnx

lna

heißt “Logarithmus zur Basis a” fur x > 0, a > 0, a 6= 1

Speziell a = e: e log x = lnxa = 10: 10 log x =Briggscher Logarithmus

immer gilt: a log a = 1 , a log 1 = 0,

Rechenregeln wie beim naturlichen Logarithmus.

3.11 Reihen und Potenzreihen

Motivation: sinx = x− x3

3! + x5

5! −x7

7! ± . . .

A.) Konvergenzkriterien

Zur Erinnerung: sn =n∑

ν=1aν Partialsummen

74


Definition:∞∑

ν=1aν := lim

n→∞

sn heißt Reihe.

Beispiel: geometrische Reihe 1 + x+ x2 + . . . =∞∑

ν=0xν = 1

1−xfur |x| < 1.

Die geometrische Reihe divergiert fur |x| ≥ 1!

Definition: alternierende Reihe: aν sind abwechselnd positiv und negativ.

Beispiel: geometrische Reihe fur x = −12 :

1 −1

2+

1

4−

1

8± . . . =

1

1 + 12

=2

3

Definition: Reihe heißt absolut konvergent, wenn∞∑

ν=1|aν | konvergiert.

Folgerungen aus Cauchys Konvergenzkriterium (Abschnitt 3.7B):

1.) Reihe konvergiert absolut ⇒ Reihe konvergiert.

zum Beweis: |an+1 + . . .+ an+m| ≤ |an+1| + . . .+ |an+m|

2.) Reihe konvergiert ⇒ aν → 0 fur ν → ∞

Warnung: Umkehrung gilt nicht! z.B. divergiert 1+ 12 + 1

3 + 14 + 1

5 +. . . (“harmonische

Reihe”).

3.) Reihe sei alternierend und es gelte fur ein N und ∀ν ≥ N die Ungleichung |aν | >|aν+1|. Dann gilt:

Reihe konvergiert ⇔ aν → 0 fur ν → ∞

Beweis: sn bilden Intervall-Schachtelung.

n+1sn+3sn+2sns s

an+1

an+2

B.) Rechenregeln

Die Reihen∞∑

ν

aν und∞∑

ν

bν seien konvergent. Dann gilt:

∞∑

ν

aν ±

∞∑

ν

bν =

∞∑

ν

(aν ± bν)

α∞∑

ν

aν =

∞∑

ν

αaν

Warnung: Klammern setzen oder fortlassen oder Umordnen ist i.A. nicht erlaubt!!

Beispiel:∞∑

ν=1(−1)ν+1 1

ν= ln 2 (→ spater: vergleiche Taylorentwicklungen)

75


Umordnen: 1 + 13 − 1

2 + 15 + 1

7 − 14 + 1

9 + 111 + 1

13 − 16 + . . . = 3

2 ln 2

C.) Konvergenzbedingungen durch Reihenvergleich

Eine Reihe∞∑

ν

bν heißt Majorante von∞∑

ν

aν , wenn 0 ≤ |ak| ≤ bk fur k ≥ N . Dann gilt:

Majoranten-Kriterium:

(1)∞∑

ν

bν konvergent ⇒∞∑

ν

aν konvergiert absolut

(2)∞∑

ν

|aν | = ∞ ⇒∞∑

ν

bν = ∞

Anwendung: Vergleich mit bekannter Reihe.

Folgerung ist

Quotienten-Kriterium: Falls |aν+1

aν| ≤ q < 1 ist ∀ ν > N , dann konvergiert Reihe

absolut.

Wurzelkriterium: Falls ν√

|aν | ≤ q < 1 ∀ ν > N , dann absolute Konvergenz.

Bemerkungen:

1.) Jede endliche Teilsumme a0 + a1 + . . . + aN spielt fur Konvergenz oder Divergenz

keine Rolle.

2.) Insbesondere liegt Konvergenz vor, falls:

limν→∞

∣∣∣∣

aν+1

aν

∣∣∣∣= q < 1

bzw. limν→∞

ν√

|aν | = q < 1

3.) Falls lim |aν+1

aν| > 1, dann Divergenz.

Beispiel:∞∑

ν=0

xν

ν! = 1 + x+ x2

2! + x2

3! + . . .

Quotientenkriterium:aν+1

aν=

xν+1

(ν+1)!xν

ν!

= xν+1

−→ 0 fur ν → ∞ ⇒ konvergiert fur

alle x

Beispiel:∞∑

ν=1

1ν:

Quotientenkriterium:aν+1

aν= ν

ν+1 −→ 1, Kriterium nicht anwendbar da q = 1,

d.h. |aν+1

aν| < 1 genugt nicht fur Konvergenz.

D.) Potenzreihen

Falls bei einer Reihe∞∑

ν=0bν die Koeffizienten Funktionen bν = fν(x) sind, dann heißt die

Reihe Funktionenreihe.

Wichtigstes Beispiel:

fν(x) = aνxν

76


Eine solche Reihe∞∑

ν=0

aνxν = a0 + a1x+ a2x

2 + . . .

heißt Potenzreihe.

Alle ihre Teilsummen sind Polynome.

Konvergenz:

bν+1

bν=aν+1x

ν+1

aνxν= x

aν+1

aν

hinreichend: limν→∞

|x| |aν+1

aν

| < 1

aquivalent: |x| limν

|aν+1

aν

| < 1

D.h. fur alle x mit |x| < limν→∞

| aν

aν+1| konvergiert Potenzreihe absolut.

Definition: ρ := limν→∞

| aν

aν+1| heißt Konvergenzradius der Potenzreihe (falls aν 6= 0).

Zusammen:

|x| < ρ ⇒ absolute Konvergenz

|x| > ρ ⇒ Divergenz

Der Konvergenzradius ρ kann auch 0 oder ∞ sein;

Fall ρ = 0 : Konvergenz nur fur x = 0

Fall ρ = ∞ : Konvergenz fur alle x

Fur |x| = ρ 6= 0 Divergenz oder Konvergenz moglich; dann gibt es keine allgemeine Aus-

sage.

allgemeine Potenzreihe:∑

∞

ν aν(x− α)ν

Konvergenzbereich |x− α| < ρ (Inneres eines Kreises um x = α mit Radius ρ)

E.) Die Taylor-Formel

Approximation von Funktionen durch Polynome

(Approximation = Naherung)

gegeben: Funktion f(x) auf Intervall.

gesucht: Polynom a0 +a1x+a2x2 + . . .+anx

n =: Pn(x) mit Koeffizienten ai derart, dass

auf dem Intervall gilt f(x) ≈ Pn(x).

Ziel: Das Polynom soll fur x = α mit f in allen Ableitungen bis zur n-ten Ordnung

ubereinstimmen. D.h.

di

dxiPn(α) =

di

dxif(α) fur i = 0, 1, . . . , n (∗)

77


x

y

α

f(x)

P (x)n

Losung: Taylor-Polynom:

Pn(x) =

n∑

k=0

f (k)(α)

k!(x− α)k

= f(α) +f ′(α)

1!(x− α) +

f ′′(α)

2!(x− α)2 + . . .+

f (n)(α)

n!(x− α)n

Probe: (∗) stimmt. (0! := 1)

Fehler beim Taylor-Polynom

Frage: Wie groß ist der Fehler f(x) − Pn(x)?

Bezeichnung: Rn(x, α) := f(x) − Pn(x) heißt Restglied.

Es gilt fur (n+ 1)-mal stetig differenzierbare Funktionen f :

Rn(x, α) =f (n+1)(ξ)

(n+ 1)!(x− α)n+1

fur ξ zwischen x und α

Folgerung: Der Fehler f(x) − Pn(x) ist umso kleiner, je naher x an α liegt.

Beispiel:

f(x) = ex , α = 0 . ⇒ f (i)(α) = 1 ∀ i und:

ex = 1 + x+x2

2!+x3

3!+ . . .+

xn

n!+

eξ

(n+ 1)!xn+1

F.) Taylor-Entwicklung

Annahme: f(x) fur x = α beliebig oft stetig differenzierbar. ⇒ Taylor-Formel fur

beliebige n gultig.

Es gilt:Restglied Rn(x, α) −→ 0 fur n→ ∞ und |x− α| < ρ

m

∞∑

k=0

f (k)(α)

k!(x− α)k konvergiert gegen f(x) fur |x− α| < ρ

78


Definition: Die Potenzreihe∞∑

k=0

f (k)(α)

k!(x− α)k

heißt Taylorreihe von f(x) mit Entwicklungspunkt x = α.

Man sagt, f(x) laßt sich um (den Entwicklungspunkt) α in eine Taylorreihe entwickeln.

oder: f(x) wird in Potenzreihe entwickelt. Wird kein Entwicklungspunkt α angegeben,

so ist meist α = 0 gemeint:∞∑

k=0

f (k)(0)k!

xk.

Beispiel: f(x) = sinx in Potenzreihe, α = 0

f ′(x) = cosx f ′(0) = 1

f ′′(x) = − sinx f ′′(0) = 0

f ′′′(x) = − cos x f ′′′(0) = −1

f (4)(x) = sinx f (4)(0) = 0

(danach periodisch)

allgemein fur f(x) = sinx : f (2k)(0) = 0 ; f (2k+1)(0) = (−1)k

|Rn| ≤1

(n+ 1)!xn+1 −→ 0 fur n→ ∞ fur beliebige x

Zusammen:

sinx =x

1!−x3

3!+x5

5!± . . . fur alle x

3.12 Funktionen von mehreren Veranderlichen

f(x1, x2, . . . , xn) ist eine reellwertige Funktion von n Veranderlichen x1, x2, . . . , xn. Der

Definitionsbereich ist der IRn oder ein Teil vom IRn.

Beispiel: f(x1, x2) kann gedeutet werden als Hohe uber der (x1, x2)-Ebene. (Illustration:

Hohenlinien f(x1, x2) = c)

Schreibweise x fur (x1, . . . , xn)

Partielle Ableitung erster Ordnung

∂f(x)

∂xk

=∂f(x1, . . . , xk−1, xk, xk+1, . . . , xn)

∂xk

entspricht der gewohnlichen ersten Ableitung von

g(t) := f(x1, . . . , xk−1, t, xk+1, . . . , xn) ,

wobei beim Differenzieren nach xk die anderen Veranderlichen x1, . . . , xk−1, xk+1, . . . , xn

als konstant angesehen werden.

79


Beispiel:

f(x1, x2) = x1x22

=⇒∂f

∂x1= x2

2 ,∂f

∂x2= x12x2

Definition: Der Vektor aller 1. partiellen Ableitungen heißt Gradient:

gradf(x) :=

(∂f(x)

∂x1, . . . ,

∂f(x)

∂xn

)

(als Spaltenvektor)

Maximum oder Minimum von f :

Notwendig fur Extremum im Inneren des Definitionsbereiches von f ist

gradf(x) = 0 .

Diese Vektorgleichung ist ein System von n Gleichungen.

(Analogie zu f ′(x) = 0 in Abschnitt 3.8G)

Analog zum eindimensionalen Fall gibt es Taylorentwicklungen.

Beispiel: Kondition (zu Abschnitt 1.5 G)

∆f.=∂f(x)

∂x1∆x1 + . . .+

∂f(x)

∂xn

∆xn

= (gradf(x))tr∆x

wobei ∆x der Vektor mit den Komponenten ∆x1, . . . ,∆xn ist.

Partielle Ableitungen hoherer Ordnung: analog!

Bezeichnungen z.B.

∂2f(x1, x2)

∂x21

fur die zweite partielle Ableitung nach x1

Anwendung: Abschnitt 6.2

80

Seydel: Mathematik II, Kap. 4, SoSe 2009

Kapitel 4 Approximation mit Kurven

4.1 Approximation und Interpolation

Problem 1: gegeben: Punkte / Zahlenpaare (xi, yi), i = 0, 1, . . . , n (z.B. aus Messungen

oder Berechnungen)

0x

0y

x

Φ

y

Frage: Welche Funktion Φ(x) passt sich “am besten” den Punkten an?

Problem 2: gegeben: Funktion f(x), die nicht elementar auswertbar ist (z.B. sinx)

ε

x

Φf(x)−

εf(x)

f(x)+

y

Aufgabe: Finde (einfachere) Ersatzfunktion Φ, so dass Φ(x) ≈ f(x), d.h. |Φ− f | < ǫ fur

eine vorgegebene Fehlerschranke ǫ

Problem 3: gegeben: Punkte (xi, yi). Aufgabe: Φ soll die Punkte interpolieren, d.h.

Φ(xi) = yi fur alle i.

x

y

Problem 4: gegeben: Integrationsproblem (“Quadratur”)

∫ b

a

f(x)dx

81


Gesucht: Φ(x), so dass

1.)∫ b

aΦ(x) dx ≈

∫ b

af(x) dx (Genauigkeit)

2.)∫ b

aΦ(x) dx einfach auszuwerten (Effizienz)

Problem 5: Φ soll Losungsfunktionen von Differentialgleichungen approximieren −→

Literatur

Das Resultat einer Approximation hangt entscheidend von dem Typ von Funktion Φ(x)

ab, den wir zulassen werden (“Funktionenklasse”).

Beispiele fur Funktionenklassen:

1.) Polynome Φ(x) = pn(x) = a0 + a1x + . . . + anxn mit Koeffizienten a0, . . . , an

(Beispiele: Taylor-Polynome)

2.) StreckenzugΦ

x

(d.h. intervallweise Polynome 1. Grades)

3.) trigonometrische Funktionen

Φ(x) = a0 +

n∑

k=1

(ak cos kx + bk sin kx)

(Beispiel: Fourier-Reihen)

4.2 Interpolation mit Polynomen

zugelassene Funktionenklasse fur Φ

pn(x) = a0 + a1x + . . . + anxn

speziell n = 1 : Gerade a0 + a1xn = 2 : Parabel a0 + a1x + a2x

2

A. Lineare Interpolation

nur Geraden zugelassen: Φ = a0 + a1x

gegeben: 2 “Stutzpunkte” (x1, y1), (x2, y2).

82


y

y

x

1

2

x2

f(x)

Φ

x1

y

Losung ist

Φ(x) = y1 +y2 − y1

x2 − x1(x− x1)

=f(x1)(x2 − x) + f(x2)(x− x1)

x2 − x1

(fruher haufig angewandt, um Zwischenwerte bei Tabellen zu approximieren.)

klassische “Interpolation”: fur ein x mit x1 < x < x2

“Extrapolation”: fur ein x außerhalb

} berechne Φ(x)

als Naherung

zu f(x)

B. Lagrange-Polynome

Gegeben: n + 1 Stutzpunkte

(x0, y0), . . . , (xn, yn), xi verschieden, d.h. xi 6= xj fur i 6= j

Definition: Lagrange-Polynom:

Lk(x) :=(x− x0) · . . . · (x− xk−1) · (x− xk+1) · . . . · (x− xn)

(xk − x0) · . . . · (xk − xk−1) · (xk − xk+1) · . . . · (xk − xn)

Eigenschaften:

Lk(xk) = 1

Lk(xi) = 0 fur i 6= k

Polynom n-ten Grades

Folgerung:

Φ(x) := L0(x)y0 + L1(x)y1 + . . . + Ln(x)yn

interpoliert: Φ(xk) = yk fur k = 0, . . . , n

Beispiel: x0 = 2, x1 = 2.5, x2 = 4, yi = 1xi

83


L0(x) =(x− 2.5)(x− 4)

(2− 2.5)(2− 4)= x2 − 6.5x + 10

L1(x) = −4

3(x2 − 6x + 8)

L2(x) =1

3(x2 −

9

2x + 5)

Φ(x) =1

2L0 +

2

5L1 +

1

4L2 =

= 0.05x2 − 0.425x + 1.15

x1 2 43

L0

Φ

0

1

x1 2 43

2

4

f(x)

(x)

L1

L2

Li

C. Eigenschaften

1.) Es seien x0, x1, . . . , xn voneinander verschieden. Dann gibt es genau ein Polynom

pn vom Grad ≤ n, das interpoliert: pn(xi) = yi (Beweis: Annahme es gibt zwei...)

2.) Fehler:

Annahme: Die Punkte “liegen auf” f (d.h. f(xi) = yi ∀ i).Frage: Wie “weit” ist pn von f entfernt?

f(x)− pn(x) =f (n+1)(ξ)

(n + 1)!(x− x0)(x− x1) · . . . · (x− xn)

hierbei ist ξ im Intervall, welches x, x0, . . . , xn umfasst. Formel brauchbar, wenn

f (n+1) wenigstens in der Großenordnung bekannt ist oder abschatzbar: |f (n+1)(ξ)| ≤C. (Beispiel f(x) = sin x −→ C = 1).

3.) gute Eigenschaften: einfache Theorie und Konstruktion

sehr schlechte Eigenschaften:

4.) Außerhalb von x0, . . . , xn steigt Fehler stark an ⇒ Extrapolation ist i.a. nicht

sinnvoll.

5.) n groß: schlecht konditioniert (pn(x) hangt empfindlich von Werten yi ab.)

6.) n groß und (beliebig) vorgegebene (z.B. aquidistante) xi: starke Oszillationen zum

Rand des Intervalls

84


n

x

f(x)

p (x)

(Abhilfe moglich, wenn xi “optimal” gelegt werden konnen, d.h. zunehmend dichter

zu den “Randern” x0 und xn. → Chebyshev-nodes, Cebysev-Polynom)

Empfehlung:

Benutze Polynom-Interpolation nur bei kleinem Grad! (sagen wir n < 6), d.h.

bei wenig Stutzpunkten.

D. Rekursionsformel von Neville

zur Auswertung eines Interpolations-Polynoms pn(x) fur einen vorgegebenen Wert von

x.

Ziel/Idee: Konstruiere Polynom hoheren Grades billig aus Polynomen niederen Grades.

Es sei Qi,j(x) das Polynom j-ten Grades (fur i ≥ j), welches die Stutzpunkte (xi−j , yi−j),. . .,(xi, yi)

interpoliert.

Dann gilt die Rekursion

Qi,0 := yi (Startwerte), i = 0, 1, 2, . . .

Qi,j(x) := Qi,j−1 +Qi,j−1 −Qi−1,j−1

x−xi−j

x−xi− 1

fur 1 ≤ j ≤ i, und i = 1, 2, . . .

Schema/Anordnung im Tableau:

x

x

x

x

0

1

2

3

y = Q

y = Q

33

y = Q

y = Q

0

2

3

00

Q

Q

Q Q

Q

Q

u . s . w .

11101

20

30 31

21 22

32

Beispiel: (xi, yi) = (0, 1), (1, 3), (3, 2). Wert des Interpolations-Polynomes fur x = 2?

85


i xi

yi

0

-3

0 1 = Q

P

11 3 = Q

2 = Q32

00

10

20 2( 2 ) = 10/3

5

10/ 35/ 21

-2

(die Nenner in Kreisen)

Praxis: Fur anderes x von vorne beginnen. Nur die letzte Zeile des Tableaus speichern.

Stutzstellen brauchen nicht geordnet zu sein, Hinzunahme weiterer Stutzpunkte/Zeilen

problemlos.

E. Konstruktion der Koeffizienten

Anstatt pn(x) = a0 + a1x + . . . + anxn besser der Ansatz von Newton:

pn(x) = b0 + b1(x− x0) + b2(x− x0)(x− x1) + . . . + bn(x− x0)(x− x1) · . . . · (x− xn−1)

Vorteil gegenuber dem bisherigen Ansatz pn(x) = a0 + a1x + . . . + anxn:

Koeffizienten bi folgen mit geringerem Aufwand:

y0 = pn(x0) = b0 + 0 → b0 = y0

y1 = pn(x1) = b0 + b1(x1 − x0) + 0 → b1 =y1 − y0

x1 − x0

y2 = pn(x2) = b0 + b1(x2 − x0) + b2(x2 − x0)(x2 − x1)→ b2 =· · ·

· · ·...

jeweils nur eine Unbekannte pro Gleichung, rekursives Vorgehen!

Wegen der Eindeutigkeit der Interpolation sind beide Interpolations-Polynome iden-

tisch. (i.a. ai 6= bi !)

Rekursion und Definition fur “dividierte Differenzen”:

f [xi] := yi (Startwerte)

f [xi, xi+1, . . . , xi+k−1, xi+k] :=f [xi+1, . . . , xi+k]− f [xi, . . . , xi+k−1]

xi+k − xi

Damit gilt:

b0 = f [x0], b1 = f [x0, x1] (s.o.),

b2 = f [x0, x1, x2], . . . , bn = f [x0, x1, . . . , xn]

Tableau fur einfaches Rechnen:

86


x

x

x

y

y

y

f[x ,x ]f[x ,x ,x ]

u.s.w.

f[x ,x ]

0

1

2

0

1

2

0 1

1 2

0 1 2

d.h.: Koeffizienten bi befinden sich in der oberen Diagonale.

Anwendung der Rekursion: Die Koeffizienten des Polynoms werden benotigt, wenn

z.B. ein Interpolations-Polynom fur viele x auszuwerten ist.

Auswertung dann mit Horner-Schema:

p(x) = (((bn(x− xn−1) + bn−1)(x− xn−2) + . . . + b1)(x− x0) + b0

Beispiel: (von oben)

Φ

1

3

2

2

-1/2-5/6 2

0

1

3

(x ) = p ( x ) = 1 + 2 x - 5/6 x(x-1)

4.3 Interpolation mit Splines

Polynominterpolation von § 4.2: brauchbar nur bei geringer Anzahl von Punkten.

gesucht: Interpolation, auch wenn viele Punkte (x0, f0), . . . , (xn, fn) vorgegeben sind!

A. Definition des Splines

Idee:

S(x)

S (x)0 0

S (x)

S (x)

S (x)

1

2

3

n-1S (x)

x0

x x x x x x1 2 3 4 n-1 n

x

f

Berechne in jedem Teilintervall ein eigenes Polynom derart, dass die Polynom–Stucke an

den “Nahtstellen” xj moglichst glatt zusammenstoßen.

Wahle Polynome von jeweils 3. Grad, d.h.

87


Ansatz fur “kubischen Spline”:

Sj(x) = aj + bj(x−xj) + cj(x−xj)2 + dj(x−xj)

3

fur xj ≤ x < xj+1 und j = 0, 1, . . . , n− 1

In jedem Teilintervall benotige aj , bj, cj, dj , also insgesamt 4n Unbekannte. Der Gesamt-

Spline S(x) besteht stuckweise aus S0(x), S1(x), . . . , Sn−1(x).

Forderungen an S(x):

Anzahl der

Bedingungen

(1) interpoliert: Sj(xj) = fj, n + 1

j = 0, 1, . . . , n− 1 dazu Sn−1(xn) = fn

(2) ist stetig: (j = 1, . . . , n− 1) Sj(xj) = Sj−1(xj) n− 1

(3) 1. Ableitung ist stetig: S′

j(xj) = S′

j−1(xj) n− 1

(4) 2. Ableitung ist stetig: S′′

j (xj) = S′′

j−1(xj) n− 1

4n− 2

Brauche 4n Gleichungen; noch 2 Bedingungen frei.

Wichtige Beispiele fur zwei noch fehlende “Randbedingungen”:

(5a) freier Rand: S′′

0 (x0) = 0, S′′

n−1(xn) = 0, “naturlicher Spline” (Mechanik:

Krummung an Endpunkten = 0)

oder

(5b) eingespannter Rand: S′

0(x0) = f ′

0, S′

n−1(xn) = f ′

n fur vorgeschriebene Werte

f ′

0, f ′

n; eventuell vorher Naherungen fur f ′

0, f′

n berechnen. (Z.B. am linken

Rand: Ein “kurzes” Polynom Plinks(x) ist so zu berechnen, dass es die “linkesten”

drei oder vier Punkte interpoliert. Dann y′

0 := P ′

links(x0). Analog am rechten

Rand.)

oder

(5c) periodische Bedingungen: (Vor.: f0 = fn): S′

0(x0) = S′

n−1(xn), S′′

0 (x0) =

S′′

n−1(xn)

oder

(5d) not a knot: Stetigkeit von S′′′ an x1 und xn−1.

Die obigen 4n Bedingungen (1)–(5) definieren eindeutig die Konstanten aj, bj , cj , dj ,

und damit den kubischen Spline.

B. Berechnung des kubischen Splines

Sj(x) = aj + bj(x− xj) + cj(x− xj)2 + dj(x− xj)

3

Interpolation (1) ⇒ Sj(xj) = aj = fj , d.h. aj sind bekannt!

Bezeichnung: hj := xj − xj−1

(2) ⇒ fj = Sj(xj) = Sj−1(xj) = fj−1 + bj−1hj + cj−1h2j + dj−1h

3j (2′)

(3) ⇒ S′

j(xj) = bj = S′

j−1(xj) = bj−1 + 2cj−1hj + 3dj−1h2j (3′)

(4) ⇒ cj = cj−1 + 3dj−1hj (gekurzt mit 2) (4′)

88


Elimination der dj aus (4’) und bj fuhrt auf

hjcj−1 + 2(hj + hj+1)cj + hj+1cj+1 = 3fj+1 − fj

hj+1− 3

fj − fj−1

hj

fur j = 1, 2, . . . , n− 1

(∗)

Dies ist ein System von n− 1 linearen Gleichungen fur die n + 1 Unbekannten

cj =S′′

j (xj)

2(wird gleich wieder mit 2 multipliziert)

Die Randbedingungen konnen durch zwei zusatzliche Gleichungen definiert werden.

Abkurzungen: fur j = 1, 2, . . . , n− 1

Mj :=S′′

j (xj)

λj :=hj+1

hj + hj+1

µj :=hj

hj + hj+1= 1− λj

rj :=6

hj + hj+1·

(fj+1 − fj

hj+1−

fj − fj−1

hj

)

und fur Fall (5a) (c0 = cn = M0 := Mn := 0) zusatzlich :

λ0 :=0, r0 := 0, µn := 0, rn := 0

Damit lautet (∗) mit Randbedingungen in Matrix-Schreibweise:

2 λ0 0

µ1 2 λ1

. . .. . .

. . .

µn−1 2 λn−1

0 µn 2

M0

M1...

Mn−1

Mn

=

r0

r1...

rn−1

rn

Die Matrix ist tridiagonal, die Losung mit dem Gaußschen Verfahren ist hier extrem

billig (Aufwand O(n) statt O(n3)).

Algorithmus (naturlicher kubischer Spline):

Eingabe: (x0, f0), (x1, f1), . . . , (xn, fn)

berechne hj , λj, µj, rj

lose Gleichungssystem mit Vorwarts-/Ruckwarts-Schleife, ergibt Mj

Koeffizienten aus

aj =yj = fj

cj =Mj/2

dj =Mj+1 −Mj

6hj+1(aus (4′))

bj =fj+1 − fj

hj+1−

hj+1

6(2Mj + Mj+1) (aus (2′))

89


Hinweise:

1.) keine Matrix speichern, nur Vektoren!

2.) Fur (5a) hatte ein System der Große n − 1 ausgereicht, weil c0 = cn = 0;

in obigem großeren Rahmen lasst sich mit anderen λ0, µn, r0, rn auch (5b)

leicht realisieren.

3.) Aus der Struktur der Matrix folgt ihre Nichtsingularitat. Es folgt, dass der

Spline eindeutig definiert ist.

C. Weitere Eigenschaften

Glattheit: nach Konstruktion S ∈ C2[x0, xn], und glatt auch im folgenden Sinn: Es gilt

∫ xn

x0

(S′′(x))2dx ≤

∫ xn

x0

(f ′′(x))2dx

fur alle beliebigen anderen interpolierenden Funktionen f(x), welche 2-mal stetig dif-

ferenzierbar sind und die Randbedingung erfullen.

Folgerung: Splines haben geringe “Krummung” und oszillieren deswegen relativ wenig.

(qualitativ)Spline

Polynom

y

x

Erganzungen zur Vorlesung:

1.) Vorwarts- / Ruckwartsschleife:

∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣

δi “neue” Diagonalelemente, δ0 := 2, r0 := r0, ri “neue” rechte Seite:

fur i = 0, 1, ..., n− 1:

δi+1 = 2− λi

µi+1

δi

, ri+1 = ri+1 − ri

µi+1

δi

Mn :=rn

δn

fur k = n− 1, n− 2, ..., 0 :

Mk =1

δk

(rk − λkMk+1)

2.) eingespannter Rand:

λ0 := 1, r0 :=6

h1

(f1 − f0

h1− f ′

0

)

,

µn := 1, rn :=6

hn

(

f ′

n −fn − fn−1

hn

)

90


4.4 Bezier-Kurven

1962 Bezier (Renault); Casteljau (Citroen)

Bernstein-Polynome: fur allgemeines Intervall a ≤ x ≤ b:

Bni (x; a, b) :=

(n

i

) (b− x)n−i(x− a)i

(b− a)n

fur i = 0, 1, . . . , n ist i-tes Bernstein-Polynom vom Grad n.

(Binomialkoeffizient(

ni

)= n!

i!(n−i)!)

oder speziell fur 0 ≤ t ≤ 1:

Bni (t) := Bn

i (t; 0, 1) =(n

i

)

(1− t)n−iti

Beispiel n = 2:

B20(t) =(1− t)2

B21(t) =2(1− t)t

B22(t) =t2

Eigenschaften fur Bni (t):

(1)

n∑

i=0

Bni (t) = 1 (“Zerlegung der 1”)

(2) t = 0 ist i-fache Nullstelle (i > 0), t = 1 ist (n− i)-fache Nullstelle (i < n)

(3) Bni (t) ≥ 0 fur 0 ≤ t ≤ 1

(4) Bni (t) hat genau ein Maximum, bei t = i

n

(5) Rekursion: Bni (t) = tBn−1

i−1 (t) + (1− t)Bn−1i (t)

Vektorwertiges Polynom: Es seien a0, a1, . . . , an Vektoren im IRd (CAD: d = 2 oder

d = 3), dann ist P (t) :=∑n

i=0 aiti ein vektorwertiges Polynom (“polynomiale

Kurve”). Fur z.B. 0 ≤ t ≤ 1 beschreibt P (t) ein Kurvenstuck im IRd, dabei ist tder Parameter der Kurve.

Es seien p0, p1, . . . , pn Punkte im IRd.

Bernstein-Bezier-Kurven:

P (t) :=

n∑

i=0

piBni (t)

Die Punkte p0, p1, . . . , pn heißen Bezier-Punkte oder Kontrollpunkte. Der Streckenzug

p0 ↔ p1 ↔ . . .↔ pn heißt B-B-Polygon.

Eigenschaften der B-B-Kurven:

(a) P (0) = p0, P (1) = pn

91


(b) In den Endpunkten sind die B-B-Kurven tangential zum Polygon durch die

Kontrollpunkte. (zeige hierzu P ′(0) =Steigung der Gerade p0 → p1, analog

P ′(1)....)(c) Die Kurve liegt in der durch p0, p1, . . . , pn aufgespannten konvexen Hulle

{n∑

i=0

sipi mit si ≥ 0,n∑

i=0

si = 1

}

(folgt mit si = Bni (t) aus (3) und (1) “Zerlegung der 1”.) [konvexe Menge:

Mit je zwei Punkten ist auch ihre Geraden-Verbindung enthalten.]

(d) Die Kurve geht “relativ nahe” an den Kontrollpunkten vorbei. (folgt aus (4):

fur t = i/n ist si = Bni maximal, die anderen sk (fur k 6= i) eher klein)

Beispiel (im IR2): (Reihenfolge der Numerierung ist wichtig!)

P

P

P

P

3

2

1

0

Polygon

konvexe Hülle

Beispiel (qualitativ): (Reihenfolge der Numerierung ist wichtig!)

5

P0

1

23

4

Berechnung: erfolgt rekursiv. Hierzu werden die vektorwertigen Teilpolynome bki

definiert:

bki (t) :=

k∑

j=0

pi+jBkj (t).

Es gehen die Punkte pi, pi+1, . . . , pi+k ein. Man zeigt leicht

bki (t) = (1− t)bk−1

i + tbk−1i+1 und bn

0 (t) = P (t) .

Anordnung der bki in Tableau (Eintrage sind Vektoren). Literatur: Algorithmus

von Casteljau, startet mit b0i = pi.

P P

PP

b =

b = =

=

b

1

0

2

3

b

b

1

0

0

30

0 02

0

3b21

2b0

b

b

11

b20

11

92


Hinweis: Mit B-Splines konnen ahnliche Kurven erzeugt werden. (“B” ← Basis)

4.5 Integration mit Trapezsummen; Extrapolation

Aufgabe: Berechne∫ b

af(x)dx, wobei a, b und f gegeben, f genugend glatt auf a ≤ x ≤ b.

1. Idee: Approximiere f(x) durch interpolierendes Polynom pn(x). Dann

∫ b

a

f(x)dx ≈

∫ b

a

pn(x)dx =

∫ b

a

n∑

i=0

f(xi)Li(x)dx =

=

n∑

i=0

f(xi)

∫ b

a

Li(x)dx

︸︷︷︸

hangen nicht von f ab.

Falls xi aquidistant mit

h = xj+1 − xj = b−an

, xj := a + jh; dann =hci

(Li: Lagrange Polynome; Letzteres wird mit der Substitution x = a + ht gezeigt.)

Die “Gewichte” ci konnen in der Literatur gefunden werden, bzw. in den folgenden

Beispielen.

Zusammenfassung: Es gelten die Newton-Cotes-Formeln:

∫ b

a

f(x)dx ≈

∫ b

a

pn(x)dx = hn∑

i=0

cif(xi)

1. Beispiel: Trapezregel

n = 1, d.h. ersetze f durch Gerade p1(x)

p (x)1

b

10

xxx

a

f(x)

c0 = c1 =1

2∫ b

a

f(x)dx ≈x1 − x0

2(f(x0) + f(x1))

= Flache des Trapezes

93


2. Beispiel: “Simpsons Regel”, “Keplersche Faßregel”

n = 2, d.h. ersetze f durch Parabel p2

Definiere h := b−an

= b−a2

, x0 = a, x1 = b+a2

, x2 = b

2p (x)

x0x

a b

f(x)

2x1x

Es gilt: c0 = 13, c1 = 4

3, c2 = 1

3. Es folgt:

∫ b

a

f(x)dx ≈h

3(f(x0) + 4f(x1) + f(x2))

= Flache unter der Parabel

absoluter Fehler:

Trapezregel: h3

12f ′′(ξ) = O(h3) fur ein ξ im Intervall.

Simpson: O(h5)

Man erhalt diese Fehlerordnungen durch Integration des Fehlers f(x)− p(x) (vgl. § 4.2

C) und Anwendung des Mittelwertsatzes.

Genauigkeitssteigerung nicht durch Polynom hoherer Ordnung, sondern mit

2. Idee: stuckweiser Zugang

F

b

f(x)

xx

a

1 xn

2

0 2x x

h :=b− a

n, xi = a + ih

Flache des i-ten Trapezes: Fi = hf(a + ih) + f(a + (i + 1)h)

2fuhrt auf Trapez-Summe

T (h) := F0 + F1 + . . . + Fn−1, also:

T (h) = h

[f(a)

2+ f(a + h) + f(a + 2h) + . . . . . . + f(b− h) +

f(b)

2

]

94


Fehler:

T (h)−

∫ b

a

f(x)dx =b− a

12h2f ′′(ξ) = O(h2)

fur a < ξ < b und f zweimal stetig differenzierbar auf a ≤ x ≤ b (d.h. f ∈ C2[a, b])

d.h. eine Ordnung der Trapezregel geht durch das Aufsummieren verloren.

Hinweis: Wenn f(x) nur stuckweise glatt ist, dann aufspalten in Teilintervalle und

getrennt integrieren:

∫ b

a

=

∫ c

a

+

∫ d

c

+

∫ b

d

xa

f(x)

c d b

3. Idee: (Asymptotische) Entwicklung des Fehlers: Man kann fur genugend

glattes f beweisen:

(∗)

T (h) = τ0 + τ1h2 + τ2h

4 + ... + τmh2m + Rm+1h2m+2

wobei τ0 =∫ b

af(x)dx der exakte Wert ist,

τ1, τ2 . . . von h unabhangig

(Nachweis vgl. Literatur.)

(∗) heißt auch “quadratische” Entwicklung, da Polynom bzw. Reihe in h2; Restglied

Rm+1 ist beschrankt; enthalt obige Fehlerformel fur m = 0. Wegen (∗) verhalt sich T (h)

fur kleine h wie ein Polynom in h2.

4. Idee: Extrapolation (Richardson 1927, Romberg 1955)

Ziel: Berechnung von T (0) := limh→0 T (h), dies ist der exakte Wert des Inte-

grals. Kann aber wegen n → ∞ nicht direkt ausgewertet werden (ware

auch nicht effizient).

moglich: T (h) kann ausgewertet werden fur einige ausgewahlte h > 0, z.B. T (h0),

T (h1), T (h2), eventuell auch mehr.

Idee: Lege durch T (h0), T (h1),. . . interpolierendes Polynom T (h) und werte

T (0) aus (einfach!), und nehme T (0) als Naherung zu T (0) =∫ b

af(x)dx.

Interpolation

T(h)

h

0

(unbekannt)

exaktes T(h)

exakter Wert

Näherung

12h h h

(Da T (h) Polynom in h2 ist, ist die “Extrapolation” auf h = 0 problemlos.)

95


Algorithmus “Romberg Integration”:

(1) Lege “Schrittweitenfolge” hi fest, z.B. Halbierungsfolge h0 := b − a, h1 =h0

2 ,. . . , hi =hi−1

2 , . . .(2) Berechne Trapezsummen

Ti0 := T (hi) fur i = 0, 1, . . . , m

(3) Mit Neville-Schema, welches sich hier schreiben lasst als

Tik := Ti,k−1 +Ti,k−1 − Ti−1,k−1

(hi−k

hi

)2− 1

berechne den Wert T (0) des Interpolationspolynoms fur h = 0 als Naherung

zum Integral.

Praxis: Mit x := h2, xi := h2i braucht Neville-Programm nicht geandert zu werden.

Eingabe: h2i , T (hi). [T (h), nicht T (h2)!!]

Bei Halbierungsfolge rechentechnische Vergunstigungen:

T (hi) = T (hi−1) ·12 + hi[f(a + hi) + f(a + 3hi) + . . .];

die Faktoren1

(hi−k

hi

)2− 1

sind 1/3, 1/15, 1/63, 1/255 . . . (dezimal abszuspeichern)

Beispiel:∫ 1

0

x5dx, h0 = 1, h1 =1

2, h2 =

1

4

(6-stellige Rechnung)

h

h

h

2

0212

2

=

T = 0.192383

=

= 1/16

1/4

1 T = 0.500000

T = 0.265625 T = 0.187500

T = 0.167969 T = 0.166666

00

10

20

11

21 22

Fehler: O(h20h

21h

22)

4.6 Diskrete Fourier-Transformation

gegeben: Daten einer Zeitreihe.

gesucht: Struktur, insbesondere zyklische Strukturen. Dazu benotige Frequenzen mit

ihren Amplituten.

A. Grundlagen

IC: komplexe Zahlen. Es sei i die imaginare Einheit, vgl. Abschnitt 3.2.

Setzt man in der Potenzreihe (vgl. Abschnitt 3.11) fur ex statt des x ∈ IR die rein

imaginare Veranderliche iϕ ein, so ergibt sich

eiϕ = (1−ϕ2

2!+

ϕ4

4!∓ . . .)

︸︷︷︸

cos ϕ

+i (ϕ−ϕ3

3!+

ϕ5

5!∓ . . .)

︸︷︷︸

sin ϕ

96


Das ist die Eulersche Formel

eiϕ = cos ϕ + i sin ϕ

Fur 0 ≤ ϕ ≤ 2π beschreibt eiϕ demnach den Einheitskreis in der komplexen Ebene IC.

Wegen den Eigenschaften der Multiplikation in IC (vgl. Abschnitte 3.2, 3.3C) gilt zum

Beispiel fur die Gleichung

(eiϕ)4 = ei4ϕ = 1 ,

dass ϕ = 0, π2, π, 3π

2die Losungen sind. D.h. mit ϕj := 2π

4j fur j = 0, 1, 2, 3 sind die

eiϕj die vier vierten Einheitswurzeln der komplexen 1.

Allgemein: ei 2πn ist n-te Einheitswurzel der komplexen 1.

Abkurzung: zj := ei 2πn

j , j = 0, 1, . . . , n− 1, sind alle n-ten Wurzeln der 1.

Fur diese zj gilt:

zνj = zj

ν

sowie Orthogonalitat:

n−1∑

ν=0

zjνz−l

ν =

{n fur l = j0 fur l 6= j

}

fur l, j ∈ {0, . . . , n− 1}

Beweis der Orthogonalitat:

znν = 1 fur alle ν ⇒ 0 = zn

ν − 1 = (zν − 1)︸︷︷︸

6=0 fur ν 6=0, ν 6=±n,...

(zn−1ν + zn−2

ν + . . . + zν + 1)

⇒

n−1∑

j=0

zjν =

{

n fur ν = 0, ±n, . . . (denn dann zν = 1)

0 fur ν 6= 0, ±n, . . .

⇒

n−1∑

j=0

zkj z−l

j =∑

zk−lj =

∑

zjk−l =

{n fur k − l = 0

0 fur k − l 6= 0

B. Komplexe Diskrete Fourier-Transformation:

Satz: Es seien g0, . . . , gn−1, c0, . . . , cn−1 ∈ IC. Dann gilt:

cν =1

n

n−1∑

j=0

gje−iνj 2π

n ⇐⇒ gj =

n−1∑

ν=0

cνeiνj 2πn

(1)

Die Formeln in (1) vermitteln die komplexe diskrete Fourier-Transformation zwis-

chen den jeweils n komplexen Zahlen cν und gν .

97


Beweis von (1): (eine Richtung ⇐, die andere analog)

∑

j

gjz−νj =

n−1∑

j=0

(c0zj0 + . . . + cνzj

ν + . . . + cn−1zjn−1) · z

−νj

=∑

j

(c0z0j + . . . + cνzν

j + . . . + cn−1zn−1j )z−ν

j

= c0

∑

j

z0j z−ν

j

︸︷︷︸

=0

+ . . . + cν

∑

j

zνj z−ν

j

︸︷︷︸

=n

+ . . . + cn−1

∑

j

zn−1j z−ν

j

︸︷︷︸

=0

= cν · n (wegen Lemma)

C. Ubergang zwischen reeller und komplexer Version:

Gegeben f0, f1, . . . , fN−1 reelle Daten (z.B. Zeitreihe) (N gerade). Gesucht: reelle Fourier

Koeffizienten A0, A1, . . . , AN2, B1, . . . , BN

2 −1. (Diese entsprechen den stetigen Fourier-

Koeffizienten ak, bk von Abschnitt 3.6C.) Statt einer direkten Transformation (unten in

(4)) “Umweg” uber n := N2 komplexe Zahlen:

f0, ..., fN−1(2)

−→

g0, g1, ..., gN2 −1

↓ (1)

A0, ..., BN2 −1

←−

(3)c0, c1, ..., cN

2 −1

(oder bei Bedarf andersherum)

Transformation im Datenraum: gj werden kunstlich gesetzt aus aufeinanderfolgen-

den f -Werten:

gj := f2j + if2j+1 fur j = 0, . . . , n− 1

(2)

Ubergang zwischen den Koeffizienten: Es sei B0 := Bn := 0 und cn := c0. Dann

gilt:

Aν − iBν =1

2(cν + cn−ν) +

1

2i(cν − cn−ν)e−iν π

n fur ν = 0, 1, . . . , n

(3)

98


(Das “Quer” in c bedeutet die konjugiert-komplexe Version.) Algorithmus: rechte Seite

ausrechnen, nach Real- und Imaginarteil trennen und Aν , −Bν ablesen.

Erganzung: Fur die Koeffizienten der reellen diskreten Fourier-Transformation gilt der

direkte Zusammenhang

Aν =2

N

N−1∑

j=0

fj cos(νj2π

N), Bν =

2

N

∑

fj sin(νj2π

N)

(4)

D. Zwei Anwendungen

Es sei f(t) periodisch mit Periode T und stuckweise stetig. ω := 2πT

Interpolation: Das trigonometrische Polynom

fn(t) :=A0

2+

n−1∑

ν=1

(Aν cos νωt + Bν sin νωt) +An

2cos nωt

interpoliert f an den Stutzstellen

tj := jT

N= j

T

2n, j = 0, 1, . . . , 2n.

Trigonometrisches Ausgleichsproblem: Das trigonometrische Polynom

fm(t) :=A0

2+

m∑

ν=1

(Aν cos νωt + Bν sin νωt)

fur m < N2

= n minimiertN∑

j=1

(fm(tj)− f(tj))2.

(f(tj)) konnen aquidistant erhobene Daten sein, f muss nicht bekannt sein.)

4.7 Fast Fourier-Transformation

zur Berechnung von Summen der Form

cν =1

n·

n−1∑

j=0

gje−iνj 2π

n fur ν = 0, . . . , n− 1, gν ∈ IC

99


A. Aufwand

Aufwand bei naivem Vorgehen: pro ν n trigonometrische Funktionen (Exponential-

Funktionen auswerten), und n Multiplikationen, dazu n− 1 Additionen. Das sind

fur alle Koeffizienten O(n2) Operationen.

n meist sehr groß! (z.B. n = 10000 oder viel mehr)

Idee 1965 Cooley & Tukey, ahnlich fruher Gauß, oder Runge:

Fast Fourier-Transformation (FFT): Aufwand O(n log2 n) Operationen

n n log2 n Ersparnis-Faktor nlog2 n

103 ≈ 10 · 103 100

104 ≈ 13 · 104 700

105 ≈ 17 · 105 6000

Annahme: n ist Zweierpotenz, d.h. n = 2p

d.h. Folge n2 , n

4 , n8 , . . . ist wohldefiniert und besteht aus naturlichen Zahlen. Abkurzung:

m :=n

2. Fur jedes ν gilt:

cν =1

n

m−1∑

k=0

g2ke−iν2k 2πn +

1

n

m−1∑

k=0

g2k+1e−iν(2k+1) 2π

n

=1

n

m−1∑

k=0

g2ke−iνk 2πm

︸︷︷︸

↓

↓

ց

+(

e−iν 2πn

)

︸︷︷︸

wνmit Abkurzung

w:=e−i 2π

n

⋆1

n

m−1∑

k=0

g2k+1e−iνk 2π

m

︸︷︷︸

↓

↓

ւ

Zwei Summen von der gleichen FFT-Struktur

Jede Summe hat 2p−1 = m Terme. An der 2. Summe ist eine Multiplikation ⋆ erforderlich

(mit e−iν 2πn ), fur alle cν insgesamt m viele (nur m, nicht n; s.u.).

Jede der beiden FFT-Summen kann analog reduziert werden; es treten weitere 2 · m2

Multiplikationen auf.

u.s.w.:

Mit m Multiplikationen ⋆ −→ 21 = 2 Summen mit je 2p−1 Termen.

Mit 2 · m2 Multiplikationen −→ 22 Summen mit je 2p−2 Termen.

Mit 4 · m4 Multiplikationen −→ 23 Summen mit je 2p−3 Termen.

...

Mit m Multiplikationen −→ 2p “Summen” mit je 1 Term.

D.h. nach p Reduktionsschritten bleibt in den Summen nichts mehr zu tun!

p = log2 n Reduktionen mit je m =n

2Multiplikationen ergibt insgesamt O(n log2 n)

Operationen.

100


B. Analyse

Analyse eines Reduktionsschrittes: Die Summen

m−1∑

k=0

g · e−iνk 2πm

sind periodisch mit Periode m und brauchen deshalb fur cm, . . . , cn−1 nicht neu berechnet

zu werden. ( ist hier Platzhalter fur 2k bzw. 2k + 1)

Es gilt namlich (ν durch m + j ersetzt):

(↓1) (↓2) (↓1)

cm+j =1

n

m−1∑

k=0

g2ke−i(m+j)k 2πm +

(e−i(m+j) 2π

n

) 1

n

m−1∑

k=0

g2k+1e−i(m+j)k 2π

m

(↓1) e−imk 2πm = e−ik2π = +1

(↓2) e−im 2πn = e−iπ = −1

}

=⇒

cm+j =1

n

m−1∑

k=0

g2ke−ijk 2πm −

(e−ij 2π

n

︸︷︷︸

wj

)⋆

1

n

m−1∑

k=0

g2k+1e−ijk 2π

m

Das bedeutet Aufspalten der g nach geraden und ungeraden Nummern (der 1. Schritt).Definiere zwei m-Vektoren y′ und y′′ fur j = 0, 1, . . . , m− 1 uber ihre Komponenten yj

y′

j :=1

n

m−1∑

k=0

g2ke−ijk 2πm , y′′

j :=1

n

m−1∑

k=0

g2k+1e−ijk 2π

m

D.h. wegen n = 2m sind y′ = 12FFT(g0, g2, g4, . . .) und y′′ = 1

2FFT(g1, g3, g5, . . .)FFTs der halben Große (2. Schritt).

Dann gilt (der 3. Schritt):

cj = y′

j + wj ⋆ y′′

j

cm+j = y′

j − (wj y′′

j )

j = 0, 1, . . . , m−1

{

Aufwand: m Multiplikationen wj ⋆ y′′

j ,

m + m = n Additionen/Subtraktionen.

(Dazu kommt die rekursive FFT-Berechnung von y′, y′′, s.o.)

Zusammenfassung/rekursive Definition von FFTn aus FFTn/2:

(m = n/2)

g0

g1...

gn−1

ր

ց

g0

g2...

g1

g3...

→

→

y′ = 12FFTm(g0, g2, . . .)

y′′ = 12FFTm(g1, g3, . . .)

→

րց

→

1. Schritt 2. Schritt

101


y′

j + wj ⋆ y′′

j

. . . . . . . . .y′

j − wjy′′

j

→

→

c0...

cm−1

. . . . . .cm...

cn−1

=: FFTn(g0, g1, . . . , gn−1)

3. Schritt

Illustration eines Rekursions-Schrittes fur n = 8:

0

c

c

c

c

c

c

c

2

4

6

1

3

5

7

1

c

g ’

yg ’

y0

g

yg

yg

yg

FFT

FFT

FFT

2

1

w

w

w

−1

−w

−w

−w

2

3

2

3

*w (Faktoren)

Bestimme w

0

4

3

’’

’’

’’

’’

1

2

3

4

5

6

7

1

2

3

8

4 y

y0

g ’

yg ’

Ersetze rekursiv die FFT-Boxen durch analoge Schemata! (d.h. der linke Teil der Illus-

tration ist vorlaufig.) Der Input von FFT4 wird wiederum nach geraden und ungeraden

Positionen sortiert ...

Es ist eine einfache Buchhaltung (ohne Umspeichern) moglich, wenn die gj gleich “richtig”

angeordnet werden! Hierzu verwende die Bit-Umkehrabbildung, vgl. Illustration. Es

werden dann jeweils benachbarte Paare von Untervektoren kombiniert, ausgehend von

Zweiergruppen, dann Viergruppen etc.

Illustration n = 8:

g c

g c

g c

g c

g c

g c

000

100 c

g c0 000

g

010

4

5

6

7

001

010

011

100

101

110

111

Bit−Umkehrabbildung Binärmuster des Index

0

3110

001

101

011

111

4

2

6

1

5

3

7

1

2

102


Praktischer Hinweis: Es wird nur ein komplexer n-Vektor benotigt als Arbeitsvektor;

zu Beginn zu besetzen mit

(g0, g4, g2, . . . , g7)

(Beispiel n = 8). Am Ende enthalt der Vektor die gesuchten Koeffizienten. Die

komplexen Zahlen wj konnen als Wurzeln der komplexen 1 mit Winkelhalbierung

berechnet werden oder durch Rekursionen der trigonometrischen Funktionen (vgl.

[Stoer I, Paragraph 1.4]). Falls n keine Zweier-Potenz ist: Es gibt analoge FFTs,

die mit Primfaktor-Zerlegung arbeiten.

Programm in den “Recipes” [Press et al.]

4.8 Ausgleichsprobleme, data fit

Mess-Reihe (tk, yk), k = 1, . . . , m

Man nimmt ein Verteilungsgesetz an (“Modell”):

y = g(t) mit noch zu bestimmenden Parametern x1, . . . , xn,

also:

g(t; x1, . . . , xn)

Beispiel: g(t) = x1 + x2t + x3t2

Annahme: mehr Daten als Parameter, d.h. m > n .

Gesucht: x1, . . . , xn, so dass

{ y1 = g(t1; x1, . . . , xn) =: f1(x1, . . . , xn)...

...

ym = g(tm; x1, . . . , xn) =: fm(x1, . . . , xn)

“moglichst gut” erfullt sind.

Wegen m > n ist dies ein “uberbestimmtes” Gleichungssystem.

Schreibe die Messdaten yk nun als Vektor y, also Vektor-Schreibweise: y = f(x)

t

g(t)

Spezialfall g(t) = x1 + x2t: Regressions–Gerade.

[ Fall m < n: Es gibt ∞-viele Losungen. → Kapitel Optimierung.]

103


Methode der kleinsten Quadrate, “Gauß-Approximation”:

minimiere uber x1, . . . , xn die Funktion

φ(x) :=

m∑

k=1

(yk − fk(x1, . . . , xn))2

Fur den minimierenden Vektor x mussen alle partiellen Ableitungen 1. Ordnung von φverschwinden, vergleiche Abschnitt 3.12. Also gilt mit der Kettenregel

2

m∑

k=1

(yk − fk(x))∂fk(x)

∂xi

= 0 fur i = 1, . . . , n

Annahme: g linear in x1, . . . , xn (nicht unbedingt in t)!Dann gibt es eine Matrix A mit

f(x) = Ax, A (m× n) Matrix, obiges Beispiel: A =

1 t1 t211 t2 t22

...

und φ(x) := (y − Ax)tr(y − Ax) = ‖y − Ax‖22 ist zu minimieren.

Es gilt

φ(x) := xtrAtrAx− 2xtrAtry + ytry ,

und man kann zeigen: grad φ = 2AtrAx− 2Atry .

gradient [φ(x)] = 0⇒ AtrAx = Atry “Normalengleichung”

des linearen Problems (notwendige Bedingung fur Minimum)

Der Gedanke, das Gleichungssystem

(AtrA)x = Atry (∗)

numerisch zu losen, ist nicht gut: Der Ubergang auf (∗) verschlechtert die Kondition

(im Vergleich zum ursprunglichen Minimierungsproblem)!

Gute Methode: n Householder Transformationen H(j) direkt auf das uberbestimmte

Gleichungssystem Ax = y anwenden, so dass A und y simultan transformiert wer-

den auf

A(n) =

n︷︸︸︷

. . . . . . .. . . . . .. . . . .. U .. . .0 . ..

0

← n

← m− n

, y(n) =

h1

h2

← n

104


(Zu Householder-Matrizen vgl. Abschnitt 2.9.)

Die Matrix H := H(n) · . . . ·H(1) ist orthogonal.

Es folgt die Beziehung (fur alle x)

‖y −Ax‖2 = ‖H(y − Ax)‖2 = ‖y(n) −A(n)x‖2 =

∥∥∥∥∥∥

h1 − Ux

h2

∥∥∥∥∥∥

2

≥ ‖h2‖2

Also: ‖y − Ax‖2 wird minimal fur die Losung x von Ux = h1

(aquivalent zur Minimierung von ‖y −Ax‖22)

Methode:

1. Berechne U und h1 mit Householder-Transformationen;

2. erhalte x aus Ux = h1 durch Ruckwartselimination.

Hinweis: Nichtlineare Ausgleichsprobleme werden linearisiert und iterativ gelost.

105



Kapitel 5 Nichtlineare Gleichungssysteme und Iterationen

Wir betrachten das Systemf(x) = 0

von n skalaren Gleichungen fi(x1, . . . , xn) = 0, i = 1, . . . , n.

Gesucht: Nullstelle x∗ von f(x) = 0. Es sei x(0) eine Naherung zu x∗, oder einfach ein

“Startvektor”.

5.1 Losen einer skalaren Gleichung

Zunachst n = 1. Fur skalare Gleichungen gibt es viele Verfahren. Z.B. Bisektion:

Intervall auf x-Achse, welches genau die Nullstelle enthalt −→ fortgesetzte Intervall-

Halbierung...

Newton-Verfahren:

(0)

f(x)

xx x x x* (2) (1)

Erhalte bessere Naherung durch Anlegen der Tangente an (x(0), f(x(0))), und durch

Aufsuchen der Nullstelle der Tangente mit f ′(x(0)) =f(x(0))

x(0) − x(1); die Auflosung ergibt

x(1) = x(0) − f(x(0))/f ′(x(0)) .

Wiederholung: Tangente an (x(1), f(x(1))) −→ x(2) u.s.w. x(3), x(4), ...

Dieses Verfahren ist das klassische Newton-Verfahren.

[Herleiten einer Iterationsfolge x(1), x(2), . . . aus abgebrochener Taylor-Entwicklung:

0 = f(x∗) = f(x) + (x∗ − x)f ′(x) + T.h.O. ,

also 0 = f(x) + (x∗ − x)f ′(x), mit geeigneter Interpretation von x und x∗.]

x(k+1) = x(k) −f(x(k))

f ′(x(k))fur k = 0, 1, 2, . . .

107


Die Iteration ist von der Form

x(k+1) = Φ(x(k)) , mit Φ(x) = x −f(x)

f ′(x)

“Fixpunkt-Iteration”. Es gilt die Fixpunkt-Gleichung Φ(x∗) = x∗.

5.2 Zur KonvergenzBeispiel: Newton-Verfahren zur Wurzelberechnung:

x∗ =√

a −→ f(x) = x2 − a

⇒ x(k+1) = x(k) −(x(k))2 − a

2x(k)

Also

Φ(x) =1

2

(

x +a

x

)

√2 ? x(0) = 1, a = 2

k x(k)

0 1

1 1.52 1.416666666

3 1.414215686

4 1.414213562

Wir beobachten “lokal” (d.h. in der Nahe von x∗) eine Verdoppelung der korrekten

Stellenzahl in jedem Schritt. Man sagt deshalb auch, dass die Konvergenz des Newton-

Verfahrens quadratisch ist.

Definition: Konvergenzordnung p ≥ 1 der Folge x(k) gegen x∗, wenn es ein C gibt,

so dass fur alle k‖x(k+1) − x∗‖ ≤ C‖x(k) − x∗‖p

mit 0 < C fur p > 1, und 0 < C < 1 fur p = 1.

Folgerung: x(k) −→ x∗ fur k → ∞.

Newton-Verfahren: p = 2.

p = 1: “lineare Konvergenz” (langsam!)

“Superlineare Konvergenz” wenn C = Ck −→ 0 fur k → ∞.

Praxis: Im Rechner ist ‖x(k+1) − x(k)‖ keine Nullfolge! Grund: Es stehen nur endlich

viele Maschinenzahlen zu Verfugung, besonders wenige in einer Umgebung U(x∗).

Am Ende i.A. periodisches Verhalten.

Umgebung

ZahlenMaschinen−

Nullstelle

Iteration

108


Probleme:

(1) “Wann” Konvergenz ?

(2) Wie schnell?

(3) Ubertragbarkeit auf Vektorfunktionen

(4) Technische Probleme: Abbruchkriterium

Beispiel fur Divergenz

(0)

Konvergenzbereich

f(x)

x*

x

Divergenz: fur das gewahlte x(0). Es gibt ein kleines Intervall um x∗ mit Konvergenz.

Wie “trifft” man hinein?

Dampfung des Newtonverfahrens

x(k+1) = x(k) − λf(x(k))

f ′(x(k))

mit “Dampfungsfaktor” λ derart, dass die “Testfunktion”

T (x) := (f(x))2 minimal wird.

Hintergrund: T (x∗) = (f(x∗))2 = 0, und T (x) > 0 fur x 6= x∗.

Fur λ = 1 ist das klassische Newtonverfahren enthalten.

Das Minimum bzw. ein optimales λ in jedem Iterationsschritt ist i.a. schwer zu finden,

deshalb Ersatzmethode (hier nur Grundprinzip):

Gedampftes Newton-Verfahren:

λ = 1 , k = 0

(1) k → k + 1

Auswerten von f(x(k))/f ′(x(k)) [= x(k) − x(k+1) = Newton-Schritt]

(2) berechne x := x(k) − λ f(x(k))f ′(x(k))

[Versuchskandidat]

falls T (x) ≥ T (x(k)) und λ ≥ λmin, dann λ := 12λ; goto (2) [λ-Halbierung]

falls T (x) ≥ T (x(k)) und λ < λmin: STOP “no convergence” [Fehlausgang]

x(k+1) := x [ T (x) < T (x(k)), x wird akzeptiert]

falls λ ≤ 12 setze λ := 2λ [λ moglichst in die Nahe von 1]

Konvergenzabfrage und -Ausgang

goto (1)

(enthalt Divergenz-Abbruch-Kriterium!) z.B. λmin = 0.01

Die Dampfung beinhaltet keine Garantie fur Konvergenz!

Abbruchkriterium, Prufen der Konvergenz

vorgebene Fehlerschranke sei ǫ (z.B. ǫ = 10−6)

Moglichkeit |f(x(k+1))| < ǫ genugt i.A. nicht, da dieses Kriterium eher von der

Skalierung von f abhangt als vom Fehler.

109


Moglichkeit |x(k+1) − x(k)| < ǫ genugt i.A. auch nicht, da dieses Kriterium nur

einen Hinweis auf den absoluten Fehler |x(k+1) − x∗| darstellt; es ist wiederum

skalierungsabhangig. Besser ist ein Maß fur den relativen Fehler.

Professionelle Programme verlangen fur den “Konvergenz-Ausgang” das Unterschreiten

mehrerer Fehlerschranken, z.B.

|f(x(k+1))| < ǫ und |x(k+1) − x(k)| < ǫ · |x(k)|

5.3 Das allgemeine Newtonverfahren

x =

x1...

xn

, f(x) =

f1(x1, . . . , xn)...

fn(x1, . . . , xn)

=

0...

0

= 0

Linearisierung [bzw. Taylorentwicklung um x(0)]:

0 = f(x∗) ≈ f(x(0)) + Df(x(0))︸︷︷︸

“Jacobi-Matrix”,

(x∗ − x(0)) (∗)

Df(x) :=

∂f1

∂x1. . . ∂f1

∂xn

......

∂fn

∂x1. . . ∂fn

∂xn

Aus (∗) erhalte ein lineares Gleichungssystem

Df(x(0)) (x(1) − x(0)) = −f(x(0))

fur den ersten Korrekturvektor ∆x = x(1) − x(0). Analog wie im Fall n = 1 erhalten wir

das allgemeine (gedampfte) Newton-Verfahren:

Newton-Algorithmus

fur k = 0, 1, 2, . . .:

Schritt 1: Berechne oder approximiere Df(x(k))

Schritt 2: Lose das lineare Gleichungssystem

Df(x(k))∆x = −f(x(k))

z.B. mit Gauß Algorithmus → ∆x

Schritt 3: Dampfungs-Strategie:

Ermittle λ derart, dass

T (x(k) + λ∆x) < T (x(k)),

wo T (x) :=∑n

i=1(fi(x))2

Schritt 4: x(k+1) = x(k) + λ∆x

k → k + 1

goto Schritt 1

110


Beispiel:

f(x) =

(f1(x1, x2)

f2(x1, x2)

)

=

((x2 − 2)2 − x1 + 1

3x1x32 − 3x1 + 1

)

= 0

geometrisch: Nullstelle x∗ ist in (x1, x2)-Ebene Schnittpunkt der Kurven, die durch

f1(x1, x2) = 0 und f2(x1, x2) = 0 definiert sind.

Jacobi-Matrix: (−1 2(x2 − 2)

3x32 − 3 9x1x

22

)

1. Iteration fur Startpunkt x(0) := (2, 1): Gleichungssystem fur den Newton-Schritt:

(−1 −2

0 18

) (∆x1

∆x2

)

=

(0

−1

)

= −f(x(0))

Losung: ∆x2 = −1/18 ⇒ ∆x1 = −2∆x2 = 1/9 ⇒

x(1) = x(0) + ∆x =

(2 + 1/9

1 − 1/18

)

≈

(2.11

0.944

)

Skizze: Schnitt von Parabel x1 = 1 + (x2 − 2)2 mit der “hyperbel-ahnlichen” Kurve

3x1(1 − x32) = 1.

5.4 Approximation der Jacobi-Matrix

Die exakte Berechnung von ∂fi/∂xj ist meist zu schwierig, oft sogar unmoglich!

Motivation im skalaren Fall:

1. Moglichkeit: 2. Moglichkeit

“numerische Approximation” “Sekantenverfahren”

(im engeren Sinn)

f ′(x(k)) ≈f(x(k) + h) − f(x(k))

hf ′(x(k)) ≈

f(x(k)) − f(x(k−1))

x(k) − x(k−1)

fur kleines |h|, z.B. h = 10−4 hier kein Extra-Funktions-

(nicht zu klein wegen Aufruf; vergleiche Figur.

Ausloschung !) Genauigkeit hangt vom

Iterationsverlauf ab.

(0)

f(x)

x

Sekante

x x x(2) (1)

111


Numerische Differentiation im Vektor-Fall:

(Es geht um Schritt 1 des Newton-Algorithmus.)

Es sei v(j) der Vektor der j-ten Spalte der Jacobi-Matrix Df ,

v(j) :=

∂f1

∂xj

...∂fn

∂xj

=

∂f(x)

∂xj

Er wird ersetzt durch die Naherung

f(x1, . . . , xj−1, xj + h, xj+1, . . . , xn) − f(x)

h

Also: spaltenweises Vorgehen. Fur jede Spalte von Df ist eine Auswertung von f not-

wendig, insgesamt also n Auswertungen von f zuzuglich der von f(x).

Algorithmus:

(f(x) sei schon berechnet und als F gespeichert.)

η := 10−4 (z.B.)

Fur j = 1, . . . , n:h = η · max{1, |xj|} · sign(xj)xj := xj + h

werte f aus → Vektor G

v(j) := 1h(G − F )

xj := xj − h [Restauration von x]

Hinweise:

1. Auch eine Verallgemeinerung der 2. Moglichkeit ist moglich: “Rang-1 Verfahren”,

“Broyden Approximation”. Solche Verfahren benotigen mehr Iterationen als Newton;

jede Iteration ist aber billiger.

2. Im IR1 ist eine Kombination von Bisektion, Sekante und inverser Interpolation sinn-

voll: Alg.v.Dekker-Brent, MATLAB fzero.

112


Kapitel 6 Optimierung

6.1 Optimierungsprobleme

Bezeichnungen:x ∈ IRn , f(x) reellwertig, ebenso

g1(x), . . . , gm(x) ,h1(x), . . . , hl(x)

Mit der Forderung x ∈ M fur geeignetes M ⊂ IRn kann z.B. auf alle ganzzahligen

Vektoren eingeschrankt werden. Dieses Kapitel: M = IRn.

mathematische Optimierungsaufgabe:

gesucht ist Vektor x so dass

f(x) → Max (oder Min)

gi(x) = 0 , 1 ≤ i ≤ mhj(x) ≤ 0 , 1 ≤ j ≤ lx ∈ M

, (OA)

(“endlich-dimensionale” Optimierung, weil Optimierung im IRn)

Vektor-Schreibweise

g(x) =

g1(x)...

gm(x)

, h(x) =

h1(x)...

hl(x)

,

0 ist passender Vektor, und ≤ ist komponentenweise zu verstehen.

dann: f(x) →Max/Min unter den Nebenbedingungen g(x) = 0, h(x) ≤ 0, x ∈ M.

f heißt Zielfunktion.

Ein x welches die Nebenbedingungen (N.B.) erfullt, heißt zulassig.

Beispiele

(1) f(x1, x2) := x1 + x2 (d.h. linear), ohne Nebenbedingungen.

OA hat keine Losung, weil f unbeschrankt.

(2) f wie eben, unter der N.B. x21 + x2

2 ≤ 1. (Einheitskreis-Scheibe)

OA hat Losung.

h(x1, x2) := x21 + x2

2 − 1 (vergleiche Figur)

(3) f wie eben, unter x21 + x2

2 ≤ 1 und x1 − x2 + 3 = 0.

OA hat keine Losung, weil keine zulassigen Punkte existieren.

(4) f(x1, x2) := 2x21 + x2

2 (d.h. nichtlinear, speziell: quadratisch) unter den N.B.

xi ≥ 0 (i = 1, 2)

x1 ≤ 1

x2 ≤ 2 − x1

(vergleiche Figur)

113


1

11

2x

x

Max

Minf=0

f=−1

1

x

1

f=4

0

f=1

x

2

1 2

Max

6.2 Methoden der Analysis

A. Freie Optimierung

Suche Min (Max) von f(x) ohne Nebenbedingung!

(Annahmen: f sei C2, x ∈ IRn)

Am Extremum gilt gradf(x) = 0, d.h.

∂f(x)

∂x1= . . . =

∂f(x)

∂xn

= 0

Der Gradient-Vektor F (x) := gradf(x) wird oft mit fx bezeichnet.

Die Komponenten von F sind also

Fi =∂f(x)

∂xi

Dann kann das Newton-Verfahren verwendet werden zur Berechnung einer Nullstelle

von F . Benotige dazu die Jacobi-Matrix von F :

∂2f(x)∂x2

1· · ·

∂2f(x)∂x1∂xn

......

∂2f(x)∂xn∂x1

· · ·∂2f(x)

∂x2n

114


Das ist die Matrix aller zweiten partiellen Ableitungen von f , auch Hesse-Matrix benannt,

oft bezeichnet mit fxx.

VORSICHT: Hier bezeichnet f die zu minimierende Funktion, wahrend F die Funktion

ist, deren Nullstelle gesucht wird!

Es resultiert das folgende Iterative Verfahren fur k = 0, 1, 2, ...: (DF · ∆x = −F )

fxx(x(k))∆x = −fx(x(k))

x(k+1) = x(k) + ∆x

fur geeigneten Startvektor x(0). Der Vektor der jeweiligen “Suchrichtung” ∆x ergibt sich

also aus der Newton-Methode fur F (x) = 0.

Beispiel: (n = 2, hier mit Bezeichnung x1 → x, x2 → y) Suche Maximum von

f(x, y) =1

3x3 − 2y2 + 2xy − x − 2y .

Das Newton-Gleichungssystem zur iterativen Berechnung einer Nullstelle von F ist

hier (2x(k) 2

2 −4

) (∆x∆y

)

= −

((x(k))2 + 2y(k) − 1

−4y(k) + 2x(k) − 2

)

Startet man mit Vektor (x(0), y(0)) = (−1, 0) und verwendet die Newton-Richtungen

(∆x, ∆y), dann ergibt sich (x(1), y(1)) = (−3,−2), und (x(2), y(2)) = (−2.2, −1.6).

(Hinweis: exaktes Maximum fur (−2,−1.5); vgl. Figur)

−1

−2 −1

−2 .

x

y

Gradienten−Iteration

1

2

1

2

Start

Newton−Iteration

Maximum

Allgemeinere Betrachtung:

Ein Vektor v heißt Abstiegsrichtung im Punkt x, wenn es ein ε > 0 gibt mit

f(x + tv) < f(x) fur 0 < t < ε .

Beispiel: negativer Gradient: v = −gradf(x)

Wenn ein Maximum gesucht wird, dann Aufstiegsrichtung, z.B. +gradf .

Der Gradient ist diejenige Richtung, in der f maximal ansteigt! Und −grad f ist die

Richtung des maximalen Gefalles!

115


Algorithmus (erlautert fur Minimierung):

1.) Konstruiere in x(k) eine Abstiegsrichtung v(k).

2.) Fuhre ein-dimensionale Minimierung durch in Richtung v(k). Bei dieser “line

search” wird das Minimum von f(x(k) + tv(k)) naherungsweise ermittelt. Wenn

das Minimum dieser line search fur ein t = tk erreicht wird, dann setze x(k+1) =

x(k) + tkv(k).

Man nennt diese iterative Minimierung Gradientenverfahren, wenn v = −grad f .

obiges Beispiel: (gleicher Startvektor) Wegen gradf(x(0)) =

(0

−4

)

ist v(0) =

(0

−1

)

eine Aufstiegsrichtung. Zu maximieren ist also in Richtung

(−1

0

)

− t

(0

1

)

=

(−1

−t

)

fur t > 0. Eingesetzt in f :

f(−1,−t) =2

3− 2t2 + 4t

hat Maximum fur t = 1. Also (x(1), y(1)) = (−1,−1). (Die nachste Iteration ergibt

(−√

3,−1), vgl. Figur)

Hinweis: Die Newton-Richtung ist i.A. “schneller” als die Gradienten-Richtung, weil sie

auch Informationen der zweiten Ableitung berucksichtigt.

B. Optimierung mit Gleichungen als Nebenbedingungen

f(x) → Min unter N.B. gi(x) = 0, i = 1, . . . , m (g sei wie f differenzierbar) mit

“Lagrange-Multiplikatoren” λ1, . . . , λm (Vektor λ)

L(x, λ) := f(x) +

m∑

j=1

λjgj(x)

n + m Unbekannte x1, . . . , xn, λ1, . . . , λm.

Satz: x∗ minimiere das Optimierungsproblem. Dann gibt es λ , so dass grad [L(x∗, λ)] =

0. (Das sind n + m Gleichungen.)

C. Konvexe Optimierung

vgl. Abschnitt 6.4.

6.3 Lineare Optimierung

f, g, h seien alle linear in x:

f(x) =c1x1 + . . . + cnxn = ctrx

gi(x) =di1x1 + . . . + dinxn − ri , i = 1, . . . , m

hj(x) =bj1x1 + . . . + bjnxn − sj , j = 1, . . . , l

116


Matrix-Vektor-Schreibweise: Mit

(ci) → c , n Vektor , analog r ∈ IRm, s ∈ IRl

((dik)) → D , m × n Matrix

((bjk)) → B , l × n Matrix

ergibt sich aus dem Problem von § 6.1 speziell das Lineare Programm (LP)

{f(x) = ctrx → Min (oder Max)

Dx = rBx ≤ s

(LP)

Unter den diversen moglichen Formen von Problemen linearer Optimierung wird ein Typ

als Standardform oder Normalform bezeichnet:

f(x) = ctrx → Min (oder Max)

unter den N.B. Ax = b und x ≥ 0(NF)

(Vektoren x, c gegenuber (LP) modifiziert, ebenso wie die Dimension n !)

“Tricks” zur Uberfuhrung von (LP) in Normalform (NF):

1.) Bx ≤ s ⇔ y := s − Bx ≥ 0

y heißt Schlupf-Variable (slack variable)Fuge y als weitere Variable und Bx + y = s als weitere Gleichung hinzu.

2.) Realisierung “freier” xi (im Sinne xi < 0 ist erlaubt): Definiere

x+i := max{xi, 0} ≥ 0

x−

i := max{−xi, 0} ≥ 0

Dann gilt: xi = x+i − x−

i

Fuge x+i und x−

i als neue Variable hinzu, nehme xi heraus, und ersetze in den

Gleichungen xi = x+i − x−

i .

eventuell noch

3.) f(x) → Max ⇔ −f(x) → Min

Beispiel

(LP) → (NF)

x1 + 2x3 ≤ 30 → x1 + 2x3 + y1 = 30

2x2 − 3x4 ≤ 0 → 2x2 − 3x4 + y2 = 0

x2 − x3 + 2x4 ≥ 1 → x2 − x3 + 2x4 − y3 = 1

x1 + x2 + x3 + x4 = 4 → bleibt

xi ≥ 0 → bleibt, hinzu kommt yi ≥ 0

neue Variable fur die Optimierung:

x1, . . . , x4, y1, y2, y3 , alle ≥ 0 (nenne sie etwa x).

Dann gilt Ax = b mit x ∈ IR7 und

A =

1 0 2 0 1 0 0

0 2 0 −3 0 1 0

0 1 −1 2 0 0 −1

1 1 1 1 0 0 0

, b =

30

0

1

4

117


Die k-te Spalte von A ergibt sich aus den Koeffizienten zu xk in (NF). Die 4 Glei-

chungen im IR7 (falls uberhaupt losbar) definieren eine Menge, welche mindestens

die Dimension 3 hat. (siehe unten) Die Menge ist nicht leer, denn zum Beispiel mit

x4 = 4, x1 = x2 = x3 = 0 sind die Ungleichungen erfullt, d.h.

x = (0, 0, 0, 4, 30, 12, 7)tr

erfullt die Gleichungen und ist also zulassiger Punkt.

Allgemeine Analyse der Menge der zulassigen Punkte

Hierzu betrachte ohne Einschrankung nur die Standardform (NF). A sei m × n Matrix,

n > m, Ax = b, x ≥ 0. (D.h. n ist anders als in (LP). Das x hier entspricht dem x.)

D.h. x ∈ IRn, b ∈ IRm; m ist die Anzahl der Gleichungen. Die Menge der zulassigen

Punkte, also die Losungen von Ax = b mit x ≥ 0, ist ein Polyeder (polyhedron) [1].

Polyeder sind konvex (sofern nicht leer).

Ax = b bedeutet: Der Vektor b ist Linearkombination der Spalten von A. Wenn Ax = blosbar ist, dann ist die Menge der Losungen ein Teilraum des IRn von der Dimension

n − Rang(A) ,

siehe auch Abschnitt 2.5.

Die Funktion ctrx nimmt ihr Minimum (Max), falls es existiert, in mindestens einem

endlichen Eckpunkt des Polyeders an.

Die Ecken heißen Basislosungen. Ein zulassiger Punkt xB ist Basislosung genau dann,

wenn diejenigen Spalten von A, die zu positiven Komponenten von xB gehoren, linear

unabhangig sind.

Folgerungen fur Rang(A) = m:

⇒ Es gibt m linear unabhangige Spalten.

⇒ Maximal m Komponenten von xB sind positiv.

⇒ Mindestens n − m Komponenten von xB sind = 0.

Setzt man n−m Komponenten von x zu Null, so definiert das n−m Gleichungen/Ebenen

xi = 0. Zusammen mit den m Gleichungen von Ax = b sind dies insgesamt n Gleichun-

gen/Ebenen, diese definieren i.A. einen Eckpunkt des Polyeders.

Wechsel der Ecke:

Gibt man eines derjenigen xi = 0 “frei”, etwa xk, welches nun erhoht wird (xk > 0),

dann lauft man eine Kante des Polyeders entlang, bis eine andere Komponente der freien

Komponenten von x (z.B. xj) Null wird. Dann hat man eine andere Ecke erreicht, und

einen Austausch-Schritt vollzogen.

Da die Zielfunktion ctrx im nicht-degenerierten Fall ihr Optimum in einer Ecke annimmt,

geht es bei der linearen Optimierung um die Konstruktion geeigneter Austausch-Schritte.

[1] Ein Polyeder ist definiert als Losungsmenge einer endlichen Anzahl von linearen

Gleichungen und Ungleichungen.

118


Beispiel:x2 ≥ 1 − x1 (I)

x2 ≤ 2 − 2x1 (II)

x2 ≤ 1 (III)

Zielfunktion z.B. −x1 − x2 = Min! (graphische Losung...)

2

1 x

x

(I)

0

(II)

(III)

1

2

1

Die zugehorige Normalform ist gegeben durch

A =

−1 −1 1 0 0

2 1 0 1 0

0 1 0 0 1

, b =

−1

2

1

Also: n = 5, m = 3. Es gibt mehrere Moglichkeiten, 2 (= n − m) der 5 Kompo-

nenten zu Null zu setzen. Wahlen wir als Null-Kandidaten die Schlupf-Variablen

x3, x4, x5 aus, so ergeben sich 3 Moglichkeiten und also 3 Eckpunkte. Diese haben

die Koordinaten(1, 0, 0, 0, 1)

( 12, 1, 1

2, 0, 0)

(0, 1, 0, 1, 0)

(Die beiden fettgedruckten Nullen sind jeweils gesetzt, und die ubrigen 3 Kompo-

nenten ergeben sich aus Ax = b.)

Algorithmus (Simplex-Verfahren): Das Simplex-Verfahren lauft am Rand des Polyed-

ers entlang der Kanten von einer Ecke zur nachsten, so dass sich der Wert der

Zielfunktion ctrx verbessert.

Dies bedeutet jeweils einen planmaßigen Austausch der Basislosung derart, dass eine

Null-Komponente positiv wird und gleichzeitig eine positive Komponente im Vektor xNull wird. Ziel dabei: minimieren (oder max.) von ctrx.

Ausfuhrung des Simplex-Verfahrens: vgl. Vorlesung oder Literatur zu Operations Re-

search.

119


6.4 Konvexe Optimierung

(Vorgehen ahnlich wie in Abschnitt 6.2B)

Konvexe Mengen

Fur x, y ∈ IRn ist

θx + (1 − θ)y

eine Gerade durch x und y (fur θ ∈ IR).

Definition: Eine Menge C heißt konvex, wenn fur alle x, y ∈ C und alle θ mit 0 ≤ θ ≤ 1

gilt:

θx + (1 − θ)y ∈ C .

Vgl. Abschnitt 4.4: Die konvexe Hulle von p1, . . . , pk ∈ IRn ist

{k∑

i=1

sipi fur si ≥ 0 ∀i ,k∑

i=1

si = 1

}

.

Konvexe Funktionen

Der Definitionsbereich D einer Funktion f sei konvex. f heißt dann konvex, wenn fur

alle x, y ∈ D und θ mit 0 ≤ θ ≤ 1 gilt

f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y)

Konvexes Optimierungsproblem (KO)

f(x) → Min. unter N.B.

hj(x) ≤ 0 (j = 1, . . . , l),wobei f, h1, . . . , hl alle konvex seien.

Vorteile dieser Annahmen:

1. Jedes lokale Minimum einer konvexen Funktion f ist auch globales Minimum.

2. Die Menge, welche durch hj(x) ≤ 0 (j = 1, . . . , l) definiert ist, ist konvex (sofern

nicht leer).

Beispiele

• Beispiel (4) in Abschnitt 6.1

• Methode der kleinsten Quadrate, vgl. Abschnitt 4.8 (dort f = φ; keine N.B.)

• Wenn A eine symmetrische und positiv-definite Matrix (xtrAx > 0 fur x 6= 0) ist,

dann ist die Funktion xtrAx konvex.

• Lineare Programmierung: wichtiger Spezialfall, vgl. Abschnitt 6.3

Einfacher Fall von (KO): Wenn fur ein x gilt grad f(x) = 0 und N.B. ist erfullt, dann ist

x∗ := x das Minimum. (vgl. Abschnitt 6.2)

Ansonsten: Anwenden der Karush-Kuhn-Tucker-Bedingungen.

120


Karush-Kuhn-Tucker-Bedingungen (KKT, manchmal auch nur Kuhn-Tucker-Be-

dingungen genannt) Betrachte (KO) mit der zusatzlichen Voraussetzung, dass die Funk-

tionen f, h1, . . . , hl alle differenzierbar sind.

x∗ sei ein Minimum. Dies ist aquivalent zur Aussage:

Es gibt l Lagrange-Multiplikatoren yj ≥ 0 (j = 1, . . . , l),so dass

∂f(x∗)

∂xi

+

l∑

j=1

yj

∂hj(x∗)

∂xi

= 0 fur i = 1, . . . , n

l∑

j=1

yj hj(x∗) = 0

Wegen h ≤ 0 und y ≥ 0 ist letztere Gleichung aquivalent zu l skalaren Gleichungen

yj hj(x∗) = 0, fur j = 1, . . . , l. Also bestehen die KKT-Bedingungen aus n+l Gleichungen

fur die n + l Unbekannten x1, . . . , xn, y1, . . . , yl. In Vektorschreibweise lassen sich die

KKT-Bedingungen kurz schreiben

y ≥ 0, gradf + (Dh)try = 0, ytrh = 0

dabei bezeichnet Dh die Jacobi-Matrix des Vektors h; (Dh)try =∑

j yj grad gj .

Beispiel (4) in Abschnitt 6.1:

f(x1, x2) := 2x21 + x2

2 = max!

h1(x1, x2) := −x1 ≤ 0

h2(x1, x2) := −x2 ≤ 0

h3(x1, x2) := x1 − 1 ≤ 0

h4(x1, x2) := x1 + x2 − 2 ≤ 0

Die Voraussetzungen sind erfullt; n = 2 und l = 4.

Die ersten zwei (i = 1, 2) Gleichungen von KKT sind:

4x1 + y1 · (−1) + y2 · 0 + y3 · 1 + y4 · 1 = 0

2x2 + y1 · 0 + y2 · (−1) + y3 · 0 + y4 · 1 = 0

Die weiteren 4 Gleichungen sind klar. Als Losung ergibt sich

(x1, . . . , xn, y1, . . . , yl) = (2, 0, 0,−8, 0,−8) .

121

Date post:	24-Aug-2019
Category:	Documents
Upload:	dangnhi
View:	218 times
Download:	0 times

Vorlesungs-Skript Mathematik fu¨r...

Documents