Loading...
Please wait, while we are loading the content...
Similar Documents
The Convergence Rate of the Sandwich Algorithm for Approximating Convex Functions G Unter Rote the Convergence Rate of the Sandwich Algorithm for Approximating Convex Functions
| Content Provider | Semantic Scholar |
|---|---|
| Author | Rote, G. Unter Belegten, Die Konvergenzrate Des |
| Copyright Year | 1992 |
| Abstract | This version is a little extended and shortened with respect to the printed revised version of October 1991. Abstract | Zusammenfassung The Convergence Rate of the Sandwich Algorithm for Approximating Convex Functions. The Sandwich algorithm approximates a convex function of one variable over an interval by evaluating the function and its derivative at a sequence of points. The connection of the obtained points is a piecewise linear upper approximation, and the tangents yield a piecewise linear lower approximation. Similarly, a planar convex gure can be approximated by convex polygons. Diierent versions of the Sandwich algorithm use diierent rules for selecting the next evaluation point. We consider four natural rules (interval bisection, slope bisection, maximum error rule, and chord rule) and show that the global approximation error with n evaluation points decreases by the order of O(1=n 2), which is optimal. By special examples we show that the actual performance of the four rules can be very diierent from each other, and we report computational experiments which compare the performance of the rules for particular functions. Vergleich der Regeln f ur einige ausgesuchte Funktionen. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.inf.fu-berlin.de/~rote/Papers/postscript/The+convergence+rate+of+the+Sandwich+algorithm+for+approximating+convex+functions.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
