Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика

Предложен метод вычисления всех корней системы нелинейных уравнений в многомерном интервале. Основная идея метода состоит в разбиении исходного интервала поиска корней на подынтервалы, в каждом из которых либо отсутствуют корни, либо выполняется критерий единственности корня, основанный на операторе...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Кибернетика и системный анализ
Datum:	2015
1. Verfasser:	Семенов, В.Ю.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schlagworte:	Новые средства кибернетики, информатики, вычислительной техники и системного анализа
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/124918
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика / В.Ю. Семенов // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 169-175. — Бібліогр.: 17 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-124918
record_format	dspace
spelling	Семенов, В.Ю. 2017-10-11T17:25:28Z 2017-10-11T17:25:28Z 2015 Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика / В.Ю. Семенов // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 169-175. — Бібліогр.: 17 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124918 519.615 Предложен метод вычисления всех корней системы нелинейных уравнений в многомерном интервале. Основная идея метода состоит в разбиении исходного интервала поиска корней на подынтервалы, в каждом из которых либо отсутствуют корни, либо выполняется критерий единственности корня, основанный на операторе Кравчика (Krawczyk). Приведен алгоритм, выполняющий такое разбиение. Работа алгоритма проиллюстрирована на примерах. Запропоновано метод обчислення усіх коренів системи нелінійних рівнянь у багатовимірному інтервалі. Головна ідея методу полягає у розбитті вихідного інтервалу пошуку коренів на підінтервали, у кожному з яких або відсутні корені, або виконується критерій єдиності кореня, що базується на операторі Кравчика (Krawczyk). Наведено алгоритм, який виконує таке розбиття. The author proposes a method to calculate all the roots of a system of nonlinear equations inside a multidimensional interval. The main idea of the method is to subdivide the original interval into subintervals, which either do not have roots or satisfy the root uniqueness criterion based on the Krawczyk operator. An algorithm performing such a subdivision is presented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика Метод знаходження усіх коренів системи нелінійних алгебраїчних рівнянь, оснований на операторі Кравчика A method to find all the roots of a system of nonlinear equations based on the Krawczyk operator Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика
spellingShingle	Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика Семенов, В.Ю. Новые средства кибернетики, информатики, вычислительной техники и системного анализа
title_short	Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика
title_full	Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика
title_fullStr	Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика
title_full_unstemmed	Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика
title_sort	метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе кравчика
author	Семенов, В.Ю.
author_facet	Семенов, В.Ю.
topic	Новые средства кибернетики, информатики, вычислительной техники и системного анализа
topic_facet	Новые средства кибернетики, информатики, вычислительной техники и системного анализа
publishDate	2015
language	Russian
container_title	Кибернетика и системный анализ
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Метод знаходження усіх коренів системи нелінійних алгебраїчних рівнянь, оснований на операторі Кравчика A method to find all the roots of a system of nonlinear equations based on the Krawczyk operator
description	Предложен метод вычисления всех корней системы нелинейных уравнений в многомерном интервале. Основная идея метода состоит в разбиении исходного интервала поиска корней на подынтервалы, в каждом из которых либо отсутствуют корни, либо выполняется критерий единственности корня, основанный на операторе Кравчика (Krawczyk). Приведен алгоритм, выполняющий такое разбиение. Работа алгоритма проиллюстрирована на примерах. Запропоновано метод обчислення усіх коренів системи нелінійних рівнянь у багатовимірному інтервалі. Головна ідея методу полягає у розбитті вихідного інтервалу пошуку коренів на підінтервали, у кожному з яких або відсутні корені, або виконується критерій єдиності кореня, що базується на операторі Кравчика (Krawczyk). Наведено алгоритм, який виконує таке розбиття. The author proposes a method to calculate all the roots of a system of nonlinear equations inside a multidimensional interval. The main idea of the method is to subdivide the original interval into subintervals, which either do not have roots or satisfy the root uniqueness criterion based on the Krawczyk operator. An algorithm performing such a subdivision is presented.
issn	0023-1274
url	https://nasplib.isofts.kiev.ua/handle/123456789/124918
citation_txt	Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика / В.Ю. Семенов // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 169-175. — Бібліогр.: 17 назв. — рос.
work_keys_str_mv	AT semenovvû metodnahoždeniâvsehkorneisistemynelineinyhalgebraičeskihuravneniiosnovannyinaoperatorekravčika AT semenovvû metodznahodžennâusíhkorenívsisteminelíníinihalgebraíčnihrívnânʹosnovaniinaoperatoríkravčika AT semenovvû amethodtofindalltherootsofasystemofnonlinearequationsbasedonthekrawczykoperator
first_indexed	2025-11-25T23:07:39Z
last_indexed	2025-11-25T23:07:39Z
_version_	1850575861777956864
fulltext	ÓÄÊ 519.615 Â.Þ. ÑÅÌÅÍÎÂ ÌÅÒÎÄ ÍÀÕÎÆÄÅÍÈß ÂÑÅÕ ÊÎÐÍÅÉ ÑÈÑÒÅÌÛ ÍÅËÈÍÅÉÍÛÕ ÀËÃÅÁÐÀÈ×ÅÑÊÈÕ ÓÐÀÂÍÅÍÈÉ, ÎÑÍÎÂÀÍÍÛÉ ÍÀ ÎÏÅÐÀÒÎÐÅ ÊÐÀÂ×ÈÊÀ Àííîòàöèÿ. Ïðåäëîæåí ìåòîä âû÷èñëåíèÿ âñåõ êîðíåé ñèñòåìû íåëèíåéíûõ óðàâíåíèé â ìíîãîìåðíîì èíòåðâàëå. Îñíîâíàÿ èäåÿ ìåòîäà ñîñòîèò â ðàçáèåíèè èñõîäíîãî èíòåð- âàëà ïîèñêà êîðíåé íà ïîäûíòåðâàëû, â êàæäîì èç êîòîðûõ ëèáî îòñóòñòâóþò êîðíè, ëèáî âûïîëíÿåòñÿ êðèòåðèé åäèíñòâåííîñòè êîðíÿ, îñíîâàííûé íà îïåðàòîðå Êðàâ÷èêà (Krawczyk). Ïðèâåäåí àëãîðèòì, âûïîëíÿþùèé òàêîå ðàçáèåíèå. Ðàáîòà àëãîðèòìà ïðîèë- ëþñòðèðîâàíà íà ïðèìåðàõ. Êëþ÷åâûå ñëîâà: ñèñòåìà íåëèíåéíûõ óðàâíåíèé, ëîêàëèçàöèÿ êîðíåé, îïåðàòîð Êðàâ÷èêà. ÂÂÅÄÅÍÈÅ Ìíîãèå ïðèêëàäíûå çàäà÷è ïðèâîäÿò ê ðåøåíèþ ñèñòåì íåëèíåéíûõ àëãåáðà- è÷åñêèõ óðàâíåíèé (ÑÍÀÓ) âèäà f x x f x x f x x n n n n 1 1 2 1 1 0 0 0 ( , , ) , ( , , ) , ( , , ) � � � � � � � � � �� (1) â íåêîòîðîì n-ìåðíîì èíòåðâàëå D a b a bn n� � �[ ; ] [ ; ]1 1 � . Ïîëàãàåì, ÷òî ôóíê- öèè f x x C Dk n( , , ) ( )( ) 1 2 � � , k n�1, ,� , ò.å. äâàæäû äèôôåðåíöèðóåìû íà èí- òåðâàëå D . Áóäåì òàêæå èñïîëüçîâàòü âåêòîðíîå ïðåäñòàâëåíèå ñèñòåìû (1) F x x x x xn( ) , ( , , , )� �0 1 2 � . Ê òàêèì çàäà÷àì îòíîñÿòñÿ, íàïðèìåð, ïîèñê òî÷åê ýêñòðåìóìîâ ôóíêöèè, ïðèáëèæåííîå ðåøåíèå íåëèíåéíûõ äèôôåðåíöèàëüíûõ è èíòåãðàëüíûõ óðàâíå- íèé, îïðåäåëåíèå ïàðàìåòðîâ àêóñòè÷åñêèõ ñèãíàëîâ, èññëåäîâàíèå óñòîé÷èâîñ- òè äèíàìè÷åñêèõ ñèñòåì è äð. Ñèñòåìà (1) ìîæåò èìåòü áîëåå îäíîãî êîðíÿ. Èçâåñòíû ðàçëè÷íûå ìåòîäû ïîèñêà îäíîãî êîðíÿ ñèñòåìû íåëèíåéíûõ óðàâ- íåíèé (1) [1, 2]. Áîëüøèíñòâî ýòèõ ìåòîäîâ — ìîäèôèêàöèè ìåòîäà Íüþòîíà (ñì., íàïðèìåð, èñòîðè÷åñêèé îáçîð â [1]). Îäíàêî áîëåå ñëîæíîé ïðîáëåìîé ÿâ- ëÿåòñÿ íàõîæäåíèå âñåõ êîðíåé ñèñòåìû (1), ò.å. çàäà÷à âûäåëåíèÿ ïîäìíîæåñòâ, ñîäåðæàùèõ îäèí êîðåíü ñèñòåìû. Ïåðâûå ðåçóëüòàòû â ýòîì íàïðàâëåíèè áûëè ïîëó÷åíû â 60-õ ãîäàõ âñëåäñòâèå ðàçâèòèÿ àïïàðàòíûõ è ïðîãðàììíûõ ñðåäñòâ âû÷èñëèòåëüíîé òåõíèêè. Ïîÿâèëèñü àëãîðèòìû è ïðîãðàììíûå ïàêåòû, ðàáîòà- þùèå ñ ñóùåñòâåííûìè íåëèíåéíîñòÿìè è áîëüøèì ÷èñëîì ïåðåìåííûõ. Íèæå ïðèâåäåíû íåêîòîðûå ñôîðìèðîâàâøèåñÿ ïîäõîäû ê ðåøåíèþ ÑÍÀÓ. Îñíîâíàÿ èäåÿ ìåòîäîâ branch-and-bound (âåòâåé è ãðàíèö) ñîñòîèò â ðå- êóðñèâíîì ðàçáèåíèè (ðàçâåòâëåíèè) èñõîäíîé îáëàñòè ïîèñêà êîðíåé íà ìåíü- øèå ïîäîáëàñòè, â êàæäîé èç êîòîðûõ ïðîâåðÿåòñÿ íàëè÷èå/îòñóòñòâèå êîðíåé (ïîäðîáíûå ñòðóêòóðû branch-and-bound àëãîðèòìîâ ïðèâåäåíû, íàïðèìåð, â [3]). Ðåçóëüòàòîì òàêîãî ðàçáèåíèÿ ÿâëÿåòñÿ ñïèñîê � ïîäîáëàñòåé, â êàæäîé èç êîòîðûõ åñòü òîëüêî îäèí êîðåíü, à òàêæå ñïèñîê � ïîäîáëàñòåé, â êîòîðûõ ñèòóàöèÿ íåîïðåäåëåííà. Î÷åâèäíî, ÷òî áîëåå «êà÷åñòâåííûì» áóäåò àëãîðèòì, èìåþùèé ìåíüøèé ðàçìåð ñïèñêà �. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51 ¹ 5 169 © Â.Þ. Ñåìåíîâ, 2015 ×àñòî ìåòîäû branch-and-bound ïðèìåíÿþò âìåñòå ñ ìåòîäàìè èíòåðâàëüíîé àðèôìåòèêè. Àïïàðàò èíòåðâàëüíîé àðèôìåòèêè âïåðâûå äåòàëüíî áûë ïðåä- ñòàâëåí â 1962 ã. â ðàáîòå Ìóðà [4]. Ïîçäíåå ïîÿâèëèñü ðàçëè÷íûå ìåòîäû ïîèñ- êà âñåõ êîðíåé ñèñòåìû íåëèíåéíûõ óðàâíåíèé, èñïîëüçóþøèå àïïàðàò èíòåð- âàëüíîé àðèôìåòèêè (ñì. îáçîð â [3]). Â ÷àñòíîñòè, ïîëó÷èë ðàñïðîñòðàíåíèå îïåðàòîð Êðàâ÷èêà, êîòîðûé ðàññìàòðèâàåòñÿ â äàííîé ñòàòüå. Îñíîâíîé îáëàñòüþ ïðèìåíåíèÿ ãîìîòîïíûõ ìåòîäîâ ÿâëÿþòñÿ ïîëèíîìè- àëüíûå ñèñòåìû. Áàçèñîì äëÿ äàííûõ ìåòîäîâ ñëóæèò òåîðåìà Áåðíøòåéíà, óñòà- íàâëèâàþùàÿ ñâÿçü ìåæäó ÷èñëîì êîìïëåêñíûõ íóëåé îòîáðàæåíèÿ F â îáëàñòè D è åãî òîïîëîãè÷åñêîé ñòåïåíüþ. Íà åå îñíîâå íàõîäÿòñÿ ðåøåíèÿ ïîëèíîìèàëüíûõ ñèñòåì ìåòîäàìè «ãîìîòîïíîãî ïðîäîëæåíèÿ» (homotopy continuation èëè path following). Íåäîñòàòêîì ýòèõ ìåòîäîâ ÿâëÿåòñÿ èõ ïðèìåíèìîñòü ê ïîèñêó òîëüêî êîìïëåêñíûõ êîðíåé, õîòÿ ÷àñòî íåîáõîäèìî îïðåäåëåíèå äåéñòâèòåëüíûõ êîð- íåé. Òàê, òîïîëîãè÷åñêàÿ ñòåïåíü îòîáðàæåíèÿ f z z( ) � �2 2010 îòíîñèòåëüíî òî÷êè z � 0 ðàâíà äâóì, íî äåéñòâèòåëüíûõ íóëåé äàííàÿ ôóíêöèÿ íå èìååò. Â òî æå âðåìÿ ýòè ìåòîäû äàþò âîçìîæíîñòü ïðîâåðêè íàëè÷èÿ âûðîæäåííûõ è ïëî- õî îáóñëîâëåííûõ êîðíåé. Îäíàêî âû÷èñëåíèå òîïîëîãè÷åñêîé ñòåïåíè îáû÷íî ñâÿçàíî ñ âû÷èñëåíèåì ïîâåðõíîñòíîãî èíòåãðàëà è ÿâëÿåòñÿ áîëåå ñëîæíûì ïîäõîäîì ïî ñðàâíåíèþ, íàïðèìåð, ñ ìåòîäàìè èíòåðâàëüíîé àðèôìåòèêè, ïðè- ìåíÿåìûìè â ìåòîäàõ branch-and-bound. Ìåòîä, ïðåäëîæåííûé Äåëëíèòöåì â ðàáîòå [5], îñíîâàí íà ðàññìîòðåíèè ìåòîäà Íüþòîíà êàê äèíàìè÷åñêîé ñèñòåìû. Ïðè ýòîì ëîêàëèçàöèÿ êîðíåé ñèñ- òåìû íåëèíåéíûõ óðàâíåíèé îñóùåñòâëÿëàñü ïóòåì ïîèñêà èíâàðèàíòîâ äàííûõ äèíàìè÷åñêèõ ñèñòåì. Ïîäõîä Êàëîâè÷à [6] çèæäåòñÿ íà èñïîëüçîâàíèè ðàçðàáîòàííîãî èì àïïà- ðàòà «èñêëþ÷àþùèõ» ôóíêöèé. ßìàìóðà [7] èñïîëüçîâàë ïðîâåðêó îòñóòñòâèÿ ðåøåíèÿ â íåêîòîðîé îá- ëàñòè, îñíîâàííóþ íà àíàëèçå çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ, äîïóñòèìîå ìíîæåñòâî êîòîðîé ñîäåðæèò âñå íóëè ðàññìàòðèâàåìîé ñèñòåìû óðàâíåíèé. Äàííàÿ ìåòîäîëîãèÿ ïî ñâîåé êîíñòðóêöèè ïðåäíàçíà÷åíà äëÿ ðåøåíèÿ ñèñòåì, â êîòîðûõ ÷èñëî íåëèíåéíûõ ñëàãàåìûõ âåñüìà ìàëî ïî ñðàâíåíèþ ñ ÷èñëîì ëè- íåéíûõ ñëàãàåìûõ. Ðîäñòâåííûé ïîäõîä ïðåäëîæåí â ðàáîòå Áóëàòîâà [8]. Çàäà÷à ïîèñêà âñåõ íóëåé ÑÍÀÓ çàìåíåíà âñïîìîãàòåëüíîé çàäà÷åé íåëèíåéíîãî ïðîãðàììèðîâà- íèÿ, äîïóñòèìîå ìíîæåñòâî êîòîðîé âêëþ÷àåò âñå èñêîìûå êîðíè. Ïðè ýòîì íå ïðèâîäèëèñü îöåíêè ñëîæíîñòè ìåòîäà è êîíêðåòíûå ÷èñëåííûå ïðèìåðû. Â ñòàòüå [9] äëÿ îòäåëåíèÿ êîðíåé ïðåäëîæåí òàê íàçûâàåìûé �s-àëãîðèòì, èñïîëüçóþùèé àïïàðàò �-ñåòåé. Â ðàáîòàõ [10–12] ïðèâåäåíû ìåòîäû, îñíîâàííûå íà ïðîâåðêå íåâûðîæ- äåííîñòè ÿêîáèàíà, à òàêæå òåîðåìå Êàíòîðîâè÷à. Ìíîãîîáðàçèå ìåòîäîâ îáúÿñíÿåòñÿ òåì, ÷òî ðåøàåìûå çàäà÷è îòëè÷àþòñÿ ÷èñëîì óðàâíåíèé, õàðàêòåðîì íåëèíåéíîñòè, ãëàäêîñòüþ ðàññìàòðèâàåìûõ ôóíê- öèé, èíôîðìàöèåé î ìåñòîïîëîæåíèè êîðíåé è ò.ä. Âñëåäñòâèå ýòîãî íå ñóùåñòâóåò óíèâåðñàëüíûõ ïîäõîäîâ ê ðåøåíèþ òàêèõ çàäà÷. Â äàííîé ñòàòüå ïðåäëîæåííûå â [10–12] ìåòîäû óñîâåðøåíñòâóþòñÿ çà ñ÷åò èñïîëüçîâàíèÿ îïåðàòîðà Êðàâ÷èêà â êà÷åñòâå êðèòåðèÿ íàëè÷èÿ/îòñóòñòâèÿ êîðíåé. ÊÐÈÒÅÐÈÉ ÅÄÈÍÑÒÂÅÍÍÎÑÒÈ ÊÎÐÍß Ãðóïïà êðèòåðèåâ åäèíñòâåííîñòè êîðíÿ â íåêîòîðîé îáëàñòè D ñôîðìèðîâà- ëàñü âñëåäñòâèå ïîïûòîê ïîêàçàòü ñõîäèìîñòü ìåòîäà Íüþòîíà áåç íà÷àëüíîé 170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 èíôîðìàöèè î íàëè÷èè êîðíÿ. Ïåðâûé ðåçóëüòàò â ýòîé îáëàñòè áûë ïîëó÷åí â 1829 ã. Êîøè [1], êîòîðûé ñôîðìóëèðîâàë äîñòàòî÷íûå óñëîâèÿ íàëè÷èÿ êîðíÿ ôóíêöèè f x x( ), �� , íà íåêîòîðîì îäíîìåðíîì îòðåçêå D a b� [ , ]. Ïåðâûé «ìíîãîìåðíûé» ðåçóëüòàò, êîãäà D n� � , ïîëó÷åí â 1916 ã. Ôàé- íîì [13]. Îäíàêî íàèáîëåå èçâåñòíûé è îáîáùàþùèé ðåçóëüòàò â ýòîì íàïðàâëå- íèè ñôîðìóëèðîâàí â 1948 ã. Êàíòîðîâè÷åì [14]. Òåîðåìà 1. Îáîçíà÷èì M 2 êîíñòàíòó Ëèïøèöà ìàòðèöû ßêîáè F x' ( ) îòî- áðàæåíèÿ F x( ) íà èíòåðâàëå D a b a bn n� � �[ ; ] [ ; ]1 1 � , ò.å. \| \| ( ) ( ) \| \| \| \| \| \| ,( ) ( ) ( ) ( ) ( ) ( )F x F x M x x x x D' '1 2 2 1 2 1 2� � � � . Ïóñòü äëÿ íåêîòîðîé òî÷êè x D( )0 � ñóùåñòâóþò êîíñòàíòû B è � òàêèå, ÷òî \| \| [ ( )] \| \| ; \| \| [ ( )] ( )\| \| ;( ) ( ) ( )F x B F x F x B M' 0 1 0 1 0 2 0� �� .5 . Ââåäåì îáîçíà÷åíèÿ r B M1 2 22 1 1 2, / ( )� � �� . Òîãäà îòîáðàæåíèå F èìååò êîðåíü â ïåðåñå÷åíèè D S x r� ( , )( )0 1 , ïðè÷åì â ïåðåñå÷åíèè D S x r� ( , )( )0 2 îí åäèíñòâåííûé. Êðèòåðèé Êðàâ÷èêà íàëè÷èÿ êîðíåé. Ïðèíöèïèàëüíî íîâûå âîçìîæíîñòè äëÿ ïðîâåðêè íàëè÷èÿ êîðíåé îòêðûëè òåîðåìû, îñíîâàííûå íà àïïàðàòå èíòåð- âàëüíîé àðèôìåòèêè, âïåðâûå äåòàëüíî ðàçðàáîòàííîì â 1962 ã. â ðàáîòå Ìóðà [4]. Îäíèì èç ôóíäàìåíòàëüíûõ ïîíÿòèé èíòåðâàëüíîé àðèôìåòèêè ÿâëÿåòñÿ îïåðà- òîð Êðàâ÷èêà, êîòîðûé äëÿ n-ìåðíîãî èíòåðâàëà D a b a bn n� � �[ ; ] [ ; ]1 1 � îïðåäå- ëÿåòñÿ êàê K F( ) ( ) ( ( , ))( )( ) ( ) ( ) ( )D x CF x I C x D D x� � � �0 0 0 0 , (2) ãäå x D( )0 � , F x( ) — âåêòîð-ôóíêöèÿ ëåâîé ÷àñòè ñèñòåìû (1), F( , )( )x D0 — èíòåðâàëüíîå ïðèðàùåíèå (slope) [15] îòîáðàæåíèÿ F íà n-ìåðíîì èíòåðâàëå D îòíîñèòåëüíî òî÷êè x ( )0 . Èíòåðâàëüíîå ïðèðàùåíèå îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì. Ñíà÷àëà çàäàäèì ôóíêöèþ ïðèðàùåíèÿ F x x( , )( )0 êàê F x F x F x x x x( ) ( ) ( , )( )( ) ( ) ( )� � �0 0 0 . (3) Ìàòðèöà F( , )( )x D0 ÿâëÿåòñÿ èíòåðâàëüíûì ðàñøèðåíèåì [15] ôóíêöèè F x x( , )( )0 íà èíòåðâàëå D . Ýòî îçíà÷àåò, ÷òî êàæäûé ýëåìåíò ìàòðèöû ïðåä- ñòàâëÿåò ñîáîé îäíîìåðíûé èíòåðâàë, ñîäåðæàùèé äèàïàçîí çíà÷åíèé ñîîò- âåòñòâóþùåãî ýëåìåíòà ìàòðèöû F x x( , )( )0 . Ìàòðèöà C âûáèðàåòñÿ êàê C F x� �[ ( )]( )' 0 1. Ïðè ýòîì âñå äåéñòâèÿ â ôîð- ìóëå (2) âûïîëíÿþòñÿ ïî ïðàâèëàì èíòåðâàëüíîé àðèôìåòèêè [15]. Êëþ÷åâûì ðåçóëüòàòîì çäåñü ÿâëÿåòñÿ òåîðåìà Ìóðà [16]. Òåîðåìà 2. Ïóñòü îáðàç îïåðàòîðà Êðàâ÷èêà âõîäèò â èíòåðâàë D, D � � � �[ ; ] [ ; ]a b a bn n1 1 � : K( )D D� . (4) Òîãäà ñèñòåìà (1) èìååò â D åäèíñòâåííûé êîðåíü. Î÷åâèäíîå ïðåèìóùåñòâî îïåðàòîðà Êðàâ÷èêà ïî ñðàâíåíèþ ñ òåîðåìîé Êàíòîðîâè÷à çàêëþ÷àåòñÿ â òîì, ÷òî íå âû÷èñëÿåòñÿ êîíñòàíòà Ëèïøèöà äëÿ ìàòðèöû ßêîáè. Â [17] ïîêàçàíî, ÷òî òåñò Êðàâ÷èêà (4) îïðåäåëÿåò íàëè÷èå êîð- íÿ â áîëåå øèðîêîì èíòåðâàëå D ïî ñðàâíåíèþ ñ òåîðåìîé Êàíòîðîâè÷à. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51 ¹ 5 171 ÊÐÈÒÅÐÈÉ ÎÒÑÓÒÑÒÂÈß ÊÎÐÍÅÉ Â äàííîé ðàáîòå èñïîëüçóåì êðèòåðèé îòñóòñòâèÿ êîðíåé íà èíòåðâàëå D a b a bn n� � �[ ; ] [ ; ]1 1 � , ïðåäëîæåííûé â [10]. Òåîðåìà 3. Ïóñòü f x x C D k nk n( , ..., ) ( ), , ,( ) 1 1 1� � � , è ñïðàâåäëèâû îãðàíè- ÷åíèÿ � � � � f x M i k nk i ki , , , ,1 � . (5) Òîãäà åñëè äëÿ íåêîòîðîãî m âûïîëíåíî óñëîâèå \| ( ) \| ( )( )f x M b am mi i n i i 0 1 1 2 � � � � , (6) ãäå x a b a b a bn n ( ) [ . ( ), . ( ), , . ( )]0 1 1 2 20 5 0 5 0 5� � , òî ñèñòåìà (1) íå èìååò êîðíåé â D . Äðóãîé ñïîñîá ïðîâåðêè îòñóòñòâèÿ êîðíåé îñíîâàí íà îïåðàòîðå Êðàâ÷è- êà (2). Êàê óòâåðæäàëîñü, íàïðèìåð, â [17], äîñòàòî÷íûì óñëîâèåì íàëè÷èÿ êîð- íÿ ÿâëÿåòñÿ âëîæåííîñòü îáðàçà îïåðàòîðà Êðàâ÷èêà â èñõîäíûé èíòåðâàë (ñîîò- íîøåíèå (4)). Îòñþäà ñëåäóåò òåîðåìà. Òåîðåìà 4. Ïóñòü îáðàç îïåðàòîðà Êðàâ÷èêà èìååò ïóñòîå ïåðåñå÷åíèå ñ èí- òåðâàëîì D : K( )D D� ��. (7) Òîãäà ñèñòåìà (1) íå èìååò êîðíåé â D. ÀËÃÎÐÈÒÌ ËÎÊÀËÈÇÀÖÈÈ ÊÎÐÍÅÉ Íàçíà÷åíèå àëãîðèòìà. Ëîêàëèçîâàòü è âû÷èñëèòü âñå êîðíè ñèñòåìû (1) â èí- òåðâàëå D a b a bn n� � �[ ; ] [ ; ]1 1 � . Âõîäíûå äàííûå. Ôîðìóëû âû÷èñëåíèÿ ôóíêöèé f x x k nk n( , , ), , ,1 1� �� , è îïåðàòîðà Êðàâ÷èêà (2); êîíñòàíòû M ki â îãðàíè÷åíèÿõ (5); � — ìèíèìàëüíûé ðàçìåð àíàëèçèðóåìîãî èíòåðâàëà. Âûõîäíûå äàííûå. Ñïèñîê � èíòåðâàëîâ, âêëþ÷àþùèõ èçîëèðîâàííûå êîðíè ñèñòåìû (1); ñïèñîê èíòåðâàëîâ � ðàçìåðîì ìåíåå �, ñîäåðæàùèõ âñå îñòàëüíûå êîðíè. Àëãîðèòì ëîêàëèçàöèè êîðíåé Â íà÷àëå ðàáîòû àëãîðèòìà âûïîëíÿåòñÿ ïðèñâîåíèå D D0 � . Øàã 1. Åñëè ðàçìåð D0 ìåíüøå �, èíòåðâàë D0 çàíîñèòñÿ â ñïèñîê � . Øàã 2. Ïðîâåðÿþòñÿ óñëîâèÿ (6) è (7). Åñëè õîòÿ áû îäíî èç íèõ âûïîëíåíî, èíòåðâàë D0 èñêëþ÷àåòñÿ èç ðàññìîòðåíèÿ. Øàã 3. Ïðîâåðÿåòñÿ óñëîâèå (4). Åñëè îíî âûïîëíåíî, èíòåðâàë D0 çàíîñèò- ñÿ â ñïèñîê � . Çíà÷åíèå êîðíÿ óòî÷íÿåòñÿ îäíèì èç èòåðàòèâíûõ ìåòîäîâ, íà- ïðèìåð ìåòîäîì Íüþòîíà. Íà÷àëüíûì çíà÷åíèåì äëÿ óòî÷íåíèÿ êîðíÿ ÿâëÿåòñÿ òî÷êà x ( )0 , èñïîëüçîâàâøàÿñÿ ïðè ïðîâåðêå (4). Øàã 4. Èíòåðâàë D0 çàìåíÿåòñÿ K( )D D0 0� . Øàã 5. Åñëè íè îäíî èç óïîìÿíóòûõ óñëîâèé íå âûïîëíåíî, D0 ðàçáèâàåòñÿ íà äâå ÷àñòè ( ,D0 1 è D0 2, ) ñëåäóþùèì îáðàçîì. Ïóñòü èíäåêñ k0 ñîîòâåòñòâóåò íàèáîëüøåé ñòîðîíå èíòåðâàëà D0 , ò.å. k b a k k k0 � �arg max { }. Òîãäà D a b a a b a bk k k n n0 1 1 1 0 0 0 0 5, [ ; ] [ ; . ( )] [ ; ]� � � � �� , D a b a b b a bk k k n n0 2 1 1 0 5 0 0 0, [ ; ] [ . ( ); ] [ ; ]� � � � �� . Äëÿ êàæäîé ÷àñòè âûïîëíÿþòñÿ øàãè 1–4. 172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 ÏÐÈÌÅÐÛ Ïðèìåð 1. Ðàññìîòðèì ïîèñê ïðèáëèæåííûõ ðåøåíèé íåëè- íåéíîãî èíòåãðàëüíîãî óðàâíå- íèÿ, îïèñàííîãî â [9]. Äàííàÿ çàäà÷à ñâîäèòñÿ ê ðåøåíèþ ñèñ- òåìû íåëèíåéíûõ óðàâíåíèé, êàæäîå èç êîòîðûõ ïðåäñòàâëÿåò ñîáîé êâàäðàòè÷íóþ ôîðìó îò- íîñèòåëüíî âåêòîðà íåèçâåñòíûõ êîýôôèöèåíòîâ x x xn� [ , , ]1 � : f x A x x b x c k nk k k k( ) ( , ) ( , ) , , ,� �1 � . (8) Çíà÷åíèÿ ìàòðèö Ai , âåêòîðîâ bi è ñâîáîäíûõ êîýôôèöèåíòîâ ci èçâåñòíû àïðèîðíî. Ïîèñê êîðíåé îñóùåñòâëÿëñÿ íà n-ìåðíîì èíòåðâàëå [ ; ]� �10 10 � � � � �[ ; ] [ ; ]10 10 10 10� . Ïîêàæåì, êàê âû÷èñëÿòü èíòåðâàëüíîå ïðèðàùåíèå (3) äëÿ ôóíêöèé (8). Èç òîæäåñòâà f x f x x x A x x b x xk k k k( ) ( ) ( ) ( ) ( , )( ) ( ) ( ) ( )� � � �0 0 0 0 ñëåäóåò âûðàæåíèå äëÿ k-é ñòðîêè èíòåðâàëüíîãî ïðèðàùåíèÿ { } TF( , ) min , max( ) ( )x D A x A x A x bk x D k x D k k k 0 0� � �� . Â òàáë. 1 îòðàæåíà çàâèñèìîñòü êîëè÷åñòâà ðàçáèåíèé ïðè ðåøåíèè ñèñòåìû (8) îò ðàçìåðíîñòè çàäà÷è n. Ïðèâîäèòñÿ òàêæå âðåìÿ ðàáîòû àëãîðèòìà â âû÷èñëèòåëü- íîé ñðåäå MATLAB®. Äëÿ êàæäîãî n áûëè íàéäåíû äâà êîðíÿ ñèñòåìû (8). Êàê âèäíî èç òàáëèöû, ÷èñëî ðàçáèåíèé ñëàáî ðàñòåò ïðè óâåëè÷åíèè ðàç- ìåðíîñòè çàäà÷è n. Çàìåòèì, ÷òî àëãîðèòì, ïðåäëîæåííûé â ðàáîòå [10], íå ïî- çâîëÿë îñóùåñòâëÿòü âû÷èñëåíèÿ çà ïðèåìëåìîå âðåìÿ (â ïðåäåëàõ 1 ÷) äëÿ ðàç- ìåðíîñòåé n � 8. Ïðèìåð 2. Ðàññìîòðèì ñèñòåìó óðàâíåíèé, îïèñûâàþùóþ íåëèíåéíóþ öåïü èç n òóííåëüíûõ äèîäîâ [7]: g x x x x i i ni n( ) , , , , � � �1 2 0 1 2� � , ãäå g x x x xi i i i( ) . . .� � 2 5 10 5 11 83 2 . (9) Ïîêàæåì, êàê âû÷èñëÿòü èíòåðâàëüíîå ïðèðàùåíèå (3) äëÿ ôóíêöèé (9). Çà- ïèøåì òîæäåñòâî f x f xk k( ) ( )( )� �0 � � ( . ( ( ) ) . ( ) . )(( ) ( ) ( )2 5 10 5 11 82 0 0 2 0x x x x x x x k k k k k k k k m m n mx x x� � � �( ) ( )) ( )0 1 0 . Îòñþäà âûòåêàåò, ÷òî ìàòðèöà èíòåðâàëüíîãî ïðèðàùåíèÿ (3) çàïîëíåíà èí- òåðâàëàìè [ , ]1 1 , çà èñêëþ÷åíèåì äèàãîíàëüíûõ ýëåìåíòîâ, êîòîðûìè ÿâëÿþòñÿ ñëåäóþùèå èíòåðâàëû: F( , ) [ min ( . ( . ) ), max( ) , ( )x D x x xk k x D k k k xk k 0 2 02 5 10 5� � � k kD k k kx x x � � ( . ( . ) )]( )2 5 10 52 0 � 2 5 10 5 12 80 2 0. ( ) . .( ) ( )x x . Â òàáë. 2 ïðåäñòàâëåíà çàâèñèìîñòü êîëè÷åñòâà ðàçáèåíèé ïðè ðåøåíèè çà- äà÷è (9) îò ðàçìåðíîñòè çàäà÷è n. Ïðèâîäèòñÿ òàêæå âðåìÿ âûïîëíåíèÿ àëãîðèò- ìà â âû÷èñëèòåëüíîé ñðåäå MATLAB®. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51 ¹ 5 173 Ò à á ë è ö à 1 Ðàçìåðíîñòü n çàäà÷è (8) ×èñëî êîðíåé ×èñëî ðàçáèåíèé Âðåìÿ, ñ 2 2 15 0.03 3 2 14 0.05 4 2 14 0.08 5 2 14 0.14 10 2 14 0.8 15 2 14 2.7 20 2 14 6 25 2 17 15 30 2 17 25 Ïðèìåð 3. Ðàññìîòðèì ïî- èñê íóëåé ïîëèíîìà ñ äåéñòâè- òåëüíûìè êîýôôèöèåíòàìè: f z a z a zp p( ) � � 1 2 1 � a z a z ap p p3 2 1� . Ïîäðàçóìåâàÿ z x ix� 1 2 , èùåì êîðíè ýêâèâàëåíòíîé ñèñòåìû 2 2� Re Im ( ( )) , ( ( )) f z f z � � � � � 0 0 íà íåêîòîðîì äâóõìåðíîì èíòåðâàëå [ , ] [ , ]a b a b1 1 2 2� . Ïîêàæåì, êàê âû÷èñëÿòü èíòåðâàëüíîå ïðèðàùåíèå äëÿ ïîëèíîìà. Çàïèøåì òîæäåñòâî f z f z G z z z z( ) ( ) ( , )( )� � �0 0 0 , ãäå êîýôôèöèåíòû ïîëèíîìà G z z( , )0 îòíîñèòåëüíî z ìîæíî íàéòè ïî ðåêóð- ðåíòíûì ôîðìóëàì g a g z g a k pk k k1 1 0 1 2� � ��; , , ,� . Äëÿ ïîäñ÷åòà ìàòðèöû èíòåðâàëüíîãî ðàñøèðåíèÿ íóæíî îöåíèòü äèàïàçîí çíà÷åíèé G z z( , )0 . Èñïîëüçóÿ ìåòîäèêó, ïðåäëîæåííóþ â [11, 12], ïîëó÷àåì \| ( , ) \| \| ( , ) \| \| ( , ) \| ! ( ) G z z G z z G z z l k z D k k k p 0 0 0 0 0 1 1 � � � � � . (10) Îáîçíà÷èì ïðàâóþ ÷àñòü (10) êàê M : M G z z G z z l k z D k k k p � � � � �\| ( , ) \| \| ( , ) \| ! ( ) 0 0 0 0 1 1 . (11) Çàìåòèì, ÷òî G z z k f z k k k( ) ( )( , ) ! ( ) ( )! 0 0 1 0 1 � . Ïîäñòàâëÿÿ ýòè ñîîòíîøåíèÿ â (11), ïîëó÷àåì âûðàæåíèå äëÿ M : M f z f z l k z D k k k p � � � � �\| ( ) \| \| ( ) \| ( )! ( ) ' 0 1 0 1 1 1 . Îòñþäà ñëåäóåò Re Re Re( ( , )) , [ ( ( )) , ( ( )) ]G z z f z M f z M0 1 1 0 0� � � I I ' ' , Im Im Im( ( , )) , [ ( ( )) , ( ( )) ]G z z f z M f z M0 2 2 0 0� � � I I ' ' . Òàêèì îáðàçîì, â êà÷åñòâå èíòåðâàëüíîãî ðàñøèðåíèÿ ìàòðèöû ïðèðàùåíèÿ ìîæíî èñïîëüçîâàòü èíòåðâàëüíóþ ìàòðèöó F I I I I ( , )( )x D0 1 2 2 1 � �� !! (îïåðàöèÿ èíâåðòèðîâàíèÿ èíòåðâàëà âûïîëíÿåòñÿ â ñîîòâåòñòâèè ñ ïðàâèëàìè èíòåðâàëüíîé àðèôìåòèêè). Ðàññìîòðèì ïðèìåð èç ðàáîòû [12]. Íåîáõîäèìî íàéòè íóëè ïîëèíîìà f z z z( ) � �50 12 1 (12) íà èíòåðâàëå [ , ] [ , ]� � �1 1 1 1 . 174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 Ò à á ë è ö à 2 Ðàçìåðíîñòü n çàäà÷è (9) ×èñëî êîðíåé ×èñëî ðàçáèåíèé Âðåìÿ, ñ 2 1 36 0.04 3 1 109 0.18 4 3 324 0.8 5 5 918 4 6 5 2747 17 7 7 7995 73 8 7 23537 308 Ïðèìåíåíèå ïðåäëîæåííîãî àëãî- ðèòìà äëÿ n � 50 ïîòðåáîâàëî 1589 ðàç- áèåíèé èñõîäíîãî èíòåðâàëà, ò.å. ìåíü- øå ïî ñðàâíåíèþ ñ ìåòîäîì ðàáî- òû [12], îñíîâàííûì íà òåîðåìå Êàíòîðîâè÷à (1665 ðàçáèåíèé). Â ðå- çóëüòàòå ëîêàëèçîâàíû âñå 50 êîðíåé óðàâíåíèÿ (12). Ðàçáèåíèå èñõîäíîãî ìíîæåñòâà ïîèñêà êîðíåé ïîêàçàíî íà ðèñ. 1. Ïóñòûå ïðÿìîóãîëüíèêè íå ñîäåðæàò êîðíåé, à íàéäåííûå êîðíè îòìå÷åíû æèðíûìè òî÷êàìè âíóòðè ñîîòâåòñòâóþùèõ ïðÿìîóãîëüíèêîâ. ÇÀÊËÞ×ÅÍÈÅ Ðàññìîòðåí ðÿä ñóùåñòâóþùèõ ìåòîäîâ ëîêàëèçàöèè âñåõ êîðíåé ÑÍÀÓ. Â ðàçâèòèå ðàíåå ïðåäëîæåííûõ ìåòîäîâ ïðåäñòàâëåí ìåòîä ëîêàëèçàöèè êîð- íåé, èñïîëüçóþùèé îïåðàòîð Êðàâ÷èêà. Íà ðàçëè÷íûõ ïðèìåðàõ ïîêàçàíî, ÷òî äàííûé ìåòîä èìååò ïðåèìóùåñòâî ïî ñðàâíåíèþ ñ ìåòîäàìè, îñíîâàííûìè íà àíàëèçå ÿêîáèàíà [10] è òåîðåìå Êàíòîðîâè÷à [12]. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Y a m a m o t o T . Historical developments in convergence analysis for Newton’s and Newton-like methods // J. Comput. Appl. Math. — 2000. — 124. — P. 1–23. 2. Ä å í í è ñ Ä æ . , Ø í à á å ë ü Ð . ×èñëåííûå ìåòîäû áåçóñëîâíîé îïòèìèçàöèè è ðåøåíèÿ íå- ëèíåéíûõ óðàâíåíèé. — Ì.: Ìèð, 1988. — 440 c. 3. K e a r f o t t R . B . Empirical evaluation of innovations in interval branch and bound algorithms for nonlinear algebraic systems // SIAM J. Sci. Comput. — 1997. — 18, N 2. — P. 574–594. 4. M o o r e R . E . Interval arithmetic and automatic error analysis in digital computing: Ph.D. Thesis. — Stanford Univ., 1962. 5. D e l l n i t z M . , S h u t z e O . , S e r t l S . Finding zeros by multilevel subdivision techniques // IMA J. Numer. Anal. — 2002. — 22, N 2. — P. 167–185. 6. K a l o v i c s F . Box valued functions in solving systems of equations and inequalities // Numerical Algorithms. — 2004. — 36. — P. 1–12. 7. Y a m a m u r a K . , F u j i o k a T . Finding all solutions of nonlinear equations using the dual simplex method // SIAM J. Numer. Anal. — 1977. — 14. — P. 611–615. 8. Á ó ë à ò î â Â . Ï . ×èñëåííûå ìåòîäû ïîèñêà âñåõ ðåøåíèé ñèñòåì íåëèíåéíûõ óðàâíåíèé // Æóðíàë âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 2000. — 40, ¹ 3. — Ñ. 348–355. 9. Á à á è ÷ Ì . Ä . , Ø å â ÷ ó ê Ë . Á . Îá îäíîì àëãîðèòìå ïðèáëèæåííîãî ðåøåíèÿ ñèñòåì íåëè- íåéíûõ óðàâíåíèé // Êèáåðíåòèêà. — 1982. — ¹ 2. — Ñ. 75–79. 10. Ñ å ì å í î â Â . Þ . Ìåòîä íàõîæäåíèÿ âñåõ äåéñòâèòåëüíûõ íåêðàòíûõ êîðíåé ñèñòåìû íåëè- íåéíûõ óðàâíåíèé // Æóðíàë âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 2007. — ¹ 9. — Ñ. 1486–1493. 11. S e m e n o v V . Method for the calculation of all non-multiple zeros of an analytic function // Comput. Methods Appl. Math. — 2011. — 11, N 1. — P. 67–74. 12. S e m e n o v V . Method for the calculation of all zeros of an analytic function based on the Kantorovich theorem // Comput. Methods Appl. Math. — 2014. — 14, N 3. — P. 385–392. 13. F i n e H . B . On Newton’s method of approximation // Proc. Nat. Acad. Sci. USA. — 1916. — 2. — P. 546–552. 14. Ê à í ò î ð î â è ÷ Ë . Â . Î ìåòîäå Íüþòîíà äëÿ ôóíêöèîíàëüíûõ óðàâíåíèé // Äîêë. ÀÍ ÑÑÑÐ. — 1948. — 59. — Ñ. 1237–1240. 15. K e a r f o t t R . B . Rigorous global search: continuous problems. — Dordrecht: Kluwer Acad. Publ., 1996. — 264 p. 16. M o o r e R . E . A test for existence of solutions to nonlinear systems // SIAM J. Numer. Anal. — 1977. — 14. — P. 611–615. 17. N e u m a i e r A . , Z u h e S . The Krawczyk operator and Kantorovich theorem // J. Math. Anal. Appl. — 1990. — 149, N 2. — P. 437–443. Ïîñòóïèëà 27.02.2015 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51 ¹ 5 175 Ðèñ. 1. Ãðàôè÷åñêîå èçîáðàæåíèå ïðèìåðà ðàáîòû àëãîðèòìà ïðè ëîêàëèçàöèè êîðíåé óðàâíåíèÿ (12) x2 x1

Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика

Institution

Ähnliche Einträge