| Autor: |
Choi, Sou-Cheng T., Ding, Yuhan, Hickernell, Fred J., Tong, Xin |
| Rok vydání: |
2016 |
| Předmět: |
|
| Zdroj: |
Journal of Complexity, 40, pp. 17-33, 2017 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1016/j.jco.2016.11.005 |
| Popis: |
Most commonly used \emph{adaptive} algorithms for univariate real-valued function approximation and global minimization lack theoretical guarantees. Our new locally adaptive algorithms are guaranteed to provide answers that satisfy a user-specified absolute error tolerance for a cone, $\mathcal{C}$, of non-spiky input functions in the Sobolev space $W^{2,\infty}[a,b]$. Our algorithms automatically determine where to sample the function---sampling more densely where the second derivative is larger. The computational cost of our algorithm for approximating a univariate function $f$ on a bounded interval with $L^{\infty}$-error no greater than $\varepsilon$ is $\mathcal{O}\Bigl(\sqrt{{\left\|f"\right\|}_{\frac12}/\varepsilon}\Bigr)$ as $\varepsilon \to 0$. This is the same order as that of the best function approximation algorithm for functions in $\mathcal{C}$. The computational cost of our global minimization algorithm is of the same order and the cost can be substantially less if $f$ significantly exceeds its minimum over much of the domain. Our Guaranteed Automatic Integration Library (GAIL) contains these new algorithms. We provide numerical experiments to illustrate their superior performance. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
