Анализ линейно определенных итеративных циклов

Представлен новый метод доказательства инвариантности системы линейных неравенств, а также завершаемости линейно определенных итеративных циклов императивных программ. Тело цикла — линейный оператор, преобразующий вектор переменных программы. Метод учитывает предусловие цикла, а также условие повтор...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автор:	Львов, M.C.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Назва видання:	Кибернетика и системный анализ
Теми:	Программно-технические комплексы
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/131398
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Анализ линейно определенных итеративных циклов / M.C. Львов // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 122-136. — Бібліогр.: 23 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-131398
record_format	dspace
spelling	irk-123456789-1313982018-03-22T03:03:03Z Анализ линейно определенных итеративных циклов Львов, M.C. Программно-технические комплексы Представлен новый метод доказательства инвариантности системы линейных неравенств, а также завершаемости линейно определенных итеративных циклов императивных программ. Тело цикла — линейный оператор, преобразующий вектор переменных программы. Метод учитывает предусловие цикла, а также условие повторения цикла в виде совокупности систем линейных неравенств. Метод основан на построении и анализе спектра этого оператора и вычислении числа итераций цикла, после выполнения которых инвариантность либо обеспечивается, либо опровергается. Теоретический материал работы иллюстрируется примерами. Розглянуто новий метод доведення інваріантності системи лінійних нерівностей, а також завершуваності лінійно визначених ітеративних циклів імперативних програм. Тіло циклу — лінійний оператор, що перетворює вектор змінних програми. Метод враховує передумову циклу, а також умову повторення циклу у вигляді сукупності систем лінійних нерівностей. Метод ґрунтується на побудові та аналізі спектра цього лінійного оператора та обчисленні кількості ітерацій циклу, після виконання яких інваріантність або забезпечується, або спростовується. Теоретичний матеріал роботи проілюстровано прикладами. The paper presents a new method to prove the invariance of the system of linear inequalities and termination of linear definite iterative loops for imperative programs. Loop body is a linear operator that transforms the vector of program variables. The method takes into account the loop precondition, as well as the condition of loop repetition in the form of a set of systems of linear inequalities. The method is based on the construction and analysis of the spectrum of the linear operator and calculating the number of loop iterations after which the invariance is either provided or disproved. The theoretical material is illustrated by examples. 2016 Article Анализ линейно определенных итеративных циклов / M.C. Львов // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 122-136. — Бібліогр.: 23 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/131398 004.421.6 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Программно-технические комплексы Программно-технические комплексы
spellingShingle	Программно-технические комплексы Программно-технические комплексы Львов, M.C. Анализ линейно определенных итеративных циклов Кибернетика и системный анализ
description	Представлен новый метод доказательства инвариантности системы линейных неравенств, а также завершаемости линейно определенных итеративных циклов императивных программ. Тело цикла — линейный оператор, преобразующий вектор переменных программы. Метод учитывает предусловие цикла, а также условие повторения цикла в виде совокупности систем линейных неравенств. Метод основан на построении и анализе спектра этого оператора и вычислении числа итераций цикла, после выполнения которых инвариантность либо обеспечивается, либо опровергается. Теоретический материал работы иллюстрируется примерами.
format	Article
author	Львов, M.C.
author_facet	Львов, M.C.
author_sort	Львов, M.C.
title	Анализ линейно определенных итеративных циклов
title_short	Анализ линейно определенных итеративных циклов
title_full	Анализ линейно определенных итеративных циклов
title_fullStr	Анализ линейно определенных итеративных циклов
title_full_unstemmed	Анализ линейно определенных итеративных циклов
title_sort	анализ линейно определенных итеративных циклов
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
topic_facet	Программно-технические комплексы
url	http://dspace.nbuv.gov.ua/handle/123456789/131398
citation_txt	Анализ линейно определенных итеративных циклов / M.C. Львов // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 122-136. — Бібліогр.: 23 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT lʹvovmc analizlinejnoopredelennyhiterativnyhciklov
first_indexed	2025-07-09T15:22:19Z
last_indexed	2025-07-09T15:22:19Z
_version_	1837183315298222080
fulltext	M.C. ËÜÂÎÂ ÓÄÊ 004.421.6 ÀÍÀËÈÇ ËÈÍÅÉÍÎ ÎÏÐÅÄÅËÅÍÍÛÕ ÈÒÅÐÀÒÈÂÍÛÕ ÖÈÊËÎÂ Àííîòàöèÿ. Ïðåäñòàâëåí íîâûé ìåòîä äîêàçàòåëüñòâà èíâàðèàíòíîñòè ñèñòåìû ëèíåéíûõ íåðàâåíñòâ, à òàêæå çàâåðøàåìîñòè ëèíåéíî îïðåäåëåííûõ èòåðàòèâíûõ öèêëîâ èìïåðà- òèâíûõ ïðîãðàìì. Òåëî öèêëà — ëèíåéíûé îïåðàòîð, ïðåîáðàçóþùèé âåêòîð ïåðåìåííûõ ïðîãðàììû. Ìåòîä ó÷èòûâàåò ïðåäóñëîâèå öèêëà, à òàêæå óñëîâèå ïîâòîðåíèÿ öèêëà â âèäå ñîâîêóïíîñòè ñèñòåì ëèíåéíûõ íåðàâåíñòâ. Ìåòîä îñíîâàí íà ïîñòðîåíèè è àíàëèçå ñïåêòðà ýòîãî îïåðàòîðà è âû÷èñëåíèè ÷èñëà èòåðàöèé öèêëà, ïîñëå âûïîëíåíèÿ êîòîðûõ èíâàðèàíòíîñòü ëèáî îáåñïå÷èâàåòñÿ, ëèáî îïðîâåðãàåòñÿ. Òåîðåòè÷åñêèé ìàòåðèàë ðàáî- òû èëëþñòðèðóåòñÿ ïðèìåðàìè. Êëþ÷åâûå ñëîâà: ñòàòè÷åñêèé àíàëèç ïðîãðàìì, ëèíåéíûå èíâàðèàíòû öèêëîâ, èíâàðè- àíòíûå ñèñòåìû ëèíåéíûõ íåðàâåíñòâ. ÂÂÅÄÅÍÈÅ Ïðîáëåìà äîêàçàòåëüñòâà ïðàâèëüíîñòè êîìïüþòåðíûõ ïðîãðàìì áûëà ïîñòàâ- ëåíà â îñíîâîïîëàãàþùèõ ðàáîòàõ Ð. Ôëîéäà [1] è ×. Õîàðà [2]. Ñâîéñòâî ïðà- âèëüíîñòè ïðîãðàììû ôîðìóëèðóþò â òåðìèíàõ åå òîòàëüíîé (ïîëíîé) êîððåêò- íîñòè (ïðàâèëüíîñòè). Ïðîãðàììà P íàçûâàåòñÿ òîòàëüíî êîððåêòíîé, åñëè íà åå âõîäå X â ðåçóëü- òàòå âûïîëíåíèÿ ïðåäóñëîâèÿ �( )X îíà çàâåðøàåò ñâîþ ðàáîòó è íà âûõîäå P X( ) âûïîëíåíî ïîñòóñëîâèå �( ( ))P X . Ïðîãðàììà íàçûâàåòñÿ ÷àñòè÷íî êîð- ðåêòíîé, åñëè èç ïðåäïîëîæåíèÿ �( )X è çàâåðøåíèÿ P ñëåäóåò �( ( ))P X . Äîêàçàòåëüñòâî çàâåðøàåìîñòè ïðîãðàììû ÷àñòî íåîáõîäèìî îñóùåñòâëÿòü íåçàâèñèìî îò äîêàçàòåëüñòâà åå ÷àñòè÷íîé êîððåêòíîñòè. Àëãîðèòìè÷åñêàÿ íåðàç- ðåøèìîñòü ïðîáëåìû îñòàíîâêè îçíà÷àåò, ÷òî îáùåãî àëãîðèòìà äîêàçàòåëüñòâà çàâåðøàåìîñòè ïðîãðàììû íå ñóùåñòâóåò. Äëÿ äîêàçàòåëüñòâà ÷àñòè÷íîé êîððåêòíîñòè ïðîãðàìì Ð. Ôëîéä è ×. Õîàð ïðåäëîæèëè èäåþ ïîñòðîåíèÿ èíâàðèàíòîâ öèêëîâ [1] è èíâàðèàíòíûõ ñîîòíî- øåíèé â êîíòðîëüíûõ òî÷êàõ ïðîãðàìì [2], ÷òî ïîçâîëÿåò äîêàçûâàòü êîððåêòíîñòü ïðîãðàììû ìåòîäîì ìàòåìàòè÷åñêîé èíäóêöèè. Òàêèì îáðàçîì, âîçíèêëà ïðîáëåìà ïîèñêà ïðîãðàììíûõ èíâàðèàíòîâ êàê êëþ÷åâàÿ ïðîáëåìà àíàëèçà ñâîéñòâ ïðîãðàìì. Îñíîâíîå âíèìàíèå â íàñòîÿùåå âðåìÿ óäåëÿåòñÿ çàäà÷å ïîñòðîåíèÿ ïîëèíîìè- àëüíûõ èíâàðèàíòîâ òèïà ðàâåíñòâ. Ìíîæåñòâî èíâàðèàíòîâ òèïà ðàâåíñòâ îáðàçóåò ïîëèíîìèàëüíûé èäåàë, êîíå÷íûé áàçèñ êîòîðîãî ñëåäóåò ïîñòðîèòü. Â îáùåì ñëó- ÷àå çàäà÷à ïîñòðîåíèÿ òàêîãî áàçèñà åùå íå ðåøåíà. Â [3] ïðåäëîæåíû îáùèå èòåðà- òèâíûå ìåòîäû ãåíåðàöèè ïðîãðàììíûõ èíâàðèàíòîâ, ïðèìåíÿåìûå äëÿ ìíîãèõ ïðåäìåòíûõ îáëàñòåé. Â [4–7] ïðèâåäåí ìåòîä äîêàçàòåëüñòâà èíâàðèàíòíîñòè ïîëè- íîìà è ïîñòðîåíèÿ áàçèñà âåêòîðíîãî ïðîñòðàíñòâà ïîëèíîìèàëüíûõ èíâàðèàíòîâ 122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 © M.C. Ëüâîâ, 2016 îãðàíè÷åííîé ñòåïåíè. Â [8] äàíî ðåøåíèå çàäà÷ ïîñòðîåíèÿ áàçèñà âåêòîðíîãî ïðî- ñòðàíñòâà ïîëèíîìèàëüíûõ èíâàðèàíòîâ äëÿ êëàññà ïðîãðàìì c ïðîöåäóðàìè, âñå âû÷èñëåíèÿ â êîòîðîé ëèíåéíû. Ìíîãèå ðàáîòû, íàïðèìåð [9–13], ïîñâÿùåíû áîëåå ÷àñòíîé, íî êëþ÷åâîé çàäà÷å ïîñòðîåíèÿ èíâàðèàíòíûõ ðàâåíñòâ äëÿ èòåðàòèâíûõ öèêëîâ. Â ÷àñòíîñòè, â [11–13] èññëåäóåòñÿ çàäà÷à ïîñòðîåíèÿ áàçèñà èäåàëà ïîëè- íîìèàëüíûõ èíâàðèàíòíûõ ðàâåíñòâ äëÿ ëèíåéíûõ öèêëîâ. Çàäà÷à äîêàçàòåëüñòâà èíâàðèàíòíîñòè íåðàâåíñòâ ìåíåå èçó÷åíà. Îñíîâíàÿ ñëîæíîñòü çäåñü — áåñêîíå÷íîñòü áàçèñà ìåòàèäåàëà [20] ïîëèíîìèàëüíûõ íåðà- âåíñòâ [12, 13]. Èòåðàòèâíûå ìåòîäû ðåøåíèÿ çàäà÷è îïèñàíèÿ ëèíåéíûõ èíâà- ðèàíòíûõ íåðàâåíñòâ ðàññìàòðèâàëàñü â [14–17]. Â [14] ðåøåíà çàäà÷à ãåíåðàöèè ïðîñòåéøèõ èíâàðèàíòíûõ íåðàâåíñòâ. Â [15, 16] ê çàäà÷å ïîèñêà ëèíåéíûõ èí- âàðèàíòíûõ íåðàâåíñòâ ïðèìåíÿþòñÿ îáùèå èòåðàòèâíûå ìåòîäû. Â [19] èçëî- æåí ìåòîä äîêàçàòåëüñòâà èíâàðèàíòíîñòè ñèñòåìû ëèíåéíûõ íåðàâåíñòâ äëÿ êëàññà ëèíåéíûõ èòåðàòèâíûõ öèêëîâ ñ äåéñòâèòåëüíûìè ñîáñòâåííûìè ÷èñëà- ìè ëèíåéíîãî îïåðàòîðà â òåëå öèêëà. Â íàñòîÿùåé ðàáîòå ýòîò ìåòîä ðàñïðîñò- ðàíÿåòñÿ íà âåñü êëàññ ëèíåéíûõ èòåðàòèâíûõ öèêëîâ è ïðèìåíÿåòñÿ äëÿ äîêàçà- òåëüñòâà èõ çàâåðøàåìîñòè. Ìàòåìàòè÷åñêèå îïðåäåëåíèÿ, ðåçóëüòàòû è àëãîðèòìû êîìïüþòåðíîé àë- ãåáðû, èñïîëüçóåìûå â ñòàòüå, ìîæíî íàéòè, íàïðèìåð, â [20–23]. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ïóñòü K n — n-ìåðíîå âåêòîðíîå ïðîñòðàíñòâî íàä ëèíåéíî óïîðÿäî÷åííûì êîíñòðóêòèâíûì ïîëåì K è K — àëãåáðàè÷åñêîå çàìûêàíèå ïîëÿ K. Îïðåäåëåíèå 1. Ëèíåéíûì ïîëóàëãåáðàè÷åñêèì ìíîæåñòâîì M x xn( , ... , )1 íàçûâàåòñÿ îáëàñòü K n , îïðåäåëÿåìàÿ áåñêâàíòîðíîé ôîðìóëîé â ñèãíàòóðå ëîãè÷åñêèõ ñâÿçîê � �, & , ñ ëèíåéíûìè íåðàâåíñòâàìè îò ïåðåìåííûõ x xn1, ... , â êà÷åñòâå àòîìîâ. Åñëè îáëàñòü M çàäàåòñÿ ôîðìóëîé F X( ), ò.å. M X F X� { }: ( ) , áóäåì îáîçíà÷àòü åå M F X( ( )). Îïðåäåëåíèå 2. Ïóñòü X x xn� ( , ... , ),1 b b bn� ( , ... , )1 — âåêòîðû ïåðåìåí- íûõ. Ëèíåéíî îïðåäåëåííûì öèêëîì ñ ïðåäóñëîâèåì íàçûâàåòñÿ ôðàãìåíò èìïå- ðàòèâíîé ïðîãðàììû âèäà X : � b; // S b( ) — ïðåäóñëîâèå While U X( , b) do X A X: � � , (1) ãäå S b( ), U X b( , ) — áåñêâàíòîðíûå ôîðìóëû ïðèêëàäíîé ëîãèêè ëèíåéíûõ ïîëóàëãåáðàè÷åñêèõ ìíîæåñòâ, A — ìàòðèöà ëèíåéíîãî îïåðàòîðà K Kn n� . Íåòåðìèíèðîâàííûì öèêëîì, àññîöèèðîâàííûì ñ öèêëîì (1), íàçûâàåòñÿ öèêë âèäà X : � b; // S b( ) — ïðåäóñëîâèå While True \| False do X A X: � � , (2) êîëè÷åñòâî ïîâòîðåíèé êîòîðîãî íåäåòåðìèíèðîâàíî. Çàìå÷àíèå 1. Îïåðàòîðû X b:� , X A X:� � èíòåðïðåòèðóþòñÿ êàê îäíî- âðåìåííûå ïðèñâîåíèÿ ïåðåìåííûì ëåâûõ ÷àñòåé çíà÷åíèé ïðàâûõ ÷àñòåé. Îïðåäåëåíèå 3. Ïîñëåäîâàòåëüíîñòü { }b m( ) , îïðåäåëåííàÿ ðåêóðñèâíûìè ñîîòíîøåíèÿìè b b b Ab mm m( ) ( ) ( ), , , ,0 1 0 1� � �� , (3) ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 123 íàçûâàåòñÿ îðáèòîé ëèíåéíîãî îïåðàòîðà A ñ íà÷àëüíîé òî÷êîé b è îáîçíà÷àåòñÿ Orbit A b( , ) . Îïðåäåëåíèå 4. Ëèíåéíî îïðåäåëåííûé öèêë (1) íàçûâàåòñÿ çàâåðøàåìûì, åñëè äëÿ ëþáîãî b M S X� ( ( )) ïîñëåäîâàòåëüíîñòü (3) ïðè íåêîòîðîì íàòóðàëüíîì m m b� �� ( ) óäîâëåòâîðÿåò ñîîòíîøåíèþ � � U b bm( , )( ) . Òàêèì îáðàçîì, åñëè öèêë çàâåðøàåì, äëÿ êàæäîãî b M S X� ( ( )) ñóøåñòâóåò íàè- ìåíüøåå íàòóðàëüíîå ÷èñëî m b� ( ) , íà êîòîðîì öèêë (1) çàâåðøàåòñÿ. Îïðåäåëåíèå 5. Ïóñòü a c K n, � . Ëèíåéíîå íåðàâåíñòâî L a c X b a X c b df ( , , , ) ( , ) ( , )� (4) íàçûâàåòñÿ óñëîâíûì èíâàðèàíòîì ëèíåéíî îïðåäåëåííîãî öèêëà (1) (ñ ïðåä- óñëîâèåì S b( )), åñëè äëÿ ëþáîãî b M S X� ( ( )) Orbit A b( , ) (ñì. (3)) óäîâëåòâî- ðÿåò ñîîòíîøåíèÿì S b L a c b b( ) ( , , , )� , U b b L a c b b m m bm m( , ) ( , , , ), , , , ( )( ) ( ) �� 1 1 2 � . Çàìå÷àíèå 2. Åñëè öèêë (1) íå çàâåðøàåòñÿ (ðàñõîäèòñÿ) â íåêîòîðîé òî÷êå b , òî m b� ( ) ñëåäóåò ñ÷èòàòü ðàâíûì áåñêîíå÷íîñòè: m b� � ��( ) . Ïðèìåð 1. Ïóñòü S x y x y( , ) ( ) & ( )� 0 1 0 1 , U x y b b x b y b( , , , ) (\| \| ) & ( \| \| )1 2 1 2�� , A � � � � � � 3 5 4 5 4 5 3 5 / / / / , L x y b b a c� � � � �2 2 1 1 2 21 2 / / ( , ), ( , ) . Â ýòîì ïðèìåðå ëèíåéíûé îïåðàòîð A — îïåðàòîð ïîâîðîòà íà óãîë � � arctg ( / )4 3 . Íà÷àëüíàÿ òî÷êà b ïðèíàäëåæèò åäèíè÷íîìó êâàäðàòó. Îðáèòà ëè- íåéíîãî îïåðàòîðà A — ïîñëåäîâàòåëü- íîñòü, êàæäàÿ òî÷êà êîòîðîé ëåæèò íà îêðóæíîñòè x y b b2 2 1 2 2 2� � � . Óñëîâèå ïîâòîðåíèÿ öèêëà: òî÷êà ( , )x y ëåæèò âíå êâàäðàòà ñî ñòîðîíîé 2� è öåíòðîì â òî÷êå ( , ) b b1 2 . Ïîýòîìó öèêë çàâåð- øèòñÿ, êîãäà òî÷êà ïîïàäåò âíóòðü ýòîãî êâàäðàòà, ò.å. ñîâåðøèò ïîâîðîò íà óãîë � ��2k ñ òî÷íîñòüþ �. Ïîñêîëüêó óãîë � íåñîèçìåðèì ñ �, îðáèòà îïåðàòîðà A ïðåäñòàâëÿåò âñþäó ïëîòíîå ìíîæåñòâî íà îêðóæíîñòè x y b b2 2 1 2 2 2� � � ; ñëå- 124 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 U(X, b) A := A � X Ñ //S(b) Ðèñ. 1. Ñõåìà ëèíåéíî îïðåäåëåííîãî öèêëà ñ êîíòðîëüíîé òî÷êîé Ñ , â êîòî- ðîé îïðåäåëåí èíâàðèàíò ( , ) ( , )a X c b Ðèñ. 2. Ãåîìåòðè÷åñêàÿ èëëþñòðàöèÿ ëèíåéíî îïðåäåëåííîãî öèêëà b L a c X b( , , , ) �U X b( , ) äîâàòåëüíî, öèêë çàâåðøèòñÿ. Íèæå îñíîâíîé àëãîðèòì áóäåò ïðèìåíÿòüñÿ äëÿ äîêàçàòåëüñòâà òîãî, ÷òî L x y b b� � �2 21 2 — ýòî óñëîâíûé èíâàðèàíò öèêëà. Â íàñòîÿùåé ðàáîòå ïîêàçàíî, ÷òî ïðîáëåìû çàâåðøàåìîñòè öèêëà (1) è äî- êàçàòåëüñòâà èíâàðèàíòíîñòè ëèíåéíîãî íåðàâåíñòâà àëãîðèòìè÷åñêè ðàçðåøè- ìû äëÿ ëþáîãî ëèíåéíîãî îïðåäåëåííîãî öèêëà (1). ÏÐÅÄÑÒÀÂËÅÍÈÅ ËÈÍÅÉÍÎÃÎ ÍÅÐÀÂÅÍÑÒÂÀ Æîðäàíîâîé êëåòêîé íàçûâàåòñÿ m m� ìàòðèöà âèäà J ( )� � � � � � � � � � � � � � � � � � � � � � � � � � 1 0 0 0 1 0 0 � � � � . (5) Ìàòðèöà îïåðàòîðà A â æîðäàíîâîé ôîðìå èìååò âèä A J J J J k k k k � � � � � � � � 1 1 2 2 1 1 0 0 0 0 0 0 0 0 ( ) ( ) ( ) ( ) � � � � � � � � � � � � , ò.å. îíà ñîñòàâëåíà èç íåñêîëüêèõ æîðäàíîâûõ êëåòîê ðàçëè÷íûõ ðàçìåðîâ, ðàñïîëîæåííûõ ïî ãëàâíîé äèàãîíàëè, ïðè÷åì êàæäàÿ æîðäàíîâà êëåòêà îïðå- äåëÿåòñÿ ñâîèì ñîáñòâåííûì çíà÷åíèåì � j îïåðàòîðà A. Â ÷àñòíîñòè, åñëè ëèíåéíûé îïåðàòîð â òåëå öèêëà (1) äèàãîíàëèçèðóåì, â áàçèñå ñîáñòâåííûõ âåêòîðîâ åãî ìàòðèöà èìååò âèä A n � � � � � � � � � � � � � � � � � � � 1 2 0 0 0 0 0 0 � � � . Ïóñòü f x( ) — ìèíèìàëüíûé õàðàêòåðèñòè÷åñêèé ìíîãî÷ëåí îïåðàòîðà A; � � { }� �1, ,� n — ìíîæåñòâî åãî êîðíåé (ñïåêòð A); e en1, ,� — ìíîæåñòâî ñîá- ñòâåííûõ âåêòîðîâ A; � �1 2, ... , k — ìíîæåñòâî êîìïëåêñíûõ ñîáñòâåííûõ ÷èñåë, à � �2 1k n� , ... , — ìíîæåñòâî äåéñòâèòåëüíûõ ñîáñòâåííûõ ÷èñåë, ïðè÷åì � � � �1 2 2 1 2� � � � � k k . Îïðåäåëèì âåêòîðû l e e l i e e1 1 2 2 1 2 1 2 1 2 � � � �( ), ( ) . Â áàçèñå ( , )l l1 2 ìàòðèöà A1 1 2 1 1 0 0 0 0 � � � � � � � � � � � � � � � � èìååò âèä B1 1 1 1 1 � � � � � � � � , ãäå � � � � 1 1 1 2 1 1� � � i i, . Ïðèìåíèâ òàêîå ïðåîáðàçîâàíèå êî âñåì ïàðàì ñîáñòâåííûõ âåêòîðîâ ñ ïîïàðíî ñîïðÿæåííûìè êîìïëåêñíûìè ñîáñòâåííûìè ÷èñëàìè, ïîëó÷èì ïðåäñòàâëåíèå ëèíåéíîãî îïåðàòîðà â òàê íàçûâàåìîé âåùåñòâåííîé æîðäàíîâîé ôîðìå ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 125 A B B Bk k ' . . . . . . . . . . . . . ... . ... . . ... � � 1 2 2 1 0 0 0 0 0 0 0 0 0 0 0 � 0 0 0 . . . . . . . . . . ... � n � � � � � � � � � � � � � � � � � � � � � . Çàìå÷àíèå 3. Ïîñëå ïåðåõîäà ê áàçèñó èç ñîáñòâåííûõ âåêòîðîâ êîýôôèöèåíòû íåðàâåíñòâà èçìåíÿòñÿ. Åñëè S ( )� — ìàòðèöà ïåðåõîäà, òî íîâûå çíà÷åíèÿ âåêòîðîâ a b, âû÷èñëÿþòñÿ ïî ôîðìóëàì a SaSS( ) � 1, b Sb SS( ) � 1. ×òîáû íå ïåðåãðóæàòü òåêñò íîâûìè îáîçíà÷åíèÿìè, áóäåì ïðèìåíÿòü îáîçíà÷åíèÿ, èñïîëüçóåìûå ðàíåå. Çàìåòèì, ÷òî ìàòðèöà âèäà �B df � � � � � � � � , ãäå � 2 2 1� � ÿâëÿåòñÿ ìàòðèöåé ïîâîðîòà âåêòîðà 2-ìåðíîãî ïðîñòðàíñòâà íà óãîë �, îïðåäåëåííûé ñîîòíîøåíè- ÿìè cos( )� �� , sin( )� � . Ïîýòîìó B r1 1 1 1 1 1 � � � � � � cos( ) sin( ) sin( ) cos( ) � � � � , r1 1 2 2� � �\| \|� � . Íåðàâåíñòâî (4), èíâàðèàíòíîñòü êîòîðîãî ðàññìàòðèâàåòñÿ äëÿ öèêëà (2) c êîíêðåòíûì íà÷àëüíûì çíà÷åíèåì b , îçíà÷àåò � � X Orbit A b a X c b( , )( , ) ( , ). Àëãîðèòì äîêàçàòåëüñòâà èíâàðèàíòíîñòè (4) áóäåì ôîðìóëèðîâàòü â ýêâèâàëåíò- íîì âèäå: Sup X Orbit A b a X c b � ( , ) ( , ) ( , ). Ðàññìîòðèì ëèíåéíóþ ôîðìó a x a x a x a Xn n df 1 1 2 2� � � �� ( , ). Ïðåîáðàçî- âàíèå X A X: � ïåðåâîäèò ýòó ôîðìó â ( , )a AX , à m-êðàòíàÿ èòåðàöèÿ öèêëà, îïèñûâàåìàÿ ïðåîáðàçîâàíèåì X A Xm: � , — ïåðåâîäèò â ( , )a A Xm . Ïóñòü X x x X x xk k k1 1 2 2 1 2� � ( , ), , ( , )� , a a a a a ak k k1 1 2 2 1 2� � ( , ), , ( , )� . Òîãäà ( , ) ( , ) ( , )a X a X a X a x a xk k k k n n� � � � � �� 1 1 2 1 2 1� � . (6) Ïðåîáðàçîâàíèå ( , )a AX ëèíåéíîé ôîðìû ìîæåò áûòü çàïèñàíî â âèäå ( , ) ( , ) ( , )a AX a B X a B X a x ak k k k k k n� � � � � �� 1 1 1 2 1 2 1 2 1� �� n nx , (7) à åãî m-ÿ èòåðàöèÿ — â âèäå ( , ) ( , ) ( , )a A X a B X a B X a xm m k k m k k m k k� � � � �� 1 1 1 2 1 2 1 2 1� �� n m n na x . (8) Ïåðåéäÿ â (8) ê ïðåäñòàâëåíèþ â âèäå B r Bj j j� � , ïîëó÷èì ( , ) ( , � ) ( , � )a A X r a B X r a B X am m m k m k k m k k m k� � � � � �1 1 1 1 2 1 2� � 1 2 1x a xk n m n n� � �� . ÌÅÒÎÄ ÏÐÎÂÅÐÊÈ ÈÍÂÀÐÈÀÍÒÍÎÑÒÈ ÍÅÐÀÂÅÍÑÒÂÀ ÄËß ÄÈÀÃÎÍÀËÈÇÈÐÓÅÌÎÃÎ ËÈÍÅÉÍÎÃÎ ÎÏÅÐÀÒÎÐÀ Ðàññìîòðèì âîïðîñ î ìíîæåñòâå çíà÷åíèé îðáèòû îïåðàòîðà ( , � )a B Xm 1 1 1 �� ( , � )a B Xk k m k äëÿ íà÷àëüíîãî çíà÷åíèÿ b b bk ( ) ( ) ( )( , , )0 1 0 0� � , ãäå b b bj j j� ( , )2 1 2 , j k�1, ,� . Áóäåì èíòåðïðåòèðîâàòü ïàðû X j , êàê òî÷êè íà 126 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 2-ìåðíîé ïëîñêîñòè, à ïðåîáðàçîâàíèÿ � cos( ) sin( ) sin( ) cos( ) B j df j j j j � � � � � � � � � � — êàê ïîâî- ðîòû òî÷åê X j íà óãîë � j . Ëåììà 1. Ïóñòü B df ( ) cos( ) sin( ) sin( ) cos( ) � � � � � � � � � � � . (9) Åñëè óãîë � ñîèçìåðèì ñ �, îðáèòà Orbit B b( ), )( )� 0 êîíå÷íà äëÿ ëþáîãî íà- ÷àëüíîãî çíà÷åíèÿ b b b( ) ( ) ( )( , )0 1 0 2 0� , à åñëè � íåñîèçìåðèì ñ �, ýòà îðáèòà áåñêîíå÷íà è âñþäó ïëîòíà íà îêðóæíîñòè x y b b2 2 1 0 2 2 0 2� � �( ) ( )( ) ( ) , ò.å. äëÿ ëþáîé òî÷êè D x y( , )0 0 , ëåæàùåé íà ýòîé îêðóæíîñòè, äëÿ ëþáîãî ïîëîæèòåëü- íîãî ÷èñëà � â �-îêðåñòíîñòè òî÷êè D ñóùåñòâóåò òî÷êà ïîñëåäîâàòåëüíîñòè { }( , )( ) ( )x yj j j� � 0 . Äîêàçàòåëüñòâî î÷åâèäíî. Îïðåäåëåíèå 6. Óãëû � è íàçîâåì �-ýêâèâàëåíòíûìè, åñëè � � � r äëÿ íåêîòîðîãî r �Rat . Ïóñòü B0 è B1 — îïåðàòîðû âèäà (9) ïîâîðîòà ïëîñêîñòè íà óãëû �0 , �1 è Orbit B X( , )0 0 , Orbit B X( , )1 1 — èõ îðáèòû. Ëåììà 2. Åñëè óãëû �0 è �1 îïåðàòîðîâ ïîâîðîòà B0 , B1 íå ÿâëÿþòñÿ �-ýê- âèâàëåíòíûìè è íåñîèçìåðèìû ñ �, äëÿ ëþáûõ òî÷åê D x y0 0 0( , ), D x y1 1 1( , ), ëå- æàùèõ íà åäèíè÷íîé îêðóæíîñòè x y2 2 1� � , äëÿ ëþáîãî ïîëîæèòåëüíîãî ÷èñ- ëà � â �-îêðåñòíîñòÿõ òî÷åê D0 , D1 ñóùåñòâóþò òî÷êè îðáèò Orbit B X( , )0 0 , Orbit B X( , )1 1 ñ îäèíàêîâûìè íîìåðàìè. Äîêàçàòåëüñòâî. Ïóñòü 0 0( ) , 1 0( ) — íà÷àëüíûå óãëû îðáèò îïåðàòîðîâ B0 , B1; 0 * , 1 * — óãëû òî÷åê D0 , D1. Òîãäà äåéñòâèå îïåðàòîðîâ B0 , B1 îïðåäåëÿåòñÿ ôîðìóëàìè � � � � 0 0 0 1 1 1 1 2( ) ( ), , , ,k kk k k� � � � � � Ðàññìîòðèì ðàçíîñòü � � � � 1 0 1 0 1 0 1 2( ) ( ) ( ) ( ), , ,k k k k � � � � Îáîçíà÷èì O( , )� � �-îêðåñòíîñòü óãëà �, ò.å. îòêðûòûé èíòåðâàë äëèíû � ñ öåíòðîì â �. Ñîãëàñíî ëåììå 1 äëÿ ëþáîãî �� 0 ñóùåñòâóåò òàêîå k0 , ÷òî � � � 1 0 1 0 0 0 2 ( ) ( ) * ( / , ) k k O � . Äàëåå, ñóùåñòâóåò òàêîå k1, ÷òî � 0 0 1( )k k� � � O k k ( / , ) ( ) ( ) � � �2 1 0 0 0 . Ýòî îçíà÷àåò, ÷òî íàéäåòñÿ òàêîå íàèìåíüøåå k2 , ÷òî � �0 0 2 0 2 1 ( ) ( / , )� � O k k k . Òîãäà � � 0 0 0 2 1( ) ( , ) k k k O � � , � � 1 1 0 2 1( ) ( , ) k k k O � � . Ëåììà 3. Åñëè óãëû � �1, ... , k îïåðàòîðîâ ïîâîðîòà B Bk1, ... , íå ÿâëÿþòñÿ ïîïàðíî �-ýêâèâàëåíòíûìè è íåñîèçìåðèìû ñ �, äëÿ ëþáûõ òî÷åê D x y D x yk k k1 1 1( , ), ...`, ( , ), ëåæàùèõ íà åäèíè÷íîé îêðóæíîñòè x y2 2 1� � , äëÿ ëþáîãî ïîëîæèòåëüíîãî ÷èñëà � â �-îêðåñòíîñòÿõ D Dk1, ... , ñóùåñòâóþò òî÷êè îðáèò Orbit B X Orbit B Xk k( , ), , ( , )1 1 � ñ îäèíàêîâûìè íîìåðàìè. Ïðè äîêàçàòåëüñòâå èñïîëüçóåòñÿ ìåòîä ìàòåìàòè÷åñêîé èíäóêöèè è òåõíè- êà äîêàçàòåëüñòâà ëåììû 2. Ëåììà 4. Ïóñòü ( , ) ( , ) ( , )a X a X a Xk k� � �1 1 � — ëèíåéíàÿ ôîðìà è B1, ... ... , Bk — äâóìåðíûå îïåðàòîðû ïîâîðîòà íà óãëû � �1, ... , k ñîîòâåòñòâåííî; ïðè- ÷åì ýòè óãëû íå ÿâëÿþòñÿ ïîïàðíî �-ýêâèâàëåíòíûìè è íåñîèçìåðèìû ñ �. Îïðå- äåëèì äåéñòâèå îïåðàòîðà A ñëåäóþùèì îáðàçîì: ( , ) ( , ) . .. ( , )a AX a B X a B Xk k k� � �1 1 1 , ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 127 à íà÷àëüíîå çíà÷åíèå b b bk� ( , ... , )1 . Òîãäà Sup Sup S X Orbit A b X Orbit B b a X a X � � � � � `( , ) ( , ) ( , ) ( , ) 1 1 1 1 � up X Orbit B b k k k k a X � ( , ) ( , ) . (10) Äîêàçàòåëüñòâî. Äëÿ îïåðàòîðà (9) ðàññìîòðèì ëèíåéíóþ ôîðìó ( , )a X a x a y� �1 2 . Ïî óñëîâèþ, àðãóìåíòû ýòîé ôîðìû îïðåäåëåíû íà îêðóæ- íîñòè O ðàäèóñà r b b� � 1 2 2 2 ñ öåíòðîì â íà÷àëå êîîðäèíàò. Ôîðìà ( , )a X äîñ- òèãàåò ñâîåãî ìàêñèìóìà â òî÷êå M x yM M( , ) êàñàíèÿ ïðÿìîé a x a y c1 2� � ê ýòîé îêðóæíîñòè, ïðè÷åì x M , yM è c âû÷èñëÿþòñÿ ìåòîäàìè àíàëèòè÷åñêîé ãåîìåòðèè. Ïîëîæèì d a a� � 1 2 2 2 . Íåòðóäíî âû÷èñëèòü, ÷òî x a r d y a r d M M� �1 2, , max � � �a x a y rdM M1 2 . Ñîãëàñíî ëåììå 1 â ëþáîé �-îêðåñòíîñòè òî÷êè M ñóùåñòâóþò òî÷êè îðáè- òû Orbit B b( , ). Ïîýòîìó Sup X Orbit B b X O a X a X rd � � � � ( , ) ( , ) max ( , ) 1 1 1 1 1 1 . Ïóñòü M M k1, ... , — òî÷êè ìàêñèìóìà äëÿ ôîðì ( , ), ... , ( , )a X a Xk k1 1 íà O1. Ïî ëåììå 3 äëÿ ñèñòåìû ýòèõ òî÷åê è ëþáîãî ïîëîæèòåëüíîãî � â �-îêðåñòíîñòÿõ ýòèõ òî÷åê ñóùåñòâóþò òî÷êè D Dk1, ... , îðáèò îïåðàòîðîâ B Bk1, ... , ñ íà÷àëüíûìè çíà÷åíèÿìè b bk1 , ... , ñîîòâåòñòâåííî. Ïîýòîìó äëÿ âû÷èñëåíèÿ Sup X Orbit A b a X � ( , ) ( , ) ñëåäóåò âû÷èñëèòü max ( , ) X O i ia X � 1 è èñïîëüçîâàòü ðàâåíñòâî (10). Ëåììà 5. Ïóñòü ëèíåéíàÿ ôîðìà ( , )a X , äâóìåðíûå îïåðàòîðû B Bk1, ... , , îïå- ðàòîð A è íà÷àëüíîå çíà÷åíèå b îïðåäåëåíû òàê æå, êàê â ëåììå 4. Òîãäà çàäà÷ó âû- ÷èñëåíèÿ Sup X Orbit A b a X � ( , ) ( , ) ìîæíî ñâåñòè ê âû÷èñëåíèÿì ïî ôîðìóëå (10). Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî � �1, ... , l — êëàññ ýêâèâàëåíòíîñòè �1 ïî îòíîøåíèþ �-ýêâèâàëåíòíîñòè � � � � �i j i j ijr~ � � , rij �Rat. Ïîñêîëüêó òî÷êè îðáèò âñåõ îïåðàòîðîâ Bi ëåæàò íà åäèíè÷íîé îêðóæíîñòè, ìîæíî ñ÷èòàòü, ÷òî x y R x y i i i � � � � � � � � � � � 1 1 , ãäå Ri — îïåðàòîðû ïîâîðîòà íà óãëû r i1 �. Ïîýòîìó ( , ) ( , ) ( )a X a X a a R a R Xl l l l1 1 1 2 2 1� � � � � �� , à ( , ) ( , )a B X a B Xl l l1 1 1 � � �� ( )a B a R B a R B Xl l l1 1 2 2 2 1� . Òàêèì îáðàçîì, âñå ñëàãàåìûå ëèíåéíîé ôîðìû ñ �-ýêâèâàëåíòíûìè óãëàìè ìîæíî âûðàçèòü ÷åðåç îäíó ëèíåéíóþ ôîðìó è â ôîðìó- ëå (10) ìîæíî ñ÷èòàòü âñå óãëû ïîïàðíî íåýêâèâàëåíòíûìè. Ëåììà 6. Ïóñòü f x K x( ) [ ]� — ìíîãî÷ëåí è � �1, ... , k — êîìïëåêñíûå êîðíè f x( ) òàêèå, ÷òî \| \| \| \|� �1 1� � �� k , � � �j j ji� �cos( ) sin( ), j k�1, ... , . Òîãäà ïðî- áëåìà âû÷èñëåíèÿ êëàññîâ �-ýêâèâàëåíòíîñòè íà ìíîæåñòâå � �1, ... , k àëãîðèò- ìè÷åñêè ðàçðåøèìà. Äîêàçàòåëüñòâî. Ïóñòü �, � � � �� { }1,... , ,k r , r �Rat, � � �� cos( ) sin( )i , � � �cos( ) sin( )i , � � � � � �/ cos( ) sin( ) cos( ) sin( )� � � �i r i r — êîðåíü íåêî- òîðîé ñòåïåíè èç åäèíèöû. Àëãîðèòìû àðèôìåòè÷åñêèõ äåéñòâèé íàä àëãåáðàè÷åñ- êèìè ÷èñëàìè èçëîæåíû, íàïðèìåð, â [23]. Îñíîâíàÿ èäåÿ ñîñòîèò â ñëåäóþùåì: îïðåäåëèì ñèñòåìó ïîëèíîìèàëüíûõ ðàâåíñòâ ( ( ) )& ( ( ) )& ( )f u f w u� � �0 0 0� � è èñêëþ÷èì èç íåå ïåðåìåííûå u, � ìåòîäàìè òåîðèè èñêëþ÷åíèé [22] èëè áàçè- ñîâ Ãðåáíåðà [23]. Â ðåçóëüòàòå èìååì ìíîãî÷ëåí h w( ), îäèí èç äåëèòåëåé 128 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 êîòîðîãî äîëæåí áûòü ìèíèìàëüíûì ìíîãî÷ëåíîì íåêîòîðîãî êîðíÿ èç åäèíèöû. Òàêèì îáðàçîì, deg Gcd( ( , ( )))w h wd �1 0 äëÿ íåêîòîðîãî íàòóðàëüíîãî d h deg ( ). Ëåììà 7. Ïóñòü f x K x( ) [ ]� — ìíîãî÷ëåí è � �1, ... , n — åãî êîðíè. Òîãäà ïðîáëåìà ðàñïîçíàâàíèÿ êîëè÷åñòâà k êîðíåé òàêèõ, ÷òî \| \| \| \|� �1 � �� k è \| \| max (\| \| \| \| )� � �1 1� � �� n , àëãîðèòìè÷åñêè ðàçðåøèìà. Äîêàçàòåëüñòâî. Ïîëîæèì x u i� � �. Òîãäà f x( ) ìîæíî ïåðåïèñàòü, âûäå- ëèâ äåéñòâèòåëüíóþ è ìíèìóþ ÷àñòè f x( ): f u i f u i f u( ) ( , ) ( , )� � � �� re im . Ïîñêîëüêó \| \|x u2 2 2� � � , çàäà÷ó îïðåäåëåíèÿ ÷èñåë ñ ðàâíûìè ìîäóëÿìè ìîæíî ñôîðìóëèðîâàòü â âèäå ñèñòåìû ðàâåíñòâ ( ( , ) )& ( ( , ) )& ( )re imf u f u w u� � �� 0 0 02 2 . (11) Òàê êàê ïåðåìåííàÿ � âõîäèò â im f u( , )� â íå÷åòíîé ñòåïåíè, òî im f u( , )� � � �� im f u1 ( , ). Ïîëîæèâ � � 0, ïîëó÷èì re f u f u( , ) ( )0 � . Òàêèì îáðàçîì, (11) óïðîñòèòñÿ äî ñèñòåìû ( ( ) )& ( )f u w u� �0 02 . Èíûìè ñëîâàìè, äëÿ ýòîãî ñëó÷àÿ çàäà÷à ñâî- äèòñÿ ê îòäåëåíèþ è âû÷èñëåíèþ êðàòíîñòåé äåéñòâèòåëüíûõ êîðíåé f x( ). Ïðè � � 0 ñèñòåìà (11) óïðîñòèòñÿ äî ( ( , ) )& ( ( , ) ) &re imf fu u� �� 0 01 & ( )w u �2 2 0� . Ïîñêîëüêó ïåðåìåííàÿ � âõîäèò â ýòó ñèñòåìó â ÷åòíîé ñòå- ïåíè, ïðè èñêëþ÷åíèè ïåðåìåííûõ àëãîðèòì îïåðèðóåò ïî ñóòè ñ ïåðåìåííîé � �1 2� . Èñêëþ÷èâ èç ñèñòåìû ïåðåìåííûå u, � 2 , ïîëó÷èì ïîëèíîìèàëüíîå ðà- âåíñòâî g w( ) � 0, äåéñòâèòåëüíûå êîðíè êîòîðîãî — ñóòü êâàäðàòû ìîäóëåé êîì- ïëåêñíîé ÷àñòè ÷èñåë � �1, ... , n . Òåïåðü çàäà÷à ñâîäèòñÿ ê îòäåëåíèþ è îïðåäåëå- íèþ êðàòíîñòåé êîðíåé g w( ) � 0. Åñëè � i — ìàêñèìàëüíûé äåéñòâèòåëüíûé êîðåíü f x( ), à � j — ìàêñèìàëüíûé äåéñòâèòåëüíûé êîðåíü g x( ) è � �i j� , òî deg Gcd( ( , ))f g � 0 è � i — äåéñòâèòåëüíûé êîðåíü Gcd ( , )f g . Ïóñòü p — êðàò- íîñòü � i , à q — êðàòíîñòü � j è � �i j� . Òîãäà êðàòíîñòü � i ðàâíà p q�2 . Åñëè � �i j� , êðàòíîñòü èñêîìîãî ìàêñèìàëüíîãî êîðíÿ ðàâíà ëèáî p (ñëó÷àé 1), ëèáî 2q (ñëó÷àé 2). Ïðèìåð 2. Ðàññìîòðèì àëãîðèòìû àëãåáðàè÷åñêèõ âû÷èñëåíèé çàäà÷è äîêà- çàòåëüñòâà èíâàðèàíòíîñòè íåðàâåíñòâà, ñ÷èòàÿ, ÷òî A � � � � � � � � � � 0 1 0 0 0 1 2 0 0 . 1. Âû÷èñëåíèå õàðàêòåðèñòè÷åñêîãî ìíîãî÷ëåíà: f x A xE x x x x( ) \| \|� � � � � � � � � � � � � 1 0 0 1 2 0 23 , f x x( ) � 3 2 , � � � � �1 3 2 3 3 3 22 2 2� � �, * , * , � � � � � � � � � �� cos sin 2 3 2 3 i , � — ïåðâîîáðàçíûé êîðåíü ñòåïåíè 3 èç åäèíèöû. 2. Àëãîðèòì ëåììû 7. Ñèñòåìà óðàâíåíèé ëåììû 7: f u i u i u( ) ( , ) ( , )� � � �� re imf f ; ( ( , ) )& ( ( , ) )& ( )re imf fu u w u� � �� 0 0 02 2 ; ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 129 x 3 2 0 � � ( )u i� �� 3 2 0 ; ( )u u u u u u 3 2 2 3 3 2 2 2 3 2 0 3 0 3 2 0 3 0 � � ! " #" � � � ! "� � � � �#" (ñëó÷àé 1) � � � ! " #" u3 2 0 0� (ñëó÷àé 2). Ñëó÷àé 1: u u u w u u u 3 2 2 2 2 2 3 3 2 0 3 0 2 3 � � � � ! "" # " " � ! "" # " " � � � � � 3 0 3 4 0 4 1 0 4 0 2 2 2 2 3 3 u w u u u w � � � � ! "" # " " � � � � � � � � . Èòàê, q �1, p �1. Ìíîãî÷ëåí f x x( ) � 3 2 èìååò p q� �2 3 êîðíÿ ñ ìàêñè- ìàëüíûì ìîäóëåì. 3. Àëãîðèòì ëåììû 6. 3.1. Ïðîâåðêà ñîèçìåðèìîñòè óãëà � ñ �. Èìååì ñèñòåìó ( ( ) )&f x � 0 & ( ( ) )& ( )f w x uw2 0 0� � , x w x uw x w x uw u3 6 3 3 2 0 4 0 0 2 0 2 0 0 � � � ! " # " � � � � ! " # " � ( w w x uw u w x uw )3 3 3 3 2 0 2 0 0 1 0 2 0 0 � � � ! " # " � � � � ! " # " � � � � � � � � �Gcd ( , ) /u u u u u3 2 21 1 1 2 3� � , ò.å. � ñîèçìåðèì ñ �. 3.2. Ïðîâåðêà ñîèçìåðèìîñòè ðàçíîñòè óãëîâ � ��u ñ �. Ñèñòåìà èìååò âèä ( ( ) )& ( ( ) )& ( )f u f w u� � �0 0 0� � , u w u w w u 3 3 3 3 3 2 0 2 0 0 2 0 2 0 0 � � � ! " # " � � � � ! " # " �� w w u 3 3 1 0 2 0 0 � � � ! " # " �� Gcd ( , ) /w w w w w u 3 2 21 1 1 2 3� � �� , ò.å. óãëû �u , � �� -ýêâèâàëåíòíû. 3.3. Ïðåäñòàâëåíèå AX äëÿ ëèíåéíîé ôîðìû âèäà (7): A x y z � � � � � � � � � � 2 2 2 2 2 3 cos( / ) sin( / ) sin( / ) cos( � � � � � � � �/ ) , � � � � � � � � � � � � � � � � � � x y z23 T . 3.4. Âû÷èñëåíèå ìàòðèöû ïåðåõîäà ê æîðäàíîâîé ôîðìå. — Âû÷èñëåíèå ñîáñòâåííûõ âåêòîðîâ ìàòðèöû A � � � � � � � � � � � 0 1 0 0 0 1 2 0 0 . Ðåøèòü ñèñòåìó îäíîðîäíûõ ëèíåéíûõ óðàâíåíèé ( )( , , )A E x y z �� T 0, ïðè÷åì âû÷èñëåíèÿ îñóùåñòâëÿþòñÿ â ïîëå K ( )� ïî ìîäóëþ �3 2 . Ðàíã ñèñòåìû � � � x z x y y z � � � ! " # " 2 0 0 0 ðàâåí äâóì. Ôóíäàìåíòàëüíîå ðåøåíèå ñèñòåìû 130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 åñòü âåêòîð s � ( , , )� �2 1 . Ñîáñòâåííûå âåêòîðû îïåðàòîðà A: s s s1 1 2 1 2 2 2 2 3 3 2 31 1 1� � �( , , ), ( , , ), ( , , )� � � � � � . — Âû÷èñëåíèå ìàòðèöû ïåðåõîäà S è îáðàòíîé ìàòðèöû S 1: S � � � � � � � � � � � � � � � � 1 2 2 2 3 2 1 2 3 1 1 1 , S S � 1 2 3 2 2 3 2 2 2 3 2 3 2 1 3 1 2 3 2 1 21 det( ) � � � � � � � � � � � � � � 3 1 3 2 1 2 1 2 2 2 1 2 2 1 2 2 � � � � � � � � � � � � � � � � � � � � � . Òåîðåìà 1. Ïðîáëåìà äîêàçàòåëüñòâà èíâàðèàíòíîñòè íåðàâåíñòâà (4) äëÿ öèêëà (1) ñ äèàãîíàëèçèðóåìûì ëèíåéíûì îïåðàòîðîì A è ñ äàííîé íà÷àëüíîé òî÷êîé b àëãîðèòìè÷åñêè ðàçðåøèìà. Äîêàçàòåëüñòâî. Ïîñêîëüêó îïåðàòîð A äèàãîíàëèçèðóåì, ïðåäñòàâëåíèå ( , )a A Xm èìååò âèä ( , ) ( , � ) ( , � )a A X r a B X r a B X am m m k m k k m k k m k� � � � � �1 1 1 1 2 1 2� � 1 2 1x a xk n m n n� � �� . (12) Ïóñòü p è q — ÷èñëà, îïðåäåëåííûå â ëåììå 7 äëÿ õàðàêòåðèñòè÷åñêîãî ïî- ëèíîìà f x( ) îïåðàòîðà A. Äëÿ îïðåäåëåííîñòè áóäåì ñ÷èòàòü, ÷òî ñîáñòâåííûå ÷èñëà îïåðàòîðà A ñ ìàêñèìàëüíûìè ìîäóëÿìè èìåþò íà÷àëüíûå íîìåðà � � � � � �1 2 2 1 2 2 1 2, , ... , , ,q q q q p � �� , ïðè÷åì � � � �1 2 2 1 2� � , ..., q q . Òîãäà (12) ìîæíî ïðåäñòàâèòü â âèäå ( , )a A Xm � � � � � �� r a B X r a B X a xm m q m q q m q q m q q1 1 1 1 2 1 2 1 2 1( , � ) ( , � )� � .. . ( )� �� 2 2 2 1q p m q p q p ma x L , ãäå L m 1 ( )— m-ÿ èòåðàöèÿ ëèíåéíîé ôîðìû âèäà (12) îò îñòàâøèõñÿ ïåðåìåí- íûõ. Íåðàâåíñòâî (4) ìîæíî ïåðåïèñàòü â âèäå ( , � ) ( , � )a B X a B Xm q q m q1 1 1 � � �� 2 1 2 1 2 1 2 2 2 1 1 1 1 q m q q q p m q p q p m ma x a x r L.. . ( ) r c b m 1 ( , ) . Îáîçíà÷èì L m 0 ( ) ëèíåéíóþ ôîðìó ( , � ) ( , � )a B X a B X a xm q q m q q m q q q p1 1 1 2 1 2 1 2 1 2 � � � � �� m q p q pa x2 2� � , ãäå � j � $1. Ïîëó÷èì L r L r c bm m m m0 1 1 1 1 1( ) ( ) ( , )� . (13) Òàê êàê r p q n1 2 1� � �max (\| \| , , \| \| )� �� , ïðè m � � èìååì 1 0 1 1 r L m � . Ñëåäîâà- òåëüíî, äëÿ ëþáîãî �� 0 ñóùåñòâóåò òàêîå íàòóðàëüíîå ÷èñëî m0 , ÷òî ïðè m m� 0 èìååì 1 1 1 r L m m( ) % �. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 131 Èìåþò ìåñòî ñëåäóþùèå ñëó÷àè. 1. Åñëè r1 1% , òî lim ( , ) m mr c b �� 1 1 . Òîãäà: — ïðè ( , )c b % 0 äëÿ ëþáîãî �� 0 ñóùåñòâóåò òàêîå m m1 % , ïðè êîòîðîì L r L Lm m m m 0 1 1 0 1( ) ( ) ( )� % � % � � , ò.å. ïðè m m m� max ( , )0 1 íåðàâåíñòâî (4) íå âûïîëíÿåòñÿ; — ïðè ( , )c b � 0 èìååì L r L Lm m m m 0 1 1 0 1( ) ( ) ( )� % � % �� , ò.å. ïðè m m m� max ( , )0 1 íåðàâåíñòâî (4) âûïîëíÿåòñÿ. 2. Åñëè r1 1� , òî lim ( , ) ( , ) m mr c b c b �� 1 1 . Ïðè m m� 0 èìååì L r Lm m m 0 1 1 1( ) ( )� % % � %L c bm 0 ( ) ( , )� . Ñëåäîâàòåëüíî, ïðè m m� 0 äëÿ âûïîëíåíèÿ íåðàâåíñòâà (4) äîëæíî âûïîëíÿòüñÿ óñëîâèå L c bm 0 ( ) ( , )% . 3. Åñëè r1 1� , òî lim ( , ) m mr c b �� 1 0 1 . Ïðè m m� 0 èìååì L r Lm m m 0 1 1 1( ) ( )� % % � %L m 0 0( ) � . Ñëåäîâàòåëüíî, äëÿ âûïîëíåíèÿ íåðàâåíñòâà (4) ïðè m m m� max ( , )0 1 äîëæíî âûïîëíÿòüñÿ óñëîâèå L m 0 0( ) % . Íåðàâåíñòâî âèäà L cm 0 ( ) % äëÿ ïðîèçâîëüíîãî c íà ïðîèçâîëüíîì ìíîæåñòâå S ýêâèâàëåíòíî Sup X S mL c � % 0 ( ) . Ïîýòîìó íåçàâèñèìî îò ñëó÷àåâ 1–3, äîêàçàòåëüñòâî èíâàðèàíòíîñòè ñâîäèòñÿ ê âû÷èñëåíèþ Sup X Orbit A b mL � ( , ) ( ) 0 , L a B b a B b a bm m q q m q q m q q0 1 1 1 2 1 2 1 2 1 ( ) ( , � ) ( , � )� � � � �� 2 2 2q p m q p q pa b . Àëãîðèòì âû÷èñëåíèÿ Sup X Orbit A b m q q m qa B b a B b � � � ( , ) ( , � ) ( , � )1 1 1 � ïðèâåäåí â ëåììàõ 4, 6. Âû÷èñëåíèå ëèíåéíîé ÷àñòè Sup X Orbit A b q m q qa b � � � � � ( , ) ...� 2 1 2 1 2 1 � � � � �� 2 2 2q p m q p q pa b îñóùåñòâëÿåòñÿ íåïîñðåäñòâåííî äëÿ ÷åòíîãî è íå÷åòíî- ãî çíà÷åíèé m. Îáùèé àëãîðèòì äîêàçàòåëüñòâà èíâàðèàíòíîñòè íåðàâåíñòâà (4) äëÿ öèê- ëà (1) è äàííîãî íà÷àëüíîãî çíà÷åíèÿ b çàêëþ÷àåòñÿ â ñëåäóþùåì. Øàã 1. Ïðèâåñòè íåðàâåíñòâî ê âèäó (13). Øàã 2. Âû÷èñëèòü çíà÷åíèå m m m* max ( , )� 0 1 è îïðåäåëèòü ïðèíàäëåæ- íîñòü ê îäíîìó èç âàðèàíòîâ: 1, 2 èëè 3. Øàã 3. Ïðîâåðèòü âûïîëíåíèå óñëîâèÿ èíâàðèàíòíîñòè äëÿ ñëó÷àÿ, îïðåäå- ëåííîãî â ï. 2, è äëÿ çíà÷åíèé m m� � . Øàã 4. Ïðîâåðèòü íåðàâåíñòâî (4), âûïîëíÿÿ öèêë (1) äëÿ âñåõ çíà÷åíèé m m � . 132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 Ïðèìåð 3 (ïðîäîëæåíèå ïðèìåðà 1). Íàïîìíèì, ÷òî S b b b b( , ) ( )& ( )1 2 1 20 1 0 1� , U x y b b x b y b( , , , ) (\| \| )&(\| \| )1 2 1 2� � � � � � , A � � � � � � 3 5 4 5 4 5 3 5 / / / / , L x y b b a c� � � � �2 2 1 1 2 21 2 / / ( , ), ( , ) . Âûïîëíèì øàã 1. — Âû÷èñëèòü õàðàêòåðèñòè÷åñêèé ìíîãî÷ëåí A � � � � � � 3 5 4 5 4 5 3 5 / / / / , \| \| / / / / /A xE x x x x � � � 3 5 4 5 4 5 3 5 6 5 12 . — Íàéòè êîëè÷åñòâî êîðíåé ñ ìàêñèìàëüíûì ìîäóëåì: x x2 6 5 1 0 � �/ � ( ) / ( )u i u i� � � �� 2 6 5 1 0 , u u u u u u 2 2 2 26 5 1 0 2 6 5 0 6 5 1 0 3 5 0 � � � � ! # � � � � � � � � �/ / / / ! # (ñëó÷àé 1) � � � � � ! # u u2 6 5 1 0 0 / � (ñëó÷àé 2). Âû÷èñëèì ñëó÷àé 1 (ñëó÷àé 2 òðèâèàëåí): u u u w u 2 2 2 2 26 5 1 0 3 5 0 9 25 18 25 1 � � � � � � ! " # " � � � �� / / / / 0 3 5 0 16 25 0 3 5 0 12 2 2 u w u u w � � � ! " # " � � � � ! " # " / / / � � . Èòàê, q �1 , p � 0 . Ìíîãî÷ëåí f x x x( ) /� �2 6 5 1 èìååò p q� �2 2 êîìïëåêñ- íûõ êîðíÿ ñ ìàêñèìàëüíûì ìîäóëåì, ðàâíûì åäèíèöå. — Ïðîâåðèòü ñîèçìåðèìîñòü óãëà � ñ �: ( ( ) )&( ( ) )&( )f x f w x uw� � �0 0 02 , x x w x uw x x w x u 2 2 26 5 1 0 1 0 0 6 5 1 0 1 0 0 � � � � ! " # " � � � � � / / ! " # " � � � � � ! " # " � u u w x u 2 6 5 1 0 1 0 0 / � � � �Gcd ( / , )u u u2 6 5 1 0 1 1, ò.å. � íåñîèçìåðèì ñ �. — Ïðîâåðèòü ñîèçìåðèìîñòü ðàçíîñòè óãëîâ � ��u ñ �: ( ( ) )&f u � 0 &( ( ) )&( )f w u� �� 0 0 , u u w u w w2 2 2 6 5 1 0 6 5 1 0 0 1 6 5 � � � � � ! " # " � � �/ / ( ) / ( / ) � � � � � � � � ! " # " 6 5 1 0 0 / � �w u � � � � � � � ! " # " � � � ( ) / ( / )w w w w w u 1 6 5 25 14 25 0 0 2 � � � �Gcd ( , )25 14 25 1 12 2w w w , ò.å. �u è �� íå ÿâëÿþòñÿ �-ýêâèâàëåíòíûìè. — Ïðåäñòàâèòü A â âåùåñòâåííîé æîðäàíîâîé ôîðìå. Ïîñêîëüêó A óæå ïðåäñòàâëåíà â òðåáóåìîé ôîðìå, òî S E� . Âûïîëíèì øàã 2. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 133 — Âû÷èñëèòü ïî ëåììå 4 ðàâåíñòâî Sup T ( , ) ( , ) ( , ( , ) ) x y Orbit A b a x y b b � � �2 1 2 2 2 . — Ïîñêîëüêó \| \|� � �w 1, èìååò ìåñòî ñëó÷àé 2 äîêàçàòåëüñòâà òåîðåìû 1. Âûïîëíèì øàã 3. — Ñîãëàñíî òåîðåìå 3 íåðàâåíñòâî (4) äîëæíî âûïîëíÿòüñÿ äëÿ âñåõ âåð- øèí ïðåäóñëîâèÿ S b( ), ò.å. ïî ëåììå 4 Sup ( , ) ( , ) ( ) x y O b b x y b b � � � 1 2 1 2 äëÿ ( , ) ( , )b b1 2 0 0� , ( , ) ( , )b b1 2 0 1� , ( , ) ( , )b b1 2 1 0� , ( , ) ( , )b b1 2 1 1� . Ïðîâåðêà: 2 0 0� , 2 2 21 2 2 2b b� � , 2 2 21 2 2 2b b� � , 2 1 2 2 2b b� � � 2 4. Òàêèì îáðàçîì, íåðàâåíñòâî ( , ) ( , )a X c b âûïîëíÿåòñÿ äëÿ âñåõ b S b� ( ). Ïîñêîëüêó âåùåñòâåííàÿ æîðäàíîâà ôîðìà ñîñòîèò èç îäíîé 2 2� êëåòêè, ïå- ðåõîäà ê ïðåäåëó â òåîðåìå 1 è âû÷èñëåíèÿ m� íå òðåáóåòñÿ. ÌÅÒÎÄ ÏÐÎÂÅÐÊÈ ÈÍÂÀÐÈÀÍÒÍÎÑÒÈ ÍÅÐÀÂÅÍÑÒÂÀ Â ÎÁÙÅÌ ÑËÓ×ÀÅ Òåîðåìà 2. Ïðîáëåìà äîêàçàòåëüñòâà èíâàðèàíòíîñòè íåðàâåíñòâà (4) äëÿ öèê- ëà (1) ñ äàííîé íà÷àëüíîé òî÷êîé b àëãîðèòìè÷åñêè ðàçðåøèìà. Äîêàçàòåëüñòâî çàêëþ÷àåòñÿ â ðàñøèðåíèè ðàññóæäåíèé òåîðåìû 1 íà ñëó÷àé ìàòðèöû A ñ íåòðèâèàëüíûìè æîðäàíîâûìè êëåòêàìè. Ïóñòü ìàòðèöà îïåðàòîðà A â æîðäàíîâîé ôîðìå èìååò íåòðèâèàëüíûå æîðäàíîâû êëåòêè. Ïîñêîëüêó äëÿ êàæäîãî êîìïëåêñíîãî ñîáñòâåííîãî çíà÷åíèÿ � ñóùåñòâóåò ñîïðÿæåííîå ñîá- ñòâåííîå çíà÷åíèå �, æîðäàíîâà ôîðìà A íàðÿäó ñ êëåòêîé Jk ( )� ñîäåðæèò êëåò- êó Jk ( )� . Ïîäìàòðèöà âåùåñòâåííîé æîðäàíîâîé ôîðìû îïåðàòîðà A, ñîîòâåò- ñòâóþùàÿ ïàðå ( , )� � , èìååò âèä J B E B B E B ( ) ( ) ( ) ... . . . . ... ( ) ... ( ) � � � � � � � � � � � � � 0 0 0 0 0 0� � � � � � � � � , B r( ) cos( ) sin( ) sin( ) cos( ) � � � � � � � � � � � , E � � � � � � 1 0 0 1 è ìàòðèöà îïåðàòîðà A èìååò âèä A J J Jl l l l� � � � �� 1 1 1 1( ) ( ) ( )� � �� ... ( )� � �J l k l k� , ãäå � � � �1 1, ,� l l ÿâëÿþòñÿ êîìïëåêñíûìè ñîáñòâåííûìè ÷èñ- ëàìè, à � �l l k� �1, ..., — âåùåñòâåííûå ñîáñòâåííûå ÷èñëà A: A J J J Jm m l m l l m l l k m l k� � � � � �� 1 1 1 1( ) ( ) ( ) ( )� � � �� . (14) Êàæäîé êëåòêå J j j( )� ñîîòâåòñòâóåò ñâîÿ ãðóïïà ïåðåìåííûõ. Ïîýòîìó ðàñ- ñìîòðèì æîðäàíîâó êëåòêó ðàçìåðà k, îáîçíà÷åííóþ â (14). Ýëåìåíòû ýòîé êëåòêè — 2 2� ìàòðèöû. Ïóñòü X X X X x xk j j j� � ( , ... , ), ( , )1 2 1 2 . Ïàðà ( , )x xj j2 1 2 ñîîòâåòñòâóåò ïàðå ñîïðÿæåííûõ ñîáñòâåííûõ ÷èñåë ( , )� �j j . Ïóñòü m — íàòóðàëüíîå ÷èñëî è b b bk� � �( )1 � , b b bj j j� ( , )2 1 2 — âåêòîð ïàð ïåðå- ìåííûõ — íà÷àëüíûõ çíà÷åíèé. Âû÷èñëèì m-þ èòåðàöèþ X b( ) ;0 � X AXm m( ) ( )� â ÿâíîì âèäå; X A Xm m( ) � : X J bm m( ) ( )� � . Ïîëó÷èì 134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 X r B m C m C m r B m C m r B m m k m k m ( ) ( ) ( ) ( ) ( ) ... ( ) ... � � � 1 1 20 0 � ( ) ( ) ... ( ) m C m r B m b b bm k � � 1 1 2 0 0 � � � � � � � � � � � � � � � � � � � � � � � � � , b b b j j j � � � � � � 2 1 2 , (15) ãäå C m C r B m j m m m j j r B mj m j m j m j( ) (( ) ) ( )... ( ) ! ((� � � � 1 1 j ) )� , j k� & 1 1, , . Ðàâåíñòâî, ñîîòâåòñòâóþùåå j-é ñòðîêå (15), èìååò âèä x r b B m C m r b C m r bj m m j j k j k j k ( ) ( ) ( ) ( ) � � � � � � � � � � � �� 1 1 � � df m jr g m r b( , , ) . (16) Ëèíåéíàÿ ôîðìà — àíàëîã (6) ïðåäñòàâëÿåò ñîáîé ñóììó, êàæäîå ñëàãàåìîå êîòîðîé îïðåäåëåíî ãðóïïîé ïåðåìåííûõ êëåòêè J j i( )� : r S r g m r b a g m r b a gj m j m j m j j j j j j k j ( ) ( ( , , ) ( , , )� � � �1 1 1 2 2 2 � ( , , ) )m r b aj jk jkj j . (17) Àíàëîã ëèíåéíîãî íåðàâåíñòâà (4) èìååò âèä r S r S r S cm m m m l m l m 1 1 2 2 ( ) ( ) ( )� � � � . (18) Îáîçíà÷èì r1 ìàêñèìàëüíîå çíà÷åíèå: r l1 1� max (\| \| , , \| \| )� �� . Òîãäà ïî- ñêîëüêó S j m( ) — ìíîãî÷ëåí îò m, à ( / )r rj m 1 — ïîêàçàòåëüíàÿ ôóíêöèÿ îò m è r rj / 1 1% , èìååì r S r j m j m m m ( ) 1 0� �� ïðè r rj � 1, r S r b B m m m m m 1 1 1 1 ( ) ( )� �� . Ïîýòîìó ìåòîä èç òåîðåìû 1 ìîæåò áûòü èñïîëüçîâàí è â äàííîé òåîðåìå, ò.å. â îáùåì ñëó÷àå. Òåîðåìà 3. Ïðîáëåìà äîêàçàòåëüñòâà èíâàðèàíòíîñòè íåðàâåíñòâà (4) äëÿ öèêëà (1) (ò.å. ñ äàííûì ïðåäóñëîâèåì S b( )) àëãîðèòìè÷åñêè ðàçðåøèìà. Äîêàçàòåëüñòâî. Ëèíåéíîå ïîëóàëãåáðàè÷åñêîå ìíîæåñòâî S b S b� { }\| ( ) ìîæíî ïðåäñòàâèòü â âèäå îáúåäèíåíèÿ âûïóêëûõ ìíîãîãðàííûõ ìíîæåñòâ, ïî- ñêîëüêó S b( ) ìîæíî ïðåäñòàâèòü â âèäå S b S bl1 ( ) ( )� �� — ñèñòåì ëèíåéíûõ íåðàâåíñòâ. Â [19, ëåììû 2, 3] äîêàçàíî, ÷òî âûïîëíåíèå ëèíåéíîãî íåðàâåíñòâà äëÿ ëþáîé òî÷êè âûïóêëîãî ìíîãîãðàííèêà ñëåäóåò èç åãî âûïîëíåíèÿ íà âñåõ âåðøèíàõ ýòîãî ìíîãîãðàííèêà. Ïîýòîìó äîêàçàòåëüñòâî èíâàðèàíòíîñòè L a c A X bm( , , , ) íà S b( ) çàêëþ÷àåòñÿ â åãî ïðîâåðêå äëÿ âñåõ S b S bl1 ( ), , ( )� . Òåîðåìà 4. Ïðîáëåìà çàâåðøàåìîñòè öèêëà (1) àëãîðèòìè÷åñêè ðàçðåøèìà. Äîêàçàòåëüñòâî. Öèêë (1) ðàñõîäèòñÿ òîãäà è òîëüêî òîãäà, êîãäà óñëîâèå U x b( , ) — èíâàðèàíò öèêëà (2). ÇÀÊËÞ×ÅÍÈÅ Íàñòîÿùàÿ ðàáîòà — ïðÿìîå ïðîäîëæåíèå [19]. Ðàññìîòðåíèå ëèíåéíîãî îïåðàòî- ðà ñ êîìïëåêñíûìè ñîáñòâåííûìè ÷èñëàìè ïðèâåäåíî â ëåììàõ 1–7 òåîðåìû 1. Â äàííîé ñòàòüå, êàê è â [19], èçëîæåíà òîëüêî îñíîâíàÿ èäåÿ ìåòîäà. Àëãîðèòìû êîìïüþòåðíîé ëèíåéíîé àëãåáðû, îöåíêè ÷èñëà m èòåðàöèé ìåòîäà, àëãîðèòìû îòäåëåíèÿ è óòî÷íåíèÿ êîðíåé ìíîãî÷ëåíîâ, ïðîâåðêè èíâàðèàíòíîñ- òè ïåðâûõ m ñîîòíîøåíèé â òî÷êàõ îðáèòû (3) çäåñü íå îáñóæäàþòñÿ. Èçëîæå- íèå ìåòîäîâ êîìïüþòåðíîé àëãåáðû ñîäåðæèòñÿ, íàïðèìåð, â [21–23]. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1 135 Ìîæíî ïðåäïîëîæèòü, ÷òî ìåòîä ìîæåò áûòü ïîëîæåí â îñíîâó îáùåãî àë- ãîðèòìà äîêàçàòåëüñòâà èíâàðèàíòíîñòè ñèñòåìû ëèíåéíûõ íåðàâåíñòâ äëÿ ëè- íåéíî îïðåäåëåííûõ ïðîãðàìì, àíàëîãè÷íîãî ìåòîäó äîêàçàòåëüñòâà èíâàðèàíò- íîñòè ïîëèíîìèàëüíûõ ðàâåíñòâ [5, 6]. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. F l o y d R . W . Assigning meanings to programs // Proc. of Symp. on Applied Mathematics / J.T. Schwartz (Ed.). — Providence, R.I.: American Mathematical Society, 1967. — 19. — P. 19–32. 2. H o a r e C . A . R . An axiomatic basis for computer programming // Communications of the ACM. — 1969. — 12, N 10. — P. 576–580. 3. 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 // Cybernetics. — 1989. — N 2. — P. 9–19. 4. Ë ü â î â Ì . Ñ . Èíâàðèàíòíûå ðàâåíñòâà ìàëûõ ñòåïåíåé â ïðîãðàììàõ, îïðåäåëåííûõ íàä ïî- ëåì // Êèáåðíåòèêà. — 1988. — ¹ 1. — C. 108–110. 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 // Applicable Algebra in Engineering, Communication and Computing. — 1993. — N 4. — P. 21–29. 6. L v o v M . About one algorithm of program polynomial invariants generation / M. Giese, T. Jebelean (Eds.) // Proc. Workshop on Invariant Generation, WING 2007. Technical Report N 07-07 in RISC Report Series, University of Linz, Austria. 06 2007. Workshop Proceedings. — P. 85–99. 7. M ��u l l e r - O l m M . , S e i d l H . Computing polynomial program invariants // Inf. Process. Lett. — 2004. — 91, N 5. — P. 233–244. 8. M ��u l l e r - O l m M . , S e i d l H . Precise interprocedural analisys through linear algebra // Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. SIGPLAN Notices. — POPL ‘04. — 2004. — 39, N 1. — P. 330–341. 9. S a n k a r a n a r a y a n a n S . , S i p m a H . , M a n n a Z . Non-linear loop invariant generation using Gr��obner bases // Proc. of Symposium on Principles of Programming Languages. — Venice, Italy, January 14–16, 2004. — New York: ACM, 2004. — P. 318–329. 10. R o d r � 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 International Symposium on Symbolic and Algebraic Computation. — Santander, Spain, July 4–7, 2004. — New York: ACM, 2004. — P. 266–273. 11. 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 Computing. — Timisoara, Romania, Sept. 25–29, 2005. IEEE Computer Society, 2005. — P. 245–249. 12. L v o v M . S . Polynomial invariants for linear loops // Ñybernetics and Systems Analysis. — 2010. — 46, N 4. — P. 660–668. 13. Ë ü â î â Ì . Ñ . , Ê ð å ê í è í Â . À . Íåëèíåéíûå èíâàðèàíòû ëèíåéíûõ öèêëîâ è ñîáñòâåííûå ïî- ëèíîìû ëèíåéíûõ îïåðàòîðîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — ¹ 2. — C. 126–139. 14. C o u s o t P . , H a l b w a c h s N . Automatic discovery of linear restraints among variables of a program // Conference Record of the Fifth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Tucson, Arizona. — New York: ACM Press, 1978. — P. 84–97. 15. Ê ð è â î é Ñ . Ë . , Ð à ê ø à Ñ . Ã . Ïîèñê èíâàðèàíòíûõ ëèíåéíûõ çàâèñèìîñòåé â ïðîãðàììàõ // Êèáåðíåòèêà. — 1984. — ¹ 6. — Ñ. 23–28. 16. Ã î ä ë å â ñ ê è é A . Á . , Ê à ï è ò î í î â à Þ . Â . , Ê ð è â î é Ñ . Ë . , Ë å ò è ÷ å â ñ ê è é A . A . Èòåðàòèâíûå ìåòîäû àíàëèçà ïðîãðàìì. Ðàâåíñòâà è íåðàâåíñòâà // Êèáåðíåòèêà. — 1990. — ¹ 3. — Ñ. 1–10. 17. Ë ü â î â Ì . Ñ . Èíâàðèàíòíûå íåðàâåíñòâà â ïðîãðàììàõ, èíòåðïðåòèðîâàííûõ íàä óïîðÿäî- ÷åííûìè ïîëÿìè // Êèáåðíåòèêà. — 1986. — ¹ 5. — Ñ. 22–27. 18. Ë ü â î â Ì . Ñ . Îá èíâàðèàíòíûõ íåðàâåíñòâàõ äëÿ ñîñòîÿíèé ñõåì ïðîãðàìì, èíòåðïðåòèðî- âàííûõ íàä âåêòîðíûì ïðîñòðàíñòâîì // Êèáåðíåòèêà. — 1985. — ¹ 2. — Ñ. 111–112. 19. Ë ü â î â M . C . Ìåòîä äîêàçàòåëüñòâà èíâàðèàíòíîñòè ëèíåéíûõ íåðàâåíñòâ äëÿ ëèíåéíûõ öèêëîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2014. — 50, ¹ 4. — C. 80–85 . 20. Ð î á è í ñ î í À . Ââåäåíèå â òåîðèþ ìîäåëåé è ìåòàìàòåìàòèêó àëãåáðû. — Ì.: Íàóêà, ÃÐÔÌË, 1967. — 376 ñ. 21. Â à í ä å ð Â à ð ä å í Á . Ë . Àëãåáðà. — 2-e èçä. — Ì.: Ìèð, 1976. — 648 ñ. 22. Õ î ä æ Â . , Ï è ä î Ä . Ìåòîäû àëãåáðàè÷åñêîé ãåîìåòðèè. Ò. 1. — Ì.: ÈË, 1954. — 462 ñ. 23. Ê î ì ï ü þ ò å ð í à ÿ àëãåáðà: cèìâîëüíûå è àëãåáðàè÷åñêèå âû÷èñëåíèÿ / Ïîä ðåä. Á. Áóõáåð- ãåðà, Äæ. Êîëëèíçà, Ð. Ëîîñà. — Ì.: Ìèð, 1986. — 392 c. Ïîñòóïèëà 29.12.2014 136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 1

Анализ линейно определенных итеративных циклов

Репозитарії

Схожі ресурси