Quadrature Rules

In the previous sections, it was observed that in multiscale approximation of functions, evaluation of integrals of product of integrable function f(x) (say), and multiresolution generator (MRG) or scale function and wavelet is an important ingredient. In most of the cases such integrals cannot be evaluated analytically either due to

  • (i) complicated form of f(x),
  • (ii) non-availability of a formal rule of correspondence of MRG with the independent variable x, e.g., scale functions and wavelets in Daubechies family, or
  • (iii) discontinuity of some elements of the basis in their support, e.g., some wavelets in multiwavelet family.

It is thus desirable to seek a quadrature rule for their evaluations. This is discussed by Panja and Mandal (Panja and Mandal, 2015). A major part of the material presented below is taken from this paper.

Daubechies family

Although standard quadrature rules can be used to evaluate integrals involved in multiscale approximation of functions numerically whenever dependence of MRG on x is known explicitly, these are not useful when explicit expression for MRG is not available or evaluation of MRG at the nodes of the quadrature formula is not possible. MRG in Daubechies family is one such example. So, it is desirable to develop a quadrature rule for evaluation of integrals involving product of scale function/wavelet and integrable functions with reasonable order of accuracy through the exercise of minimum arithmetic calculations.

Several researchers attempted to develop quadrature rules for numerical evaluation of such integrals with full or partial support of Daubechies scale function/wavelet within the domain of integration. The main difficulty of pursuing the usual steps for developing Gauss-type quadrature rule for such integrals is either the presence of some nodes outside the support of scale functions/wavelets or some of these are complex. The main reason for such inconvenience is the violation of desired non- negativity of the weight function by the scale function/wavelet involved in the integrals. Initially, Beylkin et al. (Beylkin et ah, 1991) and subsequently, Sweldens and Piessens (Sweldens and Piessens, 1994a; Sweldens and Piessens, 1994b), Kwon (Kwon, 1997) tried to resolve the first difficulty mentioned above by invoking the shifting trick. In their method, Sweldens and Piessens (Sweldens and Piessens, 1994b) tried to determine a shift in the nodes of Newton-Cotes type quadrature rule so that a r-point quadrature formula can achieve the degree of accuracy r instead of 2r — 1 as in the Gauss-type quadrature rule involving the same number of nodes. Dahmen and Micchelli (Dah- men and Micchelli, 1993) dealt with such problem from the point of view of stationary subdivision schemes. Their main idea was to identify such integrals as components of the unique solution of a certain eigenvalue-eigenvector-moment problem involving the filter coefficients of the refinement equation. But the rate of convergence of this method is somewhat slow.

In their investigations, Johnson and his co-workers (Johnson et al., 1999), Barinka et al. (Barinka et al., 2001; Barinka et ah, 2002), Xiao et al. (Xiao et ah, 2006), Li (Li and Chen, 2007) tried to employ the usual steps for derivation of Gauss-type quadrature rule involving positive semi definite weight functions. Since Daubechies scale function satisfies all other properties of weight function except the non-negativity condition, they tried to resolve this deficiency by invoking the lifting trick. But introduction of additional term into the theory reduces the degree of precision of the quadrature rule.

It is thus natural to explore what unpleasant situation may appear if one suppresses the non- negativity condition on the weight function associated with the quadrature rule. In their investigations, Laurie and de Villiers (Laurie and De Villiers, 2004) mentioned that non-negativity of weight function is a sufficient condition for the existence of Gauss-type quadrature rule. Instead, if the mask or filter in the refinement equation for scale function ip satisfies some conditions and has finite moments of certain order, then a quadrature rule can be derived based on these moments. But the conditions on filter coefficients stated there imply the non-negativity of the refinable function which does not hold by the filter associated with the refinement equation for the Daubechies family of scale functions.

However, Gautschi (Gautschi, 2004) pointed out some relaxation of the non-negativity requirement and defined quasi-weight function as follows. A real or complex valued measure <7A = u>(x)dx, ш(х) being a weight function, is said to be quasi-definite if all its Hankel determinants An = detMn of the Hankel matrices

are non-zero. Here, щ = ^ xlu>(x)dx is the ith moment of the weight function u>(x) within V = supp to. The formal orthogonal polynomials (FOP) Pn(x) with respect to ш(х) are defined as a

system of monic polynomials Po, Pi, P2,......satisfying < Pm. P„ >= v P,n(x)Pn(x)oj(x)dx = 0

for m = n, < Pm, Prn >= 0, (m = 0,1,2, • • •). There exists a unique system of FOPs Po, Pi, P2,......

with respect to the quasi-definite measure ш(х)dx. Since Daubechies scale functions have all these properties except vanishing of Hankel determinant Д2 for each member of its family, we call them pseudo-weight functions and explore whether a Gauss-type quadrature formula can be derived based on that sequence of formal orthogonal polynomials for getting highly accurate approximate values of integrals involving product of any integrable function and the Daubechies scale function.

It was pointed out by Kessler et al. (Kessler et al., 2003b) that unlike the real nodes and weights for Gauss quadrature rule involving non-negative weight functions, some nodes and weights for pseudo-weight functions are sometimes complex. It was suggested that “when nodes and weights fail to occur real, it is best to simply assign real quadrature points that lie on the support of the scaling function. In doing this some accuracy is sacrificed, but is easy to go to higher order”. Here we explore whether retaining all real as well as complex roots of the formal polynomials associated with the Daubechies scale function/wavelet as the nodes of the quadrature rule results in any difficulty for the evaluation of such integrals.

Nodes, weights and quadrature rules

The aim of Gauss-type quadrature rule is to attain better approximate numerical values of definite integrals by performing relatively less arithmetic operations. While Newton-Cotes like quadrature rules with n nodes provide exact values for polynomial integrands up to degree n — 1, Gauss-type quadrature rule containing the same number of nodes provides exact value of the integral involving product of positive semi-definite weight function and polynomial up to degree 2n — 1. The reason for additional accuracy is the higher smoothness of the polynomial used to approximate the integrand in the Gauss quadrature formula.

Instead of providing nodes as well as values of the integrand a priori in Newton-Cotes like quadrature rules, nodes for Gauss quadrature formula are determined as the zeros of a polynomial which is orthogonal to other lower degree polynomials relative to some positive definite inner product. The inner products < Pm, Pn > are defined as v Pm(x)Pn(x)u>(x)dx, where ш(х) is positive definite within T>. The positive definiteness of the inner product is asserted through the following theorem (Gautschi, 2004, p2,Th.l.2).

Theoi'em 3.2. The inner product < Pm, Pn > is positive definite on the space of real polynomials if and only if the Hankel determinant An is strictly positive for all nN. It is positive definite on Vd (the space of all polynomials of degree < d) if and only if An > 0 for n = 1,2, • ■ ■ ,d + 1.

Furthermore, the relation between positive definiteness of the inner product and the existence of orthonormal polynomials is asserted by the theorem (Gautschi, 2004, p3,Th.l.7):

Theorem 3.3. If the inner product as mentioned above is positive definite in Vd but not on Vn for any n > d, then there exists only a finite number d + I of orthogonal polynomials of maximum degree d.

The location of zeros of orthogonal polynomials (nodes of the quadrature formula) is guided by (Gautschi, 2004, p7)

Theorem 3.4. If the weight function u>(x) involved in the inner product introduced in Theorem

3.1 does not change sign in V, the polynomial Pr possesses r distinct real zeros, all of which lie within T>.

Thus the important restriction on approximating the integrand apart from the weight function by a polynomial of degree r with less error having interpolating points within the support of ш(х) is that ш(х) > 0. As mentioned in the introduction, Gautschi (Gautschi, 2004) pointed out the existence of FOPs corresponding to the inner product involving a quasi-weight function for which the Hankel determinant Д,- is non-zero instead of being positive definite. Since most of the MRGs of MRA satisfy all the requirements for existence of orthogonal polynomials, viz., (i) w(x)dx = 1, (ii) ///' = p xroj(x)dx (r € N) exists, except the non-negativity condition oj(x) > 0, it is of obvious mathematical interest to explore whether a Gauss-type quadrature formula can be possible for the integrals of product of Daubechies interior, boundary and truncated scale functions with other integrable functions.

Formal orthogonal polynomials, nodes, weights of scale functions

Scale functions in most of the wavelet bases may not be positive semi-definite. Consequently, evaluation of integrals involving those functions may not be possible by using classical Gauss type quadrature rules. This needs to be modified appropriately. In the subsequent part of this section, a Gauss type quadrature rule with complex nodes and weights have been developed for the integrals involving (interior, truncated and orthogonal) scale functions in Daubechies family.

< Prev   CONTENTS   Source   Next >