A construction of nonnegative approximate quadratures
Philip J. Davis · Mathematics of Computation · 1967
Introduction.In a paper which appeared in 1957, V. Tchakaloff [1] proved the following theorem.Let B be a closed bounded set in the plane with positive area.Let i, 02, • • -, n be N linearly independent and continuous functions of x, y in B, of which one does not vanish in B. Then we can find N points P¡:(xí, y¡) lying in B and N weights w¡ = 0 such that (1.1) // jdxdy = ¿ w¿y(Pí) , i =1,2, ...,N.Tchakaloff's demonstration is a very beautiful one, involving the theory of convex bodies.A separating hyperplane is employed and a nonconstructive proof is obtained.The theorem is valid for weighted integrals of dimension d 2ï 1.Equivalent results on finite moment spaces were obtained earlier by various authors.See, e.g., Karlin and Studden [2, Chapter II].Tchakaloff's independent work appears to be the first to formulate the result explicitly as in (1.1), thereby stressing its numerical analysis aspect.This result is interesting for numerical analysis because: (1) Quadrature rules with nonnegative weights are more favorable than rules with mixed weights in that they lead to more stable computations ; (2) Interpolating quadrature formulas determined by brute force methods do not often yield weights that are of one sign.The purpose of the present paper is to give an alternative proof of Tchakaloff's theorem which is constructive in its nature.The present proof is also a more "elementary" one than Tchakaloff's in that it makes use only of the familiar raw materials of elementary numerical analysis.Extensions and numerical applications will be published subsequently by the author and by M. W. Wilson.2. An Alternate Proof of Tchakaloff's Theorem.In this proof we limit ourselves to integrals of dimension d = 2 and to functions i, i, • • •, n that are monomials (i.e., powers) in x, y.This limitation will still enable us to exhibit the essential features of the method.We begin with a number of very simple lemmas.Lemma 1.Let fafa y) = 1, t(x, y) = x, fo(x, y) = y, 4>¿x, y) = x2, s(£, 2/) = xy, ñ(x,y) = y2, • ■ • be an arrangement of the powers x^', 0 ^ i, j n are linearly independent.That is, if f(x, y) = Y^i=i arfiix, y) = 0 in a region R, then ai = 0, i = 1, 2, • • •, N.Proof.Call m + n the degree of the monomial xmyn.We have 3m+n xmy/dxmdyn = m \, and dm+nxm'yn'/dxmdy" = Oif m' + n' = m + n but (m', ri) ^ (m, n), or if