Suchen und Finden
Service
Numerik-Algorithmen - Verfahren, Beispiele, Anwendungen
Gisela Engeln-Müllges, Klaus Niederdrenk, Reinhard Wodicka
Verlag Springer-Verlag, 2010
ISBN 9783642134739 , 756 Seiten
10. Auflage
Format PDF
Kopierschutz Wasserzeichen
Vorwort zur 10. korrigiertenund erweiterten Auflage
6
Informationen zu Quelltexten f¨ur diebeschriebenen Algorithmen
8
Bemerkungen zur vorliegenden C-Version
10
Weitere Software im Umfeld der Numerik-Bibliothek
11
Bezeichnungen
12
Inhaltsverzeichnis
14
Kapitel 1 Darstellung von Zahlen und Fehleranalyse,Kondition und Stabilit¨at
22
1.1 Definition von Fehlergr¨oßen
22
1.2 Zahlensysteme
24
1.2.1 Darstellung ganzer Zahlen
24
1.2.2 Darstellung reeller Zahlen
27
1.3 Rechnung mit endlicher Stellenzahl
32
1.4 Fehlerquellen
38
1.4.1 Eingabefehler
38
1.4.2 Verfahrensfehler
39
1.4.3 Fehlerfortpflanzung und die Kondition eines Problems
40
1.4.4 Rechnungsfehler und numerische Stabilit¨at
45
Kapitel 2 Numerische Verfahren zur L¨osungnichtlinearer Gleichungen
48
2.1 Aufgabenstellung und Motivation
48
2.2 Definitionen und S¨atze ¨uber Nullstellen
50
2.3 Allgemeines Iterationsverfahren
52
2.3.1 Konstruktionsmethode und Definition
52
2.3.2 Existenz einer L¨osung und Eindeutigkeit der L¨osung
55
2.3.3 Konvergenz eines Iterationsverfahrens
58
2.3.3.1 Heuristische Betrachtungen
58
2.3.3.2 Analytische Betrachtung
60
2.3.4 Fehlerabsch¨atzungen und Rechnungsfehler
61
2.3.5 Praktische Durchf¨uhrung
67
2.4 Konvergenzordnung eines Iterationsverfahrens
70
2.5 Newtonsche Verfahren
72
2.5.1 Das Newtonsche Verfahren f¨ur einfache Nullstellen
72
2.5.2 Ged¨ampftes Newton-Verfahren
78
2.5.3 Das Newtonsche Verfahren f¨ur mehrfache Nullstellen.Das modifizierte Newtonsche Verfahren
78
2.6 Das Sekantenverfahren
84
2.6.1 Das Sekantenverfahren f¨ur einfache Nullstellen
84
2.6.2 Das modifizierte Sekantenverfahrenf¨ur mehrfache Nullstellen
87
2.7 Einschlussverfahren
87
2.7.1 Das Prinzip der Einschlussverfahren
88
2.7.2 Das Bisektionsverfahren
90
2.7.3 Die Regula falsi
92
2.7.4 Das Pegasus-Verfahren
95
2.7.5 Das Verfahren von Anderson-Bj¨orck
98
2.7.6 Die Verfahren von King und Anderson-Bj¨orck-King.Das Illinois-Verfahren
101
2.7.7 Ein kombiniertes Einschlussverfahren
102
2.7.8 Das Zeroin-Verfahren
104
2.8 Anwendungsbeispiele
106
2.9 Effizienz der Verfahren und Entscheidungshilfen
110
Kapitel 3 Verfahren zur L¨osung algebraischerGleichungen
112
3.1 Vorbemerkungen
112
3.2 Das Horner-Schema
113
3.2.1 Das einfache Horner-Schema f¨ur reelle Argumentwerte
114
3.2.2 Das einfache Horner-Schema f¨ur komplexe Argumentwerte
116
3.2.3 Das vollst¨andige Horner-Schema f¨ur reelle Argumentwerte
118
3.2.4 Anwendungen
121
3.3 Methoden zur Bestimmung s¨amtlicherL¨osungen algebraischer Gleichungen
122
3.3.1 Vorbemerkungen und ¨Uberblick
122
3.3.2 Das Verfahren von Muller
123
3.3.3 Das Verfahren von Bauhuber
130
3.3.4 Das Verfahren von Jenkins und Traub
132
3.4 Anwendungsbeispiel
133
3.5 Entscheidungshilfen
134
Kapitel 4 Direkte Verfahrenzur L¨osung linearer Gleichungssysteme
135
4.1 Aufgabenstellung und Motivation
135
4.2 Definitionen und S¨atze
140
4.3 L¨osbarkeitsbedingungenf¨ur ein lineares Gleichungssystem
152
4.4 Prinzip der direkten Methodenzur L¨osung linearer Gleichungssysteme
153
4.5 Der Gauß-Algorithmus
156
4.5.1 Gauß-Algorithmus mit Spaltenpivotsucheals Rechenschema
156
4.5.2 Spaltenpivotsuche
161
4.5.3 Gauß-Algorithmus als Dreieckszerlegung
165
4.5.4 Gauß-Algorithmus f¨ur Systememit mehreren rechten Seiten
169
4.6 Matrizeninversion mit dem Gauß-Algorithmus
171
4.7 Verfahren f¨ur Systememit symmetrischen Matrizen
173
4.7.1 Systeme mit symmetrischer, streng regul¨arer Matrix
174
4.7.2 Systeme mit symmetrischer, positiv definiter Matrix.Cholesky-Verfahren
175
4.7.3 Systeme mit symmetrischer, positiv definiter Matrix.Verfahren der konjugierten Gradienten (CG-Verfahren)
180
4.8 Das Gauß-Jordan-Verfahren
184
4.9 Gleichungssysteme mit tridiagonaler Matrix
185
4.9.1 Systeme mit tridiagonaler Matrix
185
4.9.2 Systeme mit symmetrischer, tridiagonaler,positiv definiter Matrix
189
4.10 Gleichungssystememit zyklisch tridiagonaler Matrix
192
4.10.1 Systeme mit zyklisch tridiagonaler Matrix
192
4.10.2 Systeme mit symmetrischer, zyklisch tridiagonaler Matrix
195
4.11 Gleichungssysteme mit f¨unfdiagonaler Matrix
197
4.11.1 Systeme mit f¨unfdiagonaler Matrix
197
4.11.2 Systeme mit symmetrischer, f¨unfdiagonaler,positiv definiter Matrix
200
4.12 Gleichungssysteme mit Bandmatrix
203
4.13 L¨osung ¨uberbestimmter linearer Gleichungssystememit Householdertransformation
214
4.14 Fehler, Kondition und Nachiteration
219
4.14.1 Fehler und Kondition
219
4.14.2 Konditionssch¨atzung
223
4.14.3 M¨oglichkeiten zur Konditionsverbesserung
228
4.14.4 Nachiteration
228
4.15 Gleichungssysteme mit Blockmatrix
230
4.15.1 Vorbemerkungen
230
4.15.2 Gauß-Algorithmus f¨ur Blocksysteme
231
4.15.3 Gauß-Algorithmus f¨ur tridiagonale Blocksysteme
233
4.15.4 Weitere Block-Verfahren
234
4.16 Algorithmus von Cuthill-McKeef¨ur d¨unn besetzte, symmetrische Matrizen
235
4.17 Entscheidungshilfenf¨ur die Auswahl des Verfahrens
239
Kapitel 5 Iterationsverfahren zur L¨osunglinearer Gleichungssysteme
242
5.1 Vorbemerkungen
242
5.2 Vektor- und Matrizennormen
242
5.3 Das Iterationsverfahren in Gesamtschritten
244
5.4 Das Gauß-Seidelsche Iterationsverfahren,Iteration in Einzelschritten
253
5.5 Relaxation beim Gesamtschrittverfahren
255
5.6 Relaxation beim Einzelschrittverfahren.SOR-Verfahren
255
5.6.1 Sch¨atzung des Relaxationskoeffizienten.Adaptives SOR-Verfahren
256
Kapitel 6 Systeme nichtlinearer Gleichungen
259
6.1 Aufgabenstellung und Motivation
259
6.2 Allgemeines Iterationsverfahren f¨ur Systeme
262
6.3 Spezielle Iterationsverfahren
268
6.3.1 Newtonsche Verfahren f¨ur nichtlineare Systeme
268
6.3.1.1 Das quadratisch konvergente Newton-Verfahren
268
6.3.1.2 Ged¨ampftes Newton-Verfahren f¨ur Systeme
271
6.3.2 Sekantenverfahren f¨ur nichtlineare Systeme
272
6.3.3 Das Verfahren des st¨arksten Abstiegs(Gradientenverfahren) f¨ur nichtlineare Systeme
273
6.3.4 Das Verfahren von Brown f¨ur Systeme
275
6.4 Entscheidungshilfen f¨ur die Auswahl der Methode
276
Kapitel 7 Eigenwerte und Eigenvektoren von Matrizen
277
7.1 Definitionen und Aufgabenstellungen
277
7.2 Diagonal¨ahnliche Matrizen
278
7.3 Das Iterationsverfahren nach v. Mises
280
7.3.1 Bestimmung des betragsgr¨oßten Eigenwertesund des zugeh¨origen Eigenvektors
280
7.3.2 Bestimmung des betragskleinsten Eigenwertes
287
7.3.3 Bestimmung weiterer Eigenwerte und Eigenvektoren
287
7.4 Konvergenzverbesserung mit Hilfe des Rayleigh-Quotienten im Falle hermitescher Matrizen
289
7.5 Das Verfahren von Krylov
290
7.5.1 Bestimmung der Eigenwerte
290
7.6 Bestimmung der Eigenwerte positiv definiter,symmetrischer, tridiagonaler Matrizen mit Hilfedes QD-Algorithmus
293
7.7 Transformationen auf Hessenbergform,LR- und QR-Verfahren
294
7.7.1 Transformation einer Matrix auf obere Hessenbergform
294
7.7.2 LR - Verfahren
298
7.7.3 QR - Verfahren
300
7.8 Ermittlung der Eigenwerte und Eigenvektoreneiner Matrix nach den Verfahren von Martin,Parlett, Peters, Reinsch und Wilkinson
301
7.9 Entscheidungshilfen
302
7.10 Anwendungsbeispiel
303
Kapitel 8 Lineare und nichtlineare Approximation
308
8.1 Aufgabenstellung und Motivation
308
8.2 Lineare Approximation
311
8.2.1 Approximationsaufgabe und beste Approximation
311
8.2.2 Kontinuierliche lineare Approximationim quadratischen Mittel
313
8.2.3 Diskrete lineare Approximation im quadratischen Mittel
319
8.2.3.1 Normalgleichungen f¨ur den diskreten linearen Ausgleich
319
8.2.3.2 Diskreter Ausgleich durch algebraische Polynomeunter Verwendung orthogonaler Polynome
325
8.2.3.3 Lineare Regression. Ausgleich durch lineare algebraische Polynome
327
8.2.3.4 Householder-Transformationzur L¨osung des linearen Ausgleichsproblems
330
8.2.4 Approximation von Polynomendurch Tschebyscheff-Polynome
333
8.2.4.1 Beste gleichm¨aßige Approximation, Definition
333
8.2.4.2 Approximation durch Tschebyscheff-Polynome
334
8.2.5 Approximation periodischer Funktionen
340
8.2.5.1 Kontinuierliche Approximation periodischer Funktionenim quadratischen Mittel
341
8.2.5.2 Diskrete Approximation periodischer Funktionenim quadratischen Mittel
343
8.2.5.3 Fourier-Transformation und FFT
346
8.2.6 Fehlerabsch¨atzungen f¨ur lineare Approximationen
353
8.2.6.1 Gleichm¨aßige Approximation durch algebraische Polynome
354
8.2.6.2 Gleichm¨aßige Approximation durch trigonometrische Polynome
357
8.3 Diskrete nichtlineare Approximation
359
8.3.1 Transformationsmethode beim nichtlinearen Ausgleich
359
8.3.2 Nichtlinearer Ausgleich im quadratischen Mittel
365
8.4 Entscheidungshilfen
365
Kapitel 9 Polynomiale Interpolation sowieShepard-Interpolation
367
9.1 Aufgabenstellung
367
9.2 Interpolationsformeln von Lagrange
369
9.2.1 Lagrangesche Formel f¨ur beliebige St¨utzstellen
369
9.2.2 Lagrangesche Formel f¨ur ¨aquidistante St¨utzstellen
371
9.3 Aitken-Interpolationsschemaf¨ur beliebige St¨utzstellen
372
9.4 Inverse Interpolation nach Aitken
376
9.5 Interpolationsformeln von Newton
378
9.5.1 Newtonsche Formel f¨ur beliebige St¨utzstellen
378
9.5.2 Newtonsche Formel f¨ur ¨aquidistante St¨utzstellen
381
9.6 Absch¨atzung und Sch¨atzungdes Interpolationsfehlers
384
9.7 Zweidimensionale Interpolation
389
9.7.1 Zweidimensionale Interpolationsformel von Lagrange
390
9.7.2 Shepard-Interpolation
392
9.8 Entscheidungshilfen
401
Kapitel 10 Interpolierende Polynom-Splines zurKonstruktion glatter Kurven
403
10.1 Polynom-Splines dritten Grades
403
10.1.1 Aufgabenstellung
406
10.1.2 Woher kommen Splines? Mathematische Analyse
411
10.1.3 Anwendungsbeispiele
413
10.1.4 Definition verschiedener Arten nichtparametrischerkubischer Splinefunktionen
418
10.1.5 Berechnung der nichtparametrischen kubischen Splines
424
10.1.6 Berechnung der parametrischen kubischen Splines
441
10.1.7 Kombinierte interpolierende Polynom-Splines
449
10.1.8 N¨aherungsweise Ermittlung von Randableitungendurch Interpolation
454
10.1.9 Konvergenz und Fehlerabsch¨atzungeninterpolierender kubischer Splines
456
10.2 Hermite-Splines f¨unften Grades
458
10.2.1 Definition der nichtparametrischenund parametrischen Hermite-Splines
458
10.2.2 Berechnung der nichtparametrischen Hermite-Splines
459
10.2.3 Berechnung der parametrischen Hermite-Splines
463
10.3 Polynomiale kubische Ausgleichssplines
468
10.3.1 Aufgabenstellung und Motivation
468
10.3.2 Konstruktion der nichtparametrischen Ausgleichssplines
472
10.3.3 Berechnung der parametrischen kubischenAusgleichssplines
480
10.4 Entscheidungshilfen f¨ur die Auswahleiner geeigneten Splinemethode
481
Kapitel 11 Akima- und Renner-Subsplines
485
11.1 Akima-Subsplines
485
11.2 Renner-Subsplines
492
11.3 Abrundung von Eckenbei Akima- und Renner-Kurven
502
11.4 Berechnung der L¨ange einer Kurve
506
11.5 Fl¨acheninhalt einer geschlossenen ebenen Kurve
509
11.6 Entscheidungshilfen
512
Kapitel 12 Zweidimensionale Splines,Oberfl¨achensplines, B´ezier-Splines, B-Splines
513
12.1 Interpolierende zweidimensionalePolynomsplines dritten Gradeszur Konstruktion glatter Fl¨achen
513
12.2 Zweidimensionale interpolierendeOberfl¨achensplines
527
12.3 B´ezier-Splines
530
12.3.1 B´ezier-Spline-Kurven
531
12.3.2 B´ezier-Spline-Fl¨achen
535
12.3.3 Modifizierte (interpolierende) kubische B´ezier-Splines
543
12.4 B-Splines
544
12.4.1 B-Spline-Kurven
544
12.4.2 B-Spline-Fl¨achen
550
12.5 Anwendungsbeispiel
555
12.6 Entscheidungshilfen
560
Kapitel 13 Numerische Differentiation
562
13.1 Aufgabenstellung und Motivation
562
13.2 Differentiation mit Hilfe einesInterpolationspolynoms
563
13.3 Differentiation mit Hilfeinterpolierender kubischer Polynom-Splines
566
13.4 Differentiation mit dem Romberg-Verfahren
568
13.5 Entscheidungshilfen
574
Kapitel 14 Numerische Quadratur
575
14.1 Vorbemerkungen
575
14.2 Konstruktion vonInterpolationsquadraturformeln
578
14.3 Newton-Cotes-Formeln
581
14.3.1 Die Sehnentrapezformel
583
14.3.2 Die Simpsonsche Formel
589
14.3.3 Die 3/8-Formel
593
14.3.4 Weitere Newton-Cotes-Formeln
597
14.3.5 Zusammenfassung zur Fehlerordnungvon Newton-Cotes-Formeln
601
14.4 Quadraturformeln von Maclaurin
602
14.4.1 Die Tangententrapezformel
602
14.4.2 Weitere Maclaurin-Formeln
605
14.5 Die Euler-Maclaurin-Formeln
606
14.6 Tschebyscheffsche Quadraturformeln
609
14.7 Quadraturformeln von Gauß
611
14.8 Berechnung von Gewichten und St¨utzstellenverallgemeinerter Gauß-Quadraturformeln
615
14.9 Quadraturformeln von Clenshaw-Curtis
618
14.10 Das Verfahren von Romberg
619
14.11 Fehlersch¨atzung und Rechnungsfehler
626
14.12 Adaptive Quadraturverfahren
628
14.13 Konvergenz der Quadraturformeln
629
14.14 Anwendungsbeispiel
631
14.15 Entscheidungshilfen f¨ur die Auswahlder geeigneten Methode
632
Kapitel 15 Numerische Kubatur
633
15.1 Problemstellung
633
15.2 Konstruktion von Interpolationskubaturformeln
635
15.3 Newton-Cotes-Formelnf¨ur rechteckige Integrationsbereiche
638
15.4 Das Romberg-Kubaturverfahren f¨urRechteckbereiche
646
15.5 Gauß-Kubaturformeln f¨ur Rechteckbereiche
649
15.6 Berechnung des Riemannschen Fl¨achenintegralsmit bikubischen Splines
652
15.7 Vergleich der Verfahren anhand von Beispielen
652
15.8 Kubaturformeln f¨ur Dreieckbereiche
657
15.8.1 Kubaturformeln f¨ur Dreieckbereiche mit achsenparallelen Katheten
657
15.8.1.1 Newton-Cotes-Kubaturformeln f¨ur Dreieckbereiche mitachsenparallelen Katheten
657
15.8.1.2 Gauß-Kubaturformeln f¨ur Dreieckbereiche mit achsenparallelen Katheten
660
15.8.2 Kubaturformeln f¨ur Dreieckbereiche allgemeiner Lage
664
15.8.2.1 Newton-Cotes-Kubaturformelnf¨ur Dreieckbereiche allgemeiner Lage
665
15.8.2.2 Gauß-Kubaturformeln f¨ur Dreieckbereiche allgemeiner Lage
668
15.9 Entscheidungshilfen
671
Kapitel 16 Anfangswertprobleme bei gew¨ohnlichenDifferentialgleichungen
672
16.1 Problemstellung
672
16.2 Prinzip der numerischen Verfahren
673
16.3 Einschrittverfahren
674
16.3.1 Das Polygonzugverfahren von Euler-Cauchy
674
16.3.2 Das verbesserte Euler-Cauchy-Verfahren
677
16.3.3 Praediktor-Korrektor-Verfahren von Heun
682
16.3.4 Explizite Runge-Kutta-Verfahren
686
16.3.4.1 Konstruktion von Runge-Kutta-Verfahren
686
16.3.4.2 Klassisches Runge-Kutta-Verfahren
686
16.3.4.3 Zusammenstellung expliziter Runge-Kutta-Formeln
692
16.3.4.4 Einbettungsformeln
697
16.3.5 Implizite Runge-Kutta-Verfahren vom Gauß-Typ
709
16.3.6 Gemeinsame Darstellung aller Einschrittverfahren.Verfahrensfunktion eines Einschrittverfahrens. Konsistenz
711
16.3.7 Fehlersch¨atzung und automatische Schrittweitensteuerung
713
16.3.7.1 Fehlersch¨atzung
713
16.3.7.2 Methoden zur automatischen Schrittweitensteuerung.Adaptive Anfangswertprobleml¨oser
714
16.4 Mehrschrittverfahren
717
16.4.1 Prinzip der Mehrschrittverfahren
717
16.4.2 Das explizite Verfahren von Adams-Bashforth
718
16.4.3 Das Praediktor-Korrektor-Verfahren von Adams-Moulton
720
16.4.4 Verfahren von Adams-St¨ormer
726
16.4.5 Fehlersch¨atzungsformeln f¨ur Mehrschrittverfahren
727
16.5 Extrapolationsverfahren vonBulirsch-Stoer-Gragg
728
16.6 Stabilit¨at
730
16.6.1 Vorbemerkungen
730
16.6.2 Stabilit¨at der Differentialgleichung
731
16.6.3 Stabilit¨at des numerischen Verfahrens
731
16.7 Steife Differentialgleichungssysteme
736
16.7.1 Problemstellung
736
16.7.2 Kriterien f¨ur Steifheit eines Systems
736
16.7.3 Das Verfahren von Gear zur Integration steifer Systeme
737
16.8 Entscheidungshilfen bei derWahl des Verfahrens
741
Literaturverzeichnis
745
Sachwortverzeichnis
757