DeVore / Kunoth Multiscale, Nonlinear and Adaptive Approximation

Dedicated to Wolfgang Dahmen on the Occasion of his 60th Birthday
1. Auflage 2009
ISBN: 978-3-642-03413-8
Verlag: Springer
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 660 Seiten

Ronald DeVore's speciality is Nonlinear Approximation Theory. He is The Walter E. Koss Professor of Mathematics at Texas A&M University.He was elected a member of the American Academy of Arts and Sciences in 2001 and received an Honorary Doctorate from RWTH Aachen in 2004. In 2006, he was a Plenary Lecturer at the International Congress of Mathematicians in Madrid. Angela Kunoth is working on wavelet and multiscale methods for solving partial differential equations and for data analysis purposes. She holds the Chair of Complex Systems at Universitaet Paderborn since 2007 and is an editor of five journals in applied mathematics and numerics.

Autoren/Hrsg.

DeVore, Ronald

Kunoth, Angela

Inhaltsverzeichnis

1;Preface;6
2;Acknowledgements;7
3;Contents;8
4;List of Contributors;17
5;Introduction: Wolfgang Dahmen's mathematical work;20
5.1;Introduction;20
5.2;The early years: Classical approximation theory;21
5.3;Bonn, Bielefeld, Berlin, and multivariate splines;21
5.3.1;Computer aided geometric design;22
5.3.2;Subdivision and wavelets;23
5.4;Wavelet and multiscale methods for operator equations;24
5.4.1;Multilevel preconditioning;24
5.4.2;Compression of operators;24
5.5;Adaptive solvers;25
5.6;Construction and implementation;26
5.7;Hyperbolic partial differential equations and conservation laws;27
5.8;Engineering collaborations;28
5.9;The present;28
5.10;Final remarks;29
5.11;Publications by Wolfgang Dahmen (as of summer 2009);29
6;The way things were in multivariate splines: A personal view;37
6.1;Tensor product spline interpolation;37
6.2;Quasiinterpolation;38
6.3;Multivariate B-splines;39
6.4;Kergin interpolation;41
6.5;The recurrence for multivariate B-splines;43
6.6;Polyhedral splines;45
6.7;Box splines;46
6.8;Smooth multivariate piecewise polynomials and the B-net;49
6.9;References;52
7;On the efficient computation of high-dimensional integrals and the approximation by exponential sums;56
7.1;Introduction;56
7.2;Approximation of completely monotone functions by exponential sums;58
7.3;Rational approximation of the square root function;60
7.3.1;Heron's algorithm and Gauss' arithmetic-geometric mean;60
7.3.2;Heron's method and best rational approximation;61
7.3.3;Extension of the estimate (19);65
7.3.4;An explicit formula;66
7.4;Approximation of 1/x by exponential sums;67
7.4.1;Approximation of 1/x on finite intervals;67
7.4.2;Approximation of 1/x on [1,);68
7.4.3;Approximation of 1/x, >0;71
7.5;Applications of 1/x approximations;72
7.5.1;About the exponential sums;72
7.5.2;Application in quantum chemistry;72
7.5.3;Inverse matrix;73
7.6;Applications of 1/x approximations;75
7.6.1;Basic facts;75
7.6.2;Application to convolution;75
7.6.3;Modification for wavelet applications;77
7.6.4;Expectation values of the H-atom;77
7.7;Computation of the best approximation;79
7.8;Rational approximation of x on small intervals;80
7.9;The arithmetic-geometric mean and elliptic integrals;82
7.10;A direct approach to the infinite interval;84
7.11;Sinc quadrature derived approximations;85
7.12;References;90
8;Adaptive and anisotropic piecewise polynomial approximation;92
8.1;Introduction;92
8.1.1;Piecewise polynomial approximation;92
8.1.2;From uniform to adaptive approximation;94
8.1.3;Outline;96
8.2;Piecewise constant one-dimensional approximation;97
8.2.1;Uniform partitions;98
8.2.2;Adaptive partitions;100
8.2.3;A greedy refinement algorithm;102
8.3;Adaptive and isotropic approximation;104
8.3.1;Local estimates;105
8.3.2;Global estimates;107
8.3.3;An isotropic greedy refinement algorithm;108
8.3.4;The case of smooth functions;112
8.4;Anisotropic piecewise constant approximation on rectangles;117
8.4.1;A heuristic estimate;117
8.4.2;A rigourous estimate;120
8.5;Anisotropic piecewise polynomial approximation;125
8.5.1;The shape function;125
8.5.2;Algebraic expressions of the shape function;126
8.5.3;Error estimates;128
8.5.4;Anisotropic smoothness and cartoon functions;129
8.6;Anisotropic greedy refinement algorithms;133
8.6.1;The refinement algorithm for piecewise constants on rectangles;136
8.6.2;Convergence of the algorithm;138
8.6.3;Optimal convergence;141
8.6.4;Refinement algorithms for piecewise polynomials on triangles;145
8.7;References;151
9;Anisotropic function spaces with applications;153
9.1;Introduction;153
9.2;Anisotropic multiscale structures on Rn;155
9.2.1;Anisotropic multilevel ellipsoid covers (dilations) of Rn;155
9.2.2;Comparison of ellipsoid covers with nested triangulations in R2;158
9.3;Building blocks;159
9.3.1;Construction of a multilevel system of bases;159
9.3.2;Compactly supported duals and local projectors;161
9.3.3;Two-level-split bases;162
9.3.4;Global duals and polynomial reproducing kernels;164
9.3.5;Construction of anisotropic wavelet frames ;167
9.3.6;Discrete wavelet frames;170
9.3.7;Two-level-split frames;171
9.4;Anisotropic Besov spaces (B-spaces);172
9.4.1;B-spaces induced by anisotropic covers of Rn;172
9.4.2;B-spaces induced by nested multilevel triangulations of R2;174
9.4.3;Comparison of different B-spaces and Besov spaces;175
9.5;Nonlinear approximation;176
9.6;Measuring smoothness via anisotropic B-spaces;178
9.7;Application to preconditioning for elliptic boundary value problems;180
9.8;References;182
10;Nonlinear approximation and its applications;184
10.1;The early years;184
10.2;Smoothness and interpolation spaces;186
10.2.1;The role of interpolation;187
10.3;The main types of nonlinear approximation;189
10.3.1;n-term approximation;189
10.3.2;Adaptive approximation;193
10.3.3;Tree approximation;193
10.3.4;Greedy algorithms;196
10.4;Image compression;200
10.5;Remarks on nonlinear approximation in PDE solvers;202
10.6;Learning theory;204
10.6.1;Learning with greedy algorithms;208
10.7;Compressed sensing;210
10.8;Final thoughts;214
10.9;References;214
11;Univariate subdivision and multi-scale transforms: The nonlinear case;217
11.1;Introduction;217
11.2;Nonlinear multi-scale transforms: Functional setting;224
11.2.1;Basic notation and further examples;224
11.2.2;Polynomial reproduction and derived subdivision schemes;229
11.2.3;Convergence and smoothness;231
11.2.4;Stability;237
11.2.5;Approximation order and decay of details;241
11.3;The geometric setting: Case studies;244
11.3.1;Geometry-based subdivision schemes;245
11.3.2;Geometric multi-scale transforms for planar curves;254
11.4;References;259
12;Rapid solution of boundary integral equations by wavelet Galerkin schemes;262
12.1;Introduction;262
12.2;Problem formulation and preliminaries;265
12.2.1;Boundary integral equations;265
12.2.2;Parametric surface representation;266
12.2.3;Kernel properties;268
12.3;Wavelet bases on manifolds;269
12.3.1;Wavelets and multiresolution analyses;269
12.3.2;Refinement relations and stable completions;271
12.3.3;Biorthogonal spline multiresolution on the interval;272
12.3.4;Wavelets on the unit square;274
12.3.5;Patchwise smooth wavelet bases;279
12.3.6;Globally continuous wavelet bases;280
12.4;The wavelet Galerkin scheme;284
12.4.1;Historical notes;285
12.4.2;Discretization;286
12.4.3;A-priori compression;287
12.4.4;Setting up the compression pattern;288
12.4.5;Computation of matrix coefficients;290
12.4.6;A-posteriori compression;292
12.4.7;Wavelet preconditioning;292
12.4.8;Numerical results;294
12.4.9;Adaptivity;297
12.5;References;303
13;Learning out of leaders;308
13.1;Introduction;308
13.2;Various learning algorithms in Wolfgang Dahmen's work ;311
13.2.1;Greedy learning algorithms;311
13.2.2;Tree thresholding procedures;312
13.3;Learning out leaders: LOL;316
13.3.1;Gaussian regression model;316
13.3.2;LOL procedure;317
13.3.3;Sparsity conditions on the target function f;318
13.3.4;Results;319
13.3.5;Discussion;320
13.3.6;Restricted LOL;321
13.4;Practical performances of the LOL procedure ;322
13.4.1;Experimental design;322
13.4.2;Algorithm;323
13.4.3;Simulation results;325
13.4.4;Quality reconstruction;326
13.4.5;Discussion;327
13.5;Proofs;329
13.5.1;Preliminaries;329
13.5.2;Concentration lemma 5.4;331
13.5.3;Proof of Theorem 3.2;332
13.6;References;336
14;Optimized wavelet preconditioning;338
14.1;Introduction;338
14.2;Systems of elliptic partial differential equations (PDEs);342
14.2.1;Abstract operator systems;342
14.2.2;A scalar elliptic boundary value problem;343
14.2.3;Saddle point problems involving essential boundary conditions;344
14.2.4;PDE-constrained control problems: Distributed control;347
14.2.5;PDE-constrained control problems: Dirichlet boundary control;349
14.3;Wavelets;350
14.3.1;Basic properties;350
14.3.2;Norm equivalences and Riesz maps;353
14.3.3;Representation of operators;354
14.3.4;Multiscale decomposition of function spaces;355
14.4;Problems in wavelet coordinates;369
14.4.1;Elliptic boundary value problems;369
14.4.2;Saddle point problems;371
14.4.3;Control problems: Distributed control;374
14.4.4;Control problems: Dirichlet boundary control;378
14.5;Iterative solution;380
14.5.1;Finite systems on uniform grids;381
14.5.2;Numerical examples;385
14.6;References;389
15;Multiresolution schemes for conservation laws;392
15.1;Introduction;392
15.2;Governing equations and finite volume schemes;394
15.3;Multiscale analysis;396
15.4;Multiscale-based spatial grid adaptation;400
15.5;Adaptive multiresolution finite volume schemes;402
15.5.1;From the reference scheme to an adaptive scheme;402
15.5.2;Approximate flux and source approximation strategies;403
15.5.3;Prediction strategies;405
15.5.4;Multilevel time stepping;406
15.5.5;Error analysis;410
15.6;Numerical results;410
15.6.1;The solver Quadflow;411
15.6.2;Application;411
15.7;Conclusion and trends;415
15.8;References;418
16;Theory of adaptive finite element methods: An introduction;422
16.1;Introduction;423
16.1.1;Classical vs adaptive approximation in 1d;423
16.1.2;Outline;424
16.2;Linear boundary value problems;426
16.2.1;Sobolev spaces;426
16.2.2;Variational formulation;429
16.2.3;The inf-sup theory;432
16.2.4;Two special problem classes;436
16.2.5;Applications ;440
16.2.6;Problems;443
16.3;The Petrov-Galerkin method and finite element bases ;445
16.3.1;Petrov-Galerkin solutions;446
16.3.2;Finite element spaces;451
16.3.3;Problems;458
16.4;Mesh refinement by bisection;460
16.4.1;Subdivision of a single simplex;460
16.4.2;Mesh refinement by bisection;464
16.4.3;Basic properties of triangulations;467
16.4.4;Refinement algorithms;470
16.4.5;Complexity of refinement by bisection;475
16.4.6;Problems;481
16.5;Piecewise polynomial approximation;482
16.5.1;Quasi-interpolation;482
16.5.2;A priori error analysis;485
16.5.3;Principle of error equidistribution;487
16.5.4;Adaptive approximation;489
16.5.5;Problems;492
16.6;A posteriori error analysis;493
16.6.1;Error and residual;494
16.6.2;Global upper bound;495
16.6.3;Lower bounds;500
16.6.4;Problems;508
16.7;Adaptivity: Convergence;510
16.7.1;The adaptive algorithm;510
16.7.2;Density and convergence;512
16.7.3;Properties of the problem and the modules;514
16.7.4;Convergence;516
16.7.5;Problems;524
16.8;Adaptivity: Contraction property;525
16.8.1;The modules of AFEM for the model problem;526
16.8.2;Properties of the modules of AFEM;527
16.8.3;Contraction property of AFEM;531
16.8.4;Example: Discontinuous coefficients;533
16.8.5;Problems;535
16.9;Adaptivity: Convergence rates;537
16.9.1;Approximation class;538
16.9.2;Cardinality of Mk;543
16.9.3;Quasi-optimal convergence rates;546
16.9.4;Marking vs optimality;547
16.9.5;Problems;551
16.10;References;552
17;Adaptive wavelet methods for solving operator equations: An overview;556
17.1;Introduction;556
17.1.1;Non-adaptive methods;556
17.1.2;Adaptive methods;558
17.1.3;Best N-term approximation and approximation classes;559
17.1.4;Structure of the paper;560
17.1.5;Some properties of the (quasi-) norms ||.||As;560
17.2;Well-posed linear operator equations;562
17.2.1;Reformulation as a bi-infinite matrix vector equation;562
17.2.2;Some model examples;563
17.3;Adaptive wavelet schemes I: Inexact Richardson iteration ;565
17.3.1;Richardson iteration;565
17.3.2;Practical scheme;566
17.3.3;The routines COARSE and APPLY;571
17.3.4;Non-coercive B;575
17.3.5;Alternatives for the Richardson iteration;577
17.4;Adaptive wavelet schemes II: The Adaptive wavelet-Galerkin method ;578
17.4.1;The adaptive wavelet-Galerkin method (AWGM) in a idealized setting;578
17.4.2;Practical scheme;581
17.4.3;Discussion;587
17.5;The approximation of operators in wavelet coordinates by computable sparse matrices;587
17.5.1;Near-sparsity of partial differential operators in wavelet coordinates;588
17.5.2;The approximate computation of the significant entries;593
17.5.3;Trees;596
17.6;Adaptive frame methods;598
17.6.1;Introduction;598
17.6.2;Frames;598
17.6.3;The adaptive solution of an operator equation in frame coordinates;599
17.6.4;An adaptive Schwarz method for aggregated wavelet frames;601
17.7;Adaptive methods based on tensor product wavelet bases;603
17.7.1;Tensor product wavelets;603
17.7.2;Non-adaptive approximation;603
17.7.3;Best N-term approximation and regularity;604
17.7.4;s-computability;605
17.7.5;Truly sparse stiffness matrices;605
17.7.6;Problems in space high dimension;605
17.7.7;Non-product domains;606
17.7.8;Other, non-elliptic problems;607
17.8;References;607
18;Optimal multilevel methods for H(grad), H(curl), and H(div) systems on graded and unstructured grids;611
18.1;Introduction;611
18.2;The method of subspace corrections;613
18.2.1;Iterative methods;614
18.2.2;Space decomposition and method of subspace correction;616
18.2.3;Sharp convergence identities;619
18.3;Multilevel methods on quasi-uniform grids;621
18.3.1;Finite element methods;621
18.3.2;Multilevel space decomposition and multigrid method;623
18.3.3;Stable decomposition and optimality of BPX preconditioner;624
18.3.4;Uniform convergence of V-cycle multigrid;628
18.3.5;Systems with strongly discontinuous coefficients;630
18.4;Multilevel methods on graded grids;633
18.4.1;Bisection methods;634
18.4.2;Compatible bisections;636
18.4.3;Decomposition of bisection grids;637
18.4.4;Generation of compatible bisections;639
18.4.5;Node-oriented coarsening algorithm;641
18.4.6;Space decomposition on bisection grids;642
18.4.7;Strengthened Cauchy-Schwarz inequality;646
18.4.8;BPX preconditioner and multigrid on graded bisection grids;648
18.5;Multilevel methods for H(curl) and H(div) systems;648
18.5.1;Preliminaries;650
18.5.2;Space decomposition and multigrid methods;658
18.5.3;Stable decomposition;660
18.6;The auxiliary space method and HX preconditioner for unstructured grids;663
18.6.1;The auxiliary space method;663
18.6.2;HX preconditioner;665
18.7;References;667