# Lagrange Multivariate Polynomial Interpolation: A Random Algorithmic Approach

Authors: A. Essanhaji; M. Errachid
Journal: Journal of Applied Mathematics
 (2022)

---

## Abstract

The problems of polynomial interpolation with several variables present more difficulties than those of one-dimensional interpolation. The first problem is to study the regularity of the interpolation schemes. In fact, it is well-known that, in contrast to the univariate case, there is no universal space of polynomials which admits unique Lagrange interpolation for all point sets of a given cardinality, and so the interpolation space will depend on the setZ of interpolation points. Techniques of univariate Newton interpolating polynomials are extended to multivariate data points by different generalizations and practical algorithms. The Newton basis format, with divided-difference algorithm for coefficients, generalizes in a straightforward way when interpolating at nodes on a grid within certain schemes. In this work, we propose a random algorithm for computing several interpolating multivariate Lagrange polynomials, called RLMVPIA (Random Lagrange Multivariate Polynomial Interpolation Algorithm), for any finite interpolation set. We will use a Newton-type polynomials basis, and we will introduce a new concept called Z,z-partition. All the given algorithms are tested on examples. RLMVPIA is easy to implement and requires no storage.


---

## Body

## 1. Introduction

LetK be a commutative field and p,n∈ℕ∗. By Πp=Kx1,⋯,xp, we denote the algebra of all polynomials in p variables, and we denote by Πdp the subspace of all polynomials of total degree less than or equal to d, where d is a nonnull integer.Given a finite interpolation setZn=z1,⋯zn⊂Kp of distincts nodes, the Lagrange interpolation problem consists of finding, for a given data vector R=rz:z∈Zn∈KZn, a polynomial P∈Πp such that
(1)PZn=R,thatis,Pz=rz,z∈Zn.We will then say thatP is an interpolating polynomial for R on Z. More precisely, Zn is called poised or correct or unisolvent [1–3] for a subspace P of Πp; if the Lagrange interpolation problem (1) has a unique interpolating polynomial in P for any given data vector R=rz:z∈Zn∈KZn, it means, in other words, that the function
(2)P∈P↦Pz:z∈Zn∈KZnis a linear isomorphism. Then, it is necessary that dimP=n. The problem of researching such subspaces will be denoted PZn.In this article, we construct a random algorithm for finding several sub-spaces solutions of the problemPZn.It is well-known that in the univariate case (p=1) the Lagrange interpolation problem with respect to n distinct points is always uniquely solvable, if one takes P to be the space of all polynomials of degree less than or equal to n−1. In several variables, however, the situation is much more difficult. In order to successfully interpolate Zn on Πdp, we must have
(3)n=p+dp,since(4)dimΠdp=p+dp.And even if this is the case, there can be the problem that the points lie on some algebraic surface of degreed; i.e., there is some polynomial Q of total degree at most d which vanishes on Zn. For example, take p=2, d=1, and Z=−1,0,0,0,1,0; it is easy to see that the set Z is not poised on the space Π12=span1,x,y (since P=y vanishes on Z).So the poisedness of multivariate polynomial interpolation depends on the geometric structure of the interpolation setZn. Tensor product interpolation is the oldest particular case extending the univariate theory where the interpolation set and space are obtained by tensor products of the univariate ones. The Lagrange formula and the Newton formula with divided differences are easily extended to this problem, as can be found in [4–15].In a recent publication [7], the author proposed a generalization of the univariate program of Newton form basis and divided-difference algorithm in Kp. The required interpolation sets are those which admit an indexation having a regular structure as triangular, rectangular, or more generally a lower set [2, 7, 8, 16–18]. He shows how the index set structure appropriately determines the interpolation space. When the sum of indices is bounded by d, there is a unique interpolation with a polynomial of degree≤d.In [5], by using the Schur complements and the Sylvester identity, the authors established the RMVPIA (Recursive MultiVariate Polynomial Interpolation Algorithm) when the interpolation set is a full grid.Polynomial interpolation with several variables occurs in several topics of applied mathematics and engineering [19–22], hence the interest in seeking consistent and simple to implement polynomial interpolation algorithms.In this work, we propose a new algorithm for computing several interpolation spaces for any finite interpolation set. This algorithm which is called RLMVPIA (Random Lagrange MultiVariate Polynomial Interpolation Algorithm) is based on a recursive random scheme. RLMVPIA allows us to simultaneously determine interpolating polynomials. For that, we will use a Newton-type polynomials basis, and we will introduce a new concept calledZ,z-partition. All the given algorithms are tested on examples. As RMVPIA, RLMVPIA is easy to implement and requires no storage.The principle of our approach is to solvePZn knowing a solution of PZn−1, where Zn−1=z1,⋯,zn−1 is a subset of Zn with n−1 nodes. More precisely, if Pn−1 is an interpolation space for Zn−1, and Pn−1∈Pn−1 verifying Pn−1z=rz,z∈Zn−1; then, we construct, in a way, a polynomial Qn verifying
(5)Qnz=0,∀z∈Zn−1,Qnzn≠0.SoPn=Pn−1+KQn is a solution of PZn, and the solution of (1) in Pn is a polynomial in the form
(6)Pn=Pn−1+snQn,where sn is a scalar to compute.This work is organized as follows: in Section2 we present the notion of Z,z-partition. In Section 3, we give the algorithm RLMVPIA. In Section 4, we illustrate our algorithms by different examples.


## 2.Z,z-Partition Concept

This new approach takes into consideration the distribution of the nodes of the considered interpolation setZn by introducing a new concept described in the following. We define a notion of Z,z-partition, and we present a random algorithm for computing the polynomials Qi, for i∈1;n, which will be used for giving the algorithm RLMVPIA.In this section,Z is a finite set of Kp, p∈ℕ∗, and z∈Kp\Z. For k∈1,⋯,p, we note xk the canonical coordinated form, defined as
(7)xk:Kp⟶Kt=α1,⋯,αp↦xkt=αk,and xkZ=xkt:t∈Z.Definition 1.
Fork∈1;p, let Ik be a subset of xkZ.
(1)
It will be said thatI1,⋯,Ip is a Z-partition if(8)∀t∈Z,∃k∈1;p:xkt∈Ik
In this case,∑k=1pcardIk is called the length of the Z-partition I1,⋯,Ip.
(2)
Letz∈Kp\Z. It is said that I1,⋯,Ip is a Z,z-partition if(a)
I1,⋯,Ip is a Z-partition(b)
∀k∈1;p,xkz∉IkProposition 2.
For allz∈Kp\Z, a Z,z-partition still exists.Proof.
To prove that, we show how to construct aZ,z-partition. Let ϕ be the function
(9)Z⟶1;p,t⟶maxk:xkt≠xkz.
ϕ is well defined because z∉Z. We set
(10)ϕZ=p1,⋯,pi⊂1;p,and for k∈1;p, we take
(11)Ik=xkϕ−1k,ifk∈p1,⋯,pi,∅,else.
ThenI1,⋯,Ip is a Z,z-partition.
To illustrate the proof of the proposition, we give below some examples in the casesp=2 and p=3


### 2.1. Casep=2

Example 1.
We set(12)Z=1,1,2,1,0,2,1,2,2,2andz=3,1.
We haveϕZ=1,2 and
(13)ϕ−11=1,1,2,1,ϕ−12=0,2,1,2,2,2.
It follows that(14)I1=x1ϕ−11=1,2,I2=x2ϕ−12=2.Example 2.
We take(15)Z=1,−1,1,0,1,1,1,2,1,3,1,4,5,4,6,4,7,4,8,4,9,4,with z=11,5, and we have ϕZ=2, so we obtain
(16)I1=∅,I2=−1,0,1,2,3,4.


### 2.2. Casep=3

Example 3.
We take(17)Z=0,1,0,1,1,0,7,−1,0,2,2,−1,2,2,3,0,3,1,5,3,1,−10,3,1,with z=2,3,1, and we have ϕZ=1,3,
(18)ϕ−11=0,3,1,5,3,1,−10,3,1,ϕ−13=0,1,0,1,1,0,7,−1,0,2,2,−1,2,2,3,so
(19)I1=0,5,−10,I2=∅andI3=0,−1,3.
Now, one can easily get the following result.Proposition 6.
LetI=I1,⋯,Ip be a Z,z-partition, and let QI be the polynomial associated, given by
(20)QI=∏k=1p∏α∈Ikxk−α,with the convention that the product is equal to 1 when the set of indices is empty. So we have
(21)∀t∈Z,QIt=0.QIz≠0.The following algorithm called ZPNA (Z,z-Partition Newton Algorithm) randomly constructs a Z,z-partition and the associated polynomial.Algorithm 1:ZPNA
input:Z,zInitialization:I1,⋯,Ip : p empty setsfort in Z (a random choice)Index=1,⋯,pi= a random number of Index.whilexit=xiz:removei from Indexi= a random number of Indexendwhileremovei from Indexforj in Index:ifxjtinIj:pass to next element inZendifendforifxit not in Iiaddxit to IiQ=Q∗xi−xitendifendforoutputQ,I1,⋯,IpRemark 7.
(1)
All operations in the algorithm ZPNA have constant costs, so the complexity depends linearly on the length ofZ(2)
For aZ,z-partition, the total degree of the associated polynomial is equal to the length of the partition which is less than ∑k=1pcardxkZ(3)
The algorithm ZPNA is not deterministic. If we apply the algorithm several times, one can obtain severalZ,z-partitions from which we can choose those of minimum length
Point 3 of the precedent remark can be illustrated by the following example:(22)Z=1,−1,1,0,1,1,1,2,1,3,1,4,5,4,6,4,7,4,8,4,9,4,and z=11,5. Applying the algorithm ZPNA several times, we get the following Z,z-partitions and the associated polynomials.
(1)
I1=1,I2=4 and Q=x−1y−4(2)
I1=1,5,6,7,I2=−1,4 and Q=x−7x−6x−5x−1y−4y+1(3)
I1=∅,I2=−1,0,1,2,3,4 and Q=yy−4y+1y−1y−2y−3(4)
I1=1,5,6,7,8,I2=−1,0,1,2,4 and Q=yx−8x−7x−6x−5x−1y−4y−2y−1y+1It is clear that the first solution is the best.Theorem 8.
The algorithmZPNA is correct.Proof.
For proving that, we use loop invariant to help us understand why an algorithm is correct. We must show three things about a loop invariant:(i)
Initialization: it is true prior to the first iteration of the loop.(ii)
Maintenance: if it is true before an iteration of the loop, it remains true before the next iteration.(iii)
Termination: when the loop ends, the invariant gives us a useful property showing that the algorithm is correct.
For the ZPNA algorithm, we note fork∈1;n, z1,⋯zk the elements treated in the k first iterations, Zk=z1,⋯zk et I1k,⋯,Ipk the values of I1,⋯,Ip in the iteration k. So the following property is a loop invariant: At the start of each iteration of the for loop, the I1k−1,⋯,Ipk−1 is a Zk−1,z-partition.
For initialization, we start by showing that the loop invariant holds before the first loop iteration: whenk=1, the I1k−1,⋯,Ipk−1 are empty, and no item is treated, we take Z0=∅, so by convention, the I1k−1,⋯,Ipk−1 is a Zk−1,z-partition.
For maintenance, next, we tackle the second property, showing that each iteration maintains the loop invariant. Assume that theI1k−1,⋯,Ipk−1 is a Zk−1,z-partition, we note zk the element chosen at the start of the iteration k, as z∉Z, the loop (while xit=xiz) ends, so we note i the index founded such as xizk≠xiz. The analysis of the sequence of the iteration k makes it possible without difficulty to assert that Ijk=Ijk−1 if j≠i and for j=i two cases arise: either Iik=Iik−1 if xjzk is already present in one of the Ij, otherwise Iik=Iik−1∪xizk. In both cases, we have I1k,⋯,Ipk is a Zk,z-partition: for t∈Zk, if t∈Zk−1, then there is a j∈1;n such as xjt∈Ij because I1k−1,⋯,Ipk−1 is a Zk−1,z-partition; if t=zk by construction, we also have the result. On the other hand, as xjz is not in any of the Ijk−1,j∈1;n, and as by construction xizk≠xiz, it follows that xiz∉Iik, hence the result.
For termination, we examine finally what will happen when the loop terminates. When the loop terminates (fort in Z (a random choice)), the set Zn=Z, with the invariant of the loop, we have I1n,⋯,Ipn (which are the sets returned by the algorithm) which is a Zn=Z,z-partition. Therefore, the algorithm is correct.


## 2.1. Casep=2

Example 1.
We set(12)Z=1,1,2,1,0,2,1,2,2,2andz=3,1.
We haveϕZ=1,2 and
(13)ϕ−11=1,1,2,1,ϕ−12=0,2,1,2,2,2.
It follows that(14)I1=x1ϕ−11=1,2,I2=x2ϕ−12=2.Example 2.
We take(15)Z=1,−1,1,0,1,1,1,2,1,3,1,4,5,4,6,4,7,4,8,4,9,4,with z=11,5, and we have ϕZ=2, so we obtain
(16)I1=∅,I2=−1,0,1,2,3,4.


## 2.2. Casep=3

Example 3.
We take(17)Z=0,1,0,1,1,0,7,−1,0,2,2,−1,2,2,3,0,3,1,5,3,1,−10,3,1,with z=2,3,1, and we have ϕZ=1,3,
(18)ϕ−11=0,3,1,5,3,1,−10,3,1,ϕ−13=0,1,0,1,1,0,7,−1,0,2,2,−1,2,2,3,so
(19)I1=0,5,−10,I2=∅andI3=0,−1,3.
Now, one can easily get the following result.Proposition 6.
LetI=I1,⋯,Ip be a Z,z-partition, and let QI be the polynomial associated, given by
(20)QI=∏k=1p∏α∈Ikxk−α,with the convention that the product is equal to 1 when the set of indices is empty. So we have
(21)∀t∈Z,QIt=0.QIz≠0.The following algorithm called ZPNA (Z,z-Partition Newton Algorithm) randomly constructs a Z,z-partition and the associated polynomial.Algorithm 1:ZPNA
input:Z,zInitialization:I1,⋯,Ip : p empty setsfort in Z (a random choice)Index=1,⋯,pi= a random number of Index.whilexit=xiz:removei from Indexi= a random number of Indexendwhileremovei from Indexforj in Index:ifxjtinIj:pass to next element inZendifendforifxit not in Iiaddxit to IiQ=Q∗xi−xitendifendforoutputQ,I1,⋯,IpRemark 7.
(1)
All operations in the algorithm ZPNA have constant costs, so the complexity depends linearly on the length ofZ(2)
For aZ,z-partition, the total degree of the associated polynomial is equal to the length of the partition which is less than ∑k=1pcardxkZ(3)
The algorithm ZPNA is not deterministic. If we apply the algorithm several times, one can obtain severalZ,z-partitions from which we can choose those of minimum length
Point 3 of the precedent remark can be illustrated by the following example:(22)Z=1,−1,1,0,1,1,1,2,1,3,1,4,5,4,6,4,7,4,8,4,9,4,and z=11,5. Applying the algorithm ZPNA several times, we get the following Z,z-partitions and the associated polynomials.
(1)
I1=1,I2=4 and Q=x−1y−4(2)
I1=1,5,6,7,I2=−1,4 and Q=x−7x−6x−5x−1y−4y+1(3)
I1=∅,I2=−1,0,1,2,3,4 and Q=yy−4y+1y−1y−2y−3(4)
I1=1,5,6,7,8,I2=−1,0,1,2,4 and Q=yx−8x−7x−6x−5x−1y−4y−2y−1y+1It is clear that the first solution is the best.Theorem 8.
The algorithmZPNA is correct.Proof.
For proving that, we use loop invariant to help us understand why an algorithm is correct. We must show three things about a loop invariant:(i)
Initialization: it is true prior to the first iteration of the loop.(ii)
Maintenance: if it is true before an iteration of the loop, it remains true before the next iteration.(iii)
Termination: when the loop ends, the invariant gives us a useful property showing that the algorithm is correct.
For the ZPNA algorithm, we note fork∈1;n, z1,⋯zk the elements treated in the k first iterations, Zk=z1,⋯zk et I1k,⋯,Ipk the values of I1,⋯,Ip in the iteration k. So the following property is a loop invariant: At the start of each iteration of the for loop, the I1k−1,⋯,Ipk−1 is a Zk−1,z-partition.
For initialization, we start by showing that the loop invariant holds before the first loop iteration: whenk=1, the I1k−1,⋯,Ipk−1 are empty, and no item is treated, we take Z0=∅, so by convention, the I1k−1,⋯,Ipk−1 is a Zk−1,z-partition.
For maintenance, next, we tackle the second property, showing that each iteration maintains the loop invariant. Assume that theI1k−1,⋯,Ipk−1 is a Zk−1,z-partition, we note zk the element chosen at the start of the iteration k, as z∉Z, the loop (while xit=xiz) ends, so we note i the index founded such as xizk≠xiz. The analysis of the sequence of the iteration k makes it possible without difficulty to assert that Ijk=Ijk−1 if j≠i and for j=i two cases arise: either Iik=Iik−1 if xjzk is already present in one of the Ij, otherwise Iik=Iik−1∪xizk. In both cases, we have I1k,⋯,Ipk is a Zk,z-partition: for t∈Zk, if t∈Zk−1, then there is a j∈1;n such as xjt∈Ij because I1k−1,⋯,Ipk−1 is a Zk−1,z-partition; if t=zk by construction, we also have the result. On the other hand, as xjz is not in any of the Ijk−1,j∈1;n, and as by construction xizk≠xiz, it follows that xiz∉Iik, hence the result.
For termination, we examine finally what will happen when the loop terminates. When the loop terminates (fort in Z (a random choice)), the set Zn=Z, with the invariant of the loop, we have I1n,⋯,Ipn (which are the sets returned by the algorithm) which is a Zn=Z,z-partition. Therefore, the algorithm is correct.


## 3. RLMVPIA Random Approach

For solving, recursively, the problemPZn, we start by choosing P1=span1 as an obvious solution of the problem PZ1, since we have, for all r1∈K, the constant polynomial
(23)P1=r1,which is the interpolating polynomial of R1=r1 on Z1=z1 in P1. So we take Q1=1 as a basis of P1 and we will use the notion of Z,z-partition for computing the polynomials Qi, for i∈2;n, in order to give the algorithm RLMVPIA.The following result shows how the solution of the problemPZn can be constructed recursively using the relationship (6).Theorem 9.
Fork∈2,⋯,n, let Ik=I1k,⋯,Ipk be a Zk−1,zk-partition, and let
(24)Qk=∏i=1p∏α∈Iikxi−αbe the associated polynomial. Then, the space Pk=spanQ1,⋯Qk is a solution of the problem PZk. More precisely, giving Rk=ri:i=1,⋯,k a data vector, the interpolating polynomial for Rk on Zk in Pk is given by Pk:
(25)Pk=Pk−1+skQk,where Pk−1 is the interpolating polynomial for Rk−1=ri:i=1,⋯,k−1 on Zk−1 in Pk−1=spanQ1,⋯,Qk−1 and
(26)sk=rk−Pk−1zkQkzk.Proof.
LetRk=ri:i=1,⋯,k be a given data vector, and let us consider Pk−1 the interpolating polynomial for Rk−1=ri:i=1,⋯,k−1 on Zk−1 in Pk−1. For i=1,⋯,k−1, as I1k,⋯,Ipk is a Zk−1,zk-partition, then Qkzi=0. So the polynomial Pk defined by the expression (25) above verifies Pkzi=Pk−1zi=ri,i=1,⋯,k−1. On the other hand, we have by definition xizk∉Iik, ∀i∈1,⋯,p; then, Qkzk≠0. So taking
(27)sk=rk−Pk−1zkQkzk,we obtain Pkzk=rk. We conclude that
(28)Pkzi=ri,∀i=1,⋯,k,so Pk is an interpolating polynomial for Rk on Zk in Pk=spanQ1,⋯,Qk. We deduce that the linear mapping
(29)P∈Pk↦Pz1,⋯,Pzk∈KZkis surjective. But as dimPk≤k, we conclude that the mapping is a linear isomorphism and that Pk is an interpolation space for Zk, hence the result.Remark 10.
(1)
The interpolating polynomialsPk obtained by the previous theorem depend on the indexation choice of the nodes of Zn(2)
For constructing a solution ofPZn, the following algorithm RLMVPIA chooses a random indexation of the interpolation nodesAlgorithm 2: RLMVPIA.
Input: Interpolation setZ and interpolation values Rn = lenght(Z)P0=0Z0 =fork=1 to n:zk= a random point of ZQk=ZPNAZk−1,zk[1]Zk=Zk−1∪zkremovezk from Zsk=rk−Pk−1zk/QkzkPk=Pk−1+skQkendforreturnPn


## 4. Examples

### 4.1. Examples for the Casep=2

We will give two examples: the first one concerns the particular case where the interpolation set is a full grid. We will see that the RLMVPIA and the RMVPIA [5] are equivalent. The second one is for a random configuration.


#### 4.1.1. Example 1: Grid Case

When the interpolation set is a full grid, RLMVPIA gives a similar result to the one obtained in [5, 7]. In the following example already studied in [5] where the set of nodes, Zn=Zn1+1n2+1 is presented in Figure 1.Figure 1
The interpolation set is a grid.We take(30)Z12=0,1,2×0,1,−12,12,R12=1,0,−2,−1,1,12,−1,1,0,32,73,−4,,by applying the random RLMVPIA, several times; we obtain the same interpolating polynomial given in [5].
(31)P=1−12x−12x2+3y+7112xy−214x2y+−3y2+1076xy2−496x2y2−2y3−20xy3+383x2y3.For a random configuration using the RLMVPIA, we obtain different solutions, as can be seen in the following example.


#### 4.1.2. Example 2

In this example, we take the interpolation set (Figure2)
(32)Z11=1,−1,1,0,1,1,1,2,1,3,1,4,5,4,6,4,7,4,8,4,9,4,and for interpolation values
(33)R11=34,34,−19,−16,−4,−18,−1,24,18,−27,−4,by applying the random RLMVPIA several times; we give among the solutions obtained the two following ones. The first one
(34)Sol1=79140x5−35924x4+310321x3−1596124x2+548803420x+75y5−272y4+2296y3−13y2−99115y−741,and the second one
(35)Sol2=−14800x5y5+5340320x5y4−1630x5y3−5340320x5y2+181100800x5y+187336x5+7960x4y5−531152x4y4+2032880x4y3+531152x4y2−790x4y−18712x4−97960x3y5+51418064x3y4−2184120160x3y3−51418064x3y2+1193910080x3y+455928x3+133192x2y5−50351152x2y4+216072880x2y3+50351152x2y2−118011440x2y−1854724x2−1879800xy5+1035076720xy4−1759696720xy3−1035076720xy2+91886333600xy+531425336x+6320y5−2018y4+555596y3−118y2−41437480y−73818.Figure 2
The interpolation set is a random configuration.


### 4.2. Examples for the Casep=3

In this section, we also give two examples for a full grid and for a random configuration.


#### 4.2.1. Example 3: Grid Case

In this example, we take the full grid ofℝ3 considered in [5] (Figure 3)
(36)Z12=0,1×2,0×1,−12,73,and the interpolation values
(37)R12=1,0,−2,−1,1,12,−1,1,227,0,92,−3.by applying the random RLMVPIA, several times; we obtain the same interpolating polynomial given in [5].
(38)P=−943408+1091408x+86475712y−88995712y+139408xz+38875712yz−671408z−12835712xyz+13368z2−13768xz2−661952yz2+745952xyz2,which coincides with the solution obtained by RMVPIA in [5].Figure 3
The interpolation set is a grid (p=3).


#### 4.2.2. Example 4

In this example, we consider another configuration of the interpolation set inℝ3 (Figure 4)
(39)Z12=0,0,0,0,0,1,0,0,2,0,0,3,0,1,3,0,2,3,0,3,3,0,4,3,1,4,3,2,4,3,3,4,3,4,4,3,and we take them as interpolation values
(40)R12=0,4,13,1,−1,7,43,2,3,12,−2,5.Figure 4
The interpolation set is a random configuration (p=3).Applying the random RLMVPIA several times, we give among the solutions obtained the two following ones. The first one(41)Sol1=1576x4y4z3−1192x4y4z2+1288x4y4z−196x4y3z3+132x4y3z2−148x4y3z+11576x4y2z3−11192x4y2z2+11288x4y2z−196x4yz3+132x4yz2−148x4yz−111728x3y4z3+11576x3y4z2−11864x3y4z+11288x3y3z3−1196x3y3z2+11144x3y3z−1211728x3y2z3+121576x3y2z2−121864x3y2z+11288x3yz3−1196x3yz2+11144x3yz−1192x2y4z3+164x2y4z2−196x2y4z+132x2y3z3−332x2y3z2+116x2y3z−11192x2y2z3+1164x2y2z2−1196x2y2z+132x2yz3−332x2yz2+116x2yz+291728xy4z3−29576xy4z2+29864xy4z−29288xy3z3+2996xy3z2−29144xy3z+3191728xy2z3−319576xy2z2+319864xy2z−29288xyz3+2996xyz2−29144xyz+131432y4z3−131144y4z2+131216y4z−535216y3z3+53572y3z2−535108y3z+2653432y2z3−2653144y2z2+2653216y2z−929216yz3+92972yz2−929108yz+2z3−596z2+716z.The second one with a lower degree(42)Sol2=14x4−1112x3−34x2+2912x+13172y4+18y3z−109772y3−78y2z+142136y212yz3+3yz2−154yz−50518y+2z3−596z2+716z.Remark 11.
The last example shows the importance of the random approach, in some cases, to get solutions of fairly low degree, which can influence the cost of evaluations.


## 4.1. Examples for the Casep=2

We will give two examples: the first one concerns the particular case where the interpolation set is a full grid. We will see that the RLMVPIA and the RMVPIA [5] are equivalent. The second one is for a random configuration.


### 4.1.1. Example 1: Grid Case

When the interpolation set is a full grid, RLMVPIA gives a similar result to the one obtained in [5, 7]. In the following example already studied in [5] where the set of nodes, Zn=Zn1+1n2+1 is presented in Figure 1.Figure 1
The interpolation set is a grid.We take(30)Z12=0,1,2×0,1,−12,12,R12=1,0,−2,−1,1,12,−1,1,0,32,73,−4,,by applying the random RLMVPIA, several times; we obtain the same interpolating polynomial given in [5].
(31)P=1−12x−12x2+3y+7112xy−214x2y+−3y2+1076xy2−496x2y2−2y3−20xy3+383x2y3.For a random configuration using the RLMVPIA, we obtain different solutions, as can be seen in the following example.


### 4.1.2. Example 2

In this example, we take the interpolation set (Figure2)
(32)Z11=1,−1,1,0,1,1,1,2,1,3,1,4,5,4,6,4,7,4,8,4,9,4,and for interpolation values
(33)R11=34,34,−19,−16,−4,−18,−1,24,18,−27,−4,by applying the random RLMVPIA several times; we give among the solutions obtained the two following ones. The first one
(34)Sol1=79140x5−35924x4+310321x3−1596124x2+548803420x+75y5−272y4+2296y3−13y2−99115y−741,and the second one
(35)Sol2=−14800x5y5+5340320x5y4−1630x5y3−5340320x5y2+181100800x5y+187336x5+7960x4y5−531152x4y4+2032880x4y3+531152x4y2−790x4y−18712x4−97960x3y5+51418064x3y4−2184120160x3y3−51418064x3y2+1193910080x3y+455928x3+133192x2y5−50351152x2y4+216072880x2y3+50351152x2y2−118011440x2y−1854724x2−1879800xy5+1035076720xy4−1759696720xy3−1035076720xy2+91886333600xy+531425336x+6320y5−2018y4+555596y3−118y2−41437480y−73818.Figure 2
The interpolation set is a random configuration.


## 4.1.1. Example 1: Grid Case

When the interpolation set is a full grid, RLMVPIA gives a similar result to the one obtained in [5, 7]. In the following example already studied in [5] where the set of nodes, Zn=Zn1+1n2+1 is presented in Figure 1.Figure 1
The interpolation set is a grid.We take(30)Z12=0,1,2×0,1,−12,12,R12=1,0,−2,−1,1,12,−1,1,0,32,73,−4,,by applying the random RLMVPIA, several times; we obtain the same interpolating polynomial given in [5].
(31)P=1−12x−12x2+3y+7112xy−214x2y+−3y2+1076xy2−496x2y2−2y3−20xy3+383x2y3.For a random configuration using the RLMVPIA, we obtain different solutions, as can be seen in the following example.


## 4.1.2. Example 2

In this example, we take the interpolation set (Figure2)
(32)Z11=1,−1,1,0,1,1,1,2,1,3,1,4,5,4,6,4,7,4,8,4,9,4,and for interpolation values
(33)R11=34,34,−19,−16,−4,−18,−1,24,18,−27,−4,by applying the random RLMVPIA several times; we give among the solutions obtained the two following ones. The first one
(34)Sol1=79140x5−35924x4+310321x3−1596124x2+548803420x+75y5−272y4+2296y3−13y2−99115y−741,and the second one
(35)Sol2=−14800x5y5+5340320x5y4−1630x5y3−5340320x5y2+181100800x5y+187336x5+7960x4y5−531152x4y4+2032880x4y3+531152x4y2−790x4y−18712x4−97960x3y5+51418064x3y4−2184120160x3y3−51418064x3y2+1193910080x3y+455928x3+133192x2y5−50351152x2y4+216072880x2y3+50351152x2y2−118011440x2y−1854724x2−1879800xy5+1035076720xy4−1759696720xy3−1035076720xy2+91886333600xy+531425336x+6320y5−2018y4+555596y3−118y2−41437480y−73818.Figure 2
The interpolation set is a random configuration.


## 4.2. Examples for the Casep=3

In this section, we also give two examples for a full grid and for a random configuration.


### 4.2.1. Example 3: Grid Case

In this example, we take the full grid ofℝ3 considered in [5] (Figure 3)
(36)Z12=0,1×2,0×1,−12,73,and the interpolation values
(37)R12=1,0,−2,−1,1,12,−1,1,227,0,92,−3.by applying the random RLMVPIA, several times; we obtain the same interpolating polynomial given in [5].
(38)P=−943408+1091408x+86475712y−88995712y+139408xz+38875712yz−671408z−12835712xyz+13368z2−13768xz2−661952yz2+745952xyz2,which coincides with the solution obtained by RMVPIA in [5].Figure 3
The interpolation set is a grid (p=3).


### 4.2.2. Example 4

In this example, we consider another configuration of the interpolation set inℝ3 (Figure 4)
(39)Z12=0,0,0,0,0,1,0,0,2,0,0,3,0,1,3,0,2,3,0,3,3,0,4,3,1,4,3,2,4,3,3,4,3,4,4,3,and we take them as interpolation values
(40)R12=0,4,13,1,−1,7,43,2,3,12,−2,5.Figure 4
The interpolation set is a random configuration (p=3).Applying the random RLMVPIA several times, we give among the solutions obtained the two following ones. The first one(41)Sol1=1576x4y4z3−1192x4y4z2+1288x4y4z−196x4y3z3+132x4y3z2−148x4y3z+11576x4y2z3−11192x4y2z2+11288x4y2z−196x4yz3+132x4yz2−148x4yz−111728x3y4z3+11576x3y4z2−11864x3y4z+11288x3y3z3−1196x3y3z2+11144x3y3z−1211728x3y2z3+121576x3y2z2−121864x3y2z+11288x3yz3−1196x3yz2+11144x3yz−1192x2y4z3+164x2y4z2−196x2y4z+132x2y3z3−332x2y3z2+116x2y3z−11192x2y2z3+1164x2y2z2−1196x2y2z+132x2yz3−332x2yz2+116x2yz+291728xy4z3−29576xy4z2+29864xy4z−29288xy3z3+2996xy3z2−29144xy3z+3191728xy2z3−319576xy2z2+319864xy2z−29288xyz3+2996xyz2−29144xyz+131432y4z3−131144y4z2+131216y4z−535216y3z3+53572y3z2−535108y3z+2653432y2z3−2653144y2z2+2653216y2z−929216yz3+92972yz2−929108yz+2z3−596z2+716z.The second one with a lower degree(42)Sol2=14x4−1112x3−34x2+2912x+13172y4+18y3z−109772y3−78y2z+142136y212yz3+3yz2−154yz−50518y+2z3−596z2+716z.Remark 11.
The last example shows the importance of the random approach, in some cases, to get solutions of fairly low degree, which can influence the cost of evaluations.


## 4.2.1. Example 3: Grid Case

In this example, we take the full grid ofℝ3 considered in [5] (Figure 3)
(36)Z12=0,1×2,0×1,−12,73,and the interpolation values
(37)R12=1,0,−2,−1,1,12,−1,1,227,0,92,−3.by applying the random RLMVPIA, several times; we obtain the same interpolating polynomial given in [5].
(38)P=−943408+1091408x+86475712y−88995712y+139408xz+38875712yz−671408z−12835712xyz+13368z2−13768xz2−661952yz2+745952xyz2,which coincides with the solution obtained by RMVPIA in [5].Figure 3
The interpolation set is a grid (p=3).


## 4.2.2. Example 4

In this example, we consider another configuration of the interpolation set inℝ3 (Figure 4)
(39)Z12=0,0,0,0,0,1,0,0,2,0,0,3,0,1,3,0,2,3,0,3,3,0,4,3,1,4,3,2,4,3,3,4,3,4,4,3,and we take them as interpolation values
(40)R12=0,4,13,1,−1,7,43,2,3,12,−2,5.Figure 4
The interpolation set is a random configuration (p=3).Applying the random RLMVPIA several times, we give among the solutions obtained the two following ones. The first one(41)Sol1=1576x4y4z3−1192x4y4z2+1288x4y4z−196x4y3z3+132x4y3z2−148x4y3z+11576x4y2z3−11192x4y2z2+11288x4y2z−196x4yz3+132x4yz2−148x4yz−111728x3y4z3+11576x3y4z2−11864x3y4z+11288x3y3z3−1196x3y3z2+11144x3y3z−1211728x3y2z3+121576x3y2z2−121864x3y2z+11288x3yz3−1196x3yz2+11144x3yz−1192x2y4z3+164x2y4z2−196x2y4z+132x2y3z3−332x2y3z2+116x2y3z−11192x2y2z3+1164x2y2z2−1196x2y2z+132x2yz3−332x2yz2+116x2yz+291728xy4z3−29576xy4z2+29864xy4z−29288xy3z3+2996xy3z2−29144xy3z+3191728xy2z3−319576xy2z2+319864xy2z−29288xyz3+2996xyz2−29144xyz+131432y4z3−131144y4z2+131216y4z−535216y3z3+53572y3z2−535108y3z+2653432y2z3−2653144y2z2+2653216y2z−929216yz3+92972yz2−929108yz+2z3−596z2+716z.The second one with a lower degree(42)Sol2=14x4−1112x3−34x2+2912x+13172y4+18y3z−109772y3−78y2z+142136y212yz3+3yz2−154yz−50518y+2z3−596z2+716z.Remark 11.
The last example shows the importance of the random approach, in some cases, to get solutions of fairly low degree, which can influence the cost of evaluations.


## 5. Conclusion

In conclusion, this work contributes to solve the problem of Lagrange multivariate polynomial interpolation with any finite set of interpolation nodes, using a recursive algorithm RLMVPIA with a random approach based on theZ,z-partition concept. This study shows that RLMVPIA is easy to implement and requires no storage.Currently, we are interested firstly, in refining the random approach of the algorithm, to build, in a more deterministic way, optimal solutions of smaller degree. The problem of optimal solution and the study of the numerical stability of the RLMVPIA are under investigation. One can also find natural applications of RLMVPIA in different topics of applied mathematics and engineering as the numerical resolution of PDEs, computer-aided design (CAD), cryptography, etc.



---

*Source: 8227086-2022-03-14.xml*