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 .. 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.

2 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 .. 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 .. Evaluation of multiple integrals .. Finite-Difference Approximations.

3 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 .. 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.

4 Classification of Linear PDEs .. BASIC Concept of Well Posedness .. Overview of Discretization Methods for PDEs .. Parabolic Equations .. Explicit Euler Method for the Heat Equation .. 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 .. Graphical ANALYSIS of fixed-point iteration: the divergent case .. Geometry of Newton s method.

5 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.. 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 ( ).

6 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 .. 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.

7 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.

8 We typically think of linear algebra as being associatedwith vectors and matrices in some finite-dimensional , in fact, most of our ideas extendquite naturally to the infinite-dimensional spaces frequently encountered in the study of partialdifferential begin with the BASIC notion oflinearitywhich is crucial to much of mathematical a vector space defined on the real numbersR(or the complex numbersC), and letLbe an operator (or transformation) whose domain isS. Suppose for anyu, v Sanda, b R(orC) we haveL(au+bv) =aLu+bLv.( )ThenLis said to be a linear of linear operators includeM Nmatrices, differential operators and integral is generally important to be able to distinguish linear and nonlinear operators because prob-lems involving only the former can often be solved without recourse to iterative procedures. This12 CHAPTER 1. NUMERICAL LINEAR ALGEBRAis seldom true for nonlinear problems, with the consequencethat corresponding algorithms mustbe more elaborate.

9 This will become apparent as we of the most fundamental properties of any object, be it mathematical or physical, is itssize. Of course, in NUMERICAL ANALYSIS we are always concerned with the size of the error in anyparticular NUMERICAL approximation, or COMPUTATIONAL procedure. There is a general mathematicalobject, called thenorm, by which we can assign a number corresponding to the size of variousmathematical a (finite- or infinite-dimensional) vector space, and letk kdenote themappingS R+ {0}with the following properties:i)kvk 0, v Swithkvk= 0iffv 0,ii)kavk=|a| kvk, v S,a R,iii)kv+wk kvk+kwk v, w kis called a normfor that we can takeSto be a space of vectors, functions or even operators, and theaboveproperties apply. It is important to observe that for a givenspaceSthere are, in general, manydifferent mappingsk khaving the properties required by the above definition.

10 We will give a fewspecific examples which are of particular importance in NUMERICAL linear a finite-dimensional space of vectors with elementsv= (v1, v2, .. , vN)Tthen a familiarmeasure of the size ofvis its Euclidean length,kvk2= NXi=1v2i!12.( )The proof thatk k2, often called theEuclidean norm, or simply the2-norm, satisfies the threeconditions of the definition is straightforward, and is leftto the reader. (We note here that it iscommon in NUMERICAL ANALYSIS to employ the subscriptEto denote this norm and use the subscript2 for the spectral norm of matrices. But we have chosen to defer to notation more consistentwith pure mathematics.) Another useful norm that we often encounter in practice is themax normorinfinity normdefined askvk = max1 i N|vi|.( )In the case of Euclidean spaces, we can define another useful object related to the Euclideannorm, theinner product(often called the dot product when applied to finite-dimensional vectors).