Trigonometric and tensor-product Floater-Hormann rational

(1)

Dipartimento di Matematica ”Tullio Levi-Civita”

Corso di Laurea Magistrale in Matematica

Tesi di Laurea magistrale

Trigonometric and tensor-product Floater-Hormann rational

interpolant

Candidato Relatore

Cinzia Bandiziol Prof. Stefano De Marchi

N. di matricola: 1110865

Anno Accademico 2017/2018 6 luglio 2018

(2)

(3)

Thanks

This thesis represents the end of my university adventure, started some years ago. It is well known that the beginnings were so strong and I have sometimes vacillated but in my hearth I felt that could reach the final goal and graduate.

It is useless to say that I could not have realized my dreams without the help of some special people.

I wish to thank Professor Stefano De Marchi because accepted to be my supervisor for the second time and helped me with useful tips and suggestions to make a good thesis.

Professor Roberto Monti played an important role in my university experience.

Immediately he helped me in overcoming doubts and thanks to him I learned a lot both on a human and academic level. With his support I started to believe more in myself and in my abilities and now I’m here.

A special thanks obviously to my parents. They trusted me and even if were sometimes worried about me, they always gave me strong support.

Then of course I wish to thank my friends, known in university, among which Rudy, Paola, Chiara and Ludovica because I spent a lot of unforgettable moments and had fun with us.

Finally I must thank my hairy friend because purring it kept me company during hours spent on books.

(4)

(5)

List of Figures

2.1 g-plot in [−^π₂,^π₂]. . . 17 2.2 ω-Error plot with I = [0, π], n = 40 and d = 4. The test functions

are exp(x) (left) and x² (right). . . 28 2.3 ω-Error plot with I = [0, π], n = 40 and d = 4. The test function

are sin(2x) (left) and sin(8x) (right). . . 29 2.4 TFHRI - Test function f (x) = x² with n + 1 equispaced nodes in

[0, π], n = 10, 60, ω = 0.1 and d = 2 . . . 30 2.5 TFHRI - Test function f (x) = sin(2x) with n + 1 equispaced nodes

in [0, π], n = 10, 60, ω = 0.1 and d = 2 . . . 30 2.6 TFHRI - Test function f (x) = |x| with n + 1 equispaced nodes in

[−^π₂,^π₂], n = 10, 60, ω = 0.5 and d = 2 . . . 31 2.7 TFHRI - Test function f4 with n + 1 equispaced nodes in [0, π],

n = 10, 60, ω = 0.1 and d = 2 . . . 31 2.8 TFHRI - Test function f₅ with n + 1 equispaced nodes in [0, π],

n = 10, 60, ω = 0.1 and d = 2 . . . 32 2.9 TFHRI - Lebesgue constants with n + 1 nodes in [0, 1], 4 ≤ n ≤ 40

even, ω = 0.1, d = 0 (left) and d = 2 (right). The plots shows the Lebesgue constants (blue), the upper bounds (red) and the lower bounds (green) . . . 33 2.10 Lebesgue functions - TFHRI with n+1 nodes in [0, 1], n = 10, 20, 40,

ω = 0.1 and d = 2 . . . 34 2.11 ω-Error plot with I = [0, 1], n = 40 and d = 3. The test functions

are e^x (left) and x² (right). . . 40 2.12 ω-Error plot with I = [0, 1], n = 40 and d = 3. The test functions

are sin(2πx) (left) and sin(4πx) (right). . . 40 2.13 TFHRI - Test function f₁(x) = x² with n + 1 equispaced nodes in

[0, 1], n = 10, 60, ω = 0.1 and d = 1 . . . 41 2.14 TFHRI - Test function f₂(x) = sin(2πx) with n + 1 equispaced

nodes in [0, 1], n = 10, 60, ω = 0.1 and d = 1 . . . 41 2.15 TFHRI - Test function f₃(x) = |x| with n + 1 equispaced nodes in

[−1, 1], n = 10, 60, ω = 1 and d = 1 . . . 42 2.16 TFHRI - Test function f₄ with n + 1 equispaced nodes in [0, π],

n = 10, 60, ω = 0.1 and d = 1 . . . 43 2.17 TFHRI - Test function f₅ with n + 1 equispaced nodes in [0, π],

n = 10, 60, ω = 0.1 and d = 1 . . . 43 5

(8)

2.18 TFHRI - Lebesgue constants with n + 1 nodes, 6 ≤ n ≤ 40 even, d = 1 (left) and d = 3 (right) and ω = 0.1. The plots show the Lebesgue constants (blue), the upper bounds (red) and the lower bounds (green) . . . 44 2.19 Lebesgue functions - TFHRI with n + 1 nodes with n = 10, 20, 40

and d = 3 . . . 45 3.1 TFHRI - Test function f₁with (n+1)²equispaced nodes, n = 6, 10,

and d = 2 . . . 64 3.2 TFHRI - Test function f₁with (n+1)²Chebyshev nodes, n = 6, 10,

and d = 2 . . . 64 3.3 TFHRI - Test function f₂with (n+1)²equispaced nodes, n = 6, 10,

and d = 2 . . . 65 3.4 TFHRI - Test function f₂with (n+1)²Chebyshev nodes, n = 6, 10,

and d = 2 . . . 65 3.5 TFHRI - Test function f₁ with (n+1)²equispaced nodes in[−1, 1]²,

n = 6, 10 and d = 2 . . . 66 3.6 TFHRI - Test function f₁ with (n+1)²Chebyshev nodes in[−1, 1]²,

n = 6, 10 and d = 2 . . . 66 3.7 TFHRI - Interpolation error of f (x, y) = cos(x + y) with (n + 1)²

equispaced nodes in [0, 1]², n = 6, ..., 30, d = 0 (left) and d = 3 (right) . . . 68 3.8 TFHRI - Interpolation error of f (x, y) = cos(x + y) with (n + 1)²

equispaced nodes in [0, 1]², n = 6, ..., 30, d₁ = 1, d₂ = 3 (left) and d₁ = 2, d₂ = 3 (right) . . . 69 3.9 Lebesgue constant (blue) and theoretical bounds: upper bound

(red) and lower bound (green) with N = (n + 1)² equispaced nodes in [0, 1]² with n = m = 6, ..., 100, d = 0 (left) and d = 3 (right) . . 69 3.10 Lebesgue functions - TPFHRI with (n + 1)² equispaced nodes in

[0, 1]², n = 8 and d₁ = d₂ = 0, 2, 4 . . . 70 3.11 Lebesgue functions - TPFHRI with (n + 1)² Chebyshev nodes in

[0, 1]², n = 8 and d₁ = d₂ = 0, 2, 4 . . . 70 3.12 Lebesgue functions - TPFHRI with (n + 1)² equispaced nodes in

[0, 1]², n = 8 and d₁ = 3, d₂ = 0, 1, 2 . . . 71 3.13 Lebesgue functions - TPFHRI with (n + 1)² Chebyshev nodes in

[0, 1]², n = 8 and d₁ = 3, d₂ = 0, 1, 2 . . . 71

(9)

List of Tables

2.1 Trigonometric interpolation error - d = 4 . . . 31

2.2 Comparison TFHRI error and FHRI error - d = 4 . . . 32

2.3 Comparison TFHRI error with d = 2 and d = n . . . 33

2.4 Trigonometric interpolation error - d = 3 . . . 42

2.5 Comparison TFHRI error and FHRI error - d = 3 . . . 44

2.6 Comparison TFHRI error with d = 3 and d = n . . . 44

3.1 TPFHRI error with (n + 1)² equispaced nodes - d = 3 . . . 66

3.2 TPFHRI error with (n + 1)² Chebyshev nodes - d = 3 . . . 67

3.3 TPFHRI error with different d₁ and d₂ and equispaced nodes - Franke’s function . . . 67

3.4 TPFHRI error with different d1 and d2 and Chebyshev nodes - Franke’s function . . . 67 3.5 TPFHRI error with different d₁ and d₂ and equispaced nodes - norm 68 3.6 TPFHRI error with different d1 and d2 and Chebyshev nodes - norm 68

7

(10)

(11)

Chapter 1 Floater Hormann Rational Interpolant - FHRI

1.1 Generality

The Floater-Hormann rational interpolant, indicated as FHRI, is a family of interpolants, that depends on a parameter d. If we choose a function f : [a, b] −→

R, a sequence of n + 1 points, called nodes, a = x0 < ... < x_n = b and some values fi=f (xi) i = 0, ..., n, each FHRI can be constructed as follow: choose any integer d with 0 ≤ d ≤ n and for each i = 0, 1, ..., n − d, let p_i(x) denote the unique polynomial of degree at most d that interpolates f at the d + 1 points x_i,...,x_i+d, then

r(x) =

n−d

X

i=0

λ_i(x)p_i(x)

n−d

X

i=0

λ_i(x)

(1.1)

with

λ_i(x) = (−1)ⁱ

(x − x_i) · · · (x − x_i+d). (1.2) The functions λ_i(x) only depends on the nodes x_i so that the rational interpolant r(x) depends linearly on the data f (xi). As special cases for d = 0 we have the Berrut’s interpolant and for d = n the polynomial interpolant of total degree n.

In the following when we’ll talk about FHRI, we’ll focus our attention on an interpolant of that family with a particular d.

FHRI may be put in barycentric form [1]

r(x) =

n

X

k=0

w_k

x − x_kf (xk)

n

X

k=0

w_k x − x_k

(1.3)

9

(12)

where

w_k =X

i∈Jk

(−1)ⁱ

i+d

Y

j=i,j6=k

1

x_k− x_j (1.4)

with Jk = {i ∈ {0, 1, 2, ..., n − d} such that k − d ≤ i ≤ k}.

Lemma 1.1.1 ([4]). If the interpolation nodes are equidistant, then the weights in (1.4) satisfy

1 h^dd!

X

i∈Jk

d k − i

= |wk| ≤ 2^d

h^dd!. (1.5)

In the special case of equispaced nodes, the weights can be written in another form, knowing that an uniform scaling does not change the interpolant, [3][1]

(−1)^dh^dd!w_k= (−1)^kX

i∈Jk

d k − i

= (−1)^kβ_k where

β_k=

n

X

i=d

d i − k

=





 Pk

i=0 d

k, if k ≤ d,

2^d, if d ≤ k ≤ n − d, βn−k, if k ≥ n − d

(1.6)

So the rational interpolant becomes,

r(x) =

n

X

k=0

(−1)^kβ_k x − xk

f (x_k)

n

X

k=0

(−1)^kβ_k x − x_k

(1.7)

If we rewrite it in a more suitable form, it has been proved the following Theorem 1.1.2 (Absence of poles in R). [Th.1, [1]] For all d, 0 ≤ d ≤ n, the rational function r in (1.1) has no poles in R.

Thus now is easy to show that:

• r(x) interpolates the data (x_i, f (x_i))

• r(x) reproduces polynomials of degree at most d

For what concerns the accuracy of FHRI in the function approximation, we define

h = max

0≤i≤n−1(x_i+1− x_i), (1.8)

kf k_∞= max

x∈[a,b]

|r(x) − f (x)|

and

β = max

1≤i≤n−2min x_i+1− x_i xi− xi−1

, x_i+1− x_i xi+2− xi+1

, the following results hold

(13)

Theorem 1.1.3 (Interpolation error - case d = 0). [Th.3,1] Suppose d=0, f ∈ C²([a,b]) and let h be as in (1.8). If n is odd then

kr − f k_∞ ≤ h(1 + β)(b − a) f⁰⁰

_∞

2 . (1.9)

If n is even then

kr − f k_∞≤ h(1 + β) (b − a) f⁰⁰

_∞

2 +

f⁰

_∞

!

(1.10) Theorem 1.1.4 (Interpolation error - case d ≥ 1). [Th.2,1] Suppose d ≥ 1, f ∈ C^d+2([a,b]) and let h be as in (1.8). If n-d is odd then

kr − f k_∞ ≤ h^d+1(b − a)

f^(d+2) _∞

d + 2 . (1.11)

If n-d is even then

kr − f k_∞≤ h^d+1 (b − a)

f^(d+2) ∞

d + 2 +

f^(d+1) ∞

d + 1

!

(1.12) The Lebesgue constant is an index of stability for the interpolant, i.e. represents how much errors on the data could be amplified. If we suppose that f ∈ C([a, b]) and that we don’t know the exact values f_i but perturbated ones f˜i = fi+ δi, then

kr_n− ˜r_nk_∞ ≤ Λ_n max

0≤k≤n

f_k− ˜f_k .

where r_n,˜r_n are FHRI, that interpolate (x_i, f_i) and (x_i, ˜f_i) respectively. If we define

b_j =

w_j x − x_j

n

X

k=0

w_k x − x_k

, (1.13)

they satisfy the Lagrange property

b_i(x_j) = δ_ij = 1 se i = j,

0 se i 6= j (1.14)

and therefore they form a cardinal base. The Lebesgue constant of this operator is

Λ_n= max

a≤x≤bΛ_n(x), where Λ_n(x) is the Lebesgue function,

Λ_n(x) =

n

X

j=0

|b_j(x)| .

In the case of equidistant nodes, we cite

(14)

Theorem 1.1.5 (Bound Lebesgue constant at equidistant nodes - d = 0). [Ths.1- 2,2] The Lebesgue constant associated with rational interpolation at equidistant nodes {xj = _n^j}_j=0,...,n with the basis functions (1.13) satisfies

c_nln(n + 1) ≤ Λ_n ≤ (2 + ln(n)) (1.15) where cn= _4+nπ²ⁿ with limn→∞c_n = _π².

Theorem 1.1.6 (Bound Lebesgue constant at equidistant nodes - d ≥ 1). [Ths 1-2,3] The Lebesgue constant associated with rational interpolation at equidistant nodes {xj = _n^j}_j=0,...,n with the basis functions (1.13) and n ≥ 2d satisfies

1 2^d+2

2d + 1 d

ln(n

d − 1) ≤ Λ_n≤ 2^d−1(2 + ln(n)). (1.16)

(15)

Chapter 2 Trigonometric FHRI (TFHRI)

2.1 Trigonometric interpolation - Generality

Suppose I = [0, b] with b < 2π and be f : I −→ R. For arbitrary n + 1 nodes 0 = x₀ < ... < x_n = b and some values f_i := f (x_i) the trigonometric interpolant is

if n = 2m with m ∈ Z

p(x) = a₀ 2 +

m

X

k=1

(akcos(kx) + bksin(kx)) and if n = 2m + 1 with m ∈ Z

p(x) = a0

2 +

m

X

k=1

(a_kcos(kx) + b_ksin(kx)) + a_m+1cos(mx).

In the case n = 2m, the previous formulas tell us that the trigonometric interpolant is a linear combination of 2m+1 functions, for instance 1, cos(x), sin(x), . . . , cos(mx), sin(mx). They represent a Chebyshev system, that is for every set of data (x_i, f_i)_0≤1≤n an unique interpolant exists or equivalently

det(V ) =

1 cos(x₀) sin(x₀) . . . cos(mx₀) sin(mx₀) ... ... ... . . . ... ... 1 cos(x_n) sin(x_n) . . . cos(mx_n) sin(mx_n)

6= 0.

Instead in the case n = 2m+1, where p is a linear combination of 1, cos(x), sin(x), . . . , cos(mx), sin(mx), cos((m + 1)x), the uniqueness of the interpolant isn’t di- rectly garanteed and the non-vanishing determinant is to be checked case by case.

Now the determinant has the following form [6]

det(V ) = (−1)^3m2−m² 2^2m²^−2m+1sin

P2m−1 j=0 x_j

2

!

Y

0≤q<p≤2m−1

sin x_p− x_q 2

.

Knowing that x_k are distinct and 0 < ^x^p^−x₂ ^q < π, it follows 13

(16)

det(V ) = 0 ⇐⇒ sin

P2m−1 j=0 x_j

2

!

= 0 ⇐⇒

2m−1

X

j=0

x_j = 2νπ ∃ν ∈ N. (2.1)

For every n, adding the condition σ :=P2m−1

j=0 x_j 6= 2νπ ∀ν ∈ Z if n is odd, the trigonometric interpolant is given by [5]

p(x) =

n

X

k=0

`_k(x)f_k

where {`_k}_k=0,...,n are the Lagrange trigonometric polynomials,

`_k = a_k`(x)

cst x − x_k 2

+ c

, (2.2)

a_k = 1

Qn

j=0, j6=ksin ^x^k^−x₂ ^j , `(x) =

n

Y

j=0

sin x − x_j 2

and

cst(x) :=

( csc(x) = _sin(x)¹ if n even

cot(x) = ^cos(x)_sin(x) if n odd. , c := 0 if n even cot(^σ₂) if n odd.

If we consider the general case I = [a, b], p does not provide the formula of interpolant if for example thare are some nodes which difference is a multiple of 2π unequal to 0. With the aim to include also this case we introduce the pulsation ω = ^2π_T where T represents the period. So after choosing T > b − a the trigonometric interpolant becomes

p(x) =

n

X

k=0

`_k(x)f_k

where {`_k}_k=0,...,n are the Lagrange trigonometric polynomials,

`_k = a_k`(x)

cst ω

2(x − x_k)

+ c

, (2.3)

ak = 1

Qn

j=0, j6=ksin ^ω₂(x_k− x_j) , `(x) =

n

Y

j=0

sin ω

2(x − xj)

,

c := 0 if n even cot(^ω₂σ) if n odd.

(17)

2.2 Trigonometric FHRI (TFHRI)

Combining the results of Chapter 1 and of the previous section, we wish to ex- tend FHRI to the trigonometric case. By noting the formulas of trigonometric interpolant, cited before and first mentioned by Gauss in [7], we think that the most suitable way to build the TFHRI, is replacing λ_k(x) in (1.1) with

λ^t_k(x) := (−1)^k

sin(^ω₂(x − x_k)) · · · sin(^ω₂(x − x_k+d)) (2.4) so TFHRI might be written as

r^t(x) =

n−d

X

i=0

λ^t_i(x)

^i+d X

k=i

a_k,i`⁽ⁱ⁾(x)

cst ω

2(x − x_k)

+ c_i

f_k

n−d

X

i=0

λ^t_i(x)

(2.5)

with

a_k,i = 1

Qi+d

j=i, j6=ksin ^ω₂(x_k− x_j), `⁽ⁱ⁾(x) =

i+d

Y

j=i

sin ω

2(x − x_j)

,

ci = cot ω 2

i+d

X

j=i

xj

Noting that,

1 =

i+d

X

k=i

a_k,i`⁽ⁱ⁾(x)

cst ω

2(x − x_k)

+ c_i

we write the interpolant as

r^t(x) =

n

X

k=0

X

i∈Jk

(−1)ⁱa_k,icst ω

2(x − x_k)

+X

i∈Jk

(−1)ⁱa_k,ic_i

f_k

n

X

k=0

X

i∈Jk

(−1)ⁱa_k,icst ω

2(x − x_k)

+X

i∈Jk

(−1)ⁱa_k,ic_i

=

n

X

k=0

w^t_kcst ω

2(x − xk)

+ αk

fk n

X

k=0

w^t_kcst ω

2(x − x_k)

+ α_k

.

where

w^t_k=X

i∈Jk

(−1)ⁱak,i =X

i∈Jk

(−1)ⁱ

i+d

Y

j=i,j6=k

1

sin ^ω₂(x_k− x_j) (2.6)

(18)

with J_k = {i ∈ {0, 1, 2, ..., n − d} such that k − d ≤ i ≤ k}

and

α_k :=







0 if d even

X

i∈Jk

(−1)ⁱa_k,ic_i if d odd

2.3 Case d even

Now we consider the general case I=[a,b]. The TFHRI is r^t(x) =

n

X

k=0

b^t_k(x)f_k, (2.7)

where

b^t_k(x) =

w_k^t sin ^ω₂(x − x_k)

n

X

k=0

w^t_k sin ^ω₂(x − x_k))

(2.8)

With easy computations it may be verified that r^t(x) indeed interpolates the data {x_k, f_k}.

Hypothesis 1 on ω We assume that:

• ^ω₂|x − x_k| ≤ (b − a)^ω₂ < ^π₂ ⇒ ω < _(b−a)^π

So the sine is increasing and the functions sin(^ω₂|x − x_k|) do not vanish in I Following the same proof of the corresponding theorem in [1] we may prove Theorem 2.3.1 (Absence of poles). For all even 0 ≤ d ≤ n and every pulsation ω that satisfies Hyp 1, the TFHRI r^t in (2.7) has no poles in [a,b].

2.3.1 Lebesgue constant

Let I be as before, z_i = ^(b−a)i_n the nodes and y_i = ^bi_n.We suppose that the pulsation ω satisfies the Hyp 1, so the Lebesgue constant is

Λ_n= max

z∈[a,b]

n

X

k=0

|b_k| = max

y∈[0,b−a]

n

X

k=0

|w^t,y_k | sin ^ω₂|y − y_k|

n

X

k=0

w^t,y_k sin ^ω₂(y − y_k))

= max

y∈[0,b−a]Λ_n(y).

where w^t,y_k are the weights in (2.20) with nodes y_i.

(19)

Due to the previous reasonings, we may assume that I = [0, b − a] but we really focus our attention only I = [0, 1] because if b 6= 1 appear some constants that simplify each other. So the bounds in the following hold for every choice of I, only the pulsation ω takes care about what the actual interval I is.

We consider, without lost generality, the interval I = [0, 1] and a pulsation ω such that ω < π. We define g(x) := _sinc(x)¹ and show its plot below.

Figure 2.1: g-plot in [−^π₂,^π₂].

It is evident that g is a positive function, is greater than 1 and is simmetric respect to the origin. As it is defined, g does not exist in kπ ∀k ∈ Z r {0}. But for our purpouses, we consider it always in compact interval included in [−^π₂,^π₂].

Then the following bounds hold

1 ≤ g(ω

2(x − xk)) ≤

ω 2

sin(^ω₂) := M. (2.9)

and

(x − x_k)(x_k+1− x) ≤ 1

4n². (2.10)

We recall also the bounds for the partial sums of the Leibnitz series and the harmonic series, namely

π

4 − 1

2n + 3 ≤

n

X

k=0

(−1)^k 2k + 1 ≤ π

4 + 1

2n + 3 (2.11)

and

ln(n + 1) ≤

n

X

k=0

1

k ≤ ln(2n + 1) (2.12)

for any n ∈ N. Moreover, it follows from (2.12) that

n

X

k=0

1 2k + 1 =

2n+1

X

k=1

1 k −

n

X

k=1

1

2k ≥ ln(2n + 2) −1

2ln(2n + 1) ≥ 1

2ln(2n + 3) (2.13)

(20)

Theorem 2.3.2 (upper bound Lebesgue constant d = 0). The Lebesgue constant associated with rational interpolant in [0, 1], with a pulsation ω according to Hyp 1, at equidistant nodes {xj = _n^j}_j=0,...,n, with the basis functions (2.8) satisfies

Λ_n≤ M

2 − M(2 + ln(n)).

Proof. Let x be in I. If x = xk for any k then Λ_n(x) = 1. So let x_k < x < x_k+1 with 0 ≤ k ≤ n − 1 and consider

Λn,k(x) =

(x − x_k)(x_k+1− x)

n

X

j=0

1 sin(^ω₂|x − x_j|)

(x − x_k)(x_k+1− x)

n

X

j=0

(−1)^j sin(^ω₂(x − x_j))

:= N D.

Our goal is to bound the numerator N from above and the denominator D from below. We first analyze the numerator,

N = (x−xk)(xk+1−x)

n

X

j=0

1

sin(^ω₂|x − x_j|) = (x−xk)(xk+1−x)2 ω

n

X

j=0

g(^ω₂|x − x_j|)

|x − x_j| ≤

≤ 2M

ω (x − x_k)(x_k+1− x)

n

X

j=0

1

|x − x_j| ≤ 2M ω

1

n +ln(n) 2n

where we use (2.9) and the last inequality is described in [2]. Now we focus on the denominator and split the proof into 4 cases.

1) k and n both even

D =

(x − x_k)(x_k+1− x)

n

X

j=0

(−1)^j sin(^ω₂(x − x_j))

.

Since by Hyp 1 −^π₂ < ^ω₂(x − x_j) < ^π₂, using the fact that sine is an increasing function in [0,^π₂] and x > x_k, we have

sin ω

2(x − x₀)

> sin ω

2(x − x₁)

> ... > sin ω

2(x − x_k)

and sin ω

2(x−x_k+1)

= − sin(ω

2(x_k+1−x)) > − sin ω

2(x_k+2−x)

> ... > − sin ω

2(x_n−x)

. From these facts we get

k

X

j=0

(−1)^j

sin(^ω₂(x − x_j)) −

n

X

j=k+1

(−1)^j

sin(^ω₂(x_j − x)) = (2.14)

(21)

= 1

sin(^ω₂(x − x₀))+

1

sin(^ω₂(x − x₂))− 1

sin(^ω₂(x − x₁))

+ ...+

+

1

sin(^ω₂(x − xk))− 1

sin(^ω₂(x − xk−1))

+

1

sin(^ω₂(xk+1− x))− 1

sin(^ω₂(xk+2− x))

+

+... +

1

sin(^ω₂(x_n−1− x)) − 1

sin(^ω₂(x_n− x))

> 0.

So we can ignore the absolute value in the denominator D. Following the idea of the proof in [2] and using also (2.9), we find

D = (x−x_k)(x_k+1−x)

n

X

j=0

(−1)^j

sin(^ω₂(x − xj)) = (x−x_k)(x_k+1−x)

^k−1 X

j=0

(−1)^j sin(^ω₂(x − xj))+

+g(^ω₂(x − x_k))

ω

2(x − x_k) +g(^ω₂(x_k+1− x))

ω

2(x_k+1− x) −

n

X

j=k+2

(−1)^j sin(^ω₂(x_j− x))

≥

≥ (x − x_k)(x_k+1− x)

1

ω

2(x − x_k)+ 1

ω

2(x_k+1− x)

+

+(x−x_k)(x_k+1−x)

^k−1 X

j=0

(−1)^j sin(^ω₂(x − x_j))−

n

X

j=k+2

(−1)^j sin(^ω₂(x_j − x))

= 2

ωn+(x−x_k)(x_k+1−x)S.

We study S and use the previous observation about the positiveness of the sum in the denominator,

S =

k−1

X

j=0

(−1)^j

sin(^ω₂(x − x_j) −

n

X

j=k+2

(−1)^j

sin(^ω₂(x_j− x)) = (2.15)

= 1

sin(^ω₂(x − x₀)) +

k−2 2

X

s=1

1

sin(^ω₂(x − x_2s)) − 1

sin(^ω₂(x − x_2s−1))

− 1

sin(^ω₂(x − x_k−1))− 1

sin(^ω₂(x_k+2− x))+

n−k 2

X

s=2

1

sin(^ω₂(x_k+2s−1− x))− 1

sin(^ω₂(x_k+2s− x))

≥

≥ − 1

sin(^ω₂(x − x_k−1))− 1

sin(^ω₂(x_k+2− x)) ≥ − 1

sin(^ω₂(x_k− x_k−1))− 1

sin(^ω₂(x_k+2− x_k+1)) =

= −g ω 2n

2 ω

1

x_k− x_k−1 + 1 x_k+2− x_k+1

= g ω 2n

2(−2n)

ω ≥ 2M (−2n)

ω .

We return to D and using (2.10) we get D = 2

ωn+(x−xk)(xk+1−x)S ≥ 2

ωn−(x−xk)(xk+1−x)2M (2n)

ω ≥ 2

ωn− 1 4n²

2M (2n)

ω =

= 2 ωn

1 − M

2

= 2 ωn

2 − M 2

= 2 ω

2 − M 2n

(2.16)

(22)

2) k even and n odd

Now we add a single positive term _x ¹

n−x to S and therefore all the previous bounds are still true. We prove again (2.16).

3) k odd and n even

With similar calculation as before, we show that

k

X

j=0

(−1)^j

sin(^ω₂(x − x_j)) +

n

X

j=k+1

(−1)^j

sin(^ω₂(x − x_j)) < 0.

Now we consider ˆD, that is the denominator D without the absolute value.

Then we construct a bound for D.

D = (x−xˆ _k)(x_k+1−x)

n

X

j=0

(−1)^j

sin(^ω₂(x − x_j)) = (x−x_k)(x_k+1−x)

^k−1 X

j=0

(−1)^j

sin(^ω₂(x − x_j))−

−g(^ω₂(x − x_k))

ω

2(x − x_k) − g(^ω₂(x_k+1− x))

ω

2(x_k+1− x) −

n

X

j=k+2

(−1)^j sin(^ω₂(x_j − x))

=

= −(x − x_k)(x_k+1− x) g(^ω₂(x − x_k))

ω

2(x − x_k) + g(^ω₂(x_k+1− x))

ω

2(x_k+1− x)

+

+(x − x_k)(x_k+1− x)

k−1

X

j=0

(−1)^j

sin(^ω₂(x − x_j))−

n

X

j=k+2

(−1)^j sin(^ω₂(x_j − x))

=

= −2 ω

(x_k+1− x)g(ω

2(x − x_k)) + (x − x_k)g(ω

2(x_k+1− x))

+ (x − x_k)(x_k+1− x)S.

We might estimate S and first write it as sum of negative and positive terms,

S =

k−1

X

j=0

(−1)^j

sin(^ω₂(x − x_j)) −

n

X

j=k+2

(−1)^j

sin(^ω₂(x_j − x)) = (2.17)

=

k−3 2

X

s=0

<0

z }| {

1

sin(^ω₂(x − x_2s))− 1

sin(^ω₂(x − x_2s+1))

+ 1

sin(^ω₂(x − x_k−1))+ 1

sin(^ω₂(x_k+2− x))+

+

n−k−1 2

X

s=2

<0

z }| {

1

sin(^ω₂(x_k+2s− x)) − 1

sin(^ω₂(x_k+2s−1− x))

− 1

sin(^ω₂(x_n− x)) ≤

≤ 1

sin(^ω₂(x − x_k−1))+ 1

sin(^ω₂(x_k+2− x)) ≤ g(^ω₂(x − x_k))

ω

2(x − x_k−1) +g(^ω₂(x_k+2− x))

ω

2(x_k+2− x) ≤

≤ 2M ω

1

x_k+ x_k−1 + 1 x_k+2− x_k+1

= 2M 2n ω .

(23)

We return to ˆD and use (2.10) D ≤ −ˆ 2

ω

(xk+1−x)g(ω

2(x−xk))+(x−xk)g(ω

2(xk+1−x))

+(x−xk)(xk+1−x)S ≤

≤ −2 ω

(x_k+1−x)g(ω

2(x−x_k))+(x−x_k)g(ω

2(x_k+1−x))

+(x−x_k)(x_k+1−x)2M 2n

ω ≤

≤ 2 ω

− 1

n + M 2n 4n²

= 2 ω

−2 + M 2n

. Since ω ∈ [0, π), M < g(π) < 2 and so it implies that

D ≥ 2 ω

| − 2 + M | 2n

= 2 ω

2 − M 2n

4) k and n both odd

In S the terms with j ≥ k + 3 are an even number so we can group them all in the second sum. So we get again the bounds of the case 3).

Finally we sum up the results and obtain

Λ_n= max

k=0,...,n−1

x_k<x<xmax_k+1Λ_n,k(x)

≤ 2M

ω

1

n +ln(n) 2n

2

ω

2 − M 2n

= M

2 − M

2 + ln(n)

Theorem 2.3.3 (lower bound Lebesgue constant - d = 0). The Lebesgue constant associated with trigonometric rational interpolant in [0, 1], with a pulsation ω according to Hyp 1, at equidistant nodes {xj = _n^j}_j=0,...,n with basis functions (2.8) satisfies

Λ_n ≥ 2n

M (4 + nπ)ln(n + 1) Proof. We will follow the proof in [2].

By general definition of the Lebesgue function we have

Λ_n(x) =

n

X

j=0

1 sin(^ω₂|x − _n^j|)

n

X

j=0

(−1)^j sin(^ω₂(x −_n^j))

=

n

X

j=0

g(^ω₂|x −_n^j|)

ω

2|x − _n^j|

n

X

j=0

g(^ω₂(x −_n^j))(−1)^j

ω

2(x −_n^j)

=

n

X

j=0

g(^ω₂|x −_n^j|)

|2nx − 2j|

n

X

j=0

g(^ω₂(x −_n^j))(−1)^j (2nx − 2j)

=: N (x) D(x).

(24)

Our goal now is to bound the numerator N (x) from below and the denominator D(x) from above. We split the proof into 2 cases.

1) n even, ∃ k ∈ N such that n=2k We evaluate the numerator N(x) at x = ⁿ⁺¹_2n and using (2.9), we obtain

N n + 1 2n

=

n

X

j=0

g(^ω₂|^n+1−2j_2n |)

|n + 1 − 2j| ≥

2k

X

j

1

|2(k − j) + 1| ≥ ln(n + 1).

The last inequality is described in [2]. Now we turn to the denominator

D n + 1 2n

=

2k

X

j=0

g(^ω₂(^2(k−j)+1_2n ))(−1)^j (2(k − j) + 1)

≤

k

X

j=0

g(^ω₂(^2(k−j)+1_2n ))(−1)^j (2(k − j) + 1)

+

2k

X

j=k+1

g(^ω₂(^2(k−j)+1_2n ))(−1)^j (2(k − j) + 1)

=

(−1)^k

k

X

j=0

g(^ω₂(^2j+1_4k ))(−1)^j 2j + 1

+

(−1)^k

k−1

X

j=0

g(^ω₂(^2j+1_4k ))(−1)^j 2j + 1

=

k

X

j=0

g(^ω₂(^2j+1_4k ))(−1)^j 2j + 1

+

k−1

X

j=0

g(^ω₂(^2j+1_4k ))(−1)^j 2j + 1

=: |A| + |B|

We define y_j := ^ω₂(^2j+1_4k ), we focus on |A| but the same reasoning holds for |B|.

Since g is an increasing function in [0, π), thanks to (2.11), we note that

A = (g(y0) −1

3g(y1)) + (1

5g(y2) −1

7g(y3)) + ... ≤ g(y1)(1 −1

3) + g(y3)(1 5−1

7) + ... ≤

≤ M

k

X

j=0

1

2j + 1 ≤ M π

4 + 1 2k + 3

= M π

4 + 1 n + 3

.

A is the sum of positive terms. In fact, if k is odd, but this holds also if k is even,

A =

k−1 2

X

j=0

g(y_2j)

4j + 1 −g(y_2j+1) 4j + 3

,

g(y_2j)

4j + 1 −g(y_2j+1)

4j + 3 ≥ 0 ∀j ⇐⇒ sin ω 2

(4j + 1) 4k

≤ sin ω 2

(4j + 2) 4k

∀j.

But under our hypothesis on ω, this is true ∀j. Then we may ignore the absolute value and get

A ≤ M π

4 + 1 n + 3

.

(25)

With similar computations it may be seen that

|B| = B ≤ M π

4 + 1 n + 1

. Finally we have

|A| + |B| ≤ M π

4 + 1

n + 3 +π

4 + 1 n + 1

= M π

2 + 2 n + 1

We sum up the results and obtain

Λn ≥ 2 ln(n + 1) M

π + 4 n + 1

2) n odd, ∃ k such that n=2k+1 Now we consider x = ¹₂ and evaluate the numerator and the denominator both at this point. Let us start with the numerator. In the following sequence of inequalities we use (2.9) and (2.13) and the same proof in [2].

N 1 2

≥

n

X

j=0

g(^ω₂|^n−2j_2n |)

|n − 2j| ≥ ln(2k + 3) = ln(n + 2)

Now we focus on the denominator. As we have seen in the previous case, thanks to our hypothesis on ω, the sum is positive. So in the following the absolute value may be ignored.

D 1 2

=

n

X

j=0

g(^ω₂(^n−2j_2n ))(−1)^j (2n¹₂ − 2j)

=

k

X

j=0

g(^ω₂(^n−2j_2n ))(−1)^j 2(k − j) + 1 +

+

2k+1

X

j=k+1

g(^ω₂(^n−2j_2n ))(−1)^j 2(k − j) + 1

=

k

X

j=0

(g(^ω₂(^1−2j_2n )) + g(^ω₂(^−2j−1_2n )))(−1)^j 2j + 1

.

Defining

G_j = g ω 2

1 − 2j 2n

+ g ω 2

−2j − 1 2n

it easy to see that G_j > 0 ∀j and that it is an increasing sequence. Thanks to these observations and to the similar proof in [2], finally we have

D 1 2

=

k

X

j=0

G_j(−1)^j

2j + 1 ≤ G₁(1 −1

3) + G₃(1 5 −1

7) + ... ≤ 2M

k

X

j=0

(−1)^j 2j + 1 ≤

≤ 2M π

4 + 1 2k + 3

= M π

2 + 2 n + 2

.

(26)

We obtain

Λ_n 1 2

= N (¹₂)

D(¹₂) ≥ ln(n + 2) M π

2 + 2 n + 2

=

2 ln(n + 2) M

π + 4 n + 2

.

and conclude

Λ_n ≥ 2 ln(n + 2) M

π + 4 n + 2

≥

2 ln(n + 1) M

π + 4 n + 1

≥

2 ln(n + 1) M

π + 4

n

=

2n

M (4 + nπ)ln(n+1)

Proposition 2.3.4 (Bound weigths d even). If the interpolation nodes are equispaced, then the weigths in 2.6 satisfy

2^d ω^d

1 h^dd!

X

i∈Jk

d k − i

≤ 2^d

ω^d|wk| ≤ |w_k^t| ≤ 2^dM^d

ω^d |wk| ≤ 2^dM^d ω^d

2^d

h^dd!. (2.18) Proof.

|w^t_k| =X

i∈Jk

i+d

Y

j=i,j6=k

1

sin(^ω₂|x_k− x_j|) ≥ 2^d ω^d

X

i∈Jk

i+d

Y

j=i,j6=k

g(^ω₂|x_k− x_j|)

|x_k− x_j| ≥

≥ 2^d ω^d

X

i∈Jk

i+d

Y

j=i,j6=k

1

|x_k− x_j| = 2^d ω^d|w_k|.

Now prove the bound from above.

|w_k^t| = 2^d ω^d

X

i∈Jk

i+d

Y

j=i,j6=k

g(^ω₂|x_k− x_j|)

|x_k− x_j| ≤ 2^dM^d ω^d

X

i∈Jk

i+d

Y

j=i,j6=k

1

|x_k− x_j| = 2^dM^d ω^d |w_k|.

Thanks to (1.5) the thesis follows easily.

Theorem 2.3.5 (Upper bound Lebesgue constant - d ≥ 2, even). The Lebesgue constant associated with trigonometric rational interpolant in [0, 1], with a pulsation ω according to Hyp 1, at equidistant nodes {xj = _n^j}_j=0,...,n with basis functions (2.8) satisfies

Λ_n ≤ M^d+12^d−1 2 + ln(n)

(27)

Proof. If x = xk for any k, then Λ_n(x) = 1. Otherwise, x_k < x < x_k+1 with 0 ≤ k ≤ n − 1 and we consider

Λ_n,k(x) =

n

X

j=0

|w^t_j| sin(^ω₂|x − x_j|)

n

X

j=0

w_j^t sin(^ω₂(x − x_j))

=

h^dd!(x − x_k)(x_k+1− x)

n

X

j=0

|w_j^t| sin(^ω₂|x − x_j|)

h^dd!(x − x_k)(x_k+1− x)

n

X

j=0

w_j^t sin(^ω₂(x − x_j))

:= N_k(x) Dk(x).

First of all we try to bound the numerator from above.

N_k(x) = 2

ωh^dd!(x − x_k)(x_k+1− x)

n

X

j=0

g(^ω₂|x − xj|)|w_j^t|

|x − xj| ≤

≤ 2^d+1M^d

ω^d+1 h^dd!(x − x_k)(x_k+1− x)

n

X

j=0

g(^ω₂|x − x_j|)|w_j|

|x − x_j| ≤

≤ 2^d+1M^d+1

ω^d+1 (x−x_k)(x_k+1−x)

n

X

j=0

|w_j|h^dd!

|x − x_j| = 2^d+1M^d+1

ω^d+1 (x−x_k)(x_k+1−x)

n

X

j=0

β_j

|x − x_j| ≤

≤ 2^d+1

ω^d+1M^d+12^d 1 n + 1

2nln(n)

where the last inequality holds thanks to [3].

Now we turn to the denominator. From the definition of β_j in (1.6) is easy to see that

(−1)^dd!h^d

n

X

j=0

w_j

x − x_j = (−1)^dd!h^d

n−d

X

j=0

λ_j(x) =

n

X

j=0

(−1)^jβ_j x − x_j with λ_j(x) as in (1.2). So ∀j ∈ {0, ..., n − d}

λ^t_j(x) = (−1)^j

sin(^ω₂(x − x_j)) . . . sin(^ω₂(x − x_j+d)) = 2^d ω^d

j+d

Y

i=j

g ω

2(x − x_i)

λ_j(x)

Assuming k ≤ n − d and keeping in mind the proof of Theorem 2.3.1 and (2.9), we have

D_k(x) = d!h^d(x − x_k)(x_k+1− x)

n

X

j=0

λ^t_j(x)

≥ d!h^d(x − x_k)(x_k+1− x)|λ^t_k(x)| =

= d!h^d(x − x_k)(x_k+1− x)

sin(^ω₂(x − x_k)) sin(^ω₂(x_k+1− x)) · · · sin(^ω₂(x_k+d − x)) =

= 2^d+1 ω^d+1

d!h^d(x − x_k)(x_k+1− x)g(^ω₂(x − x_k)) . . . g(^ω₂(x − x_k+d)) (x − x_k)(x_k+1− x) · · · (x_k+d− x) ≥

(28)

≥ 2^d+1 ω^d+1

d!h^d(x − x_k)(x_k+1− x)

(x − x_k)(x_k+1− x) · · · (x_k+d− x) ≥

≥ 2^d+1 ω^d+1

d!h^d

(x_k+2− x_k) · · · (x_k+d − x_k) ≥ 2^d+1 ω^d+1

d!h^d

d!h^d−1 = 2^d+1 ω^d+1

1 n

If k > n−d a similar reasoning leads to this lower bound for D_k(x) by considering λ_k−d+1 instead of λ_k. Finally we sum up the results and obtain

Λ_n= max

k=0,...,n−1

xk<x<xmaxk+1

Λ_n,k(x)

≤ M^d+12^d−1 2 + ln(n)

Theorem 2.3.6 (Lower bound Lebesgue constant - d ≥ 2, even). The Lebesgue constant associated with trigonometric rational interpolant in [0, 1], with a pulsation ω according to Hyp 1, at equidistant nodes {xj = _n^j}_j=0,...,n with basis functions (2.8) satisfies

Λ_n≥ 1 M^d+12^d+2

2d + 1 d

ln(n

d − 1) Proof.

Λ_n(x) :=

h^dd!

n

X

j=0

|w_j^t| sin(^ω₂|x − x_j|)

h^dd!

n

X

j=0

w_j^t sin(^ω₂(x − xj))

:= N (x) D(x).

We consider x^∗ = ^x¹^−x₂ ⁰ = _2n¹ .

We first investigate the numerator, using (2.9) and the bounds of weights w_j^t,

N (x^∗) = d!h^d

n

X

j=0

|w^t_j|

sin(^ω₂|x^∗− x_j|) ≥ d!h^d2^d+1 ω^d+1

n

X

j=0

g(^ω₂(x^∗− x_j))|w_j|

|x^∗− x_j| ≥ 2^d+1 ω^d+1

n

X

j=0

βj

|x^∗− x_j| ≥

≥ 2^d+1

ω^d+1n2^dln(n d − 1) where the last inequality has been taken from [2].

Now we turn to the denominator.

D(x^∗) = h^dd!

n−d

X

j=0

λ^t_j(x^∗) .

We notice that λ^t₀(x^∗) e λ^t₁(x^∗) have the same sign and that the following λ^t_j(x^∗) oscillate in sign and decrease in absolute value. So we get, using (2.9),

D(x^∗) ≤ h^dd!(|λ^t₀(x^∗)| + |λ^t₁(x^∗)|) = d!h^d2^d+1 ω^d+1

|λ₀(x^∗)|

d

Y

i=0

g(ω

2(x^∗− x_i))+

Trigonometric and tensor-product Floater-Hormann rational

Dipartimento di Matematica ”Tullio Levi-Civita”

Corso di Laurea Magistrale in Matematica

Tesi di Laurea magistrale

Trigonometric and tensor-product Floater-Hormann rational

interpolant

Thanks

Contents

List of Figures

List of Tables

Chapter 1

Floater Hormann Rational Interpolant - FHRI

1.1 Generality

Chapter 2

Trigonometric FHRI (TFHRI)

2.1 Trigonometric interpolation - Generality

2.2 Trigonometric FHRI (TFHRI)

2.3 Case d even

2.3.1 Lebesgue constant