key: cord-0134161-1svzrb25
authors: Bildhauer, Michael; C'ardenas, Marcelo; Fuchs, Martin; Weickert, Joachim
title: Existence Theory for the EED Inpainting Problem
date: 2019-06-11
journal: nan
DOI: nan
sha: 665f6a3437c0d1a0908898efb297e8c3bd0588f6
doc_id: 134161
cord_uid: 1svzrb25

We establish an existence theory for an elliptic boundary value problem in image analysis known as edge-enhancing diffusion (EED) inpainting. The EED inpainting problem aims at restoring missing data in an image as steady state of a nonlinear anisotropic diffusion process where the known data provide Dirichlet boundary conditions. We prove existence of a weak solution by applying the Leray-Schauder Fixed point theorem and show that the set of all possible weak solutions is bounded. Moreover, we demonstrate that under certain conditions, the sequences resulting from iterative application of the operator from the existence theory contain convergent subsequences.

In the present work we study the boundary value problem div (D(∇u σ )∇u) = 0 on G ,

(1) u = f on ∂K ,

(2) D (∇u σ ) ∇u · η = 0 on ∂Ω .

(

This problem serves as a mathematical model for the anisotropic diffusion image inpainting problem [11, 13, 4] . In that setting the domain Ω ⊂ R 2 represents the area of an image whose grey values f are known only in some subset K ⊂ Ω and the goal of the inpainting problem is to recover the complete image by filling in the missing information at G := Ω−K. The diffusion tensor D : R 2 → R 2×2 depends on the gradient of a Gaussian-smoothed version of u, denoted u σ , and is usually designed in order to steer the diffusion process in such a way that important geometrical information is taken into account. The Dirichlet boundary condition (2) , on the other hand, enforces the inpainted result u to be coherent with the known data f at the boundary of the known data region ∂K. The problem is also supplemented with the natural Neumann boundary condition (3) , where η represents the outer normal of Ω.

Let us now clarify our notation and assumptions regarding problem (1)- (3) .

Notation. We use the symbol c to denote a generic constant which may change from line to line. Whenever we want to stress its dependence on other values α 1 , α 2 , ..., we write c(α 1 , α 2 , ...)

.

Consider an open set Ω ⊂ R N . We use the following notation:

• We denote with W m,p (Ω) the Sobolev space of functions u in L p (Ω) s.t. their distributional derivatives up to order m belong to L p (Ω).

• Let (u n ) n∈N ⊂ W k,p (Ω), we write u n u ∈ W k,p (Ω) to denote weak convergence.

• ∂Ω denotes the boundary of Ω.

• With L(A) we denote the Lebesgue measure of a set A ⊂ R N .

• H d (B) denotes the d-dimensional Hausdorff measure of B ⊂ R N .

Main assumptions. The set Ω ⊂ R 2 is an open bounded Lipschitz domain, and the subset K ⊂ Ω is the closure of some Lipschitz subdomain such that H 1 (∂K) > 0. Moreover, we assume that the function f : K → [0, 1] is of class W 1,2 in the interior of K and we assume that it is extended to a function in W 1,2 (Ω). The diffusion tensor D : R 2 → R 2×2 is assumed to fulfil the following properties:

• Smoothness: D is continuous.

• Symmetry: d α,β (p) = d β,α (p), with D(p) = (d α,β (p)) 1≤α≤β≤2 , for all p ∈ R 2 .

• Non-degenerate ellipticity: There exist positive constants λ, c 1 , c 2 such that

Finally, σ is a positive parameter and for any function u ∈ L 1 (G) we denote with u σ its global smoothed version given by

where K denotes the Gaussian kernel k(z; σ) := 1 2πσ 2 exp −|z| 2 2σ 2 for all z ∈ R 2 .

If (u n ) n∈N is a sequence of elements of L 1 (Ω), we use the notation u n σ := (u n ) σ .

EED inpainting. The choice of the ellipticity condition (4) covers the inpainting problem with Edge-Enhancing Diffusion (EED) [11, 13, 4] . In that setting the diffusion tensor is such that the differential operator encourages diffusion along edges over diffusion across edges. More precisely, D(∇u σ ) is defined as a 2 × 2 matrix with eigenvectors ∇u ⊥ σ and ∇u σ having as corresponding eigenvalues 1 and g(|∇u σ | 2 ), where g is the Charbonnier diffusivity [3] given by g(s) := (1 + s 2 /λ 2 ) − 1 2 . For the rest of this work we also assume w.l.o.g. that λ = 1 except when stated explicitly otherwise. Edge-enhancing anisotropic diffusion was first proposed as a parabolic evolution process for denoising [11] , where it can be regarded as an anisotropic alternative to isotropic regularisations [2] of the Perona-Malik filter [9] . This evolution has been shown to be well-posed in the continuous, space discrete, and fully discrete setting [12] . Later on, the elliptic steady state equation of EED has been supplemented with Dirichlet data and used for inpainting missing regions in matrix-valued images [13] . Its main application today is inpainting-based lossy image compression, where only a sparse, carefully optimised subset of the data is stored and the missing data are recovered by EED inpainting [4] . In this context, experiments have shown that EED gives state-of-the-art results that outperform other partial differential equations in terms of reconstruction quality [10] . Fig. 1 depicts an example for EED inpainting of sparse data, using a photo of Professor Nina Uraltseva. In spite of its qualities in practical applications, there is no existence theory for EED inpainting so far. Our paper closes this gap. . Middle: Selecting 10 % of the data with the probabilistic sparsification strategy from [7] . These data locations specify the set K. Right: Reconstruction from the sparsified data using a finite difference scheme for the EED inpainting model with λ = 1 and σ = 0.8.

Main goal and summary. In the present work, we show existence of a weak solution for problem (1)-(3) and give a characterisation of the set of possibly multiple weak solutions. Our paper is organised as follows: Section 2 covers the existence of a solution for (1)-(3). We apply the Leray-Schauder fixed point theorem [5, 6] in order to show the existence of at least one weak solution which corresponds to a fixed point of an appropriate operator. In Section 3 we show that the set of possibly multiple weak solutions is bounded and can be characterised as the minimisers of an appropriate functional. Finally, in Section 4 we study the behaviour of sequences obtained by iteratively applying the operator used in the existence theory. We show that under some conditions these sequences are bounded and hence contain convergent subsequences. Appendix A lists some auxiliary results.

The goal of this section is to show that under the above conditions problem (1)-(3) has at least one weak solution. Our strategy for the problem is to apply the Leray-Schauder fixed point theorem: First we define the weak solutions of the problem as the fixed points of an appropriate operator and then show that the operator has at least one fixed point [5, 6] . Let us begin by introducing the relevant operator. For this purpose we need the following two ingredients: the class

(see Theorem A.1 in the Appendix for the definition of the trace operator) and the family of functionals J w : W 1,2 (G) → R defined as

for any w ∈ W 1,1 (G) and any v ∈ W 1,2 (G). Note that σ is fixed throughout this section.

Definition 2.1. The operator T :

for any w ∈ W 1,1 (G).

The previous definition is well-posed as the following proposition shows.

Proposition 2.1. The set C is a convex and weakly closed subset of W 1,2 (G). Moreover, for any fixed w ∈ W 1,1 (G), the functional J w is weakly lower semicontinuous over C and has a unique minimiser in C. The unique minimiser T (w) satisfies for all φ ∈ W 1,2 (G), such that φ| ∂K = 0.

Proof. Let H ∂K := {u ∈ W 1,2 (G) : u| ∂K = 0} . Then

is clearly convex, and the trace inequality (72) shows that for any sequence (u n ) n∈N ⊂ C such that u n → u ∈ W 1,2 (G) we have

This shows that u| ∂G = f, hence C is closed in W 1,2 (G). By Mazur's lemma it is also weakly closed.

On the other hand, since w ∈ W 1,1 (G), recalling (5) it is clear that w σ is of class C ∞ (R 2 ). Therefore, ∇w σ ∈ L ∞ (G, R 2 ) which together with (4) implies that

for any x ∈ G, q ∈ R 2 and positive constants µ 1 , µ 2 . Moreover, the Poincaré inequality (73) shows that ||∇·|| L 2 (G) is a norm of the Hilbert subspace H ∂K and is thus weakly lower semicontinuous. Hence, (12) and (11) show that J w (·) is also weakly lower semicontinuous over C and the Poincaré inequality shows that J w (·) is coercive. This proves the existence of a minimiser for (8) .

Any solution satisfies (10) and (9) as a consequence of the definition (8) . Let u, v ∈ C be two different minimisers. Then applying (10) with the choice φ = u − v, together with (12), we obtain

This and the Poincaré inequality (73) shows uniqueness.

Weak solution: We say that any fixed point of the operator T corresponds to a weak solution of (1)- (3) . In order to understand why this definition of weak solution is compatible with the boundary value problem, notice that any fixed point u of T satisfies the Euler-Lagrange equation (10) with w σ = u σ and for all φ ∈ W 1,2 (G), s.t. φ| ∂G = 0 (since ∂Ω ⊂ ∂G). This is nothing else than the weak form of (1). On the other hand, the Dirichlet condition (2) is already included in the definition of C. Moreover, for sufficiently regular data (e.g. D ∈ C 1 ) we can show u ∈ W 2,2 loc (G), and (1) will hold pointwise. Furthermore, formally integrating by parts (10) and using the arbitrariness of φ near ∂Ω, we end up with the natural Neumann boundary condition (3), provided we have W 2,2 −regularity of u near ∂Ω, which is still open.

We are now ready to state our main result: Theorem 2.1. (Existence of a weak solution) Given the above assumptions about problem (1)-(3), the operator T has at least one fixed point. In other words, the boundary value problem (1)-(3) has at least one weak solution.

The proof of Theorem 2.1 is divided into different steps which we present as intermediate lemmas.

for some positive constant c which is independent of w.

Proof. First we estimate ∇w σ in terms of w: It holds for any x ∈ G that

for α = 1, 2, and we find from (14) that

with c = c(G, σ). Using the same argument, (15) is established for all higher order derivatives. Next we discuss the size of ||T (w)|| W 1,1 (G) . Fixing w ∈ W 1,1 (G), we have by Hölder's inequality that

where for the last inequality we applied the ellipticity condition (4). Moreover, choosing f as comparison function in (9) and applying (4) once again, we obtain

whereas on account of (15),

Applying these estimates of A and B to (16), we obtain

Since T (w) is in the class C, thus coinciding with f over ∂K ⊂ ∂G, we may apply the Poincaré inequality (73) to the difference T (w) − f in order to obtain

Combining this estimate with inequality (17) we end up with

for a constant c depending on f and independent of w ∈ W 1,1 (G).

Moreover, let u n = T (w n ) and u = T (w). We have to show that

From (15) and (18) we get that

which together with (4) and the continuity of D gives

for any x ∈ G, q ∈ R 2 and all n ∈ N, with constants µ 1 , µ 2 > 0. Applying (9) to u n = T (w n ) with f as comparison function on the r.h.s., together with (21) we obtain

On the other hand, since u n ∈ C, we may apply the Poincaré inequality (73) in order to get the estimate

with a constant c which depends on f. Inequalities (22) and (23) imply

Therefore, by the Banach-Alaoglu theorem we know that there exists a sub-

for someũ ∈ W 1,2 (G). Moreover, since C is a closed convex subset of W 1,2 (G), Mazur's lemma implies that it is also weakly closed andũ ∈ C. On the other hand, from (10), we have that for any φ ∈ W 1,2 (G) satisfying φ| ∂K = 0, it holds that

Hence, applying (20) and (25) in equation (26) we obtain

for any such φ. Furthermore, since (27) is also true for u = T (w) in place of u, we findũ = u, and (25) actually reads

for the whole sequence instead of a subsequence. Next we improve (28) towards

which in turn implies ∇u n → ∇u in L 1 (G, R 2 ) and thus gives our claim (19). From the ellipticity (4) it follows that for some c > 0,

For the equality on the r.h.s. we used the fact that u = T (w) and u n = T (w n ) and thus both fulfil the corresponding Euler-Lagrange equations (10) with a test function φ := u n − u. Recalling (24) and using the fact that D(∇w n σ ) → D(∇w σ ) uniformly on G (which follows from the continuity of D in combination with (20)) we have established (29), and the continuity of T follows.

for a sequence (w n ) n∈N ⊂ W 1,1 (G) with corresponding solutions u n := T (w n ) of (8). Using (4), (15) and (30) we can follow the proof of Lemma 2.2 to deduce once again (21), (24) and the existence of a subsequence (u n k ) k∈N ⊂ (u n ) n∈N such that

for someũ ∈ C like in (25). Our claim is that

which because of the Rellich-Kondrachov theorem [1] implies the existence of a further subsequence of (u n k ) k∈N converging strongly toũ in W 1,1 (G) and proves the compactness of T. Let us this time argue with a variant of the proof given in Lemma 2.2:

We observe that on account of (15) and (30) the functions A n k :Ḡ → R 2×2 , A n k (x) := D(∇w n k σ (x)), are bounded and equicontinuous onḠ, thus by Arzela's theorem there exists a further subsequence, which we still label with the same indexing as (A n k ) k∈N , that converges uniformly onḠ to some A :Ḡ → R 2×2 . Furthermore, we can write

The uniform convergence A n k → A together with (24) implies

Furthermore, taking into account that u n k = T (w n k ) and applying equation (10) with a test function φ = u n k −ũ we obtain 

Finally, the uniform convergence of A n k and (21) imply

for x ∈ G, q ∈ R 2 and a positive constant µ 1 . Applying (37) 

holds for all u ∈ W 1,1 (G) and all α ∈ [0, 1] such that

From Lemma 2.1 we have that

W.l.o.g. we may assume α > 0. Hence, applying (39)

and using Young's inequality, we obtain for any > 0

The result follows choosing > 0 small enough such that αc 2 < 1.

In the previous section we proved the existence of a solution for (1) Proof. Let w ∈ F. Then w ∈ W 1,1 (G) and reasoning as in the proof of Lemma 2.1 after (15) we obtain that

We recall ||∇w σ || L 1 (G) ≤ c||w|| L 1 (G) , and obtain from (40)

with c = c(σ, f, G). Since additionally w ∈ C, then applying the Poincaré inequality (73)

Putting together (41) and (42), we find

with c = c(σ, f, G). Furthermore, since w = T (w), we can apply (43) to obtain ||∇w|| L 1 (G) ≤ c 1 + ||∇w|| 

This shows the boundedness of F in W 1,1 (G). On the other hand, (15) together with the ellipticity condition (4) give

for any q ∈ R 2 , x ∈ G and a positive constant µ 1 . Applying Proposition 2.1 together with the fact that T (w) = w and choosing f as a comparison function in (9) we obtain

Finally, applying (44) to the l.h.s. gives

This together with the Poincaré inequality (73) show the boundedness of F in W 1,2 (G).

Next we show that the set of weak solutions of (1)-(3), or equivalently the set of fixed points F correspond to the weak limits of the minimising sequences of the functional J : C → R defined as

with C as in (7).

ii) F coincides with the set of weak−W 1,2 −limits of J −minimising sequences from C.

Proof. i) For any minimising sequence (u n ) n∈N ∈ C of J , we have that

and from the Cauchy-Schwartz inequality also

Moreover, following the proof of Proposition 3.1, we see that (43) is valid for any element of C, hence

and applying Young's inequality we get

for any > 0. Using (47) and (46) to estimate the r.h.s. of (45)

which because of (15) implies

for any x ∈ G, q ∈ R 2 and all n ∈ N with a positive constant µ 1 . Inequality (48) together with an application of (9) with f as comparison function shows that sup

Finally ||∇u n || L 2 (G) = ||∇u n + ∇T (u n ) − ∇T (u n )|| L 2 (G) ≤ (J (u n )) 1 2 + ||∇T (u n )|| 2 together with (49) and the fact that (u n ) n∈N is a minimising sequence of J implies sup n∈N ||u n || W 1,2 (G) < ∞ and hence i).

ii) From part i) we have that

Moreover, from (48) and (9) with comparison function f

which together with the Poincaré inequality (73) imply

From (50) and (51) we a find subsequence (u n k ) k∈N ⊂ (u n ) n∈N such that

for someũ, ξ in C (since C is weakly closed). Our claim is that ξ = T (ũ). Because of (15), part i), and Arzela's theorem, we may assume

uniformly on G. By (9) it holds

for any v ∈ C. By (54)

From Proposition 2.1, we know that J w is weakly lower semicontinuous, thus (52)-(53) imply

which in combination with (54) and (55) gives

for all u ∈ C. Therefore, ξ = T (ũ) by (9) , and we obtainũ = T (ũ).

In this section we are interested in the question, whether an iteration of the operator T in some sense generates a suitable practical procedure for the problem discussed above. More precisely, given an initial element u 0 ∈ C, we consider the sequence (u (n) ) n∈N defined as u (n+1) := T (u (n) ) for n ≥ 1, namely the sequence obtained by iteratively solving (8) . In particular we are interested in underlying convergence results and a priori estimates, respectively. Let us start by showing that for any u 0 ∈ C, the corresponding iterated sequence is bounded whenever the parameter σ of the Gaussian (6) is large enough. Applications can be discussed following the ideas od Section 4.1. Proof. We only prove the first inequality as it implies the second one when following the same reasoning as in Lemma 2.2 after (19).

If w ∈ C, we have that ∇w σ (x) = G ∇k(x − z; σ)w(z) dz, hence

and from the Poincaré inequality (73)

On the other hand, reasoning like in (16) we obtain

which together with (57) and (58) imply

and if σ ≥ 1, then

Applying iteratively (61) to u n we obtain that

with c = c(G, f ). Hence, if we assume σ > c(G, f ), an application of Poincaré's inequality leads to sup n∈N ||u (n) || W 1,1 (G) < ∞ .

Corollary 4.1. Let (u (n) ) n∈N and σ be like in Proposition 4.1. Then: i) There exists a subsequence (u (n k ) ) k∈N ⊂ (u (n) ) n∈N and a function u ∈ W 1,1 (G) such that u (n k ) → u ∈ W 1,1 (G) as k → ∞. ii) u ∈ C and there is a subsequence (u (n k ) ) k∈N ⊂ (u (n) ) n∈N such that u (n k ) u ∈ W 1,2 (G) as k → ∞.

Proof. The first part follows from the first inequality of Proposition 4.1 and the compactness of T. The second part follows from the second inequality of Proposition 4.1.

The discussion above relies on a fixed rather large smoothing parameter σ. Now we construct a particular approximating sequence and first establish a priori estimates which are also valid for small σ.

Recall the quite involved definition of T , where the smoothing parameter σ enters the diffusion tensor D. As a result, it is even not clear whether we have uniform estimates in the class W 1,1 . Our approach in this direction is sketched in Section 4.1.1, where the basic inequality (69) is iterated and leads to a combination of convergent series, provided that a suitable smallness condition holds true. Note that we do not have to establish regularity results on the Neumann part of the boundary, since we localize the mollification procedure under consideration. In Section 4.1.2 we then restrict the operator T to a set M of uniform local W 1,1 -bounds, T : M → M. The existence of fixed points of the iterated operators T n now follows by familiar Leray-Schauder arguments. This provides the background for investigating an iteration of T as a numerical tool in our considerations. The main difficulty is due to the fact that in general (even after passing to suitable subsequences)

This is the reason to consider subsequences of structure u (n j +k j ) and to study fixed points of the iterated operator. The numerical error is estimated by two elementary a posteriori estimates, where the second one gives a clear interpretation of choosing σ not too small.

Throughout this section, σ is some arbitrary (small) fixed positive real number. In particular, σ is not bounded from below by the data of the problem.

Fix some u (0) ∈ W 1,1 (G) (w.l.o.g. suppose u (0) = f on ∂K) and define

In order to make the following a priori estimates more precise, we also recall that there are real numbers c 1 , c 2 , λ > 0 such that for all p, q ∈ R 2 :

We now derive the main tool for the analysis of the sequence {u (j) }:

Fix η ∈ C ∞ 0 (Ω), 0 ≤ η ≤ 1, in particular η = 0 on ∂G − ∂K and observe that for all w ∈ W 1,1 (G), w = f on ∂K,

holds true. With the help of our assumption on D and on account of the minimality of T σ (w) we estimate:

Using the elementary inequality

for all a, b ≥ 0 we further obtain

Thus, it is shown that for all w ∈ W 1,1 (G)

For the kind of mollification introduced above, we recall for all v ∈ L 1 (G) the well known property

However, the discussion of derivatives needs some localized arguments. Once more we recall that the constant occuring in (15) of course depends on σ, i.e. at this point we cannot use (15). Consider η as above and v ∈ W 1,1 (G) such that v = f on ∂K. We have

where we have with an integration by parts

The function η was fixed at the very beginning and we may suppose that supp η Ω Ω. Then, if σ is sufficiently small (depending only on dist (Ω, Ω)), for any

and together it is shown that for all v as above

Now denoting the characteristic function of E by χ E , we pass to the limit η → χΩ , and apply inequality (64) to (∇v) σ andG,G := G ∩Ω, with the result

Recall that (65) merely needs the assumptions σ small w.r.t. dist (Ω, Ω), v ∈ W 1,1 (G) and v = f on ∂K. Thus, (63) yields

Define the constants

and reformulate (66) using (67) and (68) as

which allows us to prove: Theorem 4.1. With the notation of above we have for all j ≥ 2

Proof by induction. For j = 2 inequality (69) implies

which is (70) for j = 2. Now suppose that (70) holds for some j ≥ 2. As above we have for k ∈ N and for given a i ≥ 0, i = 1, . . . k, the elementary estimate

i and again with the help of (69) we obtain Moreover, fix ρ > 0 and suppose that W is a subset of W 1,1 (G) such that for

ii) For a universal constant c not depending on ρ we have i) for any n ≥ n 0 = n 0 (ρ).

Proof. Recalling the version

of Poincaré's inequality, the proof follows directly from Theorem 4.1.

In this subsection we derive the existence of iterated fixed points in a priori local bounded subsets of W 1,1 . In the following let us write T = T σ with a slight abuse of notation.

In order to find a suitable domain M, T : M → M, we first let for any fixed w ∈ W 1,1 (G)

T n (w)

= v ∈ W 1,1 (G) : v = T n (w) for some n ∈ N .

We then fix some U ⊂ W 1,1 (G), where for our purposes we may suppose in the following w.l.o.g. that v = f on ∂K for any v ∈ U. R(n j , k j ) W 1,1 (G) → 0 .

These simple observations lead to the analysis of the operator T n . In fact, if w n is a fixed point w.r.t. T n , w n = T n (w n ) , then we have T (w n ) = T n+1 (w n ) = T n (w n ) + T n+1 − T n (w n ) = w n + T n T − id (w n ) .

Now a given fixed point w n of T n in general is not simultaneously a fixed point of T, although the converse trivially is true. The error v n := (T − id)(w n ) evidently has to enter the left hand side of (71). Note that we then apply the iterated operator T n to v n . This is crucial for the numerical interpretation: Decreasing σ in the kernel appearing in T = T σ means to blow up the error via the non-contracting operator T σ in T n σ which exactly describes the behavior of the examples sketched in the introduction.

To keep our manuscript self-contained, we list three theorems in formulations that are directly applicable to our considerations.

Theorem A.1. (Continuity of the trace operator) Let G ⊂ R N be a bounded open domain with Lipschitz boundary. For any 1 ≤ p < ∞ there exists a bounded linear operator B : W 1,p (Ω) → L p (∂(Ω)) (the trace operator) such that B(u) = u| ∂G whenever u ∈ W 1,p (G) C(Ω). In particular, there exists a constant c, such that

for any u ∈ W 1,p (G).

Proof. Follows from Theorem 3.4.5 of [8] . If u ∈ W 1,p (G) with 1 ≤ p < ∞ is such that u| Γ 1 = 0 in the trace sense, then

for a positive constant c which does not depend on u.

Proof. Follows from Theorem 3.6.4 of [8] .

Theorem A.3. (Leray-Schauder) Let X be a Banach space and T : X → X be a compact mapping. If there exists a positive constant M such that ||T (w)|| X < M for all w ∈ X s.t. T (w) = αw for some α ∈ [0, 1]. Then the operator T admits at least one fixed point.

Proof. See Theorem 11.3 of [5] .

Sobolev Spaces

Image selective smoothing and edge detection by nonlinear diffusion

Two deterministic half-quadratic regularization algorithms for computed imaging

Image compression with anisotropic diffusion

Elliptic Partial Differential Equations of Second Order

Linear and Quasilinear Elliptic Equations

Optimising spatial and tonal data for homogeneous diffusion inpainting

Multiple Integrals in the Calculus of Variations

Scale space and edge detection using anisotropic diffusion

Understanding, optimising, and extending data compression with anisotropic diffusion

Theoretical foundations of anisotropic diffusion in image processing

Anisotropic Diffusion in Image Processing

Tensor field interpolation with PDEs

Germany e-mail: bibi@math.uni-sb

Germany e-mail: cardenas@mia.uni-saarland

Saarbrücken Germany e-mail: fuchs@math.uni-sb

Germany e-mail: weickert@mia.uni-saarland

Clearly, if v ∈ M then v ∈ U or v = T n (w) for some w ∈ U and some n ∈ N,With the additional notationthe same reasoning as above shows for all n ∈ NIncreasing ρ in Corollary 4.2, ii), if necessary, and choosing n 0 sufficiently large, we now chooseSince U is a closed convex subset of W 1,1 (G), the above equality shows the same for M n , and Corollary 11.2 of [5] provides for all n ≥ n 0 at least one fixed point of T n in M n , hence in M n 0 .

The numerical discussion of iterated fixed points is motivated by letting for all n, k ∈ N and for a given u (0) as aboveWith the notation R(n, k) := u (n+k) − u (k)we immediately obtain the first observation:i.e. R(n, k) provides a measure for the failure of u (k) to be numerically detected as one possible fixed point w.r.t. T n .