Numerik-Algorithmen - Verfahren, Beispiele, Anwendungen

von: Gisela Engeln-Müllges, Klaus Niederdrenk, Reinhard Wodicka

Springer-Verlag, 2010

ISBN: 9783642134739 , 756 Seiten

10. Auflage

Format: PDF

Kopierschutz: Wasserzeichen

Windows PC,Mac OSX Apple iPad, Android Tablet PC's

Preis: 42,25 EUR

Mehr zum Inhalt

Numerik-Algorithmen - Verfahren, Beispiele, Anwendungen


 

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