Numerical mathematics

Title:

Author:

Quarteroni, Alfio

ISBN:

9780387989594

Personal Author:

Quarteroni, Alfio

Publication Information:

New York : Springer Verlag , 2000.

Physical Description:

645 s. ; 24 sm.

Series:

Texts in Applied Mathematics; 37

Series Title:

Texts in Applied Mathematics; 37

Abstract:

NUMERİCAL MATHEMATİCS Quarteroni-Sacco-Saleri Contents Series Preface v Preface vii PART I: Getting Started 1. Foundations of Matrix Analysis 1 1.1 Vector Spaces ......................... 1 1.2 Matrices ............................ 3 1.3 Operations with Matrices ................... 5 1.3.1 Inverse of a Matrix .................. 6 1.3.2 Matrices and Linear Mappings ........... 7 1.3.3 Operations with Block-Partitioned Matrices .... 7 1.4 Trace and Determinant of a Matrix ............. 8 1.5 Rank and Kernel of a Matrix ................ 9 1.6 Special Matrices ........................ 10 1.6.1 Block Diagonal Matrices ............... 10 1.6.2 Trapezoidal and Triangular Matrices ........ 11 1.6.3 Banded Matrices ................... 11 1.7 Eigenvalues and Eigenvectors ................ 12 1.8 Similarity Transformations .................. 14 1.9 The Singular Value Decomposition (SVD) ......... 16 1.10 Scalar Product and Norms in Vector Spaces ........ 17 1.11 Matrix Norms ......................... 21 1.11.1 Relation Between Norms and the Spectral Radius of a Matrix ............. 25 1.11.2 Sequences and Series of Matrices .......... 26 1.12 Positive Definite, Diagonally Dominant and M-Matrices . 27 1.13 Exercises ............................ 30 2. Principles of Numerical Mathematics 33 2.1 Well-Posedness and Condition Number of a Problem ... 33 2.2 Stability of Numerical Methods ............... 37 2.2.1 Relations Between Stability and Convergence ... 40 2.3 A priori and a posteriori Analysis .............. 41 2.4 Sources of Error in Computational Models ......... 43 2.5 Machine Representation of Numbers ............ 45 2.5.1 The Positional System ................ 45 2.5.2 The Floating-Point Number System ........ 46 2.5.3 Distribution of Floating-Point Numbers ...... 49 2.5.4 IEC/IEEE Arithmetic ................ 49 2.5.5 Rounding of a Real Number in Its Machine Representation ............... 50 2.5.6 Machine Floating-Point Operations ......... 52 2.6 Exercises ............................ 54 PART II: Numerical Linear Algebra 3. Direct Methods for the Solution of Linear Systems 57 3.1 Stability Analysis of Linear Systems ............ 58 3.1.1 The Condition Number of a Matrix ........ 58 3.1.2 Forward a priori Analysis .............. 60 3.1.3 Backward a priori Analysis ............. 63 3.1.4 A posteriori Analysis ................. 64 3.2 Solution of Triangular Systems ............... 65 3.2.1 Implementation of Substitution Methods ..... 65 3.2.2 Rounding Error Analysis ................ 67 3.2.3 Inverse of a Triangular Matrix ........... 67 3.3 The Gaussian Elimination Method (GEM) and LU Factorization ....................... 68 3.3.1 GEM as a Factorization Method .......... 72 3.3.2 The Effect of Rounding Errors ........... 76 3.3.3 Implementation of LU Factorization ........ 77 3.3.4 Compact Forms of Factorization .......... 78 3.4 Other Types of Factorization ................. 79 3.4.1 LDMT Factorization ................. 79 3.4.2 Symmetric and Positive Definite Matrices: The Cholesky Factorization ............. 80 3.4.3 Rectangular Matrices: The QR Factorization ... 82 3.5 Pivoting ............................ 85 3.6 Computing the Inverse of a Matrix ............. 89 3.7 Banded Systems ........................ 90 3.7.1 Tridiagonal Matrices ................. 91 3.7.2 Implementation Issues ................ 92 3.8 Block Systems ......................... 93 3.8.1 Block LU Factorization ............... 94 3.8.2 Inverse of a Block-Partitioned Matrix ....... 95 3.8.3 Block Tridiagonal Systems .............. 95 3.9 Sparse Matrices ........................ 97 3.9.1 The Cuthill-McKee Algorithm ........... 98 3.9.2 Decomposition into Substructures ......... 100 3.9.3 Nested Dissection ................... 103 3.10 Accuracy of the Solution Achieved Using GEM ...... 103 3.11 An Approximate Computation of K(A) ........... 106 3.12 Improving the Accuracy of GEM .............. 109 3.12.1 Scaling ........................ 110 3.12.2 Iterative Refinement ................. Ill 3.13 Undetermined Systems .................... 112 3.14 Applications .......................... 115 3.14.1 Nodal Analysis of a Structured Frame ....... 115 3.14.2 Regularization of a Triangular Grid ........ 118 3.15 Exercises ............................ 121 4. Iterative Methods for Solving Linear Systems 123 4.1 On the Convergence of Iterative Methods .......... 123 4.2 Linear Iterative Methods ................... 126 4.2.1 Jacobi, Gauss-Seidel and Relaxation Methods . . . 127 4.2.2 Convergence Results for Jacobi and Gauss-Seidel Methods ................ 129 4.2.3 Convergence Results for the Relaxation Method . 131 4.2.4 A priori Forward Analysis .............. 132 4.2.5 Block Matrices .................... 133 4.2.6 Symmetric Form of the Gauss-Seidel and SOR Methods ..................... 133 4.2.7 Implementation Issues ................ 135 4.3 Stationary and Nonstationary Iterative Methods ...... 136 4.3.1 Convergence Analysis of the Richardson Method . 137 4.3.2 Preconditioning Matrices .............. 139 4.3.3 The Gradient Method ................ 146 4.3.4 The Conjugate Gradient Method .......... 150 4.3.5 The Preconditioned Conjugate Gradient Method . 156 4.3.6 The Alternating-Direction Method ......... 158 4.4 Methods Based on Krylov Subspace Iterations ....... 159 4.4.1 The Arnold! Method for Linear Systems ...... 162 4.4.2 The GMRES Method ................ 165 4.4.3 The Lanczos Method for Symmetric Systems . . . 167 4.5 The Lanczos Method for Unsymmetric Systems ...... 168 4.6 Stopping Criteria ....................... 171 4.6.1 A Stopping Test Based on the Increment ..... 172 4.6.2 A Stopping Test Based on the Residual ...... 174 4.7 Applications .......................... 174 4.7.1 Analysis of an Electric Network . .......... 174 4.7.2 Finite Difference Analysis of Beam Bending .... 177 4.8 Exercises ............................ 179 Approximation of Eigenvalues and Eigenvectors 183 5.1 Geometrical Location of the Eigenvalues .......... 183 5.2 Stability and Conditioning Analysis ............. 186 5.2.1 A priori Estimates .................. 186 5.2.2 A posteriori Estimates ................ 190 5.3 The Power Method ...................... 192 5.3.1 Approximation of the Eigenvalue of Largest Module .................... 192 5.3.2 Inverse Iteration ................... 195 5.3.3 Implementation Issues ................ 196 5.4 The QR Iteration ....................... 200 5.5 The Basic QR Iteration .................... 201 5.6 The QR Method for Matrices in Hessenberg Form ..... 203 5.6.1 Householder and Givens Transformation Matrices 204 5.6.2 Reducing a Matrix in Hessenberg Form ...... 207 5.6.3 QR Factorization of a Matrix in Hessenberg Form 209 5.6.4 The Basic QR Iteration Starting from Upper Hessenberg Form ............... 210 5.6.5 Implementation of Transformation Matrices .... 212 5.7 The QR Iteration with Shifting Techniques .........

215 5.7.1 The QR Method with Single Shift ......... 215 5.7.2 The QR Method with Double Shift ......... 218 5.8 Computing the Eigenvectors and the SVD of a Matrix . . 221 5.8.1 The Hessenberg Inverse Iteration .......... 221 5.8.2 Computing the Eigenvectors from the Schur Form of a Matrix ............... 221 5.8.3 Approximate Computation of the SVD of a Matrix 222 5.9 The Generalized Eigenvalue Problem ............ 224 5.9.1 Computing the Generalized Real Schur Form . . . 225 5.9.2 Generalized Real Schur Form of Symmetric-Definite Pencils ............. 226 5.10 Methods for Eigenvalues of Symmetric Matrices ...... 227 5.10.1 The Jacobi Method ................. 227 5.10.2 The Method of Sturm Sequences .......... 230 5.11 The Lanczos Method ..................... 233 5.12 Applications .......................... 235 5.12.1 Analysis of the Buckling of a Beam ......... 236 5.12.2 Free Dynamic Vibration of a Bridge ........ 238 5.13 Exercises ............................ 240 PART III: Around Functions and Punctionals 6. Rootfinding for Nonlinear Equations 245 6.1 Conditioning of a Nonlinear Equation ............ 246 6.2 A Geometric Approach to Rootfinding ........... 248 6.2.1 The Bisection Method ................ 248 6.2.2 The Methods of Chord, Secant and Regula Falsi and Newton’s Method ................ 251 6.2.3 The Dekker-Brent Method ............. 256 6.3 Fixed-Point Iterations for Nonlinear Equations ....... 257 6.3.1 Convergence Results for Some Fixed-Point Methods ............. 260 6.4 Zeros of Algebraic Equations ................. 261 6.4.1 The Horner Method and Deflation ......... 262 6.4.2 The Newton-Horner Method ............ 263 6.4.3 The Muller Method ................. 267 6.5 Stopping Criteria ....................... 269 6.6 Post-Processing Techniques for Iterative Methods ..... 272 6.6.1 Aitken’s Acceleration ................ 272 6.6.2 Techniques for Multiple Roots ........... 275 6.7 Applications .......................... 276 6.7.1 Analysis of the State Equation for a Real Gas . . 276 6.7.2 Analysis of a Nonlinear Electrical Circuit ..... 277 6.8 Exercises ............................ 279 7. Nonlinear Systems and Numerical Optimization 281 7.1 Solution of Systems of Nonlinear Equations ........ 282 7.1.1 Newton’s Method and Its Variants .......... 283 7.1.2 Modified Newton’s Methods ............. 284 7.1.3 Quasi-Newton Methods ............... 288 7.1.4 Secant-Like Methods ................. 288 7.1.5 Fixed-Point Methods ................. 290 7.2 Unconstrained Optimization ................. 294 7.2.1 Direct Search Methods ................ 295 7.2.2 Descent Methods ................... 300 7.2.3 Line Search Techniques ............... 302 7.2.4 Descent Methods for Quadratic Functions ..... 304 7.2.5 Newton-Like Methods for Function Minimization . 307 7.2.6 Quasi-Newton Methods ............... 308 7.2.7 Secant-Like Methods ................. 309 7.3 Constrained Optimization .................. 311 7.3.1 Kuhn-Tucker Necessary Conditions for Nonlinear Programming ............... 313 7.3.2 The Penalty Method ................. 315 7.3.3 The Method of Lagrange Multipliers ........ 317 7.4 Applications .......................... 319 7.4.1 Solution of a Nonlinear System Arising from Semiconductor Device Simulation .......... 320 7.4.2 Nonlinear Regularization of a Discretization Grid . 323 7.5 Exercises ............................ 325 8. Polynomial Interpolation 327 8.1 Polynomial Interpolation ................... 328 8.1.1 The Interpolation Error ............... 329 8.1.2 Drawbacks of Polynomial Interpolation on Equally Spaced Nodes and Runge’s Counterexample .... 330 8.1.3 Stability of Polynomial Interpolation ........ 332 8.2 Newton Form of the Interpolating Polynomial ....... 333 8.2.1 Some Properties of Newton Divided Differences . . 335 8.2.2 The Interpolation Error Using Divided Differences 337 8.3 Piecewise Lagrange Interpolation .............. 338 8.4 Hermite-Birkoff Interpolation ................ 341 8.5 Extension to the Two-Dimensional Case .......... 343 8.5.1 Polynomial Interpolation .............. 343 8.5.2 Piecewise Polynomial Interpolation ......... 344 8.6 Approximation by Splines .................. 348 8.6.1 Interpolatory Cubic Splines ............. 349 8.6.2 B-Splines ....................... 353 8.7 Splines in Parametric Form ................. 357 8.7.1 Bezier Curves and Parametric B-Splines ...... 359 8.8 Applications .......................... 362 8.8.1 Finite Element Analysis of a Clamped Beam . . . 363 8.8.2 Geometric Reconstruction Based on Computer Tomographies ............... 366 8.9 Exercises ............................ 368 9. Numerical Integration 371 9.1 Quadrature Formulae ..................... 371 9.2 Interpolatory Quadratures .................. 373 9.2.1 The Midpoint or Rectangle Formula ........ 373 9.2.2 The Trapezoidal Formula .............. 375 9.2.3 The Cavalieri-Simpson Formula ........... 377 9.3 Newton-Cotes Formulae ................... 378 9.4 Composite Newton-Cotes Formulae ............. 383 9.5 Hermite Quadrature Formulae ................ 386 9.6 Richardson Extrapolation .................. 387 9.6.1 Romberg Integration ................. 389 9.7 Automatic Integration .................... 391 9.7.1 Non Adaptive Integration Algorithms ....... 392 9.7.2 Adaptive Integration Algorithms .......... 394 9.8 Singular Integrals ....................... 398 9.8.1 Integrals of Functions with Finite Jump Discontinuities ................. 398 9.8.2 Integrals of Infinite Functions ............ 398 9.8.3 Integrals over Unbounded Intervals ......... 401 9.9 Multidimensional Numerical Integration .......... 402 9.9.1 The Method of Reduction Formula ......... 403 9.9.2 Two-Dimensional Composite Quadratures ..... 404 9.9.3 Monte Carlo Methods for Numerical Integration ................ 407 9.10 Applications .......................... 408 9.10.1 Computation of an Ellipsoid Surface ........ 408 9.10.2 Computation of the Wind Action on a Sailboat Mast ..................... 410 9.11 Exercises ............................ 412 PART IV: Transforms, Differentiation and Problem Discretization 10. Orthogonal Polynomials in Approximation Theory 415 10.1 Approximation of Functions by Generalized Fourier Series 415 10.1.1 The Chebyshev Polynomials ............. 417 10.1.2 The Legendre Polynomials ............. 419 10.2 Gaussian Integration and Interpolation ........... 419 10.3 Chebyshev Integration and Interpolation .......... 424 10.4 Legendre Integration and Interpolation ........... 426 10.5 Gaussian Integration over Unbounded Intervals ...... 428 10.6 Programs for the Implementation of Gaussian Quadratures 429 10.7 Approximation of a Function in the Least-Squares Sense . 431 10.7.1 Discrete Least-Squares Approximation ....... 431 10.8 The Polynomial of Best Approximation ........... 433 10.9 Fourier Trigonometric Polynomials ............. 435 10.9.1 The Gibbs Phenomenon ............... 439 10.9.2 The Fast Fourier Transform .............

440 10.10 Approximation of Function Derivatives ........... 442 10.10.1 Classical Finite Difference Methods ......... 442 10.10.2 Compact Finite Differences ............. 444 10.10.3 Pseudo-Spectral Derivative ............. 448 10.11 Transforms and Their Applications ............. 450 10.11.1 The Fourier Transform ................ 450 10.11.2 (Physical) Linear Systems and Fourier Transform . 453 10.11.3 The Laplace Transform ............... 455 10.11.4 The Z-Transform ................... 457 10.12 The Wavelet Transform .................... 458 10.12.1 The Continuous Wavelet Transform ........ 458 10.12.2 Discrete and Orthonormal Wavelets ........ 461 10.13 Applications .......................... 463 10.13.1 Numerical Computation of Blackbody Radiation . 463 10.13.2 Numerical Solution of Schrödinger Equation . . . . 464 10.14 Exercises ............................ 467 11. Numerical Solution of Ordinary Differential Equations 469 11.1 The Cauchy Problem ..................... 469 11.2 One-Step Numerical Methods ................ 472 11.3 Analysis of One-Step Methods ................ 473 11.3.1 The Zero-Stability .................. 475 11.3.2 Convergence Analysis ................ 477 11.3.3 The Absolute Stability ................ 479 11.4 Difference Equations ..................... 482 11.5 Multistep Methods ...................... 487 11.5.1 Adams Methods ................... 490 11.5.2 BDF Methods .................... 492 11.6 Analysis of Multistep Methods . ............... 492 11.6.1 Consistency ...................... 493 11.6.2 The Root Conditions ................. 494 11.6.3 Stability and Convergence Analysis for Multistep Methods .................. 495 11.6.4 Absolute Stability of Multistep Methods . ..... 499 11.7 Predictor-Corrector Methods ................. 502 11.8 Runge-Kutta Methods .................... 508 11.8.1 Derivation of an Explicit RK Method ....... 511 11.8.2 Stepsize Adaptivity for RK Methods ........ 512 11.8.3 Implicit RK Methods ................ 514 11.8.4 Regions of Absolute Stability for RK Methods .. 516 11.9 Systems of ODEs ....................... 517 11.10 Stiff Problems ......................... 519 11.11 Applications .......................... 521 11.11.1 Analysis of the Motion of a Frictionless Pendulum 522 11.11.2 Compliance of Arterial Walls ............ 523 11.12 Exercises ............................ 527 12. Two-Point Boundary Value Problems 531 12.1 A Model Problem ....................... 531 12.2 Finite Difference Approximation ............... 533 12.2.1 Stability Analysis by the Energy Method ..... 534 12.2.2 Convergence Analysis ................ 538 12.2.3 Finite Differences for Two-Point Boundary Value Problems with Variable Coefficients ..... 540 12.3 The Spectral Collocation Method .............. 542 12.4 The Galerkin Method ..................... 544 12.4.1 Integral Formulation of Boundary-Value Problems 544 12.4.2 A Quick Introduction to Distributions ....... 546 12.4.3 Formulation and Properties of the ’ - Galerkin Method ................... 547 12.4.4 Analysis of the Galerkin Method .......... 548 12.4.5 The Finite Element Method ............. 550 12.4.6 Implementation Issues ................ 556 12.4.7 Spectral Methods ................... 559 12.5 Advection-Diffusion Equations ................ 560 12.5.1 Galerkin Finite Element Approximation ...... 561 12.5.2 The Relationship Between Finite Elements and Finite Differences; the Numerical Viscosity .... 563 12.5.3 Stabilized Finite Element Methods ......... 567 12.6 A Quick Glance to the Two-Dimensional Case ....... 572 12.7 Applications .......................... 575 12.7.1 Lubrication of a Slider ................ 575 12.7.2 Vertical Distribution of Spore Concentration over Wide Regions .......... 576 12.8 Exercises ............................ 578 13. Parabolic and Hyperbolic Initial Boundary Value Problems 581 13.1 The Heat Equation ...................... 581 13.2 Finite Difference Approximation of the Heat Equation . . 584 13.3 Finite Element Approximation of the Heat Equation . . . 586 13.3.1 Stability Analysis of the 0-Method ......... 588 13.4 Space-Time Finite Element Methods for the . - Heat Equation ......................... 593 13.5 Hyperbolic Equations: A Scalar Transport Problem .... 597 13.6 Systems of Linear Hyperbolic Equations .......... 599 13.6.1 The Wave Equation ................. 601 13.7 The Finite Difference Method for Hyperbolic Equations . . 602 13.7.1 Discretization of the Scalar Equation ........ 602 13.8 Analysis of Finite Difference Methods ............ 605 13.8.1 Consistency ...................... 605 13.8.2 Stability ........................ 605 13.8.3 The CFL Condition ................. 606 13.8.4 Von Neumann Stability Analysis .......... 608 13.9 Dissipation and Dispersion .................. 611 13.9.1 Equivalent Equations ................ 614 13.10 Finite Element Approximation of Hyperbolic Equations . . 618 13.10.1 Space Discretization with Continuous and Discontinuous Finite Elements ........... 618 13.10.2 Time Discretization ................. 620 13.11 Applications .......................... 623 13.11.1 Heat Conduction in a Bar .............. 623 13.11.2 A Hyperbolic Model for Blood Flow Interaction with Arterial Walls ........... 623 13.12 Exercises ............................ 625 References 627 Index of MATLAB Programs 643 Index 647

Subject Term:

Matematik

Available:*

Library	Material Type	Item Barcode	Shelf Number	Status
Searching... Ferit Melen Library	Book	049577	519.4 QUAn 2000 k.1	Searching... Unknown

Available:*

On Order