Transcript Document

USING A PRIORI INFORMATION FOR
CONSTRUCTING REGULARIZING ALGORITHMS
Anatoly Yagola
Department of Mathematics, Faculty of Physics,
Moscow State University, Moscow 119899 Russia
E-mail: [email protected]
1
Main publications:
1.
Tikhonov, A.N., Goncharsky, A.V., Stepanov,
V.V. and Yagola, A.G. (1995). Numerical
methods for the solution of ill-posed problems.
Kluwer Academic Publishers, Dordrecht.
2. Tikhonov, A.N., Leonov, A.S. and Yagola, A.G.
(1998). Nonlinear ill-posed problems. Chapman
and Hall, London.
3.
Kochikov, I.V., Kuramshina, G.M., Pentin,
Yu.A. and Yagola, A.G. (1999). Inverse
problems of vibrational spectroscopy. VSP,
Utrecht, Tokyo.
2
Introduction
Az  u
z  Z , u U
(1)
A : Z  U is a linear operator,
Z , U are linear normed spaces.
The problem (1) is called well-posed on the class of
its “admissible” data if for any pair A, u 
from the set of “admissible” data the solution of
(1):
1) exists,
2) is unique,
3) continuously depends on errors in A and u (is
stable).
3
Stability means that if instead of A, u we are given
“admissible” Ah , u  such that Ah  A  h, u u   ,
the approximate solution converges to the exact
one as h,   0 . The numbers h and  are error
estimates for the approximate data Ah , u  of (1)
with the exact data A, u  . Denote   h,   .
If at least one of the mentioned requirements is
not met, then the problem (1) is called ill-posed.
4
As a generalized solution, it is often taken the so~
called normal pseudosolution z . It exists and is
unique for any exact data of the problem (1)
if A L( Z ,U ) , u  R( A)  R ( A) , ~z  Au .
Here R( A) and R  (A) denote the ranges of the
operator A and its orthogonal complement in U ,

A
and
stands for the operator pseudoinverse
to A . Below we find z as a normal
z.
pseudosolution, i.e., z  ~
5
What is to solve an ill-posed problem?
Tikhonov answered: to solve an ill-posed problem
means to produce a map (regularizing algorithm)
.R Ah ,u ,  such that
1) brings an element z  R Ah ,u ,  into
correspondence with any data Ah ,u , , Ah  L(Z ,U ) ,
.u U of the problem (1);

2) has the convergence property z  z  A u

u

R
(
A
)

R
( A) .


0
as
,
6
All inverse problems may be divided into
three groups:
1) well-posed problems,
2) ill-posed regularizable problems,
3) ill-posed nonregularizable problems.
7
Is it possible to construct a regularizing
algorithm that does not depend on h ,  ?
Theorem 1: Let R Ah , u  be a map of the set LZ ,U  U
into Z . If R Ah , u  is a regularizing algorithm
(not depending explicitly on  ), then the map
.P A, u   Au is continuous on its domain
.
.LZ ,U   R( A)  R ( A)
Proof The second condition in the definition of RA
implies in R A, u   Au  P A, u  valid for each
. A, u  LZ ,U   R( A)  R ( A) and the
convergence PAh , u   RAh , u   Au  P A, u 
as h,   0 valid for
. A, u ,  Ah , u  LZ ,U   R( A)  R ( A) .
The map P A, u  is continuous on
.LZ ,U   R( A)  R ( A)  L(Z ,U ) U .
8
It is clear from Theorem 1 that a regularizing
algorithm not using h and  explicitly can only
exist for problems (1) well-posed on the set of the
data LZ ,U   R( A)  R ( A)  LZ ,U  U .
The theorem generalized the assertion proved by
Bakushinskii. Tikhonov proved the similar
theorem when was studying ill-posed SLAE. As
result, L-curve and GCV methods cannot be
applied for the solution of ill-posed problems.
9
It is very curious that the most popular error free methods
cannot solve well-posed problems also! As the first example
we consider so-called the “L-curve method” (P.C. Hansen).
In this method the regularization parameter in Tikhonov
functional  is selected as a point maximum curvature of the
L-curve
{(ln||Ahz - u||, ln||z||):   0}.
But this method cannot be used for the solution of ill-posed
problems because the L-curve doesn’t depend on h and  (see
the theorem). Everybody can easily prove that this method is
inapplicable to solving the simplest finite-dimensional wellposed problems.
10
Let us consider the equation:z = 1. Here Z = U = R1, A = I
(unit operator), u = 1.
Let approximate data Ah = I and u = 1 for any h and .
Independently on h and , the regularization parameter
selected by the L-curve method
L(Ah, u) = 1.
Therefore, the approximate solution zL = 0.5, and it doesn’t
converge to ze = 1 as h,   0.
Using L-curve method we’ve received 0.5 instead of 1
independently on errors!!!
11
For another popular form of L-curve
{(||Ahz - u||2, ||z||2):   0}
it is possible to prove that such method has systematic
error for all well-posed systems of linear algebraic
equations (A. Leonov, A. Yagola).
Another very popular “error free” method is GCV – the
generalized cross-validation method (G. Wahba), where
(Ah, u) is found as the point of the global minimum of
the function
G() = ||(AhAh* + I)-1u|| [tr(AhAh* + I)-1]-1,   0.
This method is not applicable for the solution of ill-posed
problems including ill-posed systems of linear algebraic
equations (see the theorem above). It is possible construct
well-posed systems of linear algebraic equations the GCV
method failed for their solution.
12
Is it possible to estimate an error of an
approximate solution of an ill-posed problem?
The answer is negative. The main and very important
result was obtained by Bakushinskii.
Assume Ah  A . Let Ru ,   be a RA. Denote by
. R,  , z   sup Ru ,    z : u U , Az  u   
the error of a solution of (1) at the point z using
the algorithm R . If (1) is regularizable by a
continuous map R and there is an error estimate,
which is uniform on D
supR,  , z  : z  D      0 as   0
then the restriction of A 1 to AD  U is continuous on
. AD .
13
The accuracy of the approximate solution
.z  Ru ,   of the problem (1) could be estimated
as z  z  K   ,
where K does not depend on  and
the function    defines the convergence rate
of z to z .
Pointwise and uniform error estimations should be
distinguished.
14
Consider the results obtained by Vinokurov.
Let A be a linear continuous injective operator
acting in Banach space Z and the inverse operator
. A 1 be unbounded on DA1  . Suppose that
.   is an arbitrary positive function such that
.    0 as   0 , and R is an arbitrary method
to solve the problem.
The following equality holds for elements z except
maybe for a first category set in Z :
 R,  , z 
lim sup 


 0
    
A uniform error estimate can only exist on a first
category subset in Z .
15
A compact set is a typical example of the first
category set in a normed space Z . For this set
special regularizing algorithms may be used and a
uniform error estimation may be constructed.
Clearly, a uniform error estimate exists only for wellposed problems.
16
A posteriori error estimation
For some ill-posed problems it is possible to find a
so-called a posteriori error estimation.
Let A be an exact injective operator with closed
graph and Z be a  -compact space.
Introduce a function  u ,   such that z  Z
.  z   0 ,   (0,  z ] , u U , u u  :
z  Ru ,     u ,  
The function  u ,   is an a posteriori error
estimation for the problem (1), if  u ,    0
as   0 .
17
The generalized discrepancy method
Let Z,U be Hilbert spaces, D  Z be a closed
convex set of a priori constraints such that 0  D ,
. A , Ah be linear operators. On a set Ah ,u ,
introduce the Tikhonov's functional:
2
2

M z   Ah z  u   z
where   0 is a regularization parameter.
infM  z: z  D
(2)
For any   0 , u U and bounded linear operator
. Ah the problem (2) is solvable and has a unique
solution z  D .
18
A priori choice of  .
A regularizing algorithm using the extreme
problem (2) for M  z  : to construct   
such that z    z as   0 .
If A is an injective operator, z  D and     0,
.h  0 as   0 , then z    z as  0 ,
i.e., there is the a priori choice of  .
2
19
A posteriori choice of  .
The incompatibility measure of (1) on D :
 u , Ah   inf Ah z  u : z  D
Let it can be computed with an error   0 , i.e.,
instead of  u , Ah  there is  u , Ah  such that
 u , Ah    u , Ah    u , Ah   
The generalized discrepancy:
2
2


 2
    Ah z  u    h z    u , Ah 


The generalized discrepancy    is continuous and
monotonically non-decreasing for   0 .
20
The generalized discrepancy principle to choose the
regularization parameter:
2
2
2

1) If the condition u     u , Ah  is not just,
then z  0 is an approximate solution of (1);
2
2
2

2) If the condition u     u , Ah  is just,
then the generalized discrepancy has a positive

*
z

z
zero  and 
 .
z  z .
If A is an injective operator, then lim
0
*
z  z , where z * is the normal
Otherwise, lim
0
solution of (1), i.e., z *  inf  z : z  D, Az  u .
*
21
If A, Ah are bounded linear operators, D is a closed
convex set, 0  D , z  D , the generalized
discrepancy principle are equivalent to the
generalized discrepancy method:
find
 z : z  D, A z  u
h

2
   h z
   u , A  
2


2
h
22
Inverse problem for the heat conduction
equation.
2
wt  a wxx

w0, t   0
wl , t   0

x  t  0, l  0, T 
There is a function u    w , T  L2 0, l  , we want to
find zx  wx,0W12 0, l  such that zx   z x 
as   0 .
We may write that
2
l
l





z
x
2
2
2
2

dx
u    u   d , z x   z x  

0

0

x


23
The problem may be written in the form of integral
l
equation
u     G  , x, T  z x  dx
where G , x, t  is the Green function:
2




na
 n   nx 


2
G , x, t   l  sin
 sin
 exp  
 t
0
n 1
 l 
 l 
  l  


The problem is solved for the parameters
.a  1.0, T  0.1, l  1.0 , the function u   is taken
such that   0.05 u   .
24
The exact solution z (x) (
solution z x  (
).
) and the approximate
25
The Euler equation
The Tikhonov's functional M  z  is a strongly convex
functional in a Hilbert space.

z
The necessary and sufficient condition for  to be
a minimum point of M  z  on a set D of a priori
constraints is
 
 M  z   , z  z    0 z  D


 


If z is an interior point of D , then M  z   0 , or

h 


A A z  z  A u
*
h
*
h 
We obtain the Euler equation.
26
Sourcewise represented sets
(1)
Az  u
A : Z  U is a linear injective operator.
Assume the next a priori information: z is
sourcewise represented with a linear compact
operator B : V  Z :
z  Bv
(3)
Here V is a reflexive Banach space.
Suppose B is injective, A is known exactly, u u  .
27
Set n  1 and define the set
Zn  z  Z : z  Bv, v V , v  n
Minimize the discrepancy F z   Az  u on Z n.
If min Az  u : z  Zn   , then the solution is
found. Denote n   n . Otherwise, we change n
to n  1 and reiterate the process.
If n  is found, then we define the approximate
solution zn  of (1) as an arbitrary solution of the
inequality
Az  u  
z  Zn 
28
Theorem 2: The process described above converges:
.n    . There exists  0  0 (generally speaking,
depending on z ) such that n   n 0  for   0,  0 .
Approximate solutions zn  strongly converge to
. z as   0.
Proof The ball Vn  v V : v  n is a bounded closed
set in V . The set Z n is a compact in Z for any n ,
since B is a compact operator. Due to Weierstrass
theorem the continuous functional F z  attains its
exact lower bound on Z n.
Clearly, z  Bv  Z N , where
v
v is a positiveinteger
N 
 v   1 otherwise
.  is the integer part of a number.
29
Therefore n  is a finite number and there is  0
such that n   n 0  for any   0,  0  . The
inequality n   N for any   0 is evident.
Thus, for all   0,  0  the approximate solutions
. zn  belong to the compact set Z n  0  , and the
method coincides with the quasisolutions method
for all sufficiently small positive  . The
convergence zn   z follows from the general
theory of ill-posed problems.
Remark: The method is a variant of the method of
extending compacts.
30
Theorem 3: For the method described above there
exists an a posteriori error estimate. It means that
a functional  u ,   exists such that  u ,    0
as   0 and zn    z   u ,   at least for all
sufficiently small positive  .
Remark 2: The existence of the a posteriori error
estimation follows from the following. If by
.Z  Z we denote the space of sourcewise
represented with the operator B solutions of (1),

then Z  n1 Z n . Since Z n is a compact set, then
.Z is a  -compact space.
31
An a posteriori error estimate is not an error estimate
in general meaning that is impossible in principle
for ill-posed problems. But it becomes an upper
error estimate of the approximate solution for
“small” errors    0 , where  0 depends on the
exact solution z .
32
The operators A and B are known with errors. Let
there be linear operators AhA , BhB such that
. Ah  A  hA , Bh  B  hB . Denote the vector of errors
by    , hA , hB  . For any integer n define a
compact set Zn,h  z  Z : z  Bh v, v V , v  n .
Find a minimal positive integer number n  n  such
that the inequality
B
A
B
B


AhA z  u    hA BhB  hB AhA  hA hB  n 
has a nonempty set of solutions.
Then the a posteriori error estimation is
 u , Ah , Bh ,   hB n   max{ z  zn  : z  Z n ,h ,
A
B

B

AhA z  u    hA BhB  hB AhA  hAhB  n }
33
Inverse problem for the heat conduction
equation
For any moment of time t  0 there is
l
z    Bvx    G , x, t  vx  dx
0
where vx  wx,0 . Suppose
V  Z  U  L2 0, l .
We solve the problem using the method of extending
compacts.
Let a  1.0, l  1.0 , t  0.02 ,T  0.1 ,  0.03 u .
10 0.3  x  0.5

v  x    4 0.5  x  0.8
0
otherwise

34
The approximate solution z x  and its a posteriori error
estimation. We obtain n   5.
35
Compact sets
There is the additional a priori information:
the exact solution z of (1) belongs to a compact
set M and A is a linear continuous injective
operator.
As a set of approximate solutions of (1) it is possible
to accept

ZM
 z  M : Ah z  u  h z   

Then z  z as   0 in Z for any z  Z M .
36
After finite dimensional approximation we obtain

that Zˆ M
 Mˆ  Zˆ  , where Mˆ is a convex
polyhedron for convex or monotonic functions and


Zˆ   zˆ  Zˆ : Aˆ zˆ uˆ    
. Aˆ is a matrix, zˆ and uˆ are vectors.
To find zˆ it is possible to use the method of
conditional gradient or the method of projection
conjugated gradients.
37
Error estimation
Find the minimum and the maximum values for
each coordinate of Zˆ M . Denote them by z il , ziu ,
. i  1, n .
2) Secondly, using the found zˆ l , zˆ u we construct
functions z l x  and z u x  close to Z M such that
.z  Z M : z l x  zx  z u x for each x  a, b.
Therefore, we should minimize a linear function on a
convex set. We may approximate the set by a
convex polyhedron and solve a linear
programming problem. The simplex-method or
the method to cut convex polyhedrons may be
used.
1)
38
Inverse problem for the heat conduction
equation.
Let M be a set of convex upward functions zx  such
that 0  zx   C . Assume that a  1.0 , l  1.0 ,
.T  1.0 , C  1.2, the number of nodes 20.
39
The exact solution z x  (
), the functions z l x  , z u x  .
40
We shall formulate now general conditions for constructing of
regularizing algorithms for the solution of nonlinear ill-posed
problems in finite-dimensional spaces. These conditions could
be easily checked for an inverse vibrational problem which we
consider as a problem to find the normal pseudosolution of
nonlinear ill-posed problem on a given set of constraints. We
shall discuss typical a priori constraints.
41
In this section the main problem for us is an operator equation
Az  u,z  D  Z ,u U
(1)
where D is a nonempty set of constraints, Z and U are finitedimensional normed spaces, is a class of operators from D
into U. Let us give a general formulation of Tikhonov's
scheme of constructing a regularizing algorithm for solving
the main problem: for the operator Eq. (1) on D find an
element z* for which
 Az*, u   inf  Az , u  : z  D  
(2)
42
We assume that to some element u  u there corresponds the
nonempty set Z* in D of quasisolutions and that Z* may
consist of more than one element. Furthermore, we suppose
that a functional z is defined on D and bounded below:
z   *  inf z  : z  D  0
The  -optimal quasisolution problem for Eq. (1) is
formulated as follows: find a such that z  Z *
z   inf z  : z  Z *  .
43
We suppose that instead of the unknown exact data (A, u), we
( Ah , usatisfy
)
are given approximate data
which
the following
conditions:
u  U , u , u    ;Ah  ,  Az , Ah z    h,  z ,
z  D.
Here the function  represents the known measure of
approximation of precise operator A by approximate operator
Ah .We are given also numerical characterizations h,   0 of
the “closeness” of ( Ah , u ) to (A, u). The main problem is to
construct from the approximate data an element
z  z  Ah , u , , h,    D
which converges to the set -optimal pseudosolutions Z as
  h,   0.
44
Let us formulate our basic assumptions.
1) The class  consists of the operators A continuous from D to
U.
2) The functional z  is lower semicontinuous on D.
3) If K is an arbitrary number such that K   *
K  z  D :z   K
then the set
is compact in Z.
4) The measure of approximation  (h, ) is assumed
to be defined for h  0,   * , to depend continuously on
all its arguments, to be monotonically increasing with respect to
 for any h  0, and satisfy the equality
 0,    0,   *
45
Conditions 1)-3) guarantee that Z  .
Tikhonov’s scheme for constructing regularizing algorithms is
based on using the smoothing functional
M  z   f  Ah z, u    z , z  D,  0
in the conditional extreme problem: for fixed 0, find an
element
such that
z  D
M  z   inf M  z :z  D.
46
Here f[x] is an auxiliary function. A common choice
is
f x  x m ,m  2.
We denote the set of extremals of (5) which correspond to a
given   0 by Z  .
Conditions 1)-3) imply that Z   .
47
The scheme of construction of an approximation to the set
Z includes:
(i) the choice of the regularization parameter
  Ah , u , h,   ;
(ii) the fixation of the Z  corresponding to   , and a

special selection of an element z  in this set:

z  Z
as   0.
48
It is in this way that the generalized analogs of a posteriori
parameter choice strategies are used. They were introduced by
A.S. Leonov. We define for their formulation some auxiliary
functions and functionals:
    z ,     f  Ah z ,u   Iz ,
    f  h,           z ,
            z , z  Z  ;   0.
Here
  inf   Ah z,u   h, z    : z  D
is a generalized measure of incompatibility for nonlinear
problems having the properties [2]:
.    ,      0
as
49
All these functions are generally many-valued. They have the
following properties.
Lemma. The functions  , , , are single-valued and
continuous everywhere for  >0 except perhaps not more a
countable set of their common points of discontinuity of the
first kind, which are points of multiple-valuedness, then there



exists at least two elements z  , z  in the set Z such that
   0  z ,    0  z  . The functions , are
monotonically nondecreasing and , are nonincreasing. The
generalized discrepancy principle (GDP) for nonlinear
problems consists of the following steps.
50
(i) The choice of the regularization parameter as a generalized
solution  > 0 of the equation
    0
.
Here and in the sequel we say that  is the generalized
solution for a monotone function  if  is an ordinary solution
or if is a “jump”-point of this function over 0.
51

The method of selecting an approximate solution z from the set

Z  by means of the following selection rule. Let q>1 and
C>1 be fixed constants,
1   : q ,  2    q
are auxiliary regularization
parameters, and let z 1
and z2 be extremals of (4) for
=1,2.
2
1



 C 1 f  

z

C

z
If the inequality


1
2
z

Z
holds for z and z , then any elements
subject to
the condition  z  0
can be taken as the approximate
solution. For instance we can take z  z  . But if
 
z2   Cz1   C  1 f  
then we choose


.
z z
z

 
so as to have  z  0 , for example

52
z D
Theorem. Suppose that for any quasisolution
z *   *  inf  z  : z  D
the inequality
holds. Then (a)     0 has positive generalized solution;
(b) for any sequence  n  hn ,  n 
such as   0 , the
zn  of approximate solutions,
corresponding sequence
which is found by GDP has the following properties:
*
z n  z ,  z n    as n  .
53
Inr many practical cases it is very convenient to take
 z   z (r is a constant, r >1). If it is known in addition
that the operator equation has a solution on D, then the value
 can be omitted. GDP in linear and nonlinear cases has
some optimal properties.
54
References
1.
2.
3.
4.
5.
6.
7.
Hadamard, J. (1923). Lectures on Cauchy's problem in linear partial
differential equations, Yale Univ. Press, New Haven.
Tikhonov, A. N., Leonov, A. S. and Yagola, A. G. (1998). Nonlinear
ill-posed problems, Chapman and Hall, London.
Tikhonov, A. N. (1963). Solution of incorrectly formulated problems
and the regularization method, Sov. Math., Dokl., 5, 1035-1038.
Tikhonov, A. N. (1963). Regularization of incorrectly posed
problems, Sov. Math., Dokl., 4, 1624-1627.
Leonov, A. S. and Yagola, A. G. (1995). Can an ill-posed problems
be solved if the data error is unknown? Moscow Univ. Physics Bull.,
50(4), 25-28.
Bakushinskii, A. B. (1984). Remark about the choice of the
regularization parameter by the quasioptimality criterion and the
propertion criterion, Comput. Math. Math. Phys., 24(8), 1258-1259.
Bakushinskii, A. B. and Goncharskii, A. V. (1994). Ill-posed
problems: theory and applications, Kluwer Academic Publishers,
Dordrecht.
55
8)
9)
10)
11)
12)
13)
Tikhonov, A. N., Goncharsky, A. V., Stepanov, V. V. and Yagola, A.
G. (1995). Numerical methods for the solution of ill-posed
problems, Kluwer Academic Publishers, Dordrecht.
Vinokurov, V. A. (1979). Regularizable functions in topological
spaces and inverse problems, Sov. Math., Dokl., 20, 569-573.
Vinokurov, V. A. and Gaponenko, Yu. L. (1982). A posteriori
estimates of the solutions of ill-posed inverse problems, Sov. Math.,
Dokl., 25, 325-328.
Yagola, A. G. and Dorofeev, K. Yu. (2000). Sourcewise
representation and a posteriori error estimates for ill-posed
problems, In: Ramm, A. G. et al., eds., Fields Institute
Communications: Operator Theory and Its Applications, 25, 543550, AMS, Providence, RI.
Ivanov, V. K., Vasin, V. V. and Tanana, V. P. (1978). The theory of
linear ill-posed problems and its applications, Nauka, Moscow (in
Russian).
Dombrovskaya, I. N. and Ivanov, V. K. (1965). Some questions to
the theory of linear equations in abstract spaces, Sibirskii Mat.
Zhurnal, 16, 499-508 (in Russian).
56
14)
15)
16)
17)
18)
19)
Riesz, F. and Sz.-Nagy, B. (1990). Functional analysis, Dover
Publications Inc., New York.
Vainikko, G. M. (1982). Methods for the Solution of Linear
Incorrectly Formulated Problems in Hilbert Spaces. Textbook, Tartu
University Press, Tartu.
Leonov, A. S. and Yagola, A. G. (1998). Special regularizing
methods for ill-posed problems with sourcewise represented
solutions, Inverse Problems, 14(6), 1539-1550.
Titarenko, V. N. and Yagola, A. G. (2000). A method to cut convex
polyhedrons and its applications to ill-posed problems, Numerical
Methods and Programming, 1, section 1, 8-13, www.http://nummeth.srcc.msu.su.
Goncharsky, A. V., Cherepashchuk, A. M., and Yagola, A. G.
(1985). Ill-posed problems of astrophysics, Nauka, Moscow (in
Russian).
Goncharsky, A. V., Cherepashchuk, A. M., and Yagola, A. G.
(1978). Numerical methods for the solution of inverse problems in
astrophysics, Nauka, Moscow (in Russian).
57
20)
21)
Rusov, V. D., Babikova, Yu. F. and Yagola, A. G. (1991). Image
restoration in electronic microscopy autoradiography of surfaces,
Energoatomizdat, Moscow (in Russian).
Yagola, A. G., Kochikov, I. V., Kuramshina, G. M., and Pentin, Yu.
A. (1999). Inverse problems of vibrational spectroscopy, VSP, Zeist.
58