An algorithm for segment approximation (Q1060802)

An algorithm for computing segment approximations is developed. Let a subset G of C[a,b] containing a strictly positive function, a natural number k and a function \(f\in C[a,b]\) be given. For an arbitrary norm on C[a,b] the segment approximation problem is to determine a set of k knots \(a=x_ 0<x_ 1<...<x_ k<x_{k+1}=b\) which minimizes the expression \(\max_{0\leq i\leq k}\) \(d(f,G,[x_ i,x_{i+1}])\), where \(d(f,G,[c,d])=\inf_{g\in G}\| f-g\| [c,d]\). The authors' algorithm yields a sequence \((d_ n)\) converging to the minimal deviation. In this way a set of knots \(\{x_ 1,...,x_ k\}\) is obtained such that \(d(f,G,[x_{i-1},x_ i])=d(f,G,[x_ i,x_{i+1}])\), \(i=1,...,k\) which is sufficient for optimality. In the n-th step of the algorithm knots \(a=x_{0,n}<x_{1,n}<...<x_{k,n}<x_{k+1,n}=b\) are computed consecutively such that \(d(f,G,[x_{i,n},x_{i+1,n}])=d_ n\), \(i=0,...,k-1\). Roughly speaking, \(d_{n+1}\) is defined by \(d_{n+1}=10^{\delta_{n+1}}\), where \(\delta_{n+1}=(\delta_ n+\gamma_ n)\), \(d_ n=10^{\delta_ n}\) and \(d(f,G,[x_{k,n},x_{k+1,n}])=10^{\gamma_ n}\). The estimation \(| \delta -\delta_{n+1}| \leq | \delta_ n-\gamma_ n| \leq...\leq 1/2^ n| \delta_ 1-\gamma_ 1|\) holds, where \(10^{\delta}\) is the minimal deviation. These inequalities show that \(d_ n\) is sufficiently near to the minimal deviation after a few steps. Numerical results concerning piecewise polynomial and piecewise rational approximation with free knots are given.