Wavelet methods are by now a well-known tool in image processing (jpeg2000). These functions have been used successfully in other areas, however. Elliptic Partial Differential Equations which model several processes in, for example, science and engineering, is one such field. This book, based on the author's course, gives an introduction to wavelet methods in general and then describes their application for the numerical solution of elliptic partial differential equations. Recently developed adaptive methods are also covered and each scheme is complemented with numerical results , exercises, and corresponding software.
Author(s): Karsten Urban
Series: Numerical Mathematics and Scientific Computation
Publisher: Oxford University Press, USA
Year: 2009
Language: English
Pages: 509
Contents......Page 8
List of Algorithms......Page 13
Preface......Page 14
Acknowledgements......Page 16
List of Figures......Page 18
List of Tables......Page 27
1.1 Some aspects of the history of wavelets......Page 30
1.2 The scope of this book......Page 33
1.3 Outline......Page 35
2.1.1 Projection by interpolation......Page 38
2.1.2 Orthogonal projection......Page 41
2.2 Piecewise linear systems......Page 46
2.3.1 Stability......Page 53
2.3.2 Refinement relation......Page 54
2.3.3 Multiresolution......Page 55
2.3.4 Locality......Page 56
2.4 Multiresolution analysis on the real line......Page 57
2.4.1 The scaling function......Page 58
2.4.2 When does a mask define a refinable function?......Page 59
2.4.3 Consequences of the refinability......Page 60
2.5 Daubechies orthonormal scaling functions......Page 64
2.6 B-splines......Page 66
2.6.1 Centralized B-splines......Page 67
2.7 Dual scaling functions associated to B-splines......Page 68
2.8 Multilevel projectors......Page 72
2.9.1 A general framework......Page 75
2.9.2 Stability properties......Page 77
2.9.3 Error estimates......Page 78
2.10 Plotting scaling functions......Page 79
2.10.1 Subdivision......Page 80
2.10.2 Cascade algorithm......Page 84
2.11 Periodization......Page 86
2.12 Exercises and programs......Page 87
3.1 A model problem......Page 92
3.1.1 Variational formulation......Page 93
3.1.2 Existence and uniqueness......Page 97
3.2 Variational formulation......Page 99
3.2.1 Operators associated by the bilinear form......Page 103
3.2.3 Stability......Page 104
3.3 Regularity theory......Page 105
3.4.1 Discretization......Page 106
3.4.3 Error estimates......Page 107
3.4.4 L[sub(2)]-estimates......Page 111
3.4.5 Numerical solution......Page 112
3.5 Exercises and programs......Page 114
4.1 Multiscale discretization......Page 116
4.2.1 Piecewise linear multiresolution......Page 118
4.2.2 Periodic boundary value problems......Page 119
4.2.3 Common properties......Page 123
4.3 Error estimates......Page 124
4.4 Some numerical examples......Page 125
4.5 Setup of the algebraic system......Page 126
4.5.1 Refinable integrals......Page 127
4.5.3 Quadrature......Page 130
4.6 The BPX preconditioner......Page 131
4.7 MultiGrid......Page 133
4.8 Numerical examples for the model problem......Page 137
4.9 Exercises and programs......Page 144
5.1.1 Updating......Page 149
5.1.2 The Haar system again......Page 150
5.2.1 Multilevel decomposition......Page 153
5.2.2 The construction of wavelets......Page 155
5.2.3 Wavelet projectors......Page 158
5.3 Biorthogonal wavelets......Page 160
5.3.1 Biorthogonal complement spaces......Page 161
5.3.2 Biorthogonal projectors......Page 162
5.4 Fast Wavelet Transform (FWT)......Page 163
5.4.1 Decomposition......Page 170
5.4.2 Reconstruction......Page 172
5.4.4 A general framework......Page 174
5.5 Vanishing moments and compression......Page 176
5.6 Norm equivalences......Page 179
5.6.1 Jackson inequality......Page 180
5.6.3 A characterization theorem......Page 181
5.7 Other kinds of wavelets......Page 185
5.7.1 Interpolatory wavelets......Page 186
5.7.2 Semiorthogonal wavelets......Page 190
5.7.3 Noncompactly supported wavelets......Page 192
5.7.4 Multiwavelets......Page 193
5.7.6 Curvelets......Page 195
5.8 Exercises and programs......Page 196
6.1 Wavelet preconditioning......Page 199
6.2 The role of the FWT......Page 204
6.3.1 Rate of convergence......Page 206
6.3.2 Compression......Page 210
6.4 Exercises and programs......Page 213
7.1 Adaptive approximation of functions......Page 215
7.1.1 Best N-term approximation......Page 216
7.1.2 The size and decay of the wavelet coefficients......Page 219
7.2 A posteriori error estimates and adaptivity......Page 220
7.2.1 A posteriori error estimates......Page 221
7.2.2 Ad hoc refinement strategies......Page 223
7.3 Infinite-dimensional iterations......Page 229
7.4 An equivalent l[sub(2)] problem: Using wavelets......Page 232
7.5 Compressible matrices......Page 234
7.5.1 Numerical realization of APPLY......Page 244
7.5.2 Numerical experiments for APPLY......Page 245
7.6.1 Adaptive Wavelet-Richardson method......Page 250
7.6.2 Adaptive scheme with inner iteration......Page 253
7.6.3 Optimality......Page 255
7.7.1 Quantitative aspects of the efficiency......Page 261
7.7.2 An efficient modified scheme: Ad hoc strategy revisited......Page 263
7.8 Nonlinear problems......Page 267
7.8.1 Nonlinear variational problems......Page 268
7.8.2 The DSX algorithm......Page 270
7.8.3 Prediction......Page 272
7.8.4 Reconstruction......Page 275
7.8.5 Quasi-interpolation......Page 278
7.8.6 Decomposition......Page 281
7.9 Exercises and programs......Page 283
8 Wavelets on general domains......Page 286
8.1 Multiresolution on the interval......Page 287
8.1.1 Refinement matrices......Page 289
8.1.2 Boundary scaling functions......Page 291
8.1.3 Biorthogonal multiresolution......Page 300
8.1.4 Refinement matrices......Page 313
8.1.5 Boundary conditions......Page 316
8.1.6 Symmetry......Page 320
8.2.1 Stable completion......Page 321
8.2.2 Spline-wavelets on the interval......Page 326
8.2.3 Further examples......Page 333
8.2.4 Dirichlet boundary conditions......Page 336
8.2.5 Quantitative aspects......Page 352
8.2.6 Other constructions on the interval......Page 354
8.2.7 Software for wavelets on the interval......Page 356
8.2.8 Numerical experiments......Page 357
8.3 Tensor product wavelets......Page 364
8.4 The Wavelet Element Method (WEM)......Page 371
8.4.1 Matching in 1D......Page 373
8.4.2 The setting in arbitrary dimension......Page 386
8.4.3 The WEM in the two-dimensional case......Page 401
8.4.4 Trivariate matched wavelets......Page 415
8.4.5 Software for the WEM......Page 416
8.5 Embedding methods......Page 419
8.6 Exercises and programs......Page 420
9.1.1 Numerical realization of the WEM......Page 423
9.1.2 Model problem on the L-shaped domain......Page 424
9.2.1 Influence of the mapping – A non-rectangular domain......Page 430
9.2.2 Influence of the matching......Page 432
9.2.3 Comparison of the different adaptive methods......Page 435
9.3 Saddle point problems......Page 436
9.3.1 The standard Galerkin discretization: The LBB condition......Page 438
9.3.2 An equivalent ℓ[sub(2)] problem......Page 439
9.3.3 The adaptive wavelet method: Convergence without LBB......Page 441
9.4.1 Formulation......Page 446
9.4.2 Discretization......Page 447
9.4.3 B-spline wavelets and the exact application of the divergence......Page 448
9.4.4 Bounded domains......Page 452
9.4.5 The divergence operator......Page 454
9.4.6 Compressibility of A and B[sup(T)]......Page 456
9.4.7 Numerical experiments......Page 457
9.4.8 Rate of convergence......Page 458
9.5 Exercises and programs......Page 463
A.1 Weak derivatives and sobolev spaces with integer order......Page 466
A.2 Sobolev spaces with fractional order......Page 472
A.3 Sobolev spaces with negative order......Page 474
A.4 Variational formulations......Page 475
A.5 Regularity theory......Page 481
B: Besov spaces......Page 484
B.1 Sobolev and Besov embedding......Page 486
B.2 Convergence of approximation schemes......Page 488
C: Basic iterations......Page 491
References......Page 494
B......Page 506
I......Page 507
R......Page 508
Z......Page 509
