PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 67(81) (2000), 85–91

NUMERICAL BOUNDS FOR INVERSES OF LINEAR OPERATORS

H.-J. Dobner

Communicated by Gradimir Milovanović

Abstract. An effective way of computing bounds for inverses of linear operators is discussed. It involves computing very fast a bound for the inverse of linear Volterra and Fredholm integral operators. This approach covers a wide class of ordinary and partial initial and boundary value problems. It is demonstrated that this concept is feasible in the framework of computer algebra systems.

1. Introduction

Considered are equations of the type

L(x) = y, (1.1)

where L is a linear operator acting between two normed spaces X, Y. In the application of numerical methods for solving such problems some knowledge of the properties of the operator involved is of great importance, so existence and boundedness of L^{−1} guarantees that (1.1) is solvable and well posed. The knowledge of bounds for linear operator is also a fundamental concern when dealing with inclusion methods (cf. [2,3,5]). Additionally if an approximate solution x̃ ∈ X is available then an error estimation is given by

∥x − x̃∥ ≤ ∥L^{−1}∥ ∥L(x̃) − y∥. (1.2)

The application of (1.2) requires both a bound on the defect d = L(x̃)−y and on the inverse L^{−1}. While the computation of the defect is rather simple, the computation of a bound on ∥L^{−1}∥ raises some difficult theoretical questions. This is therefore often ignored in practice, because in traditional numerics main emphasis is put on theoretical convergence investigations rather than on practical accuracy questions. But ∥L^{−1}∥ measures the effect of errors in the solution, since a small value of ∥d∥ doesn’t mean automatically that x̃ is close to x.

1991 Mathematics Subject Classification. Primary 45L10, 65G10, 65L05, 65M15.

Key words and phrases. Numerical bounds, inverse operator, computer algebra system.

In this article we focus an extremely fast method for estimating ∥L^{−1}∥ with a least possible amount of work; consequently the accuracy for estimating ∥L^{−1}∥ is low, but if the defect is of small magnitude, then the overestimation of ∥L^{−1}∥ is of small influence. We describe our approach for linear second kind Fredholm integral operators

L_{F} (x) = (I + K_{F})(x) = x(s) + ∫_{0}^{1} k(s, t)x(t)dt , 0 ≤ s ≤ 1 , (1.3)

and linear second kind Volterra integral operators

L_{V} (x) = (I + K_{V})(x) = x(s) + ∫_{0}^{s} k(s, t)x(t)dt , 0 ≤ s ≤ 1 , (1.4)

where the kernel function k is assumed to be continuous and we restrict w.l.o.g. to the unit square as domain of definition. The integral equations corresponding to (1.3) and (1.4) have the form

x(s) + ∫_{0}^{1} k(s, t)x(t)dt = y(s) , 0 ≤ s ≤ 1, (1.5)

and

x(s) + ∫_{0}^{s} k(s, t)x(t)dt = y(s) , 0 ≤ s ≤ 1. (1.6)

It is no severe restriction to deal only with these specific problems, since linear ordinary and elliptic boundary value problems are related to Fredholm integral equations and initial value problems for ordinary and hyperbolic differential equations can be rewritten as second kind Volterra equations. An extension to higher dimensional problems is also possible with only minor technical changes.

The paper is organized as follows. In section 2 it is illustrated how to determine a bound for the inverse of Fredholm integral operators. In the following section 3 we describe a method for estimating the inverse of Volterra operators. Finally we discuss aspects of realization in the framework of the algebra system MAPLE and give some examples.

2. Bounds for the inverse of Fredholm integral operators

For bounding L_{F}^{−1} we use enclosure theory. We sketch first its basic principles. By Iℝ we denote the set of real closed intervals

[a] = [\underline{a}, \overline{a}] = \{x ∈ ℝ : \underline{a} ≤ x ≤ \overline{a}\}. (2.1)

In Iℝ the arithmetic operations ∘ ∈ Ω = {+, −, ·, /} are for [a], [b] ∈ Iℝ defined as

[a] ∘ [b] = [min\{\underline{a} ∘ \underline{b}, \underline{a} ∘ \overline{b}, \overline{a} ∘ \underline{b}, \overline{a} ∘ \overline{b}\}, max\{\underline{a} ∘ \underline{b}, \underline{a} ∘ \overline{b}, \overline{a} ∘ \underline{b}, \overline{a} ∘ \overline{b}\}], (2.2)

∘ ∈ Ω, 0 ∉ [b] in the case of division.

For these operations the associative and commutative laws are valid but instead of distributivity only subdistributivity holds:

[a]([b] + [c]) ⊆ [a][b] + [a][c], [a], [b], [c] ∈ Iℝ. (2.3)

In Iℝ set theoretic relations are defined in the usual sense. Consider (C[0, 1], ∥.∥_{∞}) with the generating system φ_{i}(s) = s^{i−1}, i = 1, …, that is \overline{span(φ_{1}, φ_{2}, …)} = C[0, 1]. Here we deal especially with J_{n}:

J_{n} = {F_{N}(s) : F_{n}(s) = ∑_{i=1}^{n}[a_{i}]φ_{i}(s), [a_{i}] ∈ Iℝ, 0 ≤ s ≤ 1}. (2.4)

An element F_{n} describes the following subset of C[0, 1]:

F_{n}(s) = {f ∈ C[0, 1] : f(s) ∈ ∑_{i=1}^{n}[a_{i}]φ_{i}(s), 0 ≤ s ≤ 1},

We confine now to the case n = 1:

J_{1} = {F_{1}(s) = [a], [a] ∈ Iℝ};

so each interval [a] represents at the same time a subset of ℝ and the following subset of C[0, 1]:

[a] = \{f ∈ C[0, 1] : \underline{a} ≤ f(s) ≤ \overline{a}\}. (2.5)

Relation (2.5) is of importance, when dealing with Fredholm integral operators, here we take [k] ∈ J_{1} such that

k(s, t) ∈ [k] = [\underline{k}, \overline{k}], 0 ≤ s, t ≤ 1, (2.6)

then

I + [k] := x(s) + ∫_{0}^{1}[k]x(t)dt

describes a set of Fredholm integral operators in the sense of (2.5).

Theorem 2.1. Let k(s, t) in (1.3) be positive and L_{F} be nonsingular. If [k] = [\underline{k}, \overline{k}] ∈ J_{1} with \underline{k} > 0 and k(s, t) ∈ [k], 0 ≤ s ≤ 1 then

∥L_{F}^{−1}∥ ≤ 1 + \frac{[k]}{1 + [k]}. (2.7)

Proof: For y ∈ C[0, 1] we have for I − [K] = I − \frac{∫_{0}^{1}[k] dt}{1+∫_{0}^{1}[k] dt}

(I − [K])(I + K)(y) =

y(s) + ∫_{0}^{1} k(s, t)y(t)dt − ∫_{0}^{1} \frac{[k]y(t)}{1 + ∫_{0}^{1}[k]dt}dt − ∫_{0}^{1} ∫_{0}^{1} \frac{[k]}{1 + ∫_{0}^{1}[k]dt}k(s, t)y(t) dt ds.

Some tedious manipulations yield

(I − [K])(I + K)(y) ⊃ y(s) + [\underline{r}, \overline{r}],

where

[\underline{r}, \overline{r}] := [ ∫_{0}^{1} (\frac{k(s, t) + ∫_{0}^{1} \underline{k}dtk(s, t) − \overline{k} − ∫_{0}^{1} \overline{k}k(s, t)ds}{1 + ∫_{0}^{1} \underline{k}dt}) y(t)dt,

∫_{0}^{1} (\frac{k(s, t) + ∫_{0}^{1} \overline{k}dtk(s, t) − \underline{k} − ∫_{0}^{1} \underline{k}k(s, t)ds}{1 + ∫_{0}^{1} \overline{k}dt}) y(t)dt].

From k(s, t) ∈ [k] we derive 0 ∈ [\underline{r}, \overline{r}], hence (I − [K])(I + K)(y)) ⊃ y(s); by assumption 1 is not an eigenvalue, therefore Q ∈ [K] with

(I − Q)(I + K)(y(s)) = y(s)

exists, thus L_{F}^{−1} ∈ (I − [K]). □

Remark 2.2. If the kernel is not positive then (1.5) can be steadily reformulated as an equivalent equation with positive kernel.

3. Bounds for the inverse of Volterra integral operators

In this paragraph we treat Volterra operators which have the form (1.4). The inverse L_{V}^{−1} of L_{V} = (I + K_{V}) is given by the series

L_{V}^{−1} = ∑_{j=0}^{∞}(−K_{V}^{j}) , (3.1)

where K_{V}^{0} = I and K_{V}^{j} = K_{V} K_{V}^{j−1}, j = 1, 2, . . .. If C is a quantity satisfying |k(s, t)| ≤ C we estimate the sum in (3.1) using the triangle inequality

∥L_{V}^{−1}∥ ≤ ∑_{j=0}^{∞} ∥K_{V}^{j} ∥ ≤ ∑_{j=0}^{∞} \frac{C^{j}}{j!} = e^{C} (3.2)

and therefore a computable bound on the inverse of L is achieved. Also initial value problems

\begin{aligned}x′(s) − a(s)x(s) & = y(s), \\ x(0) & = x_{0}, \end{aligned}

in which a(s), y(s) are continuous real valued functions defined on [0, 1] are converted into equivalent Volterra equations, yielding

x(s) = x_{0} + ∫_{0}^{s} y(t)dt + ∫_{0}^{s} a(t)x(t)dt , 0 ≤ s ≤ 1, (3.3)

so that (3.2) applies.

4. Some examples

We provide here some simple results to show that the bounds obtained from (2.7) and (3.2) are of use in practice. Inequality (1.2) contains two factors

• ∥L^{−1}∥ which controls the global behaviour of the error. A knowledge of ∥L^{−1}∥ that is the condition number is important for inaccuracies from the initial data. We accept a moderate overestimation of ∥L^{−1}∥ because we can verify the results of any algorithm with almost no additional computational effort, which is a contribution to reliable numerical methods. So long as the defect is small an overestimation of the first factor in (1.2) is not critical.

• ∥L(x̃) − y∥ which gives information about the local error-behaviour. The implementation of the ideas presents no significant problems. A great

advantage of the proposed method is its simplicity and its independency from any specific numerical method which is used for computing x̃. The main objective is to determine range bounds of kernel-functions. Therefore a programming environment providing set valued facilities is mandatory. For this purpose we may use the XSCextensions (cf. [3], [4]) of PASCAL or C or we can use INTPAK (cf. [2]), a powerful MAPLEshare library package extending MAPLE’s existing interval capabilities by providing operators and utility functions for interval arithmetic. With this tool it is possible to compute even with an algebra system, guaranteed range bounds for kernels and to establish therefore reliable bounds for the corresponding operators.

Example 4.1. (Taken from Linz [5].) For L_{F} (x) = x(s) + λ∫_{0}^{1}s^{2}t^{2}x(t)dt,

λ ∈ ℝ, we have ∥L_{F}^{−1}∥ = 1 + \frac{5|λ|}{3|5 − λ|}, λ ∈ ℝ ∖ \{5\}.

Table 1 lists the computed estimation for ∥L_{F}^{−1}∥ using (2.7)

λ  estimation exact value
0.1  1.1  1.03
1  2  1.27
10  11  2.11
100  101  2.59

Table 1

Table 2 displays the bounds for λ = −1 computed by Linz, who uses a degenerate kernel approach of degree n to estimate ∥L_{F}^{−1}∥

n  estimation from [5]
10  1.49
20  1.45
40  1.43
exact value  1.417

Table 2

Compared with (2.7), which yields 2 as bound, this degenerate kernel method needs much more computational effort. Furthermore our estimates are more precise than bounds given by other authors (cf. [1], [6]). The same is true for the next example.

Example 4.2. Let L_{F} (x) = x(s) + λ∫_{0}^{1}e^{s−t}x(t) dt, λ ∈ ℝ. The norm of L_{F}^{−1}

is ∥L_{F}^{−1}∥ = 1 + (e − 1)\frac{|λ|}{|1 − λ|}.

In Table 3 we list the bounds obtained from (2.7) together with the exact values.

λ  estimation exact value
0.1  1.26  1.16
1  2.99  1.86
10  6.81  2.56
100  8.20  2.70
-10  11.15  2.91

Table 3

For λ = −10 Linz derives, with a degenerate kernel approach of degree n = 10, the bound 3.135.

In Table 4 below we display bounds for some Volterra operators.

L_{V} (x)  bound of ∥L_{V}^{−1}∥ by (3.2)

x(s) + 2∫_{0}^{s} \frac{x(t)dt}{(s − t + 2)}, 0 ≤ s ≤ 5  12.18
u′(z) = 2zu(z) + z, 0 ≤ s ≤ 1  2.72
u(0) = 1

x(s) + ∫_{0}^{s}(sin(1.2s) − st − \frac{2}{\sqrt{1.5 + s + t}})x(t)dt, 0 ≤ s ≤ 1  5.11

x(s) + ∫_{0}^{s}(2st^{2} − e^{− \frac{s}{3+t}})x(t)dt, 0 ≤ s ≤ 1  4.04

Table 4

References

[1] C.T.H. Baker, em The Numerical Treatment of Integral Equations, Clarendon Press, 1977.

[2] G.F. Corliss, INTPAK for Interval Arithmetic in Maple: Introduction and Application, J. Symb. Comput. 11 (1997).

[3] R. Klatte et al., C-XSC, Springer-Verlag, 1993.

[4] R. Klatte et al., Pascal-XSC, Springer-Verlag, 1991.

[5] P. Linz, Precise bounds for Inverses of Integral Equation Operators, Internat. J. Comput. Math. 24 (1988), 73–81.

[6] B. Noble, Error analysis of collocation methods for solving Fredholm integral equations, in: J.J.H. Miller (ed.), Topics in Numerical Analysis, Academic Press, 1977.

Mathematisches Institut II (Received 25 02 1998) Universität Karlsruhe D-76128 Karlsruhe Germany