Handbook of Numerical Analysis. Special Volume: Foundations of Computational Mathematics

0002.tif......Page 1
0001.tif......Page 0
Contents of Volume XI......Page 2
On the place of numerical analysis in the mathematical universe......Page 3
Approximation theory......Page 6
Functional analysis......Page 10
Complexity theory......Page 14
Probability theory and statistics......Page 16
Nonlinear dynamical systems......Page 19
Topology and algebraic geometry......Page 20
Differential geometry......Page 22
Abstract algebra......Page 24
…and beyond......Page 26
Adaptivity......Page 27
Conditioning......Page 28
Structure......Page 30
Acknowledgements......Page 31
References......Page 32
Geometric Integration and its Applications......Page 35
Introduction......Page 36
Qualitative properties......Page 38
A partial listing......Page 39
Why preserve structure?......Page 42
The theory of Hamiltonian methods......Page 43
Outline......Page 45
Symplectic Runge-Kutta methods......Page 49
Splitting and composition methods......Page 51
Example 1. The Harmonic oscillator......Page 54
Example 2. The pendulum......Page 57
Example 4. Stellar dynamics and the Kepler problem......Page 59
Error analysis - a brief overview......Page 61
The backward error analysis of symplectic methods......Page 62
An analysis of splitting methods......Page 64
Outline......Page 67
Serendipitous and enforced conservation laws......Page 68
Discrete gradient methods......Page 70
Lie group methods......Page 71
Example 1. Evolution on the sphere......Page 76
Example 2. Rigid body motion......Page 77
Symmetries and reversing symmetries......Page 79
Outline......Page 81
Numerical methods for scale invariant problems......Page 83
Examples......Page 86
A comparison of methods......Page 89
Overview......Page 94
Basic theory......Page 95
Examples......Page 96
Lagrangian and action based methods for PDEs......Page 99
Methods for partial differential equations that preserve all symmetries......Page 104
Noether\'s theorem for discrete schemes......Page 109
Scaling invariance of partial differential equations......Page 112
Spatial adaptivity......Page 114
Singularities in the nonlinear Schrödinger equation (NLS)......Page 115
The nonlinear diffusion equation......Page 118
The Euler equation......Page 122
The Arakawa Jacobian......Page 123
Sine bracket type truncation......Page 124
The semi-geostrophic equations, frontogenesis and prediction ensembles......Page 125
Hamiltonian formulations......Page 128
Links with moving mesh theory......Page 129
Calculating Lyapunov exponents......Page 130
Conclusion......Page 132
Acknowledgements......Page 133
References......Page 134
A few words on linear programming......Page 141
A few words on complexity theory......Page 143
System of linear equations......Page 145
Linear least-squares problem......Page 146
System of linear inequalities (linear conic systems)......Page 147
Linear programming (LP)......Page 148
Semi-definite programming (SDP)......Page 151
Linear programming and complexity theory......Page 153
Finite precision and round-off errors......Page 154
Linear systems......Page 155
Condition-based complexity......Page 157
C(A)......Page 158
C(A)......Page 159
chiA......Page 161
sigma(A)......Page 162
Relations between condition measures for linear programming......Page 163
Interior point algorithms......Page 164
An example of complexity analysis: the Vavasis-Ye method......Page 170
Layered least squares......Page 173
One step of the algorithm......Page 177
Crossover events and LIP\'s complexity......Page 181
An example of round-off (and complexity) analysis......Page 183
Introduction......Page 190
Proof of Theorem 6.3(i)......Page 191
Proof of Theorem 6.2......Page 193
Proof of Theorem 6.2 for sigma(A)......Page 194
Semidefinite programming algorithms and analyses......Page 195
Potential reduction algorithm......Page 196
Primal-dual algorithm......Page 201
Notes......Page 203
References......Page 204
Introduction......Page 209
Random product homotopy......Page 212
m-homogeneous structure......Page 215
Cheater\'s homotopy......Page 224
Bernshteín\'s theorem......Page 228
Mixed volume and mixed subdivisions......Page 234
Polyhedral homotopy method......Page 238
The polyhedral homotopy......Page 239
Solutions of binomial systems in (C*)n......Page 242
Polyhedral homotopy procedure......Page 245
Mixed volume computation......Page 247
A basic linear programming algorithm......Page 249
Finding all lower edges of a lifted point set......Page 251
Extending level-k subfaces......Page 256
Finding all mixed cells......Page 260
Semi-mixed polynomial systems......Page 261
The relation table......Page 264
Level-1 subfaces of S=(S(1),…, S(r))......Page 269
The extension of level-xi subfaces......Page 271
Finding all cells of type (k1,…,kr)......Page 272
Stable mixed volume......Page 273
An alternative algorithm......Page 275
A revision......Page 277
Solutions of positive dimension......Page 280
Fundamental procedure for following paths......Page 285
Projective coordinates and the projective Newton method......Page 288
Balancing the lifting values in polyhedral homotopies......Page 290
The end game......Page 298
Softwares......Page 299
References......Page 300
Further reading......Page 303
Preface......Page 305
Pioneers in chaotic dynamical system......Page 307
From order to chaos......Page 309
Li-Yorke theorem......Page 313
Snap-back repeller......Page 315
Euler\'s difference scheme......Page 317
Yamaguti-Matano theorem......Page 318
Walrasian general equilibrium theory......Page 321
A mathematical model of an exchange economy......Page 322
Chaotic tatonnement......Page 323
O.D.E. with globally asymptotical stability......Page 326
Three types of O.D.E.\'s and chaos with large time steps......Page 328
Three types of O.D.E.\'s and chaos with small time step......Page 335
Lipschitz continuity at the equilibrium point......Page 339
Necessary condition for chaos......Page 342
Existence of stable periodic orbits......Page 346
Preliminary study......Page 347
Modified Euler scheme......Page 350
Central difference scheme......Page 355
Eigenvalues and eigenvectors at the fixed points......Page 357
Discretization of a system of ordinary differential equation......Page 358
Discretization of O.D.E. with one equilibrium......Page 362
Introduction......Page 372
A threshold model of collective behavior for a hairstyle fashion......Page 373
Multigrid difference scheme......Page 377
Lebesgue\'s singular function and the Takagi function......Page 378
References......Page 380
Introduction......Page 383
Geodesic curves and minimal surfaces......Page 385
Energy based active contours.......Page 386
The geodesic curve flow.......Page 388
The level-sets geodesic flow: Derivation.......Page 392
The level-sets geodesic flow: Boundary detection.......Page 393
Existence, uniqueness, stability, and consistency of the geodesic model......Page 396
Experimental results......Page 399
Three-dimensional minimal surfaces......Page 400
Vector-valued edges......Page 402
Color snakes......Page 404
Remark on level-lines of vector valued images......Page 405
Finding the minimal geodesic......Page 406
Computing the minimal geodesic......Page 407
Equal distance contours computation.......Page 408
Affine invariant active contours......Page 409
Affine invariant gradient......Page 410
Affine invariant gradient snakes......Page 413
Additional extensions and modifications......Page 416
Tracking and morphing active contours......Page 418
Gaussian filtering and linear scale-spaces......Page 423
Edge stopping diffusion......Page 425
Perona-Malik formulation......Page 426
Robust estimation.......Page 427
Robust statistics and anisotropic diffusion......Page 430
Exploiting the relationship......Page 431
Robust estimation and line processes......Page 435
Directional diffusion......Page 438
Introducing prior knowledge......Page 439
The general technique......Page 441
Contrast enhancement......Page 444
Histogram modification......Page 446
Existence and uniqueness of the flow.......Page 447
Variational interpretation of the histogram flow.......Page 448
Experimental results......Page 450
Shape preserving contrast enhancement......Page 451
Acknowledgements......Page 453
References......Page 455
Further reading......Page 461
Subject Index......Page 463