Asymptotic Rate of Convergence of a Two-Layer Iterative Method of the Variational Type
We present the definition and study the dependence on the initial approximation of the asymptotic rate of convergence of a two-layer symmetrizable iterative method of the variational type. The explicit expression is obtained for the substantial (with respect to the Lebesgue measure) range of its val...
Збережено в:
| Дата: | 2013 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська Англійська |
| Опубліковано: |
Institute of Mathematics, NAS of Ukraine
2013
|
| Онлайн доступ: | https://umj.imath.kiev.ua/index.php/umj/article/view/2541 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Репозитарії
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860508459835850752 |
|---|---|
| author | Zhuk, P. F. Musina, A. A. Жук, П. Ф. Мусина, А. А. Жук, П. Ф. Мусина, А. А. |
| author_facet | Zhuk, P. F. Musina, A. A. Жук, П. Ф. Мусина, А. А. Жук, П. Ф. Мусина, А. А. |
| author_sort | Zhuk, P. F. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:26:06Z |
| description | We present the definition and study the dependence on the initial approximation of the asymptotic rate of convergence of a two-layer symmetrizable iterative method of the variational type. The explicit expression is obtained for the substantial (with respect to the Lebesgue measure) range of its values. Its domain of continuity is described. |
| first_indexed | 2026-03-24T02:25:33Z |
| format | Article |
| fulltext |
© П. Ф. ЖУК, А. А. МУСИНА, 2013
1622 ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
УДК 519.61
П. Ф. Жук, А. А. Мусина (Нац. авиац. ун-т)
АСИМПТОТИЧЕСКАЯ СКОРОСТЬ СХОДИМОСТИ
ДВУХСЛОЙНОГО ИТЕРАЦИОННОГО МЕТОДА
ВАРИАЦИОННОГО ТИПА
We present the definition and study the dependence on the initial approximation of the asymptotic rate of convergence of a
two-layer symmetrizable iterative method of the variational type. The explicit expression is obtained for the substantial
(with respect to the Lebesgue measure) range of its values. Its domain of continuity is described.
Наведено визначення і досліджено залежність від початкового наближення асимптотичної швидкості збіжності
двошарового симетризовного ітераційного методу варіаційного типу. Знайдено явний вираз істотної (за мірою
Лебега) області її значень. Охарактеризовано її область неперервності.
Введение. Итерационные методы вариационного типа являются известными и весьма эффек-
тивными методами решения операторных уравнений и минимизации функционалов. Опера-
торы переходов таких методов нелинейные, так как их итерационные параметры не постоянны,
а выбираются на каждой итерации из условия минимума некоторого функционала.
Нелинейное поведение итерационных методов вариационного типа обуславливает сущест-
венную зависимость характеристик их сходимости от начального приближения. Интерес к
этой зависимости в настоящее время возрастает (см., например, [1 – 5]), однако прогресс в
этой области в значительной степени ограничен сложностью задачи через ее нелинейность
(так, несмотря на многочисленные публикации, посвященные известному методу Barzilai –
Borwein [6], скорость сходимости этого метода математически строго удалось изучить только
в простейшем двумерном случае).
В данной работе рассматривается двухслойный симметризуемый итерационный метод ва-
риационного типа (сокращенно: двухслойный метод) решения линейных операторных уравне-
ний и минимизации квадратичных функционалов. Этот метод включает такие известные мето-
ды, как методы наискорейшего спуска, минимальных невязок, минимальных погрешностей,
минимальных поправок. Его асимптотическое свойство (см. [7]) позволяет естественным об-
разом определить асимптотическую скорость сходимости как функцию от начального прибли-
жения. Эта функция и является предметом исследования данной статьи.
В п. 1 дано определение двухслойного метода и его асимптотической скорости сходимости.
Оператор перехода и асимптотическая скорость сходимости метода затем преобразованы к
более удобному для изучения виду на стандартном симплексе в пространстве Rn . Сформули-
рована задача исследования — определить существенную область значений и область непре-
рывности асимптотической скорости сходимости метода.
В п. 2 показано, что хотя асимптотическая скорость сходимости метода может принимать
бесконечные значения, ее существенная (по мере Лебега) область значений ограничена. Ука-
зано явное выражение этой области значений.
Поскольку при наличии ошибок округлений реальное поведение итерационного метода ва-
риационного типа может существенно отличаться от теоретического (типичным примером яв-
ляется метод сопряженных градиентов), в п. 3 асимптотическая скорость сходимости двух-
слойного метода изучается на непрерывность как функция от начального приближения. Оха-
АСИМПТОТИЧЕСКАЯ СКОРОСТЬ СХОДИМОСТИ ДВУХСЛОЙНОГО ИТЕРАЦИОННОГО МЕТОДА … 1623
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
рактеризованы множества точек непрерывности и разрыва этой функции. Показано, что если
начальное приближение является точкой разрыва асимптотической скорости сходимости, то
соответствующая итерационная последовательность „вырождается”. Из этого факта, в част-
ности, следует, что лебегова мера множества точек разрыва асимптотической скорости схо-
димости равна 0. Таким образом, в п. 3 показано, что асимптотическая скорость сходимости
двухслойного метода почти всюду (по мере Лебега) непрерывна как функция от начального
приближения.
Перспективными в данном направлении исследований являются такие задачи:
1) охарактеризовать область дифференцируемости асимптотической скорости сходимости;
2) определить структуру множества начальных приближений с заданным значением асимп-
тотической скорости сходимости;
3) установить, существуют ли значения асимптотической скорости сходимости, для кото-
рых мера Лебега указанного в задаче 2 множества отлична от 0.
1. Постановка задачи. Пусть E — конечномерное действительное евклидово прост-
ранство со скалярным произведением (u, v) и нормой u = (u, u) . Обозначим через A ,
B , D линейные невырожденные операторы, действующие в пространстве E . Относительно
них предполагаем, что:
1) оператор D самосопряжен и положительно определен в E ;
2) оператор B!1A самосопряжен и положительно определен в энергетическом простран-
стве Ep (т. е. имеет место самосопряженный, в смысле Самарского [7], случай);
3) спектр оператора B!1A состоит только из простых собственных значений (это пред-
положение не принципиально, но упрощает формулировку результатов).
Двухслойный метод решения операторного уравнения
Au = f , (1.1)
или, что то же самое, минимизации квадратичного функционала u ! u* D
2
, задается схемой
[7]
B u
(k+1) ! u(k )
"k+1
+ Au(k ) = f , k = 0,1,… , (1.2)
где u(0) — произвольное начальное приближение, итерационный параметр !k+1 выбирается
из условия минимума погрешности z k+1( ) = u k+1( ) ! u* в энергетическом пространстве Ep
и равен
!k+1 =
(B"1Az(k ), z(k ) )D
B"1Az(k ) D
2 . (1.3)
Здесь u* — точное решение уравнения (1.1), а z k( ) = u k( ) ! u* .
Асимптотическое свойство двухслойного метода состоит в следующем (см. [7]): если
1624 П. Ф. ЖУК, А. А. МУСИНА
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
z 1( ) = u 1( ) ! u* " 0 , то и z k( ) = u k( ) ! u* " 0 , k = 0,1 , …, и последовательность !!k (u
(0) ) =
= z(k+1) D / z
(k )
D монотонно убывает.
Поскольку (см. [7]) последовательность !!k (u
(0) ) , k = 0,1 , … , ограничена сверху вели-
чиной 1! "
1+ "
, где ! =
"1
" 2
, а !1 , ! 2 — границы спектра оператора B!1A , существует пре-
дел !!" (u0 ) = limk#" !!k (u(0) ) , зависящий, вообще говоря, от начального приближения u 0( ) .
Под асимптотической скоростью сходимости двухслойного метода будем понимать сле-
дующую функцию начального приближения u 0( ) :
!!(u 0( )) =
", esly z 1( ) = 0,
# ln !$" (u 0( )), esly z 1( ) % 0.
&
'
(
)(
(1.4)
Представим функцию !! в виде суперпозиции более простых функций. Из свойств опе-
раторов A , B , D следует, что оператор C = D0,5B!1AD0,5 самосопряжен и положитель-
но определен, а поэтому существует оператор C0,5 . Замена w k( ) = C0,5D0,5z k( ) позволяет
перейти от неявной схемы (1.2) двухслойного метода к явной схеме
w k+1( ) = w k( ) ! "k+1Cw k( ) , k = 0,1 , … , (1.5)
причем из формулы (1.3) следует, что
!k+1 =
w k( ) 2
(Cw k( ),w k( ))
(1.6)
(отметим, что w k( ) — последовательность невязок метода наискорейшего спуска, применен-
ного к уравнению Cu = 0 с начальным приближением u(0) = C!1w(0) ).
Рассмотрим последовательность
!!k (w(0) ) = w k+1( )
C"1 / w k( )
C"1 . Поскольку
w(k ) C!1 = z(k ) D , !!k (w
(0) ) = "!k (u(0) ) и существует предел !!" (w
(0) ) = limk#" !!k (w(0) ) ,
равный !!" (u
(0) ) . Следовательно,
!v(u
(0) ) = "v(w(0) ) , (1.7)
где
!v(w(0) ) =
!, esly w(1) = 0,
" ln !#! (w(0) ), esly w(1) $ 0.
%
&
'
('
(1.8)
Преобразуем функцию !v . Пусть ei , i = 1, 2,… , n + 1{ } — ортонормированная система
АСИМПТОТИЧЕСКАЯ СКОРОСТЬ СХОДИМОСТИ ДВУХСЛОЙНОГО ИТЕРАЦИОННОГО МЕТОДА … 1625
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
собственных векторов оператора С. Выбрав их в качестве базиса, отождествим пространство
E с арифметическим пространством Rn+1 . Обозначим через
S = x = (x1, ..., xn ) xi ! 1
i=1
n
" , xi # 0, i = 1, 2,…, n
$
%
&
'&
(
)
&
*&
стандартный симплекс пространства Rn и рассмотрим отображение ! : Rn+1 \ 0{ }" S , за-
данное формулой xi = wi2 / wj
2
j=1
n+1! , i = 1,…, n .
Сужение !+ этого отображения на множестве единичных векторов с неотрицательными
компонентами
!+ = w = (w1, ...,wn+1) wj
2 = 1, wj " 0, j = 1,…, n + 1
j=1
n+1
#
$
%
&
'&
(
)
&
*&
есть биекция, поэтому на S определена функция v(x) = !v(!+
"1(x)) . Поскольку !v(w) =
= v(!(w)) для w !Rn+1 \ {0} , из равенства (1.7) следует, что
!v(u
(0) ) = v(!(C0,5D0,5 (u(0) " u*)) . (1.9)
Таким образом, исследование функции !v сводится к изучению функции v , которая и
является основным предметом исследования данной работы. Эта функция v может быть оп-
ределена, как и функции !v и !v , с помощью некоторого итерационного процесса.
Обозначим через S1 = (1, 0,…, 0) , S2 = (0,1, 0,…, 0),…, Sn = (0,…, 0,1) , Sn+1 = (0,…, 0)
вершины симплекса S , а через S! = S \ {S1,…, Sn+1} симплекс S без вершин. Пусть
!1 <…< !n+1 — собственные значения оператора C (предполагается, что оператор B!1A ,
а следовательно, и оператор C обладают только простыми собственными значениями).
Определим отображение T : S! " S! по формуле x̂ = Tx , где x = (x1,…, xn ) , xn+1 =
= 1! x1 !…! xn , µ(x) = !i xii=1
n+1" , !(x) = (µ(x) " #i )2 xii=1
n+1$ , x̂i = (µ(x) ! "i )2 xi /#(x) ,
i = 1,…, n , x̂ = (x̂1,…, x̂n ) . Расширим, далее, отображение T на S , положив Tx = Si ,
если x = Si , i = 1, 2,…, n + 1 , и Tx = x̂ , если x !S" .
Итерационный процесс x(k+1) = Tx(k ) , k = 0,1 , … , тесно связан с итерационным процес-
сом (1.5), (1.6), а именно, если x(0) = !(w(0) ) "S# , то
x(k ) = !(w(k ) ), k = 1, 2,… , (1.10)
поэтому последовательность
!k (x(0) ) = "i#1(1# "i /µ(x(k ) ))2 xi
(k ) / "i#1xi
(k )
i=1
n+1
$
i=1
n+1
$
1626 П. Ф. ЖУК, А. А. МУСИНА
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
совпадает при x(0) = !(w(0) ) "S# с последовательностью !k (w(0) ) . Но тогда существует
предел !" (x(0) ) = limk#" !k (x(0) ) и
v(x(0) ) =
!, esly x(0) "S# ,
$ ln %! (x(0) ), esly x(0) &S# .
'
(
)
*)
(1.11)
Таким образом, функция v задается формулой, подобной формулам (1.4), (1.8). Для ее
изучения воспользуемся результатами исследования асимптотического поведения метода
наискорейшего спуска, проведенного в работе [8].
Пусть 1 ! i1 <…< im ! n + 1 . Обозначим через Si1…im грань симплекса S с вершинами
Si1 ,… , Sim , через
Si1…im = x x = !1Si1 +…+ !mSim , ! p > 0, p = 1,…,m, ! p = 1
p=1
m
"
#
$
%
&%
'
(
%
)%
внутренность этой грани, через S = S1,…, n+1 внутренность симплекса S , а через !S = S \ S
границу симплекса S . Из определения отображения T следует, что TSi1…im ! Si1…im и,
кроме того, неподвижные точки отображения T 2 образуют множество
Sij1!i< j!n+1! .
Из соотношения (1.10) и результатов работы [8] вытекает такое свойство отображения T :
если x !Si1...im , то последовательности {T 2k x, k = 0,1,…} , {T 2k+1x, k = 0,1,…} сходятся
и их пределы являются неподвижными точками отображения T 2 :
x! = lim
k"!
T 2k x #Si1im , x̂! = lim
k"!
T 2k+1x = Tx! #Si1im . (1.12)
Таким образом, если обозначить T !x = limk"! T 2k x , то из соотношений (1.12) следует,
что на множестве S! определены функции ! , i , j такие, что для любого x !S" имеют
место равенства
x! = T !x = "(x)Si(x) + (1# "(x))S j(x) , x̂! = Tx! = (1" #(x))Si(x) + #(x)S j(x) , (1.13)
где 0 < !(x) < 1 , 1 ! i(x) < j(x) ! n + 1 . Кроме того, если определить на S! функцию ! :
!(x) = "i#1(1# "i /µ(x))2 xi / "i#1xi
i=1
n+1
$
i=1
n+1
$ ,
где xn+1 = 1! x1 !…! xn , µ(x) = !i xii=1
n+1" , то из монотонности последовательности
!k (x(0) ) и соотношений (1.13) следует, что
АСИМПТОТИЧЕСКАЯ СКОРОСТЬ СХОДИМОСТИ ДВУХСЛОЙНОГО ИТЕРАЦИОННОГО МЕТОДА … 1627
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
!(x) " !(Tx) "… " !(T kx) "… #
k#$
!$ (x) = !(x$ ) = !(Tx$ ) ,
!" (x) = # (x)/ # 2 (x) + $i(x)$ j(x) !x "S# , (1.14)
где ! (x) = (" j(x) # "i(x) ) $(x)(1# $(x)) . В частности, v(x) = v(T kx) = v(x! ) !k = 1, 2,… .
Наиболее простое выражение функция v имеет при n = 1 . В этом случае S = [0,1] ,
S1 = 1 , S2 = 0 , S! =]0,1[ . Предположим, что x = x1 !S" . Тогда x̂ = Tx = 1! x , Tx̂ = x ,
поэтому x! = x , !(x) = x , i(x) = 1 , j(x) = 2 . Из соотношений (1.11), (1.14) получаем
!" (x) = !(x) = (#2 $ #1) x(1$ x) / (#2 $ #1)2 x(1$ x) + #1#2 ,
v(x) =
!, esly x "{0,1},
# ln $(x), esly x "]0,1[.
%
&
'
('
(1.15)
Из формул (1.14) несложно также найти minS v(x) . Действительно, поскольку
max
S!
" (x) = (#n+1 $ #1) max%&]0,1[
%(1$ %) =
#n+1 $ #1
2
и достигается при x* = (0, 5; 0;…) !S1,n+1 , существуют
max
S!
"# (x) = "max =
$n+1 % $1
$n+1 + $1
, min
S
v(x) = vmin = ! ln "max (1.16)
и также достигаются в точке x* .
В общем случае, при n ! 2 , функция v имеет сложный нелинейный характер и полу-
чить для нее аналитическое выражение не удается. В данной статье рассмотрены следующие
две задачи:
1) определить существенную (относительно меры Лебега) область значений функции v ;
2) охарактеризовать область непрерывности функции v .
Полученные результаты с помощью соотношения (1.9) естественным образом переносятся
на асимптотическую скорость сходимости метода !v .
2. Существенная область значений асимптотической скорости. Здесь и в дальнейшем
будем предполагать, что
mini=2,… ,n (!1 + !n+1)/2 " !i достигается лишь на одном индексе i
(который обозначим через i0 ) и ! " !i0 # (!1 + !n+1)/2 (это предположение не ограничи-
вает общность результатов, но упрощает запись).
Обозначим ! = "1"n+1 /("("1 + "n+1 # ")) , !max = ("n+1 # "1)/("n+1 + "1) , vmin =
= ! ln "max , !min = (1" # ) / (1+ # ) , vmax = ! ln "min , ! = [vmin, vmax[ , ! = [vmin, vmax ] .
Пусть x — произвольная точка симплекса S . Рассмотрим итерационную последователь-
1628 П. Ф. ЖУК, А. А. МУСИНА
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
ность x(k ) = (x1k ,…, xnk ) = T kx , k = 0,1,… . Будем говорить, что i -я компонента точки x
не вырождается, если для каждого конечного k = 0,1,… имеем xik > 0 .
Обозначим через I (x) совокупность индексов невырождающихся компонент (кроме 1),
т. е. I (x) = {i i > 1, xik > 0 !k = 0,1, ...} . Нам потребуются также множества
S* = {x !S 0 < x1, x1 +…+ xn < 1} , S* = S \ S* ,
Ui = {x !S* i ! I (x)} , i = 2, 3,…, n .
Очевидно, что
S ! S* ! S , S* ! "S , TS* = S* , TS* = S* , T !S* = S1,n+1 . (2.1)
Кроме того, обозначим
U = Uii=2
n! , V = S \U . Множество U состоит из точек симп–
лекса, у которых нет вырождающихся компонент. Множество V , напротив, состоит из то-
чек симплекса, которые имеют хотя бы одну вырождающуюся компоненту. Из определения
отображения T следует, что
V = Vik
i=1
n+1
!
k=0
!
! , (2.2)
где Vi0 , i = 1, 2,… , n , — множество точек симплекса, у которых i -я компонента равна 0,
V(n+1)0 — множество точек, у которых xn+1 = 1! x1 !…! xn = 0 , а множество Vik с k > 0
состоит из точек x , для которых T k!1x "U , но xik = 0 .
Обозначим через ! меру Лебега на Rn .
Лемма 2.1. Если n ! 1 , то !(V ) = 0 .
Доказательство. Из определения отображения T следует, что множество Vik являет-
ся подмножеством множества !ik нулей некоторого многочлена Pik (x1,…, xn ) /! 0 от n
переменных. Используя теорему Фубини, имеем !("ik ) = 0 , поэтому !(Vik ) " !(#ik ) = 0 .
Утверждение леммы вытекает теперь из разложения (2.2).
Лемма доказана.
Следствие 2.1. Множество U всюду плотно в симплексе S .
Введем следующие обозначения:
µk (x) = µ(x(k ) ) , µ! (x) = µ(x! ) , µ̂! (x) = µ(Tx! ) ,
!ik (x) = (1" #i /µk+1(x))(1" #i µk (x))
0,5 , !i" (x) = (1# $i /µ̂" (x))(1# $i /µ" (x))
0,5 ,
qik (x) = !ik (x)/!1k (x) , i = 1,…, n .
Из соотношений (1.12), (1.14) следует, что для любых x !S* и i ! I (x)
АСИМПТОТИЧЕСКАЯ СКОРОСТЬ СХОДИМОСТИ ДВУХСЛОЙНОГО ИТЕРАЦИОННОГО МЕТОДА … 1629
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
!i" (x) # !1" (x) = !" (x) , (2.3)
qi,2k (x)
k=0
m
! " 0 при m! " . (2.4)
Кроме того, из (2.1) следует, что имеет место равенство
µ! (x) + µ̂! (x) = "1 + "n+1 !x "S* . (2.5)
Из (2.3), (2.5) следует, что выполняются неравенства
!i0 ," (x) # !1" (x) , !i" (x) < !1" (x) !x "Ui0 , i ! 2, n
_____
\ {i0} , (2.6)
причем для любого x !S* неравенства !i0 ," (x) < !1" (x) , !i0 ," (x) # !1" (x) имеют место
тогда и только тогда, когда v(x) !" , v(x) !" соответственно, т. е.
!i0 ," (x) < !1" (x) ~ v(x) #$ , !i0 ," (x) # !1" (x) ~ v(x) $% , (2.7)
где ~ — знак эквивалентности.
Определим множества M = {x !S* v(x) !"} , M = {x !S* v(x) !"} .
Лемма 2.2. Если n ! 2 , то имеют место включения U ! Ui0 ! M .
Доказательство следует непосредственно из соотношений (2.6), (2.7).
Множество M характеризуется тем, что множество T ! (M ) состоит из точек притяже-
ния. А именно, справедлива следующая лемма.
Лемма 2.3. Если x принадлежит M , то для любой сколь угодно малой окрестности
O1(x! ) точки x! = T !x существуют окрестность O2 (x! ) этой же точки и число q <
< 1 такие, что для любых k = 0,1,… и y !O2 (x" ) имеют место T 2k y !O1(x" ) ,
h(T 2k y) ! y2,2k + y3,2k +…+ yn,2k " qk (под окрестностью O(x) точки x !S понимаем
ее окрестность в топологии симплекса S ).
Доказательство. Положим !i (y) = (1" #i /µ(Ty))(1" #i /µ(y))
0,5 , i = 1,…, n . По усло-
вию x !M , следовательно, V (x) !" и в силу (2.7) !i0 ," (x) < !1" (x) . Но тогда из (2.6)
вытекает, что !i," (x) < !1" (x) , i = 2, 3,…, n . Поскольку !i," (x) = !i (x" ) , то
!i (x" ) < !1(x" ) , i = 2, 3,…, n . (2.8)
Отображение T непрерывно в точке x! , поэтому в x! непрерывны функции !i (y) ,
i = 1,…, n . Из (2.8) следует существование окрестности O(x! ) и чисел m > 0 , q < 1 та-
ких, что имеют место неравенства
1630 П. Ф. ЖУК, А. А. МУСИНА
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
h(T 2y) ! qh(y) , T 2y ! y " mh(y) !y "O(x# ) . (2.9)
Без ограничения общности можно считать, что O1(x! ) " O(#, x! ) $ O(x! ) . Положим
! = "(1# q)/(nm + 1) . Из оценок (2.9) следует, что число q и окрестность O2 (x! ) "
! O(", x# ) удовлетворяют условиям леммы.
Лемма доказана.
Следствие 2.2. Если x принадлежит M , то для любых сколь угодно малых окрест-
ностей O1(x! ) и O(Tx! ) соответственно точек x! и Tx! существует окрестность
O2 (x! ) такая, что T
kO2 (x! ) " O1(x! )!O(Tx! ) , k = 0,1,… .
Лемма 2.4. Если n ! 2 , то множество M является открытым в топологии симп-
лекса S .
Доказательство. Пусть x принадлежит M . Тогда и x! = T !x принадлежит M .
Запишем точку x! в координатной форме: x! = (x1! , 0,…, 0) . Аналогично (1.15) получаем
v(x! ) = " ln #(x1! ) , (2.10)
!(x1" ) = (#n+1 $ #1) x1" (1$ x1" ) / (#n+1 $ #1)2 x1" (1$ x1" ) + #1#n+1 .
Поскольку x! принадлежит M , из равенства (2.10) вытекает существование ! > 0 тако-
го, что точка (x1! + t, 0,…, 0) "M при t < ! . Положим O1(x! ) " O(#, x! ) . В силу леммы
2.3 существует окрестность O2 (x! ) такая, что T
!O2 (x! ) " O1(x! )! S1,n+1 " M . Следова-
тельно, O2 (x! ) " M .
Поскольку T 2k x! x" при k ! " , для некоторого числа m !{0,1,…} имеет место
соотношение x(2m) = T 2mx !O2 (x" ) . Так как оператор T 2m непрерывен на множестве S! ,
для некоторой окрестности O(x) точки x верно включение T 2mO(x) ! O2 (x" ) . Но тогда
T 2mO(x) ! M , следовательно, O(x) ! M .
Лемма доказана.
Основным результатом данного пункта является следующая теорема.
Теорема 2.1. Если n ! 2 , то
vraimin
S
v(x) = vmin ,
vraimax
S
v(x) = vmax , а ! — су-
щественная область значений функции v на S .
Доказательство. Покажем сначала, что
vraimin
S
v(x) = vmin . Для этого достаточно ус-
тановить, что !(X(vmin )) = 0 и !(X(")) > 0 !" > vmin , где X(!) = {x "S | v(x) < !} , а
! — мера Лебега на Rn .
Действительно, в силу (1.16) имеем min
S
v(x) = vmin , следовательно, X(vmin ) = ! и
АСИМПТОТИЧЕСКАЯ СКОРОСТЬ СХОДИМОСТИ ДВУХСЛОЙНОГО ИТЕРАЦИОННОГО МЕТОДА … 1631
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
!(X(vmin )) = 0 . Далее, положим v0 (x) = ! ln "(x) , X0 (!) = x "S v0 (x) < !{ } . Поскольку
!(x) " !# (x) , то X0 (!) " X(!) . При ! > vmin получаем !(X0 (")) > 0 , следовательно,
!(X(")) > 0 , что и требовалось установить.
Покажем теперь, что
vraimax
S
v(x) = vmax . Для этого достаточно установить, что
!(X(vmax )) = 0 и !(X(")) > 0 !" < vmax , где X(!) = {x "S v(x) > !} .
Действительно, если x принадлежит X(vmax ) , то v(x) > vmax , следовательно, v(x) !
!" и x !M . Но тогда из леммы 2.2 вытекает, что x !U , т. е. x !V — вырождающаяся
точка. В силу леммы 2.1 !(V ) = 0 , следовательно, и !(X(vmax )) = 0 .
Предположим, наконец, что ! < vmax . Тогда существует отрезок [x, y] ! S1,n+1 такой,
что v([x, y]) !]", vmax[ (т. е. [x, y] ! X(")! M ). Положим x! = (x + y)/2 и выберем ок-
рестность O1(x! ) точки x! из условия O1(x
! )! S1,n+1 " [x, y] . В силу леммы 2.3 сущест-
вует окрестность O2 (x! ) точки x! такая, что T
!O2 (x! ) " O1(x! )! S1,n+1 , следователь-
но, T !O2 (x! ) " [x, y] " X(#) . Но тогда O2 (x! ) " X(#) и !(X(")) > 0 .
Теорема доказана.
Следствие 2.3. Существенной (по мере Лебега) областью значений асимптотической
скорости сходимости !v двухслойного метода является ! .
3. Область непрерывности асимптотической скорости. Обозначим через N множест-
во точек симплекса S , в которых функция v непрерывна, а через P = S \ N множество ее
точек разрыва.
Лемма 3.1. Если n ! 2 , то M ! N .
Доказательство. Предположим, что x принадлежит M . Покажем, что отображение
T ! непрерывно в точке x , тогда в x , очевидно, непрерывна и функция v .
Выберем произвольную окрестность O1(x! ) точки x! = T !x . В силу леммы 2.3 су-
ществует окрестность O2 (x! ) такая, что
T !O2 (x! ) " O1(x! ) . (3.1)
Поскольку T 2k x! x" при k ! " , для некоторого m !{0,1,…} имеем x(2m) =
= T 2mx !O2 (x" ) . В силу непрерывности оператора T 2m на S! существует окрестность
O(x) такая, что T 2mO(x) ! O2 (x" ) . Но тогда из (3.1) следует, что T !O(x) "O1(x! ) .
Лемма доказана.
Обозначим !2k (x) = µ" (x) # µ2k (x) , !2k+1(x) = µ2k+1(x) " µ̂# (x) , k = 0,1,… .
Лемма 3.2. Если n ! 2 , x принадлежит Ui0 и
!1" (x) = !i0 ," (x) , (3.2)
то существует номер
!k(x) такой, что
! !k(x)(x) > ! !k(x)+1(x) > ! !k(x)+2 (x) >…" 0 .
1632 П. Ф. ЖУК, А. А. МУСИНА
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
Доказательство. Обозначим xn+1,k = 1! x1k !…! xnk , µk = µk (x) , !k = !k (x) , µ =
= µ! (x) , µ̂ = µ̂! (x) , hk = hk (x) = xiki=2
n! , !k = !k (x) " #i xik /hki=2
n$ , k = 1, 2,… . Так
как x1k + xn+1,k = 1! hk , !1x1k + !n+1xn+1,k = µk " #khk , то
x1k = (!n+1 " µk " hk (!n+1 " #k ))/(!n+1 " !1) ,
(3.3)
xn+1,k = (µk ! "1 ! hk (#k ! "1))/("n+1 ! "1) .
Рассмотрим функцию
Yk (t) = (!i " t)(!i " µk )2 xik
i=1
n+1
# , !1 " t " !n+1 .
Выразив x1k и xn+1,k через правые части (3.3), запишем Yk (t) в виде Yk (t) =
= Yk
(p)(t)p=1
4! , где
Yk
(1)(t) = (!1 " t)(!1 " µk )2
!n+1 " µk
!n+1 " !1
+ (!n+1 " t)(!n+1 " µk )2
µk " !1
!n+1 " !1
,
Yk
(2)(t) = (! " t)(! " µk )2 xi0k ,
Yk
(3)(t) = (t ! "1)("1 ! µk )2hk
"n+1 ! #k
"n+1 ! "1
+ (t ! "n+1)("n+1 ! µk )2hk
#k ! "1
"n+1 ! "1
,
Yk
(4)(t) = (!i " t)(!i " µk )2 xik
i=2, i#i0
n
$
и ! = !i0 . Предположим, для определенности, что µ < µ̂ , и выберем непересекающиеся ок-
рестности O(µ) , O(!) , O(µ̂) так, чтобы !1 + !n+1 " ! #O(µ̂) . Это всегда возможно, так
как ! " (!1 + !n+1)/2 , а в силу (2.5) имеет место равенство µ + µ̂ = !1 + !n+1 , следователь-
но, µ < ! " !1 + !n+1 # ! < µ̂ .
Поскольку x принадлежит Ui0 , из условия (3.2) следует существование такого четного
числа
!k = !k(x) , что для любого k ! !k имеют место соотношения
µk !
O(µ), esly k—çetnoe,
O(µ̂), esly k—neçetnoe,
"
#
$
%$
!k "O(#) ,
АСИМПТОТИЧЕСКАЯ СКОРОСТЬ СХОДИМОСТИ ДВУХСЛОЙНОГО ИТЕРАЦИОННОГО МЕТОДА … 1633
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
sign (Yk
(2)(t) + Yk
(4)(t)) = signYk
(2)(t) !t "O(µ)!O(µ̂) ,
Yk
(3)(!1) < Yk
(1)(!1) .
Тогда при k ! !k получаем равенство
sign (Yk
(3)(!1 + !n+1 " µk )) = sign 1" (!n+1 " µk )(#k " !1)
(µk " !1)(!n+1 " #k )
$
%&
'
()
=
"1, µk *O(µ),
1, µk *O(µ̂).
+
,
-
.-
Покажем, что ! !k > ! !k+1 . Действительно, µ !k+1 является единственным корнем уравне-
ния Y !k (t) = 0 . Поскольку
Y !k
(1)(!1 + !n+1 " µ !k ) = 0 ,
Y !k
(2)(!1 + !n+1 " µ !k ) < 0 ,
Y !k
(3)(!1 +
+ !n+1 " µ !k ) < 0 , то Y !k (!1 + !n+1 " µ !k ) < 0 . Учитывая, что Y !k (!1) > 0 и µ + µ̂ =
= !1 + !n+1 , имеем µ !k+1 < !1 + !n+1 " µ !k , т. е. ! !k+1 < ! !k . Аналогично получаем Y !k+1(!1 +
+ !n+1 " µ !k+1) > 0 , Y !k+1(!1) > 0 , следовательно, µ !k+2 > !1 + !n+1 " µ !k+1 , т. е ! !k+2 < ! !k+1
и т. д.
Лемма доказана.
Лемма 3.3. Если n ! 2 , то Ui0 ! M .
Доказательство. Предположим противное, т. е. Ui0 ! M . Так как в силу леммы 2.2
Ui0 ! M , то существует точка x !Ui0 , для которой v(x) = vmax . Для этой точки выпол-
нено равенство (3.2) (см. соотношения (2.7)).
Опустим x и обозначим µ = µ! (x) , µ̂ = µ̂! (x) (для определенности предполагаем, что
µ < µ̂ ). В силу леммы 3.2 начиная с некоторого номера !k имеют место равенства
µ2k = µ ! "2k , µ2k+1 = µ̂ + !2k+1 , (3.4)
где !2 !k > !2 !k+1 > !2 !k+2…" 0 .
Рассмотрим !1,2k2 и !
i0 ,2k
2 . Выражая µ2k , µ2k+1 из (3.4), имеем
!1,2k2 = !1,"2 + #2k+1
$1(µ % $1)
µ̂2µ
% #2k
$1(µ̂ % $1)
µ̂µ2
+ &1,2k#2k2 ,
(3.5)
!
i0 ,2k
2 = !
i0 ,"
2 + #2k+1
$($ % µ)
µ̂2µ
+ #2k
$(µ̂ % $)
µ̂µ2
+ &i0 ,2k#2k
2 ,
где ! = !i0 , а величины !1,2k , !i0 ,2k равномерно ограничены по k . Поскольку µ < ! <
< µ̂ и µ + µ̂ = !1 + !n+1 , из (3.2), (3.4), (3.5) следует, что при достаточно больших k
1634 П. Ф. ЖУК, А. А. МУСИНА
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
!1,2k " !1,# = !i0 ,# " !i0 ,2k , а поэтому произведение qi0 ,2k (x)k=0
m! не сходится к нулю при
m! " , что противоречит свойству (2.4).
Лемма доказана.
Основным результатом данного пункта является следующая теорема.
Теорема 3.1. Если n ! 2 , то U ! M ! N ! M , P ! V , а функция v почти всюду
(по мере Лебега) непрерывна на симплексе S .
Доказательство. Из лемм 3.1, 3.3 следует, что U ! M ! N . Покажем, что N ! M .
Действительно, пусть x принадлежит S* . Если x !{S1,…, Sn+1} , то, очевидно, x
принадлежит P ; в противном случае T !x "S1,n+1 . Поскольку S* всюду плотно в S , в
любой окрестности точки x существует y !S* . В силу (2.1) T !y "S1,n+1 , следовательно,
отображение T ! претерпевает разрыв в точке x и x принадлежит P . Таким образом,
S* ! P и N ! S* .
Предположим теперь, что существует x , принадлежащее N \ M . Тогда v(x) !" и
существует окрестность O числа v(x) , не пересекающаяся с ! . Поскольку множество U
всюду плотно в S (следствие леммы 2.1), в любой окрестности точки x существует y !U .
Но U ! M , следовательно, v(y) !" , т. е. v(y) !O . Поэтому x принадлежит P , что
противоречит предположению x !N \ M . Таким образом, N ! M .
Для доказательства того, что P ! V , заметим, что U ! N , следовательно, P =
= S \ N ! S \U = V .
Наконец, в силу леммы 2.1, !(V ) = 0 , поэтому !(P) = 0 , т. е. функция v почти всюду
(по мере Лебега) непрерывна на симплексе S .
Теорема доказана.
Следствие 3.1. Асимптотическая скорость сходимости !v двухслойного метода почти
всюду (по мере Лебега) непрерывна.
Замечание 3.1. Из теоремы 3.1 вытекает следующее, по мнению авторов, интересное
утверждение: если x — точка разрыва функции v , то итерационная последовательность
{T kx, k = 0,1,…} принадлежит, за исключением конечного числа начальных членов, неко-
торой грани симплекса S .
Замечание 3.2. Теорема 3.1 характеризует область непрерывности функции v с точ-
ностью до множества R = M \ M . Можно показать, что:
1) R ! V , !(R) = 0 ;
2) если на множестве R ! S1,n+1 (состоящем из двух точек) функция v непрерывна, то
она непрерывна на всем множестве R ;
3) функция v не дифференцируема на R .
1. Fletcher R. A limited memory steepest descent method // Math. Program. A. – 2012. – 135. – P. 413 – 436.
2. Roberta de Asmundis, Daniela di Serafino, Filippo Riccio, Gerardo Toraldo. On spectral properties of steepest de-
scent methods // Optim. Methods and Software for Inverse Problems. – 2012. – P. 1 – 20.
АСИМПТОТИЧЕСКАЯ СКОРОСТЬ СХОДИМОСТИ ДВУХСЛОЙНОГО ИТЕРАЦИОННОГО МЕТОДА … 1635
ISSN 1027-3190. Укр. мат. журн., 2013, т. 65, № 12
3. Kees van den Doel, Uri Ascher. The chaotic nature of faster gradient descent methods. – Univ. British Columbia,
Canada. – 2011. – P. 1 – 27.
4. Narushima Y., Wakamatsu T., Yabe H. Extended Barzilai – Borwein method for unconstrained minimization prob-
lems // Pacif. J. Optim. – 2010. – 6, № 3. – P. 591 – 613.
5. Andretta M., Birgin E. G., Martinez J. M. Partial spectral projected gradient method with active-set strategy for line-
arly constrained optimization // Numer. Algorithms. – 2010. – 53. – P. 23 – 52.
6. Barzilai J., Borwein J. M. Two-point step size gradient methods // IMA J. Numer. Anal. – 1988. – 8. – P. 141 – 148.
7. Самарский А. А., Николаев Е. С. Методы решения сеточных уравнений. – М.: Наука, 1978. – 592 c.
8. Akaike H. On a successive transformation of probability distribution and its application to the analysis of the optimum
gradient method // Ann. Inst. Statist. Math. Tokyo. – 1959. – 11. – P. 1 – 16.
Получено 11.02.13
|
| id | umjimathkievua-article-2541 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | rus English |
| last_indexed | 2026-03-24T02:25:33Z |
| publishDate | 2013 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/ef/f0cd277974fb0f6251303c7ae2701eef.pdf |
| spelling | umjimathkievua-article-25412020-03-18T19:26:06Z Asymptotic Rate of Convergence of a Two-Layer Iterative Method of the Variational Type Асимптотическая скорость сходимости двухслойного итерационного метода вариационного типа Zhuk, P. F. Musina, A. A. Жук, П. Ф. Мусина, А. А. Жук, П. Ф. Мусина, А. А. We present the definition and study the dependence on the initial approximation of the asymptotic rate of convergence of a two-layer symmetrizable iterative method of the variational type. The explicit expression is obtained for the substantial (with respect to the Lebesgue measure) range of its values. Its domain of continuity is described. Наведено визначення і досліджено залежність від початкового наближення асимптотичної швидкості збіжності двошарового симетризовного ітераційного методу варіаційного типу. Знайдено явний вираз істотної (за мірою Лебега) області її значень. Охарактеризовано її область неперервності. Institute of Mathematics, NAS of Ukraine 2013-12-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/2541 Ukrains’kyi Matematychnyi Zhurnal; Vol. 65 No. 12 (2013); 1622–1635 Український математичний журнал; Том 65 № 12 (2013); 1622–1635 1027-3190 rus en https://umj.imath.kiev.ua/index.php/umj/article/view/2541/1842 https://umj.imath.kiev.ua/index.php/umj/article/view/2541/1843 Copyright (c) 2013 Zhuk P. F.; Musina A. A. |
| spellingShingle | Zhuk, P. F. Musina, A. A. Жук, П. Ф. Мусина, А. А. Жук, П. Ф. Мусина, А. А. Asymptotic Rate of Convergence of a Two-Layer Iterative Method of the Variational Type |
| title | Asymptotic Rate of Convergence of a Two-Layer Iterative Method of the Variational Type |
| title_alt | Асимптотическая скорость сходимости двухслойного итерационного метода вариационного типа |
| title_full | Asymptotic Rate of Convergence of a Two-Layer Iterative Method of the Variational Type |
| title_fullStr | Asymptotic Rate of Convergence of a Two-Layer Iterative Method of the Variational Type |
| title_full_unstemmed | Asymptotic Rate of Convergence of a Two-Layer Iterative Method of the Variational Type |
| title_short | Asymptotic Rate of Convergence of a Two-Layer Iterative Method of the Variational Type |
| title_sort | asymptotic rate of convergence of a two-layer iterative method of the variational type |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/2541 |
| work_keys_str_mv | AT zhukpf asymptoticrateofconvergenceofatwolayeriterativemethodofthevariationaltype AT musinaaa asymptoticrateofconvergenceofatwolayeriterativemethodofthevariationaltype AT žukpf asymptoticrateofconvergenceofatwolayeriterativemethodofthevariationaltype AT musinaaa asymptoticrateofconvergenceofatwolayeriterativemethodofthevariationaltype AT žukpf asymptoticrateofconvergenceofatwolayeriterativemethodofthevariationaltype AT musinaaa asymptoticrateofconvergenceofatwolayeriterativemethodofthevariationaltype AT zhukpf asimptotičeskaâskorostʹshodimostidvuhslojnogoiteracionnogometodavariacionnogotipa AT musinaaa asimptotičeskaâskorostʹshodimostidvuhslojnogoiteracionnogometodavariacionnogotipa AT žukpf asimptotičeskaâskorostʹshodimostidvuhslojnogoiteracionnogometodavariacionnogotipa AT musinaaa asimptotičeskaâskorostʹshodimostidvuhslojnogoiteracionnogometodavariacionnogotipa AT žukpf asimptotičeskaâskorostʹshodimostidvuhslojnogoiteracionnogometodavariacionnogotipa AT musinaaa asimptotičeskaâskorostʹshodimostidvuhslojnogoiteracionnogometodavariacionnogotipa |