Transcription of LECTURES IN BASIC COMPUTATIONAL NUMERICAL ANALYSIS
1 J. M. McDonoughUniversity of Kentucky Lexington, KY 40506E-mail: = x [J( )] (x )(m)(m+1)(m)(m) 1D f = 0if fi+1i 12hy = (y,t) LECTURES IN BASIC COMPUTATIONALNUMERICAL ANALYSIS LECTURES IN BASIC COMPUTATIONALNUMERICAL ANALYSISLECTURES IN BASICCOMPUTATIONALNUMERICAL ANALYSISJ. M. McDonoughDepartments of Mechanical Engineering and MathematicsUniversity of Kentuckyc 1984, 1990, 1995, 2001, 2004, 2007 Contents1 NUMERICAL Linear Some BASIC Facts from Linear Algebra .. Solution of Linear Systems.
2 NUMERICAL solution of linear systems: direct elimination .. NUMERICAL solution of linear systems: iterative methods .. Summary of methods for solving linear systems .. The Algebraic Eigenvalue Problem .. The power method .. Inverse iteration with Rayleigh quotient shifts .. The QR algorithm .. Summary of methods for the algebraic eigenvalue problem .. Summary .. 322 Solution of Nonlinear Fixed-Point Methods for Single Nonlinear Equations .. BASIC fixed-point iteration .. Newton iteration.
3 Modifications to Newton s Method .. The secant method .. The method of false position .. Newton s Method for Systems of Equations .. Derivation of Newton s Method for Systems .. Pseudo-language algorithm for Newton s method for systems .. Summary .. 433 Approximation Approximation of Functions .. The method of least squares .. Lagrange interpolation polynomials .. Cubic spline interpolation .. Extraplotation .. NUMERICAL Quadrature .. BASIC Newton Cotes quadrature formulas .. Gauss Legendre quadrature.
4 Evaluation of multiple integrals .. Finite-Difference Approximations .. BASIC concepts .. Use of Taylor series .. Partial derivatives and derivatives of higher order .. Differentiation of interpolation polynomials .. Richardson Extrapolation Revisited .. COMPUTATIONAL Test for Grid Function Convergence .. Summary .. 764 NUMERICAL Solution of Initial-Value Problems .. Mathematical Background .. BASIC Single-Step Methods .. Runge Kutta Methods .. Multi-Step and Predictor-Corrector, Methods.
5 Solution of Stiff Equations .. Boundary-Value Problems for ODEs .. Mathematical Background .. Shooting Methods .. Finite-Difference Methods .. Singular and Nonlinear Boundary-Value Problems .. Coordinate Singularities .. Iterative Methods for Nonlinear BVPs .. The Galerkin Procedure .. Summary .. 1185 NUMERICAL Solution of Mathematical Introduction .. Classification of Linear PDEs .. BASIC Concept of Well Posedness .. Overview of Discretization Methods for PDEs .. Parabolic Equations .. Explicit Euler Method for the Heat Equation.
6 Backward-Euler Method for the Heat Equation .. Second-Order Approximations to the Heat Equation .. Peaceman Rachford Alternating-Direction-Implicit Scheme .. Elliptic Equations .. Successive Overrelaxation .. The Alternating-Direction-Implicit Scheme .. Hyperbolic Equations .. The Wave Equation .. First-Order Hyperbolic Equations and Systems .. Summary .. 159 References160 List of Sparse, band matrix .. Compactly-banded matrices: (a) tridiagonal, (b) pentadiagonal .. Graphical ANALYSIS of fixed-point iteration: the convergent case.
7 Graphical ANALYSIS of fixed-point iteration: the divergent case .. Geometry of Newton s method .. Newton s method applied toF(x) = tanhx.. Geometry of the secant method .. Geometry of regula falsi .. Least-squares curve fitting of experimental data .. Linear interpolation off(x, y):R2 R1.. Ill-behavior of high-order Lagrange polynomials .. Discontinuity of 1stderivative in local linear interpolation .. Geometry of Trapezoidal Rule .. Grid-point Indexing onhand 2hGrids .. Region of absolute stability for Euler s method appliedtou = u.
8 Forward-Euler solutions tou = u, <0 .. Comparison of round-off and truncation error .. Geometry of Runge Kutta methods .. Solution of a stiff system .. Region of absolute stability for backward-Euler method.. Geometric representation of the shooting method .. Finite-Difference grid for the interval [0,1] .. Matrix structure of discrete equations approximating ( ) .. Methods for spatial discretization of partial differential equations; (a) finite differ-ence, (b) finite element and (c) spectral.. Mesh star for forward-Euler method applied to heat equation.
9 Matrix structure for 2-D Crank Nicolson method.. Implementation of Peaceman Rachford ADI.. Matrix structure of centered discretization of Poisson/Dirichlet problem.. Analytical domain of dependence for the point (x, t).. NUMERICAL domain of dependence of the grid point (m, n+ 1).. Difference approximation satisfying CFL condition.. 156iiiChapter 1 NUMERICAL Linear AlgebraFrom a practical standpoint NUMERICAL linear algebra is without a doubt the single most importanttopic in NUMERICAL ANALYSIS . Nearly all other problems ultimately can be reduced to problems innumerical linear algebra; , solution of systems of ordinary differential equation initial valueproblems by implicit methods, solution of boundary value problems for ordinary and partial dif-ferential equations by any discrete approximation method,construction of splines, and solution ofsystems of nonlinear algebraic equations represent just a few of the applications of NUMERICAL linearalgebra.
10 Because of this prevalence of NUMERICAL linear algebra, we begin our treatment of basicnumerical methods with this topic, and note that this is somewhat this chapter we begin with discussion of some BASIC notations and definitions which will beof importance throughout these lectires, but especially soin the present chapter. Then we considerthe two main problems encountered in NUMERICAL linear algebra:i) solution of linear systems ofequations, andii) the algebraic eigenvalue problem. Much attention will be given to the first ofthese because of its wide applicability; all of the examplescited above involve this class of second, although very important, occurs less frequently, and we will provide only a Some BASIC Facts from Linear AlgebraBefore beginning our treatment of NUMERICAL solution of linear systems we will review a few im-portant facts from linear algebra, itself.
