Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия
Проаналізовано лінійні балансові моделі міжгалузевої еколого-економічної взаємодії та запропоновано комп’ютерні алгоритми для їх розв’язання. Обґрунтовано ефективність цих алгоритмів і можливості їх застосування на практиці. Linear balance models of intersectorial ecological-economics interaction ar...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45122 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия / Н.А. Недашковский, Т.И. Крошка // Кибернетика и системный анализ. — 2010. — № 1. — С. 17–28. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859712287372214272 |
|---|---|
| author | Недашковский, Н.А. Крошка, Т.И. |
| author_facet | Недашковский, Н.А. Крошка, Т.И. |
| citation_txt | Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия / Н.А. Недашковский, Т.И. Крошка // Кибернетика и системный анализ. — 2010. — № 1. — С. 17–28. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Проаналізовано лінійні балансові моделі міжгалузевої еколого-економічної взаємодії та запропоновано комп’ютерні алгоритми для їх розв’язання. Обґрунтовано ефективність цих алгоритмів і можливості їх застосування на практиці.
Linear balance models of intersectorial ecological-economics interaction are analyzed and new computer algorithms for solving them are proposed. The efficiency of these algorithms and the possibility of using them in practice are substantiated.
|
| first_indexed | 2025-12-01T05:55:04Z |
| format | Article |
| fulltext |
ÓÄÊ 519.86
Í.À. ÍÅÄÀØÊÎÂÑÊÈÉ, Ò.È. ÊÐÎØÊÀ
ÂÛ×ÈÑËÈÒÅËÜÍÛÅ ÀËÃÎÐÈÒÌÛ ÄËß ËÈÍÅÉÍÛÕ ÁÀËÀÍÑÎÂÛÕ
ÌÎÄÅËÅÉ ÌÅÆÎÒÐÀÑËÅÂÎÃÎ ÝÊÎËÎÃÎ-ÝÊÎÍÎÌÈ×ÅÑÊÎÃÎ
ÂÇÀÈÌÎÄÅÉÑÒÂÈß
Êëþ÷åâûå ñëîâà: ýêîëîãî-ýêîíîìè÷åñêàÿ ñèñòåìà, ìåæîòðàñëåâîé ýêîëîãî-ýêî-
íîìè÷åñêèé áàëàíñ, îòñå÷åííûå ñèñòåìû, ðåêóððåíòíûå ñîîòíîøåíèÿ, òåïëèöåâû
ìàòðèöû.
Ñîâðåìåííûå ýêîíîìè÷åñêèå ñèñòåìû ôóíêöèîíèðóþò â óñëîâèÿõ ñèëüíîãî âëè-
ÿíèÿ ýêîñèñòåì, è íàîáîðîò, àíòðîïîãåííîå âîçäåéñòâèå íà ýêîñèñòåìû ñóùåñ-
òâåííî âëèÿåò íà èõ äèíàìèêó.  ñâÿçè ñ ýòèì ñëåäóåò â áîëüøèíñòâå ñëó÷àåâ
ðàññìàòðèâàòü ýêîíîìèêó è ýêîëîãèþ êàê ïîäñèñòåìû åäèíîé öåëîñòíîé ýêîëî-
ãî-ýêîíîìè÷åñêîé ñèñòåìû. Ýòî îñîáåííî âàæíî â íàñòîÿùåå âðåìÿ, êîãäà ÷åëî-
âå÷åñêîå ñîîáùåñòâî ñòðåìèòñÿ ê äîñòèæåíèþ óñòîé÷èâîãî ðàçâèòèÿ.
Ñðåäè ìåòîäîâ èçó÷åíèÿ ýêîëîãî-ýêîíîìè÷åñêèõ ñèñòåì èëè îòäåëüíûõ ïðî-
öåññîâ èõ âçàèìîäåéñòâèÿ âàæíîå çíà÷åíèå èìåþò ìåòîäû ìàòåìàòè÷åñêîãî ìîäå-
ëèðîâàíèÿ. Äàííàÿ ðàáîòà ïîñâÿùåíà ìàòåìàòè÷åñêîìó ìîäåëèðîâàíèþ ýêîëî-
ãî-ýêîíîìè÷åñêîãî âçàèìîäåéñòâèÿ íà ïðîèçâîäñòâåííî-òåõíîëîãè÷åñêîì óðîâíå.
Ðàññìàòðèâàþòñÿ òàê íàçûâàåìûå ìîäåëè ìåæîòðàñëåâîãî ýêîëîãî-ýêîíîìè÷åñêîãî
áàëàíñà, èëè ìîäåëè Ëåîíòüåâà–Ôîðäà.
Îäèí èç âàðèàíòîâ ïðÿìîé ëèíåéíîé ìîäåëè Ëåîíòüåâà–Ôîðäà ôîðìàëèçóåòñÿ
ñîîòíîøåíèÿìè
x A x A x y
x A x A x y
( ) ( ) ( ) ( )
( ) ( ) ( ) (
,1
11
1
12
2 1
2
21
1
22
2 2
� � �
� � � ) ,
�
�
�
(1)
ãäå x n( )1 � �R — âåêòîð îñíîâíîãî ïðîèçâîäñòâà (R�
l — íåîòðèöàòåëüíûé îðòàíò
l-èçìåðèìîãî ïðîñòðàíñòâà); x m( )2 � �R — âåêòîð óíè÷òîæåííûõ çàãðÿçíèòåëåé
(âñïîìîãàòåëüíûõ ïðîäóêòîâ-îòõîäîâ); y n( )1 � �R — âåêòîð êîíå÷íîé ïðîäóêöèè;
y m( )2 � �R — âåêòîð íåóíè÷òîæåííûõ çàãðÿçíèòåëåé; A a
ij i j
n
11
11
1
�
�
( )( )
,
— êâàä-
ðàòíàÿ ìàòðèöà çàòðàò ïðîäóêöèè i íà âûïóñê åäèíèöû ïðîäóêöèè j;
A a
i l i l
n m
12
12
1
�
�
( )( )
,
,
— ïðÿìîóãîëüíàÿ ìàòðèöà çàòðàò ïðîäóêöèè i íà óíè÷òîæåíèå
åäèíèöû çàãðÿçíèòåëÿ l; A a
lj l j
m n
21
21
1
�
�
( )( )
,
,
— ïðÿìîóãîëüíàÿ ìàòðèöà âûïóñêîâ
çàãðÿçíèòåëÿ l ïðè âûïóñêå åäèíèöû ïðîäóêöèè j; A a
ls l s
m
22
22
1
�
�
( )( )
,
— êâàäðàò-
íàÿ ìàòðèöà âûïóñêîâ çàãðÿçíèòåëÿ l ïðè óíè÷òîæåíèè åäèíèöû çàãðÿçíèòåëÿ s.
Êîìïîíåíòû âñåõ ïåðå÷èñëåííûõ âåêòîðîâ è ìàòðèö ÿâëÿþòñÿ íåîòðèöàòåëüíû-
ìè âåëè÷èíàìè, ïîñêîëüêó îíè îòîáðàæàþò ðåàëüíóþ ýêîíîìè÷åñêóþ ñóùíîñòü.
Ñóòü ìîäåëè (1) î÷åâèäíà: ïåðâîå ðàâåíñòâî — ðàñïðåäåëåíèå ïðîäóêöèè ìà-
òåðèàëüíîãî ïðîèçâîäñòâà íà çàòðàòû â îñíîâíîì è âñïîìîãàòåëüíîì ïðîèçâî-
äñòâàõ, à òàêæå íà êîíå÷íóþ ïðîäóêöèþ; âòîðîå ðàâåíñòâî — áàëàíñîâîå ñîîòíî-
øåíèå, ñîñòîÿùåå â òîì, ÷òî îáúåì ëèêâèäèðîâàííîãî çàãðÿçíåíèÿ ðàâåí ðàçíîñòè
ìåæäó îáúåìàìè âñåãî çàãðÿçíåíèÿ è íåóíè÷òîæåííîãî.
Ïî àíàëîãèè ñ êëàññè÷åñêèì ìåæîòðàñëåâûì áàëàíñîì ñîîòíîøåíèÿ (1) îñíî-
âûâàþòñÿ íà ñîîòâåòñòâóþùåé ñõåìå ìåæîòðàñëåâîãî ýêîëîãî-ýêîíîìè÷åñêîãî
áàëàíñà «ïî ñòðîêàì».
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 17
Í.À. Íåäàøêîâñêèé, Ò.È. Êðîøêà, 2010
×àñòî áîëåå èíòåðåñíûìè, ÷åì ìîäåëü (1), ÿâëÿþòñÿ åå äâîéñòâåííûå âàðèàí-
òû, ïîñêîëüêó èõ ìîæíî èñïîëüçîâàòü ïðè ðåøåíèè ïðîáëåì öåíîîáðàçîâàíèÿ. Ýòè
ìîäåëè áàçèðóþòñÿ íà ñõåìàõ ìåæîòðàñëåâîãî ýêîëîãî-ýêîíîìè÷åñêîãî áàëàíñà
[1, 2] â ñòîèìîñòíîé ôîðìå «ïî ñòîëáöàì» (ïåðâûé è òðåòèé êâàäðàíòû).
Îáîçíà÷èì:
T — îïåðàöèÿ òðàíñïîíèðîâàíèÿ;
p p pn
n( ) ( ) ( )( ,... , )1
1
1 1� � �
T R — âåêòîð öåí îñíîâíîé ïðîäóêöèè;
p p pm
m( ) ( ) ( )( )2
1
2 2� � � � ��
T R — âåêòîð ñòîèìîñòè óíè÷òîæåíèÿ åäèíè÷íûõ
îáúåìîâ çàãðÿçíåíèÿ;
k k kn
n( ) ( ) ( )( ,... , )1
1
1 1� � �
T R — âåêòîð êîýôôèöèåíòîâ óñëîâíî-÷èñòîé ïðî-
äóêöèè ëèáî îòíîñèòåëüíûõ öåí òîé ÷àñòè îñíîâíîé ïðîäóêöèè, êîòîðàÿ âêëþ÷åíà
â óñëîâíî-÷èñòóþ ïðîäóêöèþ (åñëè z
j
( )1 — óñëîâíî-÷èñòàÿ ïðîäóêöèÿ j â íàòó-
ðàëüíîé ôîðìå, òî k z x p
j j j j
( ) ( ) ( ) ( )( )1 1 1 1� );
k k km
m( ) ( ) ( )( )2
1
2 2� � � � ��
T R — âåêòîð êîýôôèöèåíòîâ óñëîâíî-÷èñòîé ïðî-
äóêöèè îòðàñëåé âñïîìîãàòåëüíîãî ïðîèçâîäñòâà ëèáî îòíîñèòåëüíûõ ñòîèìîñòåé
óíè÷òîæåíèÿ çàãðÿçíèòåëåé (åñëè zs
( )2 — óñëîâíî-÷èñòàÿ ïðîäóêöèÿ s â íàòóðàëü-
íîé ôîðìå, òî k z x ps s s s
( ) ( ) ( ) ( )( )2 2 2 2� ).
Òîãäà îäíèì èç âàðèàíòîâ äâîéñòâåííîé îòíîñèòåëüíî öåí ìîäåëè Ëåîíòüå-
âà–Ôîðäà ÿâëÿåòñÿ ñëåäóþùàÿ ìîäåëü [3, 4]:
p A p A p k
p A p A p
( ) ( ) ( ) ( )
( ) ( ) ( )
,1
11
1
21
2 1
2
12
1
22
2
� � �
� � �
T
T T k ( ) .2
�
�
�
��
(2)
Êàê äëÿ ìîäåëè (1), òàê è äëÿ ìîäåëè (2) îñíîâíîé ìàòåìàòè÷åñêîé ïðîáëåìîé
ÿâëÿåòñÿ ïðîáëåìà ïðîäóêòèâíîñòè, ò.å. ñóùåñòâîâàíèÿ íåîòðèöàòåëüíûõ ðåøåíèé
ïðè çàäàííûõ òåõíîëîãè÷åñêèõ ìàòðèöàõ A A A A11 12 21 22, , , è âåêòîðàõ y y( ) ( ),1 2 .
Íà ñåãîäíÿøíèé äåíü ýòà ïðîáëåìà äîñòàòî÷íî õîðîøî èçó÷åíà [3]. Äëÿ ïðÿ-
ìîé ìîäåëè Ëåîíòüåâà–Ôîðäà (1) óñòàíîâëåíû îïðåäåëåííûå óñëîâèÿ ïðîäóêòèâ-
íîñòè, â ÷àñòíîñòè, åñëè ñóùåñòâóþò îáðàòíûå ìàòðèöû
( )I An � �
11
1, ( )I Am � �
22
1, ( )I An � �
1
1, ( )I Am � �
2
1,
ãäå
A A A I A Am1 11 12 22
1
21� � � �( ) , A A A I A An2 22 21 11
1
12� � � �( ) ,
I In m, — äèàãîíàëüíûå åäèíè÷íûå ìàòðèöû ðàçìåðíîñòåé ( )n n
è ( )m m
, òî
ïðè y y n( ) ( )({ , } )1 10 0� � R , y y m( ) ( )({ , } )2 20 0� � R äîñòàòî÷íûì óñëîâèåì íå-
îòðèöàòåëüíîñòè ðåøåíèé ñèñòåìû (1) áóäåò óñëîâèå
A I A y yn21 11
1 1 2( ) ( ) ( )� �� (3)
èëè áîëåå æåñòêîå óñëîâèå
A y y21
1 2( ) ( )� . (4)
 ñëó÷àå ïðîäóêòèâíîñòè áëî÷íîé ìàòðèöû A
A A
A A
�
�
�
��
�
�
��
11 12
21 22
, ò.å. ñóùåñòâîâà-
íèÿ ìàòðèöû A �1, ïðè y y n( ) ( )({ , } )1 10 0� � R , y y m( ) ( )({ , } )2 20 0� � R óñëîâèå
( ) [ ( ) ] ( )( ) ( )I A A I A y ym n
m� � � � �� �
2
1
21 11
1 1 2 0 0 R (5)
ÿâëÿåòñÿ íåîáõîäèìûì è äîñòàòî÷íûì äëÿ ñóùåñòâîâàíèÿ íåîòðèöàòåëüíûõ ðå-
øåíèé (1).
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Èññëåäîâàíèå ïðîäóêòèâíîñòè äâîéñòâåííîé îòíîñèòåëüíî öåí ìîäåëè (2)
ôàêòè÷åñêè ñâîäèòñÿ ê èññëåäîâàíèþ ïðîäóêòèâíîñòè êëàññè÷åñêîé ìîäåëè Ëåîí-
òüåâà [5], òàê êàê åå ìîæíî çàïèñàòü â âèäå
p A p k� �T , (6)
ãäå p p p k k k� �( , ) , ( , )( ) ( ) ( ) ( )1 2 1 2T T .
Äëÿ ïðîäóêòèâíîñòè ìîäåëè (6) (ò.å. (2)) ñ íåîòðèöàòåëüíîé è íåðàçëîæè-
ìîé [5] ìàòðèöåé A T íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ñîáñòâåííîå ÷èñëî Ôðîáå-
íèóñà ìàòðèöû A T áûëî ìåíüøå åäèíèöû. Âîñïîëüçîâàâøèñü óñëîâèåì
| |A ET � �� 0 è ðåøèâ êâàäðàòíîå óðàâíåíèå, êîòîðîå ïðè ýòîì ïîëó÷èëîñü, èìååì
÷èñëî Ôðîáåíèóñà äëÿ ìàòðèöû A T ñëåäóþùåãî âèäà: �
A
A AT � � ��
�
�1 2
11 22
� � � �
�
�( )A A A A11 22
2
12 214 .
Ïðîñòåéøèìè äîñòàòî÷íûìè óñëîâèÿìè ñóùåñòâîâàíèÿ íåîòðèöàòåëüíûõ ðå-
øåíèé ñèñòåìû (6) ñ íåîòðèöàòåëüíîé è íåðàçëîæèìîé ìàòðèöåé A T ÿâëÿþòñÿ
óñëîâèÿ
�i ij
j
n
a� �
�
� T
1
1, i n�1, , (7)
ñðåäè êîòîðûõ õîòÿ áû äëÿ îäíîãî i
0
âûïîëíÿåòñÿ ñòðîãîå íåðàâåíñòâî ( )�i0
1� .
Òàêèì îáðàçîì, óñëîâèÿ (3)–(5) äëÿ ìîäåëè (1) è óñëîâèÿ (7) äëÿ ìîäåëè (2) èã-
ðàþò âàæíóþ ñîäåðæàòåëüíóþ ðîëü íà óðîâíå ìîäåëüíîãî àíàëèçà, ïîñêîëüêó îíè
îáåñïå÷èâàþò íà ïðàêòèêå ñóùåñòâîâàíèå ýêîíîìè÷åñêè îáîñíîâàííûõ ðåøåíèé.
Äðóãîé âàæíîé îñîáåííîñòüþ ìîäåëåé (1), (2) (êàê è äðóãèõ âàðèàíòîâ áàëàí-
ñîâûõ ìîäåëåé ýêîëîãî-ýêîíîìè÷åñêîãî âçàèìîäåéñòâèÿ) ÿâëÿåòñÿ ñòðóêòóðà ìàò-
ðèö A A A A11 12 21 22, , , .  ïðàêòè÷åñêèõ ïðèëîæåíèÿõ ýëåìåíòû ìàòðèö A A11 12, è
A A21 22, èìåþò ñîâåðøåííî ðàçíûé ïîðÿäîê. Ê òîìó æå íåêîòîðûå èç ýòèõ ìàòðèö
ìîãóò áûòü ñèëüíî ðàçðÿæåííûìè èëè ïëîõî îáóñëîâëåííûìè, èëè èìåòü áîëüøóþ
ðàçìåðíîñòü. Ýòè ôàêòîðû ñòèìóëèðóþò ðàçðàáîòêó ñïåöèôè÷åñêèõ ìåòîäîâ è àë-
ãîðèòìîâ äëÿ íàõîæäåíèÿ ðåøåíèé ìîäåëåé (1), (2) è èì ïîäîáíûõ. Íåêîòîðûå èç
íèõ ïðåäëàãàþòñÿ íèæå.
Ñíà÷àëà ðàññìîòðèì ñëó÷àé, êîãäà ýëåìåíòû ìàòðèö A A A A11 12 21 22, , , — íå-
êîòîðûå ôèêñèðîâàííûå ÷èñëà, ñâÿçàííûå ñ ïðîèçâîäñòâîì; y n( )1 � �R — ïàðàìåò-
ðè÷åñêèé âåêòîð êîíå÷íîé ïðîäóêöèè; y m( )2 � �R — ïàðàìåòð íåóíè÷òîæåííûõ çà-
ãðÿçíèòåëåé. Áóäåì èñêàòü âåêòîð âàëîâîãî (îñíîâíîãî) ïðîèçâîäñòâà x n( )1 � �R è
âåêòîð óíè÷òîæåííûõ çàãðÿçíèòåëåé x m( )2 � �R (âñïîìîãàòåëüíûõ ïðîäóêòîâ-îòõî-
äîâ) â âèäå íåêîòîðîãî àíàëèòè÷åñêîãî âûðàæåíèÿ, çàâèñÿùåãî îò ïàðàìåòðîâ y ( )1
è y ( )2 .
Ñèñòåìà (1) ìîæåò áûòü çàïèñàíà â âèäå
x
x
A A
A A
x
x
( )
( )
( )
( )
1
2
11 12
21 22
1
2
�
�
�
�
�
�
�
� �
�
�
��
�
�
��
�
�
�
�
�
�
�
� � �
�
�
�
�
�
�
�
�
y
y
( )
( )
1
2 (8)
èëè
A A
A A
E
E
x
x
11 12
21 22
1
2
0
0
�
�
��
�
�
�� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�( )
( )
�
�
� �
��
�
�
�
�
�
�
�
y
y
( )
( )
1
2
. (9)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 19
Ââåäÿ îáîçíà÷åíèå C
A A
A A
E
E
�
�
�
��
�
�
�� �
�
�
�
�
�
�11 12
21 22
0
0
, ñèñòåìó (9) ìîæíî çàïèñàòü
â âèäå
C C
C C
x
x
y
y
11 12
21 22
1
2
1
2
�
�
��
�
�
��
�
�
�
�
�
�
�
� �
��
�
�
�
( )
( )
( )
( )
�
�
�
� , (10)
îòêóäà
( ) ,
(
( ) ( ) ( )C C C C x y C C y
C C C
11 12 22
1
21
1 1
12 22
1 2
22 21 1
� � �
�
� �
1
1
12
2 2
21 11
1 1� �� �
�
�
�
�� C x y C C y) .( ) ( ) ( )
(11)
Äëÿ îïðåäåëåíèÿ íåèçâåñòíûõ x x( ) ( ),1 2 íóæíî âû÷èñëèòü C C21 11
1� è C C12 22
1�
ëèáî ðåøèòü ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé
C z C
11
1
21
T T( ) � , (12)
C z C
22
2
12
T T( ) � , (13)
ãäå C c
ij i j
n
11
11
1
�
�
( )( )
,
, C c
ls l s
m
22
22
1
�
�
( )( )
,
, C c
il i l
n m
12
12
1
�
�
( )( )
,
, , C c
lj l j
m n
21
21
1
�
�
( )( )
,
, , ò.å.
íóæíî ðåøèòü ñèñòåìó n-ãî ïîðÿäêà (12) ñ m ïðàâûìè ÷àñòÿìè è ñèñòåìó m-ãî
ïîðÿäêà ñ n ïðàâûìè ÷àñòÿìè (13).
Äëÿ ñèñòåìû (12) ìîæíî çàïèñàòü, ñîãëàñíî âòîðîìó àëãîðèòìó óñå÷åííûõ
ñèñòåì [6, 7], ðåêóððåíòíûå ñîîòíîøåíèÿ:
b
a a u
a a u
i k
i k i j j
k
j
k
k k k j j
k
j
,
, ,
( )
, ,
( )
�
�
�
�
�
�
�
�
�T T
T T
1
1
1
1
1
1
1
1
1
1 1
k
k
k
k k
s
k
k s
i k n
v b k n
v b
�
�
�
�
� �
� � �
� �
( , ),
( , ),( )
,
( )
, b v s ki s i
k
i s
k
,
( ) ( , );
� �
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1 1
(14)
b
a a v
a a v
k i
k i j i j
k
j
k
k k j k j
k
j
,
, ,
( )
, ,
( )
�
�
�
�
�
�
�
�
�T T
T T
1
1
1
1
1
1
1
1
1 1
k
k
k
k k
s
k
s k
i k n m
u b k n
u b
�
�
�
�
� � �
� � �
�
( , ),
( , ),( )
,
( )
, 1
1
1 1� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� b u s ks i i
k
i s
k
,
( ) ( , ).
(15)
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Ïðîâåäÿ âû÷èñëåíèÿ ïî ôîðìóëàì (14) è (15) äëÿ z ( )1 , ìîæíî çàïèñàòü:
z b b z
i j i n j i n k k j
k
m
,
( )
, , ,
1
1
1
� �� �
�
�
� . (16)
Ïîñëå ðàçîâîãî âû÷èñëåíèÿ z
i j,
( )1 âåêòîð x ( )1 îïðåäåëÿåòñÿ èç ôîðìóëû
x C z C y z y( ) ( ) ( ) ( ) ( )( ) ( )1
11
1
21
1 1 1 2� � �� .
Ìàòðèöà w C z C� � �( )( )
11
1
21
1 ìîæåò áûòü âû÷èñëåíà êàê ðåøåíèå ñèñòåìû
n-ãî ïîðÿäêà
( )( )C z C w E11
1
21� � (17)
ñ ïîìîùüþ àëãîðèòìà, ïîäîáíîãî ñõåìå (14)–(15).
Òàêèì îáðàçîì, äëÿ âû÷èñëåíèÿ âåêòîðà x ( )1 ïîñëå ðåøåíèÿ ñèñòåì (12) è (17)
èñïîëüçóåòñÿ ôîðìóëà x wy wz y( ) ( ) ( ) ( )1 1 1 2� � .
Äëÿ ñèñòåìû (13) ìîæíî çàïèñàòü, ñîãëàñíî âòîðîìó àëãîðèòìó óñå÷åííûõ
ñèñòåì [6, 7], ðåêóððåíòíûå ñîîòíîøåíèÿ:
b
a a u
a a u
i k
i k i j j
k
j
k
k k k j j
k
j
,
, ,
( )
, ,
( )
�
�
�
�
�
�
�
�
�T T
T T
1
1
1
1
1
1
1
1
1
1 1
k
k
k
k k
s
k
k s
i k m
v b k m
v b
�
�
�
�
� �
� � �
� �
( , ),
( , ),( )
,
( )
, b v s ki s i
k
i s
k
,
( ) ( , );
� �
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1 1
(18)
b
a a v
a a v
k i
k i j i j
k
j
k
k k j k j
k
j
,
, ,
( )
, ,
( )
�
�
�
�
�
�
�
�
�T T
T T
1
1
1
1
1
1
1
1
1 1
k
k
k
k k
s
k
s k
i k m n
u b k m
u b
�
�
�
�
� � �
� � �
�
( , ),
( , ),( )
,
( )
, 1
1
1 1� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� b u s ks i i
k
i s
k
,
( ) ( , ).
(19)
Ïîñëå ïðîâåäåíèÿ âû÷èñëåíèé ïî ôîðìóëàì (18) è (19) äëÿ âû÷èñëåíèÿ z ( )2
ìîæíî çàïèñàòü:
z b b z
i j i n j i m k k j
k
n
,
( )
, , ,
2
1
1
� �� �
�
�
� , ( )( )C z C w E22
2
12� � , x wy wz y( ) ( ) ( ) ( )2 2 2 1� � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 21
Íåñëîæíûå âû÷èñëåíèÿ ïîêàçûâàþò, ÷òî äëÿ ðåàëèçàöèè ìåòîäà íà ÝÂÌ â îá-
ùåì ñëó÷àå íóæíî âûïîëíèòü ñ òî÷íîñòüþ äî ãëàâíîãî ÷ëåíà (2 22 2mn m n� �
� �3
2
3
3
2
3
3 3n m ) àääèòèâíûõ è ( )2 2 3
2
3
3
2
3
2 2 3 3mn m n n m� � � ìóëüòèïëèêàòèâíûõ
îïåðàöèé.
Òàêîé ïîäõîä ïîçâîëÿåò âû÷èñëÿòü äëÿ êàæäîãî íîâîãî íàáîðà y y( ) ( ),1 2 íåèç-
âåñòíûå x x( ) ( ),1 2 , âûïîëíèâ âñåãî ( )2 22 2n m� àðèôìåòè÷åñêèõ îïåðàöèé ñëîæåíèÿ
è óìíîæåíèÿ.
Ðàññìîòðèì òåïåðü ñëó÷àé, êîãäà ýëåìåíòû ñèñòåìû (1) çàâèñÿò îò âðåìåíè,
ò.å.
x t A x t A x t y t
x t A x
( ) ( ) ( ) ( )
( )
( ) ( ) ( ) ( ),
( )
1
11
1
12
2 1
2
11
� � �
� ( ) ( ) ( )( ) ( ) ( ),1
12
2 2t A x t y t� �
�
�
�
(20)
ãäå
a t a t i j m ni j i j k
k
k
l
, , ,( ) ( , , , , )� � �
�
� 1 2
0
� , (21)
y t y t i n
i i k
k
k
l
( )
,
( )( ) ( , , , )1 1
0
1 2� �
�
� � , (22)
y t y t i n n m n
i i k
k
k
l
( )
,
( )( ) ( , , , )2 2
0
1 2� � � � �
�
� � . (23)
Ïî àíàëîãèè ñ ïðåäûäóùèì ñëó÷àåì ñèñòåìà (20) ìîæåò áûòü ïðèâåäåíà ê âèäó
G t G t
G t G t
x t
x t
11 12
21 22
1
2
( ) ( )
( ) ( )
( )
( )
( )
( )
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
H
H
( )
( )
1
2
, (24)
ãäå
G t
A t A t
A t A t
E
E
H
( )
( ) ( )
( ) ( )
,�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�11 12
21 22
0
0
( )
( )
( )
( )
1
2
1
2H
y
y
�
�
�
�
�
�
�
� � �
�
�
�
�
�
�
�
� . (25)
 îáùåì âèäå (24) ìîæíî çàïèñàòü êàê
G t X t H t( ) ( ) ( )� . (26)
Ðåøåíèå ñèñòåìû (26) áóäåì èñêàòü â âèäå
X
X t
v t
k
k
k
m n l
k
k
k
m n l
� �
�
�
�
�
�
( )
( )
( )
1
0
0
, (27)
ãäå X k — ÷èñëîâûå ìàòðèöû ðàçìåðà ( ) ( )m n m n�
� , à vk — ÷èñëà.
Òîãäà ñèñòåìó (26) ìîæíî çàïèñàòü ñëåäóþùèì îáðàçîì:
G t X t t G t G t Gl l l( ) ( ) (� � � �� �
0
1
1
2
2 �
� � � � � �� �
� � � � �t G t G G t X t X tl l l
m n l m n l m n l2
2
1
1 0
1
1)( ( ) ( ) ( ) 2
2X ��
� �� � � � � �� � �
� �t X X t H t H t Hm n l m n l
l l l1
1 0
1
1
2
2( ) ( ) ) (
�� � � � �� �
� � � � �t H t H H t v t v tl l l
m n l m n l m n l2
2
1
1 0
1
1)( ( ) ( ) ( ) 2
2v ��
�� � �� � � �t v t v vl m n l m n l
2
2
1
1( ) ( ) ) .
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Ïðèðàâíèâàÿ êîýôôèöèåíòû ïðè îäèíàêîâûõ ñòåïåíÿõ t, ïîëó÷àåì ñèñòåìó
( )[ ( ) ]n m l n m� � � �1 1 óðàâíåíèé ñ [( ) ]( )n m l n m� � � �1 1 íåèçâåñòíûìè
G X H v
G X G X H v H v
G X
0 0
1
0 0
0 1
1
1 0
1
0 1 1 0
0 2
0
0
( )
( ) ( )
(
,
( ) ,
� �
� � � �
1
1 1
1
2 0
1
0 2 1 1 2 0 0) ( ) ( ) ( ) ,� � � � � �G X G X H v H v H v
����������������������
�����������
G X H vs p s
s
l
s p s
s
l
�
�
�
�
� �� �( ) ,1
0 0
0
�����������
G X G X H vl n m l l n m l l n� � � � � �� �1
1
1
1
1( )
( )
( )
( )
(( m l l n m l
l n m l l n m l
H v
G X H v
) ( )
( )
( )
( )
) ,
.
� �
� �
�
�
�
�
�
�
� �
� �
1
1
0
0
�
�
�
�
�
�
�
�
�
�
�
(28)
Äëÿ áîëüøåé íàãëÿäíîñòè äàëüíåéøèõ âûêëàäîê è îáëåã÷åíèÿ àíàëèçà ñèñòå-
ìó (28) áëî÷íîãî âèäà çàïèøåì â ìàòðè÷íîì âèäå:
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G G
G
l l
l l
l l
0
1
2
0
1
1
0
1
1
1
0
1 0
1
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
�
�
�
G
G
G
G G
G
G
G
G
G
G
G
G
l l
l l
l l
l l
0
1
1
1 0
1
1
0
1
�
�
�
�
G
G
G
G
G
G
H
H
H
H
H
H
H
H
H
l l
l
l
l
l
1 0
1
1
0
1
0
1
0
1
�
� � � �
�
�
�
�
� �
�
�
�
�
�
�
�
� 2
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
Hl
�
�
�
�
�
�
�
�
�
�
� �
� �
X
X
X
X
X
X
n m
n m
n m
0
1
1
1
2
1
1
1
1
2
1
( )
( )
( )
( )
( )
( )
�
�
�
�
�
X
v
v
v
v
v
n m l
n m l
n m l
( )( )
( )
( )( )
( )( )
� �
� � �
� �
�
�
1
1
0
1
2
1 1
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
� 0.
Åñëè äàííóþ ñèñòåìó ðàññìàòðèâàòü êàê ïëîòíî çàïîëíåííóþ, òî ìîæíî ïîëó-
÷èòü àëãîðèòìû ñî ñëîæíîñòüþ ïîðÿäêà O l n m( ( ) )3 6� . Ïîýòîìó áîëåå ýôôåêòèâ-
íûå ñïîñîáû ìîãóò áûòü ïîëó÷åíû ëèøü ñ ó÷åòîì ñïåöèôèêè çàïîëíåíèÿ ÷èñëåí-
íîé ñèñòåìû.
Ñõåìà ðàçðåçàíèÿ. Ïîäåëèì ìàòðèöó ñèñòåìû (28) íà áëîêè:
D
D
D
D
11
21
12
22
|
|
|
�� � � ,
ãäå D11 — êâàäðàòíàÿ ìàòðèöà ðàçìåðà ( )( )n m l� � �1 2 , à D D12 21, , D22 — ïðÿ-
ìîóãîëüíûå ìàòðèöû ñîîòâåòñòâóþùèõ ðàçìåðîâ.
Áåç îãðàíè÷åíèÿ îáùíîñòè ïðåäïîëîæèì, ÷òî ìèíîð D11 îòëè÷åí îò íóëÿ (äëÿ
ýòîãî äîñòàòî÷íî, ÷òîáû âûïîëíÿëîñü óñëîâèå det G0 0 ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 23
Ïóñòü, íàïðèìåð, v n m l( )� �1, òîãäà çàïèøåì íåîäíîðîäíóþ ñèñòåìó:
D D
D D
Q
Q
B
B
11 12
21 22
1
2
1
2
�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
��
�
�
�� . (29)
Ðåøåíèÿ ñèñòåìû (29) ñ òî÷íîñòüþ äî ìíîæèòåëÿ ñîâïàäàþò ñ ðåøåíèÿìè
ñèñòåìû (28). Íà îñíîâå ôîðìóëû Øóðà [8] âåêòîð Q2 ìîæåò áûòü îïðåäåëåí èç
ñèñòåìû óðàâíåíèé
( )D D D D Q B D D B22 21 11
1
12 2 2 21 11
1
1� � �� � . (30)
Ïîñëå îïðåäåëåíèÿ Q2 ìîæíî ïåðåõîäèòü ê âû÷èñëåíèþ Q1 èç ñèñòåìû
D Q B D Q11 1 1 12 2� � . (31)
Òàêèì îáðàçîì, âû÷èñëåíèå íåèçâåñòíûõ Q1 è Q2 â ñèñòåìå (29) ìîæåò áûòü
ñâåäåíî ê ðåøåíèþ ñèñòåì (30) è (31) ìåíüøåãî ïîðÿäêà.
Îñòàíîâèìñÿ áîëåå äåòàëüíî íà âûïîëíåíèè êàæäîãî çâåíà àëãîðèòìà è ïðîâå-
äåì îöåíêó âû÷èñëèòåëüíûõ çàòðàò äàííîé ñõåìû íà êàæäîì øàãå ðåàëèçàöèè.
Ýòàï 1 (âû÷èñëåíèå D D
11
1
12
� è D B
11
1
1
� ). Ðàññìîòðèì ñíà÷àëà ïðîöåññ âû÷èñëå-
íèÿ ïðîèçâåäåíèÿ D D
11
1
12
� . Êàê èçâåñòíî [9], äëÿ ýòîãî äîñòàòî÷íî äëÿ âñåõ
i n m l� �1 2, , , ( )� íàéòè ðåøåíèÿ ñèñòåì âèäà
G
G G
G G G
G G G Gl l l
0
1 0
2 1 0
1 2 0
0 0 0 0
0 0 0
0 0
0
� �
� �
� �
� � � � � � �
� �
�
� �
� � � � � �
� �0 0 0 0 0
0
1
2
G
W
W
W
i
i
i
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
( )
( )
( )
( )
( )
( )
�
�
�W
W
B
B
l
i
n m l
i
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
0
0
0
0
l
0
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
. (32)
Ïî òèïó çàïîëíåíèÿ D11 — áëî÷íî-òðåóãîëüíàÿ êâàäðàòíàÿ ìàòðèöà êëåòî÷-
íî-òåïëèöåâîãî òèïà. Ñ ó÷åòîì ýòîãî îáñòîÿòåëüñòâà íåòðóäíî ñäåëàòü âûâîä, ÷òî
äîñòàòî÷íî ðåøèòü ñèñòåìó
G
G G
G G G
G G G Gl l l
0
1 0
2 1 0
1 2 0
0 0 0 0
0 0 0
0 0
0
� �
� �
� �
� � � � � � �
� �
�
� �
� � � � � �
� �0 0 0 0 0
0
1
2
G
W
W
W
i
i
i
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
( )
( )
( )
( )
( )
( )
�
�
W
W
B
B
B
B
l
i
n m l
i
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
0
1
2
3
0
�
Bl
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
. (33)
Ïîñëå âû÷èñëåíèÿ W j n m l
j
( ) ( , ,... , ( ) )1 1 2� � îñòàâøèåñÿ íåèçâåñòíûå W
j
i( )
( , ,... , ( ) ; , , ,... , ( ) )i n m l j n m l� � � �2 3 0 1 2 ìîæíî îïðåäåëèòü èç ñîîòíîøåíèé
W W W
W W
W W
i i
i
i
i
i i
i
i i
0 1 1
0
1 1
0( ) ( ) ( )
( ) ( )
( ) ( )
,
,
,
� � � �
�
�
�
�
�
!!!!
�
�
�
�
�
�
�
�
�
� � � �
.......
.
( )
( )
( )
( )W W
n m l
i
n m l i
i
(34)
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Ïîäñ÷èòàåì êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé, íåîáõîäèìûõ äëÿ ðåøåíèÿ
ñèñòåìû (28). Êàê áûëî îòìå÷åíî, åå ìàòðèöà ÿâëÿåòñÿ êëåòî÷íî-òåïëèöåâîé è, êðî-
ìå òîãî, áëî÷íî-òðåóãîëüíîé è ëåíòî÷íîé. Äëÿ ðåøåíèÿ ñèñòåìû (34) çàïèøåì àíà-
ëîã ñîîòâåòñòâóþùåãî ìåòîäà Å.Å. Òûðòûøíèêîâà [9], àäàïòèðîâàâ åãî äëÿ
êîíêðåòíîé öåëè.
Ââåäåì â ðàññìîòðåíèå ìàòðèöû
U
G
G G
G G G G
V
l l l
�
�
�
�
�
�
��
�
�
�
�
�
��
�
� �
0
1 0
1 2 0
0 0 0
0 0
�
�
� � � � �
�
,
0
0 0
0 0 0 0
1 1
2
G G G
G G
l l
l
��
�
�
�
�
��
�
�
�
�
�
��
�
�
� � � � �
�
.
Òîãäà âñëåäñòâèå èõ îïðåäåëåíèÿ G ìîæíî çàïèñàòü êàê áëî÷íî-äâóõäèàãîíàëü-
íóþ ìàòðèöó
G
U
V U
V U
�
�
�
�
�
�
��
�
�
�
�
�
��
0 0 0 0
0 0 0
0 0 0
�
�
� � � � � �
�
. (35)
 ñîîòâåòñòâèè ñ (33) ââåäåì òàêæå ñëåäóþùèå ïðåäñòàâëåíèÿ î âåêòîðíûõ
ñòîëáöàõ W è B:
W
W
W
W
B
B
B
Bn m n m
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
( )
( )
( )
( )
( )
( )
,
1
2
1
2
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
.
Ñ ó÷åòîì (35) ìîæíî çàïèñàòü:
W U B
W B U VW
( ) ( )
( ) ( ) ( )
,
,
..................
1 1 1
2 2 1 1
�
� �
�
�
..................
.( ) ( ) ( )W B U VWn m n m n m� � � � �� �
�
�
�
�
�
1 1
�
�
(36)
 ñîîòâåòñòâèè ñ ââåäåííûìè îáîçíà÷åíèÿìè ìàòðèöà U ÿâëÿåòñÿ íèæíåé
òðåóãîëüíîé, ïîýòîìó ìîæíî ñîñðåäîòî÷èòü âíèìàíèå íà àëãîðèòìå âû÷èñëåíèÿ
ýëåìåíòîâ U �1. Êàê èçâåñòíî [9], îáðàòíàÿ ìàòðèöà äëÿ ëåâîé òåïëèöåâîé ìàòðèöû
îñòàåòñÿ òåïëèöåâîé ëåâîé òðåóãîëüíîé, ò.å. èìååò âèä
U
G
G G
G G G G
l l l
�
�
� �
�
�
�
�
� �
�
�
1
0
1
1
1
0
1
1
1
1
2
1
0
1
0 0 0
0 0
�
�
� � � � �
��
�
�
�
�
�
�
�
�
�
�
�
�
. (37)
Ïðåäïîëîæèì, ÷òî l �1 ÿâëÿåòñÿ ñòåïåíüþ äâîéêè. Òîãäà ïðîöåññ ïîèñêà U �1
ëåãêî ñâîäèòñÿ ê îáðàùåíèþ åe âåäóùåé ïîäìàòðèöû Ul / 2 , êîòîðàÿ èìååò âäâîå
ìåíüøèé ïîðÿäîê. Äåéñòâèòåëüíî, ñîãëàñíî (37) íàõîäèì
U
G
G G
G G G
l
l l l
/
/ / /
2
1
0
1
1
1
0
1
2
1
2 1
1
2
0 0 0
0 0�
�
� �
�
�
�
�
�
�
�
� � � � �
2
1
0
1� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�� G
. (38)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 25
Ìàòðèöà U
l /2
1� — âåäóùàÿ ïîäìàòðèöà ìàòðèöû U �1. Îíà èìååò ïîëîâèíó ýëå-
ìåíòîâ, êîòîðûå îïðåäåëÿþò ìàòðèöó U �1. ×òîáû íàéòè âòîðîþ ïîëîâèíó, ðàñ-
ñìîòðèì ñëåäóþùåå ñîîòíîøåíèå:
G
G
G
G
G
l
l
l
/
( )
/
( )
( )
2 1
1
2 2
1
1
0
1 0 0
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
0
1
2
1
2 1
1
0
1
2
0� �
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
G
G G G
G
l l
l
�
� � � �
�
/ /
/ �
� �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
2 2 2 1
1 2 1
0 0
0
�
�
� � � �
�
G G
G G G
l l
l l l
/ /
/
G
G
G
l
0
1
1
1
2
1
( )
( )
/
( )
.
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
(39)
 ñîîòâåòñòâèè ñ (38) è (39) îáðàùåíèå òåïëèöåâîé òðåóãîëüíîé ìàòðèöû ïî-
ðÿäêà l ñâîäèòñÿ ê ðåøåíèþ àíàëîãè÷íîé çàäà÷è äëÿ ìàòðèöû ïîðÿäêà l / 2 è âûïîë-
íåíèþ óìíîæåíèÿ íà áëî÷íûé âåêòîð òåïëèöåâûõ ìàòðèö ïîðÿäêà l / 2 .
Ïðè ýòîì îäíî òàêîå óìíîæåíèå ìîæåò áûòü ðåàëèçîâàíî ñ ïîìîùüþ
3 2( )n m� äèñêðåòíûõ ïðåîáðàçîâàíèé Ôóðüå, ò.å. ñ çàòðàòîé 3 2 2
2/ ( )n m l l� log
îïåðàöèé óìíîæåíèÿ è 3 2
2( )n m l l� log îïåðàöèé ñëîæåíèÿ [9].
Òàêèì îáðàçîì, â ïðåäëîæåííîì ðåêóðñèâíîì àëãîðèòìå êîëè÷åñòâî îïåðàöèé
óìíîæåíèÿ îïðåäåëÿåòñÿ ïî ôîðìóëå
Q n m l l
l l l l
� � � � � """
�
�
�
�
�
�
�
�
3
2 2 2 2
2
2 2
2
2
2
( ) log log log .
Âûðàæåíèå â êâàäðàòíûõ ñêîáêàõ ðàâíî 2 2 22l n mlog (( ) / )� � , ïîýòîìó
Q n m l l� �6 2( ) log 2 . Êîëè÷åñòâî îïåðàöèé ñëîæåíèÿ-âû÷èòàíèÿ âäâîå áîëüøå.
Ñëåäóåò îòìåòèòü, ÷òî êîãäà l íå ÿâëÿåòñÿ ñòåïåíüþ äâîéêè, òî ìîæíî ñ÷èòàòü
U âåäóùåé ïîäìàòðèöåé íåêîòîðîé òðåóãîëüíîé òåïëèöåâîé ìàòðèöû, ïîðÿäîê êî-
òîðîé ðàâåí ñòåïåíè äâîéêè. Íàéäÿ îáðàòíóþ åé ìàòðèöó, íàéäåì òàêæå U �1.
Èòàê, â äàëüíåéøåì ìîæíî ïîëàãàòü, ÷òî l — ñòåïåíü äâîéêè. Òîãäà â ñîîòâå-
òñòâèè ñ ðàññìîòðåííûì àëãîðèòìîì äëÿ íàõîæäåíèÿ U �1 íóæíî âûïîëíèòü
6 2( )n m l l� log 2 îïåðàöèé óìíîæåíèÿ è 12 2( )n m l l� log 2 îïåðàöèé ñëîæåíèÿ. Ñîã-
ëàñíî (28) âû÷èñëåíèå W ñâÿçàíî ñ ðåàëèçàöèåé ( )2 1l � óìíîæåíèé íà «áëî÷íûé âåê-
òîð» òåïëèöåâûõ ìàòðèö áëî÷íîãî ïîðÿäêà íå âûøå l, ñðåäè êîòîðûõ ëèøü ÷åòûðå
ðàçíûõ.  òàêîì ñëó÷àå íåîáõîäèìî âûïîëíèòü ñ òî÷íîñòüþ äî ãëàâíîãî ÷ëåíà
[ ( )4 3
2n m l� �log 12 2( ) log ]n m l l� óìíîæåíèé è [ ( ) ( ) ]8 243n m l n m l l� � �log log2 2
ñëîæåíèé.
Ó÷èòûâàÿ (32), ìîæíî çàïèñàòü:
D D
W
W W
W W W
11
1
12
0
1
1
1
0
1
2
1
1
1
0
1
0 0 0 0
0 0 0
� �
( )
( ) ( )
( ) ( ) ( )
� �
� �
� �
� � � � � � �
� �
� � � � � � �
0 0
01
1
1
2
1
0
1W W W W
W
l l l
n m
( ) ( ) ( ) ( )
(
� �
� )
( )
( )
( )
( )
( )
( )
( ) ( )
l n m l n m l n m l l
W W W W1
1
1
2
1 1
0
1
� � � � � �
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
(40)
Íåòðóäíî óáåäèòüñÿ, ÷òî D B W W W
l11
1
1 0
1
1
1 10 0� � ( )( ) ( ) ( )
� �
T , ïðè÷åì W
i
( )1 —
âåêòîðû ðàçìåðíîñòè ( )n m� . Òàêèì îáðàçîì, äëÿ îïðåäåëåíèÿ D B
11
1
1
� íå íóæíî âû-
ïîëíÿòü äîïîëíèòåëüíûõ âû÷èñëåíèé.
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Ýòàï 2 (âû÷èñëåíèå D D B21 11
1
1( )� è D D D21 11
1
12( )� ). Âû÷èñëåíèå ïðîèçâåäåíèÿ
ìàòðèö D D B21 11
1
1( )� ìîæíî âûïîëíèòü ïî ïðåäûäóùåé ñõåìå, çàòðàòèâ íå áîëåå
÷åì ( )n m l� 2 2 îïåðàöèé óìíîæåíèÿ è ñëîæåíèÿ. Àëãîðèòì âû÷èñëåíèÿ
D D D21 11
1
12( )� âñëåäñòâèå áîëåå òùàòåëüíîãî èññëåäîâàíèÿ ìîæåò áûòü ñóùåñòâåí-
íî óñêîðåí. Äëÿ ýòîãî ïðîèçâåäåíèå äâóõ ìàòðèö
0 0
0 0 0
0 0 0 0
1 3 2 1
4 3 2
5 4 3
� �
� �
� �
� � � � � � � � �
G G G G G
G G G G
G G G
l l
l
�
0 0 0 0 0
0 0 0 0 0 0
1� �
� �
G G
G
l l
l
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
��
W
W W
W W W
0
1
1
1
0
1
2
1
1
1
0
1
0 0 0 0
0 0 0
0 0
( )
( ) ( )
( ) ( ) ( )
� �
� �
� �
� � � � � � �
� �
� � � � � � �
W W W W
W W
l l l
n m l n
( ) ( ) ( ) ( )
( )
( )
(
1
1
1
2
1
0
1
1
0
� �
� � � � � � � �
�
�
�
�
�
�
�
�
m l n m l n m l l l
W W W
)
( )
( )
( )
( )
( ) ( )
1
1
2
1 1
1
1
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
áóäåì âû÷èñëÿòü èíà÷å, ÷åì â ïðåäûäóùåé ñõåìå. Äëÿ óìíîæåíèÿ ñòîëáöà
( ( ) ( ) ( ) ( )
( )
( )
( )
( )W W W W W W
l l l n m n m l0
1
1
1 1
1
1
1 1
1 1
� � �
� � � � �
)T íà êëåòî÷íî-òåïëèöåâó
ìàòðèöó, çàïèñàííóþ â ïðîèçâåäåíèè ñëåâà, ìîæíî èñïîëüçîâàòü áûñòðîå ïðåîá-
ðàçîâàíèå Ôóðüå. Äëÿ åãî ðåàëèçàöèè íóæíî âûïîëíèòü 4 2( )n m l l� log 2 îïåðà-
öèé óìíîæåíèÿ è 4 2( )n m l l� log 2 îïåðàöèé ñëîæåíèÿ. Â ðåçóëüòàòå áóäóò íàéäå-
íû âñå ïîääèàãîíàëüíûå ýëåìåíòû èñêîìîé ìàòðèöû.
Ïî àíàëîãèè äëÿ íàõîæäåíèÿ âñåõ íàääèàãîíàëüíûõ ýëåìåíòîâ ïðîèçâåäåíèÿ
äîñòàòî÷íî óìíîæèòü ñòðîêó
( )0 0 0 1 2 1� �G G G Gl l� (41)
íà êàæäûé ñòîëáåö âòîðîé ìàòðèöû. Òîãäà ïðè óìíîæåíèè (41) íà âòîðîé ñòîë-
áåö âòîðîé ìàòðèöû áóäóò â êà÷åñòâå ïðîìåæóòî÷íûõ âåëè÷èí âû÷èñëåíû
è ýëåìåíòû ïåðâîé íàääèàãîíàëè. Ïðè óìíîæåíèè ýòîé ñòðîêè íà òðåòèé ñòîë-
áåö â ïðîöåññå âû÷èñëåíèé áóäóò íàéäåíû òàêæå âñå ýëåìåíòû âòîðîé íàääèàãî-
íàëè è ò.ä. Âñåãî äëÿ âûïîëíåíèÿ ýòîé ïðîöåäóðû ñ ïðèìåíåíèåì áûñòðîãî ïðå-
îáðàçîâàíèÿ Ôóðüå íóæíî âûïîëíèòü 4 2( ) ( )n m l n m l� �log 2 îïåðàöèé óìíîæå-
íèÿ è 4 2( ) ( )n m l n m l� �log 2 îïåðàöèé ñëîæåíèÿ.
 ðåçóëüòàòå âûïîëíåíèÿ îïèñàííûõ îïåðàöèé íàéäåíà ìàòðèöà G ðàçìåðà
( ) ( )n m l n m l�
� îáùåãî âèäà
G
G G G
G G G
G G G
l
l
l l ll
*
* * *
* * *
* * *
�
�
�
�
�
11 12 1
21 22 2
1 2
�
�
� � � �
�
�
�
�
�
�
�
�
�
�
�
,
êîòîðàÿ áóäåò èñïîëüçîâàíà â ïðîöåññå äàëüíåéøèõ âû÷èñëåíèé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 27
Ýòàï 3 (îïðåäåëåíèå Q2 ). Íà ýòîì ýòàïå ñíà÷àëà íóæíî âû÷èñëèòü âåëè÷èíû
[ ( )]D D D D22 21 11
1
12� � è [ ( )]B D D B2 21 11
1
1� � . Êàê áûëî ïîêàçàíî íà ýòàïå 2 ðåàëèçà-
öèè àëãîðèòìà, D D D G21 11
1
12( ) *� � — ìàòðèöà ðàçìåðà ( ) ( )n m l n m l�
� , à
� ��D D B B21 11
1
1( ) * — âåêòîð ðàçìåðíîñòè ( )n m l� . Ïîýòîìó äëÿ âû÷èñëåíèÿ
D D D D22 21 11
1
12� �( ) äîñòàòî÷íî âûïîëíèòü ( )n m l� 2 2 îïåðàöèé ñëîæåíèÿ, à äëÿ íà-
õîæäåíèÿ B D D B2 21 11
1
1� �( ) — ( )n m l� îïåðàöèé ñëîæåíèÿ. Íåïîñðåäñòâåííî äëÿ
îïðåäåëåíèÿ Q2 èç ñèñòåìû ( )n m l� -ãî ïîðÿäêà ñ ( )n m l� íåèçâåñòíûìè çàòðà÷åíî
O n m l(( ) )� � îïåðàöèé. Ïðè èñïîëüçîâàíèè àëãîðèòìà îòñå÷åííûõ ñèñòåì � � 3, äëÿ
áûñòðûõ ñõåì òèïà Ô. Øòðàññåíà � � log 2 7, à äëÿ íîâåéøèõ ìåòîäîâ åùå ìåíüøå —
� � 2 3176, .
Ýòàï 4 (îïðåäåëåíèå Q1). Íà ýòîì ýòàïå ñíà÷àëà íåîáõîäèìî âû÷èñëèòü ïðà-
âóþ ÷àñòü B D Q1 12 2� ñèñòåìû (31). Äëÿ åå íàõîæäåíèÿ ìîæíî âîñïîëüçîâàòüñÿ
ïðåäûäóùåé ñõåìîé, çàòðàòèâ ( ) /n m l� 2 2 2 îïåðàöèé óìíîæåíèÿ è òàêîå æå êîëè-
÷åñòâî îïåðàöèé ñëîæåíèÿ. Âû÷èñëåíèå Q1 ìîæíî ïðîâåñòè è ïî ñõåìå, îïèñàííîé
íà ýòàïå 1. Èòàê, ïðè èñïîëüçîâàíèè ïðèâåäåííîãî àëãîðèòìà áóäåò çàòðà÷åíî
4 2( )n m l l� log 2 îïåðàöèé óìíîæåíèÿ è 8 2( )n m l l� log 2 îïåðàöèé ñëîæåíèÿ.
Òàêèì îáðàçîì, äëÿ ïîëíîé ðåàëèçàöèè àëãîðèòìà âû÷èñëåíèÿ z t( ) ( )1 íóæíî
âûïîëíèòü Ñ n m l n m l l n m l n m l1
3 2
24 4[( ) ] ( ) ( ) ( )� � � � � �� log log2 ìóëüòèïëèêà-
òèâíûõ îïåðàöèé è Ñ n m l n m l l n m l n m l2
3 2
28 8[( ) ] ( ) ( ) ( )� � � � � �� log log2 àääè-
òèâíûõ äåéñòâèé íà ÝÂÌ.
Êîíñòàíòû C C1 2, è � çàâèñÿò îò âûáðàííîãî àëãîðèòìà ðåøåíèÿ ñèñòåì ëè-
íåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé.
Ïîñëå âû÷èñëåíèÿ êîýôôèöèåíòîâ X
k
( )1 è � k ( , , , ( ) )k n m l� �01 � â (27) ïåðå-
ñ÷åò X t( ) äëÿ ïðîèçâîëüíîãî t ïîòðåáóåò íå áîëåå ( )n m l� 3 îïåðàöèé ñëîæåíèÿ è
( )n m l� 3 îïåðàöèé óìíîæåíèÿ.
 ðàáîòå ïðåäëîæåíû ýôôåêòèâíûå ñ òî÷êè çðåíèÿ âû÷èñëèòåëüíîé ìàòåìàòè-
êè êîìïüþòåðíûå àëãîðèòìû äëÿ ëèíåéíûõ áàëàíñîâûõ ìîäåëåé ýêîëîãî-ýêîíîìè-
÷åñêîãî âçàèìîäåéñòâèÿ, à òàêæå ïðîâåäåíà îöåíêà ýôôåêòèâíîñòè èõ ïðèìåíåíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. à ð è ã î ð ê ³ â  . Ñ . Ìîäåëþâàííÿ åêîíîì³êè. ×. 1: Íàâ÷. ïîñ³á. — ×åðí³âö³: Ðóòà, 2006. — 124 ñ.
2. à ð è ã î ð ê ³ â  . Ñ . ,  å ð ñ ò ÿ ê À .  . Ïðîãíîçóâàííÿ ñèñòåìè çáàëàíñîâàíèõ ö³í íà îñíîâ³ ìîäåë³
Ëåîíòüºâà-Ôîðäà // Íàóê. â³ñí. Ëüâ³â. íàö. óí-òó ³ìåí³ ²âàíà Ôðàíêà. Ïðîáëåìè åêîíîì³÷íî¿
ê³áåðíåòèêè / Çà ðåä. ïðîô. Â.Ì. Âîâêà. — Ëüâ³â: ²íòåðåêî, 2007. — 16 (ñïåöâèïóñê). — Ñ. 61–68.
3. à ð è ã î ð ê ³ â  . Ñ . Ìîäåëþâàííÿ åêîëîãî-åêîíîì³÷íî¿ âçàºìî䳿: Íàâ÷. ïîñ³á. — ×åðí³âö³: Ðóòà,
2007. — 84 ñ.
4. Ë ÿ ø å í ê î ² . Ì . Åêîíîì³êî-ìàòåìàòè÷í³ ìåòîäè òà ìîäåë³ ñòàëîãî ðîçâèòêó. — Ê.: Âèùà øê., 1999.
— 236 ñ.
5. à ð è ã î ð ê ³ â  . Ñ . Ìîäåëþâàííÿ åêîíîì³êè. ×. 2: Íàâ÷. ïîñ³á. — ×åðí³âö³: Ðóòà, 2006. — 100 ñ.
6. Í å ä à ø ê î â ñ ü ê è é Ì . Î . , Ê î â à ë ü ÷ ó ê Î . ß . Îá÷èñëåííÿ ç �-ìàòðèöÿìè. — Êè¿â: Íàóê.
äóìêà, 2007. — 294 ñ.
7. Í å ä à ø ê î â ñ ü ê è é Ì . Î . Øâèäêà ñõåìà ðîçâ’ÿçàííÿ äëÿ ñèñòåì ëiíiéíèõ àëãåáðà¿÷íèõ ðiâíÿíü
ç �-ìàòðèöÿìè // Äîï. ÍÀÍ Óêðà¿íè. Ñåð. À. — Êè¿â, 1995. — ¹ 4. — Ñ. 23–29.
8.  î å â î ä è í  .  . Âû÷èñëèòåëüíûå îñíîâû ëèíåéíîé àëãåáðû. — Ì.: Íàóêà, 1977. — 303 ñ.
9.  î å â î ä è í  .  . , Ò û ð ò û ø í è ê î â Å . Å . Âû÷èñëèòåëüíûå ïðîöåññû ñ òåïëèöåâûìè
ìàòðèöàìè. — Ì.: Íàóêà, 1987. — 320 ñ.
Ïîñòóïèëà 28.05.2009
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
|
| id | nasplib_isofts_kiev_ua-123456789-45122 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T05:55:04Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Недашковский, Н.А. Крошка, Т.И. 2013-06-07T19:05:57Z 2013-06-07T19:05:57Z 2010 Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия / Н.А. Недашковский, Т.И. Крошка // Кибернетика и системный анализ. — 2010. — № 1. — С. 17–28. — Бібліогр.: 9 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45122 519.86 Проаналізовано лінійні балансові моделі міжгалузевої еколого-економічної взаємодії та запропоновано комп’ютерні алгоритми для їх розв’язання. Обґрунтовано ефективність цих алгоритмів і можливості їх застосування на практиці. Linear balance models of intersectorial ecological-economics interaction are analyzed and new computer algorithms for solving them are proposed. The efficiency of these algorithms and the possibility of using them in practice are substantiated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия Обчислювальні алгоритми для лінійних балансових моделей міжгалузевої еколого-економічної взаємодії Computational algorithms for linear balance models of intersectorial ecological-economic interaction Article published earlier |
| spellingShingle | Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия Недашковский, Н.А. Крошка, Т.И. Кибернетика |
| title | Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия |
| title_alt | Обчислювальні алгоритми для лінійних балансових моделей міжгалузевої еколого-економічної взаємодії Computational algorithms for linear balance models of intersectorial ecological-economic interaction |
| title_full | Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия |
| title_fullStr | Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия |
| title_full_unstemmed | Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия |
| title_short | Вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия |
| title_sort | вычислительные алгоритмы для линейных балансовых моделей межотраслевого эколого-экономического взаимодействия |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45122 |
| work_keys_str_mv | AT nedaškovskiina vyčislitelʹnyealgoritmydlâlineinyhbalansovyhmodeleimežotraslevogoékologoékonomičeskogovzaimodeistviâ AT kroškati vyčislitelʹnyealgoritmydlâlineinyhbalansovyhmodeleimežotraslevogoékologoékonomičeskogovzaimodeistviâ AT nedaškovskiina občislûvalʹníalgoritmidlâlíníinihbalansovihmodeleimížgaluzevoíekologoekonomíčnoívzaêmodíí AT kroškati občislûvalʹníalgoritmidlâlíníinihbalansovihmodeleimížgaluzevoíekologoekonomíčnoívzaêmodíí AT nedaškovskiina computationalalgorithmsforlinearbalancemodelsofintersectorialecologicaleconomicinteraction AT kroškati computationalalgorithmsforlinearbalancemodelsofintersectorialecologicaleconomicinteraction |