Zeitschrift für Analysis und ihre Anwendungen

Journal for Analysis and its Applications Volume 18 (1999), No. 2, 267–286

Stability Rates for Linear Ill-Posed Problems with Compact and Non-Compact Operators

B. Hofmann and G. Fleischer

Dedicated to Prof. L. von Wolfersdorf on the occasion of his retirement

Abstract. In this paper we deal with the ‘strength’ of ill-posedness for ill-posed linear operator equations Ax = y in Hilbert spaces, where we distinguish according to M. Z. Nashed the illposedness of type I if A is not compact, but we have R(A) ≠ \overline{R(A)} for the range R(A) of A, and the ill-posedness of type II for compact operators A. From our considerations it seems to follow that the problems with non-compact operators A are not in general ‘less’ ill-posed than the problems with compact operators. We motivate this statement by comparing the approximation and stability behaviour of discrete least-squares solutions and the growth rate of Galerkin matrices in both cases. Ill-posedness measures for compact operators A as discussed by B. Hofmann and U. Tautenhahn are derived from the decay rate of the non-increasing sequence of singular values of A. Since singular values do not exist for non-compact operators A, we introduce stability rates in order to have a common measure for the compact and noncompact cases. Properties of these rates are illustrated by means of convolution equations in the compact case and by means of equations with multiplication operators in the non-compact case. Moreover, using increasing rearrangements of multiplier functions specific measures of illposedness called ill-posedness rates are considered for multiplication operators. In this context, the character of sufficient conditions providing convergence rates of Tikhonov regularization are compared for compact operators and multiplication operators.

Keywords: Linear ill-posed problems, compact and non-compact linear operators in Hilbert spaces, discrete least-squares method, stability rates, singular values, convolution and multiplication operators, Galerkin matrices, condition numbers, increasing rearrangements

AMS subject classification: Primary 65 J 20, secondary 47 B 38, 65 R 30

1. Introduction

Let A ∈ L(X, Y) be a bounded linear operator between two infinite dimensional separable Hilbert spaces X and Y with trivial null spaces N(A) = {0} and N(A^{∗}) = {0} of the operator A and its adjoint A^{∗}, i.e., A is injective and \overline{R(A)} = Y for the closure \overline{R(A)} in Y of the range R(A) of the operator A. We denote by ⟨·, ·⟩ and ∥ · ∥ inner product and norm in the Hilbert spaces, respectively. In view of the injectivity of A the inverse

Both authors: Techn. Univ. of Chemnitz, Fac. Math., D-09107 Chemnitz

ISSN 0232-2064 / $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag Berlin

operator A^{−1} : R(A) ⊂ Y → X exists. If the norm symbol ∥ · ∥ is used for operators B ∈ L(X, Y), then we mean the spectral norm ∥B∥ = sup_{x∈X\\{0\}} \frac{∥Bx∥}{∥x∥}.

According to the concept of M. Z. Nashed [15] a linear operator equation

Ax = y  (x ∈ X, y ∈ Y)  (1.1)

is called ill-posed if

R(A) ≠ \overline{R(A)},  (1.2)

i.e., if the operator A has a non-closed range. Then one has to be very careful in solving the operator equation (1.1) numerically, since as a consequence of (1.2) the inverse A^{−1} is an unbounded linear operator (cf., e.g., [5: Proposition 2.4]). Following [15] we have to distinguish two alternative situations of ill-posed linear operator equations (1.1):

Definition 1.1. We call the linear operator equation (1.1) ill-posed of type I if A is not compact, but if we have R(A) ≠ \overline{R(A)}. On the other hand, we call equation (1.1) ill-posed of type II, if the operator A is compact.

If A is a compact linear operator, then condition (1.2) is automatically satisfied. On the other hand, if (1.1) is ill-posed of type I, then the range R(A) contains a closed infinite dimensional subspace.

M. Z. Nashed wrote in [15: p. 55] that “... in Hilbert spaces, an equation involving a bounded non-compact operator with non-closed range is ‘less’ ill-posed than an equation with a compact operator with infinite dimensional range. In comparison with least-squares or generalized inverse problems for m × n matrices, one may say that for operators with non-closed range the case of a non-compact operator corresponds to the full-rank case for matrices, while the case of a (non-degenerate) compact operator is the infinite dimensional analog of the rank-deficient case for matrices.” Hence by Nashed’s opinion an equation (1.1) ill-posed of type I is in general ‘less’ ill-posed than an equation (1.1) which is ill-posed of type II. In this paper we will critically reflect this opinion by comparing the approximation and stability behaviour of discretized solutions for illposed equations of both types. For stability considerations in Section 2 we introduce stability rates characterizing the asymptotic stability behaviour of discrete least-squares solutions to equation (1.1). From that stability point of view non-compact operators A do not lead in general to ‘less’ ill-posed situations than compact operators.

On the other hand, G. Vainikko repeatedly mentioned in his papers on linear illposed problems of type I (cf., e.g., [19]) the additional difficulties arising from the noncompactness of the linear operator in the process of discretization and regularization. The reason for such additional difficulties seems to be the approximation gap between a non-compact operator A with dim(R(A)) = ∞ and approximate operators A_{N} with finite-dimensional range dim(R(A_{N})) = N. This gap is a consequence of the following well-known lemmas (cf. [12: p. 18 – 19]):

Lemma 1.2. Let the sequence of compact linear operators B_{n} ∈ L(X, Y) be norm convergent to a linear operator B ∈ L(X, Y), that is, ∥B_{n} − B∥ → 0 as n → ∞. Then B is compact.

Lemma 1.3 Let B ∈ L(X, Y) be a bounded linear operator with finite-dimensional range R(B). Then B is compact.

We are going to formulate a corollary of both lemmas which characterizes the approximation gap immediately. Throughout this paper let denote by {w_{n}}_{n=1}^{∞} a complete orthonormal system in the Hilbert space X. Moreover, let X_{N} = span (w_{1}, ..., w_{N}) designate the N-dimensional subspace of X spanned over the first N elements of the orthonormal system under consideration. In this context, our investigations partially depend on the chosen orthonormal system. However, such an approach seems to be justified, since the practical treatment of linear inverse problems always requires a concentration to specific bases as polynomials, splines or wavelets.

Based on the operator A introduced with infinite dimensional range R(A) we define operators A_{N} with N-dimensional range R(A_{N}) = AX_{N} by the formula

A_{N} x = ∑_{n=1}^{N}⟨x, w_{n}⟩ Aw_{n}  (x = ∑_{n=1}^{∞}⟨x, w_{n}⟩ w_{n} ∈ X) .  (1.3)

If A is non-compact, then by Lemma 1.2 and Lemma 1.3 we obtain lim inf_{N→∞} ∥A−A_{N}∥ > 0 and hence:

Corollary 1.4. Let the operator A ∈ L(X, Y) be non-compact. Then there exists a constant ε > 0 such that ∥A_{N} − A∥ ≥ ε for all positive integers N.

As a consequence of Corollary 1.4 also in Section 2 we will mention some approximation drawback of ill-posed equations of type I (A non-compact) compared to ill-posed equations of type II with respect to discrete least-squares solutions of equation (1.1). Since both stability and approximation are factors influencing the solution behaviour of discrete least-squares solutions, both aspects are to be considered for characterizing the total kind of ill-posedness of a problem (1.1). Summarizing the observed phenomena we cannot find strict arguments that non-compact operators behave ‘better’ than compact ones.

It seems to be difficult to compare ill-posed problems of type I and type II based on common ill-posedness measures. At all, ill-posedness measures for equations (1.1) are extensively studied in the literature only for compact operators A. For such operators various authors (cf., e.g., [5: p. 40], [7], [8: p. 8], [9: p. 31] and [21]) have considered a degree of ill-posedness μ = μ(A) using the well-defined singular system {s_{n}, û_{n}, v̂_{n}}_{n=1}^{∞} (cf. [1: p. 63]) of the compact operator A, where

s_{1}(A) ≥ s_{2}(A) ≥ ... ≥ s_{n}(A) ≥ ... → 0 as n → ∞

is the ordered sequence of positive singular values, {û_{n}(A)}_{n=1}^{∞} and {v̂_{n}(A)}_{n=1}^{∞} are complete orthonormal systems of eigenelements in X and Y, respectively, satisfying

Aû_{n} = s_{n}v̂_{n} (n ≥ 1).

Note that Poincaré’s max-min principle for the n-th singular value yields the formula

s_{n}(A) = max_{T_{n}} min_{x∈T_{n}\\{0\}} \frac{∥Ax∥}{∥x∥} = min_{x∈T̂_{n}\\{0\}} \frac{∥Ax∥}{∥x∥} = \frac{∥Aû_{n}∥}{∥û_{n}∥}  (1.4)

where the maximum which was taken over all n-dimensional subspaces T_{n} of X is attained for the eigenspace T̂_{n} = span (û_{1}, ..., û_{n}).

In particular, the degree of ill-posedness is derived from the decay rate of the nonincreasing sequence {s_{n}(A)}_{n=1}^{∞} of singular values of the operator A. If, for example, A is an integral operator with a kernel arising from the Green function of a differential equation problem, we frequently have a proportionality

s_{n}(A) ∼ n^{−μ}  as n → ∞  (1.5)

where μ = μ(A) > 0 can be characterized as the degree of ill-posedness. Then there is a one-to-one correspondence between the decay rate μ > 0 of the singular values and the associated growth rate

κ̂_{N}(A) ∼ \frac{1}{s_{N}(A)} ∼ N^{μ}  as N → ∞  (1.6)

of the condition numbers

κ̂_{N}(A) = \frac{s_{1}(A)}{s_{N}(A)} = cond (\underline{Â}_{N}) = ∥\underline{Â}_{N}∥_{2} ∥\underline{Â}_{N}^{−1}∥_{2}  (1.7)

where ∥\underline{Â}_{N}∥_{2} denotes the spectral norm of the matrix

\underline{Â}_{N} = (⟨Aû_{i}, v̂_{j}⟩)_{i=1,2,...,N}^{j=1,2,...,N} = diag(s_{1}(A), ..., s_{N}(A)).  (1.8)

Since the smallest singular value σ_{N} of a non-singular Galerkin matrix

\underline{A}_{N} = (⟨Au_{i}, v_{j}⟩)_{i=1,2,...,N}^{j=1,2,...,N}  (1.9)

arising in the discretization process of (1.1) using a Galerkin method (cf., e.g., [11: p.68]) with N-dimensional subspaces generated by orthonormal systems {u_{n}}_{n=1}^{∞} in X and {v_{n}}_{n=1}^{∞} in Y is not greater than s_{N}(A) (cf. [22]), the growth rate of κ̂_{N} for N → ∞ is minimal with respect to the growth rate of all condition numbers

κ_{N} = cond (\underline{A}_{N}) = ∥\underline{A}_{N}∥_{2} ∥\underline{A}_{N}^{−1}∥_{2}  (1.10)

of such Galerkin matrices \underline{A}_{N}. For a general discussion of the condition numbers of discretized ill-posed operator equations, we refer to [18] (see also [13]).

In the recent paper [10] it was recommended to measure the ill-posedness of equation (1.1) with a compact operator A by an interval of ill-posedness

[\underline{μ}(A), \overline{μ}(A)] = [lim inf_{n→∞} \frac{− ln s_{n}(A)}{ln n}, lim sup_{n→∞} \frac{− ln s_{n}(A)}{ln n}] ⊆ [0, ∞]  (1.11)

evaluating by the left end and by the right end of the interval the slowest and the fastest decay rate to zero of subsequences of {s_{n}(A)}_{n=1}^{∞}, respectively. Namely, a single number μ(A) ∈ [0, ∞] alone cannot always characterize the decay rates and associated condition number rates sufficiently complete, in particular if no conditions (1.5) and consequently (1.6) are satisfied.

For non-compact operators A singular values do not exist. The sequence

s_{n}(A) = sup_{T_{n}} min_{x∈T_{n}\\{0\}} \frac{∥Ax∥}{∥x∥} > 0  (n ≥ 1)  (1.12)

as a generalization of (1.4) is also not helpful in the non-compact case, because this sequence is constant for sufficiently large integers n and so has no decay rate. Therefore we will use stability rates motivated by the discrete least-squares method in Section 2 for comparing the stability behaviour of ill-posed problems in the compact and in the non-compact case. Least-squares solutions restricted to finite-dimensional spaces play a fundamental role in the process of the numerical solution of an equation (1.1) (cf. [13]). Even though or just because of the fact that discrete least-squares solutions do not converge in general to the exact solution if the discretization dimension tends to infinity, this approach yields more insight for distinguishing the compact and the non-cmpact case than an unconditionally convergent regularization method.

In Section 3 the compact case is studied by considering a family of convolution equations in the space X = Y = L^{2}(0, 1), whereas in Section 4 multiplication operators in the same space form an example for the non-compact case. Some discussions on condition numbers of Galerkin matrices for both cases in Section 5 complete the paper.

2. Stability and approximation of discrete least squares

In this section we deal with discrete least-squares solutions of the linear operator equation (1.1), where we denote by x ∈ X the uniquely determined solution of (1.1) for a given right-hand side y = Ax ∈ Y. The symbol y_{δ} designates a perturbed right-hand side with

∥y − y_{δ}∥ ≤ δ  (2.1)

for a noise level δ > 0. Using N-dimensional subspaces X_{N} = span(w_{1}, ..., w_{N}) as introduced in Section 1 we can consider discrete least-squares solutions x_{N} solving the discrepancy minimization problem with exact right-hand side y

∥Az − y∥ → min  subject to z ∈ X_{N},  (2.2)

and moreover elements x_{N}^{δ} solving the corresponding problem with a noisy right-hand side y_{δ},

∥Az − y_{δ}∥ → min  subject to z ∈ X_{N}.  (2.3)

Both elements x_{N} = R_{N}y and x_{N}^{δ} = R_{N}y_{δ} are uniquely determined in X_{N}, since A is injective. The linear discretized solution operator R_{N} ∈ L(Y, X) on a fixed level N is bounded. For all integers N we introduce the positive number

γ_{N} = γ_{N}(X_{N}) = ( min_{z∈X_{N} \\{0\}} \frac{∥Az∥}{∥z∥})^{−1} = max_{z∈X_{N} ,∥Az∥=1} ∥z∥.  (2.4)

Because of

⟨AR_{N}y_{δ}, Az_{N}⟩ = ⟨y_{δ}, Az_{N}⟩ for all z_{N} ∈ X_{N}

we have ∥AR_{N}y_{δ}∥ ≤ ∥y_{δ}∥ and hence ∥R_{N}∥ ≤ γ_{N}. In the well-posed case we would have γ_{N} ≤ ∥A^{−1}∥ < ∞ with γ_{N} uniformly bounded by a finite constant. Reflecting the ill-posed case, however, such a constant does not exist.

Lemma 2.1. If the linear operator equation (1.1) is ill-posed, then we have, for all orthonormal systems {w_{n}}_{n=1}^{∞} generating the spaces X_{N}, the limit condition

lim_{N→∞} γ_{N} = ∞.  (2.5)

Proof. Since the operator A^{−1} is unbounded, we have a sequence {z_{k}}_{k=1}^{∞} ⊂ X with ∥z_{k}∥ = 1 for all k and

\frac{∥Az_{k}∥}{∥z_{k}∥} → 0  as k → ∞.  (2.6)

If the limit condition (2.5) was injured, then we would have a constant ε > 0 and a sequence of dimensions N_{i} → ∞ as i → ∞ with ∥Az∥ ≥ ε∥z∥ for all z ∈ X_{N_{i}}. Now for all positive integers i and k the N_{i}-dimensional approximations

z_{k}^{N_{i}} = ∑_{j=1}^{N_{i}}⟨z_{k}, w_{j}⟩ w_{j}

of z_{k} satisfy ∥Az_{k}^{N_{i}}∥ ≥ ε∥z_{k}^{N_{i}}∥ and with lim_{i→∞} z_{k}^{N_{i}} = z_{k} the inequality ∥Az_{k}∥ ≥ ε∥z_{k}∥. This, however, contradicts the limit condition (2.6)

Now we consider the error of discrete least-squares solutions. We obtain from the triangle inequality

∥x_{N}^{δ} − x∥ ≤ γ_{N}δ + ∥x_{N} − x∥.  (2.7)

On the one hand, the first term γ_{N}δ in (2.7) is a ‘stability term’ and expresses the noise influence in the solution. Here γ_{N} acts as a stability factor. The greater the value γ_{N} gets for fixed N, the more instable is the solution process of (1.1) on this discretization level. By formula (1.4) we have for all integers N and A compact

γ_{N} ≥ (s_{N}(A))^{−1}  and  γ_{N} = (s_{N}(A))^{−1} if and only if X_{N} = T̂_{N}.  (2.8)

On the other hand, the second term ∥x_{N} − x∥ in (2.7) is an ‘approximation term’. In order to get convergence

x_{N(δ)}^{δ} → x  as δ → 0  (2.9)

two requirements should be satisfied. First N(δ) should be chosen such that

γ_{N(δ)}δ → 0  as δ → 0  (2.10)

and secondly we should have

lim_{N→∞} ∥x_{N} − x∥ = 0  (2.11)

for arbitrary solutions x ∈ X.

Under the assumptions stated above we find in the literature the following convergence proposition for discrete least-squares solutions (cf. [11: Theorem 3.10] and [14: Satz 4.5.6]).

Proposition 2.2. If there exists a constant c > 0, independent of N, such that

min_{z_{N} ∈X_{N}} {∥x − z_{N}∥ + γ_{N}∥A(x − z_{N})∥} ≤ c∥x∥  for all x ∈ X,  (2.12)

then we have a constant c̃ > 0 with

∥x − x_{N}^{δ}∥ ≤ γ_{N}δ + c̃ min_{z_{N} ∈X_{N}} ∥x − z_{N}∥  for all x ∈ X.  (2.13)

If (2.12) is satisfied, we have convergence (2.9) for arbitrary solutions x ∈ X of equation (1.1) whenever we choose N(δ) according to (2.10). Namely, by our choice of X_{N} the term min_{z_{N} ∈X_{N}} ∥x − z_{N}∥ tends to zero with N → ∞ for all x ∈ X. However, this convergence is not uniform. Therefore we cannot obtain convergence rates from formula (2.13). By formula (2.12) Proposition 2.2 gives a sufficient condition for R_{N} to be a regularizer characterized by ∥R_{N}A∥ ≤ const < ∞ for all integers N and implying the convergence condition (2.11) for all x ∈ X. Even if (2.12) is only sufficient and not necessary for the regularizing property, its discussion may help to distinguish typical situations of equation (1.1).

Theorem 2.3. Condition (2.12) of Proposition 2.2 is always satisfied if the linear operator equation (1.1) is well-posed. If equation (1.1) is ill-posed of type II (A compact), then (2.12) can be ensured by an appropriate choice of the orthonormal system {w_{n}}_{n=1}^{∞} generating the finite-dimensional subspaces X_{N}. If equation (1.1) is ill-posed of type I (A non-compact), then (2.12) is never satisfied.

Proof. In the well-posed case we have γ_{N} ≤ ∥A^{−1}∥ and for all x ∈ X

min_{z_{N} ∈X_{N}} {∥x − z_{N}∥ + γ_{N}∥A(x − z_{N})∥} ≤ ∥x∥ + γ_{N}∥Ax∥ ≤ (1 + ∥A∥∥A^{−1}∥)∥x∥.

For ill-posed problems of type II (A compact) we can choose the orthonormal system {w_{n}}_{n=1}^{∞} generating X_{N} by using the eigensystem {û_{n}}_{n=1}^{∞}. Then we have for all x ∈ X

min_{z_{N} ∈X_{N}} {∥x − z_{N}∥ + γ_{N}∥A(x − z_{N})∥}

≤ ∥ ∑_{n=N+1}^{∞}⟨x, u_{n}⟩u_{n}∥ + \frac{1}{s_{N}} ∥ ∑_{n=N+1}^{∞} s_{n}⟨x, u_{n}⟩v_{n}∥

≤ (1 + \frac{s_{N+1}}{s_{N}} )∥x∥

≤ 2∥x∥.

For ill-posed problems of type I (A non-compact) condition (2.12) is always injured. Because of Lemma 2.1 (2.12) requires a limit condition

lim_{N→∞} sup_{x∈X\\{0\}} \frac{min_{z_{N} ∈X_{N}} ∥A(x − z_{N})∥}{∥x∥} = 0.

This, however, contradicts the assertion of Corollary 1.4. Namely, we can write

sup_{x∈X\\{0\}} \frac{min_{z_{N} ∈X_{N}} ∥A(x − z_{N})∥}{∥x∥} = sup_{x∈X\\{0\}} \frac{∥(A_{N} − A)x∥}{∥x∥} = ∥A_{N} − A∥ ≥ ε > 0

where A_{N} is the linear operator with N-dimensional range which is defined for an orthogonal decomposition X = X̃_{N} ⊕ X̃_{N}^{⊥} with X̃_{N} = A^{∗}AX_{N} as follows: For x = x̃_{N} + x̃_{N}^{⊥} with x̃_{N} ∈ X̃_{N} and x̃_{N}^{⊥} ∈ X̃_{N}^{⊥} we set A_{N}x = Ax̃_{N}

For linear ill-posed problems (1.1) with non-compact operators A, Theorem 2.3 indicates some drawback concerning the convergence of discrete least-squares solutions. At least in this sense, linear ill-posed problems of type II are ‘less’ ill-posed than ill-posed problems of type I. However, up to now it is an open question for the authors whether there exist in the case of non-compact A orthonormal systems {w_{n}}_{n=1}^{∞} generating the finite-dimensional spaces X_{N} such that R_{N} is still a regularizer. This question is related to the evaluation of the gap between sufficiency and necessity of (2.12) with respect to the limit condition (2.11).

In the paper [13], J. Lin et al. also discussed properties of discrete least-squares solutions of equation (1.1). As an optimal choice of X_{N} they considered a situation such that, for arbitrarily given ε > 0, inequalities of the form

min_{z∈X_{N} \\{0\}} \frac{∥Az∥}{∥z∥} ≥ ε  and  sup_{z∈X_{N}^{⊥}\\{0\}} \frac{∥Az∥}{∥z∥} ≤ ε  (2.14)

can be satisfied where X_{N}^{⊥} is the infinite-dimensional orthogonal complement of X_{N}. The first inequality of (2.14) is to stabilize the discrete least-squares solutions. In our setting this condition corresponds to γ_{N} ≤ \frac{1}{ε}. The second inequality of (2.14), however, is an approximation requirement. From Corollary 1.4 we can easily derive that for sufficently small values ε > 0 such an inequality can never hold for ill-posed problems (1.1) of type I with non-compact operator A. In the compact case, (2.14) is obviously fulfilled if we choose X_{N} = T̂_{N} = span (û_{1}, ..., û_{N}) and N such that

s_{N+1}(A) ≤ ε ≤ s_{N}(A).

To evaluate the stability term γ_{N}δ of inequality (2.7) for compact and non-compact operators A in a unified manner we compare growth rates of γ_{N} for N → ∞.

Definition 2.4. Let the linear operator equation (1.1) be ill-posed. We call ν > 0 a stability rate of (1.1) if we have an orthonormal system {w_{n}}_{n=1}^{∞} in X generating subspaces X_{N} = span (w_{1}, ..., w_{N}) such that, for γ_{N} = γ_{N}(X_{N}) defined by formula (2.4),

γ_{N} = O(N^{ν})  as N → ∞.  (2.15)

If we consider a family of ill-posed problems (1.1) with a uniform stability rate ν > 0, then for any such problem there is an appropriate choice of an orthonormal system {w_{n}}_{n=1}^{∞} in X generating X_{N} such that the stability term γ_{N}δ in (2.7) can be bounded by CN^{ν}δ with a constant C > 0 independent of N.

Let denote by

A ≺ B ⟺ ∃ K̂ > 0 : ∥Ax∥ ≤ K̂∥Bx∥ for all x ∈ X  (2.16)

a semi-ordering between injective linear operators in L(X, Y) with infinite dimensional range. Then by definition of γ_{N} we immediately obtain

Proposition 2.5. Let B ∈ L(X, Y) be an injective operator with infinite dimensional range and

Bx = y  (x ∈ X, y ∈ Y)  (2.17)

an ill-posed linear operator equation. If A ≺ B and ν > 0 is a stability rate of equation (1.1), then ν is also a stability rate of equation (2.17).

In the next two sections we analyze stability rates for selected classes of compact and non-compact operators A more in detail.

3. Ill-posed equations with compact convolution operators

Here we consider in the spaces X = Y = L^{2}(0, 1) the class of linear convolution equations

[Ax](s) = ∫_{0}^{s} k(s − t)x(t) dt = y(s)  (0 ≤ s ≤ 1)  (3.1)

where we assume for the kernel k of the convolution operator A

k ∈ L^{2}(0, 1)  and  sup{s : k = 0 a.e. in [0, s]} = 0.  (3.2)

Hence the convolution operator A ∈ L(L^{2}(0, 1), L^{2}(0, 1)) from (3.1) with a kernel k satisfying (3.2) is a Hilbert-Schmidt operator and therefore compact. Moreover, it is injective due to Titchmarsh’s theorem (cf., e.g., [2: p. 138]). That means, (3.1) is as an operator equation (1.1) in the space X = Y = L^{2}(0, 1) ill-posed of type II. Convolution equations occur in practice in problems of indirect measurements when the values x(t) of a physical quantity depending on time t cannot be measured directly, but by means of a convolution product with a measuring tool function k, where for fixed t only values x(τ) of the past 0 ≤ τ ≤ t influence the convolution result. Ill-posed convolution equations, for example, we also find in the identification of memory kernels in heat conduction and viscoelasticity (cf. for general considerations L. von Wolfersdorf and J. Janno [23]).

From formula (2.8) we directly obtain the following

Lemma 3.1. An equation (1.1), which is ill-posed of type II, possesses a stability rate ν > 0 if and only if we have a constant C > 0 such that, for all integers n,

s_{n}(A) ≥ Cn^{−ν}.  (3.3)

If, on the other hand, there are constants μ > 0 and Ĉ > 0 such that, for all integers n,

s_{n}(A) ≤ Ĉn^{−μ},  (3.4)

then we have ν ≥ μ whenever ν > 0 is a stability rate of equation (1.1).

Because we have with respect to γ_{N} a well-defined optimal orthonormal system {w_{n}}_{n=1}^{∞} for a compact operator A (see formula (2.8)), we make use of it Lemma 3.1. It should be mentioned that in applications the computation of such optimal singular systems may be rather expensive.

By considering the interval of ill-posedness (1.11) introduced in [10] formula (3.3) yields \overline{μ}(A) ≤ ν. In the compact case the stability rate ν in the sense of Definition 2.4 is a majorant of the right end of the interval of ill-posedness. Unfortunately, given smoothness assumptions on a Hilbert-Schmidt kernel of an integral equation, as for example in the following proposition, can only help to find inequalities (3.4) and hence conditions of the form \underline{μ}(A) ≥ μ yielding lower bounds for the left end of interval of ill-posedness.

For Fredholm integral operators with quadratically integrable kernel we have a wellknown connection between the kernel smoothness and the decay rate of the singular values which is due to S. H. Chang (cf., e.g., [4: Satz 8.5] or [22]):

Proposition 3.2. Consider with kernel κ ∈ L^{2}((0, 1)^{2}) the Fredholm integral equation

[Ax](s) = ∫_{0}^{1} κ(s, t)x(t) dt = y(s) (0 ≤ s ≤ 1).

If

κ, \frac{∂κ}{∂s}, \frac{∂^{2}κ}{∂s^{2}}, …, \frac{∂^{i−1}κ}{∂s^{i−1}} are continuous in s for a.a. t

and

\frac{∂^{i}κ(s, t)}{∂s^{i}} = ∫_{0}^{s} g(τ, t) dτ + h(t) where g ∈ L^{2}((0, 1)^{2}) and h ∈ L^{1}(0, 1),

then we have for the ordered singular values s_{n} of A

s_{n} = o(n^{−i− \frac{3}{2}} ) as n → ∞.

Provided that the kernel function k = k(t) (0 ≤ t ≤ 1) of the convolution equation (3.1) for some positive integer l is (l − 1)-times continuously differentiable on the closed interval [0, 1], belongs to the Sobolev space H^{l}(0, 1) possessing quadratically integrable generalized derivatives up to the l-th order and is ‘flat’ enough in a neighbourhood of t = 0, then lower bounds for the stability rate can be formulated.

From Lemma 3.1 and Proposition 3.2 we immediately obtain the following

Corollary 3.3. Let ν > 0 be a stability rate for the convolution equation (3.1) subject to (3.2). Then we have in any case ν > \frac{1}{2}. If, moreover, we have an integer l > 0 with

k ∈ H^{l}(0, 1) ∩ C^{l−1}[0, 1] and k(0) = k′(0) = ... = k^{(l−1)}(0) = 0,  (3.5)

then ν > l + \frac{1}{2}. If (3.5) is valid for arbitrarily large integers l, then (3.1) has no stability rate ν < ∞.

Deriving stability rates ν > 0, whenever they exist for a given kernel k of the convolution equations (3.1), requires to estimate the fastest decay rate of a subsequence {s_{n_{l}}}_{l=1}^{∞}(A) of corresponding singular values. This is explicitly possible only for specific examples.

Example 3.4. If we consider the family k(t) = t^{r−1} (\frac{1}{2} < r < ∞) of kernels in equation (3.1), then we know from [20] that we have for the associated singular values s_{n}(A) ∼ n^{−r} as n → ∞. Hence the convolution equation

[A_{r}x](s) = ∫_{0}^{s} \frac{(s − t)^{r−1}}{Γ(r)} x(t) dt = y(s)  (0 ≤ s ≤ 1)  (3.6)

with the fractional integral operator A_{r} has a minimal stability rate ν = r.

Considering this example and the ‘flatness’ discussion of the function k = k(t) at t = 0 in the context of Corollary 3.3 one could conjecture that convolution kernels satisfying for a constant C̃ > 0 and an exponent \frac{1}{2} < ν < ∞ an inequality

k(t) ≥ C̃t^{ν−1}  (0 ≤ t ≤ 1)  (3.7)

lead to equations (3.1) with stability rates ν. Unfortunately, this is not true. We will see, however, in the next section that for non-compact multiplication operators an assertion of similar type holds (cf. Theorem 4.4).

At the end of this section we consider for the compact operator A from (3.1) and exact right-hand sides y = Ax convergence rates of Tikhonov regularization. For the minimizer

x_{α} = (A^{∗}A + αI)^{−1}A^{∗}y

of the extremal problem

∥Az − y∥^{2} + α ∥z∥^{2} → min, subject to z ∈ X

we have for 0 < η < 1 (cf. [16])

∥x_{α} − x∥ = O(α^{η})  as α → 0  (3.8)

if and only if

∑_{i=n}^{∞}⟨x, û_{i}⟩^{2} = O ((s_{n}(A))^{4η})  as n → ∞.  (3.9)

If ν > 0 is a stability rate of (3.1), then

∑_{i=n}^{∞}⟨x, û_{i}⟩^{2} = O(n^{−4ην})  as n → ∞  (3.10)

is sufficient for (3.9) and hence for the convergence rate (3.8) of Tikhonov regularization, where (3.10) is a decay condition for the Fourier components of x with respect to the eigenelements û_{i} in relation to negative powers of n. The strength of condition (3.10) for x obviously grows with ν. In this sense, the set of elements x ensuring a rate (3.8) is the ‘bigger’ the smaller the value ν can be verified. Note that a condition (3.10) and consequently a rate condition (3.8) is not automatically satisfied if the solution element x is smooth enough, for example if x ∈ L^{∞}(0, 1) or if x ∈ C^{∞}(0, 1).

4. Ill-posed equations with multiplication operators

In this section we consider in the spaces X = Y = L^{2}(0, 1) the class of equations

[Ax](s) = φ(s) · x(s) = y(s)  (0 ≤ s ≤ 1)  (4.1)

with a multiplication operator A (see also [6]) generated by a real muliplier function φ, where we assume

φ ∈ L^{∞}(0, 1),  φ(s) ≥ 0 (0 ≤ s ≤ 1),  meas{s : φ(s) = 0} = 0.  (4.2)

The operator A ∈ L(L^{2}(0, 1), L^{2}(0, 1)) from (4.1) subject to (4.2) is a self-adjoint injective bounded linear operator. Furthermore, let the essential infimum of φ vanish, i.e.,

essinf_{s∈[0,1]} φ(s) = 0.  (4.3)

In view of the following proposition, (4.1) subject to (4.2) and (4.3) is for X = Y = L^{2}(0, 1) an operator equation (1.1) ill-posed of type I.

Proposition 4.1. The multiplication operator A ∈ L(L^{2}(0, 1), L^{2}(0, 1)) defined in (4.1) with a multiplier function φ satisfying (4.2) is not compact. Moreover, we have a non-closed range R(A) ≠ \overline{R(A)} if and only if condition (4.3) is fulfilled.

Proof. Following [17] the spectrum of the linear multiplication operator A coincides with the essential range of the real function φ ∈ L^{∞}(0, 1). This essential range is the set-theoretical complement (with respect to ℝ) of the union of all open sets G ⊂ ℝ with meas(φ^{−1}(G)) = 0. Now, no real value λ of the spectrum of A can be an eigenvalue with finite multiplicity. Namely, λ can only be an eigenvalue at all, if the pre-image φ^{−1}({λ}) has a positive measure. However, on this set the function φ(s) − λ vanishes and we can find an infinite orthogonal system of functions with support in this set forming the eigenfunctions according to the eigenvalue λ. If a linear operator is compact, then it has a discrete spectrum and all non-zero eigenvalues have finite multiplicity. Therefore, a compact multiplication operator could only have 0 in its spectrum and so in its essential range. Consequently, φ has to vanish almost everywhere. This however contradicts (4.2). If and only if (4.3) is satisfied, the value 0 belongs to the (continuous) spectrum of the multiplication operator A. Then the inverse operator A^{−1} is not bounded and the range R(A) is not closed if and only if we have (4.3)

Multiplication operators occur, for example, as Fréchet derivatives of Nemytski operators. On the other hand, Nemytski operators play an important role as the nonlinear part in the decomposition of Hammerstein equations into an ill-posed linear Fredholm integral equation as the outer equation and a non-linear inner equation of Nemytski type.

The ‘strength’ of ill-posedness for such multiplication operators is essentially characterized by the behaviour of the increasing rearrangement φ̃ of φ in a neighbourhood of s = 0. For φ ∈ L^{∞}(0, 1) we define the increasing rearrangement

φ̃(s) = sup{t : d_{φ}(t) ≤ s} (0 ≤ s ≤ 1),

a non-decreasing and right-continuous function, by using the distribution function

d_{φ}(t) = meas{s ∈ [0, 1] : 0 ≤ φ(s) ≤ t}.

Note that (4.3) is equivalent to φ̃(0) = 0. From (4.2), however, we find φ̃(s) > 0 for s > 0.

Definition 4.2. We call ν̃ > 0 an ill-posedness rate of equation (4.1) if we have a constant K > 0 such that

φ̃(s) ≥ Ksν̃  (0 ≤ s ≤ 1).  (4.4)

As we will see for the multiplication operators under consideration there are close connections between the ill-posedness rate ν̃ and the stability rate ν of Definition 2.4. First the following theorem indicates an analogous behaviour of ν̃ and ν with respect to the semi-ordering (2.16).

Theorem 4.3. Let A_{1} and A_{2} satisfying A_{1} ≺ A_{2} according to the semi-ordering (2.16) denote two multiplication operators with the multiplier functions φ_{1} and φ_{2}, respectively, subject to (4.2) and (4.3). If ν̃ > 0 is an ill-posedness rate corresponding to A_{1}, then this value ν̃ is also an ill-posedness rate corresponding to A_{2}.

Proof. For A_{1} ≺ A_{2} we have a constant K̂ > 0 such that

∥φ_{1} · x∥_{L^{2}(0,1)} ≤ K̂∥φ_{2} · x∥_{L^{2}(0,1)} for all x ∈ L^{2}(0, 1).

From this we get φ_{1}(s) ≤ K̂φ_{2}(s) for a.a. s ∈ [0, 1]. Otherwise there would exist a set Ω ⊂ [0, 1] with meas(Ω) > 0 and φ_{1}(s) > K̂φ_{2}(s) for s ∈ Ω. Then the characteristic function χ_{Ω} ∈ L^{2}(0, 1) would fulfill the inequality

∥φ_{1} · χ_{Ω}∥_{L^{2}(0,1)} > K̂∥φ_{2} · χ_{Ω}∥_{L^{2}(0,1)}.

This, however, contradicts the above assumption. Now we have

d_{φ_{2}}(t) = meas\{s : φ_{2}(s) ∈ [0, t]\} ≤ meas\{s : K̂^{−1}φ_{1}(s) ∈ [0, t]\} = d_{\frac{φ_{1}}{K̂}} (t)

and consequently φ̃_{1}(s) ≤ K̂φ̃_{2}(s) for all s ∈ [0, 1]. From φ̃_{1}(s) ≥ K_{1}s_{ν} (0 ≤ s ≤ 1) with a constant K_{1} > 0 we finally derive

φ̃_{2}(s) ≥ K̂^{−1}φ̃_{1}(s) ≥ K̂^{−1}K_{1}s_{ν}.

This completes the proof

A second connection between ν̃ and ν is indicated by the following theorem.

Theorem 4.4. Provided that we have for positive constants ν and K

φ(s) ≥ Ks^{ν}  (0 ≤ s ≤ 1),  (4.5)

equation (4.1) possesses a stability rate ν.

Proof. We generate the finite-dimensional spaces X_{N} by the Haar wavelet base as the orthonormal system {w_{n}}_{n=1}^{∞}. This base is given by

\begin{matrix}θ & = 1 (scaling function) \\ ψ_{ml}(s) & = 2^{\frac{m}{2}} ψ(2^{m}s − l) (m ≥ 0; l = 0, …, 2^{m} − 1) \end{matrix} \}

where ψ is the Haar mother wavelet ψ = χ_{[0, \frac{1}{2} ]} − χ_{[ \frac{1}{2} ,1]}. So we can numerate

\begin{matrix}w_{1} & = θ \\ w_{2^{m}+l+1} & = ψ_{ml} (m ≥ 0; l = 0, …, 2^{m} − 1). \end{matrix} \}

For N := 2^{m} + l + 1 any function z in X_{N} can be expressed by

z = ∑_{i=1}^{2l+2} c_{i}χ_{[\frac{i−1}{2^{m+1}} , \frac{i}{2^{m+1}} ]} + ∑_{i=2l+3}^{N} c_{i}χ_{[\frac{i−l−2}{2^{m}} , \frac{i−l−1}{2^{m}}]}

where the second sum vanishes when we have l = 2^{m} − 1. Now from (4.5) we obtain for γ_{N} that \frac{1}{γ_{N}^{2} K^{2}} can be estimated below by the minimum over \{c_{1}, …, c_{N}\} of the expression

\frac{∫0^{\frac{1}{2^{m+1}}} c_{1}^{2}s^{2ν}ds + … + ∫ \frac{l+1}{2^{m}} ; \frac{2l+1}{2^{m+1}} c_{2l+2}^{2}s^{2ν}ds + ∫ \frac{l+2}{2^{m}} ; \frac{l+1}{2^{m}} c_{2l+3}^{2}s^{2ν}ds + … + ∫ 1_{\frac{2^{m}−1}{2^{m}}} c_{N}^{2}s^{2ν}ds}{\frac{1}{2^{m+1}} (c_{1}^{2} + … + c_{2l+2}^{2}) + \frac{1}{2^{m}} (c_{2l+3}^{2} + … + c_{N}^{2})}.

It can easily be seen that the minimum is attained whenever the constants c_{2}, …, c_{N} are zero and c_{1} is arbitrarily chosen. Then

γ_{N} ≤ \frac{\sqrt{2ν + 1}(2^{m+1})^{ν}}{K}

follows. For 2^{m} < N ≤ 2^{m+1} we have γ_{N} ≤ K̃N^{ν} with a fixed constant K̃ > 0, i.e. we have found an orthonormal system, for which the γ_{N} grow maximally as the rate of ill-posedness

Now we consider also for multiplication operators in the case of exact right-hand sides y = Ax Tikhonov regularized solutions

x_{α}(s) = \frac{φ(s)}{φ^{2}(s) + α} y(s) a.e. in [0, 1]

and their convergence rates (3.8) for 0 < η < 1. Then in contrast to the case of a compact operator A (see formula (3.10)) under the smoothness assumption x ∈ L^{∞}(0, 1) we have a uniform convergence rate depending on the given ill-posedness rate ν̃ > \frac{1}{4}.

Theorem 4.5. Let ν̃ > \frac{1}{4} be an ill-posedness rate of equation (4.1). Then we have for all x ∈ L^{∞}(0, 1)

∥x_{α} − x∥ = O(α^{\frac{1}{4ν̃}})  as α → 0.  (4.6)

Proof. To prove this theorem we apply the following equivalence of Neubauer (cf. [16]) for 0 < η < 1:

∥x_{α} − x∥ = O(α^{η}) ⟺ ∫_{0}^{μ} d∥E_{λ}x∥^{2} = O(μ^{2η}).

Here E_{λ} is the spectral family of the operator A^{∗}A, i.e. in our case

[E_{λ}(x)](s) = \{ \begin{matrix}x(s) & if φ^{2}(t) ≤ λ \\ 0 & if φ^{2}(s) > λ. \end{matrix}

Now with (4.4) we can estimate

∫_{0}^{μ} d∥E_{λ}x∥^{2} = ∫_{0}^{μ} d(E_{λ}x, x)

= ∫_{0}^{μ} d ∫_{{s:φ^{2}(s)≤λ}} x^{2}(s) ds = ∫_{{s:φ^{2}(s)≤μ}} x^{2}(s) ds

≤ ∫_{\{s:φ^{2}(s)≤μ\}} dt · ∥x∥_{L^{∞}(0,1)}^{2} = d_{φ}(\sqrt{μ})∥x∥_{L^{∞}(0,1)}^{2}

= d_{φ}(\sqrt{μ})∥x∥_{L^{∞}(0,1)}^{2}

≤ K̃μ^{\frac{1}{2ν̃}} .

This yields formula (4.6)

Note that the assertion of Theorem 4.5 is not valid for ν̃ = \frac{1}{4} as the following example shows.

Example 4.6. Consider the multiplication operator A from (4.1) with the multiplier function

φ(s) = s^{\frac{1}{4}} .  (4.7)

Evidently, we have ν̃ = \frac{1}{4}. Then (4.6) cannot hold for φ from (4.7) and a solution x(s) = 1 (0 ≤ s ≤ 1). Namely,

∥x_{α} − x∥^{2} = ∫_{0}^{1} \frac{α^{2}}{(\sqrt{s} + α)^{2}} ds = O(α^{2}) as α → 0

would contradict the limit condition

lim_{α→0} ∫_{0}^{1} \frac{1}{(\sqrt{s} + α)^{2}} ds = lim_{α→0} (\frac{−2}{α + 1} + 2 ln (1 + \frac{1}{α})) = ∞.

5. Case studies on condition numbers

If we reinterpret the remarks on condition numbers κ̂_{N} (see formula (1.7)) of Galerkin matrices \underline{Â}_{N} in Section 1 with respect to stability rates in the case of compact operators A, we find close connections between the growth rates (1.6) and (2.15). In this section we first illustrate these remarks on condition numbers by some computational results. We consider the family (3.6) of fractional integral operators A_{r} with kernels k(t) = Ct^{r−1} and singular values (s_{N}(A_{r}))^{−1} ∼ N^{r}. Instead of using Galerkin matrices we discretize the operator A_{r} by the lower triangular Toeplitz matrices

\underline{Ā}_{N} = ( \begin{matrix}k_{1} & 0 & … & 0 \\ k_{2} & k_{1} & ... & ⋮ \\ ⋮ & ... & ... & 0 \\ k_{N} & … & k_{2} & k_{1} \end{matrix} )

with

k_{i} = k(\frac{2i − 1}{2N}) (i = 1, 2, ..., N)

and compute condition numbers

κ̄_{N} = cond(\underline{Ā}_{N}) = ∥\underline{Ā}_{N}∥_{2}∥\underline{Ā}_{N}^{−1}∥_{2}

using MATLAB routines. By setting N_{j} = 2^{j} (j ≥ 1) and

κ̄_{N} ≈ C̄N ν̄  (5.1)

the exponent ν̄ was fitted by observing the values

ν̄_{j} = \frac{ln κ̄_{N_{j+1}} − ln κ̄_{N_{j}}}{ln 2} (j ≥ 1).

Table 1 shows the values ν̄_{j} for j = 1, 2, ..., 8 and a sample of indices r. In particular, for larger j (e.g., j = 7 and j = 8) we get an impression of the realistic exponent ν̄ in (5.1). For the sufficiently small stability rates \frac{1}{2} ≤ r < 2 (situations a) - e) in Table 1) we can conclude that an equation ν̄ = r is realistic. If the index r approaches to 2 from below, then we have a rather sharp jump of magnitude 1 with respect to the observed exponent ν̄ (ν̄ ≈ 2 for r = 1.9 and ν̄ ≈ 3 for r = 2). This is an interesting phenomenon which we cannot interpret in detail. For larger values r > 2 it became clear that a reliable computation of condition numbers using MATLAB failed the more r and j were growing. The situation h) in Table 1 with r = 2.1 confirms for small j the growth of ν̄_{j} as r grows. However, larger values j lead to inacceptable results. The results of r = 3 and r = 4 were completely instable and useless. This seems to be due to the fact mentioned by J. W. Demmel [3] that computing a condition number of a problem is approximately as hard as computing the solution of the problem itself.

Table 1: Condition number rates for fractional integral operators

In the second part of this section we want to demonstrate some comparable results for the non-compact multiplication operators to show that non-compact operators are not always ‘less’ ill-posed in general with respect to growth rates of condition numbers. We consider Galerkin-Ritz schemes as a concretization of the ansatz (1.9) with X = Y = L^{2}(0, 1) and orthonormal systems

{u_{n}}_{n=1}^{∞} = {v_{n}}_{n=1}^{∞} = {w_{n}}_{n=1}^{∞} ⊂ L^{2}(0, 1)

for this case. Using the N-dimensional space X_{N} = span(w_{1}, ..., w_{N}) we obtain Galerkin matrices

\underline{A}_{N} = (\underline{a}_{ij})_{i=1,2,...,N}^{j=1,2,...,N} with \underline{a}_{ij} = ∫_{0}^{1} φ(s)w_{j}(s)w_{i}(s) ds

for the operator of multiplication with the multiplier function φ ∈ L^{∞}(0, 1).

First we consider for {w_{n}}_{n=1}^{∞} the Haar wavelet base introduced in the previous section. The arising Galerkin matrices \underline{A}_{N} are sparse due to the small support of the functions ψ_{ml}. Comparative numerical computations indicate that the non-diagonal entries do not essentially influence the decay rate of the singular values of such matrices. So it seems to be realistic to have a look at the corresponding diagonal matrices for which the singular values can be verified explicitly. These values coincide with the diagonal entries of the Galerkin matrices for omitted non-diagonal entries. Now we assume for positive constants ν̃ and K that the multiplier function satisfies the equation

φ(s) = Ksν̃  (0 ≤ s ≤ 1).  (5.2)

Then for n = 2^{m} + l + 1 the diagonal entries \underline{a}_{nn} of \underline{A}_{N} can be written as follows:

\begin{aligned}\underline{a}_{nn} & = ∫_{0}^{1} φ(s)u_{n}^{2}(s) ds = ∫_{0}^{1} Ksν̃u_{n}^{2}(s) ds = ∫_{0}^{1} Ksν̃u_{2^{m}+l+1}^{2}(s) ds \\ & = K ∫_{0}^{1} sν̃ψ_{ml}^{2}(s) ds = K ∫_{\frac{l}{2^{m}}}^{\frac{l+1}{2^{m}}}sν̃ · 2^{m}ds = \frac{K}{(ν̃ + 1)2^{mν̃}} ((l + 1)^{ν̃+1} − l^{ν̃+1}) . \end{aligned}

For a fixed N = 2^{m_{N}} + l_{N} + 1 it can be found out that the smallest singular value σ_{N} = \frac{K}{(ν̃+1)2^{mν̃}} of \underline{A}_{N} occurs as the diagonal entry \underline{a}_{nn} with m = m_{N} and l = 0, whereas the largest singular value σ_{1} can be estimated above by

σ_{1} ≤ \frac{K}{(ν̃ + 1)2^{m_{N} ν̃}} ((2^{m_{N}})^{ν̃+1} − (2^{m_{N}} − 1)^{ν̃+1}) .

This implies for the condition number

κ_{N} = \frac{σ_{1}}{σ_{N}} ≤ ((2^{m_{N}})^{ν̃+1} − (2^{m_{N}} − 1)^{ν̃+1}) ≤ (ν̃ + 1)2^{m_{N} ν̃}

since we have 0 < \frac{a^{ν̃+1}−(a−1)^{ν̃+1}}{aν̃} < ν̃ + 1 for all values 1 < a < ∞. With respect to 2^{m_{N}} < N ≤ 2^{m_{N} +1} we derive that κ_{N} ≤ (ν̃ + 1)N ν̃.

For another example we consider

φ(s) = s  (0 ≤ s ≤ 1)  (5.3)

and use a set of weighted orthogonal polynomials. Let U_{n} denote the Chebyshev polynomials of the second kind. Then the sequence

\{\sqrt{\frac{2}{π}} ^{4} \sqrt{1 − s^{2}}U_{n}(s)\}_{n=1}^{∞}

forms a orthonormal system in L^{2}(−1, 1). If we transform this sequence to the interval (0, 1), we obtain the orthonormal system {w_{n}}_{n=1}^{∞} with

w_{n} = \{\sqrt{\frac{8}{π}} ^{4} \sqrt{s − s^{2}}U_{n}(2s − 1)\}_{n=1}^{∞}

Stability Rates for Linear Ill-Posed Problems 285

in L^{2}(0, 1). Here the entries \underline{a}_{ij} of the Galerkin matrix \underline{A}_{N} are expressed by the formula

\underline{a}_{ij} = ∫_{0}^{1} s\frac{8}{π} \sqrt{s − s^{2}}U_{i}(2s − 1)U_{j}(2s − 1) ds = \{ \begin{matrix}\frac{1}{2} & if i = j \\ \frac{1}{4} & if |i − j| = 1 \\ 0 & else. \end{matrix}

It can be verified that the singular values of \underline{A}_{N} have the form

σ_{n} = sin^{2} (\frac{(N − n + 1)π}{2(N + 1)} ) (n = 1, …, N).

So the condition number κ_{N} is given by

κ_{N} = \begin{matrix}sin & 2 & ( & \frac{Nπ}{2(N+1)} & ) \\ sin & 2 & ( & \frac{π}{2(N+1)} & ) \end{matrix} ∼ N^{2} as N → ∞.

In such a case the condition numbers grow for N → ∞ faster to infinity than the illposedness rate indicates. Comparable investigations concerning other functions φ show similar results for the same orthonormal system.

The last example has indicated that for multiplication operators the condition number growth of Galerkin matrices may be worse than κ_{N} ∼ N^{ν} for φ satifiying (4.5) if we choose an inappropriate system of orthonormal functions {w_{n}}_{n=1}^{∞}. On the other hand, from our considerations one can derive that at least for the Haar base {w_{n}}_{n=1}^{∞} the growth rate of the condition numbers κ_{N} is bounded by the ill-posedness rate ν̃ of equation (4.1).

Acknowledgement. The first author is grateful to Professor E. Schock (Kaiserslautern) for stimulating discussions in the context of this paper. Both authors wish to thank two referees for detailed suggestions and comments. Moreover, the authors acknowledge partial support through Deutsche Forschungsgemeinschaft (DFG) under Ho 1454/3-2.

References

[1] Baumeister, J.: Stable Solution of Inverse Problems. Braunschweig: Vieweg 1987.

[2] Berg, L.: Operatorenrechnung. Part II: Funktionentheoretische Methoden. Berlin: Dt. Verlag Wiss. 1974.

[3] Demmel, J. W.: On condition numbers and the distance to the nearest ill-posed problem. Numer. Math. 51 (1987), 251 – 289.

[4] Engl, H. W.: Integralgleichungen. Wien: Springer 1997.

[5] Engl, H. W., Hanke, M. and A. Neubauer: Regularization of Inverse Problems. Dordrecht: Kluwer 1996.

[6] Fleischer, G.: Multiplication operators and its ill-posedness properties. Preprint. Chemnitz: Techn. Univ., Fac. Math. Preprint 97-26 (1997), 1 – 27.

[7] Gorenflo, R. and B. Hofmann: On autoconvolution and regularization. Inverse Problems 10 (1994), 353-373.

[8] Hansen, P. C.: Rank-Deficient and Discrete Ill-Posed Problems. Philadelphia: SIAM 1998.

[9] Hofmann, B.: Regularization for Applied Inverse and Ill-Posed Problems. Leipzig: B. G. Teubner 1986.

[10] Hofmann, B. and U. Tautenhahn: On ill-posedness measures and space change in Sobolev scales. Z. Anal. Anw. 16 (1997), 979 – 1000.

[11] Kirsch, A.: An Introduction to the Mathematical Theory of Inverse Problems. New York: Springer 1996.

[12] Kress, R.: Linear Integral Equations. Berlin: Springer 1989.

[13] Liu, J., Guerrier, B. and C. Bernard: A sensitivity decomposition for the regularized solution of inverse heat conduction problems by wavelets. Inverse Problems 11 (1995), 1177 – 1187.

[14] Louis, A.: Inverse und schlecht gestellte Probleme. Stuttgart: B. G. Teubner 1989.

[15] Nashed, M. Z.: A new approach to classification and regularization of ill-posed operator equations. In: Inverse and Ill-posed Problems (eds.: H. W. Engl and C. W. Groetsch). Orlando: Acad. Press 1987, pp. 53 – 75.

[16] Neubauer, A.: On converse and saturation results for Tikhonov regularization of linear ill-posed problmes. SIAM J. Numer. Anal. 34 (1997), 517 – 527.

[17] Rudin, W.: Functional Analysis, 2nd ed. New York: McGraw-Hill 1991.

[18] Schock, E.: What are the proper condition numbers of discretized ill-posed problems ? Lin. Alg. Appl. 81 (1986), 129 – 136.

[19] Vainikko, G.: On the discretization and regularization of ill-posed problems with noncompact operators. Numer. Funct. Anal. Optimiz. 13 (1992), 381 – 396.

[20] Vu Kim Tuan and R. Gorenflo: Asymptotics of singular values of fractional integral operators. Inverse Problems 10 (1994), 949 – 955.

[21] Wahba, G.: Ill-posed problems: Numerical and statistical methods for mildly, moderately and severely ill-posed problems with noisy data. Report. Madison: University of Wisconsin, Techn. Rep. No. 595 (1980), 1 – 69.

[22] Wing, G.M.: Condition numbers of matrices arising from the numerical solution of linear integral equations of the first kind. J. Int. Equ. 9 (Suppl.) (1985), 191 – 204.

[23] Wolfersdorf, L. von and J. Janno: On Tikhonov regularization for identifying memory kernels in heat conduction and viscoelasticity. Freiberg: Techn. Univ. Bergakademie, Fac. Math. Inf. Preprint 98-01 (1998), 1 – 19.

Received 17.04.1998