Numerical Analysis

Numerical Analysis

Doron Levy

Department of Mathematics and

Center for Scientific Computation and Mathematical Modeling (CSCAMM) University of Maryland

March 4, 2008

D. Levy

Preface

i

D. Levy

CONTENTS

Contents

Preface

i

1 Introduction

1

2 Interpolation

2

2.1 What is Interpolation? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2 The Interpolation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 Newton's Form of the Interpolation Polynomial . . . . . . . . . . . . . . 5

2.4 The Interpolation Problem and the Vandermonde Determinant . . . . . . 6

2.5 The Lagrange Form of the Interpolation Polynomial . . . . . . . . . . . . 7

2.6 Divided Differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.7 The Error in Polynomial Interpolation . . . . . . . . . . . . . . . . . . . 12

2.8 Interpolation at the Chebyshev Points . . . . . . . . . . . . . . . . . . . 15

2.9 Hermite Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.9.1 Divided differences with repetitions . . . . . . . . . . . . . . . . . 23

2.9.2 The Lagrange form of the Hermite interpolant . . . . . . . . . . . 25

2.10 Spline Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.10.1 Cubic splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.10.2 What is natural about the natural spline? . . . . . . . . . . . . . 34

3 Approximations

36

3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2 The Minimax Approximation Problem . . . . . . . . . . . . . . . . . . . 41

3.2.1 Existence of the minimax polynomial . . . . . . . . . . . . . . . . 42

3.2.2 Bounds on the minimax error . . . . . . . . . . . . . . . . . . . . 43

3.2.3 Characterization of the minimax polynomial . . . . . . . . . . . . 44

3.2.4 Uniqueness of the minimax polynomial . . . . . . . . . . . . . . . 45

3.2.5 The near-minimax polynomial . . . . . . . . . . . . . . . . . . . . 46

3.2.6 Construction of the minimax polynomial . . . . . . . . . . . . . . 46

3.3 Least-squares Approximations . . . . . . . . . . . . . . . . . . . . . . . . 48

3.3.1 The least-squares approximation problem . . . . . . . . . . . . . . 48

3.3.2 Solving the least-squares problem: a direct method . . . . . . . . 48

3.3.3 Solving the least-squares problem: with orthogonal polynomials . 50

3.3.4 The weighted least squares problem . . . . . . . . . . . . . . . . . 52

3.3.5 Orthogonal polynomials . . . . . . . . . . . . . . . . . . . . . . . 53

3.3.6 Another approach to the least-squares problem . . . . . . . . . . 58

3.3.7 Properties of orthogonal polynomials . . . . . . . . . . . . . . . . 63

4 Numerical Differentiation

65

4.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.2 Differentiation Via Interpolation . . . . . . . . . . . . . . . . . . . . . . . 67

4.3 The Method of Undetermined Coefficients . . . . . . . . . . . . . . . . . 70

4.4 Richardson's Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . . 72

iii

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download