Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов
Введено поняття власного полінома лінійного оператора, сформульовано алгоритм побудови власних поліномів і встановлено зв’язок між власними поліномами та поліноміальними інваріантами лінійних циклів програм. Основний результат роботи — побудова множини L-інваріантів циклів для операторів, жорданова...
Saved in:
| Date: | 2012 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84040 |
| 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: | Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов / М.С. Львов, В.А. Крекнин // Кибернетика и системный анализ. — 2012. — Т. 48, № 2. — С. 126-140. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84040 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-840402025-02-23T18:07:18Z Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов Нелінійні інваріанти лінійних циклів та власні поліноми лінійних операторів Nonlinear invariants for linear loops and eigenpolynomials of linear operators Львов, М.С. Крекнин, В.А. Программно-технические комплексы Введено поняття власного полінома лінійного оператора, сформульовано алгоритм побудови власних поліномів і встановлено зв’язок між власними поліномами та поліноміальними інваріантами лінійних циклів програм. Основний результат роботи — побудова множини L-інваріантів циклів для операторів, жорданова форма яких містить нетривіальні блоки. The authors introduce the concept of eigenpolynomial of a linear operator, outline an algorithm to develop eigenpolynomials, and establish a relationship between eigenpolynomials and polynomial invariants of linear cycles of programs. The main result of the article is construction of a set of L-invariant cycles for operators with a Jordan form that contain nontrivial blocks. 2012 Article Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов / М.С. Львов, В.А. Крекнин // Кибернетика и системный анализ. — 2012. — Т. 48, № 2. — С. 126-140. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84040 004.421.6 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Программно-технические комплексы Программно-технические комплексы |
| spellingShingle |
Программно-технические комплексы Программно-технические комплексы Львов, М.С. Крекнин, В.А. Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов Кибернетика и системный анализ |
| description |
Введено поняття власного полінома лінійного оператора, сформульовано алгоритм побудови власних поліномів і встановлено зв’язок між власними поліномами та поліноміальними інваріантами лінійних циклів програм. Основний результат роботи — побудова множини L-інваріантів циклів для операторів, жорданова форма яких містить нетривіальні блоки. |
| format |
Article |
| author |
Львов, М.С. Крекнин, В.А. |
| author_facet |
Львов, М.С. Крекнин, В.А. |
| author_sort |
Львов, М.С. |
| title |
Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов |
| title_short |
Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов |
| title_full |
Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов |
| title_fullStr |
Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов |
| title_full_unstemmed |
Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов |
| title_sort |
нелинейные инварианты линейных циклов и собственные полиномы линейных операторов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Программно-технические комплексы |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84040 |
| citation_txt |
Нелинейные инварианты линейных циклов и собственные полиномы линейных операторов / М.С. Львов, В.А. Крекнин // Кибернетика и системный анализ. — 2012. — Т. 48, № 2. — С. 126-140. — Бібліогр.: 15 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT lʹvovms nelinejnyeinvariantylinejnyhciklovisobstvennyepolinomylinejnyhoperatorov AT krekninva nelinejnyeinvariantylinejnyhciklovisobstvennyepolinomylinejnyhoperatorov AT lʹvovms nelíníjníínvaríantilíníjnihciklívtavlasnípolínomilíníjnihoperatorív AT krekninva nelíníjníínvaríantilíníjnihciklívtavlasnípolínomilíníjnihoperatorív AT lʹvovms nonlinearinvariantsforlinearloopsandeigenpolynomialsoflinearoperators AT krekninva nonlinearinvariantsforlinearloopsandeigenpolynomialsoflinearoperators |
| first_indexed |
2025-11-24T08:27:53Z |
| last_indexed |
2025-11-24T08:27:53Z |
| _version_ |
1849659619733929984 |
| fulltext |
ÓÄÊ 004.421.6
Ì.Ñ. ËÜÂÎÂ, Â.À. ÊÐÅÊÍÈÍ
ÍÅËÈÍÅÉÍÛÅ ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÖÈÊËÎÂ
È ÑÎÁÑÒÂÅÍÍÛÅ ÏÎËÈÍÎÌÛ ËÈÍÅÉÍÛÕ ÎÏÅÐÀÒÎÐÎÂ
Êëþ÷åâûå ñëîâà: ñòàòè÷åñêèé àíàëèç ïðîãðàìì, ïîëèíîìèàëüíûå èíâàðèàíòû öèêëîâ,
ñîáñòâåííûå ïîëèíîìû ëèíåéíûõ îïåðàòîðîâ, çàäà÷à àâòîìàòè÷åñêîé ãåíåðàöèè.
ÂÂÅÄÅÍÈÅ
Ïðîáëåìà ïîèñêà èíâàðèàíòîâ öèêëîâ â èìïåðàòèâíûõ ïðîãðàììàõ áûëà ïî-
ñòàâëåíà â ðàáîòàõ Ð. Ôëîéäà [1] è Ñ. Õîàðà [2] êàê êëþ÷åâàÿ ïðîáëåìà ïðî-
öåññà àíàëèçà ñâîéñòâ ïðîãðàìì.
Ñóùåñòâîâàíèå è ýôôåêòèâíîñòü àëãîðèòìîâ ãåíåðàöèè ïðîãðàììíûõ èíâà-
ðèàíòîâ çàâèñÿò îò ñâîéñòâ àëãåáð äàííûõ, ñ êîòîðûìè ðàáîòàåò ïðîãðàììà.
Èññëåäîâàíèÿ çàäà÷è àâòîìàòè÷åñêîé ãåíåðàöèè ïðîãðàììíûõ èíâàðèàíòîâ äëÿ
ðàçëè÷íûõ àëãåáð äàííûõ âûïîëíÿëèñü â Èíñòèòóòå êèáåðíåòèêè èìåíè
Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, íà÷èíàÿ ñ 70-õ ãîäîâ ïðîøëîãî âåêà. Èõ îñíîâ-
íûå ðåçóëüòàòû èçëîæåíû â [3, 4].  ðàáîòå [5] îïèñàí îáùèé àëãîðèòì âû÷èñëå-
íèÿ ïîëèíîìèàëüíûõ èíâàðèàíòîâ â ïðîèçâîëüíîé êîíòðîëüíîé òî÷êå ïðîãðàì-
ìû, îñíîâàííûé íà èòåðàöèîííîì ìåòîäå [3] è ìåòîäå âû÷èñëåíèÿ
ïîëèíîìèàëüíûõ èíâàðèàíòîâ îãðàíè÷åííîé ñòåïåíè.
 [6] îïèñàí àëãîðèòì âû÷èñëåíèÿ ïîëèíîìèàëüíûõ èíâàðèàíòîâ îãðàíè-
÷åííîé ñòåïåíè â ïðîãðàììàõ ñ ëèíåéíûìè öèêëàìè è ðåêóðñèâíûìè âûçîâàìè
ïðîöåäóð. Â [7] ïðåäëîæåí ìåòîä ïîñòðîåíèÿ íåëèíåéíûõ è, âîîáùå ãîâîðÿ, íå-
ïîëèíîìèàëüíûõ èíâàðèàíòíûõ ñîîòíîøåíèé äëÿ ëèíåéíûõ öèêëîâ. Ìåòîä èñ-
ïîëüçóåò ñîáñòâåííûå çíà÷åíèÿ è ñîáñòâåííûå âåêòîðû ëèíåéíîãî îïåðàòîðà
â òåëå öèêëà.  [8] èçëîæåíû àëãåáðàè÷åñêèå îñíîâû çàäà÷è ïîèñêà ïîëèíîìè-
àëüíûõ èíâàðèàíòîâ öèêëîâ. Îñíîâíîé ðåçóëüòàò ýòîé ðàáîòû — àëãîðèòì âû-
÷èñëåíèÿ âñåõ ïîëèíîìèàëüíûõ èíâàðèàíòîâ äëÿ öèêëîâ ñ òàê íàçûâàåìûìè ðàç-
ðåøèìûìè îïåðàòîðàìè ïðèñâàèâàíèÿ.  ÷àñòíîñòè, ðàçðåøèìûìè ÿâëÿþòñÿ àô-
ôèííûå îïåðàòîðû ñ ïîëîæèòåëüíûìè âåùåñòâåííûìè ñîáñòâåííûìè
çíà÷åíèÿìè.  [9] ïðåäëîæåí àëãîðèòì ïîèñêà èíâàðèàíòîâ íåêîòîðûõ êëàññîâ
ëèíåéíûõ öèêëîâ, îñíîâàííûé íà ïîñòðîåíèè ñèñòåìû ðåêóððåíòíûõ ñîîòíî-
øåíèé îò ïåðåìåííûõ öèêëà è ïàðàìåòðà n — ÷èñëà ïîâòîðåíèé öèêëà. Àëãîðèòì
èùåò ðåøåíèå ýòîé ñèñòåìû, çàâèñÿùåå îò n. Àëãîðèòì ðåàëèçîâàí â ïðîãðàììíîé
ñèñòåìå Òåîðåìà (Theorema System). Â [10, 11] ïðåäëîæåí íîâûé ìåòîä ïîñòðîå-
íèÿ íîâîãî êëàññà ïîëèíîìèàëüíûõ èíâàðèàíòîâ ëèíåéíûõ öèêëîâ, òàê íàçûâàå-
ìûõ L-èíâàðèàíòîâ. Íàñòîÿùàÿ ðàáîòà — ïðÿìîå ïðîäîëæåíèå [10, 11].
1. L-ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÎÒÎÁÐÀÆÅÍÈÉ
È ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÖÈÊËÎÂ
 [10, 11] ïðèâåäåíî îïðåäåëåíèå L-èíâàðèàíòà ëèíåéíîãî îïåðàòîðà A è óñòà-
íîâëåíà ñâÿçü ìåæäó L-èíâàðèàíòàìè è ïðîãðàììíûìè èíâàðèàíòàìè èòåðàöèîí-
íûõ öèêëîâ, â òåëå êîòîðûõ âûïîëíÿåòñÿ îïåðàòîð A. Ïîâòîðèì ýòè îïðåäåëåíèÿ.
Îïðåäåëåíèå 1. Ïóñòü W — n-ìåðíîå âåêòîðíîå ïðîñòðàíñòâî íàä ïîëåì ðà-
öèîíàëüíûõ ÷èñåë Q è Q — àëãåáðàè÷åñêîå çàìûêàíèå ïîëÿ Q. Ïóñòü
X x x
n
� ( , , )1 � — n-ìåðíûé âåêòîð ïåðåìåííûõ. Ðàöèîíàëüíàÿ ôóíêöèÿ
p X Q X( ) ( )� íàçûâàåòñÿ L-èíâàðèàíòîì ëèíåéíîãî îïåðàòîðà A W W: � , åñëè
äëÿ ëþáîãî âåêòîðà b W� èìååò ìåñòî ñîîòíîøåíèå
p Ab p b( ) ( )� . (1)
126 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
© Ì.Ñ. Ëüâîâ, Â.À. Êðåêíèí, 2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 127
Îïðåäåëåíèå 2. Ïóñòü X x x
n
� ( , , )1 � , b b b
n
� ( , , )1 � — äâà íàáîðà ïåðå-
ìåííûõ. Ëèíåéíûì öèêëîì ìû íàçûâàåì ôðàãìåíò èìïåðàòèâíîé ïðîãðàììû
âèäà
X := b;
While Q(X, b) do X := A*X
Çàìå÷àíèå 1. Îïåðàòîðû X:=b, X:=A*X èíòåðïðåòèðóþòñÿ êàê îäíîâðå-
ìåííûå ïðèñâîåíèÿ ïåðåìåííûì ëåâûõ ÷àñòåé çíà÷åíèé ïðàâûõ ÷àñòåé.  äàëü-
íåéøåì óñëîâèå Q(X,b) áóäåì èãíîðèðîâàòü, ñ÷èòàÿ ëèíåéíûé öèêë áåñêîíå÷-
íûì, à åãî âûïîëíåíèå — íåäåòåðìèíèðîâàííûì. Òàêèì îáðàçîì, ìû ðàññìàòðè-
âàåì öèêëû âèäà
X := b;
While True|False do X := A*X
Òåîðåìà 1. Åñëè p X r X q X( ) ( ) / ( )� — L-èíâàðèàíò ëèíåéíîãî îïåðàòîðà A,
òî ìíîãî÷ëåí r X q b q X r b( ) ( ) ( ) ( )� — èíâàðèàíò ëèíåéíîãî öèêëà íàä ïîëåì Q .
Òàêèå èíâàðèàíòû öèêëîâ áóäåì íàçûâàòü L-èíâàðèàíòàìè (ëèíåéíûõ öèêëîâ).
 [10, 11] èçëîæåíû ðåçóëüòàòû, ôàêòè÷åñêè ñâÿçàííûå ñ ñîáñòâåííûìè âåê-
òîðàìè îïåðàòîðà A
T
. Ñôîðìóëèðóåì îñíîâíîé ðåçóëüòàò ýòîé ðàáîòû.
Òåîðåìà 2. Ïóñòü � �1, ,�
m
— ñîáñòâåííûå çíà÷åíèÿ ëèíåéíîãî îïåðàòîðà
A è s s
m1, ,� — ñîîòâåòñòâóþùèå èì ñîáñòâåííûå âåêòîðû ñîïðÿæåííîãî îïåðà-
òîðà A
T
. Ïðåäïîëîæèì, ÷òî ñóùåñòâóþò òàêèå öåëûå ÷èñëà k k
m1, ,� , ÷òî
� �
1
1 1
k
m
k
m
� � �� . (2)
Òîãäà
p X s X s X
k
m
k
m( ) ( , ) ( , )� � �1
1
� (3)
— L-èíâàðèàíò ëèíåéíîãî îïåðàòîðà A.
Çàìåòèì, ÷òî â îáùåì ñëó÷àå íåâûðîæäåííûé ëèíåéíûé îïåðàòîð A â ïîäõî-
äÿùåì áàçèñå ìîæåò áûòü ïðåäñòàâëåí ìàòðèöåé — æîðäàíîâîé ôîðìîé [12, 13]:
A
J
J
J
m m
�
�
�
�
�
�
�
�
1 1
2 2
0 0
0 0
0 0
( )
( )
( )
�
�
�
�
�
� � � �
�
, (4)
ãäå J
i i
( )� — æîðäàíîâû êëåòêè ðàçíûõ ðàçìåðîâ. Æîðäàíîâà êëåòêà èìååò
âèä
J ( )�
�
�
�
�
�
�
�
�
�
�
�
�
0 0
0 0
0 1
0 0
�
�
�
�
. (5)
Òàêèì îáðàçîì, òåîðåìà 2 îòíîñèòñÿ òîëüêî ê òåì ñòðîêàì ìàòðèöû ëèíåé-
íîãî îïåðàòîðà A, êîòîðûå ñîîòâåòñòâóþò ñîáñòâåííûì âåêòîðàì A, ò.å. ê ñîâî-
êóïíîñòè ïîñëåäíèõ ñòðîê æîðäàíîâûõ êëåòîê J
i i
( )� , i m�1, ,� . Íèæå ðàñïðî-
ñòðàíèì ýòó òåîðåìó íà ïðîèçâîëüíûå íåâûðîæäåííûå ëèíåéíûå îïåðàòîðû,
ââåäÿ â ðàññìîòðåíèå æîðäàíîâû êëåòêè â öåëîì.
2. ÑÎÁÑÒÂÅÍÍÛÅ ÏÎËÈÍÎÌÛ ÆÎÐÄÀÍÎÂÛÕ ÊËÅÒÎÊ
Äëÿ àíàëèçà ëèíåéíûõ öèêëîâ ëèíåéíûé îïåðàòîð A ñëåäóåò ðàññìàòðèâàòü
êàê ëèíåéíîå ïðåîáðàçîâàíèå X AX
ïåðåìåííûõ X x x
n
� ( , , )1 � ëèíåéíîãî
ïðîñòðàíñòâà Q X
d
[| | ] îäíîðîäíûõ ïîëèíîìîâ íåêîòîðîé ñòåïåíè d. Ïðåîáðà-
çîâàíèå X AX
îïðåäåëÿåò ëèíåéíîå ïðåîáðàçîâàíèå ïðîñòðàíñòâà Q X
d
[| |]
â ñåáÿ (ãîìîìîðôèçì) T Q X Q X
A
d d
: [| | ] [| | ]� . Äëÿ p X Q X
d
( ) [| | ]� îíî çàäà-
íî ôîðìóëîé
T p X p AX
A
( ( )) ( )� .
Îïðåäåëåíèå 3. Ïîëèíîì p X Q X
d
( ) [| | ]� íàçûâàåòñÿ ñîáñòâåííûì ïîëèíî-
ìîì ëèíåéíîãî îïåðàòîðà A ñ ñîáñòâåííûì ÷èñëîì ��Q , åñëè p X( ) — ñîáñò-
âåííûé âåêòîð T
A
, ò.å. T p X p X
A
( ( )) ( )� � . Òàêèì îáðàçîì, ñîáñòâåííûé ïîëè-
íîì îïðåäåëÿåòñÿ ôîðìóëîé
p AX p X( ) ( )� � . (6)
Çàìå÷àíèå 2. Ïîíÿòèÿ ñîáñòâåííîãî ìíîãî÷ëåíà è L-èíâàðèàíòà ëèíåéíîãî
îïåðàòîðà — íåêîòîðûå àíàëîãè îñíîâíûõ ïîíÿòèé ãåîìåòðè÷åñêîé òåîðèè èíâà-
ðèàíòîâ, à èìåííî ïîíÿòèé îòíîñèòåëüíîãî è àáñîëþòíîãî èíâàðèàíòîâ ãðóïïû G
ïðåîáðàçîâàíèé âåêòîðíîãî ïðîñòðàíñòâà â òîì ñëó÷àå, êîãäà ýòà ãðóïïà îïðåäåëå-
íà êàê öèêëè÷åñêàÿ c îáðàçóþùèì ýëåìåíòîì A: G A A
A
�
� �
{� , , ,
2 1
E A A, , ,
2
�}
[14, 15].
Ïðèìåð 1. Ïóñòü s s s
n
� ( , , )1 � — ñîáñòâåííûé âåêòîð îïåðàòîðà A
T
è � —
åãî ñîáñòâåííîå çíà÷åíèå. Òîãäà ( , )s X s x s x
n n
� � �1 1 � — ñîáñòâåííûé ïîëè-
íîì îïåðàòîðà A ñ ñîáñòâåííûì ÷èñëîì �.
Ïðåäïîëîæèì, ÷òî ëèíåéíûé îïåðàòîð A ñîñòîèò èç îäíîé æîðäàíîâîé êëåò-
êè âèäà (5), êîòîðóþ îáîçíà÷èì J
n
( )� . Åñëè ðàçìåðû êëåòêè è åå ñîáñòâåííîå
çíà÷åíèå â äàííîì êîíòåêñòå íå èãðàþò ðîëè, èõ îáîçíà÷åíèÿ áóäåì èãíîðèðîâàòü,
îáîçíà÷àÿ îïåðàòîð ÷åðåç J. Ïðèâåäåì ðåøåíèå çàäà÷è ïîñòðîåíèÿ âñåõ ñîáñòâåí-
íûõ ïîëèíîìîâ æîðäàíîâîé êëåòêè J
n
( )� .
Ðàññìîòðèì âåêòîðíîå ïðîñòðàíñòâî U Q y z
d
� ( ) [| , | ]� îäíîðîäíûõ ìíîãî-
÷ëåíîâ ñòåïåíè d îò äâóõ ïåðåìåííûõ ( y è z) íàä ïîëåì Q( )� ðàöèîíàëüíûõ
ôóíêöèé îò ïåðåìåííîé �, äëÿ êðàòêîñòè îáîçíà÷åííîåU . Ýòî ïðîñòðàíñòâî èìå-
åò ðàçìåðíîñòü d �1 íàä ïîëåì Q( )� . Â ñàìîì äåëå, îäèí èç áàçèñîâ ýòîãî ïðî-
ñòðàíñòâà — ñèñòåìà ìîíîìîâ ( , , , , )y y z yz z
d d d d� �1 1
� . Ïóñòü
U y y z yz z
d d d d
�
� �
( , , , , )
1 1
� . (7)
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:
U z U yz z U y z z U U
d d d
k
k d k d
d0 1
1
� � � �
� �
( ), ( , ), , ( , , ), ,� � � . (8)
Ïóñòü T
J
— ëèíåéíîå ïðåîáðàçîâàíèå ïðîñòðàíñòâà U , äåéñòâóþùåå íà áà-
çèñå (7) ñëåäóþùèì îáðàçîì:
T y y z
J
d d
( ) ( )� �� , … , T y z y z z
J
k d k k d k
( ) ( ) ( )
� �
� �� � , … , T z z
J
d d d
( ) � � .
Îáîçíà÷èì S T E
J
d
� � � . Î÷åâèäíî, êàæäîå èç ïîäïðîñòðàíñòâU
k
, 0 � �k d,
èíâàðèàíòíî îòíîñèòåëüíî ëèíåéíîãî ïðåîáðàçîâàíèÿ S .
Ëåììà 1. Äëÿ ëþáîãî k, 0 1� � �k d , ñïðàâåäëèâû ñëåäóþùèå óòâåðæäåíèÿ:
1) ïîäïðîñòðàíñòâî U
k
ÿâëÿåòñÿ îáðàçîì ïîäïðîñòðàíñòâà U
k�1 ïîä äåé-
ñòâèåì ïðåîáðàçîâàíèÿ S , ò.å. � � � �
�
f f U S f U
k k
( ( ) )1 ;
2) ÿäðîì ïðåîáðàçîâàíèÿ S ÿâëÿåòñÿ ïîäïðîñòðàíñòâî U 0 , ò.å.
� � � �f f U S f( ( ) )0 0 .
Äîêàçàòåëüñòâî. Ïåðâîå óòâåðæäåíèå ëåììû äîêàæåì èíäóêöèåé ïî k. Íå-
ïîñðåäñòâåííî èç îïðåäåëåíèÿ S ñëåäóåò, ÷òî S z
d
( ) � 0. Êðîìå òîãî,
S yz y z z yz yz z yz
d d d d d d d d d
( ) ( )( )
� � � � �
� � � � � �
1 1 1 1 1
� � � � � �
d d d
z
� �
�
1 1
� .
128 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
Îòñþäà ñëåäóåò S U U( )1 0� . Òàêèì îáðàçîì, ïðè k � 0 ïåðâîå óòâåðæäåíèå
ëåììû âûïîëíÿåòñÿ. Ïðåäïîëîæèì ïî èíäóêöèè, ÷òî ýòî óòâåðæäåíèå ñïðà-
âåäëèâî ïðè íåêîòîðîì k, k d� �2 . Ðàññìîòðèì ïîäïðîñòðàíñòâî U
k�1
. Ïî
ïðåäïîëîæåíèþ èíäóêöèè S U U
k k
( )
�
�1 . Òàê êàê U U
k k� �
�1 2 , òî
U S U
k k
�
�
( )2 . Êðîìå òîãî,
S y z y z z y z
k d k k d k d k d k
( ) ( ) ( )
� � � � � � � � �
� � � �
2 2 2 2 2 2
� � �
� �
�
� � � �
C y z w
k
d k d k
2
1 1 1 1
� ,
ãäå w C y z C y z
k
d k d k
k
j d j k j d k j d k
� � � � �
�
� �
�
� � � � � � �
2
2 2
2
2 2
� � �� �
�2
z
d
. Î÷å-
âèäíî, ÷òî w U S U
k k
� �
�
( )2 . Îòñþäà ñëåäóåò, ÷òî C y z
k
d k d k
�
� � � �
�
2
1 1 1 1
�
� � �
� � �
�
S y z w S U
k d k
k
( ) ( )
2 2
2 . Ïîýòîìó y z S U
k d k
k
� � �
�
�
1 1
2( ) . Òàêèì îáðà-
çîì, S U U
k k
( ) ( ,
�
�2 y z U
k d k
k
� � �
�
�
1 1
1) . Îáðàòíîå âêëþ÷åíèå U S U
k k� �
�1 2( )
î÷åâèäíî. Ñëåäîâàòåëüíî, S U U
k k
( )
� �
�2 1. Ïðåäïîëîæåíèå èíäóêöèè îïðàâäà-
íî, ïåðâîå óòâåðæäåíèå ëåììû äîêàçàíî.
Òàê êàê S U U
d
( ) �
�1, ðàíã S ðàâåí d, à çíà÷èò, äåôåêò S ðàâåí 1. Ïîñêîëüêó
S z
d
( ) � 0, òî Ker( )S z
d
� ( ).
Ëåììà äîêàçàíà.
Ñëåäñòâèå. Íå ñóùåñòâóåò ñîáñòâåííûõ ïîëèíîìîâ îò äâóõ ïåðåìåííûõ: y z, .
Äîêàçàòåëüñòâî. S U U
k k
( ) ( )
�
� �1 0 äëÿ ëþáîãî k.
Ðàññìîòðèì îäíîðîäíûå ìíîãî÷ëåíû ñòåïåíè d �1 îò ïåðåìåííûõ
( , , , , )x x y z
d1 � . Ïóñòü U U U U
d
� 0 1, , ,� — ïîñëåäîâàòåëüíîñòü ïîäïðîñ-
òðàíñòâ, îïðåäåëåííàÿ â (8).
Òåîðåìà 3. Ñóùåñòâóþò ñèñòåìà ìíîãî÷ëåíîâ q y z U
j j
( , )� , j �1, 2,…, d �1,
ñòåïåíè d è ìíîãî÷ëåí q y z
d�1 ( , ) ñòåïåíè d �1 òàêèå, ÷òî ìíîãî÷ëåí
p x z x q y z
d
� � �1 2 1 ( , ) �
... ( , ) ( , ) ( , ) ( , )� � � � �
� � �
x q y z x q y z yq y z q y z
j j d d d d1 1 1� (9)
ÿâëÿåòñÿ ñîáñòâåííûì ìíîãî÷ëåíîì îïåðàòîðà T
J
.
Äîêàçàòåëüñòâî. Çàïèøåì âûðàæåíèå äëÿ ìíîãî÷ëåíà T p p JX
J
( ) ( )� :
( ( ) ( ) ( ) ( ( , )) (p JX x x z x x T q y z x x
d d
j j
� � � � � � �
�
� � � �1 2 2 3 1 1� ) ( ( , ))T q y z
j�
�1 �
�� � � � �
� �
( ) ( ( , )) ( ) ( , ) ( ( , ))� �x y T q y z y z T y z T q y z
d
d d d1 1 .
 ïîëó÷åííîì âûðàæåíèè ðàñêðîåì ñêîáêè è ïåðåãðóïïèðóåì ñëàãàåìûå:
T p x z x z x T q y z x T q y z
d d d d
( ) [ ] [ ( ( , )) ( ( , ))]� � � �� � � �1 2 2 1 3 1 � �
� �� � � �
� � � �
[ ( ( , )) ( ( , ))] [ ( (� �x T q y z x T q y z x T q
j j j j d d1 1 1 1 y z, )) �
� � � �
� �
yT q y z yT q y z zT q y z T q y
d d d d
( ( , ))] ( ( , )) ( ( , )) ( ( ,1 1� z G H)) � � ,
ãäå
G x z x T q y z
d d
j j
� � � �
�
�
� �
1
1 1� �( ( , ))
... ( ( , )) ( ( , )) ( ( , ))� � �
� �
� �x T q y z yT q y z T q y z
d d d d1 1 , (10)
H x z x T q y z yT q y z zT q
d d
j j d d
� � � � � �
� � �
� 2 1 1 1� �( ( , )) ( ( , )) ( ( y z, )) . (11)
 ïðàâîé ÷àñòè ôîðìóëû (10) ïðåîáðàçóåì âûðàæåíèå T q y z
k
( ( , )) äëÿ
k d�12, , ,� :
T q y z S q y z q y z
k k
d
k
( ( , )) ( ( , )) ( , )� � � . (12)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 129
Ïîäñòàâèì âûðàæåíèå T q y z
k
( ( , )) èç (12) â ôîðìóëó (10):
G x z x q y z x q y z x
d d d d
j j
d
� � � � � �
� � �
�
�
� � � �
1
1
1
2 1
1
1
1
( , ) ( , )� �
d d
q y z
�
�1 ( , )
� � � � �
�
� �
� � �
d
d d j j
yq y z q y z x S q y z x S q
1
1 2 1 1( , ) ( , ) ( ( , )) ( (� y z, )) ��
... ( ( , )) ( ( , )) ( ( , ))� � �
� �
� �x S q y z yS q y z S q y z
d d d d1 1 .
Òàê êàê
� �
d d d
x z x q y z
� �
� �
1
1
1
2 1 ( , ) �
... ( , ) ( , ) ( , )� � � �
�
�
� �
�
�
� � � �
d
d d
d
d
d
d
d
x q y z yq y z q y z
1
1
1 1
1
1
p ,
òî
G p x S q y z
d
� � �
�
� �
1
2 1( ( , )) �
... ( ( , )) ( ( , )) ( ( , ))� � �
� �
� �x S q y z yS q y z S q y z
d d d d1 1 . (13)
Èç ôîðìóë (10), (11) è (13) ïîëó÷èì
T p p x S q y z
d
( ) ( ( , ))� � �
�
� �
1
2 1 �
... ( ( , )) ( ( , )) ( ( , ))� � � �
� �
� � �x S q y z x S q y z yS q y z
j j d d d1 1� �
� � � �
�
S q y z x z x T q y z
d
d d
( ( , )) ( ( , ))1 2 3 1� �
... ( ( , )) ( ( , )) ( ( , ))� � � � � �
� � �
x T q y z yT q y z z T q y z
j j d d1 1 1�
� � � �
� �
� � �
d d d
p x S q z
1
2 1
1
( ( ) )
� � � � � �
� �
x S q T q x S q T q
j j j3 2 1 1 2( ( ) ( )) ( ( ) ( )) ...� ��
�� � � � � �
� � �
x S q T q y S q T q zT q S
d d d d d d
( ( ) ( )) ( ( ) ( )) ( ) (� �1 2 1 q
d�1 ) .
Èòàê,
T p p x S q T z
d d
( ) ( ( ) ( ))� � � �
�
� �
1
2 1
� � � � � �
� �
x S q T q x S q T q
j j j3 2 1 1 2( ( ) ( )) ( ( ) ( ))� �� �
... ( ( ) ( )) ( ( ) ( )) ( )� � � � � �
� � �
x S q T q y S q T q zT q
d d d d d d
� �1 2 1 S q
d
( )
�1 . (14)
Ïî ëåììå 1 S U U( )1 0� ; ïîñêîëüêó T z U
d
( )� 0 , òî â ïðîñòðàíñòâå U 1 ñó-
ùåñòâóåò ìíîãî÷ëåí q1 òàêîé, ÷òî S q
T z
d
( )
( )
1 � �
�
. Ïðè òàêîì âûáîðå ìíîãî÷ëå-
íà q1 ïîëó÷èì, ÷òî �S q T z
d
( ) ( )1 0� � . Òàê êàê T q U( )1 1� , q U2 2� , òî ïî ëåììå 1
â ïîäïðîñòðàíñòâå U 2 ñóùåñòâóåò òàêîé ìíîãî÷ëåí q2 , ÷òî S q
T q
( )
( )
2
1
� �
�
, ïî-
ýòîìó �S q T q( ) ( )2 1 0� � . Ïðîäîëæàÿ ïðîöåññ ïîñòðîåíèÿ ìíîãî÷ëåíîâ q
k
, ìîæ-
íî òî÷íî òàê æå äîêàçàòü ñóùåñòâîâàíèå òàêîãî ìíîãî÷ëåíà q
j
, ÷òî âûïîëíÿåòñÿ
ðàâåíñòâî �S q T q
j j
( ) ( )� �
�1 0, j d� 3 4, , ,� . Íàêîíåö, ìíîãî÷ëåí zq U
d d
� �
�
� �
( , , , , )y z y z yz z
d d d d1 2 1
� . Ïî ëåììå 1 åñëè U y
d
d
�
�
�1
1
( , y z
d
, �
..., , )yz z
d d�1
, òî S U U
d d
( )
�
�1 . Ïîýòîìó â ïðîñòðàíñòâåU
d�1 ñóùåñòâóåò òàêîé
ìíîãî÷ëåí q y z
d�1 ( , ), ÷òî S q y z zq y z
d d
( ( , )) ( , )
�
� �1 . Ñëåäîâàòåëüíî,
zT q S q
d d
( ) ( )� �
�1 0.
Èòàê, åñëè âûáèðàòü óêàçàííûì ñïîñîáîì ìíîãî÷ëåíû q y z U
j j
( , )� , j �1,
2,…, d, è q y z
d�1 ( , ) , òî â ïðàâîé ÷àñòè ôîðìóëû (14) âñå ñëàãàåìûå, êðîìå ïåðâî-
ãî, îáðàòÿòñÿ â 0.
Ñëåäîâàòåëüíî, T p p
d
( ) �
�
�
1
, ò.å. ìíîãî÷ëåí p ÿâëÿåòñÿ ñîáñòâåííûì ìíî-
ãî÷ëåíîì îïåðàòîðà T
J
.
Òåîðåìà äîêàçàíà.
130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
Ïðèìåð 2. Ïðèâåäåì ïîñëåäîâàòåëüíîñòü ñîáñòâåííûõ ïîëèíîìîâ æîðäàíî-
âîé êëåòêè J5 ( )� â ïðîñòðàíñòâå W w x y z5 ( , , , , )� :
� �1 � , p z1 � ,
� �2
2
� , p x y z y2
21
2
1
2
� �
�
�
�
�
�
�
�
�
,
� �3
3
� , p w y z x yz y3
2
2 31
3
1
3
� �
�
�
�
�
�
� � �
�
( ) ,
� �4
4
� , p y z w x y yz x y4
3
3
2
21
4
1
2
1
8
1
2
1
4
� �
�
�
�
�
�
� � � � �
�
�
�
�
�
� � ��
� � � �
�
�
�
�
�
�
�y z y
2 41
8
.
Òåîðåìà 4. Äëÿ æîðäàíîâîé êëåòêè J
n
( )� ñóùåñòâóåò íàáîð B
n
, ñîñòîÿùèé
èç n�1 ñîáñòâåííîãî ïîëèíîìà âèäà (9): B p p p
n n
�� �
�1 2 1, , ,� ,
p z1 � , p Q z y x
n2 2�
�
( )[ , , ],� … , p Q z y x x
n n� �
�1 1 2( )[ , , , , ]� � .
Ëþáîé ñîáñòâåííûé ïîëèíîì q X( ) æîðäàíîâîé êëåòêè J
n
( )� ìîæíî ïðåä-
ñòàâèòü â âèäå
q X
z
F p p p
k
n
( ) ( , , ..., )�
�
1
1 2 1 , (15)
ãäå F — ìíîãî÷ëåí îò n�1 ïåðåìåííîé ñ êîýôôèöèåíòàìè èç Q( )� .
Äîêàçàòåëüñòâî. Ðàññìîòðèì ñèñòåìó ðàâåíñòâ
u p z u p z y x u p z y x x
n n n n1 1 2 2 2 1 1 1 2� � � �
� � � �
, ( , , ), , ( , , , , )� � ,
ãäå U u u
n
�
�
( , , )1 1� — íàáîð ïåðåìåííûõ. Ëþáîå ðàâåíñòâî ýòîé ñèñòåìû
ìîæíî ïðåîáðàçîâàòü ê âèäó
x
z
f y u x x
j
n j
j j j n
�
� �
� �
1
1
1 2( , , , , )� . (16)
Ïóñòü q z y x x
n
( , , , , )1 2�
�
— ïðîèçâîëüíûé ñîáñòâåííûé ïîëèíîì. Ïîäñòàâ-
ëÿÿ â q z y x x
n
( , , , , )1 2�
�
ïîñëåäîâàòåëüíî çíà÷åíèÿ x j n
j
, , ,� �1 1� , èç (16) è
ïðèâîäÿ ê îáùåìó çíàìåíàòåëþ ðåçóëüòàòû, ïîëó÷àåì
q y U
z
F y u u
k
n
( , ) ( , , ..., )�
�
1
1 1 .
Ëåãêî äîêàçàòü ïî èíäóêöèè, ÷òî q y U( , ) — âçâåøåííî îäíîðîäíûé ïîëè-
íîì, åñëè ñîáñòâåííûå ÷èñëà ïåðåìåííûõ u
j
îïðåäåëèòü êàê � �
j
j
� , à ïåðåìåí-
íîé y — êàê �. Ïîêàæåì, ÷òî ïîëèíîì F íå çàâèñèò îò y. Ðàçëîæèì äëÿ ýòîãî F
ïî ñòåïåíÿì y. Ïîëó÷èì F Q y Q y Q
d
k k
� � � �
�0 1� . Çàìåòèì, ÷òî âñå êîýôôèöè-
åíòû F — ñîáñòâåííûå ïîëèíîìû. Âû÷èñëåíèå îïåðàòîðà S T E
J
d
� � � íà ïîëè-
íîìå F ïîêàçûâàåò, ÷òî S F( ) — ïîëèíîì ñòåïåíè d �1 ïî ïåðåìåííîé y :
deg
y
S F d( ( )) � �1 . Ñëåäîâàòåëüíî, ïðåäïîëîæåíèå n � 0 ïðîòèâîðå÷èò óñëîâèþ
òåîðåìû. Èòàê, d � 0.
Òåîðåìà äîêàçàíà.
Çàìå÷àíèå 3. Îòìåòèì, ÷òî ôîðìóëû (16) îïðåäåëÿþò èçîìîðôíîå îòîáðàæåíèå
âåêòîðíîãî ïðîñòðàíñòâà îäíîðîäíûõ ïîëèíîìîâ Q z y x x
d
n
( )
[ , , , , ]1 2�
�
ñòåïåíè d
â âåêòîðíîå ïðîñòðàíñòâî ñîáñòâåííûõ ïîëèíîìîâ Q y u u
P n
( , , , )1 1�
�
, ýëåìåíòû
êîòîðîãî èìåþò âèä
1
1 2 1
z
F y u u u
k
n
( , , , ..., )
�
, ãäå F y u u u
n
( , , , ..., )1 2 1� — âçâåøåí-
íî-îäíîðîäíûé ïîëèíîì ñ âåñàìè ïåðåìåííûõ
weight weight weight( ) , ( ) , , ( )y u u n
n
� � � �
�
1 1 11 1� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 131
Ñèñòåìà îáðàçóþùèõ P ïðîñòðàíñòâà Q y u u
P n
( , , , )1 1�
�
ñîñòîèò èç ñîáñò-
âåííûõ ïîëèíîìîâ è ïåðåìåííîé y :
P y p p p
n
�� �
�
, , , ,1 2 1� .
 ñèñòåìå îáðàçóþùèõ P ìàòðèöà A
P
îïåðàòîðà A èìååò âèä
A
P
n
�
�
�
�
�
�
�
�
�
�
� � � �
� � � �
� � � �
� � � �
�
� � � � �
�
�
�
2 .
Ïðèìåð 3. Äëÿ ñèñòåìû îáðàçóþùèõ ïðèìåðà 2 ôîðìóëû îáðàòíûõ ïðåîá-
ðàçîâàíèé èìåþò âèä:
x
z
p yz y� � �
�
�
�
�
1 1
2
1
2
2
2
�
,
w
z
p p y yz y z y� � � � �
�
�
�
�
1 1
3
1
2
1
62
3 2
2
2 2 3
� �
,
�
� � � �
� � � � � � �
1 1
2
1
2
1
4
11
24
1
43
4 3 2 2
2
3
3
2
2 2
z
p p y p yz p y yz y z y
3 41
24
z y�
�
�
�
�
.
 êà÷åñòâå ïðèìåðà ýòèõ ïðåîáðàçîâàíèé ðàññìîòðèì çàäà÷ó âûðàæåíèÿ ñîáñò-
âåííîãî ïîëèíîìà âòîðîé ñòåïåíè G îò ïåðåìåííûõ �, , , ,w x y z ÷åðåç ñèñòåìó îá-
ðàçóþùèõ z p p p, , , , ...2 3 4 Ïóñòü
G z wy wz x xy y yz� � � � � � ��
� � � �
3
2
1
2
1
2
1
4
1
4
2
2
2
3
.
Âû÷èñëèì ïðåîáðàçîâàíèÿ êàæäîãî èç ìîíîìîâ G. Ïîëó÷èì:
�
� � � �
z
z
p p y p yz p y yz y z� � � � � � �
1 1
2
1
2
1
4
11
24
1
42
4 3 2 2
2
3
3
2
2 2
y z y
3 41
24
�
�
�
�
�
,
� � � � � � �
�
�
�
�
wy
z
p y p y y z y z y
1 1
3
1
2
1
62
3 2
2
2
2 2 3 4
� �
,
3
2
1 3
2
3
2
1
2
3
4
1
42
3 2
3
3
2
2 2 3
� � � � � �
wz
z
p z p yz yz y z y z� � � � �
�
�
�
�
,
1
2
1 1
2
1
2
1
2
1
8
1
8
1
4
2
2 2
2
2 2
2
2
2 2 4 3
x
z
p p yz p y y z y y z� � � � � �
�
� � �
�
�
�
,
� � � � �
�
�
�
�
�
1
2
1
2
1
4
1
4
2
2
2
2 2 3
� � � �
xy z p yz y z y z ,
d z y z yz� �
�
�
�
�
�2
2
2 2
3
31
4
1
4� �
.
Ïðîñóììèðóåì ïîëó÷åííûå ðàâåíñòâà è âûäåëèì ïîëèíîì, íå çàâèñÿùèé îò y :
G z p p z p� � �
�
�
�
�
�2
4 3 2
23
2
1
2�
.
Ýòî è åñòü ïðåäñòàâëåíèå G â ñèñòåìå ñîáñòâåííûõ îáðàçóþùèõ
P z p p p� ( , , , ... )2 3 4 . Îñòàëîñü ïðîâåðèòü, ÷òî âñå êîýôôèöèåíòû ïðè ìîíîìàõ,
çàâèñÿùèõ îò y, ðàâíû 0.
132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
3. ÌÀÒÐÈ×ÍÀß ÔÎÐÌÓËÈÐÎÂÊÀ ÇÀÄÀ×È È ÀËÃÎÐÈÒÌ ÂÛ×ÈÑËÅÍÈß
ÑÎÁÑÒÂÅÍÍÛÕ ÏÎËÈÍÎÌÎÂ
Ââåäåì íåîáõîäèìûå ìàòðè÷íûå îáîçíà÷åíèÿ. Ïóñòü
J J( )�
� � �
�
� � �
� � �
� �
�
�
�
�
�
�
�
�
1
0 1 0
0
0
�
�
� � � � �
�
�
, J J( )�
� � � �
� � �
� �
� �
�
�
�
�
�
�
�
�
�
� � � � �
�
0
0 0
,
U z z y y z y
n n n n
�
� � � �
[ , , , , ]
1 2 1 1
� ,
X
x
x
y
z
n
�
�
�
�
�
�
�
�
�
�
1
1
�
, X
x
x
y
n
�
�
�
�
�
�
�
�
�
1
1
�
, Q
q q q
q q
q
n
n
nn
�
�
�
�
�
�
�
�
11 12 1
22 20
0 0
�
�
� � � �
�
,
M
C C C
C
n n
n
n n
n
n
�
� �
�
� �
�
�
� � � �
� � �
�
1 2
1
1 1
2
1 2
1
1
2
2
0
0
�
�
� � � � �
� � �
� � �
n
n
n n
n
C
�
�
� �
�
�
�
�
�
�
�
�
�
�
1
1
2 2
1
0 �
, m C
ij
j
i n i j
�
�
� � � �
1
1 1
� .
Ìàòðèöó M ïðåäñòàâèì â âèäå M E M
n
� �
�
�
1
1, ãäå M1 — âåðõíÿÿ òðå-
óãîëüíàÿ ìàòðèöà ñ íóëÿìè íà ãëàâíîé äèàãîíàëè (íàääèàãîíàëüíàÿ ìàòðèöà).
Îñíîâíîå îïðåäåëåíèå ñîáñòâåííîãî ìíîãî÷ëåíà æîðäàíîâîé êëåòêè èìååò âèä
p JX p X
n
( ) ( )� � .
Áóäåì èñêàòü ñîáñòâåííûé ìíîãî÷ëåí â âèäå p X U QX( ) ( , )� , ò.å.
( ( ), ( )) ( , )J U Q J X U QX
n
� � � .
 ìàòðè÷íûõ îáîçíà÷åíèÿõ ýòî ðàâåíñòâî ïåðåïèøåòñÿ â âèäå
( , ) ( , )UM QJX U QX
n
� � èëè
U MQJX QX
n
( )� �� 0. (17)
Ïóñòü E E E E0 10 0� �[ , ], [ , ] :
E0
1 0 0 0 0
0 1 0 0 0
0 0 0 1 0
�
�
�
�
�
�
�
�
� � � � �
, E1
0 1 0 0 0
0 0 1 0 0
0 0 0 0 1
�
�
�
�
�
�
�
�
� � � � �
.
Òîãäà J E E� �� 0 1, QE Q0 0� [ , ] , QE Q1 0� [ , ] , QJ Q Q� �[ , ] [ , ]� 0 0 ,
MQJ MQ MQ E M Q MQ
n
� � � � �[ , ] [ , ] [( ) , ] [ , ]� � �0 0 0 01 ,
MQJ Q M Q MQ
n
� � �[ , ] [ , ] [ , ]� �0 0 01 , � � �[ , ] [ , ]�M Q MQ1 0 0 .
Ìàòðèöà M Q1 , êàê è ìàòðèöà M1, — íàääèàãîíàëüíàÿ ìàòðèöà. Ïóñòü
MQ r
ij
i j
n
�
�
( )
, 1
. Ïîëîæèì r r q
ij ij
n
ij
� �
� � �
1
, òîãäà
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 133
[ , ]�M Q
r r r
r r
r
n
n
n
1
12 13 1
23 2
0
0 0
0 0 0
0 0 0
�
� � �
� �
�
�
�
�
� � � � � �
� 1 0
0 0 0 0 0
,n
�
�
�
�
�
�
�
�
�
, [ , ]
,
0
0
0 0
0 0
0 0
11 12 1
22 2
1 1 1
MQ
r r r
r r
r r
n
n
n n n n
�
� � �
�
�
� � � � �
�
� 0 r
nn
�
�
�
�
�
�
�
�
�
.
Ïóñòü � — ìàòðèöà â ðàçíîñòè MQJX QX
n
� � :
�X
r r r r r r r
r r r
n n n
n
�
� � � � � �
� � �
�
0
0 0
12 11 13 12 1 1 1 1
23 22 2
�
�
,
�
� �
�
� � � �
r r
r r r
r
n n
n n n n n n
nn
2 1 2
1 1 1 10 0 0
0 0 0 0
,
, , ,
� � � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
x
x
x
y
z
n
1
2
1
�
.
Îáîçíà÷èì äëÿ êðàòêîñòè ÷åðåç d
ij
ýëåìåíòû ìàòðèöû �. Ðàññìîòðèì ñêà-
ëÿðíîå ïðîèçâåäåíèå ( , )U X� , ãäå U z z y y z y
n n n n
�
� � � �
( , , , , )
1 2 1 1
� :
d x d y d z z d x d y d
j j n n
j
n
n
j j n1 1 1 1
2
1
1
2 2 2� �
�
�
�
�
�
�
�
�
� � �
�
�
�
�
� n
j
n
n
nj j nn nn
j n
z yz
d x d y d z
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
1
3
1
2
1
�
...
�
�
�
�
�
�
�
�
�
�
�
�
1
1
1
0
n
n
y .
Âî-ïåðâûõ, ñóììà â ëåâîé ÷àñòè òîæäåñòâà íå çàâèñèò îò x1. Âî-âòîðûõ, âûðàæå-
íèÿ — êîýôôèöèåíòû ïðè êàæäîé èç ïåðåìåííûõ x x
n2 1, ,�
�
— òîæäåñòâåííî ðàâ-
íû íóëþ. Ïîñêîëüêó êàæäîå èç ýòèõ âûðàæåíèé — îäíîðîäíûé ïîëèíîì îò ïåðåìåí-
íûõ y z, ñ êîýôôèöèåíòàìè èç ìíîæåñòâà D d i n j n
ij
� � � � �{ }: , , ; , ,1 1 1 1� � , âñå
êîýôôèöèåíòû èç D ðàâíû íóëþ. Â-òðåòüèõ, ýòî îçíà÷àåò, ÷òî
( ) ( ) ( ,d y d z z d y d z yz d y d
n n
n
n n
n
nn n n1 1 1
1
2 2 1
2
� � � � � �
�
�
�
�
�
� 1
1
0z y
n
)
�
,
d z d d yz d d y z d
n
n
n n
n
n n
n
n1 1 1 2 1
1
2 3 1
2 2
� �
�
�
�
� � � � � �( ) ( ) (, , �
� �
� 1 1 0, , )
n n n
n
d y .
Îòñþäà
d d d d d d d
n n n n n n n n n1 1 1 2 1 2 3 1 1 10 0 0
� � � � �
� � � � � � �, , , ,, , , ,� 0.
Èòàê, ìàòðèöà � îïðåäåëÿåò ñëåäóþùèå ïîäñèñòåìû îäíîðîäíûõ ëèíåéíûõ
óðàâíåíèé îòíîñèòåëüíî ïåðåìåííûõ q
ij
.
Ïîäñèñòåìà 1:
d d d
n12 13 1 10 0 0� � �
�
, , , ;�
d d
n23 2 10 0� �
�
, , ;�
...
d
n n� �
�2 1 0, .
Ïîäñèñòåìà 2:
d
d d d d d d
n
n n n n n n n n
1 1
1 2 1 2 3 1 1 1
0
0 0
�
� � � �
�
� � � � � �
,
, , ,, , , ,� 0.
Ñèñòåìà ñîäåðæèò
( )( )n n
n
� �
�
2 1
2
óðàâíåíèé è
n n( )�1
2
ïåðåìåííûõ. Äëÿ
òîãî ÷òîáû ïîëó÷èòü ñèñòåìó åå ôóíäàìåíòàëüíûõ ðåøåíèé, ìîæíî ïîëîæèòü
( , , ) ( , , ..., ), ( , , ) ( , ..., )q q q q
n n11 1 1 11 1 110 0 0 1 0� �
� �
� � , , ( , , ) ( , , ..., ).� �q q
n11 1 1 0 0 1
�
�
134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
Êàæäîå ôóíäàìåíòàëüíîå ðåøåíèå ïðåäñòàâëÿåò ñîîòâåòñòâóþùèé ñîáñò-
âåííûé ïîëèíîì èç íàáîðà � �p p
n2 , ,� (ñì. ïðèìåð 2).
Ñèñòåìà óðàâíåíèé â ýòîì ñëó÷àå ñîñòîèò èç äâóõ ïîäñèñòåì, à ýôôåêòèâ-
íûé ìåòîä çàêëþ÷àåòñÿ â òîì, ÷òî ðåøàåòñÿ ñíà÷àëà ïîäñèñòåìà 1, à çàòåì åå ðå-
øåíèå ïîäñòàâëÿåòñÿ â ïîäñèñòåìó 2.
Ïðèìåð 4. Âû÷èñëåíèå ñîáñòâåííîãî ïîëèíîìà p u w x y z5 ( , , , , , )� :
J �
�
�
�
�
� �
� � �
� � �
� � �
� � �
�
0 0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0 0 0
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�, ,X
u
w
x
y
z
M
�
� � � � �
� � �
� �
�
3
3
2 3
0
0 0
� ��
� � �
�
� � ��
� � � � �
�
� �
�
�
�
�
�
�
�
�
�
�
�
,
Q
q
q q q q
q q q
q q
q
�
�1 0 0 0
0
0 0
0 0 0
0 0 0 0
15
22 23 24 25
33 34 35
44 45
55�
�
�
�
�
�
�
�
,
MQ
q q q q q
q
i
i
i
i
i
i
�
�
�
�
�
�
� �
� � � � � �
�
4 3
22
3
23
2
33
5
2
4
4
5
1
5
5
4
20 2
4
23
3
33
5
1
3
1 4
5
1
4
1 5
4
2
0 0
� � � �
�
q q i q i q
q
i
i
i
i
i
i
�
�
�
�
�
�
�� �, ,
33
4
34
3
44
4
35
3
45
2
55
4
44
4
45
3
3 3 6
0 0 0 4
� � � � �
� � �
q q q q q
q q
� � �
� q
q
55
4
550 0 0 0 �
�
�
�
�
�
�
�
�
�
�
�
�
,
[ , ]�
� � � � �
M Q
q q q q q
i
i
i
i
i
i
1
4
22
4
23
3
33
6
2
4
4
6
2
5
5
0
0
�
�
�
�
�
�
� �
0
0 0 2 0
0 0 0 3
4
33
6
2
3
1 4
6
2
4
1 5
4
4
� � �
�
q i q i q
q
i
i
i
i
i
i
�
�
�
�
�
�� �, ,
4
4
45
3
55
4
55
3 6 0
0 0 0 0 4 0
0 0 0 0 0 0
� �
�
q q
q
�
�
�
�
�
�
�
�
�
�
�
�
�
,
[ , ]0
0
4 3
22
3
23
2
33
5
2
4
4
5
1
5
5
MQ
q q q q q
i
i
i
i
i
i
�
�
�
�
�
�
� �
� � � � � �
0 0 2
4
22
4
23
3
33
5
1
3
1 4
5
1
4
1� � � � �q q q i q i q
i
i
i
i
i
i
�
�
�
�
�
�
�� �, ,5
4
33
4
34
3
44
4
35
3
45
2
55
4
44
0 0 0 3 3 6
0 0 0 0
� � � � � �
� �
q q q q q q
q
� � �
4
45
3
55
4
55
4
0 0 0 0 0
q q
q
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 135
Ïîäñèñòåìà 1 èìååò âèä
d12 : � �
4
22
4
0q � � ,
d13 : � � �
4
23
3
33
3
22 0q q q� � � ,
d14 : � � � � �
4
24
3
34
2
44
3
23
2
33 0q q q q q� � � � � ,
d23 : 2 0
4
33
4
22� �q q� � ,
d24 : 2 3 2 0
4
34
3
44
4
23
3
33� � � �q q q q� � � � ,
d34 : 3 0
4
44
4
33� �q q� � .
Óïðîùåíèå ýòîé ïîäñèñòåìû ïðèâîäèò ê ñèñòåìå
d12 : q22 1 0� � ,
d13 : �q q q23 33 22 0� � � ,
d14 : � � �
2
24 34 44 23 33 0q q q q q� � � � � ,
d23 : 2 033 22q q� � ,
d24 : 2 3 2 034 44 23 33� �q q q q� � � � ,
d34 : 3 044 33q q� � .
Ðåøåíèå:
d12 : q22 1� � , d13 : q23
1
2
�
�
, d14 : q24
2
1
3
� �
�
,
d23 : q33
1
2
� , d24 : q34
1
2
� �
�
, d34 : q44
1
6
� � .
Ïîäñèñòåìà 2 èìååò âèä
�
5
5
1
5
0
�
�
�
�
i
i
i
q ,
� � �
6
5
2
5
5
4
2
4
5�
�
�
�
�
�� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
i
i
i
i
i
i
i
i
q q i q 1 5
1
4
0,
i�
�
�
�
�
�
�
�
�
�
� ,
i q i q
i
i
i
i
i
i
� �
6
1 5
2
4
5
1 4
1
3
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�, , ( )� � �
4
35
3
45
2
553 6 0q q q� � � ,
( ) ( ) ( )3 6 3 4 0
4
45
3
55
4
34
3
44
4
45
3
55� � � � � �q q q q q q� � � � � � ,
( ) ( ) ( )4 0
4
55
4
44
4
55� � �q q q� � � .
Óïðîùåíèå ýòîé ïîäñèñòåìû ïðèâîäèò ê ñèñòåìå
� � � �
4
15
3
25
2
35 45 55 0q q q q q� � � � � ,
( ) ( )2 3 4 5 0
4
25
3
35
2
45 55� � � � �q q q q� � � � � � ,
( )3 6 10
11
6
0
4
35
3
45
2
55
2
� � � �q q q� � � �
�
�
�
�
�
�
� ,
( ) ( )4 10 0
4
45
3
55
3
� � �q q� � � � , ( ) ( )5
1
6
0
4
55
4
� �q � � � .
Ðåøåíèå:
�
4
15
1
5
q � � , �
3
25
1
6
q � � , �
2
35
1
6
q � , �q45
1
6
� , q55
1
30
� .
Ñîáñòâåííûé ïîëèíîì P u w x y z5 ( , , , , , )� :
P u y z w x y yz5
4
4
2 3
31
5
1
2
1
3
1
6
1
2
� �
�
�
�
�
�
� � � � � �
�
�
�
�
�
� �
�
�
� � �
w x y y z� �
�
�
�
�
�
� �
1
2
1
6
2
2 2
� �
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
1
6
1
6
1
30
3 4
x y y z y y
�
.
136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
4. ÑÎÁÑÒÂÅÍÍÛÅ ÏÎËÈÍÎÌÛ È L-ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÎÏÅÐÀÒÎÐÎÂ
Ïóñòü A — ïðîèçâîëüíûé íåâûðîæäåííûé ëèíåéíûé îïåðàòîð, äåéñòâóþùèé
íà âåêòîðíîì ïðîñòðàíñòâå Q X
d( )
[ ] îäíîðîäíûõ ìíîãî÷ëåíîâ êàê ëèíåéíîå
ïðåîáðàçîâàíèå ïåðåìåííûõ f X f AX( ) ( )� , d — íàòóðàëüíîå ÷èñëî è
� !X X . Ìíîæåñòâî ñîáñòâåííûõ ïîëèíîìîâ ñòåïåíè d îò ïåðåìåííûõ èç �X
îáðàçóåò êîíå÷íîìåðíîå âåêòîðíîå ïîäïðîñòðàíñòâî, êîòîðîå îáîçíà÷èì
W A d X( , , )� . Áàçèñ ýòîãî ïîäïðîñòðàíñòâà ñîñòîèò èç êîíå÷íîãî ÷èñëà ïîëèíî-
ìîâ ( , .., )q q
M1 .
Îòìåòèì, ÷òî äëÿ îïåðàòîðîâ — æîðäàíîâûõ êëåòîê — òåîðåìà 4 äàåò îïè-
ñàíèå ýòîãî áàçèñà ÷åðåç ïîëèíîìû íàáîðà ( , , )p p
n1 1�
�
, à èìåííî
q X
p
F p p p
j
k
j n
( ) ( , , ... )�
�
1
1
1 2 1 ,
F u u a M a M
j n j j K j K j
j j
( , , )
1 1 1 1� �
�
� � � , a Q
ij
� ( )� , M
ij
— ìîíîìû îò ïåðå-
ìåííûõ ( , , )u u
n1 1�
�
.
Ïóñòü M u u
k
n
k
n
�
�
�
1 1
1 1... — òàêîé ìîíîì. Òîãäà d k n
n
� � �
�1 1( ) k n
n�
� �2 2( ) �
... � �k k1 . Îòìåòèì, ÷òî áàçèñ ïîäïðîñòðàíñòâà W A d X( , , )� ìîæíî âû÷èñëèòü
ìåòîäîì íåîïðåäåëåííûõ êîýôôèöèåíòîâ, îäíàêî âû÷èñëèòåëüíàÿ ñëîæíîñòü
ýòîãî àëãîðèòìà — ïîëèíîì îò ( )d
n
�
�
1
1
. Ïîýòîìó çàäà÷ó ýôôåêòèâíîãî êîí-
ñòðóêòèâíîãî îïèñàíèÿ áàçèñà W A d X( , , )� ñëåäóåò ñ÷èòàòü îòêðûòîé.
 ÷àñòíîñòè, îäèí èç âîïðîñîâ ìîæíî ñôîðìóëèðîâàòü òàê: ïóñòü ìíîæåñòâî
áàçèñíûõ ìîíîìîâ çàäàíî ôîðìóëîé
B J d X M M u u d k n k n
k
n
k
n n
n( , , ) | ... , ( ) (� � � � � � �
�
� �
�{
1 1 1 2
1 1 1 � � �2 1) � k }.
Î÷åâèäíî, B J d X W J d X( , , ) ( , , )� . ßâëÿåòñÿ ëè ýòî ìíîæåñòâî áàçèñîì
W J d X( , , )? Íàïðèìåð, ÿâëÿåòñÿ ëè ìíîæåñòâî
p zp z p z p z p p zp5 4
2
3
3
2
5
3 2 2
2
, , , , , ,
(ïðèìåðû 2, 3) áàçèñîì ïîäïðîñòðàíñòâà W J u w x y z( , , , , , , , )5 5 { }� ?
Äëÿ êàæäîé æîðäàíîâîé êëåòêè J
k k
( )� æîðäàíîâîé ôîðìû îïåðàòîðà A
îïðåäåëåíà ñâîÿ ïîñëåäîâàòåëüíîñòü ïîäïðîñòðàíñòâ ñîáñòâåííûõ ïîëèíîìîâ.
Ïóñòü J — îäíà òàêàÿ êëåòêà. Òîãäà â îáîçíà÷åíèÿõ, èñïîëüçóåìûõ âûøå ïðè ðàñ-
ñìîòðåíèè îïåðàòîðîâ — æîðäàíîâûõ êëåòîê, ýòà ïîñëåäîâàòåëüíîñòü èìååò âèä
W J z W J x y z W J n x x y
n n
( , , ( )) ( , , ( , , )) ( , , ( , , , ,1 3 1 1 1� � �
� �
� � z)) .
Ñîáñòâåííûì ÷èñëîì ïîäïðîñòðàíñòâà W J d X( ( ), , )�
�
íàçîâåì ÷èñëî �
d
.
Ïîñëåäîâàòåëüíîñòü ñîáñòâåííûõ ÷èñåë ðàññìàòðèâàåìûõ ïîäïðîñòðàíñòâ èìååò
âèä ( , , , )� � �
3
�
n
. Åñëè æîðäàíîâà ôîðìà îïåðàòîðà A ñîñòîèò èç íåñêîëüêèõ
êëåòîê, â îïðåäåëåíèè ïîäïðîñòðàíñòâ ñîáñòâåííûõ ïîëèíîìîâ A, î÷åâèäíî,
èìååò ñìûñë ðàññìàòðèâàòü òîëüêî ïîäìíîæåñòâà ïåðåìåííûõ âèäà
X X
J
i
J
� �
�
( )
, ãäå X x x y z i
i
J
i
J
n
J J J
J
( ) ( ) ( ) ( ) ( )
, , , , ,� "
�
df
{ }�
1
1, — ïîäìíîæåñòâà ïå-
ðåìåííûõ, ñîîòâåòñòâóþùèõ äàííîé æîðäàíîâîé êëåòêå îïåðàòîðà A,
à îáúåäèíåíèå áåðåòñÿ ïî âñåì æîðäàíîâûì êëåòêàì îïåðàòîðà A.
Ðàññìîòðèì ëèíåéíûé îïåðàòîð, îáðàçîâàííûé äâóìÿ æîðäàíîâûìè êëåòêà-
ìè: J J
n n1 21 2( ), ( )� � . Ëþáîå ïîäïðîñòðàíñòâî ñîáñòâåííûõ ïîëèíîìîâ îïåðàòî-
ðà A â ýòîì ñëó÷àå ÿâëÿåòñÿ ïðÿìûì ïðîèçâåäåíèåì ïîäïðîñòðàíñòâ æîðäàíîâûõ
êëåòîê:
W J d X W J d X W A d d X X
n n
( , , ) ( , , ) ( , , )
1 21 1 2 2 1 2 1 2# � � $ .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 137
Îáîçíà÷èì Base( )W áàçèñ ïîäïðîñòðàíñòâà W. Òîãäà
Base( ( , , ) ( , , ))W J d X W J d X
n n1 21 1 2 2# �
= Base Base( ( , , )) ( ( , , ))W J d X W J d X
n n1 21 1 2 2# .
Åñëè
Base( ( , , )) ( ( ), , ( ))W J d X q X q X
n k1 11 1 11 1 1 1� � ,
Base( ( , , )) ( ( ), , ( ))W J d X q X q X
n k2 22 2 21 2 2 2� � ,
òî
Base {( ( , , ) ( , , )) ( ) ( ),W J d X W J d X q X q X i
n n i j1 21 1 2 2 1 1 2 2# � �1 11 2... , ...k j k� },
à ñîáñòâåííîå ÷èñëî ýòîãî ïîäïðîñòðàíñòâà ðàâíî � �
1 2
1 2d d
. Ýòà êîíñòðóêöèÿ íå-
ïîñðåäñòâåííî ðàñïðîñòðàíÿåòñÿ íà îïåðàòîðû, ñîäåðæàùèå ïðîèçâîëüíîå êî-
ëè÷åñòâî æîðäàíîâûõ êëåòîê ïðîèçâîëüíûõ ðàçìåðîâ.
Åñëè æîðäàíîâà ôîðìà ëèíåéíîãî îïåðàòîðà A ñîñòîèò èç æîðäàíîâûõ êëå-
òîê J n X J n X
m m m
( , , ), , ( , , )� �1 1 1 � , ò.å.
A J n X J n X
m m m
� # #( , , ) ( , , )� �1 1 1 � ,
äëÿ îïåðàòîðà A ìîæíî âûäåëèòü ñèñòåìó ïîäïðîñòðàíñòâ ñîáñòâåííûõ ïîëè-
íîìîâ, êàæäîå èç êîòîðûõ õàðàêòåðèçóåòñÿ ñîáñòâåííûì ÷èñëîì � � �
1 2
1 2d d
m
d
m
� ,
d n j m
j j
� �, , ,1 � .
Òåîðåìà 5. Åñëè ñîáñòâåííûå ÷èñëà äâóõ ïîäïðîñòðàíñòâ ñîáñòâåííûõ ïî-
ëèíîìîâ ëèíåéíîãî îïåðàòîðà A ðàâíû, èõ ñóììà òàêæå îáðàçóåò ïîäïðîñòðàí-
ñòâî ñîáñòâåííûõ ïîëèíîìîâ:
� � � � � � � � � �
1 2 1 2 1 2
1 2 1 2k k
m
k l l
m
l
m m
W X W X W� �� � % � �( , ) ( , ) ( , X X1 2$ ).
Äîêàçàòåëüñòâî î÷åâèäíî.
Íèæå ïîêàæåì, ÷òî îïðåäåëåíèå ïîäïðîñòðàíñòâ ñîáñòâåííûõ ïîëèíîìîâ — îäíà
èç íàèáîëåå âàæíûõ çàäà÷ òåîðèè ïðîãðàììíûõ èíâàðèàíòîâ ëèíåéíûõ îïåðàòîðîâ.
Ðàññìîòðèì òåïåðü çàäà÷ó ïîñòðîåíèÿ L-èíâàðèàíòîâ ëèíåéíûõ îïåðàòîðîâ
(ñì. îïðåäåëåíèå 1). Ïóñòü îïåðàòîð A ñîñòîèò èç îäíîé æîðäàíîâîé êëåòêè è
q X( ) — ñîáñòâåííûé ïîëèíîì A ñ ñîáñòâåííûì ÷èñëîì �
d
. Òîãäà ðàöèîíàëüíîå
âûðàæåíèå
r X
q X
z
d
( )
( )
�
— L-èíâàðèàíò A. Òàêèì îáðàçîì, äëÿ æîðäàíîâîé êëåòêè ðàçìåðà d ñóùåñ-
òâóåò ïî êðàéíåé ìåðå d �2 L-èíâàðèàíòà
r X
p X
z
r X
p X
z
n
d
d
3
3
3
( )
( )
, , ( )
( )
� �� .
(18)
Ýòè èíâàðèàíòû áóäåì íàçûâàòü âíóòðèêëåòî÷íûìè.
Çàìå÷àíèå 4. Ñèñòåìà L-èíâàðèàíòîâ (18), îïðåäåëÿåìàÿ ÷åðåç ñîáñòâåííûå
ìíîãî÷ëåíû, çàäàåò òàê íàçûâàåìóþ îðáèòó ëèíåéíîãî îïåðàòîðà A â ïðîñòðàí-
ñòâå W. Â ñàìîì äåëå, åñëè âåêòîð b b b
n
( ) ( ) ( )
( , , )
0
1
0 0
� � âûáðàí êàê íà÷àëüíûé,
ïîñëåäîâàòåëüíîñòü âåêòîðîâ, çàäàííàÿ ðåêóððåíòíûì ñîîòíîøåíèåì
b Ab
j j( ) ( )�
�
1
, ëåæèò â äâóìåðíîì àëãåáðàè÷åñêîì ìíîãîîáðàçèè, çàäàííîì ñèñ-
òåìîé óðàâíåíèé
[ ( ) ( )]& & [ ( ) ( )]
( ) ( )
r X r b r X r b
n n3 3
0 0
� �� . (19)
Ìîæíî îæèäàòü, ÷òî îðáèòà A, êàê áåñêîíå÷íàÿ ïîñëåäîâàòåëüíîñòü, ëåæèò
â îäíîìåðíîì ìíîãîîáðàçèè, ïðè÷åì íåäîñòàþùèì ÷ëåíîì ñèñòåìû (19) äîëæíî
áûòü óðàâíåíèå, çàäàâàåìîå L-èíâàðèàíòîì, çàâèñÿùèì îò y z, . Ñëåäñòâèå ê ëåì-
ìå 1 ïîêàçûâàåò, ÷òî òàêèõ èíâàðèàíòîâ íå ñóùåñòâóåò. Îäíàêî ëåãêî ïðîâåðèòü,
138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
÷òî íåàëãåáðàè÷åñêàÿ ôóíêöèÿ
p y z z
yz
� �
1
� �ln( )
ln ( )
óäîâëåòâîðÿåò ñîîòíîøåíèþ (6): p AX P X
yz yz
( ) ( )� � . Ïîýòîìó ê àëãåáðàè÷åñ-
êîé ñèñòåìå (19) ìîæíî äîáàâèòü íåàëãåáðàè÷åñêîå óðàâíåíèå, ïîëó÷èâ îïèñà-
íèå îäíîìåðíîãî ìíîãîîáðàçèÿ, ñîäåðæàùåãî îðáèòó A:
[ ( , ) ( , )]& [ ( ) (
( ) ( ) ( ) ( )
b p y z zp b b r X r b
n yz yz
n
n
0
1
0 0
3 3
0
� �
�
)]& & [ ( ) ( )]
( )
� r X r b
n n
�
0
.
Òåîðåìà 5 îïðåäåëÿåò òàê íàçûâàåìûå ìåæêëåòî÷íûå èíâàðèàíòû. Èìåííî,
ïóñòü ïðîñòðàíñòâî ñîáñòâåííûõ ïîëèíîìîâ ïðîèçâîëüíîãî ëèíåéíîãî îïåðàòîðà
ñîäåðæèò äâà ðàçëè÷íûõ ïîäïðîñòðàíñòâà: W W1 2, , ñ ðàâíûìè ñîáñòâåííûìè çíà-
÷åíèÿìè (ò.å. óäîâëåòâîðÿþò òåîðåìå 5), q X W q X W1 1 1 2 2 2( ) , ( )� � . Ïðè ýòîì
r X X
q X
q X
( )
( )
( )
1 2
1 1
2 2
$ � — L-èíâàðèàíò îïåðàòîðà A.
Òåîðåìà 6. Ïóñòü r X
q X
s X
( )
( )
( )
� — L-èíâàðèàíò ëèíåéíîãî îïåðàòîðà A. Òîã-
äà q X s X( ), ( ) — ñîáñòâåííûå ïîëèíîìû A ñ ðàâíûìè ñîáñòâåííûìè ÷èñëàìè.
Äîêàçàòåëüñòâî. Áóäåì ñ÷èòàòü, ÷òî äðîáü
q X
s X
( )
( )
íåñîêðàòèìà:
r AX
q AX
s AX
r X
q X
s X
( )
( )
( )
( )
( )
( )
� � � .
Ïîñêîëüêó íåñîêðàòèìûå äðîáè â ïîëå ðàöèîíàëüíûõ âûðàæåíèé Q X( )
ïðåäñòàâëÿþòñÿ â âèäå îòíîøåíèÿ öåëûõ âûðàæåíèé åäèíñòâåííûì îáðàçîì ñ
òî÷íîñòüþ äî ÷èñëîâîãî ìíîæèòåëÿ,
q AX q X s AX s X( ) ( ), ( ) ( )� �� � .
Òåîðåìà äîêàçàíà.
 çàêëþ÷åíèå ñôîðìóëèðóåì îñíîâíóþ òåîðåìó îá L-èíâàðèàíòàõ ëèíåéíûõ
îïåðàòîðîâ.
Òåîðåìà 7. Ïóñòü q q
m1, ,� — ìíîæåñòâî âñåõ áàçèñíûõ ïîëèíîìîâ âñåõ æîð-
äàíîâûõ êëåòîê ëèíåéíîãî îïåðàòîðà A è � �1, ,�
m
— ñîâîêóïíîñòü èõ ñîáñòâåí-
íûõ ÷èñåë. Ïðåäïîëîæèì, ÷òî ñóùåñòâóþò òàêèå öåëûå ÷èñëà k k
m1, ,� , ÷òî
� �
1
1 1
k
m
k
m
� � �� . (20)
Òîãäà r X q q
k
m
k
m( ) � � �
1
1
� — L-èíâàðèàíò ëèíåéíîãî îïåðàòîðà A.
Äîêàçàòåëüñòâî î÷åâèäíî.
Òàêèì îáðàçîì, ïðîáëåìà îïèñàíèÿ L-èíâàðèàíòîâ ëèíåéíîãî îïåðàòîðà A
ñâîäèòñÿ ê ïðîáëåìå îïèñàíèÿ âñåõ ñîîòíîøåíèé (20). Â [10, 11] äîêàçàíî, ÷òî
ýòî ìíîæåñòâî èìååò êîíå÷íûé áàçèñ.
Åñëè âñå ñîáñòâåííûå ÷èñëà ëèíåéíîãî îïåðàòîðà A — ðàöèîíàëüíûå ÷èñëà,
ïðîáëåìà ïîñòðîåíèÿ ýòîãî áàçèñà àëãîðèòìè÷åñêè ðàçðåøèìà ñ ïîìîùüþ òåîðå-
òèêî-÷èñëîâîãî àëãîðèòìà.
 ñëó÷àå, êîãäà �
j
— àëãåáðàè÷åñêèå ÷èñëà, ïðîáëåìà ïîñòðîåíèÿ áàçèñà
ìíîæåñòâà ñîîòíîøåíèé (2) îñòàåòñÿ îòêðûòîé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. F l o y d R . W . Assigning Meanings to Programs // Proceedings of Symposium on Appl. Mathemat.
— 1967. — 19. — Ð. 19–32.
2. H o a r e C . A . R . An Axiomatic Basis for Computer Programming // Commun of the ACM. —
1969. — ¹ 12(10). — Ð. 576–580.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 139
3. L e t i c h e v s k y A . A . About one approach to program analysis // Cybernetics. — 1979. — N 6.
— P. 1–8.
4. G o d l e v s k y A . B . , K a p i t o n o v a Y . V . , K r i v o y S . L . , L e t i c h e v s k y A . A .
Iterative methods of program analysis // Ibid. — 1989. — N 2. — P. 9–19.
5. L e t i c h e v s k y A . , L v o v M . Discovery of invariant equalities in programs over data fields //
Appl. Algebra in Engineer., Communic. and Comput. — 1993. — N 4. — P. 21–29.
6. M ü l l e r - O l m M . , S e i d l H . Precise interprocedural analysis through linear algebra // Proc. of
Symposium on Principles of Programming Languages. – Venice, Italy, January 14–16, 2004. ACM:
New York, NY, USA, 2004. — P. 330–341.
7. C a p l a i n M . Finding invariant assertions for proving programs // Proc. of the Intern. Conf. on
Reliable Software. — Los Angeles, California, April 21–23 1975. ACM: New York, NY, USA –
1975. — P. 165–171.
8. R o d r i g u e z - C a r b o n e l l E . , K a p u r D . Automatic generation of polynomial loop
invariants: algebraic foundations // Proc. of Intern. Symp. on Symbolic and Algebraic Comput. —
Santander, Spain, July 4–7, 2004. — ACM: New York, NY, USA, 2004. — P. 266–273.
9. K o v � c s L . I . , J e b e l e a n T . An algorithm for automated generation of invariants for loops
with conditionals // Proc. of Intern. Symp. on Symbolic and Numeric Algorithms for Scientific
Comput. — Timisoara, Romania, 25–29 Sept. 2005. IEEE Comput. Soc., 2005. — P. 245–249.
10. Ë ü â î â Ì . Ñ . Ïîëèíîìèàëüíûå èíâàðèàíòû ëèíåéíûõ öèêëîâ // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2010. — ¹ 4. — Ñ. 159–168.
11. L v o v M . S . Polynomial invariants for linear loops // Cybernetics and Systems Analysis. — 2010.
— 46, N 4. — P. 660–668.
12. Â à í ä å ð Â à ð ä å í Á . Ë . Àëãåáðà. Èçä. 2-å. — Ì.: ÃÐÔÌË, 1979. — 624 ñ.
13. Õ î ä æ  . , Ï è ä î Ä . Ìåòîäû àëãåáðàè÷åñêîé ãåîìåòðèè. Ò. 1. — Ì.: Èçä-âî èíîñòð. ëèò.,
1954. — 462 ñ.
14. Ë ü â î â Ì . Ñ . Èíâàðèàíòíûå ðàâåíñòâà ìàëûõ ñòåïåíåé â ïðîãðàììàõ, îïðåäåëåííûõ íàä
ïîëåì // Êèáåðíåòèêà, 1988. — ¹ 1. — Ñ. 108–110.
15. Ä ü å ä î í í å Æ . , Ê å ð ð î ë Ä æ , Ì à ì ô î ð ä Ä . Ãåîìåòðè÷åñêàÿ òåîðèÿ èíâàðèàíòîâ. —
Ì.: Ìèð, 1974. — 280 ñ.
Ïîñòóïèëà 16.11.2010
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Gray Gamma 2.2)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.3
/CompressObjects /Off
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages false
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /LeaveColorUnchanged
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams true
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts false
/TransferFunctionInfo /Apply
/UCRandBGInfo /Remove
/UsePrologue false
/ColorSettingsFile (Color Management Off)
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 290
/ColorImageMinResolutionPolicy /Warning
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 600
/ColorImageDepth 8
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.01667
/EncodeColorImages true
/ColorImageFilter /FlateEncode
/AutoFilterColorImages false
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 290
/GrayImageMinResolutionPolicy /Warning
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 600
/GrayImageDepth 8
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 2.03333
/EncodeGrayImages true
/GrayImageFilter /FlateEncode
/AutoFilterGrayImages false
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 800
/MonoImageMinResolutionPolicy /Warning
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 2400
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/PDFX3:2003
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError false
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox false
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile (None)
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000500044004600206587686353ef901a8fc7684c976262535370673a548c002000700072006f006f00660065007200208fdb884c9ad88d2891cf62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef653ef5728684c9762537088686a5f548c002000700072006f006f00660065007200204e0a73725f979ad854c18cea7684521753706548679c300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002000740069006c0020006b00760061006c00690074006500740073007500640073006b007200690076006e0069006e006700200065006c006c006500720020006b006f007200720065006b007400750072006c00e60073006e0069006e0067002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f0062006500200050004400460020007000610072006100200063006f006e00730065006700750069007200200069006d0070007200650073006900f3006e002000640065002000630061006c006900640061006400200065006e00200069006d0070007200650073006f0072006100730020006400650020006500730063007200690074006f00720069006f00200079002000680065007200720061006d00690065006e00740061007300200064006500200063006f00720072006500630063006900f3006e002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f007500720020006400650073002000e90070007200650075007600650073002000650074002000640065007300200069006d007000720065007300730069006f006e00730020006400650020006800610075007400650020007100750061006c0069007400e90020007300750072002000640065007300200069006d007000720069006d0061006e0074006500730020006400650020006200750072006500610075002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f006200650020005000440046002000700065007200200075006e00610020007300740061006d007000610020006400690020007100750061006c0069007400e00020007300750020007300740061006d00700061006e0074006900200065002000700072006f006f0066006500720020006400650073006b0074006f0070002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea51fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e30593002537052376642306e753b8cea3092670059279650306b4fdd306430533068304c3067304d307e3059300230c730b930af30c830c330d730d730ea30f330bf3067306e53705237307e305f306f30d730eb30fc30d57528306b9069305730663044307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e30593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020b370c2a4d06cd0d10020d504b9b0d1300020bc0f0020ad50c815ae30c5d0c11c0020ace0d488c9c8b85c0020c778c1c4d560002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken voor kwaliteitsafdrukken op desktopprinters en proofers. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200066006f00720020007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c00690074006500740020007000e500200062006f007200640073006b0072006900760065007200200065006c006c00650072002000700072006f006f006600650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020007000610072006100200069006d0070007200650073007300f5006500730020006400650020007100750061006c0069006400610064006500200065006d00200069006d00700072006500730073006f0072006100730020006400650073006b0074006f00700020006500200064006900730070006f00730069007400690076006f0073002000640065002000700072006f00760061002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a00610020006c0061006100640075006b006100730074006100200074007900f6007000f60079007400e400740075006c006f0073007400750073007400610020006a00610020007600650064006f007300740075007300740061002000760061007200740065006e002e00200020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740020006600f600720020006b00760061006c00690074006500740073007500740073006b0072006900660074006500720020007000e5002000760061006e006c00690067006100200073006b0072006900760061007200650020006f006300680020006600f600720020006b006f007200720065006b007400750072002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/DEU <FEFF004a006f0062006f007000740069006f006e007300200066006f00720020004100630072006f006200610074002000440069007300740069006c006c0065007200200037002e000d00500072006f006400750063006500730020005000440046002000660069006c0065007300200077006800690063006800200061007200650020007500730065006400200066006f0072002000680069006700680020007100750061006c0069007400790020007000720069006e00740069006e0067002e000d0028006300290020003200300031003000200053007000720069006e006700650072002d005600650072006c0061006700200047006d006200480020>
/ENU (Use these settings to create Adobe PDF documents for quality printing on desktop printers and proofers. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /NoConversion
/DestinationProfileName ()
/DestinationProfileSelector /NA
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure true
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles true
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /NA
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /LeaveUntagged
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [2834.646 2834.646]
>> setpagedevice
|