Construction of Optimal Quadrature Formula for Numerical Calculation of Fourier Coefficients in Sobo...

Nurali D. Boltaev, Abdullo R. Hayotov, Kholmat M. Shadimetov

American Journal of Numerical Analysis

Construction of Optimal Quadrature Formula for Numerical Calculation of Fourier Coefficients in Sobolev Space L2(1)

Nurali D. Boltaev1, Abdullo R. Hayotov1,, Kholmat M. Shadimetov1

1Department of Comptational Methods, Institute of Mathematics, National University of Uzbekistan, Tashkent, Uzbekistan

Abstract

In the present paper the optimal quadrature formula for approximate evaluation of Fourier coefficients is constructed for functions of the space . At the same time the explicit formulas for optimal coefficients, which are very useful in applications, are obtained. The obtained formula is exact for constant. In particular, as consequences of the main result the new optimal quadrature formulas for approximate evaluation of integrals and are obtained. Furthermore, the order of convergence of the constructed optimal quadrature formula is studied.

Cite this article:

  • Nurali D. Boltaev, Abdullo R. Hayotov, Kholmat M. Shadimetov. Construction of Optimal Quadrature Formula for Numerical Calculation of Fourier Coefficients in Sobolev Space L2(1). American Journal of Numerical Analysis. Vol. 4, No. 1, 2016, pp 1-7. http://pubs.sciepub.com/ajna/4/1/1
  • Boltaev, Nurali D., Abdullo R. Hayotov, and Kholmat M. Shadimetov. "Construction of Optimal Quadrature Formula for Numerical Calculation of Fourier Coefficients in Sobolev Space L2(1)." American Journal of Numerical Analysis 4.1 (2016): 1-7.
  • Boltaev, N. D. , Hayotov, A. R. , & Shadimetov, K. M. (2016). Construction of Optimal Quadrature Formula for Numerical Calculation of Fourier Coefficients in Sobolev Space L2(1). American Journal of Numerical Analysis, 4(1), 1-7.
  • Boltaev, Nurali D., Abdullo R. Hayotov, and Kholmat M. Shadimetov. "Construction of Optimal Quadrature Formula for Numerical Calculation of Fourier Coefficients in Sobolev Space L2(1)." American Journal of Numerical Analysis 4, no. 1 (2016): 1-7.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction

Computation of integrals of strongly oscillating functions is one of the more important problems of numerical analysis, because such integrals are encountered in applications in many branches of mathematics as well as in other science such as quantum physics, flow mechanics and electromagnetism. Main examples of strongly oscillating integrands are encountered in different transformation, for example, the Fourier transformation and Fourier-Bessel transformation. Standard methods of numerical integration frequently require more computational works and they cannot be successfully applied.

The earliest formulas for numerical integration of rapidly oscillatory functions were given by Filon [3] in 1928. The Filon’s approach for Fourier integrals

is based on piecewise approximation of by arcs of the parabola on the integration interval. Then finite integrals on the subintervals are exactly integrated. The Filon’s approach was modified by many mathematicians and for integrals with different type highly oscillating functions many special effective methods such as Filon-type method, Clenshaw-Curtis-Filon type method, Levin type methods, modifed Clenshaw-Curtis method, generalized quadrature rule, Gauss-Laguerre quadrature are worked out (see, for example, [2, 4, 5, 6, 8, 9, 10, 14, 16, 21], for more review see, for instance, [7, 11, 13] and references therein).

In [12] the authors studied approximate computation of univariate oscillatory integrals (Fourier coefficients) for the standard Sobolev spaces of periodic and non-periodic functions with an arbitrary integer . They found matching lower and upper bounds on the minimal worst case error of algorithms that use function or derivative values. They also found sharp bounds on the information complexity which is the minimal for which the absolute or normalized error is at most .

In the work [18] the weight lattice optimal cubature formulas in the periodic Sobolev's space were constructed. In particular, from the result of the work [18], in univariate case when the weight is the function (where and is an integer), the Babuska's optimal quadrature formula for Fourier coefficients [1] was obtained.

The present work is also devoted to one of such methods, i.e. to construction of optimal quadrature formulas in the sense of Sard for approximate calculation of Fourier integrals.

We consider the following quadrature formula

(1)

here are coefficients, is Dirac’s delta function, is the indicator of the interval [0,1]. Functions belong to the space , where

is the Sobolev space of complex valued functions and the inner product in this space is defined by the equality

(2)

where is the conjugate function to the function and the norm of the function is correspondingly defined by the formula

and .

The following difference

(3)

is said to be the error of the formula (1), where

(4)

is the error functional of the formula (1).

Since the space is a Hilbert space, then by the Cauchy-Schwarz inequality

(5)

where is the conjugate space of the space .

Since the difference (3) is estimated with the help of the norm of the error functional

(6)

Therefore, the estimation of the error of the quadrature formula (1) over functions of the space is reduced to finding the norm (6) of the error functional in the conjugate space Clearly the norm of the error functional depends on coefficients. The problem of finding the minimum of the norm of the error functional by coefficients when the nodes are fixed (in our case the distances between neighbor nodes of the formula (1) are equal, i.e. ) is called Sard’s problem and the obtained formula is called the optimal quadrature formula in the sense of Sard. This problem was first investigated by Sard [15] which corresponds to the case of the quadrature formula (1).

The main aim of the present work is to solve the Sard problem for the quadrature formula of the form (1) in the space using the Sobolev method for , i.e. to find the coefficients , that satisfy the following equality

(7)

Thus in order to construct optimal quadrature formulas of the form (1) in the sense of Sard we need to solve the following problems

Problem 1. Find the norm of the error functional of the quadrature formulas of the form (1) in the space

Problem 2. Find the coefficients that satisfy equality (7).

The paper is organized as follows: in Section 2 the extremal function of the quadrature formula (1) is found and with the help of this function the representation of the norm of the error functional is obtained. In Section 3, using Lagrange method, the system of linear equations for the optimal coefficients is obtained and the existence and uniqueness of the solution of this system is discussed. In Section 4 we give the method for solution of this system which allows to get the explicit formulas for optimal coefficients and we obtain the explicit formulas for the optimal coefficients that are very useful in applications. Finally, in Section 5 we calculate the norm of the optimal error functional.

2. Extremal Function and the Norm of the Error Functional

In this section we solve Problem 1. To evaluate the norm of the error functional in space we use extremal function of the quadrature formula (1). The function is called the extremal for the given functional (see [19]) if the following holds

(8)

Since the space is a Hilbert space, then the extremal function in this space is found with the help of Riesz theorem. Then for the functional and for any function of the space there exists a unique function of the space for which the following holds

(9)

where is the inner product defined in the space . Since the error functional defined on the space , then from equality (9) we get the following condition which means exactness of the quadrature formula (1) on constant term, i.e.

(10)

It follows that the extremal function is a solution of the following boundary problem

(11)

From S.L.Sobolev result [19, 20] about extremal function of quadrature formulas, in particular when , we get the following result.

Theorem 1. The solution of the boundary problem (11) is the extremal function and has the form:

where

(12)

and is a complex number.

Recall that is the convolution and the convolution of two functions is defined by the formula

Taking into account the definition of convolution and equality (4) we calculate the convolution , i.e.

where and are conjugate to and , respectively.

Then keeping in mind (9), (10) and (12) we have

(13)

Further, simplifying the last equality we get

(14)

We show that the right hand side of (13) is real.

Really, let

(15)

where and are real.

Using Euler’s formula we get the following equalities

Keeping in mind the last three equalities, from (14) for the norm of the error functional we have

(16)

And from (10), keeping in mind (15), we have the following equalities

(17)

Therefore, Problem 1 is solved.

3. Linear System for Optimal Coefficients

Here we solve Problem 2. To find the minimum of the expression (16) under the condition (17) we apply Lagrange method of undetermined coefficients. Consider the function

(18)

Equating partial derivatives of the function (18) by and by we get the following system of linear equations

(19)
(20)
(21)
(22)

Multiplying (20) and (22) by and adding to (19) and (21), respectively, using denotations (15) and , for the coefficients of the optimal quadrature formulas of the form (1) we get the following system of linear equations

(23)
(24)

Existence and uniqueness of the solution of system (23)-(24) are proved in [12, 13], i.e. the square of the norm (14) of the error functional , being multidimensional quadratic function of the coefficients , has a unique minimum in certain value of .

As it was said in the first section the quadrature formula (1) with coefficients , corresponding to this minimum is called the optimal quadrature formula in the sense of Sard and are called the optimal coefficients.

Below, for the purposes of convenience, the optimal coefficients will be denoted as .

The method of solution of system (23)-(24)

Here we give the method of solution of system (23)-(24). In this section we use similar method, suggested by S.L.Sobolev [19, 20] for finding coefficients of optimal quadrature formulas in the space . Here we mainly use the concept of functions of discrete argument and operations on them. Theory of discrete argument functions is given in [19]. For completeness we give some definitions about functions of discrete argument from [19].

Definition 1. A function is called function of discrete argument if it is defined on some set of integer values of .

Definition 2. We define the inner product of two functions and as the following number

(25)

If the series on the right hand side of equality (25) converges absolutely.

Definition 3. We define convolution of two functions and the inner product

Now we return to our problem. Suppose for and . Then, using the above definitions, we rewrite system (23)-(24) in the convolution form

(26)
(27)

Here

(28)

where the function is defined by (12).

Problem 3. Find and which satisfy the system (26)-(27) for given .

Further we investigate Problem 3 which is equivalent to Problem 2 and instead of we introduce the functions

(29)
(30)

In this statement it is necessary to express the coefficients by the function . For this we have to construct such operator which satisfies the equality

(31)

where i.e. is discrete delta function.

In the works [17, 19] the discrete analogue of the differential operator was investigated and in the work [17] was constructed. In particular, from the results of [17] for we get the following theorems.

Theorem 2. The discrete analogue of the differential operator satisfying equality (31) has the form

(32)

Theorem 3. The discrete analogue of the differential operator satisfies the following equalities

Then taking account (30), (31) and Theorems 2 and 3 for the optimal coefficients we have

(33)

Thus, if we find then optimal coefficients will be found from (33). To calculate convolution (33) we have to find the representation of the function for all integer values of. From (26) we obtain that for . Now we find the representation of for and .

Since for and , then

Suppose , then keeping in mind (12) and (27) we have

(34)

Similarly, for

(35)

Then, from (30) taking into account (34) and (35), we get

where is defined by (28).

We denote

(36)

Then taking account of the last representation of the function , we get the following problem which is equivalent to Problem 3.

Problem 4. Find the solution of the equation

(37)

having the form

(38)

Clearly that Problem 4 is equivalent to Problem 3 and Problem 2 respectively. Here and are unknowns. These unknowns can be found from (37). For and from (37) we get the following system

Hence using (32) and (38), we have

(39)

Then

(40)

So that for from (38), taking into account (39), we have

(41)

where is defined by equality (28).

Now, using the last equality from (33) can be calculated optimal coefficients.

4. Coefficients of the Optimal Quadrature Formulas (1)

For the coefficients of the optimal quadrature formulas of the form (1) the following theorem holds.

Theorem 4. Coefficients of the optimal quadrature formulas of the form (1) in the sense of Sard when in the space have the form

(42)

Proof. Let , then from (33) we get

Now using equalities (32) and (41), from the last equality for we correspondingly get the explicit formulas for the coefficients , which are given in the statement of the theorem.

Theorem 4 is proved.

Note that the formulas for the optimal coefficients are decomposed into two parts – real and imaginary parts. Therefore from Theorem 4 we get the following.

Corollary 1. The coefficients of the optimal quadrature formulas of the form

in the sense of Sard when in the space of real valued function have the form

(43)

Corollary 2. The coefficients of the optimal quadrature formulas of the form

in the sense of Sard when in the space of real valued functions have the form

(44)

5. The Norm of the Optimal Error Functional

In this section we investigate order of convergence of the constructed optimal quadrature formula of the form (1) with the coefficients which are presented in Theorem 4.

It is known that the absolute value of the error of the optimal quadrature formula (1) with coefficients (42) is estimated using the Cauchy-Schwarz inequality as follows

where functions belong to the space . This means that in order to find upper bound of the error of the constructed optimal quadrature formula we should calculate .

The following hold.

Theorem 5. The square of the norm of the error functional (2) of the optimal quadrature formula (1) on the space has the forms

(45)

and

(46)

Proof. We rewrite the equality (16) in the following form

Taking into account (40) we get that . Then from (19) and (20) we have

and

respectively. Keeping in mind the last two equalities we obtain

Hence calculating the definite integrals and using (43) and (44), after some simplifications we get (45). Finally, expanding the expression (45) in a series in powers of h we have (46). Theorem 5 is proved.

Remark. Order of convergence of the constructed optimal quadrature formula (1) with coefficients (42) is .

6. Conclusion

Thus in the present work we have constructed the optimal quadrature formula for approximate calculation of the Fourier coefficients of functions from the Sobolev space . And we have obtained the explicit formulas for the optimal coefficients which are very useful in applications. The obtained quadrature formula is exact for the constant term. In particular, as a corollary from the main result the optimal quadrature formulas for approximate calculation of integrals have been obtained. Furthermore, we have studied the order of convergence of our optimal quadrature formula.

Acknowledgement

The final part of this work has been done in the Friedrich-Schiller University of Jena, Germany. A.R.Hayotov is very grateful to professor Erich Novak and his research group for hospitality. A.R. Hayotov thanks the DAAD for scholarship. Authors thank the reviewer for remarks and suggestions, which have improved the quality of the paper.

References

[1]  Babuska, I., Vitasek, E., Prager, M. Numerical processes in differential equations. Wiley, New York, 1966.
In article      
 
[2]  Bakhvalov, N.S., Vasil'eva, L.G. Evaluation of the integrals of oscillating functions by interpolation at nodes of Gaussian quadratures (Russian) USSR Computational Mathematics and Mathematical Physics. 8, 1968, 241-249.
In article      
 
[3]  Filon, L.N.G. On a quadrature formula trigonometric integrals // Proc. Roy. Soc. Edinburgh. 1928. Pp.38-47.
In article      
 
[4]  Flinn, E.A. A modification of Filon’s method of numerical integration, J. Assoc. Comp. Mach. 7 (1960) 181-184.
In article      
 
[5]  Havie, T. Remarks on an expansion for integrals of rapidly oscillation functions, BIT, 13 (1973) 16-29.
In article      
 
[6]  Iserles, A., Nørsett, S.P. On quadrature methods for highly oscillatory integrals and their implementation, BIT Numer Math 44: 755-772, 2004.
In article      
 
[7]  Iserles, A., Nørsett, S.P. Efficient quadrature of highly oscillatory integrals using derivatives, Proc. R. Soc. A (2005) 461, 1383-1399.
In article      
 
[8]  Levin, D. Fast integration of rapidly oscillatory functions, J. Comput. Appl. Math., 67 (1996) 95-101.
In article      
 
[9]  Melenk, J.M. On the convergence of Filon quadrature, Jour of Comp and Appl Math 234 (2010) 1692-1701.
In article      
 
[10]  Milovanovic, G.V. Numerical calculation of integrals involving oscillatory and singular kernels and some applications of quadratures, Computers Math. Applic. Vol. 36, no. 8, (1998). 19-39.
In article      
 
[11]  Milovanovic, G.V., Stanic, M.P. Numerical integration of highly oscillating functions // Analytic Number Theory, Approximation Theory, and Special Functions. Springer, 2014. Pp. 613-649.
In article      
 
[12]  Novak, E., Ullrich, M., Wozniakowski, H. Complexity of oscillatory integration for univariate Sobolev space, Journal of Complexity, 31 (2015) 15-41.
In article      
 
[13]  Olver, S. Numerical approximation of highly oscillatory integrals, PhD dissertation, University of Cambridge, 2008.
In article      
 
[14]  Olver, Sh. Fast, numerically stable computation of oscillatory integrals with stationary points, BIT Numer Math (2010) 50: 149-171.
In article      
 
[15]  Sard, A. Best approximate integration formulas; best approximation formulas, Am. J. Math. 71 (1949) 80-91.
In article      
 
[16]  Shampine, L.F. Efficient Filon method for oscillatory integrals, Appl Math and Comp 221 (2013) 691-702.
In article      
 
[17]  Shadimetov, Kh.M. The discrete analogue of the differential operator and its construction, Quest. Comput. Appl. Math., Tashkent, 1985, pp. 22-35 (2010).
In article      
 
[18]  Shadimetov, Kh.M. Weight optimal cubature formulas in Sobolev's periodic space, (Russian) Siberian J. Numer. Math. -Novosibirsk, v.2, no. 2 (1999) 185-196.
In article      
 
[19]  Sobolev, S.L. Introduction to the Theory of Cubature formulas. – Moscow: Nauka, (Russian) 1974-808 p.
In article      
 
[20]  Sobolev, S.L. The coefficients of optimal quadrature formulas // Selected works of S.L. Sobolev. – Berlin: Springer, 2006).Pp. 561-566.
In article      
 
[21]  Xu, Z., Milovanovic, G.V., Xiang, S. Efficient computation of highly oscillatory integrals with Henkel kernel, Appl. Math. and Comp. 261 (2015) 312-322.
In article      
 
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn