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

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