Theoretical Numerical Analysis: A Functional Analysis Framework

Series Preface vii

Preface to the Second Edition ix

Preface to the First Edition xi

1 Linear Spaces 1

1.1 Linear spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Normed spaces . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.1 Convergence . . . . . . . . . . . . . . . . . . . . . . 10

1.2.2 Banach spaces . . . . . . . . . . . . . . . . . . . . . 13

1.2.3 Completion of normed spaces . . . . . . . . . . . . . 14

1.3 Inner product spaces . . . . . . . . . . . . . . . . . . . . . . 21

1.3.1 Hilbert spaces . . . . . . . . . . . . . . . . . . . . . . 26

1.3.2 Orthogonality . . . . . . . . . . . . . . . . . . . . . . 28

1.4 Spaces of continuously differentiable functions . . . . . . . 38

1.4.1 H¨older spaces . . . . . . . . . . . . . . . . . . . . . . 41

1.5 Lp spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

1.6 Compact sets . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2 Linear Operators on Normed Spaces 51

2.1 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

2.2 Continuous linear operators . . . . . . . . . . . . . . . . . . 55

2.2.1 L(V,W) as a Banach space . . . . . . . . . . . . . . 59

xiv Contents

2.3 The geometric series theorem and its variants . . . . . . . . 60

2.3.1 A generalization . . . . . . . . . . . . . . . . . . . . 64

2.3.2 A perturbation result . . . . . . . . . . . . . . . . . 66

2.4 Some more results on linear operators . . . . . . . . . . . . 71

2.4.1 An extension theorem . . . . . . . . . . . . . . . . . 72

2.4.2 Open mapping theorem . . . . . . . . . . . . . . . . 73

2.4.3 Principle of uniform boundedness . . . . . . . . . . . 75

2.4.4 Convergence of numerical quadratures . . . . . . . . 76

2.5 Linear functionals . . . . . . . . . . . . . . . . . . . . . . . 79

2.5.1 An extension theorem for linear functionals . . . . . 80

2.5.2 The Riesz representation theorem . . . . . . . . . . 82

2.6 Adjoint operators . . . . . . . . . . . . . . . . . . . . . . . . 85

2.7 Types of convergence . . . . . . . . . . . . . . . . . . . . . . 90

2.8 Compact linear operators . . . . . . . . . . . . . . . . . . . 93

2.8.1 Compact integral operators on C(D) . . . . . . . . . 94

2.8.2 Properties of compact operators . . . . . . . . . . . 95

2.8.3 Integral operators on L2(a, b) . . . . . . . . . . . . . 97

2.8.4 The Fredholm alternative theorem . . . . . . . . . . 99

2.8.5 Additional results on Fredholm integral equations . 103

2.9 The resolvent operator . . . . . . . . . . . . . . . . . . . . 107

2.9.1 R(λ) as a holomorphic function . . . . . . . . . . . . 108

3 Approximation Theory 113

3.1 Approximation of continuous functions by polynomials . . . 114

3.2 Interpolation theory . . . . . . . . . . . . . . . . . . . . . . 115

3.2.1 Lagrange polynomial interpolation . . . . . . . . . . 117

3.2.2 Hermite polynomial interpolation . . . . . . . . . . . 121

3.2.3 Piecewise polynomial interpolation . . . . . . . . . . 121

3.2.4 Trigonometric interpolation . . . . . . . . . . . . . . 124

3.3 Best approximation . . . . . . . . . . . . . . . . . . . . . . . 129

3.3.1 Convexity, lower semicontinuity . . . . . . . . . . . . 129

3.3.2 Some abstract existence results . . . . . . . . . . . . 131

3.3.3 Existence of best approximation . . . . . . . . . . . 134

3.3.4 Uniqueness of best approximation . . . . . . . . . . 136

3.4 Best approximations in inner product spaces, projection on

closed convex sets . . . . . . . . . . . . . . . . . . . . . . . . 139

3.5 Orthogonal polynomials . . . . . . . . . . . . . . . . . . . . 146

3.6 Projection operators . . . . . . . . . . . . . . . . . . . . . . 150

3.7 Uniform error bounds . . . . . . . . . . . . . . . . . . . . . 154

3.7.1 Uniform error bounds for L2-approximations . . . . 156

3.7.2 Interpolatory projections and their convergence . . . 158

4 Fourier Analysis and Wavelets 161

4.1 Fourier series . . . . . . . . . . . . . . . . . . . . . . . . . . 161

4.2 Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . 175

Contents xv

4.3 Discrete Fourier transform . . . . . . . . . . . . . . . . . . . 180

4.4 Haar wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . 185

4.5 Multiresolution analysis . . . . . . . . . . . . . . . . . . . . 193

5 Nonlinear Equations and Their Solution by Iteration 201

5.1 The Banach fixed-point theorem . . . . . . . . . . . . . . . 202

5.2 Applications to iterative methods . . . . . . . . . . . . . . . 206

5.2.1 Nonlinear equations . . . . . . . . . . . . . . . . . . 207

5.2.2 Linear systems . . . . . . . . . . . . . . . . . . . . . 208

5.2.3 Linear and nonlinear integral equations . . . . . . . 211

5.2.4 Ordinary differential equations in Banach spaces . . 215

5.3 Differential calculus for nonlinear operators . . . . . . . . . 219

5.3.1 Fr´echet and Gˆateaux derivatives . . . . . . . . . . . 219

5.3.2 Mean value theorems . . . . . . . . . . . . . . . . . . 223

5.3.3 Partial derivatives . . . . . . . . . . . . . . . . . . . 224

5.3.4 The Gˆateaux derivative and convex minimization . . 226

5.4 Newton’s method . . . . . . . . . . . . . . . . . . . . . . . . 230

5.4.1 Newton’s method in a Banach space . . . . . . . . . 230

5.4.2 Applications . . . . . . . . . . . . . . . . . . . . . . 233

5.5 Completely continuous vector fields . . . . . . . . . . . . . . 236

5.5.1 The rotation of a completely continuous vector field 238

5.6 Conjugate gradient method for operator equations . . . . . 239

6 Finite Difference Method 249

6.1 Finite difference approximations . . . . . . . . . . . . . . . 249

6.2 Lax equivalence theorem . . . . . . . . . . . . . . . . . . . . 256

6.3 More on convergence . . . . . . . . . . . . . . . . . . . . . . 265

7 Sobolev Spaces 273

7.1 Weak derivatives . . . . . . . . . . . . . . . . . . . . . . . . 273

7.2 Sobolev spaces . . . . . . . . . . . . . . . . . . . . . . . . . 279

7.2.1 Sobolev spaces of integer order . . . . . . . . . . . . 280

7.2.2 Sobolev spaces of real order . . . . . . . . . . . . . . 286

7.2.3 Sobolev spaces over boundaries . . . . . . . . . . . . 288

7.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

7.3.1 Approximation by smooth functions . . . . . . . . . 290

7.3.2 Extensions . . . . . . . . . . . . . . . . . . . . . . . 291

7.3.3 Sobolev embedding theorems . . . . . . . . . . . . . 291

7.3.4 Traces . . . . . . . . . . . . . . . . . . . . . . . . . . 293

7.3.5 Equivalent norms . . . . . . . . . . . . . . . . . . . . 294

7.3.6 A Sobolev quotient space . . . . . . . . . . . . . . . 298

7.4 Characterization of Sobolev spaces via the Fourier transform 303

7.5 Periodic Sobolev spaces . . . . . . . . . . . . . . . . . . . . 307

7.5.1 The dual space . . . . . . . . . . . . . . . . . . . . . 309

7.5.2 Embedding results . . . . . . . . . . . . . . . . . . . 310

xvi Contents

7.5.3 Approximation results . . . . . . . . . . . . . . . . . 311

7.5.4 An illustrative example of an operator . . . . . . . . 312

7.5.5 Spherical polynomials and spherical harmonics . . . 313

7.6 Integration by parts formulas . . . . . . . . . . . . . . . . . 319

8 Variational Formulations of Elliptic Boundary Value Problems

323

8.1 A model boundary value problem . . . . . . . . . . . . . . . 324

8.2 Some general results on existence and uniqueness . . . . . . 326

8.3 The Lax-Milgram Lemma . . . . . . . . . . . . . . . . . . . 330

8.4 Weak formulations of linear elliptic boundary value problems 334

8.4.1 Problems with homogeneous Dirichlet boundary conditions

. . . . . . . . . . . . . . . . . . . . . . . . . . 334

8.4.2 Problems with non-homogeneous Dirichlet boundary

conditions . . . . . . . . . . . . . . . . . . . . . . . . 335

8.4.3 Problems with Neumann boundary conditions . . . . 337

8.4.4 Problems with mixed boundary conditions . . . . . . 339

8.4.5 A general linear second-order elliptic boundary value

problem . . . . . . . . . . . . . . . . . . . . . . . . . 340

8.5 A boundary value problem of linearized elasticity . . . . . . 343

8.6 Mixed and dual formulations . . . . . . . . . . . . . . . . . 348

8.7 Generalized Lax-Milgram Lemma . . . . . . . . . . . . . . . 353

8.8 A nonlinear problem . . . . . . . . . . . . . . . . . . . . . . 355

9 The Galerkin Method and Its Variants 361

9.1 The Galerkin method . . . . . . . . . . . . . . . . . . . . . 361

9.2 The Petrov-Galerkin method . . . . . . . . . . . . . . . . . 367

9.3 Generalized Galerkin method . . . . . . . . . . . . . . . . . 370

9.4 Conjugate gradient method: variational formulation . . . . 372

10 Finite Element Analysis 377

10.1 One-dimensional examples . . . . . . . . . . . . . . . . . . . 379

10.1.1 Linear elements for a second-order problem . . . . . 379

10.1.2 High order elements and the condensation technique 382

10.1.3 Reference element technique, non-conforming method 384

10.2 Basics of the finite element method . . . . . . . . . . . . . . 387

10.2.1 Triangulation . . . . . . . . . . . . . . . . . . . . . . 387

10.2.2 Polynomial spaces on the reference elements . . . . . 389

10.2.3 Affine-equivalent finite elements . . . . . . . . . . . . 391

10.2.4 Finite element spaces . . . . . . . . . . . . . . . . . 392

10.2.5 Interpolation . . . . . . . . . . . . . . . . . . . . . . 395

10.3 Error estimates of finite element interpolations . . . . . . . 396

10.3.1 Interpolation error estimates on the reference element 397

10.3.2 Local interpolation error estimates . . . . . . . . . . 398

10.3.3 Global interpolation error estimates . . . . . . . . . 401

Contents xvii

10.4 Convergence and error estimates . . . . . . . . . . . . . . . 404

11 Elliptic Variational Inequalities and Their Numerical Approximations

413

11.1 Introductory examples . . . . . . . . . . . . . . . . . . . . . 413

11.2 Elliptic variational inequalities of the first kind . . . . . . . 420

11.3 Approximation of EVIs of the first kind . . . . . . . . . . . 425

11.4 Elliptic variational inequalities of the second kind . . . . . . 428

11.5 Approximation of EVIs of the second kind . . . . . . . . . . 434

11.5.1 Regularization technique . . . . . . . . . . . . . . . . 436

11.5.2 Method of Lagrangian multipliers . . . . . . . . . . . 438

11.5.3 Method of numerical integration . . . . . . . . . . . 440

12 Numerical Solution of Fredholm Integral Equations of the

Second Kind 447

12.1 Projection methods: General theory . . . . . . . . . . . . . 448

12.1.1 Collocation methods . . . . . . . . . . . . . . . . . . 448

12.1.2 Galerkin methods . . . . . . . . . . . . . . . . . . . 450

12.1.3 A general theoretical framework . . . . . . . . . . . 451

12.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

12.2.1 Piecewise linear collocation . . . . . . . . . . . . . . 457

12.2.2 Trigonometric polynomial collocation . . . . . . . . 459

12.2.3 A piecewise linear Galerkin method . . . . . . . . . 461

12.2.4 A Galerkin method with trigonometric polynomials . 463

12.3 Iterated projection methods . . . . . . . . . . . . . . . . . . 468

12.3.1 The iterated Galerkin method . . . . . . . . . . . . . 470

12.3.2 The iterated collocation solution . . . . . . . . . . . 472

12.4 The Nystr¨om method . . . . . . . . . . . . . . . . . . . . . 478

12.4.1 The Nystr¨om method for continuous kernel functions 478

12.4.2 Properties and error analysis of the Nystr¨om method 481

12.4.3 Collectively compact operator approximations . . . . 489

12.5 Product integration . . . . . . . . . . . . . . . . . . . . . . . 492

12.5.1 Error analysis . . . . . . . . . . . . . . . . . . . . . . 494

12.5.2 Generalizations to other kernel functions . . . . . . . 496

12.5.3 Improved error results for special kernels . . . . . . . 498

12.5.4 Product integration with graded meshes . . . . . . . 498

12.5.5 The relationship of product integration and collocation

methods . . . . . . . . . . . . . . . . . . . . . . 503

12.6 Iteration methods . . . . . . . . . . . . . . . . . . . . . . . . 504

12.6.1 A two-grid iteration method for the Nystr¨om method 505

12.6.2 Convergence analysis . . . . . . . . . . . . . . . . . . 508

12.6.3 The iteration method for the linear system . . . . . 511

12.6.4 An operations count . . . . . . . . . . . . . . . . . . 513

12.7 Projection methods for nonlinear equations . . . . . . . . . 515

12.7.1 Linearization . . . . . . . . . . . . . . . . . . . . . . 515

xviii Contents

12.7.2 A homotopy argument . . . . . . . . . . . . . . . . . 518

12.7.3 The approximating finite-dimensional problem . . . 520

13 Boundary Integral Equations 523

13.1 Boundary integral equations . . . . . . . . . . . . . . . . . 524

13.1.1 Green’s identities and representation formula . . . . 525

13.1.2 The Kelvin transformation and exterior problems . 527

13.1.3 Boundary integral equations of direct type . . . . . 531

13.2 Boundary integral equations of the second kind . . . . . . . 537

13.2.1 Evaluation of the double layer potential . . . . . . . 540

13.2.2 The exterior Neumann problem . . . . . . . . . . . 543

13.3 A boundary integral equation of the first kind . . . . . . . 549

13.3.1 A numerical method . . . . . . . . . . . . . . . . . . 551

References 555

Index 569