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 |