Approximation Algorithms for Complex Systems (eBook)

Approximation Algorithms for Complex Systems 
3 
Preface 
5 
Contents 
7 
List of Contributors 
9 
Part I Invited Surveys 11
Emergent Behaviour in Large Electrical Networks 12
1 Introduction and Overview 12
2 Simple Network Models and Their Responses 14
2.1 Modelling Composites as Complex Rectangular Networks 14
Percolation and Power-Law Emergent Behaviour 15
The Effects of Network Size N and Capacitor Proportion p. 18
3 Linear Circuit Analysis of the Network 19
3.1 Linear Circuit Formulation 20
3.2 Poles and Zeroes of the Admittance Function 22
4 The Distribution of the Resonances 23
4.1 Pole Location 24
4.2 Pole-Zero Spacing 24
4.3 Limiting Finite Resonances 26
4.4 Summary 27
5 Asymptotic Analysis of the Power Law Emergent Response 27
5.1 Derivation of the Response 28
6 Comparison of the Asymptotic and Numerical Results for the Critical Case 32
7 Discussion 34
References 35
Algorithms and Error Bounds for Multivariate Piecewise Constant Approximation 36
1 Introduction 36
2 Linear Approximation on Isotropic Partitions 38
3 Nonlinear Approximation 43
4 Anisotropic Partitions 51
References 53
Anisotropic Triangulation Methods in Adaptive Image Approximation 55
1 Introduction 55
2 Image Approximation on Triangulations 57
2.1 Triangulations and Function Spaces 57
2.2 Isotropic and Anisotropic Approximation Methods 61
2.3 Techniques for Proving Approximation Rates 63
3 Four Algorithms for Adaptive Image Approximation 64
3.1 Generic Triangulations and Simulated Annealing 64
3.2 Adaptive Thinning Algorithms 66
3.3 Anisotropic Geodesic Triangulations 68
3.4 Greedy Triangle Bisections 70
4 Numerical Simulations 71
5 Final Remarks and Future Work 74
References 75
Form Assessment in Coordinate Metrology 77
1 Introduction 77
2 Computer-Aided Inspection of Manufactured Parts 78
2.1 Specification of Ideal Geometry 78
2.2 Coordinate Measuring Machines 78
2.3 Orthogonal Distances 78
3 Surface Parametrization 79
3.1 Separating Position, Size and Shape 79
3.2 Parametrization of Geometric Elements 81
3.3 Topology of the Space of Elements 81
3.4 Condition of a Parametrization 82
3.5 Parametrization of NURBS Surfaces 82
3.6 Position and Shape of a Parametric Surface 83
4 Least Squares Orthogonal Distance Regression 84
4.1 Validation of LSODR Software 85
5 Chebyshev Orthogonal Distance Regression 86
5.1 Optimisation Subject to Nonlinear Inequality Constraints 87
5.2 Optimality Conditions 87
5.3 Chebyshev Optimisation for Surface Fitting 88
5.4 Validation of Chebyshev ODR Software 91
5.5 Non-Vertex Solutions: Cylindricity 92
6 Concluding Remarks 94
References 95
Discontinuous Galerkin Methods for Linear Problems: An Introduction 99
1 Introduction 99
1.1 Sobolev Spaces 101
2 The Finite Element Method 102
2.1 Error Analysis of the FEM 105
3 Discontinuous Galerkin Methods 106
4 Discontinuous Galerkin Methods for Elliptic Problems 107
4.1 Error Analysis of the DG Method 109
A Priori Error Bounds 112
A Posteriori Error Bounds 113
5 DG Methods for First Order Hyperbolic Problems 115
5.1 Error Analysis of the DG Method 118
6 Problems with Non-Negative Characteristic Form 121
7 Numerical Examples 123
7.1 Example 1 123
7.2 Example 2 125
8 Solving the Linear System 129
9 Concluding Remarks 131
References 131
A Numerical Analyst's View of the Lattice Boltzmann Method 135
1 Introduction 135
2 The Boltzmann Equation 137
3 The Lattice Boltzmann Method 141
4 The Chapman Enskog Procedure 142
5 The Time Discretisation Expansion 144
6 Decoupling Time Step and Viscosity 146
7 Stability 148
7.1 The Well-Behaved Case 149
7.2 The Difficult Case 150
8 Numerical Experiments 152
8.1 Shock Tube 152
8.2 Flow around a Square Cylinder 154
9 Conclusions 155
References 156
Approximating Probability Measures on Manifolds via Radial Basis Functions 159
1 Introduction 159
2 The New Approach 164
3 Erdos-Turán Type Inequalities 169
4 LeVeque Type Inequalities 170
5 Applications of LeVeque Type Inequalities 174
6 Generalisations to Other Manifolds 180
References 186
Part II Contributed Research Papers 189
Modelling Clinical Decay Data Using Exponential Functions 190
1 Introduction 190
2 Problem Formulation 192
2.1 Raw Data and Associated Uncertainties 192
2.2 Model Function and Feasibility 192
2.3 Derived Quantities 193
2.4 Objective 194
3 Solution Approach 195
3.1 Analysis 195
3.2 Initial Parameter Approximation 196
3.3 Model Parameter Estimation 197
3.4 Consistency of Model and Data 198
3.5 Uncertainties Associated with Parameter Estimates and Estimates of Derived Quantities 198
4 Results 199
4.1 Example 1 199
4.2 Example 2 200
4.3 Example 3 200
5 Scope for Further Work 202
5.1 Contextual Information 202
5.2 Experimental Design Issues 202
5.3 Probability Density Functions 203
6 Conclusions 205
References 209
Towards Calculating the Basin of Attraction of Non-Smooth Dynamical Systems Using Radial Basis Functions 211
1 Introduction 211
2 Non-Smooth Dynamical Systems 213
2.1 Filippov Solutions 213
2.2 Periodic Solution 214
3 Collocation by Radial Basis Functions 215
4 Approximation of the Weight Function 218
4.1 Artificial Gap 218
4.2 Determination of and 220
4.3 Jump Conditions and Breakpoint 221
5 Approximation of V 222
5.1 Collocation Matrix 222
5.2 Error Analysis 223
6 Example: Dry Friction 223
References 230
Stabilizing Lattice Boltzmann Simulation of Fluid Flow past a Circular Cylinder with Ehrenfests' Limiter 232
1 Introduction 232
2 Lattice Boltzmann Method 234
3 Ehrenfests' Coarse-Graining 236
4 Computational Setup for Flow Past Circular Cylinders 239
5 Boundary Conditions 240
6 Results and Discussion 242
References 243
Fast and Stable Interpolation of Well Data Using the Norm Function 245
1 Introduction 245
2 The Interpolant and Algorithm 246
3 Convergence 252
4 Numerical Examples 253
5 Conclusions and Further Developments 256
References 257
Algorithms and Literate Programs for Weighted Low-Rank Approximation with Missing Data 258
1 Introduction 258
2 Low-Rank Approximation with Uniform Weights 261
3 Algorithms 263
3.1 Alternating Projections 263
3.2 Variable Projections 264
4 Implementation 266
4.1 Alternating Projections 267
4.2 Variable Projections 268
5 Test on Simulated Data 269
6 Test on the MoviLens Data 272
7 Conclusions 273
References 276
On Bivariate Interpolatory Mask Symbols, Subdivision and Refinable Functions 277
1 Introduction 277
2 Main Results 280
3 Existence Results for Refinable Functions 288
4 Numerical Application 291
5 Conclusion 292
References 293
Model and Feature Selection in Metrology Data Approximation 295
1 Introduction 295
2 Model Fitting and Selection 296
3 Selection Criteria 297
3.1 Root Mean Square 298
3.2 Akaike Information Criterion 298
3.3 Bayes Information Criterion 298
3.4 Example: Polynomial Regression 299
4 Directed Model Selection 300
4.1 Partial Least Squares 301
4.2 Least Angle Regression (LARS) 302
4.3 Simulations to Assess the Performance of PLS and LARS 303
4.4 Application: Measurement of Naturalness 305
5 Concluding Remarks 308
References 308