On the efficient method of solving ill-posed problems by adaptive discretization
To solve ill-posed problems Ax = f is used the Fakeev-Lardy regularization, using an adaptive discretization strategy. It is shown that for some classes of finitely smoothing operators proposed algorithm achieves the optimal order of accuracy and is more economical in the sense of amount of discrete...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут математики НАН України
2009
|
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/6332 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | On the efficient method of solving ill-posed problems by adaptive discretization / S.G. Solodky, E.A. Volynets // Збірник праць Інституту математики НАН України. — 2009. — Т. 6, № 2. — С. 524-549. — Бібліогр.: 11 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-6332 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-63322010-02-24T12:01:05Z On the efficient method of solving ill-posed problems by adaptive discretization Solodky, S.G. Volynets, E.A. Геометрія, топологія та їх застосування To solve ill-posed problems Ax = f is used the Fakeev-Lardy regularization, using an adaptive discretization strategy. It is shown that for some classes of finitely smoothing operators proposed algorithm achieves the optimal order of accuracy and is more economical in the sense of amount of discrete information then standard methods 2009 Article On the efficient method of solving ill-posed problems by adaptive discretization / S.G. Solodky, E.A. Volynets // Збірник праць Інституту математики НАН України. — 2009. — Т. 6, № 2. — С. 524-549. — Бібліогр.: 11 назв. — англ. 1815-2910 http://dspace.nbuv.gov.ua/handle/123456789/6332 en Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Геометрія, топологія та їх застосування Геометрія, топологія та їх застосування |
| spellingShingle |
Геометрія, топологія та їх застосування Геометрія, топологія та їх застосування Solodky, S.G. Volynets, E.A. On the efficient method of solving ill-posed problems by adaptive discretization |
| description |
To solve ill-posed problems Ax = f is used the Fakeev-Lardy regularization, using an adaptive discretization strategy. It is shown that for some classes of finitely smoothing operators proposed algorithm achieves the optimal order of accuracy and is more economical in the sense of amount of discrete information then standard methods |
| format |
Article |
| author |
Solodky, S.G. Volynets, E.A. |
| author_facet |
Solodky, S.G. Volynets, E.A. |
| author_sort |
Solodky, S.G. |
| title |
On the efficient method of solving ill-posed problems by adaptive discretization |
| title_short |
On the efficient method of solving ill-posed problems by adaptive discretization |
| title_full |
On the efficient method of solving ill-posed problems by adaptive discretization |
| title_fullStr |
On the efficient method of solving ill-posed problems by adaptive discretization |
| title_full_unstemmed |
On the efficient method of solving ill-posed problems by adaptive discretization |
| title_sort |
on the efficient method of solving ill-posed problems by adaptive discretization |
| publisher |
Інститут математики НАН України |
| publishDate |
2009 |
| topic_facet |
Геометрія, топологія та їх застосування |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/6332 |
| citation_txt |
On the efficient method of solving ill-posed problems by adaptive discretization / S.G. Solodky, E.A. Volynets // Збірник праць Інституту математики НАН України. — 2009. — Т. 6, № 2. — С. 524-549. — Бібліогр.: 11 назв. — англ. |
| work_keys_str_mv |
AT solodkysg ontheefficientmethodofsolvingillposedproblemsbyadaptivediscretization AT volynetsea ontheefficientmethodofsolvingillposedproblemsbyadaptivediscretization |
| first_indexed |
2025-07-02T09:15:34Z |
| last_indexed |
2025-07-02T09:15:34Z |
| _version_ |
1836526079251054592 |
| fulltext |
Çáiðíèê ïðàöüIí-òó ìàòåìàòèêè ÍÀÍ Óêðà¨íè2009, ò.6, �2, 524-549
S. G. Solodky
Institute of Mathematics, National Academy of Sciences of
Ukraine
E-mail: solodky@imath.kiev.ua
E. A. Volynets
Institute of Mathematics, National Academy of Sciences of
Ukraine
On the efficient method of solving
ill-posed problems by adaptive
discretization
To solve ill-posed problems Ax = f is used the Fakeev-Lardy regulariza-
tion, using an adaptive discretization strategy. It is shown that for some
classes of finitely smoothing operators proposed algorithm achieves the op-
timal order of accuracy and is more economical in the sense of amount of
discrete information then standard methods.
Keywords: optimal approximations, order of accuracy, ill-posed problems,
Fakeev-Lardy method, discrepancy principle
1. Introduction. Statement of the problem
In a Hilbert space X with inner product (· , · ) and norm
‖x‖ =
√
(x, x)
we consider the operator equation of the first kind
(1) Ax = f,
where A is a compact linear operator in X and f ∈ Range(A).
Suppose that instead of the exact right-hand side of (1) some its
perturbation fδ : ‖f − fδ‖ ≤ δ, δ > 0 is available only.
c© S. G. Solodky, E. A. Volynets, 2009
On the efficient method of solving ill-posed problems 525
We will construct approximations to minimal-norm solution x†
of (1) that satisfies the Holder-type source condition, i.e.
(2) x† ∈Mν,ρ(A) = {u : u = |A|νv, ‖v‖ ≤ ρ},
|A| = (A∗A)1/2, ρ ≥ 1,
where A∗ is the adjoint of A and the parameter ν > 0 is unknown.
Consider a class Hr, r = 1, 2, . . ., of compact linear operators
A, ‖A‖ ≤ 1, such that for any m = 1, 2, . . . the conditions
(3) ‖ (I − Pm)A ‖≤ m−r, ‖ A(I − Pm) ‖≤ m−r
are satisfied, where Pm is the orthoprojector onto linear span of
the first m elements of some orthonormal basis E = {ei}∞i=1 in
space X.
As an example of equation (1) with operator A ∈ Hr in the
space X = L2(0, 1) one can take Fredholm integral equation of
the first kind
Ax(t) ≡
∫ 1
0
k(t, τ)x(τ)dτ = f(t),
where max
0≤t,τ≤1
|k(t, τ)| ≤ 1, operators A and A∗ act from L2(0, 1)
into the Sobolev space W r
2 [0, 1] and as basis E is selected the
orthonormal system of Legendre polynomials or (if r = 1) the
orthonormal system of Haar functions.
It is known (see [11, p. 14]) that the best accuracy of recovering
minimal-norm solutions of (1) that fill up set Mν,ρ(A) can be lower
estimated by
ρ1/(ν+1)δν/(ν+1).
This is because every method guaranteeing approximation accu-
racy O(δν/(ν+1)) on the set of solutions (2) is referred to as order-
optimal approximate method for solving (1).
In this paper we investigate projection methods of solving (1)
that using Galerkin information as discrete information about (1).
526 Solodky S.G., Volynets E.A.
Remind that by Galerkin information about equation (1) one usu-
ally mean a set of inner products
(4) (Aej , ei), (fδ, ei).
The volume of inner products (4) used to approximate solve
(1) characterizes economical properties of corresponding projec-
tion methods.
Obviously that to construct economical projection method spe-
cial attention must be put to effective choice of set Ω of indices
(i, j) for inner products (Aej , ei) which form discrete operator AΩ.
In the first time the problem of constructing economical projec-
tion methods for solving (1) was studied in [3] in the framework of
traditional Galerkin discretization scheme with Ω = [1,m]× [1, n].
From [3] it is follows that to guarantee the optimal order of ac-
curacy we need to choose n ≍ m ≍ O(δ−1/r), i.e. to compute at
least O(δ−2/r) inner products (4).
Statement of the problem. Our aim is to construct an al-
gorithm of solving (1) on class of operators Hr such that, firstly,
guarantees the optimal order of accuracy for solutions x† of the
form (2) and, secondly, is more economical in the sense of using
Galerkin information compare with methods considered in [3].
To construct such algorithm we will use an adaptive approach to
discretization that earlier was studied in [1]. To reduce the volume
of Galerkin information for this approach it will apply so-called
hyperbolic cross (see Section 4) as the area Ω and the discretization
level will be selected during computations as following
(5) ‖ A∗A−A∗
ΩAΩ ‖= O(
√
αδ),
where α is a regularization parameter.
For the first time such adaptive discretization scheme was stud-
ied in [1] for the standard Tikhonov method. In [6], [8] it was
investigated the optimality of the adaptive approach for the sta-
tionary iterated Tikhonov method, in [4] for the nonstationary
iterated Tikhonov method, in [10] for the generalized Tikhonov
On the efficient method of solving ill-posed problems 527
method, in [8], [9] for the Landweber method and in [7] for the
method of asymptotical regularization.
It turn out that discretization strategy (1.5) allows to solve the
problem formulated for all mentioned above regularization meth-
ods. Let us continue these investigations and verify efficiency of
adaptive discretization for the Fakeev-Lardy regularizator.
In conclusion we want mention one more adaptive discretiza-
tion scheme proposed in [2]. In the framework of this scheme the
discretization level is chosen as ‖ A − AΩ ‖= O(
√
α
√
δ), and as
area Ω is selected rectangle. It turn out that such approach is not
order-optimal and is less economical with compare both nonadap-
tive scheme in [3] and adaptive scheme in the present paper.
2. Fakeev-Lardy method
The Fakeev-Lardy method is an iterative procedure of the fol-
lowing type:
(6) x0 = 0; µxl +A∗Axl = µxl−1 +A∗fδ,
l = 1, 2, . . . , µ = const > 2/ρ.
For generating function of this method
gl(λ) =
1
λ
(
1 −
(
µ
µ+ λ
)l)
=
l−1∑
j=0
µj
(µ+ λ)j+1
, λ 6= 0,
the following estimates (see [11, p. 22])
sup
0≤λ<∞
gl(λ) = l/µ; sup
0≤λ<∞
λgl(λ) ≤ 1;
sup
0≤λ<∞
λ1/2gl(λ) = (l/µ)1/2; sup
0≤λ<∞
λp(1 − λgl(λ)) ≤ κpl
−p;
0 ≤ p ≤ l, κ0 = 1, κp = (µp)p, p > 0.
(7)
are true.
Let λk are singular values of operator A and φk, ψk are cor-
responding singular elements. Then operator A can be written
528 Solodky S.G., Volynets E.A.
as
A =
∑
k
λkφk(· , ψk)
and following relations
x† = |A|νv = (A∗A)ν/2v =
∑
k
|λk|νψk(ψk, v),
f := Ax† = A|A|νv =
∑
k
λk|λk|νφk(ψk, v).
(8)
hold.
Then the elements xl and Axl can be written as
xl = gl(A
∗A)|A|ν+2v = gl(A
∗A)
∑
k
|λk|ν+2ψk(ψk, v) =
=
∑
k
gl(|λk|2)|λk|ν+2ψk(ψk, v),
Axl =
∑
k
λkφk
(
ψk,
∑
m
gl(|λm|2)|λm|ν+2ψm(ψm, v)
)
=
=
∑
k
λkφk
∑
m
|λm|ν+2(ψm, v)gl(|λm|2)(ψk, ψm) =
=
∑
k
λk|λk|ν+2gl(|λk|2)φk(ψk, v).
As it follows from (5) in our approximate method discretized
operator can be changed in every step of iterations. Denote as
Al, l = 1, 2, . . ., discretized operator corresponding l-th step of
iterative process. More detailed this discretization scheme will be
considered in Section 4.
On the efficient method of solving ill-posed problems 529
Thus a finite-dimensional version of the method (6) has the form
x̂1 = (µI +A∗
1A1)
−1A∗
1fδ,
x̂2 = (µI +A∗
2A2)
−1(µ(µI +A∗
1A1)
−1A∗
1 +A∗
2)fδ,
. . .
x̂l =
l−1∑
k=0
µk
k∏
j=0
(µI +A∗
l−jAl−j)
−1
A∗
l−kfδ.
To prove the optimality of the method we have to estimate error
of approximation of minimal-norm solution x† by elements x̂l. So
in l-th step of iterative process it’s holds
x† − x̂l = gl(A
∗A)A∗(f − fδ)+
+ (x† − gl(A
∗A)A∗f) + (gl(A
∗A)A∗fδ − x̂l)
and hence the error can be upper estimated:
(9) ‖x† − x̂l‖ ≤ ‖gl(A∗A)A∗(f − fδ)‖+
+ ‖x† − xl‖ + ‖gl(A∗A)A∗fδ − x̂l‖.
Let us estimate now the right-hand side of (9) term by term. Due
to conditions (7) on generating function it is immediately follows
that for the first term
(10) ‖gl(A∗A)A∗(f − fδ)‖ ≤ ‖gl(A∗A)A∗‖‖f − fδ‖ ≤
≤ δ sup
λ
λ1/2gl(λ) ≤ δ
(
l
µ
)1/2
.
The second term can be represented by (8) as
(11)
x† − xl = (I − gl(A
∗A)A∗A)x† =
∑
k
(
µ
µ+ λ2
k
)l
|λk|νψk(v, ψk).
530 Solodky S.G., Volynets E.A.
Thus,
‖x† − xl‖2 =
∑
k
(
µ
µ+ λ2
k
)2l
|λk|2ν(v, ψk)2,
or
(12) ‖x† − xl‖2 = |cν,l(v)|2l−ν ,
where |cν,l(v)|2 := lν
∑
k
(
µ
µ+λ2
k
)2l
|λk|2ν(v, ψk)2.
To estimate (11) we need to estimate ‖Axl − f‖ too. Taking
into account (8) and relation
1 − λ2gl(λ
2) =
(
µ
µ+ λ2
)l
,
we have
‖Axl − f‖2 = µ2l
∑
k
|λk|2(ν+1) (v, ψk)
2
(µ+ λ2
k)
2l
.
and hence
(13) ‖Axl − f‖2 = |dν,l(v)|2l−(ν+1)
with |dν,l(v)|2 := µ2l
∑
k |λk|2(ν+1) (v,ψk)2
(µ+λ2
k)2l l
ν+1.
To estimate ‖x†−xl‖ we need the following auxiliary statement.
Lemma 1. For functions cν,l(v) and dν,l(v) the bounds
|cν,l(v)| ≤ ρκ
ν/(ν+1)
(ν+1)/2 , |dν,l(v)| ≤ ρκ ν+1
2
hold.
On the efficient method of solving ill-posed problems 531
Using Holder’s inequality we have
|cν,l(v)|2 =
∑
k
(
lν+1µ2lλ
2(ν+1)
k
(µ+ λ2
k)
2l
(v, ψk)
2
) ν
ν+1 (
µ2l
(µ+ λ2
k)
2l
(v, ψk)
2
) 1
ν+1
≤
≤
∑
k
(
lν+1µ2lλ
2(ν+1)
k
(µ+ λ2
k)
2l
(v, ψk)
2
) ν
ν+1
‖v‖ 2
ν+1 =
= |dν,l(v)|
2ν
ν+1 ρ
2
ν+1 .
For the second inequality we obtain
|dν,l(v)|2 ≤ lν+1 sup
λ
λ2(ν+1)
(
µ
µ+ λ2
)2l∑
k
(v, ψk)
2 ≤
≤ κ2
(ν+1)/2‖v‖2 = ρ2κ2
(ν+1)/2.
Substitution of this estimate into previous inequality completes
the proof of Lemma.
Thus due to (12) and to the first estimate in Lemma 1 we have
(14) ‖x† − xl‖ ≤ ρκ
ν/(ν+1)
(ν+1)/2 l
−ν
2 .
To estimate the last term in (9) we consider the auxiliary oper-
ator
Bl =
l−1∑
k=0
(
µk(µI +A∗A)−(k+1)A∗ −Gk,lA
∗
l−k
)
with Gk,l = µk
∏k
j=0(µI +A∗
l−jAl−j)
−1.
Then for the third item in the right-hand side of (9) we obtain
(15) gl(A
∗A)A∗fδ − x̂l = Blfδ.
To estimate norm of the element Blfδ we write down Bl in more
suitable form that will be shown in next statement.
532 Solodky S.G., Volynets E.A.
Lemma 2. For any l = 2, 3, . . . it holds
(16) Bl =
l−1∑
k=0
µk(µI +A∗A)−(k+1)(A∗ −A∗
l−k) −
l∑
k=1
Fk,
where
Fk =
l−k∑
j=0
(µI +A∗A)−jTj,k, k = 1, . . . , l;
(17)
Tj,k = Dj
l∑
i=j+1
(µI +A∗A)−(i−j)Ti,k−1,
j = 0, . . . , l − k, k ≥ 2;
Dj = (µI +A∗
l−jAl−j)
−1(A∗A−A∗
l−jAl−j), j = 0, . . . , l − 1;
Tj,1 = Dj
l∑
i=j+1
µi−1(µI +A∗A)−(i−j)A∗
l−i+1, j = 0, . . . , l − 1.
To reduct computation we introduce into consideration some
denotations:
Iµ := µI +A∗A; Jµ := I−1
µ ;
Uj := A∗A−A∗
l−jAl−j ; Hj := DjJµ = (Iµ − Uj)
−1UjJµ.
Quite easy to check that
(µI +A∗
l−jAl−j)
−1 = Jµ +Hj
and Iµ, Jµ, Uj , Hj ∈ L(X), where L(X) is the space of linear
continuous operators in X.
Further we need to introduce a special operation of substitut-
ing operators. Thus suppose that we have sequence of operators
On the efficient method of solving ill-posed problems 533
{Φi}, i = 1, 2, . . ., Φi ∈ L(X), and operator Ψ ∈ L(X). The oper-
ation of substitution we will note as
Φ
M⊕
N
Ψ(p),
where M ≥ N ≥ 1, p ≤ M − N + 1. This operation affects on
product of M − N + 1 operators ΦN ,ΦN+1, . . . ,ΦM . The main
point of the operation consists in replacement of all possible com-
binations from p distinct operators Φi of initial product by the
operator Ψ with preserved order of remained (M − N − p + 1)
multipliers Φi. Thus, as result of described operation we obtain a
sum of (M−N+1)!
p!(M−N−p+1)! (distinct!) replacement in such way opera-
tors, every of it is the product of p operators Ψ and (M−N−p+1)
operators Φi.
The above operation has some properties that will be used in
further reasoning. Namely,
Φ
M⊕
N
Ψ(M−N+1) =
M∏
j=N
Ψj,
Φ
M⊕
N
Ψ(M−N) =
M−N∑
q=0
(
q−1∏
i=0
Ψi+N
)
ΦN+q
M−N∏
s=q+1
Ψs+N
,
Φ
M⊕
N
Ψ(p) =
p∑
q=0
(
q−1∏
i=0
Ψi+N
)
ΦN+q
Φ
M⊕
N+q+1
Ψ(p−q)
,
p < M −N.
Let’s note operator Gk,l in new form with help of above operation:
Gk,l = µk
k∏
j=0
(Iµ − Uj)
−1 = µk
k∏
j=0
(Hj + Jµ) =
534 Solodky S.G., Volynets E.A.
= µk
k+1∑
i=0
H
k⊕
0
J (k−i+1)
µ =
= µk
(
Jk+1
µ +
k+1∑
i=1
H
k⊕
0
Jk−i+1
µ
)
= µk
(
Jk+1
µ +
k+1∑
i=1
Sk,i
)
with Sk,i = H
k⊕
0
J
(k−i+1)
µ .
Then
Bl :=
l−1∑
k=0
(
µkJk+1
µ A∗ − µk(Jk+1
µ +
k+1∑
i=1
Sk,i)A
∗
l−k)
)
=
=
l−1∑
k=0
µkJk+1
µ (A∗ −A∗
l−k) −
l−1∑
k=0
µk(
k+1∑
i=1
Sk,i)A
∗
l−k =
=
l−1∑
k=0
µkJk+1
µ (A∗ −A∗
l−k) −
l∑
j=1
l−1∑
k=j−1
µkSk,jA
∗
l−k.
Denote
F̂j :=
l∑
j=1
l−1∑
k=j−1
µkSk,jA
∗
l−k
and establish that Fj = F̂j .
At first we consider the case j = 1
F̂1 =
l−1∑
k=0
(µkSk,1)A
∗
l−k =
l−1∑
k=0
µk
(
H
k⊕
0
J (k)
µ
)
A∗
l−k =
On the efficient method of solving ill-posed problems 535
=
l−1∑
k=0
µk(
k∑
q=0
JqµHqJ
k−q
µ )A∗
l−k =
l−1∑
q=0
JqµHq
l−1∑
k=q
µkJk−qµ A∗
l−k =
=
l−1∑
j=0
JjµHj
l∑
i=j+1
µi−1J i−j−1
µ A∗
l−i+1 =
=
l−1∑
j=0
JjµHjJ
−1
µ
l∑
i=j+1
µi−1J i−jµ A∗
l−i+1 =
l−1∑
j=0
JjµTj,1.
Let now j ≥ 2. Then
F̂j =
l−1∑
k=j−1
µkSk,jA
∗
l−k =
l−j∑
p=0
µp+j−1Sp+j−1,jA
∗
l−(p+j−1) =
=
l−j∑
p=0
µp+j−1
(
H
p+j−1⊕
0
J (p)
µ
)
A∗
l−(p+j−1) =
=
l−j∑
p=0
µp+j−1
p∑
q=0
JqµHq(H
p+j−1⊕
q+1
J (p−q)
µ )
A∗
l−(p+j−1) =
=
l−j∑
q=0
JqµHq
l−j∑
p=q
µp+j−1
H
p+j−1⊕
q+1
J (p−q)
µ )
A∗
l−(p+j−1) =
=
l−j∑
k=0
Jkµ T̂k,j,
where T̂k,j = Hk
l−j∑
p=k
µp+j−1
(
H
p+j−1⊕
q+1
J
(p−q)
µ
)
A∗
l−p−j+1.
We need to prove that Tk,j = T̂k,j if j ≥ 2. For j = 2, k =
0, . . . , l − 2, it holds
536 Solodky S.G., Volynets E.A.
T̂k,2 = Hk
l−2∑
p=k
µp+1
(
H
p+1⊕
k+1
J (p−k)
µ
)
A∗
l−p−1 =
= Hk
l−2∑
p=k
µp+1
p−k∑
q=0
JqµHk+q+1J
(p−q−k)
µ )
A∗
l−p−1 =
= Hk
l−k−2∑
q=0
JqµHk+q+1
l−2∑
p=q+k
(µp+1Jp−q−kµ )
A∗
l−p−1 =
= Hk
l−1∑
i=k+1
J i−(k+1)
µ Hi
l−2∑
p=i−1
(µp+1Jp−i+1
µ )A∗
l−p−1 =
= HkJ
−1
µ
l−1∑
i=k+1
J i−kµ Hi
l∑
m=i+1
µm−1Jm−i−1
µ A∗
l−m−1 =
= Dk
l−1∑
j=k+1
Jj−kµ Ti,1
Finally, for j ≥ 3, k = 0, . . . , l − j, we have:
T̂k,j=Hk
l−j∑
p=k
µp+j−1
(
H
p+j−1⊕
k+1
J
(p−k)
µ
)
A∗
l−p−j+1 =
=Hk
l−j∑
p=k
µp+j−1
p−k∑
q=0
Jq
µHk+q+1
(
H
p+j−1⊕
k+1+q+1
J
(p−k−q)
µ
)
A∗
l−p−j+1 =
=Hk
l−j−k∑
q=0
Jq
µHk+q+1
l−j∑
p=k+q
µp+j−1
(
H
p+j−1⊕
k+q+2
J
(p−k−q)
µ
)
A∗
l−p−j+1=
=Hk
l−j+1∑
i=k+1
J i−k
µ J−1
µ Hi
l−j∑
p=i−1
µp+j−1
(
H
p+j−1⊕
i+1
J
(p−i+1)
µ
)
A∗
l−p−j+1=
On the efficient method of solving ill-posed problems 537
=HkJ
−1
µ
l−j+1∑
i=k+1
J i−k
µ Hi
l−j+1∑
m=i
µm+j−2
(
H
m+j−2⊕
i+1
J
(m−i)
µ
)
A∗
l−m−j+2 =
=Dk
l−(j−1)∑
i=k+1
J i−k
µ Hi×
×
l−(j−1)∑
m=i
µm+(j−1)−1
(
H
m+(j−1)−1⊕
i+1
J
(m−i)
µ
)
A∗
l−m−(j−1)+1 =
=Dk
l−j+1∑
i=k+1
J i−k
µ T̂i,j−1.
The lemma is proved completely.
3. Error bound
Concrete representation of discrete operator Al, l = 1, 2, . . .,
will shown in (23). To prove further statements we restrict our-
selves some additional conditions to Al. Namely, we will consider
discretization which satisfies the following conditions:
‖A∗A−A∗
lAl‖ ≤ δ
ρ
√
l
; ‖A−Al‖ ≤
(
δ√
l
)1/2
;
‖(A−Al)A
∗‖ ≤ δ
ρ
√
l
; ‖(A∗ −A∗
l )A‖ ≤ δ
ρ
√
l
.
(18)
It is not difficult to notice that first of inequalities (18) corre-
sponds to requirement of adaptive discretization strategy (5) with
α = 1/l.
Without lost of generality we will consider that number L of
steps of iterative process satisfies to the condition:
(19) δ
√
L ≤ 1.
Remind that to estimate error ‖ x† − x̂l ‖ we have to estimate
the last term in (9). To do this we estimate right-hand side of
538 Solodky S.G., Volynets E.A.
expansion (16) term by term. It’s easy to see that for the first
item
‖
l−1∑
k=0
µk(µI +A∗A)−(k+1)(A∗ −A∗
l−k)fδ‖ =
=
1
µ
l−1∑
k=0
‖ µk+1(µI +A∗A)−(k+1)‖‖(A∗ −A∗
l−k)fδ‖ ≤
≤ 1
µ
l−1∑
k=0
2δ√
l − k
.
Next statement gives bound for second term in the right-hand
side of (16).
Lemma 3. For any l = 1, 2, . . . , L there is a constant c1 < ∞
such that
l∑
k=1
‖Fkfδ‖ ≤ c1δ
√
l.
First of all by (18) we can write inequality
‖ (A∗ −A∗
l )fδ ‖≤‖ (A∗ −A∗
l )Ax
† ‖ + ‖ (A∗ −A∗
l )(f − fδ) ‖≤
≤ δ√
l
+
δ3/2
l1/4
≤ 2δ√
l
.
Due to (17) obviously equality
l∑
k=1
‖Fkfδ‖ =
l∑
k=1
‖
l−k∑
j=0
J−j
µ Tj,kfδ‖
On the efficient method of solving ill-posed problems 539
is true. Now let us estimate norm of Tj,kfδ and Jµ. Firstly we find
a bound of element Tj,1fδ:
Tj,1fδ := Dj
l∑
i=j+1
µi−1J i−jµ A∗
l−i+1fδ =
= Dj
l∑
i=j+1
µi−1J i−jµ A∗fδ −Dj
l∑
i=j+1
µi−1J i−jµ (A∗ −A∗
l−i+1)fδ.
Remind that
gl(λ) =
l−1∑
i=0
µi
(µ+ λ)i+1
.
Change order of summation in the last equality
gl−j(A
∗A) =
l−j−1∑
i=0
µiJ i+1
µ =
= µ0J1
µ + . . . + µl−j−1J l−jµ =
l∑
i=j+1
µl−iJ l−i+1
µ .
Hence
l∑
i=j+1
µi−1J i−jµ = µjJ1
µ + µj+1J2
µ + . . .+ µl−1J l−jµ =
=
l∑
i=j+1
µl+j−iJ l−i+1
µ = µj
l∑
i=j+1
µl−iJ l−i+1
µ = µjgl−j(A
∗A).
540 Solodky S.G., Volynets E.A.
By this relation Tj,1fδ can be written as
Tj,1fδ =
= Djµ
jgl−j(A
∗A)A∗fδ −Dj
l∑
i=j+1
µi−1J i−jµ (A∗ −A∗
l−i+1)fδ =
Djµ
jgl−j(A
∗A)A∗Ax† −Djµ
jgl−j(A
∗A)A∗(f − fδ)−
−Dj
l∑
i=j+1
µi−1J i−jµ (A∗ −A∗
l−i+1)fδ.
Taking into account estimations (cf. (7))
‖gl−j(A∗A)A∗A‖ ≤ 1, ‖gl−j(A∗A)A∗‖ ≤
√
l − j
µ
,
‖µi−1J i−jµ ‖ ≤ µj−1,
(20)
we have
‖Tj,1fδ‖ ≤ ‖Dj‖µj
(
ρ+
δ√
µ
√
l − j
)
+
+ ‖Dj‖µj−12δ
l∑
i=j+1
1√
l − i+ 1
.
Using the last relation and estimation
l∑
i=j+1
1√
l − i+ 1
≤
∫ l−j
0
dx√
x
= 2
√
l − j,
On the efficient method of solving ill-posed problems 541
we find
‖Tj,1fδ‖ ≤ µj−1‖Dj‖(µρ+ δ
√
µ
√
l − j + 4δ
√
l − j) ≤
≤ δ
µρ
√
l − j
µj−1(µρ+ (4 +
√
µ)δ
√
l − j) ≤
≤ δ
ρ
√
l − j
µj−2(4 +
√
µ+ µρ) =
c2δ√
l − j
µj−1,
where c2 = ρ+ 1/
√
µ+ 4/µ.
Now we have
‖Tj,2fδ‖ = ‖Dj
l−1∑
i=j+1
(µI +A∗A)−(i−j)Ti,1fδ‖ ≤
≤ µj−1‖Dj‖c2δ
l−1∑
i=j+1
1√
l − i
≤
≤ µj−1‖Dj‖c22δ
√
l − j − 1 ≤ 2c2
ρ
µj−2 δ√
l − j
.
In a like manner for every k = 1, 2, . . . one can find
‖Tj,kfδ‖ ≤
(
2
ρ
)k−1
c2µ
j−k δ√
l − j
.
Thus we have
‖Fkfδ‖ = ‖
l−k∑
j=0
(µI +A∗A)−jTj,kfδ‖ ≤
(
2
ρ
)k−1 2c2
µk
δ
√
l,
l∑
k=1
‖Fkfδ‖ ≤ 2c2δ
√
l
µ
l∑
k=1
(
2
ρµ
)k−1
≤ 2c2δ
√
l
µ− 2/ρ
.
We obtain assertion of Lemma for c1 = 2c2
µ−2/ρ .
Next statement contains finally estimation of third item in the
right-hand side of (9).
542 Solodky S.G., Volynets E.A.
Lemma 4. For every l ≤ L it holds
(21) ‖Blfδ‖ ≤ (4/µ+ c1)δ
√
l.
Taking into account Lemmas 2 and 3 we find
‖Blfδ‖ ≤ ‖
l−1∑
k=0
µkJk+1
µ (A∗ −A∗
l−k)fδ −
l∑
k=1
Fkfδ‖ ≤
≤
l−1∑
k=0
‖µkJk+1
µ (A∗ −A∗
l−k)fδ‖ +
l∑
k=1
‖Fkfδ‖ ≤
≤
l−1∑
k=0
‖µkJk+1
µ (A∗ −A∗
l−k)fδ‖ + c1δ
√
l.
Using (18) and (20) we estimate first item:
l−1∑
k=0
‖µkJk+1
µ ‖‖(A∗ −A∗
l−k)fδ‖ =
=
1
µ
l−1∑
k=0
‖µk+1Jk+1
µ ‖‖(A∗ −A∗
l−k)fδ‖ ≤ 1
µ
l−1∑
k=0
2δ√
l − k
.
As a result we have:
‖Blfδ‖ ≤ 2δ
µ
l−1∑
k=0
1√
l − k
+ c1δ
√
l ≤
(
4
µ
+ c1
)
δ
√
l.
The lemma is proved.
Final bound for method’s accuracy (6) is contained in next
statement.
Lemma 5. For every l ≤ L there exists a constant c3 > 0 such
that
(22) ‖x† − x̂l‖ ≤ ρκ
ν
ν+1
ν+1
2
l−ν/2 + c3δ
√
l.
On the efficient method of solving ill-posed problems 543
Taking into account (10), (14) and (21) from relation (9) we
have
‖x† − x̂l‖ ≤ ρκ
ν
ν+1
ν+1
2
l−ν/2 + δ
√
l√
µ
+ (4/µ + c1)δ
√
l =
= ρκ
ν
ν+1
ν+1
2
l−ν/2 + c3δ
√
l.
We obtain assertion of Lemma for c3 = 1/
√
µ+ 4/µ+ c1.
4. Algorithm of solving
First of all we describe adaptive discretization scheme used in
this paper for solving (1) with operators A ∈ Hr. Let the dis-
cretization level n depends on step of iteration process: n = n(l).
Denote as Γn area
Γn := ∪2n(l)
k=1 (2k−1, 2k] × [1, 22n(l)−k) ∪ {1} × [1, 22n(l)].
of coordinate plane corresponding to the basis E that appear in
the definition of class Hr.
Operators Al, l = 1, 2, . . ., will be constructed in the following
way:
(23) An(l) = Al =
2n(l)∑
k=1
(P2k − P2k−1)AP22n(l)−k + P1AP22n(l) .
Next statement characterizes some approximation properties of
the operator An(l).
Lemma 6. If parameter n = n(l) is chosen by relation
(24)
c4n2−2nr =
δ
ρ
√
l
, c4 = max
{
1 + 2r+3; 3 ∗ 2r; 2r +
2r+1
√
22r − 1
}
,
then for operator An(l) = Al (23) and any operator A ∈ Hr it
holds estimates (18).
544 Solodky S.G., Volynets E.A.
This lemma can be proved in the same way as Lemma 1 [1].
Denote
c5 := 1 +
1√
µ
+
1
µ
(
4 +
1
ρ
+ 2πκ1/2
)
+
c2(2 + (1 + π)κ1/2)
µ− 2/ρ
.
Now we describe algorithm that consists of Fakeev-Lardy regu-
larization method and proposed adaptive discretization strategy.
(1) Given data: A ∈ Hr, fδ, δ, ρ.
(2) Initialization: x̂0 = 0, b > c5 + 2.
(3) Iteration by l = 1, 2, . . .
(a) choosing of discretization level n = n(l, δ):
(25) c4n2−2nr =
δ
ρ
√
l
;
(b) computation of Galerkin functionals:
(fδ, ei), i ∈ (22n(l−1), 22n(l)]
(Aej , ei), (i, j) ∈ Γn(l) \ Γn(l−1);
(26)
(c) solving equation
(27) µx̂l +A∗
n(l)An(l)x̂l = µx̂l−1 +A∗
n(l)fδ;
(d) stop rule by discrepancy principle
‖ An(L)x̂L − P22n(L)fδ ‖≤ bδ,
‖ An(l)x̂l − P22n(l)fδ ‖> bδ, l < L.
(28)
(4) Approximate solution: x̂L.
To establish optimality of the algorithm we need two assertions.
Lemma 7. For any l ≤ L the inequality
‖Axl − f‖ ≤ ‖Alx̂l − f‖+ c5δ
is true.
Denote expression Axl − f as:
(29) Axl − f := Agl(A
∗A)A∗f − f = Z1 + Z2 + Z3 + Z4 + Z5,
On the efficient method of solving ill-posed problems 545
where
Z1 = Agl(A
∗A)A∗(f − fδ);
Z2 = (A−Al)A
∗gl(AA
∗)fδ;
Z3 = −(A−Al)(gl(A
∗A)A∗fδ − x̂l);
Z4 = A(gl(A
∗A)A∗fδ − x̂l);
Z5 = Alx̂l − f.
Let’s estimate all elements Z1 − Z4. By (7) we obtain
‖Z1‖ ≤ ‖AA∗gl(A
∗A)‖‖f − fδ‖ ≤ δ.
Taking into account (7) and (18) we find
‖Z2‖ ≤ ‖(A−Al)A
∗‖(‖gl(A∗A)Ax†‖ + ‖gl(A∗A)‖‖f − fδ ‖≤
≤ δ
ρ
√
l
(
ρ
√
l
µ
+ δ
l
µ
)
≤ δ
(
1√
µ
+
1
ρµ
)
.
Using Lemma 4 and (18) we have
‖Z3‖ ≤
(
δ√
l
)1/2
(4/µ+ c1)δ
√
l ≤ (4/µ+ c1δ).
To estimate Z4 we use Lemma 2 and (17)
Z4 = ABlfδ =
l−1∑
k=0
AµkJk+1
µ (A∗ −A∗
l−k) −
l∑
k=1
AFkfδ.
By inequality
‖µkA(µI +A∗A)−(k+1)‖ ≤ 1
µ
sup
λ
λ1/2(1 − λgk+1(λ)) ≤
≤
κ1/2
µ
(k + 1)−1/2,
we have
‖Z4‖ ≤ 2δκ1/2
µ
l−1∑
k=0
1√
(k + 1)(l − k)
+
l∑
j=1
‖AFjfδ‖.
546 Solodky S.G., Volynets E.A.
We estimate both items in the right-hand side of last relation.
So
l−1∑
k=0
1√
(k + 1)(l − k)
=
N∑
j=1
1√
j(N − j)
≤
∫ N
0
dx
x(N − x)
= π.
Now
‖AFjfδ‖ ≤
l−j∑
i=0
‖A(µI +A∗A)−iTi,jfδ‖ ≤
≤
l−j∑
i=0
µ−i‖µiA(µI +A∗A)−i‖‖Ti,jfδ‖ ≤
≤
(
1 +
l−j∑
i=1
µ−i√
i
µi−j√
l − j
)
κ1/2c2
(
2
ρ
)j−1
δ =
=
κ1/2c2
(
2
ρ
)j−1
δ
µj
(
1 +
l−j∑
i=1
1√
i(l − i)
)
≤ c6
(
2
ρµ
)j−1
δ,
where c6 =
(1+π)c2κ1/2
µ .
Then
l∑
j=1
‖AFjfδ‖ ≤ c6δ
l−1∑
j=0
(
2
ρµ
)j
≤
(1 + π)c2κ1/2
µ− 2/ρ
δ.
Finally we obtain
‖Z4‖ ≤ κ1/2
(
2π
µ
+
(1 + π)c2
µ− 2/ρ
)
δ.
By combining received estimates we obtain the statement of
Lemma.
Lemma 8. Let L satisfy to discrepancy principle (28), where
b > 2+c5, A ∈ Hr and discretization parameter is chosen as (24).
On the efficient method of solving ill-posed problems 547
Then there are constants b1, b2 > 0 exist such that
b1δ ≤ ‖AxL − f‖ ≤ b2δ.
According to (24) for any l ≤ L it holds
‖(I − Pl)f‖ ≤ δ.
Using (28) we have
‖ALx̂L − f‖ ≤ ‖ALx̂L −PLfδ‖+ ‖PL(f − fδ)‖+ ‖(I − PL)f‖ ≤
≤ (b+ 2)δ.
Then by Lemma 7 we find
‖(AxL − f)‖ ≤ b2δ
with b2 = b+c5+2. On the other hand, in (L−1)-th step according
to (28)
‖AL−1x̂L−1 − PL−1fδ‖ > bδ.
Using triangle inequality and Lemma 7 we find from (29) with
l = L− 1
‖AxL−1 − f‖ ≥ ‖AL−1x̂L−1 − PL−1fδ‖ − (c5 + 2)δ.
Let’s estimate
‖AxL − f‖2 = µ2L
∑
k
|λk|2(ν+1) (v, ψk)
2
(µ+ λ2
k)
2L
=
= µ2
(
µ2(L−1)
∑
k
|λk|2(ν+1) (v, ψk)
2
(µ+ λ2
k)
2(L−1)
(µ+ λ2
k)
−2
)
≥
≥
(
µ
µ+ j2
)2
(
µ2(L−1)
∑
k
|λk|2(ν+1) (v, ψk)
2
(µ+ λ2
k)
2(L−1)
)
.
Consequently
‖AxL − f‖ ≥ µ
µ+ 1
‖AxL−1 − f‖.
Finally we have
‖AxL − f‖ ≥ b1δ,
548 Solodky S.G., Volynets E.A.
where b1 = µ
µ+1 (b− 2 − c5). Thus Lemma is completely proved.
5. Optimality of the algorithm. Amount of Galerkin
information
In the following statement we will show that described algo-
rithm (23)-(28) guarantees the optimal order of accuracy O(δ
ν
ν+1 )
on the whole class of the considered equations.
Theorem 1. Algorithm (23)-(28) achieves the optimal order of
accuracy O(δ
ν
ν+1 ) on the class of equations with operator A ∈ Hr
and minimal-norm solutions x† ∈Mν,ρ(A), ν > 0.
From Lemmas 1, 8 and relation (13) it follows that
(30) δ
√
L = δ
( |dν,L(v)|
‖AxL − f‖
) 1
ν+1
≤ δ
(
ρκ(ν+1)/2
b1δ
) 1
ν+1
≤
≤
(
ρ
b1
) 1
ν+1
√
µ(ν + 1)
2
δ
ν
ν+1 ,
|cν,L(v)|L−ν
2 = |cν,L(v)|
(‖ AxL − f ‖
|dν,L(v)|
) ν
ν+1
≤ ρ
1
ν+1 (b2δ)
ν
ν+1 .
Substituting the estimates into (22), we have
‖x† − x̂L ‖≤ ξδ
ν
ν+1 ,
where ξ = ρ
1
ν+1
(
b
ν
ν+1
2 + c3b
− 1
ν+1
1
√
µ(ν+1)
2
)
.
The theorem is proved.
Corollary. To achieve the optimal order of the accuracy on
the considered class of equations in the framework of algorithm
(23)-(28) it is enough to calculate
(31) O(δ
− ν+2
(ν+1)r log1+1/r δ−1)
of Galerkin functionals (26).
To proof this statement it is sufficiently to estimate volume of
the inner products that is equivalent to square of figure Γn, which
On the efficient method of solving ill-posed problems 549
is equal to (n + 1)22n. Using (24) and (30) in this expression we
have estimate (31).
Remind (see Section 1) that to achieve the optimal order of ac-
curacy in traditional Galerkin discretization scheme it is necessary
to calculate O(δ−2/r) inner products (26). Thus for any ν > 0 al-
gorithm (23)-(28) is more economical then methods using in [3]
with traditional Galerkin discretization scheme.
References
[1] Maas P., Pereverzev S.V., Ramlau R., Solodky S.G. An adaptive dis-
cretization for Tikhonov-Phillips regularization with a posteriori param-
eter selection // Numer. Math. — 2001. — V. 87, No 1. — P. 485-502.
[2] Maas P., Rieder A. Wavelet-accelerated Tikhonov-regularization with ap-
plications // Inverse Problems in Medical Imaging. — Springer: Vienna,
1997. — P. 134-158.
[3] Plato R., Vainikko G. On the Regularization of Projection Methods for
solving Ill-posed Problems // Numer. Math. — 1990. — 57. — P. 63-79.
[4] Solodky S.G. Economic discretization scheme for the nonstationary iter-
ated Tikhonov method // J. Optim. Theory Appl. — 2007. — 132, No. 1.
— P. 21-39.
[5] Solodky S.G. An optimal approximations for solving linear ill-posed prob-
lems // J.Complexity. — 2001. — V.17, No. 1. — P. 98-116.
[6] Solodky S.G. An optimal approximations for stationary iterated Tikhonov
method // East J. Approx. — 2004. — V.10, No. 1-2. — P. 189-200.
[7] Solodky S.G. On a quasi-optimal regularized projection method for solving
operator equations of the first kind // Inverse Problems. — 2005. — V. 21,
No. 4. — P. 1473-1485.
[8] Solodky S.G. Adaptive discretization of ill-posed problems // Doklady
Ross. Akad. Nauk. — 2002. — V. 382, No. 4. — P. 460-462.
[9] Solodky S.G. An one scheme of discretization for Landweber method //
Zh. Vychisl. Mat. Mat. Fiz. — 2004. — V. 44, No. 3. — P. 387-396.
[10] Solodky S.G. An economic selection of discrete information in solving ill-
posed problems // Izvest. VUZ. Mat. — 2005. — No. 12. — P. 56-62.
[11] Vainikko G.M., Veretennikov A.Y. Iterative procedures in ill-posed prob-
lems // Moskow: Nauka, 1986.
|