118
Institut für Angewandte und Numerische Mathematik KIT - Universität des Landes Baden-Württemberg und nationales Forschungszentrum in der Helmholtz-Gemeinschaft www.kit.edu Einführung in die Numerische Mathematik Skript zur den Vorlesungen im Studienjahr 2012/2013 Christian Wieners Version vom 14. Februar 2014

Einführung in die Numerische Mathematikwieners/EinfuehrungNumerik.pdf · Eine einführende Vorlesung in die Numerische Mathematik muss gleichermaßen drei Aspek-te berücksichtigen:

  • Upload
    lehanh

  • View
    237

  • Download
    0

Embed Size (px)

Citation preview

nationales Forschungszentrum in der Helmholtz-Gemeinschaft

Institut für Angewandte und Numerische Mathematik

KIT - Universität des Landes Baden-Württemberg undnationales Forschungszentrum in der Helmholtz-Gemeinschaft www.kit.edu

Einführung in die Numerische MathematikSkript zur den Vorlesungen im Studienjahr 2012/2013

Christian Wieners

Version vom 14. Februar 2014

Inhaltsverzeichnis

1 Einführendes Beispiel: Die euklidische Approximation 1

2 Direkte Lösungsverfahren für lineare Gleichungen 3

3 Lineare Ausgleichsrechnung 18

4 Eigenwertberechnung 27

5 Iterationsverfahren für lineare Gleichungssysteme 38

6 Iterative Lösungsverfahren für nichtlineare Gleichungssysteme 51

7 Orthogonalpolynome 59

8 Polynominterpolation 69

9 Splines 79

10 Numerische Integration 93

11 Trigonometrischce Interpolation 107

Eine einführende Vorlesung in die Numerische Mathematik muss gleichermaßen drei Aspek-te berücksichtigen:

• Einführung in die Mathematische und Numerische ModellbildungJede numerische Berechnung setzt im ersten Schritt die Formulierung eines An-wendungsproblems als ein mathematisches Modell voraus. In einem zweiten Schrittwird dann ein diskretes, numerisch berechenbares Modell erstellt.

• Einführung in die Numerische AnalysisDie Numerische Analysis (als direkte Fortsetzung der Grundvorlesungen LineareAlgebra und Analysis) ist der mathematische Kern der Numerischen Mathematikund der Schwerpunkt dieser Vorlesung.

• Einführung in die Algorithmische Numerische MathematikJede numerische Berechnung setzt die Formulierung und Implementation eines Al-gorithmus voraus. In tieferes Verständnis numerischer Verfahren setzt eine Ausein-andersetzung mit der algorithmischen Umsetzung dieser Verfahren voraus.

Obwohl eine ganze Reihe hervoragender Lehrbücher (auch in deutscher Sprache) zu die-sem Thema verfügbar sind, ist es für viele Studenten leichter, einem Text zu folgen, dasgenau auf den Kurs abgestimmt ist. Insbesondere basieren viele einführende Lehrbücherin die Numerische Mathematik auf einem Kurs über mehrere Semester, und sie enthaltenweit mehr Stoff als in einer einführenden Vorlesung behandelt werden kann. Daher ergibtsich die Notwendigkeit, die klassischen Methoden und Resultate komprimiert zusammen-zufassen.

In diesem Text wird daher meine persönliche Auswahl von Themen aus den unten angege-benen Lehrbüchern angegeben, die in einer einführenden Vorlesung nicht fehlen sollten.Dabei konzentriere ich mich auf einen systematischen Aufbau der Grundlagen der Nu-merischen Analysis. Der Kurs richtet sich speziell an Mathematiker, denen damit auchdas Handwerkzeug zu weiterer Vertiefung in der Numerischen Analysis vermittelt werdensoll. Ergänzend werden zu vielen Algorithmen Matlab-Skripten angegeben.

Diese Einführung enthält keine eigenen Ergebnisse, alle Beweise sind der Literatur ent-nommen. Zudem möchte ich mich an dieser Stelle bei allen Studierenden und Mitarbei-tern bedanken, die bei der Erstellung des Textes geholfen haben, insbesondere bei RaminShirazi-Nejad für die Erstellung der ersten Version und bei Phillip Ost und Jan Ihrens fürdie korrigierte Fassung.

Literatur

Deuflhard / Hohmann: Numerische Mathematik I, de Gruyter 2002 (3. Auflage)Hanke-Bourgois: Grundlagen der Numerischen Mathematik, Teubner 2003Höllig: Grundlagen der Numerik, Zavelstein 1998Kress: Numerical Analysis Springer 1998Süli / Mayers: An Introduction to Numerical Analysis Cambridge 2003

1 Einführendes Beispiel: Die euklidische Approximation

Sei V ein reeller euklidischer Vektorraum. Das Skalarprodukt in V wird mit 〈·, ·〉V und dieNorm mit ‖ · ‖V bezeichnet.

(1.1) ProblemSei v ∈V , und sei VN ⊂V ein endlich-dimensionaler Teilraum der Dimension N.Bestimme v∗N ∈V mit

‖v− v∗N‖V = minvN∈VN

‖v− vN‖V .

Im Folgenden sei φnn=1,...,N eine Basis von VN . Zunächst benötigen wir ein Hilfsresultat.

(1.2) LemmaDie Matrix

A =(〈φm,φn〉V

)m,n=1,...,N

∈ RN×N

ist symmetrisch und positiv definit.

Beweis. Die Symmetrie der Matrix folgt aus der Symmetrie des Skalarprodukts.Sei y ∈ RN , y 6= 0. Zeige yT Ay > 0.

Da y 6= 0 ist, gilt auchN∑

n=1y[n]φn 6= 0, denn die Basisvektoren φn sind linear unabhängig.

Also gilt ‖∑Nn=1 y[n]φn‖V > 0 und somit

yT Ay =N

∑m=1

y[m]N

∑n=1

y[n]〈φm,φn〉V

=N

∑m=1

y[m]⟨

φm,N

∑n=1

y[n]φn

⟩V

=⟨ N

∑m=1

y[m]φm,N

∑n=1

y[n]φn

⟩V=∥∥∥ N

∑n=1

y[n]φn

∥∥∥2

V≥ 0 .

(1.3) SatzProblem (1.1) ist eindeutig lösbar. Es gilt

v∗N =N

∑n=1

x[n]∗φn ,

wobei x∗ ∈ RN die eindeutige Lösung des linearen Gleichungssystems

Ax∗ = b

mit b =(〈v,φm〉V

)m=1,...,N

∈ RN ist.

1

Beweis. Definiere f (x) = 12

∥∥v−∑Nn=1 x[n]φn

∥∥2V . Dann gilt

2 f (x) =⟨v−

N

∑m=1

x[m]φm,v−N

∑n=1

x[n]φn⟩

V

= 〈v,v〉V −N

∑m=1

x[m]⟨φm,v〉V −

N

∑n=1

x[n]⟨v,φn

⟩V +

N

∑m=1

x[m]N

∑n=1

x[n]⟨φm,φn

⟩V

=⟨v,v〉V −2xT b+ xT Ax .

Also ist f beliebig oft stetig differenzierbar, und es gilt

∂x[n]x = en (n-ter Einheitsvektor in RN),

∂x[n]f (x) = −(en)

T b+12(en)

T Ax+12

xT Aen = (en)T (Ax−b) ,

∂ 2

∂x[m]∂x[n]f (x) =

12(en)

T Aem +12(em)

T Aen = (em)T Aen

=12(en)

T (A+AT )em = (em)T Aen ,

denn A ist symmetrisch. Die kritischen Stellen von f (·) sind durch

∇ f (x∗) = 0 ⇐⇒ Ax∗−b = 0 ,

charakterisiert. Also ist x∗ = A−1b die einzige kritische Stelle. Da die Hessematrix

∇2 f (x∗) = A

positiv definit ist (Lemma (1.2)), ist die kritische Stelle ein Minimum, und das Minimumist eindeutig.

BemerkungAnaloge Aussagen gelten, wenn VN durch eine konvexe und abgeschlossene Menge ersetztwird.

2

2 Direkte Lösungsverfahren für lineare Gleichungen

Sei A ∈ RN×N invertierbar und b ∈ RN . Löse Ax = b genau und effizient.

Die LR-Zerlegung

Wir berechnen eine Zerlegung A= LR mit L, R∈RN×N und den folgenden Eigenschaften:

L[n,n] = 1, R[n,n] 6= 0, L[n,k] = R[k,n] = 0 für n = 1, . . . ,N, k > n.

L ist eine untere normierte Dreiecksmatrix: L =

1 0. . .

∗ 1

.

R ist eine obere reguläre Dreiecksmatrix: R =

∗ ∗. . .

0 ∗

.

Um Ax = b zu lösen, löse zunächst Ly = b, Rx = y und damit Ax = LRx = Ly = b.

(2.1) Satz(a) Sei L ∈ RN×N eine normierte untere Dreiecksmatrix (d.h. diagL = IN und L[1 : n,n+

1] = 0n für n = 1, ...,N − 1), und sei b ∈ RN . Dann ist L regulär und das LineareGleichungssystem (LGS) Ly = b ist mit O(N2) Operationen lösbar.

(b) Für eine reguläre obere Dreiecksmatrix R ∈ RN×N , (d.h. R[n,n] 6= 0 für alle n undR[n+1,1 : n] = 0T

n für n < N) ist das LGS Rx = y in O(N2) Operationen lösbar.

Beweis. Zu (a): Wir lösen das LGS L[1 : n,1 : n]x[1 : n] = y[1 : n] induktiv für n = 1, ...,Ndurch Vorwärtssubstitution. Es gilt det(L[1 : n,1 : n]) = 1, also ist L[1 : n,1 : n] regulär.Für n = 1 gilt y[1] = b[1].Nun sei für n > 1 bereits y[1 : n− 1] mit L[1 : n− 1,1 : n− 1]y[1 : n− 1] = b[1 : n− 1]berechnet. Aus dem Ansatz(

L[1 : n−1,1 : n−1] 0n−1L[n,1 : n−1] 1

)(y[1 : n−1]

y[n : n]

)=

(b[1 : n−1]

b[n : n]

)folgt L[n,1 : n−1]y[1 : n−1]+ y[n : n] = b[n : n], also ist

y[n : n] = b[n : n]−L[n,1 : n−1]y[1 : n−1]

mit O(N) Operationen berechenbar. Zusammen werden somit O(N2) Operationen benö-tigt.Zu (b): Umgekehrt lösen wir LGS R[n : N,n : N]y[n : N] = b[n : N] induktiv für n = N, ...,1durch Rückwärtssubstitution. Da R regulär ist, gilt det(R)=∏

Nn=1 R[n,n] 6= 0, also R[n,n] 6=

0 für alle n = 1, ...,N.Für n = N setze x[N] = y[N]/R[N,N].Nun sei für n≤ N bereits x[n : N] mit R[n : N,n : N]x[n : N] = y[n : N] berechnet. Aus(

R[n−1,n−1] R[n−1,n : N]0N−n+1 R[n : N,n : N]

)(x[n−1 : n−1]

x[n : N]

)=

(y[n−1 : n−1]

y[n : N]

)3

folgt R[n−1,n−1]x[n−1 : n−1]+R[n−1,n : N]x[n : N] = y[n−1 : n−1], also ist

x[n−1 : n−1] =(

y[n−1 : n−1]−R[n−1,n : N]x[n : N])/R[n−1,n−1]

mit O(N) Operationen berechenbar. Zusammen werden somit O(N2) Operationen benö-tigt.

(2.2) Satza) Die normierten unteren Dreiecksmatrizen bilden eine Gruppe.

b) Die regulären oberen Dreiecksmatrizen bilden eine Gruppe.

Beweis. Das Produkt von Dreiecksmatrizen ist wieder eine Dreiecksmatrix.Wie zeigen induktiv, dass L[1 : n,1 : n]−1 normierte untere Dreiecksmatrix ist.Für n = 1 gilt L[1,1]−1 = 1.Nun betrachte n > 1. Der Ansatz(

L[1 : n,1 : n] 0nL[n+1,1 : n] 1

)(L[1 : n,1 : n]−1 0n

`T 1

)=

(IN 0n0T

n 1

)mit ` ∈ Rn ergibt `T = −L[n+ 1,1 : n]L[1 : n,1 : n]−1. Also besitzt L[1 : n+ 1,1 : n+ 1]eine Inverse. Wenn L[1 : n,1 : n]−1 normierte untere Dreiecksmatrix ist, dann ist damitauch L[1 : n+1,1 : n+1]−1 normierte untere Dreiecksmatrix.Wenn R reguläre obere Dreiecksmatrix ist, dann ist L = diag(R)−1RT normierte untereDreiecksmatrix. Also ist L−1 normierte untere Dreiecksmatrix und somit

R−1 =(

LT diag(R))−1

= diag(R)−1L−T

obere Dreiecksmatrix.

Diagonalskalierung

Die Multiplikation einer Matrix A∈RM,N mit einer Diagonalmatrix DM = diag(d1, ...,dM)von links entspricht einer Zeilenskalierung (bzw. mit DN = diag(d1, ...,dN) von rechtseiner Spaltenskalierung):

DMA =

d1A[1,1 : N]...

dMA[M,1 : N]

, ADN =(

d1A[1 : M,1]∣∣∣ · · · ∣∣∣dNA[1 : M,N]

).

(2.3) SatzWenn eine Matrix A ∈ RN×N eine LR-Zerlegung A = LR besitzt, dann ist A regulär unddas LGS Ax = b ist mit O(N2) Operationen lösbar.

Beweis. Es gilt nach Voraussetzung det(L) = 1 und det(R) 6= 0, also det(A) = det(LR) =det(L)det(R) = det(R) 6= 0. Also ist A regulär.Weiterhin gilt b = Ax = LRx = Ly für y = Rx. Also löse zunächst Ly = b und dann Rx = y.

4

(2.4) SatzEine Matrix A ∈ RN×N besitzt genau dann eine LR-Zerlegung, wenn alle Hauptunterma-trizen A[1 : n,1 : n], (n = 1, . . . ,N) regulär sind. Die LR-Zerlegung ist eindeutig und lässtsich mit O(N3) Operationen berechnen.

Beweis. (i) Existenz:Wir berechnen die LR-Zerlegung A[1 : n,1 : n] = L[1 : n,1 : n]R[1 : n,1 : n] induktiv fürn = 1, ...,N.Für n = 1 gilt L[1,1] = 1, R[1,1] = A[1,1] 6= 0.Nun sei eine Zerlegung A[1 : n,1 : n] = L[1 : n,1 : n]R[1 : n,1 : n] berechnet. Der Ansatz(

L[1 : n,1 : n] 0nL[n+1,1 : n] 1

)(R[1 : n,1 : n] R[1 : n,n+1]

0Tn R[n+1,n+1]

)=

(A[1 : n,1 : n] A[1 : n,n+1]A[n+1,1 : n] A[n+1,n+1]

)ergibt die Gleichungen

L[1 : n,1 : n]R[1 : n,n+1] = A[1 : n,n+1] ,L[n+1,1 : n]R[1 : n,1 : n] = A[n+1,1 : n] ,

L[n+1,1 : n]R[1 : n,n+1]+R[n+1,n+1] = A[n+1,n+1] .

Da A[1 : n,1 : n] regulär ist, sind auch L[1 : n,1 : n] und R[1 : n,1 : n] regulär, also gilt

R[1 : n,n+1] = L[1 : n,1 : n]−1A[1 : n,n+1] ,L[n+1,1 : n] = A[n+1,1 : n]R[1 : n,1 : n]−1 ,

R[n+1,n+1] = A[n+1,n+1]−L[n+1,1 : n]R[1 : n,n+1] .

Damit ist eine LR-Zerlegung A[1 : n+1,1 : n+1] = L[1 : n+1,1 : n+1]R[1 : n+1,1 : n+1]berechnet, und aus

0 6= detA[1 : n+1,1 : n+1] = detR[1 : n+1,1 : n+1]= det

(R[1 : n,1 : n]

)R[n+1,n+1]

folgt R[n+1,n+1] 6= 0. Also ist R[1 : n+1,1 : n+1] regulär.(ii) Eindeutigkeit:Sei A = LR eine weitere LR-Zerlegung von A. Dann ist LR = LR, also L−1L = RR−1. AusSatz (2.2) folgt, dass L−1L und RR−1 sowohl untere normierte Dreiecksmatrix ist wie auchobere Dreieckmatrix. Somit gilt L−1L = RR−1 = IN , also ist L = L, R = R.(iii) Aufwand:In jedem Schritt werden zwei Dreieckssysteme mit O(n2) Operationen gelöst, N Schrittewerden benötigt. Damit ist die Anzahl der Operationen in der Größenordnung O(N3).

BemerkungDie LR-Zerlegung respektiert die Hüllenstruktur. Für k < n gilt:

A[n,1 : k] = 0Tk =⇒ L[n,1 : k] = 0T

k

A[1 : k,n] = 0k =⇒ R[1 : k,n] = 0k

5

Algorithmus 1 Berechnung einer LR-Zerlegung, Vorwärts- und Rückwärtssubstitution.

function x = lr_solve(A,b)N = size(A,1);for n=1:N-1

A(n+1:N,n) = A(n+1:N,n)/A(n,n);A(n+1:N,n+1:N) = A(n+1:N,n+1:N) - A(n+1:N,n) * A(n,n+1:N);

endx = b;for n=2:N

x(n) = x(n) - A(n,1:n-1) * x(1:n-1);endfor n=N:-1:1

x(n) = (x(n) - A(n,n+1:N)*x(n+1:N))/A(n,n);end

return

(2.5) DefinitionEine Matrix A ∈ RN×N heißt diagonaldominant, wenn

|A[n,n]| ≥N

∑k=1k 6=n

|A[n,k]| (n = 1, . . . ,N)

gilt, und strikt diagonaldominant, falls

|A[n,n]|>N

∑k=1k 6=n

|A[n,k]| (n = 1, . . . ,N)

(2.6) FolgerungWenn A ∈ RN×N strikt diagonal dominant ist, dann existiert eine LR-Zerlegung.

Beweis. Wenn keine LR-Zerlegung existiert, dann existiert ein n, für das die UntermatrixA[1 : n,1 : n] singulär ist, und es existiert x ∈ Rn mit A[1 : k,1 : k]x = 0 und x 6= 0n. Wählek ∈ 1, . . . ,n mit |x[k]| ≥ |x[ j]| für alle j = 1, ...,n. Dann folgt aus

|A[k,k]| |x[k]|=∣∣∣ n

∑j=1j 6=k

A[k, j]x[ j]∣∣∣≤ n

∑j=1j 6=k

|A[k, j]| |x[ j]|

≤ ∑j 6=k|A[k, j]| |x[k]|< |x[k]| |A[k,k]|

und x[k] 6= 0 ein Widerspruch.

(2.7) SatzSei A∈RN×N symmetrisch und positiv definit. Dann existiert genau eine Cholesky-ZerlegungA = LLT mit regulärer unterer Dreiecksmatrix L.

6

Beweis. Da A positiv definit ist, ist det(A[1 : n,1 : n]) > 0; es existiert also eine LR-Zerlegung A = LR.Definiere D = diag(R). Aus

n

∏k=1

D[k,k] = det(R[1 : n,1 : n]) = det(A[1 : n,1 : n])> 0

folgt induktiv D[k,k] > 0. Wir skalieren die Spalten von L und Zeilen von R und setzenL = LD

12 , R = D−

12 R. Damit folgt

LR = LR = A = AT = RT LT = RT LT

Hieraus ergibt sich R−T L = LT R−1 = IN , woraus R = LT folgt.

Die Berechnung der Cholesky-Zerlegung benötigt nur halb soviele Operationen wie dieBerechnung einer LR-Zerlegung.

Algorithmus 2 Berechnung einer Cholesky-Zerlegung, Vorwärts- und Rückwärtssubsti-tution.

function x = cholesky_solve(A,b)N = size(A,1);for n=1:N

A(n:N,n) = A(n:N,n) - A(n:N,1:n-1) * A(n,1:n-1)’;A(n:N,n) = A(n:N,n) / sqrt(A(n,n));

endx = bfor n=1:N

x(n) = (x(n) - A(n,1:n-1) * x(1:n-1))/ A(n,n);endfor n=N:-1:1

x(n) = (x(n) - A(n+1:N,n)’ * x(n+1:N))/ A(n,n);end

return

Die LR-Zerlegung mit Pivotsuche

Durch Zeilenvertauschungen von A lässt sich immer garantieren, dass eine LR-Zerlegungexistiert.

(2.8) DefinitionSei π ∈ SN eine Permutation. Dann heißt Pπ =

(eπ−1(1)

∣∣ · · · ∣∣eπ−1(N)

)∈ RN×N Permutati-

onsmatrix zu π .

Die Multiplikation einer Matrix A ∈ RM×N mit einer Permutationsmatrix Pπ von linksvertauscht die Zeilen (bzw. mit Pσ von rechts vertauscht die Spalten).

(PπA)[n,k] = A[π(n),k]

(APσ )[n,k] = A[n,σ−1(k)]

7

Also ist die Zeile n von A die Zeile π(n) von PπA.

Als Beispiel betrachte π ∈ S3 mit π(1) = 3, π(2) = 1 und π(3) = 2 und A =

1 2 34 5 67 8 9

.

Dann gilt Pπ =

0 0 11 0 00 1 0

, PπA =

7 8 91 2 34 5 6

und APπ =

2 3 15 6 48 9 7

.

(2.9) SatzDie Permutationsmatrizen in RN×N bilden eine Gruppe.Es gilt PπPσ = Pπσ und (Pπ)

−1 = PTπ .

(2.10) SatzSei A ∈ RN×N regulär. Dann existiert eine Permutationsmatrix P, so dass PA eine LR-Zerlegung mit |L[n,k]| ≤ 1 besitzt.

Beweis. Wir konstruieren die Zerlegung induktiv. Für N = 1 ist nichts zu zeigen. Nun seiN > 1. Suche in der ersten Spalte n = 1 das Pivotelement A[p,1] mit dem größten Betrag,d.h. |A[p,1]| ≥ |A[k,1]| für alle k = 1, ...,N. Da A regulär ist, ist A[1 : N,1] 6= 0N , alsoA[p,1] 6= 0. Falls p 6= 1, vertausche die Zeilen 1 und p und setze τ = [1 p]. Sonst setzeτ = id. Nun setze A1 = PτA, d.h. A1[1,1] = A[p,1],

L1 =

(1 0T

N−1−A1[2 : N,1]/A1[1,1] IN−1

)

L1A1 =

(1 0T

N−1−A1[2 : N,1]/A1[1,1] IN−1

)(A1[1,1] A1[1,2 : N]

A1[2 : N,1] A1[2 : N,2 : N]

)=

(A1[1,1] A1[1,2 : N]0N−1 A2

)mit der Restmatrix A2 = A1[2 : N,2 : N]+L1[2 : N,1]A1[1,2 : N]. Dann gilt per Konstruk-tion L1A1 = R1. Aus

A1[1,1]detA2 = det(L1)det(A1) = det(PτA) = det(Pτ)︸ ︷︷ ︸=±1

detA 6= 0

folgt detA2 6= 0. Also existiert in RN−1×N−1 per Induktionsvoraussetzung eine LR-ZerlegungP2A2 = L2R2. Wir setzen

P2 =

(1 0T

N−10N−1 P2

), L2 =

(1 0T

N−10N−1 L2

), R =

(A1[1,1] A1[1,2 : N]0N−1 R2

).

Aus P = P2Pτ folgt P2L1A1 = L2R. Damit erhalten wir eine LR-Zerlegung mit Pivotsuche:

PA = P2PτA = P2A1 = P2L−11 L1A1 = L−1

1 P2L1A1 = L−11 L2R = LR

8

Das System Ax = b wird wie folgt gelöst: Es gilt LRx = PAx = Pb. Berechne erst y =Rx durch Vorwärtssubstitution von Ly = Pb und dann x durch Rückwärtssubstitution vonRx = y.Die LR-Zerlegung mit Spaltenpivotsuche benötigt zusätzlich O(N2) Operationen. Die Sta-bilität (siehe unten) der LR-Zerlegung lässt sich durch sogenannte totale Pivotsuche er-höhen: Durch den Zeilen- und Spaltentausch ersetze in jedem Schritt An[1,1] durch denmaximalen Eintrag in der Restmatrix An. Hierfür werden allerdings O(N3) Operationenbenötigt.

Algorithmus 3 Berechnung einer LR-Zerlegung mit Pivotsuche, Vorwärts- und Rück-wärtssubstitution.

function x = lr_pivot_solve(A,b)N = size(A,1);p = (1:N)’;for n = 1:N-1

[r,m] = max(abs(A(n:N,n)));m = m+n-1;if abs(A(m,n))<eps

error(’*** ERROR *** Matrix fast singulär’);endif (m ~= n)A([n m],:) = A([m n],:); p([n m]) = p([m n]);

endA(n+1:N,n) = A(n+1:N,n)/A(n,n);A(n+1:N,n+1:N) = A(n+1:N,n+1:N) - A(n+1:N,n)*A(n,n+1:N);

endx = b(p);for n=2:N

x(n) = x(n) - A(n,1:n-1) * x(1:n-1);endfor n=N:-1:1

x(n) = (x(n) - A(n,n+1:N)*x(n+1:N))/A(n,n);end

return

9

Störungsrechnung(2.11) SatzSei A ∈ RN×N regulär, und sei ∆A ∈ RN×N so klein, dass ‖∆A‖< 1

‖A−1‖ gilt. Dann ist die

Matrix A = A+∆A regulär. Sei b ∈ RN , b 6= 0N , ∆b ∈ RN klein und b = b+∆b.Dann gilt für die Lösung x ∈ RN von Ax = b und x ∈ RN von Ax = b

|∆x||x|≤ κ(A)

1−κ(A)‖∆A‖‖A‖

(|∆b||b|

+‖∆A‖‖A‖

).

Dabei ist ∆x = x− x der absolute Fehler, |∆x||x| der relative Fehler, und

κ(A) = ‖A‖‖A−1‖

die Kondition von A.

Beweis. Aus der Voraussetzung ‖∆A‖< 1‖A−1‖ folgt, dass die Reihe

∑k=0

(−∆AA−1)k kon-

vergiert. Also ist A = A+∆A ∈ RN×N regulär, es gilt für die Inverse die Darstellung

(A+∆A

)−1= A−1

∑k=0

(−∆AA−1)k

und die Normabschätzung ‖(A+∆A)−1‖ ≤ ‖A−1‖1−‖A−1‖‖∆A‖ .

Ferner folgt aus (A+ ∆A)(x+ ∆x) = b+ ∆b und Ax = b die Gleichung (A+ ∆A)∆x =∆b−∆Ax und somit

|∆x| ≤ ‖(A+∆A)−1‖(|∆b|+‖∆A‖|x|)

≤ ‖A−1‖1−‖A−1‖‖∆A‖

(|∆b||x|

+‖∆A‖)|x|

≤ ‖A‖‖A−1‖1−‖A‖‖A−1‖‖∆A‖

‖A‖

(|∆b|‖A‖|x|

+‖∆A‖‖A‖

)|x|.

Mit κ(A) = ‖A‖‖A−1‖ und |∆b|‖A‖|x| ≤

|∆b||b| folgt die Behauptung.

Vektor- und Matrixnormen

Wir verwenden für x ∈ RN und A ∈ RK×N

|x|1 =N

∑n=1|x[n]| 1-Norm

|x|2 =√

xT x 2-Norm / euklidische Norm|x|∞ = max

n=1,...,∞|x[n]| Maximumsnorm

‖A‖p = supx 6=0

|Ax|p|x|p

zugeordnete Operatornorm (p = 1,2,∞) .

10

(2.12) SatzSei A ∈ RK×N . ‖ · ‖p ist submultiplikativ und es gilt

‖A‖1 = maxn=1,...,N

K

∑k=1|A[k,n]| Spaltensummennorm

‖A‖2 =√

ρ(AT A) Spektralnorm

‖A‖∞ = maxk=1,...,K

N

∑n=1|A[k,n]| Zeilensummennorm .

Dabei ist

ρ(A) = max|λ | : λ ∈ σ(A) Spektralradius von A,σ(A) = λ ∈ C : det(A−λ IN) = 0 Spektrum von A .

Beweis. Zur Submultiplikativität der Norm:

‖AB‖p = supx 6=0

|ABx|p|x|p

≤ supx 6=0

‖A‖p|Bx|p|x|p

= ‖A‖p‖B‖p

p = 1: Es gilt

|Ax|1 =K

∑k=1

∣∣∣∣∣ N

∑n=1

A[k,n]x[n]

∣∣∣∣∣leq

K

∑k=1

N

∑n=1|A[k,n]||x[n]|

≤ maxn=1,...,N

K

∑k=1|A[k,n]|

N

∑n=1|x[n]|

= ‖A‖1|x|1

Für n0 mit ∑Kk=1 |A[k,n0]|= ‖A‖1 ist

|Aen0|1 =K

∑k=1|A[k,n0]en0[n0]|= ‖A‖1

Also gilt

‖A‖1 = minC ≥ 0 | |Ax|1 ≤C|x|1= supx 6=0

|Ax|1|x|1

p = 2: Zu AT A ∈ RN,N symmetrisch existiert eine orthogonale Matrix Q ∈ RN,N (d.hQ−1 = QT ) mit

QT AT AQ = diag(λ1, . . .λN) =: Λ

und Eigenwerten λn ≥ 0 von AT A.Es gilt

|Qy|22 = (Qy)T Qy = yT QT Qy = yT y = |y|22|AQy|22 = (AQy)T AQy = yT QT AT AQy = yT

Λy≤ |√

Λy|22.

11

Damit ergibt sich (mit der Substitution x = Qy)

‖A‖= supx 6=0

|Ax|2|x|2

= supy6=0

|AQy|2|Qy|2

= supy6=0

|√

Λy|2|y|2

≤max√|λn| ,

es gilt also ‖A‖2 ≤√

ρ(AT A).Wähle n0 mit λn0 = ρ(AT A) und q ∈ RN mit Aq = λn0q, q 6= 0N mit AT Aq = λn0q. Danngilt

‖A‖2 = supx 6=0

|Ax|2|x|2

≥ |Aq|2|q|2

=√

λn0 = ρ(AT A) ,

da |Aq|22 = qT AT Aq = λn0qT q = λn0|q|22.p = ∞: siehe Analysis II

BemerkungWenn A symmetrisch ist mit Eigenwerten λ1, . . . ,λN , dann gilt

‖A‖2 =√

ρ(A2) = ρ(A) = maxn=1,...,N

|λn|

und

‖A−1‖2 = maxn=1,...,N

1|λn|

=1

minn=1,...,N

|λn|.

Also ist

κ(A) = ‖A‖2‖A−1‖2 =

maxn=1,...,N

|λn|

minn=1,...,N

|λn|.

Grundlagen der Arithmetik

In der Praxis muss das Schema Eingabe—Algorithmus—Resultat ergänzt werden:Untersuche Eingabe mit Fehlern—Algorithmus mit Fehlern—Resultat mit Fehlern.

(2.13) Definitiona) Die Gleitkommazahlen zur Basis B ∈ 2,3,4, . . ., Mantissenlänge M ∈ N und Expo-

nent E ∈ N ist die Menge

FL =

±Be

M

∑m=1

amB−m ∈Q | e = e−+E−1

∑k=0

ekB−k, ak, ek ∈ 0, . . . ,B−1

b) Eine Gleitkommaarithmetik wird durch eine Abbildung

fl: R−→ FL

mit fl(x) = x für x ∈ FL definiert: x +©y = fl(x+ y), x ·©y = fl(xy).

12

Mit eps := sup|x−fl(x)||x| | x ∈ R\FL

bezeichnen wir die Maschinengenauigkeit.

Als Ergebnis einer Rechenoperation werden zusätzlich folgende Fehlerzustände definiert:NaN (not a number) nicht definiertes Ergebnisoverflow Ergebnis > maxFL oder < minFLunderflow fl(x) = 0, aber x 6= 0

Beispiele:NaN (not a number) Division durch 0,

√−1

overflow exp(100)underflow exp(−100)

Im IEEE-Standard wird double mit 64 Bit = 8 Byte dargestellt:

1 Bit Vorzeichen

52 Bits Mantisse m =51

∑i=0

ai2i ai ∈ 0,1

11 Bits Exponenten e = E−+10

∑j=0

b j2 j b j ∈ 0,1

Es ist M = 252−1, E−=−1022, E+ = 1023 und damit gilt für die Maschinengenauigkeit

eps≈ 10−16.

Außerdem erhalten wir

FL⊂ [−10308,−10−308]∪0∪ [10−308,10308].

Folgende Probleme treten wegen der begrenzten Zahlenmenge auf:

(1) Unvermeidliche Rundungsfehler:Setze doublex = 4 · arctan(1). Dies sollte π sein. Wir erhalten:

x = 3.14159265358979316... π = 3.1415926535897932384...

(2) Auslöschung:Auslöschung tritt immer dann auf, wenn zwei fast gleich große Zahlen voneinanderabgezogen werden.Sei beispielsweise doublex = exp(1). Berechne nun y = x+ 10−8 und z = fl(x− y).Dann gilt

|z−10−8| ≈ 1e−16 ,

und für den relativen Fehler|z−10−8||z|

≈ 1e−8 .

Also ist die Berechnung nur auf 8 Dezimalstellen genau.

Ein typisches Beispiel für vermeidbare Rundungsfehler ist die Auswertung von exp(−x)für x > 0: Die Berechnung der Exponentialfunktion ist gut konditioniert, aber die direktenumerische Auswertung der Exponentialreihe für negative Argumente ist (durch Auslö-schung) sehr ungenau. Die Auswertung exp(−x) = 1/exp(x) ist numerisch stabil.

13

Kondition und Stabilität

Bei vielen Anwendungen sind die Daten (z.B. durch ungenaue Messungen) unsicher. Dazuführen wir einige Begriffe ein.

Bezeichnunga) Ein Problem heißt sachgemäß gestellt, wenn es eindeutig lösbar ist und die Lösung

stetig von den Daten abhängt.

b) Die Kondition eines Problems ist ein Maß dafür, wie stark die Abhängigkeit derLösung von den Daten ist.

c) Die Stabilität eines numerischen Algorithmus ist ein Maß dafür, wie stark die Da-tenabhängigkeit der numerischen Lösung im Vergleich zu der tatsächlichen Lösungist.

Also: Ein Problem ist gut konditioniert, wenn kleine Änderungen der Daten die Lösungnur wenig ändern.Ein numerischer Algorithmus ist stabil, wenn durch kleine Änderungen der Daten dieÄnderung der numerischen Lösung durch den Algorithmus nicht zusätzlich verstärkt wird.Damit ergibt sich folgende Charakterisierung:Kondition des Problems: Unvermeidbare Fehlerverstärkung bei optimaler Problem-

lösung.Stabilität des Algorithmus: Der gewählte Algorithmus vergrößert den Fehler nicht

stärker als die unvermeidliche Fehlerverstärkung.

Beispiela) Wetterberechnung ist schlecht konditioniert: Kleine Veränderungen der Ausgangs-

lage können langfristig große Auswirkungen haben.

b) Sei V = L2(0,1) ausgestattet mit der Norm ‖v‖2V =

∫ 10 |v(t)|2dt; VN = PN seien die

Polynome mit Grad kleiner oder gleich N.Zu v(t) = 1

1−t bestimme die euklidische Bestapproximation in PN . Nach Kapitel 1 istP(t) = ∑

Nk=0 x[k]tk mit Ax = b in RN+1

A =

(∫ 1

0tkt jdt

)k, j=0,...,N

=

(1

1+ k+ j

)k, j=0,...,N

(Hilbertmatrix)

b =

(∫ 1

0v(t)tkdt

)k=0,...,N

A ist sehr schlecht konditioniert, aber das Problem selber ist gut konditioniert.

c) Die Berechnung von xT y(x,y ∈ RN ist gut konditioniert, d.h. es existiert ein Algo-rithmus ohne Rundungsfehlerverstärkung.

d) Die Polynomauswertung mit dem Hornerschema

P(t) = a0 +a1t +a2t2 +a3t3 +a4t4

= a0 + t(a1 + t(a2 + t(a3 +a4t)))

ist stabil.

14

e) Bei der Auswertung von Differenzenquotienten

f ′(t)≈ 1h( f (t +h)− f (t))

ist Auslöschung unvermeidbar. Ein Kompromiss ist die Wahl h = |x|√eps. Die Ge-nauigkeit beträgt liegt dann im Bereich von | f (x)||x

√eps.

f) Das Berechnen einer Orthonormalbasis mit dem Gram-Schmidt-Verfahren ist nichtstabil.

Konditionszahlen(2.14) DefinitionSei f : RN −→ RK differenzierbar, x,δxk ∈ RN .Dann heißt κnk

abs(x) = |∂n fk(x)| absolute Konditionszahl, und ist | fk(x+ δx)− fk(x)| derabsolute Fehler von fk.Falls fk(x) 6= 0, so heißt κnk

rel = |∂n fk(x)| |xn|| fk(x)|

relative Konditionszahl, und | fk(x+δx)− fk(x)|| fk(x)|

ist der relative Fehler von fk.

Eine Taylor-Entwicklung erster Ordnung liefert

fk(x+δx) = fk(x)+N

∑n=1

∂n fk(x)δxn +o(δx) .

Daher gilt für den absoluten Fehler

| fk(x+δx)− fk(x)| ≤N

∑n=1

κnkabs(x)|δxn|+o(δx)

und den relativen Fehler

| fk(x+δx)− fk(x)|| fk(x)|

≤N

∑n=1

κnkrel(x)

|δxn||xn|

+o(δx) .

Beispiela) f (x1,x2) = x1+x2; die Jacobi-Matrix ist J f (x1,x2) = (1,1), d.h. es gilt κnk

abs ≡ 1 und

κn1rel(x) =

|xn||x1+x2| ≤ 1 für x1, x2 ≥ 0.

b) f (x1,x2) = x1 · x2; die Jacobi-Matrix ist J f (x1,x2) = (x2,x1).Es ist κ11

rel(x) =|x1||x2||x1x2| = 1.

Addition und Multiplikation sind gut konditioniert.

c) f (b) = A−1b; es gilt ∂n fk(b) = eTk A−1en. Die relative Konditionszahl ist durch die

Kondition von A beschränkt:

κnkrel(b) = |e

Tk A−1en|

|bn||eT

k A−1b|≤ ‖A−1‖|AA−1b|

|A−1b|≤ ‖A−1‖‖A‖= κ(A)

15

Stabilitätsanalyse

a) Ein Algorithmus ist vorwärtsstabil, wenn die einzelnen Schritte in

f = fK fK−1 . . . f2 f1

nicht wesentlich schlechter konditioniert sind als das Problem f .

b) Zu einem gestörten Ergebnis y = f (x) suche x mit f (x) = y (exaktes Ergebnis mitgestörten Eingangsdaten).Falls |x−x|

|x| klein ist, heißt der Algorithmus rückwärtsstabil.

16

Satz von Wilkinson

Sei PA≈ LR eine numerisch berechnete LR-Zerlegung. Dann gilt

‖PA− LR‖∞

‖A‖∞

≤ 2N3r(A)eps

mit

r(A) =max|a| | a ∈ R tritt im Algorithmus auf

max|A[n,k]|und

r(A)≤ 2N−1 LR-Zerlegung mit Spaltenpivotsucher(A)≤ 1 Cholesky-Zerlegungr(A)≤ 2 A tridiagonal oder strikt diagonaldominant

PA≈ LR impliziert A−1 ≈ (PT LR)−1 = B.

17

3 Lineare Ausgleichsrechnung

(3.1) Lemma (Givensrotation)Zu x ∈ RN mit x[k]2 + x[n]2 > 0 für k 6= n, k,n ∈ 1, . . . ,N, existiert eine Givensrotation

Q = c(ekeTk + eneT

n )+ s(ekeTn − eneT

k )+ ∑j 6=k,n

e jeTj

mit c2 + s2 = 1 und (Qx)[n] = 0.Es gilt QQT = IN , also ist Q orthogonal.

Beweis. Aus y = Qx folgt

y[i] =

x[i] i 6= m,ncx[m]+ sx[n] i = m−sx[m]+ cx[n] i = n

Soll nun y[n] = −sx[m]+ cx[n] = 0 gelten, dann folgt sx[m] = cx[n]. Zur stabilen Berech-nung von c, s müssen wir Auslöschung vermeiden, also unterscheiden wir zwei Fälle:

Fall 1: Für |x[n]|> |x[k]| setze τ =x[k]x[n]

=cs

. Dann gilt

τ2 =

c2

s2 =c2 + s2− s2

s2 =1− s2

s2 =1s2 −1 =⇒ s =

1√1+ τ2

, c = τs .

Fall 2: Für |x[n]| ≤ |x[k]| setze τ =x[n]x[k]

=sc

. Dann gilt

τ2 =

s2

c2 =s2 + c2− c2

c2 =1− c2

c2 =1c2 −1 =⇒ c =

1√1+ τ2

, s = τc .

Eine Givensrotation beschreibt eine Drehung um den Winkel ϕ mit (s,c) = (sinϕ,cosϕ)in der Ebene, die von em und en aufgespannt wird.

(3.2) Lemma (Householdertransformation)Zu x∈RN , x 6= 0, existiert eine orthogonale Matrix Q = IN−βwwT ∈RN×N mit β = 2

wT w ,w[1] = 1 und Qx = σe1 , |σ |= |x|2.

Beweis. Q = IN−βwwT ist orthogonal, es gilt also

IN = QT Q = Q2 = (IN−βwwT )(IN−βwwT )

= IN−2βwwT +β2wwT wwT

= IN +β (−2+β2wwT )wwT ,

d.h. es ist β = 0 oder β = 2wT w . Es gilt Qx = x−βwwT x = x− (βwT x)w und |Qx|22 = |x|22.

Aus Qx = σe1 folgt |σ |= |x|2. Weiterhin folgt aus σe1 = x− (β 2wT x)w

σ = σe1[1] = x[1]−βwT x ,

18

d.h. βwT x = σ − x[1] und w = 1x[1]−σ

(x−σe1).Zur Vermeidung von Auslöschung betrachte zwei Fälle:1. Fall: Für x[1]> 0 wähle σ =−|x|2, d.h. w = 1

x[1]+|x|2 (x+ |x|2e1).

2. Fall: Für x[1]≤ 0 wähle σ = |x|2, d.h. w = 1x[1]−|x|2 (x−|x|2e1).

(3.3) Satz (QR-Zerlegung)Sei A ∈ RK×N . Dann existiert eine orthogonale Matrix Q ∈ RK×K und eine obere Drei-ecksmatrix R ∈ RK×N mit A = QR.

Beweis. Wir führen eine Induktion über N durch. Für N = 1 folgt sofort Q = 1, R = A.N > 1: Setze x = A[1 : K,1] ∈ RK . Wir unterscheiden zwei Fälle:1. Fall: x[2 : K] = 0K−1Setze Q1 = IN und σ = A[1,1].2. Fall: x[2 : K] 6= 0K−1. Setze

σ =

−|x|2 x[1]> 0,|x|2 x[1]≤ 0,

w ∈ RN mit w[1] = 1, w =1

x[1]−σx[2 : K],

Q1 = IN−2

wT wwwT .

Damit gilt

Q1A =

(σ R1[1,2 : N]

0M−1 A2

),

mitR1[1,2 : N] = Q1[1,1 : K]A[1 : K,2 : N] ∈ R1×N−1

undA2 = Q1[2 : K,1 : K]A[1 : K,2 : K] ∈ RK−1×N−1.

Nun sei A2 = Q2R2 ∈ RK−1,N−1 eine QR-Zerlegung der Restmatrix. Also

A = Q1

(σ R1[1,2 : N]

0K−1 Q2R2

)= Q1

(1 0T

K−10K−1 Q2

)︸ ︷︷ ︸

=:Q

(σ R1[1,2 : N]

0K−1 R2

)︸ ︷︷ ︸

=:R

Bemerkung (Aufwand)Zählt man alle Operationen zur Lösung des LGS Ax = b zusammen, so erhält man denAufwand der Verfahren (nur die Terme mit höchstem Exponenten):

QR−Zerlegung :43

N3 Operationen,

LR−Zerlegung :23

N3 Operationen,

LLT −Zerlegung :13

N3 Operationen.

19

Wir betrachten die folgenden Spezialfälle:

1. K = N, A regulär:Es gilt 0 6= detA = detQdetR, also ist 0 6= detR = ∏

Nn=1 R[n,n], woraus R[n,n] 6=

0, n = 1, . . . ,N, folgt.Eine Lösung von Ax = b berechnet sich wie folgt: Aus QT Ax = QT QRx = QT bfolgt Rx = QT b; x = R−1(QT b) ist mit Rückwärtssubstitution in O(N2) Operationenlösbar.

2. K > N, rang(A) = NEs existiert eine QR-Zerlegung A = QR mit

R =

(R[1 : N,1 : N]

0

)Dann gilt:

Ax = b ist lösbar ⇐⇒ Rx = QT b = y ist lösbar⇐⇒ y[N +1 : K] = 0K−N

3. K < N, rang(A) = K:Es existiert eine Permutationsmatrix P mit AP=QR mit R=

(R[1 : K,1 : K] R[1 : K,K +1 : N]

)=(

R1 R2). Dann gilt:

Ax = b⇐⇒ AP PT x︸︷︷︸=:z

= b⇐⇒ QRz = b⇐⇒ Rz = QT b =: y

Die spezielle Lösung ist z[1 : K] = R−11 y[1 : K]. Für die allgemeine Lösung wähle

z[K +1 : N] ∈ RN−K , dann folgt z[1 : K] = R−11 (b−R2z[K +1 : N])

Im Allgemeinen ist das lineare Gleichungssystem Ax = b für b ∈ RK und A ∈ RK×N nichtoder nicht eindeutig lösbar. Stattdessen untersuchen wir nun das Minimierungsproblem:

Bestimme x ∈ RN mit |Ax−b|2 = Min!

(3.4) SatzSei A ∈ RK×N , b ∈ RK . Dann ist äquivalent:

(a) |Ax−b|2 ≤ |Ay−b|2 ∀y ∈ RN

(b) x ∈ RN löst die Normalengleichung AT Ax = AT b.

Beweis. Betrachte

F(x) =12|Ax−b|22

=12(Ax−b)T (Ax−b)

=12

xT AT Ax− 12

bT Ax− 12(Ax)T b+

12

bT b

20

Algorithmus 4 Berechnung einer QR-Zerlegung und Lösung eines Gleichungssystems.

function x = qr_solve(A,b)[M,N] = size(A);for m = 1:min(N,M-1)

[v,beta] = householder(A(m:M,m));if beta ~= 0

w = beta * v’ * A(m:M,m:N);A(m:M,m:N) = A(m:M,m:N) - v * w;A(m+1:M,m) = v(2:M-m+1);

endendfor m = 1:min(N,M-1)

v = [1;A(m+1:M,m)];beta = 2 / (v’ * v);if beta ~= 2b(m:M) = b(m:M) - beta*(v’ * b(m:M)) * v;

endendx = zeros(N,1);for n=min(N,M):-1:1

x(n) = (b(n) - A(n,n+1:N) * x(n+1:N)) / A(n,n);end

return

21

„(a) =⇒ (b)“Es gilt F(x)≤ F(y) für alle y ∈ RN , d.h. es gilt

∂nF(x) =12

eTn AT Ax+

12

xT AT Aen−12

bT Aen−12(Aen)

T b

= eTn (A

T Ax−AT b)= 0

Damit folgt AT Ax = AT b.„(b) =⇒ (a)“Mittels Taylorentwicklung folgt

F(y) = F(x)+∇F(x)(y− x)+12(y− x)T Hk(x)(y− x)

= F(x)+12|A(y− x)|22

≥ F(x)

BemerkungDie Normalengleichung ist lösbar. Sei dazu y ∈ Kern(AT A). Dann gilt AT Ay = 0, alsoyT AT Ay = |Ay|22 = 0. Somit ist y ∈ Kern(A), bT (Ay) = (AT b)T y = 0, also AT Ax = AT blösbar.

Anwendungen1. N K, rangA = N

AT A∈RN×N ist symmetrisch und positiv definit. Berechne eine Cholesky-ZerlegungLLT = AT A und löse LLT x = AT b.

2. K < N, rangA = KAT A ∈RN×N ist singulär. Berechne eine QR-Zerlegung A = QR. Damit gilt AT Ax =RT QT QRx = RT Rx = RT Qb.Ist R[1 : K,1 : K] = R1 regulär, so löst x[1 : K] = R−1

1 QT b, x[K +1 : N] = 0N−K dieNormalengleichung.

3. A hat nicht vollen RangDas Ausgleichsproblem ist nicht sachgemäß gestellt; es muss regularisiert werden.

22

Die Singulärwertzerlegung(3.5) SatzSei A ∈ RK×N mit R = rang A. Dann existieren Singulärwerte σ1, . . . ,σR > 0 und ortho-gonale Matrizen V ∈ RK×R, U ∈ RN×R und eine Zerlegung

A =V ΣUT

mit Σ ∈ RR×R, Σ = diag(σ1, . . . ,σR).

Beweis. Die Matrix AT A∈RN×N ist symmetrisch und positiv semidefinit mit rang A = R.Also existieren eine Orthonormalbasis u1, . . . ,un ∈ RN und Eigenwerte

λ1 ≥ . . .≥ λR > λR+1 = . . .= λN = 0

mit AT Auk = λkuk.Dann gilt AT AU =UΣ2, mit U [1 : N,k] = uk, Σ = diag(

√λ1, . . . ,

√λR). Weiter gilt UTU =

IR, also UT AT AU = Σ2.Definiere V = AUΣ−1 ∈ RK×N , d.h. es ist A =V ΣUT .V ist orthogonal: V TV = Σ−1UT AT AUΣ−1 = Σ−1Σ2Σ−1 = IR.

BemerkungEs gilt

kern A = spanuk | k = R+1, . . . ,N,bild A = spanvk | k = 1, . . . ,R, vk =V [1 : K,k].

Damit ergibt sich die Darstellung

A =V ΣUT =R

∑k=1

σkvkuTk , Ax =

R

∑r=1

σk(uTk xk)vk

(3.6) DefinitionWir definieren die Pseudo-Inverse durch A+ = UΣ−1V T . Es gilt A+ = ∑

Rr=1

1σr

urvTr und

A+y = ∑Rr=1

1σr(vT

r y)ur.

(3.7) LemmaDie Normalengleichung AT Ax = AT b wird durch x = A+b gelöst.

Beweis. Sei dazu x = A+b =UΣ−1V T b. Dann gilt ΣUT x =V T b; durch Erweitern erhaltenwir UΣV TV ΣUT x =UΣV T b, also AT Ax = AT b.

23

Die Tikhonov-Regularisierung

Zwei Probleme bleiben bei den bisherigen Verfahren bestehen:

Problem 1: Wenn eine Aufgabe schlecht konditioniert ist dann werden Datenfehler extremverstärkt. Dies ist zum Beispiel der Fall bei Ax = b mit κ(A) 1.

Problem 2: Wenn eine Aufgabe nicht sachgemäß gestellt ist, ist sie entweder nicht ein-deutig lösbar oder die Lösung ist nicht stetig von den Daten abhängig. Einesolche Situation tritt beispielsweise bei |Ax− b|2 = min! für Kern A 6= 0auf.

Zu F(x)=min! betrachte Fα(x)=F(x)+ α

2 |x|22, α > 0, die Regularisierung von F . Fα(x)=

min! ist für α > 0 sachgemäß gestellt. Die Aufgabe ist, einen Kompromiss zwischengroßem Regularisierungsfehler bei großem α und schlechter Kondition bei kleinem α

zu finden.

(3.8) SatzZu A∈RK×N , b∈RK, α > 0 existiert genau ein xα ∈RN , welches die Tikhonov-Regularisierung

Fα(x) :=12|Ax−b|22 +

α

2|x|22

minimiert. Es giltxα = (AT A+αIN)

−1AT b.

Beweis. Es gilt

Fα(x) =12|Ax−b|22 +

α

2|x|22 =

12(xT AT Ax−2xT Ab+bT b+αxT x),

sodass

∇Fα(x) = AT Ax−AT b+αx,∇

2Fα(x) = AT A+αIN .

Damit ist xα Extremwert von Fα(x), wenn ∇Fα(x) = 0N , also AT Ax+αx = AT b. Folglichist xα einziger kritischer Punkt und da ∇2Fα(xα) positiv definit ist, ist xα ein lokalesMinimum. Weiterhin gilt Fα(x)−→ ∞ für |x|2→ ∞, also ist xα globales Minimum.

(3.9) SatzEs gilt:

limα→0

xα = limα→0

(AT A+αIN)−1AT b = A+b.

Beweis. Sei A =V ΣUT Singulärwertzerlegung mit U = (u1| . . . |uR),V = (v1| . . . |vR), Σ =diag(σ1, . . . ,σR), σ2

r positive Eigenwerte von AT A,UTU = V TV = IR und R = rang A.Dann gilt

AT A =UΣV TV ΣUT =UΣ2UT

AT b =UΣV T b =R

∑r=1

urσr(vTr b)

24

Somit folgt

(AT A+αIN)uk = ∑Rr=1 urσ

2r (u

Tr uk +αuk = (σ2

k +α)uk

also

xα = (AT A+αIN)−1

R

∑r=1

urσr(vTr b)

=R

∑r=1

σr

σ2r +α

(vTr b)ur,

und damit

limα→0

xα =R

∑r=1

1σr

(vTr b)ur =UΣ

−1V T b = A+b.

(3.10) Folgerung1. A+ = lim

α→0(AT A+αIN)

−1AT ist eindeutig bestimmt.

2. Für rangA = N gilt A+ = (AT A)−1AT .

BemerkungA+ ist eindeutig durch die Penrose-Axiome

(A+A)T = A+A, (AA+)T = AA+, A+AA+ = A+, AA+A = A

bestimmt. Allgemein ist (AB)+ 6= B+A+.

BemerkungFür die Kondition der Tikhonov-Regularisierung gilt

κ2(AT A+αIN) = ‖AT A+αIN‖2‖(AT A+αIN)−1‖2

=maxσ2

n +α

minσ2n +α

≤ ρ2(A)+α

α.

Das Diskrepanz-Prinzip

Wir betrachten nun den Fall, dass die rechte Seite b nur ungefähr gegeben ist (z.B. we-gen Messungenauigkeiten). Dazu definieren wir einen sogenannten Noiselevel δ > 0 undzeigen: wenn δ kleiner wird, dann wird das optimale α kleiner. Genauer:Sei x = A+b ∈ Bild(A), also Ax = b, und es gelte |bδ −b|2 < δ < |b|2.Dann existiert zu δ ein α = α(δ ) mit xα = (AT A+αIN)

−1AT bδ und |Axα−bδ |2 = δ , undfür δ → 0 gilt xα −→ x.

Beweis. Es gilt für

Fδ (α) = |Axα −bδ |2−δ2 =

K

∑k=1

α2

(α +σ2k )

2 vTk bδ −δ

2

25

Fδ (0) =−δ 2 < 0, und Fδ (α) ist für wachsendes α streng monoton wachsend.Also existiert α = α(δ ) mit Fδ (α) = 0 und |bδ |2−δ = |bδ |2−|Axα −bδ |2 ≤ |Axα |2.Aus (AT A+αIN)xα = AT bδ folgt αxα = AT bδ −AT Axα und

α|Axα |2 = |A(AT bδ −AT Axα)|2 ≤ |AAT (Axα −bδ )|2 ≤ ‖AAT‖2δ .

Also gilt

α ≤ δ‖AAT‖2

|Axα |2≤ δ‖AAT‖2

|bδ |−δ≤ ‖AAT‖2δ −→ 0 für δ → 0

26

4 Eigenwertberechnung

Kondition des Eigenwertproblems(4.1) SatzSei A ∈ CN×N und λ0 ∈ C ein einfacher Eigenwert von A. Seien x0, y0 ∈ CN normierteEigenvektoren zu λ0 mit Ax0 = λ0x0 und AHy0 = λ0y0.Sei B∈CN×N und A(t) =A+tB. Dann gilt: Es existiert ein ε > 0 und eine differenzierbareFunktion λ : (−ε,ε)→ C mit λ (0) = λ0 so, dass λ (t) Eigenwert zu A(t) ist. Es gilt

λ′(0) =

yH0 Bx0

yH0 x0

(4.2) Folgerung1. Wenn |yH

0 x0| 1, dann ist die Eigenwertberechnung sehr schlecht konditioniert.

2. Für symmetrische Matrizen gilt y0 = αx0 mit α ∈ C und |α| = 1 (bzw. es kannx0 = y0 gewählt werden). Damit ist |yH

0 x0|= 1, und die Eigenwertberechnung ist gutkonditioniert.Somit ist auch die Singulärwertzerlegung gut konditioniert, da AT A symmetrisch ist.

Beweis. Sei χA das charakteristische Polynom zu A und sei λ einfache Nullstelle, alsoχ ′A(λ ) 6= 0. Definiere F(t,λ ) = χA(t)(λ ), d.h. F(0,λ ) = 0, ∂2F2(0,λ ) 6= 0.Betrachte nun F(t,λ (t)) = 0. Nach dem Hauptsatz implizit definierter Funktionen existiertλ : (−ε,ε)→ C mit F(t,λ (t)) = 0 und λ (0) = λ0. λ (t) ist also Eigenwert von A(t).Entsprechend existiert x : (−ε,ε)→ CN mit x(0) = x0. Betrachte A(t)x(t) = λ (t)x(t).Ableiten nach t liefert

A′(t)x(t)+A(t)x′(t) = λ′(t)x(t)+λ (t)x′(t).

Setzt man t = 0, so folgt

Bx0 +Ax′(0) = λ′(0)x0 +λ0x′(0).

Aus yH0 Ax′(0) = (AHy0)

Hx′(0) = λ0yH0 x′(0) folgt yH

0 Bx0 = λ ′(0)yH0 x0.

Problemreduktion(4.3) DefinitionEine Matrix A ∈ RN,N heißt reduzibel, wenn eine Permutationsmatrix P und ein n < Nexistiert mit (PAPT )[n+1 : N,1 : n] = 0, d.h. für B = PAPT gilt

B =

(B[1 : n,1 : n] B[1 : n,n+1 : N]

0 B[n+1 : N,n+1 : N]

)=

(B11 B120 B22

)Sie heißt irreduzibel, wenn keine Permutationsmatrix P existiert, so dass PAPT reduzibelist.

27

BemerkungIm Fall P = IN gilt für reduzible Matrixen A:

1. Aus det(A− tIN) = det(A11− tIn)det(A22− tIN−n) folgt σ(A) = σ(A11)∪σ(A22).

2. A ist regulär genau dann, wenn A11, A22 regulär sind.Ax = b lässt sich wie folgt lösen:

x[n+1 : N] = A−122 b[n+1 : N]

x[1 : n] = A−111 (b[1 : n]−A12x[n+1 : N])

(4.4) DefinitionEine Matrix H ∈ RN×N heißt (obere) Hessenbergmatrix, wenn H[n+ 2 : N,n] = 0N−n−1für n = 1, ...,N−2 gilt.

Eine Hessenbergmatrix ist reduzibel, falls H[n+1,n] = 0 für ein 0 < n < N.Symmetrische Hessenbergmatrizen sind tridiagonal.

(4.5) SatzSei A ∈RN,N . Dann existiert eine orthogonale Matrix Q ∈RN×N , so dass H = QAQT eineHessenbergmatrix ist. Die Berechnung von Q benötigt O(N3) Operationen.

BemerkungIst A symmetrisch, so ist H = QAQT eine symmetrische Tridiagonalmatrix.

Beweis. (Beweis von 4.5) Induktion über N.Für N < 3 ist nichts zu zeigen.Sei nun N ≥ 3: Definiere v ∈ RN mit: v[1] = 0, v[2 : N] = A[2 : N,1]

1.Fall v[3 : N] = 0N−2Setze Q1 := IN , A1 := A.

2.Fall v[3 : N] 6= 0N−2Setze

σ =

−|v|2, v[2]> 0|v|2, v[2]≤ 0

,

w =1

v[2]−σ

(v−σe2

)∈ RN ,

Q1 = IN−βwwT mit β :=2

wT w.

Damit ergibt sich

A1 := Q1AQT1 =

A[1,1] A1[1,2 : N]σ

0N−2A2

mit

A1[1,2 : N] = A[1,2 : N]−β (A[1,2 : N]w[2 : N])w[2 : N]T

A2 = (IN−1−βw[2 : N]w[2 : N]T )A[2 : N,2 : N](IN−1−βw[2 : N]w[2 : N]T ) .

28

Nach Induktionsvoraussetzung existiert eine orthogonale Matrix Q2 ∈ R(N−1)×(N−1) mitQ2[2 : N−1] = 0N−2 (nach Konstruktion), so dass H2 = Q2A2QT

2 eine obere Hessenberg-matrix ist. Setze

Q :=(

1 0TN−1

0N−1 Q2

)Q1 .

Somit folgt

QAQT =

(1 0T

N−10N−1 Q2

)A1

(1 0T

N−10N−1 QT

2

)=

A[1,1] A[1;2 : N]QT2

σ

ON−2H2

= H

Damit ist der Induktionsschritt bewiesen.Zum Aufwand: In jedem Schritt werden O(N2) Operationen benötigt, insgesamt alsoO(N3) Operationen.

Strategie zur Eigenwertberechnung von symmetrischen Matrizen A ∈ RN×N :

1. Transformation in eine Hessenbergmatrix H. Ist A symmetrisch, dann ist H symme-trisch und tridiagonal.

2. Zerlegung in irreduzible Tridiagonalmatrizen

3. Eigenwertberechnung von irreduziblen Tridiagonalmatrizen

(4.6) LemmaEine symmetrische Tridiagonalmatrix A ∈ RN×N ist genau dann irreduzibel, wenn

A[n+1,n] 6= 0 n = 1, . . . ,N−1 .

Beweis. Wir unterscheiden zwei Fälle.

1. Fall Es existiert ein k mit A[k+1,k] = 0.Dann folgt A[k+1 : N,1 : k] = 0 und A ist reduzibel.

2. Fall Es gilt A[n+1,n] 6= 0 für n = 1, . . . ,N−1.Dann gilt für jede Permutationsmatrix P = Pπ

(PπAPTπ )[π(n+1),π(n)] = A[n+1,n] 6= 0

(PπAPTπ )[π(n),π(n+1)] = A[n,n+1] = A[n+1,n] 6= 0

Annahme: Es gilt (PπAPTπ )[k+1 : N,1 : k] = 0. Dann gilt:

π(n)≤ k =⇒ π(n+1)≤ kπ(n)≥ k+1 =⇒ π(n+1)≥ k+1

Das ist ein Widerspruch zur Annahme; A ist irreduzibel.

Ziel: Zeige, dass irreduzible, symmetrische Tridiagonalmatrizen N verschiedene Eigen-werte haben.

29

(4.7) LemmaSei A ∈ RN×N eine symmetrische Tridiagonalmatrix.

Setze Pn(t) = det(A[1 : n,1 : n]− tIn) ∈ Pn und P0(t) = 1. Dann gilt für n = 2, . . . ,N dieDreitermrekursion

Pn(t) = (A[n,n]− t)Pn−1(t)−A[n−1,n]2Pn−2(t)

Beweis. Setze αn := A[n,n], βn := A[n−1,n], damit gilt

A− tIN =

α1− t β2

β2 α2− t . . .. . . . . . βn

βn αn− t

und es folgt mit dem Entwicklungssatz

Pn(t) = (αn− t)det(A[1 : n−1,1 : n−1]− tIn−1)︸ ︷︷ ︸=Pn−1(t)

−β2n det(A[1 : n−2,1 : n−2]− tIn−2)︸ ︷︷ ︸

=Pn−2(t)

(4.8) DefinitionSeien Pn ∈ Pn (n = 1, . . . ,N) Polynome mit reellen Nullstellen λ n

1 ≤ λ n2 ≤ . . .≤ λ n

n .Dann heißt P1, . . . ,Pn eine Sturmsche Kette, wenn

λnk < λ

n−1k < λ

nk+1

für n= 2, . . . ,N, k = 1, . . . ,N−1 gilt. λ nk bezeichnet die k-te Nullstelle des n-ten Polynoms.

(4.9) SatzEine symmetrische irreduzible Tridiagonalmatrix

A =

α1 β2

β2. . . . . .. . . . . . βN

βN αN

∈ RN×N

hat N verschiedene Eigenwerte.

Beweis. A ist symmetrisch, d.h. alle Eigenwerte sind reell.Zeige induktiv, dass P1,P2, . . . ,PN aus 4.7 eine Sturmsche Kette bilden.

n = 2: P1(t) = α1− t hat die Nullstelle λ 11 = α1.

Es gilt

P2(t) = det(

α1− t β2β2 α2− t

)= (α1− t)(α2− t)−β

22

30

Die Nullstellen sind

λ21 =

α1 +α2−√(α1−α2)2 +4β 2

2

2

=⇒ λ21 <

12(α1 +α2−

√(α1−α2)2) =

12(α1 +α2−|α1−α2|)

= minα1,α2 ≤ α1 = λ11

λ22 =

12(α1 +α2 +

√(α1−α2)2 +4β 2

2 )>12(α1 +α2 + |α1−α2|)

= maxα1,α2 ≥ α1 = λ11

Also gilt λ 21 < λ 1

1 < λ 22 .

n→ n+1: Sei λ nk < λ

n−1k < λ n

k+1 für k = 1, . . . ,n−1.Pn−1(t) hat eine Nullstelle λ

n−1k ∈ (λ n

k ,λnk+1). Es gilt Pn−1(λ

nk )Pn−1(λ

nk+1) < 0 (wegen

Vorzeichenwechsel in (λ nk ,λ

nk+1)). Aus 4.7 folgt

Pn+1(λnk ) = (αn+1−λ

nk )Pn(λ

nk )︸ ︷︷ ︸

=0

−β2n Pn−1(λ

nk ) =−β

2n Pn−1(λ

nk )

D.h. es gilt, aufgrund verschiedener Vorzeichen, Pn+1(λnk )Pn−1(λ

nk ) < 0. Weiterhin ist

Pn+1(λnk )Pn+1(λ

nk+1) < 0 für k = 1, . . . ,n− 1. Also existiert mindestens eine Nullstelle

λn+1k+1 ∈ (λ n

k ,λnk+1). Somit existieren n−1 Nullstellen von Pn+1 in (λ n

1 ,λnn ).

Analog (ohne Beweis): Es existieren zwei weitere Nullstellen λn+11 < λ n

1 und

λn+1n+1 < λ n

n .Also: PN(t) hat N verschiedene Nullstellen. Nach Definition von PN sind dies die Eigen-werte von A.

BemerkungSei w(t) := #k ∈ 1, . . . ,N : Pk−1(t)Pk(t)< 0 oder Pk−1(t) = 0. Dann gilt

λNw(t) < t ≤ λ

Nw(t)+1

−‖A‖∞ < λN1

λNN < ‖A‖∞

Damit lassen sich durch Bisektion Eigenwerte einschließen. Bisektion konvergiert nur li-near; es gibt bessere Algorithmen.

Sei A∈RN×N symmetrisch, irreduzibel, mit Eigenwerten λ1, ...,λN und Orthonormalbasisv1, ...,vN aus Eigenvektoren. Dann gilt

V = (v1| . . . |vN) ∈ RN×N ist orthogonal

V T AV = diag(λ1, . . . ,λN)

x =N

∑n=1

(xT vn)vn

Ax =N

∑n=1

(xT vn)λnvn

31

(4.10) Definitionr(A,x) = xT Ax

xT x heißt Rayleigh-Quotient zu A und x ∈ RN \0, und es gilt

r(A,vn) =vT

n Avn

vTn vn

= λn

BemerkungFür alle c 6= 0 gilt r(A,cx) = r(A,x).

(4.11) SatzSei |λ1| = ρ(A) = maxn=1,...,N |λn|, d.h. |λn| < |λ1| für n = 2, ...,N. Dann gilt für allew ∈ RN mit wT v1 > 0:

limk−→∞

r(A,Akw) = λ1 , limk−→∞

1|Akw|2

Akw = v1 .

Beweis. Es gilt

Akw = Ak−1N

∑n=1

(wT vn)λnvn =N

∑n=1

(wT vn)λkn vn = λ

k1

N

∑n=1

(λn

λ1

)k

(wT vn)vn

Es gilt

limk→∞

(λn

λ1

)k

=

1, n = 10, n 6= 1

.

Damit ergibt sich

limk→∞

1λ k

1Akw = (wT v1)v1

und es folgt

limk→∞

r(A,Akw) = limk→∞

r(

A,1

λ k1

Akw)= r(A,(wT v1)v1) = r(A,v1) = λ1

sowie

limk→∞

1|Akw|2

Akw = limk→∞

wT v1

|wT v1|2v1 = v1

Definiere also für k = 1,2, . . .

wk :=1|Akw|

Akw

µk := r(A,wk)

zur Approximation von v1 = limk−→∞

wk und λ1 = limk−→∞

µk.

Als Abbruchkriterium verwendet man das Residuum Awk−µkwk. Ist das sinnvoll?

32

(4.12) Satz (Satz von Weinstein)Sei w ∈ RN , wT w = 1, µ = r(A,w). Dann gilt

minn=1,...,N

|λn−µ| ≤ |Aw−µw|

Beweis. Sei A = ∑λnvnvTn ∈RN×N , µ = r(A,w) = wT Aw

wT w = wT Aw. Aus w = ∑Nn=1(v

Tn w)vn

folgt wT w = ∑(vTn w)2. Somit gilt

|Aw−µw|22 =

∣∣∣∣∣ N

∑n=1

((vT

n w)λnvn−µ(vTn w)vn

)∣∣∣∣∣2

2

=N

∑n=1

(vTn w)2(λn−µ)2

≥ minn=1,...,N

(λn−µ)2N

∑n=1

(vTn w)2

= minn=1,...,N

(λn−µ)2

Vektoriteration

S0) Wähle z0 ∈ RN \0, ε > 0, setze k = 0

S1) wk =1|zk|zk, µk = r(A,wk)

S2) Falls |Awk−µkwk|2 < ε STOP

S3) zk+1 = Awk

S4) Setze k := k+1, gehe zu S1).

Varianten

• In S3): zk+1 = A−1wkDann konvergiert µk gegen den betragskleinsten Eigenwert

• Inverse Iteration mit festem Shift s ∈ R:In S3): zk+1 = (A− sIN)

−1wkµk konvergiert linear gegen den nächsten Eigenwert zu s.

• Inverse Iteration mit sk = µk, d.h. S3) zk+1 = (A−µkIN)−1wk konvergiert kubisch.

(4.13) SatzSei λ = λn ein einfacher Eigenwert, und der Startvektor z0 sei hinreichend nahe bei einemEigenvektor v∈RN zu λ mit vT v= 1. Dann konvergiert die inverse Iteration mit variablemShift kubisch.

33

Beweis. (i) Sei ρ > 0 mit (λ−ρ,λ +ρ)∩σ(A) = λ, d. h. |λ−λ j|> ρ für alle weiterenEigenwerte λ j 6= λ .In S1) definiere wk = wk− (vT wk)v, d. h. wT v = 0. Es gilt

1 = |wk|22 = (vT wk)2 + |wk|22 = (cosφk)

2 +(sinφk)2, φk ∈ [0,2π),

d. h. wk = cosφkv+ sinφkwk mit wk =1|wk|wk.

Zeige: Es gilt |sinφk+1| ≤C|sinφk|3 f alls φk klein genug ist.Aus |sinφ −φ |= O(φ 3) folgt damit die Behauptung |φk+1| ≤ C|φk|3.(ii) Es ist Awk = λ cosφkv+ sinφkAwk. Damit gilt

µk = r(A,wk) = wTk Awk = λ cos2

φk + wTk Awk sin2

φk = λ +(wTk Awk−λ )sin2

φk

Es folgt |µk−λ | ≤ 2‖A‖2 sin2φk.

(iii) Es gilt

zk+1 = (A−µkIN)−1wk =

1λ −µk

cosφkv+ sinφk(A−µkIN)−1wk ,

(A−µkIN)−1wk = ∑

j 6=n(A−µkIN)

−1 (wTk v j)

v j = ∑j 6=n

wTk v j

λ j−µkv j .

Daraus folgt vT (A−µkIN)−1wk = 0 und somit

|zk+1|2 ≥1

|λ −µk||cosφk| .

Mit dem Resultat aus (ii) erhalten wir1

|zk+1|2≤ 1|cosφk|

2‖A‖2 sin2φk

(iv) Sei zk so nahe bei v, dass 2‖A‖2 sin2φk ≤ ρ

2 gilt. Für j 6= n folgt dann

|λ j−µk| ≥ |λ j−λ |− |λ −µk| ≥ ρ−2‖A‖2 sin2φk ≥

ρ

2|cosφk|2 = 1− sin2

φk ≥ 1− ρ

4‖A‖2,∣∣(A−µkI−1

N )wk∣∣2 ≤

2ρ,

wk+1 =1|zk+1|

zk+1 = cosφk+1v+ sinφk+1wk+1 .

Koeffizientenvergleich mit (iii) liefert

|sinφk+1|=|sinφk+1||zk+1|2

∣∣(A−µkIN)−1wk

∣∣2 ≤

2‖A‖2

|cosφk||sinφk|3

2ρ≤ 1

ρ

4‖A‖2√1− ρ

4‖A‖2

|sinφk|3 .

Nun betrachten wir die Vektoriteration mit dem speziellen Anfangsvektor z0 = eN . Damitergibt sich als ersten Rayleigh-Quotient µ0 = A[N,N]. Um nun A− µ0IN möglichst gutkonditioniert zu invertieren, berechenen wir eine QR-Zerlegung QR = A−µ0IN und damitdie nächste Iterierte z1 = R−1QT eN . Da A− µ0IN symmetrisch ist, gilt QR = RT QT , alsoz1 = QR−T eN = R[N,N]−1QeN und somit

zT1 Az1 = R[N,N]−2eT

NQT AQTeN = eTNA1eN zT

1 z1 , A1 = QT AQ = RQ+µ0IN .

Für den Rayleigh-Quotient µ1 = r(A,z1) gilt daher µ1 = A1[N,N]. Wiederholte Anwen-dung von diesem Prinzip ergibt die QR-Iteration mit Shift.

34

QR-Iteration mit Shift Gegeben sei A ∈ RN×N symmetrisch.

S0) Berechne A0 = QAQT tridiagonal (Hessenberg-Transformation).Wähle ε ≥ 0. Setze k = 0.

S1) Falls |Ak[n+1,n]| ≤ ε für ein n:Getrennte Eigenwertberechnung für Ak[1 : n,1 : n] und Ak[n+1 : N,n+1 : N].

S2) Berechne dk =12(Ak[N−1,N−1]−Ak[N,N]) und

µk = Ak[N,N]+dk− sgn(dk)√

d2k +Ak[N−1,N]2

S3) Berechne eine QR-Zerlegung

QkRk = Ak−µkIN

und setze

Ak+1 = RkQk +µkIN

S4) Setze k := k+1, gehe zu S1).

Bemerkung1. Es gilt

Ak+1 = RkQk +µkIN

= QTk Qk(RkQk +µkIN)

= QTk ( QkRk︸ ︷︷ ︸

=Ak−µkIN

+µkIN)Qk

= QTk AkQk,

d.h. σ(Ak+1) = σ(Ak) mit limk→∞ Ak = diag(λ1, . . . ,λN), QQ1Q2 . . .Qk konvergiertgegen die Eigenvektoren.

2. S2) berechnet den Eigenwert von A[N−1 : N,N−1 : N], der näher an A[N,N] liegt.

3. In der Praxis werden etwa 2N-3N Iterationen benötigt.

4. Ist Ak tridiagonal, dann lässt sich die Hessenbergmatrix Qk mit N− 1 Givensrota-tionen bestimmen. Weiterhin ist Ak+1 = RkQk = QT

k AkQk eine symmetrische Hes-senbergmatrix, also tridiagonal.

5. S0) benötigt O(N3), S3) O(N2) Operationen

35

Eigenwert-Abschätzungen(4.14) Satz (Satz von Gerschgorin)Zu A ∈ RN×N sind die Gerschgorin-Kreise durch

Kn =

λ ∈ C : |λ −A[n,n]| ≤ ∑k 6=n|A[n,k]|

, n = 1, ...,N

definiert. Dann gilt

σ(A)⊂N⋃

n=1

Kn .

Beweis. Sei λ ∈ σ(A). Dann existiert ein w ∈ CN \ 0 mit Aw = λw. Also existiert einn ∈ 1, . . . ,N mit

0 6= |w[n]| ≥ |w[k]| , k = 1, . . . ,N .

Damit folgt

(Aw)[n] = A[n,1 : N]w = λw[n] =⇒ |A[n,n]−λ ||w[n]|=

∣∣∣∣∣∑k 6=nA[n,k]w[k]

∣∣∣∣∣=⇒ |A[n,n]−λ | ≤ ∑

k 6=n|A[n,k]| |w[k]|

|w[n]|≤ ∑

k 6=n|A[n,k]|

Somit gilt λ ∈ Kn.

Bemerkung1. Wenn für I ⊂ 1, . . . ,N gilt: ⋃

i∈I

Ki∩⋃i 6∈I

Ki = /0,

dann enthält⋃

i∈I Ki genau #I Eigenwerte (mit Vielfachheiten).

2. Wenn A irreduzibel ist, dann gilt σ(A)⊂ int(⋃N

n=1 Kn).

Beispiel1. Sei

A =

d1 ε ε

ε d2 ε

ε ε d3

, |ε| |dn|.

Dann existiert ein λn mit |dn−λn| ≤ 2ε .

2. Sei

A =

2 1

212 2 1

2. . . . . . . . .

. . . . . . 12

12 2

.

Dann gilt σ(A)⊂ (1,3) und κ2(A)≤ 3.

36

3. Sei

A =

2 −1−1 2 −1

. . . . . . . . .. . . . . . −1−1 2

.

A ist regulär und es gilt σ(A)⊂ (0,4).

(4.15) Satz (Min-Max-Theorem)Sei A ∈ RN×N symmetrisch mit Eigenwerten λN ≤ λN−1 ≤ . . .≤ λ1. Dann gilt

λn = maxdimS=nS⊂RN

minx∈S\0

r(A,x)

Beweis. Sei (v1| . . . |vN) Orthonormalbasis in RN mit A = ∑λnvnvTn .

≤: Setze Sn = spanv1, . . . ,vn, x ∈ Sn; also x = ∑nk=1(x

T vk)vk. Dann gilt

xT Ax =n

∑k=1

λk(xT vk)2 ≥ λn

n

∑k=1

(xT vk)2 = λnxT x

und mit vn ∈ Sn folgt

λn = minx∈Sn

r(A,x)≤ maxdimS=n

minx∈S

r(A,x)

≥: Wähle S ⊆ RN ,dimS = n. Es gilt dim( S︸︷︷︸dimn

∩spanvn, . . . ,vN︸ ︷︷ ︸dimN−n+1

) ≥ 1. Also existiert

ein y ∈ S mit y = ∑Nk=n(y

T vk)vk. Somit gilt

λn ≥ r(A,y)≥ minx∈S\0

r(A,x).

Da S beliebig war, folgt die Behauptung.

BemerkungEs gilt λN+1−n = mindimS=n maxx∈S\0 r(A,x).

37

5 Iterationsverfahren für lineare Gleichungssysteme

Klassische Iterationsverfahren

Sei A∈RN×N und b∈RN . Wir wollen nun das LGS Ax = b iterativ lösen. Dazu betrachtenwir die Komponenten m = 1, . . . ,N:

N

∑n=1

A[m,n]x[n] = b[m].

Wir formen um und erhalten für x[m]:

A[m,m]x[m] = b[m]− ∑n6=m

A[m,n]x[n].

Falls A[m,m] 6= 0 erhalten wir also

x[m] =

(b[m]− ∑

n6=mA[m,n]x[n]

)/A[m,m].

Daraus können wir das Gesamtschritt-Verfahren (Jacobi-Verfahren) ableiten:

S0) Wähle x0 ∈ RN , ε > 0, setze k = 0.

S1) Falls |Axk−b|2 < ε STOP.

S2) Berechne xk+1[m] = (b[m]− ∑n 6=m

A[m,n]xk[n])/A[m,m] für m = 1, ...,N.

S3) Setze k := k+1, gehe zu S1).

Dieses Verfahren kann man mit der Idee abändern, dass bei der Berechnung von xm diexn für n < m ja schon bekannt sind. Dementsprechend kann man auch gleich mit diesenWerten weiterrechnen.Dies führt zum Einzelschritt-Verfahren (Gauß-Seidel-Verfahren):

S0) Wähle x0 ∈ RN , ε > 0, setze k = 0.

S1) Falls |Axk−b|2 < ε STOP.

S2) Berechne xk+1[m] =

(b[m]−

m−1∑

n=1A[m,n]xk+1[n]−

N∑

n=m+1A[m,n]xk[n]

)/A[m,m] für

m = 1, ...,N.

S3) Setze k := k+1, gehe zu S1).

Um die Konvergenz von Iterationsverfahren zu untersuchen formulieren wir sie in Matrix-form. Beachte, dass für invertierbare Matrizen B ∈ RN,N die Aufgabe Ax = b äquivalentist zu BAx = Bb. Ein solches B heißt Vorkonditionierer von A, da B möglichst so gewähltwird, dass BA eine kleinere Kondition als A hat. Wir formulieren dies um in eine Fixpunk-taufgabe, also x = Bb−BAx+ x und erhalten so

x = (I−BA)x+Bb = x+B(b−Ax) .

38

Wir bestimmen nun B für das Jacobi- und das Gauß-Seidel-Verfahren. Dazu zerlegen wir

A = L+D+R

mit der strikt unteren Dreiecksmatrix L = lower(A), der Diagonalmatrix D = diag(A) undder strikt oberen Dreiecksmatrix R = upper(A). Damit folgt für diese beiden Verfahren:

GesamtschrittverfahrenEs gilt:

Dxk+1 = b− (L+R)xk = b− (L+D+R)xk +Dxk.

Somit ist D(xk+1− xk) = b−Axk und schließlich

xk+1 = xk +D−1(b−Axk),

also BJ = D−1.

EinzelschrittverfahrenEs gilt

Dxk+1 = b−Lxk+1−Rxk,

woraus (D+L)xk+1 = b−Rxk = b− (L+D+R)xk +(L+D)xk = b−Axk +(D+L)xk

folgt und somitxk+1 = xk +(D+L)−1 (b−Axk),

also BGS = (D+L)−1.

(5.1) SatzSeien A,B ∈ RN×N mit ρ(I−BA)< 1.

Dann ist A invertierbar und für alle b ∈ RN , x0 ∈ RN konvergiert die Iteration

xk+1 = xk +B(b−Axk) k = 0,1,2, . . . ,

so dass gilt

limk→∞

xk = A−1b. und A−1 = B∞

∑k=0

(IN−AB)k .

(5.2) SatzSei K ∈ RN×N und ε > 0. Dann existiert eine Norm ‖ · ‖ mit ‖K‖ ≤ ρ(K)+ ε .

Beweis. Aus der linearen Algebra wissen wir, dass eine reguläre Matrix U ∈ CN×N exi-stiert, sodass

U−1KU = diag(λ1, . . . ,λN)+R

mit einer strikt oberen Dreiecksmatrix R, wobei λn (n = 1, . . . ,N) die Eigenwerte von Ksind. Zu δ = ε

ε+‖R‖∞∈ (0,1] definiere D = diag(1,δ 1,δ 2, . . .). Damit gilt

D−1 = diag(1,δ−1,δ−2, . . .) und

D−1RD = (δ n−mR[m,n])m,n=1...,N

=

0 δR[1,2] δ 2R[1,3] . . .0 δR[2,3] . . .

0 . . .

39

Somit folgt‖D−1RD‖∞ ≤ δ‖R‖∞ = ε− εδ = ε (1−δ )︸ ︷︷ ︸

∈[0,1)

< ε . (1)

Nun definiere die Vektornorm |x|= |D−1U−1x|∞ und erhalte

‖K‖= supx 6=0

|Kx||x|

= supx 6=0

|D−1U−1Kx|∞|D−1U−1x|∞

= supy6=0

|D−1U−1KUDy|∞|y|∞

= ‖D−1(diag(λn)+R)D‖∞

≤ ‖diag(λn)‖∞︸ ︷︷ ︸=ρ(K)

+‖D−1RD‖∞

(1)≤ ρ(K)+ ε.

Beweis. (Beweis von 5.1) Zu einer Matrix K = IN −BA wähle | · |, ‖ · ‖ wie in 5.2 zu ε =1−ρ(K)

2 > 0. Es gilt ‖K‖ ≤ ρ(K)+ ε = 1− ε

2 < 1. Damit ist A invertierbar; die Inverse ist

mit der Neumannschen Reihe A−1 =∞

∑k=0

(IN−BA)kB darstellbar.

Für x = A−1b gilt dann

xk+1− x = xk +B(b−Axk)− x = xk− x+B(Ax−Axk)

= xk− x+BA(x− xk) = (IN−BA)︸ ︷︷ ︸=K

(xk− x).

Und somit

|xk+1− x| ≤ ‖IN−BA‖|xk− x| ≤ ‖IN−BA‖k+1|x0− x| −→ 0 (k→ ∞).

BemerkungFalls ρ(IN−BA)≥ 1, dann existiert q ∈ RN mit

|(IN−BA)q|2 = ρ(IN−BA)|q|2 ≥ |q|2 6= 0

Wähle b = 0, x0 = q, dann konvergiert (xk) nicht gegen 0N .

(5.3) SatzSei A = L+D+LT ∈RN×N symmetrisch und positiv definit. Dann konvergiert das Gauß-Seidel Verfahren mit B = (L+D)−1 in der Energienorm |x|A :=

√xT Ax.

Beweis. Sei dazu A = L+D+LT mit L = lower(A), D = diag(A) und K = IN−BA, wobeiB = (D+L)−1. Zeige nun ‖K‖A = sup

x 6=0

|Kx|A|x|A < 1, dann gilt ρ(K)≤ ‖K‖A < 1.

Es gilt

|Kx|2A = (x−BAx)T A(x−BAx)= xT (A−ABA−ABT A+ABT ABA)x= xT Ax− xT A(BT +B−BT AB)Ax.

40

Weiter giltA+D = L+D+D+LT = B−1 +B−T ,

sodass

BT +B−BT AB = BT +B−BT (A+D−D)B= BT +B+BT DB−BT (B−1 +B−T )B= BT DB .

Da AT BT DBA positiv definit ist, existiert ein α > 0 mit xT (AT BT DBA)x≥ αxT Ax. Es giltalso

|Kx|2A = |x|2A− xT (ABT DBA)x≤ |x|2A−α|x|2A ≤ (1−α)|x|2A

und somit

‖K‖A = supx 6=0N

|Kx|A|x|A

= sup|x|A=1

|Kx|A ≤ 1−α < 1 .

Bemerkung1. Häufig wird die symmetrische Variante verwendet.

2. Beim SOR1-Verfahren ist B = ω(D−ωL)−1 mit ω ∈ (1,2).

(5.4) DefinitionSei A ∈RN×N . Die Matrix A heißt stark diagonaldominant, wenn sie diagonaldominant ist(|A[n,n]| ≥ ∑k 6=n |A[n,k]|, n = 1, . . . ,N) und wenn für ein j ∈ 1, . . . ,N,|A[ j, j]|> ∑k 6= j |A[ j,k]| gilt.

(5.5) SatzSei A ∈ RN×N stark diagonaldominant und irreduzibel. Dann gilt:

a) A ist regulär und das Jacobi-Verfahren konvergiert.

b) Falls A[n,n]> 0, dann ist A positiv definit.

c) Falls A[n,n]> 0, A[n,k]≤ 0(n 6= k) ist, dann gilt A−1[n,k]≥ 0.

(5.6) LemmaWenn A irreduzibel ist, dann ist der Matrixgraph Γ = (k,n) : A[k,n] 6= 0 zusammenhän-gend: zu jedem Paar n 6= j existiert eine Folge j = j0, j1, . . . , jR = n mitA[ j1, j0] 6= 0, A[ j2, j1] 6= 0, . . . , A[ jR, jR−1] 6= 0.

Beweis. (nur skizziert) Ohne Einschränkung sei j < n.Definiere I = k : es ex. ein Weg in Γ von j zu k.Annahme: n 6∈ I; ohne Einschränkung sei I = 1, . . . ,K.Dann gilt A[m,k] = 0 für k ∈ I, k ≤ K, m > K.Es folgt: A ist irreduzibel mit A[K +1 : N,1 : K] = 0. Das ist ein Widerspruch.

1Successive Over-Relaxation, dt. Überrelaxation

41

Beweis. (Beweis von 5.5) Sei A irreduzibel. Dann gilt ∑Nk=1 |A[n,k]| > 0, mit 5.4 folgt

|A[n,n]|> 0 für n = 1, . . . ,N. Somit sind B = D−1, K = IN−D−1A wohldefiniert.Zu zeigen ist nun ρ(K)< 1. Sei dazu µ ∈C Eigenwert mit Eigenvektor w∈CN \0N undKw= µw; ohne Einschränkung sei |w|∞ = 1= |w[n]| für ein n∈ 1, . . . ,N. Aus µw=Kwfolgt

|µ||w[n]|=

∣∣∣∣∣ N

∑k=1

K[n,k]w[k]

∣∣∣∣∣≤ |A[n,n]|−1

∑k 6=n|A[n,k]|

≤ 1

Annahme: |µ|= 1. Zu j wähle j = j0, j1, . . . , jk = n mit A[ j1, j] 6= 0. Es folgen

|w[ j]|= |µw[ j]|= |(Kw)[ j]| ≤ |A[ j, j]|−1∑k 6= j|A[ j,k]| ≤ 1

und

|w[ j1]|= |µw[ j1]| ≤ |A[ j1, j1]|−1

∣∣∣∣∣∑k 6= j1

|A[ j1,k]w[k]|

∣∣∣∣∣≤ |A[ j1, j1]|−1

∣∣∣∣∣ ∑k 6= j1, j

|A[ j1,k]|+ |A[ j1, j1]w[ j]|

∣∣∣∣∣< |A[ j1, j1]|−1

∑k 6= j1

|A[ j1,k]|

≤ 1

Induktiv folgt |w[ jr]|< 1, also |w[n]|< 1; dies ist ein Widerspruch zur Annahme.

zu a) Aus ρ(K) = ρ(IN−D−1A)< 1 folgt (IN−K)−1 = ∑k≥0 Kk, also A−1 = KkD−1.

zu b) Mit dem Satz von Gerschgorin und der Diagonaldominanz von A folgtσ(A) ⊂ λ ∈ C : |λ −A[n,n]| ≤ |A[n,n]|, n = 1, . . . ,N. Da A invertierbar ist, folgt0 6∈ σ(A); es ist also Reσ(A)> 0, somit ist A positiv definit.

zu c) Aus K = IN−D−1A = D−1(D−A) folgt K[n,k]≥ 0.A−1 = ∑KkD−1 zeigt A−1[n,k]≥ 0.

42

Krylovraum–Verfahren

Sei B ∈RN×N ein Vorkonditionierer zu A ∈RN,N . Wir betrachten wieder die lineare Itera-tion

xk+1 = xk +B(b−Axk) = xk +Brk,

wobei rk das Residuum rk = b−Axk sei. Für das Residuum folgt die Gleichung

rk+1 = b−Axk+1 = b−A(xk +Brk) = (IN−AB)rk,

und somitrk = (IN−AB)kr0.

(5.7) DefinitionZu C ∈ RN×N und d ∈ RN heißt Kk(C,d) := spand,Cd, . . . ,Ck−1d ⊂ RN der k-te Kry-lovraum. Es gilt:

a) dimKk(C,d)≤ k

b) Kk(C,d) = P(C)d : P ∈ Pk

c) xk− x ∈Kk(BA,x0− x)

d) xk ∈Kk(AB,r0)

e) xk+1 ∈ x0 +Kk(BA,Br0)

(5.8) LemmaSei Ax = b und x0 ∈ RN Startwert, r0 = b−Ax0, A, B regulär. Falls dimKk(AB,r0) < k)ist, dann gilt

x ∈ x0 +Kk−1(BA,Br0)

Beweis. Seien r0,ABr0, . . . ,(AB)k−1r0 linear abhängig. Dann existieren α0, . . . ,αk−1 ∈ Rmit α0r0+α1ABr0+ . . .+αk−1(AB)k−1r0 = 0. Ohne Einschränkung sei α0 = 1. Dann gilt

b−Ax0 +α1ABr0 + . . .+αk−1(AB)k−1r0 = 0

=⇒ b = A(x0−α1Br0− . . .−αk−1(BA)k−2Br0)︸ ︷︷ ︸=x

Auf folgender Idee basieren die Krylovraum-Verfahren:

(1) Wähle ein geeignetes Skalarprodukt in RN mit zugehöriger Norm.

(2) Konstruiere eine Orthonormalbasis v1, . . . ,vk von Kk bezüglich des gewählten Skalar-produktes.

(3) Approximiere x = A−1b mit minimalem Fehler (bzw. minimalem Residuum) inx0 +Kk.

43

Gram-Schmidt-Verfahren

Wir suchen eine Orthonormalbasis bzgl. eines Skalarprodukts 〈·, ·〉 bzw. Norm |x|=√〈·, ·〉

des oben definierten Krylovraumes. Dazu bietet sich zunächst das Gram-Schmidt-Verfahrenan. Die ersten zwei Schritte des Krylovraumverfahrens lauten also

S0) Wähle x0 ∈ RN , ε > 0. Berechne r0 = b−Ax0, z1 = Br0, h10 = |z1| und v1 = 1h10

z1

(falls |h10|> ε).

Setze k = 1.

S1) Berechne

wk = BAvk

zk+1 = wk−k

∑j=1

h jkv j mit h jk = 〈v j,wk〉

vk+1 =1

hk+1,kzk+1 mit hk+1,k = |zk+1|.

Dann ist v1, ...,vk eine Orthonormalbasis des Krylovraums

Kk(BA,Br0) = spanv1, ...,vk= spanw1, ...,wk= spanz1, ...,zk

Es ist |vk|= 1 und h21〈v2,v1〉= 〈z2,v1〉= 〈w1,v1〉−h11 = 0.Induktiv folgt 〈vk,v j〉= 0 für j < k.

Wir schreiben BAvk = wk = zk+1 +∑kj=1 h jkv j =

k+1∑j=1

h jkv j, also

BAVk =Vk+1Hk

mit Vk = (v1| . . . |vk) ∈ RN×k und Hk = (h jm) ∈ Rk+1,k.Beachte, dass Hk obere Hessenbergform hat.

BemerkungFalls hk+1,k = 0 ist, dann ist wk = BAvk ∈ spanv1, . . . ,vk.Es gilt dann Kk+1(BA,Br0) = Kk(BA,Br0).

44

GMRES-Verfahren

Für das GMRES2-Verfahren wähle 〈v,w〉V = vT w. Somit gilt V Tk Vk = Ik. Dieses Verfahren

baut auf folgender Beobachtung auf:

(5.9) SatzEs gilt

minz∈x0+Kk(BA,Br0)

|B(b−Az)|2 = miny∈Rk|h10e1−Hky|2.

mit e1 = (1,0, . . . ,0)T ∈ Rk+1, h10 = |Br0|2, Hk ∈ Rk+1,k.

Beweis. Es gilt

minz∈x0+Kk(BA,Br0)

|B(b−Az)|2 = miny∈Rk|B(b−A(x0 +Vky))|2

= miny∈Rk|Br0−BAVky|2

= miny∈Rk|h10v1−Vk+1Hky|2 = min

y∈Rk|Vk+1(h10e1−Hky)|2

= miny∈Rk|h10e1−Hky|2

Algorithmus für das GMRES-Verfahren:

S0) Wähle x0 ∈RN , ε > 0. Berechne r0 = b−Ax0, z1 = Br0, h10 = |z1|2 und v1 = 1h10

z1.Setze k = 1.

S1) Berechne wk =BAvk, zk+1 =wk−∑kj=1 h jkv j, h jk =(wk)T v j, vk+1 = 1

hk+1,kzk+1, hk+1,k =

|zk+1|. (D.h. BAVk =Vk+1Hk.)

S2) Berechne yk ∈ Rk mitρk = |h10e1−Hkyk|2 = min!

Dabei ist Hk = (h jm) j=1,...,k+1, m=1,...,k ∈ Rk+1,k.

S3) Wenn ρk < ε , setze

xk = x0 +k

∑j=1

ykjv

j

und STOP.

S4) Setze k := k+1 und gehe zu S1).

Bemerkung(1) Das Ausgleichsproblem in S2) ist effizient lösbar: berechne eine QR-Zerlegung von

Hk ∈ R(k+1)×k mit k Givensrotationen.

(2) Ist |B(b − Axk)|2 = |Brk|2 = ρk, dann gilt rk|2 ≤ ‖B−1‖2ρk und es folgt|x− xk| ≤ ‖(BA)−1‖2ρk

2generalized minimal residual

45

(3) Aus ρk > 0 folgt rk 6= 0, also xk 6= x. Somit ist dimKk(BA,Br0) = k, es gilt alsohk+1,k 6= 0.Das GMRES-Verfahren ist wohldefiniert.

(4) Das Gram-Schmidt-Verfahren ist numerisch nicht stabil (beginne nach kmax wieder beiS0)).

(5.10) SatzSei BA positiv definit mit zT (BA)z ≥ αzT z, α > 0, und sei ‖BA‖2 ≤C. Dann konvergiertdas GMRES-Verfahren, und es gilt

|xk− x|2 ≤ κ2(BA)

√1− α2

C2

k

|x0− x|

Beweis. Es ist

Brk = B(b−Axk) = B(b−A(x0 +Vkyk))

= B(r0−AQk(BA)Br0) (Qk ∈ Pk−1)

= (IN−BAQk(BA))Br0

= Pk(BA)Br0

mit Pk(t) = 1− tQk(t), d.h. Pk ∈ Pk mit P(0) = 1. Es gilt

|Brk|2 = minP∈Pk,P(0)=1

|P(BA)Br0|2

≤∣∣∣∣(IN−

α

C2 BA)k

Br0∣∣∣∣2

(√1− α2

C2

)k

|Br0|2,

denn ∣∣∣∣(IN−α

C2 BA)k

z∣∣∣∣22= zT z− α

C2 zT BAz− α

C2 (BAz)T z+α2

C2 |BAz|22

≤ zT z−2α2

C2 zT z+α2

C2 |z|22

=

(1− α2

C2

)|z|22

Damit folgt

|xk− x|2 = |A−1rk|2 = |A−1B−1Brk|2≤ ‖A−1B−1‖2|Brk|2

≤ ‖(BA)−1‖2

(√1− α2

C2

)k

|Br0|2

≤ ‖AB‖2|x− x0|2

46

Bemerkung1. α ist der kleinste Eigenwert von 1

2(BA+AT BT ).

2. Falls A, B symmetrisch sind, ist κ2(BA) = Cα

.

3. Falls A, B symmetrisch und positiv definit sind existiert eine Abschätzung mit√

κ2(BA).

Das cg-Verfahren

Seien A,B∈RN×N symmetrisch und positiv definit und wähle als Skalarprodukt das Ener-gieskalarprodukt 〈v,w〉A = vT Aw mit zugeordneter Energienorm |x|A =

√〈x,x〉A. Bestim-

me xk mit dem kleinsten Fehler in der Energienorm; genauer: zum Startwert x0 berechner0 = b−Ax0, Kk(BA,Br0) und eine Orthonormalbasis Vk = (v1| . . . |vk) mit V T

k AVk = Ik.Berechne yk ∈ Rk und xk = x0 +Vkyk mit

|xk− x|A ≤ |x0 +Vky− x|A ∀y ∈ Rk

(5.11) SatzFür yk =V T

k r0 und xk = x0 +Vkyk gilt

|xk− x|A ≤ |x0 +Vky− x|A ∀y ∈ Rk

Beweis. Es gilt

F(y) =12|x0−Vky− x|2A

=12(x0−Vky− x)T A(x0−Vky− x)

=12(x0−Vky− x)T (AVky− r0)

=12

yTV Tk AVky− yTV T

k r0− 12(x0− x)T r0

also impliziert F(yk) = min! dass ∇F(yk) = 0 ist und somit yk−V Tk r0 = 0.

Das Ziel ist es, einen Algorithmus zu entwerfen, in welchem nicht alle k Vektoren abge-speichert werden.Eine erste Version ist gegeben durch:

S0) Wähle x0, ε > 0, definiere r0 = b−Ax0, w0 = z0 =Br0, h10 = |z0|A, v1 = 1h10

z0. Setzek = 1.

S1) Falls |rk−1|< ε: Stop.

S2) Berechne

wk+1 = BAvk

zk+1 = wk+1−k

∑j=1

h jkv j, h jk = (v j)T Awk+1

vk+1 =1

hk+1,kzk+1, hk+1,k = |zk+1|A

47

S3) Berechne

xk+1 = xk +((r0)T vk+1

)vk+1

rk+1 = rk− (r0)T vk+1Avk+1

S4) Setze k := k+1 und gehe zu S1)

Beobachtung Aus hk+1,kvk+1 = zk+1 =BAvk−∑kj=1 h jkv j folgt Vk+1Hk =BAVk mit Vk =

(v1| . . . |vk) und Hk[ j,n] = h jn symmetrischer Hessenbergmatrix, denn es gilt

Hk[ j,k] = h jk = 〈BAvk,v j〉A =(

BAvk)T

Av j = (vk)T (ABA)v j = hk j

Somit ist h jk = 0 für j = 0, . . . ,k−2 und es gilt

zk+1 = wk+1−hkkvk−hk−1,kvk−1

Im k-ten Schritt werden v1, . . . ,vk−2 nicht mehr benötigt.

(5.12) LemmaEs gilt 〈xk− x,v j〉A = 0 = (rk)T v j für j = 1, . . . ,k.

Beweis. Es gilt

〈xk− x,v j〉= 〈x0 +Vkyk− x,v j〉A= 〈Vkyk,v j〉A−〈x− x0,v j〉A

=k

∑n=1

yk[n]〈vn,v j〉A− (r0)T v j

= yk[ j]− (r0)T v j

= 0

(5.13) FolgerungFür j < k gilt

〈Brk,v j〉A = 〈BA(x− xk),v j〉A= (x− xk)T ABAv j

= 〈x− xk,BAv j〉A= 0

Also giltBrk = 〈Brk,vk+1〉Avk+1 + 〈Brk,vk〉Avk (2)

(5.14) LemmaSei dk = 〈Brk−1,vk〉Avk, dann gilt

xk = xk−1 +αkdk

dk+1 = Br0 +ρk

ρk−1dk

mit ρk = (Brk)T rk und αk =ρk−1|dk|2A

.

48

Beweis. Für k = 1 gilt d1 = Br0. Weiter

(Brk)T rk = (dk+1)T rk

= 〈dk+1,x− xk〉A= 〈dk+1,x− x0〉A= (dk+1)T r0

Also gilt

xk = xk−1 +((r0)T vk

)vk = xk−1 +

(r0)T dk

|dk|2Adk = xk−1 +αkdk

Es gilt

Brk = dk+1 +1|dk|2A

〈Brk,dk〉Adk

und schliesslich

αk〈Brk,dk〉A = (Brk)T (αkAdk) = (Brk)(rk−1− rk) =−(Bk)T rk =−ρk

Der Algorithmus für das cg-Verfahren lautet somit

S0) Wähle x0, r0 = b−Ax0, d1 = y0 = Br0, ρ0 = (y0)T r0, ε > 0. Setze k := 0.

S1) Falls√

ρk < ε: Stop

S2) Setze k := k+1 und berechne

uk = Adk

αk =ρk+1

(uk)T dk

xk = xk−1 +αkdk

rk = rk−1−αkuk

yk = Brk

ρk = (yk)T rk

dk+1 = yk +ρk

ρk−1dk

Gehe zu S1)

(5.15) SatzFür das cg-Verfahren gilt die Fehlerabschätzung

|xk− x|A ≤ 2

(√κ(BA)−1√κ(BA)+1

)k

|x0− x|A.

49

(5.16) Satz (ohne Beweis)Es gilt

minP∈Pk,P(0)=1

maxt∈[a,b]

|P(t)| ≤

ba −1√ba +1

k

Beweis. (Beweis von 5.15) Es gilt

|x− xk|A = miny∈Rk|x0 +Vky− x|A

= minQ∈Pk−1

|x0−Q(BA)Br0− x|A r0 = A(x− x0)

= minQ∈Pk−1

|(IN−Q(BA)BA)(x0− x)|A P(t) = 1− tQ(t)

= minP∈Pk,P(0)=1

|P(BA)(x0− x)|A︸ ︷︷ ︸≤‖P(BA)‖A|x0−x|A

Behauptung: ‖P(BA)‖A ≤maxt∈σ(BA) |P(t)|Aus A = LLT folgt σ(BA) = σ(BLLT ) = σ(LT BL), also ‖P(BA)‖A = ‖P(LT BL)‖2. Somitgilt

‖P(BA)‖A = ‖P(LT BL)‖2 = maxµ∈σ(P(LT BL))

|µ|= maxλ∈σ(LT BL)

|P(λ )|

50

6 Iterative Lösungsverfahren für nichtlineare Gleichungs-systeme

Wir untersuchen in diesem Kapitel das Newton-Verfahren. Sei dazu F : D→ RN stetigdifferenzierbar für eine offene Menge D ⊂ RN . Für eine Nullstelle x∗ ∈ D von F undx0 ∈ D gilt dann:

0N = F(x∗) = F(x0)+ JF(x0)(x∗− x0)+RF(x∗,x0)

mit |RF (x∗,x0)||x∗−x0| → 0 für x0 → x∗. Falls 0N ≈ F(x0)+ JF(x0)(x∗− x0) gilt und falls JF(x0)

regulär ist, folgt −JF(x0)−1F(x0) ≈ x∗− x0, d. h. x∗ ≈ x0− JF(x0)−1F(x0) =: φ(x0) mitφ(x) = x− JF(x)−1F(x).Insbesondere ist x∗ ein Fixpunkt von φ(x) := x−JF(x)−1F(x). Das entsprechende Fixpunkt-Verfahren ist die Newton-Iteration xk+1 = φ(xk).

Bemerkung1. Die Konvergenz, bzw. Lösung, des Newtonverfahrens hängt vom Startwert x0 ab.

2. Das Newtonverfahren konvergiert im allgemeinen nur lokal, d. h. x0 muss nahe beider Nullstelle x∗ liegen.

(Approximatives) NewtonverfahrenSei F : D→ RN mit D⊂ RN gegeben.

S0) Wähle x0 ∈ D, ε > 0, setze k = 0

S1) Falls |F(xk)|< ε: STOP (Konvergenz)

S2) Wähle Bk ≈ JF(xk) und löse Bkdk =−F(xk)

S3) Setze xk+1 = xk +dk.Falls xk+1 6∈ D: STOP (Divergenz)

S4) Setze k := k+1, gehe zu S1)

(6.1) SatzSei D ⊂ RN konvex, F : D→ RN stetig differenzierbar, x∗ ∈ D Nullstelle von F und B ∈RN×N . Falls ρ(IN −BJF(x∗)) < 1, dann konvergiert die Fixpunktiteration xk+1 = φ(xk),mit φ(x) = x−BF(x), linear gegen x∗, d. h. es existiert ein q ∈ (0,1) mit

|xk− x∗| ≤ qk|x0− x∗| .

(6.2) Satz (Banachscher Fixpunktsatz)Sei D⊂ RN konvex und φ : D→ D kontrahierend, d. h. es existiert q ∈ (0,1) mit

|φ(z)−φ(y)| ≤ q|z− y| für y,z ∈ D .

Dann gilt für alle x0 ∈ D und xk+1 = φ(xk), k = 0,1, . . .:

1. xk ist Cauchyfolge mit Grenzwert x∗ ∈ D und x∗ ist der einzige Fixpunkt von φ in D

51

2. |xk− x∗| ≤ qk

1−q |x1− x0|

3. |xk− x∗| ≤ q1−q |x

k− xk−1|

Beweis. Zu 1. Für k,n≥ 1 gilt:

|xk+n− xk|=

∣∣∣∣∣ n

∑j=1

xk+ j− xk+ j−1

∣∣∣∣∣≤ n

∑j=1|xk+ j− xk+ j−1|︸ ︷︷ ︸≤q|xk+ j−1−xk+ j−2|

≤n

∑j=1

q j−1+k|x1− x0| ≤ qk|x1− x0|∞

∑j=1

q j =qk

1−q|x1− x0| .

xk ist also eine Cauchyfolge in D; es existiert x∗ = limk→∞ xk ∈ D und es gilt

φ(x∗) = φ

(limk→∞

xk)= lim

k→∞φ(xk) = lim

k→∞xk+1 = x∗

x∗ ist eindeutig. Sei dazu x∗∗ ∈ D mit φ(x∗∗) = x∗∗. Dann gilt

|x∗− x∗∗|= |φ(x∗)−φ(x∗∗)| ≤ q|x∗− x∗∗|

Es folgt x∗ = x∗∗.Zu 2. und 3. Es gilt

|x∗− xk|=

∣∣∣∣∣ ∞

∑n=k

xn+1− xn

∣∣∣∣∣≤ ∞

∑n=k|xn+1− xn| ≤ |xk− xk−1|

∑n=k

qn−k+1 = |xk− xk−1| q1−q

≤ qk−1|x1− x0| q1−q

.

Beweis. (Beweis von 6.1) Es gilt: JF ist stetig, es existiert also ein δ > 0 mit

‖BJF(x)−BJF(x∗)‖ ≤ε

2für x ∈ D0 = z ∈ D : |z− x∗| ≤ δ .

(i) Zeige: φ(x) = x−BF(x) ist kontrahierend mit q = 1− ε

2 .Zu y,z ∈ D0 definiere ϕ(t) = F((1− t)z + ty); es gilt ϕ ′(t) = JF((1− t)z + ty)(y− z).Weiter gilt

F(y)−F(z) = ϕ(1)−ϕ(0) =∫ 1

0ϕ′(t)dt =

∫ 1

0JF((1− t)z+ ty)(y− z)dt .

Es folgt

φ(y)−φ(z) = (y− z)−B(F(y)−F(z)) =∫ 1

0(IN−BJF((1− t)z+ ty))(y− z)dt

und damit

|φ(y)−φ(z)| ≤∫ 1

0‖IN−BJF(

=:w︷ ︸︸ ︷(1− t)z+ ty)‖|y− z|dt ≤ q|y− z| ,

52

denn es gilt die Abschätzung

‖IN−BJF(w)‖ ≤ ‖IN−BJF(x∗)‖︸ ︷︷ ︸≤1−ε

+‖BJF(x∗)−BJF(w)‖︸ ︷︷ ︸≤ ε

2

≤ 1− ε

2= q .

(ii) Zeige: Aus x ∈ D0 folgt φ(x) ∈ D0.Es ist F(x∗) = 0N ; es folgt φ(x∗) = x∗ und |φ(x)− x∗| = |φ(x)−φ(x∗)| ≤ q|x− x∗| ≤ δ .Damit folgt φ(x) ∈ D0.

(6.3) LemmaSei P(t) = α−β t + γ

2t2 mit α,β ,γ > 0, β 2−2αγ > 0. Dann gilt:Das Newtonverfahren mit t0 = 0, tk+1 = tk−P′(tk)−1P(tk) konvergiert quadratisch gegendie kleinste Nullstelle t∗ von P mit

0 = t0 < t1 < .. . < tk < tk+1 = tk +γ

2(tk− tk−1)

2

β − γtk< t∗ und

|tk+1− t∗|< 2γ

1β − γt∗

|tk− t∗|2

Beweis. Es ist t1 = t0−P′(t0)−1P(t0) = 0+ β−1α = α

β≤ 2α

β+√

β 2−2αγ= t∗. Weiter gilt

P′(t) =−β + γt, also P′(t1)< P′(t∗)< 0.Zeige induktiv: tk+1 < t∗ (also P′(tk+1)< 0).Für k = 1 ist nichts zu zeigen. Betrachte den Schritt k→ k+1. Es gilt

tk = tk−1−α−β tk−1 +

γ

2t2k−1

−β + γtk−1

also (tk− tk−1)(β − γtk−1) = α−β tk−1 +γ

2t2k−1. Es ergibt sich

γ

2t2k − γtktk−1 +

γ

2t2k−1 = α−β tk +

γ

2t2k ,

also γ

2(tk− tk−1)2 = P(tk). Damit folgt

tk+1 = tk−P(tk)P′(tk)

= tk +γ

2(tk− tk−1)

2

β − γtk.

Zeige nun: tk+1 < t∗. Es gilt

P′(tk)(t∗− tk+1) = P′(tk)(t∗− tk)+P(tk)−P(t∗)

=∫ t∗

tk

(P′(tk)−P′(s)

)ds =

∫ t∗

tk

∫ tk

sP′′(u)︸ ︷︷ ︸≡γ

duds =∫ t∗

tkγ(s− tk)ds

2(t∗− tk)2

Aus P′(tk)< 0 folgt damit t∗− tk+1 < 0. Also gilt auch

|t∗− tk+1| ≤1

|P′(tk)|γ

2|t∗− tk|2 ≤

1|P′(t∗)|

γ

2|t∗− tk|2 .

53

(6.4) Satz (Satz von Newton-Kantorovich)Sei D ⊂ RN offen, F : D→ RN stetig differenzierbar und x0 ∈ D. Gelten für α,β ,γ ∈ Rdie Bedingungen

a) |F(x0)| ≤ α ,

b) |JF(x0)y| ≥ β |y| ∀y ∈ RN ,

c) U := U(x0, 2α

β) =

z ∈ RN : |z− x0| ≤ 2α

β

⊂ D,

d) ‖JF(y)− JF(z)‖ ≤ γ|y− z| ∀y,z ∈ U ,

e) 2αγ < β 2

dann ist das Newtonverfahren xk+1 = xk− JF(xk)−1F(xk) wohldefiniert und konvergiertquadratisch gegen eine Nullstelle x∗ ∈ U von F mit

|x∗− x0| ≤ 2α

β +√

β 2−2αγ.

Beweis. Idee: Wähle P(t) = α−β t− γ

2t2 und definiere t0 = 0, tk+1 = tk− P(tk)P′(tk)

und zeige

f) |JF(xk)y| ≥ (β − tky)|γ| ∀y ∈ RN

g) |xk+1− xk| ≤ tk+1− tk

Dann folgt aus f), dass JF(xk) ist regulär ist und damit ist xk+1 wohldefiniert.(i) Zeige für y,z ∈ U : |F(y)−F(z)− JF(z)(y− z)| ≤ γ

2 |y− z|2.Es gilt ϕ(λ ) = F((1−λ )z+λy), λ ∈ (0,1), also ϕ ′(λ ) = JF((1−λ )z−λy)(y− z).Weiterhin gilt

F(y)−F(z)− JF(z)(y− z) = ϕ(1)−ϕ(0)−ϕ′(0) =

∫ 1

0

(ϕ′(λ )−ϕ

′(0))dλ

=∫ 1

0(JF((1−λ )z+λy)− JF(z))(y− z)dλ

und damit

|F(y)−F(z)− JF(z)(y− z)| ≤∫ 1

0‖JF((1−λ )z+λy)− JF(z)‖|y− z|dλ

d)≤∫ 1

0γ|(1−λ )z+λy− z||y− z|dλ

≤∫ 1

0γλ |y− z|2dλ =

γ

2|y− z|2

(ii) Zeige f) und g) induktiv.k = 0: Zu f): Das ist gerade Aussage b).

Zu g): Es gilt |x1− x0|= |JF(x0)−1F(x0)︸ ︷︷ ︸=:y

|b)≤ 1

β|F(x0)|

a)≤ α

β= t1− t0.

54

Induktionsschritt zu g): Es gilt∣∣∣xk+1− xk∣∣∣ f )≤ 1

β − γtk|F(xk)|

=1

β − γtk|F(xk)−F(xk−1)− JF(xk−1)(xk− xk−1)︸ ︷︷ ︸

=0

|

(i)≤ 1

β − γtk

γ

2

∣∣∣xk− xk−1∣∣∣2 g)≤ γ

2(tk− tk−1)

2

β − γtk= tk+1− tk .

Induktionsschritt zu f): Es gilt

(β − γtk)|y| ≤∣∣∣JF(xk)y

∣∣∣= ∣∣∣(JF(xk)− JF(xk+1)− JF(xk+1))

y∣∣∣

≤∥∥∥JF(xk)− JF(xk+1)

∥∥∥ |y|+ ∣∣∣JF(xk+1)y∣∣∣

d)≤ γ

∣∣∣xk− xk+1∣∣∣ |y|+ ∣∣∣JF(xk+1)y

∣∣∣g)≤ γ(tk+1− tk)|y|+

∣∣∣JF(xk+1)y∣∣∣

(iii) Zeige:

xk ist eine Cauchyfolge. Es gilt

∣∣∣xk+n− xk∣∣∣≤ ∣∣∣∣∣ n

∑j=1

xk+ j− xk+ j−1

∣∣∣∣∣≤ n

∑j=1

∣∣∣xk+ j− xk+ j−1∣∣∣ g)≤

n

∑j=1

tk+ j− tk+ j−1 ≤ |tk+n− tk|

Da tk eine Cauchyfolge ist (vgl. Lemma 6.3), gilt dies auch für

xk. Insbesondereexistiert also x∗ ∈ U mit x∗ = limk→∞ xk. Weiterhin gilt

∣∣xk− x0∣∣≤ tk− t0 = tk. Damit folgt

schließlichlimk→∞

∣∣∣xk− x0∣∣∣= ∣∣x∗− x0∣∣≤ tk =

β +√

β 2−2αγ.

Zusatz x∗ ist die einzige Nullstelle von F mit

|x− x∗|< 2∣∣∣∣t∗− β

γ

∣∣∣∣= t∗∗− t∗ .

Dabei ist t∗∗ die zweite Nullstelle des Vergleichspolynoms.Aus f) folgt

(β − γt∗) |x− x∗| ≤ |−JF (x∗)(x− x∗)|

≤ |F(x)−F(x∗)− JF(x∗)(x− x∗)|+ |F(x)| ≤ γ

2|x− x∗|2 + |F(x)|

Daraus folgt|F(x)| ≥ |x− x∗|

(β − γt∗− γ

2|x− x∗|

),

55

d. h. es gilt |F(x)|> 0 für

β − γt∗− γ

2|x− x∗|> 0 =⇒ |x− x∗|< 1

γ(β − γt∗) .

Bemerkung1. Der Satz von Newton-Kantorovich beweist die Existenz einer Nullstelle

2. Für alle Eigenwerte λ von JF(x0) gilt |λ | ≥ β , d. h. JF(x0) ist regulär.

3. Aus d) folgt, daß JF lokal Lipschitz stetig ist.

Beispiel1. Wurzelberechnung im Taschenrechner

Sei c = 2pa mit a ∈ (0.5,1], d. h.

√c =

2m√a p = 2m2m√

2√

a p = 2m+1

Es genügt also die Berechnung von√

a, a ∈ (0.5,1] (√

2 sei fest abgespeichert).Es ist F(x) = x2− a, F ′(x) = 2x 6= 0 für x > 0 und φ(x) = x− F(x)

F ′(x) =12

(x+ a

x

).

Setze x0 = 1, xk+1 = φ(xk).Behauptung: |

√a− x5|< 10−16 für 1

2 < a < 1.

Beweis. Es gilt: x−φ(x) = 12

(x− a

x

)= 1

2x

(x2−a

).

0 <(

x− ax

)2= x2−2a+

a2

x2 ⇔ 4a < x+2a+a2

x2 =(

x+ax

)2⇔√

a < φ(x)

(a) Zeige induktiv: 1 = x0 > x1 > .. . > xk >√

aDer Fall k = 0 ist klar. Betrachte den Schritt k→ k+1: Da xk >

√a ist, folgt

xk+1 = φ(xk)>√

a. Aus xk−φ(xk)> 0 folgt xk > xk+1.(b) Es gilt

|F(x0)|= |12−a| ≤ 12= α

|F ′(x0)y|= |2y| =⇒ β = 2F ′′ ≡ 2 =⇒ γ = 2

Also gilt 2αγ = 2 < β 2 = 4. Damit folgt |xk−√

a| ≤ |tk− t∗| mit P(t) = 12 −

2t + t2, t0 = 0, tk+1 = tk− P(tk)P′(tk)

.Es ergibt sich

t∗− t0 = t∗

t∗− t1 ≈ 0,042t∗− t2 ≈ 0,0012

t∗− t3 ≈ 10−6

t∗− t4 ≈ 8 ·10−13

t∗− t5 < 10−16

56

2. Matrixinvertierung auf dem GraphikchipSei A ∈RN×N; setze X0 =

1‖A‖∞

IN , Xk+1 = 2Xk−XkAXk = φ(Xk), also φ(X) = 2X−XAX. Es gilt

A−1−φ(X) = A−1−2X−XAX

= A−1AA−1−XAA−1−A−1AX +XAX

=(A−1−X

)A(A−1−X

)Daraus folgt

∥∥A−1−φ(X)∥∥

∞≤ ‖A‖∞

∥∥A−1−X∥∥2

∞.

Herleitung als Newtonverfahren Betrachte F(X) = X−1−A.Dann ist Xk+1 = Xk− JF(Xk)

−1F(Xk) äquivalent zu

JF(Xk)(Xk+1−Xk) =−F(Xk) . (3)

Es gilt JF(X)H = ∂HF(X) = limt→01t (F(X + tH)−F(X)) =−X−1HX−1, wobei

F(X + tH)−F(X) = (X + tH)−1−A−X−1 +A =(X(IN + tX−1H)

)−1−X−1

=(IN−

(−tX−1H

))−1X−1−X−1 = ∑

n≥1

(−tX−1H

)nX−1

gilt. Aus (3) folgt damit −X−1k (Xk+1−Xk)X−1

k = −X−1k +A. Auflösen nach Xk+1

liefertXk+1 = 2Xk−XkAXk

3. EigenwerteZu A ∈ RN×N definiere

F(x,λ ) =(

Ax−λx12

(1− xT x

))Es ist also

JF

(xλ

)=

(A−λ IN −x−xT 0

)und φ

(xλ

)=

(xλ

)−(

A−λ IN −x−xT 0

)−1( Ax−λx12

(1− xT x

))Sei Ax∗ = λ ∗x∗ eine Lösung. Wir untersuchen nun, ob JF(x∗,λ ∗) regulär ist. Fürjede homogene Lösung (y,µ) von(

A−λ ∗IN −x∗

−(x∗)T 0

)(yµ

)=

(0N0

)gilt Ay−λ ∗y = (A−λ ∗IN)y = µx∗ und damit (A−λ ∗IN)

2y = 0N . Daraus folgt, daßy Hauptvektor ist. Im Fall dass die algebraische Vielfachheit von λ ∗ gleich der geo-metrischen Vielfachheit von λ ∗ ist (z.B. falls A symmetrisch ist), dann JF(x∗,λ ∗)T

regulär.

57

4. Nichtlineare AusgleichsproblemeSei F : D⊂ RM→ RN . Bestimme x∗ ∈ D mit |F (x∗)|2 ≤ |F(x)|2, x ∈ D.Definiere g(x) = 1

2 |F(x)|22 = 12F(x)T F(x). Minimiere g, d. h. suche die kritische

Stelle von ∇g. Es gilt

G(x) = ∇g(x) = Jg(x)T = JF(x)T F(x) ,

JG(x) = Hg(x) =N

∑n=1

HFn(x)F(x)+ JF(x)T JF(x) .

Gauß-Newton-VerfahrenS0) Wähle x0 ∈ D, ε > 0, setze k = 0.

S1) Falls∣∣∣JF(xk)T F

(xk)∣∣∣

2< ε : STOP

S2) Berechne die Linearisierung F(y) ≈ F(xk) + JF(xk)(y− xk) = bk + Aky mitbk = F(xk)− JF(xk)xk, Ak = JF(xk), und berechne xk+1 als Lösung des Aus-gleichsproblems

|Aky+bk|2 = Min!

S3) Falls xk+1 6∈ D : STOP (Divergenz)

S4) Setze k := k+1; gehe zu S1).

Newtonverfahren mit DämpfungS0) Wähle x0 ∈ D, θ ∈ (0,1), ε > 0, setze k = 0.

S1) Falls∣∣F (xk)∣∣≤ ε : STOP

S2) Löse JF(xk)dk =−F

(xk)

S3) Bestimme tk ∈

1,θ ,θ 2, . . . ,θ mmit xk+tkdk ∈D und∣∣F (xk + tkdk)∣∣

2 <∣∣F (xk)∣∣

2,sonst: STOP

S4) Setze xk+1 = xk + tkdk, k := k+1; gehe zu S1).

Eine Methode, um bessere Startwerte zu finden, ist ein Homotopieverfahren:

HomotopieSei F0 : RN → RN ein Vektorfeld mit Nullstelle x0, d. h. F0

(x0)= 0N .

Wähle 0 < λ1 < λ2 < .. . < λM = 1.

S0) Setze m = 1.

S1) Berechne die Nullstelle xm von Fm mit Fm(x) = (1− λm)F0(x)+ λmF(x) mitStartwert xm−1.

S2) Falls m < M ist, setze m := m+1 und gehe zu S1).

58

7 Orthogonalpolynome

BeispielSei f : [0,1]→ R stetig.Aufgabe: Bestimme die Bestapproximation P∈ PN mit ‖P− f‖≤ ‖Q− f‖ für alle Q∈ PN

bezüglich der Norm ‖u‖=√〈u,u〉 mit dem Skalarprodukt 〈u,v〉=

∫ 10 u(t)v(t)dt.

Lösung 1: Wähle Monombasis 1, t, t2, . . . , tN . Nun lässt sich Satz (1.3) anwenden:Löse Ax = b mit

A =(〈tk, tn〉

)k,n=0,...,N

∈ R(N+1)×(N+1)

b =(〈 f , tk〉

)k=0,...,N

∈ RN+1

Damit ergibt sich die “Bestapproximation” P(t) =N∑

k=0x[k]tk.

Zur Bestimmung von A berechnen wir

〈tk, tn〉=∫ 1

0tktn dt =

∫ 1

0tk+n dt =

tk+n+1

k+n+1

∣∣∣∣10=

1k+n+1

.

Die Matrix A heißt Hilbert-Matrix. Sie ist symmetrisch positiv definit, und mithilfe derCholeskyzerlegung A = LLT gilt LLT x = b, also Ly = b und LT x = y. Allerdings gilt indiesem Beispiel κ2(A)> 1016 für N > 15; somit ist das Gleichungssystem extrem schlechtkonditioniert.Lösung 2: Berechne eine Orthonormalbasis Q0, . . . ,QN von PN . Damit ergibt sich

A =(〈Qk,Qn〉

)k,n

= IN+1 P(t) =N

∑k=0〈 f ,Qk〉Qk(t)

Also: Mit Orthogonalpolynomen lassen sich also effizient “optimale“ Approximationenberechnen. Daher studieren wir die Konstruktion und ihre Eigenschaften.

Allgemein:Sei −∞ ≤ a < b ≤ ∞, I = (a,b) ⊂ R ein Intervall, W : I → (0,∞) eine stetige positiveGewichtsfunktion und auf V =C(I) definiere

〈u,v〉V =∫ b

au(t)v(t)W (t) dt ‖u‖V =

√〈u,v〉V ;

damit ist (V,〈·, ·〉) ein euklidischer Vektorraum.

Beispiel

A) Legendre: (a,b) = (−1,1) W = 1

B) Chebychev: (a,b) = (−1,1) W (t) =1√

1− t2

C) Jacobi: (a,b) = (−1,1) W (t) = (1− t)α(1+ t)β

D) Laguerre: (a,b) = (0,∞) W (t) = exp(−t)

E) Hermite: (a,b) = R W (t) = exp(−t2)

59

OrthogonalisierungSetze R0 ≡ 1, ρ0 = ‖R0‖V , Q0 =

1ρ0

R0.Für n = 0,1, . . . ,N−1:

Rn+1(t) = tQn(t)−n

∑k=0

hknQk(t) , mit hkn = 〈Qk, tQn〉V ,

Qn+1(t) =1

hn+1,nRn+1(t) , mit hn+1,n = ‖Rn+1‖V .

Induktiv ergibt sich tQn ∈Pn+1\Pn =⇒ Rn+1 ∈Pn+1\Pn =⇒ Rk+1 6= 0 =⇒ hn+1,n 6= 0.Weiterhin ist

〈Qk, tQn〉V =∫ b

aQk(t)tQn(t)W (t)dt = 〈Qn, tQk〉V

und somit hkn = hnk. Falls k+1 < n, gilt

tQk ∈ Pn−1 =⇒ hkn = 〈tQk,Qn〉V = 0 .

Zusammen erhalten wir

tQn(t) =n

∑k=0

hknQk(t)+Rn+1(t) =n+1

∑k=0

hknQk(t)

= hn+1,nQn+1(t)+hnnQn(t)+hn,n−1Qn−1(t)

Nun definiere

ρn+1 = hn+1,n = 〈Rn+1,Qn+1〉V = 〈tQn,Qn+1〉V > 0 ,βn = 〈Qn, tQn〉V = hnn .

(7.1) SatzFür die Orthogonalpolynome Q0,Q1, . . . in V gilt

Q−1 ≡ 0, Q0 ≡1ρ0

, und ρn+1Qn+1 = (t−βn)Qn−ρnQn−1 für n > 0

mit ρ0 =√∫ b

a W (t)dt, ρn = 〈Qn, tQn−1〉V > 0 für n > 0, und βn = 〈tQn,Qn〉V .

BemerkungHäufig werden nicht-normierte Orthogonalpolynome verwendet mit einfacheren Koeffizi-

enten als ρ1 = ‖t−β0‖V/ρ0 und ρn+1 =√‖(t−βn)Qn‖2

V +ρ2n verwendet.

BeispielA) Legendre: (a,b) = (−1,1), W = 1; die Polynome

Ln(t) =1

2nn!

(ddt

)n

(t2−1)n = tn + . . .

60

sind orthogonal, denn für n > k gilt:

∫ b

a

(ddt

)n

(t2−1)n(

ddt

)k

(t2−1)k dt =∫ 1

−1(t2−1)(−1)n

(ddt

)n+k

(t2−1)k dt = 0 .

BeobachtungMit ρn+1Qn+1(t) = (t−βn)Qn(t)−ρnQn+1(t) erhalten wir aus den OrthogonalpolynomenQ0,Q1, . . . ,Qn

Pn(t) =n

∏k=0

ρ−1k Qk(t) = tn + . . .

Pn ∈ Pn ist das charakteristische Polynom der symmetrischen irreduziblen Tridiagonalma-trix

A =

β0 ρ1ρ1 β1 ρ2

ρ2 β2. . .

. . . . . .

, ρn > 0

P0,P1,P2, . . ., also auch Q0,Q1,Q2, . . . bilden eine Sturmsche Kette, vgl. Satz (4.9). Alsohat Qn die verschiedenen Nullstellen λ

(n)1 < .. . < λ

(n)n mit λ

(n)k < λ

(n−1)k < λ

(n)k+1 für k < n

und es gilt

λ(n)k < t ⇐⇒ k ≤ #

j ∈ 1, . . . ,n : Q j(t)Q j−1(t)< 0

.

Wir zeigen nun zusätzlich a < λ(n)1 < λ

(n)n < b.

(7.2) SatzQn hat n verschiedene Nullstellen in (a,b).

Beweis. Seien a< λ1 < .. . < λr < b alle Nullstellen von Qn in (a,b), in denen Qn das Vor-zeichen wechselt. Dann definieren wir P(t) = ±∏

rk=1(t−λk) und wähle das Vorzeichen

so, dass P(t)Qn(t) ≥ 0 für alle t ∈ (a,b) und damit 〈P,Qn〉V =∫ b

a P(t)Qn(t)W (t)dt > 0gilt.Annahme: r < n.Dann wäre P ∈ Pr ⊂ Pn−1 und somit 〈P,Qn〉V = 0. Widerspruch!

BeispielB) Chebychev-Polynome: (a,b) = (−1,1), W (t) = 1√

1−t2 . Definiere

Tn(t) = cos(narccos t), t ∈ [−1,1]

Mit der Substitution t = cosx ergibt sich für k 6= n∫ 1

−1

1√1− t2

Tn(t)Tk(t)dt =∫

π

0cos(nx)cos(kx)dx = 0 .

61

Zeige: Tn ∈ PnT0 ≡ 1, T1(t) = t. Für n≥ 1 gilt

Tn−1(t)+Tn+1(t) = cos((n−1)x)+ cos((n+1)x) (wende nun Additionstheoreme an)= cos(nx)cos(−x)︸ ︷︷ ︸

=cosx

−sin(nx)sin(−x)︸ ︷︷ ︸=−sinx

+cos(nx)cosx− sin(nx)sinx

= 2cos(nx)cosx= 2t Tn(t) .

Also gilt Tn+1(t) = 2t Tn(t)−Tn−1(t).

Für |t| ≥ 1 gilt weiterhin die Identität

Tn(t) =12

(t +√

t2−1)n

+12

(t−√

t2−1)n

denn aus T0 ≡ 1, T1 =12t + 1

2t = t und(t±√

t2−1)2

= t2±2t√

t2−1+ t2−1 = 2t(

t±√

t2−1)−1

folgt ebenfalls die Dreitermrekursion Tn+1(t) = 2tTn(t)−Tn−1(t).

(7.3) Folgerung (für Chebychev-Polynome)Sei ξ /∈ [−1,1]. Dann gilt für P(t) = 1

Tn(ξ )Tn(t)

maxt∈[−1,1]

|P(t)| ≤ maxt∈[−1,1]

|Q(t)| für alle Q ∈ Pn mit Q(ξ ) = 1 .

Beweis. Annahme: Es existiert ein Q ∈ Pn mit Q(ξ ) = 1 und

maxt∈[−1,1]

|Q(t)|< 1Tn(ξ )

maxt∈[−1,1]

|Tn(t)|=1

Tn(ξ )

Für tk = cos(kπ

n ) (k = 0, . . . ,n) gilt Tn(tk) = cos(kπ) =±1.Betrachte R(t) = Q(t)− 1

Tn(ξ )Tn(t) ∈ Pn.

=⇒ R(ξ ) = 0 und R(tk) = Q(tk)−1

Tn(ξ )cos(kπ)

=⇒ R(tk)R(tk−1)< 0 für k = 1, . . . ,n=⇒ R hat eine Nusllstellen in (tk−1, tk) für k = 1, . . . ,n=⇒ R hat n Nullstellen in [−1,1] und die Nullstelle ξ 6∈ [−1,1]=⇒ R hat n+1 Nullstellen=⇒ R≡ 0

=⇒ Q =1

Tn(ξ )Tn Widerspruch!

62

(7.4) FolgerungSei 0 < a < b. Dann gilt

minP∈Pn

P(0)=1

maxt∈[a,b]

|P(t)| ≤ 2

ba −1√ba +1

n

Beweis. Definiere φ : R→ R, x 7→ −1+ 2b−a(x−a), d.h. φ ((a,b)) = (−1,1), und

P(x) :=1

Tn (φ(x))Tn (φ(x)) ∈ Pn =⇒ ‖P‖∞,[a,b] ≤

1|Tn(ξ )|

mit ξ = φ(0)<−1

Definiere κ = ba > 1. Zu zeigen:

∣∣Tn(1+κ

1−κ

)∣∣≥ 12

√κ+1√κ−1 . Für t = 1+κ

1−κgilt

t±√

t2−1 =1+κ±

√4κ

1−κ=

(1±√

κ)2(

1−√

κ)(

1+√

κ) = 1±

√κ

1∓√

κ,

und Tn(t) = 12

(t +√

t2−1)n

+ 12

(t−√

t2−1)n

ergibt |Tn(t)| ≥ 12

(√κ+1√κ−1

)n.

Anwendungen in der numerischen linearen Algebra

Das cg-Verfahren Seien A,B∈RN×N symmetrisch positiv definit, b∈RN , x0 ∈RN undo.E. r0 = b−Ax0 6= 0. Wir approximieren die Lösung x = A−1b iterativ.Sei x− x0 = A−1r0 /∈Kn = Kn(BA,Br0) = P(BA)Br0 : P ∈ Pn−1, dann ist dimKn = n(Lem. (5.8)).Definiere auf Pn das Skalarprodukt 〈P,Q〉A,B = (x− x0)T P(AB)AQ(BA)(x− x0).Dann gilt für xn ∈ x0 +Kn mit |xn− x|A ≤ |y− x|A für alle y ∈ x0 +Kn

=⇒ xn = x0 +Pn(BA)Br0 für ein Pn ∈ Pn−1

=⇒ |x0 +Pn(BA)Br0− x|A = |1− tPn|A,B ≤ |1− tQ|A,B ∀Q ∈ Pn−1

=⇒ |xn− x|A ≤ minQ∈Pn−1

|1− tQ|A,B = minR∈Pn

R(0)=1

|R|A,B

Nun folgt aus (7.4) für σ(BA)⊂ [a,b] und κ = ba

|R|A,B ≤ |x0− x|A maxλ∈σ(BA)

|R(λ )| ≤ |x0− x|A maxt∈[a,b]

|R(t)| ≤ 2(√

κ−1√κ +1

)n

|x0− x|A .

63

Das Lanczos Verfahren Sei A ∈ RN×N symmetrisch, z ∈ RN \0N “zufällig”.Zu n < N definiere Kn = Kn(A,z) = P(A)z : P ∈ Pn−1Voraussetzung: dimKn = nDann ist 〈P,Q〉A = zT P(A)Q(A)z ein Skalarprodukt in Pn−1Orthogonalisierung: ρ0 = |z|2, v1 =

1ρ0

z.Für k = 1, . . . ,n−1:

zk+1 = Avk−k

∑j=1

h jkv j mit h jk = (Azk)T v j

vk+1 =1ρk

zk+1 mit hk+1,k = ρk = |zk+1|2

=⇒ ρk = vTk+1zk+1 = vT

k+1Avk = hk,k+1, βk = hkk = vTk Avk =⇒ Avk =

k+1

∑j=1

h jkv j

=⇒ AVk =VkHk +hk+1,kvk+1 mit Vk = (v1 | · · · | vk) ∈ RN×k und

der irreduziblen, symmetrischen Tridiagonalmatrix Hk =

β1 ρ1ρ1 β2 ρ2

ρ2 β3. . .

. . . . . .

.

Bemerkung1. Der Lanczos-Algorithmus hat die Form

zk+1 = (A−βkIN)vk−ρk−1vk−1 ,

βk = vTk Avk , ρk = |zk|2 , vk+1 =

1ρk

zk+1 .

2. Die Eigenwerte von Hk approximieren einige Eigenwerte von A (insbesondere dengrößten und den kleinsten Eigenwert). Sie sind Nullstellen der zugehörigen Ortho-gonalpolynome.

64

Approximation mit Orthogonalpolynomen(7.5) Satz (Approximationssatz von Weierstraß)Jede stetige Funktion f ∈C(R) lässt sich im Intervall [a,b] gleichmäßig durch Polynomeapproximieren, d.h. zu jedem ε > 0 existiert ein P ∈ P mit

|P(t)− f (t)|< ε, t ∈ [a,b]

Beweis. Ohne Einschränkung sei [a,b] = [−0.25,0.25] und f (t) = 0 für |t| ≥ 0.5.Dann ist f gleichmäßig stetig auf R, also existiert zu jedem ε > 0 ein δ > 0 mit

| f (t + s)− f (t)|< ε

2für t ∈ R und |s|< δ .

Definiere

R2n(t) = rn(1− t2)n ∈ P2n mit∫ 1

−1Rn(t)dt = 1 , d.h. rn =

(∫ 1

−1(1− t2)n dt

)−1

.

Wir betrachten nun die Faltung

P2n(t) = (Rn ∗ f )(t) =∫R

Rn(s) f (t− s)ds =∫R

Rn(t− x) f (x)dx =∫ 0.5

−0.5Rn(t− x) f (x)dx .

Zu t,x ∈ R existieren Koeffizienten ank j ∈ R mit R2n(t− x) =2n∑

j,k=0ank jtkx j, also gilt

P2n(t) =2n

∑j,k=0

an jktk0.5∫−0.5

x j f (x)dx ∈ P2n .

Für |t| ≤ 0.25 und |s| ≥ 0.75 gilt f (t− s) = 0 und damit

Pn(t)− f (t) =∫ 1

−1Rn(s) f (t− s)ds− f (t)

∫ 1

−1Rn(s)ds︸ ︷︷ ︸=1

=∫ 1

−1Rn(s)( f (t− s)− f (t)) ds .

Hieraus folgt

|Pn(t)− f (t)| ≤∫|s|<δ

|Rn(s)( f (t− s)− f (t))|ds+∫|s|∈(δ ,1)

|Rn(s)( f (t− s)− f (t))|ds

≤ max|s|<δ

| f (t− s)− f (t)|+ rn(1−δ2)n 2‖ f‖∞

≤ ε

2+

ε

2mit (1−δ

2)n ≤ ε

4‖ f‖∞rnfür große n.

Sei L2(−1,1) der Hilbertraum der L2-Funktionen und

〈u,v〉0 =∫ 1

−1u(t)v(t)dt

das L2-Skalarprodukt. Dann gilt:Die Orthogonalpolynome Q0,Q1, . . . zu 〈·, ·〉0 bilden eine “Hilbertbasis“ von L2(−1,1):

65

(7.6) FolgerungFür jede stetige Funktion f ∈C[−1,1] konvergiert die Folge der Orthogonalprojektionen

pn( f ) =n

∑k=0〈 f ,Qk〉0Qk ∈ Pn in ‖ · ‖0

Beweis. ‖ f − p2n( f )‖0 = minP∈Pn ‖P− f‖0 ≤ ‖P2n− f‖0 ≤√

2‖P2n− f‖∞→ 0.

Da die stetigen Funktionen in L2 dicht liegen, gilt die Aussage für alle L2-Funktionen.

Bemerkung1. pn : C[−1,1]→ Pn Orthogonalprojektion, denn es gilt pn (pn( f )) = pn( f ), d.h.

pn pn = pn, und

〈pn( f )− f , pn( f )〉0 =

⟨n

∑k=0〈 f ,Qk〉Qk− f ,

n

∑j=0〈 f ,Q j〉Q j

⟩0

=n

∑j=0

(〈 f ,Q j〉−〈 f ,Q j〉

)〈 f ,Q j〉= 0

2. Die Konvergenz kann beliebig langsam sein!

3. Es gilt ‖ f‖0 =

√∞

∑n=0〈 f ,Qn〉20.

4. In [0,1] konvergieren die Bernsteinpolynome

Bn(t) =n

∑k=0

(nk

)(1− t)k tn−k f

(kn

)∈ Pn

gleichmäßig gegen stetige Funktionen f in [0,1].

(7.7) SatzEs existiert C > 0, sodass für alle f ∈Ck[−1,1] gilt:

‖Pn( f )− f‖0 ≤Cnk

∣∣∣∣∣∣∣∣∣∣(

ddt

)k

f

∣∣∣∣∣∣∣∣∣∣0

.

Beweis. Beweis für den Fall k = 2, n≥ 2.Die Orthogonalpolynome in L2(−1,1) sind skalierte Orthogonalpolynome, d.h. es giltQn = qn

( ddt

)n(t2−1)n mit Normierungsfaktor qn ∈ R.

(i) Zeige: Die Orthogonalpolynome sind Lösung der Sturm-Liouville-Differentialgleichung

− ddt

[(1− t2)

ddt

Qn

]= λnQn mit λn = n(n+1) .

Es gilt

Qn = qn

(ddt

)n

(t2−1)n = qn2nn! tn + . . . =⇒ 1 = 〈Qn,Qn〉0 = qn2nn!〈tn,Qn〉0 .

66

Daraus ergibt sich für j < n:

−⟨

ddt

[(1− t2)Q′n

],Q j

⟩0=−

∫ 1

−1

ddt

[(1− t2)Q′n

]Q j dt

= −(1− t2)Q′nQ j∣∣1−1 +

∫ 1

−1

[(1− t2)Q′n

]Q′j dt

= Q′n(1− t2)Q′j∣∣1−1−

∫ 1

−1Qn

ddt

[(1− t2)Q′j

]︸ ︷︷ ︸

∈P j

dt = 0

Insgesamt ergibt sich also aus Q′n(t) = qn2nn!ntn−1 und Q′′n(t) = qn2nn!n(n−1) tn−2

Pn 3 −ddt

[(1− t2)Q′n

]=

n

∑j=0−⟨

ddt(1− t2)Q′n,Q j

⟩0

Q j

=−⟨

ddt

[(1− t2)Q′n

],Qn

⟩0

Qn

=⟨2tQ′n− (1− t2)Q′′n,Qn

⟩0 Qn

= qn2nn!〈2ntn +(n(n−1)) tn,Qn〉0 Qn

= (2n+n(n−1))qn2nn!〈tn,Qn〉0Qn = n(n+1)Qn = λnQn .

(ii) Definiere die Norm ‖ f‖2s = ∑k≥0 λ s

k 〈 f ,Qk〉20 und den HilbertraumHs = f ∈ L2(−1,1) | ‖ f‖s < ∞. Zeige

‖pn( f )− f‖0 ≤1

λ sn+1‖ f −P‖2s für alle f ∈ H2s, P ∈ Pn .

Es gilt

‖pn( f )− f‖20 = ∑

j>n〈 f ,Q j〉20 ≤ λ

−2sn+1 ∑

j>nλ

2sj 〈 f ,Q j〉20 = λ

−2sn+1 ∑

j>nλ

2sj 〈 f −P,Q j〉20

≤ λ−2sn+1 ∑

j≥0λ

2sj 〈 f −P,Q j〉20 = λ

−2sn+1‖ f −P‖2

2s .

Im Folgenden ersetze f durch f − t f ′(0), also o.E. f ′(0) = 0.(iii) Zeige: Es gilt ‖ f‖2 = ‖ d

dt

((1− t2)

) ddt f‖0.

Dazu betrachte

‖ f‖22 = ∑

k≥0〈 f ,λkQk〉20 = ∑

k≥0λ

2k 〈 f ,Qk〉20

(i)= ∑

k≥0

⟨f ,

ddt

[(1− t2)Q′k

]⟩2

0

= ∑k≥0

⟨f ′,(1− t2)Q′k

⟩20 = ∑

k≥0

⟨ddt

[(1− t2) f ′

],Qk

⟩0=

∥∥∥∥ ddt(1− t2) f ′

∥∥∥∥2

0.

(iv) Zeige: Es gilt∥∥ d

dt

[(1− t2) f ′

]∣∣0 ≤ 3‖ f ′′‖0.

Mit ddt

[(1− t2) f ′

]=−2t f ′+(1− t2) f ′′ und

∥∥t f ′∥∥2

0 =∫ 1

−1t2 f ′(t)2 dt =

∫ 1

−1t2

f ′(t)− f ′(0)︸ ︷︷ ︸=0

2

dt

=∫ 1

−1t2(∫ t

0f ′′(s)ds

)2

dt ≤ ‖ f ′′‖20

∫ 1

−1t2 dt =

23‖ f ′′‖2

0

67

folgt insgesamt∥∥∥∥ ddt

[(1− t2) f ′

]∥∥∥∥0≤ 2‖t f ′‖0 +‖(1− t2) f ′′‖0 ≤ 2

√23‖ f ′′‖0 +‖ f ′′‖0 ≤ 3‖ f ′′‖0 .

Zusammen ergibt sich damit

‖pn( f )− f‖0 ≤1

λn+1‖ f − t f ′(0)‖2 ≤

3(n+1)(n+2)

‖ f ′′‖0 .

BemerkungIm Beweis haben wir gezeigt, dass Legendre-Polynome

Ln(t) =1

2nn!

(ddt

)n

(t2−1)n ∈ Pn Qn =1‖Ln‖0

Ln

die Sturm-Liouville Eigenwert-Aufgabe

− ddt

((1− t)2 d

dtLn(t)

)= λnLn(t) mit λn = n(n+1)

lösen, und dass sich damit eine Skala von Hilberträumen für s≥ 0

Hs :=

f ∈ L2(−1,1) :

∑n=0

λsn〈 f ,Qn〉20 < ∞

⊂ H0 = L2(−1,1) mit s≥ 0

mit dem Skalarprodukt 〈 f ,g〉s = ∑λ sn〈 f ,Qn〉0〈g,Qn〉0 definieren lässt.

Bemerkung1. Die Berechnung von Pn erfordert Integration. Diese ist im Allgemeinen nur appro-

ximativ möglich.

2. Qualitative Konvergenz erfordert Regularität!

3. Die Auswertung von P = ∑nk=0 akQk an der Stelle t mit der 3-Term-Rekursion benö-

tigt nur O(n) Operationen!

4. Effizienter (aber nicht besser) ist Interpolation (siehe Kapitel 8).

5. Auch für allgemeine Jacobi-Polynome zum Gewicht W (t) = (1− t)α (1+ t)β gilt:

J(α,β )n (t) =W (t)−1

(ddt

)n

(1− t)α+n(1+ t)β+n, |t|< 1

löst eine Sturm-Lioville-Eigewertaufgabe

(1− t2)u′′+(β −α +(α +β +2)t)u′+n(α +β +n+1)︸ ︷︷ ︸λn

u = 0 .

68

8 Polynominterpolation

Interpolations-Aufgabe: Von einer glatten Kurve seien nur endlich viele Punktewertegegeben. Wähle einen endlichdimensionalen Funktionenraum. Konstruiere nun eineKurve in diesem Funktionenraum durch die gegebenen Punkte.

Fragen:(1) Wie berechnet man so eine Kurve?

(2) Wie groß ist der Interpolationsfehler?

(8.1) Definition (Interpolationsaufgabe von Lagrange)Zu Stützstellen t0 < t1 · · ·< tN und Werten f0, f1, . . . , fN ∈R bestimme ein Polynom P∈ PNmit

P(tn) = fn , n = 0, . . . ,N .

(8.2) SatzDie Interpolationsaufgabe von Lagrange (8.1) ist eindeutig lösbar.

Beweis.

(1) Eindeutigkeit:Seien P, P zwei Lösungen der Aufgabe (8.1). Definiere Q := P− P ∈ PN . Dann hatQ nach Definition N +1 Nullstellen und ist daher das Nullpolynom.

(2) Existenz:Die Zuordnung eines Polynoms P ∈ PN auf die Auswertungen in den Stützstellenist linear, d.h. die Lösung der Interpolationsaufgabe entspricht der Lösung eines Li-nearen Gleichungssystems in RN+1. Da die Lösung eindeutig ist, ist die zugehörigeMatrix regulär und somit ist die Aufgabe immer lösbar.

Konstruktion des InterpolationspolynomsZum Lösen der Interpolationsaufgabe muss man im Grunde den Koeffizientenvektor a =

(a0,a1, . . . ,an)T ∈ RN+1 bestimmen, welcher

a0 +a1tn +a2t2n + · · ·+aNtN

n = fn

für n= 0, . . . ,N genügt. Dies ist ein lineares Gleichungssystem Ta= f mit f =( f0, . . . , fN)T ∈

RN+1 und der Vandermonde-Matrix

T = (tkn)n,k=0,...,N =

1 t0 t2

0 · · · tN0

1 t1 t21 · · · tN

1...

...... . . . ...

1 tN t2N · · · tN

N

∈ RN+1,N+1 .

Diese Matrix ist zwar regulär (da die tn paarweise verschieden sind), hat aber in derRegel eine sehr schlechte Kondition. Eine andere Möglichkeit ist die Darstellung über die

69

Lagrange Basispolynome Lk ∈ PN mit

Lk(t) =N

∏n=0n6=k

t− tntk− tn

Diese Polynome genügen der Bedingung

Lk(tn) =

1, k = n0, k 6= n

.

Also ist

P(t) :=N

∑k=0

fkLk(t)

Lösung der Interpolationsaufgabe (8.1).

Vor- und Nachteile der Lagrange-Darstellung

+ Explizite Darstellung der Lösung.

+ Auswertung von P benötigt O(N2) Operationen, während das Lösen von Ta = f mitder LR-Zerlegung O(N3) Operationen benötigt.

− Die Lagrange Basis ist stark oszillierend, somit ist die Auswertung für große Nnumerisch instabil und führt zur Auslöschung.

− Wenn ein weiterer Wert hinzugefügt wird, müssen alle Basispolynome neu berech-net werden!

(8.3) Definition (Hermitesche Interpolationsaufgabe)Zu t0 ≤ t1 ≤ ·· · ≤ tN definiere

dn := maxn− k : tk = tk+1 = · · ·= tn,

und es sei d = maxdn . Zu f ∈Cd(R) bestimme P ∈ PN mit(ddt

)dn

P(tn) =(

ddt

)dn

f (tn) für n = 0, . . . ,N.

Beispiele

(1) Sind die tn paarweise verschieden, dann folgt dn = 0 und wir erhalten die Lagrange-Interpolation.

(2) Für t0 = t1 = · · ·= tN ergibt sich das Taylor-Polynom

P(t) =N

∑n=0

1n!(t− t0)n

(ddt

)n

f (t0).

70

(3) Betrachte die kubische Hermite-Interpolation mit

a = t0 = t1 < t2 = t3 = b .

Dann gilt d0 = 0,d1 = 1,d2 = 0,d3 = 1 und es ergibt sich P(t) = H( t−a

b−a

)für

H(t) = f (a)H00(t)+(b−a) f ′(a)H10(t)+ f (b)H01(t)+(b−a) f ′(b)H11(t).

Dabei sind die Hermite-Polynome gegeben durch

H00(t) = 1−3t2 +2t3, H10(t) = t−2t2 + t3 ,

H01(t) = 3t2−2t3, H11(t) = −t2 + t3 .

(8.4) DefinitionZu t0, . . . , tN definiere die Newton-Basis von PN rekursiv durch

ω0 ≡ 1 , ωk(t) = (t− tk−1)ωk−1(t) , k = 1, . . . ,N .

BemerkungEs gilt degωk = k, und spanω0, . . . ,ωk= Pk.

(8.5) SatzDie Hermitesche Interpolationsaufgabe (8.3) ist eindeutig lösbar.

Beweis. Definiere die Linearform µn : Cd[a,b]−→ R mit

µn( f ) =1dn

(ddt

)dn

f (tn) .

Suche ein Polynom P ∈ PN mit µn(P) = µn( f ) für n = 0, . . . ,N. Da µn linear ist, löst einPolynom

P(t) =N

∑k=0

bkωk(t)

genau dann (8.3), wenn

N

∑k=0

µn(ωk)bk = µn( f )

für n = 0, . . . ,N gilt. Es bleibt also zu zeigen, dass die Matrix

A := (µn(ωk))n,k=0,...,N ∈ RN+1,N+1

regulär ist. Es gilt µn(ωk) = 0 für n < k und µn(ωn) = 1. Also ist A eine normierte Drei-ecksmatrix und somit regulär.

71

(8.6) DefinitionDer eindeutig bestimmte höchste Koeffizient

bN =1

N!

(ddt

)N

P(t)

der Hermiteschen Interpolationsaufgabe (8.3) bzgl. der Newton-Basis wird mit

bN =: f [t0, . . . , tN ]

bezeichnet. bN heißt N-te dividierte Differenz von f an t0, . . . , tN .

Bemerkung1) Für N = 0 gilt f (t0) = f [t0].

2) Falls t0, . . . , tN nicht sortiert sind, dann definiere f [t0, . . . , tN ] = f [tk0, . . . , tkN ] mit derSortierung tk0 ≤ ·· · ≤ tkN .

(8.7) Satza) Das Polynom

PN(t) :=N

∑k=0

f [t0, . . . , tk]ωk(t)

löst die Interpolationsaufgabe (8.3) zu f an t0 ≤ ·· · ≤ tN .

b) Für f ∈CN+1(R) gilt

f (t) = PN(t)+ f [t0, . . . , tN , t]ωN+1(t) .

Beweis. Zu a) Wir führen eine Induktion über N durch.N = 0: Es gilt P0(t) = f (t0) = f [t0].N−1−→ N: Sei PN ∈ PN die Interpolation zu f an t0, . . . , tN . Dann definiere

PN−1(t) := PN(t)− f [t0, . . . , tN ]ωN(t) ∈ PN−1 .

Dieses PN−1 erfüllt(ddt

)N

PN−1(t) =(

ddt

)N

PN(t)−1

N!

(ddt

)N

PN(t)(

ddt

)N

ωN(t)︸ ︷︷ ︸=N!

= 0,

daher ist PN−1 ∈ PN−1. Ferner gilt für n < N nach Konstruktion µn(ωN) = 0. Also erfülltPN−1 für n < N die Gleichung

µn(PN−1) = µn( f ).

Damit löst PN−1 (8.3) für t0, . . . , tN−1 und nach Induktionsvoraussetzung gilt

PN−1(t) =N−1

∑k=0

f [t0, . . . , tk]ωk(t).

72

Zu b) Für festes t definiere das Polynom Qt ∈ PN+1 mit

Qt(s) = PN(s)+ f [t0, . . . , tN , t]ωN+1(s) .

Nach a) ist Qt die Hermite-Interpolation zu f an den Stellen t0, . . . , tN , t. Somit gilt insbe-sondere Qt(t) = f (t).

(8.8) SatzFür den Interpolationsfehler gilt

f (t)−PN(t) =1

(N +1)!

(ddt

)N+1

f (τt)ωN+1(t)

mit τt ∈ I := [mint0, t,maxt, tN].

Beweis. Sei dazu

Qt(s) = PN(s)− f [t0, . . . , tN , t]ωN+1(s) ∈ PN+1

die Interpolation zu f an t0, . . . , tN , t. Also hat f (s)−Qt(s) in I mindestens N+2 Nullstel-len (mit Vielfachheiten). Nach dem Satz von Rolle gilt, dass f ′(s)−Q′t(s) in I mindestensN +1 Nullstellen (mit Vielfachheiten) hat. Induktiv folgt also, dass(

dds

)N+1

( f −Qt)(s) =(

dds

)N+1

f (s)− f [t0, . . . , tN , t](N +1)!

in I mindestens eine Nullstelle τt ∈ I hat. Und damit gilt für diese Nullstelle(dds

)N+1

f (τt) = f [t0, . . . , tN , t](N +1)! ,

woraus mit Satz (8.7) die Behauptung folgt.

Anwendung von (8.8)Es gilt für den Fehler der Lagrange-Interpolation mit tn := a+nh, h := b−a

N

maxt∈[a,b]

| f (t)−PN(t)| ≤ maxt∈[a,b]

∣∣∣∣∣ 1(N +1)!

(ddt

)N+1

f (τt)ωN+1(t)

∣∣∣∣∣≤ 1

N +1hN+1 max

t∈[a,b]

∣∣∣∣∣(

ddt

)N+1

f (τt)

∣∣∣∣∣ ,für f ∈CN+1[a,b], denn

maxt∈[a,b]

|ωN+1(t)|= maxn=1,...,N

maxt∈[tn−1,tn]

|ωN+1(t)|

≤n

∏n=k

(k+1)h≤N

∏k=n+1

(N +1− k)h≤ N! hN+1 .

BemerkungIm Allgemeinen ist

( ddt

)kf (t) unbeschränkt, wenn k immer größer wird.

73

Zur Auswertung der Interpolation verwenden wir die folgenden Rekursionen.

(8.9) Lemmaa) Für tk < tn gilt

f [tk, . . . , tn] =f [tk+1, . . . , tn]− f [tk, . . . , tn−1]

tn− tk.

b) Für tk = · · ·= tn gilt

f [tk, . . . , tn] =1

(n− k)!

(ddt

)n−k

f (tn).

BemerkungEs gelten

f [t] = f (t) ,

f [t, t] = limh→0

f [t +h, t] = limh→0

f [t +h]− f [t]h

= f ′(t) ,

f [t, t, t] = limh→0

f [t−h, t, t +h]a)= lim

h→0

f [t +h, t]− f [t−h, t]2h

a)= lim

h→0

f [t−h]−2 f [t]+ f [t +h]2h2 = f ′′(t).

Beweis. Zu a) Sei Pkn ∈ Pn−k die Interpolation zu f an tk, . . . , tn, d.h.

f [tk, . . . , tn] =1

(n− k)!

(ddt

)n−k

Pnk(t) .

Dann definiere zu k < n

P(t) :=1

tn− tk

((t− tk)Pn,k+1(t)+(tn− t)Pn−1,k(t)

). (4)

Somit gelten

P(tn) = Pn,k+1(tn) = f (tn) und P(tk) = Pn−1,k(tk) = f (tk)

und für k < j < n gilt

P(t j) =1

tn− tk

(f (ti)(t j− tk)+ f (ti)(tn− t j)

)= f (t j).

Außerdem folgt

P′(t) =1

tn− tk

(Pn,k+1(t)−Pn−1,k(t)+(t− tk)P′n,k+1(t)+(tn− t)P′n−1,k(t)

),

und damit P′(ti) = 1tn−tk

((ti− tk)P′n,k+1(ti) + (tn− ti)P′n−1,k(ti)

). Daraus lässt sich able-

sen, dass P auch für doppelte Stützstellen die Interpolationseigenschaft erfüllt (analog für

74

weitere Ableitungen). Also ist P ∈ Pn−k Interpolation zu f an tk, . . . , tn. Mittels Koeffizi-entenvergleichs von

( ddt

)n−1P folgt dann die Behauptung:

f [tk, . . . , tn] =1

(n− k)!

(ddt

)n−k

P(t)

=1

(n− k)!1

tn− tk

(ddt

)n−k(tP1(t)− tP0(t)

)=

1tn− tk

(f [tk+1, . . . , tn]− f [tk, . . . , tn−1]

).

Zu b) Das Taylor-Polynom

P(t) =n−k

∑j=0

1j!

(ddt

) j

f (tk)(t− tk) j

interpoliert f an tk = · · ·= tn, d.h. es gilt

P(t) =n−k

∑j=0

f [tk, . . . , tk+ j](t− tk) j

Damit folgt

1(n− k)!

(ddt

)n−k

P(t) = f [tk, . . . , tn] =1

(n− k)!

(ddt

)n−k

f (tk).

75

Algorithmus 5 Polynom-Interpolation mit dem Neville-Schema.

function y = eval_neville(t,f,x)N = length(t);for k=1:N-1

for n=N:(-1):k+1if t(n) ~= t(n-k)f(n) = ((x-t(n-k))*f(n) + (t(n)-x)*f(n-1)) / (t(n) - t(n-k));

endend

endy = f(N);

return

function f = koeffizienten_neville(t,f)N = length(t);for k=1:N-1

for n=N:(-1):k+1if t(n) ~= t(n-k)f(n) = (f(n) - f(n-1)) / (t(n) - t(n-k));

endend

endreturn

function y = eval_poylnom(t,b,x)N = length(t);y = b(1);p = 1;for n=2:N

p = p * (x - t(n-1));y = y + b(n) * p;

endreturn

76

BeispielMit Hilfe des vorhergehenden Lemmas lässt sich nun relativ einfach das Interpolations-polynom berechnen (also die Koeffizienten bezüglich der Newton-Basis). Ferner kann mandas Interpolationspolynom auswerten, ohne das Polynom explizit berechnen zu müssen.Wir werden dies hier an einem Beispiel illustrieren. Das Schema, mit dem man die Aus-wertung vornimmt, nennt man Neville-Schema.Betrachte dazu die Stützstellen tn = n für n = 0, . . . ,3. Die Funktionswerte seien f (0) =1, f (1) = 2, f (2) = 0 und f (3) = 1. Dann lautet das Neville-Schema:

tn f [tn]0 11 2 f [0,1] = 12 0 f [1,2] =−2 f [0,1,2] =−3

23 1 f [2,3] = 1 f [1,2,3] = 3

2 f [0,1,2,3] = 1

Die gesuchten Koeffizienten stehen dann auf der Hauptdiagonalen, also ist

P3(t) = 1+1(t−0)− 32(t−0)(t−1)+1(t−0)(t−1)(t−2)

= t3− 92

t2 +92

t +1.

Mit Gleichung (4) funktioniert die Auswertung an einer bestimmten Stelle. Wir wählent = 4 und berechnen

tn f [tn]0 1

1 24−01−0

·2+ 1−41−0

·1 = 5

2 04−12−1

·0+ 2−42−1

·2 =−4 −13

3 14−23−2

·1+ 3−43−2

·0 = 2 5 11 = P3(4)

Für die Auswertung des Interpolationspolynoms bzw. der Berechnung der Koeffizientenwerden O(N2) Operationen benötigt.

(8.10) Satz (Hermite-Genocchi-Formel)Es sei ΣN der Standard N-Simplex (Dreieck für N = 2, Tetraeder für N = 3), d.h.

ΣN =

s0

...sN

∈ RN+1 :N

∑n=0

sn = 1 ,sn ≥ 0

mit s0 = 1− (s1 + · · ·+ sN). Dann gilt

f [t0, . . . , tN ] =∫

ΣN

(ddt

)N

f

(N

∑n=0

sntn

)ds .

77

Es gilt für die Integration im Standardsimplex

∫ΣN

g(s)ds =∫

∑Nn=1 sn≤1sn≥0

g(

1−N

∑n=1

sn,s1, . . . ,sN

)ds

=

1∫0

1−s1∫0

1−s1−s2∫0

· · ·1−s1−...−sN−1∫

0

g(

1−N

∑n=1

sn︸ ︷︷ ︸=s0

,s1, . . . ,sN

)dsN · · · ds1 .

Beweis. Falls t0 = . . .= tN so gilt t0 = ∑N+1n=1 sntn für s ∈ ΣN , also

f [t0, . . . , tN ] =1

N!

(ddt

)N

f (t0) =∫

ΣN

(ddt

)N

f (t0)ds .

Für N = 0 haben wir f [t0] = f (t0).N→ N +1: Ohne Einschränkung gelte t0 6= tN+1.

∫ΣN+1

(ddt

)N+1

f

(N+1

∑n=0

sntn

)ds =

∫∑

N+1n=1 sn≤1

sn≥0

(ddt

)N+1

f

(t0 +

N+1

∑n=1

sn(tn− t0)

)ds

=∫

∑Nn=1 sn≤1sn≥0

1−∑Nn=0 sn∫

0

(ddt

)N+1

f

(t0 +

N

∑n=1

sn(tn− t0)+ sN+1(tN+1− t0)

)dsN+1 dsN · · · ds1

=∫

∑Nn=1 sn≤1sn≥0

1tN+1− t0

(ddt

)N

f

(t0 +

N

∑n=1

sn(tn− t0)+ sN+1(tN+1− t0)

)∣∣∣∣∣sN+1=1−∑

Nn=1 sn

sN+1=0

dsN · · · ds1

=1

tN+1− t0

∫∑

Nn=1 sn≤1sn≥0

[( ddt

)N

f

(tN+1 +

N

∑n=1

sn(tn− tN+1)

)

−(

ddt

)N

f

(t0 +

N

∑n=1

sn(tn− t0)

)]dsN . . . ds1

I.V.=

1tN+1− t0

( f [t1, . . . , tN+1]− f [t0, . . . , tN ]) = f [t0, . . . , tN+1] .

78

9 Splines

Beispiel (Periodische kubische Bezier-Splines)Aufgabe: Seien y0, . . . ,yM ∈ R2 Punkte in der Ebene mit y0 = yM gegeben. Verbinde diePunkte durch eine glatte periodische Kurve.Ansatz: Wähle stückweise kubische Polynome Pm : R→ R2 für m = 1, . . . ,M mit

Pm(0) = ym−1, Pm(1) = ym,

P′m(0) = P′m−1(1),P′′m(0) = P′′m−1(1).

Dabei setze P0 = PM und PM+1 = P1.Damit ergeben sich 8M Bedingungen für 8M Koeffizienten. Es stellt sich nun die Frage,ob dieses lineare System lösbar ist.

1. Schritt: Wähle geeignete Polynombasis: Verwende die Bernstein-Polynome

(1− t)3, 3(1− t)2t, 3(1− t)t2, t3

(und nicht die Monom-Basis 1, t, t2, t3, . . . ). Dann ist folgende Zerlegung der 1möglich:

1 = 1N =((1− t)+ t

)N=

N

∑k=0

(Nk

)(1− t)N−ktk .

2. Schritt: Für die Koeffizienten bm,0, . . . ,bm,3 ∈ R2 (Kontrollpunkte) wähle den Ansatz

Pm(t) := (1− t)3bm,0 +3(1− t)2tbm,1 +3(1− t)t2bm,2 + t3bm,3.

Aus der Interpolationseigenschaft folgt zunächst

Pm(0) = bm,0 = ym−1,

Pm(1) = bm,3 = ym.

Dann lauten die ersten zwei Ableitungen

P′m(t) = −3(1− t)2ym−1 +3(1−4t +3t2)bm,1 +3(2t−3t2)bm,2 +3t2ym,

P′′m(t) = 6(1− t)ym−1 +3(−4+6t)bm,1 +3(2−6t)bm,2 +6tym.

3. Schritt: Bedingungen für die Glattheit: Nach Aufgabenstellung soll gelten

P′m(1) =−3bm,2 +3ym != P′m+1(0) =−3ym +3bm+1,1 .

Damit ergibt sich

ym =12(bm,2 +bm+1,1) .

79

Außerdem soll gelten

P′′m(1) = 6bm,1−12bm,2 +6ym != P′′m+1(0) = 6ym−12bm+1,1 +6bm+1,2,

woraus

−bm,1 +2bm,2 = 2bm+1,1−bm+1,2 =: dm

folgt. Die Punkte dm nennen wir de-Boor-Punkte.

4. Schritt: Daher erhalten wir eine Lösung der Aufgabe durch die Berechnung der dm.Aus der Definition der de-Boor-Punkte folgt

dm−1 +4dm +dm+1 = 2bm,1−bm,2 +2(−bm,1 +2bm,2)

+2(2bm+1,1−bm+1,2)+(−bm+1,1 +2bm+1,2)

= 3(bm,2 +bm+1,1) = 6ym.

In Matrixschreibweise lautet dieses Gleichungssystem dann, aufgespaltet in diezwei Komponenten:

16

4 1 11 4 1

1 4. . . 1

1 1 4

d1i......

dMi

=

y1

i......

yMi

i = 1,2 .

Die Matrix ist strikt diagonal-dominant und daher regulär. Daher sind die de-Boor-Punkte eindeutig definiert, und die weiteren Kontrollpunkte berechnensich mit

bm,1 =23

dm−1 +13

dm , bm,2 =13

dm−1 +23

dm .

(9.1) DefinitionSei r ≥ 0 und k = 2r+1 ∈ N.

a) Zu einer Zerlegung ∆ : a = t0 < t1 < · · · < tN = b des Intervalls [a,b] definiere denSpline-Raum vom Grad k durch

Sk(∆) :=

S ∈Ck−1[a,b] : Sn = S|[tn−1,tn] ∈ Pk, n = 1, . . . ,N

.

Wir nehmen ferner an, dass k ≤ N ist.

b) Sei f ∈C[a,b]. S ∈S heißt interpolierender Spline zu f , wenn gilt:

S(tn) = f (tn) , n = 0, . . . ,N .

(9.2) SatzEs gilt dimSk(∆) = N + k.

80

Beweis. i) Zeige dimSk(∆)≥ N + k.Dazu definiere

ϕn(t) =

(t− t0)k+n −k ≤ n≤ 0max0, t− tnk 0 < n < N .

Wir zeigen, dass ϕn−k,...,N−1 ⊆Sk(∆) linear unabhängig ist. Dazu betrachte

S(t) :=k

∑m=0

αm(t− t0)m +N−1

∑n=1

βnϕn(t)≡ 0 .

Sei zunächst t ∈ (t0, t1]. Dann ist

S(t) =k

∑m=0

αm(t− t0)m ≡ 0 ,

also ist αm = 0 für alle m = 0, . . . ,k, da t − t0 > 0 für t ∈ (t0, t1] ist. Daher fallen alleMonome weg. Es bleiben noch die abgebrochenen Potenzen ϕn(t). Für t ∈ (t1, t2] gilt

S(t) = β1ϕ1(t) = 0

und es folgt β1 = 0. Analog folgt für t ∈ (tn−1, tn]

S(t) = βn−1ϕn−1(t) = 0

und somit folgt induktiv βn = 0 für alle n = 1, . . . ,N−1. Also gilt dimSk(∆)≥ N + k.ii) Zeige dimSk(∆)≤ N + k.Sei dazu S∈Sk(∆) und definiere die Einschränkung Sn := S|[tn−1,tn] ∈Pk. Da S∈Ck−1[a,b]ist, folgt (

ddt

)m

Sn(tn) =(

ddt

)m

Sn+1(tn) (n = 1, . . . ,N−1, m = 0, . . . ,k−1).

Das sind (N− 1)k lineare Bedingungen. Da Sn ∈ Pk ist, stehen also zunächst höchstensN · dimPk = N(k+ 1) Freiheitsgrade zur Verfügung. Andererseits werden (N− 1)k Frei-heitsgrade benötigt, um die Glattheitsbedingungen zu gewährleisten. Also gilt

dimSk(∆)≤ N(k+1)− (N−1)k = N + k.

(9.3) DefinitionBei einem interpolierende Spline vom Grad k = 2r+ 1 sind also erst N + 1 Freiheitsgra-de festgelegt. Demnach fehlen zur eindeutigen Bestimmung eines interpolierenden Splinesnoch 2r Bedingungen. Ein interpolierender Spline kann folglich durch zusätzliche Rand-bedingungen (RB) eindeutig bestimmt werden.

(I) Den Splineraum mit natürlichen Randbedingungen bezeichnen wir mit

Sk,0(∆) :=

S ∈Sk(∆) :( d

dt

)m

S(a)=(

ddt

)m

S(b)= 0 für alle r+1≤m≤ 2r.

81

(II) Die Hermite-Randbedingungen zu f ∈Cr[a,b] seien für 1≤ m≤ r gegeben durch(ddt

)m

S(a) =(

ddt

)m

f (a) und(

ddt

)m

S(b) =(

ddt

)m

f (b) .

(III) Den Splineraum mit periodischen Randbedingungen bezeichnen wir mit

Sk,per(∆) :=

S∈Sk(∆) :(

ddt

)m

S(a) =(

ddt

)m

S(b) für alle 1≤m≤ 2r.

Einführung in die Variationsrechnung

Wir definieren die Seminorm

|g|2 =(∫ b

a|g′′|2 dt

) 12

= ‖g′′‖0 mit ‖v‖0 =

(∫ b

av2 dt

) 12

in L2(a,b) .

(9.4) SatzZu einer Zerlegung a≤ t0 < t1 < .. . < tN ≤ b und Werten f0, . . . , fN ∈R (N ≥ 2) definiere

M =

g ∈C2[a,b] : g(tn) = fn, n = 0, . . . ,N.

Dann gilt: Es existiert genau ein S ∈M mit |S|2 ≤ |g| für alle g ∈M.Für S gilt S′′(t) = 0 für t ∈ [a, t0]∪ [tN ,b] und Sn = S|[tn−1,tn] ∈ P3.

Beweis. (i) Sei V0 = C2[a,b] euklidischer Vektorraum mit 〈v,w〉V = 〈v,w〉0 + 〈v′′,w′′〉0Sei V Vervollständigung von V0 bezüglich ‖ · ‖V . Damit ist V ein Hilbertraum. Sei M ⊂Vabgeschlossen und konvex, d.h. u,v ∈M,λ ∈ (0,1) =⇒ (1−λ )u+λv ∈M.(ii) Definiere F(g) = 1

2 |g|22.

Zeige: F(·) ist gleichmäßig konvex auf M, d.h. es existiert ein c0 > 0 für mit

F ((1−λ )u+λv)+ c0(1−λ )λ‖u− v‖2V ≤ (1−λ )F(u)+λF(v), u,v ∈M, λ ∈ (0,1) .

Es gilt

|(1−λ )u+λv|22 = (1−λ )2|u|22 +2(1−λ )λ 〈u,v〉2 +λ2|v|22

= (1−λ )|u|22 +(λ 2−λ )|u|22 +2(λ −λ2)〈u,v〉2 +(λ 2−λ )|v|22 +λ |v|22 .

Daraus folgt:

F ((1−λ )u+λv) = (1−λ )F(u)− 12(λ −λ

2)|u− v|22 +λF(v)

Für z = u−v gilt z(tn) = 0 (n = 0, . . . ,N). Somit existiert ξn ∈ (tn−1, tn) (n = 1, . . . ,N)mit z′(ξn) = 0. Daraus folgt:

‖z‖20 =

∫ b

a|z(t)|2 dt =

N

∑n=1

∫ tn

tn−1

|z(t)|2 dt =N

∑n=1

∫ tn

tn−1

|z(t)− z(tn−1)|2 dt =N

∑n=1

∫ tn

tn−1

∣∣∣∫ t

tn−1

z′(s)ds∣∣∣2 dt

82

und somit für h = max tn− tn−1

‖z‖20 =

N

∑n=1

∫ tn

tn−1

∣∣∣∫ t

tn−1

(z′(s)− z′(ξn))ds∣∣∣2 dt

=N

∑n=1

∫ tn

tn−1

∣∣∣∫ t

tn−1

∫ s

ξn

z′′(τ)dτ ds∣∣∣2 dt

=N

∑n=1

∫ tn

tn−1

∣∣∣∫ t

tn−1

∫ s

ξn

1 · z′′(τ)dτ ds∣∣∣2 dt

CSU≤

N

∑n=1

∫ tn

tn−1

∣∣∣∫ t

tn−1

[∫ s

ξn

1dτ

]1/2[∫ s

ξn

| · z′′(τ)|2 dτ

]1/2

ds∣∣∣2 dt

CSU≤

N

∑n=1

∫ tn

tn−1

∫ t

tn−1

|s−ξn|ds∫ t

tn−1

∫ s

ξn

| · z′′(τ)|2 dsdt ≤ h4|z|22 .

Mit der Definition von ‖ · ‖V erhalten wir ‖z‖2V = ‖z‖2

0 + |z|22 ≤(h4 +1

)︸ ︷︷ ︸=:C

|z|22.

Es gilt also |z|22 ≥1C‖z‖

2V und für c0 = 1/(2C)

F ((1−λ )u+λv)+ c0(1−λ )λ‖u− v‖2V ≤ F ((1−λ )u+λv)+ c0C︸︷︷︸

12

(1−λ )λ‖u− v‖22

≤ (1−λ )F(u)+λF(v) .

Mit λ = 12 ergibt sich

F(1

2u+

12

v)+

c0

4‖u− v‖2

V ≤12

F(u)+12

F(v) .

(iii) Sei F∗ = infg∈M

F(g)≥ 0. Wähle eine Minimalfolge vn ⊂M , d.h. limn→∞

F(vn) = F∗.

Mit (ii) folgt

c0

4‖vn− vk‖2

V ≤12

F(vn)+12

F(vk)−F(

12

vn +12

vk

)≤ 1

2F(vn)+

12

F(vk)−F∗ −→n,k→∞

0

vn ist also eine Cauchyfolge in M und somit existiert ein S ∈M mit limn→∞

vn = S (d.h. es

gilt limn→∞‖vn−S‖V = 0).

(iv) Zeige: F∗ = F(S)⇐⇒ 〈S,S−g〉2 = 0 ∀g ∈MEs gilt für µ ∈ R

0≤ F (S+µ(S−g))−F∗ =12|S|2 +µ〈S,S−g〉2 +

12

µ2|S−g|22−

12|S|22

= µ

(〈S,S−g〉2 +

µ

2|S−g|22

).

Daraus folgt “⇐”.“⇒”: Annahme: 〈S,S−g〉2 6= 0Wähle µ =− 〈S,S−g〉2

2|S−g|22∈ R. Das ergibt den Widerspruch

0≤−12〈S,S−g〉22|S−g|22

Annahme< 0 .

83

(v) Nach (iv) gilt 〈S,u〉2 = 0 für alle u ∈C2[a,b] mit u(tn) = 0 für n = 0, . . . ,N, also

0 =∫ b

aS′′u′′ dt =

∫ t0

aS′′(t)u′′(t)dt +

N

∑n=1

∫ tn

tn−1

S′′(t)u′′(t)dt +∫ b

tNS′′(t)u′′(t)dt .

Falls S′′(t) 6= 0 für ein t ∈ [a, t0)∪(tN ,b], dann wähle u∈C2[a,b] mit u(s)= 0 für s∈ [t0, tN ],S′′(s)u′′(s)≥ 0 für s ∈ [a,b] und S′′(t)u′′(t)> 0. Dann wäre 0 <

∫ ba S′′u′′ dt, Widerspruch!

Also ist S′′(t) = 0 für t ∈ [a, t0)∪ (tN ,b], und somit gilt

0 =∫ b

aS′′u′′ dt =

N

∑n=1

∫ tn

tn−1

S′′(t)u′′(t)dt =N

∑n=1

S′′(t)u′(t)∣∣tntn−1−∫ tn

tn−1

S′′′n (t)u′(t)dt

= S′′(tN)u′(tN)−S′′(t0)u′(t0)− S′′′n (t)u(t)∣∣tntn−1︸ ︷︷ ︸

=0

+∫ tn

tn−1

S(4)n (t)u(t)dt .

Falls S(4)n (t) 6= 0 für ein t ∈ (tn−1, tn), wähle u∈C2[a,b] mit u(s)= 0 für s∈ [a, tn−1]∪ [tn,b],S(4)n (s)u(s)≥ 0 in [a,b] und S(4)n (t)u(t)> 0. Dann wäre 0 <

∫ ba S′′u′′ dt, Widerspruch! Also

ist S(4)n ≡ 0 in (tn−1, tn), d.h., Sn ∈ P4. Also gilt 0 = S′′(tN)u′(tN)− S′′(t0)u′(t0). Mit demgleichen Argument zeigen wir die natürlichen Randbedingungen S′′(tN) = 0 = S′′(t0).

Existenz und Eindeutigkeit der Spline-Interpolation(9.5) DefinitionDefiniere für g, h ∈Cm[a,b] das Skalarprodukt

〈g,h〉m :=∫ a

b

(ddt

)m

g(t)(

ddt

)m

h(t)dt

und die Seminorm

|g|m :=√〈g,g〉m .

Im folgenden sei N ≥ r.

(9.6) SatzSei S ∈S2r+1(∆) ein interpolierender Spline zu f und sei zusätzlich eine der Randbedin-gungen (I), (II) oder (III) erfüllt.Sei g ∈Cr+1[a,b] mit g(tn) = f (tn) für n = 0, ...,N, und zusätzlich gelteim Fall (II)(

ddt

)m

g(a) =(

ddt

)m

f (a) und(

ddt

)m

g(b) =(

ddt

)m

f (b) für 1≤ m≤ r

und im Fall (III)(ddt

)m

g(a) =(

ddt

)m

g(b) für 1≤ m≤ r.

Dann gelten

〈S−g,S〉r+1 = 0 und |S|r+1 ≤ |g|r+1.

84

Beweis. i) Zeige zunächst 〈g−S,S〉r+1 = 0.Es gilt

〈g−S,S〉r+1Def.=

∫ a

b

(ddt

)r+1

(g−S)(t)(

ddt

)r+1

S(t)dt

=

(ddt

)r

(g−S)(t)(

ddt

)r+1

S(t)

∣∣∣∣∣b

a

−∫ b

a

(ddt

)r

(g−S)(t)(

ddt

)r+2

S(t)dt

=r−1

∑j=0

(−1) j(

ddt

)r− j

(g−S)(t)︸ ︷︷ ︸=0 im Fall (II),(III)

(ddt

)r+1+ j

S(t)︸ ︷︷ ︸=0 im Fall (I)

∣∣∣ba

+(−1)rN

∑n=1

∫ tn

tn−1

(g−S)′(t)(

ddt

)2r+1

S(t)︸ ︷︷ ︸konstant

dt

= (−1)rN

∑n=1

(ddt

)2r+1

Sn(t)∫ tn

tn−1

(g−S)′(t)dt︸ ︷︷ ︸(g−S)|tntn−1

=0

.

ii) Nun zeige |S|r+1 ≤ |g|r+1.Es gilt mit i) 〈g,S〉r+1 = 〈S,S〉r+1 und damit

0≤ |g−S|2r+1 = |g|2r+1−2〈g,S〉r+1 + |S|2r+1

= |g|2r+1−2〈S,S〉r+1 + |S|2r+1 = |g|2r+1−|S|2r+1 .

BemerkungFür k = 3 gilt, dass der kubische Spline mit natürlichen Randbedingungen die Krümmungminimiert, d.h., es gilt

∫ b

a|S′′(t)|2dt ≤

∫ b

a|g′′(t)|2dt

für alle interpolierenden Funktionen g.

(9.7) FolgerungDie Spline-Interpolation S ∈S2r+1(∆) zu f mit einer der Randbedingungen (I), (II), (III)ist eindeutig lösbar.

Beweis. Seien S, S zwei Lösungen. Dann gilt

|S− S|r+1 = |S|2r+1−2 〈S, S〉r+1︸ ︷︷ ︸=〈S,S〉r+1, da S Lsg.

+|S|2r+1 = |S|2r+1−|S|2r+1 ≤ 0 ,

85

da S als Lösung die Seminorm | · |r+1 minimiert. Also ist |S− S|r+1 = 0 und es folgt(ddt

)r+1

(S− S)≡ 0 .

Also ist S− S ∈ Pr. Da S− S aber N +1 Nullstellen hat, folgt S− S≡ 0 aus r ≤ N.

Nun untersuchen wir, wie man für ein gegebenes Interpolationsproblem den zugehörigenkubischen Spline (k = 3) berechnen kann.

(9.8) SatzDie Momente Mn = S′′(tn) des Interpolationssplines S ∈S3(∆) zu f erfüllen

µnMn−1 +Mn +λnMn+1 = 3 f [tn−1, tn, tn+1]

mit µn =hn

2(hn+hn+1), λn =

hn+12(hn+hn+1)

, hn = tn− tn−1.

BemerkungIm Fall hn := h und tn := a+nh gilt µn = λn =

14 , µn +λn =

12 .

Beweis. i) Sn ∈ P3 ist durch f (tn−1), f (tn), Mn−1, Mn bestimmt, denn es gilt (einfachesNachrechnen)

Sn(t) =Mn(t− tn−1)

3 +Mn−1(tn− t)3

6hn

+

(f (tn)− f (tn−1)

hn− hn

6(Mn−Mn−1)

)(t− tn + tn−1

2

)+

f (tn)+ f (tn−1)

2− h2

n12

(Mn +Mn−1) .

ii) Aus der Stetigkeit von S′ folgt

S′n(tn) =12

Mnhn + f [tn−1, tn]−hn

6(Mn−Mn−1) ,

S′n+1(tn) = −12

Mnhn+1 + f [tn, tn+1]−hn+1

6(Mn+1−Mn) .

Gleichsetzen liefert

(hn +hn+1) f [tn−1, tn, tn+1] = f [tn, tn+1]− f [tn−1, tn]

=hn +hn+1

3Mn +

hn

6Mn−1 +

hn+1

6Mn+1 .

SplineberechnungDurch die Berechnung der Momente können wir jetzt, wie man im vorherigen Beweisgesehen hat, den interpolierenden Spline erhalten. Die Momente erhalten wir durch dasLösen eines zu den Randbedingungen passenden Gleichungssystems:

86

(I) Im Fall M0 = MN = 0 löse1 λ1µ2 1 λ2

. . . . . . . . .µN−2 1 λN−2

µN−1 1

︸ ︷︷ ︸

A

M1......

MN−1

= 3

f [t0, t1, t2]

...

...f [tN−2, tN−1, tN ]

︸ ︷︷ ︸

b

,

wobei µi +λi =12 . Damit ist A strikt diagonal-dominant und somit regulär.

(II) Im Fall S′(a) = f ′(t0) = f [t0, t0], S′(b) = f ′(tN) = f [tN , tN ] löse1 λ0µ1 1 λ1

. . . . . . . . .µN−1 1 λN−1

µN 1

M0......

MN

= 3

f [t0, t0, t1]f [t0, t1, t2]

...f [tN−1, tN , tN ]

mit λ0 = µN = 1

2 . Dabei muss im Beweis des letzten Satzes noch eine eigene Rand-punktbetrachtung durchgeführt werden.

(III) Im Fall S′(a) = S′(b) und M0 = S′′(a) = S′′(b) = MN löse1 λ1 µ1µ2 1 λ2

. . . . . . . . .µN−1 1 λN−1

λN µN 1

M1......

MN

= 3

f [t0, t1, t2]

...

...f [tN−1, tN , tN+1]

mit λN = h1

2(hN+h1), µN = hN

2(hN+h1). Dabei setze tN+1 = tN +h1 und f (tN+1) = f (t1).

87

Fehlerabschätzung für kubische Splines bezüglich der Maximumsnorm(9.9) DefinitionZur Zerlegung a = t0 < t1 < · · · < tN = b definieren wir die Schrittweiten hn = tn− tn−1und die Feinheit h = max

n=1,...,Nhn.

(9.10) LemmaSei f ∈C2[a,b] und S ∈S3(∆) zu f mit Randbedingungen (I),(II) oder (III) (vgl. (9.6)).Dann gilt:

‖S′′‖∞ ≤ 3‖ f ′′‖∞

Beweis. Es gilt für M = (Mn):AM = b

mit A = tridiag(µn,1,λn), µn +λn =12 und b = 3( f [tn−1, tn, tn+1]).

Es gilt f [tn−1, tn, tn+1] =12 f ′′(τ j) für τ j ∈ (tn−1, tn+1).

Mit der Neumannschen Reihe erhalten wir

A−1 = (I− (I−A))−1 = ∑k≥0

(I−A)k .

Mit ‖I−A‖∞ = max|λn|+ |µn|= 12 folgt

‖A‖−1∞ ≤

∑k=0‖I−A‖k

∞ =∞

∑k=0

(12

)k

= 2 .

Aus |b|∞ ≤ 32‖ f ′′‖∞ folgt dann insgesamt

‖S′′‖∞ = |M|∞ = |A−1b|∞ ≤ 2|b|∞ = 3‖ f ′′‖∞ .

(9.11) SatzSei f ∈C4[a,b].Dann gilt für S ∈S3(∆) zu f mit einer der Randbedinungen (I), (II) oder (III):

‖S− f‖∞ ≤ h4

∥∥∥∥∥(

ddt

)4

f

∥∥∥∥∥∞

.

Beweis. (i) Sei L ∈S1(∆) linearer interpolierender Spline zu f ′′. Definiere

v(t) =∫ t

t0(t− s)L(s)ds .

Dann gilt v′(t) =∫ t

t0 L(s)ds und v′′(t) = L(t). Also ist v ∈S3(∆) und S = S− v ist Splinezu f − v, und es gilt

‖S′′− f ′′‖∞ = ‖(S− v)′′+( f − v)′′‖∞ ≤ ‖(S− v)′′‖∞ +‖( f − v)′′‖∞

≤(9.10)

4‖ f ′′− v′′‖∞ = 4‖ f ′′−L‖∞ .

88

(ii) Für u = f ′′−L gilt

u(tn) = 0 n = 0, . . . ,Nu′(τn) = 0 n = 1, . . . ,N mit τn ∈ (tn−1, tn)

Dann gilt

u(t) =∫ tn

tn−1

u′(s)ds =∫ tn

tn−1

∫ s

τn

u′′(τ)dτ ds t ∈ (tn−1, tn)

Es folgt

‖u‖∞ ≤ ‖u′′‖∞

∫ tn

tn−1

∫ s

τn

dτ ds︸ ︷︷ ︸∫ ttn−1

(s−τn)ds

≤ 12

h2‖u′′‖∞

Zusammen erhalten wir ‖S′′− f ′′‖∞ ≤ 2h2‖ f (4)‖∞ .(iii) Für w(t) = (S− f )(t) gilt w(tn) = 0 für n = 0, . . . ,N. Daraus folgt

‖S− f‖∞ = ‖w‖∞ ≤12

h2‖w′′‖∞ ≤ h4‖ f (4)‖∞ .

(9.12) SatzEs gilt für m = 0, . . . ,r und h = maxn=1,...,N hn, hn = tn− tn−1 die Fehlerabschätzung

|S− f |m ≤ 2−(r+1−m)

2(r+1)!

m!hr+1−m| f |r+1 .

Beweis. Setze u(t) := S(t)− f (t). Dann gilt u(tn) = 0, also hat u mindestens N +1 Null-stellen λ 0

n := tn. Mit dem Satz von Rolle folgt, dass u′(t) = 0 an mindestens N Stellenλ 1

n ∈ (λ 0n−1,λ

0n ) gilt. Induktiv folgt, dass

( ddt

)mu(t) mindestens N + 1−m Nullstellen

λ mn ∈ (λ m−1

n−1 ,λ m−1n ) hat. Setze λ m

0 = a, λ mN+2−m = b. Dann gilt

∫λ m

n

λ mn−1

∣∣∣∣( ddt

)m

u(t)∣∣∣∣2 dt =

∫λ m

n

λ mn−1

∣∣∣∣∣∫ t

λ mn−1

(dds

)m+1

u(s)ds

∣∣∣∣∣2

dt

CSU≤

∫λ m

n

λ mn−1

∫ t

λ mn−1

12ds∫ t

λ mn−1

∣∣∣∣∣(

dds

)m+1

u(s)

∣∣∣∣∣2

dsdt

≤∫

λ mn

λ mn−1

(t−λmn−1)dt︸ ︷︷ ︸

(∗)

∫λ m

n

λ mn−1

∣∣∣∣∣(

dds

)m+1

u(s)

∣∣∣∣∣2

ds.

Dabei gilt in (∗) die Abschätzung

∫λ m

n

λ mn−1

(t−λmn−1)dt =

12(λ m

n −λmn−1)

2 ≤ 12((m+1)h)2

89

und wir erhalten∫ b

a

∣∣∣∣( ddt

)m

u(t)∣∣∣∣2 dt =

N+2−m

∑n=1

∫λ m

n

λ mn−1

∣∣∣∣( ddt

)m

u(t)∣∣∣∣2 dt

≤ 12(m+1)2h2

∫ b

a

∣∣∣∣∣(

ddt

)m+1

u(t)

∣∣∣∣∣2

dt.

Wiederholtes Anwenden ergibt

|u|m ≤ 1√2(1+m)h|u|m+1 =

1√2(m+1)!

m!h |u|m+1

≤ ·· · ≤(

1√2

)r+1−m (r+1)!m!

hr+1−m |u|r+1 ,

und Einsetzen von |u|2r+1 = |S− f |2r+1 = | f |2r+1−|S|2r+1 ≤ | f |2r+1 ergibt die Behauptung.

BeispielFür kubische Splines (k = 3, r = 1) und m = 0 ergibt sich |S− f |0 ≤C h2 | f |2.

Kubische Ausgleichssplines

Zu −∞ < a < b < ∞ definire V = g ∈C2[a,b] : g(a) = g(b) = 0.Gegeben sei eine Zerlegung ∆ = a = t0 < t1 < · · · < tN = b, Werte f1, . . . , fN−1 ∈ R undδ > 0. Definiere

G(g) =12

(N−1

∑n=1|g(tn)− fn|2− (N−1)δ 2

)≤ 0

M = g ∈V : G(g)≤ 0

(9.13) SatzEs existiert genau ein S ∈M∩S3,0(∆) mit |S|2 ≤ |g|2 ∀g ∈M.

Beweis. Definiere L(g,λ ) = 12 |g|

22 +λG(g) für g ∈V und λ ≥ 0 .

(i) Zeige: Wenn (S,λ ) ∈V ×R≥0 Sattelpunkt von L ist, d.h.

L(S,µ)≤ L(S,λ )≤ L(g,λ ) für alle g ∈V und µ ≥ 0 ,

dann gilt S ∈M und |S|2 ≤ |g|2 ∀g ∈M, denn

a) Aus µG(S)≤ λG(S) ∀µ ≥ 0 folgt G(S)≤ 0 mit µ = λ +1; also gilt S ∈M.

b) Es gilt G(S)≤ 0, λ ≥ 0. Annahme: G(S)< 0, λ > 0.Mit µ = 1

2λ folgt 0≤ 12λG(S)< 0. Widerspruch! Also gilt λG(S) = 0.

c) Aus g ∈M folgt

12|S|22 = L(S,λ ) ≤

λ≥0G(g)≤0

12|g|22 .

90

(ii) Zeige: Wenn (S,λ ) Sattelpunkt ist mit Sn = S|[tn−1,tn] ∈C4[tn−1, tn] (n = 1, . . . ,N)

dann gilt S(4)n ≡ 0, S′′(a) = S′′(b) = 0 und

S′′′n+1(tn)−S′′′n (tn) = λ (S(tn)− fn) , n = 1, ...,N−1 ,

denn:

d) Sei DgL(S,λ ) = 〈S,g〉2 +λ ∑N−1n=1 (S(tn)− fn)g(tn) die Ableitung bezüglich g.

Behauptung: DgL(S,λ ) = 0 für alle g ∈V .Es gilt L(S+µg,λ ) = L(S,λ )+µDgL(S,λ )+ 1

2 |µg|2 +λ ∑N−1n=1 |µg(tn)|2.

Annahme: DgL(S,λ ) 6= 0.Dann gilt auch g 6= 0 und damit 1

2 |g|2 +λ ∑

N−1n=1 |g(tn)|2 6= 0.

Definiere µ =−12

DgL(S,λ )12 |g|2+λ ∑

N−1n=1 |g(tn)|2

. Dann folgt aus L(S,λ )≤ L(S+µg,λ )

0≤ µDgL(g,λ )+µ2(1

2|g|2 +λ

N−1

∑n=1|g(tn)|2

)=−1

2L(S,λ )< 0 .

Widerspruch!

e) Annahme: Es existiert ein τ ∈ (tn−1, tn) mit S(4)n (τ) 6= 0.Wähle g ∈ V mit g(t) = 0 für t ∈ [a, tn−1]∪ [tn,b], S(4)n (t)g(t) ≥ 0, S(4)n (τ)g(τ) > 0.Damit ergibt sich der folgende Widerspruch:

0 <∫ tn

tn−1

S(4)n (t)g(t)dt = S′′′n (t)g(t)∣∣tntn−1︸ ︷︷ ︸

=0

−∫ tn

tn−1

S′′′n (t)g′(t)dt

= −S′′n(t)g′(t)∣∣tntn−1︸ ︷︷ ︸

=0

+∫ tn

tn−1

S′′n(t)g′′(t)dt = DgL(S,λ ) = 0 .

f) Annahme: S′′(a) 6= 0. Wähle g ∈V mit g′(a) = 1,g(a) = 0 und g(t) = 0 für t ≥ t1:

0 = DgL(S,λ ) =∫ t1

aS′′(t)g′′(t)dt = S′′(t)g′(t)

∣∣t1a −

∫ t1

aS′′′(t)g′(t)dt

= S′′(a)− S′′′(t)g(t)∣∣t1a +

∫ t1

aS(4)(t)g(t)dt =−S′′(a) .

Analog zeigt man S′′(b) = 0.

g) Wähle g ∈V mit g(tn) = 1 und g′(tn) = 0 und g(t) = 0 für t ∈ [a, tn−1]∪ [tn+1,b]∫ tn+1

tn−1

S′′(t)g′′(t)dt = S′′(t)g′(t)∣∣tntn−1

+ S′′(t)g′(t)∣∣tn+1tn−∫ tn+1

tn−1

S′′′(t)g′(t)dt

= 0−S′′′n (tn)−S′′′n+1(tn)+∫ tn+1

tn−1

S(4)(t)︸ ︷︷ ︸≡0

g′(t)dt ,

also

0 = DgL(S,λ ) =−S′′′n (tn)+S′′′n+1(tn)+λ

N−1

∑n=1

(S(tn)− f (tn))g(tn)︸ ︷︷ ︸S(tn)− fn

.

91

(iii) Definiere x =

S(t1)...

S(tN−1)

, y =

S′′(t1)...

S′′(tN−1)

und b =

f1...

fN−1

. Mit (9.8) erhalten

wir dann Ay = T x mit den Tridiagonalmatrizen A,T ∈ R(N−1)×(N−1)

A =16

2(h1 +h2) h2h2 2(h2 +h3) h3

. . . . . . . . .

und T =

h−11 +h−1

2 −h−12

−h−12 h−1

2 +h−13 −h−1

3. . . . . . . . .

und

S′′′n+1(tn)−S′′′n (tn)︸ ︷︷ ︸=

yn+1−ynhn+1

− yn−yn−1hn

= λ (S(tn)− fn)

Also gilt −Ty = λ (x−b). Es folgt −T 2y = λT x−λT b = λAy−λT b und wegen λ > 0erhalten wir (A+λ−1T 2)y = T b.(iv) 1. Fall: Aus |b|22 = ∑ | fn|2 ≤ (N−1)δ 2 folgt, dass S≡ 0 zulässig ist, d.h. G(0)≤ 0.Also ist S≡ 0 Lösung.2. Fall: Sei nun |b|22 > (N−1)δ 2. Bestimme S ∈S3,0(∆) mit G(S) = 0. Es gilt

G(S) =12 ∑

n(S(tn)− fn)

2︸ ︷︷ ︸|x−b|22

−12

δ2(N−1)

Wegen x−b = λ−1Ty = λ−1T(A+λ−1T 2)−1 T b =

(λT−1AT−1 + IN−1

)−1 b gilt

G(S) = 0⇐⇒ 12|x−b|2 = 1

2(N−1)

⇐⇒ |(λT−1AT−1 + IN−1

)−1b|22 = (N−1)δ 2

Wir suchen also eine Nullstelle von

R(λ ) = |(λT−1AT−1 + IN−1

)−1b|22− (N−1)δ 2 .

Die Matrix T−1AT−1 is symmetrisch und positiv definit. Einsetzen der SpektralzerlegungT−1AT−1 = ∑ µ jw jwT

j ergibt

R(λ ) = ∑

(1

1+λ µ jbT w j

)2

− (N−1)δ 2

Also gilt R(0) = |b|22− δ 2(N− 1) > 0 und R(λ ) λ→∞−→ −δ 2(N− 1) < 0. Nach dem Zwi-schenwertsatz existiert somit ein λ > 0 mit R(λ ) = 0.Daraus berechnet sich y = (A+λ−1T 2)−1T b und x = T−1Ay und damit der Spline S.

Der Algorithmus zur Bestimmung des Ausgleichssplines lautet damit

S0) berechne A,T,b.

S1) bestimme λ mit R(λ ) = 0, z.B. mit dem Newton-Verfahren

S2) berechne y, berechne x, berechne S.

92

10 Numerische Integration

Beispiel (Keplersche Fassregel)Wir stellen uns ein Holzfass der Höhe H vor. Rmin bzw. Rmax sei der Radius des kleinstenbzw. größten Querschnitts des Fasses (also am Boden und in der Mitte). Für das Volumengilt dann

V ≈ Hπ

3(R2

min +2R2max).

Wie gut ist diese Approximation?

(10.1) DefinitionSei Ξ ⊆ [a,b]⊂R eine endliche Menge von Stützstellen ξ ∈Ξ und seien ωξ ∈R für ξ ∈Ξ

die Quadraturgewichte. Dann heißt

IΞ : C[a,b]→ R, IΞ ( f ) = ∑ξ∈Ξ

ωξ f (ξ )

Quadraturformel, und

EΞ ( f ) :=∫ b

af (t)dt− IΞ ( f )

heißt Quadraturfehler.Die Quadraturformel IΞ heißt exakt von der Ordnung p, wenn

EΞ (P) = 0 für alle P ∈ Pp .

Beispiel (Summierte Trapezregel)Für N ∈ N seien h := b−a

N und

Ξ := ξn = a+nh : n = 0, . . . ,N.

Definiere dann zu f ∈C[a,b] die Quadraturformel.

IΞ ( f ) :=N

∑n=1

h2

(f (ξn−1)+ f (ξn)

)=

h2

f (a)+hN−1

∑n=1

f (ξn)+h2

f (b) .

Zur Abschätzung des Quadraturfehlers betrachten wir den linearen Spline S f ∈ S1(Ξ) mitS f (ξn) = f (ξn). Damit ergibt sich

EΞ ( f ) =∫ b

af (t)dt− IΞ ( f ) =

∫ b

af (t)dt− IΞ (S f ) =

∫ b

a( f (t)−S f (t))dt .

Falls f ∈C2[a,b] gilt für den Interpolationsfehler und damit auch für den Quadraturfehler

|EΞ ( f )| ≤ (b−a)‖ f −S f ‖∞ ≤b−a

8h2‖ f ′′‖∞ .

Dabei ist ‖ f‖∞ := maxt∈[a,b] | f (t)| die Supremumsnorm.

93

BemerkungDie Konstruktion von Quadraturformeln basiert auf der Idee, eine Funktion zunächst zuinterpolieren und dann dieses Interpolationspolynom zu integrieren. Ist die Interpolationfür Polynome vom Grad N exakt, dann ist also auch die zugehörige Quadraturformel exaktvon der Ordnung N. Dies führt zum folgenden Satz.

(10.2) SatzSei |Ξ |= N +1 und IΞ sei exakt von der Ordnung p≥ N. Dann gilt

ωξ =∫ b

aLξ (t)dt mit Lξ (t) = ∏

η∈Ξ\ξ

t−η

ξ −η∈ PN .

Beweis. Da p≥ N, gilt PN ⊆ Pp und somit EΞ (Lξ ) = 0. Damit folgt

∫ b

aLξ (t)dt = IΞ (Lξ ) = ωξ Lξ (ξ ) = ωξ .

(10.3) DefinitionDie Quadraturformeln IN von der Ordnung N zu äquidistanten Stützstellen

ΞN = ξn := a+nb−a

N: n = 0, . . .N

heißen Newton-Cotes-Quadraturformeln. Nach Satz (10.2) gilt also für ωn zu ξn

ωn =∫ b

aLn(t)dt =

b−aN

∫ N

0Ln(a+ s

b−aN︸ ︷︷ ︸

=t

)ds =b−a

N

∫ N

0

N

∏k=0k 6=n

s− kn− k

ds

=b−a

N(−1)N−n

n!(N− k)!

∫ N

0

N

∏k=0k 6=n

(s− k)ds = ωN−n.

BeispielDie Newton-Cotes-Formeln für N = 1, . . . ,4 lauten:

N = 1 : I1( f ) = b−a2 ( f (a)+ f (b)) Trapezregel

N = 2 : I2( f ) = b−a6

(f (a)+4 f

(a+b2

)+ f (b)

)Simpsonregel

N = 3 : ω0 = ω3 =b−a

8 , ω1 = ω2 =3(b−a)

8 Newton’sche38

-Regel

N = 4 : ω0 = ω4 =7(b−a)

90 , ω1 = ω3 =32(b−a)

90 , ω2 =12(b−a)

90 Milne-Regel

BemerkungFür N > 4 können auch negative Gewichte auftreten. Dadurch besteht bei der Auswertungdie Gefahr der Auslöschung, so dass diese Formeln numerisch weniger stabil sind.

(10.4) LemmaDie Newton-Cotes-Formeln sind für gerade N exakt von der Ordnung N +1.

94

Beweis. Zu den äquidistanten Stützstellen ξn ∈ ΞN definiere

Q(t) :=N

∏n=0

(t−ξn) ∈ PN+1.

Es gilt IN(Q) = 0 und die Symmetrie-Eigenschaft Q(a+b2 +s) = (−1)N+1Q(a+b

2 −s). Dar-aus ergibt sich für gerade N

∫ b

aQ(t)dt =

∫ a+b2

aQ(t)dt +

∫ b

a+b2

Q(t)dt = (1+(−1)N+1)∫ a+b

2

aQ(t)dt = 0 .

Jedes P∈PN+1 lässt sich in der Form P= aQ+P0 für ein a∈R und ein P0 ∈PN darstellen.Damit ergibt sich∫ b

aP(t)dt =

∫ b

aP0(t)dt = IN(P0) = IN(aQ+P0) = IN(P) ,

da IN nach Konstruktion schon exakt von der Ordnung N ist.

(10.5) Lemma (Mittelwertsatz der Integralrechnung)Seien g,h ∈C[a,b] mit g(t)≥ 0 für t ∈ [a,b]. Dann gilt:

∫ b

ag(t)h(t)dt = h(τ)

∫ b

ag(t)dt

für eine Zwischenstelle τ ∈ (a,b).

Beweis. Wir betrachten

F(t) :=∫ b

ag(s)h(s)ds−h(t)

∫ b

ag(s)ds.

Wähle t0, t1 ∈ [a,b], sodass h(t0)≤ h(t)≤ h(t1) für alle t ∈ [a,b] gilt. Dann folgen

F(t0) ≥∫ b

ag(s)h(t0)ds−h(t0)

∫ b

ag(s)ds = 0 und

F(t1) ≤∫ b

ag(s)h(t1)ds−h(t1)

∫ b

ag(s)ds = 0.

Da F stetig ist, existiert nach dem Zwischenwertsatz ein τ ∈ (mint0, t1,maxt0, t1) mitF(τ) = 0.

(10.6) SatzSei f ∈C4[a,b]. Dann gilt für die Simpsonregel

I2( f )−∫ b

af (t)dt =

(b−a

2

)5 190

f (4)(τ)

für ein τ ∈ (a,b).

95

Beweis. Sei P ∈ P3 das Hermite-Interpolationspolynom von f an den Stellen t0 = a, t1 =t2 = a+b

2 , t3 = b. Dann folgt mit Satz (8.7) b)

f (t)−P(t) = f [t0, t1, t2, t3, t](t− t0)(t− t1)2(t− t3) ,

und da nach Lemma (10.4) E2(P) = 0 ist, gilt

I2( f )−∫ b

af (t)dt = I2(P)−

∫ b

af (t)dt =

∫ b

aP(t)dt−

∫ b

af (t)dt

=∫ b

af [t0, t1, t2, t3, t] (t− t0)(t− t1)2(t3− t)︸ ︷︷ ︸

≥0

dt

(10.5)= f [t0, t1, t2, t3,τ]︸ ︷︷ ︸

= 14! f ′′′′(τ)

∫ b

a(t− t0)(t− t1)2(t3− t)dt︸ ︷︷ ︸

= 415(

b−a2 )

5

=

(b−a

2

)5 190

f (4)(τ).

(10.7) LemmaDie maximale Ordnung einer Quadratur IΞ mit N = |Ξ | Stützstellen ist 2N−1.

Beweis. Definiere zu den Stützstellen tn ∈ Ξ

Q(t) =N

∏n=1

(t− tn)2 ∈ P2N .

Dann gelten

IΞ (Q) = ∑ξ∈Ξ

ωξ Q(ξ )︸ ︷︷ ︸=0

= 0 und∫ b

aQ(t)dt > 0,

da Q(t)> 0 auf [a,b]\Ξ . Folglich ist IΞ nicht exakt von der Ordnung 2N.

Bisher haben wir nur gezeigt, dass die maximale Ordnung kleiner als 2N ist. Die Existenzeiner Quadratur der Ordnung 2N−1 gewährleistet uns der nächste Satz. Dazu betrachtenwir etwas allgemeiner gewichtete Integrale

I(Q) =∫ b

af (t)W (t)dt

zu −∞ ≤ a < b ≤ ∞ und Gewicht mit W (t) > 0 für t ∈ (a,b) und∫ b

a W (t)dt < ∞. Daszugehörige Skalarprodukt wird mit

〈u,v〉W =∫ b

au(t)v(t)W (t)dt

bezeichnet, und QN seien die zugehörigen Orthonormalpolynome.

96

(10.8) Satz (Gauß-Quadratur)Es existiert genau eine Quadraturformel GN mit N Stützstellen ξ1, . . . ,ξN , die exakt vomGrad 2N−1 ist. Die Stützstellen sind Nullstellen des Orthonormalpolynoms QN .

Beweis. Sei GN die Quadratur zu Nullstellen a < ξ1 < · · ·< ξN < b, die exakt vom GradN−1 ist. Zu P ∈ P2N−1 existieren P0,P1 ∈ PN−1 mit P = P1QN +P0 (Polynomdivision mitRest). Damit gilt

GN(P0) = ∑ξ∈Ξ

ωξ P0(ξ ) = ∑ξ∈Ξ

ωξ (P1(ξ )QN(ξ )+P0(ξ )) = GN(P1QN +P0) = GN(P) ,

denn QN(ξ ) = 0 für alle ξ ∈ Ξ . Da die Quadratur für P0 ∈ PN−1 exakt ist, gilt nun∫ b

aP(t)W (t)dt = 〈P,1〉W = 〈P1QN +P0,1〉W

= 〈P1,QN〉W︸ ︷︷ ︸=0, da QN⊥PN−1

+∫ b

aP0(t)W (t)dt = GN(P0) = GN(P) .

Und damit ist GN exakt von der Ordnung 2N−1.Nun sei G eine weitere Quadraturformel, die ebenfalls exakt von der Ordnung 2N−1 istmit Stützstellen η1, . . . ,ηN . Definiere

Ln(t) :=N

∏k=1

ηk 6=ηn

t−ηk

ηn−ηk∈ PN−1.

Dann folgt aus Ln(ηn) = 1 und der Exaktheit von G

ωηn = GN(Ln) = GN(L2n) =

∫ b

aLn(t)2dt > 0 ,

und es gilt

0 = 〈QN ,Ln〉W =∫ b

aQN(t)Ln(t)︸ ︷︷ ︸∈P2N−1

W (t)dt = GN(QNLn) = ωηnQN(ηn).

Also ist QN(ηn) = 0 für n = 1, ...,N.

(10.9) FolgerungDie Gewichte der Gauß-Quadratur sind positiv.

(10.10) SatzSei f ∈C2N [a,b]. Für die Gauß-Quadratur GN gilt dann

I( f )−GN( f ) =1

(2N)!

(ddt

)2N

f (τ) 〈QN ,QN〉W

mit τ ∈ (a,b) und QN(t) = ∏Nn=1(t−ξn).

97

Beweis. Wähle zu f die Hermite-Interpolatierende P∈P2N−1 an den Stellen ξ1,ξ1, . . . ,ξN ,ξN .Aus Satz (8.7) folgt wiederum f (t)−P(t) = f [ξ1,ξ1, . . . ,ξN ,ξN , t]QN(t)2 und damit

I( f )−GN( f ) = I( f )−GN(P) = I( f )− I(P) =∫ b

a( f (t)−P(t))W (t)dt

=∫ b

af [ξ1,ξ1, . . . ,ξN ,ξN , t]QN(t)2W (t)︸ ︷︷ ︸

=g(t)≥0

dt

(10.5)= f [ξ1,ξ1, . . . ,ξN ,ξN ,τ]

∫ b

aQN(t)2W (t)dt︸ ︷︷ ︸〈QN ,QN〉W

=1

(2N)!

(ddt

)2N

f (τ) 〈QN ,QN〉W .

BeispielA) (a,b) = (−1,1)

G1( f ) = 2 f (0)

G2( f ) = f

(−√

13

)+ f

(√13

)

B) Gauß-Lobatto-QuadraturSei W (t) = (t − a)(b− t) und seien ξ1, . . . ,ξN−2 Nullstellen des Orthogonalpoly-noms QN−2 bezüglich W. Dann ist die Quadratur von

∫ ba f (t)dt mit den Stützstellen

a,ξ1, . . . ,ξN−2,b exakt vom Grad k = 2N−3.

C) Radau-QuadraturSei W (t) = (b− t) und ξ1, . . . ,ξN−1 Nullstellen von QN−1 zu W. Dann ist die Qua-dratur die Quadratur von

∫ ba f (t)dt mit den Stützstellen ξ1, . . . ,ξN−1,b exakt vom

Grad k = 2N−2.

D) Kubatur auf DreieckenSei Ω = conv

(00

),(1

0

),(0

1

)das Einheitsdreieck. Dann gilt für f ∈C(Ω)

∫Ω

f (x,y)dxdy =∫ 1

0

∫ 1−x

0f (x,y)dydx =

∫ 1

0

∫ 1

0f (x,(1− x)t)(1− x)dtdx.

a) Wähle Gauß-Quadratur ξn, ωn bezüglich dem Skalarprodukt 〈u,v〉=∫ 1

0u(t)v(t)dt.

b) Wähle Gauß-Quadratur ξn, ωn bezüglich dem Skalarprodukt∫ 1

0(1−t)u(t)v(t)dt

Definiere dann

GN( f ) :=N

∑n,k=1

ωnωk f (ξn,(1−ξn)ξk)

98

(10.11) SatzSei (Ik) eine Folge von Quadraturformeln mit

a) Konsistenz: limk→∞

Ik(P) =∫ b

a P(t)W (t)dt ∀P ∈ P

b) Stabilität: Es existiert ein C > 0 mit ∑ξ∈Ξ |ωk,ξ |<C für alle k.

Dann gilt:

Konvergenz: limk→∞

Ik( f ) =∫ b

af (t)W (t)dt f ∈C[a,b]

Beweis. Zu jedem ε > 0 und f ∈C[a,b] existiert P ∈ P mit ‖ f −P‖∞ < ε und k mit

|Ek(P)|=∣∣∣∣Ik(P)−

∫ b

aP(t)W (t)dt

∣∣∣∣< ε

Damit folgt Ek( f ) = Ek( f −P)+Ek(P) und

|Ek( f )| ≤ ∑ξ∈Ξ

|ωk,ξ ||( f −P)(ξ )|+∫ b

a‖ f −P‖∞W (t)dt + |Ek(P)|

≤ ‖ f −P‖∞︸ ︷︷ ︸<ε

(C+

∫ b

aW (t)dt

)+ ε −→

ε→00 .

BeispielDie summierte Trapezregel und die Gauß-Quadratur konvergieren für alle stetigen Funk-tionen. Die Folge der Newton-Cotes-Formel konvergiert nicht.

BemerkungI, Ik : C[a,b]→ R sind lineare Operatoren mit |Ik( f )| ≤C‖ f‖∞ und somit punktweise be-schränkt. Mit dem “uniform boundedness principle” folgt dann ‖Ik‖∞ <C.

99

Zusammengesetzte Quadratur

Zu Stützstellen Ξ =

ξ1, . . . , ξN

⊂ [0,1] und Gewichten ω1, . . . , ωN sei

(f)=

N

∑n=1

ωn f (ξn)

exakt von der Ordnung p, d.h.∫ 1

0 P(t)dt = IΞ

(P)

für alle P ∈ Pp. Für den Fehler gelte∣∣∣∣IΞ

(f)−∫ 1

0f (t)dt

∣∣∣∣≤C maxt∈[0,1]

∣∣∣∣∣(

ddt

)p+1

f (t)

∣∣∣∣∣ .A) Substitution: ϕ : [0,1]→ [a,b], s 7→ a+ s(b−a)

Definiere

IΞ ( f ) =N

∑n=1

ωn f (ξn) mit ξn = ϕ(ξn), ωn = (b−a)ωn

Dann ist IΞ exakt vom Grad p, denn für P ∈ Pp gilt

IΞ (P) =N

∑n=1

ωnP(ξn) = (b−a)N

∑n=1

ωn (Pϕ)︸ ︷︷ ︸=P∈Pp

(ξn)

= (b−a)∫ 1

0P(t)dt =

∫ b

aP(s)ds .

Fehlerabschätzung:∣∣∣∣IΞ ( f )−∫ b

af (s)ds

∣∣∣∣= (b−a)∣∣∣∣IΞ

( f ϕ)−∫ 1

0f ϕ(t)dt

∣∣∣∣≤ (b−a)C max

t∈[0,1]

∣∣∣∣∣(

ddt

)p+1

f ϕ(t)

∣∣∣∣∣= (b−a)p+2C max

s∈[a,b]

∣∣∣∣∣(

dds

)p+1

f (s)

∣∣∣∣∣B) Summierte Quadratur:

Sei M ∈ N, h = b−aM . Es sei Ξ =

M⋃m=1

ϕm(Ξ) mit ϕm(s) = a+(m− 1+ s)h. Weiter

sei ωn = hωn. Dann definiere die summierte Quadratur

IΞ ( f ) = hM

∑m=1

N

∑n=1

ωn f(

ϕm(ξn)).

Fehlerabschätzung:∣∣∣∣IΞ ( f )−∫ b

af (s)ds

∣∣∣∣≤ hM

∑m=1︸ ︷︷ ︸

=(b−a)

Chp+1 maxt∈[a,b]

∣∣∣∣∣(

ddt

)p+1

f (t)

∣∣∣∣∣100

Beispiel1) Summierte Trapezregel:

IΞ ( f ) =h2( f (a)+ f (b))+h

M−1

∑m=1

f (a+mh)

2) Summierte Simpson-Regel:

IΞ ( f ) =h6( f (a)+ f (b))+

h3

M−1

∑m=1

f (a+mh)︸ ︷︷ ︸13 · Trapezregel

+23

hM

∑m=1

f(

a+(

m− 12

)h)

Es gilt ∣∣∣∣IΞ ( f )−∫ b

af (t)dt

∣∣∣∣≤ (b−a)Ch4 maxt∈[a,b]

∣∣∣∣∣(

ddt

)4

f (t)

∣∣∣∣∣3) Mehrdimensionale Quadratur:∫ 1

0

∫ 1

0f (x1,x2)dx1 dx2 ≈

N

∑n=1

N

∑k=1

ωnωk f (ξn, ξk)

Mit der Parametrisierung ϕ : [0,1]2 Ω erhalten wir

∫Ω

f (x)dx =∫[0,1]2

( f ϕ)(x)detJϕ(x)dx≈N

∑n=1

ωn

N

∑k=1

ωk detJϕ(ξn, ξk) f(

ϕ(ξn, ξk))

wobei Jϕ die Jacobi-Matrix bezeichnet.“Fluch der Dimension”: In RD haben wir ND Quadraturpunkte.

101

Romberg-Quadratur

Die Romberg-Quadratur ist ein Extrapolationsverfahren, das aus der summierten Trapez-regel

Th( f ) := h

(12

f (a)+N−1

∑n=1

f (a+nh)+12

f (b)

), h =

b−aN

durch Extrapolation eine verbesserte Approximation von

I( f ) :=∫ b

af (t)dt

berechnet.

Idee der ExtrapolationSei Ih eine Quadraturformal mit

Ih− I ≈Chp

wobei C abhängig von f ist. Dabei bedeutet ≈, dass wir eine Taylorentwicklung vorliegenhaben und keine Terme hq mit q < p auftauchen. Die Idee ist nun, für ein h > 0 sowohlIh als auch I2h zu berechnen, und dann diese Werte in Abhängigkeit von h linear zu inter-polieren. Das resultierende Polynom können wir dann an der Stelle h = 0 auswerten, wirbekommen also einen Schätzwert für limh→0 Ih. Zunächst erhalten wir

I2h− I ≈C(2h)p = 2pChp ≈ 2p(Ih− I).

Durch Umsortierung folgt:

(2p−1)I ≈ 2pIh− I2h = (2p−1)Ih + Ih− I2h

und damit

I ≈ Ih +1

2p−1(Ih− I2h) := Ih .

Der Fehler wird dabei durch 12p−1(Ih−I2h) abgeschätzt und Ih wird Extrapolation genannt.

(10.12) LemmaSei die Fehlerentwicklung

Ih− I =Chp +O(hq)

mit q > p gegeben. Dann gilt für die Extrapolation Ih = Ih +1

2p−1(Ih− I2h

)a) |I− Ih|= O(hq) ,

b) |I− Ih|= 12p−1

(Ih− I2h

)+O(hq) .

102

Beweis. Zu a) Es gilt

(I2h− I)−2p(Ih− I) =C(2h)p−2pCh2 +O(hq) = O(hq) .

Damit folgt

I− Ih =1

2p−1((I2h− I)−2p(Ih− I)) = O(hq) .

Zu b) Es gilt

I− Ih = Ih− Ih + I− Ih =1

2p−1|Ih− I2h|+O(hq) .

Anwendung auf die summierte TrapezregelWir wenden nun die Extrapolation auf die summierte Trapezregel an:

• Setze Tk0 := Thk( f ) mit hk = 2−kh.Dann folgt mit p = 2:

|Tk0− I( f )|= O(h2k).

• Extrapoliere

Tk1 = Tk0 +13(Tk0−Tk−1,0) = O(h4

k).

• Dann zeige

|Tk1− I( f )|= O(h4k) =Ch4

k +O(h6k),

also p = 4.

• Extrapoliere nun

Tk2 = Tk1 +115

(Tk,1−Tk−1,1).

Im Folgenden untersuchen wir, ob sich dieser Prozess fortsetzen lässt.

(10.13) Satz (Euler-MacLaurinsche Summenformel)Für g ∈C2m+2[0,1] gilt

∫ 1

0g(s)ds =

12(g(0)+g(1)) +

m

∑j=1

b j

((ddt

)2 j−1

g(0)−(

ddt

)2 j−1

g(1)

)

+ bm+1

(ddt

)2m+2

g(τ)

mit τ ∈ (0,1). Dabei sind die b j ∈ R unabhängig von g.

103

BeispielHermite Quadratur:∫ 1

0g(t)dt =

12(g(0)+g(1))+

12(g′(0)−g′(1))+b2g(4)(τ)

(10.14) FolgerungFür f ∈C2m+2[a,b] und h = b−a

N gilt

Th( f )− I( f ) =m

∑j=1

c jh2 j +O(h2m+2)

mit c j = b j(( d

dt )2 j−1 f (b)− ( d

dt )2 j−1 f (a)

).

Beweis. Setze tn := a+nh, gn(s) := f (tn−1 + sh). Damit folgt(ddt

) j

gn(t) = h j(

dds

) j

f (tn−1 + sh).

Und somit gilt

I( f ) =N

∑n=1

∫ tn

tn−1

f (t)dt =N

∑n=1

h∫ 1

0gn(s)ds

= hN

∑n=1

[12(gn(0)+gn(1))

+m

∑j=1

b j

((ddt

)2 j−1

gn(0)−(

ddt

)2 j−1

gn(1)

)

+bm+1

(ddt

)2m+2

g(τi)

]

= Th( f )+hm

∑j=1

b j

((ddt

)2 j−1

gN(1)−(

ddt

)2 j−1

g1(0)

)︸ ︷︷ ︸

=c jh2 j−1

+O(h2m+2).

(10.15) SatzZu Tk0 = Thk( f ) mit hk = 2−kh (k = 0, . . . ,m) definiere rekursiv

Tki = Tk,i−1 +1

4i−1(Tk,i−1−Tk−1,i−1), i = 1, . . . ,m und k = i, . . . ,m.

Dann gilt

|Tmm− I( f )| ≤Ch2m+2

∥∥∥∥∥(

ddt

)2m+2

f

∥∥∥∥∥∞

,

wobei C > 0 unabhängig von f ist, d.h. Tmm ist exakt von der Ordnung 2m+1.

104

Beweis. Setze c j0 := c j, c ji := 4i−4 j

4i−1 c j,i−1. Zeige nun induktiv

Tki = I( f )+m

∑j=i+1

c jih2 jk +O(h2m+2

k ).

i = 0 ist die Folgerung (10.14) aus der Euler-MacLaurinsche Summenformel.i−1→ i:

(4i−1)Tki = 4iTk,i−1−Tk−1,i−1

(Ind.-Vor.)= 4i

(I( f )+

m

∑j=1

c j,i−1h2 jk

)+O(h2m+2

k )− I( f )

−m

∑j=1

c j,i−1hk−1 +O(h2m+2k−1 )

= (4i−1)I( f )+m

∑j=1

(4i−22 j)︸ ︷︷ ︸=0 für i= j

c j,i−1h2 jk +O(h2m+2

k ).

BemerkungSei P ∈ Pm mit P(h2

k) = Thk( f ) für k = 0, . . . ,m.Dann ist Tmm = P(0) Extrapolation von P für t = 0. (Neville Schema)

(10.16) FolgerungEs gilt für k = 0,1, . . . ,m

a) |I( f )−Tkk|= O(h2k+2k ),

b) |I( f )−Tk,k−1|= |Tkk−Tk,k−1|︸ ︷︷ ︸Fehlerabschätzung

+O(h2k+2k ) .

Algorithmus:

S0) Wähle N, ε > 0, Ordnung m, h = b−aN , T00 = Th( f ), k = 1.

S1) hk = 2−kh, Tk0 =12Tk−1,0 +hk ∑

2n=0 f (a+(2n+1)hk)

S2) Für i = 1, . . . ,k : Tk,i = Tk,i−1 +1

4i−1(Tk,i−1−Tk−1,i−1)

S3) Falls |Tk,k−Tk,k−1|< ε STOP

S4) Falls k = m STOP

S5) Setze k := k+1, gehe zu S1).

Adaptive Quadratur

I( f ,a,b,ε) =

Tkk falls |Tkk−Tk,k−1|< ε für ein k ≤ mI( f ,a, b+a

2 , ε

2)+ I( f , b+a2 ,b, ε

2) sonst

Dies lässt sich rekursiv anwenden.

105

Monte-Carlo-Quadratur

Sei Ω ⊂ RD. Wähle (Pseudo-) Zufallszahlen ξ1, . . . ,ξN ⊂Ω . Setze

IN( f ) =|Ω |N

N

∑n=1

f (ξn)

Für eine Folge unabhängiger gleichverteilter Zufallsvariablen gilt

|I( f )− IN( f )| ≤ c√N

mit einer Wahrscheinlichkeit

P(c) =1√

2πσ( f )

∫ c

−cexp(− t2

2σ( f )

)dt +o(1)

und der Varianz

σ( f ) =1|Ω |

∫Ω

(f − 1|Ω |

I( f ))2

dx .

Damit ist die Konvergenz unabhängig von der Dimension D, aber für kleine D langsamerals Standardverfahren.

106

11 Trigonometrischce Interpolation

BeispielSei f : [0,T ]→ R ein (akustisches) Signal. Setze f : R→ R zu einer 2T -periodischenFunktion mit f (t) = f (−t) fort. Berechne (approximativ) die Fourierreihe bis zum Grad n

fn(t) =a0

2+

n

∑k=1

ak cos(ωkt) mit ω =Tπ.

Wir beobachten, dass die Koeffizienten ak je nach Regularität von f sehr schnell fallen.Deshalb lässt sich das Signal mit wenigen ak gut approximieren.

AnwendungenMP3, MPEG, seismische Wellenanalyse, Lösung von Differentialgleichungen auf periodi-schen Gittern,...

Ziel:

• Schnelle Algorithmen zur Berechnung der Koeffizienten

• Konvergenzanalyse

(11.1) DefinitionDie 2π-periodischen komplexen trigonometrischen Polynome T ∈Πn sind von der Form

T (t) =n

∑k=−n

αk exp(ikt) mit i =√−1, t ∈ R, αk ∈ C .

BemerkungWenn αk = α−k für alle k, dann ist

T (t) =a0

2+

n

∑k=1

(ak cos(kt)+bk sin(kt))

mit ak = 2Reαk und bk = 2Imαk.

(11.2) LemmaDie Funktionen Qk(t) = 1√

2πexp(ikt) mit |k| ≤ n bilden eine Orthogonalbasis von Πn

bezüglich 〈 f ,g〉0 =∫ 2π

0 f (t)g(t)dt.

Beweis. Es gilt

〈Qk,Qk〉0 =1

∫ 2π

0exp(ikt)exp(ikt)dt =

12π

∫ 2π

0exp(ikt)exp(−ikt)dt = 1 .

Für k 6= j gilt

〈Qk,Q j〉0 =1

∫ 2π

0exp(i(k− j)t)dt =

12π

1i(k− j)

exp(i(k− j)t)∣∣∣∣2π

0= 0 .

Hier geht im letzten Schritt die Periodizität der komplexen Exponentialfunktion auf derimaginären Achse ein.

107

(11.3) FolgerungSei f ∈ L2(0,2π). Dann ist

pn( f ) =n

∑k=−n〈 f ,Qk〉0 Qk ∈Πn

die Orthogonalprojektion von f mit ‖ f − pn( f )‖0 ≤ ‖ f −T‖0 für alle T ∈Πn. Es gilt

‖pn( f )‖20 =

n

∑k=−n| 〈 f ,Qk〉0︸ ︷︷ ︸=√

2παk

|2 ≤ ‖ f‖20 .

Beweis. Es gilt 〈 f − pn( f ),Qk〉0 = 0 ∀Qk ∈Πn. Damit gilt auch 〈 f − pn( f ), pn( f )〉0 = 0.Daraus folgt die Behauptung.

BemerkungEs gilt ‖ f‖2

0 = ∑k∈Z |〈 f ,Qk〉|2, und die Funktionen Qk bilden Hilbertbasis in L2(0,2π).Falls f stückweise stetig ist konvergiert pn( f ) punktweise:

limn→∞

pn( f ) =∞

∑k=−∞

αk exp(ikt) =12( f (t−)+ f (t+)) .

Idee der trigonometrischen InterpolationApproximiere αk = 1

∫ 2π

0 f (t)exp(−ikt)dt auf äquidistante Gitter t j = j 2π

N durch dieTrapezsumme

αk =1N

N−1

∑j=0

f (t j)exp(−ikt j) .

Es gilt α−k = αN−k. Für n < N2 erhält man die zugehörige Interpolation mit

pn( f )(t) =n

∑k=−n

αk exp(ikt) .

(11.4) LemmaSei N ∈ N, ω = ωN = exp

(i2π

N

)die N-te Einheitswurzel.

Dann gilt exp(ikt j) = exp(

i2πk jN

)= ω

k jN . Definiere die Fouriermatrix

FN =(

ωjk

N

)j,k=0,··· ,N−1

=

1 1 1 · · · 11 ω ω2 · · · ωN−1

1 ω2 ω4 · · · ω2(N−1)

......

......

1 ωN−1 ω2(N−1) · · · ω(N−1)2

∈ CN,N .

Dann gilt F−1N = 1

N FN , d.h√

1N FN ist unitär. Es gilt also

N−1

∑j=0

exp(ikt j)exp(−ilt j) =

N falls k = l0 sonst

108

Beweis. Es gilt

FNFN =

(N−1

∑j=0

ωjk

ω−l j

)l,k=0,··· ,N−1

.

Dann folgt

1) für l = k : ∑N−1j=0 ω0 = N.

2) für l 6= k: Definiere dazu η = ω l−k 6= 1. Damit folgt ηN = 1 und

0 =1−ηN

1−η=

N−1

∑j=0

ηj =

N−1

∑j=0

ωl j

ω− jk.

Insgesamt ergibt sich FNFN = NIN .

(11.5) FolgerungSei f = ( f (t j)) j=0,...,N−1 ∈ CN und α = (αk)k=0,...,N−1 ∈ CN dazu so gewählt, dass gilt

α =1N

FN f und f =1N

FNFN f = FNα

d.h. f (t j) = ∑N−1k=0 αk exp(ikt j) = T (t j) mit

T (t) =n

∑k=1−n

αk exp(ikt)

für N = 2n mit α−k = αN−k.

(11.6) LemmaSei N = 2n ∈ N gerade und y = FNx ∈ CN . Dann gilt

y2k =n−1

∑j=0

x+j ωk jn mit x+j = x j + x j+n,

y2k+1 =n−1

∑j=0

x−j ωk jn mit x−j = (x j− x j+n)ω

jN .

Beweis. Es gilt

ω2k jN = ω

k jn und ω

(2k+1) jN = ω

k jn ω

jN .

Damit folgt

y2k =N−1

∑j=0

x jω2k jN =

n−1

∑j=0

x jωk jn +

N−1

∑j=n

x jωk jn =

n−1

∑j=0

x+j ωk jn ,

109

und die Behauptung folgt aus

y2k+1 =N−1

∑j=0

x jω(2k+1) jN =

n−1

∑j=0

x jωk jn ω

jN +

N−1

∑j=n

x jωk jn ω

jN

=n−1

∑j=0

ωj

N

(x jω

k jn + x j+nω

k jn ω

knn︸︷︷︸

=1

ωnN︸︷︷︸

=−1

)=

n−1

∑j=0

x−j ωk jn .

FFT-Algorithmus

FFT-Algorithmus für die Berechnung von y = FNx für N = 2K .

S1) Wenn N = 1 und y = x: STOP

S2) Definiere

x+ = x[

0 :N2−1]+ x[

N2

: N−1]∈ C

N2

x− = diag(

ωj

N

)(x[

0 :N2−1]− x[

N2

: N−1])∈ C

N2

S3) Berechne y+ = FN2x+, y− = FN

2x−

S4) Berechne y = (y+[0],y−[0],y+[1],y−[1], · · ·) ∈ CN : STOP

(11.7) SatzDer FFT-Algorithmus benötigt N log(N) Operationen.

Beweis. Speichere einen Vektor (ωnN) ∈ CN .

Dann erfordert S2) im Schritt k = K,K−1, . . . ,1 bei der Durchführung 2K−k-Operationenfür die Additionen und 1

2 ·2K−k-Operationen für die Multiplikationen. S2) wird dabei N

2K−k

mal aufgerufen, d.h.

2K−k · N2K−k = N Additionen

und

12·2K−k · N

2K−k =N2

Multiplikationen.

Für N = 2K wird S3) K mal aufgerufen, d.h.

K ·N Additionen+K · N2

Multiplikationen.

Da K in O(log(N)) folgt insgesamt ein Aufwand von O(N log(N)) Operationen.

BemerkungEffiziente Implementierung erfolgt durch Bitumkehr. Dabei wird (ωN) als Vektor abge-speichert.

110

Konvergenzanalyse

Definiere zu s≥ 0

‖ f‖s =

(∑k∈Z

(1+ |k|2s)|αk|2) 1

2

mit αk =1

∫ 2π

0f (t)exp(−ikt)dt

und Hs = f ∈ L2(0,2π) : f ist periodisch fortsetzbar und ‖ f‖s < ∞.Es gilt: Hs ist ein Hilbertraum, H0 = L2(0,2π).

(11.8) SatzEs sei Cm

per[0,2π] der Raum der auf [0,2π] periodischen und m-mal stetig differenzierbarenFunktionen. Es gilt:

a) Hs ⊂C0per[0,2π] (die stetige periodische Funktionen über [0,2π]) für s > 1

2 .

b) Cmper[0,2π]⊂ Hm für m ∈ N.

Beweis. Zu a) Wir betrachten die Funktionenreihe f (t) =∞

∑k=−∞

αk exp(ikt)︸ ︷︷ ︸stetig

.

∣∣∣∣∣ ∑n≤|k|≤m

αk exp(ikt)

∣∣∣∣∣≤ ∑n≤|k|≤m

(|αk||k|s)(|k|−s)

CSU≤

(∑

n≤|k|≤m|αk|2|k|2s

) 12

︸ ︷︷ ︸≤‖ f‖s

(∑

n≤|k|≤m|k|−2s

) 12

︸ ︷︷ ︸≤ε für großes n

In die letzte Abschätzung geht ein, dass ∑k∈Z |k|−2s < ∞ gilt. Die stetige Funktionenreihekonvergiert also nach dem Cauchy-Kriterium gleichmäßig. Damit ist auch ihr Grenzwertstetig.zu b) Sei m = 1 (analog für m≥ 2). Wegen

kαk =1

i2π

∫ 2π

0f (t)ik exp(−ikt)dt =− 1

i2π

∫ 2π

0f (t)

ddt

exp(−ikt)dt

=1

i2π

∫ 2π

0f ′(t)exp(−ikt)dt

erhalten wir ‖ f ′‖20 = ∑k∈Z |kαk|2 und damit ‖ f‖2

1 = ‖ f‖20 +‖ f ′‖2

0 < ∞ für f ∈C1[0,2π].

(11.9) LemmaSei f ∈ Hs für s > 1

2 , sowie

αk =1

∫ 2π

0f (t)exp(−ikt)dt und αk =

1N

N−1

∑j=0

f (t j)exp(−ikt j) mit t j = j2π

N

Dann gilt:

αk = ∑m∈Z

αk +mN für |k|< N2.

111

Beweis.

αk =1N

N−1

∑j=0

(∑l∈Z

αl exp(ilt j)

)︸ ︷︷ ︸

= f (t j)

exp(−ikt j) = ∑l∈Z

αl1N

N−1

∑j=0

exp(ilt j)exp(−ikt j)︸ ︷︷ ︸N, l− k ∈ N ·Z0, l− k /∈ N ·Z

Bei der Vertauschung der Summen geht die absolute Konvergenz der Funktionenreihe ein,die im Beweis von (11.8) nachgewiesen wurde.

(11.10) SatzSei f ∈ Hs für s > 1

2 , und für n < N2 betrachte

Tn(t) =n

∑k=−n

αk exp(ikt) .

Dann exisitert ein (von f unabhängiges) Cs > 0 mit

‖ f −Tn‖0 ≤Cs

ns ‖ f‖s

Beweis. (i) Sei k ≤ n.

|αk− α|2 =

∣∣∣∣∣ ∑|m|>0

αk +mN

∣∣∣∣∣2

[∑|m|>0

(|αk +mN||k+mN|s) |k+mN|−s

]2

CSU≤

(∑|m|>0

|αk +mN|2|k+mN|2s

)︸ ︷︷ ︸

≤‖ f‖2s

(∑|m|>0

(k+mN)−2s

)︸ ︷︷ ︸≤(N

2 )−2s

∑|l|>0

l−2s≤C 1n2s

(ii) Sei k > n.

∑|k|>n|αk|2 ≤ ∑

|k|>n

(|k|n

)2s

|αk|2 ≤1

n2s ∑|k|>n

(1+ |k|2s) |αk| ≤

1n2s‖ f‖2

s .

Damit erhalten wir

12π‖ f −Tn‖2

0 = ∑|k|≤n|αk− αk|2 + ∑

|k|>n|αk|2 ≤ (C+1)

1n2s‖ f‖2

s .

112

Anwendungen

Schwingungsanalyse

Wir denken uns eine Brücke mit Querverstrebungen und betrachten sie von der Seite.Das System besteht aus dann aus aneinandergefügten Dreiecken. Die Punkte an denen dieQuerstreben beginnen oder enden bezeichnen wir mit zl (von links nach rechts durchnum-meriert). xl(t) ∈ R2 sei die Auslenkung am Punkt zl zum Zeitpunkt t.Die Newtonsche Mechanik liefert

M(

ddt

)2

x(t) = Kx(t)

mit symmetrisch positiv definiten Matrizen M und K. Wir erhalten

x(t) =L

∑l=1

γl cos(√

λlt)wl mit Kwl = λlMwl

(λl heißt die Eigenschwingung des Systems).Sei f (t) = ∑

Ll=1 γl cos(

√λlt)wl(zn) eine Messung and einem Punkt zn.

Berechnnung der Approximation

Tn(t) =n

∑k=1−n

αk exp(

ik2π

Tt)

mit Tn(t j) = f (t j) für j = 0, . . . ,N−1 und t j = jh zur Periode T und Abtastrate h = TN .

Es gilt: Wenn |γl| groß genug ist, dann sind die Koeffizienten |αk| bei ωk ≈√

λl2π

signifikantgrößer als die anderen.

Das JPEG Prinzip

Es gelte f (t) = f (2π− t). Dann haben wir

αl =1π

∫π

0f (t)cos(kt)dt =

ak

2

Tn(t) =a0

2+

n−1

∑k=1

ak cos(kt)

ak =2N

n−1

∑j=0

f(

2 j+1N

π

)cos(

k2 j−1

)︸ ︷︷ ︸

=C[k, j]

C[1 : n−1,1 : n−1] sei hierbei die “Cosinusmatrix”, die die entsprechenden Auswertungenenthält. Der FFT-Algorithmus lässt sich auf C übertragen.

113

Ausblick: Multiskalen-Methoden

Anwendung: Sei f : [0,T ]→ R eine EKG-Messung.Beobachtung: Nur 24 der 2048 Fourierkoeffizienten sind kleiner als 10−4.Begründung: Fourierentwicklung konvergiert für nicht-glatte Daten langsam.

BeispielSei χ(t) =

1, t ∈ [0,1]0, sonst

.

Dann gilt |αk| ∼ 1k und wir beobachten das Gibbs-Phänomen: Für große n überschwingt

die abgeschnittene Fourier-Entwicklung Tn den Sprung um etwa 18%, d.h.

‖χ−Tn‖0 ≤ ‖χ−T‖0 ∀T ∈Πn, aber ‖χ−Tn‖∞ ≈ 0,18 6= 0 .

(11.11) DefinitionSei ∆k = jhk : j = 0, . . . ,2k mit hk = 2−k eine Familie äquidistanter Gitter.

χ jk(t) =

2

k2 , t ∈ I jk = [ jhk,( j+1)hk]

0, sonstd.h. ‖χ jk‖L2(0,1) = 1

Vk = spanχ jk : j = 0, . . . ,2k − 1 ⊂ L2(0,1) Wir beobachten, dass die χ jk bilden eineL2-Orthogonalbasis von Vk. Es gilt

χ jk(t) = 2k2 χ(2kt− jhk)

χ0k(t) = 2k2 χ(2kt) (Stauchung)

χ jk(t + jhk) = χk0(t) (Verschiebung)

Idee: Orthogonale Aufspaltung Vk+1 =Vk⊕Wk.Dabei beschreibt Vk den Trend und Wk die Fluktuation.

(11.12) DefinitionWir betrachten das Haar-Wavelet (Wavelet bedeutet “kleine Welle”)

Ψ(t) =

1, t ∈ [0, 1

2)

−1, t ∈ [12 ,1]

Definiere Ψjk(t) = 2k2Ψ(2kt− jhk), d.h.

Ψ0k(t) = 2k2Ψ(2kt) (Stauchung)

Ψjk(t + jhk) =Ψk0(t) (Verschiebung)

(11.13) Lemmaa) Zweiskalenbasis: χk j und Ψk j für j = 0, . . . ,2k − 1 bilden eine Orthonormalbasis

von Vk+1.

b) Multiskalenbasis von Vk+1 =V0⊕W0⊕W1⊕·· ·⊕Wk:

χ,Ψjl l = 0, . . . ,k , j = 0, . . . ,2l−1

114

Wavelet-TransformationFür

f =2k+1−1

∑j=0

α jχk+1, j ∈Vk+1

gilt

f =2k−1

∑j=0

β jχk j + γ jΨjk mit β j =1√2(α2 j +α2 j+1) und γ j =

1√2(α2 j−α2 j+1)

Rekursiver Algorithmus für N = 2k:

S1) Falls N = 1: STOP

S2) Berechne

α+ = (α[0],α[2],α[4], . . . ,α[N−2])

α− = (α[1],α[3],α[5], . . . ,α[N−1])

β =1√2(α++α

−)

γ =1√2(α+−α

−)

S3) Aufruf für β mit N2 .

Aufwand: ∑kl=0 2l ≈ 2k+1 = 2 ·dimVk = O(N)

Wenden wir dieses Verfahren auf das EKG im am Anfang dieses Abschnitts an, sind 75%der 2048 Koeffizienten kleiner als 10−4.Vorteile:

+ schneller als FFT

+ bessere Lokalisierung (adaptive Wavelets)

+ bessere Approximation bei nicht-glatten Daten

Nachteile:

- langsame Konvergenz bei glatten Daten

Alternative: Wähle anderes Paar χ,Ψ , z.B.

χ(t) =

t, 0≤ t ≤ 12− t, 1≤ t ≤ 20, sonst

Konstruiere Ψ mit Orthogonalitätseigenschaft.

115