De Gruyter Studium Friedrich/Pietschmann · Numerische Methoden Hermann Friedrich Frank Pietschmann Numerische Methoden Ein Lehr- und Übungsbuch De Gruyter Prof. Dr. Hermann Friedrich Fakultät Mathematik/Naturwissenschaften Hochschule Zittau/Görlitz (cid:2) University of Applied Sciences Theodor-Körner-Ring 16 02763 Zittau E-Mail: [email protected] Prof. Dr. Frank Pietschmann Fakultät Mathematik/Naturwissenschaften Hochschule Zittau/Görlitz (cid:2) University of Applied Sciences Theodor-Körner-Ring 16 02763 Zittau E-Mail: [email protected] 2010 Mathematics Subject Classification: Primary 65-01. Secondary 65C05, 65D05, 65D07, 65D25, 65D30, 65H04, 65L06, 65T40, 65T50 ISBN 978-3-11-021806-0 e-ISBN 978-3-11-021807-7 BibliografischeInformationderDeutschenNationalbibliothek DieDeutscheNationalbibliothekverzeichnetdiesePublikationinderDeutschen Nationalbibliografie;detailliertebibliografischeDatensindimInternet überhttp://dnb.d-nb.deabrufbar. (cid:2)2010WalterdeGruyterGmbH&Co.KG,Berlin/NewYork Satz:Da-TeXGerdBlumenstein,Leipzig,www.da-tex.de DruckundBindung:AZDruckundDatentechnikGmbH,Kempten (cid:3)GedrucktaufsäurefreiemPapier PrintedinGermany www.degruyter.com Vorwort Da die meisten praktischen Probleme im Ingenieurwesen und in der Ökonomie nu- merisch gelöst werden müssen, gehören die numerischen Methoden zu den mathe- matischenGrundlagenfächernanHochschulen,insbesondereanHochschulen,wodie StudentenbesondersengenBezugzurPraxisinderAusbildungerhalten.Dabeimüs- sendiemathematischenGrundlagendernumerischenAlgorithmenbeimStudiumver- mitteltundnatürlichanHandvongeeignetenBeispielenundAufgabendemonstriert undgefestigtwerden.Esistwichtig,dassderStudentnichtnurdasRechenprogramm zu einem numerischen Verfahren kennt und anwenden kann, sondern dass er durch Kenntnis der mathematischen Hintergründe die Fähigkeit zum richtigen Einsatz der Verfahren(BeachtungderEinsatzvoraussetzungen,KenntnisüberKonsequenzenbei Verletzung der Einsatzbedingungen, Zurückgreifen auf ein anderes Verfahren), zum eventuellnotwendigenselbständigenEingriffindasRechenprogrammundzumNeu- programmiereneinesaufeinenbestimmtenRechnertypzugeschnittenen,dannmeis- tens effektiveren Programms besitzt. Der Anwender eines numerischen Verfahrens muss Kenntnisse über die Stabilität des Algorithmus und über zu erwartende Fehler von Näherungslösungen besitzen. Der Student sollte mittels zahlreicher angemesse- ner Aufgaben zum selbständigen Arbeiten angeregt und befähigt werden. Natürlich gehörenauchumfassendeKenntnisseüberprogrammierbareRechenanlagenunddie Programmiertechnikdazu;diesezuvermitteln,istaberAufgabederInformatik. In elf Kapiteln des Buches werden ausgewählte numerische Methoden behandelt, diejedochnureinenEinblickindasweitausgebauteGebietdernumerischenMathe- matikgebenkönnen. Im ersten Kapitel erfolgt eine Zusammenstellung benötigter Grundlagen aus den BereichenMatrizen,DeterminantenundNormen.AufdiebeinumerischenMethoden wichtigenProblemederFehlerentstehung,FehlerfortpflanzungundKonditionszahlen sowie der Fehlerabschätzungen bei numerischen Rechnungen ist im zweiten Kapitel eingegangen.FehlerabschätzungenwerdendurchgängigbeiallenbehandeltenMetho- denabgeleitetundbenutzt. DieKapiteldreibisneunbehandelnklassischeVerfahrendernumerischenMathe- matik.ZunächstwirdimdrittenKapitelaufGrundlagenundMethodenbeiIterations- verfahren (Bisektionsmethode, Regula falsi, Newtonsches Iterationsverfahren, Ver- fahrenvonAitkin,Steffensen-Verfahren)eingegangen.DasvierteKapitelbeschäftigt sichmitderLösunglinearerGleichungssystemesowohlmitEliminationsverfahrenals auch mit Iterationsverfahren (Gaußscher Algorithmus, Choleski-Verfahren, Givens- Verfahren,Jacobi-Verfahren,Gauß-Seidel-Verfahren). vi Vorwort DenfürpraktischeProblemewichtigenApproximations-undInterpolationsverfah- renwerdendiefolgendenbeidenKapitelgewidmet.SchwerpunktedesfünftenKapi- tels sind diskrete Approximation (Methode der kleinsten Quadrate, Linearisierung), stetige Approximation (Legendresche Polynome, Trigonometrische Funktionen, Komplexe Fourier-Reihen) und lokale Approximation (Taylor-Reihen). Im sechsten Kapitel folgen Polynomiterationen (Interpolationsverfahren von Lagrange, Newton- schesInterpolationsverfahren,Hermite-Interpolation),Splineinterpolationen(Lineare Splines,QuadratischeSplines,KubischeSplines,B-Splines)undInterpolationenmit periodischenFunktionen(InterpolationmitkomplexenExponentialfunktionen,Inter- polationmittrigonometrischenFunktionen,SchnelleFourier-Transformation). NumerischeUmsetzungenderDifferential-undIntegralrechnungsindGegenstand der nächsten beiden Kapitel. Zuerst wird auf die numerische Differentiation einge- gangen. Danach sind im achten Kapitel numerische Integrationsmethoden behandelt (Trapezformel, Simpsonsche Formel, Verfahren von Romberg, Adaptive Simpson- Quadratur,Gauß-Integrationsformeln).ImneuntenKapitelsindnumerischeLösungs- verfahren für Anfangswertaufgaben bei gewöhnlichen Differentialgleichungen er- örtert (Verfahren von Picard-Lindelöf, Euler-Cauchy Polygonzugverfahren, Runge- Kutta-Verfahren, explizite und implizite Mehrschrittverfahren, Prädiktor-Korrektor- Verfahren,steiferDifferentialgleichungen). DierestlichenbeidenKapitelbehandelnnumerischeHilfsmittelundMethoden,die inspeziellenProblemenoftmalsvonBedeutungsind,inEinführungenindienumeri- sche Mathematik aber in der Regel nicht vorkommen. Im zehnten Kapitel wird aus- führlich auf reelle und komplexe Polynome eingegangen (Wertberechnung, Abspal- tung von Polynomen niedrigerer Ordnung, Berechnung von reellen und konjugiert- komplexen Nullstellen unter Benutzung von ein- und mehrzeiligen einfachen und vollständigenHorner-Schemata).EinausführlicherAbschnittbehandeltAussagenzur Anzahl und Lage von Nullstellen bei reellen und komplexen Polynomen. Das elfte Kapitel enthält selten dargestellte Grundlagen und Methoden der numerischen Si- mulation von Zufallsgrößen (Zufallsgrößen, Zufallsgeneratoren, Anwendungen von ZufallszahlenzurnumerischeBerechnungbestimmterIntegrale). Allen Kapiteln sind zahlreiche Übungsaufgaben mit Lösungen beigegeben. Wenn zusätzliches Interesse an weiter gehenden numerischen Verfahren besteht oder für numerische Aufgabenstellungen spezielle Verfahren benötigt werden, kann auf die reichlichvorhandeneundimLiteraturverzeichnisaufgelisteteLiteraturzurückgegrif- fenwerden. Die Autoren danken allen, die durch Diskussion, kritische Hinweise und fördern- deAnregungenzumEntstehendesBuchesbeigetragen haben.Besonderer Dankgilt HerrnDr.RobertPlato,HerrnSimonAlbroscheitundFrauFriederikeDittberner,die dieVeröffentlichungermöglichtundgeförderthaben. Berlin/Zittau,Oktober2009 H.Friedrich F.Pietschmann Inhaltsverzeichnis Vorwort v 1 Grundlagen 1 1.1 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 MatrizenundDeterminanten . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2 Determinanten . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 QuadratischeMatrizen . . . . . . . . . . . . . . . . . . . . . 14 1.3 BetragundNormen . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.1 Betrag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.2 Vektor-undMatrixnormen . . . . . . . . . . . . . . . . . . . 23 1.4 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 NumerischesRechnenundFehler 29 2.1 Fehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.1 Fehlerarten . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.2 NumerischstabileundinstabileAlgorithmen . . . . . . . . . 30 2.2 Maschinenzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.1 Zahlendarstellungen . . . . . . . . . . . . . . . . . . . . . . 33 2.2.2 Rundung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.3 Unterlauf,Überlauf . . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Fehlerfortpflanzung . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.1 Maximalfehler . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.2 Fehlerquadratsumme . . . . . . . . . . . . . . . . . . . . . . 37 2.4 Konditionszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4.1 KonditionszahlenbeiFunktionen . . . . . . . . . . . . . . . 39 2.4.2 KonditionszahlenbeilinearenGleichungssystemen . . . . . . 40 2.5 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3 Iterationsverfahren 43 3.1 Iterationsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.1.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.1.2 Zwischenwertsatz. . . . . . . . . . . . . . . . . . . . . . . . 44 3.1.3 Iterationsverfahren . . . . . . . . . . . . . . . . . . . . . . . 44 3.1.4 Fixpunktsatz . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 AnschaulicheDeutungdesIterationsverfahrens . . . . . . . . . . . . 53 viii Inhaltsverzeichnis 3.3 Fehlerabschätzungen . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 AbbruchkriterienbeiIterationsverfahren . . . . . . . . . . . . . . . . 59 3.5 Konvergenzordnung . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.6 SpezielleIterationsverfahren . . . . . . . . . . . . . . . . . . . . . . 61 3.6.1 Bisektionsmethode . . . . . . . . . . . . . . . . . . . . . . . 61 3.6.2 Regulafalsi . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.6.3 NewtonschesIterationsverfahren . . . . . . . . . . . . . . . . 68 3.7 Konvergenzverbesserung . . . . . . . . . . . . . . . . . . . . . . . . 73 3.7.1 VerkleinernderLipschitzkonstanten . . . . . . . . . . . . . . 73 3.7.2 VerfahrenvonAitken . . . . . . . . . . . . . . . . . . . . . . 75 3.7.3 Steffensen-Verfahren . . . . . . . . . . . . . . . . . . . . . . 76 3.8 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4 LineareGleichungssysteme 80 4.1 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2 Eliminationsverfahren. . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2.1 GaußscherAlgorithmus . . . . . . . . . . . . . . . . . . . . 81 4.2.2 Pivotstrategie . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.2.3 Givens-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . 89 4.2.4 Cholesky-VerfahrenbeisymmetrischerKoeffizientenmatrix . 95 4.2.5 Nachiteration . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.2.6 BerechnungderinversenMatrix . . . . . . . . . . . . . . . . 101 4.2.7 AbschätzungderFehlerfortpflanzung . . . . . . . . . . . . . 104 4.3 Iterationsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.3.1 Gesamtschritt-oderJacobi-Verfahren . . . . . . . . . . . . . 107 4.3.2 AbbruchbeimGesamtschrittverfahren . . . . . . . . . . . . . 109 4.3.3 Einzelschritt-oderGauß-Seidel-Verfahren . . . . . . . . . . . 110 4.3.4 AbbruchbeimEinzelschrittverfahren . . . . . . . . . . . . . 110 4.3.5 KonvergenzbeimGesamtschrittverfahren . . . . . . . . . . . 111 4.3.6 KonvergenzbeimEinzelschrittverfahren . . . . . . . . . . . . 113 4.3.7 FehlerabschätzungbeiIterationsverfahren . . . . . . . . . . . 114 4.4 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5 ApproximationvonFunktionen 122 5.1 Problemstellungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.2 DiskreteApproximation . . . . . . . . . . . . . . . . . . . . . . . . 122 5.2.1 DieAusgleichsgeradenachderMethodederkleinstenQuadrate122 5.2.2 ApproximationdurchweitereFunktionen . . . . . . . . . . . 125 5.2.3 Linearisierungen . . . . . . . . . . . . . . . . . . . . . . . . 131 5.3 StetigeApproximation . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.3.1 Orthonormalsysteme . . . . . . . . . . . . . . . . . . . . . . 142 5.3.2 LegendreschePolynome . . . . . . . . . . . . . . . . . . . . 145 Inhaltsverzeichnis ix 5.3.3 ApproximationdurchtrigonometrischeFunktionen . . . . . . 148 5.3.4 DiekomplexeFormderFourier-Reihe . . . . . . . . . . . . . 156 5.4 LokaleApproximation . . . . . . . . . . . . . . . . . . . . . . . . . 162 5.4.1 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . 162 5.4.2 DieTaylor-Entwicklung . . . . . . . . . . . . . . . . . . . . 163 5.5 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 6 Interpolationsprobleme 173 6.1 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 6.2 Polynominterpolation . . . . . . . . . . . . . . . . . . . . . . . . . . 174 6.2.1 InterpolationsverfahrenvonLagrange . . . . . . . . . . . . . 175 6.2.2 DerFehlerderPolynominterpolation . . . . . . . . . . . . . 178 6.2.3 NewtonschesInterpolationsverfahren . . . . . . . . . . . . . 180 6.2.4 Hermite-Interpolation . . . . . . . . . . . . . . . . . . . . . 192 6.3 Splineinterpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 6.3.1 LineareSplines . . . . . . . . . . . . . . . . . . . . . . . . . 200 6.3.2 QuadratischeSplines . . . . . . . . . . . . . . . . . . . . . . 201 6.3.3 KubischeSplines . . . . . . . . . . . . . . . . . . . . . . . . 205 6.3.4 B-Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 6.4 InterpolationmitperiodischenFunktionen . . . . . . . . . . . . . . . 247 6.4.1 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . 247 6.4.2 DiediskreteFourier-Transformation . . . . . . . . . . . . . . 248 6.4.3 InterpolationmitkomplexenExponentialfunktionen . . . . . 261 6.4.4 InterpolationmittrigonometrischenFunktionen . . . . . . . . 264 6.4.5 SchnelleFourier-Transformation . . . . . . . . . . . . . . . . 270 6.5 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 7 NumerischeDifferentiation 288 7.1 Vorbemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 7.2 NumerischeBestimmungvonerstenAbleitungen . . . . . . . . . . . 289 7.3 Rundungsfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 7.4 NumerischeBestimmungvonhöherenAbleitungen . . . . . . . . . . 298 7.5 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 8 NumerischeIntegrationsmethoden 301 8.1 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 8.2 Trapezformel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 8.2.1 Herleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 8.2.2 AbbruchbedingungbeiderTrapezformel . . . . . . . . . . . 304 8.3 SimpsonscheFormel . . . . . . . . . . . . . . . . . . . . . . . . . . 307 8.3.1 Herleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 8.3.2 AbbruchbedingungbeiderSimpsonschenFormel . . . . . . . 311