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 R d to approximate a function f ∈ W p 3 ( Ω ) with the order N − 6 / ( 2 d + 1 ) in the L p -norm, where N is the total number of cells of all partitions, which makes a marked improvement over the N − 2 / d order achievable on a single convex partition. The gradient of f is approximated with the order N − 3 / ( 2 d + 1 ) . The first algorithm creates d convex partitions and relies on the knowledge of the eigenvectors of the average Hessians of f over the cells of an auxiliary uniform partition, whereas the second algorithm with d + 1 2 convex partitions is independent of f . In addition, we also give an f -independent partitioning algorithm for a sum of d piecewise constants that achieves the approximation order N − 2 / ( d + 1 ) .