Approximation by sums of piecewise linear polynomials

We present two partitioning algorithms that allow a sum of piecewise linear polynomials over a number of overlaying convex partitions of the unit cube ΩΩ in RdRd to approximate a function f∈Wp3(Ω) with the order N−6/(2d+1)N−6/(2d+1) in the LpLp-norm, where NN is the total number of cells of all partitions, which makes a marked improvement over the N−2/dN−2/d order achievable on a single convex partition. The gradient of ff is approximated with the order N−3/(2d+1)N−3/(2d+1). The first algorithm creates dd convex partitions and relies on the knowledge of the eigenvectors of the average Hessians of ff over the cells of an auxiliary uniform partition, whereas the second algorithm with d+12 convex partitions is independent of ff. In addition, we also give an ff-independent partitioning algorithm for a sum of dd piecewise constants that achieves the approximation order N−2/(d+1)N−2/(d+1).