Numerical methods based on the Floater–Hormann interpolants for stiff VIEs

Abstract

The Floater–Hormann family of the barycentric rational interpolants has recently gained popularity because of its excellent stability properties and highly order of convergence. The purpose of this paper is to design highly accurate and stable schemes based on this family of interpolants for the numerical solution of stiff Volterra integral equations of the second kind.

1 Introduction

Volterra integral equations (VIEs) of the second kind are often used as mathematical models of physical or biological phenomena with history arising in many practical applications in science and engineering (see [14, 16]), and have the form

$$ y(t)=g(t)+{\int}_{t_{0}}^{t} K(t,s,y(s)) ds, t\in I:=[t_{0},T], $$

(1)

in which $g:I\rightarrow \mathbb {R}^{D}$ and $K:S\times \mathbb {R}^{D}\rightarrow \mathbb {R}^{D}$ are assumed to be given functions where D denotes the dimension of the system and S := {(t, s) : t₀ ≤ s ≤ t ≤ T}. In what follows, we assume that the given functions g and K are smooth enough such that the system of equations (1) has a unique solution [14, 16, 32].

Over the last few decades, numerous numerical methods for the numerical solution of (1) have been introduced in different classes such as global or spectral methods, multistage (and multivalue) methods, and direct quadrature methods which all rely on a considerable variety of foundations and methodologies. Although the convergence of spectral methods may be exponential for equations involving analytic functions g and K (see [33]), and their order adapts automatically to the degree of smoothness of these data, they cannot be very useful in the case of Volterra type equations. Indeed, they treat Volterra equations as the Fredholm ones which means that they require the value of T in advance while this is not very natural in time-dependent problems. In contrast, multistage methods such as collocation methods [13], two-step almost collocation methods [18] and multistep collocation methods [19] are more popular and efficient for solving VIEs (1). An other class of the multistage methods for VIEs is the class of general linear methods, introduced by Izzo et al. in [27] and investigated more in [1, 3]. Although multistage methods have desirable stability and accuracy properties, the computational cost of these methods which usually are fully implicit for computing the internal stage values (for instance, see [1, 3, 27]), is considerable. In fact, they require the values of y, g, and K to be computed at stage abscissa points and solve a (nonlinear) system in sD dimensions in which s is the number of internal stages. The direct quadrature methods [6, 16, 32] for solving (1) are the simplest in the implementation and most familiar ones. Recently, two direct quadrature (global and composite versions) methods based on linear barycentric rational interpolants (LBRI) have been introduced in [10]. The linear stability properties of the composite one have been investigated in [26]. It has been shown that its stability regions, for various choices of (n, d), with respect to both the basic test equation of the form

$$ y(t)=1+{\lambda{\int}_{0}^{t}} y(s) ds, \quad t\geq0, $$

(2)

with $\lambda \in \mathbb {C}$, and a more significative test equation (the convolution test equation) of the form

$$ y(t)=1+{{\int}_{0}^{t}} (\lambda+\mu(t-s)) y(s) ds, t\geq0, $$

(3)

with $\lambda ,\mu \in \mathbb {R}$, are bounded and found that the construction of methods with unbounded stability regions in this class is an open problem. In this paper, we are going to introduce new methods in this class with unbounded stability regions with respect to both test equations (2) and (3).

The paper is organized along the following lines. In Section 1, we briefly review the LBRI and their applications in approximating the definite integral and the first derivative of a given function on a arbitrary set of nodes. The goal of the paper is included in Section 3 with the aim of designing LBRI-based methods for (1) having desirable stability properties which are suited to the numerical solution of stiff VIEs. The convergence analysis of the methods together with their order of convergence are investigated in Section 4. Section 5 provides a discussion on the linear stability of the methods with respect to both the basic and convolution test equations. The robustness and efficiency of the methods and the theoretical results on their order of convergence are illustrated by some numerical experiments in Section 6. Finally, the work of the paper is summed up in Section 7.

2 A review on the barycentric rational finite differences and quadrature

The barycentric form of Lagrange’s interpolation formula to interpolate the given n + 1 data values f_j := f(t_j), j = 0,1,…, n, corresponding to a real function $f:[a,b]\rightarrow \mathbb {R}$ at the n + 1 distinct nodes t₀, t₁, …, t_n, takes the form

$$ p_{n}(t) = \sum\limits_{j=0}^{n} {\lambda_{j}\over t - t_{j}}f_{j}\left/ \sum\limits_{j=0}^{n} {\lambda_{j}\over t - t_{j}}\right., $$

(4)

with the barycentric weights

$$ \lambda_{j} = \left( {\prod}_{i=0\atop i\ne j}^{n}(t_{j}-t_{i})\right)^{-1},\qquad j=0,1,\ldots,n, $$

(5)

which is eminently suitable for machine computation [11, 23]. Note that if the barycentric weights λ_j in (5) are changed to any arbitrary nonzero numbers, namely β_j, the interpolation property of p_n in (4) is still preserved but the resulting function p_n is usually no longer a polynomial but a rational function. In [9], it has been proved that the signs of the barycentric weights β_j must alternate for the rational function to have no poles in [a, b].

Berrut [8] has introduced two LBRI schemes for ordered distinct nodes $t_{0}<t_{1}<\cdots <t_{n}$ in which the barycentric weights are chosen as $\beta _{j}=(-1)^{j}$ and $\beta _{j}=(-1)^{j}\delta _{j}$ with δ_j equal to 1/2 for j = 0, n and 1 for j = 1,2,…, n − 1; the latter are equal to the weights of polynomial interpolation for Chebyshev points of the second kind. A major drawback of these choices for the weights is the low rate of the convergence. It was proved in [20] that the first one converges as $\mathcal {O}(h)$ and the second one as $\mathcal {O}(h^{2})$ for small values of the stepsize $h := {\max \limits } \{t_{j+1} - t_{j} \}$. These low rates of convergence make these schemes rather inadequate for the numerical solution of equations.

Floater and Hormann [20] have introduced a new family of LBRI, depending on a parameter d, as a rational blend of n − d + 1 polynomials interpolating at d + 1 consecutive nodes, converging at the rate $\mathcal {O}(h^{d+1})$. For uniformly spaced points t_j, the barycentric weights of this LBRI take the form, up to a constant factor,

$$ \beta_{j} = {(-1)^{j-d}\over 2^{d}}\sum\limits_{i\in J_{j}}{d\choose j-i},\quad J_{j} := \left\{i\in\{0,\ldots,n-d\}:j-d\le i\le j\right\}, $$

which is used throughout the paper. This family of LBRI does not exhibit Runge’s phenomenon for d fixed [21]. The convergence rate together with the accuracy and desirable stability properties of this LBRI make it an interesting choice for solving smooth problems on the basis of equispaced samples.

A natural way to approximate the derivative and/or integral of a given function is to use the derivative and/or the integral of its interpolant. Because of the good accuracy and excellent stability properties of these LBRI [29], the spirit of the proposed methods for the numerical solution of VIE (1), presented in Section 3, is based on two exemplary applications of the LBRI

$$ r_{n}(t) = \sum\limits_{j=0}^{n} f_{j}\ell_{j}(t),\quad \ell_{j}(t) := {\beta_{j}\over t - t_{j}}\left/ \sum\limits_{i=0}^{n} {\beta_{i}\over t - t_{i}}\right., $$

(6)

to approximate the derivative and integral of a real smooth function f sampled at n + 1 equispaced nodes which will be briefly reviewed here: Differentiating the LBRI (6) and evaluating it at the node t_i, i = 0,1,…, n, leads to the barycentric rational finite differences (RFD) formula to approximate $f^{\prime }(t_{i})$ [29, 31] as

$$ f^{\prime}(t_{i})\approx r^{\prime}_{n}(t_{i})=\frac{1}{h}\sum\limits_{j=0}^{n} d_{i,j} f_{j},\quad i=0,1,\ldots,n, $$

(7)

with

$$ d_{i,j}=\left\{\begin{array}{cl} \frac{\beta_{j}}{\beta_{i}}\frac{1}{i-j} , & j\ne i,\\ - \sum\limits_{l=0 \atop l\ne i}^{n} d_{i,l} , & j = i. \end{array} \right. $$

(8)

The convergence rate of the RFD formula (7) is given by the following theorem.

Theorem 1

[29, 31] Suppose n and d, d ≤ n, are positive integers, t₀, t₁, …, t_n are equispaced nodes in the interval [a, b] and f ∈ C^d+ 2[a, b]. Then the absolute error of the approximation formula (7) with weights (8) goes to zero as $\mathcal {O}(h^{d})$.

Another application of the LBRI is to approximate the definite integral

$$ {\int}_{t_{0}}^{t_{n}} f(t) dt, $$

for a real integrable function f in the interval $[t_{0},t_{n}]$ and sampled at the distinct ordered nodes t₀, t₁, …, t_n, through a quadrature rule. Integrating the LBRI (6) leads to the direct linear rational quadrature (DRQ) [29, 30] as

$$ {\int}_{t_{0}}^{t_{n}} f(t) dt\approx h\sum\limits_{j=0}^{n} w_{j}f_{j}, $$

(9)

with

$$ w_{j} = h^{-1}{\int}_{t_{0}}^{t_{n}}\ell_{j}(t) dt. $$

The weights w_j can be evaluated in machine precision by means of an accurate quadrature rule such as Gauss or Clenshaw–Curtis which are provided in the Chebfun system [7, 34, 35]. The convergence rate of DRQ rule (9), for d ≤ n/2 − 1 and $f\in C^{d+3}[t_{0},t_{n}]$, is $\mathcal {O}(h^{d+2})$ [30].

3 Description of the LBRI-based methods

In this section, considering a uniform grid

$$ t_{0}<t_{1}<\cdots<t_{N}=T, $$

for the given interval [t₀, T] with the constant stepsize $h=t_{j+1}-t_{j}$, j = 0,1,…, N − 1, we are interested in developing methods based on the LBRI (6) for the numerical solution of (1). In each step of the proposed methods, say the step number m ≤ N, we require a quadrature rule to approximate a definite integral on the interval $[t_{0},t_{m}]$. In order to avoid computing new quadrature weights for every step, a composite version of (9), introduced in [10], should be considered in which the quadrature weights are scale and translation invariant. To define the composite barycentric rational quadrature (CBRQ) rule, let d and n be positive integers with d ≤ n ≤ m/2 and set p := ⌊m/n⌋− 1. Then, the CBRQ rule can be written as

$$ {\int}_{t_{0}}^{t_{m}} f(s) ds \approx h \sum\limits_{j=0}^{p-1} \sum\limits_{k=0}^{n} w_{k}^{(n)} f(t_{jn+k}) + h \sum\limits_{k=0}^{m-pn} w_{k}^{(m-pn)} f(t_{pn+k}), $$

(10)

where

$$ w_{k}^{(m)} = h^{-1}{\int}_{t_{0}}^{t_{m}} \frac{\frac{\beta_{k}}{s-t_{k}}}{ {\sum}_{j=0}^{m} \frac{\beta_{j}}{s-t_{j}}} ds, \quad m=n,n+1,\ldots,2n-1. $$

(11)

Notice that in the case of n ≤ m < 2n, we just have the last term of (10) which is the global quadrature rule, i.e., DRQ rule (9) with m + 1 points.

The convergence order of the rule (10) is given in the following theorem.

Theorem 2

[10] Suppose n, d and m, d ≤ n ≤ m/2, are positive integers, $f\in C^{d+2}[t_{0},T]$. Then the absolute error in the approximation of the integral of f with (10) goes to zero as $\mathcal {O}(h^{d+1})$.

Remark 1

According to Thm. 2 in [20], in the case of odd n − d, the bound on the interpolation error involves an additional factor nh, so that the orders of the related RFD formula and quadrature rule are one unit larger than stated in Theorems 1 and 2.

In [26], it has been shown that the stability regions of the direct quadrature method based on CBRQ rule (10), called CBRQM, are bounded. Here, we are going to introduce new methods in this class with unbounded stability regions for various choices of (n, d): Differentiating (1), cf. [36], yields Volterra integro-differential equations of the second kind

$$ y^{\prime}(t)=g^{\prime}(t)+K(t,t,y(t))+{\int}_{t_{0}}^{t} \frac{\partial K}{\partial t}(t,s,y(s)) ds, $$

(12)

with initial condition $y(t_{0})=g(t_{0})$. We start approximating the left-hand side of (12) at t_m by an application of the RFD formula. At time t_m, only values of y at t_k for k ≤ m are known, so left one-sided differences should be used as follows

$$ \sum\limits_{j=0}^{n} d_{n,j} y_{m-n+j} = h\left( K(t_{m},t_{m},y_{m})+F^{\prime}_{m}(t_{m})\right), \quad m=n,n+1,\ldots,N, $$

(13)

where y_m denotes an approximation for the exact solution y of (1) at t_m and the function F_m(t) is given by

$$ F_{m}(t)=g(t)+{\int}_{t_{0}}^{t_{m}}K(t,s,y(s)) ds. $$

In order to avoid calculating the derivative of the functions in (1), we approximate $F^{\prime }_{m}(t_{m})$, in (13), numerically. There are two options: One is to use the left one-sided RFD formula which leads to

$$ \sum\limits_{j=0}^{n} d_{n,j} y_{m-n+j} = h K(t_{m},t_{m},y_{m})+\sum\limits_{j=0}^{n} d_{n,j} F_{m}(t_{m-n+j}), \quad m=n,n+1,\ldots,N, $$

(14)

and the other one is to use the right one-sided RFD formula in which the weights are the same as those of the left one-sided RFD formula, though taken from right to left and reversed sign, i.e.,

$$ \sum\limits_{j=0}^{n} d_{n,j} y_{m-n+j} = h K(t_{m},t_{m},y_{m})-\sum\limits_{j=0}^{n} d_{n,j} F_{m}(t_{m+n-j}), \quad m=n,n+1,\ldots,N. $$

(15)

Now, to have fully discretized methods, it is required to use a quadrature rule finding an approximation to F_m(t), denoted by Q_m(t;h), in equations (14) and (15). We use the CBRQ (10) with the weights given by (11) as

$$ \begin{array}{@{}rcl@{}} Q_{m}(t;h):=g(t)&+&h \sum\limits_{j=0}^{p-1} \sum\limits_{k=0}^{n} w_{k}^{(n)} K(t,t_{jn+k},y_{jn+k})\\ &+& h \sum\limits_{k=0}^{m-pn} w_{k}^{(m-pn)} K(t,t_{pn+k},y_{pn+k}), \end{array} $$

(16)

which gives the methods fully based on the LBRI with Floater–Hormann weights inheriting all the advantages of this family of interpolation. Therefore, two versions of the method take the form

$$ \sum\limits_{j=0}^{n} d_{n,j} y_{m-n+j} = h K(t_{m},t_{m},y_{m})+\sum\limits_{j=0}^{n} d_{n,j} Q_{m}(t_{m-n+j};h), \quad m = n,n+1,\ldots,N, $$

(17)

which uses the left one-sided RFD formulae to approximate both of $y^{\prime }(t_{m})$ and $F^{\prime }_{m}(t_{m})$ and will be referred to as LBRILLM, and

$$ \sum\limits_{j=0}^{n} d_{n,j} y_{m-n+j} = h K(t_{m},t_{m},y_{m})-\sum\limits_{j=0}^{n} d_{n,j} Q_{m}(t_{m+n-j};h), \quad m = n,n+1,\ldots,N. $$

(18)

which uses the left one-sided RFD formula for $y^{\prime }(t_{m})$ and right one-sided RFD formula for $F^{\prime }_{m}(t_{m})$ and will be referred to as LBRILRM.

The nature of the LBRILLM (17) and LBRILRM (18) is multistep, hence they require a starting procedure of adequate accuracy. Indeed, the values y₁, y₂, …, y_n− 1 should be known to compute y_n, y_n+ 1, …, y_N by the LBRILLM and LBRILRM. In what follows, we design a starting procedure which is again based on the LBRI (6). Evaluating (12) at the mesh point t_m, m = 1,2,…, n − 1, and using the RFD formula (7) to approximate the values $y^{\prime }(t_{m})$ and $F^{\prime }_{m}(t_{m})$, leads to

$$ \sum\limits_{j=0}^{n} d_{m,j} y_{j} = h K(t_{m},t_{m},y_{m})+\sum\limits_{j=0}^{n} d_{m,j} {Q_{m}^{S}}(t_{j};h), \quad m=1,2,\ldots,n-1, $$

(19)

wherein ${Q_{m}^{S}}(t_{j};h)$ is an approximation to $F_{m}(t_{j})$ given by

$$ {Q_{m}^{S}}(t_{j};h):=g(t_{j})+h \sum\limits_{k=0}^{n} w_{k}^{(m)} K(t_{j},t_{k},y_{k}),\quad j=1,2,\ldots,n-1, $$

(20)

with

$$ w_{k}^{(m)} = h^{-1}{\int}_{t_{0}}^{t_{m}} \frac{\frac{\beta_{k}}{s-t_{k}}}{ {\sum}_{j=0}^{n} \frac{\beta_{j}}{s-t_{j}}} ds, \quad k=0,1,\ldots,n-1. $$

(21)

Notice that in addition to the unknown values y₁, y₂, …, y_n− 1, another unknown value y_n is included in the system of equations (19) while there are only n − 1 equations in this system. So, the upper bound for m in equations (19), (20), and (21) must be increased to n. In this way, the value y_n is computed by the starting procedure and so the LBRILLM (17) and LBRILRM (18) should be begun from m = n + 1 instead of m = n.

4 Convergence analysis

In this section, we analyze the convergence of the LBRILLM (17) and LBRILRM (18) and obtain their order of convergence in terms of the parameters of the method. Since the convergence rate of the starting procedure affects directly that of the main method, we shall first investigate the order of convergence of the starting procedure. In the following theorem, we obtain the convergence rate of the starting procedure (19) in terms of the parameter d.

Theorem 3

Assume that $g\in C^{d+2}[t_{0},T]$ and $K\in C^{d+2}(S\times \mathbb {R}^{D})$, and let $y_{1},y_{2},\ldots ,y_{n}$ be the approximate values for the exact solution (1) at the points $t_{1},t_{2},\ldots ,t_{n}$, obtained by the starting procedure (19) with d ≤ n. Then the norm of the starting error vector $\mathbf {e}_{n}=(e_{1},e_{2},\ldots ,e_{n})^{T}$ with e_i = y(t_i) − y_i, i = 1,2,…, n, tends to zeros as $\mathcal {O}(h^{d+\delta })$ with δ = 1 for even n − d and δ = 2 for odd n − d.

Proof

Substituting the exact values for y in the starting procedure (19), and including their consistency error R_m(h), we get

$$ \sum\limits_{j=0}^{n} d_{m,j} y(t_{j}) = h K(t_{m},t_{m},y(t_{m}))+\sum\limits_{j=0}^{n} d_{m,j} \widetilde{Q}_{m}^{S}(t_{j};h)+R_{m}(h), \quad m = 1,2,\ldots,n, $$

(22)

where

$$ \widetilde{Q}_{m}^{S}(t_{j};h):=g(t_{j})+h \sum\limits_{k=0}^{n} w_{k}^{(m)} K(t_{j},t_{k},y(t_{k})),\quad j=1,2,\ldots,n. $$

Subtracting (12), in which t is substituted by t_m, from (22), for m = 1,2,…, n, and adding the terms $\pm \frac {1}{h}{\sum }_{j=0}^{n} d_{m,j}F_{m}(t_{j})$ gives

$$ \begin{array}{@{}rcl@{}} \frac{1}{h} R_{m}(h)&=&\left( \frac{1}{h} \sum\limits_{j=0}^{n} d_{m,j} y(t_{j})-y^{\prime}(t_{m})\right)+\left( F_{m}^{\prime}(t_{m})-\frac{1}{h}\sum\limits_{j=0}^{n} d_{m,j}F_{m}(t_{j})\right)\\ &&+\frac{1}{h}\sum\limits_{j=0}^{n} d_{m,j}\left( F_{m}(t_{j})-\widetilde{Q}_{m}^{S}(t_{j};h)\right). \end{array} $$

Now, by using Theorems 1 and 2 together with Remark 1, we find that $R_{m}(h)=O(h^{d+\delta })$, for m = 1,2,…, n, with δ = 1 for even n − d and δ = 2 for odd n − d.

Subtracting (19) from (22) and using the mean-value theorem, we find that, for m = 1,2,…, n,

$$ \begin{array}{@{}rcl@{}} \sum\limits_{j=1}^{n} d_{m,j} e_{j} \!& = &\! h\left( K(t_{m},t_{m},y(t_{m}))-K(t_{m},t_{m},y_{m})\right)\\ &&+\sum\limits_{j=0}^{n} d_{m,j} \left( \widetilde{Q}_{m}^{S}(t_{j};h)-{Q_{m}^{S}}(t_{j};h)\right)+R_{m}(h)\\ &=&h \widehat{\frac{\partial K}{\partial y}}(t_{m},t_{m},\xi_{m})e_{m}+h\sum\limits_{k=1}^{n}\sum\limits_{j=0}^{n}d_{m,j}w_{k}^{(m)} \widehat{\frac{\partial K}{\partial y}}(t_{j},t_{k},\zeta_{k})e_{k}+R_{m}(h),\\ \end{array} $$

(23)

where the hat indicates that each row of ∂K/∂y is evaluated at a different mean value ξ_m, each lying in the internal part of the line segment joining y(t_m) and y_m, and the same case for ζ_k. Equation (23) can be written in the matrix form

$$ (\mathcal{D}_{n}-h(\mathcal{W}_{n}+\mathcal{\overline{W}}_{n}))\mathbf{e}_{n}=\mathbf{R}_{n}(h), $$

in which $\mathbf {R}_{n}(h):=[R_{1}(h),R_{2}(h),\ldots ,R_{n}(h)]^{T}$, the matrix $\mathcal {W}_{n}$ is a diagonal matrix with $\widehat {\frac {\partial K}{\partial y}}(t_{m},t_{m},\xi _{m})$, m = 1,2,…, n, on the diagonal and the matrices $\mathcal {D}_{n}$ and $\mathcal {\overline {W}}_{n}$ are defined by d_{m, k} and ${\sum }_{j=0}^{n}d_{m,j}w_{k}^{(m)}\widehat {\frac {\partial K}{\partial y}}(t_{j},t_{k},\zeta _{k})$ on their (m, k) elements, respectively. Because of the differentiability hypothesis on the function K, $\widehat {\frac {\partial K}{\partial y}}$ has a maximum absolute value and also the weighs d_{m, j} and $w_{k}^{(m)}$ since in the starting procedure, n is fixed and only the stepsize h is variable. This means that the norm of the matrices $\mathcal {W}_{n}$ and $\mathcal {\overline {W}}_{n}$ are bounded so that $h\|\mathcal {W}_{n}+\mathcal {\overline {W}}_{n}\|_{\infty }$ may be made as small as necessary by decreasing h. Therefore, with small enough stepsize h and nonsingularity of the matrix $\mathcal {D}_{n}$ [30], there exists a positive constant $\mathcal {C}$ such that

$$ \begin{array}{@{}rcl@{}} \|\mathbf{e}_{n}\|_{\infty} &\leq&\left\|(\mathcal{D}_{n}-h(\mathcal{W}_{n}+\mathcal{\overline{W}}_{n}))^{-1}\right\|_{\infty}\|\mathbf{R}_{n}(h)\|\\ &\leq&\frac1{\|\mathcal{D}_{n}\|_{\infty}-h\|\mathcal{W}_{n}+\mathcal{\overline{W}}_{n}\|_{\infty}}\|\mathbf{R}_{n}(h)\|_{\infty}\\ &\leq&\mathcal{C}\|\mathbf{R}_{n}(h)\|_{\infty}, \end{array} $$

which implies $\|\mathbf {e}_{n}\|_{\infty }=\mathcal {O}(h^{d+\delta })$. □

In a similar way to convergence theory of Volterra linear multistep (VLM) methods for the numerical solution of VIEs (1), we first introduce the polynomial ρ defined by

$$ \rho(w) := d_{n,n}w^{n}+d_{n,n-1}w^{n-1}+\cdots+d_{n,0}, $$

and note that for every $z\in \mathbb {C}$, the coefficients d_{n, j}, j = 0,1,…, n, satisfy

$$ \sum\limits_{j=0}^{n}d_{n,j}\exp(jz)=z\exp(nz)+O(z^{d+\delta}), $$

which gives ρ(1) = 0 and $\rho ^{\prime }(1)=1$.

Zero-stability is essential for multistep methods, such as the LBRILLM (17) and LBRILRM (18), to be convergent, and it requires that the polynomial ρ satisfies the root condition, i.e., all its zeros lie in or on the closed unit circle |w| = 1 with only simple zeros on the boundary. The simple and elegant Bistritz stability criterion [12] can be used to determine how many zeros of $\rho (w)\left /(1-w)\right .$ lie strictly inside the unit disk. This is discussed in [2] for various pairs of (n, d) and found that the polynomial ρ satisfies the root condition for every choice of n ≥ d with n ≤ 20, d ≤ 6, except for (n, d) = (7,6), (8,6), (11,6), and (12,6).

We are now in a position to state the convergence theorem of the LBRILLM (17) and LBRILRM (18) which can be deduced by using Theorem 3.2.6(b) in [16] as a general convergence theorem for VLM methods. This theorem establishes an upper bound for the global error e_m, m = n + 1, n + 2,…, N, defined by

$$ e_{m}:=y(t_{m})-y_{m},\quad m=n+1,n+2,\ldots,N. $$

Theorem 4

Assume that g and K be continuous on [t₀, T] and $S\times \mathbb {R}^{D}$, respectively, and let the functions K and ∂K/∂t satisfy a Lipschitz condition with respect to their third argument. Assume also that n and d be such that the LBRILLM (17) (or the LBRILRM (18)) is zero-stable. Then there exists a constant C independent of the stepsize h such that, for all sufficiently small h,

$$ \|e_{m}\|\leq Ch^{-1}\left( h\|\mathbf{e}_{n}\|+\bigl\|\mathcal{L}[y(t_{m});h]\bigr\|\right),\quad m=n+1,n+2,\ldots,N, $$

wherein

$$ \mathcal{L}[y(t_{m});h]:=\sum\limits_{j=0}^{n} d_{n,j} y(t_{m-n+j}) - h K(t_{m},t_{m},y(t_{m}))-\sum\limits_{j=0}^{n} d_{n,j} \widetilde{Q}_{m}(t_{m-n+j};h), $$

in the case of the LBRILLM and

$$ \mathcal{L}[y(t_{m});h]:=\sum\limits_{j=0}^{n} d_{n,j} y(t_{m-n+j}) - h K(t_{m},t_{m},y(t_{m}))+\sum\limits_{j=0}^{n} d_{n,j} \widetilde{Q}_{m}(t_{m+n-j};h), $$

in the case of the LBRILRM, with

$$ \begin{array}{@{}rcl@{}} \widetilde{Q}_{m}(t;h):=g(t)&+&h \sum\limits_{j=0}^{p-1} \sum\limits_{k=0}^{n} w_{k}^{(n)} K(t,t_{jn+k},y(t_{jn+k}))\\ & +& h \sum\limits_{k=0}^{m-pn} w_{k}^{(m-pn)} K(t,t_{pn+k},y(t_{pn+k})). \end{array} $$

It should be noted that ${\mathscr{L}}[y(t_{m});h]$, introduced in Theorem 4, may be considered as the local truncation error of the LBRILLM (17) or LBRILLM (18). For g ∈ C^d+ 2[t₀, T] and $K\in C^{d+2}S\times \mathbb {R}^{D}$, we have

$$ \mathcal{L}[y(t_{m});h]=\mathcal{O}(h^{d+\delta}), $$

(24)

with δ introduced in Theorem 3, which can be proved by adapting the analysis employed for the consistency error of the starting procedure R_m(h), m = 1,2,…, n, in the proof of Theorem 3.

On the basis of Theorem 4, we have the following corollary regarding the order of convergence of the methods (17) and (18) which can be deduced from Corollary 3.2.2 stated in [16].

Corollary 1

Let the conditions of Theorem 4 together with additional conditions $g\in C^{d+2}[t_{0},T]$ and $K\in C^{d+2}(S\times \mathbb {R}^{D})$ be satisfied. Then the order of convergence of the methods (17) and (18) is $\min \limits \{d_{1},d_{2}\}$ where d₁ and d₂ are the largest positive integers such that $R_{m}(h)=O(h^{d_{1}})$, m = 1,2,…, n, and ${\mathscr{L}}[y(t_{m});h]=O(h^{d_{2}+1})$.

By Theorem 3 and (24), we find that the integers d₁ and d₂ appearing in Corollary 1 are respectively d + δ and d + δ − 1. Therefore, the order of convergence of the methods (17) and (18) is $\min \limits \{d_{1},d_{2}\}=d+\delta -1$ (see Table 1).

Table 1 Angles α of A(α)-stability for BDFs, LBRILLM (17), and LBRILRM (18)

5 Stability analysis

As is known, the convergence property for a numerical method tells us only what happens in the limit as $h\rightarrow 0$ and does not give us any guarantee that the numerical solution will be acceptable for a sufficiently small fixed non-zero stepsize h. Actually, the numerical stability analysis is absolutely necessary in assessing the fitness of the used method in the numerical solution. Here, we study the linear stability of the methods (17) and (18) with respect to both the basic and convolution test equations (2) and (3). These test equations have an exponentially decaying solution for Re(λ) < 0 and for $\lambda ,\mu \in \mathbb {R}^{-}$, respectively [6, 15, 32]. The study of linear stability of the numerical methods provides a general framework for understanding the condition under which the numerical solution exhibits the same behavior.

Applying, the LBRILLM (17) and LBRILRM (18) to the basic test (2), we get

$$ \sum\limits_{j=0}^{n} d_{n,j} y_{m-n+j} = z y_{m}+\left( \!1 + z\sum\limits_{j=0}^{p-1} \sum\limits_{k=0}^{n} w_{k}^{(n)} y_{jn+k} + z \sum\limits_{k=0}^{m-pn}\! w_{k}^{(m-pn)} y_{pn+k}\!\right)\!\sum\limits_{j=0}^{n} d_{n,j}, $$

and

$$ \sum\limits_{j=0}^{n} d_{n,j} y_{m-n+j} = z y_{m}-\left( \!1 + z\sum\limits_{j=0}^{p-1} \sum\limits_{k=0}^{n} w_{k}^{(n)} y_{jn+k} + z \sum\limits_{k=0}^{m-pn}\! w_{k}^{(m-pn)} y_{pn+k}\!\right)\sum\limits_{j=0}^{n} d_{n,j}, $$

with z := hλ, respectively, which by considering ${\sum }_{j=0}^{n} d_{n,j}=\rho (1)=0$, both of them are reduced to

$$ \sum\limits_{j=0}^{n} d_{n,j} y_{m-n+j} = z y_{m}. $$

So, the linear stability properties of the both methods (17) and (18) with respect to the basic test (2) are determined by the “stability polynomial” Φ(w, z) defined by

$$ {\Phi}(w,z):=\rho(w)-z w^{n}, $$

which is the same as that of the introduced method based on the LBRI in [5] for the numerical solution of ordinary differential equations. In [5], it has been shown that the method is A(α)-stable with wider angles α in comparison with BDFs of the same order. Indeed, the LBRILLM (17) and LBRILRM (18) are solutions for the open problem proposed in [26]. In Table 1, the values of α of A(α)-stability for various pairs of (n, d) are presented and compared with those for BDFs which shows that the stability properties of the methods (17) and (18) are better that those of BDFs for VIEs introduced in [36].

Now, we investigate the stability properties of the methods (17) and (18) with respect to the convolution test (3). To this end, in a way similar to what is done for investigating the stability properties of the proposed methods in [26] and [4], let us introduce y^[m− 1], y^[m] and Y^[m− 1], for any positive integer m, as

$$ \begin{array}{@{}rcl@{}} y^{[m-1]}&:=&\left[y_{mn} y_{mn+1} {\cdots} y_{(m+1)n-1} \right]^{T},\\ y^{[m]}&:=&\left[y_{(m+1)n} y_{(m+1)n+1} {\cdots} y_{(m+2)n-1} \right]^{T},\\ Y^{[m-1]}&:=&\sum\limits_{\ell=0}^{m-1}\sum\limits_{k=0}^{n}(1-\delta_{\ell n+k,mn})w_{k}^{(n)}y_{\ell n+k}, \end{array} $$

where δ_jk denotes the Kronecker delta and also introduce the n × n matrices W₀, W₁, V, and $\overline {V}$ with

$$ \begin{array}{@{}rcl@{}} W_{0}&:=&\left[ \begin{array}{cccc} w_{n}^{(n)} & 0 & {\cdots} & 0 \\ w_{n}^{(n+1)} & w_{n+1}^{(n+1)} & {\cdots} & 0 \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ w_{n}^{(2n-1)} & w_{n+1}^{(2n-1)} & {\cdots} & w_{2n-1}^{(2n-1)} \end{array} \right], W_{1}:=\left[ \begin{array}{ccccc} w_{0}^{(n)} & w_{1}^{(n)} & {\cdots} & w_{n-1}^{(n)} \\ w_{0}^{(n+1)} & w_{1}^{(n+1)} & {\cdots} & w_{n-1}^{(n+1)} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ w_{0}^{(2n-1)} & w_{1}^{(2n-1)} & {\cdots} & w_{n-1}^{(2n-1)} \end{array} \right]\\ &&+w_{n}^{(n)}\mathrm{e}\mathrm{e}_{1}^{T},\\ V&:=&\left[ \begin{array}{cccc} d_{n,n} & 0 & {\cdots} & 0 \\ d_{n,n-1} & d_{n,n} & {\cdots} & 0 \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ d_{n,1} & d_{n,2} & {\cdots} & d_{n,n} \end{array} \right], \overline{V}:=\left[ \begin{array}{cccc} d_{n,0} & d_{n,1} & {\cdots} & d_{n,n-1} \\ 0 & d_{n,0} & {\cdots} & d_{n,n-2} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ 0 & 0 & {\cdots} & d_{n,0} \end{array} \right], \end{array} $$

where the n dimensional vectors e and e₁ are the all-ones vector and the first standard unit vector, respectively. Now, by using the relations ${\sum }_{j=0}^{n} d_{n,j}=\rho (1)=0$ and ${\sum }_{j=0}^{n} jd_{n,j}=\rho ^{\prime }(1)=1$, it is easy to show that both methods (17) and (18) applied to the test (3) lead to

$$ \begin{array}{@{}rcl@{}} \left\{ \begin{array}{l} Vy^{[m]}+\overline{V}y^{[m-1]}=(\xi I_{n}+\eta W_{0})y^{[m]}+ \eta W_{1} y^{[m-1]}+\eta Y^{[m-1]}\mathrm{e}, \\ Y^{[m]}=Y^{[m-1]}+\overline{w} y^{[m-1]}, \end{array} \right. \end{array} $$

(25)

where ξ := λh, η := μh², $\overline {w}$ is the first row of the matrix W₁ and I_n stands for the identity matrix of order n. Equation (25) can be written more compactly as

$$ \left[ \begin{array}{c} y^{[m]} \\ Y^{[m]} \end{array} \right] = M(\xi,\eta)\left[ \begin{array}{c} y^{[m-1]} \\ Y^{[m-1]} \end{array} \right], m\geq1, $$

with the “stability matrix” M(ξ, η) given by

$$ M(\xi,\eta) = \left[ \begin{array}{c@{}c} (V-\xi I_{n}-\eta W_{0})^{-1}(\eta W_{1}-\overline{V}) & \eta (V-\xi I_{n}-\eta W_{0})^{-1}\mathrm{e} \\ \overline{w} & 1 \end{array} \right], $$

(26)

which is exactly the same as that of the method based on the LBRI introduced in [4] for the numerical solution of Volterra integro-differential equations

$$ \left\{\begin{array}{ll} y^{\prime}(t)=f\left( t,y(t),\displaystyle{\int}_{t_{0}}^{t} K(t,s,y(s)) ds\right),& t\in[t_{0},T],\\ y(t_{0})=y_{0}, & \end{array} \right. $$

when its stability properties are analyzed with respect to the test equation

$$ y^{\prime}(t)=\lambda y(t)+{\mu{\int}_{0}^{t}} y(s) ds, \quad t\geq0, \quad y(0)=1. $$

(27)

The stability properties of both the LBRILLM (17) and LBRILRM (18) with respect to the convolution test (3) are governed by the “stability polynomial” Φ(w, ξ, η) defined by

$$ \frac{\Phi(w,\xi,\eta)}{{\prod}_{k=0}^{n-1}\left( d_{n,n}-\xi-\eta w_{n+k}^{(n+k)}\right)}=\det(wI_{n+1}-M(\xi,\eta)). $$

(28)

So, the set of values of $(\xi ,\eta )\in \mathbb {R}^{-}\times \mathbb {R}^{-}$ for which any solution to the equation Φ(w, ξ, η) = 0 lies in the unit disk with only simple roots on the boundary is known as the stability region. By (28), we find that the roots of Φ for w are rational functions in terms of ξ and η in which degree of ξ in numerator and denominator are respectively n − 1 and n. So, for a fixed arbitrary η < 0, all the roots w of Φ tend to zero when $\xi \rightarrow -\infty$. This means that the stability regions of the methods are unbounded. Although we did not find V₀-stable methods within this class of methods, the proposed methods (17) and (18) are V₀(α)-stable with a large value for α. We should recall that a method is said to be V₀– and/or V₀(α)-stable, for α ∈ [0, π/2), if its stability region with respect to (3) contains the all pairs of (ξ, η) with ξ ≤ 0 and η ≤ 0 and/or the set $\{(\xi ,\eta ): 0\leq \arctan (\eta /\xi )< \alpha , \xi <0\}$ [3, 27]. In Table 2, the values of α of V₀(α)-stability for various pairs of (n, d) are presented. The boundary locus technique has been used to obtain the value of α which is described in [28]. Moreover, we have plotted the stability regions of the methods in the (ξ, η)-plane and domain [− 50,0] × [− 50,0], for various zero-stable choices of n and d in Fig. 1.

Table 2 Angles α of V₀(α)-stability for LBRILLM (17) and LBRILRM (18)

Fig. 1

Stability regions of the LBRILLM (17) and LBRILRM (18) with respect to the convolution test (3) for various choices of n and d

Although the stability analysis shows that the stability properties of both methods (17) and (18) are the same with almost identical accuracy (see Tables 3, 4, and 5), the advantage of the method (17) is that method (18) requires the kernel function K to be defined in a larger interval [t₀, T + nh], instead of [t₀, T], for its first variable, while it is not the case for the LBRILLM (17).

Table 3 Numerical results of the methods for example (30)

Table 4 Numerical results of the methods for example (31)

6 Numerical experiments

In this section we present the results of numerical experiments with various values of n and d for which our methods are zero-stable, to validate the stability results of both methods (17) and (18) and show their capability and efficiency in solving stiff VIEs. For comparison, we also add the results from the CBRQM introduced in [10].

Efficiency and accuracy of the proposed methods are shown by measuring

$$ \kappa_{S}(h):=-\log_{10}\left( \max_{1\leq m\leq n}\|y_{m}-y(t_{m})\|_{\infty}\right), $$

and

$$ \kappa_{N}(h):=-\log_{10}\left( \|y_{N}-y(t_{N})\|_{\infty}\right), $$

yielding the number of correct decimal digits at the starting values and at the endpoint t_N, respectively. To verify theoretical results on the order of accuracy, we compute an experimental estimate of the order of accuracy for the starting procedure by the formula $O_{S}:=\log _{2}(10)\cdot \left (\kappa _{S}(h/2)-\kappa _{S}(h)\right )$, and for the methods (17) and (18), denoted by O_N and computed by the similar formula for O_S. In our numerical experiments, we use superscript LL and LR for κ_N and O_N to refer to the results from LBRILLM and LBRILRM, respectively.

As a first example, we consider the VIE

$$ y(t)=g(t)-{{\int}_{0}^{t}}\left( 100 + 1500(t-s)\right)y^{3}(s) ds, $$

(29)

to illustrate the stability regions of the proposed methods in Section 3. Here, the function g is chosen such that the exact solution is $y(t)=2-\exp (-t)$. For this example, the parameters λ and μ, appearing in (3), can be approximated by λ ≈− 300 and μ ≈− 4500. We solve this example with (n, d) = (5,3) and (4,3), and two different fixed stepsizes h₁ = 0.1 and h₂ = 0.05. Considering the stability regions for the methods with (n, d) = (5,3) and (4,3), plotted in Fig. 1, $(\xi _{1},\eta _{1})=(\lambda h_{1},\mu {h_{1}^{2}})$ lies outside of the stability regions while $(\xi _{2},\eta _{2})=(\lambda h_{2},\mu {h_{2}^{2}})$ lies inside of these regions. Also, both of these points lie outside of the stability region for the CBRQM which are plotted in paper [26]. Figure 2 shows the numerical stability and instability behavior of the LBRILLM and CBRQM by a graph for the error over the whole interval, which demonstrate beautifully their agreement with the theoretical results and superiority of the LBRILLM compared with the CBRQM.

Fig. 2

Errors versus t for example (29) solved by the LBRILLM and CBRQM with the parameters (n, d) = (5,3) (left) and (4,3) (right) and the stepsizes h = 0.1 and h = 0.05

Next we study the nonlinear stiff VIE [36]

$$ y(t)=-15t+17(\exp(t)-1)+{{\int}_{0}^{t}}\left( 16(s-t)-1\right)\exp(y(s)) ds,\quad t\in[0,10], $$

(30)

with the exact solution y(t) = t. The stiffness parameters ∂K/∂y and ∂²K/∂t∂y for this example increase with t. The numerical results of the methods have been reported in Table 3 and Fig. 3. Table 3 illustrates the efficiency and capability of the methods in solving stiff VIEs together with their theoretical orders. The CBRQM fails to solve this example for all choices of (n, d) and the corresponding stepsizes h reported in Table 3. Indeed, considering the approximated values for λ and μ at T = 10 which are − 22026 and − 352423, and the stability regions of the CBRQM, for instance for (n, d) = (3,2), the stepsize h must be less than 1.01 × 10^− 4. Figure 3 shows that the CBRQM becomes unstable at t ≈ 5 whereas LBRILLM and LBRILRM are stable in the whole interval. This discussion clearly clarifies that the proposed methods outperform CBRQM in the sense of stability for solving stiff VIEs.

Fig. 3

Errors versus t for example (30) solved by the LBRILRM, LBRILLM, and CBRQM with (n, d) = (3,2) and the stepsize h = 2^− 8

We also study the system of VIEs

$$ \begin{array}{@{}rcl@{}} \left[ \begin{array}{c} y_{1}(t) \\ y_{2}(t) \end{array} \right]& = &\frac1{100}\left[ \begin{array}{c} b^{21} \\ 1 + (10 - b^{20})b \end{array} \right] \end{array} $$

(31)

$$ \begin{array}{@{}rcl@{}} &&+{{\int}_{0}^{t}}\left[ \begin{array}{c@{}c} a^{21} & 0 \\ (1 - a^{20})a & a/1000 \end{array} \right]\left[ \begin{array}{c} 3y_{1}(s)(1 - y_{1}(s) - y_{2}(s)) \\ 1 - y_{1}(s) - y_{2}(s) \end{array} \right] ds, \end{array} $$

(32)

with t ∈ [0,50], $a=\exp ((s-t)/20)$, and $b=\exp (-t/20)$, which models endemic infectious disease [24, 25]. Reference solution at the endpoint of integration T = 50 is given by [25]

$$ \begin{array}{@{}rcl@{}} \left[ \begin{array}{c} y_{1}(50) \\ y_{2}(50) \end{array} \right]=\left[ \begin{array}{c} 0.031716689391939 \\ 0.62784627209779 \end{array} \right]. \end{array} $$

The numerical results of the LBRILLM and LBRILRM for various choices of n and d have been reported in Table 4. This table shows that, as it is expected, the order of convergence does appear to be d + 1 in the case of odd n − d, or d, for even n − d.

Finally, we study the nonlinear VIE

$$ y(t)=1+{{\int}_{0}^{t}}(t-s)^{3}(4-t+s)\exp(-t+s)\frac{y^{4}(s)}{1+2y^{2}(s)+2y^{4}(s)} ds,\quad t\in[0,10], $$

(33)

arising in the analysis of neural networks with post inhibitory rebound [17, 22]. Reference solution at the endpoint of integration T = 10 is given by y(10) = 1.25995582337233 [17]. The numerical results of the LBRILLM and LBRILRM with (n, d) equal to (6,3), (5,4), and (13,6) have been reported in Table 5. As to be expected, the orders observed are four, five, and seven respectively.

Table 5 Numerical results of the methods for example (33)

7 Conclusion

The stability region of the LBRI-based method, introduced in [10], for solving VIEs of the second kind is bounded, which make it unsuitable for solving stiff problems. This was a motivation for this work to derive methods in this class with unbounded stability regions. We proved that the stability regions of the proposed methods are unbounded and obtained their order of convergence in terms of the parameters of the methods. The effectiveness of our methods was confirmed by some numerical experiments.