# Approximation of Functions on a Square by Interpolation Polynomials at Vertices and Few Fourier Coefficients

Authors: Zhihua Zhang
Journal: Journal of Function Spaces
 (2017)

---

## Abstract

For a bivariate function on a square, in general, its Fourier coefficients decay slowly, so one cannot reconstruct it by few Fourier coefficients. In this paper we will develop a new approximation scheme to overcome the weakness of Fourier approximation. In detail, we will use Lagrange interpolation and linear interpolation on the boundary of the square to derive a new approximation scheme such that we can use the values of the target function at vertices of the square and few Fourier coefficients to reconstruct the target function with very small error.


---

## Body

## 1. Introduction

It is well-known that smooth periodic functions can be approximated well by Fourier series [1, 2]. But, if we expand a bivariate function on the square robustly into Fourier series, in general, its Fourier coefficients decay slowly. Therefore, one cannot reconstruct it by few Fourier coefficients [3–5]. This is also viewed as the weakness of Fourier approximation compared with wavelet approximation [6, 7]. In this paper we will develop a new approximation scheme to overcome the weakness of Fourier approximation. Our main idea is as follows: For a smooth function on the square 0,12, based on the Lagrange interpolation and the linear interpolation [8–11] of the target function f at the vertices of 0,12, we construct a bivariate function g such that f=g on the boundary of 0,12. Secondly, we take Fourier expansion of the residual r=f-g. Finally, based on this decomposition, we can derive a new scheme to approximate f by using the values of f at the vertices of [0,1]2 and few Fourier coefficients.Throughout this paper we denote the boundary of the unit square0,12 by ∂0,12 and denote the vertices of 0,12 by {0,1}2; that is, (1)0,12=0,0,0,1,1,0,1,1. Denote fxiyj=∂i+jf/∂xi∂yj and ∑k‍=∑k=-∞∞‍. We say f∈C3,30,12 if fx3y3∈C0,12.Expandf into a Fourier series: (2)fx,y=∑m∑ncmnfe2πimx+ny, where cmnf is the Fourier coefficient of f: (3)cmnf=∬01fx,ye-2πimx+nydxdy. The Fourier series hyperbolic cross truncations are defined as [12] (4)sNhf;x,y=∑1≤mn<Nm,n<Ncmnfe2πimx+ny.


## 2. New Approximation Scheme of Bivariate Functions

Letf(x,y) be defined on the square 0,12. We use its values at vertices of the square 0,12 and its few Fourier coefficients to reconstruct f(x,y) on 0,12.Step 1.
Take the linear interpolation off on the vertical intercept x,y,0≤y≤1 of the square 0,12, for a fixed x(0≤x≤1): (5)g1x,y=fx,01-y+fx,1y0≤y≤1.Let φ0x=fx,0-f0,01-x+f1,0x. Expand φ0 into Fourier series: (6)φ0x=∑mcmφ0e2πimx, where cmφ0 is the Fourier coefficient of φ0. We reconstruct fx,0 by (7)hN1x=f0,01-x+f1,0x+∑m<Ncmφ0e2πimx. Let φ1x=fx,1-f0,01-x+f1,1x. Expand φ1 into Fourier series: (8)φ1x=∑mcmφ1e2πimx. We reconstruct f(x,1) by (9)hN2x=f0,11-x+f1,1x+∑m<Ncmφ1e2πimx. So we reconstruct g1(x,y) by (10)g1Nx,y=hN1x1-y+hN2xy,that is, the values of f at vertices 0,12 and Fourier coefficients cm(φ(0)),cm(φ(1))(|m|<N).Step 2.
Take the linear interpolation off on the horizontal intercept x,y,0≤x≤1 of the square 0,12, for a fixed y0≤y≤1, (11)g2x,y=f0,y1-x+f1,yx0≤x≤1.Let ψ0y=f0,y-f0,01-y+f0,1y. Expand ψ0 into Fourier series: (12)ψ0y=∑ncnψ0e2πiny, where cnψ0 is the Fourier coefficient of ψ0. We reconstruct f0,y by (13)hN3y=f0,01-y+f0,1y+∑n<Ncnψ0e2πiny. Let ψ1=f1,y-f1,01-y+f1,1y. Expand ψ1 into Fourier series: (14)ψ1y=∑ncnψ1e2πiny. We reconstruct f1,y by (15)hN4y=f1,01-y+f1,1y+∑n<Ncnψ1e2πiny. So we reconstruct g2x,y by (16)g2Nx,y=hN3y1-x+hN4yx,that is, the values of f at vertices {0,1}2 and Fourier coefficients cn(ψ(0)),cn(ψ(1))(|n|<N).Step 3.
Take the bivariate interpolation polynomial off(x,y) with nodes {0,1}2: (17)g3x,y=f0,01-x1-y+f0,11-xy+f1,0x1-y+f1,1xy.Define an algebraic sum as (18)gx,y=g1x,y+g2x,y-g3x,y0≤x,y≤1which can be reconstructed by gNx,y=g1Nx,y+g2Nx,y-g3x,y.Step 4.
Let(19)rx,y=fx,y-gx,y.Expand rx,y into Fourier series: (20)rx,y=∑m∑ncmnre2πimx+ny. Take the hyperbolic cross truncation of the Fourier series: (21)rNx,y=∑1≤mn<Nm,n<Ncmnre2πimx+ny which can reconstruct rx,y by rNx,y, that is, by few Fourier coefficients. Precisely say that the number Nd of Fourier coefficients used in rNx,y is equal to Nlog⁡N; that is, (22)Nd~Nlog⁡N.Step 5.
We reconstruct the target functionf by (23)fNx,y=gNx,y+rNx,y.
Now we can reconstruct a target functionf by the values of f at 0,12: f0,0,f0,1,f1,0,f1,1 and Fourier coefficients cmφ0,cmφ1m<N, cnψ0,cnψ1n<N, and cmnrmn<N,m,n<N.


## 3. Asymptotic Formula of the Errors for the Reconstruction ofg(x,y)

In order to give the error estimate of our approximation scheme, we need to first give the asymptotic formula of the Fourier coefficients.Assume thatf∈C3,30,12. In Section 2, we know that fx,y=gx,y+rx,y. We first reconstruct gx,y. To reconstruct it, we need to use Fourier coefficients cmφ0,cmφ1,cnψ0,cnψ1, and cmnr which are stated in Section 2. From (24)φ0x=fx,0-f0,01-x+f1,0x, we deduce that φ00=φ01. So (25)cmφ0=∫01φ0xe-2πimxdx=-12πimφ0xe-2πimxx=01-∫01φx0xe-2πimxdx=12πim∫01φx0xe-2πimxdx=-12πim2φx01-φx00-∫01φx20xe-2πimxdx.Since f∈C3,30,12, we have φ0∈C30,1, and so (26)∫01φx20xe-2πimxdx=O1m. This gives an asymptotic formula as follows:(27)cmφ0=14π2m2φx01-φx00+O1m3. Differentiating (24), we get φx0x=fxx,0+f0,0-f1,0. So (28)cmφ0=14π2m2fx1,0-fx0,0+O1m2.Similarly, we discuss the Fourier coefficientscmφ1,cnψ0, and cnψ1. We get the following.Theorem 1.
Letf∈C3,30,12 and φ0, φ1, ψ0, and ψ1 be stated in Section 2. Then, for their Fourier coefficients, one has the following asymptotic formulas:(29)cmφ0=14π2m2fx1,0-fx0,0+O1m3,cmφ1=14π2m2fx1,1-fx0,1+O1m3,cnψ0=14π2n2fy1,0-fy0,0+O1n3,cnψ1=14π2n2fy1,1-fy0,1+O1n3.Denote the partial sums of the Fourier series ofφ(0) by sN(φ(0),x); that is, (30)sNφ0,x=∑m<Ncmφ0e2πimx. By the Parseval identity, the mean square error of φ0 satisfies (31)φ0-sNφ022=∑m<Ncmφ02. From (37), it follows that (32)cmφ02=116π4m4fx1,0-fx0,02+O1m5. Noticing that ∑m<N‍1/m4=2/N3+O1/N4, we get (33)φ0-sNφ022=18π4N3fx1,0-fx0,02+O1N4. Therefore, we can reconstruct φ0 by Fourier coefficients cmφ0m<N and we obtain the asymptotic formula of the error. Again, by Theorem 1, we get (34)fx,0-hN1x22=fx,0-f0,01-x-f1,0x-sNφ0;x22=18π4N3fx1,0-fx0,02+O1N4.From this, we see that fx,0 can be reconstructed by f0,0,f1,0 and Fourier coefficients cmφ0m<N, the order of the error is 1/N3, and the coefficient is 1/8π4fx1,0-fx0,02.Similarly, for the boundary functionsfx,1,f0,y, and f1,y, the corresponding asymptotic formulas are the following:(35)fx,1-hN2x22=fx,1-f0,11-x-f1,1x-sNφ1;x22=18π4N3fx1,1-fx0,12+O1N4,f0,y-hN3y22=f0,y-f0,01-y-f0,1y-sNψ0;y22=18π4N3fy0,1-fy0,02+O1N4,f1,y-hN4y22=f1,y-f1,01-y-f1,1y-sNψ1;y22=18π4N3fy1,1-fy1,02+O1N4.By definitions ofgx,y and gNx,y in Section 2, we get (36)gx,y-gNx,y22≤2g1x,y-g1Nx,y22+2g2x,y-g2Nx,y22≤4fx,0-hN1x22+4fx,1-hN2x22+4f0,y-hN3y22+4f1,y-hN4y22.So, from the above four asymptotic formulas, we know that (37)gx,y-gNx,y22≤D2π4N3+O1N4,where(38)D=fx1,0-fx0,02+fx1,1-fx0,12+fy0,1-fy0,02+fy1,1-fy1,02.From this, we know that the functiongx,y, defined in (18), can be reconstructed by f0,0,f0,1 and f1,0,f1,1 and Fourier coefficients cmφ0,cmφ1m<N and cn(ψ(0)),cn(ψ(1))(|n|<N), and the order of error is 1/N3.From the reconstruction ofgx,y, we know that it is a simple combination of the boundary functions of fx,y and factors x,y,1-x,1-y. It possesses the following important properties.Theorem 2.
Letf be defined on 0,12 and let g be stated in Section 2. Then(39)gx,0=fx,0gx,1=fx,10≤x≤1,g0,y=f0,yg1,y=f1,y0≤y≤1.That is, g and f have same boundary functions: gx,y=fx,yx,y∈∂0,12.Proof.
By (5), (11), and (17),(40)g1x,0=fx,0,g2x,0=f0,01-x+f1,0x,g3x,0=f0,01-x+f1,0x.So gx,0=g1x,0+g2x,0-g3x,0=fx,00≤x≤1. Similarly, the rest equalities can be proved by the same way.


## 4. Asymptotic Formula of Approximation Error forrx,y

In this section, we will estimate the approximation errors of our proposed approximation scheme. In order to show thatrx,y in (19) can be reconstructed by few Fourier coefficients, we give the following asymptotic formula of Fourier coefficients of rx,y.Theorem 3.
Letf∈C3,30,12 be defined on 0,12 and let g be stated as in Theorem 2, and let(41)rx,y=fx,y-gx,y.Then Fourier coefficients of rx,y satisfy the following asymptotic formula:(42)cmnr=116π4m2n2fxy1,1-fxy1,0-fxy0,1+fxy0,0+O1m2n21m+1nm≠0,n≠0.Proof.
Fromr(0,y)=r(1,y)=0(0≤y≤1), it follows that(43)cmnr=∬01rx,ye-2πimx+nydxdy=12πm2∫01rx1,y-rx0,ye-2πinydy-12πm2∬01rx2x,ye-2πimx+nydxdy≕Smn+Tmn.From rx,0=rx,1=00≤x≤1, we have rx0,0=rx0,1=rx1,0=rx1,1=0, and so (44)Smn=-12πim22πin∫01rxy1,y-rxy0,ye-2πinydy=12πim22πin2rxy1,y-rxy0,yy=01-12πim22πin2∫01rxy21,y-rxy20,ye-2πinydy.Since rxy2 is a differentiable function of y, the integral value in this formula is equal to O1/n; that is,(45)Smn=12πim22πin2rxy1,y-rxy0,yy=01+O1m2n2.From rx,y=fx,y-g1x,y-g2x,y-g3x,y and (5), (11), and (17), it can be checked that (46)rxy1,y-rxy0,yy=01=fxy1,y-fxy0,yy=01,and so(47)Smn=12πm22πn2fxy1,y-fxy0,yy=01+O1m2n2.By rx2x,0=rx2x,1=00≤x≤1, we deduce that Tmn=O1/m2n2. From this, we get (42).Theorem3 shows that the decay rate of Fourier coefficients of r is equivalent to 1/m2n2. The principal part of cmnr only depends on the values of fxy at vertices 0,12.Now we discuss the special case: Fourier coefficientscm0 and c0n.Sincer∈C3,30,12 and rx,y=0x,y∈∂0,12,(48)∫01rx,ye-2πimxdx=12πm∫01rxx,ye-2πimxdx=-12πm2rx1,y-rx0,y-∫01rx2x,ye-2πimxdx=12πm2rx1,y-rx0,y+O1m3m≠0.So(49)cm0r=∬01rx,ye-2πimxdxdy=12πm2∫01rx1,y-rx0,ydy+O1m3.Now we computerx1,y-rx0,y.By (5), (11), and (17) and Theorem 2, we have(50)gxν,y=fxν,01-y+fxν,1y-f0,y+f1,y+f0,01-y+f0,1y-f1,01-y-f1,1y,and so (51)rx1,y-rx0,y=fx1,y-fx0,y+fx0,0-fx1,01-y+fx0,1-fx1,1y.From this and (49), it follows that cm0r=A/2πm2+O1/m3m≠0, where (52)A=∫01fx1,y-fx0,ydy+12fx0,0-fx1,0+fx0,1-fx1,1.Similarly, we havec0nr=B/2πn2+O1/n3 (n≠0), where(53)B=∫01fyx,1-fyx,0dx+12fy0,0-fy0,1+fy1,0-fy1,1.By (52), (53), and Theorem 3, it follows that(54)cmnr2=C22πm42πn4+O1m4n41m+1nm≠0,n≠0,cm0r2=A22πm4+O1m5m≠0,c0nr2=B22πn4+O1n5n≠0,where C=fxy1,1-fxy1,0-fxy0,1+fxy0,0 and A,B are stated in (52) and (53).To reconstructrx,y by few Fourier coefficients, we consider the hyperbolic cross truncation of the Fourier series of rx,y:(55)rNx,y=∑m<Ncm0re2πimx+∑0<n<N∑m≤N/ncmnre2πimx+ny,and so(56)rx,y-rNx,y=∑m≥Ncm0re2πimx+∑n≥N∑mcmnre2πimx+ny+∑0<n<N∑m≥N/ncmnre2πimx+nyBy the Parseval identity, the mean square error satisfies (57)rx,y-rNx,y22=∑m≥Ncm02+∑n≥Ncn02+∑n≥N∑m≠0cmnr2+∑0<n<N∑m≥N/ncmnr2=DN1+DN2+DN3+DN4,where(58)DN1=A22π4∑m≥N1m4+O1N4=A28π4N3+O1N4,DN2=B22π4∑n≥N1n4+O1N4=B28π4N3+O1N4,DN3=C22π8∑n≥N1n4∑m≠01m4+O1N4=4γC22π8N3+O1N4γ=∑m=0∞1m4,DN4=C22π8∑0<n<N1n4∑m≥N/n1m4+O1∑0<n<N1N4∑m≥N/n1m5+O1∑0<n<N1n5∑m≥N/n1m4.Noticing that ∑m≥N/n1/m4=2n3/N3+On4/N4 and ∑m≥N/n1/m5=2n4/N4+On5/N5, we deduce that (59)DN4=2C22π8∑0<n<N1n1N3+O1N3=4C22π8∫1N1xdx1N3+O1N3=4C22π8log⁡NN3+O1N3.From this and (57), we obtain finally the following theorem.Theorem 4.
Suppose thatfx,y∈C3,30,12 and rx,y be stated in (19) and rNx,y be the hyperbolic cross truncation of Fourier series of rx,y. Then the mean square error of reconstruction of rx,y by rNx,y satisfies the following asymptotic formula:(60)rx,y-rNx,y22=4C22π8log⁡NN3+18π4A2+B2+αC264π81N3+O1N4,where(61)A=∫01fx1,y-fx0,ydy+12fx0,0-fx1,0+fx0,1-fx1,1,B=∫01fyx,1-fyx,0dx+12fy0,0-fy0,1+fy1,0-fy1,1,C=fxy1,1-fxy1,0-fxy0,1+fxy0,0,α=∑m=1∞1m4.


## 5. Approximation Error off(x,y)

In this section, we will compare our improved Fourier approximation scheme with traditional ones. By (18), (19), and (23),(62)fx,y-fNx,y22≤2gx,y-gNx,y22+2rx,y-rNx,y22.By (57) and (60),(63)fx,y-fNx,y22≤8C22π8log⁡NN3+A2+B24π4+αC232π8+Dπ41N3+O1N4,where A,B,C, and α are stated as above and D is stated in (38).To constructfNx,y, data used by us are four values of f at vertices on 0,12 and 8N-4 univariate Fourier coefficients as well as M bivariate Fourier coefficients cmnmn<N;m,n<N, where (64)M=4N-1+∑1≤n<N∑1≤m<N/n1≤4N-1+2N∑1≤n<N1n≤4N-1+4N1+∫1N1tdt=8N-1+4Nlog⁡N.Therefore, in the reconstruction scheme, the total number of coefficients used by us is less than 16N+4Nlog⁡N. From this and (63), we get (65)fx,y-fNx,y22=Olog4⁡NdNd3,where Nd is the number of coefficients used to construct fN.One the other hand, if we directly expandf∈C3,30,12 into Fourier series, (66)fx,y=∑m∑ncmnfe2πimx+ny,and use the partial sums of Fourier series as a approximation tool(67)sNf;x,y=∑m<N∑n<Ncmnfe2πimx+nyto reconstruct fx,y, then, from cmnf~1/mn [3–5], we deduce that (68)fx,y-sNf;x,y22=O1N.There are Ns=2N+12 Fourier coefficients in the partial sum sNf;x,y; that is,(69)fx,y-sNf;x,y22=O1Ns.Comparing this formula with (65), we see that the approximation scheme proposed in this paper has obvious advantage over traditional method.



---

*Source: 9376505-2017-05-22.xml*