Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида
Розглянуто розпаралелювальні алгоритми локалізації та обчислення екстремумів функцій для знаходження наближених розв’язків систем нелінійних рівнянь, а також алгоритми обчислювання екстремумів різницевих розв’язків систем звичайних диференціальних рівнянь і для аналізу стійкості за Ляпуновим. Алгори...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84194 |
| 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: | Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида / Я.Е. Ромм, И.В. Заика // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 165-180. — Бібліогр.: 25 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84194 |
|---|---|
| record_format |
dspace |
| spelling |
Ромм, Я.Е. Заика, И.В. 2015-07-03T15:51:24Z 2015-07-03T15:51:24Z 2011 Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида / Я.Е. Ромм, И.В. Заика // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 165-180. — Бібліогр.: 25 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84194 681.3.06:681.323(519.6) Розглянуто розпаралелювальні алгоритми локалізації та обчислення екстремумів функцій для знаходження наближених розв’язків систем нелінійних рівнянь, а також алгоритми обчислювання екстремумів різницевих розв’язків систем звичайних диференціальних рівнянь і для аналізу стійкості за Ляпуновим. Алгоритми побудовано на основі сортування послідовності зі взаємно однозначною відповідністю вхідних і вихідних індексів, екстремуми локалізуються шляхом порівняння індексів без нагромадження похибки. Parallelized algorithms for localization and computation of extrema of functions applied to find approximate solutions of systems of nonlinear equations are outlined. It is shown that they can be used to find the extrema of difference solutions of systems of ordinary differential equations and to perform an analysis for Lyapunov stability. The algorithms are based on sorting a sequence with biunique correspondence of input and target indices, extrema being localized by comparing of indices without error accumulation. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида Чисельна оптимізація на основі алгоритмів сортування для розв’язання диференційних і нелійних рівнянь загального виду Numerical sorting-based optimization as applied to general differential and nonlinear equations 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 |
2011 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Чисельна оптимізація на основі алгоритмів сортування для розв’язання диференційних і нелійних рівнянь загального виду Numerical sorting-based optimization as applied to general differential and nonlinear equations |
| description |
Розглянуто розпаралелювальні алгоритми локалізації та обчислення екстремумів функцій для знаходження наближених розв’язків систем нелінійних рівнянь, а також алгоритми обчислювання екстремумів різницевих розв’язків систем звичайних диференціальних рівнянь і для аналізу стійкості за Ляпуновим. Алгоритми побудовано на основі сортування послідовності зі взаємно однозначною відповідністю вхідних і вихідних індексів, екстремуми локалізуються шляхом порівняння індексів без нагромадження похибки.
Parallelized algorithms for localization and computation of extrema of functions applied to find approximate solutions of systems of nonlinear equations are outlined. It is shown that they can be used to find the extrema of difference solutions of systems of ordinary differential equations and to perform an analysis for Lyapunov stability. The algorithms are based on sorting a sequence with biunique correspondence of input and target indices, extrema being localized by comparing of indices without error accumulation.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84194 |
| citation_txt |
Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида / Я.Е. Ромм, И.В. Заика // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 165-180. — Бібліогр.: 25 назв. — рос. |
| work_keys_str_mv |
AT rommâe čislennaâoptimizaciânaosnovealgoritmovsortirovkispriloženiemkdifferencialʹnyminelineinymuravneniâmobŝegovida AT zaikaiv čislennaâoptimizaciânaosnovealgoritmovsortirovkispriloženiemkdifferencialʹnyminelineinymuravneniâmobŝegovida AT rommâe čiselʹnaoptimízacíânaosnovíalgoritmívsortuvannâdlârozvâzannâdiferencíinihínelíinihrívnânʹzagalʹnogovidu AT zaikaiv čiselʹnaoptimízacíânaosnovíalgoritmívsortuvannâdlârozvâzannâdiferencíinihínelíinihrívnânʹzagalʹnogovidu AT rommâe numericalsortingbasedoptimizationasappliedtogeneraldifferentialandnonlinearequations AT zaikaiv numericalsortingbasedoptimizationasappliedtogeneraldifferentialandnonlinearequations |
| first_indexed |
2025-11-25T23:52:36Z |
| last_indexed |
2025-11-25T23:52:36Z |
| _version_ |
1850587171957768192 |
| fulltext |
ÓÄÊ 681.3.06:681.323(519.6)
ß.Å. ÐÎÌÌ, È.Â. ÇÀÈÊÀ
×ÈÑËÅÍÍÀß ÎÏÒÈÌÈÇÀÖÈß ÍÀ ÎÑÍÎÂÅ ÀËÃÎÐÈÒÌÎÂ
ÑÎÐÒÈÐÎÂÊÈ Ñ ÏÐÈËÎÆÅÍÈÅÌ Ê ÄÈÔÔÅÐÅÍÖÈÀËÜÍÛÌ
È ÍÅËÈÍÅÉÍÛÌ ÓÐÀÂÍÅÍÈßÌ ÎÁÙÅÃÎ ÂÈÄÀ
Êëþ÷åâûå ñëîâà: ÷èñëåííàÿ îïòèìèçàöèÿ, ïàðàëëåëüíàÿ ëîêàëèçàöèÿ ýêñòðå-
ìóìîâ, ïðèáëèæåííîå ðåøåíèå ñèñòåì íåëèíåéíûõ óðàâíåíèé, ñîðòèðîâêà,
óñòîé÷èâîñòü ïðè âîçìóùåíèè ïàðàìåòðîâ.
Ââåäåíèå.  ñòàòüå ïðåäñòàâëåíû êîíñòðóêòèâíûå àëãîðèòìû âû÷èñëåíèÿ ýêñòðå-
ìóìîâ ôóíêöèé è ïðèáëèæåííûõ ðåøåíèé ñèñòåì íåëèíåéíûõ óðàâíåíèé, âêëþ-
÷àÿ ñèñòåìû àëãåáðàè÷åñêèõ è òðàíñöåíäåíòíûõ óðàâíåíèé. Òàêæå ðàññìîòðåíû
àëãîðèòìû âû÷èñëåíèÿ ýêñòðåìóìîâ ðàçíîñòíûõ ðåøåíèé ñèñòåì îáûêíîâåííûõ
äèôôåðåíöèàëüíûõ óðàâíåíèé (ÎÄÓ), àíàëîãè êîòîðûõ ïðèìåíèìû ê óðàâíåíèÿì
â ÷àñòíûõ ïðîèçâîäíûõ. Âû÷èñëåíèÿ ïîñòðîåíû ïî åäèíîé ñõåìå íà îñíîâå ñî-
ðòèðîâêè ïîñëåäîâàòåëüíîñòè ñ âçàèìíî îäíîçíà÷íûì ñîîòâåòñòâèåì âõîäíûõ è
âûõîäíûõ èíäåêñîâ. Ñõåìà èíâàðèàíòíà îòíîñèòåëüíî ðàçìåðíîñòè, âèäà çàäà÷è
è ñâîäèòñÿ ê äîïóñêàþùåìó ðàñïàðàëëåëèâàíèå öèêëè÷åñêîìó ïîèñêó ëîêàëüíî
ýêñòðåìàëüíûõ ýëåìåíòîâ ïîñëåäîâàòåëüíîñòè. Ïðè ýòîì âõîäíàÿ ïîñëåäîâàòåëü-
íîñòü çàâèñèò îò âèäà çàäà÷è. Äëÿ ïîèñêà ýêñòðåìóìîâ ôóíêöèè îäíîé äåéñòâè-
òåëüíîé ïåðåìåííîé ýòà ïîñëåäîâàòåëüíîñòü ñîñòàâëåíà èç çíà÷åíèé ôóíêöèè íà
ðàâíîìåðíîé ñåòêå. Ïðè ðåøåíèè ýòîé çàäà÷è äëÿ ñèñòåìû ÎÄÓ âõîäíûìè ÿâëÿ-
þòñÿ ïîñëåäîâàòåëüíîñòè ðàçíîñòíûõ çíà÷åíèé êàæäîé ïåðåìåííîé. Äëÿ îäíîðîä-
íîé ñèñòåìû òðàíñöåíäåíòíûõ óðàâíåíèé èñïîëüçóåòñÿ ïîñëåäîâàòåëüíîñòü çíà÷å-
íèé íîðì ëåâîé ÷àñòè íà ìíîãîìåðíîé ñåòêå. Íà îñíîâå ñõåìû ïðîãðàììèðóåòñÿ
ëîêàëèçàöèÿ îäíîâðåìåííî âñåõ ýêñòðåìóìîâ âõîäíîé ïîñëåäîâàòåëüíîñòè ïðè
ïðîèçâîëüíî çàäàííûõ ðàäèóñàõ îêðåñòíîñòè ëîêàëèçàöèè.  ñëó÷àå íåïðåðûâíî-
ãî ðåøåíèÿ çàäà÷è ê ëîêàëèçîâàííûì çíà÷åíèÿì âûïîëíÿåòñÿ ñïóñê ïîñðåäñòâîì
âûáîðà íàèìåíüøåãî çíà÷åíèÿ íà ðàâíîìåðíîé ñåòêå ñ èòåðàòèâíûì ñóæåíèåì
ëîêàëèçîâàííîé îáëàñòè. Íóëè ôóíêöèè èäåíòèôèöèðóþòñÿ êàê ìèíèìóìû ìîäó-
ëåé çíà÷åíèé ïðè óñëîâèè èõ äîñòàòî÷íîé ìàëîñòè.  îáùåì ñëó÷àå îáëàñòü ïî-
èñêà íóëåé è ýêñòðåìóìîâ ïîäðàçäåëÿåòñÿ íà ôðàãìåíòû, ãðàíèöû êîòîðûõ ïðî-
âåðÿþòñÿ íà íàëè÷èå ýêñòðåìóìà èëè íóëÿ ïî ñõåìå íà îñíîâå ñîðòèðîâêè â îò-
ëè÷èå îò ñïîñîáà, îïèñàííîãî äëÿ ÷àñòíîãî ñëó÷àÿ â [1].
Èäåíòèôèêàöèÿ ýêñòðåìàëüíûõ ýëåìåíòîâ ÷èñëîâîé ïîñëåäîâàòåëüíî-
ñòè íà îñíîâå ñîðòèðîâêè. Èñïîëüçóåì óñòîé÷èâóþ [2] âíóòðåííþþ ñîðòèðîâ-
êó îäíîìåðíîãî ìàññèâà ïî êëþ÷ó (íèæå — ñîðòèðîâêó) ñ âçàèìíî îäíîçíà÷íûì
ñîîòâåòñòâèåì âõîäíûõ è âûõîäíûõ èíäåêñîâ. Ñîðòèðîâêà ñòðîèòñÿ ñ ïîìîùüþ
ìàòðèö ñðàâíåíèé (ÌÑ) [3, 4], ðàçíîâèäíîñòü êîòîðûõ îïðåäåëÿåòñÿ íèæå. Ïóñòü
ïî îòíîøåíèþ � òðåáóåòñÿ óïîðÿäî÷èòü ýëåìåíòû ìàññèâà
{ }c nl l
n
� � �
1
, . (1)
Ìàññèâ (1) ðàñïîëàãàåòñÿ ãîðèçîíòàëüíî íàä òàáëèöåé è âåðòèêàëüíî ñëåâà îò
íåå. ÌÑ ïðèíèìàåò âèä
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 165
c c c
c
c
c
n
n
n
n n n nn
1 2
1 11 12 1
2 21 22 2
1 2
�
�
�
� � � � �
�
� � �
� � �
� � �
(2)
© ß.Å. Ðîìì, È.Â. Çàèêà, 2011
Çäåñü
� ij
i j
i j
j i
c c
c c
c c
�
�
�
� �
�
�
1
0
1
, ,
, ,
, ,
(3)
ãäå i n�1 2, , ,� , j n�1 2, , ,� . Çíà÷åíèÿ � ij
èç (3) öåëåñîîáðàçíî çàìåíèòü ñèìâî-
ëàìè �, 0, �. Íàïðèìåð, äëÿ ìàññèâà C � ( . , . , . , . , )7 3 2 1 8 1 2 1 8 ÌÑ (2) ïðèìåò âèä
×òîáû îïðåäåëèòü íîìåð â îòñîðòèðîâàííîì ìàññèâå j-ãî ýëåìåíòà âõîäíîãî
ìàññèâà, äîñòàòî÷íî ïîäñ÷èòàòü ÷èñëî íóëåé è ïëþñîâ â j-ì ñòîëáöå íàä äèàãî-
íàëüþ (âêëþ÷àÿ äèàãîíàëüíûé ýëåìåíò) è ñóììèðîâàòü ýòî ÷èñëî ñ ÷èñëîì ïëþ-
ñîâ j-é ñòðîêè íèæå äèàãîíàëè. Åñëè îáîçíà÷èòü îòñîðòèðîâàííûé ìàññèâ c1, òî
ïîëó÷èì
c c c c c c c c c1 3 1 1 1 2 1 5 3 12 4 1 4[ ] [ ], [ ] [ ], [ ] [ ], [ ] [ ], [ ]� � � � � c[ ]5 .
Ïðîöåäóðà sort00 (Delphi) äàííîé ñîðòèðîâêè:
const n=5; a: array [1..n] of real = (7.3,2.1,8.1,2.1,8);
type veñt=array [1..n] of real; veñt1=array [1..n] of integer;
var c, c1: veñt; e: veñt1;
procedure sort00(var c,c1: veñt; var e: veñt1);
var i,j,k: integer;
begin
for j:=1 to n do begin k:=0;
for i:=1 to j do if c[j]>=c[i] then k:=k+1;
for i:=j+1 to n do if c[j]>c[i] then k:=k+1;
c1[k]:=c[j]; e[k]:=j;
end; end;
Âñå îïåðàöèè ñðàâíåíèÿ â (2) âçàèìíî íåçàâèñèìû è èíâåðòèðóþò çíàê îò-
íîñèòåëüíî äèàãîíàëè — ñîðòèðîâêà ìàêñèìàëüíî ïàðàëëåëüíà ñ îöåíêîé âðå-
ìåííîé ñëîæíîñòè T N O( / ) ( )2 2 1� [4]. Äëÿ èäåíòèôèêàöèè ýêñòðåìàëüíûõ ýëå-
ìåíòîâ ñóùåñòâåííî, ÷òî ïðè êàæäîì èíäåêñå k ýëåìåíòà c k1[ ] îòñîðòèðîâàííîãî
ìàññèâà â ïðîöåäóðå sort00 âûïîëíÿåòñÿ ïðèñâàèâàíèå
c k c j1[ ]: [ ]� (4)
è çàïîìèíàåòñÿ èíäåêñ ýòîãî æå ýëåìåíòà âî âõîäíîì ìàññèâå
e k j[ ]: � , (5)
íà âûõîäå ñîðòèðîâêè ýëåìåíòû c k1[ ] è e k[ ] èìåþò îäèíàêîâûé èíäåêñ k.
Ëîêàëüíî ìèíèìàëüíûé â �-îêðåñòíîñòè ýëåìåíò c j ïîñëåäîâàòåëüíîñòè (1)
äàëåå îïðåäåëÿåòñÿ ñîãëàñíî íåðàâåíñòâàì
c c c cj j j j� � � �� �� � � �, , , ,1 2 �,
à ëîêàëüíî ìàêñèìàëüíûé ýëåìåíò — ñîãëàñíî íåðàâåíñòâàì
c c c cj j j j� �� � � �� � � �, , , ,1 2 �.
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
7.3 2.1 8.1 2.1 8
7.3 0 � � � �
2.1 � 0 � 0 �
8.1 � � 0 � �
2.1 � 0 � 0 �
8 � � � � 0
Îïðåäåëåíèÿ àäàïòèðîâàíû ïðèìåíèòåëüíî ê îòíîøåíèþ �, ïî êîòîðîìó ýëå-
ìåíòû óïîðÿäî÷åíû äàííîé ñîðòèðîâêîé. Ïðè ðàâåíñòâå îòñîðòèðîâàííûõ ýëå-
ìåíòîâ ïåðâûé èç íèõ ñ÷èòàåòñÿ íàèìåíüøèì, ïîñëåäíèé — íàèáîëüøèì.
Ïóñòü òðåáóåòñÿ èäåíòèôèöèðîâàòü âñå ëîêàëüíî ýêñòðåìàëüíûå ýëåìåíòû
ìàññèâà (1). Âûïîëíÿåòñÿ åãî ñîðòèðîâêà sort00, â ðåçóëüòàòå êîòîðîé ìàññèâ (1)
ïåðåâîäèòñÿ â ìàññèâ
C c c c n1 1 1 1 2 1� ( [ ], [ ], , [ ])� , (6)
äëÿ êîòîðîãî âûïîëíåíû ñîîòíîøåíèÿ (4), (5). Ïðè êàæäîì k óñëîâèå ëîêàëè-
çàöèè ìèíèìàëüíîãî ýëåìåíòà (çäåñü è íèæå îòíîñèòåëüíî òîëüêî äàííîãî
îïðåäåëåíèÿ) ïðîâåðÿåòñÿ ñèñòåìîé íåðàâåíñòâ
| [ ] [ ] |e k e k L� �
�, L k� �1 2 1, , ,� . (7)
Âûïîëíåíèå îäíîâðåìåííî âñåõ íåðàâåíñòâ (7) îçíà÷àåò, ÷òî âíóòðè �-îêðåñò-
íîñòè âõîäíîãî ýëåìåíòà ìàññèâà (1) ñ âõîäíûì èíäåêñîì e k[ ] íåò ýëåìåíòà
èç ìàññèâà (6), ìåíüøåãî ïî çíà÷åíèþ, ÷åì ýëåìåíò c k1[ ] . Ïðîâåðêó âûïîëíÿ-
åò îïåðàòîð ëîêàëèçàöèè ìèíèìóìà:
k:=1; while k<=n do begin for L:=1 to k-1 do if abs(e[k-L]-e[k])<=eps0 then goto 22; writeln(' ',c1[k],' ',e[k]);
22: k:=k+1 end;
 ýòîì ôðàãìåíòå n — ÷èñëî ýëåìåíòîâ èç (1), à eps0 � � . Ïðè óñëîâèè, ÷òî
eps0 ìåíüøå ïîëîâèíû ðàññòîÿíèÿ ìåæäó áëèæàéøèìè ëîêàëüíî ìèíèìàëü-
íûìè ýëåìåíòàìè, èäåíòèôèöèðóþòñÿ îäíîâðåìåííî âñå ëîêàëüíî ìèíèìàëü-
íûå ýëåìåíòû â îêðåñòíîñòÿõ ðàäèóñà eps0.
Ïðèìåð 1. Âñå ëîêàëüíî ìèíèìàëüíûå ýëåìåíòû ïîñëåäîâàòåëüíîñòè
C � ( . , . , . , . , )73 2 1 8 1 2 1 8 ñ ðàäèóñàìè îêðåñòíîñòåé ëîêàëèçàöèè eps0 1� è eps0 2�
èäåíòèôèöèðóåò ñëåäóþùàÿ ïðîãðàììà:
Program extrim;
{$APPTYPE CONSOLE}
uses SysUtils;
label 22, 24;
const n=5; eps0=1; {eps0=2;} a: array [1..n] of real = (7.3,2.1,8.1,2.1,8);
type veñt=array [1..n] of real; veñt1=array [1..n] of integer;
var i,k,l: integer; c, c1: veñt; e: veñt1;
procedure sort00 (var c,c1: veñt; var e: veñt1);
begin
for i:=1 to n do c[i]:=a[i];
sort00(c,c1,e); for i:=1 to n do write (' ',c[i]:2:4,' '); writeln;
k:=1; while k <= n do begin
for L:= 1 to k-1 do
if abs(e[k]- e[k-L])<= eps0 then goto 22;
writeln (' min=',c1[k]:2:4,' ',e[k],' ');writeln;
22: k:=k+1 end; readln;
end.
Ðåçóëüòàò ðàáîòû ïðîãðàììû ïðè eps0 1� :
Ïðè eps0 2� ïîëó÷èì
Èäåíòèôèêàöèþ âñåõ ëîêàëüíî ìàêñèìàëüíûõ ýëåìåíòîâ ïîñëåäîâàòåëüíî-
ñòè ìîæíî ïðîèçâåñòè ïî ýòîé æå ïðîãðàììå, äîáàâèâ îïåðàòîð ëîêàëèçàöèè
ìàêñèìóìà ñ îáðàòíûì íàïðàâëåíèåì ïðîñìîòðà ýëåìåíòîâ îòñîðòèðîâàííîãî
ìàññèâà
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 167
Oïèñàíèå ïðîöåäóðû sort 00
Ìèíèìóì Íîìåð ìèíèìóìà âî âõîäíîì ìàññèâå
Min=2.10000000000000E+0000 2
Min=2.10000000000000E+0000 4
Min=2.1000000000000E+0000 2
| [ ] [ ] |e k e k L� �
�, L n k� �1 2, , ,� , (8)
â ïðîãðàììíîé ôîðìå:
k:=1; while k <= n do begin for L:=1 to n-k do if abs(e[k+L]-e[k]) <= eps0 then goto 24; writeln (' ',c1[k],' ',e[k]);
24: k:=k+1 end;
Ðåçóëüòàò ðàáîòû ìîäèôèöèðîâàííîé ïðîãðàììû äëÿ eps0 1� :
Ïðè eps0 2� ïîëó÷èì
Îïåðàòîð ëîêàëèçàöèè èäåíòèôèöèðóåò âñå ýêñòðåìàëüíûå ýëåìåíòû ïîñëå-
äîâàòåëüíîñòè ïî ïîñòðîåíèþ ïîñëå îäíîêðàòíîé ñîðòèðîâêè ñî ñâîéñòâîì
óñòîé÷èâîñòè, îïèðàÿñü íà âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå âõîäíûõ è âûõîä-
íûõ èíäåêñîâ ñîðòèðóåìûõ ýëåìåíòîâ. Îïåðàòîð ìàêñèìàëüíî ðàñïàðàëëåëèâà-
åòñÿ ïî âñåì èíäåêñàì L è k ñ îöåíêîé T n O( ) ( )2 1� . Èäåíòèôèêàöèÿ ýêñòðåìóìîâ
âûïîëíÿåòñÿ ñ ïîìîùüþ îáðàáîòêè òîëüêî ýòèõ èíäåêñîâ, ïîýòîìó îïèñûâàåìûé
ñïîñîá íå çàâèñèò îò òèïà ïîñëåäîâàòåëüíîñòè è èñêëþ÷àåò íàêîïëåíèå ïîãðåø-
íîñòè.
Âû÷èñëåíèå ýêñòðåìóìîâ ôóíêöèé îäíîé ïåðåìåííîé. Ïóñòü ïîñëåäîâà-
òåëüíîñòü âèäà (1) îáðàçîâàíà äèñêðåòèçàöèåé ôóíêöèè îäíîé äåéñòâèòåëüíîé
ïåðåìåííîé. Òîãäà ëîêàëèçîâàííûå íà îñíîâå ñîðòèðîâêè çíà÷åíèÿ ÿâëÿþòñÿ
âçàèìíî îòäåëåííûìè ïðèáëèæåíèÿìè ýêñòðåìóìîâ. Ñ öåëüþ óòî÷íåíèÿ èõ çíà-
÷åíèé ê íèì ìîæíî âûïîëíèòü ñïóñê. Ïóñòü äëÿ ôóíêöèè
y f x� ( ) (9)
ðàññìàòðèâàåìîãî âèäà íà ïðîèçâîëüíîì îòðåçêå [ , ]( ) ( )x x N0 â îáëàñòè åå
îïðåäåëåíèÿ òðåáóåòñÿ íàéòè âñå ëîêàëüíûå ýêñòðåìóìû ïðè ïðîèçâîëüíî çà-
äàííîì, íî äîñòàòî÷íî ìàëîì ðàäèóñå îêðåñòíîñòè ëîêàëèçàöèè. Ñòðîèòñÿ
ðàâíîìåðíàÿ ñåòêà x x Lhl � �( )0 , L N� 0 1, , ,� , h
x x
N
N
�
�( ) ( )0
, â óçëàõ êîòî-
ðîé çíà÷åíèÿ ôóíêöèè èíòåðïðåòèðóþòñÿ êàê ýëåìåíòû ìàññèâà
c i f x i Ni[ ] ( ), , , ,� ��1 1 2 � . (10)
Ìàññèâ (10) ïîñòóïàåò íà âõîä ñîðòèðîâêè sort 00. Ê âûõîäó ïðîöåäóðû
sort00, êàê è â ïðîãðàììå extrim, ïîäñîåäèíÿåòñÿ öèêëè÷åñêèé îïåðàòîð ïðî-
âåðêè (7), â êîòîðîì ñ ó÷åòîì øàãà ñåòêè ìîäèôèöèðóåòñÿ ïðàâàÿ ÷àñòü:
| [ ] [ ]| /e k e k L h� �
� , L k� �1 2 1, , ,� . (11)
Èäåíòèôèêàöèÿ ëîêàëüíîãî ìèíèìóìà (â âèäå ïðèáëèæåíèÿ ê åãî ÷èñëîâî-
ìó çíà÷åíèþ) âûïîëíèòñÿ, ïîñêîëüêó íåðàâåíñòâà (11) ýêâèâàëåíòíû
íåðàâåíñòâàì
| [ ] [ ] |e k h e k L h� � � �
�, L k� �1 2 1, , ,� .
Ïîñëåäíåå îçíà÷àåò, ÷òî íà ðàâíîìåðíîé ñåòêå ðàññòîÿíèå ìåæäó òåêóùèì óçëîì
x e k h( ) [ ]0 � � è ëþáûì äðóãèì åå óçëîì x e k L h( ) [ ]0 � � � áîëüøå ðàäèóñà � äëÿ
òåõ çíà÷åíèé ôóíêöèè, êîòîðûå â îòñîðòèðîâàííîì ìàññèâå ïðåäøåñòâóþò
c k f xk[ ] ( )� �1 . Òàêèì îáðàçîì, ñèñòåìà íåðàâåíñòâ (11) ñîîòâåòñòâóåò íàèìåíüøå-
ìó â ñìûñëå îòíîøåíèÿ ïîðÿäêà � çíà÷åíèþ f x k( )�1 â îêðåñòíîñòè ðàäèóñà �.
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
Ìàêñèìóì Íîìåð ìàêñèìóìà âî âõîäíîì ìàññèâå
Max=7.300000000000E+0000 1
Max=8.100000000000E+0000 3
Max=8.000000000000E+0000 5
Max=8.100000000000E+0000 3
Ïîñëå ëîêàëèçàöèè âûïîëíÿåòñÿ ñïóñê ê ìèíèìàëüíîìó çíà÷åíèþ âíóòðè
îêðåñòíîñòè ëîêàëèçîâàííîé òî÷êè ïóòåì âûáîðà íàèìåíüøåãî çíà÷åíèÿ â ñóæà-
åìîé îêðåñòíîñòè c ôèêñèðîâàííûì ÷èñëîì ýëåìåíòîâ ðàâíîìåðíîé ñåòêè (íèæå
â ïðîãðàììå ýòî ÷èñëî ðàâíî mm). Ñóæåíèå ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íå áó-
äåò äîñòèãíóòà òðåáóåìàÿ òî÷íîñòü ïðèáëèæåíèÿ. Ñïóñê ïðåäñòàâëåí ïðîãðàì-
ìíûì ôðàãìåíòîì (ñóæåíèå ðàäèóñà îêðåñòíîñòè ñ êîýôôèöèåíòîì 1.2, íàèìåíü-
øåå çíà÷åíèå âûáèðàåòñÿ ïðîöåäóðîé min1ñ óêàçàíèåì èíäåêñà ìèíèìóìà ee):
xk:=x0+e[k]*h; eps1:=eps0; xk0:=xk-eps1; xk1:=xk+eps1; h0:=2*eps1/mm; while eps1 > eps do
begin x:=xk0; min1(x,ee); eps1:=eps1/1.2; xk0:=xk0+ee*h0-eps1; xk1:=xk0+ee*h0+eps1; h0:=2*eps1/mm end;
Íóëè ôóíêöèè ëîêàëèçóþòñÿ êàê ìèíèìóìû ìîäóëåé c i f x i[ ] | ( ) |� �1 ,
i N�1 2, , ,� , ñ ïðîâåðêîé ìàëîñòè (ïðè ïîèñêå íóëåé ìíîãî÷ëåíà â ñèëó ïðèíöè-
ïà ìàêñèìóìà ìîäóëÿ [5] ïðîâåðêà ìàëîñòè èçëèøíÿ).
Èäåíòèôèêàöèþ âñåõ ëîêàëüíûõ ìàêñèìóìîâ ìîæíî âûïîëíèòü íà îñíîâå
öèêëè÷åñêîé ïðîâåðêè íåðàâåíñòâ (8), ãäå ïî àíàëîãèè ñ (11) ïðàâóþ ÷àñòü ñëå-
äóåò çàìåíèòü âûðàæåíèåì � / h. Ïðîöåäóðà min1 çàìåíÿåòñÿ ïðîöåäóðîé max1,
àíàëîãè÷íî ñïóñêó îñóùåñòâëÿþùåé ïðèáëèæåíèå ê íàèáîëüøåìó çíà÷åíèþ
âíóòðè îêðåñòíîñòè ëîêàëèçîâàííîé òî÷êè.
Åñëè îòðåçîê [ , ]X X NN00 ïîèñêà ýêñòðåìóìîâ øèðå èñõîäíîãî (ñïðàâà), òî
â êîíöå áëîêà èíñòðóêöèé ïðîèñõîäèò âûïîëíåíèå öèêëè÷åñêîãî ñìåùåíèÿ îò-
ðåçêà [ , ]( ) ( )x x N0 íà åãî äëèíó äî òåõ ïîð, ïîêà íå áóäåò ïðîéäåí âåñü àïðèîðè
çàäàííûé îòðåçîê [ , ]X X NN00 . Ïðè ýòîì äîïîëíèòåëüíî ïðîâåðÿþòñÿ íà ýêñòðå-
ìóìû ãðàíèöû ñìåùàåìîãî îòðåçêà. Ñîðòèðîâêà sort 00 ñ íåêîòîðûì ôîðìàëü-
íûì âèäîèçìåíåíèåì è îïåðàòîð ëîêàëèçàöèè ýêñòðåìóìîâ íà êàæäîì øàãå ñìå-
ùåíèÿ ïðèìåíÿþòñÿ ê ïîñëåäîâàòåëüíîñòè çíà÷åíèé ôóíêöèè â çàêëþ÷èòåëüíûõ
óçëàõ ïðåäûäóùåãî îòðåçêà è íà÷àëüíûõ óçëàõ òåêóùåãî îòðåçêà. Ïðè íàëè÷èè
ýêñòðåìóìà íà ãðàíèöå ñìåùàåìîãî îòðåçêà ê íåìó âûïîëíÿåòñÿ ñïóñê ïóòåì âû-
áîðà íàèìåíüøåãî çíà÷åíèÿ â ñóæàåìîé âîêðóã åãî ëîêàëèçîâàííîãî çíà÷åíèÿ
îêðåñòíîñòè.  ðåçóëüòàòå âñå ýêñòðåìóìû è íóëè èäåíòèôèöèðóþòñÿ ïî çíà÷å-
íèþ è ïî èíäåêñó êàê âíóòðè, òàê è íà ãðàíèöàõ ñìåùàåìîãî îòðåçêà èíâàðèàí-
òíî îòíîñèòåëüíî ðàçìåðà àïðèîðè çàäàííîãî îòðåçêà [ , ]X X NN00 . Ýòî ïîçâîëÿåò
âûïîëíÿòü èäåíòèôèêàöèþ ýêñòðåìóìîâ ïàðàëëåëüíî ïî âñåì íåïåðåñåêàþùèìñÿ
îòðåçêàì, íà êîòîðûå ðàçáèâàåòñÿ ïîëíûé îòðåçîê ïîèñêà, çàòåì ïàðàëëåëüíî
«ñêëåèòü» ðåçóëüòàòû ïî âñåì ãðàíèöàì ñîñòàâëÿþùèõ îòðåçêîâ. Ñ òî÷íîñòüþ äî
ôîðìàëüíûõ îãîâîðîê èíâàðèàíòíîñòü ñõåìû ñîõðàíÿåòñÿ îòíîñèòåëüíî âèäà
ôóíêöèè, õàðàêòåðà ýêñòðåìóìîâ è àïðèîðè çàäàííîé ãðàíèöû ïîãðåøíîñòè âû-
÷èñëåíèÿ. Ýêñïåðèìåíò ïîêàçûâàåò óñòîé÷èâîñòü ëîêàëèçàöèè è âûñîêóþ òî÷-
íîñòü âû÷èñëåíèÿ îäíîâðåìåííî âñåõ ýêñòðåìóìîâ è íóëåé ôóíêöèè íà ïðîèç-
âîëüíîì îòðåçêå èç îáëàñòè åå îïðåäåëåíèÿ [6–9].
Íèæå äàíà ñõåìà èäåíòèôèêàöèè ýêñòðåìóìîâ ôóíêöèè äâóõ ïåðåìåííûõ.
Îíà ñòðîèòñÿ àíàëîãè÷íî ñõåìå äëÿ îäíîé ïåðåìåííîé, íî èìååò ïðèíöèïèàëü-
íûå èçìåíåíèÿ.
Ëîêàëèçàöèÿ è âû÷èñëåíèå ýêñòðåìóìîâ ôóíêöèè äâóõ äåéñòâèòåëü-
íûõ ïåðåìåííûõ. Äëÿ ïðèáëèæåííîãî âû÷èñëåíèÿ âñåõ ýêñòðåìóìîâ äåéñòâè-
òåëüíîé ôóíêöèè
z f x y� ( , ) (12)
îò äâóõ äåéñòâèòåëüíûõ ïåðåìåííûõ âíà÷àëå çàäàþòñÿ òåêóùèå îòðåçêè
[ , ]( ) ( )x x N0 è [ , ]( ) ( )y y M0 , îáðàçóþùèå ïðÿìîóãîëüíèêè âíóòðè îáëàñòè åå îïðåäå-
ëåíèÿ. Âíóòðè ïðÿìîóãîëüíèêîâ ñòðîèòñÿ ðàâíîìåðíàÿ ñåòêà
h x x NN� �| | /( ) ( )0 , x x h� �� �( )0 , � �� � �0 1, N , y y h� �� �( )0 , � �� � �0 1, M.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 169
Äëÿ êàæäîãî çíà÷åíèÿ j N� 0 1, , ,� âûïîëíÿåòñÿ ïðîõîä â íàïðàâëåíèè îñè OY
âäîëü j-ãî ñòîëáöà ïðÿìîóãîëüíîé ñåòêè, âî âðåìÿ êîòîðîãî îïðåäåëÿåòñÿ ìè-
íèìàëüíîå ïî ýëåìåíòàì ñòðîê çíà÷åíèå ôóíêöèè (12) â ñòîëáöå
c j f x y
j
i M
j i[ ] min ( , )�
�
� �
const
1
.
Ýòîò ìèíèìóì çàíîñèòñÿ íà âõîä ñîðòèðîâêè êàê j-é ýëåìåíò îäíîìåðíîãî
ìàññèâà. Ââèäó êâàäðàòè÷íîãî ðîñòà îáðàáàòûâàåìîé èíôîðìàöèè äëÿ óñêîðå-
íèÿ ïîñëåäîâàòåëüíîé ðåàëèçàöèè ìåòîäà èñïîëüçóåòñÿ óñòîé÷èâàÿ ñîðòèðîâêà
ñëèÿíèåì ïî ÌÑ [1, 3] ñ âçàèìíî îäíîçíà÷íûì ñîîòâåòñòâèåì âõîäíûõ è âû-
õîäíûõ èíäåêñîâ, êîòîðàÿ â ïîñëåäîâàòåëüíîì âàðèàíòå èìååò âðåìåííóþ
ñëîæíîñòü T O N N( ) ( log )1 2� è âìåñòå ñ òåì ýôôåêòèâíî ðàñïàðàëëåëèâàåòñÿ:
T N O N( / ) ( )2
24 � log . Íèæå ïðîöåäóðà sort ýòîé ñîðòèðîâêè áåç èçìåíåíèé çà-
èìñòâóåòñÿ èç [1].
Ê âûõîäó ïðîöåäóðû sort ïîäñîåäèíÿåòñÿ îïåðàòîð ëîêàëèçàöèè ìèíèìóìà.
Äëÿ òåêóùåãî óçëà, îïðåäåëÿåìîãî èíäåêñîì, çàïèñàííûì â ýëåìåíò ìàññèâà e k[ ] ,
îïåðàòîð èäåíòèôèöèðóåò êàæäûé óçåë äâóìåðíîé ñåòêè, â ïðîåêöèè eps0-îêðå-
ñòíîñòè êîòîðîãî íà îñü OX îòñóòñòâóþò óçëû, äîñòàâëÿþùèå çíà÷åíèÿ ýëåìåí-
òîâ âõîäíîé ïîñëåäîâàòåëüíîñòè, êîòîðûå ïðåäøåñòâóþò c e k[ [ ]] â îòñîðòèðîâàí-
íîì ìàññèâå. Çíà÷åíèå ëîêàëèçîâàííîé àáñöèññû ìèíèìóìà xk x e k h: [ ]� � �0
ðàññìàòðèâàåòñÿ êàê ïðèâÿçêà ê êîîðäèíàòàì äâóìåðíîãî ìèíèìóìà. Àáñöèññà
xk ôèêñèðóåòñÿ, è â íåé ïî àíàëîãè÷íîé îäíîìåðíîé ñõåìå ëîêàëèçóåòñÿ îðäèíà-
òà yk äâóìåðíîãî ìèíèìóìà. Òî÷êà ( , )xk yk ðàññìàòðèâàåòñÿ êàê ïðèáëèæåíèå ê
èñêîìûì êîîðäèíàòàì ìèíèìóìà ôóíêöèè (12). Âûïîëíÿåòñÿ ñïóñê ê íàèìåíü-
øåìó çíà÷åíèþ â îêðåñòíîñòè ëîêàëèçîâàííîé òî÷êè. Îí îñóùåñòâëÿåòñÿ âûáî-
ðîì íàèìåíüøåãî çíà÷åíèÿ â ñóæàåìîé îêðåñòíîñòè ïðèáëèæåíèÿ c ôèêñèðîâàí-
íûì ÷èñëîì ýëåìåíòîâ â ñåòêå (ïðè÷åì, ïî îáåèì ïåðåìåííûì) ïîêà íå äîñòèãà-
åòñÿ òðåáóåìàÿ òî÷íîñòü. Ñ öåëüþ ïîâûøåíèÿ òî÷íîñòè ñïóñê ïîâòîðÿåòñÿ
äâàæäû [1, 6].
Àíàëîãè÷íîå ïðèìåíåíèå îïåðàòîðà ëîêàëèçàöèè ìàêñèìóìà îáåñïå÷èâàåò
ëîêàëèçàöèþ òî÷êè ìàêñèìóìà. Ïðèáëèæåíèå ê íàèáîëüøåìó çíà÷åíèþ â îêðå-
ñòíîñòè ëîêàëèçîâàííîé òî÷êè îñóùåñòâëÿåòñÿ âûáîðîì íàèáîëüøåãî çíà÷åíèÿ
â èòåðàòèâíî ñóæàåìîé îêðåñòíîñòè.
Äëÿ èññëåäîâàíèÿ âñåé îáëàñòè ïîèñêà ýêñòðåìóìîâ ôóíêöèè (12) âûïîëíÿåòñÿ
öèêëè÷åñêîå ñìåùåíèå îòðåçêîâ [ , ]( ) ( )x x N0 è [ , ]( ) ( )y y M0 íà èõ äëèíó âäîëü ñòðîê
è ñòîëáöîâ ñåòêè äî òåõ ïîð, ïîêà íå áóäåò ïðîéäåíà âñÿ àïðèîðè çàäàííàÿ îáëàñòü.
Äîïîëíèòåëüíàÿ ïðîâåðêà íàëè÷èÿ ýêñòðåìóìîâ â îêðåñòíîñòÿõ ãðàíèö ñìåùàåìûõ
ïðîìåæóòêîâ âûïîëíÿåòñÿ ïî ñõåìå, àíàëîãè÷íîé ñõåìå äëÿ îäíîìåðíîãî ñëó÷àÿ, —
èñïîëüçóþòñÿ ýëåìåíòû ìàññèâà, îáðàçóåìîãî çíà÷åíèÿìè ôóíêöèè ñëåâà è ñïðàâà
îò ëåâîé ãðàíèöû êàæäîãî ñìåùàåìîãî îòðåçêà [ , ]( ) ( )x x N0 è [ , ]( ) ( )y y M0 . Êàê è
äëÿ îäíîìåðíîãî ñëó÷àÿ, ýòî ïîçâîëÿåò âûïîëíÿòü èäåíòèôèêàöèþ ýêñòðåìóìîâ
ïàðàëëåëüíî ïî âñåì ïðÿìîóãîëüíèêàì ðàññìàòðèâàåìîãî âèäà, êîòîðûå ïðè
îáúåäèíåíèè ïîêðûâàþò îáëàñòü ïîèñêà, çàòåì ïàðàëëåëüíî «ñêëåèòü» ðåçóëüòà-
òû ïî âñåì ãðàíèöàì ñîñòàâëÿþùèõ ïðÿìîóãîëüíèêîâ.
Äëÿ âû÷èñëåíèÿ íóëåé èäåíòèôèöèðóþòñÿ ìèíèìóìû ìîäóëÿ ôóíêöèè ñ îöåí-
êîé ìàëîñòè íàéäåííûõ çíà÷åíèé [1, 6].
Òàêèì îáðàçîì, íà÷àëüíàÿ ñõåìà ïðèìåíèìà äëÿ ôóíêöèè äâóõ äåéñòâèòåëü-
íûõ ïåðåìåííûõ. Ñ åå ïîìîùüþ ëîêàëèçóþòñÿ è âû÷èñëÿþòñÿ âñå ýêñòðåìóìû
ïðîèçâîëüíîé ôóíêöèè äàííîãî âèäà â ïðîèçâîëüíî ôèêñèðîâàííîé îáëàñòè íà
ïëîñêîñòè, âõîäÿùåé â îáëàñòü îïðåäåëåíèÿ ôóíêöèè. Ðàäèóñ îêðåñòíîñòè ëîêàëè-
çàöèè çàäàåòñÿ òàêæå ïðîèçâîëüíî, íî ôèêñèðóåòñÿ ñ ó÷åòîì îãðàíè÷åíèÿ, ñîãëàñíî
êîòîðîìó îí äîëæåí áûòü ìåíüøå ïîëîâèíû ðàññòîÿíèÿ ìåæäó áëèæàéøèìè ñîñåä-
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
íèìè ýêñòðåìóìàìè èñêîìîãî âèäà (ìàêñèìóìàìè ëèáî ìèíèìóìàìè). Êàê è â îä-
íîìåðíîì ñëó÷àå, îãðàíè÷åíèå âûòåêàåò èç ïîñòðîåíèÿ ñõåìû. Ýêñïåðèìåíòàëüíîå
ñîîòíîøåíèå ìåæäó ðàäèóñîì eps0 îêðåñòíîñòè ëîêàëèçàöèè è øàãîì ñåòêè h ìî-
æåò çàèìñòâîâàòüñÿ èç [1], ãäå îíî èñïîëüçóåòñÿ äëÿ âû÷èñëåíèÿ êîìïëåêñíûõ íó-
ëåé ìíîãî÷ëåíà.
Ïðèìåð 2. Âñå ëîêàëüíûå ìèíèìóìû ôóíêöèè z e
x y� � �� � �( )2 2 22
� �� � �
e xy
x y( )
. sin( )
2 2 23
0 1 â êâàäðàòå x � �[ , ]5 5 , y � �[ , ]5 5 ñ ðàäèóñîì îêðåñò-
íîñòè ëîêàëèçàöèè eps0 �1 èäåíòèôèöèðóåò ñëåäóþùàÿ ïðîãðàììà:
Program funcXYmin;
{$APPTYPE CONSOLE}
uses SysUtils;
label 22, 23;
const eps=1.1e-444; eps0=1; h=eps0/67; n00=400; x00=-5; x11=5; y00=-5; y11=5;
nn=n00+round(n00/2)+1; mm=64;
type vect1=array [1..2*nn+nn] of extended;
vect2=array [1..2*nn+nn] of longint;
var i,ii,j,k,k1,r,ee,ee1,tty,nn0,k0k,k0k0x,k0k0y,L : longint; c,a1: vect1; e,e3, e33: vect2;
x,x0,x1,xk,xk0,xk1,hx,hy,min,eps1,eps11,eps12,eps13: extended;
y,y0,y1,yk,yk0,yk1, ykk0,aak,bbk,hh,p: extended;
n00n: longint; a01x,a01y,c01x,c01y: vect1; e01x,e01y: vect2;
{çàäàíèå ôóíêöèè}
function func (x,y:extended):extended;
begin func:= -exp(-sqr((sqrt(x*x+y*y)-2)))-exp(-sqr(sqrt(x*x+y*y)-3))+0.1*sin(x*y); end;
procedure minx (var x,y, min:extended; var ee:integer);
begin min:=func(x,y); ee:=0; for i:=1 to mm do begin x:=xk0+i*hx;
IF min > func(x,y) then begin min:=func(x,y);ee:=i end; end; end;
procedure miny (var x,y, min:extended; var ee1:integer);
begin min:=func(x,y); ee1:=0; for i:=1 to tty do begin y:=ykk0+i*hy;
IF min > func(x,y) then begin min:=func(x,y); ee1:=I; end; end; end;
{ïðîöåäóðà ñîðòèðîâêè ñëèÿíèåì}
procedure sort(var nn0:longint; var c: vect1; var e: vect2);
{ïðîöåäóðà ñîðòèðîâêè ïîäñ÷åòîì}
procedure sort00 (var n00n: longint; var a01,c01: vect1; var e01: vect2);
begin
x0:=x00; x1:=x11; y0:=y00; y1:=y11; nn0:=n00; hh:=nn0*h; n00n:=4;
while x0 <= x11 do begin while y0 <= y11 do begin
k0k0x:=1; for r:=1 to nn0 do begin
x:=x0+r*h; ykk0:=y0; y:=y0; tty:=n00;hy:=h;
miny (x,y, min,ee1); a1[r]:= min; if (r > nn0-n00n div 2) and (k0k0x <= n00n div 2) then
begin a01x[k0k0x]:= min; k0k0x:=k0k0x+1; end; end;
sort(nn0, a1, e3); k:=1; while k <= nn0 do
begin for r := 1 to k-1 do IF abs(e3[k]-e3[k-r]) <= eps0/h then goto 23;
if (e3[k] <= 1) or( e3[k] >= nn0-1) then begin
sort00(n00n,a01x,c01x,e01x); k0k := 1; while k0k<= n00n do begin
for L := 1 to k0k-1 do IF abs(e01x[k0k - L] - e01x[k0k]) <= eps0/h then goto 23;
k0k:=k0k+1; end; end;
xk:= x0+e3[K]*h;
k0k0y:=1; for r:=1 to nn0 do begin y:=y0+r*h; a1[r]:=func(xk,y);
if (r > nn0-n00n div 2) and (k0k0y <= n00n div 2) then begin a01y[k0k0y]:=func(xk,y);
k0k0y:=k0k0y+1; end; end;
sort( nn0, a1, e33); k1:=1; while k1 <= nn0 do begin for r := 1 to k1-1 do
IF abs(e33[k1]-e33[k1-r]) <= eps0/h then goto 22;
if (e33[k1] <= 1) or ( e33[k1] >= nn0-1) then begin
sort00(n00n,a01y,c01y,e01y); k0k := 1; while k0k <= n00n do begin
for L := 1 to k0k-1 do IF abs(e01y[k0k - L] - e01y[k0k]) <= eps0/h then goto 22;
k0k:=k0k+1; end; end;
yk:= y0+e33[K1]*h;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 171
Oïèñàíèå ïðîöåäóðû sort 00; n00n — ÷èñëî ñîðòèðóåìûõ ýëåìåíòîâ,
a01 — âõîäíîé, c01 — âûõîäíîé ìàññèâû; e01 — ìàññèâ âûõîäíûõ èíäåêñîâ
Oïèñàíèå ïðîöåäóðû sort
{ñïóñê ê íàèìåíüøåìó çíà÷åíèþ ôóíêöèè}
eps1:=eps0; eps11:=eps0; xk0:=xk-eps1; xk1:=xk+eps1; hx:=abs(2*eps1)/mm; y:=yk;
spuskx(eps1,xk0,xk1,hx,y);
yk0:=yk-eps11; yk1:=yk+eps11; hy:=abs(2*eps11)/mm; x:=xk0+ee*hx+eps1;
spusky( eps11,yk0,yk1,hy,x); eps12:=eps0/1.2;
xk0:=x-eps12; xk1:=x+eps12; hx:=abs(2*eps12)/mm; y:=yk0+ee1*hy+eps11;
spuskx( eps12, xk0,xk1,hx,y); eps13:=eps0/1.2;
yk0:=yk0+ee1*hy-eps13; yk1:=yk0+2*eps13; hy:=abs(2*eps13)/mm;
x:=xk0+ee*hx+eps12; spusky( eps13,yk0,yk1,hy,x);
writeln ('',x:30:5' '); writeln ('',yk0:30:5' ',func(x,yk0));writeln;
22: k1:=k1+1 end;
23: k:=k+1 end;
y0:=y0+hh;ii:=1; if (k0k0y <= n00n) then begin y:=y0+ii*h; a01y[k0k0y]:=func(x,y);
ii:=ii+1; k0k0y:=k0k0y+1; end; end; k0k0y:=1; x0:=x0+hh;
for r:=1 to n00n do begin x:=x0+r*h; ykk0:=y0; y:=y0; tty:=n00;hy:=h;
miny (x,y,min,ee1);
a01x[k0k0x]:=min; k0k0x:=k0k0x+1; end; k0k0x:=1; y0:=y00; end; readln; end.
Ðåçóëüòàòû ðàáîòû ïðîãðàììû ïðåäñòàâëåíû â òàáë 1.
Äëÿ âû÷èñëåíèÿ íóëåé äîñòàòî÷íî
â ïîäïðîãðàììå func ñôîðìèðîâàòü
çíà÷åíèÿ ìîäóëÿ ôóíêöèè:
function func (x,y:extended):extended;
begin func:=abs(-exp(-sqr((sqrt(x*x+y*y)-2)))
-exp(-sqr(sqrt(x*x+y*y)-3))+0.1*sin(x*y)); end;
Ðåçóëüòàòû ðàáîòû ïðîãðàììû
ïðåäñòàâëåíû â òàáë 2. Ðàññìîòðåííûì
ñïîñîáîì íàõîäÿòñÿ äåéñòâèòåëüíàÿ è
ìíèìàÿ ÷àñòè êîìïëåêñíûõ íóëåé ìíî-
ãî÷ëåíà [1], êâàäðàò ìîäóëÿ êîòîðîãî
ìîæíî îïðåäåëÿòü óìíîæåíèåì íà êîì-
ïëåêñíî-ñîïðÿæåííîå çíà÷åíèå ìíîãî÷ëåíà, âû÷èñëÿåìîå â àðèôìåòèêå êîìïëåê-
ñíûõ ÷èñåë [7–9].
Ñóùåñòâåííûì ÿâëÿåòñÿ êà÷åñòâî îäíîâðåìåííîé èäåíòèôèêàöèè âñåõ íóëåé
è ýêñòðåìóìîâ ôóíêöèé äâóõ ïåðåìåííûõ â îêðåñòíîñòÿõ ïðîèçâîëüíîãî (äîñòà-
òî÷íî ìàëîãî) ðàäèóñà áåç àïðèîðíîãî óêàçàíèÿ îáëàñòè îòäåëüíîãî íóëÿ èëè ýêñ-
òðåìóìà, îáëàñòè âñåãî èõ ìíîæåñòâà è íà÷àëüíîãî ïðèáëèæåíèÿ. Ìàòåìàòè÷åñêèå
ìåòîäû, êàê ïðàâèëî [10, 11], èñïîëüçóþò äàííûå ïàðàìåòðû. Â ïðåäëîæåííîé
ñõåìå âñå íóëè è ýêñòðåìóìû èäåíòèôèöèðóþòñÿ ïî çíà÷åíèþ è ìåñòîïîëîæåíèþ.
Ñîãëàñíî ÷èñëåííûì ýêñïåðèìåíòàì [6, 9, 12–14] óñòîé÷èâîñòü è òî÷íîñòü ïðè-
áëèæåíèÿ àíàëîãè÷íû äîñòèãàåìûì â îäíîìåðíîì ñëó÷àå.
Ëîêàëèçàöèÿ ýêñòðåìóìîâ ôóíêöèè íåñêîëüêèõ äåéñòâèòåëüíûõ ïåðå-
ìåííûõ. Îòíîñèòåëüíî äåéñòâèòåëüíîé ôóíêöèè n äåéñòâèòåëüíûõ ïåðåìåííûõ
� � f x x x n( , , , )1 2 � ïðåäïîëàãàåòñÿ, ÷òî ïîâòîðíûå ïðåäåëû ñîâïàäàþò ñ ïðåäå-
ëàìè îäíîâðåìåííî ïî âñåì ïåðåìåííûì â êàæäîé òî÷êå ýêñòðåìóìà. Èçëîæåí-
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
Ò à á ë è ö à 1
Çíà÷åíèÿ àðãóìåíòîâ Çíà÷åíèÿ
ìèíèìóìîâ
ôóíêöèè zx y
� 2.41477 0.65000 � 1.6576010915
� 2.07453 � 1.71591 � 1.5695232027
����� ����� �����
1.87936 1.88013 � 1.5763022602
1.87957 5.84920 � 0.1000509240
Ò à á ë è ö à 2
Çíà÷åíèÿ àðãóìåíòîâ
Çíà÷åíèÿ íóëåé ôóíêöèè z
x y
� 4.9552450E+0000 � 4.4776119E-0002 0.00000000000000E+0000
� 4.95798840E+0000 � 2.5373134E+0000 3.44107134822060E-0020
� 4.1243246E+0000 � 3.8059701E+0000 4.00223067577657E-0020
������� ������� �������
6.7463688E+0000 4.6567164E+0000 7.25056330178458E-0020
4.8166294E+0000 6.5223880E+0000 3.23831094870378E-0020
íàÿ ñõåìà îáîáùàåòñÿ íà ñëó÷àé äàííîé ôóíêöèè ñëåäóþùèì îáðàçîì. Ââîäèòñÿ
ìíîãîìåðíàÿ ðàâíîìåðíàÿ ñåòêà ñ óçëàìè ïåðåìåííûõ, ðàñïîëîæåííûìè âäîëü
ïðÿìûõ, ïàðàëëåëüíûõ ñîîòâåòñòâåííûì îñÿì äåêàðòîâûõ êîîðäèíàò. Âíà÷àëå
âûáèðàåòñÿ ïåðåìåííàÿ x1 è äëÿ êàæäîãî åå óçëîâîãî çíà÷åíèÿ íà ïðÿìîé, ïàðàë-
ëåëüíîé ñîîòâåòñòâåííîé ýòîé ïåðåìåííîé îñè, íàõîäèòñÿ ìèíèìóì (ìàêñèìóì)
ôóíêöèè �, êîòîðûé áåðåòñÿ ïî n �1 äðóãèì ïåðåìåííûì. Âñå òàêèå ìèíèìóìû
(ìàêñèìóìû) ïîñòóïàþò íà âõîä ñîðòèðîâêè â âèäå ïîñëåäîâàòåëüíîñòè, îïåðà-
òîð ëîêàëèçàöèè èäåíòèôèöèðóåò ñðåäè åå ýëåìåíòîâ âñå ëîêàëüíî ìèíèìàëüíûå
(ìàêñèìàëüíûå) ýëåìåíòû — ïî çíà÷åíèþ è ïî èíäåêñó. Êàæäîå ëîêàëèçîâàííîå
çíà÷åíèå x1 ôèêñèðóåòñÿ â êà÷åñòâå ïðèâÿçêè ê èñêîìîìó ëîêàëüíîìó ýêñòðåìó-
ìó ôóíêöèè n ïåðåìåííûõ. Ïðè êàæäîì çíà÷åíèè ôèêñèðîâàííîé òàêèì ñïîñî-
áîì êîîðäèíàòû äëÿ îñòàâøèõñÿ n �1 äðóãèõ êîîðäèíàò âîçîáíîâëÿåòñÿ ïðîöåññ,
ïîëíîñòüþ èäåíòè÷íûé èçëîæåííîìó âûøå äëÿ n êîîðäèíàò. Êîíêðåòíî äëÿ êàæ-
äîãî ôèêñèðîâàííîãî çíà÷åíèÿ ëîêàëèçîâàííîé êîîðäèíàòû x1 âûáèðàþòñÿ ìè-
íèìóìû (ìàêñèìóìû) ïî n �2 ïåðåìåííûì ïðè êàæäîì óçëîâîì çíà÷åíèè ïåðå-
ìåííîé x2, âçÿòîì íà ïðÿìîé ðàâíîìåðíîé ñåòêè, ïàðàëëåëüíîé ñîîòâåòñòâåííîé
ýòîé ïåðåìåííîé îñè. Ìèíèìóìû îáðàçóþò íîâóþ ïîñëåäîâàòåëüíîñòü, êîòîðàÿ
ïîñòóïàåò íà âõîä ñîðòèðîâêè, ñ ïîìîùüþ îïåðàòîðà ëîêàëèçàöèè èäåíòèôèöè-
ðóþòñÿ âñå çíà÷åíèÿ ïðèáëèæåíèé âòîðîé êîîðäèíàòû èñêîìûõ ëîêàëüíûõ ýêñ-
òðåìóìîâ. Äàëåå, ïðè ïîñëåäîâàòåëüíîì ôèêñèðîâàíèè êàæäîãî ñî÷åòàíèÿ ïàðû
óæå ëîêàëèçîâàííûõ êîîðäèíàò ïðîöåññ âîçîáíîâëÿåòñÿ äëÿ îñòàâøèõñÿ n �3 êî-
îðäèíàò è ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà â çàäàííîì ïîðÿäêå íå áóäóò ëîêàëèçî-
âàíû âñå íåçàâèñèìûå ïåðåìåííûå ôóíêöèè �. Êàê è â ñëó÷àå äâóõ ïåðåìåííûõ,
ñõåìà ïîçâîëÿåò èäåíòèôèöèðîâàòü âñå ëîêàëüíûå ýêñòðåìóìû â îêðåñòíîñòè
ïðîèçâîëüíîãî ðàäèóñà, êîòîðûé ìåíüøå ïîëîâèíû íàèìåíüøåãî ðàññòîÿíèÿ
ìåæäó ýêñòðåìóìàìè, áåç àïðèîðíîãî îïðåäåëåíèÿ îáëàñòè ëîêàëèçàöèè è íà-
÷àëüíûõ ïðèáëèæåíèé. Ê ëîêàëèçîâàííûì ïðèáëèæåíèÿì ìîæíî âûïîëíèòü
ñïóñê, àíàëîãè÷íûé ñïóñêó äëÿ äâóõ ïåðåìåííûõ. Íóëè èäåíòèôèöèðóþòñÿ êàê
ìèíèìóìû ìîäóëÿ ôóíêöèè ñ îöåíêîé ìàëîñòè çíà÷åíèÿ. Ïðîãðàììà, ðåàëèçóþ-
ùàÿ ñõåìó äëÿ ôóíêöèè òðåõ ïåðåìåííûõ, ïðèâîäèòñÿ â ðàáîòå [15], äëÿ ÷åòûðåõ
è ïÿòè ïåðåìåííûõ — â [6].
Åñëè îáëàñòü ëîêàëèçàöèè èìååò áîëüøîé ðàçìåð, òî íåîáõîäèìî ïîî÷åðåä-
íî ñìåùàòü îòðåçêè [ , ]
( ) ( )
x x
N
1
0
1
, [ , ] , , [ , ]
( ) ( ) ( ) ( )
x x x x
M
n n
R
2
0
2
0� íà èõ äëèíó äî òåõ
ïîð, ïîêà âñÿ îáëàñòü íå îêàæåòñÿ ïðîéäåííîé. Ïðîâåðêà ýêñòðåìóìîâ â îêðå-
ñòíîñòÿõ ãðàíèö ñìåùàåìûõ îòðåçêîâ äîëæíà âûïîëíÿòüñÿ ïî àíàëîãèè ñ äâó-
ìåðíîé ñõåìîé: èñïîëüçóþòñÿ ýëåìåíòû ìàññèâà óçëîâûõ çíà÷åíèé ïî îáå ñòîðî-
íû îò ëåâîé ãðàíèöû êàæäîãî èç ñìåùàåìûõ îòðåçêîâ. Îòñþäà âûòåêàåò âîçìîæ-
íîñòü èäåíòèôèêàöèè ýêñòðåìóìîâ ïàðàëëåëüíî ïî âñåì ýëåìåíòàì
ðàññìàòðèâàåìîãî âèäà, êîòîðûå ïðè îáúåäèíåíèè ïîêðûâàþò îáëàñòü ïîèñêà,
çàòåì ïàðàëëåëüíî «ñêëåèòü» ðåçóëüòàòû ïî âñåì ãðàíèöàì ýëåìåíòîâ.
×èñëåííîå ðåøåíèå íåëèíåéíûõ ñèñòåì óðàâíåíèé îáùåãî âèäà. Ïðèìå-
íèì ðàññìàòðèâàåìóþ ñõåìó ê ïðèáëèæåííîìó ðåøåíèþ ñèñòåì íåëèíåéíûõ
óðàâíåíèé. Ïóñòü èñõîäíàÿ ñèñòåìà ïðåîáðàçîâàíà ê âèäó
f x x x i ni n( , , ..., ) , ,1 2 0 1� � . (13)
Çäåñü ëåâûå ÷àñòè ÿâëÿþòñÿ äåéñòâèòåëüíûìè ôóíêöèÿìè îò n äåéñòâèòåëü-
íûõ ïåðåìåííûõ. Ñîâîêóïíîñòü ôóíêöèé ëåâîé ÷àñòè (13) îáðàçóåò n-ìåðíóþ
âåêòîð-ôóíêöèþ àðãóìåíòîâ x x x n1 2, , ..., . Òðåáóåòñÿ ïðèáëèæåííî íàéòè âñå
ðåøåíèÿ ñèñòåìû (13) â ìíîãîìåðíîì ïàðàëëåëåïèïåäå [ , ]
( ) ( )
x x
L
1
0
1
1 ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 173
[ , ]
( ) ( )
x x
L
2
0
2
2 , � , [ , ]
( ) ( )
x xn n
Ln0
, âõîäÿùåì â îáëàñòü îïðåäåëåíèÿ äàííîé âåê-
òîð-ôóíêöèè. Ñòðîèòñÿ ìíîãîìåðíàÿ ñåòêà x x hj j j jj� �� �( )0
, h
x x
L
j
j
L
j
j
j
�
�
( ) ( )0
,
� �j jL� 0 1, , , , j n�1, . Âî âñåõ åå óçëàõ âû÷èñëÿþòñÿ çíà÷åíèÿ êàíîíè÷åñêîé
íîðìû (äëÿ îïðåäåëåííîñòè || || | |Z z i
i
n
�
�
�
1
) ðàññìàòðèâàåìîé âåêòîð-ôóíêöèè, êî-
òîðûå âûðàæàþòñÿ ýëåìåíòàìè n-ìåðíîãî ìàññèâà
c f x f x f xj j j n jj j j j� � � ��� � � �| ( ) | | ( ) | | ( ) |1 2 , (14)
ãäå èíäåêñû ñîîòâåòñòâóþò óçëàì ìíîãîìåðíîé ñåòêè. Ëåâàÿ ÷àñòü (14) èíòåð-
ïðåòèðóåòñÿ êàê äèñêðåòèçèðîâàííàÿ ôóíêöèÿ n ïåðåìåííûõ, åå ìèíèìóìû
ìîæíî èäåíòèôèöèðîâàòü ïðîãðàììíî ïî èçëîæåííîé ñõåìå. Ïðè ýòîì âñå
íóëè íîðìû ôóíêöèè èç ëåâîé ÷àñòè (13) èäåíòèôèöèðóþòñÿ ñðåäè ìèíèìó-
ìîâ ïî çàäàííîé ãðàíèöå ~� ìàëîñòè: 0 � �min ~
j
j
j
j
c
�
� � .
Ïðèìåð 3. Ïðèáëèæåííîå ðåøåíèå ñèñòåìû
x y z
x y z
x y
2 2
2 2 2
0
0
08 0
� � �
� � �
� � �
�
�
,
,
ln .
â ïàðàëëåëåïèïåäå x � [ . , ]0 1 1 , y � [ , ]0 1 , z � [ , ]0 1 âû÷èñëÿåòñÿ ïî ñëåäóþùåé
ïðîãðàììå:
Program UravnNelin;
{$APPTYPE CONSOLE}
Uses SysUtils;
label 21,22,23;
const eps0=0.1; h=eps0/23; x00=0.1; x11=1; y00=0; y11=1; z00=0; z11=1;
n00=trunc(4/h); nn=n00+round(n00/2)+1;
type vect1=array [1..2*nn+nn] of extended;
vect2=array [1..2*nn+nn] of longint;
var i,j,k,k1,r,rx,ry,rz,nn0,kx,ky,kz : longint;
c,a1,az: vect1; e, ex, ey,ez: vect2; x,x0,x1,xk,minx,minz: extended;
y,y0,y1,yk,z0,z1,z,zk: extended;
function f1 (x,y,z:extended):extended;
begin f1:= x*x+y*y-z ; end;
function f2 (x,y,z:extended):extended;
begin f2:= x*x+y*y-z*z; end;
function f3 (x,y,z:extended):extended;
begin f3:= ln(x)-sqrt(y)+0.8; end;
function func (x,y,z:extended):extended;
var p: extended; i1: integer;
begin func:= abs(f1(x,y,z))+abs(f2(x,y,z))+abs(f3(x,y,z)); end;
procedure minyz (var x,y,z,minx:extended);
begin minx:=func(x,y,z);
for i:=1 to trunc((y11-y00)/h) do
for j:=1 to trunc((z11-z00)/h) do
begin y:=y0+i*h; z:=z0+j*h;
IF minx > func(x,y,z) then minx:=func(x,y,z) end end;
procedure minyy (var x,y,z,minz:extended);
begin minz:=func(x,y,z); for i:=1 to trunc((y11-y00)/h) do
begin y:=y0+i*h; IF minz > func(x,y,z) then minz:=func(x,y,z) end end;
procedure sort(var nn0:longint; var c: vect1; var e: vect2);
begin x0:=x00; x1:=x11; y0:=y00; y1:=y11;z0:=z00; z1:=z11; nn0:=n00{-3};
for rx:=1 to nn0 do begin x:=x0+rx*h; minyz (x,y,z,minx); a1[rx]:=minx; end;
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
Oïèñàíèå ïðîöåäóðû sort
sort( nn0, a1, ex); kx:=1; while kx <= nn0 do begin
for rx := 1 to kx-1 do IF abs( ex[kx]-ex[kx-rx] ) <= eps0/h then goto 21;
xk:= x0+ex[kx]*h; for rz:=1 to nn0 do begin
z:=z0+rz*h; x:=xk; minyy (x,y,z,minz); az[rz]:=minz; end;
sort( nn0, az, ez); kz:=1; while kz <= nn0 do begin
for rz := 1 to kz-1 do IF abs(ez[kz]-ez[kz-rz]) <= eps0/h then goto 22; zk:= z0+ez[kz]*h;
for ry:=1 to nn0 do begin y:=y0+ry*h; a1[ry]:=func(xk,y,zk) end;
sort( nn0, a1, ey); ky:=1; while ky <= nn0 do begin
for ry := 1 to ky-1 do IF abs(ey[ky]-ey[ky-ry]) <= eps0/h then goto 23;
yk:= y0+ey[ky]*h; writeln (' ', xk:30:4,' '); writeln (' ', yk:30:4,' ');
writeln (' ', zk:30:4,' ', f1(xk,yk,zk):2:4,' ',f2(xk,yk,zk):2:4,' ',f3(xk,yk,zk):2:4); writeln;
23: ky:=ky+1; end;
22: kz:=kz+1; end;
21: kx:=kx+1; end; writeln('end'); readln; end.
 ðåçóëüòàòå ïîëó÷èì çíà÷åíèÿ,
ïðåäñòàâëåííûå â òàáë. 3. Äëÿ íåëè-
íåéíûõ ñèñòåì ñ íååäèíñòâåííûì
ðåøåíèåì ñõåìà ïîçâîëÿåò ïðîãðàì-
ìíî ëîêàëèçîâàòü âñå ìèíèìóìû
íîðìû (14) è ñðåäè íèõ âûäåëèòü
íàèáîëåå áëèçêèå ê íóëþ. Èõ ëîêà-
ëèçàöèÿ â îêðåñòíîñòè íàïåðåä çà-
äàííîãî ðàäèóñà îçíà÷àåò ïðèáëè-
æåíèå ê ðåøåíèþ ïî íîðìå ñ òî÷íîñòüþ äî çíà÷åíèÿ ðàäèóñà. Íàïðèìåð, äëÿ
ñèñòåìû
x y xy
x y y x
3 3 8 0
0
� � �
�
�
�
,
ln( ) – ln( ) ,
êîòîðàÿ èìååò òðè ðåøåíèÿ, ïðåäëîæåííàÿ ñõåìà äàåò ñåìü çíà÷åíèé ìèíèìó-
ìîâ íîðìû, èç íèõ òðè íàèìåíüøèå, äîñòàòî÷íî áëèçêèå ê íóëþ (ïîä÷åðêíó-
òû), ïðèáëèæàþò èñêîìûå ðåøåíèÿ (òàáë. 4).
Ñõåìà áåç èçìåíåíèÿ ìîæåò
ïðèìåíÿòüñÿ äëÿ ïðèáëèæåííûõ ðå-
øåíèé ñèñòåì ëèíåéíûõ è íåëèíåé-
íûõ àëãåáðàè÷åñêèõ, à òàêæå òðàíñ-
öåíäåíòíûõ óðàâíåíèé [6], ïî ñïî-
ñîáó êîìïüþòåðèçàöèè îòëè÷àÿñü îò
àíàëîãîâ èç [10, 16]. Òàêîé ìåòîä íà
âõîäå èñïîëüçóåò çíà÷åíèÿ ôóíêöèè,
êîòîðûå ñ ó÷åòîì îáùíîñòè îãðàíè-
÷åíèé ìîãóò áûòü ïîëó÷åíû â ðåçóëü-
òàòå ðåøåíèÿ íåêîòîðîé äðóãîé çàäà-
÷è â ðåàëüíîì âðåìåíè. Ñóùåñòâåí-
íûì îãðàíè÷åíèåì ïðè ýòîì ÿâëÿåòñÿ
òðåáîâàíèå äîñòàòî÷íîé ìàëîñòè
øàãà äèñêðåòèçàöèè. Îòëè÷èòåëüíûì
êà÷åñòâîì (êàê è â äâóìåðíîì ñëó÷àå)
ÿâëÿåòñÿ îòñóòñòâèå íà÷àëüíûõ ïðè-
áëèæåíèé, à òàêæå îòñóòñòâèå îáëà-
ñòè ëîêàëèçàöèè ýêñòðåìóìîâ, èñ-
ïîëüçóåìûõ â ìàòåìàòè÷åñêèõ ìåòî-
äàõ [11, 12, 16]. ×èñëåííûé
ýêñïåðèìåíò ïîêàçûâàåò ïðèìåíè-
ìîñòü ñõåìû â ñëó÷àå ñëîæíûõ ðåëüåôîâ âåêòîð-ôóíêöèé èç ëåâîé ÷àñòè (13)
[6], âêëþ÷àÿ ðàçðûâû ïåðâîãî ðîäà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 175
Ò à á ë è ö à 3
Çíà÷åíèÿ àðãóìåíòîâ
Çíà÷åíèÿ
êîìïîíåíò
x y z
0.8870 0.4609 1.0000
f1 00009� � .
f 2 00009� � .
f 3 00012� .
Ò à á ë è ö à 4
Çíà÷åíèÿ àðãóìåíòîâ
Çíà÷åíèÿ êîìïîíåíò
f
f
1
2
x y
1.94007 3.67910
� 00000000000
00890364151
.
.
2.07596 3.77313
� 0.0000000000
0.0006942907
2.49393 4.01045
�
�
00000000000
02011612746
.
.
3.67927 1.94030
00000000000
00888810927
.
.�
3.77324 2.07612
0.0000000000
0.0005957791�
4.01049 2.49403
00000000000
02011954085
.
.
4.00000 4.00000
� 0.0000000000
0.0000000000
Èäåíòèôèêàöèÿ ýêñòðåìóìîâ è íóëåé ðàçíîñòíûõ ðåøåíèé ñèñòåì
ÎÄÓ. Ðàññìîòðèì çàäà÷ó Êîøè äëÿ óðàâíåíèÿ
dy
dt
f t y y t y� �( , ), ( )0 0 , (15)
îòíîñèòåëüíî êîòîðîãî ïðåäïîëàãàåòñÿ âûïîëíåíèå âñåõ óñëîâèé ñóùåñòâîâà-
íèÿ è åäèíñòâåííîñòè. Êðîìå òîãî, ïðåäïîëàãàåòñÿ ñõîäèìîñòü ìåòîäà Ýéëåðà
ñ ðàâíîìåðíûì øàãîì ê ðåøåíèþ çàäà÷è (15) íà îòðåçêå [ , ]t T0 :
y y f t y h t t ih i N h
T t
N
i i i i i
N
�
�
� � � � � �
�
1 0
00 1( , ) , , , , , ; ; lim�
�
�y yi . (16)
Ðàçíîñòíûå çíà÷åíèÿ èç (16) ðàññìàòðèâàþòñÿ êàê ýëåìåíòû ìàññèâà
c i y t i[ ] ( )� �1 , i N�1 2, , ,� , (17)
êîòîðûé ñîðòèðóåòñÿ ñ ïðèñîåäèíåíèåì îïåðàòîðà ëîêàëèçàöèè ýêñòðåìóìîâ.
Îáðàáîòêà ìàññèâà (17) ïðàêòè÷åñêè íå îòëè÷àåòñÿ îò îáðàáîòêè ìàññèâà (10)
äëÿ ôóíêöèè îäíîé ïåðåìåííîé, çà èñêëþ÷åíèåì òîãî, ÷òî â ñëó÷àå ðàçíî-
ñòíîé ñõåìû íåëüçÿ âûïîëíèòü ñïóñê. Ïðè äàííîì ñïîñîáå ëîêàëèçàöèÿ ïî èí-
äåêñó øàãà îçíà÷àåò îêîí÷àòåëüíóþ èäåíòèôèêàöèþ ýêñòðåìóìà. Ïîýòîìó ïî-
ãðåøíîñòü âû÷èñëåíèÿ ýêñòðåìóìîâ ðåøåíèÿ óðàâíåíèÿ (15) ïîëíîñòüþ îïðåäå-
ëÿåòñÿ ïîãðåøíîñòüþ ðàçíîñòíîãî ïðèáëèæåíèÿ è íå ïðåâûñèò åå. Â ýòèõ
ãðàíèöàõ èìåþò ìåñòî óñòîé÷èâîñòü ëîêàëèçàöèè è âû÷èñëåíèÿ ýêñòðåìóìîâ
ðåøåíèÿ (16) [6, 14]. Äëÿ ïîèñêà íóëåé äîñòàòî÷íî âçÿòü ìîäóëè çíà÷åíèé (17)
è èç èõ ìèíèìóìîâ âûáðàòü áëèçêèå ê íóëþ. Êàê è â ñëó÷àå ôóíêöèè îäíîé
ïåðåìåííîé, íåîáõîäèìî ñìåùåíèå òåêóùåãî îòðåçêà ïî âñåìó ïðîìåæóòêó ïî-
èñêà ýêñòðåìóìîâ ñ äîïîëíèòåëüíîé ïðîâåðêîé ãðàíèö ñìåùàåìîãî îòðåçêà íà
ýêñòðåìóì. Ïðîâåðêà âûïîëíÿåòñÿ ñîðòèðîâêîé íåêîòîðîãî ÷èñëà ýëåìåíòîâ
â îêðåñòíîñòè ëåâîé ãðàíèöû òåêóùåãî îòðåçêà ñ ïðèñîåäèíåíèåì îïåðàòîðà
ëîêàëèçàöèè. Â èòîãå äîñòèãàåòñÿ èíâàðèàíòíîñòü ñõåìû îòíîñèòåëüíî ðàçìå-
ðîâ èññëåäóåìîãî îòðåçêà [ , ]t T0 . Ìåòîä Ýéëåðà ìîæíî çàìåíèòü ðàçíîñòíûì
ìåòîäîì áîëåå âûñîêîãî ïîðÿäêà. ×èñëåííûé ýêñïåðèìåíò ñ êîäîì ïðîãðàìì
íà Delphi ïðåäñòàâëåí â [6].
Ñõåìà áåç ïðèíöèïèàëüíûõ èçìåíåíèé ïåðåíîñèòñÿ íà ñëó÷àé äâóõ è áîëåå
óðàâíåíèé ïîñðåäñòâîì åå áóêâàëüíîãî ïîâòîðåíèÿ äëÿ êàæäîãî óðàâíåíèÿ â îò-
äåëüíîñòè. Ïðåäïîëàãàåòñÿ, ÷òî äëÿ çàäà÷è Êîøè
dY
dt
F t Y Y t Y� �( , ), ( )0 0, (18)
ãäå F t Y f t Y f t Y f t Yn( , ) ( ( , ), ( , ), , ( , ))� 1 2 � , Y y t y t y tn� ( ( ), ( ), , ( ))1 2 � , Y y0 01� ( ,
y y n02 0, , )� , âûïîëíåíû âñå óñëîâèÿ ñóùåñòâîâàíèÿ è åäèíñòâåííîñòè. Ïðè ýòîì
èìååò ìåñòî ñõîäèìîñòü ê ðåøåíèþ ðàññìàòðèâàåìîãî ðàçíîñòíîãî ìåòîäà íà îòðåçêå
[ , ]t T0 . Íà âõîä ñîðòèðîâêè ïîäàþòñÿ ðàçíîñòíûå ïðèáëèæåíèÿ (äëÿ ïðîñòîòû ïî ìå-
òîäó Ýéëåðà) êàæäîé êîìïîíåíòû ðåøåíèÿ
y y f t y y y h ck i y tk i ki k i i i ni ki i( ) ( , , , , ) , [ ] ( )� �� � � �1 1 2 1� , , , ,k n�1 2 � ; (19)
t t ih i N h
T t
N
i � � � �
�
0
00 1, , , , ,� .
 ðåçóëüòàòå ïðèìåíåíèÿ ìåòîäà èäåíòèôèöèðóþòñÿ âñå ëîêàëüíûå ýêñòðåìóìû
êàæäîé ïåðåìåííîé yk , äèñêðåòèçèðîâàííîé â âèäå ïîñëåäîâàòåëüíîñòè ck i[ ] ,
â îêðåñòíîñòÿõ ïðîèçâîëüíîãî (äîñòàòî÷íî ìàëîãî) ðàäèóñà íà âñåì îòðåçêå
[ , ]t T0 . Íóëè ðàçíîñòíûõ ïðèáëèæåíèé êîìïîíåíò áóäóò èäåíòèôèöèðîâàíû,
åñëè íà âõîä ïîäàâàòü ìîäóëè çíà÷åíèé (19) ñ îöåíêîé íà âûõîäå ìàëîñòè ìè-
íèìóìîâ. Ïî-ïðåæíåìó íåîáõîäèìî ñìåùåíèå òåêóùåãî îòðåçêà ïî âñåìó ïðî-
ìåæóòêó ïîèñêà ýêñòðåìóìîâ ñ ïðîâåðêîé ãðàíèö ñìåùàåìîãî îòðåçêà íà ýêñò-
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
ðåìóì. Âìåñòî ìåòîäà Ýéëåðà ìîãóò ïðèìåíÿòüñÿ ðàçíîñòíûå ìåòîäû âûñøåãî
ïîðÿäêà. ×èñëåííûé ýêñïåðèìåíò â [6] ïîêàçûâàåò âîçìîæíîñòü èäåíòèôèêàöèè
ýêñòðåìóìîâ ñ òî÷íîñòüþ äî ôîðìàòà ïðåäñòàâëåíèÿ äàííûõ â ÿçûêå ïðîãðàì-
ìèðîâàíèÿ.
Äëÿ èäåíòèôèêàöèè ýêñòðåìóìîâ íîðìû ðåøåíèé ôîðìèðóåòñÿ îäíîìåðíûé
ìàññèâ çíà÷åíèé íîðìû || ( ) ||Y t i ðàçíîñòíîãî ðåøåíèÿ ñèñòåìû (18), íàïðèìåð
c i y i y i y in[ ] | [ ] | | [ ] | | [ ] | ,� � � � � � �1
2
2
2 21 1 1� i N�1 2, , ,� . (20)
Ñ èñïîëüçîâàíèåì ïðîöåäóðû sort è îïåðàòîðà ëîêàëèçàöèè ê îäíîìåðíîìó
ìàññèâó (20) ïðèìåíÿåòñÿ ñõåìà èäåíòèôèêàöèè ýêñòðåìóìîâ ÷èñëîâîé ïîñëåäî-
âàòåëüíîñòè. Íóëè ðàçíîñòíîãî ïðèáëèæåíèÿ âåêòîð-ôóíêöèè ðåøåíèÿ ñèñòå-
ìû (18) îïðåäåëÿþòñÿ êàê äîñòàòî÷íî ìàëûå ìèíèìóìû íîðìû (20).
Îïðåäåëåíèå ýêñòðåìóìîâ âîçìóùåíèé ðàçíîñòíûõ ðåøåíèé ñèñòåì
ÎÄÓ ïðè âàðèàöèè ïàðàìåòðîâ. Ðàññìàòðèâàåìûé ïîäõîä ìîæíî ïðèìåíèòü
äëÿ îïðåäåëåíèÿ ýêñòðåìóìîâ âîçìóùåíèé ðåøåíèé ñèñòåì ÎÄÓ â ðàçíîñòíîé
ôîðìå, â òîì ÷èñëå ïðè âàðèàöèè ïàðàìåòðîâ. Èäåíòèôèêàöèè ýêñòðåìóìîâ
íîðì ìóëüòèïëèêàòèâíûõ [17, 18] ïðåîáðàçîâàíèé ðàçíîñòíûõ ðåøåíèé ïîçâîëÿ-
åò îöåíèòü ýêñòðåìàëüíîå îòêëîíåíèå ñèñòåìû îò óñòîé÷èâîãî ñîñòîÿíèÿ. Óñòîé-
÷èâîñòü â ñìûñëå Ëÿïóíîâà ïîíèìàåòñÿ ïî îïðåäåëåíèþ èç [19]. Ïóñòü äàíà ñèñ-
òåìà ÎÄÓ îáùåãî âèäà
dY
dt
F t Y a a a Y t Y� �( , , , , ), ( )1 2 3 0 0 , (21)
ãäå Y t( ) îïðåäåëÿþòñÿ êàê â (18), t t T0 � � . Äëÿ ïðîñòîòû ðàññìàòðèâàþòñÿ
òðè âàðüèðóåìûõ ÷èñëîâûõ ïàðàìåòðà: a a a1 2 3, , â äèàïàçîíå a a a10 1 11� � ,
a a a20 2 21� � , a a a30 3 31� � (àíàëîãè÷íî ìîãóò ðåøàòüñÿ çàäà÷è ñ ÷åòûðüìÿ è
áîëåå ïàðàìåòðàìè). Âîçìóùåííûå íà÷àëüíûå äàííûå îáîçíà÷àþòñÿ
~
( )
~
,Y t Y0 0�
ñîîòâåòñòâåííîå âîçìóùåííîå ðåøåíèå —
~
( )Y t . Òðåáóåòñÿ íàéòè âñå ýêñòðå-
ìàëüíûå çíà÷åíèÿ âîçìóùåíèé ïðè âàðèàöèè ïàðàìåòðîâ â ðàçíîñòíîì ïðè-
áëèæåíèè ðåøåíèé. Äëÿ ýòîãî â ãðàíèöàõ âàðèàöèè äîñòàòî÷íî îöåíèòü íîðìó
îòêëîíåíèÿ îò íóëÿ ðàçíîñòè ìåæäó âîçìóùåííûì è íåâîçìóùåííûì ðàçíîñ-
òíûìè ðåøåíèÿìè ñèñòåìû (21).
Ñïîñîá îñíîâûâàåòñÿ íà èçëîæåííîé ñõåìå èäåíòèôèêàöèè ýêñòðåìóìîâ
ôóíêöèè ÷åòûðåõ ïåðåìåííûõ.  êà÷åñòâå äèñêðåòèçèðóåìîé ôóíêöèè âûñòóïà-
åò íîðìà âû÷èñëÿåìûõ ïî ðàçíîñòíîé ñõåìå çíà÷åíèé Y t Y t( )
~
( )� , ïðè ýòîì â êà-
÷åñòâå îäíîé íåçàâèñèìîé ïåðåìåííîé âûñòóïàåò t , â êà÷åñòâå òðåõ äðóãèõ —
âàðüèðóåìûå ïàðàìåòðû. Ïðè âûáîðå, íàïðèìåð, åâêëèäîâîé íîðìû íà âõîä
ìåòîäà ïîñòóïàåò ýëåìåíò ìàññèâà
c i a a a y i y ik k
k
n
[ , , , ] | [ ] ~ [ ] | ,1 2 3
2
1
1 1� � � �
�
� i N�1 2, , ,� . (22)
Çíà÷åíèÿ Y t Y t( ),
~
( ) ñèíõðîííî âû÷èñëÿþòñÿ ïî ðàçíîñòíîé ñõåìå îòäåëüíî äëÿ
êàæäîãî íàáîðà äèñêðåòèçèðîâàííûõ çíà÷åíèé ïàðàìåòðîâ. Øàã èçìåíåíèÿ íå-
çàâèñèìîé ïåðåìåííîé, åñëè ýòî íå íàðóøàåò êîððåêòíîñòè ðåøåíèÿ, âûáèðàåò-
ñÿ íà ïîðÿäîê ìåíüøå øàãà äèñêðåòèçàöèè ïàðàìåòðîâ (ñ öåëüþ óñêîðåíèÿ âû-
÷èñëåíèé). Äèñêðåòèçèðîâàííûå çíà÷åíèÿ ëåâîé ÷àñòè (22) çàäàþò ÷åòûðåõìåð-
íûé ìàññèâ ñ ýëåìåíòàìè c i j r[ , , , ]� . Ñîãëàñíî (22) c i j r c i a a a[ , , , ] [ , , , ]� � 1 2 3
ïðè çíà÷åíèÿõ ïàðàìåòðîâ a a j1 1� [ ] , a a2 2� [ ]� , a a r3 3� [ ] , èíäåêñû ñîîòâå-
òñòâóþò íîìåðàì øàãîâ äèñêðåòèçàöèè. Â îñòàëüíîì ñõåìà èäåíòèôèêàöèè ýêñ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 177
òðåìóìîâ ôóíêöèè ÷åòûðåõ ïåðåìåííûõ íå èçìåíÿåòñÿ. Íàéäåííûå ïî òàêîé
ñõåìå ýêñòðåìóìû õàðàêòåðèçóþò ðàçíîñòíîå ïðèáëèæåíèå ìåðû îòêëîíåíèÿ
âîçìóùåííîãî ðåøåíèÿ îò íåâîçìóùåííîãî. Âèäîèçìåíåíèå óñëîâèÿ (8) â ôîð-
ìå íåðàâåíñòâà | [ ] [ ] |e k L e k� � � 1, L n k� �1 2, , ,� , â ðåçóëüòàòå ïðèìåíåíèÿ
ìåòîäà äàåò ãëîáàëüíûé ìàêñèìóì; àíàëîãè÷íîå èçìåíåíèå óñëîâèÿ (7) äàåò
ãëîáàëüíûé ìèíèìóì [12]. Ñ ýòèìè èçìåíåíèÿìè èäåíòèôèöèðóþòñÿ ãëîáàëü-
íûå ýêñòðåìóìû âîçìóùåíèÿ ðåøåíèÿ ñèñòåìû (21) íà îòðåçêå t t T0 � � ïðè
âñåõ äèñêðåòíûõ çíà÷åíèÿõ òðåõ ïàðàìåòðîâ, â ðåçóëüòàòå îïðåäåëÿþòñÿ çíà÷å-
íèÿ ïàðàìåòðîâ è ìîìåíò âðåìåíè, ïðè êîòîðûõ ýêñòðåìóìû âîçìóùåíèé íàè-
áîëåå «îïàñíû» äëÿ ñèñòåìû óïðàâëåíèÿ.
Äëÿ îáùåé îöåíêè âîçìóùåíèå ðåøåíèÿ ñèñòåìû (21) ïðåîáðàçóåòñÿ ê âèäó
~ ( )( ~ )( ) ( )
( )
y y D h y yk i k i
i
i l
k
k k
r
i
� �
�
�
�
�
� � � � ��1 1
0
0 0
0
1
�
1
0
11� �
�
� � �� �
�
i
i l
k
k i r kiD h w w( )
( )
( ) ,
ãäå h äàíî â (19), D
f t Y f t Y
y yi
k k i i k i i
ki ki
( ) ( ,
~
) ( , )
~�
�
�
, wki — îñòàòî÷íûå ÷ëåíû ðàçëî-
æåíèÿ ðàçíîñòè ðåøåíèé ïî ôîðìóëå Òåéëîðà íà i -ì øàãå ìåòîäà Ýéëåðà,
k n�1 2, , ,� . Íà îñíîâå äàííîãî ïðåîáðàçîâàíèÿ îöåíèâàåòñÿ íå òîëüêî ýêñòðå-
ìàëüíîå âîçìóùåíèå ïðè ðàññìàòðèâàåìîé âàðèàöèè ïàðàìåòðîâ, íî è óñòîé-
÷èâîñòü íåâîçìóùåííîãî ðåøåíèÿ [6, 17–20]. Ïðè ýòîì îöåíêå ïîäëåæèò íîð-
ìà âåêòîðà, êîìïîíåíòàìè êîòîðîãî ÿâëÿþòñÿ
��
�� �
0
1
i
i l
k
D h( )
( )
, k n�1 2, , ,� .
Àíàëîãè÷íîå ïðåîáðàçîâàíèå äëÿ ëèíåéíîé îäíîðîäíîé ñèñòåìû
dY
dt
A t a a a Y� ( , , , )1 2 3 , Y t( )0 0�
�
ïðèìåò âèä
~
( ( , , , ))(
~
)Y Y E hA t a a a Y Yi i
i
� �
�
�
� � � ��1 1
0
1
1 2 3 0 0
�
� [17, 18]. Äëÿ îöåíêè
óñòîé÷èâîñòè äàííîé ñèñòåìû äîñòàòî÷íî àíàëèçèðîâàòü ýêñòðåìóìû çíà÷åíèé
�
�
�
�
� �
0
1
1 2 3
i
E hA t a a a( ( , , , )) ïðè âàðèàöèè äèñêðåòèçèðîâàííûõ ïàðàìåòðîâ.
Ãëîáàëüíûé ýêñòðåìóì íåïîñðåäñòâåííî óêàçûâàåò ìåðó îòêëîíåíèÿ ñèñòåìû
îò óñòîé÷èâîãî ñîñòîÿíèÿ íà ïðîìåæóòêå ðåøåíèÿ â ãðàíèöàõ âàðèàöèè. Ñîîò-
âåòñòâåííûå ÷èñëåííûå ýêñïåðèìåíòû ñ èñïîëüçîâàíèåì ðàçëè÷íûõ ðàçíîñ-
òíûõ ñõåì è ïîëíûå êîäû ïðîãðàìì ïðèâîäÿòñÿ â [6, 20, 21]. Â [21] äàííûé
ïîäõîä ïðèìåíÿåòñÿ ê îöåíêå âîç-
ìóùåíèé ýíåðãåòè÷åñêèõ ñèñòåì
áîëüøîé ìîùíîñòè ïðè âîçìóùå-
íèè ïàðàìåòðîâ. Îáîñíîâàíèå îïè-
ðàåòñÿ íà êðèòåðèè, èçëàãàåìûå
â [17, 18]. Òàêîé ïîäõîä ñîîòíîñèò-
ñÿ ñ âîçìîæíîñòüþ àíàëèçà óñòîé-
÷èâîñòè ëèíåéíîé ñèñòåìû íà
îñíîâå íóëåé õàðàêòåðèñòè÷åñêîé
ôóíêöèè. Íàïðèìåð, äëÿ ñèñòåìû
óïðàâëåíèÿ ñ èäåàëüíûì çàïàçäûâàíèåì ïî âðåìåíè (ðèñ. 1) õàðàêòåðèñòè÷åñ-
êîå óðàâíåíèå èìååò âèä s s s e
t s3 22 00� � � �� . Íóëè òðàíñöåíäåíòíîé ôóíêöèè
f s s s s e
t s( ) � � � � �3 22 0 ìîæíî íàéòè ïî îïèñàííîé âûøå ñõåìå, åñëè f s( ) ïðå-
îáðàçîâàòü â ôóíêöèþ äâóõ ïåðåìåííûõ óìíîæåíèåì íà êîìïëåêñíî-ñîïðÿæåí-
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
Ðèñ. 1
�
�
1
1 2s s( )�
e
t s� 0
íîå çíà÷åíèå. Ïðè âàðèàöèè t0 ñ øàãîì 0.01 âû÷èñëÿþòñÿ ñëåäóþùèå ïîïàðíî ðàñ-
ïîëàãàåìûå çíà÷åíèÿ äåéñòâèòåëüíîé è ìíèìîé ÷àñòåé íóëåé: (0.01: �0.12, �0.74;
�0.12, 0.74; �1.75, �4.56); (0.02: �0.12, �0.74; �0.12, 0.74; �1.75,
�4.57); � ; (0.51: �2.32, 0.71; �2.32, �0.71; �1.64, �2.35); (0.52: 1.97E�003, 0.71;
1.97E�003, �0.71; �1.64, 0); (0.53: �1.63, 0; 4.16E�003, 0.71; 4.16E�003,
�0.71); (0.54: �1.63, 0; 6.34E�003, 0.71; 6.34E�003, �0.71); (0.55: 8.51E�003,
0.71; 8.51E�003, �0.71; �1.62, 0); (0.56: 1.07E�002, 0.71; 1.07E�002, �0.71;
�1.62, �2.57); …
Òàêèì îáðàçîì, íà îòðåçêå [ , . ]0 0 51 èìååò ìåñòî àñèìïòîòè÷åñêàÿ óñòîé÷è-
âîñòü ñèñòåìû (îòðèöàòåëüíûå äåéñòâèòåëüíûå ÷àñòè íóëåé), íà îòðåçêå
[ . , . ]0 52 0 55 èìååò ìåñòî íåàñèìïòîòè÷åñêàÿ óñòîé÷èâîñòü (íóëåâûå äåéñòâèòåëü-
íûå ÷àñòè), äàëåå ñëåäóåò îáëàñòü íåóñòîé÷èâîñòè, êîòîðàÿ ìåíÿåò õàðàêòåð
ñ ðîñòîì t0.
Ïîäõîä ê ïîèñêó íà àíàëîãè÷íîé îñíîâå íóëåé è ýêñòðåìóìîâ ðàçíîñòíûõ
ðåøåíèé óðàâíåíèé â ÷àñòíûõ ïðîèçâîäíûõ èçëàãàåòñÿ â [6, 13].
Îáîáùåííàÿ ëîêàëèçàöèÿ ýêñòðåìóìîâ íà îñíîâå ñîðòèðîâêè. Èäåíòèôè-
êàöèÿ ýêñòðåìàëüíûõ ýëåìåíòîâ ïîñëåäîâàòåëüíîñòè ñîãëàñíî óñëîâèÿì (7), (8)
âûïîëíÿåòñÿ èñêëþ÷èòåëüíî ïî èíäåêñàì, ïîýòîìó ìîæåò áûòü îòíåñåíà ê ïîñëå-
äîâàòåëüíîñòè ýëåìåíòîâ ïðîèçâîëüíîãî ìíîæåñòâà, åñëè íà íåì àïðèîðè çàäàíî
îòíîøåíèå ïîðÿäêà �. Âîçìîæíî ñàìîñòîÿòåëüíîå îïðåäåëåíèå ïðîãðàììèñòîì
ôóíêöèè ñðàâíåíèÿ ñëîæíûõ îáúåêòîâ è âûäåëåíèå ñðåäè íèõ ýêñòðåìàëüíûõ
â ñìûñëå äàííîãî ñðàâíåíèÿ. Ïî ìåòðèêå, êîòîðàÿ äîëæíà áûòü àïðèîðè îïðåäåëå-
íà íà ìíîæåñòâå, èäåíòèôèöèðóåòñÿ çíà÷åíèå ýêñòðåìàëüíîãî ýëåìåíòà èëè îáúåê-
òà. Âûäåëåííûå ïî ýêñòðåìàëüíûì ïðèçíàêàì îáúåêòû ìîæíî ñîïîñòàâëÿòü ñ ïî-
ìîùüþ ôóíêöèè ñðàâíåíèÿ è ìåòðè÷åñêîãî çíà÷åíèÿ ñ ïîðîãîâûìè ýëåìåíòàìè,
ýòàëîííûìè îáúåêòàìè, îïðåäåëÿòü ýêñòðåìàëüíóþ ìåðó ñõîäñòâà è îòëè÷èÿ. Ïðè
òàêîì ïîäõîäå âîçìîæíî îñóùåñòâëÿòü ñèíòåç àëãîðèòìîâ ïîèñêà [22] è ðàñïîçíà-
âàòü îáúåêòû ñëîæíîé ïðèðîäû ïðè íàëè÷èè ïîìåõ [23–25].  ñèëó èäåíòèôèêà-
öèè ñîãëàñíî óñëîâèÿì (7), (8) îäíîâðåìåííî âñåõ ýêñòðåìóìîâ ïðåäñòàâëÿåòñÿ èí-
ôîðìàöèÿ î òîïîëîãèè âçàèìíîãî ïîëîæåíèÿ îáúåêòîâ ðàñïîçíàâàíèÿ. Èíôîðìà-
öèÿ âêëþ÷àåò ìíîæåñòâî âñåõ ëîêàëüíûõ ýêñòðåìóìîâ âî âñåõ îêðåñòíîñòÿõ
ëîêàëèçàöèè ïðè âñåõ àïðèîðè çàäàííûõ ðàäèóñàõ â ìíîãîìåðíîì ïðîñòðàíñòâå
ñ ìåòðèêîé. Â êàæäîé îêðåñòíîñòè ýêñòðåìóì èäåíòèôèöèðóåòñÿ ïî èíäåêñàì è ìåò-
ðè÷åñêîìó çíà÷åíèþ. Äîñòèãàåòñÿ ïîëíîòà îáðàçà ðåëüåôà ïðîñòðàíñòâåííîé ïîâåðõ-
íîñòè è ðàñïîëîæåíèÿ íà íåé îáúåêòîâ. Ìîãóò áûòü èäåíòèôèöèðîâàíû íå òîëüêî îò-
äåëüíûå ýêñòðåìóìû, íî è ëþáîå èõ ïîäìíîæåñòâî ñ îïðåäåëÿåìîé èíäåêñàìè êîí-
ôèãóðàöèåé âçàèìíîãî ðàñïîëîæåíèÿ. Íà ýòîé îñíîâå îñóùåñòâèìî ðàñïîçíàâàíèå
öåëåâûõ îáúåêòîâ è èõ ïîäìíîæåñòâ ñ çàäàííûìè ýêñòðåìàëüíûìè ñâîéñòâàìè.
Çàêëþ÷åíèå. Èçëîæåííàÿ ëîêàëèçàöèÿ ýêñòðåìóìà ôóíêöèè n ïåðåìåííûõ
â îêðåñòíîñòè ïðîèçâîëüíîãî (äîñòàòî÷íî ìàëîãî) ðàäèóñà �0 îçíà÷àåò îäíîâðå-
ìåííîå âû÷èñëåíèå òî÷êè ýêñòðåìóìà ñ ãðàíèöåé àáñîëþòíîé ïîãðåøíîñòè �0
â ìåòðèêå Rn . Ïðè îöåíêå óñòîé÷èâîñòè íå îáÿçàòåëüíî âûïîëíÿòü ñïóñê — çíàê
äåéñòâèòåëüíîé ÷àñòè íóëåé õàðàêòåðèñòè÷åñêîé ôóíêöèè îïðåäåëèòñÿ íåïî-
ñðåäñòâåííî â ðåçóëüòàòå ëîêàëèçàöèè. Ýòî, â ÷àñòíîñòè, îòíîñèòñÿ ê ñëó÷àþ ëî-
êàëèçàöèè íóëåé õàðàêòåðèñòè÷åñêîãî ïîëèíîìà ìàòðèöû êîýôôèöèåíòîâ ñèñòå-
ìû ëèíåéíûõ ÎÄÓ. Ñ òî÷íîñòüþ äî ðàçìåðíîñòè ïðåäñòàâëåííûå ñõåìû ðàçëè-
÷àþòñÿ ëèøü ñïîñîáîì ïðåäñòàâëåíèÿ è äèñêðåòèçàöèè äàííûõ íà âõîäå ìåòîäà
â çàâèñèìîñòè îò âèäà çàäà÷è. Ñ èõ ïîìîùüþ ìîæíî îöåíèòü ëîêàëüíî è ãëîáàëü-
íî ýêñòðåìàëüíîå îòêëîíåíèå ðåøåíèÿ äèôôåðåíöèàëüíîé ñèñòåìû îò óñòîé÷èâî-
ãî ñîñòîÿíèÿ. Ñõåìû îòëè÷àþòñÿ ïîñòðîåíèåì íà îñíîâå ñîðòèðîâêè, àâòîìàòè÷-
íîñòüþ ïðîãðàììíîé ëîêàëèçàöèè ýêñòðåìóìîâ ôóíêöèé, à òàêæå ðàçíîñòíûõ ðå-
øåíèé äèôôåðåíöèàëüíûõ óðàâíåíèé, âîçìîæíîñòüþ ïðèáëèæåííîãî ðåøåíèÿ
ñèñòåì àëãåáðàè÷åñêèõ è òðàíñöåíäåíòíûõ óðàâíåíèé. Ïðîãðàììíàÿ ðåàëèçàöèÿ
ñõåì èíâàðèàíòíà îòíîñèòåëüíî ðàçìåðîâ îáëàñòè èññëåäîâàíèÿ è ðàñïàðàëëåëè-
âàåòñÿ ïî ôðàãìåíòàì îáëàñòè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 179
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ð î ì ì ß . Å . Ëîêàëèçàöèÿ è óñòîé÷èâîå âû÷èñëåíèå íóëåé ìíîãî÷ëåíà íà îñíîâå ñîðòèðîâêè. I // Êè-
áåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 1. — Ñ. 165–183.
2. Â è ð ò Í . Àëãîðèòìû è ñòðóêòóðû äàííûõ. — Ì.: Ìèð, 1989. — 360 ñ.
3. Ð î ì ì ß . Å . Ïàðàëëåëüíàÿ ñîðòèðîâêà ñëèÿíèåì ïî ìàòðèöàì ñðàâíåíèé. I // Êèáåðíåòèêà è ñèñ-
òåìíûé àíàëèç. — 1994. — ¹ 5. — Ñ. 3–23.
4. Ð î ì ì ß . Å . Ïàðàëëåëüíàÿ ñîðòèðîâêà ñëèÿíèåì ïî ìàòðèöàì ñðàâíåíèé. II // Òàì æå. — 1995. —
¹ 4. — Ñ. 13–37.
5. Ì à ð ê ó ø å â è ÷ À . È . , Ì à ð ê ó ø å â è ÷ Ë . À . Ââåäåíèå â òåîðèþ àíàëèòè÷åñêèõ ôóíêöèé. —
Ì.: Ïðîñâåùåíèå, 1997. — 320 ñ.
6. Ç à è ê à È . Â . Ðàçðàáîòêà è èññëåäîâàíèå ñõåì îïòèìèçàöèè íà îñíîâå àëãîðèòìîâ ñîðòèðîâêè ñ
ïðèëîæåíèåì ê èäåíòèôèêàöèè ýêñòðåìóìîâ ðåøåíèé äèôôåðåíöèàëüíûõ óðàâíåíèé: Àâòîðåô.
äèñ. ... êàíä. òåõí. íàóê. — Òàãàíðîã: ÒÐÒÓ, 2007. — 19 ñ.
7. Ð î ì ì ß . Å . , Ç à è ê à È .  . , Ë à á è í ö å â à À . À . Áåçóñëîâíàÿ ÷èñëåííàÿ îïòèìèçàöèÿ ïðè
âàðèàöèè ïàðàìåòðîâ. I. — Òàãàíðîã, 2008. — 31 ñ. Äåï. â ÂÈÍÈÒÈ 04.03.2008, ¹ 193-Â2008.
8. Ð î ì ì ß . Å . , Ç à è ê à È .  . , Ë à á è í ö å â à À . À . Áåçóñëîâíàÿ ÷èñëåííàÿ îïòèìèçàöèÿ ïðè
âàðèàöèè ïàðàìåòðîâ. II. — Òàãàíðîã, 2008. — 44 ñ. Äåï. â ÂÈÍÈÒÈ 04.03.2008 ¹ 194-Â2008.
9. Ð î ì ì ß . Å . , Ç à è ê à È . Â . , Ë à á è í ö å â à À . À . Áåçóñëîâíàÿ îïòèìèçàöèÿ íà îñíîâå ñîðòèðîâ-
êè ñ ïðèëîæåíèåì ê êîìïüþòåðíîìó àíàëèçó óñòîé÷èâîñòè ñèñòåì óïðàâëåíèÿ // Èçâ. âóçîâ. Ñåâå-
ðî-Êàâêàç. ðåãèîí. Òåõí. íàóêè. Ñåð. «Óïðàâëåíèå, âû÷èñëèòåëüíàÿ òåõíèêà è èíôîðìàòèêà». —
2008. — ¹ 6. — Ñ. 11–17.
10. Á å ð å ç è í È . Ñ . , Æ è ä ê î â Í . Ï . Ìåòîäû âû÷èñëåíèé. — Ì.: Ôèçìàòãèç, 1962. — Ò.2. — 640 ñ.
11.  à ñ è ë ü å â Ô . Ï . ×èñëåííûå ìåòîäû ðåøåíèÿ ýêñòðåìàëüíûõ çàäà÷. — Ì.: Íàóêà, 1988. — 552 ñ.
12. Ð î ì ì ß . Å . Ëîêàëèçàöèÿ è óñòîé÷èâîå âû÷èñëåíèå íóëåé ìíîãî÷ëåíà íà îñíîâå ñîðòèðîâêè. II //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 2. — Ñ. 161–175.
13. Ð î ì ì ß . Å . , Ç à è ê à È . Â . , Ò þ ø í ÿ ê î â à È . À . Èäåíòèôèêàöèÿ ýêñòðåìóìîâ ôóíêöèé íà îñ-
íîâå ñîðòèðîâêè ñ ïðèëîæåíèåì ê âû÷èñëèòåëüíûì ñõåìàì àëãåáðû, àíàëèçà è ðàñïîçíàâàíèþ
èçîáðàæåíèé // Ïðîáëåìè ïðîãðàìóâàííÿ: Ìàòåðiàëè 5-¿ Ìiæíàð. íàóê.-ïðàêò. êîíô. ç ïðîãðàìóâàí-
íÿ ÓêðÏÐÎÃ’2006. 23–25 òðàâíÿ 2006 ð., Óêðà¿íà, Êè¿â. — 2006. — ¹ 2–3. — Ñ. 708–717.
14. Ð î ì ì ß . Å . , Ç à è ê à È . Â . Ïðîãðàììíàÿ ëîêàëèçàöèÿ ýêñòðåìóìîâ ôóíêöèé è ðàçíîñòíûõ ïðè-
áëèæåíèé ðåøåíèé äèôôåðåíöèàëüíûõ óðàâíåíèé // Èçâ. âóçîâ. Ñåâåðî-Êàâêàç. ðåãèîí. Òåõí.
íàóêè. Ñïåö. âûïóñê «Ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå è êîìïüþòåðíûå òåõíîëîãèè», 2005. —
Ñ. 55–61.
15. Ð î ì ì ß . Å . , Ç à è ê à È . Â . , Ñ î ë î â ü å â à È . À . Ìåòîä ïðîãðàììíîé îïòèìèçàöèè â ïðèëîæå-
íèè ê ìàòåìàòè÷åñêèì ìîäåëÿì ýêîíîìèêè. Ñá. äîêë. IV-é Ìåæäóíàð. íàó÷.-ïðàêò. êîíô. «Ïðîáëå-
ìû ðåãèîíàëüíîãî óïðàâëåíèÿ, ýêîíîìèêè, ïðàâà è èííîâàöèîííûõ ïðîöåññîâ â îáðàçîâàíèè». Ò. 2
(8–10 ñåíòÿáðÿ 2005 ã., ÒÈÓèÝ). — Òàãàíðîã, 2005. — Ñ. 17–26.
16. Ä å ì è ä î â è ÷ Á . Ï . , Ì à ð î í È . À . Îñíîâû âû÷èñëèòåëüíîé ìàòåìàòèêè. — Ì.: Ôèçìàòãèç,
1963. — 660 ñ.
17. Ð î ì ì ß . Å . Ìóëüòèïëèêàòèâíûå êðèòåðèè óñòîé÷èâîñòè íà îñíîâå ðàçíîñòíûõ ðåøåíèé îáûêíî-
âåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 1. —
Ñ. 128–144.
18. Ð î ì ì ß . Å . Ìîäåëèðîâàíèå óñòîé÷èâîñòè ïî Ëÿïóíîâó íà îñíîâå ïðåîáðàçîâàíèé ðàçíîñòíûõ
ñõåì ðåøåíèé îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé // Èçâ. ÐÀÍ. Ìàò. ìîäåëèðîâàíèå. —
2008. — 20, ¹ 12. — Ñ. 105–118.
19. × å ç à ð è Ë . Àñèìïòîòè÷åñêîå ïîâåäåíèå è óñòîé÷èâîñòü ðåøåíèé îáûêíîâåííûõ äèôôåðåíöè-
àëüíûõ óðàâíåíèé. — Ì.: Ìèð, 1964. — 478 ñ.
20. Ê à ò ð è ÷ Ñ . À . Ðàçðàáîòêà è èññëåäîâàíèå ñõåì ïðîãðàììíîãî ìîäåëèðîâàíèÿ óñòîé÷èâîñòè
ðåøåíèé íåëèíåéíûõ äèôôåðåíöèàëüíûõ óðàâíåíèé íà îñíîâå ðàçíîñòíûõ ìåòîäîâ: Àâòîðåô. äèñ.
... êàíä. òåõí. íàóê. — Òàãàíðîã: ÒÐÒÓ, 2006. — 20 ñ.
21. Áó ë à í î â Ñ . à . Ðàçðàáîòêà è èññëåäîâàíèå ìåòîäîâ ïðîãðàììíîãî ìîäåëèðîâàíèÿ óñòîé÷èâîñòè
ñèñòåì ëèíåéíûõ äèôôåðåíöèàëüíûõ óðàâíåíèé íà îñíîâå ìàòðè÷íûõ ìóëüòèïëèêàòèâíûõ ïðåîá-
ðàçîâàíèé ðàçíîñòíûõ ñõåì: Àâòîðåô. äèñ. ... êàíä. òåõí. íàóê. — Òàãàíðîã: ÒÐÒÓ, 2006. — 20 ñ.
22. Á å ë î ê î í î â à Ñ . Ñ . Ðàçðàáîòêà è èññëåäîâàíèå ñõåì äåòåðìèíèðîâàííîãî ïîèñêà íà îñíîâå ñîð-
òèðîâêè ñ ïðèëîæåíèåì ê èäåíòèôèêàöèè îöèôðîâàííûõ îáúåêòîâ ðàçëè÷íûõ òèïîâ: Àâòîðåô. äèñ .
... êàíä. òåõí. íàóê. — Òàãàíðîã: ÒÒÈ ÞÔÓ, 2007. — 18 ñ.
23. Ð þ ì è í Î . Ã . Ðàçðàáîòêà è èññëåäîâàíèå àëãîðèòìîâ ðàñïîçíàâàíèÿ èçîáðàæåíèé íà îñíîâå
îïðåäåëåíèÿ ýêñòðåìàëüíûõ ïðèçíàêîâ çàìêíóòûõ êîíòóðîâ ñ ïîìîùüþ ñîðòèðîâêè: Àâòîðåô. äèñ.
... êàíä. òåõí. íàóê. — Òàãàíðîã: ÒÒÈ ÞÔÓ, 2008. — 16 ñ.
24. Ð î ì ì ß . Å . , Ä î ð ä î ï ó ë î À . È . , Ç à ÿ ð í û é Â . Â . Ïðîãðàììíàÿ ëîêàëèçàöèÿ íóëåé ìíîãî-
÷ëåíîâ ñ ïðèëîæåíèåì ê èäåíòèôèêàöèè îáúåêòîâ ïî äàííûì ãèäðîàêóñòè÷åñêîé ëîêàöèè. —
Òàãàíðîã: Èçä-âî ÒÃÏÈ, 2005. — 217 ñ.
25. Ð î ì ì ß . Å . , Ç à ÿ ð í û é  .  . Êîìïüþòåðíàÿ îáðàáîòêà ñèãíàëîâ ãèäðîàêóñòè÷åñêîé ëîêàöèè è
èäåíòèôèêàöèÿ îáúåêòîâ ðàñòðîâûõ èçîáðàæåíèé // Ñèñòåìû óïðàâëåíèÿ è èíôîðìàöèîííûå òåõíî-
ëîãèè. — 2007. — ¹ 4, Âûï. 2(30). — Ñ. 290–295.
Ïîñòóïèëà 25.06.2009
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
|