Level set of the asymptotic rate of convergence of the method of steepest descent
UDC 519.61 The asymptotic rate of convergence of the steepest descent method is considered as a function of the initial approximation. In this work, we study the set of the level of this speed, i.e. the set of initial approximations for which it takes a given value. A method for constructing this se...
Збережено в:
| Дата: | 2022 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Institute of Mathematics, NAS of Ukraine
2022
|
| Онлайн доступ: | https://umj.imath.kiev.ua/index.php/umj/article/view/6885 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Репозитарії
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860512555186782208 |
|---|---|
| author | Zhuk , P. F. Жук, Петро Федорович Жук, П. Ф. |
| author_facet | Zhuk , P. F. Жук, Петро Федорович Жук, П. Ф. |
| author_sort | Zhuk , P. F. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2025-03-31T08:45:58Z |
| description | UDC 519.61
The asymptotic rate of convergence of the steepest descent method is considered as a function of the initial approximation. In this work, we study the set of the level of this speed, i.e. the set of initial approximations for which it takes a given value. A method for constructing this set is proposed and its connected components are found. |
| doi_str_mv | 10.37863/umzh.v74i2.6885 |
| first_indexed | 2026-03-24T03:30:39Z |
| format | Article |
| fulltext |
DOI: 10.37863/umzh.v74i2.6885
УДК 519.61
П. Ф. Жук (Нац. авiац. ун-т, Київ)
МНОЖИНА РIВНЯ АСИМПТОТИЧНОЇ ШВИДКОСТI ЗБIЖНОСТI
МЕТОДУ НАЙШВИДШОГО СПУСКУ
The asymptotic rate of convergence of the method of steepest descent is considered as a function of the initial approximation.
In this work, we study the level set of this rate, i.e., the set of initial approximations, for which it takes a given value. A
method for constructing this set is proposed and its connected components are found.
Асимптотична швидкiсть збiжностi методу найшвидшого спуску розглядається як функцiя вiд початкового набли-
ження. У данiй роботi вивчається множина рiвня цiєї швидкостi, тобто множина початкових наближень, для яких
вона має задане значення. Запропоновано спосiб побудови цiєї множини i знайдено її компоненти зв’язностi.
Вступ. Метод найшвидшого спуску (SD), запропонований Кошi [1] для скiнченновимiрних
просторiв, є одним iз найбiльш вiдомих методiв оптимiзацiї та розв’язання операторних рiвнянь.
Канторович [2] узагальнив цей метод на нескiнченновимiрнi простори. Теоретичне дослiдження
нелiнiйних iтерацiйних методiв варiацiйного типу (до яких вiдноситься i метод SD) викликає
значнi труднощi, оскiльки їхнi послiдовнi наближення вже через кiлька iтерацiй складним
чином залежать вiд початкового наближення. Тому зазвичай обмежуються (див., наприклад, [3,
4]) оцiнкою норми оператора переходу iтерацiйного процесу.
Але такий пiдхiд для ряду практично важливих iтерацiйних методiв є занадто грубим. Так,
у роботах [5, 6] на п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д початкового наближення.
Для методу SD при мiнiмiзацiї квадратичного додатно визначеного функцiонала таке уточ-
нення можна здiйснити на основi його асимптотичної поведiнки. У статтi [7] на пiдставi обчис-
лювальних експериментiв було висловлено припущення, що в цьому випадку послiдовностi
нормованих градiєнтiв методу SD за парними i непарними iтерацiями збiгаються i їхнi гра-
ницi належать площинi натягненої на власнi вектори матрицi функцiонала, що вiдповiдають
найменшому i найбiльшому власним значенням цiєї матрицi. Це припущення було доведено в
статтi [8]. На пiдставi цього результату в роботi [9] введено поняття асимптотичної швидкостi
збiжностi методу SD i вказано суттєву за мiрою Лебега область її значень (без доведення).
Аналогiчнi результати для задач на власнi значення було отримано в роботах [10 – 12].
У статтi [13] Дж. Форсайт висловив припущення, що результат [8] можна узагальнити на
s-кроковий метод SD (цю гiпотезу не доведено i не спростовано досi, див. [14]). Деякий прогрес
в цьому напрямку було досягнуто в роботах [15 – 20]: у [16] описано множину граничних точок
послiдовностей нормованих градiєнтiв s-крокового методу, в [18, 19] доведено, що послiдов-
c\bigcirc П. Ф. ЖУК, 2022
178 ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
МНОЖИНА РIВНЯ АСИМПТОТИЧНОЇ ШВИДКОСТI ЗБIЖНОСТI МЕТОДУ НАЙШВИДШОГО . . . 179
ностi iтерацiйних параметрiв цього методу за парними i непарними iтерацiями збiгаються, а в
[20] детально розглянуто випадок s = 2.
Пiсля появи новаторської роботи [6] увага до градiєнтних методiв значно зросла. В роботi
[6] на пiдставi обчислювальних експериментiв було показано, що шляхом змiни величини
кроку можна значно збiльшити швидкiсть збiжностi методу SD. У наступних роботах (див.,
наприклад, [21 – 23] i наведену там бiблiографiю) багато зусиль було затрачено на виявлення
причин i розробку нових стратегiй вибору величини кроку для методiв швидкого градiєнтного
спуску. При цьому теоретичнi обґрунтування запропонованих стратегiй в основному спиралися
на роботи [8, 13]. Але, як зазначено в [24], нормованi градiєнти таких методiв демонструють
хаотичну поведiнку, що вимагає розробки нових теоретичних пiдходiв до їх аналiзу.
Зазначимо, що ранiше подiбний [6] результат було отримано у статтi [5]. Там на пiдставi об-
числювальних експериментiв показано, що чергування iтерацiй методу SD i методу мiнiмальних
нев’язок (так званий двоступеневий градiєнтний спуск) призводить до iстотного прискорення
цих методiв, узятих окремо. Узагальненню та теоретичному аналiзу двоступеневого градiєн-
тного спуску присвячено роботу [25]. Там показано, що за допомогою оцiнок норм операторiв
переходiв спостережуване прискорення пояснити не можна.
У роботах [26, 27] асимптотичну швидкiсть збiжностi методу SD було дослiджено на не-
перервнiсть i диференцiйовнiсть. Доведено, що для майже всiх за мiрою Лебега початкових
наближень вона неперервна та неперервно диференцiйовна. Показано також, що точками роз-
риву можуть бути лише точки з виродженням, тобто такi початковi наближення, якi або самi,
або їхнi наступнi наближення мiстять компоненти точного розв’язку. В роботi [28] вивчено
властивостi множини точок з виродженням i запропоновано спосiб їх побудови за допомогою
введених там обернених операторiв (зауважимо, що для методу SD в роботах [26 – 28] було
використано спецiальну симплексну форму).
У данiй роботi, що є продовженням робiт [26 – 28], вивчається множина рiвня асимптотичної
швидкостi збiжностi методу SD, тобто множина початкових наближень з фiксованим значенням
цiєї швидкостi (на необхiднiсть подiбного дослiдження вказувалося, наприклад, у [29]). У п. 2
запропоновано спосiб побудови цiєї множини за допомогою обернених операторiв, а в п. 3
визначено його структуру у виглядi компонент зв’язностi i запропоновано спосiб їх побудови.
Перспективним напрямком для подальших дослiджень є, на думку автора, поширення отри-
маних результатiв на s-кроковий метод найшвидшого спуску.
1. Постановка задачi. Нехай H — скiнченновимiрний дiйсний гiльбертовий простор зi
скалярним добутком (u, v) i нормою \| u\| =
\sqrt{}
(u, u), а A : H \rightarrow H — лiнiйний самоспряжений
i позитивно визначений оператор, спектр якого складається лише з простих власних значень
(це припущення не є принциповим, але спрощує формулювання результатiв).
Метод найшвидшого спуску (SD) розв’язання операторного рiвняння Au = f, або, що те
саме, мiнiмiзацiї квадратичного функцiонала F (u) = 0,5(Au, u) - (f, u) в просторi H, задається
рекурентним спiввiдношенням
u(k+1) = u(k) - \tau kw
(k), k = 0, 1, . . . , (1.1)
де u(0) \in H — довiльне початкове наближення, w(k) = Au(k) - f — нев’язка на k-й iтерацiї,
а iтерацiйний параметр \tau k задовольняє умову мiнiмуму величини функцiонала F (u(k+1)) =
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
180 П. Ф. ЖУК
= 0,5(Au(k+1), u(k+1)) - (f, u(k+1)) i обчислюється за формулою
\tau k =
\| w(k)\| 2
(Aw(k), w(k))
. (1.2)
Метод SD має таку асимптотичну властивiсть [3]: якщо перше наближення u(1) не є точним
розв’язком u\ast рiвняння Au = f, то iснує числова послiдовнiсть
\~\rho k(u
(0)) =
\sqrt{} \bigl(
F (u(k+1)) - F (u\ast )
\bigr)
/(F (u(k)) - F (u\ast )), k = 0, 1, . . . ,
яка монотонно не спадає i збiгається.
Позначимо через \~\rho \infty (u(0)) її границю i визначимо на H функцiю
\~V (u(0)) =
\left\{ \infty , якщо u(1) = u\ast ,
- \mathrm{l}\mathrm{n} \~\rho \infty (u(0)), якщо u(1) \not = u\ast ,
(1.3)
яку будемо називати асимптотичною швидкiстю збiжностi методу SD.
Основним завданням даної роботи є вивчення множини рiвня функцiї \~V , тобто множини по-
чаткових наближень iз заданим значенням асимптотичної швидкостi збiжностi. Для вирiшення
цього завдання зручно представити метод найшвидшого спуску в симплекснiй формi.
Нехай \{ ei, i = 1, 2, . . . , n + 1\} — ортонормована система власних векторiв оператора A.
Вибравши їх в якостi базису простору H, ототожнимо цей простiр з арифметичним простором
\BbbR n+1 . Позначимо через S1 = (1, 0, . . . , 0), S2 = (0, 1, 0, . . . , 0), . . . , Sn = (0, . . . , 0, 1), Sn+1 =
= (0, . . . , 0) вершини стандартного симплекса
\=S =
\Biggl\{
x = (x1, . . . , xn)
\bigm| \bigm| \bigm| \bigm| \bigm|
n\sum
i=1
xi \leq 1, xi \geq 0, i = 1, 2, . . . , n
\Biggr\}
простору \BbbR n, а через S\omega = \=S \setminus \{ S1, . . . , Sn+1\} симплекс \=S без вершин.
Нехай \lambda 1 < . . . < \lambda n+1 — власнi значення оператора A (припускаємо, що вони простi; їх
сукупнiсть позначимо через \Lambda ). Визначимо вiдображення T : S\omega \rightarrow S\omega за формулою \^x = Tx,
де x = (x1, . . . , xn), xn+1 = 1 - x1 - . . . - xn, \mu (x) =
\sum n+1
i=1
\lambda ixi, \beta (x) =
\sum n+1
i=1
(\mu (x) - \lambda i)
2xi,
\^xi = (\mu (x) - \lambda i)
2xi/\beta (x), i = 1, . . . , n, \^x = (\^x1, . . . , \^xn). Подовжимо далi вiдображення T на
весь симплекс \=S, покладаючи TSi = Si, i = 1, 2, . . . , n+ 1.
Симплексною формою методу SD будемо називати iтерацiйний процес x(k+1) = Tx(k),
k = 0, 1, . . . . Вiн тiсно пов’язаний з iтерацiйним процесом (1.1), (1.2), а саме, якщо x(0) =
= \chi (w(0)) \in S\omega , то
x(k) = \chi (w(k)), k = 1, 2, . . . , (1.4)
де вiдображення \chi : \BbbR n+1 \setminus \{ 0\} \rightarrow \=S задано формулою xi = w2
i
\Big/ \sum n+1
j=1
w2
j , i = 1, 2, . . . , n.
З рiвностi (1.4) випливає, що послiдовнiсть
\rho k(x
(0)) =
\sqrt{} n+1\sum
i=1
\lambda - 1
i
\bigl(
1 - \lambda i
\big/
\mu (x(k))
\bigr) 2
x
(k)
i
\Big/ n+1\sum
i=1
\lambda - 1
i x
(k)
i
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
МНОЖИНА РIВНЯ АСИМПТОТИЧНОЇ ШВИДКОСТI ЗБIЖНОСТI МЕТОДУ НАЙШВИДШОГО . . . 181
збiгається при x(0) = \chi (w(0)) \in S\omega з послiдовнiстю \~\rho k(u
(0)) i
\~V (u(0)) = V (x(0)) =
\Biggl\{
\infty , якщо x(0) /\in S\omega ,
- \mathrm{l}\mathrm{n} \rho \infty (x(0)), якщо x(0) \in S\omega ,
(1.5)
де \rho \infty (x(0)) = \mathrm{l}\mathrm{i}\mathrm{m}k\rightarrow \infty \rho k(x
(0)).
Функцiю V, визначену на симплексi \=S формулою (1.5), будемо називати асимптотичною
швидкiстю збiжностi методу SD в симплекснiй формi. Таким чином, дослiдження асимптотич-
ної швидкостi збiжностi методу SD, заданої формулою (1.3), зводиться до вивчення функцiї V,
заданої виразом (1.5).
Розглянемо асимптотичну поведiнку методу SD в симплекснiй формi.
Нехай 1 \leq i1 < . . . < im \leq n + 1 — деякi цiлi числа. Позначимо через \=Si1...im грань
симплекса \=S з вершинами Si1 , . . . , Sim , через
Si1...im =
\left\{ x | x = \alpha 1Si1 + . . .+ \alpha mSim , \alpha p > 0, p = 1, . . . ,m,
m\sum
p=1
\alpha p = 1
\right\}
внутрiшнiсть цiєї гранi, через S = S1...n+1 внутрiшнiсть симплекса \=S, а через \partial S = \=S \setminus S його
поверхню. З означення вiдображення T випливає, що T \=Si1...im \subseteq \=Si1...im i, крiм того, нерухомi
точки вiдображення T 2 утворюють множину
\bigcup
1\leq i<j\leq n+1
\=Sij .
Асимптотична поведiнка методу SD в симплекснiй формi випливає з результатiв робо-
ти [8] i спiввiдношення (1.4): якщо x \in Si1...im , то послiдовностi точок \{ T 2kx, k = 0, 1, . . .\} ,
\{ T 2k+1x, k = 0, 1, . . .\} збiгаються i їхнi границi є нерухомими точками вiдображення T 2 :
x\infty = \mathrm{l}\mathrm{i}\mathrm{m}
k\rightarrow \infty
T 2k \in Si1im , \^x\infty = \mathrm{l}\mathrm{i}\mathrm{m}
k\rightarrow \infty
T 2k+1x = Tx\infty \in Si1im . (1.6)
Таким чином, якщо ввести вiдображення T\infty , задане формулою T\infty x = \mathrm{l}\mathrm{i}\mathrm{m}k\rightarrow \infty T 2kx, то
зi спiввiдношень (1.6) випливає, що на множинi S\omega визначено функцiї \xi , i, j такi, що для
будь-якого x \in S\omega мають мiсце рiвностi
x\infty = T\infty x = \xi (x)Si(x) + (1 - \xi (x))Sj(x),
(1.7)
\^x\infty = Tx\infty = (1 - \xi (x))Si(x) + \xi (x)Sj(x),
де 0 < \xi (x) < 1, 1 \leq i(x) < j(x) \leq n+ 1. Крiм того, якщо визначити на множинi S\omega функцiю
\rho :
\rho (x) =
\sqrt{} n+1\sum
i=1
\lambda - 1
i
\bigl(
1 - \lambda i
\big/
\mu (x)
\bigr) 2
xi
\bigg/ n+1\sum
i=1
\lambda - 1
i xi,
де xn+1 = 1 - x1 - . . . - xn, \mu (x) =
\sum n+1
i=1
\lambda ixi, то з монотонностi послiдовностi \rho k(x(0)) i
рiвностi (1.7) випливає, що для будь-якого x \in S\omega справджуються спiввiдношення
\rho (x) \leq \rho (Tx) \leq . . . \leq \rho (T kx) \leq . . . \rightarrow \rho \infty (x) = \rho (x\infty ) = \rho (Tx\infty ),
\rho \infty (x) = \gamma (x)
\Big/ \sqrt{}
\gamma 2(x) + \lambda i(x)\lambda j(x),
(1.8)
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
182 П. Ф. ЖУК
де \gamma (x) = (\lambda j(x) - \lambda i(x))
\sqrt{}
\xi (x)(1 - \xi (x)). Зокрема,
V (x) = V (T kx) = V (x\infty ), k = 1, 2, . . . .
Тут i далi будемо припускати що n \geq 2 i \mathrm{m}\mathrm{i}\mathrm{n}i=2,3,...,n
\bigm| \bigm| (\lambda 1 + \lambda n+1)/2 - \lambda i
\bigm| \bigm| досягається лише
на одному iндексi i (який позначимо через i0) i \lambda \equiv \lambda i0 \leq (\lambda 1 + \lambda n+1)/2 (це припущення не
обмежує загальностi результатiв, але спрощує запис).
Позначимо
\rho max = (\lambda n+1 - \lambda 1)/(\lambda n+1 + \lambda 1), Vmin = - \mathrm{l}\mathrm{n} \rho max,
\gamma = \lambda 1\lambda n+1/(\lambda (\lambda 1 + \lambda n+1 - \lambda )), \rho min =
\sqrt{}
(1 - \gamma )/(1 + \gamma ),
Vmax = - \mathrm{l}\mathrm{n} \rho min, \Delta = [Vmin, Vmax), \=\Delta = [Vmin, Vmax].
Зауважимо, що Vmin — мiнiмальне значення функцiї V на симплексi \=S (див. [26], (1.16)), а \=\Delta —
суттєва (за мiрою Лебега) область значень цiєї функцiї на \=S [26] (теорема 2.1).
Нам будуть потрiбнi також множини
S\ast =
\bigl\{
x \in \=S | 0 < x1, x1 + . . .+ xn < 1
\bigr\}
, S\ast = \=S \setminus S\ast , M =
\bigl\{
x \in S\ast | V (x) \in \Delta
\bigr\}
.
З [26] (формула (2.1)) маємо, що S \subset S\ast \subset \=S, S\ast \subset \partial S, TS\ast = S\ast , TS\ast = S\ast , T
\infty S\ast = S1,n+1.
Нехай x — довiльна точка симплекса \=S . Розглянемо iтерацiйну послiдовнiсть T kx,
k = 0, 1, . . . . Можливi два випадки.
1. Iснує скiнченне число k \in \{ 0, 1, . . .\} таке, що T kx \in \partial S . У цьому випадку iснує єдине
число
k(x) =
\left\{ 0, якщо x \in \partial S,
p, якщо T p - 1x \in S, T px \in \partial S, p \geq 1,
яке будемо називати номером виродження точки x, а саму точку x — вектором iз виродженням.
При k(x) = 0 вектор x будемо називати виродженим, а при k(x) \geq 1 — вектором, що вирод-
жується. Позначимо через \=V множину векторiв iз виродженням, а через V множину векторiв,
що вироджуються. Оскiльки множиною вироджених векторiв є \partial S, справджуються рiвностi
\=V = \partial S \cup V, \partial S \cap V = \varnothing .
2. Для будь-якого скiнченного числа k \in \{ 0, 1, . . .\} T kx \in S . Такий вектор x будемо
називати вектором без виродження; множину всiх векторiв без виродження позначимо через U.
Очевидно, що
\=S = \partial S \cup V \cup U.
2. Побудова множини рiвня. Пiд множиною рiвня c функцiї V будемо розумiти множину
\=V - 1(c) =
\bigl\{
x \in \=S | V (x) = c
\bigr\}
,
де c — довiльне дiйсне число.
Задача побудови множини \=V - 1(c) рекурсивна. Справдi, запишемо \=V - 1(c) у виглядi об’єд-
нання двох неперетинних множин X = \=V - 1(c)\cap S\ast i Y = \=V - 1(c)\cap S\ast . Оскiльки за означенням
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
МНОЖИНА РIВНЯ АСИМПТОТИЧНОЇ ШВИДКОСТI ЗБIЖНОСТI МЕТОДУ НАЙШВИДШОГО . . . 183
S\ast = \{ x \in \=S | x1 = 0 \} \cup \{ x \in \=S | x1 + . . . + xn = 1 \} , то S\ast — замкнена множина, що є
об’єднанням двох (n - 1)-вимiрних граней симплекса \=S .
Таким чином, задача побудови множини рiвня для n-вимiрного симплекса \=S зводиться до
побудови множини X i множини рiвня для (n - 1)-вимiрного симплекса. Тому далi об’єктом
дослiдження буде множина V - 1(c) = \{ x \in S\ast | V (x) = c\} , яку будемо також називати
множиною рiвня функцiї V (на множинi S\ast ).
Оскiльки Vmin — мiнiмальне значення функцiї V на симплексi \=S, то множина V - 1(c) буде
порожньою при c < Vmin. Тому цiкавим є лише випадок c \in [Vmin,\infty ). У цьому випадку
(див. (1.6)) множина V - 1(c)\cap S1,n складається з двох точок: xc i \^xc = Txc (при c = Vmin вони
збiгаються).
Виходячи зi спiввiдношень (1.7), (1.8), множину V - 1(c) можна виразити через множини
рiвня функцiї \xi , визначеної в (1.7):
V - 1(c) = \xi - 1(xc) \cup \xi - 1(\^xc), (2.1)
де \xi - 1(y) =
\bigl\{
x \in S\ast | \xi (x) = \xi (y)
\bigr\}
. Зауважимо, що множини \xi - 1(xc), \xi
- 1(\^xc) не перетина-
ються при c \not = Vmin i збiгаються при c = Vmin .
Будова множини рiвня якiсно змiнюється в залежностi вiд того, чи належить значення c
суттєвiй областi значень функцiї V чи нi. Тому розглянемо два випадки.
1. Припустимо спочатку, що c \in \Delta . Покажемо, що в цьому випадку рiвняння
\xi (x) = \xi (xc) (2.2)
визначає неявну функцiю в околi точки xc .
Позначимо
x1c = \xi (xc), \BbbR n
+ =
\bigl\{
x \in \BbbR n | xi \geq 0, i = 1, . . . , n
\bigr\}
, \BbbR n - 1
1 =
\bigl\{
x \in \BbbR n | x1 = 0
\bigr\}
,
K\varepsilon =
\bigl\{
x \in \BbbR n | x1c - \varepsilon < x1 < x1c + \varepsilon , - \varepsilon < xi < \varepsilon , i = 2, . . . , n
\bigr\}
, K+
\varepsilon = K\varepsilon \cap \BbbR n
+.
За лемою 2.4 [26] множина M вiдкрита в \=S, отже, для деякого \varepsilon > 0 K+
\varepsilon \subseteq M. Тодi з [27]
випливає, що \xi \in C1(K+
\varepsilon ). Тому (див., наприклад, [30, с. 127]) iснує розширення \=\xi функцiї \xi
на область K\varepsilon зi збереженням класу гладкостi. При цьому з [27] випливає рiвнiсть \=\xi \prime x1
(xc) = 1,
тобто для функцiї \=\xi в точцi xc виконано умови теореми про неявну функцiю. За цiєю теоремою
рiвняння (2.2) локально розв’язне вiдносно x1 :
x1 = \zeta c(\~x), (2.3)
де \~x = (0, x2, . . . , xn) \in \~O(\delta , 0) \subseteq \BbbR n - 1
1 , \~O (\delta , 0) — окiл нуля в просторi \BbbR n - 1
1 (вiдкрита куля
радiуса \delta ), а функцiя \zeta c \in C1( \~O(\delta , 0)).
Теорема 2.1. Якщо c \in \Delta , то в деякому околi O(xc) точки xc множина V - 1(c) є (n - 1)-
вимiрною поверхнею класу гладкостi C1, що задана рiвнянням (2.3).
Доведення. Для досить малих \varepsilon > 0 множина рiвня \xi - 1(xc) в околi O(\varepsilon , xc) задається
рiвнянням (2.3) i є (n - 1)-вимiрною поверхнею класу гладкостi C1 .
При xc = \^xc маємо V - 1(c) = \xi - 1(xc), отже, твердження теореми є правильним.
Припустимо тепер, що xc \not = \^xc . Тодi iснує \varepsilon > 0, при якому множини \xi - 1(\^xc) i O(\varepsilon , xc)
не перетинаються. Справдi, в iншому випадку iснувала б послiдовнiсть x(1), x(2), . . . точок з
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
184 П. Ф. ЖУК
множини \xi - 1(\^xc), яка б збiгалася до точки xc . Але тодi внаслiдок неперервностi функцiї \xi
при c \in \Delta (див. [26], теорема 3.1) послiдовнiсть \xi (x(1)), \xi (x(2)), . . . збiгалась би до \xi (xc), що
суперечить умовi xc \not = \^xc . Таким чином, необхiдне значення \varepsilon > 0 iснує. Твердження теореми
тепер випливає з розвинення (2.1).
Теорему 2.1 доведено.
Зауваження 2.1. Теорема 2.1 справедлива i для точки \^xc .
Спираючись на теорему 2.1, побудуємо множину V - 1(c) за допомогою багатозначного
оператора T - 1 (див. [28], теорема 1). Покладемо
\=G = \~O (\delta , 0) \cap \BbbR n
+, \=\Sigma o =
\bigl\{ \bigl(
\zeta c(\~x), \~x2, . . . , \~xn
\bigr)
| \~x = (0, \~x2, . . . , \~xn) \in \=G
\bigr\}
.
Теорема 2.2. Якщо c \in \Delta , то
V - 1(c) =
\infty \bigcup
k=0
T - k \=\Sigma o. (2.4)
Доведення. Припустимо, що точка x \in V - 1(c). Тодi або T 2kx \rightarrow xc, або T 2k+1x \rightarrow xc при
k \rightarrow \infty . Отже, при деякому цiлому невiд’ємному числу m точка Tmx потрапить в окiл O(xc)
точки xc, що задовольняє теорему 2.1. Оскiльки Tmx \in V - 1(c), то за теоремою 2.1 Tmx \in \=\Sigma o,
тобто x \in T - m \=\Sigma o .
Припустимо тепер, що точка x \in
\bigcup \infty
k=0 T
- k \=\Sigma o . Тодi x \in T - m \=\Sigma o при деякому числу m,
тобто Tmx \in \=\Sigma o. За теоремою 2.1 \=\Sigma o \subseteq V - 1(c), отже, x \in V - 1(c).
Теорему 2.2 доведено.
2. Розглянемо тепер випадок c \in [Vmax,\infty ). За означенням множини M маємо V - 1(c)\cap M =
= \varnothing , i з [27] випливає, що функцiя V в цьому випадку в будь-якiй точцi множини рiвня V - 1(c)
не диференцiйовна. Оскiльки за теоремою 3.1 [26] U \subseteq M, то
V - 1(c) \subseteq \=V.
Отже, при c \in [Vmax,\infty ) будь-яка точка x множини рiвня V - 1(c) є вектором з виродженням,
тобто або вона сама знаходиться на поверхнi симплекса \=S, або там знаходиться деяка її iтерацiя
T kx. Множину рiвня в цьому випадку запишемо у виглядi
V - 1(c) = V - 1
\partial S (c) \cup V - 1
S (c),
де V - 1
\partial S (c) = V - 1(c) \cap \partial S, V - 1
S (c) = V - 1(c) \cap S. Множина V - 1
\partial S (c) є слiдом множини V - 1(c)
на поверхнi симплекса \=S, а тому складається з множин рiвня функцiї V на (n - 1)-вимiрних
симплексах (гранях симплекса \=S ).
Розглянемо множину V - 1
S (c). Вона складається з векторiв, що вироджуються. Вкажемо
спосiб її побудови за припущення, що множина V - 1
\partial S (c) є вiдомою.
Нехай y \in V - 1
\partial S (c) — деяка внутрiшня точка деякої (n - 1)-вимiрної гранi симплекса \=S, ха-
рактеристичне рiвняння якої (див. [28], (2.6)) має корiнь з \Lambda (множину таких точок позначимо
через B\partial S ). Тодi рiвняння Tx = y має нескiнченно багато розв’язкiв, що задаються форму-
лою (2.11) [28] i утворюють пiвiнтервал x = x(\alpha ), \alpha \in [0,\infty ). Позначимо через X(y) iнтервал
x = x(\alpha ), \alpha \in (0,\infty ), а через BS множину
BS =
\bigcup
y\in B\partial S
X(y).
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
МНОЖИНА РIВНЯ АСИМПТОТИЧНОЇ ШВИДКОСТI ЗБIЖНОСТI МЕТОДУ НАЙШВИДШОГО . . . 185
Доведемо, що множину V - 1
S (c) можна записати у виглядi
V - 1
S (c) =
\infty \bigcup
k=0
T - kBS . (2.5)
Справдi, припустимо спочатку, що точка x \in V - 1
S (c). Тодi x \in V, отже, T k(x) - 1x \in S,
T k(x)x \in \partial S, де k(x) — номер виродження точки x. Покладемо z = T k(x) - 1x, y = Tz . Оскiльки
точка y належить внутрiшностi деякої (n - 1)-вимiрної гранi симплекса \=S, то y \in V - 1
\partial S (c). Далi,
оскiльки Tz = y, z \in S, y \in \partial S, то \mu (z) \in \Lambda , тобто характеристичне рiвняння для точки y
має корiнь з \Lambda . Таким чином, y \in B\partial S i z \in X(y) \subseteq BS , отже, x \in T - (k(x) - 1)BS .
Припустимо тепер, що точка x \in T - kBS при деякому невiд’ємному числу k . Тодi T kx \in
\in BS , отже, T kx \in X(y) для деякого y \in B\partial S . З означення iнтервалу X(y) випливає, що
T kx \in S, T k+1x = y \in \partial S, отже, x \in V i, оскiльки y \in V - 1
\partial S (c), то x \in V - 1
S (c). Рiвнiсть (2.5)
доведено.
3. Структура множини рiвня. Формула (2.4) дозволяє побудувати множину рiвня асимп-
тотичної швидкостi збiжностi методу SD, але не показує структури цiєї множини. Знайдемо
компоненти зв’язностi множини V - 1(c).
Позначимо через G внутрiшнiсть множини \=G в топологiї простору \BbbR n - 1 . Покладемо \partial G =
= \=G \setminus G, \Sigma o =
\Bigl\{ \bigl(
\zeta c(\~x), \~x2, . . . , \~xn
\bigr)
| \~x = (0, \~x2, . . . , \~xn) \in G
\Bigr\}
, \partial \Sigma o = \=\Sigma o \setminus \Sigma o . Тодi
\Sigma o \subseteq S, \partial \Sigma o \subseteq \partial S, \=\Sigma o = \Sigma o \cup \partial \Sigma o. (3.1)
З (2.4), (3.1) маємо
V - 1(c) = \Sigma \cup \partial \Sigma , (3.2)
де \Sigma =
\bigcup \infty
k=0 T
- k\Sigma o, \partial \Sigma =
\bigcup \infty
k=0 T
- k\partial \Sigma o.
Доведемо, що множина \partial \Sigma не залежить вiд вибору околу \~O(\delta , 0) (хоча множини \Sigma o, \partial \Sigma o
залежать).
Лема 3.1. Якщо c \in \Delta , то множина \partial \Sigma дорiвнює V - 1(c) \cap \=V i не залежить вiд вибору
околу \~O(\delta , 0).
Доведення. Припустимо, що точка x \in \partial \Sigma . Тодi x \in V - 1(c) i для деякого числа k \in
\in \{ 0, 1, . . .\} T kx \in \partial \Sigma o. Зi спiввiдношень (3.1) випливає, що T kx \in \partial S, тому x \in \=V. Отже,
x \in V - 1(c) \cap \=V.
Припустимо тепер, що точка x \in V - 1(c)\cap \=V. Оскiльки x \in \=V, то T kx \in \partial S при k \geq k(x), де
k(x) — номер виродження точки x. Далi, оскiльки x \in V - 1(c), то i T k(x)x \in V - 1(c). Але тодi
за теоремою 2.2 iснує число m \in \{ 0, 1, . . .\} таке, що Tm
\bigl(
T k(x)x
\bigr)
\in \=\Sigma o. Отже, T k(x)+mx \in \partial \Sigma o,
тобто x \in \partial \Sigma .
Таким чином, \partial \Sigma = V - 1(c) \cap \=V. Залишилося зазначити, що права частина цiєї рiвностi не
залежить вiд вибору околу \~O(\delta , 0), отже, i множина \partial \Sigma не залежить вiд вибору цього околу.
Лему 3.1 доведено.
Множина \Sigma , взагалi кажучи, залежить вiд вибору околу \~O(\delta , 0). Покажемо, що за винятком
скiнченного числа значень c \in \Delta окiл \~O(\delta , 0) можна вибрати так, щоб множини \Sigma i \partial \Sigma не
перетиналися (зауважимо, що це твердження не випливає з того, що не перетинаються множини
\Sigma o i \partial \Sigma o).
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
186 П. Ф. ЖУК
Розглянемо множину \{ x \in T\infty M | \mu (x) \in \Lambda \} . Оскiльки n \geq 2, то ця множина непорожня
i скiнченна; позначимо її елементи через x(1), . . . , x(l), 1 \leq l \leq n - 1
\bigl(
це точки вигляду\bigl(
(\lambda n+1 - \lambda i)/(\lambda n+1 - \lambda 1), 0, . . . , 0
\bigr) \bigr)
. Покладемо
ci = V (x(i)), i = 1, . . . , l, \Delta \ast = \Delta \setminus \{ c1, . . . , cl\} .
Лема 3.2. Якщо c \in \Delta \ast , то iснує окiл \~O(\delta , 0) такий, що \Sigma \cap \partial \Sigma = \varnothing .
Доведення. Оскiльки c \in \Delta \ast , то xc, \^xc /\in \{ x(1), . . . , x(l)\} i \mu (xc), \mu (\^xc) /\in \Lambda . Тому iснують
околи O1
\bigl(
xc
\bigr)
i O (\^xc) вiдповiдних точок такi, що
\mu (x) /\in \Lambda \forall x \in O1(xc) \cup O(\^xc). (3.3)
За наслiдком 2.2 [26] iснує окiл O2(xc) точки xc такий, що T kO2(xc) \subseteq O1(xc) \cup O(\^xc),
k = 0, 1, . . . . Тому зi спiввiдношення (3.3) випливає, що
S \cap O2(xc) \cap \=V = \varnothing . (3.4)
Покладемо O3(xc) = O2(xc)\cap O(xc), де O
\bigl(
xc
\bigr)
— окiл, який гарантує теорема 2.1, i виберемо
окiл \~O(\delta , 0) так, щоб \=\Sigma o \subseteq O3(xc). Тодi з рiвностi (3.4) випливає, що \Sigma o \cap \=V = \varnothing . Це означає,
що i \Sigma \cap \=V = \varnothing , оскiльки для будь-якої точки x \in \Sigma \cap \=V iснує таке число k \in \{ 0, 1, . . .\} , що
T kx \in \Sigma o \cap \=V. Залишилось зауважити, що за лемою 3.1 \partial \Sigma \subseteq \=V.
Лему 3.2 доведено.
Лема 3.3. Якщо c \in \Delta i \Sigma \cap \partial \Sigma = \varnothing , то \Sigma \subseteq U.
Доведення проведемо вiд супротивного. Припустимо, що точка x \in \Sigma \setminus U. Тодi x \in \=V i за
лемою 3.1 x \in \partial \Sigma , тобто \Sigma \cap \partial \Sigma \not = \varnothing . Прийшли до суперечностi.
Лема 3.4. Якщо c \in \Delta , то iснує окiл \~O (\delta , 0) такий, що для будь-якої точки x \in \Sigma маємо
\xi \prime (x) \not = 0.
Доведення. Оскiльки c \in \Delta , то \Sigma \subseteq V - 1(c) \subseteq M. Отже, згiдно з [27], похiдна \xi \prime (x) iснує
i неперервна в будь-якiй точцi x \in \Sigma . Оскiльки \xi \prime x1
(xc) = 1, то \xi \prime (xc) \not = 0 й iснує окiл \~O(\delta , 0)
такий, що \xi \prime (x) \not = 0 на множинi \Sigma o. Покажемо, що для цього околу \~O(\delta , 0) похiдна \xi \prime (x) не
дорiвнює нулю i на множинi \Sigma .
Припустимо протилежне: \xi \prime (x) = 0 для деякої точки x \in \Sigma . З означення множини \Sigma
випливає, що T kx \in \Sigma o для деякого числа k \in \{ 0, 1, . . .\} , тому
\xi \prime (T kx) \not = 0. (3.5)
Але, з iншого боку, \xi \prime (x) = \xi \prime (T kx)\scrJ (x, T k), отже,
\xi \prime (T kx)\scrJ (x, T k) = 0. (3.6)
Розглянемо матрицю Якобi \scrJ (x, T k). Оскiльки T kx \in \Sigma o \subseteq S, то
\Lambda (x, k) =
\bigl\{
\mu (T ix), i = 0, 1, . . . , k - 1
\bigr\}
\cap \Lambda = \varnothing ,
отже, за теоремою 4 [28] матриця \scrJ (x, T k) невироджена. Таким чином, система лiнiйних
однорiдних рiвнянь (3.6) має лише тривiальний розв’язок \xi \prime (T kx) = 0, що суперечить нерiв-
ностi (3.5).
Лему 3.4 доведено.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
МНОЖИНА РIВНЯ АСИМПТОТИЧНОЇ ШВИДКОСТI ЗБIЖНОСТI МЕТОДУ НАЙШВИДШОГО . . . 187
Зауваження 3.1. Припустимо, що \Sigma \cap \partial \Sigma = \varnothing . Тодi з леми 3.3 випливає, що \Sigma \subseteq U.
Тому матриця Якобi \scrJ (x, T k) невироджена для будь-яких x \in \Sigma i k \in \{ 0, 1, . . .\} [28] (лема 2).
Вiзьмемо довiльну точку x \in \Sigma . Оскiльки \xi \prime (xc) \not = 0, то для досить великого числа k також
\xi \prime (T kx) \not = 0. Але тодi з невиродженостi матрицi \scrJ (x, T k) випливає, що \xi \prime (x) \not = 0. Тобто з
умови \Sigma \cap \partial \Sigma = \varnothing маємо, що \xi \prime (x) \not = 0 \forall x \in \Sigma .
Перейдемо тепер до диз’юнктивного розвинення множини \Sigma при умовi, що c \in \Delta \ast , а окiл
\~O (\delta , 0) такий, що \Sigma \cap \partial \Sigma = \varnothing .
Оскiльки c \in \Delta \ast , то \mu (xc), \mu (\^xc) /\in \Lambda й iснують числа i(1), i(2) \in \{ 1, 2, . . . , n\} такi, що
\mu (xc) \in
\bigl(
\lambda i(1) , \lambda i(1)+1
\bigr)
, \mu (\^xc) \in
\bigl(
\lambda i(2) , \lambda i(2)+1
\bigr)
. На множинi S визначено оберненi оператори
T - 1
i(1)
, T - 1
i(2)
та їх добуток L = T - 1
i(1)
T - 1
i(2)
: S \rightarrow S . Покладемо
Eo = \Sigma o, Ek+1 = LEk, k = 0, 1, . . . ,
(3.7)
E =
\infty \bigcup
k=0
Ek.
Лема 3.5. Якщо c \in \Delta \ast i \Sigma \cap \partial \Sigma = \varnothing , то E \subseteq \Sigma .
Доведення. Припустимо, що x \in E. Тодi x = Lky, де y \in \Sigma o . Отже, y = T 2kx \in \Sigma o, тобто
x \in T - 2k\Sigma o \subseteq \Sigma .
Лема 3.6. Якщо c \in \Delta \ast i \Sigma \cap \partial \Sigma = \varnothing , то E є компонентою зв’язностi множини \Sigma .
Доведення. З означення множини \Sigma o випливає, що вона зв’язна. Оскiльки оператор L є
неперервним на S, то i множини Ek, k = 0, 1, . . . , за побудовою, також є зв’язними. Покажемо,
що
Ek \cap \Sigma o \not = \varnothing \forall k = 1, 2, . . . . (3.8)
Справдi, нехай x(m) \in \Sigma o, m = 1, 2, . . . , — довiльна збiжна до точки xc послiдовнiсть,
а y(m) = Lx(m) . Послiдовнiсть y(m) обмежена, оскiльки розташована у множинi S . Кожна її
гранична точка y є, очевидно, розв’язком рiвняння T 2y = xc, яке еквiвалентне системi рiвнянь
Tw = xc, T y = w. За теоремою 1 [28] ця система рiвнянь має єдиний розв’язок: w = \^xc,
y = xc . Отже, послiдовнiсть y(m) = Lx(m), m = 1, 2, . . . , збiгається до точки xc .
Аналогiчно доводимо, що послiдовностi Lkx(m), m = 1, 2, . . . , збiгаються до точки xc
для будь-якого числа k = 1, 2, . . . . Отже, для будь-якого k = 1, 2, . . . iснує число m, що
залежить вiд k, таке, що точки x(m), Lkx(m) належать множинi \Sigma o . Але тодi Lkx(m) \in Ek \cap \Sigma o
i спiввiдношення (3.8) є правильним. З цього спiввiдношення i зв’язностi множин Ek, k =
= 0, 1, . . . , випливає зв’язнiсть множини E.
Далi, з неперервностi операторiв T, L на S випливає, що для будь-якої точки x множини
E iснує окiл O(x) такий, що O(x) \cap \Sigma \subseteq E, тобто множина E є компонентою зв’язностi
множини \Sigma .
Лему 3.6 доведено.
Розглянемо поряд з множиною E множину \^E = TE.
Лема 3.7. Якщо c \in \Delta \ast i \Sigma \cap \partial \Sigma = \varnothing , то \^E — зв’язна пiдмножина множини \Sigma i
\mu (E) \subseteq (\lambda i(1) , \lambda i(1)+1), \mu (\^E) \subseteq (\lambda i(2) , \lambda i(2)+1). (3.9)
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
188 П. Ф. ЖУК
Доведення. Перше твердження випливає з леми 3.6 i неперервностi оператора T на S . Далi,
оскiльки функцiя \mu неперервна на симплексi \=S, то множини \mu (E), \mu (\^E) також зв’язнi. Зазначи-
мо, що точки xc i \^xc є граничними для множин E i \^E вiдповiдно, тому \mu (E)\cap (\lambda i(1) , \lambda i(1)+1) \not = \varnothing ,
\mu (\^E) \cap (\lambda i(2) , \lambda i(2)+1) \not = \varnothing . Отже, якщо хоча б одне iз включень (3.9) не виконано, то iснує
точка x \in E \cup \^E, для якої \mu (x) \in \Lambda . Але тодi x \in \=V i за лемою 3.3 x /\in \Sigma , що суперечить
включенню E \cup \^E \subseteq \Sigma .
Лему 3.7 доведено.
Лема 3.8. Якщо c \in \Delta \ast i \Sigma \cap \partial \Sigma = \varnothing , то \^E = TE, E = T - 1
i(1)
\^E, E = T \^E, \^E = T - 1
i(2)
E.
Доведення. За означенням \^E = TE, отже, вiдображення T : E \rightarrow \^E є сюр’єктивним. Пока-
жемо, що воно бiєктивне.
Розглянемо рiвняння Tx = y, де y \in \^E. Оскiльки y \in S, то воно має n розв’язкiв:
x(j)(y) = T - 1
j y, j = 1, . . . , n. За теоремою 2 [28] \mu (x(j)(y)) \in (\lambda j , \lambda j+1), j = 1, . . . , n, тому
якщо x(j)(y) \in E, то з леми 3.7 випливає, що j = i(1) .
Отже, вiдображення T : E \rightarrow \^E є бiєктивним i першi двi рiвностi доведено.
Далi, з означення (3.7) множини E випливає, що T 2E = E, тому T \^E = E. Аналогiчно
попередньому випадку доводимо, що вiдображення T : \^E \rightarrow E бiєктивне i оберненим до нього
є T - 1
i(2)
.
Лему 3.8 доведено.
Лема 3.9. Якщо xc \not = \^xc, то E \cap \^E = \varnothing , iнакше E = \^E.
Доведення. Оскiльки T\infty E = \{ xc\} , T\infty \^E = \{ \^xc\} , то за умови xc \not = \^xc множини E i \^E,
очевидно, не перетинаються.
Розглянемо випадок xc = \^xc . Нехай x — довiльна точка з множини E. Оскiльки послiдов-
нiсть T kx, k = 1, 2, . . . , збiгається до точки xc, то iснує число m, яке залежить вiд x, таке, що
T 2m+1x \in \Sigma o. Тодi точка LmT 2m+1x належить множинi E. Але за лемою 3.8 LmT 2m+1x = Tx,
отже, Tx \in E. Таким чином, TE \subseteq E, тобто \^E \subseteq E. Далi, враховуючи, що T 2E = E, T 2E \subseteq TE,
маємо E \subseteq \^E. Отже, E = \^E.
Лему 3.9 доведено.
Побудуємо всю сукупнiсть компонент зв’язностi множини \Sigma при xc \not = \^xc (випадок xc = \^xc
легко зводиться до цього випадку).
З лем 3.6 – 3.9 випливає, що множини E i \^E є компонентами зв’язностi множини \Sigma . Назвемо
їх компонентами зв’язностi нульового рангу i покладемо \frakB 0 = \{ E\} , \^\frakB 0 = \{ \^E\} .
Далi, утворюємо множини Xi = T - 1
i E, i \in \{ 1, 2, . . . , n\} \setminus \{ i(2)\} , i \^Xi = T - 1
i
\^E, i \in
\in \{ 1, 2, . . . , n\} \setminus \{ i(1)\} . Оскiльки вiдображення T : Xi \rightarrow E, T : \^Xi \rightarrow \^E є iзоморфiзмами,
то цi множини також є компонентами зв’язностi множини \Sigma (вiдмiнними вiд E i \^E ). Назвемо
їх компонентами зв’язностi першого рангу i покладемо \frakB 1 =
\bigl\{
Xi, i \in \{ 1, 2, . . . , n\} \setminus \{ i(2)\}
\bigr\}
,
\^\frakB 1 =
\bigl\{
\^Xi, i \in \{ 1, 2, . . . , n\} \setminus \{ i(1)\}
\bigr\}
.
Множини \frakB 1, \^\frakB 1 мiстять по n - 1 рiзних компонент зв’язностi першого рангу. Точки цих
компонент не належать компонентам зв’язностi нульового рангу, але вiдображаються на них
оператором T .
Аналогiчно утворюємо компоненти зв’язностi другого рангу:
\frakB 2 = \{ T - 1
i X | i \in \{ 1, 2, . . . , n\} , X \in \frakB 1\} , \^\frakB 2 = \{ T - 1
i
\^X | i \in \{ 1, 2, . . . , n\} , \^X \in \^\frakB 1\} .
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
МНОЖИНА РIВНЯ АСИМПТОТИЧНОЇ ШВИДКОСТI ЗБIЖНОСТI МЕТОДУ НАЙШВИДШОГО . . . 189
Множини \frakB 2, \^\frakB 2 мiстять по (n - 1)n рiзних компонент зв’язностi другого рангу. Точки цих
компонент не належать компонентам зв’язностi першого i нульового рангiв, але вiдображаються
на них операторами T i T 2 вiдповiдно.
У загальному випадку компоненти зв’язностi k-го рангу визначаються рекурентно:
\frakB k = \{ T - 1
i X | i \in \{ 1, . . . , n\} , X \in \frakB k - 1\} , \^\frakB k = \{ T - 1
i
\^X | i \in \{ 1, . . . , n\} , \^X \in \^\frakB k - 1\} .
Множини \frakB k, \^\frakB k мiстять по (n - 1)nk - 1 рiзних компонент зв’язностi k-го рангу. Точки
цих компонент не належать компонентам зв’язностi менших рангiв, але вiдображаються на них
операторами T, T 2, . . . , T k вiдповiдно.
Позначимо через \frakB множину всiх компонент зв’язностi множини \Sigma . Оскiльки будь-яка
точка x множини \Sigma належить компонентi зв’язностi деякого рангу (тому що T kx \in E для
деякого натурального числа k), то
\frakB =
\infty \bigcup
k=0
(\frakB k \cup \^\frakB k).
Таким чином, множина \Sigma складається зi злiченної множини \frakB непорожнiх попарно непе-
ретинних компонент зв’язностi.
Теорема 3.1. Якщо c \in \Delta \ast i \Sigma \cap \partial \Sigma = \varnothing , то множина рiвня V - 1(c) має злiченне диз’юнк-
тивне розвинення:
V - 1(c) =
\bigcup
X\in \frakB
X \cup \partial \Sigma .
Доведення безпосередньо випливає з означення множини \frakB i розвинення (3.2).
Теорема 3.1 описує структуру i вказує алгоритм побудови множини V - 1(c).
Зауваження 3.2. З означення множин \frakB k випливають рiвностi T\frakB k = \frakB k - 1, T \^\frakB k =
= \^\frakB k - 1, k = 1, 2, . . . , T\frakB 0 = \^\frakB 0, T \^\frakB 0 = \frakB 0, де дiя оператора T поширена на множини
\frakB k за формулою T\{ X,Y, . . .\} = \{ TX, TY, . . .\} . Тому iтерацiйний процес методу найшвидшого
спуску можна записати у виглядi переходiв пiд дiєю оператора T :
\frakB k \rightarrowtail \frakB k - 1 \rightarrowtail \frakB k - 2 \rightarrowtail . . . \rightarrowtail \frakB 0 \rightleftarrows \^\frakB 0,
якщо початкове наближення належить компонентi зв’язностi рангу k з множини \frakB k, i у виглядi
переходiв
\^\frakB k \rightarrowtail \^\frakB k - 1 \rightarrowtail \^\frakB k - 2 \rightarrowtail . . . \rightarrowtail \^\frakB 0 \rightleftarrows \frakB 0,
якщо початкове наближення належить компонентi зв’язностi рангу k з множини \^\frakB k .
Лiтература
1. A. Cauchy, Méthode générale pour la résolution des systèmes d’équations simultanées, Comptes Rend. Hebd. Seances
Acad. Sci. Paris, 25, 536 – 538 (1847).
2. Л. В. Канторович, Функциональный анализ и прикладная математика, Успехи мат. наук, 3, № 6 (28), 89 – 185
(1948).
3. А. А. Самарский, Е. С. Николаев, Методы решения сеточных уравнений, Наука, Москва (1978).
4. J. M. Ortega, W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Acad. Press, New
York, London (1970).
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
190 П. Ф. ЖУК
5. В. В. Ермаков, Н. Н. Калиткин, Двухступенчатый градиентный спуск, Журн. вычислит. математики и мат.
физики, 20, № 4, 1040 – 1045 (1980).
6. J. Barzilai, J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141 – 148 (1988).
7. G. E. Forsythe, T. S. Motzkin, Asymptotic properties of the optimum gradient method (abstract), Bull. Amer. Math.
Soc., 57 (1951).
8. H. Akaike, On a successive transformation of probability distribution and its application to the analysis of the
optimum gradient method, Ann. Inst. Statist. Math., 11, 1 – 16 (1959).
9. И. В. Емелин, О быстроте сходимости метода наискорейшего спуска, Успехи мат. наук, 32, № 1 (193),
163 – 164 (1977).
10. П. Ф. Жук, Об асимптотических свойствах метода наискорейшего спуска в задачах на собственные значения,
Журн. вычислит. математики и мат. физики, 21, № 2, 271 – 285 (1981).
11. П. Ф. Жук, В. Г. Приказчиков, Эффективная оценка сходимости неявного итерационного метода в задачах
на собственные значения, Дифференц. уравнения, 18, № 7, 1197 – 1202 (1982).
12. П. Ф. Жук, Асимптотическая скорость сходимости метода наискорейшего спуска в задачах на собственные
значения, Журн. вычислит. математики и мат. физики, 24, № 4, 605 – 607 (1984).
13. G. Е. Forsythe, On the asymptotic directions of the s-dimensional optimum gradient method, Numer. Math., 11, № 1,
57 – 76 (1968).
14. J. Liesen, The Forsythe conjecture, XXI Householder Symp. Numer. Linear Algebra. Book Abstracts, June 14 – 19,
249 – 250 (2020).
15. А. Ф. Заболоцкая, Асимптотическое поведение s-шагового метода скорейшего спуска в гильбертовом про-
странстве, Журн. вычислит. математики и мат. физики, 19, № 1, 228 – 232 (1979).
16. П. Ф. Жук, Асимптотические свойства s-шагового метода скорейшего спуска, Журн. вычислит. математики
и мат. физики, 22, № 2, 269 – 279 (1982).
17. П. Ф. Жук, Л. Н. Бондаренко, Об одной гипотезе Дж. Форсайта, Мат. сб., 121 (163), № 4 (8), 435 – 453 (1983).
18. П. Ф. Жук, Асимптотическое поведение s-шагового метода наискорейшего спуска в задачах на собственные
значения в гильбертовом пространстве, Мат. сб., 184, № 12, 87 – 122 (1993).
19. П. Ф. Жук, Асимптотическое поведение s-шагового метода наискорейшего спуска при минимизации квадра-
тичного функционала в гильбертовом пространстве, Журн. вычислит. математики и мат. физики, 35, № 2,
163 – 177 (1995).
20. L. Pronzato, H. P. Wynn, A. Zhigljavsky, A dynamical-system analysis of the optimum s-gradient algorithm, Optimal
Design and Related Areas in Optimization and Statistics, Springer, New York (2009), p. 39 – 80.
21. L. Pronzato, A. Zhigljavsky, Gradient algorithms for quadratic optimization with fast convergence rates, Comput.
Optim. and Appl., 50, 597 – 617 (2011).
22. R. De Asmundis, D. Di Serafino, F. Riccio, G. Toraldo, On spectral properties of steepest descent methods, IMA J.
Numer. Anal., 33, № 4, 1416 – 1435 (2013).
23. Y. Huang, Y. H. Dai, X. W. Liu, H. Zhang, Gradient methods exploiting spectral properties, Optim. Methods and
Software, 35, № 4, 681 – 705 (2020).
24. K. van den Doel, U. Ascher, The chaotic nature of faster gradient descent methods, J. Sci. Comput., 51, 560 – 581
(2012).
25. Л. Н. Бондаренко, П. Ф. Жук, Комбинированные итерационные методы вариационного типа, Журн. вычислит.
математики и мат. физики, 28, № 9, 1283 – 1296 (1988).
26. П. Ф. Жук, А. А. Мусина, Асимптотическая скорость сходимости двухслойного итерационного метода
вариационного типа, Укр. мат. журн., 12, 1622 – 1635 (2013).
27. П. Ф. Жук, Область диференцiйованостi асимптотичної швидкостi збiжностi методу найшвидшого спуску,
Математичнi проблеми механiки та обчислювальної математики, 11, № 4, 102 – 110 (2014).
28. П. Ф. Жук, А. А. Мусина, Об операторе перехода метода наискорейшего спуска, Мат. моделирование, 8,
65 – 80 (2014).
29. В. С. Козякин, М. А. Красносельский, О нескольких задачах, связанных с методом минимальных невязок,
Журн. вычислит. математики и мат. физики, 19, № 2, 508 – 510 (1979).
30. В. П. Михайлов, Дифференциальные уравнения в частных производных, Наука, Москва (1976).
Одержано 21.08.21
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 2
|
| id | umjimathkievua-article-6885 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-03-24T03:30:39Z |
| publishDate | 2022 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/9f/b029a6963f5227eafd727eef5e34479f.pdf |
| spelling | umjimathkievua-article-68852025-03-31T08:45:58Z Level set of the asymptotic rate of convergence of the method of steepest descent Множество уровня асимптотической скорости сходимости метода наискорейшего спуска Множина рівня асимптотичної швидкості збіжності методу найшвидшого спуску Zhuk , P. F. Жук, Петро Федорович Жук, П. Ф. швидкість збіжності асимптотична поведінка метод найшвидшого спуску множина рівня the steepest descent method rate of convergence asymptotic behavior the set of the level UDC 519.61 The asymptotic rate of convergence of the steepest descent method is considered as a function of the initial approximation. In this work, we study the set of the level of this speed, i.e. the set of initial approximations for which it takes a given value. A method for constructing this set is proposed and its connected components are found. Асимптотическая скорость сходимости метода наискорейшего спуска рассматривается как функция от начального приближения. В данной работе изучается множество уровня этой скорости, т.е. множество начальных приближений, для которых она принимает заданное значение. Предложен способ построения этого множества и найдены его компоненты связности. УДК 519.61Асимптотична швидкiсть збiжностi методу найшвидшого спуску розглядається як функцiя вiд початкового наближення. У данiй роботi вивчається множина рiвня цiєї швидкостi, тобто множина початкових наближень, для яких вона має задане значення. Запропоновано спосiб побудови цiєї множини i знайдено її компоненти зв’язностi. Institute of Mathematics, NAS of Ukraine 2022-02-21 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/6885 10.37863/umzh.v74i2.6885 Ukrains’kyi Matematychnyi Zhurnal; Vol. 74 No. 2 (2022); 178 - 190 Український математичний журнал; Том 74 № 2 (2022); 178 - 190 1027-3190 uk https://umj.imath.kiev.ua/index.php/umj/article/view/6885/9190 Copyright (c) 2022 Петро Федорович Жук |
| spellingShingle | Zhuk , P. F. Жук, Петро Федорович Жук, П. Ф. Level set of the asymptotic rate of convergence of the method of steepest descent |
| title | Level set of the asymptotic rate of convergence of the method of steepest descent |
| title_alt | Множество уровня асимптотической скорости сходимости метода наискорейшего спуска Множина рівня асимптотичної швидкості збіжності методу найшвидшого спуску |
| title_full | Level set of the asymptotic rate of convergence of the method of steepest descent |
| title_fullStr | Level set of the asymptotic rate of convergence of the method of steepest descent |
| title_full_unstemmed | Level set of the asymptotic rate of convergence of the method of steepest descent |
| title_short | Level set of the asymptotic rate of convergence of the method of steepest descent |
| title_sort | level set of the asymptotic rate of convergence of the method of steepest descent |
| topic_facet | швидкість збіжності асимптотична поведінка метод найшвидшого спуску множина рівня the steepest descent method rate of convergence asymptotic behavior the set of the level |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/6885 |
| work_keys_str_mv | AT zhukpf levelsetoftheasymptoticrateofconvergenceofthemethodofsteepestdescent AT žukpetrofedorovič levelsetoftheasymptoticrateofconvergenceofthemethodofsteepestdescent AT žukpf levelsetoftheasymptoticrateofconvergenceofthemethodofsteepestdescent AT zhukpf množestvourovnâasimptotičeskojskorostishodimostimetodanaiskorejšegospuska AT žukpetrofedorovič množestvourovnâasimptotičeskojskorostishodimostimetodanaiskorejšegospuska AT žukpf množestvourovnâasimptotičeskojskorostishodimostimetodanaiskorejšegospuska AT zhukpf množinarívnâasimptotičnoíšvidkostízbížnostímetodunajšvidšogospusku AT žukpetrofedorovič množinarívnâasimptotičnoíšvidkostízbížnostímetodunajšvidšogospusku AT žukpf množinarívnâasimptotičnoíšvidkostízbížnostímetodunajšvidšogospusku |