Паралельне обчислення нерухомої точки циклічного оператора
Визначено поняття циклічного оператора в напівупорядкованому банаховому просторі. Цей оператор має блочну структуру і виникає при моделюванні циклічних хімічних процесів у каскадах апаратів. За певних умов циклічний оператор має нерухому точку, що моделює усталений режим роботи каскаду. Запропонован...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/38708 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Паралельне обчислення нерухомої точки циклічного оператора / П.Ф. Жук, Л.М. Бондаренко // Доп. НАН України. — 2011. — № 9. — С. 15-19. — Бібліогр.: 6 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859852554361372672 |
|---|---|
| author | Жук, П.Ф. Бондаренко, Л.М. |
| author_facet | Жук, П.Ф. Бондаренко, Л.М. |
| citation_txt | Паралельне обчислення нерухомої точки циклічного оператора / П.Ф. Жук, Л.М. Бондаренко // Доп. НАН України. — 2011. — № 9. — С. 15-19. — Бібліогр.: 6 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Визначено поняття циклічного оператора в напівупорядкованому банаховому просторі. Цей оператор має блочну структуру і виникає при моделюванні циклічних хімічних процесів у каскадах апаратів. За певних умов циклічний оператор має нерухому точку, що моделює усталений режим роботи каскаду. Запропоновано і обгрунтовано метод паралельного обчислення цієї нерухомої точки циклічного оператора.
The concept of cyclic operator is defined in a semiordered Banach space. This operator has a sectional structure and arises at the design of cyclic chemical processes in the cascades of apparatus. Under certain conditions, a cyclic operator has a fixed point which designs a withstand mode of operations of a cascade. The method of parallel computing of this fixed point of the cyclic operator is offered and grounded.
|
| first_indexed | 2025-12-07T15:42:08Z |
| format | Article |
| fulltext |
УДК 519.634
© 2011
П.Ф. Жук, Л.М. Бондаренко
Паралельне обчислення нерухомої точки цикл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снуючих
алгоритмiв з реалiзацiєю можливостей широкого паралелiзму (див., наприклад, [1]). Незва-
жаючи на те, що проблематицi паралельних обчислень присвячено значне число публiкацiй
(особливо це стосується задач лiнiйної алгебри (наприклад, [2])), питання побудови пара-
лельних алгоритмiв для систем як звичайних диференцiальних рiвнянь, так i в частинних
похiдних, а також для операторних рiвнянь, якi є математичною основою для сучасних
наукових i iнженерних задач, залишаються актуальними (див. [3, 4]).
У данiй роботi розглядається можливiсть паралельного обчислення нерухомої точки
нелiнiйного оператора спецiального вигляду, названого нами циклiчним, оскiльки оператори
такого роду виникають при математичному моделюваннi циклiчних хiмiчних процесiв [5].
1. Постановка завдання. Позначимо через E1 i E2 банаховi простори, напiвупоряд-
кованi за допомогою конусiв K1 i K2 вiдповiдно. У цих просторах зафiксуємо деякi конуснi
вiдрiзки J1 = 〈a∗, a
∗〉 ⊆ E1, J2 = 〈c∗, c
∗〉 ⊆ E2 i неперервний монотонний оператор P , що
вiдображає конусний вiдрiзок J1 × J2 простору E1 × E2 на себе.
Для визначення циклiчного оператора задамо деяке натуральне число m i розглянемо
m + 1 спiввiдношень
(a′0, c1) = P (a1, c
∗),
(a′i, ci+1) = P (ai+1, ci), i = 1, 2, . . . ,m− 1,
(a′m, cm+1) = P (a∗, cm),
(1)
послiдовне застосування яких дозволяє для будь-яких вiдомих елементiв a1, a2, . . . , am
конусного вiдрiзка J1 однозначно знайти елементи a′0, a
′
1, . . . , a
′
m конусного вiдрiзка J1 i еле-
менти c1, c2, . . . , cm+1 конусного вiдрiзка J2. Тому рiвняння
A~a = ~a′, C~a = ~c, (2)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №9 15
де вектори ~a = (a1, a2, . . . , am) ∈ Jm
1 , ~a′ = (a′1, a
′
2, . . . , a
′
m) ∈ Jm
1 , ~c = (c1, c2, . . . , cm) ∈ Jm
2 ,
задають деякi неперервнi оператори A : Jm
1 → Jm
1 , C : Jm
1 → Jm
2 . Покажемо, що цi оператори
монотоннi.
Дiйсно, нехай ~aj = (a1j , a2j , . . . , amj), j = 1, 2, — двi довiльнi точки конусного вiдрiз-
ка Jm
1 такi, що ~a1 6 ~a2. Тодi компоненти векторiв ~a′j = (a′1j , a
′
2j , . . . , a
′
mj) = A~aj , ~cj =
= (c1j , c2j , . . . , cmj) = C~aj, j = 1, 2, задовольняють нерiвностi
(a′01, c11) = P (a11, c
∗) 6 P (a12, c
∗) = (a′02, c12),
(a′i1, ci+1,1) = P (ai+1,1, ci1) 6 P (ai+1,2, ci2) = (a′i2, ci+1,2), i = 1, . . . ,m− 1,
(a′m1, cm+1,1) = P (a∗, cm1) 6 P (a∗, cm2) = (a′m2, cm+1,2),
тобто A~a1 6 A~a2, C~a1 6 C~a2, що i потрiбно було показати.
Оператор A, заданий спiввiдношенням (2), називатимемо циклiчним, якщо виконується
хоч би одна з двох умов:
1) серед множин AjJm
1 , j = 0, 1, . . ., є принаймнi одна компактна множина;
2) конус K1 правильний.
Практичне значення мають нерухомi точки циклiчного оператора. Щодо них є вiрним
твердження.
Теорема 1. Нехай A є циклiчним оператором, а ~a∗ є найменшою точкою конусного
вiдрiзка Jm
1 . Тодi iтерацiйна послiдовнiсть ~a1 = ~a∗, ~ak+1 = A~ak, k = 1, 2, . . ., монотонно
зростає i збiгається в просторi Em
1 до найменшої нерухомої точки ~a∞ оператора A.
Доведення. Оскiльки ~a1 є найменшою точкою Jm
1 , то ~a2 = A~a1 > ~a1, отже, ~ak+1 =
= A~ak > A~ak−1 = ~ak, k = 2, 3, . . ., тобто послiдовнiсть ~ak, k = 1, 2, . . ., монотонно зростає.
Але вона обмежена зверху найбiльшою точкою ~a∗ конусного вiдрiзка Jm
1 , а тому, за умо-
ви циклiчностi оператора A, збiгається в просторi Em
1 (див., наприклад, [6]), причому її
границя ~a∞ = lim
k→∞
~ak є, очевидно, нерухомою точкою оператора A.
Нехай ~a — довiльна нерухома точка оператора A. Оскiльки ~a1 6 ~a, то ~ak = Ak−1~a1 6 ~a,
k = 1, 2, . . ., отже, ~a∞ 6 ~a. Тому ~a∞ є найменшою нерухомою точкою оператора A. Теорему
доведено.
Наше завдання полягає в органiзацiї паралельного обчислення нерухомої точки ~a∞ опе-
ратора A.
2. Паралельне обчислення нерухомої точки ~a∞. Введемо поняття узагальненого
циклiчного оператора. Для цього використовуватимемо аналоги спiввiдношень (1):
(a′0, c
′
1) = P (a1, c
∗),
(a′i, c
′
i+1) = P (ai+1, ci), i = 1, 2, . . . ,m− 1,
(a′m, c′m+1) = P (a∗, cm).
(3)
Рiвнiсть (3) дозволяє для будь-яких вiдомих елементiв a1, a2, . . . , am з J1 i c1, c2, . . . , cm
з J2 однозначно знаходити елементи a′0, a
′
1, . . . , a
′
m, c′1, c
′
2, . . . , c
′
m+1. Тому iснує оператор, що
вiдображає конусний вiдрiзок Jm
1 × Jm
2 банахова простору Em
1 × Em
2 на себе за формулою
B(~a,~c) = (~a′,~c′), (4)
де компоненти векторiв ~a = (a1, a2, . . . , am) ∈ Jm
1 , ~c = (c1, c2, . . . , cm) ∈ Jm
2 , ~a′ =
= (a′1, a
′
2, . . . , a
′
m) ∈ Jm
1 , ~c′ = (c′1, c
′
2, . . . , c
′
m) ∈ Jm
2 задовольняють спiввiдношення (3).
16 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №9
Нам будуть необхiднi деякi властивостi оператора B, сформульованi у виглядi леми.
Лема 1. Нехай B — оператор, визначений рiвнiстю (4). Тодi:
1) оператор B неперервний i монотонний;
2) рiвнiсть B(~a,~c) = (A~a,~c) має мiсце тодi i тiльки тодi, коли ~a ∈ Jm
1 , ~c = C~a;
3) якщо (~a,~c) ∈ Jm
1 × Jm
2 i (~a,~c) 6 B(~a,~c), то (~a,~c) 6 (A~a,C~a) 6 Bm(~a,~c).
Доведення. Неперервнiсть оператора B випливає безпосередньо iз спiввiдношень (3)
i неперервностi оператора P . Доведемо монотоннiсть.
Вiзьмемо двi довiльнi точки (~aj,~cj) = ((a1j , a2j , . . . , amj), (c1j , c2j , . . . , cmj)), j = 1, 2, ко-
нусного вiдрiзка Jm
1 × Jm
2 такi, що (~a1,~c1) 6 (~a2,~c2). Тодi компоненти точок (~a′j ,~c
′
j) =
= ((a′1j , a
′
2j , . . . , a
′
mj), (c
′
1j , c
′
2j , . . . , c
′
mj)) = B(~aj,~cj), j = 1, 2, задовольняють спiввiдношення
(a′01, c
′
11) = P (a11, c
∗) 6 P (a12, c
∗) = (a′02, c
′
12),
(a′i1, c
′
i+1,1) = P (ai+1,1, ci1) 6 P (ai+1,2, ci2) = (a′i2, c
′
i+1,2), i = 1, 2, . . . ,m− 1,
(a′m1, c
′
m+1,1) = P (a∗, cm1) 6 P (a∗, cm2) = (a′m2, c
′
m+1,2),
тобто B(~a1,~c1) 6 B(~a2,~c2), що i потрiбно було довести.
Для доведення другого твердження зазначимо, що рiвнiсть (~a′,~c′) = B(~a,~c) = (A~a,~c)
має мiсце тодi i тiльки тодi, коли ~a ∈ Jm
1 , ~a′ = A~a, ~c′ = ~c. При цьому спiввiдношення (1),
(3) збiгаються, отже, ~c = C~a, що i потрiбно було довести.
Припустимо, нарештi, що (~a,~c) ∈ Jm
1 × Jm
2 i (~a,~c) 6 B(~a,~c). Тодi, через монотоннiсть
оператора B, послiдовнiсть Bj(~a,~c), j = 0, 1, . . ., монотонно зростає. Вважаючи, що A~a =
= (α1, α2, . . . , αm), C~a = (β1, β2, . . . , βm), Bj(~a,~c) = ((a1j , a2j , . . . , amj), (c1j , c2j , . . . , cmj)),
маємо
(a01, c1) 6 (a01, c11) = P (a1, c
∗) = (α0, β1),
(ai, ci+1) 6 (ai1, ci+1,1) = P (ai+1, ci) 6 P (ai+1, βi) = (αi, βi+1), i = 1, 2, . . . ,m− 1,
(am, cm+1,1) = (am1, cm+1,1) = P (a∗, cm) 6 P (a∗, βm) = (αm, βm+1),
тобто (~a,~c) 6 (A~a,C~a). Аналогiчно отримуємо
(α0, β1) = P (a1, c
∗) = (a01, c11),
(αi, βi+1) = P (ai+1, βi) 6 P (ai+1,i, cii) = (ai,i+1, ci+1,i+1), i = 1, 2, . . . ,m− 1,
(αm, βm+1) = P (a∗, βm) 6 P (a∗, cmm) = (amm, cm+1,m+1),
тобто (A~a,C~a) 6 Bm(~a,~c). Лему доведено.
Оператор B, заданий спiввiдношенням (4), називатимемо узагальненим циклiчним, якщо
виконується хоч би одна з двох умов:
1) серед множин Bj(Jm
1 × Jm
2 ), j = 0, 1, . . ., є принаймнi одна компактна множина;
2) конус K1 правильний, а конус K2 нормальний.
Для узагальненого циклiчного оператора має мiсце аналог теореми 1.
Теорема 2. Нехай B — циклiчний оператор, а (~a∗,~c∗) — найменша точка конусного
вiдрiзка Jm
1 × Jm
2 . Тодi iтерацiйна послiдовнiсть
(~a1,~c1) = (~a∗,~c∗), (~ak+1,~ck+1) = B(~ak,~ck), k = 1, 2, . . . , (5)
монотонно зростає i збiгається в просторi Em
1 × Em
2 до найменшої нерухомої точки
(~a∞,~c∞) оператора B, де ~a∞ — найменша нерухома точка оператора A, а ~c∞ = C~a∞.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №9 17
Рис. 1. Паралельна система для реалiзацiї оператора B
Доведення. Оскiльки (~a1,~c1) — найменша точка конусного вiдрiзка Jm
1 × Jm
2 , то, оче-
видно, (~a1,~c1) 6 B(~a1,~c1). Тому, за лемою 1, послiдовнiсть (~ak,~ck), k = 1, 2, . . . , монотонно
зростає, обмежена зверху найбiльшою точкою (~a∗,~c∗) конусного вiдрiзка Jm
1 × Jm
2 i мають
мiсце оцiнки
(~ajm+1,~cjm+1) 6 (A~ajm+1, C~ajm+1) 6 (~a(j+1)m+1,~c(j+1)m+1), j = 0, 1, . . . . (6)
Покажемо, що послiдовнiсть (~ak,~ck), k = 1, 2, . . . , збiгається в просторi Em
1 ×Em
2 . Дiйсно,
у разi коли певна множина Bj(Jm
1 ×Jm
2 ), j = 0, 1, . . . , компактна, це безпосередньо випливає
з монотонностi i обмеженостi послiдовностi (~ak,~ck), k = 1, 2, . . . (див., наприклад, [6]).
У другому можливому випадку конус K1 є правильний, а тому послiдовнiсть ~ak, k =
= 1, 2, . . ., збiгається. Але тодi з нерiвностей (6) i нормальностi конуса K2 випливає збiжнiсть
послiдовностi ~ck, k = 1, 2, . . ..
Таким чином, iснує границя (~a,~c) = lim
k→∞
(~ak,~ck). Оскiльки оператор B неперервний, то
(~a,~c) — його нерухома точка. Бiльш того, з оцiнок (6) випливає, що ~a — нерухома точка
оператора A i ~c = C~a. Залишається показати, що ~a = ~a∞.
Дiйсно, за лемою 1, B(~a∞, C~a∞) = (A~a∞, C~a∞) = (~a∞, C~a∞), тобто (~a∞, C~a∞) — неру-
хома точка оператора B. Тому (~a,~c) 6 (~a∞, C~a∞), ~a 6 ~a∞. Але, за теоремою 1, ~a > ~a∞,
отже, ~a = ~a∞. Теорему доведено.
Зауваження. Фактично доведено, що iтерацiйна послiдовнiсть (~ak,~ck), k = 1, 2, . . . , мо-
нотонно зростає i збiгається до (~a∞,~c∞) у просторi Em
1 × Em
2 при будь-якому початковому
наближеннi (~a1,~c1) такому, що ~a1 6 ~a∞, (~a1,~c1) 6 B(~a1,~c1).
Теорема 2 дозволяє знаходити найменшу нерухому точку ~a∞ циклiчного оператора A
за допомогою iтерацiйної послiдовностi (5), тобто шляхом послiдовного застосування уза-
гальненого циклiчного оператора B.
Оператор B допускає чисельну реалiзацiю на паралельнiй системi у виглядi лiнiйного
масиву m + 1 процесорiв з локальною пам’яттю, зображеного на рис. 1.
Для обчислення компонент векторiв (~a′,~c′) = B(~a,~c) у локальнiй пам’ятi процесора
P1 розмiщується iнформацiя про елементи a1, c
∗; у локальнiй пам’ятi процесора Pi, i =
= 2, 3, . . . ,m, — iнформацiя про елементи ai, ci−1; у Pm+1 — про елементи a∗, cm. Алгоритм
обчислення компонент векторiв (~a′,~c′) на данiй паралельнiй системi складається з двох
етапiв.
На першому етапi реалiзуються спiввiдношення (3): на процесорi P1 обчислюються еле-
менти a′0, c
′
1; на процесорi Pi, i = 2, 3, . . . ,m, — елементи a′i−1, c
′
i; на Pm+1 — елементи
a′m, c′m+1. На другому етапi вiдбувається обмiн iнформацiєю в системi: у локальну пам’ять
процесора P1 надходить з локальної пам’ятi процесора P2 iнформацiя про елемент a′1; у ло-
кальну пам’ять процесора Pi, i = 2, 3, . . . ,m, надходить iнформацiя про елемент c′i−1 з Pi−1
та iнформацiя про елемент a′i з Pi+1; у пам’ять процесора Pm+1 надходить iнформацiя про
елемент c′m. Обмiн iнформацiєю мiж процесорами Pi−1, Pi, Pi+1 схематично показаний на
рис. 2.
Тут позначено (ai−1, ci−2), (ai, ci−1), (ai+1, ci) — початковi данi, а (a′i−2, c
′
i−1), (a
′
i−1, c
′
i),
(a′i, c
′
i+1) — результати роботи процесорiв Pi−1, Pi, Pi+1 на першому етапi.
18 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №9
Рис. 2. Схема взаємодiї процесора Pi iз сусiднiми процесорами Pi−1, Pi+1
Як перший, так i другий етапи обчислення векторiв (~a′,~c′) можуть бути здiйсненi для
всiх процесорiв паралельної системи одночасно. Тим самим досягається максимальний сту-
пiнь паралелiзму.
1. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. – Санкт-Петербург: БХВ-Петербург,
2002. – 608 с.
2. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. – Москва:
Мир, 1991. – 368 с.
3. Воеводин В.В. Вычислительная математика и структура алгоритмов. – Москва: Изд-во Моск. ун-та,
2006. – 112 с.
4. Ильин В.П. Параллельные алгоритмы для больших прикладных задач: проблемы и технологии //
Автометрия. – 2007. – 43, № 2. – С. 3–21.
5. Жук П.Ф., Бондаренко Л.Н. Асимптотическое поведение решения нелинейной математической мо-
дели каскада последовательно соединенных сорбционных аппаратов // Журн. вычисл. математики
и мат. физики. – 2004. – 44, № 7. – С. 1306–1313.
6. Красносельский М.А. Положительные решения операторных уравнений. – Москва: Физматгиз, 1962. –
394 с.
Надiйшло до редакцiї 26.11.2010Iнститут iнформацiйно-дiагностичних систем
Нацiонального авiацiйного унiверситету, Київ
P.F. Zhuk, L. M. Bondarenko
The parallel computing of the fixed point of a cyclic operator
The concept of cyclic operator is defined in a semiordered Banach space. This operator has a
sectional structure and arises at the design of cyclic chemical processes in the cascades of apparatus.
Under certain conditions, a cyclic operator has a fixed point which designs a withstand mode of
operations of a cascade. The method of parallel computing of this fixed point of the cyclic operator
is offered and grounded.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №9 19
|
| id | nasplib_isofts_kiev_ua-123456789-38708 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:42:08Z |
| publishDate | 2011 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Жук, П.Ф. Бондаренко, Л.М. 2012-11-19T16:33:11Z 2012-11-19T16:33:11Z 2011 Паралельне обчислення нерухомої точки циклічного оператора / П.Ф. Жук, Л.М. Бондаренко // Доп. НАН України. — 2011. — № 9. — С. 15-19. — Бібліогр.: 6 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/38708 519.634 Визначено поняття циклічного оператора в напівупорядкованому банаховому просторі. Цей оператор має блочну структуру і виникає при моделюванні циклічних хімічних процесів у каскадах апаратів. За певних умов циклічний оператор має нерухому точку, що моделює усталений режим роботи каскаду. Запропоновано і обгрунтовано метод паралельного обчислення цієї нерухомої точки циклічного оператора. The concept of cyclic operator is defined in a semiordered Banach space. This operator has a sectional structure and arises at the design of cyclic chemical processes in the cascades of apparatus. Under certain conditions, a cyclic operator has a fixed point which designs a withstand mode of operations of a cascade. The method of parallel computing of this fixed point of the cyclic operator is offered and grounded. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Паралельне обчислення нерухомої точки циклічного оператора The parallel computing of the fixed point of a cyclic operator Article published earlier |
| spellingShingle | Паралельне обчислення нерухомої точки циклічного оператора Жук, П.Ф. Бондаренко, Л.М. Математика |
| title | Паралельне обчислення нерухомої точки циклічного оператора |
| title_alt | The parallel computing of the fixed point of a cyclic operator |
| title_full | Паралельне обчислення нерухомої точки циклічного оператора |
| title_fullStr | Паралельне обчислення нерухомої точки циклічного оператора |
| title_full_unstemmed | Паралельне обчислення нерухомої точки циклічного оператора |
| title_short | Паралельне обчислення нерухомої точки циклічного оператора |
| title_sort | паралельне обчислення нерухомої точки циклічного оператора |
| topic | Математика |
| topic_facet | Математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/38708 |
| work_keys_str_mv | AT žukpf paralelʹneobčislennâneruhomoítočkiciklíčnogooperatora AT bondarenkolm paralelʹneobčislennâneruhomoítočkiciklíčnogooperatora AT žukpf theparallelcomputingofthefixedpointofacyclicoperator AT bondarenkolm theparallelcomputingofthefixedpointofacyclicoperator |