3. Lagrange-type multivalued interpolation

Interpolation methods for multivalued functions

Ildiko Somogyi and Anna So´ os

Dedicated to Professor Gheorghe Coman on the occasion of his 80th anniversary Abstract. The aim of these article is to study the interpolation problem for multi- valued functions. We give some methods for the approximation of these functions.

Mathematics Subject Classification (2010):65D05, 65D07.

Keywords:Numerical interpolation, spline functions.

1. Introduction

The notion of multivalued functions appeared in the first half of the twentieth century. A multivalued function also known as multi-function, multimap, set-valued function. This is a ”function” that assume two or more values for each point from the domain. These functions are not functions in the classical way because for each point assign a set of points, so there is not a one-to-one correspondence. The term of

”multivalued function” is not correct, but became very popular. Multivalued functions often arise as inverse of functions which are non-injective. For example the inverse of the trigonometric, exponential, power or hyperbolic functions are multivalued func- tions. Also the indefinite integral can be considered as a multivalued function. These functions appears in many areas, for example in physics in the theory of defects of crystals, for vortices in superfluids and superconductors but also in optimal control theory or game theory in mathematics.

2. Interpolation problem

Let [a, b]⊆Randf : [a, b]→P(R) be a multivalued function, whereP(R) is the power set ofR, andf(x) is nonempty for every x∈[a, b]. We say that a multivalued function is single-valued if, f(x) contain only one element for every x∈[a, b]. Thus a common function can be considered as single-valued multifunction. Furthermore, we suppose that for each x ∈ [a, b], card(f(x)) < ∞. We suppose that the points xi ∈[a, b], i = 1,2, . . . , l are given and also the set of function values on this points are known yij ∈ R, i = 1,2, . . . , l, j = 1,2, . . . , k. We will interpolate the sets of

pointsMj ={(xi, yij), i= 1,2, . . . , l}, j = 1,2, . . . , k using an interpolation operator Pj:C[a, b]−→R, j= 1,2, . . . , kand the remainder operatorRj.

Definition 2.1. Ifx∈[a, b], x6=x_i, i= 1,2, . . . , k, the value of the multivalued function inxis approximated by the following set{P1(x), . . . , P_k(x)}. The approximation error on the pointxis given byR₁(x) +. . .+R_k(x).

Definition 2.2. We have the following interpolation formula:

f(x) = (P1∪P2. . .∪Pk)(x) + (R1+R2+. . .+Rk)(x) (2.1) whereP1∪. . .∪Pk is the interpolation operator andR1+. . .+Rk is the remainder operator.

Remark 2.3. The P₁∪. . .∪P_k is an interpolation operator because the following interpolation condition are satisfied:P_i(x_j) =y_ji.

Theorem 2.4. The interpolation operatorP1∪. . .∪Pk exists and is unique.

Proof. It is obvious, because at each setMj, j= 1,2, . . . , kthe interpolation operators

Pj, j= 1,2, . . . , k exists and are unique.

Furthermore let’s consider the case when we have the following type of data {(xi, yn_jj), i= 1,2, . . . , l, j= 1,2, . . . , k, ni ∈N, ni<∞}.

Let bem = min{nj, j = 1,2, . . . , k}, then we will consider the following set of data {(xm, ymi, i= 1,2, . . . , k)}, in this way we reduce the problem to the previous case.

3. Lagrange-type multivalued interpolation

If we considering the case when at each set M_j, the points (x_i, y_ij) are in- terpolated using Lagrange type interpolation, then the interpolation operator is Ll₁ ∪. . . ∪Ll_k, where Ll_i, i = 1,2, . . . , k are l −1 degree Lagrange polynomials, and the remainder is equal toRl₁+Rl₂+. . .+Rl_k whereRl_i are the corresponding remainder operators.

Theorem 3.1. The value of the multivalued Lagrange type interpolation function on the point x∈[a, b],x6=x_i, i= 1,2, . . . , lis given by

L_l1∪. . .∪L_lk(x) =

k

[

i=1 l−1

X

j=1

l_ij(x)y_ij (3.1)

wherelij are the basic Lagrange polynomials with degreel−1.

Proof. From Theorem 2.4 we have that the value of the multivalued function on the pointxis approximated by the following values{P1(x), . . . , Pk(x)}, wherePiare the corresponding interpolation operators for the data (xi, yij), j = 1,2, . . . , l. Because now we use Lagrange-type interpolation to approximate these data, we have

Pi(x) =L_l−1(x) =

l

X

i=1

lij(x)yij,

wherelij are the corresponding basic Lagrange polynomials.

We suppose thatyij=fj(xi) wherefj ∈C[a, b], j= 1,2, . . . , k.

Theorem 3.2. If fj ∈C^l−1[a, b], j = 1,2, . . . , k, and∃f_j^(l)j = 1,2, . . . , k on[a, b] then the remainder of the multivalued interpolation formula is

(R₁+R₂+. . .+R_k)(x) =

k

X

j=1

u(x)

l! f_j^(l)(ξ_j) (3.2) were ξj ∈(a, b) andu(x) = (x−x1)(x−x2). . .(x−xl).

Proof. If we consider the Lagrange interpolation formula for each setMj

fj(x) =Lj(x) +Rj(x), j= 1,2, . . . , k

where iffj∈C^l−1[a, b] and ∃f_j^(l)on [a, b] then there∃ξj ∈(a, b), j= 1,2, . . . , k such that

Rj(x) = u(x)

(l!)f_j^(l)(ξj), j= 1,2, . . . , k

Example 3.3. If consider the multivalued function, obtained as the inverse of the func- tiong(x) = sin(x), on the interval [a, b] = [−1,1], using the method described below with Lagrange type interpolation operators on each set of pointsM_j, we obtain the graph from figure 1, where the dotted line is the graph of the multivalued function and the continuous line is the graph of the multivalued function obtained by interpolation.

Figure 1. Interpolation of multivalued function with Lagrange operators

4. Shepard-type multivalued interpolation

We suppose that the points xi ∈[a, b], i= 1,2, . . . , lare given and also the set of function values on this points are known yij ∈R, i= 1, . . . , l, j= 1, . . . , k. We will

interpolate the sets of pointsMj={(xi, yij), i= 1, . . . , l}, j= 1, . . . , kusing Shepard interpolation studied also in [2], [1], [4] and [6].

Theorem 4.1. The Shepard-type multivalued interpolation operator is

k

[

i=1

Si(x) =

k

[

i=1 l

X

j=1

Aj(x)yij, (4.1)

whereSi are the univariate Shepard operators and

A_j(x) = Y

i=1,i6=j

l|x−xi|^µ

l

X

t=1

Y

i=1,i6=t

l|x−x_i|^µ

andµ∈R+.

Remark 4.2. The basis functionsA_j can be also written in the following barycentric form

Aj(x) = |x−xj|^−µ

l

X

i=1

|x−xk|^−µ

, j= 1,2, . . . , l,

and they satisfy

l

X

j=1

A_j(x) = 1, A_j(x_p) =δ_jp, j, p= 1,2, . . . , l.

Figure 2. Interpolation of multivalued function with Shepard operators

From the remark it follows that the Shepard operators has the following prop- erties: first of all they have the interpolation conditionsSi(xj) =yij, j = 1,2, . . . , l, i= 1,2, . . . , k, and they have the degree of exactnessdex(Si) = 0, i= 1,2, . . . , k.

The graph of the function from the previous example in the case when we use Shepard operators with different parameters, is given in Figure 2.

The major disadvantage of the Shepard operator is the low degree of exactness, but this can be overcome combining the Shepard operator with another interpolation operators, for example Lagrange, Hermite, Birkhoff or other interpolation operators.

5. Spline-type multivalued interpolation

We will consider again the points x_i ∈[a, b], i= 1,2, . . . , l and also the set of function values on this pointsy_ij ∈R, i= 1,2, . . . , l, j= 1,2, . . . , kwhich are known, letM_j ={(x_i, y_ij), i= 1,2, . . . , l}, j = 1,2, . . . , k be the set of interpolation points.

In this section we will interpolate the multivalued function given by the set of points fromMj with spline interpolation function.

We suppose that the valuesyij =fj(xi), wherefj∈H^m,2[a, b] is the set of functions withfj ∈C^m−1[a, b], f^(m−1) absolute continuous on [a, b] and f^(m)∈L²[a, b].

Theorem 5.1. The multivalued interpolation operator in the case of spline interpolation is

l

[

i=1

Si(x) =

l

[

i=1 k

X

j=1

sij(x)yij (5.1)

wheresij are the fundamental spline interpolation functions.

Remark 5.2. The fundamental spline functions satisfies the following minimum prop- erties kS_i^(m)k2 −→ min, in the set of all functions which satisfies the interpolation conditions.

To determine the fundamental spline functions we can use the structural cha- racterization theorem of spline functions given also in [3] and we have

sij(x) =

m−1

X

t=0

a^ij_t x^t+

l

X

p=1

b^ij_p(x−xp)^2m−1₊ , i= 1,2, . . . , l, j= 1,2, . . . , k

witha^ij_t , andb^ij_p obtained as the solution of the following systems:

s^(r)_ij (α) = 0, r=m, . . . ,2m−1, and α > xl

s_ij(x_ν) = δ_jν, ν= 1,2, , . . . , l forj= 1,2, . . . , k, i= 1,2, . . . , l.

Theorem 5.3. Iff_j∈H^m,2[a, b], j= 1,2, . . . , k then the remainder term of the spline- type multivalued interpolation formula is

k

X

j=1

Rj(x) =

k

X

j=1

Z b

a

ϕj(x, t)f_j^(m)(t)dt (5.2)

where

ϕj(x, t) =(x−t)^m−1₊ (m−1)! −

l

X

i=1

sij(x)(xi−t)^m−1₊ , j= 1,2, . . . , k.

This follows from the representation of the error using the Peano theorem.

The graph of the function from the previous example using third degree natural spline interpolation operators is given in Figure 3.

Figure 3. Interpolation of multivalued function with spline operators

References

[1] Coman, Gh.,Shepard operators of Birkhoff-type, Calcolo,35(1998), 197–203.

[2] Coman, Gh., Trˆımbit¸a¸s, R., Combined Shepard univariate operators, East Journal on Approximations,7(2001), 471–483.

[3] Coman, Gh., Birou, M., O¸san, C., Somogyi, I., C˘atina¸s, T., Opri¸san, A., Pop, I., Todea, I.,Interpolation operators, Ed. Casa C˘art¸ii de S¸tiint¸˘a, Cluj-Napoca, 2004.

[4] C˘atina¸s, T., Interpolation of scattered data, Ed. Casa C˘art¸ii de S¸tiint¸˘a, Cluj-Napoca, 2007.

[5] Sauer, T.,Polynomial interpolation of minimal degree, Numer. Math.,78(1997), 59–85.

[6] Trˆımbit¸a¸s, R., Univariate Shepard-Lagrange interpolation, Kragujevac J. Math., 24(2002), 85–94.

Ildiko Somogyi

Babe¸s-Bolyai University

Faculty of Mathematics and Computer Science Cluj-Napoca, Romania

e-mail:[email protected] Anna So´os

Babe¸s-Bolyai University

Faculty of Mathematics and Computer Science Cluj-Napoca, Romania

e-mail:[email protected]