PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 98(112) (2015), 147–151 DOI: 10.2298/PIM1512147G

A NOTE ON DIVIDED DIFFERENCES

Ioan Gavrea and Mircea Ivan

Abstract. We obtain a new recurrence formula for sequences of divided differences. In a particular case, the recurrence formula simplifies the classical Newton–Girard identities relating power sums and elementary symmetric polynomials.

1. Introduction and preliminary results

Divided differences are a basic tool in numerical analysis often used both in theory and in practice. In the last two decades the classical topic of interpolation has been strongly reinvigorated. A new insight was provided into the study of efficient numerical algorithms for the calculations of divided difference, chain rules, mean value theorems and representations of the divided differences of ordinary and implicit functions. In this context, far from being exhaustive, we briefly mention the papers: [1–17, 20] and the references therein.

Throughout the paper n and m denote non-negative integers. Let z_{0}, …, z_{n} be pairwise distinct complex numbers and F be the set of all complex-valued functions defined on a set A ⊇ {z_{0}, …, z_{n}}. In most books on numerical analysis, the divided differences of a function f ∈ F are defined recursively:

[z_{0}; f] = f(z_{0}), …,

[z_{0}, …, z_{n}; f] = \frac{[z_{1}, …, z_{n}; f] − [z_{0}, …, z_{n−1} ; f]}{z_{n} − z_{0}} , n = 1, 2, . . ..

For the sake of clarity, we will also use the alternative notation [z_{0}, …, z_{n}; f(t)]_{t} to represent the divided difference [z_{0}, …, z_{n}; f]. The divided difference [z_{0}, …, z_{n}; f] can equivalently be defined as the coefficient of z^{n} of the interpolating polynomial L[z_{0}, …, z_{n}; f].

2010 Mathematics Subject Classification: 65Q30; 41A05.

Key words and phrases: divided differences, Lagrange interpolation, Newton–Girard formulae.

Communicated by Giuseppe Mastroianni.

The polynomial L[z_{0}, …, z_{n}; f] can be written in the Lagrange–Waring form

(1.1)  L[z_{0}, …, z_{n}; f](z) = ∑_{k=0}^{n} \frac{ℓ_{n}(z)}{z − z_{k}} · \frac{f(z_{k})}{ℓ′_{n}(z_{k})},

where ℓ_{n}(z) = (z−z_{0}) ⋯ (z−z_{n}). From (1.1) we obtain the following representation of the divided difference

(1.2)  [z_{0}, …, z_{n}; f] = ∑_{k=0}^{n} \frac{f(z_{k})}{ℓ′_{n}(z_{k})}.

Let e_{i}: ℂ → ℂ denote the monomial functions e_{i}(z) = z^{i}, i = 0, 1, . . .. In our analysis we will focus on a recurrence formula for sequences of divided differences of the form [z_{0}, …, z_{n}; e_{m}f], m = 0, 1, . . ..

Popoviciu [19] proved that

(1.3)  [z_{0}, …, z_{n}; e_{n+r} ] = ∑ z_{0}^{k_{0}} …z_{n}^{k_{n}} ,

where the sum runs over all non-negative k_{0}, …, k_{n} with k_{0} + ⋯+ k_{n} = r, where r is a non-negative integer. Popoviciu’s formula (1.3) was rediscovered in 1981 by Neuman [18]. Another representation for the divided differences of monomials in terms of the complete Bell polynomials was given in [2]. Maybe the technique used in [17] could be useful in finding an alternative explicit formula for [z_{0}, …, z_{n}; e_{m}f].

We note that, obtaining a recurrence formula of order n (the same as the number of knots) for the sequence [z_{0}, …, z_{n}; e_{m}f], m = 0, 1, …, is quite simple and well known. However, the problem of finding a recurrence formula of a given order m (independent of n) is not so simple, and this is the main aim of the paper. This is similar to finding a recurrence formula of order m for the sequence of determinants of order n + 1:

|\begin{matrix}1 & z_{0} & ⋯ & z_{0}^{n−1} & z_{0}^{m} f(z_{0}) \\ 1 & z_{1} & ⋯ & z_{1}^{n−1} & z_{1}^{m} f(z_{1}) \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 1 & z_{n} & ⋯ & z_{n}^{n−1} & z_{n}^{m} f(z_{n}) \end{matrix} | , m = 0, 1, …

2. Main results

Let D ⊆ ℂ and P, Q: D → ℂ^{∗} be two m + 1 times differentiable functions. To simplify the proof of the main result we consider the function F: D → ℂ^{∗}, F = \frac{P}{Q}. Taking into account the identity ( \frac{P}{Q} )′ = \frac{P}{Q} ( \frac{P′}{P} − \frac{Q′}{Q} ), and using the Leibniz formula for the high order derivative of a product, we obtain the following recurrence formula of order m for the high order derivatives of F, which may be interesting in itself,

(2.1)  \frac{F^{(m+1)}}{(m + 1)!} = \frac{1}{m + 1} ∑_{k=0}^{m} \frac{F^{(k)}}{k!} \frac{1}{(m − k)!} ( \frac{P′}{P} − \frac{Q′}{Q})^{(m−k)} .

In order to simplify the notations we will suppose that [z_{0}, …, z_{n}; f] ≠ 0, but mention that the current method works for [z_{0}, …, z_{n}; f] = 0 also, with only slight modifications.

Let ζ_{1}, ζ_{2}, …, ζ_{n} ∈ ℂ denote the roots of the polynomial L[z_{0}, …, z_{n}; f], and consider the power sums:

s_{k} := s_{k}(z_{0}, …, z_{n}) := ∑_{j=0}^{n} z_{j}^{k}, k = 0, 1, …,

σ_{k} := σ_{k}(ζ_{1}, …, ζ_{n}) := ∑_{i=1}^{n} ζ_{i}^{k}, k = 0, 1, . . ..

The following theorem is the main result of this paper.

Theorem 2.1. The following recurrence formula of order m is satisfied

[z_{0}, …, z_{n}; e_{m+1} f] = \frac{1}{m + 1} ∑_{k=0}^{m} [z_{0}, …, z_{n}; e_{k}f](s_{m+1−k} − σ_{m+1−k} ), (2.2)

m = 0, 1, …

Proof. We will make use of the following formula

(2.3)  [z_{0}, …, z_{n}; \frac{f(t)}{z − t} ]_{t} = \frac{L(z_{0}, …, z_{n}; f)(z)}{(z − z_{0}) ⋯ (z − z_{n})} , z ∈ ℂ ∖ \{z_{0}, …, z_{n}\},

which is a direct consequence of (1.1) and (1.2). We replace z with \frac{1}{z} in (2.3) and define

F(z) := [z_{0}, …, z_{n}; \frac{f(t)}{1 − zt} ]_{t} = [z_{0}, …, z_{n}; f] \frac{(1 − z ζ_{1}) ⋯ (1 − z ζ_{n})}{(1 − zz_{0}) ⋯ (1 − zz_{n})} ,

in a suitable neighborhood D of z = 0. Let P (z) = [z_{0}, …, z_{n}; f] (1 − z ζ_{1}) ⋯ (1 − z ζ_{n}) and Q(z) = (1 − zz_{0}) ⋯ (1 − zz_{n}). We have

(2.4)  \frac{F^{(k)}(0)}{k!} = [z_{0}, …, z_{n}; e_{k}f], k = 0, 1, …

and

( \frac{P′}{P})^{(m−k)} (0) = −(m − k)!σ_{m+1−k} , ( \frac{Q′}{Q})^{(m−k)} (0) = −(m − k)!s_{m+1−k} .

The use of (2.4) and of (2.1) for z = 0 completes the proof. □

Remark 2.1. In particular, for f = e_{n}, (2.2) becomes

[z_{0}, …, z_{n}; e_{n+m+1} ] = \frac{1}{m + 1} ∑_{k=0}^{m} [z_{0}, …, z_{n}; e_{n+k} ]s_{m+1−k} , m = 0, 1, …

Indeed, for f = e_{n}, we obtain L[z_{0}, …, z_{n}; f]= e_{n} with roots ζ_{1} = 0, …, ζ_{n} = 0 . We rewrite (2.2) in the form

(2.5) [z_{0}, …, z_{n}; e_{q}f] = \frac{1}{q} ∑_{k=0}^{q−1} [z_{0}, …, z_{n}; e_{k}f] (s_{q−k} − σ_{q−k} ), q = 1, 2, . . ..

Let us suppose now that f possesses a derivative f^{(n)} (0) ≠ 0.

Remark 2.2. Coalescing all points z_{0}, …, z_{n} to zero, equation (2.5) simplifies to a recurrence formula for the derivatives of f in terms of the roots of its Maclaurin polynomial,

(2.6)  (e_{q}f)^{(n)}(0) = −\frac{1}{q} ∑_{k=0}^{q−1} (e_{k}f)^{(n)} (0) σ_{q−k} , q = 1, 2, . . ..

Remark 2.3. By taking in (2.6)

f(t) = (t − ζ_{1}) ⋯ (t − ζ_{n}) = ∑_{i=0}^{n} c_{i}t^{n−i} ,

we rediscover the classical Newton identities (also known as the Newton–Girard formulae):

c_{0} = 1,

c_{q} = −\frac{1}{q} ∑_{k=0}^{q−1} c_{k} σ_{q−k} , q = 1, 2, …, n.

References

1. U. Abel, M. Ivan, Some identities for the operator of Bleimann, Butzer and Hahn involving divided differences, Calcolo 36(3) (1999), 143–160.

2. , Asymptotic expansion of a sequence of divided differences with application to positive linear operators, J. Comput. Anal. Appl. 7(1) (2005), 89–101.

3. , The differential mean value of divided differences, J. Math. Anal. Appl. 325(1) (2007), 560–570.

4. U. Abel, M. Ivan, T. Riedel, The mean value theorem of Flett and divided differences, J. Math. Anal. Appl. 295(1) (2004), 1–9.

5. C. Brezinski, Rational approximation to formal power series, J. Approx. Theory 25(4) (1979), 295–317.

6. , The Mühlbach-Neville-Aitken algorithm and some extensions, BIT 20(4) (1980), 444–451.

7. C. de Boor, Divided differences, Surv. Approx. Theory 1 (2005), 46–69.

8. M. S. Floater, A chain rule for multivariate divided differences, BIT 50(3) (2010), 577–586.

9. M. S. Floater, T. Lyche, Two chain rules for divided differences and Faà di Bruno’s formula, Math. Comp. 76258 (2007), 867–877 (electronic).

10. M. Gasca T. Sauer, On the history of multivariate polynomial interpolation, J. Comput. Appl. Math. 122(1–2) (2000), 23–35, Numerical analysis 2000, Vol. II: Interpolation and extrapolation.

11. I. Gavrea, M. Ivan, R. Moga, Some applications of Hopf’s identity on divided differences, Ann. Tiberiu Popoviciu Semin. Funct. Equ. Approx. Convexity 11 (2013), 41–51.

12. M. Ivan, A note on the Hermite interpolation polynomial for rational functions, Appl. Numer. Math. 57(2) (2007), 230–233.

13. , A note on the Hermite interpolation, Numer. Algorithms 69(3) (2015), 517–522.

14. G. Mühlbach, A recurrence formula for generalized divided differences and some applications, J. Approx. Theory 9 (1973), 165–172.

15. , A recurrence relation for generalized divided differences with respect to ECT-systems, Numer. Algorithms 22(3–4) (1999), 317–326 (2000).

16. G. Muntingh, Divided differences of multivariate implicit functions, BIT 52(3) (2012), 703– 17. G. Muntingh, M. Floater, Divided differences of implicit functions, Math. Comp. 80(276)

(2011), 2185–2195.

18. E. Neuman, Problems and Solutions: E2900, Am. Math. Monthly 88(7) (1981), 537–538.

19. T. Popoviciu, Introduction à la théorie des différences divisées, Bull. Math. Soc. Roumaine Sci. 42(1) (1940), 65–78.

20. G. Walz, Asymptotic expansions for classical and generalized divided differences including applications, Numer. Algorithms 7(2–4) (1994), 161–171.

Department of Mathematics (Received 02 03 2014) Technical University of Cluj-Napoca Cluj-Napoca Romania

ioan.gavrea@math.utcluj.ro
mircea.ivan@math.utcluj.ro