Interpolation from spaces spanned by monomials
- PDF / 208,853 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 91 Downloads / 197 Views
Advances in Computational Mathematics (2007) 26: 63–70
Interpolation from spaces spanned by monomials C. de Boor PO Box 1076, Eastsound, WA 98245, USA E-mail: [email protected]
Received 2 September 2004; accepted 22 December 2004 Communicated by J. Carnicer and J.M. Peña
Dedicated to Mariano Gasca on the occasion of his sixtieth birthday
This is an extension and emendation of recent results on the use of Gauss elimination in multivariate polynomial interpolation and, in particular, ideal interpolation. Keywords: multivariate, polynomial, interpolation
Let ⊂ (Fd → F) be the space of all polynomials in d real (F = R) or complex (F = C) variables. Let Q be an n-row map on , i.e., a linear map from to Fn , and consider the task of solving Q? = a for given a ∈ Fn . We assume that this problem has a solution for arbitrary a ∈ Fn , i.e., that Q is onto. Then there is a standard recipe for finding all solutions, namely Gauss elimination applied to the Gram matrix QV = (ηi vj : i = 1:n, j ∈ J ), with the linear functionals ηi the rows of the row map Q, i.e., Qf =: (ηi f : i = 1:n), and the polynomials vj the columns of the invertible column map vj a(j ) V = [vj : j ∈ J ] : FJ0 → : a → j
or basis for (indexed by some set J ). Here, FJ0 := {a : J → F: # supp a < ∞}, hence V is well-defined.
64
C. de Boor / Interpolation
Take for V a monomial basis, i.e., the column map Zd V = ( )α : α ∈ Zd+ : F0 + → : pˆ → p := ( )α p(α), ˆ α
with its columns the monomials ( )α : Fd → F : x → x α := x(1)α(1) · · · x(d)α(d) arranged in some order in which each collection of columns has a left-most one (i.e., the order must be a well-ordering). Since Q is onto, QV is of full rank, hence has exactly n bound columns, i.e., columns that are not weighted sums of columns to the left of it. This is a standard result of basic linear algebra in case V has finitely many columns but needs, perhaps, a proof in the present setting, of a V with infinitely many columns. For this, let , ≺, etc, indicate the order on Zd+ corresponding to the order in which the monomials appear as columns in V . Further, let βj := min j , j := γ : rank Q ( )α : α γ j , j = 1:n. There is, in fact, such a minimum since j must be nonempty (due to the fact that rank QV = n), hence, by our assumption on the columns’ ordering, must have a leftmost element. Further, with βj that left-most element, column βj is necessarily bound (since its adjunction to Q[( )α : α ≺ βj ] raises the rank). It follows that all the columns of the square matrix QVβ , with Vβ := ( )βj : j = 1:n , are bound, hence QVβ is invertible. This makes F := ran Vβ a monomial subspace (i.e., a space spanned by monomials) that is correct for Q in the sense that Q maps it 1-1 onto Fn , i.e., F contains, for every a ∈ Fn , exactly one f that matches the information a in the sense that Qf = a. Put differently, F contains, for each p ∈ , exactly one f that agrees with p at Q in the sense that Qf = Qp. We can write this f in the form f = Pp, with P := Vβ (QVβ )−1 Q the li
Data Loading...
