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 Vorlesung im Sommersemester 2009
Christian Wieners
Version vom 8. Juni 2011
Inhaltsverzeichnis
1 Einführendes Beispiel: Die euklidische Approximation 1
2 Direkte Lösungsverfahren für lineare Gleichungen 3
3 Eigenwertberechnung 23
4 Iterationsverfahren für lineare Gleichungssysteme 33
5 Iterationsverfahren für nichtlineare Gleichungen 41
6 Interpolation und Approximation 46
7 Numerische Integration 67
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 Mitarbeiternbedanken, die bei der Erstellung des Textes geholfen haben.
Literatur
Deuflhard / Hohmann: Numerische Mathematik I, de Gruyter 2002 (3. Auflage)Höllig: Grundlagen der Numerik, Zavelstein 1998Hanke-Bourgois: Grundlagen der Numerischen Mathematik, Teubner 2003Kress: 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 φ nNn=1,...,N eine Basis von VN . Zunächst benötigen wir ein Hilfsresultat.
(1.2) LemmaDie Matrix
A =(〈φ m
N ,φ nN〉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=1ynφ n
N 6= 0, denn die Basisvektoren φ nN sind linear unabhängig.
Also gilt ‖∑Nn=1 ynφ n
N‖V > 0 und somit
yT Ay =N
∑m=1
ym
N
∑n=1
yn〈φ mN ,φ n
N〉V
=N
∑m=1
ym〈φ mN ,
N
∑n=1
ynφnN〉V
= 〈N
∑m=1
ymφmN ,
N
∑n=1
ynφnN〉V = ‖
N
∑n=1
ynφnN‖2
V ≥ 0 .
(1.3) SatzProblem (1.1) ist eindeutig lösbar. Es gilt
v∗N =N
∑n=1
x∗nφnN ,
wobei x∗ ∈ RN die eindeutige Lösung des linearen Gleichungssystems
Ax∗ = b
mit b =(〈v,φ m
N 〉V)
m=1,...,N∈ RN ist.
1
Beweis. Definiere f (x) = 12
∥∥v−∑Nn=1 xnφ n
N
∥∥2V . Dann gilt
2 f (x) =⟨v−
N
∑m=1
xmφmN ,v−
N
∑n=1
xnφnN⟩
V
= 〈v,v〉V −N
∑m=1
xm⟨φ
mN ,v〉V −
N
∑n=1
xn⟨v,φ n
N⟩
V +N
∑m=1
xm
N
∑n=1
xn⟨φ
mN ,φ n
N⟩
V
=⟨v,v〉V −2xT b+ xT Ax .
Also ist f beliebig oft stetig differenzierbar, und es gilt
∂
∂xnx = en (n-ter Einheitvektor in RN),
∂
∂xnf (x) = −(en)T b+
12(en)T Ax+
12
xT Aen = (en)T (Ax−b) ,
∂ 2
∂xm∂xnf (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
Die LR-Zerlegung(2.1) DefinitionSei x = (xn)n=1,...,N ∈ RN ein Spaltenvektor, und sei A = (am,n)m=1,...,M, n=1,...,N ∈ RM,N
eine Matrix.
(a) Sei 1≤ m≤ n≤ N. Dann ist
x[m : n] = (xk)k=m,...,n ∈ R1+n−m
Teilvektor von x.
(b) Seien 1≤ m1 ≤ m2 ≤M, 1≤ n1 ≤ n2 ≤ N. Dann ist
A[m1 : m2,n1 : n2] = (a jk) j=m1,...,m2, k=n1,...,n2 ∈ R1+m2−m1,1+n2−n1
Untermatrix von A.
(c) Die Matrix A lässt sich in A = lower(A)+diag(A)+upper(A) zerlegen. Dabei ist
(i) lower(A) ∈ RM,N eine strikte untere Dreiecksmatrix mitlower(A)[m,n] = A[m,n] für m > n,
(ii) diag(A) ∈ RM,N eine Diagonalmatrix mitdiag(A)[n,n] = A[n,n] für n = 1, ...,minM,N,
(iii) upper(A) ∈ RM,N eine strikte obere Dreiecksmatrix mitupper(A)[m,n] = A[m,n] für m < n.
(d) A ist eine untere Dreiecksmatrix, wenn A = diag(A)+ lower(A) gilt.A ist eine obere Dreiecksmatrix, wenn A = diag(A)+upper(A) gilt.Eine Dreiecksmatrix A heißt normiert, wenn diag(A)[n,n] = 1 für n = 1, ...minM,Ngilt.
(e) Mit 0N ∈RN wird der Nullvektor bezeichnet, mit en ∈RN wird der n-te Einheitsvektorbezeichnet, und mit IN ∈ RN,N die Einheitsmatrix.
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]
).
3
(2.2) Satz(a) Sei L ∈ RN,N eine normierte untere Dreiecksmatrix und b ∈ RN . Dann ist L regulär
und das Lineare Gleichungssystem (LGS) Ly = b ist mit O(N2) Operationen lösbar.
(b) Für eine reguläre obere Dreiecksmatrix R ∈ RN,N ist das LGS Rx = y in O(N2) Ope-rationen 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) 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]0T
N−n R[n : N,n : N]
)(x[n−1 : n−1]
x[n : N]
)=(
y[n−1 : n−1]y[n : N]
)folgt R[n−1,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,1 : n−1]
mit O(N) Operationen berechenbar. Zusammen werden somit O(N2) benötigt.
(2.3) SatzWenn eine Matrix A ∈ RN,N eine LR-Zerlegung
A = LR L normierte untere Dreiecksmatrix,R reguläre obere Dreiecksmatrix
besitzt, dann ist A regulär und das 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) 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] 0Tn
L[n+1,1 : n] 1
)(L[1 : n,1 : n]−1 0T
n`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, daher auch 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.
(2.5) SatzEine Matrix A ∈ RN,N besitzt genau dann eine LR-Zerlegung von A, wenn alle Hauptun-termatrizen A[1 : n,1 : n] regulär sind. Die LR-Zerlegung ist eindeutig und lässt sich mitO(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] .
5
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 RR−1 = L−1L.Da RR−1 eine obere Dreiecksmatrix ist, gilt 0 = lower(RR−1) = lower(L−1L). Also istRR−1 = L−1L = IN + lower(L−1L) = IN . Daraus folgt R = R und dann L = L.(iii) Aufwand:Nun folgt noch die Berechnung des Aufwandes: In jedem Schritt werden zwei Dreiecks-systeme mit O(n2) Operationen gelöst, N Schritte werden benötigt. Damit ist die Anzahlder Operationen in der Größenordnung O(N3).
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.6) DefinitionEine Matrix A ∈ RN,N heißt diagonal-dominant, wenn
|amm| ≥N
∑n=1n6=m
|amn| , m = 1, ...,N
gilt, und strikt diagonal-dominant, falls
|amm|>N
∑n=1n6=m
|amn| , m = 1, ...,N .
6
(2.7) FolgerungWenn A ∈ RN,N strikt diagonal dominant ist, dann existiert eine LR-Zerlegung.
Beweis. Wenn keine LR-Zerlegung existiert, dann ist für ein n die Untermatrix A[1 : n,1 :n] singulär, und es existiert x ∈ Rn mit x 6= 0 und A[1 : n,1 : n]x = 0. Nun wähle m ∈1, ...,n mit xm ≥ xk. Dann folgt aus A[m,1 : n]x = 0
|amm| |xm|=∣∣∣ n
∑k=1k 6=m
amkxk
∣∣∣≤ n
∑k=1k 6=m
|amk| |xk| ≤n
∑k=1k 6=m
|amk| |xm|< |amm| |xm|
ein Widerspruch.
(2.8) SatzSei A∈RN,N symmetrisch und positiv definit. Dann existiert genau eine Cholesky-ZerlegungA = LDLT mit einer normierten unteren Dreiecksmatrix L und einer Diagonalmatrix D.
Beweis. Wenn keine LR-Zerlegung existiert, dann ist für ein n die Untermatrix A[1 : n,1 :n] singulär, und es existiert x ∈Rn mit x 6= 0 und A[1 : n,1 : n]x = 0. Dann gilt auch Ay = 0für y ∈ RN mit y[1 : n] = x und y[n + 1,N] = 0N−n, also y 6= 0 und yT Ay = 0. Das ist einWiderspruch zur Voraussetzung, dass A positiv definit ist.Also existiert eine LR-Zerlegung A = LR = LD
(D−1R
)mit D = diag(R). Da A symme-
trisch ist, gilt A = AT = RT LT =(D−1R
)T DLT . Da die LR-Zerlegung eindeutig ist, giltL =
(D−1R
)T und R = DLT .
Die klassische Cholesky-Zerlegung berechnet A = LLT mit L = L√
D.
Die Berechnung der Cholesky-Zerlegung benötigt nur halb soviele Operationen wie dieBerechnung einer LR-Zerlegung.
Gauß-Algorithmus und Cholesky-Algorithmus erhalten die Hüllenstruktur von A, d.h. fürm < n gilt: Aus A[n,1 : m] = 0T
m folgt L[n,1 : m] = 0Tm, und aus A[1 : m,n] = 0m folgt
L[n,1 : m] = 0m. Für Matrizen mit vielen 0-Einträgen kann versucht werden, durch Zeilen-und Spaltenvertauschung die Hüllenstruktur zu vergrößern.
Eine Matrix mit Hüllenstruktur für m = n−1− k ist eine Bandmatrix mit der Bandbreite2k +1.
Die LR-Zerlegung mit Pivotsuche
Durch Zeilenvertauschungen von A lässt sich immer garantieren, dass eine LR-Zerlegungexistiert.
(2.9) DefinitionSei π ∈ SN eine Permutation. Dann heißt Pπ =
(eπ(1)
∣∣ · · · ∣∣eπ(N)) ∈RN,N Permutationsma-trix zu π . Wir schreiben P(mn) für die Permutationsmatrix mit der Vertauschung π = (mn),d.h. π(m) = n, π(n) = m, π(k) = k für k 6= m,n.
7
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 Multiplikation einer Matrix A ∈ RM,N mit einer Permultationsmatrix Pπ von linksvertauscht die Zeilen (bzw. mit Pσ von rechts vertauscht die Spalten)
PπA =
A[π−1(1),1 : N]...
A[π−1(M),1 : N]
, APσ =(
A[1 : M,σ(1)]∣∣∣ · · · ∣∣∣A[1 : M,σ(N)]
).
Also ist die Zeile n von A die Zeile π(n) von PπA. Das heißt, dass in der Zeile n von PπAdie Zeile π−1(n) von A steht.
(2.10) SatzDie Permutationsmatrizen in RN,N bilden eine Gruppe.Es gilt Pσ Pπ = Pπσ und Pπ−1 = PT
π .
(2.11) SatzSei A ∈ RN,N regulär. Dann existiert eine Permutationsmatrix P, so dass PA eine LR-Zerlegung PA = LR besitzt und für die Einträge |L[m,n]| ≤ 1 gilt.
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[p1,1] mit dem größten Betrag,d.h. |A[p1,1]| ≥ |A[m,1]| für alle m = 1, ...,N. Da A regulär ist, ist A[1 : N,1] 6= 0N , alsoA[p1,1] 6= 0. Falls p1 6= 1, vertausche die Zeilen 1 und p1 und setze π1 = (1p1). Sonstsetze π1 = id. Nun setze A1 = Pπ1A,
L1 =(
1 0TN−1
−A1[2 : N,1]/A1[1,1] IN−1
), R1 =
(A1[1,1] A1[1,2 : N]0N−1 A2
).
mit der Restmatrix A2 = A1[2 : N,2 : N]+L1[2 : N,1]R1[1,2 : N]. Dann gilt per Konstruk-tion L1A1 = R1. Aus
A1[1,1]detA2 = detR1 = det(L1Pπ1A) = detPπ1 detA 6= 0
8
folgt detA2 6= 0. Also existiert in RN−1,N−1 per Induktionsvoraussetzung eine LR-ZerlegungP2A2 = L2R2, also A2 = PT
2 L2R2 und
R1 =(
1 0TN−1
0N−1 PT2
)(1 0T
N−10N−1 L2
)(R1[1,1] R1[1,2 : N]0N−1 R2
).
Dann erhalten wir für
P =(
1 0TN−1
0N−1 P2
)Pπ1 ,
L1 =(
1 0TN−1
0N−1 P2
)L−1
1
(1 0T
N−10N−1 PT
2
)=(
1 0TN−1
PT2 A1[2 : N,1]/A1[1,1] IN−1
)eine LR-Zerlegung mit Pivotsuche
PA =(
1 0TN−1
0N−1 P2
)A1
=(
1 0TN−1
0N−1 P2
)L−1
1
(1 0T
N−10N−1 PT
2
)(1 0T
N−10N−1 L2
)(R1[1,1] R1[1,2 : N]0N−1 R2
)=(
1 0TN−1
PT2 A1[2 : N,1]/A1[1,1] L2
)(R1[1,1] R1[1,2 : N]0N−1 R2
)= LR .
Das System Ax = b wird dann wie folgt gelöst: Es gilt LRx = PAx = Pb. Berechne ersty = Rx durch Vorwärtssubstitution von Ly = Pb und dann x durch Rückwärtssubstitutionvon Rx = y.Die Spaltenpivotsuche benötigt zusätzlich O(N2) Operationen. Die Stabilität (siehe un-ten) der LR-Zerlegung lässt sich durch sogenannte totale Pivotsuche erhöhen: Durch denZeilen- und Spaltentausch ersetze in jedem Schritt An[1,1] durch den maximalen Eintragin der Restmatrix An. Aber hierfür beträgt der Aufwand O(N3) Operationen.
9
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
10
Kondition und Stabilität
Bei vielen Anwendungen sind die Daten (z.B. durch ungenaue Messungen) unsicher. Dazuführen wir einige Begriffe ein.
(2.12) Definitiona) 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 Daten-Abhängigkeit der numerischen Lösung im Vergleich zu der tatsächlichen Lösung ist.
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.Sei nun | · | eine Vektornorm, und sei ‖ · ‖ eine zugeordete Matrixnorm, d. h.,
|Ax| ≤ ‖A‖|x| , x ∈ RN , A ∈ RM,N .
(2.13) 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
∞
∑n=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∞
∑n=0
(−∆AA−1)k
11
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−∆Ax|
≤ ‖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.
Matrixnormen
Wir verwenden für x ∈ RN und A ∈ RM,N
|x|1 =N
∑n=1|xn| 1-Norm
|x|2 =√
xT x 2-Norm / euklidische Norm|x|∞ = max
n=1,...,∞|xn| Maximumsnorm
‖A‖p = supx 6=0N
|Ax|p|x|p
zugeordnete Operatornorm (p = 1,2,∞) .
(2.14) SatzSei A ∈ RM,N . Dann gilt
‖A‖1 = maxn=1,...,N
M
∑m=1|amn| Spaltensummennorm
‖A‖2 =√
ρ(AT A) Spektralnorm
‖A‖∞ = maxm=1,...,M
N
∑n=1|amn| Zeilensummennorm .
Dabei ist
ρ(A) = max|λ | : λ ∈ σ(A) Spektralradius,σ(A) = λ ∈ C : det(A−λ IN) = 0 Spektrum .
Beweis. p = 1,∞: Schnaubelt, Analysis II, Bsp. 1.15.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) =: Λ
12
und Eigenwerten λn ≥ 0 von AT A. Wähle m mit ρ(AT A) = |λm| ≥ |λn| für n = 1, . . . ,N .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≤ λm |y|22.
Damit ergibt sich (mit der Substitution x = Qy)
‖A‖= supx 6=0
|Ax|2|x|2
= supy6=0
|AQy|2|Qy|2
≤ supy6=0
√λm |y|2|y|2
=√
ρ(AT A) .
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 =max
n=1,...,N|λn|
minn=1,...,N
|λn|.
Rundungsfehleranalyse und Zahldarstellung
In der Praxis muss das Schema Eingabe—Algorithmus—Resultat ergänzt werden:Untersuche Eingabefehler—Fehler im Algorithmus—Fehler im Resultat.
(2.15) Definitiona) Eine Gleitkommadarstellung ist eine Abbildung
fl: R−→ FL = ±m ·2e; m,e ∈ N, 0≤ m≤M, E− ≤ e≤ E+
mit fl(x) = x für x ∈ FL .
b) Die Maschinengenauigkeit ist
eps := sup|x−fl(x)||x|
; 0 < |x|< M
.
c) Als Ergebnis einer Rechenoperation werden zusätzliche folgende Fehlerzustände defi-niert:NaN (not a number) nicht definiertes Ergebnisoverflow |x|> (M−1)2E+
underflow |x| 6= 0 und |x|< 2E− , dann ist fl(x) = 0.
13
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+ = 1025 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.
14
QR-Zerlegung(2.16) LemmaSei Q ∈ RN,N orthogonal, d.h. QT Q = IN . Dann gilt κ2(Q) = 1.
Beweis. Es gilt
|Qx|22 = (Qx)T Qx = xT QT Qx = xT x = |x|22,
und somit folgt
‖Q‖2 = supx 6=0
|Qx|2|x|2
= supx 6=0
|x|2|x|2
= 1.
Ferner gilt ‖Q−1‖2 = ‖QT‖2 = 1, sodass κ2(Q) = ‖Q‖2‖Q−1‖2 = 1.
BemerkungDie orthogonale Matrizen bilden eine Gruppe.
(2.17) Lemma (Givensrotation)Zu x ∈ RN und m 6= n mit x2
m + x2n > 0 existiert eine orthogonale Matrix Q ∈ RN,N mit(
Q[m,m] Q[m,n]Q[n,m] Q[n,n]
)=(
c s−s c
), c2 + s2 = 1 ,
und Q[k][k] = 1 für k 6= n,m und Q[k][ j] = 0 sonst, so dass für y = Qx gilt: yn = 0.
Beweis. Aus y = Qx folgt
yi =
xi i 6= m,ncxm + sxn i = m−sxm + cxn i = n
Soll nun yn =−sxm + cxn = 0 gelten, dann folgt sxm = cxn. Zur stabilen Berechnung vonc, s müssen wir Auslöschung vermeiden, also unterscheiden wir zwei Fälle:Fall 1: Für |xn|> |xm| setze τ =
xm
xn=
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 |xm| ≥ |xn| setze τ =xn
xm=
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.
15
(2.18) Lemma (Householdertransformation)Zu x ∈RN , x 6= 0, existiert eine orthogonale Matrix Q = IN−βwwT ∈RN,N mit β = 2
wT w ,w1 = 1 und Qx = σe1 mit σ ∈ R.
Beweis. Aus dem Ansatz
Qx =(IN−βwwT)x = x−2
wT xwT w
w != σe1
folgt x−σe1 = µw, und w1 = 1 ergibt µ = x1−σ . Weiterhin gilt
|x|2 = |Qx|2 = |σe1|2 = |σ | .
Zur Vermeidung von Auslöschung betrachte zwei Fälle:1. Fall: Für x1 > 0 wähle σ =−|x|2, d.h. w = 1
x1+|x|2 (x+ |x|2e1). 2. Fall: Für x1 ≤ 0 wähle
σ = |x|2, d.h. w = 1x1−|x|2 (x−|x|2e1).
Q beschreibt eine Spiegelung an der Ebene senkrecht zu w.Es gilt wwT = (w1w|w2w|w3w| . . .) und (wwT )T = wwT , also QT = Q. Aus
QT Q = Q2 =(
IN−2
wT wwwT
)(IN−
2wT w
wwT)
= IN−4
wT w︸ ︷︷ ︸=2β
wwT +4
(wT w)2︸ ︷︷ ︸=β 2
(wwT )(wwT )︸ ︷︷ ︸=w(wT w)wT
!= IN .
folgt 2β = β 2wwT , also β = 0 oder β = 2wT w . Q ist selbstinvers, symmetrisch und ortho-
gonal.
(2.19) Satz (QR-Zerlegung)Sei A ∈RM,N . Dann existiert eine orthogonale Matrix Q ∈RM,M und eine obere Dreiecks-matrix R ∈ RM,N mit A = QR.
Beweis. Wir führen eine Induktion über M durch. Für M = 1, N beliebig folgt sofortQ = 1, R = A.M− 1→ M: Nach Induktionsvoraussetzung existiere eine QR-Zerlegung für M− 1 undbeliebige N. Setze x = A[1 : M,1] ∈ RM. Wir unterscheiden zwei Fälle:1. Fall: x[2 : M] = 0M−1Setze Q1 = IM und σ = A[1,1].2. Fall: x[2 : M] 6= 0M−1. Setze
σ =
−|x|2 x1 > 0,
|x|2 x1 ≤ 0,w =
1x1−σ
(x−σe1) , Q1 = IN−2
wT wwwT .
Damit gilt
Q1A =(
σ R1[1,2 : N]0M−1 A2
),
16
Algorithmus 4 Berechnung eines Householder-Vektors.
function [v,beta] = householder(y)N = length(y);s = y(2:N)’ * y(2:N);if N == 1
s = 0;endv = [1;y(2:N)];if s == 0
beta = 0;else
mu = sqrt(y(1)^2 + s);if y(1) <= 0
v(1) = y(1) - mu;else
v(1) = -s/(y(1) + mu);endbeta = 2*v(1)^2/(s + v(1)^2);v = v / v(1);
endreturn
mitR1[1,2 : N] = Q1[1,1 : M]A[1 : M,2 : N] ∈ RM,N−1
undA2 = Q1[2 : M,1 : M]A[1 : M,2 : N] ∈ RM−1,N−1.
Nun sei A2 = Q2R2 ∈ RM−1,N−1 eine QR-Zerlegung der Restmatrix. Also
A = Q21A = Q1(Q1A) = Q1
(σ R1[1,2 : N]
0M−1 Q2R2
)= Q1
(1 0T
N−10M−1 Q2
)︸ ︷︷ ︸
=:Q
(σ R1[1,2 : N]
0M−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 (N = M),
LR−Zerlegung :23
N3 Operationen,
LLT −Zerlegung :13
N3 Operationen.
17
Algorithmus 5 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 ~= 2
b(m:M) = b(m:M) - beta*(v’ * b(m:M)) * v;end
endx = 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
18
Lineare Ausgleichsrechnung
Im Allgemeinen ist das lineare Gleichungssystem Ax = b für b ∈ RM und A ∈ RM,N nichtoder nicht eindeutig lösbar. Stattdessen untersuchen wir nun das Minimierungsproblem:
Bestimme x ∈ RN mit |Ax−b|2 = Min!
(2.20) SatzSei A ∈ RM,N , b ∈ RM. Dann ist äquivalent:
(a) x ∈ RN minimiert |Ax−b|2.
(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((Ax)T (Ax)− (Ax)T b−bT (Ax)+bT b)
=12
xT (AT A)x−bT Ax+12
bT b.
Es gilt
∂
∂xnF(x) =
12(en)T (AT A)x+
12
xT (AT A)en−bT Aen = (en)T (AT Ax−AT b),
und
∂
∂xn∂xmF(x) = (en)T AT Aem.
„(a)⇒ (b)“Aus F(x) = Min! folgt ∇F(x) = 0, also AT Ax−AT b = 0.„(b)⇒ (a)“Sei AT Ax−AT b = 0, dann folgt mittels Taylor-Entwicklung
F(y) = F(x)+∇F(x)T (y− x)︸ ︷︷ ︸=0
+12
(y− x)T∇
2F(x)(y− x)︸ ︷︷ ︸=|Ay−Ax|22≥0
≥ F(x).
Die Singulärwertzerlegung(2.21) SatzSei A ∈RM,N mit R = rang A. Dann existieren Singulärwerte σ1, . . . ,σR > 0 und orthogo-nale Matrizen V ∈ RM,M, U ∈ RN,N und eine Zerlegung
A = V ΣUT
mit Σ ∈ RM,N , Σ[r,r] = σr für r = 1, ...,R und Σ[m,n] = 0 sonst.
19
Beweis. Die Matrix AT A ∈RN,N ist symmetrisch und positiv semi-definit mit rang A = R.Also existiert eine orthogonale Matrix U ∈ RN,N mit
UT (AT A)U = diag(λ1, . . . ,λN)
mit Eigenwerten λn, n∈ 1, . . . ,N von AT A. Ohne Einschränkung gilt λ1, . . . ,λR > 0 undλR+1, . . . ,λN = 0. Dann definiere σr =
√λr > 0.
Als nächstes berechne eine QR-Zerlegung von AU = QB mit orthogonaler Matrix Q ∈RM,M und oberere Dreiecksmatrix B ∈ RM,N .Damit folgt
BT B = (QT AU)T (QT AU) = UT AT QQT AU = diag(λ1, . . . ,λN).
Somit gilt B[1,1]2 = λ1 und B[1,1]B[1,2 : N] = 0TN−1, also B[1,2 : N] = 0T
N−1. Induktivfolgt B[r,r]2 = λr und B[r,r +1 : N] = 0T
N−r für r = 2, ...,R.Nun definiere S ∈ RM,M mit
S[r,r] =
−1 B[r,r] < 01 sonst,
für r = 2, ...,R ,
und S[m,n] = 0 sonst. Dann gilt SB = Σ.Setze V = QS ∈ RM,M orthogonal, dann folgt
V ΣUT = QSΣUT = QBUT = AUUT = A.
BemerkungDie Spalten un = U [1 : N,n], n = 1, ...,N, bilden eine ONB von RN , die Spalten vm = V [1 :M,m], m = 1, ...,M, bilden eine ONB von RM. Damit ergibt sich die Darstellung
Ax = V ΣUT x =R
∑r=1
σr(xT ur)vr ,
und es gilt
kern A = spanuR+1, . . . ,uN,bild A = spanv1, . . . ,vR.
(2.22) DefinitionWir definieren die Pseudo-Inverse durch
A+ = UΣ+V T ∈ RN,M
mit Σ+ ∈ RN,M, Σ+[r,r] = 1σr
für r ∈ 1, . . . ,R und Σ[m,n] = 0 sonst.
BemerkungEs gilt
A+y =R
∑r=1
1σr
(yT vr)ur.
Ist außerdem N = M = R, dann gilt A+ = A−1.
20
(2.23) LemmaDie Normalengleichung und damit |Ax−b|2 = Min! wird durch x = A+b gelöst.
Beweis. Sei dazu x = A+b, dann gilt UT x = Σ+V T b. Wegen ΣT ΣΣ+ = ΣT ist ΣT ΣUT x =ΣTV T b und nach Erweitern schließlich
UΣTV T︸ ︷︷ ︸
=AT
V ΣUT x = UΣTV T︸ ︷︷ ︸
=AT
b.
Die Tikhonov-Regularisierung
Zwei Probleme bleiben bei den bisherigen Verfahren bestehen:
Problem 1: Wenn eine Aufgabe A schlecht konditioniert ist dann werden Datenfehlerextrem verstärkt. Dies ist zum Beispiel der Fall bei Ax = b mit κ(A) 1.
Problem 2: Wenn eine Aufgabe A nicht sachgemäß gestellt ist, ist sie entweder nichteindeutig lösbar oder die Lösung ist nicht stetig abhängig von den Daten. Einesolche Situation tritt beispielsweise auf bei |Ax−b|2 = min! für Kern A 6= 0.
Um bei diesen Problemen Abhilfe zu schaffen verwende eine Aufgabe Aα = Regulari-sierung von A , die besser konditioniert ist (Problem 1) oder die sachgemäß gestellt ist(Problem 2), sodass für eine Eingabe e gilt
limα→0
Aα(e) = A (e).
Die Wahl von α muss dabei ein Kompromiss zwischen Regularisierung und Fehlerver-stärkung durch κ(Aα) sein.
(2.24) SatzZu A∈RM,N , b∈RM, α > 0 existiert genau ein xα ∈RN , das 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 AT b+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) = 0, also AT Ax+αx = AT b. Folglich istxα einziger kritischer Punkt und da ∇2Fα(xα) positiv definit ist, ist xα ein Minimum.
21
(2.25) SatzEs gilt:
limα→0
xα = limα→0
(AT A+αIN)−1AT b = A+b.
Beweis. Sei A = V ΣUT Singulärwertzerlegung und R = rang A. Dann gilt
AT A = UΣTV TV ΣUT = U(ΣT
Σ)UT .
Somit folgt für un = U [1 : N,n] und vm = V [1 : M,m]
(AT A+αIN)un = (σ2n +α)un ,
AT b = UΣTV T b =
k
∑r=1
((vr)T b)σrur ,
also
xα = (AT A+αIN)−1AT b =R
∑r=1
(bT vr)σr(AT A+αIN)−1ur
=R
∑r=1
(bT vr)σr
σ2r +α
ur,
und somit
limα→0
xα =R
∑r=1
(bT vr)1σr
ur = A+b.
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)+α
α.
22
3 Eigenwertberechnung
(3.1) DefinitionEine Matrix A ∈ RN,N heißt (obere) Block-Dreiecksmatrix, wenn ein n ∈ N existiert, so-dass A[n+1 : N,1 : n] = 0 gilt, d.h.:
A =(
A[1 : n,1 : n] A[1 : n,n+1 : N]0 A[n+1 : N,n+1 : N]
)Sie heißt reduzibel, wenn eine Permutationsmatrix P existiert, so dass PAPT Block-Drei-ecksmatrix ist.Sie heißt irreduzibel, wenn keine Permutationsmatrix P existiert, so dass PAPT Block-Dreiecksmatrix ist.
Für reduzible Matrizen lässt sich die Eigenwertberechnung in zwei kleinere Probleme (derGröße n und N−n) unterteilen.
(3.2) DefinitionEine Matrix H ∈ RN,N heißt (obere) Hessenberg-Matrix, 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.
(3.3) SatzSei A ∈ RN,N . Dann existiert eine orthogonale Matrix Q ∈ RN,N , so dass H = QAQT eineHessenberg-Matrix ist. Die Berechnung von Q benötigt O(N3) Operationen.
Beweis. Induktion über N.Für N < 3 ist nichts zu zeigen.N ≥ 3: Definiere x ∈ RN mit: x[1] = 0, x[2 : N] = A[2 : N,1]1.Fall: x[3 : N] = 0N−2Dann setze Q1 := IN , A1 := A.2.Fall: x[3 : N] 6= 0N−2Setze
σ =−|x|2, x[2] > 0|x|2, x[2]≤ 0 ,
w =1
x[2]−σ
(x−σe2
)∈ RN ,
Q1 = IN−βwwT mit β :=2
wT w.
Damit ergibt sich
A1 := Q1AQT1 =
A[1,1] A1[1,2 : N]σ
0N−2A2
23
mit
A1[1,2 : N] = A[1,2 : N]−β (A[1,2 : N]w[2 : N]wT [2 : N])
A2 = (IN−1−βw[2 : N]wT [2 : N])A[2 : N,2 : N](IN−1−βw[2 : N]wT [2 : N]) .
Nach Induktionsvoraussetzung existiert eine orthogonale Matrix Q2 ∈ RN−1,N−1, so dassH2 = Q2A2QT
2 eine obere Hessenberg-Matrix ist. Setze
Q :=(
1 0N−10N−1 Q2
)Q1 .
Somit folgt
QAQT =(
1 0TN−1
0N−1 Q2
)A1
(1 0T
N−10N−1 Q2
)=
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.
Wenn A symmetrisch ist, dann ist H = QAQT eine Tridiagonalmatrix.
(3.4) SatzSei A ∈ RN,N symmetrisch, tridiagonal und irreduzibel, d.h. A[n− 1,n] = A[n,n− 1] 6= 0und A[n + 2 : N,n] = A[n,n + 2 : N]T = 0N−n−1. Für das Spektrum von A gelte σ(A) ⊂(λ ,λ ).
a) Die charakteristischen Polynome Pn(t) = det(A[1 : n,1 : n]− tIn
)der Hauptunter-
matrizen lassen sich durch eine Dreitermrekursion berechnen: Setze
P0 ≡ 1 ,
P1(t) = A[1,1]− t ,Pn(t) = (A[n,n]− t)Pn−1(t)−A[n−1,n]2Pn−2(t) , n = 2, ...,N .
b) Sie bilden eine Sturmsche Kette: Für die Nullstellen λ n1 ≤ λ n
2 ≤ ·· · ≤ λ nn von Pn gilt
λn−1k−1 < λ
nk < λ
n−1k
(mit λ n0 = λ und λ n
n+1 = λ ).
c) Für t ∈ (λ ,λ ) gilt
λnk < t ≤ λ
nk+1
mit k = Wn(t) und Wn(t) = #
j ∈ 1, ...,n : Pj(t)Pj−1(t) < 0 oder Pj−1(t) = 0
.
24
Algorithmus 6 Berechnung der Hessenberg-Transformation für allgemeine Matrizen mitAbspeicherung der Householder-Vektoren, Rekonstruktion der orthogonalen Transforma-tionsmatrix, und Berechnung der Hessenberg-Transformation für symmetrische Matritzenohne Abspeicherung der Householder-Vektoren.
function A = hessenberg(A)N = size(A,1);for n = 1:N-2
[v,beta] = householder(A(n+1:N,n));if beta ~= 0
w = beta * A(:,n+1:N) * v;A(:,n+1:N) = A(:,n+1:N) - w * v’;w = beta * v’ * A(n+1:N,n:N);A(n+1:N,n:N) = A(n+1:N,n:N) - v * w;A(n+2:N,n) = v(2:N-n);
endend
return
function Q = hessenbergrotation(A)N = size(A,1);Q = eye(N);for n = 1:N-2
v = [1;A(n+2:N,n)];beta = 2 / (v’ * v);if beta ~= 2w = beta * v’ * Q(n+1:N,:);Q(n+1:N,:) = Q(n+1:N,:) - v * w;
endend
return
function A = symmetric_hessenberg(A)N = size(A,1);for n = 1:N-2
[v,beta] = householder(A(n+1:N,n));if beta ~= 0w = beta * A(n:N,n+1:N) * v;A(n:N,n+1:N) = A(n:N,n+1:N) - w * v’;w = beta * v’ * A(n+1:N,n:N);A(n+1:N,n:N) = A(n+1:N,n:N) - v * w;
endend
return
25
Beweis. zu a) Übung.zu b) und c) Induktion über n.Sei n = 1. Dann gilt λ 1
1 = A[1,1] ∈ (λ ,λ ), also
λ00 = λ < λ
11 < λ = λ
01 ,
und für t ∈ (λ ,λ ) gilt:
• Für W1(t) = 0 ist P0(t)P1(t)≥ 0, also t ≤ A[1,1] und λ 10 < t ≤ λ 1
1 .
• Für W1(t) = 1 ist somit t > A[1,1] mit λ 11 < t ≤ λ 1
2 .
n→ n+1:Nach Induktionsvoraussetzung ist Pn−1(λ n
k ) 6= 0. Damit ergibt sich aus a) Pn+1(λ nk ) =
−A[n,n+1]2Pn−1(λ nk ) 6= 0 und somit
Pn+1(λ nk )Pn−1(λ n
k ) < 0 . (1)
Nach Induktionsvoraussetzung hat Pn−1(·) genau eine Nullstelle in (λ nk−1,λ
nk ). Daraus
folgt Pn−1(λ nk−1)Pn−1(λ n
k ) < 0 und mit (1) gilt dann Pn+1(λ nk−1)Pn+1(λ n
k ) < 0. Somit exi-stiert auch eine Nullstelle von Pn+1(·) in (λ n
k−1,λnk ). Somit existieren mindestens n− 1
Nullstellen von Pn+1(·) in (λ n1 ,λ n
n ).
Analog folgt die Existenz von jeweils einer Nullstelle von Pn+1(·) in (λ ,λ n1 ) und (λ n
n ,λ ).Also gilt für alle n+1 Nullstellen λ n
k−1 < λn+1k < λ n
k . Aus k = Wn(t) folgt λ nk−1 < t ≤ λ n
kund
Pn(t)Pn+1(t) =k−1
∏i=1
(λ ni − t)(λ n+1
i − t)︸ ︷︷ ︸≥0
(λ n+1k − t)
n
∏i=k
(λ ni − t)(λ n+1
k+1 − t)︸ ︷︷ ︸≥0
.
Daher gilt Pn(t)Pn+1(t)≥ 0 genau dann, wenn λn+1k ≥ t. Das ergibt
Wn+1(t) = k ⇐⇒ λn+1k ≥ t ≥ λ
nk > λ
n+1k−1 ,
Wn+1(t) = k +1 ⇐⇒ λn+1k < t < λ
nk < λ
n+1k+1 .
Im Folgenden sei stets A ∈ RN,N symmetrisch mit Eigenwerten λ1, ...,λN und ONB ausEigenvektoren v1, ...,vN . Dann gilt
A =N
∑n=1
λnvn(vn)T .
(3.5) DefinitionDer Rayleigh-Quotient ist definiert durch
r(A,x) =xT AxxT x
, x ∈ RN , x 6= 0N .
(3.6) SatzSei |λ1|= ρ(A) und |λn|< |λ1| für n = 2, ...,N. Dann gilt für alle w ∈ RN mit wT v1 > 0:
limk−→∞
r(A,Akw) = λ1 , limk−→∞
1|A2kw|2
A2kw = v1 .
26
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
Somit folgt
r(A,Akw) =(Akw)T AAkw(Akw)T (Akw)
=λ
2k+11 ∑
Nn=1
(λnλ1
)2k+1(wT vn)2
λ 2k1 ∑
Nn=1
(λnλ1
)2k(wT vn)2
k→∞−−−→ λ1(wT v1)2
(wT v1)2 = λ1,
da
limk→∞
(λn
λ1
)k
=
1, n = 10, n 6= 1
und1
|A2kw|2A2kw k→∞−−−→ wT v1√
(wT v1)2v1 = v1.
(3.7) SatzSei w ∈ RN mit |w|2 = 1 und λ = r(A,w). Dann gilt
minn=1,...,N
|λ −λn| ≤ |Aw−λw|2.
Beweis. Es gilt w = ∑Nn=1(w
T vn)vn und damit 1 = |w|22 = wT w = ∑Nn=1(w
T vn)2.
Ferner
|Aw−λw|22 =
∣∣∣∣∣ N
∑n=1
λn(wT vn)vn−λ (wT vn)vn
∣∣∣∣∣2
2
=
∣∣∣∣∣ N
∑n=1
(λn−λ )(wT vn)vn
∣∣∣∣∣2
2
=N
∑n=1|λn−λ |2(wT vn)2 ≥ min
n=1,...,N|λn−λ |2
N
∑n=1
(wT vn)2
= minn=1,...,N
|λn−λ |.
(3.8) DefinitionEine konvergente Folge (dk)k∈N in R mit Grenzwert d∗ konvergiert
(a) linear, wenn c ∈ (0,1) und k0 ∈ N existieren mit
|dk+1−d∗| ≤ c |dk−d∗| für k ≥ k0
(b) superlinear, wenn zu jedem ε > 0 ein k0 ∈ N existiert mit
|dk+1−d∗| ≤ ε |dk−d∗| für k ≥ k0
27
(c) von der Ordnung p > 1, wenn C > 0 existiert mit
|dk+1−d∗| ≤C |dk−d∗|p .
Wenn der größte Eigenwert isoliert ist, konvergiert die einfache Vektoriteration linear(Satz 3.6). Mit Satz 3.7 erhalten wir ein Abbruchkriterium für die Iteration.
Inverse Iteration mit variablem Shift
S1) Wähle z0 ∈ RN , z0 6= 0N , ε ≥ 0. Setze k = 0.
S2) Setze wk = 1|zk|2
zk, sk = r(A,wk).
S3) Falls |Awk− skwk|2 ≤ ε STOP.
S4) zk+1 = (A− skIN)−1wk
S5) Setze k := k +1, gehe zu S2).
(3.9) SatzWenn der Startvektor z0 hinreichend nahe bei einem Eigenvektor vm mit isoliertem Eigen-wert λm liegt, konvergiert die Inverse Iteration mit variablem Shift kubisch (d.h. von derOrdnung p = 3).
Beweis. Setze v = vm und λ = λm mit Av = λv und vT v = 1. Da λ ein isolierter Eigenwertist, existiert ein ρ > 0 mit (λ −ρ,λ +ρ)∩σ(A) = λ.Der Beweis erfolgt in vier Schritten.(i) Definiere wk = wk− (vT wk)v. Dann ist wk = (vT wk)v + wk eine orthogonale Zerle-gung mit (wk)T v = 0 und 1 = |wk|22 = (vT wk)2 + |wk|22. Also existiert ein ϕk ∈ [0,π/2] mit|vT wk|= cos(ϕk) und |wk|2 = sin(ϕk), woraus wir folgende Darstellung erhalten:
wk = cos(ϕk)v+ sin(ϕk)wk, wk =wk
|wk|2.
Wir zeigen nun die Abschätzung |sin(ϕk+1)| ≤C |sin(ϕk)|3. Dann konvergiert wk kubischgegen einen Eigenvektor von A.(ii) Es gilt Awk = λ cos(ϕk)v+ sin(ϕk)Awk. Daraus folgt
sk = λ |cos(ϕk)|2 + |sin(ϕk)|2(wk)T Awk = λ + |sin(ϕk)|2[(wk)T Awk−λ
]und wegen λ ≤ ‖A‖2 sowie (wk)T Awk ≤ ‖A‖2:
|sk−λ | ≤ |sin(ϕk)|2(2‖A‖2).
(iii) Weiterhin haben wir
zk+1 = (A− skIN)−1wk =cos(ϕk)λ − sk
v+ sin(ϕk)(A− skIn)−1wk , (2)
also (für cos(ϕk) > 0)
|zk+1|2 ≥|cosϕk||λ − sk|
⇒ 1|zk+1|2
≤ |λ − sk||cosϕk|
.
28
Ferner gilt(A− skIN)−1wk = ∑
n6=m(λn− sk)−1
((wk)T vn
)vn.
(iv) Sei zk so nahe bei v, dass 2‖A‖2|sin(ϕk)|2 ≤ ρ
2 und |cos(ϕk)| > 1/2 gilt. Dann folgtmit (ii)
|λ − sk| ≤ρ
2,
und mit der Bedingung an ρ für n 6= m
1|λn− sk|
≤ 2ρ
.
Hiermit erhalten wir|(A− skIN)−1wk|2 ≤
2ρ
.
Aus wk+1 = 1|zk+1|2
zk+1 = cos(ϕk+1)v+ sin(ϕk+1)wk+1 und (2) folgt
|sin(ϕk+1)|=|sin(ϕk)(A− skIN)−1wk|2
|zk+1|2(iii)≤ |sin(ϕk)|
4ρ|λ − sk|
(ii)≤ 8‖A‖2
ρ|sin(ϕk)|3.
QR-Iteration mit Shift
S0) Gegeben sei A ∈ RN,N symmetrisch.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
sk = Ak[N,N]+dk− sgn(dk)√
d2k +Ak[N−1,N]2 .
S3) Berechne eine QR-Zerlegung
QkRk = Ak− skIN
und setze
Ak+1 = RkQk + skIN .
S4) Setze k := k +1, gehe zu S1).
29
Es gilt
Ak+1 = RkQk + skIN = QTk (Ak− skIN)Qk + skIN = QT
k AkQk . (3)
Somit wird A in jedem Schritt nur mit orthogonalen Matrizen transformiert, die Eigen-werte ändern sich nicht. Da wir die QR-Iteration auf tridiagonale irreduzible Matrizenanwenden, sind alle Eigenwerte verschieden, vgl. Satz (3.4). Dann lässt sich zeigen, dassdie QR-Iteration (ohne variablen Shift) gegen eine Diagonalmatrix konvergiert (lineareKonvergenz). Mit variablem Shift ist die Konvergenz weit besser.
(3.10) SatzFalls in S2) der Shift sk = Ak[N,N] gewählt wird, entspricht die QR-Iteration der InversenIteration mit variablem Shift für die Matrix A0 und den Startvektor z0 = eN .
Beweis. Sei z0 = eN . Im ersten Schritt gilt w0 = z0 = eN und s0 = r(A0,eN) = A0[N,N].Es genügt wk = Q0Q1 · · ·Qk−1eN zu zeigen, denn dann folgt aus (3)
sk = r(A0,wk) = r(Ak,w0) = Ak[N,N] .
Da Ak symmetrisch ist, gilt Ak− skIN = QkRk = RTk QT
k . Aus zk+1 = (A0− s0IN)−1wk folgt
eN = QTk−1 · · ·QT
0 wk
= QTk−1 · · ·QT
0 (A0− skIN)zk+1
= (A1− skIN)QTk−1 · · ·QT
0 zk+1
= RTk QT
k QTk−1 · · ·QT
0 zk+1 ,
also
QTk QT
k−1 · · ·QT0 zk+1 = R−T
k eN = Rk[N,N]−1eN .
Daraus folgt |zk+1|2 = |Rk[N,N]|−1 und somit die Behauptung wk+1 = 1|zk+1|2
zk+1Q0 · · ·QkeN .
(3.11) Satz (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 ∈ RN\0 mit Aw = λw. Also existiert einn ∈ 1, . . . ,N mit
0 6= |wn| ≥ |wm| , m = 1, . . . ,N .
30
Algorithmus 7 QR-Iteration mit implizitem Shift.
function [c,s] = givens_parameter(a,b)if b == 0.0
c = 1.0; s = 0.0;else
if abs(b) > abs(a)t = -a/b; s = 1/sqrt(1+t^2); c = s*t;
elset = -b/a; c = 1/sqrt(1+t^2); s = c*t;
endend
return
function A = givens_transformation(A,G,k)N = size(A,1);if k>1 && k<N-1 && N>=3
ind = k-1:k+2;elseif k==N-1 && N>=3
ind = N-2:N;elseif k==1 && N>=3
ind = 1:3;elseif N == 2
ind = 1:2;endA([k k+1],ind) = G’ * A([k k+1],ind);A(ind,[k k+1]) = A(ind,[k k+1]) * G;
return
function lambda = qr_iteration(A,tol)N = size(A,1);H = symmetric_hessenberg(A);while 1
h00 = H(N-1,N-1); h10 = H(N,N-1); h11 = H(N,N);if (abs(h10) < tol*abs(h11+h00)), N = N-1; endif N < 2, break; endd = (h00 - h11)/2;if d ~= 0, mu = h11 + d - sign(d)*sqrt(d^2+h10^2);else, mu = h11 - h10; enda = H(1,1) - mu; b = H(2,1);for k = 1:N-1
[c,s] = givens_parameter(a,b);H = givens_transformation(H,[c,s;-s,c],k);if k<N-1, a = H(k+1,k); b = H(k+2,k); end
endendlambda = diag(H)
return
31
Damit folgt
A[n,1 : N]w = λwn⇒(A[n,n]−λ )wn =− ∑m 6=n
A[n,m]wm
⇒|A[n,n]−λ ||wn| ≤ ∑m 6=n|A[n,m]||wm| ≤ |wn| ∑
m 6=n|A[n,m]|
⇒|λ −A[n,n]| ≤ ∑m 6=n|A[n,m]| ⇒ λ ∈ Kn.
Für irreduzible Matrizen gilt eine Verschärfung: Die Eigenwerte liegen im Inneren derGershgorin-Kreise oder auf dem Durchschnitt der Ränder der Gershgorin-Kreise.
(3.12) Satz (Courant-Hilbert)Sei A ∈ RN,N symmetrisch mit Eigenwerten λ1 ≥ λ2 ≥ ·· · ≥ λN .
λn = maxdimS=n
min0N 6=x∈S
r(A,x) ,
λN+1−n = mindimS=n
max0N 6=x∈S
r(A,x) .
Beweis. Es sei VAV T = diag(λ1, . . . ,λN) mit V = (v1| . . . |vN) orthogonal. Dann gilt
A =N
∑n=1
λnvn(vn)T .
“≤”: Setze Sn := spanv1, . . . ,vn. Dann gilt für x ∈ Sn:
xT Ax =N
∑k=1
λk(xT vk)2 =n
∑k=1
λk(xT vk)2 ≥ λn
n
∑k=1
(xT vk)2 = λnxT x.
Damit folgt r(A,x) = xT AxxT x ≥ λn und somit
λn = r(A,vn) = minx∈Snx 6=0N
r(A,x)≤ maxdimS=n
minx∈S
x 6=0N
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. Also gilt
λn ≥ r(A,y)≥ minx∈S
x 6=0N
r(A,x).
Da S beliebig war, folgt die Behauptung.
32
4 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]xn = bm.
Wir formen um und erhalten für xm:
A[m,m]xm = bm− ∑n6=m
A[m,n]xn.
Falls A[m,m] 6= 0 erhalten wir also
xm =
(bm− ∑
n6=mA[m,n]xn
)/A[m,m].
Daraus können wir das Gesamtschritt-Verfahren (Jacobi-Verfahren) ableiten:
S0) Wähle x0 ∈ RN , ε > 0, setze k = 0.
S1) Falls |Ax−b|2 < ε STOP.
S2) Berechne xk+1m = (bm− ∑
n 6=mA[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 |Ax−b|2 < ε STOP.
S2) Berechne xk+1m =
(bm−
m−1∑
n=1A[m,n]xk+1
n −N∑
k=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 untersuchen zu können, schreiben wir sie inMatrixform. Dazu beachten wir, dass für invertierbare Matrizen B ∈ RN,N die AufgabeAx = b äquivalent ist zu BAx = Bb. Ein solches B nennen wir Vorkonditionierer von A, daB möglichst so gewählt wird, dass BA eine kleinere Kondition als A hat. Wir formulierendies um in eine Fixpunktaufgabe, also x = Bb−BAx+ x und erhalten so
x = (I−BA)x+Bb = x+B(b−Ax) .
33
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− (L+D+R)xk +(L+D)xk folgt und somit
xk+1 = xk +(D+L)−1 (b−Axk),
also BGS = (D+L)−1.
(4.1) SatzSeien A,B ∈ RN,N mit ρ(I−BA) < 1. Dann ist A invertierbar und für alle x0 ∈ RN kon-vergiert die Iteration
xk+1 = xk +B(b−Axk) k = 0,1,2, . . . ,
sodass giltlimk→∞
xk = A−1b.
Beweis. Wir verwenden hier das Resultat aus dem nachfolgenden Satz (4.2): Zu einerMatrix K = IN−BA mit ρ(K) < 1 existiert eine Vectornorm | · |, so dass für die zugeordneteMatrixnorm ‖K‖ < 1 gilt. Also folgt aus ‖IN −BA‖ < 1, dass A invertierbar ist und die
Inverse mit der Neumannschen Reihe A−1 =∞
∑k=0
(IN−BA)kB darstellbar ist. Für x = A−1b
gilt dann
xk+1− x = xk +B(b−Axk)− x = xk− x+B(Ax−Axk) = (IN−BA)︸ ︷︷ ︸=K
(xk− x).
Und somit
|xk+1− x| ≤ ‖IN−BA‖|xk− x| ≤ ‖IN−BA‖k+1|x0− x| −→ 0 (k→ ∞).
34
(4.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 . . .
.
Somit folgt‖D−1RD‖∞ ≤ δ‖R‖∞ = ε− εδ = ε (1−δ )︸ ︷︷ ︸
∈[0,1)
< ε . (4)
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‖∞
(4)≤ ρ(K)+ ε.
(4.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.
Weiter giltA+D = L+D+D+LT = B−1 +B−T ,
35
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 A und BT DB positiv definit sind, existieren c1,c2 > 0 mit xT Ax > c1xT x und yT BT DBy >cyT y, also
|Kx|2A = |x|2A− xT ABT DBAx≤ |x|2A− c2 xT A2x≤ |x|2A− c1c2 |x|2A
und somit
‖K‖A = supx 6=0N
|Kx|A|x|A
= sup|x|A=1
|Kx|A = max|x|A=1
|Kx|A ≤ 1− c1c2 < 1 .
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.
Insbesondere gilt
r0− rk = r0− (IN−AB)kr0 = (IN− (IN−AB)k)r0
= −k
∑j=1
(kj
)(−AB) jr0.
Da nun aber r0− rk = b−Ax0− (b−Axk) ist, folgt
xk = x0 +k−1
∑j=0
(kj
)(−BA) jBr0 ∈ x0 +Vk.
Dabei definieren wir den Krylov-Raum Vk zu BA, Br0 und k durch
Vk := spanBr0,BABr0, . . . ,(BA)k−1Br0= P(BA)Br0 : P ∈ Pk−1.
Auf folgender Idee basieren die Krylovraum-Verfahren:
(1) Wähle ein geeignetes Skalarprodukt in V = RN mit zugehöriger Norm.
(2) Konstruiere eine Orthonormalbasis v1, . . . ,vk von Vk.
(3) Approximiere x = A−1b mit minimalem Fehler (bzw. minimalem Residuum) in x0 +Vk.
36
Gram-Schmidt-Verfahren
Wir suchen eine Orthonormalbasis des oben definierten Krylov-Raums. Dazu bietet sichzunächst das Gram-Schmidt-Verfahren an. Die ersten zwei Schritte der Krylovraum-Ver-fahren lauten also
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−k
∑j=1
h jkv j mit h jk = (v j)T wk
vk+1 =1
hk+1,kzk+1 mit hk+1,k = |zk+1|2.
Dann ist v1, ...,vk eine Orthonormalbasis des Krylovraums
Vk = spanBr0,BABr0, ...,(BA)k−1Br0= Qky : y ∈ Rk ,
wobei Qk =(v1|....|vk) . Wir schreiben BAvk =
k+1∑j=1
h jkv j, also
BAQk = Qk+1Hk
mit Hk = (h jm) ∈ Rk+1,k. Beachte, dass Hk obere Hessenbergform hat.
GMRES-Verfahren
Für das GMRES-Verfahren (generalized minimal residuum) wähle 〈v,w〉V = vT w. Somitgilt QT
k Qk = IN . Dieses Verfahren baut auf folgender Beobachtung auf:
(4.4) SatzEs gilt
minz∈x0+Vk
|B(b−Az)|2 = minyk∈Rk
|Hkyk−h10e1|2.
Beweis. Es gilt mit Vk = Qkyk : yk ∈ Rk:
|B(b−A(x0 +Qkyk))|2 = |Br0−BAQkyk|2= |h10v1−Qk+1Hkyk|2= |h10QT
k+1v1−Hkyk|2 = |h10e1−Hkyk|2.
Demnach lauten die nächsten Schritte im GMRES-Verfahren:
37
S2) Berechne yk ∈ Rk mitρk = |Hkyk−h10e1|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) Falls A(x0 +Qkyk) 6= b ist, gilt hk+1,k 6= 0. Ist A regulär, so hat Hk vollen Rang, d.h. yk
in S2) ist eindeutig.
(2) Die Orthogonalisierung ist anfällig für Rundungsfehler! Das sorgt gerade bei großerDimension des Krylovraums für numerische Probleme. Daher wird in der Regel dieDimension des Krylovraums beschränkt, d.h. das GMRES wird mehrfach hintereinan-der mit einer festen Zahl von Schritten aufgerufen.
Das cg-Verfahren
Seien A,B symmetrisch und positiv definit und wähle als Skalarprodukt das Energieska-larprodukt 〈v,w〉V = 〈v,w〉A = vT Aw mit zugeordneter Energienorm |v|A =
√〈v,v〉A. Das
Gram-Schmidt-Verfahren bezüglich 〈·, ·〉A ergibt A−orthonormale Vektoren v1, ...,vk, d.h.es gilt QT
k AQk = Ik. Für den Anfangsfehler gilt
〈x− x0,vi〉A = (Ax−Ax0)T vi = (r0)T vi,
und damit
xk = x0 +k
∑j=1
((r0)T v j)v j.
(4.5) SatzFür
xk = x0 +Qk(QTk r0) = x0 +
k
∑j=1
((r0)T v j)v j = xk−1 +((r0)T vk)vk
gilt|xk− x|A = min
yk∈Rk|(x0 +Qkyk)− x|A = min
z∈x0+Vk
|z− x|A.
Beweis. Es gilt
|x0 +Qkyk− x|2A = (x0− x+Qkyk)T A(x0− x+Qkyk)= (x0− x+Qkyk)T (−r0 +AQkyk)= −(x0− x)T r0−2yT
k QTk r0 + yT
k yk = min!
38
genau dann, wenn
−2QTk r0 +2yk = 0.
Somit folgt
yk = QTk r0.
BemerkungEs ist für alle i = 1, . . . ,k
(rk)T vi = 〈xk− x,vi〉A
= 〈x0− x,vi〉A +k
∑j=1
((r0)T v j)〈v j,vi〉A
= (−r0)T vi +(r0)T vi = 0.
Also haben wir für i = 1, . . . ,k−1
〈Brk,vi〉A = (ABrk)T vi = 0,
was bedeutet, dass Brk ∈ spanvk+1,vk gilt, da Brk nach Definition schon in Vk+1 liegt.Wir definieren
dk+1 := 〈Brk,vk+1〉Avk+1.
Damit ist d0 = Br0 unddk+1 = Brk−βkdk,
wobei βk := 〈Brk,dk〉A〈dk,dk〉A
. Ferner ist
xk = xk−1 +αkdk
mit αk = (r0)T dk
〈dk,dk〉A. Es gilt
(r0)T dk+1 = 〈x− x0,dk+1〉A = 〈x− xk,dk+1〉A= (rk)T dk+1 = (rk)T Brk.
Also haben wir
αk+1 =(rk)T Brk
(dk+1)T Adk+1
und
−αk〈Brk,dk〉A = (Brk)T (−αkAdk)= (Brk)T (rk− rk−1) = (rk)T Brk,
woraus folgt
βk =− (rk)T Brk
(rk−1)T Brk−1 .
39
Also ist das cg-Verfahren gegeben durch:
S0) Wähle x0 ∈RN , ε > 0. Berechne r0 = b−Ax0, w0 = Br0, ρ0 = (w0)T r0 und d1 = w0.
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
wk = Brk
ρk = (wk)T rk
dk+1 = wk +ρk
ρk−1dk.
Gehe zu S1).
(4.6) SatzFür das cg-Verfahren gilt die Fehlerabschätzung
|xk− x|A ≤ 2
(√κ(BA)−1√κ(BA)+1
)k
|x0− x|A.
Beweis. Es gilt
|xk− x|A = minz∈x0+Vk
|z− xk|A
= minP∈Pk−1
|(IN−P(BA))BA)(x− x0)|A
= minP∈Pk,P(0)=1
|P(BA)(x− x0)|A
≤ minP∈Pk,P(0)=1
‖P(BA)‖A|x− x0|A
mit
‖P(BA)‖A(∗)= ‖A
12 P(BA)A−
12‖2 = ‖P(A
12 BA
12︸ ︷︷ ︸
sym.
)‖2 = maxt∈σ(A
12 BA
12 )
|P(t)|2 .
Dabei wurde die Gleichung (∗) auf Übungsblatt 8 in Aufgabe 33d) bewiesen. Weiter giltσ(A
12 BA
12 ) = σ(BA)⊆ [a,b], κ(BA) = b
a und somit
minP∈Pk,P(0)=1
maxt∈[a,b]
|P(t)|2(∗∗)≤ 2
√
ba −1√ba +1
k
,
Ungleichung (∗∗) wurde bewiesen auf Übungsblatt 8 in Aufgabe 34d).
40
5 Iterationsverfahren für nichtlineare Gleichungen
Wir untersuchen in diesem Kapitel das Newton-Verfahren. Sei dazu F : D→ RN stetigdifferenzierbar für eine offene Menge D ⊂ RN . Ferner sei x∗ ∈ D mit F(x∗) = 0N . Dannexistiert ein δ > 0 mit B(x∗,δ )⊂ D und
0N = F(x∗) = F(x)+F ′(x) · (x∗− x)+o(|x∗− x|) , x ∈ B(x∗,δ ) .
Also gilt 0N ≈ F(x)+F ′(x) · (x∗− x), und falls F ′(x) regulär ist:
x∗ ≈ x−F ′(x)−1F(x).
Insbesondere ist x∗ ein Fixpunkt von
φ(x) := x−F ′(x)−1F(x).
Das entsprechende Fixpunkt-Verfahren ist die Newton-Iteration
xk+1 = φ(xk) .
Newton-VerfahrenS0) Wähle den Startwert x0 ∈ D und die Fehlertoleranz ε . Setze k := 0.
S1) Falls |F(x0)|< ε: STOP.
S2) Berechne die Newton-Korrektur dk: Löse
F ′(xk)dk =−F(xk).
S4) Setze
xk+1 := xk +dk,
und k := k +1. Gehe dann zu S1).
Zunächst untersuchen wir den Fall, dass F ′(x)−1 durch eine feste Matrix B ∈RN,N appro-ximiert wird. Im Schritt S2) wird dann das LGS Bdk =−F(xk) gelöst.
(5.1) SatzSei D⊂ RN offen, F ∈C1(D,RN) und x∗ ∈ D mit F(x∗) = 0N .Falls ein B ∈ RN,N mit
ρ(I−BF ′(x∗)
)< 1
existiert, dann ist die Fixpunktiteration
xk+1 = φ(xk)
mit
φ(x) = x−BF(x)
lokal linear konvergent, d.h. es existiert ein δ > 0, C > 0 und θ ∈ (0,1) mit
|xk− x∗| ≤Cθk |x∗− x0|
für alle x0 ∈ B(x∗,δ ).
41
Beweis. Mit (4.2) folgt die Existenz einer Norm ‖ · ‖ und eines ε > 0, sodass
‖IN−BF ′(x∗)‖ ≤ 1− ε
gilt. Weiterhin existiert ein δ > 0 mit B(x∗,δ )⊂ D und
‖BF ′(x)−BF ′(x∗)‖<ε
2
für alle x ∈ B(x∗,δ ), da F ′ stetig ist.Wir zeigen nun in zwei Schritten, dass φ(y),φ(z) ∈ B(x∗,δ ) für alle y,z ∈ B(x∗,δ ), unddass
|φ(y)−φ(z)| ≤ θ |y− z| , y,z ∈ B(x∗,δ ) ,
für θ = 1− ε/2 ∈ (0,1) erfüllt ist. Denn dann folgt aus dem Banach’schen Fixpunktsatz,dass die Folge (xk)k∈N konvergiert und dass für alle k ∈ N gilt
|xk− x∗| ≤ θ k
1−θ|x0− x∗|.
(i) Im ersten Schritt zeigen wir
F(y)−F(z) =∫ 1
0F ′(z+ t(y− z))(y− z)dt
für alle y,z∈ B(x∗,δ )⊂D. Dazu definiere ψ(t) := z+ t(y−z) und ϕ(t) := F(ψ(t)). Danngilt
ϕ′(t) = F ′(ψ(t))ψ ′(t) = F ′(z+ t(y− z))(y− z)
und damit
F(y)−F(z) = ϕ(1)−ϕ(0) =∫ 1
0ϕ′(t)dt =
∫ 1
0F ′(z+ t(y− z))(y− z)dt.
(ii) Als nächstes zeigen wir, dass φ kontrahierend ist. Es gilt für y,z ∈ B(x∗,δ )
φ(y)−φ(z) = y− z−B(F(y)−F(z)) = y− z−B∫ 1
0F ′(z+ t(y− z))(y− z)dt
= y− z−BF ′(x∗)(y− z)−B∫ 1
0
[F ′(z+ t(y− z))−F ′(x∗)
](y− z)dt.
Daraus folgt
|φ(y)−φ(z)| ≤ ‖IN−BF ′(x∗)‖|y− z|+∫ 1
0‖BF ′(z+ t(y− z))−BF ′(x∗)‖|y− z|dt
≤ (1− ε)|y− z|+ ε
2|y− z|
=(
1− ε
2
)|y− z|.
Insbesondere gilt
|φ(y)− x∗|= |φ(y)−φ(x∗)| ≤(
1− ε
2
)|y− x∗|︸ ︷︷ ︸≤δ
,
also φ(y) ∈ B(x∗,δ ).
42
(5.2) SatzSei α,β ,γ > 0 mit 2αγ ≤ β 2.Betrachte das Newton-Verfahren angewendet auf das Polynom
P(t) := α−β t +γ
2t2 .
tk+1 = tk−P′(tk)−1P(tk),
für den Startwert t0 = 0. Diese Iteration konvergiert monoton gegen die Nullstelle
t∗ =β
γ−
√(β
γ
)2
− 2α
γ=
2α
β +√
β 2−2αγ.
Ferner gilt für k ∈ N
0 = t0 < t1 <α
β< t2 < · · ·< tk < tk+1 +
γ
2tk− tk−1
β − γtk< t∗.
Beweis. Übungen.
(5.3) Satz (Newton-Kantorovich)Sei D ⊂ RN offen, F : D→ RN stetig differenzierbar und x0 ∈ D. Gelten für α,β ,γ ∈ Rmit 2αγ < β 2 die Bedingungen
a) |F(x0)| ≤ α ,b) |F ′(x0)y| ≥ β |y| für alle y ∈ RN ,c) B := B(x0, 2α
β)⊂ D,
d) ‖F ′(y)−F ′(z)‖ ≤ γ|y− z| für alle y,z ∈ B,dann ist das Newton-Verfahren wohldefiniert und konvergiert quadratisch gegen eine Null-stelle x∗ ∈ D von F mit
|x∗− x0| ≤ 2α
β +√
β 2−2αγ.
Beweis. (i) Zeige zuerst
|F(y)−F(z)−F ′(z)(y− z)| ≤ γ
2|y− z|2.
Es gilt wie im Beweis von (5.1)
F(y)−F(z)−F ′(z)(y− z) =∫ 1
0F ′(z+ t(y− z))(y− z)dt−
∫ 1
0F ′(z)(y− z)dt
und damit
|F(y)−F(z)−F ′(z)(y− z)| ≤∫ 1
0‖F ′(z+ t(y− z))−F ′(z)‖|y− z|dt
d)≤
∫ 1
0γ|t(y− z)||y− z|dt =
12
γ|y− z|2.
43
(ii) Nun wählen wir P und tk wie im vorherigen Satz (5.2) und zeigen induktiv für k≥ 1:
e) |F ′(xk−1)y| ≥ (β − γtk−1)|y| für alle y ∈ RN ,f) |xk− xk−1| ≤ tk− tk−1.
k = 1: in diesem Fall folgt e) aus b), da t0 = 0. Außerdem gilt f), denn
|x1− x0|b)≤ 1
β|F ′(x0)(x1− x0)︸ ︷︷ ︸
=F(x0)
|= 1β|F(x0)|
a)≤ α
β= t1− t0.
k→ k +1: Es gilt
(β − γtk−1)|y|e)≤ |F ′(xk−1)y|= |(F ′(xk−1)−F ′(xk)+F ′(xk))y|≤ ‖F ′(xk−1)−F ′(xk)‖d)≤ γ|xk−1− xk|
f )≤ γ|tk− tk−1|.
Damit liefert y = xk+1− xk in e)
|xk+1− xk|e)≤ 1
β − γtk|F ′(xk)(xk+1− xk)|
=1
β − γtk|F(xk)−F(xk−1)−F ′(xk−1)(xk− xk−1)︸ ︷︷ ︸
=0N
|
(i)≤ 1
β − γtk
γ
2|xk− xk−1|2
f )≤ 1
β − γtk
γ
2(tk− tk−1)2 = tk+1− tk.
(iii) Zeige nun: (xk)k∈N ist eine Cauchy-Folge bzgl. | · |. Es gilt
|xk+ j− xk| ≤k+ j
∑i=k+1
|xi− xi−1|f )≤
k+ j
∑i=k+1
(ti− ti−1) = |tk+ j− t j|.
Da (tk)k∈N eine Cauchy-Folge ist, gilt dies somit auch für (xk)k∈N.Insbesondere gilt |x j− x0| ≤ t j− t0 = t j ≤ t∗ < 2α/β , also x j ∈ B.Also existiert ein x∗ ∈ B, sodass limk→∞ xk = x∗ mit x∗ = x0 +∑
∞k=1(x
k− xk−1) gilt.Damit folgt schließlich
|x∗− x0| ≤∞
∑k=1|xk− xk−1|
f )≤
∞
∑k=1
(tk− tk−1) = t∗ =2α
β +√
β 2−2αγ.
44
BemerkungIm Allgemeinen konvergiert das Newton-Verfahren nur lokal! Wir können diese Konver-genz dadurch etwas verbessern, dass wir die Newtonkorrekturen dk dämpfen.
Newton-Verfahren mit DämpfungS0) Wähle den Startwert x0 ∈D, den Dämpfungsparameter θ ∈ (0,1) und die Fehlerto-
leranz ε . Setze k := 0.
S1) Falls |F(x0)|< ε: STOP.
S2) Löse das Gleichungssystem
F ′(xk)dk =−F(xk).
Breche ab, falls F ′(xk) singulär ist und starte mit anderem x0.
S3) Bestimme ein tk ∈ 1,θ ,θ 2, . . . ,θ r mit |F(xk + tkdk)| minimal.
S4) Setze
xk+1 := xk + tkdk,
und k := k +1. Gehe dann zu S1).
Globale Konvergenz erfordert häufig weitere Strategien, z.B. Homotopie-Verfahren.
45
6 Interpolation und Approximation
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?
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.
46
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)
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 .
47
Polynominterpolation(6.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 .
(6.2) SatzDie Interpolationsaufgabe von Lagrange (6.1) ist eindeutig lösbar.
Beweis.
(1) Eindeutigkeit:Seien P, P zwei Lösungen der Aufgabe (6.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] ∈ 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 ]∈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 dieLagrange 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
.
48
Also ist
P(t) :=N
∑k=0
fkLk(t)
Lösung der Interpolationsaufgabe (6.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!
(6.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).
(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 .
49
(6.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.
(6.5) SatzDie Hermitesche Interpolationsaufgabe (6.3) ist eindeutig lösbar.
Beweis. Definiere die Linearform µn : Cd[a,b]−→ R mit
µn( f ) =(
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 (6.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. Dazu genügt zu zeigen, dass aus Ab = 0N+1 schon b = 0N+1 folgt.Aus Ab = 0N+1 folgt µn(P) = 0 für n = 0, . . . ,N, wobei P ∈ PN wie oben definiert ist.Folglich hat P mindestens N + 1 Nullstellen (mit Vielfachheiten). Und somit gilt P ≡ 0.Dies liefert wiederum b = 0N+1 und damit die Regularität von A.
(6.6) DefinitionDer eindeutig bestimmte höchste Koeffizient
bN =1
N!
(ddt
)N
P(t)
der Hermiteschen Interpolationsaufgabe (6.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].
50
2) Falls t0, . . . , tN nicht sortiert sind, dann definiere f [t0, . . . , tN ] = f [tk0 , . . . , tkN ] mit derSortierung tk0 ≤ ·· · ≤ tkN .
(6.7) Satza) Das Polynom
PN(t) :=N
∑k=0
f [t0, . . . , tk]ωk(t)
löst die Interpolationsaufgabe (6.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)− 1N!
(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 (6.3) für t0, . . . , tN−1 und nach Induktionsvoraussetzung gilt
PN−1(t) =N−1
∑k=0
f [t0, . . . , tk]ωk(t).
Zu b) Für festes t definiere das Polynom Qt ∈ PN+1 mit
Qt(s) = PN(t)+ 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).
(6.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].
51
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 (6.7) die Behauptung folgt.
Anwendung von (6.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)| ≤N
∏n=0
nh≤ N! hN+1 .
BemerkungIm Allgemeinen ist
( ddt
)kf (t) unbeschränkt, wenn k immer größer wird.
52
Zur Auswertung der Interpolation verwenden wir die folgenden Rekursionen.
(6.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) Setze d := n− k und sei P0 ∈ Pd−1 die Interpolation zu f an tk, . . . , tn−1,d.h.
f [tk, . . . , tn−1] =1
(d−1)!
(ddt
)d−1
P0(t)
und P1 ∈ Pd−1 die Interpolation zu f an tk+1, . . . , tn, d.h.
f [tk+1, . . . , tn] =1
(d−1)!
(ddt
)d−1
P1(t) .
Dann definiereP(t) :=
1tn− tk
((t− tk)P1(t)+(tn− t)P0(t)). (5)
Somit gelten
P(tn) = P1(tn) = f (tn) und P(tk) = P0(tk) = f (tk)
und für k < i < n gilt
P(ti) =1
tn− tk( f (ti)(ti− tk)+ f (ti)(tn− ti)) = f (ti).
Außerdem folgt
P′(t) =1
tn− tk
(P1(t)−P0(t)+(t− tk)P′1(t)+(tn− t)P′0(t)
),
53
und damit P′(ti) = 1tn−tk
((ti− tk)P′1(ti)+(tn− ti)P′0(ti)
). Daraus lässt sich ablesen, dass P
auch für doppelte Stützstellen die Interpolationseigenschaft erfüllt (analog für weitere Ab-leitungen). Also ist P ∈ Pd Interpolation zu f an tk, . . . , tn. Mittels Koeffizientenvergleichsvon
( ddt
)dP folgt dann die Behauptung:
f [tk, . . . , tn] =1d!
(ddt
)d
P(t)
=1d!
1tn− tk
(ddt
)d (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).
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.
54
Mit Gleichung (5) 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.
55
Algorithmus 8 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
56
Splines(6.10) 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 .
(6.11) SatzEs gilt dimSk(∆) = N + k.
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).
57
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.
(6.12) 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
.
(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
.
(6.13) 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 .
(6.14) 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
58
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.
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.
59
(6.15) 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 ,
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. Nun hat S− S aber N + 1 Nullstellen, also folgt mit k ≤ N, dassS− S≡ 0 ist.
Nun untersuchen wir, wie man für ein gegebenes Interpolationsproblem den zugehörigenkubischen Spline (k = 3) berechnen kann.
(6.16) 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 = hn2(hn+hn+1)
, λn = hn+12(hn+hn+1)
, hn = tn− tn−1.
BemerkungIm Fall hn := h und tn := a+nh gilt µn = λn = 1
4 , µ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
− h2n
12(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 .
60
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:
(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öse
1 λ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 = 12 . 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öse
1 λ1 µ1µ2 1 λ2
. . . . . . . . .µN−1 1 λN−1
λN µN 1
M1......
MN
= 3 ·
f [t0, t1, t2]
...
...f [tN−1, tN , t1]
mit λN = h12(hN+h1)
, µN = hN2(hN+h1)
.
(6.17) SatzEs gilt für m = 0, . . . ,r und h = maxi=n,...,N hi, 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
61
λ 1n ∈ (λ 0
n−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
und wir erhalten∫ b
a
∣∣∣∣( ddt
)m
u(t)∣∣∣∣2 dt =
N+1−m
∑n=1
∫λ m
n
λ mn−1
∣∣∣∣( ddt
)m
u(t)∣∣∣∣2 dt,
≤ 12(m+1)2h2
∫ b
a
∣∣∣∣∣(
ddt
)n+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) gilt |S− f |0 ≤C h2 | f |2.
62
Orthogonalpolynome
Sei W ∈C(a,b) ein Gewicht mit W > 0 auf (a,b). Definiere dazu das Skalarprodukt
〈u,v〉W :=∫ b
aW (t)u(t)v(t)dt
und die Norm
‖u‖W :=√〈u,v〉w.
(6.18) AufgabeZu f ∈C(a,b) bestimme P ∈ PN mit
‖P− f‖W = minQ∈PN
‖Q− f‖W . (6)
BeispielFolgende Gewichte und Intervalle werden häufig verwendet:
(a,b) W (t)Legendre (−1,1) 1
Tschebyscheff (−1,1)1√
1− t2
Jacobi (−1,1) (1− t)r(1+ t)s
Laguerre (0,∞) e−t
Hermite (−∞,∞) e−12 t2
(6.19) SatzSei Q0,Q1, . . . ,QN eine ONB von PN bezüglich 〈·, ·〉W . Dann löst
P(t) =N
∑n=0〈Qn, f 〉W Qn(t)
die Aufgabe (6.18)
Beweis. Nach Satz (1.3) gilt
P =N
∑n=0
xnQn
mit der Lösung x ∈ RN+1 des linearen Gleichungssystems Ax = b, wobei
A = (〈Qk,Qn〉W )k,n=0,...,N = IN+1
und b = (〈Qn, f 〉W ) = x ∈ RN+1 ist.
BemerkungFür das Gewicht W ≡ 1 auf (a,b) = (0,1) und die Basis 1, t, t2, . . . , tN von PN gilt, dass
A = (〈tk, tn〉W )k,n=0,...,N =(
11+ k +n
)k,n=0...,N
die Hilbertmatrix ist, die sehr schlecht konditioniert ist!
63
Berechnung einer Orthonormalbasis mit dem Gram-Schmidt-VerfahrenEs seien
R0 ≡ const,
Q0 ≡1
‖R0‖W.
Dann berechne für n = 0,1, . . .
ank = 〈tRn,Qk〉w, k = 0, . . . ,n,
Rn+1 = tRn−n
∑k=0
ankQk,
ρn+1 = ‖Rn+1‖W ,
Qn+1 =1
ρn+1Rn+1.
Dann gilt nach Konstruktion 〈Rn+1,Qn〉W = 0 für k = 0, . . . ,n.
Es bleibt zu zeigen, dass degRn = n und dass dieser Algorithmus wohldefiniert ist, alsoρn = ‖Rn‖W > 0.
(6.20) SatzSetze
R−1 :≡ 0, R0 :≡ ρ0
‖1‖W
mit ρ0 > 0. Ferner sei ρ−1 := 1. Dann gilt für n≥ 1 die Drei-Term-Rekursion
Rn+1(t) = (t−βn) Rn(t)− γn Rn−1(t) ∈ Pn+1
wobei
βn =〈tRn,Rn〉W
ρ2n
und γn =ρ2
n
ρ2n−1
> 0 .
Beweis. Wir führen eine Induktion über n.Für alle n gilt Rn = ρnQn und ρnβn = ann = 〈tRn,Qn〉W = (1/ρn)〈tRn,Rn〉W .n = 0: Per Konstruktion gilt R1(t) = tR0−a00Q0 = tR0−β0ρ0Q0 = tR0−β0R0.n−1→ n: Als Induktionsvoraussetzung gelte
∀ P ∈ Pn−1 : 〈Rn,P〉W = 0 .
Für k < n−1 gilt tRk ∈ Pk+1 ⊂ Pn−1 und somit
ρkank = 〈tRn,ρkQk〉W = 〈tRn,Rk〉W = 〈Rn, tRk〉W = 0 .
Daraus folgt
Rn+1 = tRn−ann
ρn︸︷︷︸=βn
Rn−an,n−1
ρn−1︸ ︷︷ ︸=γn
Rn−1 ,
64
und aus Rn 6≡ 0 folgt
ρ2n−1γn = ρn−1an,n−1 = 〈tRn,Rn−1〉W = 〈Rn, tRn−1〉W
IV= 〈Rn,Rn +βn−1Rn−1 + γn−1Rn−1〉W= 〈Rn,Rn〉W = ρ
2n > 0 .
BemerkungEs gilt
Rn(t) = tnρ0 + · · · .
BemerkungDie Nullstellen von Rn sind die Eigenwerte der Tridiagonalmatrix
β0√
γ1√γ1 β1
√γ2√
γ2 β2√
γ3. . . . . . . . .
. . . . . .
,
da diese Matrix gerade das charakteristische Polynom Rn besitzt.
(6.21) SatzDas Orthogonalpolynom Rn besitzt n verschiedene Nullstellen in (a,b).
Beweis. Seien a < λ1 < · · ·< λk < b alle Nullstellen von Rn, an denen Rn das Vorzeichenwechselt. Dann definiere
Pk(t) :=±k
∏j=1
(t−λ j) ∈ Pk
und ohne Einschränkung gelte Rn(t)P(t)≥ 0. Es ist Rn(t) = Pk(t) = 0 für t = λ j. Dann gilt
〈Pk,Rn〉W =∫ b
aW (t)︸︷︷︸
>0
Pk(t)Rn (t)︸ ︷︷ ︸≥0
dt > 0 .
Angenommen k < n, dann ist Pk ∈ Pn−1, also 〈Pk,Rn〉W = 0, was ein Widerspruch ist.
Beispiel (Legendre-Polynome)Definiere für t ∈ (−1,1) die Legendre-Polynome durch
Ln(t) :=1
2nn!
(ddt
)n
(t2−1)n ∈ Pn .
Es gilt
L−1 ≡ 0, L0 ≡ 1,
65
und die Rekursion
(n+1)Ln+1(t) = (2n+1)tLn(t)−nLn−1(t).
Ferner gilt
∫ 1
−1
(ddt
)n
(t2−1)n(
ddt
)k
(t2−1)kdt
= (−1)n∫ 1
−1(t2−1)n
(ddt
)n+k
(t2−1)k︸ ︷︷ ︸=0, da n>k
dt = 0
Außerdem gilt, dass Ln die Differentialgleichung
− ddt
((1− t)2 d
dtLn(t)
)= λnLn(t)
löst, wobei λn = n(n+1) ist.
Beispiel (Tschebyscheff-Polynome)Definiere für t ∈ (−1,1) die Tschebyscheff-Polynome durch
Tn(t) := cos(narccos(t)) .
Es gilt
T−1 ≡ 0, T0 ≡ 1, T1(t) = t,
und die Rekursion
Tn+1(t) = 2tTn(t)−Tn−1(t) ∈ Pn+1.
Ferner gilt für n 6= k∫ 1
−1
1√1− t2
Tn(t)Tk(t)dtt=cos(x)
=∫
π/2
−π/2cos(nx)cos(kx)dx = 0 .
66
7 Numerische Integration
(7.1) DefinitionSei Ξ ⊆ [a,b]⊂R eine endliche Menge von Stützstellen ξ ∈Ξ und seien wξ ∈R für ξ ∈Ξ
die Quadraturgewichte. Dann heißt
IΞ : C[a,b]→ R, IΞ ( f ) = ∑ξ∈Ξ
wξ 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
∀ P ∈ Pp : EΞ (P) = 0.
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 Fehlers betrachten wir den linearen Spline S f ∈ S1(Ξ) mit S 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
EΞ ( f )≤ (b−a)‖ f −S f ‖∞ ≤b−a
8h2‖ f ′′‖∞ .
Dabei ist ‖ f‖∞ := maxt∈[a,b] | f (t)| die Supremumsnorm.
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.
(7.2) SatzSei |Ξ |= N +1 und IΞ sei exakt von der Ordnung p≥ N. Dann gilt
wξ =∫ b
aLξ (t)dt mit Lξ (t) = ∏
η∈Ξ\ξ
t−η
ξ −η∈ PN .
67
Beweis. Da p≥ N, gilt PN ⊆ Pp und somit EΞ (Lξ ) = 0. Damit folgt
∫ b
aLξ (t)dt = IΞ (Lξ ) = wξ Lξ (ξ ) = wξ .
(7.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 (7.2) gilt also für wn zu ξn
wn =∫ b
aLn(t)dt =
b−aN
∫ N
0Ln(a+ s
b−aN︸ ︷︷ ︸
=t
)ds =b−a
N
∫ N
0
N
∏k=0k 6=i
s− kn− k
ds
=b−a
N(−1)N−n
n!(N− k)!
∫ N
0
N
∏k=0k 6=i
(s− k)ds = wN−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 : w0 = w3 = b−a8 , w1 = w2 = 3(b−a)
8 Newton’sche38
-Regel
N = 4 : w0 = w4 = 7(b−a)90 , w1 = w3 = 32(b−a)
90 , w2 = 12(b−a)90 Milne-Regel
BemerkungFür N > 4 treten auch negative Gewichte auf. Dadurch besteht bei der Auswertung dieGefahr der Auslöschung, so dass diese Formeln numerisch ungünstig sind.
(7.4) LemmaDie Newton-Cotes-Formeln sind für gerade N exakt von der Ordnung N +1.
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
∫ 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
68
für gerade N.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.
(7.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.
(7.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).
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 (6.7)
f (t)−P(t) = f [t0, t1, t2, t3, t](t− t0)(t− t1)2(t− t3) ,
69
und da nach Lemma (7.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
(7.5)= f [t0, t1, t2, t3,τ]︸ ︷︷ ︸
= 14! f ′′′′(τ)
∫ b
a(t− t0)(t− t1)2(t3− t)dt︸ ︷︷ ︸
= 415( b−a
2 )5
=(
b−a2
)5 190
f (4)(τ).
(7.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) = ∑ξ∈Ξ
wξ 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.
(7.8) SatzEs existiert genau eine Quadraturformel GN mit N Stützstellen ξ1, . . . ,ξN , die exakt vomGrad 2N−1 ist. Die Stützstellen sind Nullstellen des Orthogonal polynoms RN bezüglichdes Skalarproduktes
(u,v) =∫ b
au(t)v(t)dt.
Wir nennen diese Quadraturformel Gauß-Quadratur.
Beweis. Sei GN eine Quadratur zu Nullstellen a < ξ1 < · · ·< ξN < b, die exakt vom GradN−1 ist. Zu P ∈ P2N−1 existieren P0,P1 ∈ PN−1 mit P = P1RN +P0 (Polynomdivision mitRest). Damit gilt∫ b
aP(t)dt = (P,1) = (P1RN +P0,1) = (P1,RN)︸ ︷︷ ︸
=0, da RN⊥PN−1
+∫ b
aP0(t)dt = GN(P0),
70
da P0 ∈ PN−1 ist. Ferner gilt RN(ξ ) = 0 für alle ξ ∈ Ξ , folglich
GN(P0) = ∑ξ∈Ξ
wξ P0(ξ ) = ∑ξ∈Ξ
wξ (P1(ξ )RN(ξ )+P0(ξ )) = GN(P1RN +P0)
= GN(P),
also gilt ∫ b
aP(t)dt = 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:
wηn = GN(Ln) = GN(L2n) =
∫ b
aLn(t)2dt > 0,
aber
0 = (RN ,Ln) =∫ b
aRN(t)Ln(t)︸ ︷︷ ︸∈P2N−1
dt = GN(RNLn) = wηnRN(ηn).
Also ist RN(ηn) = 0 für n = 1, ...,N.
(7.9) SatzSei f ∈C2N [a,b]. Für die Gauß-Quadratur GN gilt dann∫ b
af (t)dt−GN( f ) =
1(2N)!
(ddt
)2N
f (τ) (QN ,QN)
mit τ ∈ (a,b) und QN(t) = ∏Nn=1(t−ξn).
Beweis. Wähle zu f die Hermite-Interpolatierende P∈P2N−1 an den Stellen ξ1,ξ1, . . . ,ξN ,ξN .Aus Satz (6.7) folgt wiederum f (t)−P(t) = f [ξ1,ξ1, . . . ,ξN ,ξN , t]QN(t)2 und damit∫ b
af (t)dt−GN( f ) =
∫ b
af (t)dt−GN(P) =
∫ b
a( f (t)−P(t))dt
=∫ b
af [ξ1,ξ1, . . . ,ξN ,ξN , t]QN(t)2︸ ︷︷ ︸
≥0
dt
(7.5)= f [ξ1,ξ1, . . . ,ξN ,ξN ,τ]
∫ b
aQN(t)2dt
=1
(2N)!
(ddt
)2N
f (τ) (QN ,QN).
71
Anwendungen: KubaturSei Ω = 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, wn bezüglich dem Skalarprodukt (u,v) =∫ 1
0u(t)v(t)dt.
b) Wähle Gauß-Quadratur ξn, wn bezüglich dem Skalarprodukt∫ 1
0(1− t)u(t)v(t)dt
Definiere dann
GN( f ) :=N
∑n,k=1
wnwk f (ξn,(1−ξn)ξk).
72
Romberg-Quadratur
Die Romberg-Quadratur ist ein Extrapolationsverfahren, das aus der summierten Trapez-regel
Th( f ) := h
(12
f (a)+M−1
∑n=1
f (a+nh)+12
f (b)
), h =
b−aM
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.
(7.10) 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) .
73
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 +1
15(Tk,1−Tk−1,1).
Im Folgenden untersuchen wir, ob sich dieser Prozess fortsetzen lässt.
(7.11) 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.
74
(7.12) 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).
(7.13) 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.
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 ).
75
i = 0 ist die Folgerung (7.12) aus der Euler-MacLaurinsche Summenformel.i−1→ i:
(4i−1)Tki = 4iTk,i−1−Tk−1,i−1
(Ind.-Vor.)= 4i
(I +
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 ).
(7.14) 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 ) .
76
