Hyperbolic cross and complexity of various classes of linear ill-posed problems
The present paper is a survey of the latest results obtained in the fields of information and algorithmiс complexity of severely ill-posed problems.
Saved in:
| Date: | 2017 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Institute of Mathematics, NAS of Ukraine
2017
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/1748 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860507602707808256 |
|---|---|
| author | Myleiko, G. L. Solodkii, S. G. Милейко, Г. Л. Солодкий, С. Г. Милейко, Г. Л. Солодкий, С. Г. |
| author_facet | Myleiko, G. L. Solodkii, S. G. Милейко, Г. Л. Солодкий, С. Г. Милейко, Г. Л. Солодкий, С. Г. |
| author_sort | Myleiko, G. L. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2019-12-05T09:25:34Z |
| description | The present paper is a survey of the latest results obtained in the fields of information and algorithmiс complexity of
severely ill-posed problems. |
| first_indexed | 2026-03-24T02:11:56Z |
| format | Article |
| fulltext |
УДК 519.642
Г. Л. Милейко, С. Г. Солодкий (Iн-т математики НАН України, Київ)
ГIПЕРБОЛIЧНИЙ ХРЕСТ I СКЛАДНIСТЬ РIЗНИХ КЛАСIВ
ЛIНIЙНИХ НЕКОРЕКТНИХ ЗАДАЧ
The present paper is a survey of the latest results obtained in the fields of information and algorithmiс complexity of
severely ill-posed problems.
Приведен обзор последних результатов в области информационной и алгоритмической сложности некорректных
задач.
1. Вступ. На сьогоднi однiєю з найбiльш актуальних проблем, що виникають при побудовi
чисельних методiв розв’язування рiзного роду задач, є пiдвищення їх ефективностi шляхом
забезпечення мiнiмально можливих iнформацiйних та обчислювальних витрат зi збереженням
точностi наближення. Подiбного роду питання iнтенсивно вивчаються в межах загальної теорiї
оптимальних алгоритмiв, основи якої були закладенi у монографiях [16, 33]. У рамках цiєї
теорiї пiд iнформацiйною складнiстю розумiється найменший обсяг дискретної iнформацiї, що
необхiдна для знаходження наближеного розв’язку iз заданою точнiстю, а пiд алгоритмiчною
складнiстю – мiнiмальне число арифметичних дiй, якi потрiбно виконати для побудови такого
розв’язку.
Варто зазначити, що для некоректних задач проблема їх складностi до недавнього часу
залишалася вiдкритою. Бiльш того, в [34, 35] обговорювалася принципова можливiсть коректної
постановки подiбних задач. Тому результати робiт [13, 23], що мiстять першi точнi порядковi
оцiнки iнформацiйної та алгоритмiчної складностi деяких класiв помiрно некоректних задач,
можна вважати вiдправною точкою у вивченнi зазначеної проблематики.
Основним об’єктом дослiджень у теорiї лiнiйних некоректних задач є операторне рiвняння
Ax = f, (1)
де A — лiнiйний неперервний оператор, що дiє мiж просторами X та Y. Далi вважатимемо,
що X = Y — гiльбертiв простiр. Для скорочення позначимо скалярний добуток в X через (\cdot , \cdot )
i вiдповiдну йому норму через \| \cdot \| . До того ж таким самим символом \| \cdot \| позначатимемо
стандартну операторну норму.
Метою наших дослiджень є наближене знаходження розв’язку x \in X рiвняння (1), що вiд-
повiдає правiй частинi f \in X. Враховуючи можливiсть невиконання умови єдиностi (в умовах
коректностi за Адамаром), далi будемо будувати наближення до точного розв’язку (1), який має
мiнiмальну норму у просторi X. Такий розв’язок (див., наприклад, [17]) називають нормальним
розв’язком (1) i позначають символом x\dagger . Для отримання оцiнок точностi необхiдна додаткова
iнформацiя про властивостi гладкостi шуканого розв’язку. Тому зазвичай припускається, що
розв’язок x\dagger задовольняє деяку умову джерела. Загальна умова джерела має вигляд
x\dagger \in M\rho (A) :=
\bigl\{
u : u = \varphi (A\ast A)v, \| v\| \leq \rho
\bigr\}
, (2)
де A\ast — оператор, спряжений до A, а iндексна функцiя \varphi є монотонно зростаючою i такою, що
\varphi (0) = 0. При цьому \varphi може припускатися як вiдомою (апрiорний випадок), так i невiдомою
c\bigcirc Г. Л. МИЛЕЙКО, С. Г. СОЛОДКИЙ, 2017
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7 951
952 Г. Л. МИЛЕЙКО, С. Г. СОЛОДКИЙ
(апостерiорний випадок). Найбiльш дослiджуваною на сьогоднi є умова джерела гельдерiвсько-
го типу. Тут \varphi — степенева функцiя \varphi (\lambda ) = \lambda p, де p > 0 — параметр, що характеризує гладкiсть
розв’язку. У цьому випадку
x\dagger \in Mp,\rho (A) :=
\bigl\{
u : u = (A\ast A)p/2v, \| v\| \leq \rho
\bigr\}
. (3)
Задачi (1), розв’язки яких задовольняють умову (3), називаються помiрно некоректними i є
традицiйним об’єктом дослiдження в теорiї некоректних задач (див., наприклад, [5]).
Iнший, не менш поширений, тип гладкостi розв’язкiв характеризується умовою джерела
логарифмiчного типу. У цьому випадку маємо
x\dagger \in MK
p,\rho (A) :=
\bigl\{
u : u = (\mathrm{l}\mathrm{n} . . . \mathrm{l}\mathrm{n}\underbrace{} \underbrace{}
K разiв
(A\ast A) - 1) - pv, \| v\| \leq \rho
\bigr\}
. (4)
Задачi (1) з розв’язками (4) називаються жорстко некоректними (див., наприклад, [18, 25]).
Зауважимо, що умова джерела гельдерiвського вигляду (3) зберiгає тип гладкостi розв’язку
порiвняно з множиною \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(A): наприклад, якщо оператор дiє у простiр функцiй скiнченної
гладкостi, то й розв’язок x\dagger матиме скiнченну гладкiсть. Така ж ситуацiя має мiсце i для помiр-
но некоректних задач у разi просторiв нескiнченно диференцiйовних функцiй. На вiдмiну вiд
описаної ситуацiї для жорстко некоректних задач спостерiгається суттєве погiршення гладкостi
розв’язку x\dagger вигляду (4) щодо гладкостi оператора A. Тут характерними є такi випадки: опе-
раторам нескiнченної гладкостi вiдповiдають розв’язки iз класiв функцiй соболєвського типу, а
операторам скiнченної гладкостi — розв’язки, швидкiсть спадання коефiцiєнтiв Фур’є яких буде
бiльш повiльною, нiж у функцiй соболєвського типу гладкостi. Вiдомо (див., наприклад, [19]),
що на класi задач (1) з розв’язками вигляду (2) оптимальний порядок точностi розв’язування є
O
\bigl(
\varphi (\theta - 1)(\delta /\rho )
\bigr)
, де \theta (t) =
\surd
t\varphi (t), t > 0. Це означає, зокрема, що для помiрно некоректних
задач iз розв’язками (3) оптимальний порядок точностi складає O
\bigl(
\delta p/(p+1)
\bigr)
(див. [3, c. 14]),
а у випадку жорстко некоректних задач iз розв’язками (4) — O
\left( \left( \mathrm{l}\mathrm{n} . . . \mathrm{l}\mathrm{n}\underbrace{} \underbrace{}
K разiв
1
\delta
\right) - p\right) (див. [32]).
Таким чином, хоча для помiрно некоректних задач i спостерiгається втрата точностi вiднов-
лення розв’язкiв (порiвняно з рiвнем збурення), проте обидвi цi величини належать до однiєї
шкали
\bigl(
O(\delta p/(p+1)) i \delta вiдповiдно
\bigr)
. З iншого боку, для жорстко некоректних задач ситуацiя
принципово iнша — рiвень точностi наближення розв’язкiв визначається логарифмом вiд рiвня
збурення вхiдних даних.
Приклад 1. Обернена задача теплопровiдностi. Розглянемо рiвняння теплопровiдностi
\partial u
\partial t
(x, t) =
\partial 2u
\partial x2
(x, t), x \in [0, \pi ], t \geq 0, (5)
з однорiдними граничними умовами Дiрiхле u(0, t) = u(\pi , t) = 0, t \geq 0, та припустимо,
що задано кiнцеву температуру f(x) := u(x, 1), x \in [0, \pi ], де f(0) = f(\pi ) = 0. Необхiдно
визначити початкову температуру v(x) := u(x, 0), x \in [0, \pi ].
Вiдомо (див., наприклад, [17]), що обернена задача еквiвалентна розв’язуванню iнтеграль-
ного рiвняння першого роду
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
ГIПЕРБОЛIЧНИЙ ХРЕСТ I СКЛАДНIСТЬ РIЗНИХ КЛАСIВ ЛIНIЙНИХ НЕКОРЕКТНИХ ЗАДАЧ 953
Kv(x) :=
\pi \int
0
k(x, \tau ) v(\tau )d\tau = f(x), (6)
де
k(x, \tau ) :=
2
\pi
\infty \sum
n=1
e - n2
\mathrm{s}\mathrm{i}\mathrm{n}(n\tau ) \mathrm{s}\mathrm{i}\mathrm{n}(nx).
Зазначимо, що сингулярна система для iнтегрального оператора в (6) задається у виглядi\Biggl(
e - n2
;
\sqrt{}
2
\pi
\mathrm{s}\mathrm{i}\mathrm{n}(nx),
\sqrt{}
2
\pi
\mathrm{s}\mathrm{i}\mathrm{n}(nx)
\Biggr)
. (7)
Вiдомо (див. [17]), що розв’язок рiвняння (6) визначається формулою
v(x) =
\sqrt{}
2
\pi
\infty \sum
n=1
en
2
fn \mathrm{s}\mathrm{i}\mathrm{n}(nx), (8)
де fn — коефiцiєнти Фур’є правої частини (6) за тригонометричним базисом. Нехай тепер fn
такi, що | fn| \asymp e - 2n2
, тодi v0(x):
| vn| =
\sqrt{}
2
\pi
en
2 | fn| \asymp
\sqrt{}
2
\pi
e - n2
,
де vn, n = 1, 2, . . . , визначають коефiцiєнти Фур’є функцiї v(x). Тодi гладкiсть розв’язку
вимiрюється у такiй самiй шкалi (див. спiввiдношення вище), що й гладкiсть оператора (див.
сингулярну систему (7)), а це означає, що задача (6) є помiрно некоректною при p = 1.
Зазначимо, що якщо fn такi, що | fn| \asymp e - n2 1
n
, то для коефiцiєнтiв Фур’є розв’язку справ-
джується оцiнка
| vn| =
\sqrt{}
2
\pi
en
2 | fn| \asymp
\sqrt{}
2
\pi
1
n
.
Порiвнюючи (7) iз наведеним вище спiввiдношенням, робимо висновок, що у такому випадку
задача (6) є жорстко некоректною з розв’язками вигляду (4) при K = 1 й p =
1
2
.
Нехай далi X — сепарабельний гiльбертiв простiр, а E = \{ e1, e2, . . . , en, . . .\} — деякий
ортонормований базис в X. Розглянемо такi класи лiнiйних неперервних операторiв:
\scrH r,s
\gamma ,E(D) = \scrH r,s
\gamma (D) :=
\Biggl\{
A : A \in \scrL (X,X), \| A\| \leq \gamma 0,
\infty \sum
n+m=1
(Aem, en)
2n2rm2s \leq \gamma 21
\Biggr\}
,
\scrH r,s
\gamma ,E(S) = \scrH r,s
\gamma (S) :=
\Biggl\{
A : A \in \scrL (X,X), \| A\| \leq \gamma 0,
\infty \sum
n+m=1
(Aem, en)
2(n2r +m2s) \leq \gamma 21
\Biggr\}
,
де r, s > 0, \gamma = (\gamma 0, \gamma 1), n,m \in \BbbZ +, n = 1 при n = 0 i n = n у протилежному випадку.
Вiдомо (див., наприклад, [9]), що змiстовним прикладом операторiв iз класу \scrH r,s
\gamma (S) є
iнтегральнi оператори Фредгольма
Af(t) =
1\int
0
a(t, \tau )f(\tau ) d\tau , t \in [0, 1], (9)
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
954 Г. Л. МИЛЕЙКО, С. Г. СОЛОДКИЙ
з ядрами a(t, \tau ), що належать до соболєвського класу функцiй W r,s
2 . Якщо a(t, \tau ) \in W r,s
2 має,
крiм того, обмежену похiдну
\partial r+sa(t, \tau )
\partial tr\partial \tau s
, то такий оператор (9) належить до класу \scrH r,s
\gamma (D).
Класи рiвнянь (1) з операторами A \in \scrH r,s
\gamma i розв’язками x\dagger \in Mp позначатимемо (\scrH r,s
\gamma ,Mp),
де пiд \scrH r,s
\gamma далi розумiтимемо клас \scrH r,s
\gamma (S) або \scrH r,s
\gamma (D), а пiд Mp — Mp,\rho (A) (3) або M1
p,\rho (A)
(4), де K = 1. Звiсно, що для жорстко некоректних задач цiлком природною буде умова
\gamma 0 \leq e - 1/2.
Наведемо тепер строгу постановку задачi, що дослiджується. Оскiльки \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(A) не припус-
кається замкненим
\bigl(
тобто вважається, що \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(A) \not = \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(A)
\bigr)
, то задача (1) не є коректною
у сенсi Адамара, а отже, для побудови стiйкого наближеного розв’язку (1) необхiдна регуляри-
зацiя.
Далi зосередимося на дослiдженнi проекцiйних методiв розв’язування помiрно та жорстко
некоректних задач iз визначених вище класiв (\scrH r,s
\gamma ,Mp) при r \geq s.
Вiзьмемо довiльну обмежену область \Omega \subset [1;\infty ) \times [1;\infty ) координатної площини. Через
\omega 1, \omega 2 позначимо проекцiї цiєї областi на осi Oi та Oj : \omega 1 :=
\bigl\{
i : (i; j) \in \Omega
\bigr\}
, \omega 2 :=
\bigl\{
j :
(i; j) \in \Omega
\bigr\}
. За допомогою \Omega виконаємо перехiд до дискретизованого рiвняння A\Omega x = P\omega 1f\delta ,
де
A\Omega x =
\sum
(i,j)\in \Omega
(Aej , ei)(x, ej)ei, P\omega 1f\delta =
\sum
k\in \omega 1
(f\delta , ek)ek. (10)
Набiр скалярних добуткiв вигляду
(Aej , ei), (f\delta , ek), (i; j) \in \Omega , k \in \omega 1, (11)
що використовуються при побудовi (10), називають гальоркiнською iнформацiєю про (1), а пiд
\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(\Omega ) розумiється загальна кiлькiсть скалярних добуткiв вигляду (Aej , ei) з (11). Зокрема,
якщо \Omega = [1;n] \times [1;m], \omega 1 = [1, n], то ми одержуємо стандартну гальоркiнську схему дис-
кретизацiї з \mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(\Omega ) = n \cdot m. Дослiдження рiзних класiв некоректних задач за допомогою саме
такої схеми були проведенi у низцi робiт, серед яких видiлимо [19, 20].
Наведемо класичне означення регуляризатора (див. [15]).
Означення 1. Сiм’я обмежених операторiв R\alpha : X \rightarrow X називається методом регуляри-
зацiї (регуляризатором) задачi (1), якщо для кожного f \in Range(A) виконується
\mathrm{s}\mathrm{u}\mathrm{p}
f\delta : \| f - f\delta \| \leq \delta
\mathrm{i}\mathrm{n}\mathrm{f}
x\in A - 1f
\| R\alpha f\delta - x\| \rightarrow 0
при \alpha \rightarrow 0, де \alpha = \alpha (\delta ) \rightarrow 0 при \delta \rightarrow 0. Тут A - 1f — повний прообраз елемента f.
Таким чином, згiдно з означенням 1 регуляризатори забезпечують збiжнiсть наближень
до точного розв’язку при \delta \rightarrow 0. На сучасному етапi розвитку чисельного аналiзу при по-
будовi стiйких методiв увага насамперед придiляється таким регуляризаторам, що додатково
забезпечують оптимальний порядок точностi. Саме такi методи регуляризацiї прийнято нази-
вати регуляризаторами за Бакушинським. Отже, наслiдуючи А. Б. Бакушинського [2], будемо
розглядати оператори регуляризацiї, якi можна подати у виглядi
R\alpha := g\alpha (A
\ast A)A\ast
за допомогою твiрної функцiї g\alpha , що задовольняє умови
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
ГIПЕРБОЛIЧНИЙ ХРЕСТ I СКЛАДНIСТЬ РIЗНИХ КЛАСIВ ЛIНIЙНИХ НЕКОРЕКТНИХ ЗАДАЧ 955
\mathrm{s}\mathrm{u}\mathrm{p}
0<\lambda \leq 1
\lambda \mu
\bigm| \bigm| 1 - \lambda g\alpha (\lambda )
\bigm| \bigm| \leq \varkappa \mu \alpha
\mu ,
\mathrm{s}\mathrm{u}\mathrm{p}
0<\lambda \leq 1
\lambda 1/2
\bigm| \bigm| g\alpha (\lambda )\bigm| \bigm| \leq \varkappa \ast \alpha
- 1/2
(12)
при деяких додатних сталих \varkappa \mu ,\varkappa \ast та параметрi 0 \leq \mu \leq \mu \ast . При цьому \mu \ast називають квалi-
фiкацiєю методу R\alpha . Ця величина визначає максимальну „гладкiсть” розв’язку, при якiй метод
R\alpha досягає оптимального порядку точностi. Зауважимо (див., наприклад, [3]), що бiльшiсть
вiдомих регуляризаторiв (у тому числi стандартний метод Тихонова та його узагальнений й
iтерований варiанти) вiдповiдають умовам (12).
Означення 2. Пiд проекцiйним методом розв’язування рiвняння (1) будемо розумiти будь-
яке вiдображення \scrP = \scrP (\Omega ) : X \rightarrow X, яке за допомогою гальоркiнської iнформацiї (11) про
рiвняння (1) зiставляє правiй частинi розв’язуваного рiвняння елемент \scrP (A\Omega )f\delta \in X, що є
многочленом за базисом \{ ei\} \infty i=1 з номерами гармонiк iз \omega 2. Цей елемент приймається за
наближений розв’язок рiвняння (1).
Зазначимо, що вiд методу \scrP не вимагається анi лiнiйностi, анi неперервностi. Таке загальне
розумiння методу корисне, зокрема, при порiвняннi апроксимацiйних властивостей якомога
бiльш широкого кола можливих способiв розв’язування рiвняння (1).
Пiд похибкою методу \scrP (\Omega ) на класi рiвнянь (\scrH r,s
\gamma ,Mp), зазвичай, будемо розумiти його
найбiльше вiдхилення
\varepsilon \delta
\bigl(
\scrH r,s
\gamma ,Mp,\scrP (\Omega )
\bigr)
= \mathrm{s}\mathrm{u}\mathrm{p}
A\in \scrH r,s
\gamma
\mathrm{s}\mathrm{u}\mathrm{p}
x\dagger \in Mp
\mathrm{s}\mathrm{u}\mathrm{p}
f\delta : \| f - f\delta \| \leq \delta
\bigm\| \bigm\| x\dagger - \scrP (A\Omega )f\delta
\bigm\| \bigm\| .
Мiнiмальний радiус гальоркiнської iнформацiї задамо величиною
RN,\delta
\bigl(
\scrH r,s
\gamma ,Mp
\bigr)
= \mathrm{i}\mathrm{n}\mathrm{f}
\Omega : card(\Omega )\leq N
\mathrm{i}\mathrm{n}\mathrm{f}
\scrP (\Omega )
\varepsilon \delta
\bigl(
\scrH r,s
\gamma ,Mp,\scrP (\Omega )
\bigr)
.
Ця величина визначає найменшу можливу точнiсть серед усiх проекцiйних методiв при обме-
женнi на обсяг гальоркiнської iнформацiї. Таким чином, RN,\delta характеризує iнформацiйну склад-
нiсть класу задач (\scrH r,s
\gamma ,Mp).
Позначимо через \Pi M множину всiх можливих проекцiйних методiв, якi для побудови на-
ближеного розв’язку потребують виконання не бiльш нiж M елементарних арифметичних
операцiй. Мiнiмальний радiус обсягу обчислювальних витрат задамо величиною
RM,\delta
\bigl(
\scrH r,s
\gamma ,Mp
\bigr)
= \mathrm{i}\mathrm{n}\mathrm{f}
\Omega : card(\Omega )\leq M
\mathrm{i}\mathrm{n}\mathrm{f}
\scrP (\Omega )\in \Pi M
\varepsilon \delta
\bigl(
\scrH r,s
\gamma ,Mp,\scrP (\Omega )
\bigr)
.
Ця величина визначає найменшу можливу точнiсть проекцiйних методiв при обмеженнi на
обсяг обчислювальних витрат. Таким чином, RM,\delta характеризує алгоритмiчну складнiсть класу
задач (\scrH r,s
\gamma ,Mp) у сенсi кiлькостi задiяних елементарних арифметичних дiй.
Зрозумiло, що запропонованi нижче пiдходи будуть регуляризуючими, завдяки чому стає
можливим досягнення найменших значень RN,\delta , RM,\delta . З iншого боку, iнфiмум у цих величинах
береться по всiх можливих проекцiйних методах (не обов’язково стiйких) для забезпечення
максимальної широти пiдходiв, що порiвнюються.
Щодо iсторiї дослiдження складностi некоректних задач зауважимо, що вперше економiчнi
проекцiйнi методи розв’язування помiрно некоректних задач були побудованi в роботi [20], де
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
956 Г. Л. МИЛЕЙКО, С. Г. СОЛОДКИЙ
в якостi схеми дискретизацiї використовувалася стандартна схема Гальоркiна. Пiзнiше в роботi
[23] були отриманi першi порядковi оцiнки мiнiмального радiуса гальоркiнської iнформацiї
для помiрно некоректних задач iз розв’язками (3) при фiксованому p = 2 й операторами з
класiв \scrH r,r
\gamma . Далi дослiдження, iнiцiйованi у [23], були продовженi в низцi робiт, серед яких
i роботи [14, 26]. При цьому, як виявилося, оптимальнi порядки величин, що характеризують
iнформацiйну та алгоритмiчну складнiсть рiвнянь (1), реалiзуються не в рамках стандартної
схеми Гальоркiна, а деякої її модифiкацiї, що ґрунтується на iдеї гiперболiчного хреста (док-
ладнiше про це див. пiдпункт 2.1). Зауважимо, що складнiсть некоректних задач довгий час
вивчалася лише у випадку рiвнянь (1) iз розв’язками вигляду (3). Щодо iнших типiв некоректних
задач (зокрема, жорстко некоректних), то першi кроки у цьому напрямку були зробленi у [19],
де розглядалося питання економiчної дискретизацiї в межах стандартної схеми Гальоркiна для
задач (1) з розв’язками, що задовольняють загальну умову джерела (2). Проте оцiнки складностi
в роботi [19] не було знайдено. Вiдправною точкою дослiдження складностi жорстко некорект-
них задач можна вважати статтю [29], результати якої знайшли свiй подальший розвиток у
роботах [27, 30]. Основнi досягнення вказаного напрямку викладено у пiдпунктах 2.3, 2.4.
2. Економiчна модифiкацiя гальоркiнської схеми. Оцiнки складностi. Оскiльки на прак-
тицi при побудовi чисельного розв’язку припустиме використання лише скiнченного обсягу
дискретної iнформацiї про задачу, то замiсть вихiдного рiвняння доводиться розглядати його
скiнченновимiрний аналог. Такий етап побудови наближеного розв’язку в чисельному аналiзi
прийнято називати дискретизацiєю. У зв’язку з цим виникає актуальна проблема мiнiмiзацiї
обсягу задiяної дискретної iнформацiї та зменшення кiлькостi виконуваних у процесi розв’язу-
вання арифметичних дiй без втрати точностi.
Для економiчної дискретизацiї рiвнянь з
\bigl(
\scrH r,s
\gamma M\rho (A)
\bigr)
замiсть стандартної схеми Гальоркi-
на PnAPm застосуємо її модифiкацiю, що називається гiперболiчним хрестом. Слiд зазначити,
що вперше гiперболiчний хрест був запроваджений К. I. Бабенко [1] при обчисленнi колмо-
горовських поперечникiв для деяких класiв перiодичних функцiй, що мають домiнуючу мiша-
ну частинну похiдну. Iдея застосування гiперболiчного хреста при розв’язуваннi операторних
рiвнянь другого роду належить С. В. Переверзєву й реалiзована ним у низцi робiт (див., на-
приклад, [8, 10, 11, 22]). Ефективнiсть використання гiперболiчного хреста при розв’язуваннi
некоректних задач продемонстрована у роботах [21, 23, 27, 31].
Отже, наближений розв’язок шукатимемо у виглядi
xn\alpha ,\delta = g\alpha (A
\ast
\Omega A\Omega )A
\ast
\Omega P\Omega f\delta , (13)
де g\alpha задовольняє умови (12), а \Omega — гiперболiчний хрест (конкретнi приклади див. нижче).
2.1. Помiрно некоректнi задачi (апрiорний випадок). За область \Omega у випадку помiрно
некоректних задач вiзьмемо такi хрести:
для рiвнянь з класу
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
, 1 < p \leq 2:
\Omega 1 = \{ 1\} \times
\Bigl[
1; 2
pr
s
n
\Bigr] n\bigcup
k=1
\Bigl(
2k - 1; 2k
\Bigr]
\times
\Bigl[
1; 2
pr
s
(n - k/2)
\Bigr]
\subset [1; 2n]\times
\Bigl[
1; 2
pr
s
n
\Bigr]
, (14)
де 2 - (p+1)rn \asymp \delta ;
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
ГIПЕРБОЛIЧНИЙ ХРЕСТ I СКЛАДНIСТЬ РIЗНИХ КЛАСIВ ЛIНIЙНИХ НЕКОРЕКТНИХ ЗАДАЧ 957
для рiвнянь з
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
, 2 \leq p \leq 2\mu \ast :
\Omega 2 = \{ 1\} \times
\Bigl[
1; 2
2rn
s
\Bigr] n\bigcup
k=1
\Bigl(
2k - 1; 2k
\Bigr]
\times
\biggl[
1; 2
2rn
s
- (3p - 2)rk
2ps
\biggr]
\subset [1; 2n]\times
\Bigl[
1; 2
2rn
s
\Bigr]
, (15)
де 2 - (p+1)rn/p \asymp \delta ;
для рiвнянь з
\bigl(
\scrH r,s
\gamma (S),Mp,\rho (A)
\bigr)
, 2 \leq p \leq 2\mu \ast :
\Omega 3 = \{ 1\} \times
\Bigl[
1; 2
2rn
s
\Bigr] n\bigcup
k=1
\Bigl(
2k - 1; 2k
\Bigr]
\times
\biggl[
1; 2
2rn
s
- (p - 1)rk
ps
\biggr]
\subset [1; 2n]\times
\Bigl[
1; 2
2rn
s
\Bigr]
, (16)
де 2 - 2(p - 1)rn/p \asymp \delta .
Тодi областям (14) – (16) вiдповiдатимуть такi дискретизованi оператори:
A\Omega 1 := P1AP2
pr
s n +
n\sum
k=1
(P2k - P2k - 1)AP
2
pr
s (n - k/2) ,
A\Omega 2 := P1AP
2
2rn
s
+
n\sum
k=1
(P2k - P2k - 1)AP
2
2rn
s - (3p - 2)rk
2ps
,
A\Omega 3 := P1AP
2
2rn
s
+
n\sum
k=1
(P2k - P2k - 1)AP
2
2rn
s - (p - 1)rk
ps
.
Як вiдомо, для помiрно некоректних задач параметр регуляризацiї \alpha слiд вибирати (апрiорно)
згiдно з правилом
\alpha \asymp \delta 2/(p+1). (17)
Проекцiйнi методи (12), (13), (17) зi схемами дискретизацiї (14), (15), (16) позначимо че-
рез \scrP 1, \scrP 2, \scrP 3 вiдповiдно.
Далi пiд ci будемо розумiти рiзнi додатнi сталi, що, взагалi кажучи, не залежать вiд \delta та N.
Теорема 1. A. 1. Якщо 1 < p \leq 2 i r/s > 2/p, то для N \asymp \delta
- p
(p+1)s справджується
RN,\delta
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
\asymp N - s \asymp \delta
p
p+1 .
Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
реалiзується у межах проекцiйного мето-
ду \scrP 1.
2. Якщо p \geq 2 i r/s >
2p
3p - 2
, то для N \asymp \delta
- p
(p+1)s справджується
RN,\delta
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
\asymp N - s \asymp \delta
p
p+1 .
Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
реалiзується у межах проекцiйного методу \scrP 2.
Б. 1. Якщо 1 < p \leq 2 i r/s = 2/p, то для N \asymp \delta
- p
(p+1)s \mathrm{l}\mathrm{n} 1/\delta справджується
c1N
- s \leq RN,\delta
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
\leq c2N
- s \mathrm{l}\mathrm{n}sN.
Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
реалiзується у межах проекцiйного методу \scrP 1.
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
958 Г. Л. МИЛЕЙКО, С. Г. СОЛОДКИЙ
2. Якщо p \geq 2 i r/s =
2p
3p - 2
, то для N \asymp \delta
- p
(p+1)s \mathrm{l}\mathrm{n} 1/\delta справджується
c3N
- s \leq RN,\delta
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
\leq c4N
- s \mathrm{l}\mathrm{n}sN.
Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
реалiзується у межах проекцiйного методу \scrP 2.
Теорема 2. Нехай p \geq 2. Тодi для r/s >
p
p - 1
справджується
RN,\delta
\bigl(
\scrH r,s
\gamma (S),Mp,\rho (A)
\bigr)
\asymp N - s \asymp \delta
p
p+1
при N \asymp \delta
- p
(p+1)s , а для r/s =
p
p - 1
виконується
c5N
- s \leq RN,\delta
\bigl(
\scrH r,s
\gamma (S),Mp,\rho (A)
\bigr)
\leq c6N
- s \mathrm{l}\mathrm{n}sN
при N \asymp \delta
- p
(p+1)s \mathrm{l}\mathrm{n} 1/\delta . Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (S),Mp,\rho (A)
\bigr)
реалiзується у межах
проекцiйного методу \scrP 3.
Теорема 3. A. 1. Якщо параметри p, r i s такi, що точка (p, r/s) належить множинi
(1, 2]\times (4/p,\infty ), то для N \asymp \delta
- p
(p+1)s справджується
RN,\delta
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
\asymp N - s \asymp \delta
p
p+1 .
Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
реалiзується у межах проекцiйного мето-
ду \scrP 1, де як регуляризатор використано узагальнений метод Тихонова з g\alpha (\lambda ) = \lambda q(\alpha q+1 +
+ \lambda q+1) - 1, q \geq - 1
2
, \mu \ast = q + 1.
2. Якщо параметри p, r i s такi, що точка (p, r/s) належить множинi
[2, 6]\times
\biggl(
2p
3p - 4
,\infty
\biggr) \bigcup
(6,\infty )\times [3/2,\infty ),
то для N \asymp \delta
- p
(p+1)s справджується
RN,\delta
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
\asymp N - s \asymp \delta
p
p+1 .
Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
реалiзується у межах проекцiйного мето-
ду \scrP 2, де як регуляризатор використано узагальнений метод Тихонова.
Б. 1. Якщо 1 < p \leq 2, r/s = 4/p, то для N \asymp \delta
- p
(p+1)s \mathrm{l}\mathrm{n} 1/\delta справджується
c7N
- s \leq RN,\delta
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
\leq c8N
- s \mathrm{l}\mathrm{n}sN.
Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
реалiзується у межах проекцiйного мето-
ду \scrP 1, де як регуляризатор використано узагальнений метод Тихонова.
2. Якщо 2 \leq p \leq 6, r/s =
2p
3p - 4
, то для N \asymp \delta
- p
(p+1)s \mathrm{l}\mathrm{n} 1/\delta справджується
c9N
- s \leq RN,\delta
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
\leq c10N
- s \mathrm{l}\mathrm{n}sN.
Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (D),Mp,\rho (A)
\bigr)
реалiзується у межах проекцiйного мето-
ду \scrP 2, де як регуляризатор використано узагальнений метод Тихонова.
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
ГIПЕРБОЛIЧНИЙ ХРЕСТ I СКЛАДНIСТЬ РIЗНИХ КЛАСIВ ЛIНIЙНИХ НЕКОРЕКТНИХ ЗАДАЧ 959
Теорема 4. Нехай p \geq 2. Тодi для r/s >
2p
p - 1
справджується
RN,\delta
\bigl(
\scrH r,s
\gamma (S),Mp,\rho (A)
\bigr)
\asymp N - s \asymp \delta
p
p+1
при N \asymp \delta
- p
(p+1)s , а для r/s =
2p
p - 1
виконується
c11N
- s \leq RN,\delta
\bigl(
\scrH r,s
\gamma (S),Mp,\rho (A)
\bigr)
\leq c12N
- s \mathrm{l}\mathrm{n}sN
при N \asymp \delta
- p
(p+1)s \mathrm{l}\mathrm{n} 1/\delta . Зазначений порядок на класi
\bigl(
\scrH r,s
\gamma (S),Mp,\rho (A)
\bigr)
реалiзується у межах
проекцiйного методу \scrP 3, де як регуляризатор використано узагальнений метод Тихонова.
Доведення теорем 1 – 4 опублiковано у [12, 13].
2.2. Помiрно некоректнi задачi (апостерiорний випадок). Недолiком апрiорного вибору \alpha
є його обов’язкове „налаштування” на певне значення p. При цьому оптимальний порядок точ-
ностi O(\delta p/(p+1)) або O
\left( \left( \mathrm{l}\mathrm{n} . . . \mathrm{l}\mathrm{n}\underbrace{} \underbrace{}
K разiв
1
\delta
\right) - p\right) забезпечується лише для задач (1) з нормальним
розв’язком x\dagger \in Mp,\rho (A) або x\dagger \in MK
p,\rho (A) вiдповiдно, де величина p є фiксованою. Очевид-
но, що такий пiдхiд до розв’язування некоректних задач можливий, якщо нам точно вiдомо
значення параметра p. Але оскiльки така iнформацiя, зазвичай, або вiдсутня, або не є точною, то
на практицi необхiднi апостерiорнi правила вибору параметра регуляризацiї, реалiзацiя яких не
потребує додаткових знань про гладкiсть розв’язку. Одним iз найбiльш розповсюджених таких
правил є принцип нев’язки Морозова, який уперше було застосовано для помiрно некоректних
задач у [4, 6, 7]. Для жорстко некоректних задач цей принцип розглядався, зокрема, у роботi [25].
Замiсть множини Mp,\rho (A) введемо у розгляд множину
M(A) =
\bigcup
0<p\leq 2\mu \ast
Mp,\rho (A). (18)
У цьому пiдпунктi для економiчного розв’язування рiвнянь iз класiв
\bigl(
\scrH r,s
\gamma (D),M(A)
\bigr)
та\bigl(
\scrH r,s
\gamma (S),M(A)
\bigr)
буде запропоновано пiдхiд, що полягає у комбiнуваннi iтерованого методу
Тихонова з правилом зупинки згiдно з принципом нев’язки Морозова.
Для дискретизацiї застосовується хрест вигляду
\Omega 4 = \{ 1\} \times
\bigl[
1; 22an
\bigr] 2n\bigcup
k=1
(2k - 1; 2k]\times
\bigl[
1; 2(2n - k)a
\bigr]
\subset
\bigl[
1; 22n
\bigr]
\times
\bigl[
1; 22an
\bigr]
, (19)
де a — довiльне число таке, що 1 < a <
r
s
, r > s i a = 1, r = s. Тодi
A\Omega 4 = P1AP22an +
n\sum
k=1
(P2k - P2k - 1)AP2(2n - k)a .
Проекцiйний метод (12), (13), (19) з вибором параметра регуляризацiї згiдно з принципом
нев’язки Морозова позначимо через \scrP 4.
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
960 Г. Л. МИЛЕЙКО, С. Г. СОЛОДКИЙ
Теорема 5. Для достатньо малих \delta виконується
c1N
- pr
p+1 \leq RN,\delta
\bigl(
\scrH r,r
\gamma (D),M(A)
\bigr)
\leq c2N
- pr
p+1 \mathrm{l}\mathrm{n}
p(1+2r)
2(p+1) N, r = s, (20)
RN,\delta
\bigl(
\scrH r,s
\gamma (D),M(A)
\bigr)
\asymp N
- ps
p+1 , r > s, (21)
де сталi c1, c2 > 0 не залежать вiд \delta та N. Оптимальнi за порядком оцiнки iнформацiй-
ної складностi реалiзуються у рамках алгоритму \scrP 4, де як регуляризатор використовується
iтерований метод Тихонова з gm,\alpha (\lambda ) =
1
\lambda
\bigl(
1 - (1 + \alpha - 1\lambda ) - m
\bigr)
, \lambda \not = 0,m \geq 1, \mu \ast = m.
Доведення цiєї теореми наведено у [12, 13].
2.3. Жорстко некоректнi задачi (апрiорний випадок). Для економiчної дискретизацiї рiв-
нянь iз класу (\scrH r,s
\gamma (D),M1
p (A)), 0 < p < \infty , застосуємо проекцiйну схему з
\Omega 5 = \{ 1\} \times
\bigl[
1; 2bn
\bigr] n\bigcup
k=1
(2k - 1; 2k]\times
\bigl[
1; 2bn - rk/s
\bigr]
\subset [1; 2n]\times
\bigl[
1; 2bn
\bigr]
, (22)
де
r
s
< b \leq 2r
s
, n \in \BbbN та
A\Omega 5 = P1AP2bn +
n\sum
k=1
(P2k - P2k - 1)AP
2bn - r
s k . (23)
Проекцiйний метод (12), (13), (23) з апрiорним правилом вибору параметра регуляризацiї \alpha
\mathrm{l}\mathrm{n} - p \alpha - 1 = \delta /
\surd
\alpha (24)
позначимо через \scrP 5.
Теорема 6. При N, що задовольняють умову
N - s \mathrm{l}\mathrm{n} - pN2s \asymp
\left\{
\delta
\mathrm{l}\mathrm{n}s+1 \delta - 1
, r = s,
\delta
\mathrm{l}\mathrm{n} \delta - 1
, r > s,
справджується
RN,\delta
\bigl(
\scrH r,s
\gamma ,M1
p (A)
\bigr)
\asymp \mathrm{l}\mathrm{n} - pN2s \asymp \mathrm{l}\mathrm{n} - p \delta - 1.
Зазначений оптимальний порядок на класi
\bigl(
\scrH r,s
\gamma (D),M1
p (A)
\bigr)
, 0 < p < \infty , r \geq s, реалiзується
в рамках проекцiйного методу \scrP 5.
Теорема 7. При r \geq 2s мають мiсце спiввiдношення
RN,\delta
\bigl(
\scrH r,s
\gamma (D),M1
p (A)
\bigr)
\asymp \mathrm{l}\mathrm{n} - p \delta - 1 \asymp \mathrm{l}\mathrm{n} - pN2s, (25)
де N — обсяг обчислювальних витрат. При цьому
N =
\left\{
O
\Bigl(
\delta -
1
s (\mathrm{l}\mathrm{n} \delta - 1)
1 - p+s
s
\Bigr)
, r = 2s,
O
\Bigl(
\delta -
1
s (\mathrm{l}\mathrm{n} \delta - 1)
1 - p
s
\Bigr)
, r > 2s.
(26)
Зазначений оптимальний порядок реалiзується в рамках проекцiйного методу \scrP 5, де за регу-
ляризатор вибрано стандартний метод Тихонова.
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
ГIПЕРБОЛIЧНИЙ ХРЕСТ I СКЛАДНIСТЬ РIЗНИХ КЛАСIВ ЛIНIЙНИХ НЕКОРЕКТНИХ ЗАДАЧ 961
Доведення теорем 6 та 7 опублiковано в роботах [27, 29].
Зауваження 1. З оцiнки (26) випливає, що збiльшення гладкостi оператора A за зовнiш-
ньою змiнною r (вiд r = 2s до r > 2s) приводить до зменшення на логарифмiчний множник
в оцiнцi обсягу обчислювальних витрат, що необхiднi для досягнення оптимального порядку
точностi.
Зауваження 2. З результатiв роботи [19] випливає, що для стандартної схеми Гальоркiна
обсяг обчислювальних витрат на тих самих класах рiвнянь складає O(\delta - 1/s\delta - 2\varepsilon /r \mathrm{l}\mathrm{n} - p/s \delta - 1).
Порiвнюючи цей результат з теоремою 7, можна дiйти висновку, що запропонований проекцiй-
ний метод \scrP 5 дозволяє не лише скоротити обсяг обчислень вiдносно стандартної гальоркiнської
схеми, а й реалiзувати порядковi оцiнки величини RN,\delta на класах рiвнянь
\bigl(
\scrH r,s
\gamma (D),M1
p (A)
\bigr)
,
r \geq 2s.
Зауваження 3. Для досягнення оптимального порядку точностi при розв’язуваннi жорстко
некоректних задач достатньо скористатися регуляризатором малої квалiфiкацiї (\mu \ast = 1). Ця
ситуацiя принципово вiдрiзняється вiд випадку помiрно некоректних задач, де збiльшення
параметра p призводить до використання регуляризатора великої квалiфiкацiї.
2.4. Жорстко некоректнi задачi (апостерiорний випадок). Нехай параметр p в (4) є
невiдомим. Шукатимемо розв’язок з множини
M1(A) :=
\bigcup
p\in (0,p1]
M1
p (A). (27)
Тут p1 < \infty — верхня межа можливих значень p.
Для економiчного розв’язування рiвнянь iз класу
\bigl(
\scrH r,r
\gamma (D),M1(A)
\bigr)
буде запропоновано два
пiдходи, що полягають у комбiнуваннi стандартного методу Тихонова з принципом нев’язки
Морозова, а також з принципом рiвноваги вiдповiдно.
В межах наших дослiджень скористаємося проекцiйною схемою з хрестом вигляду
\Omega 6 = \{ 1\} \times [1; 22n]
2n\bigcup
k=1
(2k - 1; 2k]\times [1; 22n - k] \subset [1; 22n]\times [1; 22n]. (28)
Нагадаємо, що принцип рiвноваги полягає у виборi значення параметра регуляризацiї таким
чином, щоб врiвноважити двi функцiї (\Psi 1, \Psi 2), що складають оцiнку похибки: \| x\dagger - xdisc\| \leq
\leq \Psi 1(\alpha ) + \Psi 2(\alpha ), де \Psi 1(\alpha ) = \varphi (\alpha ) = \mathrm{l}\mathrm{n} - p \alpha є монотонно зростаючою по \alpha , а \Psi 2(\alpha ) =
=
17
10
\delta \surd
\alpha
— монотонно спадною. Враховуючи поведiнку функцiй \Psi 1, \Psi 2 (а саме, їх монотон-
нiсть та ввiгнутiсть), вибiр такого \~\alpha , що теоретично мiнiмiзує праву частину оцiнки похибки,
буде врiвноважувати функцiї \Psi 1 та \Psi 2. А оскiльки функцiя \varphi , яка характеризує гладкiсть шука-
ного розв’язку, є невiдомою, то апрiорний вибiр \~\alpha неможливий. Замiсть теоретично найкращого
\~\alpha за параметр регуляризацiї, згiдно з принципом рiвноваги, беремо елемент
\alpha + = \mathrm{m}\mathrm{a}\mathrm{x}
\bigl\{
\alpha : \alpha \in D+
n
\bigr\}
,
що є досить близьким до \~\alpha . Тут
D+
n =
\Bigl\{
i :
\bigm\| \bigm\| x\delta \alpha i,n - x\delta \alpha j ,n
\bigm\| \bigm\| \leq 4\Psi 2(\alpha j) \forall i > j, i = 1, . . . ,M
\Bigr\}
, (29)
а множина можливих значень для параметра \alpha визначається таким чином:
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
962 Г. Л. МИЛЕЙКО, С. Г. СОЛОДКИЙ
DM =
\bigl\{
\alpha i = \alpha 0(q
2)i, i = 1, 2, . . . ,M
\bigr\}
,
де \alpha 0 =
\biggl(
17
10
\biggr) 2
\delta 2, M =
\biggl[
\mathrm{l}\mathrm{o}\mathrm{g}\alpha - 1
0
2 \mathrm{l}\mathrm{o}\mathrm{g} q
\biggr]
. Саме такий пiдхiд гарантує оптимальний порядок точнос-
тi, який, як зазначалося вище, складає O
\Biggl( \biggl(
\mathrm{l}\mathrm{n}
1
\delta
\biggr) - p
\Biggr)
.
Проекцiйнi методи (12), (13), (28) з правилами зупинки згiдно з принципом нев’язки Мо-
розова та принципом рiвноваги вiдповiдно будемо позначати через \scrP 6 та \scrP 7.
Теорема 8. Має мiсце порядкова оцiнка
RN,\delta
\bigl(
\scrH r,r
\gamma (D),M1(A)
\bigr)
\asymp \mathrm{l}\mathrm{n} - pN2r \asymp \mathrm{l}\mathrm{n} - p 1
\delta
,
де N \asymp \delta -
1
r \mathrm{l}\mathrm{n}1+
1
2r \delta - 1. Зазначений оптимальний порядок досягається у межах проекцiйних
методiв \scrP 6, \scrP 7, де як регуляризатор застосовано стандартний метод Тихонова.
Доведення теореми 8 опублiковано в роботах [28, 30].
Зауваження 4. Порiвняння результатiв для методу з [19], де як схему дискретизацiї вико-
ристано стандартну схему Гальоркiна, з теоремою 8 дозволяє дiйти висновку, що всi цi пiдходи
гарантують оптимальний порядок точностi на класi жорстко некоректних задач, тодi як задiяна
нами модифiкацiя гальоркiнської схеми дискретизацiї (28) дозволяє суттєво скоротити обсяг
дискретної iнформацiї. З iншого боку, якщо порiвнювати теорему 8 з теоремою 6, де параметр
регуляризацiї вибирався апрiорно, то у випадку апостерiорного вибору обсяг задiяної гальор-
кiнської iнформацiї є бiльшим на логарифмiчний множник. Таке збiльшення обсягу iнформацiї
можна розглядати як деяку „плату” за вiдмову вiд знання iнформацiї про гладкiсть шуканого
розв’язку.
Лiтература
1. Бабенко К. И. О приближении периодических функций многих переменных тригонометрическими многочле-
нами // Докл. АН СССР. – 1960. – 132, № 2. – С. 247 – 250.
2. Бакушинский А. Б., Кокурин М. Ю. Итеративные методы для решения некорректных операторных уравнений
с гладкими операторами. – М.: Едиториал УРСС, 2002. – 192 с.
3. Вайникко Г. М., Веретенников А. Ю. Итерационные процедуры в некорректных задачах. – М.: Наука, 1986. –
182 с.
4. Иванов В. К. О приближенном решении операторных уравнений первого рода // Журн. вычислит. математики
и мат. физики. – 1966. – 6, № 6. – С. 1089 – 1094.
5. Лаврентьев М. М. О некоторых некорректных задачах математической физики. – Новосибирск: СО АН СССР,
1962. – 92 с.
6. Морозов В. А. О выборе параметра при решении функциональных уравнений методом регуляризации // Докл.
АН СССР. – 1967. – 175, № 6. – С. 1225 – 1228.
7. Морозов В. А. О регуляризации некорректно поставленных задач и выборе параметра регуляризации // Журн.
вычислит. математики и мат. физики. – 1966. – 6, № 1. – С. 170 – 175.
8. Переверзев С. В. Гиперболический крест и сложность приближенного решения интегральных уравнений
Фредгольма II рода с дифференцируемыми ядрами // Сиб. мат. журн. – 1991. – 32, № 1. – С. 107 – 115.
9. Переверзев С. В. Оптимизация методов приближенного решения операторных уравнений. – Киев: Ин-т мате-
матики НАН Украины, 1996. – 252 с.
10. Переверзев С. В. О сложности задачи нахождения решений уравнений Фредгольма II рода с гладкими ядра-
ми. I // Укр. мат. журн. – 1988. – 40, № 1. – С. 84 – 91.
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
ГIПЕРБОЛIЧНИЙ ХРЕСТ I СКЛАДНIСТЬ РIЗНИХ КЛАСIВ ЛIНIЙНИХ НЕКОРЕКТНИХ ЗАДАЧ 963
11. Переверзев С. В. О сложности задачи нахождения решений уравнений Фредгольма II рода с гладкими ядра-
ми. II // Укр. мат. журн. – 1989. – 41, № 2. – С. 189 – 193.
12. Солодкий С. Г. Информационная сложность проекционных алгоритмов решения уравнений Фредгольма I ро-
да. I // Укр. мат. журн. – 1998. – 50, № 5. – С. 699 – 711.
13. Солодкий С. Г. Информационная сложность проекционных алгоритмов решения уравнений Фредгольма I ро-
да. II // Укр. мат. журн. – 1998. – 50, № 6. – С. 838 – 844.
14. Солодкий С. Г. Оптимизация проекционных методов решения линейных некорректных задач // Журн. вычислит.
математики и мат. физики. – 1999. – 39, № 2. – С. 195 – 203.
15. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. – М.: Наука, 1979. – 288 с.
16. Трауб Дж., Вожьняковский Х. Общая теория оптимальных алгоритмов. – М.: Мир, 1983. – 382 с.
17. Engl H. W., Hanke M., Neubauer A. Regularization of inverse problems. – Dordrecht etc.: Kluwer Acad. Publ.,
1996. – 321 p.
18. Mair B. A. Tikhonov regularization for finitely and infinitely smoothing operators // SIAM J. Math. Anal. – 1994. –
25, № 1. – P. 135 – 147.
19. Mathe P., Pereverzev S. V. Discretization strategy for ill-posed problems in variable Hilbert scales // Inverse Problems. –
2003. – 19, № 6. – P. 1263 – 1277.
20. Plato R., Vainikko G. M. On the regularization of projection methods for solving ill-posed problems // Numer. Math. –
1990. – 57. – P. 63 – 79.
21. Pereverzev S. V. Optimization of projection methods for solving ill-posed problems // Computing. – 1995. – 55. –
P. 113 – 124.
22. Pereverzev S., Scharipov C. Information complexity of equations of second kind with compact operators in Hilbert
space // J. Complexity. – 1992. – 8. – P. 176 – 202.
23. Pereverzev S. V., Solodky S. G. The minimal radius of Galerkin information for the Fredholm problems of first kind //
J. Complexity. – 1996. – 12, № 4. – P. 401 – 415.
24. Saranen J., Vainikko G. Periodic integral and pseudodifferential equations with numerical approximation. – Berlin:
Springer, 2002.
25. Schock E., Pereverzev S. V. Morozov’s discrepancy principle for Tikhonov regularization of severely ill-posed
problems in finite-dimensional subspaces // Numer. Funct. Anal. and Optim. – 2000. – 21, № 7-8. – P. 901 – 916.
26. Solodky S. G. The optimal approximations for solving linear ill-posed problems // J. Complexity. – 2001. – 17, № 1. –
P. 98 – 116.
27. Solodky S. G., Myleiko G. L. On optimization of projection methods for solving some classes of severely ill-posed
problems // J. Appl. Anal. – 2016. – 95, № 4. – P. 826 – 841.
28. Solodky S. G., Myleiko G. L. On optimal selection of Galerkin information for solving severely ill-posed problems //
J. Comput. and Appl. Math. – 2016. – 2(100). – P. 92 – 105.
29. Solodky S. G., Myleiko G. L. The minimal radius of Galerkin information for severely ill-posed problems // J. Inverse
and Ill-Posed Probl. – 2014. – 22, № 5. – P. 739 – 757.
30. Solodky S. G., Semenova E. V. About minimal informational efforts by solving exponentially ill-posed problems //
J. Comput. and Appl. Math. – 2015. – 2. – P. 90 – 100.
31. Solodky S. G., Semenova E. V. On the optimal order of accuracy of an approximate solution to the Symm’s integral
equation // Журн. вычислит. математики и мат. физики. – 2012. – 52, № 3. – С. 472 – 488.
32. Tautenhahn U. Optimality for ill-posed problems under general source condition // Numer. Funct. Anal. and Optim. –
1998. – 19, № 3-4. – P. 377 – 398.
33. Traub J. F, Wasilkowski G., Wozniakowski H. Information-based complexity. – Boston: Acad. Press, 1988. – 523 p.
34. Werschulz A. G. What is the complexity of ill-posed problems? – New York: Columbia Univ., 1985. – 352 p.
35. Wozniakowski H. Information based complexity // Ann. Rev. Comput. Sci. – 1986. – 1. – P. 319 – 380.
Одержано 13.09.16
ISSN 1027-3190. Укр. мат. журн., 2017, т. 69, № 7
|
| id | umjimathkievua-article-1748 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | rus |
| last_indexed | 2026-03-24T02:11:56Z |
| publishDate | 2017 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/c5/b7ffe9fe90c733145350aef34080e5c5.pdf |
| spelling | umjimathkievua-article-17482019-12-05T09:25:34Z Hyperbolic cross and complexity of various classes of linear ill-posed problems Гіперболічний хрест і складність різних класів лінійних некоректних задач Myleiko, G. L. Solodkii, S. G. Милейко, Г. Л. Солодкий, С. Г. Милейко, Г. Л. Солодкий, С. Г. The present paper is a survey of the latest results obtained in the fields of information and algorithmiс complexity of severely ill-posed problems. Приведен обзор последних результатов в области информационной и алгоритмической сложности некорректных задач. Institute of Mathematics, NAS of Ukraine 2017-07-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/1748 Ukrains’kyi Matematychnyi Zhurnal; Vol. 69 No. 7 (2017); 951-963 Український математичний журнал; Том 69 № 7 (2017); 951-963 1027-3190 rus https://umj.imath.kiev.ua/index.php/umj/article/view/1748/730 Copyright (c) 2017 Myleiko G. L.; Solodkii S. G. |
| spellingShingle | Myleiko, G. L. Solodkii, S. G. Милейко, Г. Л. Солодкий, С. Г. Милейко, Г. Л. Солодкий, С. Г. Hyperbolic cross and complexity of various classes of linear ill-posed problems |
| title | Hyperbolic cross and complexity of various classes of linear ill-posed
problems |
| title_alt | Гіперболічний хрест і складність різних класів лінійних
некоректних задач |
| title_full | Hyperbolic cross and complexity of various classes of linear ill-posed
problems |
| title_fullStr | Hyperbolic cross and complexity of various classes of linear ill-posed
problems |
| title_full_unstemmed | Hyperbolic cross and complexity of various classes of linear ill-posed
problems |
| title_short | Hyperbolic cross and complexity of various classes of linear ill-posed
problems |
| title_sort | hyperbolic cross and complexity of various classes of linear ill-posed
problems |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/1748 |
| work_keys_str_mv | AT myleikogl hyperboliccrossandcomplexityofvariousclassesoflinearillposedproblems AT solodkiisg hyperboliccrossandcomplexityofvariousclassesoflinearillposedproblems AT milejkogl hyperboliccrossandcomplexityofvariousclassesoflinearillposedproblems AT solodkijsg hyperboliccrossandcomplexityofvariousclassesoflinearillposedproblems AT milejkogl hyperboliccrossandcomplexityofvariousclassesoflinearillposedproblems AT solodkijsg hyperboliccrossandcomplexityofvariousclassesoflinearillposedproblems AT myleikogl gíperbolíčnijhrestískladnístʹríznihklasívlíníjnihnekorektnihzadač AT solodkiisg gíperbolíčnijhrestískladnístʹríznihklasívlíníjnihnekorektnihzadač AT milejkogl gíperbolíčnijhrestískladnístʹríznihklasívlíníjnihnekorektnihzadač AT solodkijsg gíperbolíčnijhrestískladnístʹríznihklasívlíníjnihnekorektnihzadač AT milejkogl gíperbolíčnijhrestískladnístʹríznihklasívlíníjnihnekorektnihzadač AT solodkijsg gíperbolíčnijhrestískladnístʹríznihklasívlíníjnihnekorektnihzadač |