Условия примитивности нелинейного оператора шага некоторых итерационных процессов в терминах матриц

Математическое моделирование динамики природно-экономических систем нередко приводит к итерационным процессам [1]. Если оператор перехода от предыдущего состояния к следующему линеен, то он задается т.н. проекционной матрицей [2]; для нелинейных моделей оператор перехода от состояния к состоянию задается некоторым отображением F е | r + ^ R + } .

Рассматриваемые далее модели являются аналитическими (качественными), поскольку имеют целью (в отличие от имитационных моделей) не воспроизведение во всех подробностях поведения моделируемого объекта, а отражение лишь на качественном уровне важнейших его свойств, хотя, следует отметить, конкретные их реализации возникли в процессе моделирования реальных природных систем.

Таким образом, имеется некоторый итерационный процесс xt+i = F(xt) , t = 0,1,2,... (1)

Подробные характеристики отображения F (называемого оператором шага итерационного процесса) неизвестны, но, тем не менее, известны некоторые его качественные свойства. Одним из таких свойств является неотрицательность:

F ( R I ) c R I (2)

Обычно будет предполагаться, что нуль О пространства R q является неподвижной точкой отображения F , которой соответствует тривиальное состояние равновесия системы:

F (О) = О .

Нас интересуют асимптотические свойства итерационного процесса (1). Определяющим здесь оказывается, как мы увидим дальше, наличие или отсутствие ненулевых неподвижных точек отображения F , которые будем называть нетривиальными состояниями равновесия системы.

Далее предполагается также, что оператор шага является возрастающим на R I :

V x, y G R I : x <  y ^ F ( x ) <  F ( у ) (3) и псевдовогнутым в соответствии со следующим определением.

О п р е д е л е н и е 1. Отображение F G { R I ^ R I } называется псевдовогну-тым , если

Vx G RI Va G (0,1) F (ax) > aF (x) (4)

Псевдовогнутость является требованием к скорости возрастания и позволяет, в частности, отражать так называемый ”эффект насыщения”, наблюдающийся во многих реальных системах с дефицитом ресурса. Понятие псевдовогнутости в работе [3] определяется с помощью строгого неравенства в (4); мы здесь такие отображения будем называть строго псевдовогнутыми .

Как известно [4], положительно однородное первой степени отображение имеет доминирующее собственное значение, которое определяет динамические свойства соответствующего итерационного процесса (при некоторых дополнительных предположениях). В работе [5] показано, что сходимость итерационного процесса (1) с псевдовогнутым возрастающим оператором шага определяется доминирующими собственными значениями некоторых отобра- жений F0, F^, которые можно поставить в соответствие каждому псевдовогнутому отображению.

Теорема 1 [5]. Если отображение F псев-довогнуто, то существуют положительно однородные первой степени отображен и я F o ⁽ x ) = ( f ⁽ x ⁾ ) , F ⁽ x ⁾ = (£ ⁽ x ⁾ ) , удовлетворяющие условию

V x G RI F (x) ^ F (x) ^ Fo (x) (5)

Отображение F _M всюду на R I конечно. Если отображение F возрастает, то каждая компонента отображения F _o либо всюду на R _I ^q конечна, либо всюду на int R I есть +.

Если отображение F к тому же сепарабельно, то F (x) = Fx, где F = I ,j I, s s s I s I f^,j = Jim?s a 1 fi,j (a) (i, j G 1, q, s G {o, I ^})

Напомним, что отображение F G { R I ^ R I } называется сепарабельным , если

q

V x G RI F (x ) = £ F( xj), Fj( xj ) = (fi,j (xj) ) j=1

Для положительно-однородного первой степени отображения H существует обобщение понятия собственного числа для матриц [2], и, в частности, существует т.н. доминирующее собственное число А ( H ) .

Условия существования положительного равновесия возрастающего монотонно возрастающего псевдовогнутого отображения оказывается возможным сформулировать [5-8] в терминах доминирующих собственных значений положительно-однородных первой степени отображений F_o , F ^ .

В частности, достаточным для существования положительного равновесия является условие

^А ( F J< ¹<  А ( F ) ,

(при дополнительных условиях примитивности отображения F на некотором множестве, гарантирующих положительность ненулевого состояния равновесия).

При этих условиях итерационный процесс (1) сходится к некоторому равновес-

Смирнов А.И.

ному состоянию, зависящему от выбора начального приближения x ₀ . Если состояние равновесия единственное, то имеется сходимость к нему независимо от ненулевого начального приближения.

При отсутствии нетривиального равновесия итерационный процесс (1) сходится к тривиальному состоянию равновесия.

Таким образом, при ограниченности отображения F для рассматриваемого итерационного процесса справедлива следующая альтернатива: имеет место сходимость либо к положительному состоянию равновесия, либо к нулевому.

Далее везде на протяжении этой статьи отображение F ( x ) = ( f ( x ) ) предполагается возрастающим ( F ( О ) = О ) , псевдовог-нутым и сепарабельным на R ‘ .

Замечание . Будем предполагать в дальнейшем та кже, что

Vг G 1q 3 x G R9+ : fi (x) > 0 (7)

Для псевдовогнутого возрастающего отображения в этом случае справедливо соотношение

F ( int R ) c int R (8)

При изучении существования состояния равновесия отображения F предполагалось выполнение условия примитивности на некотором множестве, содержащем нулевой вектор О . В общем случае проверка этого условия довольно затруднительна.

Тем не менее, для сепарабельного отображения удается свести анализ примитивности к соответствующему анализу (значительно более простому и конструктивному) для некоторой матрицы.

Теорема 2 [6] . Если отображение F псевдовогнуто и отображение F 0 конечно, то отображение F примитивно в точке _x = О тогда и только тогда, когда отображение F 0 примитивно в точке _x = о •

Далее, псевдовогнутое сепарабельное отображение F примитивно в точке _x = О тогда и только тогда, когда некоторая степень матрицы A F = [ a Fj ] положительна, где « F, = f i,₃ ( 1 ) ( V i , j G 1, q ) .

Используя этот результат, найдем усло-

вия примитивности соответствующих мат-

риц для некоторых часто встречающихся модификаций итерационного процесса (1).

2. Структура оператора шага некоторых

разновидностей итерационного процесса (1)

Рассмотрим итерационный процесс вида

^X 1    = ^f . ( ^X 1 , x 2 ,•••, x q - 1 , x q ) ,

x 2   = ^f 2 ( ^X 1   , x 2 ,•••, x q - 1 , x q ) ,

x- q ^{+ 1} = f q ( x t ^{, 1}. x 2 G., x q ч. x- q ) ,

Очев и дно, оператор шага

F ( x ) = ( ft ( x ) ) для этого процесса опреде-

ляется следующим образом:

f 1 ( x ) = f ( x_p x ₂

x q - 1, x q ) ,

^f 2 ( x ) = ^f 2 ( ^f 1 ( x ) , ^X 2 ^,•••^, x q - 1, x q ) ,

> (10)

^fq ⁽ x ) = ^fq ( ^f 1 ⁽ x ) , ^f 2 ⁽ x ) ^,•••^{, f}q - 1 ⁽ x ) , x q )

Отображение _F также является возрастающим ( F ( О ) = О ) псевдовогнутым и, хот я не является сепарабельным, но является суперпозицией сепарабельных отображений.

Элементы матрицы A _F можно задать индуктивно:

a Fj , i = 1, j g 1, q ,

F a i , j

i -1        _

F F X a.xakj ,

k = 1

t e 2, q , j g 1, t - 1,

t-1        _         _____ ____ aFj + X aFkak,j, t e 2, q, j e t, q.

k = 1

Теорема 3 . Матрица A _F неразложима тогда и только тогда, когда неразложима матрица ^j

A f и X a - -, j >  0 ( ^V j e 1, q - 1 ) .

t =1

Д о к а з а т е л ь с т в о. Необходимость. Из равенст в (11) видно, что, есл и a ,^Fj = 0 ( v t e 1, j ) при некотором j _e 1, q - 1 , то матрица A _F разложима как имеющая нулевой столбец.

Если разложима матрица A_F , то суще-

ствует такое множество I , 0 ^ I с 1, q , что af, j = 0 ( V i ^е J , j ^е I , J = 1, q \ I ) . Индукцией по множеству J _х I покажем, что матрица A _F разложима.

Пусть i1 = min J, j1 = min I. Если i1 = 1, то af. = af. = 0 . Если i > 1, то j = 1 и i1 , j1           i1 , j1                                       1                              1

af_; = 0, так как 1 i - 1 c I . Таким обра- i ₁ , j ₁                                                   1

зом, af _к = 0 .

Предположим, что af,i = ° (Vie J, j eI: i ^ r, j ^ s, i + j < r + s) где r e J, s e I, и покажем, что afs = 0 . Если 1, r - 1 c I, то ar,s = 0 в силу равенства afk при k e I. Если же I' = 1, r -1\I / 0 , то

F V' F F ar,s = E ar,kak,s k e I'

Так как max I' „ r - 1, k e J , то, по предп о ложению индукции, в этой сумме все a f _s = 0, и, следовательно, a f _s = 0, что и требовалось.

Д о с т а т о ч н о с т ь. Пусть матрица A _F разложима и I - то множество, о котором идет речь в определении разложимости. Если | l | = 1, то из (11) нетрудно заметить, что a ij = 0 ( V i £ I , j e I ) .

Предположим, что это равенство справедливо при всех i , для которых | l | < I . Пусть | l | = I , I = { i 1 ,..., i _t } .

Если aij = 0 (Vi £ I, j e I) , то заключе- ние теоремы справедливо.

Если af _jo ^ 0 при некоторых i₀ £ I , j ₀ e I , то из (11) следует, что J' 0 e i, i f- 1 и a^iF₁,i = 0 (^V j e I ) .

Поэтому a_z ^f _j = 0 ( V i £ I ', j e I ') , где I ' = I \ { j ₀ } и, по предположению индукции, матрица A_F разложима. Теорема доказана.

Точно так же может быть доказана следующая

Теорема 4. Матрица A_H , где H - оператор шага итерационного процесса

^ Г¹ = f ( x t ,

x 2 ^t

x q - 1 , x q ) ,

x 2 ^{+ 1} = f - ( x t * ¹ , x 2

x q - 1 , x q ) * g 2,1 ( x t ) ,

^ (12)

x q * 1 = f, ( x t * 1 , x ; * ' ,..., x q *- 1 , x q ) + £ g , „ ( x t ) .

.j = 1

неразложима тогда и только тогда, когда jq

E a f + £ a f >  0 ( V j e 1, q - 1 )      (13)

i = 1            i = j * 1

и неразложима матрица

A F * G , ^G ( x ) = ( g i ( x ) ) , g i ( x ) = E g i , j ( x j ) j = 1

Учитывая, что неразложимая матрица, имеющая положительный диагональный элемент, примитивна [4], получаем

Следствие 1. Матрица AF примитивна тогда и только тогда, когда матрица AF jF неразложима и E a-,j > 0 (Vj e 1,q - 1).

i = 1

Таким образом, проверка примитивности оператора шага итерационного процесса (9) сводится к проверке неразложимости матрицы A_F и существования ненулевого элемента на главной диагонали или выше во всех столбцах, кроме последнего (существование такого элемента в последнем столбце вытекает из неразложимости матрицы A_F ).

Рассмотрим теперь случай, когда компоненты xt+1 (j e p +1, q ) вектора xt+1 не зависят явно от координат вектора xt и полностью определяются значениями осталь- ных координат вектора .

Пусть p e1, q -1 и для итерационного процесса (9) выполнено условие afj = 0 (Vi e p +1, q, j e i, q)         (14)

Тогда итерационный процесс (1) сводится к итерационному процессу меньшей размерности p :

y_t * 1 = H ( y t ) , t = 0,1,2,...,              (15)

где yt = xt (1, p) и отображение H(У) = (hi(У)) (H e{R +p ^R +p}) опреде- ляется равенствами

Смирнов А.И.

У1, У 2 ,..., У р - 1 , У р , f p + 1 ⁽ У ⁾ ,..., fq ⁽ У ⁾ ) , h l ⁽ У ⁾ , У 2 ,...,У_Р - 1 , У р , f p + 1 ⁽ У ⁾ ,..., f q ⁽ У ⁾ ) ,

h p ⁽ У ⁾ = f p ( h ⁽ У ⁾ , h 2⁽ У ),..., h p - 1⁽ У ), У р , f p + 1 ⁽ У ⁾ ,..., f q ⁽ У ⁾ ) , где

fp+1 (У) = fp+1 (У1, У2,...,Уp, 0, 0,..., 0, 0),

fp+2 (У) = fp+2 (У1, У2,...,Уp, fp+1 (У), 0,..., 0, 0), г ( X г I                      г / X г / X г / X гА

fq (У) fq (У1, У 2,..., Уp , fp+1 (У) , fp+2 (y) ,•", fq-1 (y), 0).

В соответствии с теоремой 2, для нахождения условий неразложимости матрицы AH , элементы которой задаются равенствами aiHj

H a kj

aFj+ S aF aHJ, i = 1, J e1, p, к=p+1

i - 1                        q

• ■ S a F a H j ⁺ S a F a H j , i ^{e 2}, p , ^{J e 1,} i - 1,

к=i              к=p+i i-1                  q                           _______ ______ s

( ai,J + S ai,kak,J S ai,kak,J, i e 2, p, J ei, q, к=1          к=p+1

aF j , к = p +1, J e1, p, к-1                     ____________ _____ aF j + E aF aHj ,к e p+2, q,J e 1 p, e=p+1

необходимо найти условия неразложимости матрицы AG =[aGz ] (i, J G1, p) для отображения G ( у ) = (gi ( у )), где g.(У )= f, (У1,..., yp, ^fp+1(У),..., ^fq(У)) (vi Gl, p)

Эта матрица имеет элементы

q

G F     FF aij= a,j+ S a,каки, (i, J e1, p)    (18)

к = p + 1

Введем понятие главной подматрицы квадратной матрицы.

О п р е д е л е н и е 2.

Главной подматрицей A (I) (I c 1, q) матрицы A = [ai,J ] (i, J G1, q) называется матрица, получающаяся из матрицы A вычерчиванием строк и столбцов с номерами из 1,q\I .

Теорема 5 . Пусть выполнено условие qq

S a F, ■ >  0 ( v i e p + 1, q ) , S a F, ■ >  0 ( ^V J e p + 1, q ) ⁽¹⁹⁾

J = 1                                        i = 1

Тогда матрица A_G неразложима тогда и только тогда, когда неразложима матрица A_F .

Д о к а з а т е л ь с т в о.

Н е о б х о д и м о с т ь. Пусть матрица A_F разложима. Тогда существует множество 1 , 0 ^ I c 1, q , удовлетворяющее условию a' F,_J = 0 ( v i e J = 1, q \ I , J e I ) .

Покажем, что I q i^ p ^0 , j q i^ p ^0 .

Действительно, если, например,

I Q 1, p = 0 , то J ^ 1, p и

aF/ = 0 (v i e1, p, j e I). Пусть J0 = max I. Тогда j0 +1, q c J и a'F, j0 = 0 (vie j0 + 1, q). Так как, согласно (14), aF/o = 0 (vi e p +1, j0), то aF/o = 0 (vi e 1, q), что противоречит на- шим предположениям.

Итак, I Q 1, p *0 , J Q 1, p *0 . Пусть I ' = 1, p Q I , J ' = 1, p Q J . Покажем, что a^G_/ = 0 ( v i e J ', j e I ') .

Действительно, имеем aF. = 0 (vie J', j e I *) .

Из (18) получаем:

a G = E a F ^aL , (^V i ^e J', ^{j e} I ' ) , где k e J о

J ₀ = p + 1, q П J ^.

Пусть k ₀ = min J 0 ( k ₀ . . p + 1 ).

Если k0 > p +1, то aL = aL = 0 (Vj e I') - Если k0 = P + 1, то учитывая соотношения p +1, k0 -1 с I, aF,l = 0 (VI e p +1, k0 -1), опять получаем at (jI')-

Таким образом, если J ₀| = 1, то a kj = 0 ( V j e I ', k e J ₀ ) . Если же | J ₀| >  1, то последнее равенство доказывается индукцией по множеству J ₀ . Отсюда ^ai , j = E ^ai , k^ak , j = ^{0 (V} i ^{e J} , ^{j e} I ) и матрица X 0 разложима-

Д о с т а т о ч н о с т ь. Пусть матрица AG разложима. Тогда aGj = 0 (Vi e J, j e I) 0 / I c 1, q, J = 1, p \ I

Из равенств (18) получаем

j 0 (V i e J, j e I), .

a^F_ka k,j = 0 ( V k e p + 1, q , i e J, j e I ) (20)

Нам необходимо построить множество I , удовлетворяющее условию

0^ I cA?q , a i = 0 ( V i Е J = 1 q \ ⁷ , j Е I ) (21)

Мы получим это множество в виде некоторого элемента I_t последовательности множеств

• 1 1 = I U I t , I t с I 'U K ( V t e 0, 7 0 ) , где

I ' = { k ^e p + ^1, q : a Fk = 0 (^{V i e} J ) , 3 j ^e I a Fj >  0 } , J ' = { k e p + 1, q : a^F_k j = 0 ( V j e I ) , 3 i e J a^F_k >  0 } , K = { k e p + 1, q : a^F k = a^F_k j = 0 ( V i e J , j e I ) } .

Положим I ₀ = I ' U K и, предположив, что множество I_t построено, но множество

I_t не удовлетворяет условию (21), построим множество I_{t + 1} .

Заметим, что из определения множества

I_t и равенств (20) вытекает, что

V i Е J_t = 1, q \ I t , j Е I ) , a Fj = 0 ( V i Е J, j Е It )                  (22)

Поэтому условие (21) при I = 1₁ может быть невыполненным только тогда, когда существуют i ₀ e J_t, j ₀ e I_t , для которых a^F_jo ^ 0. Так как главная подматрица A_F ( p + 1, q ) матрицы A_F имеет нули на главной диагонали и выше, то i₀ >  j ₀ (и, следовательно, i₀ >  p + 1). Так как i 0 e J t с J 'U K , то a^F , j = 0 ( V j e I ) .

Используя (18), получаем равенства a iF, _t a Fj = 0 ( V j e I , ^ e p + 1, i ₀ - 1 ) . Отсюда ^aF,j = ^{0 (V j e} I ) и можно положить I t . 1 = I t \ { j 0 } -

Итак, в результате мы получаем последовательность множеств { I t } 0 0 , причем при 1 ₀ >  0 справедливо \l _{t + 1}| = | I_t | - 1 ( V t e 0, 1 ₀ - 1 ) -

Очевидно, 1 ₀ „| I ₀| . Если 1 ₀< | I ₀| , то построено множество I t , для которого I_t ^ 0 . Если же 1 ₀ = | I ₀| , то после 1 ₀ - кратного повторения указанной процедуры получаем I_t = 0 , I t = I . Это множество удовлетворяет (21) в силу условия (22).

Вернемся к рассмотрению итерационного процесса (15). Условие (13) для отображения (16) преобразуется в следующее:

j     pq

E ^a ^⁺ E E ^aF ^aFj > ⁰ ( ^{V j e 1,} p ^- 1 ) (23) i = 1              i = 1 k = p + 1

Лемма 1 . Если столбцы матрицы A_F с номерами p+1,…, q - ненулевые, то условие (23) эквивалентно условию jq

E aid ⁺ E ^aF • >  ⁰ ( ^{V j e 1}, p ^{- 1} )     (24)

i = 1             i = p + 1

Смирнов А.И.

Д о к а з а т е л ь с т в о. Если a Fi = 0 ( v i € 1, j U p + 1, q ) при некотором j _€ 1, p - 1 , то, очевидно, справедливо отрицание условия (23).

Обратно, если условие (23) не выполнено, то при некотором справедливо

Обратно, если условие (23) не выполнено, то при некотором j _€ 1, p - 1 справедливо

^F i , j

F

= 0 ( v i € 1, j ) ,

F

a i , k a k , j

= 0 ( v k € p + 1, q , i € 1, p ) .

V r € k , q - 1: a’ Fr = 0 ( v i € 1, p ) , 3 a € r + 1, q : a F , r >  0 ^ a ^ = 0 ( V i € 1, p ) (26)

Применяя утверждение (26) последовательно для r = k , k + 1,..., q - 1 , получаем, что столбец с номером q - нулевой, что противоречит нашим предп оложениям. Поэтому a F _j = 0 ( v k € p + 1, q ) и справедливо отрицание условия (24). Лемма доказана.

Компиляцией теорем 3, 5 и леммы 1 является следующая

Теорема 6 . Пусть выполнены условия (14),(19). Тогда матрица A_H неразложима

Поэтому для завершения доказательства достаточно показать, что a F _j = 0 ( v k € p + 1, q ) .

Предположим противное: пусть a’F _j >  0 при некотором k _€ p + 1, q . Тогда в силу (25) справедливы равенства a Fk = 0 ( v i € 1, p ) (и тем самым k <  q , так как в противном случае столбец с номером q , согласно (14), является нулевым).

Заметим, что из (25) вытекает справедливость следующего утверждения:

тогда и только тогда, когда выполнено условие (24) и матрица A_F неразложима.

Таким образом, проверка неразложимости матрицы оператора шага итерационного процесса (15), т.е. итерационного процесса (9) с условием (14), сводится к проверке неразложимости матрицы A_F и проверке существования ненулевого элемента этой матрицы на главной диагонали или выше, либо ниже q –ой строки в каждом столбце матрицы , кроме последнего