Techniques and algorithms for finding univariate Newton interpolating polynomials can be extended to multivariate data points by different generalizations. The Newton basis format and divided-difference algorithm for coefficients can be generalized in a straightforward way when interpolating at nodes on a grid. Two different approaches, the tensor product case or the triangular case, are usually considered. The multi-index notation is used to refer to nodes. Node configurations where the tensor product case applies are called lower sets, and they include $n$-dimensional rectangles and triangles. Arbitrary distinct nodes do not ensure unique interpolating polynomials but, when possible, a different basis generalization, which we call Newton--Sauer basis, results in a nice triangular linear system for the coefficients. For the right number of distinct nodes, an algorithm based on Gaussian elimination produces either this Newton--Sauer basis or a polynomial that is zero on all nodes, showing that unique interpolation is impossible. The algorithm may also be used on any distinct nodes to produce a polynomial subspace of minimal degree where unique interpolation is possible.
|
