Numerik-Algorithmen - Verfahren, Beispiele, Anwendungen

Vorwort zur 10. korrigiertenund erweiterten Auflage

Informationen zu Quelltexten f¨ur diebeschriebenen Algorithmen

Bemerkungen zur vorliegenden C-Version

Weitere Software im Umfeld der Numerik-Bibliothek

Bezeichnungen

Inhaltsverzeichnis

Kapitel 1 Darstellung von Zahlen und Fehleranalyse,Kondition und Stabilit¨at

1.1 Definition von Fehlergr¨oßen

1.2 Zahlensysteme

1.2.1 Darstellung ganzer Zahlen

1.2.2 Darstellung reeller Zahlen

1.3 Rechnung mit endlicher Stellenzahl

1.4 Fehlerquellen

1.4.1 Eingabefehler

1.4.2 Verfahrensfehler

1.4.3 Fehlerfortpflanzung und die Kondition eines Problems

1.4.4 Rechnungsfehler und numerische Stabilit¨at

Kapitel 2 Numerische Verfahren zur L¨osungnichtlinearer Gleichungen

2.1 Aufgabenstellung und Motivation

2.2 Definitionen und S¨atze ¨uber Nullstellen

2.3 Allgemeines Iterationsverfahren

2.3.1 Konstruktionsmethode und Definition

2.3.2 Existenz einer L¨osung und Eindeutigkeit der L¨osung

2.3.3 Konvergenz eines Iterationsverfahrens

2.3.3.1 Heuristische Betrachtungen

2.3.3.2 Analytische Betrachtung

2.3.4 Fehlerabsch¨atzungen und Rechnungsfehler

2.3.5 Praktische Durchf¨uhrung

2.4 Konvergenzordnung eines Iterationsverfahrens

2.5 Newtonsche Verfahren

2.5.1 Das Newtonsche Verfahren f¨ur einfache Nullstellen

2.5.2 Ged¨ampftes Newton-Verfahren

2.5.3 Das Newtonsche Verfahren f¨ur mehrfache Nullstellen.Das modifizierte Newtonsche Verfahren

2.6 Das Sekantenverfahren

2.6.1 Das Sekantenverfahren f¨ur einfache Nullstellen

2.6.2 Das modifizierte Sekantenverfahrenf¨ur mehrfache Nullstellen

2.7 Einschlussverfahren

2.7.1 Das Prinzip der Einschlussverfahren

2.7.2 Das Bisektionsverfahren

2.7.3 Die Regula falsi

2.7.4 Das Pegasus-Verfahren

2.7.5 Das Verfahren von Anderson-Bj¨orck

2.7.6 Die Verfahren von King und Anderson-Bj¨orck-King.Das Illinois-Verfahren

2.7.7 Ein kombiniertes Einschlussverfahren

2.7.8 Das Zeroin-Verfahren

2.8 Anwendungsbeispiele

2.9 Effizienz der Verfahren und Entscheidungshilfen

Kapitel 3 Verfahren zur L¨osung algebraischerGleichungen

3.1 Vorbemerkungen

3.2 Das Horner-Schema

3.2.1 Das einfache Horner-Schema f¨ur reelle Argumentwerte

3.2.2 Das einfache Horner-Schema f¨ur komplexe Argumentwerte

3.2.3 Das vollst¨andige Horner-Schema f¨ur reelle Argumentwerte

3.2.4 Anwendungen

3.3 Methoden zur Bestimmung s¨amtlicherL¨osungen algebraischer Gleichungen

3.3.1 Vorbemerkungen und ¨Uberblick

3.3.2 Das Verfahren von Muller

3.3.3 Das Verfahren von Bauhuber

3.3.4 Das Verfahren von Jenkins und Traub

3.4 Anwendungsbeispiel

3.5 Entscheidungshilfen

Kapitel 4 Direkte Verfahrenzur L¨osung linearer Gleichungssysteme

4.1 Aufgabenstellung und Motivation

4.2 Definitionen und S¨atze

4.3 L¨osbarkeitsbedingungenf¨ur ein lineares Gleichungssystem

4.4 Prinzip der direkten Methodenzur L¨osung linearer Gleichungssysteme

4.5 Der Gauß-Algorithmus

4.5.1 Gauß-Algorithmus mit Spaltenpivotsucheals Rechenschema

4.5.2 Spaltenpivotsuche

4.5.3 Gauß-Algorithmus als Dreieckszerlegung

4.5.4 Gauß-Algorithmus f¨ur Systememit mehreren rechten Seiten

4.6 Matrizeninversion mit dem Gauß-Algorithmus

4.7 Verfahren f¨ur Systememit symmetrischen Matrizen

4.7.1 Systeme mit symmetrischer, streng regul¨arer Matrix

4.7.2 Systeme mit symmetrischer, positiv definiter Matrix.Cholesky-Verfahren

4.7.3 Systeme mit symmetrischer, positiv definiter Matrix.Verfahren der konjugierten Gradienten (CG-Verfahren)

4.8 Das Gauß-Jordan-Verfahren

4.9 Gleichungssysteme mit tridiagonaler Matrix

4.9.1 Systeme mit tridiagonaler Matrix

4.9.2 Systeme mit symmetrischer, tridiagonaler,positiv definiter Matrix

4.10 Gleichungssystememit zyklisch tridiagonaler Matrix

4.10.1 Systeme mit zyklisch tridiagonaler Matrix

4.10.2 Systeme mit symmetrischer, zyklisch tridiagonaler Matrix

4.11 Gleichungssysteme mit f¨unfdiagonaler Matrix

4.11.1 Systeme mit f¨unfdiagonaler Matrix

4.11.2 Systeme mit symmetrischer, f¨unfdiagonaler,positiv definiter Matrix

4.12 Gleichungssysteme mit Bandmatrix

4.13 L¨osung ¨uberbestimmter linearer Gleichungssystememit Householdertransformation

4.14 Fehler, Kondition und Nachiteration

4.14.1 Fehler und Kondition

4.14.2 Konditionssch¨atzung

4.14.3 M¨oglichkeiten zur Konditionsverbesserung

4.14.4 Nachiteration

4.15 Gleichungssysteme mit Blockmatrix

4.15.1 Vorbemerkungen

4.15.2 Gauß-Algorithmus f¨ur Blocksysteme

4.15.3 Gauß-Algorithmus f¨ur tridiagonale Blocksysteme

4.15.4 Weitere Block-Verfahren

4.16 Algorithmus von Cuthill-McKeef¨ur d¨unn besetzte, symmetrische Matrizen

4.17 Entscheidungshilfenf¨ur die Auswahl des Verfahrens

Kapitel 5 Iterationsverfahren zur L¨osunglinearer Gleichungssysteme

5.1 Vorbemerkungen

5.2 Vektor- und Matrizennormen

5.3 Das Iterationsverfahren in Gesamtschritten

5.4 Das Gauß-Seidelsche Iterationsverfahren,Iteration in Einzelschritten

5.5 Relaxation beim Gesamtschrittverfahren

5.6 Relaxation beim Einzelschrittverfahren.SOR-Verfahren

5.6.1 Sch¨atzung des Relaxationskoeffizienten.Adaptives SOR-Verfahren

Kapitel 6 Systeme nichtlinearer Gleichungen

6.1 Aufgabenstellung und Motivation

6.2 Allgemeines Iterationsverfahren f¨ur Systeme

6.3 Spezielle Iterationsverfahren

6.3.1 Newtonsche Verfahren f¨ur nichtlineare Systeme

6.3.1.1 Das quadratisch konvergente Newton-Verfahren

6.3.1.2 Ged¨ampftes Newton-Verfahren f¨ur Systeme

6.3.2 Sekantenverfahren f¨ur nichtlineare Systeme

6.3.3 Das Verfahren des st¨arksten Abstiegs(Gradientenverfahren) f¨ur nichtlineare Systeme

6.3.4 Das Verfahren von Brown f¨ur Systeme

6.4 Entscheidungshilfen f¨ur die Auswahl der Methode

Kapitel 7 Eigenwerte und Eigenvektoren von Matrizen

7.1 Definitionen und Aufgabenstellungen

7.2 Diagonal¨ahnliche Matrizen

7.3 Das Iterationsverfahren nach v. Mises

7.3.1 Bestimmung des betragsgr¨oßten Eigenwertesund des zugeh¨origen Eigenvektors

7.3.2 Bestimmung des betragskleinsten Eigenwertes

7.3.3 Bestimmung weiterer Eigenwerte und Eigenvektoren

7.4 Konvergenzverbesserung mit Hilfe des Rayleigh-Quotienten im Falle hermitescher Matrizen

7.5 Das Verfahren von Krylov

7.5.1 Bestimmung der Eigenwerte

7.6 Bestimmung der Eigenwerte positiv definiter,symmetrischer, tridiagonaler Matrizen mit Hilfedes QD-Algorithmus

7.7 Transformationen auf Hessenbergform,LR- und QR-Verfahren

7.7.1 Transformation einer Matrix auf obere Hessenbergform

7.7.2 LR - Verfahren

7.7.3 QR - Verfahren

7.8 Ermittlung der Eigenwerte und Eigenvektoreneiner Matrix nach den Verfahren von Martin,Parlett, Peters, Reinsch und Wilkinson

7.9 Entscheidungshilfen

7.10 Anwendungsbeispiel

Kapitel 8 Lineare und nichtlineare Approximation

8.1 Aufgabenstellung und Motivation

8.2 Lineare Approximation

8.2.1 Approximationsaufgabe und beste Approximation

8.2.2 Kontinuierliche lineare Approximationim quadratischen Mittel

8.2.3 Diskrete lineare Approximation im quadratischen Mittel

8.2.3.1 Normalgleichungen f¨ur den diskreten linearen Ausgleich

8.2.3.2 Diskreter Ausgleich durch algebraische Polynomeunter Verwendung orthogonaler Polynome

8.2.3.3 Lineare Regression. Ausgleich durch lineare algebraische Polynome

8.2.3.4 Householder-Transformationzur L¨osung des linearen Ausgleichsproblems

8.2.4 Approximation von Polynomendurch Tschebyscheff-Polynome

8.2.4.1 Beste gleichm¨aßige Approximation, Definition

8.2.4.2 Approximation durch Tschebyscheff-Polynome

8.2.5 Approximation periodischer Funktionen

8.2.5.1 Kontinuierliche Approximation periodischer Funktionenim quadratischen Mittel

8.2.5.2 Diskrete Approximation periodischer Funktionenim quadratischen Mittel

8.2.5.3 Fourier-Transformation und FFT

8.2.6 Fehlerabsch¨atzungen f¨ur lineare Approximationen

8.2.6.1 Gleichm¨aßige Approximation durch algebraische Polynome

8.2.6.2 Gleichm¨aßige Approximation durch trigonometrische Polynome

8.3 Diskrete nichtlineare Approximation

8.3.1 Transformationsmethode beim nichtlinearen Ausgleich

8.3.2 Nichtlinearer Ausgleich im quadratischen Mittel

8.4 Entscheidungshilfen

Kapitel 9 Polynomiale Interpolation sowieShepard-Interpolation

9.1 Aufgabenstellung

9.2 Interpolationsformeln von Lagrange

9.2.1 Lagrangesche Formel f¨ur beliebige St¨utzstellen

9.2.2 Lagrangesche Formel f¨ur ¨aquidistante St¨utzstellen

9.3 Aitken-Interpolationsschemaf¨ur beliebige St¨utzstellen

9.4 Inverse Interpolation nach Aitken

9.5 Interpolationsformeln von Newton

9.5.1 Newtonsche Formel f¨ur beliebige St¨utzstellen

9.5.2 Newtonsche Formel f¨ur ¨aquidistante St¨utzstellen

9.6 Absch¨atzung und Sch¨atzungdes Interpolationsfehlers

9.7 Zweidimensionale Interpolation

9.7.1 Zweidimensionale Interpolationsformel von Lagrange

9.7.2 Shepard-Interpolation

9.8 Entscheidungshilfen

Kapitel 10 Interpolierende Polynom-Splines zurKonstruktion glatter Kurven

10.1 Polynom-Splines dritten Grades

10.1.1 Aufgabenstellung

10.1.2 Woher kommen Splines? Mathematische Analyse

10.1.3 Anwendungsbeispiele

10.1.4 Definition verschiedener Arten nichtparametrischerkubischer Splinefunktionen

10.1.5 Berechnung der nichtparametrischen kubischen Splines

10.1.6 Berechnung der parametrischen kubischen Splines

10.1.7 Kombinierte interpolierende Polynom-Splines

10.1.8 N¨aherungsweise Ermittlung von Randableitungendurch Interpolation

10.1.9 Konvergenz und Fehlerabsch¨atzungeninterpolierender kubischer Splines

10.2 Hermite-Splines f¨unften Grades

10.2.1 Definition der nichtparametrischenund parametrischen Hermite-Splines

10.2.2 Berechnung der nichtparametrischen Hermite-Splines

10.2.3 Berechnung der parametrischen Hermite-Splines

10.3 Polynomiale kubische Ausgleichssplines

10.3.1 Aufgabenstellung und Motivation

10.3.2 Konstruktion der nichtparametrischen Ausgleichssplines

10.3.3 Berechnung der parametrischen kubischenAusgleichssplines

10.4 Entscheidungshilfen f¨ur die Auswahleiner geeigneten Splinemethode

Kapitel 11 Akima- und Renner-Subsplines

11.1 Akima-Subsplines

11.2 Renner-Subsplines

11.3 Abrundung von Eckenbei Akima- und Renner-Kurven

11.4 Berechnung der L¨ange einer Kurve

11.5 Fl¨acheninhalt einer geschlossenen ebenen Kurve

11.6 Entscheidungshilfen

Kapitel 12 Zweidimensionale Splines,Oberfl¨achensplines, B´ezier-Splines, B-Splines

12.1 Interpolierende zweidimensionalePolynomsplines dritten Gradeszur Konstruktion glatter Fl¨achen

12.2 Zweidimensionale interpolierendeOberfl¨achensplines

12.3 B´ezier-Splines

12.3.1 B´ezier-Spline-Kurven

12.3.2 B´ezier-Spline-Fl¨achen

12.3.3 Modifizierte (interpolierende) kubische B´ezier-Splines

12.4 B-Splines

12.4.1 B-Spline-Kurven

12.4.2 B-Spline-Fl¨achen

12.5 Anwendungsbeispiel

12.6 Entscheidungshilfen

Kapitel 13 Numerische Differentiation

13.1 Aufgabenstellung und Motivation

13.2 Differentiation mit Hilfe einesInterpolationspolynoms

13.3 Differentiation mit Hilfeinterpolierender kubischer Polynom-Splines

13.4 Differentiation mit dem Romberg-Verfahren

13.5 Entscheidungshilfen

Kapitel 14 Numerische Quadratur

14.1 Vorbemerkungen

14.2 Konstruktion vonInterpolationsquadraturformeln

14.3 Newton-Cotes-Formeln

14.3.1 Die Sehnentrapezformel

14.3.2 Die Simpsonsche Formel

14.3.3 Die 3/8-Formel

14.3.4 Weitere Newton-Cotes-Formeln

14.3.5 Zusammenfassung zur Fehlerordnungvon Newton-Cotes-Formeln

14.4 Quadraturformeln von Maclaurin

14.4.1 Die Tangententrapezformel

14.4.2 Weitere Maclaurin-Formeln

14.5 Die Euler-Maclaurin-Formeln

14.6 Tschebyscheffsche Quadraturformeln

14.7 Quadraturformeln von Gauß

14.8 Berechnung von Gewichten und St¨utzstellenverallgemeinerter Gauß-Quadraturformeln

14.9 Quadraturformeln von Clenshaw-Curtis

14.10 Das Verfahren von Romberg

14.11 Fehlersch¨atzung und Rechnungsfehler

14.12 Adaptive Quadraturverfahren

14.13 Konvergenz der Quadraturformeln

14.14 Anwendungsbeispiel

14.15 Entscheidungshilfen f¨ur die Auswahlder geeigneten Methode

Kapitel 15 Numerische Kubatur

15.1 Problemstellung

15.2 Konstruktion von Interpolationskubaturformeln

15.3 Newton-Cotes-Formelnf¨ur rechteckige Integrationsbereiche

15.4 Das Romberg-Kubaturverfahren f¨urRechteckbereiche

15.5 Gauß-Kubaturformeln f¨ur Rechteckbereiche

15.6 Berechnung des Riemannschen Fl¨achenintegralsmit bikubischen Splines

15.7 Vergleich der Verfahren anhand von Beispielen

15.8 Kubaturformeln f¨ur Dreieckbereiche

15.8.1 Kubaturformeln f¨ur Dreieckbereiche mit achsenparallelen Katheten

15.8.1.1 Newton-Cotes-Kubaturformeln f¨ur Dreieckbereiche mitachsenparallelen Katheten

15.8.1.2 Gauß-Kubaturformeln f¨ur Dreieckbereiche mit achsenparallelen Katheten

15.8.2 Kubaturformeln f¨ur Dreieckbereiche allgemeiner Lage

15.8.2.1 Newton-Cotes-Kubaturformelnf¨ur Dreieckbereiche allgemeiner Lage

15.8.2.2 Gauß-Kubaturformeln f¨ur Dreieckbereiche allgemeiner Lage

15.9 Entscheidungshilfen

Kapitel 16 Anfangswertprobleme bei gew¨ohnlichenDifferentialgleichungen

16.1 Problemstellung

16.2 Prinzip der numerischen Verfahren

16.3 Einschrittverfahren

16.3.1 Das Polygonzugverfahren von Euler-Cauchy

16.3.2 Das verbesserte Euler-Cauchy-Verfahren

16.3.3 Praediktor-Korrektor-Verfahren von Heun

16.3.4 Explizite Runge-Kutta-Verfahren

16.3.4.1 Konstruktion von Runge-Kutta-Verfahren

16.3.4.2 Klassisches Runge-Kutta-Verfahren

16.3.4.3 Zusammenstellung expliziter Runge-Kutta-Formeln

16.3.4.4 Einbettungsformeln

16.3.5 Implizite Runge-Kutta-Verfahren vom Gauß-Typ

16.3.6 Gemeinsame Darstellung aller Einschrittverfahren.Verfahrensfunktion eines Einschrittverfahrens. Konsistenz

16.3.7 Fehlersch¨atzung und automatische Schrittweitensteuerung

16.3.7.1 Fehlersch¨atzung

16.3.7.2 Methoden zur automatischen Schrittweitensteuerung.Adaptive Anfangswertprobleml¨oser

16.4 Mehrschrittverfahren

16.4.1 Prinzip der Mehrschrittverfahren

16.4.2 Das explizite Verfahren von Adams-Bashforth

16.4.3 Das Praediktor-Korrektor-Verfahren von Adams-Moulton

16.4.4 Verfahren von Adams-St¨ormer

16.4.5 Fehlersch¨atzungsformeln f¨ur Mehrschrittverfahren

16.5 Extrapolationsverfahren vonBulirsch-Stoer-Gragg

16.6 Stabilit¨at

16.6.1 Vorbemerkungen

16.6.2 Stabilit¨at der Differentialgleichung

16.6.3 Stabilit¨at des numerischen Verfahrens

16.7 Steife Differentialgleichungssysteme

16.7.1 Problemstellung

16.7.2 Kriterien f¨ur Steifheit eines Systems

16.7.3 Das Verfahren von Gear zur Integration steifer Systeme

16.8 Entscheidungshilfen bei derWahl des Verfahrens

Literaturverzeichnis

Sachwortverzeichnis