W. Oevel

Numerik I Inhalt

1 Kurzer Ausblick 1

2 Fehleranalyse 5 2.1 Gleitpunktdarstellung . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Arithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Fehlerfortpflanzung . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3.1 Fehlerfortpflanzung in der Grundarithmetik . . . . . . . . 12 2.3.2 Differentielle Fehleranalyse . . . . . . . . . . . . . . . . . 14

3 Nichtlineare Gleichungen (skalar) 21 3.1 Der Banachsche Fixpunktsatz . . . . . . . . . . . . . . . . . . . . 21 3.2 Superlineare Konvergenz . . . . . . . . . . . . . . . . . . . . . . . 27 3.3 Das Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 Ein Newton–Verfahren für entartete Nullstellen . . . . . . . . . . 33 3.5 Höhere Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.6 Bisektion (Intervallhalbierung) . . . . . . . . . . . . . . . . . . . 36 3.7 Das Sekantenverfahren . . . . . . . . . . . . . . . . . . . . . . . . 36 3.8 Mehrfache Nullstellen . . . . . . . . . . . . . . . . . . . . . . . . 39 3.9 Nullstellen von Polynomen . . . . . . . . . . . . . . . . . . . . . . 40

3.9.1 Das Horner-Schema . . . . . . . . . . . . . . . . . . . . . 40 3.9.2 Nullstellenabschätzung . . . . . . . . . . . . . . . . . . . . 42 3.9.3 Das Newton-Verfahren für Polynome . . . . . . . . . . . . 44

4 Lineare Gleichungssysteme 49 4.1 Vorbemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.2 Blockzerlegungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3 Strassens schnelle Matrixmultiplikation . . . . . . . . . . . . . . . 50 4.4 Dreieckssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.5 Der Gauß-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 53 4.6 LR-Faktorisierung . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.7 Bandmatrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.8 Pivotierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.9 Cholesky-Faktorisierung . . . . . . . . . . . . . . . . . . . . . . . 66 4.10 Invertierung von Matrizen . . . . . . . . . . . . . . . . . . . . . . 70 4.11 QR-Faktorisierung . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.12 Normen und Fehlerkontrolle . . . . . . . . . . . . . . . . . . . . . 80 4.13 Nachiteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.14 Iterative Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 90

5 Nichtlineare Gleichungssysteme 97

6 Eigenwertprobleme 103 6.1 Allgemeine Abschätzungen . . . . . . . . . . . . . . . . . . . . . 104 6.2 Die von-Mises-Iteration . . . . . . . . . . . . . . . . . . . . . . . 109 6.3 Die Wielandt-Rayleigh-Iteration . . . . . . . . . . . . . . . . . . 112 6.4 Weitere Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6.4.1 Das Jacobi-Verfahren für symmetrische Matrizen . . . . . 117 6.4.2 Das QR-Verfahren . . . . . . . . . . . . . . . . . . . . . . 118

7 Interpolation 119

7.1 Polynominterpolation . . . . . . . . . . . . . . . . . . . . . . . . 119 7.1.1 Entwicklung nach Monomen . . . . . . . . . . . . . . . . . 120 7.1.2 Lagrange-Darstellung . . . . . . . . . . . . . . . . . . . . 120 7.1.3 Newton-Darstellung . . . . . . . . . . . . . . . . . . . . . 121 7.1.4 Praktische Durchführung der Interpolation . . . . . . . . 127

8 Splines 133 8.1 Spline-Räume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 8.2 B-Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 8.3 Interpolation mit Splines . . . . . . . . . . . . . . . . . . . . . . . 143

8.3.1 Kubische Splines . . . . . . . . . . . . . . . . . . . . . . . 144 8.3.2 Die Minimaleigenschaft kubischer Splines . . . . . . . . . 147 8.3.3 Fehlerabschätzungen . . . . . . . . . . . . . . . . . . . . . 150

9 Quadratur (Integration) 153 9.1 Newton-Cotes-Formeln . . . . . . . . . . . . . . . . . . . . . . . . 154 9.2 Gauß-Quadratur . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 9.3 Adaptive Quadratur . . . . . . . . . . . . . . . . . . . . . . . . . 167

Literatur

[Scw93] H.R. Schwarz: Numerische Mathematik. Stuttgart: Teubner 1993. (hervorragende, leicht lesbare Einführung, sehr empfehlenswert)

[Sto93] J. Stoer: Numerische Mathematik 1. Berlin: Springer 1993.

[StB90] J. Stoer und R. Bulirsch: Numerische Mathematik 2. Berlin: Springer 1990. (Klassiker, sehr umfangreich und vollständig, als erste Einführung weniger leicht lesbar als [Scw93], da sehr detailliert)

[ScW92] R. Schaback und H. Werner: Numerische Mathematik. Berlin: Springer 1992. (gut lesbar, kompakter als [Scw93],[Sto93],[StB90])

[Oev96] W. Oevel: Einführung in die Numerische Mathematik. Heidelberg: Spektrum Akademischer Verlag 1996. (leicht lesbare Einführung, sehr breit geschrieben, reduzierte Themenauswahl im Vergleich zu [Scw93],[Sto93],[StB90],[ScW93]. Ist eine sehr detaillierte Ausarbeitung der in dieser Vorlesung behandelten Themen.)

Sammlung weiterer Literatur:

1. Numerische Mathematik

Abramowitz, M.; Stegun, I. A. (Eds.): Handbook of Mathematical Functions. Washington: National Bureau of Standards 1965; New York: Dover 1982.

Atkinson, K. E.: Introduction to Numerical Analysis. New York: Wiley 1989.

Bunse, W.; Bunse-Gerstner, A.: Numerische lineare Algebra. Stuttgart: Teubner 1985.

Conte, S. D.; de Boor, C.: Elementary Numerical Analysis. An Algorithmic Approach. Singapore: McGraw–Hill 1986.

Deuflhard, P.; Hohmann, A.: Numerische Mathematik I. Eine algorithmisch orientierte Einführung. Berlin: de Gruyter 1993.

Deuflhard, P.; Bornemann, F.: Numerische Mathematik II. Integration gewöhnlicher Differentialgleichungen. Berlin: de Gruyter 1994.

Engeln–Müllges, G.; Reutter, F.: Numerische Mathematik für Ingenieure. Mannheim: Bibliographisches Institut 1994.

Golub, G. H.; Van Loan, C. F.: Matrix Computations.

Baltimore: Johns Hopkins University Press 1989.

Golub, G. H.; Ortega, J. M.: Wissenschaftliches Rechnen und Differentialgleichungen. Eine Einführung in die Numerische Mathematik. Lemgo: Heldermann 1995.

Golub, G. H.; Ortega, J. M.: Scientific Computing. Eine Einführung in das wissenschaftliche Rechnen und Parallele Numerik. Stuttgart: Teubner 1996.

Hämmerlin, G.; Hoffmann, K.-H.: Numerische Mathematik. Berlin: Springer 1994.

Hager, W. W.: Applied Numerical Linear Algebra. Englewood Cliffs. Prentice Hall 1988.

Hart, J. F.; et al.: Computer Approximations. New York: Wiley 1978.

Isaacson, E.; Keller, H. B.: Analyse numerischer Verfahren. Frankfurt: Deutsch 1973.

– Nachdruck der amerikanischen Originalausgabe: Analysis of Numerical Methods.

New York: Dover 1994.

Kiełbasiński, A.; Schwetlick, H.: Numerische lineare Algebra.

Berlin: Deutscher Verlag der Wissenschaften 1988.

Köckler, N.: Numerische Algorithmen in Softwaresystemen – unter besonderer Berücksichtigung der NAG-Bibliothek. Stuttgart: Teubner 1990.

Locher, F.: Numerische Mathematik für Informatiker. Berlin: Springer 1993.

Maess, G.: Vorlesungen über Numerische Mathematik. Band I: Lineare Algebra. Band II: Analysis. Basel: Birkhäuser 1985, 1987.

Maron, M. J.: Numerical Analysis: A Practical Approach. New York: Macmillan 1991.

Oevel, W.: Einführung in die Numerische Mathematik. Heidelberg: Spektrum 1996.

Opfer, G.: Numerische Mathematik für Anfänger. Braunschweig: Vieweg 1994.

Schaback, R.; Werner, H.: Numerische Mathematik. Berlin: Springer 1993.

Schwarz, H. R.: Numerische Mathematik. Stuttgart: Teubner 1993.

Späth, H.: Numerik. Eine Einführung für Mathematiker und Informatiker. Braunschweig: Vieweg 1994.

Stoer, J.: Numerische Mathematik 1, 2 (Band 2 gemeinsam mit R. Bulirsch). Berlin: Springer 1994, 1991 .

Stummel, F.; Hainer, K.: Praktische Mathematik. Stuttgart: Teubner 1982.

Törnig, W.; Spellucci, P.: Numerische Mathematik für Ingenieure und Physiker. Band 1: Numerische Methoden der Algebra. Band 2: Eigenwertprobleme und numerische Methoden der Analysis. Berlin: Springer 1988, 1990.

Überhuber, C.: Computer–Numerik 1, 2. Berlin: Springer 1995.

Werner, J.: Numerische Mathematik. Band 1: Lineare und nichtlineare Gleichungssysteme, Interpolation, numerische Integration. Band 2: Eigenwertaufgaben, lineare Optimierungsaufgaben, unrestringierte Optimierungsaufgaben. Braunschweig: Vieweg 1992.

2. Programmsammlungen

Anderson, E.; Bai, Z.; Bischof, C.; et al.: LAPACK Users’ Guide. Philadelphia: SIAM 1995.

Dongarra, J. J.; Bunch, J. R.; Moler, C. B.; Stewart, G. W.: LINPACK Users’ Guide. Philadelphia: SIAM 1979.

Engeln–Müllges, G.; Uhlig, G.: Numerical Algorithms with Fortran. Berlin: Springer 1996.

Garbow, B. S.; Boyle, J. M.; Dongarra, J. J.; Moler, C. B.:

Matrix Eigensystem Routines – EISPACK Guide Extension. Berlin: Springer 1990.

NAG Fortran Library. Oxford: Numerical Algorithms Group.

– Introductory Guide, Mark 16. 1993.

– Manual, Mark 16, Vols. 1–12. 1993.

– Mark 16, Contents Summary. 1993.

Piessens, R.; de Doncker–Kapenga, E.; Überhuber, C.W.; Kahaner, D. K.: QUADPACK, A Subroutine Package for Automatic Integration. Berlin: Springer 1983.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.:

Numerical Recipes in FORTRAN: The Art of Scientific Computing. Cambridge: Cambridge University Press 1993.

Rice, J.; Boisvert, R. F.: Solving Elliptic Problems Using ELLPACK. Berlin: Springer 1985.

Schwarz, H. R.: FORTRAN–Programme zur Methode der finiten Elemente. Stuttgart: Teubner 1991.

Smith, B.T.; Boyle, J.M.; Dongarra, J.J.; Garbow, B.S.; Ikebe, Y.; Klema, V. C.; Moler, C. B.: Matrix Eigensystem Routines – EISPACK Guide. Berlin: Springer 1990.

Abkürzung SIAM : Society for Industrial and Applied Mathematics INHALT vii