Numerik-Algorithmen (eBook)

Gisela Engeln-Müllges war von 1982 bis 2005 Professorin am Fachbereich Maschinenbau und Mechatronik der Fachhochschule Aachen mit dem Lehr- und Forschungsgebiet Numerische Mathematik und Datenverarbeitung, 1991 bis 2005  Prorektorin für Forschung. Von 1997 bis 2003 war sie Mitglied des Wissenschaftsrates. Seit 2005 ist sie in diversen wissenschaftsbezogenen Gremien, Jurys und Arbeitsgruppen tätig.Klaus Niederdrenk ist seit 1993 als Professor an der Fachhochschule Münster tätig. Von 1998 bis 2008 war er Rektor dieser Einrichtung, seit 2009 gehört er dem Fachbereich Wirtschaft mit dem Lehr- und Forschungsgebiet Mathematik, Quantitative Methoden an. Von 2004 bis 2007 war er Vorstandsmitglied im DAAD, seit 2007 ist er Mitglied im Wissenschaftsrat. Außerdem ist er in zahlreichen wissenschaftsbezogenen Gremien und Kommissionen engagiert.Reinhard Wodicka arbeitete von 1953 bis 1988 am Institut für Geometrie und Praktische Mathematik der Rheinisch-Westfälischen Technischen Hochschule Aachen in verschiedenen Positionen, zuletzt war er dort ab 1975 als Studienprofessor tätig. Nach seiner Pensionierung setzte er sich intensiv mit Fragen der Numerischen Mathematik auseinander.

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