Методи вилучення невідомих за допомогою операцій проектування
In the paper the connection between operation of projection and methods of elimination of unknowns is investigated. Separately, considered is a method of sequential elimination of one unknown, and a method of elimination of group of unknowns. Special attention is given to methods of elimination of u...
Saved in:
| Date: | 2019 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/176507 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302594844983296 |
|---|---|
| author | Ostapenko, V. V. Finin, G. S. |
| author_facet | Ostapenko, V. V. Finin, G. S. |
| author_sort | Ostapenko, V. V. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-08-21T15:53:44Z |
| description | In the paper the connection between operation of projection and methods of elimination of unknowns is investigated. Separately, considered is a method of sequential elimination of one unknown, and a method of elimination of group of unknowns. Special attention is given to methods of elimination of unknowns from the system of inequalities with a graph structure. |
| first_indexed | 2025-07-17T10:26:19Z |
| format | Article |
| fulltext |
© В.В. Остапенко, Г.С. Фінін
Системні дослідження та інформаційні технології, 2002, 2 96
УДК 518.9
МЕТОДИ ВИЛУЧЕННЯ НЕВІДОМИХ ЗА ДОПОМОГОЮ
ОПЕРАЦІЙ ПРОЕКТУВАННЯ
В.В. ОСТАПЕНКО, Г.С. ФІНІН
В статті досліджується зв'язок між операцією проектування та методами
вилучення невідомих. Окремо розглядаються метод послідовного вилучення
однієї невідомої, а також метод вилучення групи невідомих. Значну увагу
приділяється методам вилучення невідомих із систем нерівностей, що
описуються нерівностями, які мають структуру графу.
В роботах [1–4] наведені і обгрунтовані методи вилучення невідомих при
розв'язанні систем лінійних алгебраїчних нерівностей. В [1] досліджено
метод послідовного вилучення одної невідомої, в [2–4] — метод вилучення
групи невідомих. Розроблені у цих роботах методи використовувались для
визначення невідомих течій у сітках із узагальненим законом Кірхгофа. В
даній роботі запропонована загальна схема вилучення невідомих на основі
операторів проектування.
1. Схема вилучення невідомих. Нехай nE — n-вимірний евклідів
простір, множина nEM ⊂ . Розглянемо задачу : знайти точку Mx ∈* . Для
розв'язання цієї задачі скористаємося методом вилучення невідомих.
Позначимо одиничні орти через ie ,)0,...,0,1,0,...,0(
i
= ni ,...,1= . Нехай
)(
sii
s e...eE ,,
1
— підпростір у nE , який натягнутий на вектори
sii ee ,...,
1
sii xx ,...,
1
π — оператор ортогонального проектування на підпростір
)(
sii
s e...eE ,,
1
. Припустимо, що вектори
sii e...e ,,
1
,
kjj e...e ,,
1
, nks =+
складають базис простору nE , тобто змінні
sii x...x ,,
1
,
kjj x...x ,,
1
складають множину всіх змінних nxx ,...,1 .
В зроблених позначеннях операція вилучення групи невідомих
kjj x...x ,,
1
еквівалентна операції ортогонального проектування
sii xx ,...,
1
π множини М
на підпростір )(
sii
s e...eE ,,
1
. Щоб це підкреслити, покладемо ),,(
1 kjj x...xπ ≡
≡
sii ,...,xxπ
1
.
Наприклад, вилучення одної невідомої 1x еквівалентно застосуванню
оператора )( 1xπ ≡
nx,...,xπ
2
.
Нехай *
i
*
i n
x...x ,,
1
— фіксовані значення відповідних координат вектора
nEx∈ .
Методи вилучення невідомих за допомогою операцій проектування
Системні дослідження та інформаційні технології, 2002, 2 97
Позначимо
{ }**
1
** ,...,:),...,(),...,(
111 ssn iiii
n
nii xxxxExxxxxL ==∈== .
Опишемо схему послідовного вилучення одної невідомої. Будемо
послідовно вилучати невідомі nxx ,...,1 . Прямий хід методу вилучення
невідомих полягає у наступному. Послідовно знаходимо множини ( )Mx1π ,
( ) ( ) ( )MxxMxxMxx nk 11121 ,,...,,...,,...,,..., −πππ . Остання множина додається
до підпростору )(1
neE який має вимірність 1 і задає обмеження тільки на
змінну nx .
Опишемо зворотній хід методу вилучення невідомих. Визначаємо
точку ( )Mxxx nn 11
* ,..., −∈π . Множина ( ) ( )*
21,..., nn xLMxx ∩−π має вимірність
1 і задає обмеження тільки на змінну 1−nx . Визначаємо точку
( ) ( )*
21
*
1 ,..., nnn xLMxxx ∩−− ∈π . Якщо відомі значення **
1,..., nk xx + , то
значення *
kx знаходиться із одновимірної множини ( ) ∩Mxx k 11,..., −π
( )**
1,..., nk xxL +∩ .
Продовжуючи такий процес, знаходимо точку ( ) Mxxx n ∈= **
1
* ,..., .
Зазначимо, що у випадку, коли М — опукла замкнена множина, то для
будь-якого k множина ( ) ( )**
111 ,...,,..., nkk xxLMxx +− ∩π є або всією дійсною
віссю, де змінюється kx , або піввіссю, або проміжком.
Аналогічно описується схема послідовного вилучення групи
невідомих. Припустимо, що послідовно вилучаються наступні групи:
nnnnnn xxxxxxx
ss
=++ −
,...,;...;,...,;,..., 111 1211
.
Прямий хід полягає у послідовному визначенні множин
( )Mxx n1
,...,1π , ( ) ( )MxxMxx
snn 12
,...,,...,,..., 11 −
ππ
Множина ( )Mxx
sn 1
,...,1 −
π включається до підпростору ),,( 11 nn e...eE
s +−
,
який має вимірність 1−− snn і задає обмеження на змінні **
1,...,
1 nn xx
s +−
.
Зворотний хід полягає у наступному. Визначаємо точку ( )∈+−
**
1,...,
1 nn xx
s
( )Mxx
sn 1
,...,1 −
∈π . Множина ( )Mxx
sn 2
,...,1 −
π ( )**
1,...,
1 nn xxL
s +−
∩ визначає
обмеження на невідомі
12
,...,1 −− + ss nn xx . У цій множині знаходимо точку
( )**
1 12
,...,
−− + ss nn xx і продовжуємо процес далі. В результаті одержуємо точку
( ) Mxxx n ∈= **
1
* ,..., .
Процес вилучення групи невідомих можна звести до послідовного
вилучення одної невідомої. Але, як показано у роботах [2–4], метод
В.В. Остапенко, Г.С. Фінін
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 98
вилучення групи невідомих у ряді випадків більш ефективний, ніж метод
послідовного вилучення одної невідомої.
2. Обмеження у вигляді многогранників. Припустимо, що М —
опуклий многогранник. За визначенням, многогранник — опукла оболонка
скінченного числа точок. Відомо (див., наприклад [5]), що многогранник
можна зобразити у вигляді скінченної системи лінійних нерівностей. Таке
зображення, як правило, виникає в процесі побудови лінійних моделей.
Розглянемо вектори ( ) n
n Eaaa ∈= ,...,1 , ( ) n
n Exxx ∈= ,...,1 . Позначимо
через ∑
=
=
n
i
ii xaxa
1
, скалярний добуток векторів a та x.
Нехай ( )i
n
ii aaa ,...,1= , mi ,...,1= — набір сталих векторів; ib , mi ,...,1=
— деякі числа. Припускаємо, що многогранник М задається у вигляді
системи нерівностей
i
i bxa ≤, , mi ,...,1= . (1)
Для опису множин ( )Mxx k,...,1π зручно представити множину М не у
вигляді (1), а за допомогою крайніх точок (вершин).
Відомо [5], що 0x є крайньою точкою множини М, заданої у вигляді
(1), тоді і тільки тоді, коли множина { }ii bxaixI == 00 ,:)( містить
підмножину 0I , що має потужність n, і вектори ia , 0Ii∈ лінійно
незалежні. Із цього випливає, що можна визначити всі крайні точки
множини М. Для цього треба розв'язати ряд невироджених систем лінійних
рівнянь.
Недоліком даного підходу є необхідність великої кількості переборів
таких систем рівнянь.
Нехай pxx ,...,1 — знайдені крайні точки множини М. Тоді
{ }pxxM ,...,1co= (со — опукла оболонка множини). Очевидно, що
( ) =Mxx k,...,1π co ( ) ( ){ }p
kk xxxxxx ,...,,...,,..., 1
1
1 ππ
Здійснення операції проектування одної точки ( ) i
k xxx ,...,1π , pi ,...,1=
досить тривіально.
Для здійснення зворотного ходу методу необхідно будувати множини
вигляду
( ) ( )**
111 ,...,,..., nkk xxLMxx +− ∩π .
При цьому зручно многогранник ( )Mxx k 11,..., −π задавати системою
нерівностей.
Методи вилучення невідомих за допомогою операцій проектування
Системні дослідження та інформаційні технології, 2002, 2 99
Нехай nq Rxx ⊂,...,1 — деякий набір точок, { }qxxN ,...,co 1= —
многогранник. Використовуючи викладений в [5] апарат, по точках qxx ,...,1
можна побудувати скінченну систему нерівностей, яка описує множину N.
Позначимо опорну функцію )( *xWN = *,sup xx
Nx∈
= *
1
,max xxi
qxi≤≤
.
Для кожного *x визначимо { }qixWxxixI N
i ,...,1),(,:)( *** === .
Гіперплощина )(, ** xWxx N= називається опорою. Якщо )( *xIj∈ і
серед векторів ji xx − , )( *xIi∈ є n – 1 лінійно незалежних, то опора
називається крайньою.
Кожну крайню опору описує вектор *x і число )( *xWN . Кількість
різних опор скінченна. Дійсно, розглянемо різні набори по n векторів ix
qi ,...,1= . Нехай ix , Ii∈ , nI = — такий набір. Зафіксуємо Jj∈ та
перевіримо чи будуть вектори jii xxy −= , Ii∈ , ji ≠ лінійно
незалежними. Якщо ні, то розглядаємо наступний набір векторів. Якщо так,
то відшукуємо ортогональний векторам iy , }{\ jIi∈ вектор *x , тобто
0,* =iyx , }{\ jIi∈ . Розв'язок цієї системи є одновимірним простором.
Для побудови шуканої системи нерівностей досить розглянути тільки
вектори *x одиничної довжини. Таких векторів буде два : *
+x , *
−x ,
**
+− −= xx . Знаходимо *
1
,max ±
≤≤
± = xxb i
qxi
= )( *
±xWN .
В результаті одержуємо, що до опису множини N повинні входити
нерівності — +
+
− ≤≤ bxxb *, . Таких нерівностей буде скінченна кількість.
Описаний метод вимагає істотного перебору. Крім того, одержана
система нерівностей може містити велику кількість нерівностей, які
випливають з інших нерівностей.
3. Вилучення невідомих із систем нерівностей. Скінченна система
нерівностей у загальному випадку описує многогранну множину і
многогранник, якщо ця множина обмежена.
Питання послідовного вилучення невідомих розглянуто у роботі [1].
Основним ускладненням, що виникає при вилученні невідомої є те, що нова
система може мати більше нерівностей, ніж вихідна. В роботах [2–4]
викладено метод вилучення групи невідомих із систем лінійних нерівностей.
Показано, що у ряді випадків цей метод більш ефективний ніж метод
послідовного вилучення невідомих.
4. Методи вилучення течій у сітках із узагальненим законом
Кірхгофа. Розглянемо зв'язний граф { }EVG ,= , де V — множина вершин; E
— множина ребер графа G. З кожним ребром ),( jie = зіставимо невідому
величину jiij xx = , Eji ∈),( .
В.В. Остапенко, Г.С. Фінін
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 100
Нехай { }Ejixx ij ∈= ),(, — вектор течій, що течуть по усіх ребрах
Eji ∈),( , для яких jiij xx = . Множина X є векторним простором вимірності
dim X = |E|. Позначимо { }EjijiN ∈= ),(:)( окіл вершини. Для кожної
вершини i ∈ V розглянемо вектори течій, що збігаються до цієї вершини
{ })(, iNjxx iji ∈= . Позначимо через iX множину усіх таких векторів ix .
Множина iX є векторним простором вимірності )(dim iNX i = .
Нехай ii XM ⊂ , Vi∈ — замкнені підмножини. Покладемо
{ }iii MxXxM ∈∈= :
~
. (2)
Простори iX є підпросторами в X. Позначимо iπ — оператор
ортогонального проектування по iX . Тоді
{ }iii MxXxM ∈∈= π:
~
. (3)
Обмеження (2) або (3) назвемо обмеженнями, які мають структуру
графа.
Сформулюємо задачу: знайти вектор Xx ∈* , такий що
iMx
~* ∈ , Vi∈ . (4)
Розглянемо метод послідовного вилучення одної невідомої.
Припустимо, що вилучається одна невідома abx , Eba ∈),( . При цьому
ребро ),( ba стягується, точки a та b збігаються і стають одною точкою, яку
позначимо ba . Опишемо спосіб побудови множини
ba
M
~
. Розглянемо
простір векторів { }),(),(,),(,),( bajiEjixbaX ij ≠∈= , у яких відсутня
координата abx з номером ),( ba . Множина ),( baX є підпростором
простору Х. Нехай )( baπ оператор ортогонального проектування простору
Х на підпростір )( baX . Покладемо baab MMM
~~~ ∩= , baba MbaM
~
)(
~
π= .
Вище всі множини iM
~ , Vi∈ було описано за допомогою множин
iM . Ці множини задають обмеження на координати вектора х, що
знаходяться у просторі iX . Дамо аналітичний опис множини baM
~ .
Розглянемо два векторних простори:
{ })(),(:, bNjaNixxX bjaiab ∈∈= ;
{ }ajbibNjaNixxX bjaiba ≠≠∈∈= ,),(),(:, .
Методи вилучення невідомих за допомогою операцій проектування
Системні дослідження та інформаційні технології, 2002, 2 101
Множина baX є підпростором простору abX . Нехай )( baπ —
оператор ортогонального проектування простору abX на підпростір baX .
Покладемо
{ }aaaba MxXxbM ∈∈= :)( ; { }bbabb MxXxaM ∈∈= :)( ;
)()( aMbMM baab ∩= , abba MbaM )(π= .
Із побудови випливає, що { }bababa MxbaXxM ∈∈= :)(
~
.
Таким чином, як наслідок вилучення невідомої abx , виходить нова
система нерівностей, що має структуру графа )( baG . Граф )( baG виходить
з графа G шляхом стягування ребра (a, b) та злиття точок a та b в одну
точку )( ba , тобто )( baG ={ )( baV , )( baE }, де { ,:)( aiVibaV ≠∈=
} )( babi ∪≠ ; )( baE = { }),(),(,),( bajiEji ≠∈ .
При цьому нова система нерівностей описує множину невідомих
векторів із простору abX .
Розглянемо вилучення групи невідомих. Нехай H={VH, EH} —
зв'язний підграф графа G; VH, EH — відповідно множини його вершин та
ребер. Будемо вилучати невідомі αβx , EH∈),( βα .
Розглянемо векторні простори, які складаються з наступних координат:
{ }EiViVHxX iH ∈∈∈= ),(,,, ααα ,
{ }EiVHiViVHxX iH ∈∉∈∈= ),(,,,, ααα .
Множина HX є підпростором простору HX . Нехай )(Hπ —
оператор ортогонального проектування простору HX на підпростір HX .
Покладемо { }ααα MxXx(H)M H ∈∈= : , VH∈α , )(HMM
VH
H α
α
∩
∈
= ,
HH MHM )(π= .
Утворимо з графа G новий граф )H(G , який випливає з графа шляхом
стягування підграфа Н в точку. Позначимо цю точку через H . При
вилученні групи невідомих αβx , EH∈),( βα одержуємо нову систему
нерівностей зі структурою графа )H(G . Для цієї системи всі αM
~ визначені,
як і вище, а { }HHH MxHXxM :
~
)(∈= .
Зауваження. В роботах [2–4] розглянуті випадки, коли кожній вершині
графа G відповідає одна двостороння нерівність. В цьому випадку можна
вилучати невідомі , що відповідають проміжним та кінцевим ребрам.
В.В. Остапенко, Г.С. Фінін
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 102
ЛІТЕРАТУРА
1. Черников С.Н. Линейные неравенства. — М.: Наука, 1968. — 488 с.
2. Остапенко В.В., Финин Г.С. Метод исключения неизвестных для систем
линейных неравенств со структурой графа // Кибернетика и системный
анализ. — 1999. — № 5. — С. 66–74.
3. Остапенко В.В., Финин Г.С. Методы исключения неизвестных из систем
линейных неравенств и их приложения // Укр. мат. журн. — 2001. — № 1.
— С. 50–56.
4. Финин Г.С. Решение систем линейных неравенств методами исключения
неизвестных // Вестник Междунар. Соломонов. ун-та. — 1999.— №1.— С.
116–122.
5. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука,
1980. — 320 с.
Надійшла 15.03.2002
|
| id | journaliasakpiua-article-176507 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:26:19Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/b7/bf974b2181ff4a44f5e31876ff1435b7.pdf |
| spelling | journaliasakpiua-article-1765072019-08-21T15:53:44Z Methods for eliminating unknowns with the help of projection operations Методы исключения неизвестных с помощью операций проектирования Методи вилучення невідомих за допомогою операцій проектування Ostapenko, V. V. Finin, G. S. In the paper the connection between operation of projection and methods of elimination of unknowns is investigated. Separately, considered is a method of sequential elimination of one unknown, and a method of elimination of group of unknowns. Special attention is given to methods of elimination of unknowns from the system of inequalities with a graph structure. В статье исследуется связь между операцией проектирования и методами исключения неизвестных. Отдельно рассматривается метод последовательного исключения одной неизвестной, а также метод исключения группы неизвестных. Большое внимание уделено методам исключения неизвестных из системы неравенств, имеющих структуру графа. В статті досліджується зв’язок між операцією проектування та методами вилучення невідомих. Окремо розглядаються метод послідовного вилучення однієї невідомої, а також метод вилучення групи невідомих. Значну увагу приділяється методам вилучення невідомих із систем нерівностей, що описуються нерівностями, які мають структуру графу. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-08-21 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/176507 System research and information technologies; No. 2 (2002); 96-102 Системные исследования и информационные технологии; № 2 (2002); 96-102 Системні дослідження та інформаційні технології; № 2 (2002); 96-102 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/176507/176268 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Ostapenko, V. V. Finin, G. S. Методи вилучення невідомих за допомогою операцій проектування |
| title | Методи вилучення невідомих за допомогою операцій проектування |
| title_alt | Methods for eliminating unknowns with the help of projection operations Методы исключения неизвестных с помощью операций проектирования |
| title_full | Методи вилучення невідомих за допомогою операцій проектування |
| title_fullStr | Методи вилучення невідомих за допомогою операцій проектування |
| title_full_unstemmed | Методи вилучення невідомих за допомогою операцій проектування |
| title_short | Методи вилучення невідомих за допомогою операцій проектування |
| title_sort | методи вилучення невідомих за допомогою операцій проектування |
| url | https://journal.iasa.kpi.ua/article/view/176507 |
| work_keys_str_mv | AT ostapenkovv methodsforeliminatingunknownswiththehelpofprojectionoperations AT finings methodsforeliminatingunknownswiththehelpofprojectionoperations AT ostapenkovv metodyisklûčeniâneizvestnyhspomoŝʹûoperacijproektirovaniâ AT finings metodyisklûčeniâneizvestnyhspomoŝʹûoperacijproektirovaniâ AT ostapenkovv metodivilučennânevídomihzadopomogoûoperacíjproektuvannâ AT finings metodivilučennânevídomihzadopomogoûoperacíjproektuvannâ |