The bit-complexity of finding nearly optimal quadrature rules for weighted integration
| Title: | The bit-complexity of finding nearly optimal quadrature rules for weighted integration |
|---|---|
| Authors: | Volker Bosserhoff |
| Contributors: | The Pennsylvania State University CiteSeerX Archives |
| Source: | http://www.jucs.org/jucs_14_6/the_bit_complexity_of/jucs_14_06_0938_0955_bosserhoff.pdf. |
| Publication Year: | 2008 |
| Collection: | CiteSeerX |
| Description: | Given a probability measure ν and a positive integer n. How to choose n knots and n weights such that the corresponding quadrature rule has the minimum worst-case error when applied to approximate the ν-integral of Lipschitz functions? This question has been considered by several authors. We study this question whithin the framework of Turing machine-based real computability and complexity theory as put forward by [Ko 1991] and others. After having defined the notion of a polynomialtime computable probability measure on the unit interval, we will show that there are measures of this type for which there is no computable optimal rule with two knots. We furthermore characterize -in terms of difficult open questions in discrete complexity theory -the complexity of computing rules whose worst-case error is arbitrarily close to optimal. |
| Document Type: | text |
| File Description: | application/pdf |
| Language: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1088.4197; http://www.jucs.org/jucs_14_6/the_bit_complexity_of/jucs_14_06_0938_0955_bosserhoff.pdf |
| Availability: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1088.4197; http://www.jucs.org/jucs_14_6/the_bit_complexity_of/jucs_14_06_0938_0955_bosserhoff.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| Accession Number: | edsbas.52D09D4F |
| Database: | BASE |