книги / Регулярные методы решения некорректно поставленных задач
..pdfВведем обозначение
6opt(M/>{£)$) “ S^P eopt(w/»?)*
ate ( O s
Те о р е м а 95. Справедливо соотношение
Urn eopt(«/>{ |> s ) = 0. a-»0
Д о к а з а т е л ь с т в о . Имеем
Л |
2 |
|
I |
<J2U 2 |
TV |
Л ч |
2 |
A |
2 |
|
eО |
|
|
|
< |
a 2 + |
U |
||||
|
|
|
/=1 |
+ h 2? |
X^v |
|
i-N + l |
|
7* |
|
|
|
|
|
|
|
|
|
|||
Так |
как 2 |
и} |
|
О, W-*00, то можно выбрать такое 7У=УУ(а), |
||||||
что |
*=ЛГ+1 |
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
lim N(p) = +°°, |
|
lim |
— а 2 |
= 0. |
|
|
|
|
|
а-*0 |
|
|
ст-^О |
^JV |
|
|
|
|
|
Теорема доказана.
Будем рассматривать решение задачи I при фиксированном Uf и возмущении £ G {£ } £,т.е. будем строить ({Г},«/,{£}^-оптималь ные приближения. Легко видеть, что
X /а2 + а 2/?
4 ( “/> {* > s)= 2
;=i Х,(а, + Х,)2
Минимизируя ег (м^, {£}$) по а( , получим
£o 2f ]
eoptW > ^)s)
<=1 М $ 2 + //2 )
при a, = a/*pt = \ ,o2/fj(i = 1 ,2 ,...) - Тогда ({Г}, м/,{?}£)-опти- мальное приближение определяется по формуле
п |
и |
|
*орt = z |
|
|
/=1 *2 + Д |
ч д : |
|
Легко видеть, что eopt(«/,{£} 3) = eopt |
||
но, как доказано выше, |
lim eopt |
(и/,{£Ь) *0. |
|
Ъ-+0 |
° |
( 12)
. и, следователь-
, Далее предположим, что псевдорешение Uf принадлежит классу {uf}c ^{u: м2< с 2}, где бесконечномерный вектор с= (clfc2__ )
*таков, что ряд 2 |
с2 сходится. |
/ = |
1 |
201
Тогда |
({Г}, {uf )c,{%}$ оптимальное приближение определяет |
||||||
ся по формуле |
|
|
|
|
|
||
*4>pt |
2 |
\ с } |
|
f , |
|
|
|
о2 + Xjcf |
л/Х/ |
' ’ |
|
|
|||
|
/=1 |
|
|
||||
а погрешность этого приближения - |
по формуле |
||||||
|
|
|
|
Л 2 |
2 |
|
|
eo p |
t |
{£}' ) - |
2 |
о2 с2 |
|
|
|
о2 + |
|
|
|||||
|
|
|
/=i |
|
|
||
|
|
|
А |
|
|
|
|
и стремится к нулю при а-*0. |
|
|
|
||||
Пусть система {е/} |
конечномерна (размерности 7V). Отнесем к |
||||||
классу {м/}дг все псевдорешения, для |
которых и2 < С 2 (/ = 1 ,... |
||||||
...,А А ), |
где |
постоянная |
С априорно |
задана. Тогда |
|||
{ |} а)-оптимальное решение задачи |
(1) |
является решением регу- |
|||||
ляризованного уравнения |
|
|
|
|
|||
Оx E+A*A) u=A*f |
|
|
|
|
|
||
при а = <*opt = о2/С2. При этом |
|
|
|
||||
|
|
|
N |
а 2С 2 |
|
|
|
е$Р*««/>лг,Ш 5) = |
2 |
— |
■ ' |
2 . |
|||
|
|
|
»=1 |
о2 + X, С2 |
|
Доказательства этих утверждений достаточно просты и поэтому не приводятся.
4. Оценим точность оптимальных приближений. Обозначим
Д2 ({«/}, |
< П ) = |
, |
sup |
e2pt( u , a |
|
|
|
|
ue { u /}, |
*е{*} |
|
где класс {£) Q (£ ) j |
• Аналогично определим величину |
||||
A2({«/},U >S )= |
sup |
е5р,(и ,{ ? } ;) . |
|||
Т е о р е м а |
96. Цусгь |
|
|
||
{иг } = ( щ } кр щ |
|
|
|
||
|
|
|
2р/(2к+1) |
||
■M(t)оо |
|
< /?2 р /(2 к + 1 ) 1 |
|||
|
|
|
|
|
|
= { £ £ { £ } - • |
2 а ^ Я / ( 2 к ^ 1 ) < 0 4 к Я/ ( 2 к + \ ) ^ |
||||
где к > 0 , |
1, <7 ^ |
1 —некоторые постоянные, причем —+ — = 1. |
|||
|
|
|
|
|
Р Я |
202
Тогда справедливо неравенство
A({w/}^ , |
Ш * |
) < С ка 2к/(2*+1)Д 1/(2к+1) , |
|
(1 3 ) |
||||
где С \ - |
1 |
(2к)2к/(2к + 1\ Оценка (13) неулучшаема. |
|
|||||
2к+1 |
|
|||||||
|
|
|
|
|
|
|
|
|
Д о к а з а т е л ь с т в о .С о г л а с н о (9) |
|
|
|
|||||
о |
, |
00 o j g f x y |
|
|
|
|||
где £2 = и2/Х? к . Рассмотрим функцию |
|
|
|
|||||
|
c r V x 2K |
|
|
Х > 0, |
|
|
|
|
|
а 2 +£2Х2к+1 |
’ |
|
|
|
|||
|
|
|
|
|
||||
с числовыми |
параметрами |
о 2 3* 0, g 2 > 0. |
Легко |
показать, |
что |
|||
max ^(Х) = ^(Хтах) = С 2 о 4к/(2к+1) ^ 2/(2к+1)( |
|
|
||||||
\ > О |
|
|
|
|
|
|
|
|
гдеХщах = (2к О2/^ 2) 1 /(2 к + ,). Следовательно, |
|
|
||||||
e o p t ( « / ,? ) < C 2 |
2 |
а/4к/(2 к+ 1) О/2/(2к + 1) |
|
|
||||
|
|
|
/=1 |
|
|
|
|
|
Применяя неравенство Гёльдера, получаем |
|
|
|
|||||
. г р , ( « л й < с н £ |
|
f |
|
|
|
|||
|
|
|
/=1 |
|
|
|
|
|
Отсюда следует (13). |
|
|
|
|
|
|||
Пусть |
Uf = Ujei, |
где м7* = \ “ Я 2, £ = |
£ / £ , |
таково, |
что |
|||
Л/^2 = а2 = ^ |
j X f K+1R 2K 2K +1) . Л тко |
проверить, что |
щ Е |
|||||
е (и/К> |
|
|
причем |
|
|
|
|
|
eopt {uf ,$) = CKo2*l(2K" ) R l « 2K+l\ |
|
|
|
|||||
т.е. оценка (13) неулучшаема. Теорема доказана. |
|
|
||||||
З а м е ч а н и е . Пусть р - |
1, q = °°. Тогда { £} ~ = {£}£, и, следо |
|||||||
вательно, |
|
|
|
|
|
|
|
|
Д « и Д '. |
{ | } ^) < Ск Q2k/<2k+1)^ ! /(2кт1 >. |
|
(14) |
|||||
Пусть р = 2к + 1, |
= |
2к +1 |
|
|
|
|||
---------- ; обозначим |
|
|
|
|||||
|
|
|
|
2к |
|
|
|
|
{uf ) k Huf ) pK={ur : |
2 |
(» 2/Xf ) 2 < К 2} , |
|
|
||||
Ш 0 = Ш |
‘' ={?: |
2 |
о2 < о2}. |
|
|
|
||
|
|
|
|
/= I |
|
|
|
|
203
Тогда из (13) следует оценка |
|
) < С к о 2<£« а*+ ,>Л, « 2“+ ,>. |
(15) |
Укажем достаточные признаки принадлежности псевдорешения
(1) классу {uf ) к . |
|
|
Л е м м а 51. Если U f = A * h , h E F , II h II/г <Я , |
то Uf G {щ } к |
|
при к = 1/2. Если Uf = (А*А)Кw, |
Я, то Uf Е |
при любом |
к > 0 .
Условия леммы выполняются, например, если оператор А нор мально разрешим (§ 24). Для доказательства следует воспользо ваться разложениями (5) и (6) для элементов w и h соответ
ственно. |
|
|
|
|
{uf)*K={uf : U f - { A * A ) Kwy w ^ H , |
||||
З а м е ч а н и е . |
Пусть |
||||||||
\\w\\H <Я }. Легко |
видеть, что класс {uf}*K компактен в Я при |
||||||||
любом к > 0 . Определим квазирешение ик |
задачи |
(1) как реше |
|||||||
ние задачи |
|
|
|
|
|
|
|
|
|
\\Аик - / \ \ р = |
min |
\ \ A u - f \ \ F . |
|
|
|
||||
|
|
U<E{uf ) к |
|
|
|
|
|
||
Здесь считается, что возмущение £ не случайно. Полагая |
|
||||||||
д ( { « /Я ,< Ш ) = |
, . . s u p , , . |
|
|
|
|||||
|
|
|
Uf^{uf yK, ^ U ) a |
|
|
|
|||
где {£}£ ={%6 F : |
II | |
11* < а ) , можно показать, что |
|
|
|||||
А ({И/}; М}*а ) < ( 2 о 2кД )1/(2к+1К |
|
|
(16) |
||||||
Сравнивая |
(15) |
и |
(16), замечаем, что порядки оценок сов |
||||||
падают, однако постоянная в (15) |
меньше, чем в |
(16), по край |
|||||||
ней мере для к = 1/2,1,2. |
|
|
|
|
|
||||
5. |
Рассмотрим |
проблему эффективной реализации |
( { Г } , U f , |
||||||
{ £ h ) -оптимальных |
приближений |
(12). |
Определим |
элемент |
|||||
uq opt |
|
f \ |
|
fi |
|
|
|
(17) |
|
'=* |
u2 + / j |
|
|
|
|
||||
|
({Г}, иf ,{£}а) -квазиоптимальным при |
||||||||
который |
будем называть |
||||||||
ближением,. Заметим, |
что |
для реализации |
(17) |
требуется знать |
лишь а, т.е. точность задания элемента/ .
Сформулируем некоторое допущение, которое назовем прин ципом линеаризации. Пусть
Пft
V A,(S2 + /7 ) |
у/% |
204
Б удем считать, что в разложении
/г( ? /) = Я 0 ) + /7 '(0 )^ + . . .
с достаточной степенью точности можно ограничиться линейными членами.
Т е о р е м а |
97. |
Пусть выполняется |
принцип линеаризации. |
Тогда |
|
|
|
М Лйк opt - |
Uf II |
pt( uf>{%} £ ). |
(18) |
Д о к а з а т е л ь с т в о . Имеем
1 |
Г |
o2fi |
+f? |
|
|
|
F i b ) * — |
|
|
— |
+ — ------- — |
|
|
И |
. |
d*+/i* |
(32 + л2)2 |
|
|
|
Следовательно, |
|
|
|
Л 2 у*2 |
||
|
|
|
|
|
||
^ И и , о Р* - и / 1 1 и ^ |
£ F 2 & ) < 9 |
2 — ^ |
-------- . |
|||
|
|
|
|
f= I |
i = ' h t f 2 + f h |
|
Теорема доказана. |
|
Если Uf Е { Uf) l , то, учитывая (14), можно |
||||
С л е д с т в и е . |
||||||
получить и оценку |
точности квазиоптимальных |
приближений: |
||||
М II uq opt - |
uf IIН2 £ 9 СКг (а 2кЯ )2/<2к+1>. |
|
Пусть далее псевдорешения Uf Е { Uf) к, возмущения £ G {£ } а ,
а класс |
регуляризаторов ( Г ) = |
= (Г : |
Те{- - otXf 2 кet-} , |
|||||
а > 0 - |
параметр. Тогда |
|
|
|
|
|
||
|
|
|
\ 4 к |
+ 1 _ 2 |
. л |
2ч2к„2т,2 л 3 |
|
|
е1к (“/.? )= |
Z |
Л/ |
О/ |
+ Of |
Л/ |
&• |
|
|
|
(о + Х?к+1)2 |
|
|
|||||
|
|
'= 1 |
|
|
|
|||
где, как и выше, gf |
=Uj'KJ2li. Положим |
|
||||||
|
X4,c+1 |
|
|
|
|
X2* |
Х >0. |
|
<p(k) = |
|
|
Ф (X) =------------- |
|||||
|
(а + Х2к+1) 2 |
|
|
(а + Х2к+1)2 |
|
|||
Имеем |
|
|
|
|
|
|
|
|
max <р(X) = С 'а - 1 / ( 2 к + 1) J |
max ^ (X) = с"а2к^ 2к+,\ |
|||||||
\ |
|
|
|
|
л |
|
|
|
где |
|
|
|
|
|
|
|
|
(4к +1)(/»к + 1 )/(2 К+1) |
|
|
|
|
||||
С' = |
(4к + 2)2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
2к/(2к +1) |
|
|
||
\ |
2к + 1 |
/ \ |
#с + 1 |
/ |
|
|
|
|
205
В этих обозначениях
(«/.«)<
< С 'а 2а - |/(2к + 1) + С''Л2а2к/(2к + 1)н 62 (а)
для любых Uf £ { Uf ) к, |
{£}„. Поэтому |
||||
inf |
е2 |
U |
) 0) < |
inf |
е2 (а) = |
а > О |
* а |
|
а |
> |
О |
= ек(«к) = Ск2 (а2к/г)2/(2к + 1). |
|
||||
С,2 = (2к + 1) |
|
|
l/(2K-t 1) |
||
|
|
|
|
= |
Их)’ |
|
2кС |
Таким образом, |
|
infe ({ М/}к„ { П а ) < С к (о2к/?)1/(2к + 1). |
(1 9 )
(20)
( 21)
Полученная оценка неулучшаема по порядку величин а и Я. Чтобы
убедиться в этом, достаточно взять Uf - ще19 Uj = \ 2KR 2,% = £/со/, М%2 = а 2, а = о2 R~2 и вычислить е к (<Uf, £).
Таким образом, справедлива
Т е о р е м а 98. Погрешность ({ 7 ^ } , {w/}K, { £ } CT)-0wrw-
мольных приближений не превосходит правой части неулучшаемой по порядку величин о и R оценки (21). Для получения квазиоптимальных приближений в Т*-регуляризирующем алгоритме доста
точно выбрать a = |
по формуле (20). Точность этих приближе |
ний совпадает по порядку величин о и R с точностью оптимальных |
|
приближений. |
|
З а м е ч а н и е . |
Вычисление ( { Т£ }, { } к, { £ } 0)-квазиопти- |
мальных приближений может быть затруднено в связи с необхо димостью знания спектрального разложения оператора А*А. Пусть оператор L таков, что L e t = \ T 2Kej, NA*A C./V/,. Тогда ^ -р егу л я
ризация сводится к решению уравнения
(CLL + A*A)U =A*J'9
которое может быть выполнено достаточно эффективно.
Далее рассмотрим случай Та-регуляризации, где Та = аЕ. Легко
видеть, что |
|
€тп ( иг Л) - 2 |
+ cr |
i = i (a + X,)2 |
/=1 (a + X/)2 |
206
Б удем считать, что м/ Е { Uf) к, £ Е |
{И стТогда |
|||||||
2 |
/ |.\ |
S |
W |
. |
2 |
£ |
X«?V |
— |
е?’ |
(wr, £) = |
2 |
----------(а + Х/)2- |
+ а |
|
2 |
---------- |
|
|
а |
/= i |
|
/= 1 |
(а + Х/)2 |
где, как и раньше, gf = uf /X2 к.
Л е м м а 52. Пусть <^(Х) = Х/(а + X)2, ф(X) = Х2к/(а + Х)2, X > 0.
Тогда
*(Х )< — , \К Х )< |
Ска 2к~2, |
0 < к < 1, |
|
|
|
4а |
Х2(к_1), |
к > 1 , |
|
М-НЬГ0-10’-
Используя эту лемму, получаем
« |
Х.о? |
а 2 |
|
2 |
- ' ■■-■ < — , |
|
|
i= |
1 (а + Х,-)2 |
4а |
|
|
>2 к „ 2 |
OL2KCKR 2 , 0 < к < 1, |
|
а 2 |
X; gt |
|
|
2 |
|
|
|
|
»= 1 (а + X,)2 |
а 2Я2, |
к > 1. |
|
|
Эти оценки неулучшаемы. Действительно, полагая £ = £,-cof, Л/£2= о2, а = Х|, будем иметь:
Х/О/
/ = 1 (а + X*)2 |
4а |
| _
Аналогично при 0 < к < 1, полагая иу = ы,е„ к2 = X2KR2 , а = ------ X,
1/
получим
°°Х2кя ?
а2 2 |
— i |
|
=а2кСкЯ2. |
|
|
/=1 |
(а + X,)2 |
|
|
|
|
Остается заметить, что при к > |
1 |
|
|||
Игл |
2 |
№ |
= £>2 |
|
|
|
R 2. |
|
|
||
<х -* о |
i = 1 (а + X/)2 |
|
|
||
Используя полученные выше оценки, имеем |
|
||||
|
|
|
а2 |
( a2KCKR2, 0 < к < 1 , |
|
4 а (<м/ > « Л £><, )<— + 1 |
|
||||
|
|
|
4а |
[ а2/?2, |
к > 1. |
|
|
|
|
207
Минимальное значение правой части этой оценки достигается при
_ _ Л -2/(2к+1)( |
0 < к < 1> |
|
8к С. |
|
(22) |
|
|
|
— R ^ 2' \ |
к > 1. |
|
8 |
|
|
Учитывая это, получаем |
|
|
|
С2(о4кЯ2) ,/(2’£+1), 0 < к < 1, |
|
е7’а ( i uf ) к> { £ ) а) ^ ) |
|
(23) |
3 |
4/3 |
|
“ к |
-------- |
о4/3Л2/3, К>1, |
I |
V 64 |
|
Ск2 = (2к + 1)Ск1/(2к+,)/(8к)(2к+1)/(2к).
Из сказанного выше вытекает справедливость следующего утверж дения:
Т е о р е м а 98. Пусть иа удовлетворяетуравнению (aE + A*A)u0l=A*f
и параметр а определен согласно (22). Тогда точность полученно го приближения к решению основной задачи определяется оцен кой (23).
З а м е ч а н и е . Нетрудно видеть, что порядки оценок (21) и (23) при 0 < к < 1 совпадают, а при к > 1 оценка (23) по а хотя и имеет более низкий порядок, однако соответствующая постоянная не зависит от к, что существенно облегчает использование (23). Кроме того, -алгоритм реализуется более просто, чем Т£.
6. Приведенные результаты применимы к широкому кругу задач. В качестве примера рассмотрим решение эволюционного уравнения
du
---- = Zw, и (0 )= /, 0 < f < Г, |
(24) |
dt |
|
где L — положительно определенный самосопряженный оператор с дискретным неограниченным спектром, действующий из Я в Я. Предполагается, что задача (24) разрешима.
Обозначим A t = e~t L . Тогда (24) сводится к решению парамет рического операторного уравнения
Atu ~f> |
(25) |
Пусть {е,- ) — полная система |
собственных функций оператора L : |
Lej = \ e h /= 1 , 2 , . . . , |
lim Х/ = +<». |
Тогда псевдорешение (25) имеет вид
Uf(t)= 2 ехр{ Xjt) ft eiy ft = (/, et)H. i = 1
Для задачи (25) ( { T ) , м^,£) -оптимальное решение имеет вид
“ optO )= . 2 |
f l |
exp {\jt}ftei. |
|
af+ff |
|||
J = l |
|
Отсюда легко получить ({ T }, Uf9{ £ }$) -оптимальное и соответст венно квазиоптимальное решения.
T - t
Положим к = ------ . Тогда, очевидно, 21
Uf{t) = (Af A t)Kuf (T) = A j Kuf (T),
т.е. выполняются условия леммы 51.
Гд-регуляризованные приближения определяются согласно формуле
ua(t)= 2 exp(X,f)(l + а ехр(2Х,- Т)) 1Л е,.
.1 = 1
Замечая, что {иft) } к ={ uf. II м /Г ) \\H < R] и используя (21), получаем оценку
M\\uaK( t ) - u f (t) II2И < С 2КaHi-tiT)R 2t/T9 о < г < Г.
Как бьшо доказано выше, порядок этой оценки неулучшаем.
В заключение ’ отметим* что |
проведенный |
анализ справедлив |
|
и в том случае, когда элемент |
/ случаен; |
необходимо только |
|
потребовать, что |
= 0, и заменить везде /}2 на M f *. В случае, |
||
когда А = Е, задача I совпадает с задачей оптимальной фильтрации |
|||
случайного процесса / |
[2]. |
|
|
§ 26. Численные алгоритмы выбора параметра регуляризации
1. Численное решение некорректнее поставленных задач методом регуляризации А.Н, Тихонова обычно сводится к задаче минимиза ции квадратичной формы
Фа [м] = IIЛw - / !£, + а \\и ll£, а > 0 , |
(1) |
на пространстве векторов и = (их, . . . , ип)т S R n и |
к определению |
параметра регуляризации а из дополнительного условия вида
где ф —нелинейный функционал, определенный на решениях задачи
14. В.А. Морозов |
209 |
( 1) , а еу - априори задаваемый уровень допустимых значений функционала ф.
Вфункционале ( 1) А означает прямоугольную матрицу размера
тX п\С= С Т - априори задаваемая положительно определенная матрица порядка и, определяющая степень корреляции компонент
вектора и, llu \\2С =(Си, u)Rn,/ = ( / 1, . . . ,fmy € . R m. |
Евклидову |
||
норму в Rn и Rm обозначаем соответственно II • ll„, б • llm . |
|||
Далее рассматриваются следующие три способа выбора парамет |
|||
ра регуляризации а: |
|
|
|
р(а) = |
II Аиа - f IIw = ер |
{принцип невязки): |
(2) |
у (а) = |
II иа 1с = еу |
{принцип квазирешений) ; (3) |
|
<р{а) = р2(а) + а у 2(а) = е^ |
{принцип сглаживающего |
||
|
|
фун кционала). |
(4) |
Величина ер характеризует задаваемый уровень невязки и опре |
|||
деляется |
методом невязки. Величина еу определяется |
методом |
квазирешений и связана с априорными сведениями о размере
области, в которой находится искомое решение. Величина |
прак |
тически выбирается из тех же соображений, что и величина ер . |
|
В § 9 доказано, что функции р(а), у{а) и <р(а) непрерывны при |
|
а > 0, при этом р(а) и <р(а) строго монотонно возрастают, a |
7(a) |
строго монотонно убывает. Там же вычислены предельные значения для р(а) и ip(a) при а-*0,+ °°. Таким образом, если ер. еу, е^ принадлежат множествам значений функций р ,у и <р, то уравнения (2 ) -(4 ) однозначно разрешимы. Это условие мы предполагаем всегда выполненным. Корни уравнений (2) —(4) обозначим через ар, ау и соответственно; считается,чго 0 < а^ < 00 \/ ф.
Заметим, что отмеченные свойства функций р, у и у? не обеспечи вают безусловной применимости быстро сходящихся алгоритмов
ньютоновского типа для отыскания корней уравнений |
(2)—(4). |
|||||||||
Далее приводятся такие модификации этих уравнений, к которым |
||||||||||
методы ньютоновского типа всегда применимы. |
|
|
|
|||||||
2. |
Положим R (а) = р( 1/а), |
F{a) = <р(1/а), |
а > 0. |
Справедлива |
||||||
следующая лемма (s - |
показатель степени). |
|
|
|
||||||
Л е м м а 53. Функции R s(ot), ys{ot) и |
F S(OL) |
являются |
убываю |
|||||||
щими выпуклыми вниз функциями при любом s > |
0 и возрастаю |
|||||||||
щими выпуклыми вверх функциями при - 1 < s < |
0. Если s < - 1 , |
|||||||||
то рассматриваемые функции могут менять направление выпук |
||||||||||
лости. |
|
|
|
|
|
|
|
|
С - |
К ТК, где |
Д о к а з а т е л ь с т в о . |
Выполнив |
разложение |
||||||||
К т — верхняя |
треугольная матрица, |
и о б о з н а ч и в = KuaiN = |
||||||||
= АК~1, найдем: |
|
|
|
|
|
|
|
|
|
|
р(а) = II Nxa - |
/ |
II,,,. |
у(а) = II |
II„, |
|
|
|
|
||
y>(a) = II Nxa - |
/ |
II l, + a II |
I I . |
|
|
|
|
(5) |
210