Tractability of multivariate problems. Standard information for functionals

E_book_novak_II.pdf......Page 0
Preface......Page 7
Contents......Page 13
Introduction......Page 19
L_2 Discrepancy Anchored at the Origin......Page 25
Bounds for the L_2 Discrepancy......Page 26
The Exponent of the L_2 Discrepancy......Page 29
Normalized L_2 Discrepancy......Page 30
Weighted L_2 Discrepancy......Page 31
Normalized Weighted L_2 Discrepancy......Page 35
Multivariate Integration......Page 36
Discrepancy Anchored at the Origin......Page 41
Discrepancy and Wiener Sheet Measure......Page 43
Discrepancy Anchored at alpha......Page 45
Quadrant Discrepancy at  alpha......Page 49
Extreme or Unanchored Discrepancy......Page 51
Are They Always Related?......Page 54
Tractability......Page 62
L_p Discrepancy Anchored at the Origin......Page 70
Centered L_p Discrepancy......Page 75
Spaces Without Boundary Values......Page 77
Star Discrepancy......Page 79
Notes and Remarks......Page 86
Introduction......Page 89
Linear Functionals......Page 91
One Function Value......Page 93
Bad or Good Convergence......Page 97
Example: Kernel for Non-Separable Space......Page 99
Example: Unbounded Kernel......Page 101
Example: Sobolev Space Anchored at 0......Page 103
Non-negative Kernels and Algorithms......Page 105
Example: Kernel for Non-Separable Space (Continued)......Page 108
Example: Unbounded Kernel (Continued)......Page 109
Example: Kernels Related to Discrepancies......Page 110
Example: Polynomials of Degree Two......Page 112
Power of Negative Coefficients......Page 114
Multivariate Integration......Page 116
QMC Algorithms......Page 117
Example: Tensor Product Problems......Page 121
Example: Modified Sobolev Space......Page 123
Example: Korobov Space with Varying Smoothness......Page 125
Example: Korobov Space with Fixed Smoothness......Page 128
Properly Normalized QMC Algorithms......Page 129
Example: Tensor Product Problems (Continued)......Page 133
Example: Modified Sobolev Space (Continued)......Page 134
Algorithms with Arbitrary Coefficients......Page 135
Example: Tensor Product Problems (Continued)......Page 139
Example: Another Modified Sobolev Space (Continued)......Page 140
Example: Unbounded Kernel (Continued)......Page 142
The Operator W_d......Page 144
Relations to Multivariate Integration......Page 148
Example: Linear Functionals in Korobov Space......Page 150
General Case......Page 153
Example: Tensor Product Problems (Continued)......Page 159
Notes and Remarks......Page 160
Introduction......Page 164
Linear Tensor Product Functionals......Page 165
Preliminary Error Estimates......Page 166
Decomposable Kernels......Page 179
Example: Weighted Integration......Page 187
Example: Uniform Integration......Page 191
Example: Centered Discrepancy......Page 193
Example: Two Function Values......Page 196
Non-decomposable Kernels......Page 197
Example: Weighted Integration (Continued)......Page 204
Example: Uniform Integration......Page 206
Example: Centered Discrepancy (Continued)......Page 207
Example: Sobolev Space Anchored at 0......Page 209
Which Linear Tensor Product Functionals Are Tractable?......Page 213
Example: Sobolev Spaces with r=1 over [0,1]^d......Page 216
Example: Sobolev Space with r \ge 1 over R^d......Page 220
Notes and Remarks......Page 224
Introduction......Page 226
Weighted Linear Functionals......Page 228
Lower Bounds......Page 232
Example: Constant and Almost Constant Weights......Page 237
Example: Three Function Values......Page 238
Example: Order-Dependent Weights......Page 240
Product Weights......Page 242
Example: Unbounded Weights......Page 249
Example: Weighted Integration (Continued)......Page 250
Further Lower Bounds......Page 254
Example: Weighted Integration (Continued)......Page 262
Upper Bounds for Multivariate Integration......Page 266
Example: Uniform Integration (Continued)......Page 278
Example: Bounds on Weighted L_2 Discrepancy......Page 283
Upper Bounds Based on Theorem 10.10......Page 284
Example: Integration and Unbounded Kernel......Page 293
Upper Bounds for the General Case......Page 295
Notes and Remarks......Page 304
Basics of the Average Case Setting......Page 306
Linear Functionals......Page 308
Relations to the Worst Case Setting......Page 309
Notes and Remarks......Page 314
Introduction......Page 315
Tractability in the Probabilistic Setting......Page 316
Relations to the Worst Case Setting......Page 318
Absolute Error Criterion......Page 322
Normalized Error Criterion......Page 327
Summary......Page 328
Relative Error......Page 329
Notes and Remarks......Page 337
Introduction......Page 338
Unweighted Case: Algorithms......Page 340
Explicit Form......Page 342
Explicit Error Bound......Page 344
Explicit Cost Bound......Page 351
-Cost Bound......Page 353
Tractability......Page 357
Example: Integration of Smooth Periodic Functions......Page 363
Example: Integration of Non-Periodic Functions......Page 366
Example: Discrepancy......Page 369
Implementation Issues......Page 371
Weighted Case: Algorithms......Page 374
Explicit Form......Page 381
Explicit Error Bound......Page 382
Explicit Cost Bound......Page 384
-Cost Bound......Page 385
Tractability for Finite-Order Weights......Page 388
The First Class of WTP Algorithms......Page 389
The Second Class of WTP Algorithms......Page 393
Example: Perturbed Coulomb Potential......Page 398
Open Problems for Finite-Order Weights......Page 400
Tractability for Product Weights......Page 401
Example: Uniform Integration (Continued)......Page 405
Example: Weights for Cobb Douglas Functions......Page 407
Example: Integration of Smooth Functions......Page 409
Robustness of WTP Algorithms......Page 410
Notes and Remarks......Page 413
Introduction......Page 416
Weighted Korobov Spaces......Page 420
Multivariate Integration......Page 422
Lattice Rules......Page 424
The Existence of Good Lattice Rules......Page 425
Tractability for General Weights......Page 433
Tractability for Product Weights......Page 439
Tractability for Weights Independent of d......Page 445
Tractability for Finite-Order and Order-Dependent Weights......Page 447
Worst Case Error for  Approaching to 1/2......Page 450
CBC Algorithm......Page 451
Cost of the CBC Algorithm......Page 456
Cost for Product Weights......Page 457
Cost for Finite-Order and Finite-Diameter Weights......Page 459
Cost for Order-Dependent Weights......Page 460
Kernels and Shift-Invariant Kernels......Page 462
Relations to Weighted Sobolev Space......Page 468
Tractability for Weighted Korobov Spaces......Page 475
Weighted Sobolev Spaces......Page 481
Shifted Lattice Rules......Page 484
Tractability for Finite-Order Weights......Page 489
Shifted Lattice Rules for Finite-Order Weights......Page 495
Tractability Using Low Discrepancy Sequences......Page 498
Notes and Remarks......Page 504
17 Randomized Setting......Page 505
Monte Carlo for Multivariate Integration......Page 506
Uniform Integration......Page 512
Gaussian Integration......Page 528
Periodicity May Help......Page 531
Periodicity May Hurt......Page 532
Monte Carlo May Lose......Page 534
Can Monte Carlo Be Improved?......Page 535
Importance Sampling......Page 544
Results for Sobolev spaces......Page 546
Local Solution of the Laplace Equation......Page 550
Notes and Remarks......Page 556
18 Nonlinear Functionals......Page 557
Deterministic Algorithms and Quasi-Linearity......Page 558
Randomized Algorithms......Page 560
Analysis for  F_C(Omega)......Page 561
Log Concave Densities......Page 566
Explicit Error Bounds for MCMC......Page 567
Integral Equations......Page 580
Worst Case Setting......Page 581
Restricted Randomized Setting......Page 582
Computation of Fixed Points......Page 589
Global Optimization......Page 592
Computation of the Volume......Page 594
Notes and Remarks......Page 597
Path Integration......Page 598
Weighted Sobolev Space with d = infinity......Page 603
The Result of Sobol......Page 607
Quantum Computation......Page 608
Model of Quantum Computation......Page 609
Grover's Search Algorithm......Page 612
Computation of Sums and Integrals......Page 613
Solution of PDEs......Page 614
Tractability in the Quantum Setting......Page 615
Notes and Remarks......Page 616
Introduction......Page 618
Preliminaries......Page 619
First Sobolev Space......Page 623
Second Sobolev Space......Page 633
Third Sobolev Space......Page 642
Notes and Remarks......Page 644
Appendix D List of Open Problems......Page 645
Appendix E Errata for Volume I......Page 650
Bibliography......Page 653
Index......Page 673