my
.353
. an”. .. .
an“...

6..
5.. in»
z... 1:.

.4. ft.

 

u..‘uJ&—«'A_»

mm

‘7 1...)? A ll.
'41::

 

 

 

we lllllllllll lllllllilllllllll l’llllllll

3 1293 01688 0464

This is to certify that the

dissertation entitled

Sequential Predictor-Corrector Methods for
Variable Regularization of Ill-Posed Voiterra Problems

presented by

Thomas L. Scofieid

has been accepted towards fulfillment
of the requirements for

EL D - degree in MalhemaflLs.

0&6»me

Major professor

 

Date _Augu51_22_._1228_

MSU is an Affirmative Action/Equal Opportunity Institution 0-12771

 

 

LIBRARY

Michigan State
University

 

 

 

PLACE lN RETURN Box
to remove this checkout from your record.
TO AVOID FINES return on or before date due.

 

DATE DUE I MTE DUE

DATE DUE

 

 

AW

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1198 Wm“

SEQUENTIAL PREDICTOR—CORRECTOR
METHODS FOR VARIABLE
REGULARIZATION OF ILL-POSED
VOLTERRA PROBLEMS

By

Thomas L. Scofield

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements

for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

1998

ABSTRACT

SEQUENTIAL PREDICTOR—CORRECTOR
METHODS FOR VARIABLE
REGULARIZATION OF ILL-POSED
VOLTERRA PROBLEMS

By

Thomas L. Scofield

Inverse problems based on first-kind Volterra integral equations appear naturally
in the study of many applications, from geophysical problems to the inverse heat
conduction problem. The ill-posedness of such problems means that a regularization
technique is required, but classical regularization schemes like Tikhonov regularization
destroy the causal nature of the underlying problem and, in general, produce over-
smoothed results. In this paper we investigate a new class of predictor—corrector meth-
ods for regularization in which the original (unstable) problem is approximated by a
parameterized family of well-posed, second—kind Volterra equations. Being Volterra,
these approximating second-kind equations retain the causality of the original prob-
lem.

Lamm (1995) was the first to place these methods in a generalized framework and

to provide a mathematical analysis of their convergence using approximating equa-
tions which were parameterized by a single numeric parameter to regularize problems
with convolution kernels. Here, we extend the analysis to nonconvolution kernels.
Moreover, we use approximating equations whose regularizing parameter is a func-
tion (rather than a single constant), allowing for more or less smoothing at different
points in the (one—dimensional) domain.

We also introduce another class of predictor—corrector methods, one that employs
a penalty term. Here again our regularization parameter is a function, and the ad-
dition of the penalty term does not significantly alter the regularizing equation that
we solved in the above-mentioned class of predictor—corrector methods. Nevertheless,
its presence provides for significantly stronger convergence theorems in comparison

to those we are able to prove for the first class.

To my patient, loving Wife Pam

iv

ACKNOWLEDGMENTS

I would like to thank my advisor, Patricia Lamm, for the many hours of instruc-
tion, of looking over my ideas, of proposing new directions to pursue (thankfully, none
of them outside of mathematics), and of reading and commenting upon this thesis.
There are many good advisors, some even who will go above and beyond the call of
duty, and then Professor Lamm.

~ The other members of my thesis committee, Professors Dennis R. Dunninger,
Charles R. MacCluer, William T. Sledd, and C. Y. Wang have all been my teachers,
and I have appreciated very much their interest in and dedication to their students
in general and me specifically. Thank you for serving on this committee, for reading
my thesis, and for your input as to its content, presentation and merit.

Many teachers have been instrumental in my development. While there are too
many to name them all, I want to mention Professors Sheldon Axler and Wade Ramey.
They were my teachers at the critical period when I was making the transition from
undergraduate to graduate-level mathematical thinking. The exacting standards they
placed upon me were invaluable in my negotiation of this passing.

Aaron Cinzori, my fellow graduate student under Professor Lamm, listened on
many an occassion to presentations of my work, though often it may have seemed
irrelevant to his own. Thank you for your friendship through this common phase in
our lives, Aaron.

I would also like to thank Steve and Julie Shaw for their friendship and hospitality
to me during my last year and a half as a graduate student, when the two-hour drive
home was too much to bear.

Many are the family and friends who have shown strong support of this endeavor.
You have my sincere thanks.

TABLE OF CONTENTS

INTRODUCTION

1

5

6

The Constant-r Case
1.1 Definitions and Preliminary Equations .................

1.2 Convergence Using Noise-Free Data ...................
1.3 Noisy Data ................................

The Variable r(.) Case

2.1 Preliminaries ...............................
2.2 Convergence Using Abstract Measures .................
2.3 Application to Specific Measures .....................

Penalty Predictor—Corrector Methods
3.1 Motivation for the Method ........................
3.2 Convergence of Solutions .........................

The Discretized Problem
4.1 The Setup ................................
4.2 Conditions for Convergence .......................

Numerical Results

Summary and Future Work

BIBLIOGRAPHY

vi

11
13
16
18

22
22
24
29

32
33
35

43
44
50

60

68

71

Introduction

We consider the scalar Volterra first-kind integral problem: given a suitable function

f(-) defined on [0,1], find u(-) satisfying for a.e. t 6 [0,1]
Au(t) = f(t), (1)
where
Au(t) ;= [0‘ k(t, s)u(s) d3, a.e. t 6 [0,1].

Problem (1) is an important one, having many applications. One is the inverse heat
conduction problem (IHCP), which in the one-dimensional case can be stated as

follows:

Given f (t) in some appropriate space, find it so that the problem

w(0, t) = u(t),
“1(1) t) = f“),
w(:r,0) = 0,

has a bounded solution 21) = w(:r,t) for :1: E (O, oo),t > 0.

When written in the form of (1), this form of the IHCP has a convolution kernel

k(t, s) = K.(t — s), where

—1/4t

_ 1
“m - W

Another application arises from capillary viscometry (see [12]). The integral equa-
tion takes the form of (1) with k(t, s) = 4(s/t)3, a nonconvolution kernel. Here f (the
known function) is the apparent wall shear rate (itself a measured quantity rather
than the true wall shear rate) and the desired quantity, the reciprocal of u(-), is the
viscosity.

It is well-known that in the typical case for (1) where k a non-degenerate square-
integrable function, one has that R(.A) is not closed, and hence problem (1) is ill-
posed, lacking stability. When using measured data, as is the case in the example
from capillary viscometry (and as is typically the case in all applications), direct
recovery of the actual solution is hopeless. One attempts to overcome the problem’s
instability through some “regularization” method.

Indeed, there are a number of regularization techniques. The best-known is
Tikhonov regularization, which amounts to a constrained minimization performed

upon a suitably—restricted set ’D of admissable functions u() G Ll (U a Hilbert space).

The method is usually transformed into the global minimization problem
{gig “Au — In; + aucuné (2)

through a Lagrange—multiplier type approach, introducing a penalty term, the effect
of which upon the computed solution is relegated by the single positive “regularization
parameter” a. Here L : D —> 9 (g a Hilbert space) is a closed linear operator and
H - “f, H - “g are norms in the spaces .7: (the range space of A, another Hilbert space)
and g respectively. If .C is, say, a derivative operator, then increases (decreases) in a

generally cause greater smoothing (roughness) in the computed solution.

The theory of Tikhonov regularization is a highly-developed one (see, for example,
[5]). To give the flavor of the types of convergence results to be proved later for another
regularization method, we (loosely) summarize results for Tikhonov in the following

theorem:

Theorem 0.1 (Tikhonov Regularization) Under classical assumptions, there is
for each a > 0 a unique minimizer aa( f ) of (2). This iia( f) depends continuously
upon f. Moveouer, if f (the “true data”) is replaced by f5 ( “noisy” data) where
Hf” — f|| S 6, then a = 0(6) can be chosen in such a way that ua(5)(f5) —> a as

6—)0.

It is in the sense suggested by this theorem that we say problem (2) is a “regularized
approximation” of (1).

There are undesirable side effects inherent in the application of Tikhonov regular-
ization to our problem. One is that it replaces the original “causal” problem with a
full-domain one. Problem ( 1) is considered causal in that for any t E (O, 1], the solu-
tion u on the interval [0, t] is determined only from values of f on that same interval.

Differentiating problem (2) leads to the necessary condition that the solution satisfies

(A‘A + a£*£)u = A“ f.

This problem is, in fact, equivalent to (2) when ’D = D(£). Yet A“ f is determined,
in general, using data values from the interval [t, 1] (“future values”), thus destroying
the causal nature of the original problem.

Another side effect arises in the usage of a single regularization parameter when a
priori information calls for a solution that is rough in some areas of the domain and
smooth in others (see, for example, Figure 5.2). While newer regularization methods

based on (2) can provide this type of variability in the solution, they do so outside

of the Hilbert space framework, using a norm in g that is Ll-type, resulting in a
non-differentiable problem. Such formulations are, therefore, difficult and costly to
implement.

A different class of regularization methods, “predictor—corrector” techniques, has
been the focus of study in recent years. One of the earliest of these was developed
by J. V. Beck in the 1960’s for application to the IHCP. In this method, Beck held
solutions rigid for a short time into the future (regularized “prediction”) and then
truncated the prediction to improve accuracy (“correction”). More on this method
can be found in [1]. The method is easy to implement numerically and provides fast
results in almost real-time — that is, the causal nature of the original problem is not
badly compromised.

The method of Beck is a discretization of a special case of the more general class
of predictor—corrector methods considered in [9], [8] and [10]. In what follows, we lay
the groundwork for this class of methods.

We will make the following assumption throughout this work.

Hypothesis 0.1 The kernel k(t, s) from (1) is continuous, and can be extended so
that it is defined on 0 S s S t S T for some T > 1. Along with this extension of our
kernel, we assume that f E L2(O, T) is such that there exists a function (necessarily

unique) it E L2(0,T) satisfying (1) for a. e. t E [0, T].

Thus, for a.e. t 6 [0,1] and a.e. p E [0,T — 1], 2) satisfies

[ow k(t + p, s)u(s) ds = f(t + p).

Splitting the left-hand side of this equation up into the sum of two integrals, we have

(after a change in variables)

fotk(t+p,s)u(s)ds+[0pk(t+p,s+t)u(s+t)ds = f(t+p). (3)

Now let us assume that r : [0, 1] -+ (O, T — 1] is a given continuous function and that
77,. is an associated finite positive Borel measure on [0, ||r||oo]. Let us also assume that
for each t 6 [0,1], f (t + p) is nr-integrable (in the variable p). We note that, should
f be just piecewise continuous, then this last assumption is obtained.

On the set of 1],—integrable functions whose domains include [0, r(t)] we may define

the continuous linear functional firm by

Q::_‘r(t)¢ [011% P)(Pd7lr

Applying firm to both sides of (3) we get that it satisfies

r(t)
/ [k (s)t+p, s)pdsdn.()
r(t)

+/0,(¢)/0pu k(t+p,s+t)u(s+t)dsdnr(p) = 0 f(t+Pld77r(P)a (4)

for a. e. t 6 [0,1]. After a change in order of integration in the first term of (4)
(valid by Fubini’s Theorem), we have a term that defines a new integral operator on

L2(0,T), namely
t-
Aru(t) :2 f0 k(t,s;r)u(s) ds, t 6 [0,1],

where

(sass) == [0 "” t(t+p, s) twp), (5)

for O S s S t S 1,r(t) E (O,T — 1]. So now (4) becomes

gamma) ds+ for“) Apk(t+p,s+t)u(s+t)dsd17r(p)
= formf(t+p)dnr(p)s (6)

an equation that is satisfied by a() for a.e. t E [0, 1].

The instability in the original problem manifests itself (as we shall see later in
numerical examples) even when the problem is discretized making it a matrix problem
(hence well-posed). We shall see that solutions of such a discretized system tend to be
highly oscillatory, becoming more so as the stepsize in the discretization shrinks. Our
hope is that some change to equation (6) will yield a new equation whose solution
is not so oscillatory, even though this solution will no longer be a. We further hope
that our new equation will serve as a regularizing approximation of the old one —
that is, its solutions approach that of (1) as the parameter controlling the amount of

perturbation shrinks. In [9], Lamm proposed the following equation in place of (6):

[0‘ in, s; isms) as + a(t; r)u(t) = f(t; r), (7)
where
a(t, r) := for“) [Op k(t + p, s + t) ds dnr(p) (8)
and
f(t; 2) := [0”) f(t + p) dnr(p)- (9)

Here r serves as a functional regularization parameter, with r(t) indicating the length
of a future interval for given t. In [9] the author considered only convolution kernels
with a constant r(t) E r, making (7) a generalization of the equation put forth there.
We can view (7) as a perturbation of (1) in the following way. At a fixed t E [0, 1], if

we divide (7) through by r(t) and consider integral expressions of the form

til—t) [arm ' dnr(p)

to be average values in some sense, then (heuristically) the resulting equation collapses

to (1) as r(t) —> 0. As motivation for the jump from (6) to (7) we may think of (7)

as holding u() constant (temporarily) on a small interval — i.e., u(s + t) = u(t) for
s E [0,p],p E [O,r(t)].

As (7) is a new equation, we must direct our attention to questions of existence
and uniqueness of solutions. If we have assumptions that are sufficient to give that
a(t; r) 76 O for t 6 [0,1] (for instance, k(t,s) > 0 for 0 S s S t _<_ T and a positive
measure that is nonzero on intervals of the form [O,r], for r > 0), then (7) can be

written as the second-kind equation

t...

u(t)+a‘1(t;r)/ok(t,s;r)u(s)ds = a‘1(t;r)f(t;r). (10)

Now if the function

(a—Iu; s)( (fo'm dnr)

is square-integrable (in t) on [0, 1], then using the terminology found in Chapter 9 of

[6],
K(t, s) 2: a‘1(t; r)h(t, s; r)

is a type L2 kernel on [0, 1] (by Proposition 9.2.7) which has a type L2 resolvent (by
Corollary 9.3.16). So, by Theorem 9.3.6, (7) has a unique solution u(-; r) E L2(0, 1)
if a‘1(t; r) f (t; r) 6 L2(O, 1). (Here the references to numbered results all come from
[6]). Incidentally, it is also true that u(s;r) depends continuously in the norm of
L2(0, 1) on f(qr), and hence on f in, say, L°°(0, 1) for example —— that is, (7) is a
well-posed problem. Henceforth we shall assume this well-posedness.

Numerical examples (seen later) seem to indicate that our hope that solutions of
(7) are more well-behaved than solutions of (6) is indeed realized. There is still the
question of whether solutions of (7) are good approximations to those of (6), and the
need for a theoretical justification of the continuous dependence of these solutions

upon data. In [9], Lamm proved the following theorem.

Theorem 0.2 ([9]) Let us assume that the kernel k in (1 ) is a convolution kernel
with k E 61([0,T]) and k(O) > 0. We assume also a constant function r(t) E r
and that f and the measures 1), are such that (7) has a solution u = u(-;r) for all
r E (O,T — 1]. If the true solution a of (1) on [0,T] is in C1, then u(-;r) converges
uniformly on [0,1] to u as r —-) 0. In the presence of noisy data, r = r(6) can be

chosen appropriately for the level 6 of noise so that convergence occurs as 6 —> 0.

In [8], Lamm went on to consider a discretized version of (1), looking at a step
function uAt(t;T; j”) that satisfies (7) with (possibly) noisy data f5 at N = 1/At
collocation points t,- = iAt, i = 1, . . . , N. In this case, both r and At are regularization

parameters. The following theorem was proved.

Theorem 0.3 ([8]) Let k be a convolution kernel in C1 with k(t) > 0 fort 6 [0,1].
Assume that a E W1’°°, that r(t) E r, that f6 E L°°(0,T) and that r is directly

proportional to At. Given a class of measures 77, for which

r(t) == [NH/MW)

(the new right-hand side of ( 7) corresponding to the function fl) is well-defined for
allt E [0,1], 1' E (O,T — 1], the solution uAt(t; r; f6) converges to u(t) at each of the
collocation points t = t,,i = 1, . . . , N as the noise in the data goes to zero, provided

At is proportional to the square root of that noise.

We seek here to extend these results.

In each special case with “noise-free” data f that we consider, we will look at the

difference

y(t; 1") == u(it; 7") - W), t6 [0,1].

of the solutions to (1) and (7) (i.e., the error), trying to show that this difference goes

to zero in some sense as Ieroo —> 0. Subtracting (6) from (7) we have that y(-;r)

satisfies

[at k(t, s; r)y(s) ds + a(t; r)y(t)

r(t) )0
A [0 k(t + p, 3 + t) [11(3 + t) - fl(t)] d3 d17,.(p),

for a.e. t 6 [0,1]; or, still assuming that a'1(t; r) exists for each t, y(~; r) satisfies

y(t) = —s-1(t;r)/0‘Is(ts;s)y(s)ds+F(t;s), (11)

where

F(t; r) :2 a"1(t; r) form [0p k(t + p, s + t) [u(s + t) — u(t)] ds d7},(p).

We will use equation (11) — the equation solved by y(-; r) —— throughout in showing
that y goes to zero with Hrlloo.

We have assumed throughout the discussion thus far that (1) is a scalar equation.
Nevertheless, the entire analysis to this point can be generalized to vector equations
with very little change. Our arguments in the chapters that follow will not be so
easily generalizable, and we will continue to assume a scalar equation.

Finally, to motivate the need for a specialized argument like the one involving an
approximate identity to be found in Chapter 1, we note that if our (“true”) data f is

such that the “true solution” a E C1[0, T], and if k(t, s) > O for O S s S t g T, then

 

(F(t:s)( _<_ am [rm/u t+p,s+t) Is(<.(s))(sdsdn.(p)

..(_)I[%_/Or(t)/Ok( (t+p,s+t)d3d77r(.0)

= 00(0),

|/\

10

and thus

l|F(';r(°))ll S 0(H7‘lloo)-

It might appear, then, that an immediate application of the Gronwall Inequality to
(11) will show that our error goes to zero with [lrllw This would indeed be the case

if we had a uniform bound on
lf(t, 8; r)
u(t; 1")

 

 

as Ilrlloo —> 0. Nevertheless, a close inspection of this expression shows that it is
not reasonable to expect such a bound. For instance, when dnr(p) E dp (Lebesgue
measure) and k(t, s) E 1, we have

k(t, s; r) _ 2

a(t; r) — r(t).
Therefore, it will be necessary to perform a more in-depth analysis upon the error to

show that it goes to zero.

 

CHAPTER 1

The Constant-r Case

First we work to extend the results of [9] to nonconvolution kernels. To obtain results
throughout this paper, we will require assumptions on 7),, k, a, f and f5. The
following will suffice for this chapter, and will be standing assumptions even when
not explicitly mentioned. Often we will require similar, or even identical hypotheses
in other chapters to the ones we state here. When identical, we will simply refer back

to these by number.

Hypothesis 1.1 We assume that Hypothesis 0.1 holds, that k E C1([0, T] x [0,T])
and that k(t, s) > O for O _<_ s _<_ t g T. We also assume that a 6 Cl([O,T]). Having
assumed these, it is without loss of generality that we further assume k(t, t) = 1 for
t E [0, T], for problem (1 ) can always be divided by k(t,t) yielding a new right-hand

side f (t) / k(t, t) for which the above assumptions hold.

Hypothesis 1.2 The measure 1),, parameterized by r > O is a positive finite Borel
measure on [0, r] satisfying the following condition: if we have a positive integrand

g(t) > 0 fort E (0,r], then we require

[’90) ds,.(p) > 0.

When r is a continuous function on [0, 1] into (0, T— 1], we assume 7), to be a (single)

11

12

associated finite positive Borel measure on [0, llrlloo] for which

[0“ g(t) dn(p) > o,

for all x E [rm-n, [eroo], where rm,” :2 min{r(t) : t 6 [0,1]}.
We further assume that, for a measure 77,. of the variety described above, we have

that the quantities

for“) dm 0
0(t; r) u(t; 1‘)

 

are square-integrable on [0,1], where a and f are defined in ( 8) and ( 9) respectively.

Hypothesis 1.3 When noisy data f6 is used in place of f, we assume that f6(t) =
f(t) + d(t), where d(-) E L°°(0,T) satisfies Ildllc,o S 6 for some fixed 6 > 0 (here
I] - “0° denotes the L°°(0, T) norm). For n, a family of measures parameterized by
r E (O,T — 1] and satisfying Hypothesis 1.2, we assume that f; d(t + p) dn,(p) is
well-defined for all t 6 [0,1], and that

f; f‘(t + p) dnr(p)
u(t; 1")

 

is square-integrable ( in t) on [0,1]. If the measures are parameterized by continuous
functions r : [0, 1] —> (0, T — 1], we assume that for“) d(t + p) dnr(p) is well-defined for

allt 6 [0,1] and that

for“) f“(t + p) dos-(p)
d(t; r)

 

is square integrable on [0,1].

As in [9], we will assume in this chapter that r(t) E r (constant) for t 6 [0,1].
Notice that Hypotheses 1.2 and 1.1 together imply that (7) has a unique solution
u(-; r) E L2(O,T). The goal in the remainder of this chapter is to demonstrate the

convergence of u() solving equation (7) to the solution a of ( 1) in the case of r(t) = r

13

a constant. We will do this in the absence of noise in the data, and also for the case

of noisy data.

1.1 Definitions and Preliminary Equations
For t 6 [0,1], r E (O,T — 1] let us define

2 f6“ ft’ [pD1k(t + 6. t + C) + sD2k(t + at + 6)] ds dnr(p)

a. ‘ )3" fl’ ds ds,-(p) ’

 

(1.1)

where, for each fixed t 6 [0,1], (p,s) E [0,T—1]x[0,T—1], 5 = £t(p,s) and C = (r(p, s)

are chosen by Taylor’s Theorem so that

k(t + p, s + t) = k(t,t) + lek(t + {,t + C) + ngk(t + £,t + C). (1.2)

Because we assume that k satisfies Hypothesis 1.1, we have that

f6 lite + 8) d8 dvr(p)
ii If d8 dnr(p)

 

[18t,r[

|/\

llkllim

27"llklliss

|/\

0(7‘),

uniformly in t E [0, 1].

Now for r small enough that Iflw] < 1, we have the expansion

 

 

 

 

1 1
d(t; 7‘) z for $196+ )0, s + t) d8 date)
1
_ it it [k(t, t) + lek(t + t, t + C) + sD2k(t + t. t + 4)] d8 dnr(p)
1 1
— for if d8 dnr(p) ' 1+ fit.)—
1 + 7hr

: f6 pdnr(p)’ (1'3)

M

where 7” = 0(r) uniformly in t E [0,1]. Employing another Taylor expansion, we

have from (5) that

k(t, s; r) = [or [k(t, s) + pD1k(t + 5"”, 3)] dnr(p)

= Mtfi<fldm)+flb$fl,

where

(g(t,s;s)( 3 (til... [0 ptsrv)

forallOStSl.

With these definitions, we write equation (11) (the equation in the error y(t; r) =

u(t;r) — u(t)) as

y(t) = —f———01p2;77:’(p)r / k t, s; r) s);ds+F(t r)
—f0—,1pi;1;—:’(;)—)[(/0 (1%)]: k( (t,s)y(s)ds+[otg(t,s;r)y(s) ds
+F(t; r). (1-4)

Employing a technique used in [9] we define

Q Ht<0
¢U¢M= (LO
ift/E, ift Z 0,
f’pdnr p
8(1‘) 2: —--—————° for d77( ),

and convolving both sides of equation (1.4) with w(t, e(r)), we get

/t(t—ss()) )ysd()s

f0 Pd717———r_(p) )/o¢(t ())/0 (1 + ’Yr,r)9(r, s;r)y(s) d3 dr

15

3173/0 ’i/J( t — r, 5(7‘ —:)/(:( (1+ '77,.)k(, s)y(s) ds dr + w(t,e(r)) * F(t; r)

— f0 Pd717r(,0 )/o /¢(t ))(.1+’Y~rr)g(7',8;r)dry(s) d3
_—/0 f 1M t — r,5(r 1+ 71,.)k(r, s) d7“y(3) d3 + l/l(t,€(7‘)) * F(t; 7.)
lo Pd77(p )/o l. W (t‘ T 5(7" 1+ 77,r)g(T73;T) 6179(3) d8

t
1 [0 [k(t S)_e_ (t- s)/s(r)k(8 3)_/ e—(t—r)/€(r)D1k(7-,3)d'r y(s)ds

_J)
(1.6)

——/0 / w(t ))71rk (r, s)dry(s)ds+t/J(t,e(r)) at F(t; r).
Subtracting equation (1.6) from equation (1.4) we get

y(t) = Katmai/(3)013 + H1(t;r), t 6 [0,1], (1.7)
where we define the quantities
O S s S t S 1 (1.8)

C(t, s;r) z: Gl(t, s; r) + 02(t, s; r),

with

G1(t,s;r) :: g(t — s,e(r))[1—k(s,s)]—/stw(t—r,e r

G2(ta3i7‘)
._ W [ft—T 1))( (t— 7' €(T))(1 + 77¢)g(7', S; 7‘) 617' — (1+ 7t,r)g(t13;T)

+—[/. «f(t )),7rrk (T8)dT-%,rk(t,8) ,

16

forogsgtgland

H1(t;r) 2: F(t;r) — w(t,5(r)) =1: F(t;r), t E [0,1].

1.2 Convergence Using Noise-Free Data

We wish to show that solutions of (7) do well in approximating solutions of (1) as
the equations themselves become more alike — that is, as r —> 0. This, along with
the results in section 1.3 will justify the solving of (7) as a regularization scheme for
(1).

We begin by assuming that the data itself is free of error. Though this is not
likely to be the case in numerical representations on a computer, this is a good first
test-case, as we could never hope to have convergence in the noisy-data case if we
did not have it in the noise—free one. Furthermore, even in those rare instances where
the true data can be represented exactly numerically, the numerical solution process

itself will introduce errors that call for some stabilizing scheme.

Theorem 1.1 Let fink, f and a satisfy Hypotheses 1.2 and 1.1. If there exists a

constant C' 2 1 for which

r T 1'
dr >_/dr)
fopflpLC 0 77

for each r > O sufficiently small, then the solution u(-;r) of (7) converges uniformly

on [0,1] tou asr—->O.

To show (ultimately) convergence of y to zero as r —> O, we will use the Gronwall
Inequality on equation (1.7). We will show that Cl and G2 have uniform bounds

(independent of r,t and s), and that H1 —> O uniformly.

17

Proof of Theorem 1.1: First, we have that

t
[G1(t,s;r)] g /w(t-r,e(r))|D1k(r,s)]dr
8
t
||k||1.00/e—(t-r)/e(r)d7.
8 7' s

= llkll1,oo(1 _ e-(t-8)/E(r))

-<— “killpo
for O S s g t g 1.
Next, we see that
|G2(t, 3'7‘)|1
S )[fslliitrjg )(1+ Tr r,;srdr+l+ , t,;sr
f‘0—— ””1”“ l7 |)|.9( )l ( In |)|9( )l
+—’l‘ )[)/st( w“ [Wrr]k(, 3)dT+ [7t,r]k(t,8)]

s (list... [A t( (t— s,s(r))(1+ (Md. + (1 + mm]
$31—39 [f s(t - mew...) ctr + ml]

5 2mm)... [1+ [3‘ so: - new) ctr] + 1%][ut— s,s(s))(s.,.( ts +17...)

for small enough r, since 7),. = (9(r). Now by assumption we have

so that [77,r]/€(T) 3 C1 for some Cl > 0 independent of r. Thus,

(02(t,s;r)l s (2((k((1,..+clnt((..) [1+ [ts-newss-

< 2(2 + Cl)llkl|1,oo,

18

for O S s g t S 1. Thus GI and G2 (and hence G) are bounded uniformly in
Ogsgt31,r>0asr—)O.
Since a E C1[0, T] we argue similarly to the argument found near the end of the

introduction that, for each t E [0, 1],

|F(t;r)| S s+t)l’t‘1(8+t)-’l1(t)ldsdt7r(p)

               

.__ Hf] Hp,s+t)(u(<t(s))(sdsdn.(p)

S rIIfltII°°//olc( (+p,8+t) dsdnr(p)

_ Tllfl’llooa _
" u(t;r) (t’ I
= 0(7‘),

 

 

which shows that ||F(-, r)||00 = (9(r). Thus,

t
[H1(t;r)| s (IF(-,r)((.. [1+ [0 t(t — s,s(s)) dr
_<_ 2||F(',7‘)||os
= 0(r).
The theorem is now a trivial consequence of the Gronwall Inequality. 2

1.3 Noisy Data

If our data has noise in it then recovery of the “true” a (corresponding to the true f)
becomes hopeless because of the instability of problem (1). In fact, it is likely that

(1) has no solution when f is replaced by a function f6 satisfying Hypothesis 1.3, as

 

19

f" need not be in 72(A). In contrast, for this function f " we can define

f"(t;r) := [hummus/)),

and have that

a(t;r)u(t)+/0tk(t,s;r)u(s)ds = f"(t;r), (1.9)

— equation (7) with f5 in place of f —— has a unique solution u"(t; r) E L2(0, 1).
If we denote by y" the error y" (t) = y" (t; r) := u6(t; r) — u(t), then we find that

y" solves an equation analogous to (11), namely

~

1
y(t) = —m/Ok(t,s;r)y(s)ds+F(t;r)+E(t;r), (1.10)

a.e. t E [0,1], where

E(t; r) 2:

 

as...) /.'d(t+s)ts(p), te [0,1].

Let us define

km,” :2 min{k(t, s) :0 S s S t S T}.
Then

< f6 |d(t + p)| date)

" it ft k(t + as + t) dsdnAp)
”dlloo . it” do.-

kmig f(I Pdflr (,0)

< —— t 01.

|E(t;r)|

 

 

S

20

Convolving (1.9) with w(t, E(T)) and subtracting as before we get that
f(t) = [OI GU, 8; “Flt/6(3) d8 + H(t; T),
where H(t; r) z: H1(t; r) + H2(t; r) with
H2(t; r) 2: E(t;r) — w(t,5(r)) * E(t;r), t E [0,1].

Here G and H1 are as in the last section. Now

 

[H2(t;r)| = [E(t;r)—/0t1/2(t—s,5(r))E(s;r)ds
s (IE(-;r)n.. [1 + [its — s,s(r))ds]
25
S m, t€[0,l].

Thus, if r = r(t)) is chosen so that the quantities

6 _ Jfédnr

e(T) — Iii/16111410)

and r(6) both go to zero as 6 -—> 0, then, since we have H(-) (in place of H1(v))
converging uniformly to zero on [0,1], the argument used to prove Theorem 1.1 still

goes through; that is, we have the following result.

Theorem 1.2 Let 77., k,f, f" and a satisfy Hypotheses 1.2 — 1.3. Suppose also that,

for some C 2 1, the r], satisfy the condition

for/1610.032 é/Ordnr

 

21

for all r > 0 sufficiently small. [fr 2 r(6) is chosen so that both r(6) ——> 0 and

for“) d77r(6)
r 6
foI I Pdnr(6)(,0)

 

as 6 —> 0, then the solution u6(t; r) of (1.9) converges uniformly to a on [0,1] as

6 -—> 0.
We have the following simple corollary.

Corollary 1.1 Let us assume the conditions of Theorem 1.1. If for fixed p E (0,1),

01 > 0 we take r(6) 2 C36”, then u6(t; r) -—> a uniformly on [0,1] as 6 -—> 0.

Proof of Corollary 1.1: Since p E (0,1) it is clear that r((S) —) 0 as 6 —+ 0.

And by assumption we have

asb-—>0. 2

What this theorem and corollary demonstrate is that, in the presence of noisy data,
r cannot be allowed to go to zero too quickly. It must be tied to the level of noise
in the data, providing an adequate level of regularization appropriate for the amount
of noise present. Apparently, the instability of the original problem (1) begins to
manifest itself in the perturbed problem (1.9) as the regularization parameter r ——> 0,
and it is necessary to relegate the extent to which this happens in relation to the
exactness of the data. This is the same kind of phenomenon that is suggested in

Theorem 0.1 concerning the regularization parameter a for Tikhonov regularization.

 

CHAPTER 2

The Variable r() Case

In Chapter 1 we extended the results of [9] to cover nonconvolution kernels. While
this is a significant step, we have our sights set upon more. In particular, our goal is
to extend the method to accommodate a function r() that varies throughout [0,1],

allowing for variable amounts of regularization.

2. 1 Preliminaries

We will use the symbols rm,” and rm“. (or ||r||oo) to denote the minimum and maxi-
mum values of r() on the interval [0,1]. When rn is one in a sequence of functions,
we denote these values by rmmin and rum,” respectively.

For a fixed function r(-) we define

Using this notation, we can write

k(t, s; s) = )0”) (k(t, s) + pate + asp), s)) dn.(p)

= ao(t;r)k(t,8) + form PD1k(t +€s,s(p),8) rim-(p)- (2-2)

22

 

23
It can also be shown exactly like in (1.3) that

l _ 1+')'(t;r)

 

 

 

 

 

 

 

Ct(t; T) _ a1(t;r) (23)
where 7(t;r) = O(r(t)) _<_ 0(Tmax) for t E [0,1].
Using these estimates, we write
k(t,s;r) _ a0(t; r) .
d(t; r) — a(t; r) k(t, s) + D(t, s, r)
_ 00(t; T) 00“; Tmin) (“y(t; Tmin)[1 + If(t; rmin)l ,
_ (d(t; r) —————a(t; Tmin) + a1(t; rmin) k(t, s) + D(t, s, r)
= A(t, s; r) + B(t, s; r) + C(t, s; r) + D(t, s; r),
where
“D(tirmin)
. 3: .4
A(t, s,r) a.(t;sm..)“t’3)’ (2 )
ao(t;r) ao(t;rm.-n)
. ,2 _ __ 2.
B(t, s, r) (d(t; r) a“; Tmm) ) k(t, s), ( 5)
00(t; Tmin)7(t; Tmin)
. ,2 2.
C(t, s,r) 01 (t; Tm") k(t, s), ( 6)
Dt- -— I “no“ () d() (27)
(737T) '— m 0 P1(+€t,sP,8)7irP, '

each defined for 0 S s g t g 1. Thus, we write the error equation (1.10) in y6(t)

u5(t; r) — u(t) as

y(t) = — [OI [A(t, s; r) + B(t, s; r) + C(t, s; r) + D(t, s; r)] y(s) ds

+F(t; r) + E(t; r) (2.8)

for t E [0,1].

24

We choose to break down B further, writing it as

 

 

01(t; T) (11(t;7'min)
= [131(t,s;r)+ Bz(t, 8; r) + Ba(t, 8; 7)] k(t, 8),

B(t,s; r) : (a0(t;r)[1+ y(t; r)] a0(t;rm,,,)[1 + y(t; rmin)]) k(t, s)

where, forOS sgtg 1,

r(t) d
WW) ,Z 1.42.

a1(t;7‘)

1 1

B t ; := t; min ——-—__ I
2(137') “OI T )(a1(t;r) al(tirmin))

a0(t; 7‘) ao(t; Tmin)
Bt; Z=——t; -_ timin-
3(13T) al(t;7°)7( T) 31(tifmin)7( 7' I

We intend to convolve the equation (2.8) with w(t,e) defined in (1.5), as in the
proof of Theorem 1.1. In that proof it became clear that, when g() is a bounded

function on [0, 1], then so is

[W - r,t)gmds,

for O _<_ s S t S 1. The first issue, then, will be to get conditions sufficient for a
uniform bound (in t, s and r()) on as many of the elements of the kernel in (2.8) as

possible — namely, on B, C and D.

2.2 Convergence Using Abstract Measures

In Chapter 1 we had a numeric parameter r which served as regularization parameter,
with r ——) O, and to each such r we associated a measure 77,. In this chapter we replace
the constant parameter r with a function r(-), and we will talk about sequences of

such functions going to zero. As before, we associate a single measure 7), to each

 

25

(fixed) function r : [0, 1] —> (O,T — 1].
To show the boundedness of the various quantities in the last section, we will
need to make several assumptions about how the sequence of functions (rn()) and

the associated measures 77,” are chosen.

Hypothesis 2.1 We assume that (rn()) is a sequence of continuous functions on
[0, 1] into (O,T — 1] converging uniformly to 0 as n —+ 00, and that the associated
sequence of measures (1),") is such that 77,." satisfies Hypothesis 1.2 for each n =
1,2,. ... We assume further that these sequences are chosen to satisfy the following

conditions:

(i) The sequence
fIIrnIIOOd

7'71 mm

for“ "“" pdnr..(p )

 

is bounded.

(ii) The sequence
IIrnIIoo dnrn

0""0 "‘"‘ )0 dnr. (p)

 

ll nlloo
is bounded.
We can now prove the following theorem.

Theorem 2.1 Assume that k, f and a satisfy Hypothesis 1.1. Suppose we have a
sequence of continuous functions rn : [0, 1] —> (O,T — 1] (so rmmin > O for each
n) converging uniformly to zero and (77,") is a corresponding sequence of measures

satisfying Hypothesis 2.1. Then u(t; rn), the solution of

fotk(t,s;rn)u(s)ds+oz(t;r,,)u (t)=f f;(t Tn),

converges uniformly to a on [0, 1] as n —> 00. Moreover, if f 5" satisfies Hypothesis 1.3

for (6,, ), a sequence of positive numbers converging to zero, then the solution it" "(t; r")

 

26

[OI k(t, s; rn)u(s) ds + d(t; r,,)u(t) = [OIIIIII f6n(t + p) dry,“ (p)

converges uniformly to it on [0, 1], provided that r,,(-) = r,,(-; 6”) is chosen so that the

quantities

fIITnIIoo d,” 771‘s;

I" Tn. min W 0
f0 pdnrn(p )

 

and ||rn||oo —+ 0 as n —> 00.

As in chapter 1, the first assertion is really a corollary of the second, arising from
the special case where 6,, = 0 and E (t; r,,) E 0 for all n. Note that, in that instance,
the condition about rn(-, 6”) being chosen to have the expression above converge to
zero is really no condition at all. Thus, we will prove only the second assertion.
Throughout the proof we will suppress the n, writing simply r or r() for a function
that comes from the sequence. Whenever a bound is asserted, it will be emphasized
that this bound is independent of 71..

Proof of Theorem 2.1: We know that the difference y(t; r) = u(t; r) — u(t)

satisfies (2.8). Taking
0.1(t; Tmin)

5 = E Tmi = ,
I II) 0003; 1‘min)

(note that 5(rmm) is independent of t) we convolve (2.8) with w(t, E(rm,,,)) to get

(It/(t — s s )
_ k(_7_',__ s ,r) . .
_ / 1))(t 7150;” T—)— y(s)dsdr+7,b(t,e) 1 [E(t,r) + F(t,r)]
= —/oI [I 1))(t k(II Ic)7(r8Ir'I))dT y(s )ds+1b(t,e)*[E(t;r)+F(t;r)].

Subtracting this equation from equation (2.8) we get

y(t) = [OI C(t, s; r)y(s) ds + H.(t; 7) + H2(t; 7). (2.9)

 

27

where

G'(t, s; r)
:= f: w(t — r,€)[A(r, s; r) + B(7', 3; r) + C(r, s; r) + D(r, s; r)] dr

+2/2(t — 3,5) — A(t, s; r) — B(t, s; r) -— C(t, s; r) -— D(t, s; r) (2.10)
and

H1(t;r) := F(t;r)—i,b(t,e)*F(t;r), (2.11)

H2(t;r) := E(t; r) — w(t,e) =1: E(t; r), (2.12)

for t E [0,1].

As mentioned earlier, the boundedness of
t
B(t,s; r) —/ 1))(t — r,e)B(r, s; r) dr

hinges upon the boundedness of B itself, which in turn rests upon the boundedness

of B1, 82 and 83. We have

Tmuz d 1'
Bl(t13; 7.) S rizrm T, i
0 )0 dnr (p)

 

which is bounded (uniformly in n) by Hypothesis 2.1(i). Next we have

. _ Tmin Lit: Pdllr (p)
[3205, S, r)] — (/0 dTlr) (fJIIIPdnr(p))( ormin pdanPll

( gendn. r )( f.',;':;'dn. )
Jm‘"pdnr(p) "III Jm‘“pdnr(p) I

the first factor of which is bounded by Hypothesis 2.1(ii), and the second factor by

 

 

 

 

28

 

(i) (both uniformly in n). To get, finally, that B(t, s; r) is bounded, we have

frmaz dnr

B(t,s;r _ r
I I II o'""‘pdnr(p

 

) I‘llt; 7) + ’70:; Tminll a

which is bounded (uniformly in n) by Hypothesis 2.1(ii) and the fact that there exists
a Cl > 0 for which |'y(t; r)] S Clrmax uniformly in t E [0, 1], n = 1,2,. . ..
One shows that C(t,s;r) has a uniform bound independent of t,s and r (one

bound for all n) just as we showed it for B3. For D, we have

1+ (t,r)
(D(t.s.s)( s ——"’t——'0III’ plel (,p,t+t..() s)(tn.(p)

|/\

IIkII1,ooI1 + l7(t; r)|l.

which shows that D also has a uniform bound in t, s and r independent of n.
With A(t, s; r) = %k(t, s), we perform an integration by parts (details like those
11 (1.6)) to get

 

w(t — s, e) — A(t, s; r) + [I w(t — r,€)A(r, s; r) (17'

 

[I w(t — r, 5)D1k(r, 3) dr

S ||k||1,oo-

 

 

Thus, our kernel G is bounded (uniformly in t, s and r, independent of n).
One shows that H1(t;r,,) goes to zero uniformly as ||rn||oo —-> 0 just as it was
shown in the constant-r case for Theorem 1.1. Also, as in the constant-r case, the

expression
form .7110: dnrn
fo ""“"pdnr.(p)

comes out of looking at the bound on H2(t; rn), and the convergence of this expression

 

to zero is a sufficient condition to get that ||H2(-; r,,(-))||,,o —+ O uniformly as 6 —+ 0.

29

Now the result follows from the Gronwall inequality. 2

Theorem 2.1 is, in fact, a generalization of Theorems 1.1 and 1.2. For, if each
rn(-) is a constant function, then the terms of the sequence in Hypothesis 2.1(i) are

all zero. Also, (ii) reduces to the condition

7‘ tr 1"
dr >—/ 1')
fopn(p)_c 0dn

stated in Theorem 1.1.

2.3 Application to Specific Measures

As an application of theorem 2.1, suppose that, for each continuously differentiable
r : [0, 1] —> (O,T — 1] we take 77, to be a weighted Lebesgue measure of the form
dn,(p) = w(p)dp, where we assume that w : [0,T — 1] ——> (0,00) is in L°° with
0 < wmin _<. w(p) S “cellos, for P E [0,T - 1]-

Suppose now that r() = r,,() is one in a sequence of continuous functions sat-
isfying Hypothesis 2.1 with associated measure as described above. Looking at the

expression from condition (i) in that hypothesis, we see that

Irma: LU(p) dp < 2IIC‘JIIOOIIrmax _' Tmin)

rmin

form" WIP) dp — wminrrInin

 

Thus, condition (i) under these types of measures comes down to the existence of

some M1 > 0 (independent of n) for which

Tn,max '— Tn,min S All?"2 (213)

n,min ’

for all n.

 

30

From Hypothesis 2.1(ii) we take the expression

It“: w(p) dp T < 2llwlloor3n...
.IIOIImIII ”(pl dp — wminrgm'n

 

Hence condition (ii) requires that there be an M2 > 0 such that

M < M2 (2.14)

Tn,min

for alln= 1,2,....

We thus have the following corollary.

Corollary 2.1 Assume that k, f, it and r,, satisfy the conditions of Theorem 2.1, and
that dnrn = w(p) dp for each n as described above. If there exist constants M1, M2 >
0 so that the conditions in (2.13) and (2.14) are satisfied for all n, then u(t;rn)
converges uniformly to a on [0, 1] as n —-) 00. Moreover, if f"" satisfies Hypothesis

1.3 for (6”), a sequence of positive numbers converging to zero, then the solution

“In (t; Tn) 0f
[OI k(t, s; r,,)u(s) ds + d(t; rn)u(t) = [OIIIIII f5n (t + p) dry," (p)

converges uniformly to a on [0, 1], provided that r,,(-) = rn(-; 6,,) is chosen so that the

quantities

5nII7In(';6n)IIoo

2
Tn,min

—>0

 

and ||r,,(-;6,,)||oo —> 0 as n —> 00.

The condition in (2.13) deserves some scrutiny. It says, basically, that the func-
tions rn are becoming constant at the square of the rate at which they are converging

to zero. The convergence proved in Corollary 2.1 is asymptotically the same type of

 

31

convergence as proved in Theorem 1.1. Nevertheless, for 6 > 0 (which is generally

the case), r() need not be constant.

CHAPTER 3

Penalty Predictor—Corrector

Methods

In Chapter 2, we proved a convergence result for the class of predictor—corrector
methods that has been the main focus of this work so far. While some conditions
under which this convergence was shown are quite general — the main one being
that r(t) is allowed to vary, providing varying amounts of regularization throughout
the domain — others were somewhat limiting. While not ruling out the use of truly
variable r(-) in the (usual) case of noisy data, Hypothesis 2.1(i) seems to limit the
variation allowed in the (functional) regularization parameter r(-), at least in the limit
as the noise level converges to zero. In fact, as seen in Corollary 2.1 for a particular
choice of measure, the limiting behavior of r() must be, in some sense, like a constant.

The goal of obtaining convergence results under less stringent conditions on the
sequence r,,(-) of functions remains an open problem. Motivated by this, we explore a
new class of regularizing methods that we dub Penalty Predictor—Corrector methods
for their similarity to the earlier class. In contrast to the results in Chapter 2, we
find for this new class of methods that we do not need to constrain the variation on

the regularization parameter r() as the noise level goes to zero.

32

33

3.1 Motivation for the Method

Let us assume for the moment that, at some fixed t E [0,1], r(t) > 0 and u() is
a known function on [0, t). We assume also that u(t; r) > 0. We may then seek a
constant c that solves

r(t) 2
mm /
cER o

foIk(t+p,s)u(s)ds+c/opk(t+p,s+t)ds—f(t+p) dp

 

+c2p(t; r). (3.1)

This minimization problem harkens back to equation (2), where the set D consists of
constant extensions of u(), and the norm in .77 is an LZ-norm on [t, t + r(t)]. Taking

% of this expression, we get the necessary condition on a solution c that

[[0,—(t) [0” k(t + p, s + t) ds w(t, p) dp + (u(t; 7.)] c

+ [OIIII [OI k(t + p, s)u(s) ds w(t, p) dp = [OIIII f(t + p)w(t, )0) dpi (3-2)

where

p
w(t,p) :=/0 k(t+p,s+t) ds.

For the moment, let us say that this process has been carried out at t = t,-. This
solution c is, in the sense of Tikhonov regularization, the best constant to represent
u() on the interval [t,, t,- + r(t,)]. In [11], the authors deal with a discretization of the
problem and, under supposition that r(t,) = rAt for some integer r > 0, they find the
best step function (represented as a vector in R') to approximate u() on [t,, t.-+r(t,-)].
They follow this prediction of the solution into the future with a correction, retaining
only the first component of this vector as the value of the approximate solution 721(3)
on [t,, t,- + At] and discarding the rest of the vector. Because theirs is a discretization

of the problem, they can move on to the next ‘t’-value, namely t,-+1 = t.- + At and

34

repeat the process on the interval [t,+1,t,-+1 + r(t,+1)]. As At shrinks, the retained
value from the vector is used in the definition of it on correspondingly shorter intervals
at each step.

We are considering the full continuous problem. Following after the discussion in
the last paragraph, we might (in the limit) take our approximation u(t) = c (just at
that particular t value). Identifying u(t) with c, then, (3.2) becomes (after a change

in order of integration)

[fOIIII [0p k(t + p, s + t) ds w(t, p) dp + u(t; r)] u(t)

t r(t) r(t)

which is a special case of the more general equation

[form [0" k(t + P, 3 + t) ds dnt,,(p) + u(t; r)] u(t)

+ [OI foIII) k(t + 10.8) d771,r(10) 21(8)“ 2 foIIII f (t + p) d777,.(p).

If we define a(t;r),k(t,s;r) and f(t;r) using (8), (5) and (9), respectively, corre-

sponding to the measure m, (for each t E [0,1]), then this equation becomes

foIIII’SiIII‘ISId“ WW) +#(t;7‘)IU(t) = f(tn‘), (3.3)

an equation that closely resembles (7). The appearance of the new function u(t; r)
has to do with the difficulties we encountered in the variable-r(t) case. If we make
a wise choice for this )1 — say, one that when added to u(t; r) makes for something
like a constant (in t) coefficient c = c(r) of u(t) (of course, not so much of a constant

that we lose the benefits of our function r(-) over the constant parameter r used in

 

35

Chapter 1) — our hope is the solution of (3.3), or of

[OI k(t, s; r)u(s) ds + c(r)u(t) = f(t; r), (3.4)

(assuming that one exists) will converge to the solution of (1) as r,,(-) —> 0, and that

it will do so under less stringent conditions than those we required in Chapter 2.

3.2 Convergence of Solutions

In the last section we motivated a new penalty predictor-corrector type method. We
proposed the introduction of a function u(t; r) into the perturbed equation of the
predictor-corrector methods we studied earlier, hinting that we could do so in such
a way as to give ourselves a new perturbed equation in the classic second-kind form
— that is, where the coefficient of the u(t)-term was constant. As we shall see, the
function )2 that we will use in the results of this chapter is not actually intended to
make this coefficient into a constant. Here, rather, we have chosen )1 so that the
problem reduces to one quite similar to the one we analyzed in Chapter 1. The
comparison of equation (3.1) to (2) together with results from earlier chapters should
make us expect convergence in the noise-free case only as r(-), and simultaneously
p, go to zero. We may also expect that, in the presence of error in the data, both
functions must somehow be tied to the amount of error in order to get convergence
as the error goes to zero.

For this reason, it is reasonable to tie the two parameters together. Let p E
(O, 1 / 2]. Given a continuous function r : [0, 1] —> (0, T — 1] and a finite Borel measure

77, on [0, |[r||oo], we will set

r(t)
u(t;r) == llt‘ll’éo 0 dm- (3-5)

36

With this definition for u, it follows again from the results in [6] to which we referred
in the introduction that equation (3.3) has a unique solution u(t; r) if Hypotheses 1.1

— 1.2 are met with d(t; r) + u(t; r) in place of d(t; r).

Theorem 3.1 Suppose that k satisfies the assumptions made in Hypothesis 1.1. As-
sume that f is such that a continuous solution a of (1) exists on [0,T] with 11(0) = 0.
Let (rn()) be a sequence of continuous functions with r,, : [0, 1] —) (O,T — 1], r,, ——> 0
uniformly, and assume that the measures 17,.“ satisfy Hypothesis 1.2. If u(t;rn) is
given as in (3.5) (where r,, replaces r), then the solution u(t;rn) of (3.3) converges

uniformly to u(t) as n —+ 00.

To prove this theorem, we will need a lemma, the truth of which is asserted in
[3] but not proved there. It asserts that our function w(t,e) defined in (1.5) is an

approximate identity in the space C ([0, TI), at least in a certain sense.

Lemma 3.2 Suppose that g : [0, T] —+ R is a continuous function satisfying g(O) = 0.
Then

was) . g(t) == [OI t(t — s,s)g(s) ds

(w as defined in (1.5)) converges uniformly to g(t) on [0, T] as 5 -—> 0+.

The proof is fashioned after that for a similar assertion in [4]. Because we want
to use the variable 5 in another, more traditional sense during this proof, we elect
to use the symbol 7) (in no way related to the measures called by the same name in
other parts of this work) as the second argument for the function 11).

Proof of Lemma 3.2: . Let 5 > 0. By the uniform continuity of g on [0, T]

there exists a number 6 > 0 such that, for each t E [0, T], O S s S min{6, t},

|9(t - 8) - g(t)! S

(\DIO')

37

Taking s = t, we note that this last condition along with the assumption that g(O) = 0

implies that |g(t)| S 5/2 for t E [0,6]. If we define

then

WM) * g(t) - g(t)l

Thus, for t E [0,6],

flnltl z: LII/((3)77) d3 =1— (ft/II,

5 Wt. 7)) * g(t) - 7517(t)9(tll + l9(t)llfin(t) - 1|

s [0‘ ()(s, s)(g(t — s) — g(t)) ds + (g(t))e-W

WM) sg(t) — g(t)) < 5 (”mswfig

and, for t E [6, T],

|w(t,n) * g(t) - WM

/06 M3, 77)]g(t — s) - g(t)] d3
+/6Iv(s,17)|g(t — s) - g(t)| ds + mm (53ng (9‘7”)
§+ 3||gllsse“’/I’

E

for all 77 2 77(6) sufficiently small. 2

In proving Theorem 3.1, we will take r() to be one element in the sequence (rn(-))

of functions.

38

Proof of Theorem 3.1: From (6) we see that the true solution it of (1) satisfies

[or 120,3; T)ft(s) ds + [u(t; r) + u(t; r)] u(t)

= f(t;s)—[III’fIt(t+p.s+t)(t-t(s+t)-t1(t)1dsdn.(p)+s(t;r)s(t), (3.6)

for t E [0,1]. Setting y(t; r) : u(t; r) — u(t), we get that y(t; r) solves

 

 

_1 t,. ..
y(t) = u(t;r)ww) f0 k(t,s;r)y(s)ds+F(t;r), tE [0,1], (3.7)
where
F(t; ,r) ;= 0"" It k(t + p, s + t) [tt(s + t) - 11(t)] dsdw) — u(t; r)t‘t(t).

u(t; T) + u(t; T)
As in (2.2), we write

~

t(t.s;s) = [0 I") (k(t. s) +pD.t(t+e,.(p).s)1 dn.(s)

= (form dn,) [k(t, s) + H(t, s; r)], t E [0,1], (38)

where, for 0 g s g t g l, we have

f6“) lek(t + 51,.(p). S)dnr(p)l
[H(t,s;r)| = r(t) ,
f0 dllr

pdnrbo)

foIIIIdnr

S ||k||1,oo||Tlloo-

 

 

T(t)
S ||k||1.oo O

 

Employing a Taylor expansion as in (1.3), we also write

a(1t; T) = [In pdtM/T) + h(t; T),

39

for t E [0, 1], where

W) p
h(t;r) := [0 f0 [pD1k(t+€,t+C)+sDzk(t+€,t+C)l dsdn.(p).

 

 

Then

r(t) ~
u(t;r) = ((71):. (/ dos) he; 1).

0

where

[h(t )] I IIII d ()+h(t )
;T = ,. )0 7lrp ;T
||T|II<§o(foIIIdnr) °

 

 

1 ’ r(t) 3 r(t)
. ((71)..[/ ds.)+—nt(1.,../ pIdnr(p)[
urns (10“) dnr) . o 2 o
__ 3
s ((71);? [1 + §l|kll1.oollTllos]

= 0(HTHIQ”)

Using our definition for u from (3.5), we then have for NHL» sufficiently small that

 

 

1 1 1
u(t; 7) + u(t; 7) _ ”rug. 70"“) an. 1 + h(t; r)
1 + 7,,(t; r)

 

,. , (3.9)
llTll’o’s foIII dnr
where ”u(t; T) = 0(IITIILT”) 88 MI» -> 0-

Returning to equation (3.7), we employ (3.8) and (3.9) to get that

y(t) = —I+|——-—|————:'|I|,,O:II II [OI [k( (t, s) H(,t (s;r)] y(s)ds+F(t;r)

—_— ;“1p—/0Ik(t,s)y(s) ds -— III/OIG(t, s; r)y(s) ds + F(t; 7"), t5 [0713-10)

llT so

40
where, forOS sgtg 1,

[G(t,3;7‘)[ : IIT ——I[—|p Ik(t7 5071?“; II) +H(t7 '3 ,1") I1 +7P(t7 T)“

= 0(llTlléoI'I)

Since p E (0,1/2], G is bounded (at least) for all 0 S s S t S 1.
Now as in previous chapters, we will convolve (3.10) with 7/7(t, s(r)) and subtract

the result from (3.10). In this instance, we take c(r) = ||rllgo, and the result is
y(t) = [OI K(t, s; r)y(s) ds + F(t; r) — 7/7(t,e(r)) at: F(t; r), (3.11)
where
K(,t s; r) :=/I w( t — r, 6(7‘ )G(r, s; r) dr - C(t, s; r) — /8Iw(t — r,e(r))D1k(r, 3) dr.

Here the suppressed details are much like those seen when applying this convolution

technique in previous chapters. We see that, for 0 _<_ s S t S 1,
|K(t, 8;T)| S leGlloo + ||k||1,oo,

showing that K is bounded.

Next we look at the terms of

III” f0” k(t + p, s + t) [71(8 + t) - 176)] d8 (177(0) + a(t; T)T‘t(t)

III II : 0t(t; T) + u(t; T)

— u(t).

 

First, we have from (3.9) for all t E [0, 1] that

it“) it k(t + p. s + t) [77(8 + t) — e(t)] ds dn.(p)|
a(t; T) + u(t; T)

 

 

41

2llklloollt’tllso JIIIpdnr(p)
“ d(t; T) + u(t; T)

S 2I1+u(t;T)I|Iklloollftlloo||Tlch;I

 

= 0(HTIICIQII)

Likewise, for all t E [0, 1],

a(t; T)

s(t;s) + WW) 5 [1+ u(t;r))nsnmnsnsp.

 

Thus,
F(t; T) - 1W, 5(7)) * F(t; T) = (Mt, 5(7)) * (E(t) - E(t) + 0(llTlléJ")
And, by Lemma 3.2
(170.5(7)) * W) - W) = 7W, ||Tllio) * (1(0- W)

converges to zero uniformly as NHL» —> 0.
With these observations about the boundedness of the kernel K and the uniform

convergence of

wakF—FI

to zero, we may apply the Gronwall Inequality to (3.11) to get the desired result. 2

We note here that, should we replace our expression for u(t; r) in (3.5) with a
constant multiple of it (say, multiplied by some c > 0), then the proof of Theorem 3.1
still goes through. Evidently, though, the proof fails if u(t; r) E 0, as the presence of
a nonzero constant added to h(t; r) = O(|]r||1"’ in the denominator in (3.9) after the

IITII’;o f5“) dn, has been factored out is crucial.

42

As in earlier chapters, we need to know that the convergence asserted in Theorem
3.1 will happen in the presence of noisy data. As before, the proof does not change

much from the “pure data” case.

Theorem 3.1 Along with all of the assumptions in Theorem 3.1, we also assume that
f6" satisfies Hypothesis 1.3 with respect to the measures 77,.” for (6"), a sequence of
positive numbers converging to zero. If for some c > 0, q E (0,2) we have ||r,,|]oo = 06"

n’

then the solution u"’1 (t; r,,) of

IIT(t,s;sn)u(s)ds+ (s(t;r.) +11(t;s.)1u(t) = IIIIII76"(t+p)dn..(p)

converges uniformly to a as n -—) 00.

Proof of Theorem 3.1: As in the proof of Theorem 3.1 we form the difference
y(t; r) = u"(t; r) —u(t) (here we are suppressing the dependence upon n), convolve the
equation for y with 717(t, ||rllgo) and subtract to get equation (3.11) with the additional
terms

E(t; T) - (W’s—“(TD * E(t; T),

where

 

T(t)
E(t;T) — f0 d(t + )0) 012(10)-
But, from (3.9),

|1+7p(t;T)| re

 

I ( )I ||r||€o foIIIIdUr 0 ( ,0) 77 (P)
(5
5 mil + I’YpItirlll-

Since p E (0,1/2], it is clear that ||E(; r)||,,0 —+ O (and hence E— 7/7* E) for any choice
of q E (0,2). 2

CHAPTER 4

The Discretized Problem

Most problems of type (1) are solved numerically on a computer, and nearly always
with some error introduced as a result. It is impractical, in general, to represent a
function on [0, 1] (or any interval) perfectly. Most likely, the functions involved are
known only by samplings at specific times, and represented on a machine as vectors.

One numerical approach to problem (1) without using a special regularization
technique is to simply partition the interval [0, 1] into N subintervals [t,-,t,+1], i =
0, . ..N — 1, each of width At = l/N and to seek constants a,,i = 0,. . .,N — 1, so

that the step function

N—l
u(t) = a aiXiIt)

satisfies (1) at the collocation points t = t,, i = 1,. . ., N. In this discretized form,
(1) becomes a lower-triangular matrix problem with nonzero diagonal elements (un-
der suitable conditions upon the kernel) and as such is well-posed. Nevertheless,
the instability of (1) (the infinite-dimensional problem) manifests itself even in this
discretized setting, with the condition number of the matrix growing as At shrinks.
Often it is necessary to keep the value of N so small that solutions are hardly of any
use in order to keep those solutions from becoming highly oscillatory. We will not

delve deeply into these issues, but more can be found in [10].

43

44

Thus, in considering a discretized version of problem (1), it makes sense for us
to also consider a discretization of some perturbed, well-posed problem that we will
solve in lieu of it. In this chapter, we will consider a discretized form of the penalty
predictor-corrector equation (3.3) (with penalty function u(t; r) for t E [0, 1]) and
show that the solution of this equation converges to the true solution of (1) at collo-
cation points as the grid size shrinks. Further (in contrast to the continuous theory
in Chapter 3), our convergence theory will also apply to the case of p(-; r) E 0. The
significance of this result is that we will obtain convergence of solutions of standard
discretizations of equation (7) in the case of regularization parameters r() that are

not limited by a variability constraint such as that given in Hypothesis 2.1(i).

4.1 The Setup

We assume that [0, 1] has been partitioned up into N (a positive integer) subintervals
[t,, t,+1] where t,- = iAt, i = 0,. . ., N— 1, At = 1/N. We further assume that k, a and
f satisfy Hypothesis 1.1. So we have a satisfies (1) at each t E [0, 1]; in particular, at
t=t,~,i=1,...,N.

We take as our perturbation of (1) the equation (3.3) for u(t; r) 2 0, namely

[OI [E(t, s; r)u(s) ds + [u(t; r) + u(t; r)]u(t) = f(t; r). (4.1)

where for now, we take r(-) to be a continuous function on [0, 1] into (0, T — 1].

In discretizing (4.1) we seek constants (to, . . . , aN_1 so that the step function
N-l
u(t; At) = 5: (1.7).-(t) (4.2)
i=0

satisfies (4.1) at each of the points t1, . . . ,tN. Here (25,- is the indicator function on the

45

half-open interval (t,, t,+1] for i = 1,. . . ,N — 1

1, ifte(tiati+1l
(0,“) I: {

0, otherwise,

and (to is the indicator function on the closed interval [t0, t1]. Substituting (4.2) into

(4.1) and setting t = tj+1 gives us

j n+1 ~ ~
2011/ k(tj+173;7‘)d3+ [0(tj+1;7‘) +#(tj+1;7")laj = f(tj+1;7‘) (4-3)

i=0 If

for j = 0, . . . , N —1. (Notice that we have taken to writing r,- for r(tj).) Equation (4.3)
can be written as a lower-triangular matrix system (in the a,’s) where the diagonal

elements

9+1 Tj+1
/; /(I) k(tJ'I‘l +p7 3) dnr(p) d3+a(tj+l;7‘) +H(tj+l;T)
JI

are all positive if we assume that k > 0, u(t; r) 2 0 and 7), satisfies Hypothesis 1.2.
Under these assumptions, constants (to, . . .,aN_1 do exist (uniquely) so that (4.2)
satisfies (4.1) at tj, j = 1,...,N.

In previous chapters we have talked about convergence of an approximate solution
to the true solution as a (function) parameter r() —> 0. In the discretized setting,
we also want to see what happens as At —7 0, and we will link these two parameters

together.

Hypothesis 4.1 Let 'y : [0,1] —> (0,00) be a piecewise-continuous func-

tion. We will assume that r() := 7(-)At.

Because of this assumption, it makes sense to write p(t,-;7, At) in place of p(t,-;r)
for j = 0,. . . , N — 1. We will adopt a notation pj(At), suppressing the dependence
upon '7. Likewise, in place of 77, we will write 77737 (also suppressing the measure’s

dependence upon 7).

46
Let us then define constants cj(At) = c,-(p, At) by

c,-(At) 2: “(J’I)+“J(AII, j=0,...,N—1, (4.4)

00031”)

 

where a” is defined as in (2.1) for V = 0,1. (Note that the a,,(t;r,-),a(tJ-;r) depend
ultimately upon '7 and At by Hypothesis 4.1, but they do so through the r,-.) Using

these, (4.3) can be written as

tH—l ~ -
Z (11 fl k(tj+1, S; 7‘) d3 + a0(t,-+1; r)cj+1(At)aj = f(tj+1; 7").

i=0

Alternatively, if dnAt is a positive Borel measure satisfying Hypothesis 1.2 and f6
satisfies Hypothesis 1.3 with respect to dnAt, then with f" in place of f in (4.1) there
is a unique step function u(-; At, f 5) (whose dependence upon .7 is suppressed) of the

form (4.2) satisfying

 

j t1+1 k(tj+1 3") Ii“ JIIIt‘H 'I' P)
a- ——I—i——ds+c- Ata- = f I d , 4.5
12:; I ./t.- a0(tj+1; r) III( I I o ao(tj+1;r) IIAIIPI I I
forj=0,...,N—- 1.
We will use a differencing technique similar to that used in [8] to analyze conver-
gence. To this end, we make a shift in the indices j in (4.5) to get that u(t; At, f")

satisfies

tt'+1k(t,s;r T1 5t-+
201/ —3——Ids +CjIAtlaj—l = Mdnmp),

t.- ao(tj;1‘) 0 0003317")
for j = 1, . . . , N. Subtracting this equation from (4.5) yields

t1+1 [k(t,-+1, s; r)

c- At 07- +
J+l( ) J tj a0(tj+1;r)

03-01(3) ds

47

= __1__T)_ [OI’II [f(tj+1+ p) + d(t-+1 + 9)] dnAt(P)

GOItj+1;
IIIaoIth; 7) [0 I [f(t)- + P) + d(tj + Pl] d’WIp) + ”(AIM—I
Iii/II“ [w __ k(tj,8;7')

GOItj+li T) ao(tj; T)

a,<t,-(s) ds, (4.6)

720 t

which holds for j = 1,. . .,N — 1. We have seen in (3.6) that the true solution it

satisfies

foIk(t,;usr)( (s)ds+/0IIII/OIIk(t (tt+p,s+ )[u(s+t)—u(t)]dsdnm(p)

+[0t(t; T) +u(t;T)lfl(t) = Of(t+p)al77m()0)+/t(1t;T)’t’t(T)s (4-7)

for all t E [0, 1]. If, as we did above, we evaluate (4.7) at t = t,- and divide through by
a0(t,-; r), and then subtract the resulting equation from the one arising from evaluation

at t = tj+1 and division by a0(t,-+1; r), we get

 

 

 

Cj+1()Mt(tj+1) + [:III I—)——a(:’;:;IITI] 17(3) 018
--/."‘ (1.51:: ’ ‘—(—9l 77717777“)
—/0III I/Ik( tj+1 +p,s+t,-+1)II IIII +5581; SII’IIII d8 dump)
+/OII/0I k(t,+p,s+t,-) IIIIZOIétINf IIIAIdsdn (p)
+/0I’II Wit At( )- 0 I%E%dvm(p)
+u7+1(At)—0(itfiI,—IT-)-# 2(A 1*) ,,II(II.I;IT)’ III'III

forj = 1, . . . , N — 1. Subtracting (4.6) from (4.8) gives us

Cj+1(At) (s( t.+1)— as) + [,I“ I—(T—TIH) — sitter ds

48

z _f'“i(£2+_1:fld Mp) + ['3 Mme) +cj<At>w<tj> — (17—11

. aoltj+1~; 7") ~ aoltj; 7‘)
— g (I [——’:f:g;j:j;3l — ——’:f:g,’jf,)] [71(3) — men .13

 

”+1 P 71(8 + t-+1) - W -+1)
— kt- + , +t- J 3 d d
A A (3+1 p 3 3+1) aO(tj+1;T) '3 "At(p)

 

r,- p ' . c(s + t,) — u(tj)
+/0 f0 k(t] + M + t3) aw”) ds d77At(p)
ii(7541) g(t.)
+- At——’—-—— .At——’—. 4.9
MJ+I( Ia0(tj+1;r) IuJ( )00(tj; 7‘) ( )
By a Taylor expansion we can write
21(15) = fill/3+1)+(t-tj+1)71I(Zj(t)), (4-10)

for some 2,-(t) between t and tj+1. Thus for t E (tj, tj+1] we have

u(t) — ajasjm = At 77 + I Xf‘sz-(m ,

 

forj=0,...,N—1,where

”H(t‘ 1) — (1‘
fij .: J+At J.

 

Using this and dividing through by At, (4.9) becomes

 

‘2' 0003341; 7‘) - 00051413") At

_ . . __1_ ”I‘m _ ”M
— CJ(At)IBJ—l At {A 006541;?) d77At(P) ‘/(I) aoztjfl') dnAt(P)

r1+1 P 11 8 + t' — 27, t‘
+/ / k(tj+1 + P, 3 + tj+1) I III) , I III) d3 d77At(p)
o o a0(tj+1,r)

— [0 II foIk(t,- + p, s + t;-)IIII" I I) _ IIII’I deflAt(P)}

tJ-IIIct- - t1:lEt—,; —t-
[Cj+1(At)+/ I IIIIIIIIIIdIIl 51+], I IIII IIIII IIIIaI(Zj(S))dS

 

 

 

00(tj; 7‘)
II—I II“ 1203341 8’7‘) E(tj 3°7‘)] [ 3-73.“
g1." [ ao(tj+1;1‘) a0(tj; r) ’6 At ( ( ))

 

mi, [unmafi — #j(At)II(::ITI)l , (4.11)

49

forj=1,...,N—1.

Finally, we define the quantities (for which the dependence upon 7 is suppressed)

tj+1 k(tj+1, S; 7')

 

 

1),-(At) :2 cj+1(At)+/tj a0(tj+1;r)ds, (4.12)
w,(At) :2 %, (4.13)
E705. At) == D,- (1m) MI“ W dnAe(p)
—/0II%,—E§dnm(p)l, (4.14)
v.14) 7: m [33:11") .. 3:55;?) 7., (4.15)
Z,(At) = 13—11%, (4.16)

where

 

'1'“ p 17(3 + tj+1) — 7105341)
R] (At) A [0 k(t1+l + pa 8 + t]+1) ao(tj+1;7') S d77At(p)

rJ- ”t. _‘t.
-/0 [OIWJ- +p,s+tj)III I III III II dsdnAAp)

 

aolthT)
1‘1 tH-l [E(tqq 8'7') k(t 3II’I)
+ / —J_;;___;14— s—h i743 “
12:?) t.- [ao(tj+1;7I) “00137) I III I III

IJI‘H III‘I:(tj-+-113;I’II) —I
—_ _ t. . d
+/th a0(tj+1;r) ('3 3+1)” (23(8)) 3
i1(tj)

ML + ,1,(At)— (4.17)

_ . At ,
“1+“ )aoaJ-m) ao<t77r>

for z' = 0,. ..,j — 1, j = 1, . . . , N — 1. With these expressions, (4.11) can be written

JI-l 1

fl,- = W7(At)flj_1—AtZVJ-,7(At)fi.

— —E-(6, At) — z.(At), (4.18)
i=0 At II II

forj=1,...,N—1.

50

Now if we evaluate (4.5) at j = 0 and (4.7) at t = t1 (dividing through the

resulting equation by a0(t1; r)) and then subtract the two equations, we get

 

 

1
so = —EE0(6, At) — Zo(At), (4.19)
where
,_ I‘ Hipsfl‘)
D0(At) .— C1(At) +./O mds, (4.20)
E0(61At) := DozAt) /0IIII gfi} d77At(p)a (421)
,_ R0(At)
with
1 r1 P ° _ _
Row“) 1: (1001”,) [[0 j; k(tl + P,3 +151) [u(s + t1) — “(t1)ld3d77At(P)
+/0I1Ic(t1,s;r)(s — t1)u'(zo(s)) ds — p1(At)a(t1) . (4.23)

4.2 Conditions for Convergence

In the last section we defined expressions that arose out of a “differencing” approach
to the solutions a and u(t; At, f5). While the quantities themselves are somewhat
different, the purpose they serve is the same as similarly-defined expressions in [8].
The next theorem and proof also come from [8]. We provide the proof here for

convenience.

Theorem 4.1 Assume that point evaluations of the solution a to (1) make sense,

and that dnAt, f5, 1: and ,u satisfy the conditions discussed above. Suppose positive

51

numbers w, M, v and z exist such that

Wj(At) < w, J =1,. ,N — 1,

V,,,-(At) s v, i=0,...,j—1,j=1,...,N—1,
6

E-6At < M— '= N 1

)(1 ) AtI .7 0: i a

Zj(At) _<_ 2, j = 0,. ,N — 1,

uniformly in At > 0, with w 6 (0,1). If At = At(6) = m/d for afirced c > 0, then the
solution u(t; At, f5) of (4.5) converges to a at the collocation points t,, j = 0, . . . , N(6)
{N(6) = 1/At(6)) as 6 —> 0. This convergence is at the best possible rate with respect
to 6; that is,

(u(t); At, fI) — w.» s KW + 0(6),

forj = 1,. . . ,N(6), as 6 —¥ 0, where K is a positive constant independent ofci and

At.

Proof of Theorem 4.2: Arguing as in [8] we define constants B,- = B,(At, 6),

j = 0, ...,N — 1 satisfying

1
B = —M
0 At2 (5+2,
1‘1 1
Bj = WBj—l'l'AthBi'l'fiMéI—l'zy j=1,...,N—1.
i=0

If we assume that At = At(6) is chosen so that 6/At2(6) remains bounded as 6 —-) 0,
then the coefficients in the relations above are bounded. It is easily verified that these

B,- satisfy the second-order difference equation

1
B0 = fiMd‘l’Z,
B1 = (w+Atv)Bo+—I——M6+z,

At2

52

B,- = (1+w+Atv)B,-_1 -wB,-_2, j: 2,...,N— 1.
By the theory of difference equations we find that
Bj = CIin +0273,
forj =0,...,N—1. Here

T1 = 1+1—f-JAt+O(At2),

’1)
T2 = w [1— mAt] + 0(At2),

ML
01(5, At) = Iii—fift— + 0(At),
6
02(5, At) = —w 1111?? + 0(At).

From the definitions of the B,- it is clear that each B,- > O, and that r1 > 12 > 0.

Since 02 < 0 for At sufficiently small, we have

B,- = 01(6,At)7{+02(6,At)r2j

= C1(6, At) [1+ l—l—At + 0(At2)]I

—w

s 201(5,At)e$p(-1—2:ILE) ,

and thus taking At(6) = cx/d gives us that the B,- have a uniform bound for j =

0,. . . , N — 1, independent of N. A simple induction argument gives that

l/leSBja j=0,...,N—1,

53

showing that
Ia, - H(tj+1)| S 2C1(5,At)Atexp(1—_II—w) —) 0

as 6 (and hence At(6)) goes to 0. 2

Theorem 4.2 Suppose that k, a and f satisfy Hypothesis 1.1, that we have measures
nAt = 77,13, for At > O (sufficiently small) that satisfy Hypothesis 1.2, and that f5
satisfies Hypothesis 1.3 with respect to these measures. Assume also that Hypothesis

4.1 holds, and that ||y||oo < kmin/Hklloo. If we take
pj(At) :2 ca0(tj;r)Atq,

for c 2 0, q 2 1, then the conclusions of Theorem 4.1 hold concerning the convergence
of u(t; At, f6) to a as 6 —> 0 at the best possible rate with respect to 6, provided
At = At(6) = cx/g.

Proof of Theorem 4.2: From our assumptions, we have that Dj(At) > 0 for

each j = 0,. . . , N — 1. Furthermore, we have for each of these j that

 

 

 

 

1 = ao(tj+1; 7")
Dj(At) a(t,-+1; 7‘) + #j+1(At) + fthIII f(lIIII k(th + P13) d7)At(p)d3
00(t1'+1; 7‘)
fthII foIIIII k(th + P13)d77At(P) d3
1
< . 4.24
_ kminAt I I

From this we see that

 

1 'j 1 1 '2‘
|EJ-(6,At)| 3 II / I d77At(,0) + —/ d77At(p)
kminAt aoltj+1;7”) 0 0003;?) 0

26
kminAt I

 

54

for j = 1, . . . , N — 1, and likewise we have the same bound for IE0(6, At)|. We can
thus take M (in the statement of Theorem 4.1) to be M = 2 / kmm.

In (2.2) we showed that

k(t, s; r) = a0(t; r)k(t, s) + [OIIII lek(t + €3,¢(p), s) dnm(p). (4.25)

Thus,
g(t)-“s;r) _ k(t-s;r)

t4+1
A ao(tt+1;T) (u(t;-7r)
ti rj D k t. + s _ , d
5 [II (|k(tj+1,s)—k(tj,s)|+f° Pl 1 (a 57:10)) 3)! mp)
II 00(tjar)

+ f(iIIII PlD1k(tj+1 + €3,t,-+1(P)a3)l d77At(p)) ds

00(tj+1;7‘)
ti+l
ft. [ID1k(t,-+§,,t,(At),s)|At +||k||1,oo(rj+rj+1)] ds

3 llkll1,oo(1+ 2|I7H00)At2.

 

ds

 

 

 

 

|/\

This along with (4.24) shows that we may bound the Vj,,-,i = 0,...,j — 1,j =

1,...,N—1by

kl 00
” '1’ (Hahn...)

kmin

 

'1}:

Turning to the Z], we see that by (4.24) we need only show that each of the terms
of the Rj is 0(At2). We have that the first term

 

'1'“ ” u(s+tI+l) ”(t +1)
k t- t- J 3 d d
/0 f0 (3+1+P,3+ 1+1) ao(t,-+1;r) s nA,(p )

 

k 0° '1'“
_ “ ” / / sIu (z.(t.+1+s))ldsdnm(p)
00(t1+1;r
llklloollfi’llIoo

|/\

rj+l
a0(t,+1.,., 7341/0 pdnAt(p)
J 1
S llklloollfi'lloollvllioAtI,

55

for j = 1,. . . , N — 1. The first term of R0 is handled similarly, as is the second term
in the expression for R], j = 1,. . .,N —- 1.

Our work in bounding the V,,- also shows that

 

:[JIII [k(t,-+1,s;r) _ k(t,,s;r)] (s _ t,-+1)u'(z,-(s))ds

i=0 a0(t,-+1; 7") 0005;“; 7")

 

 

~

j 1'+1 ,s; r If: 73., ;
a’llooAtZI/I ——II I " _I I _I. II
,_ tt 00( tj+1;7‘ 0005317")

< llkllimllfl'lloofl+2l|7||oo)NAItI’

ds

l/\

 

 

llkl|1,oo||fi'lloo(1 + 2|l7|loo)AtI,

which takes care of the summation term of the R], j = 1, . . . , N — 1. The fourth term
for these same values of j is handled similarly, as is the second term in the expression
for R0.

Using our definition for the p,, we handle the remaining terms from the expression

for the Rj, j = 1,...,N— 1 as follows:

 

u.+.(At>i((J—“—)—— ut<At>af(Ij) = c|fi(tt+t)-fi(tt)lAt"

tJ+1i7I )
g cllu’llooAtq“.

Since q 2 1, this term is (at least) 0(At2). The final term in the expression for R0

can be written as

C [11(t1) - 11(0)] At”,

since we assume 11(0) 2 0, and is then handled the same way.

Next, we have that

CAN)
ft?“ k(tj+1, s; r) ds

 

Wj(At) =

 

Cj+1(At)+

000111;?)

56

Cj(At)
cj(At) + [cj+1(At) — cj(At)] + 1 ft?“ h(t,~+1, s; r) ds

00(tj+1;7‘)
1

1+KjI

 

 

 

forj=1,...,N—1,where

1 1 t1+1 ~
K. :: —_ . _ . —/ . '
J cj(At) (c,+1(At) c,(At) + ao(tj+1; r) t- k(t,+1, s, r) d3)

1 (0(tj+1;7I)+ tit—“(Av _ @6117“) + tit-(At)
(2)-(At) ao(tt+t;r) ao(tt;r)

 

 

1 t1+1 rj+1
,) ft, [0 k(tj+l+p13)d77At(p)d3)

00(tj+1;
: 1 (0105141; 7')

“99:21
Cj(At) +cAt

ao(tj+1;7‘) 00%;?)
1 9+1 "J'+1
/ / k(tj+1+p,s)dnm(p)ds)
7‘) tj 0

a0(tj+1;
1 0034.1; 7‘) d(tj; 7‘) )
— —— + lem.-..N

CAN) (000141; 7‘) 00%; 7”)
1 llklloo foII pdnAtOO) )

0 — + kminAt
c,-(At) ( ao(t,-; r)
At
'(At)

— cAt‘l

 

 

IV

 

IV

 

IV

(—llkllooll7ll00 + kmin) '

“('3

Now we have assumed that

kmin

llklloo’

 

llvlloo <

which means that there exists an L > 0 such that

 

 

 

LAt
K- >
I — Cj(At)
_ La0(t,-; 7‘)At
— OIII {k(tj +pas+tj) dnAt(p) (13+ cao(t,-;r)Atq
> 110.0(6), T)At
_ llklloo foII pdvAt(p) + cao(t,-; r)Atq

L
>
‘ llklloollvlloo + 0M“

 

57

L
llklloollvlloo + 0’

 

since At 3 1 and q 2 1. Thus, if we define w 2 [1+ L/(llkllooll'yll00 + CH“, then we

haveWJ-(At)$w<1forallj=1,...,N—1. 2

One surprising thing about this theorem is that the proof goes through with
the constant c = O, and thus with u(t; r) E 0. Recall that in the continuous case
(see Chapter 3) we could not prove convergence with u(t; r) E 0 without restricting
the variability of r(t) in the limit as the noise level goes to zero (as in Chapter
2). This shows that, at least in the case of the discretized problem, the penalty
predictor-corrector class of methods we have analyzed here is a generalization of the
predictor-corrector class of methods we discussed in Chapters 1 and 2.

The condition assumed in Theorem 4.2 that

kmin

Nelle:>

 

llvlloo <

is used at the end of the proof in order to get the existence of an L > O for which

kmin _ llklloolh'lloo > L,

and, ultimately, an upper bound to E [0, 1) upon the Wj. A closer inspection shows

that what is really necessary is an L > 0 for which

O“(15341;7‘) _ d(tjfl‘)
ao(tJ-+1; r)At ao(tj; r)At

 

+ kmin > L.

We exploit this observation to arrive at several corollaries.

Corollary 4.1 If we assume all of the stated conditions of Theorem 4.2, replacing

only the condition ll’yll00 < kmm/Hklloo with the assumption that the function 7 in

58
Hypothesis 4.1 is constant, then the conclusions of Theorem 4.2 hold.
Proof of Corollary 4.1: If we take L = kmin, then

1
g < 1
1+ L/(llklloollilloo + C)

 

WAN)

forj=1,...,N—1. 2

Corollary 4.1 gives us a chance to compare the generality of Theorem 4.2 with
the one found in [8] (summed up in Theorem 0.3). This result is more general both
in that it allows for nonconvolution kernels and in the few requirements placed upon

the measures, as Theorem 0.3 is proved only for special types of measures.

Corollary 4.2 Let us assume all of the stated conditions of Theorem 4.2, replacing
only the condition ll'yllCO < kmin/“klloo with the assumptions that '7 E C1 and the
following condition (like in Theorem (1.1)). there exists a constant C 2 1 such

that, for each At > 0 {sufficiently small) and each a: E [Tminarmax] (that is, x/At E

[7mina 7max])2

 

.1” x .1:
/ pdmp) 2 — / cm... (4.26)
o C o
If
ll7lloo< min 4 ,
“NICO-5%”

Then the conclusions of Theorem 4.2 hold.

Note that, should a positive C exist so that (4.26) is satisfied, it necessarily the

case that C 2 1. This is because

5‘3 fox d77At
fox P d77At(p)
1’3 fox dnAt
5’3 fox dnAt'

C

 

59

Proof of Corollary 4.2: Forj = 1, . . . , N — 1 we have

 

 

 

 

 

 

 

u(tjn‘) k . fdj p_dnm(p)
“D(tfi") — mm 0” din:
kmin’YjAt
_ ——C .
Also,
d(tjfl)
__ < . .
00(tj;1‘) — IIkIIW7JAt
Thus
(r(th; T) a(tj; T) kmin7j+1
—— kmin Z ———koo' kmin
a0(tj+l;T)At ao(tj;1‘)At + C H H 7] +
kmin kmin
= C (7j+1_7j)+7j( C - “k“oo) +kmin
kmin kmin
z c ”Y'(€2'>At+w( C —Hkn..)+k......

Now kminlly’lloo / C is bounded, and so the first term above can be made as small as

needed as At —> 0. Thus, if

 

k in
m g — Ilklloo) + k..... > o,
for each j = 1, . . . , N — 1, the conclusion holds. Our assumption above upon the size

of ll’ylloo is sufficient to imply this. 2

CHAPTER 5

Numerical Results

In Chapter 4 we described a collocation scheme which uses no special regularization
method in its attempt to find a step-function solution that matches the data at N
discrete points. We emphasize the word “special”, because the act of discretization so
as to consider a finite-dimensional problem in place of the original infinite-dimensional
one is itself a regularizing process. Nevertheless, we claimed that without a relatively
large stepsize, such solutions become highly oscillatory. Figure 5.1, supports this

assertion.

To produce the results in Figure 5.1, a convolution kernel of k(t) E 1 was used
along with a known true u(t) = t, so that the true data is f (t) = t2/2. A random
amount of noise not exceeding 10‘2 (making for a relative error of 2%) was then
added to f to produce noisy data, which then was used (in place of f) in the colloca-
tion process described above. The resulting approximate solution from four different
stepsizes corresponding to N = 8, 15, 25 and 45 subintervals of [0, 1] is plotted against
the known true solution, with the approximate solution plotted in dashing. The ap-
proximate solution, which we said was a step function, has not actually been plotted

as such. Instead, the constant interval in the solution has been condensed down to

60

61

15

Collocation: N =

8

Collocation: N =

Collocation: N =

 

 

 

 

 

45

25

Collocation: N =

26

0

 

 

 

 

 

Figure 5.1. Simple Collocation at Various Stepsizes

62

a point, with these points then being joined by straight lines. The other numerical

examples we include in this work are obtained and displayed in similar fashion.

In the Introduction we claimed that, using standard Tikhonov regularization, it
is difficult to find a value for the parameter a that provides for a smooth solution in
certain sections of the domain and a rough one in others. We demonstrate this with
an example using a discretized Tikhonov scheme. In Figure 5.2 we have discretized
[0,1] into 40 subintervals and used this scheme for four different choices of oz, a =
0 (equivalent to the discretized scheme of Figure 5.1), 10‘11,5 x 10—10, and 5 x
10‘9. In this example, the “spike” function that is the solid graph in each of the
four plots was numerically integrated against the kernel k(t) = t2 to obtain the
quasi-true f. Random noise not exceeding 10‘6 was then added to the data, with
Tikhonov regularization then being applied to the resulting perturbed data to obtain
the (dashed) approximate solutions.

We note that, at a = 10‘“, the approximate solution recovers the spike quite
well, but the smooth sections of the true solution are correspondingly rough in the
approximate one. As a is increased, this roughness is smoothed out nicely, but at the
expense of recovering the spike. This is a tendency that is found in all regularization
methods, that as the regularization parameter is increased solutions tend to become

oversmoothed.

In Figure 5.3 we have applied our discretized method (with ,a E 0) to the same
problem as that in Figure 5.2 to allow for comparison of its success against that of
Tikhonov. Three of the plots are for constant "y(t), with these values set at 1,2 and
3. In the fourth plot, we have set 7 to 5 through most of the domain, but it equals 1

in the region of the spike.

0000

0000

63

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

alpha = 0 alpha = lO“(-11)
.2’ Ill 1.21
1’ Ii 1*
.8: 0.8»
6’ l 0.6
4’ l. 0.4-
.2' (“A a ‘ 0.2
.,... \
.2’ \ll‘l ill -o.2» ' 0'4,
alpha = 5 x 10“(-10) alpha = S x 10“(-9)
.2 1.2-
1 1.
.8» 0.8:
6 0.6’
4* 0.4r
2 I ,‘ 0.2»
Trufz‘“ 0 Z 4"”? . 6 o I 8 C i o l 8 1
.2. -o.2

 

Figure 5.2. Tikhonov Regularization for Several oz Values

0000

0000

 

 

64

 

 

 

 

 

 

.2» 1.2»
1' 1-
.8: 0.8:
6» 0.6»
4’ 0.4»
2 0.2»
_ - 04
.2» -O.2
gamma = 3 gamna=5,l,5

.2 1.2»
1» 1» ’l
.8: 0.8’
6+ 0.6-
4: 0.4
.2: 0.2»

5 1 42‘“ .‘4‘""o 6
.2 -O.2

 

 

Figure 5.3. Tikhonov Regularization for Several a Values

65

The relationship between Figures 5.4 and 5.5 is analogous to that between Figures
5.2 and 5.3. The true solution is a step function (though our plotter renders it
as looking continuous). We have again discretized to 40 subintervals, numerically
integrated the true solution against the kernel k(t) = t, added relative error in the
amount of around 0.05%, and applied a regularization process to this perturbed data,

using Tikhonov at several values of a in Figure 5.4 and our method in Figure 5.5.

66

= 10“(-7)

alpha

= 10“(-8)

alpha

 

 

1.2:

1»

 

 

 

 

alpha = 10“(-5)

alpha = 10“(-6)

 

 

 

1.2*

1»

 

 

 

Figure 5.4. More Tikhonov Solutions

0000

0000

67

 

 

 

 

 

 

 

 

 

gamma = 1 gamma = 2

.2: 1.2’
1’ 1L
.8: 0.8
6' 0.6
4 0.4:
.2» 0.2

-O.2
.2’ 1.2:
l' 1.
.8» 0.8’
6 0.6’
.4: 0.4:
.2: 0.2:

-O.2

 

Figure 5.5. More Solutions using Predictor-Corrector Scheme

69

this new class of methods to be a generalization of the earlier class. It is our hope
that we may be able to show this in the case of the infinite-dimensional (continuous)
problem as well.

In order to demonstrate the practical value of these methods, we provided numer-
ical examples of computed solutions plotted against known true solutions. Of course,
the purpose of any regularization technique is to find approximate solutions for prob-
lems the solutions of which are not known. One might reasonably ask (regardless
of the particular regularization technique of which we are speaking) how we are to
choose the correct value for the regularization parameter. Why, after all, would we
know that 5 x 10‘10 is a better value for (1 than 5 x 10‘9 in the example of Figure
5.2 if we did not have the true solution with which to compare it?

This is a difficult question to address mathematically. In the case of Tikhonov
regularization, at least, we have discrepancy principles that provide somewhat sat-
isfactory answers. To summarize one known as the Morozov Discrepancy Principle,
we assume that we have perturbed data f6 for the true f in (1) with an estimate on
the noise Hf” — f H; S 6. It is an established fact that the minimization problem (2)

usin f5 for f has a unique solution it" for each a > 0, and that the “discrepancy”
g a

”Alli - f6“;r

is monotone in a. The Morozov Discrepancy Principle says that the correct value of
a is the one for which the discrepancy equals 6 (see, for example, [5] or [7] for further
information on this topic). It is an open problem how to select the regularization
parameter r() for the predictor-corrector method described in Chapters 1 and 2,
or how to select the regularization parameters for the penalty predictor-corrector
methods of Chapters 3 and 4. A sequential type of discrepancy principle seems the

natural choice for these types of regularization methods, so that the proper value of

70

r,- is chosen at the ith step in the discretized process. We hope that, after further
work, we may be able to get a satisfactory answer to this question.

Finally, the convergence proofs in this work have consistently been under the
hypothesis that k(t, s) > 0 for all t, s. In the case of a convolution kernel, even just the
weaker assumption that k(O) 75 0 is sufficient to quantify the degree of ill-posedness
in problem (1) as being of first-order in that a single differentiation of (1) would lead
to a well-posed second-kind equation. We call such a kernel 1-smoothing. While
problems with 1-smoothing kernels are certainly ill-posed, there are many problems
which do not fall under this classification, having u-smoothing kernels (i.e., kernels
for which

k(O) = k’(0) = ... = Jew-”(0) = 0, Wm) 7e 0,

so that the problem (1) becomes a well-posed second-kind equation after u differenti-
ations) for integer u > 1. In the case of the IHCP, the kernel is infinitely-smoothing in
that no amount of differentiation ever leads to a well-posed equation. We seek a more
general theory that applies to problems in some (or all) of these types of problems as

well.

BIBLIOGRAPHY

BIBLIOGRAPHY

[1] J. V. Beck, B. Blackwell and C. R. St. Clair, Jr., Inverse Heat Conduction, Wiley-
Interscience, 1985.

[2] T. A. Burton, Volterra Integral and Differential Equations, Academic Press, New
York, 1983.

[3] C. Corduneanu, Integral Equations and Applications, Cambridge University Press,
1991.

[4] R. E. Edwards, Fourier Series ( a Modern Introduction), Vol. 1, 2nd Ed, Springer-
Verlag, Berlin, 1979.

[5] Heinz W. Engl, Martin Hanke, and Andreas Neubauer, Regularization of Inverse
Problems, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.

[6] G. Gripenberg, S. O. Londen, and O. Saffens, Volterra Integral and Functional
Equations, Cambridge Univ. Press, Cambridge, 1990.

[7] C. W. Groetsch, The Theory of Tikhonov Regularization for Fredholm Equations
of the First Kind, Pitman, Boston, 1984.

[8] P. K. Lamm, Approximation of ill-posed Volterra problems via predictor—corrector
regularization methods, SIAM J. Appl. Math. 56 (1996) 524—41.

[9] P. K. Lamm, Future-sequential regularization methods for ill-posed Volterra equa-
tions: applications to the inverse heat conduction problem, J. Math. Anal. Appl.
195 (1995) 469—94.

[10] P. K. Lamm, Regularized inversion of finitely smoothing Volterra operators:
predictor—correCtor regularization methods, Inverse Problems 13 (1997) 375—402.

[11] P. K. Lamm and L. Eldén, Numerical solution of first-kind Volterra equations
by sequential Tikhonov regularization, SIAM J. Numer. Anal. 34 (1997), no. 4,
1432—1450.

71

72

[12] Jose C. Munoz and Y. Leong Yeow, Applications of maximum entropy method
in capillary viscometry, Rhea. Acta bf 35 (1996), 76—82.

   

MICHIGAN STnTE UNIV. LIBRARIES
[Illllllllll[Illlllllllll[llIllIllllllllllllllllllll
31293016880464