Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема
Розглянуто задачу еліпсоїдальної апроксимації суми двох еліпсоїдів, оптимальної за мінімумом багатомірного об’єму. Наведено її розв’язок без використання афінних перетворень і подачі у вигляді задачі умовної оптимізації. Розглянуто розв’язок такої задачі при одночасному виродженні доданих еліпсоїдів...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2011 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84259 |
| 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, № 6. — С. 138-144. — Бібліогр.: 11 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860260567476862976 |
|---|---|
| author | Шолохов, А.В. |
| author_facet | Шолохов, А.В. |
| citation_txt | Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема / А.В. Шолохов // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 138-144. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто задачу еліпсоїдальної апроксимації суми двох еліпсоїдів, оптимальної за мінімумом багатомірного об’єму. Наведено її розв’язок без використання афінних перетворень і подачі у вигляді задачі умовної оптимізації. Розглянуто розв’язок такої задачі при одночасному виродженні доданих еліпсоїдів. Дано геометричну інтерпретацію апроксимації. Наведено результати чисельного моделювання.
The problem of the ellipsoidal approximation of the sum of two ellipsoids optimal in the minimum of multidimensional volume is considered. Its solution without use of affinities and representation as a conditional optimization problem is shown. The case of simultaneous degeneracy of the ellipsoids is considered. A geometrical interpretation of the approximation is given. Results of the numerical modeling are presented.
|
| first_indexed | 2025-12-07T18:55:00Z |
| format | Article |
| fulltext |
ÓÄÊ 519.6
À.Â. ØÎËÎÕÎÂ
ÎÁ ÝËËÈÏÑÎÈÄÀËÜÍÎÉ ÀÏÏÐÎÊÑÈÌÀÖÈÈ ÑÓÌÌÛ ÄÂÓÕ
ÝËËÈÏÑÎÈÄÎÂ ÏÎ ÌÈÍÈÌÓÌÓ ÎÁÚÅÌÀ
Êëþ÷åâûå ñëîâà: ãàðàíòèðîâàííîå îöåíèâàíèå, ìíîæåñòâî äîñòèæèìîñòè,
ýëëèïñîèäàëüíàÿ àïïðîêñèìàöèÿ, ìíîãîìåðíûé îáúåì ýëëèïñîèäà, îïåðàòîð
ðàñòÿæåíèÿ–ñæàòèÿ, âûïóêëàÿ ñîáñòâåííàÿ ôóíêöèÿ.
ÂÂÅÄÅÍÈÅ
Ýëëèïñîèäàëüíàÿ àïïðîêñèìàöèÿ ìíîæåñòâ äîñòèæèìîñòè äèíàìè÷åñêèõ ñèñòåì
ïðè ãàðàíòèðîâàííîì îöåíèâàíèè ÿâëÿåòñÿ ðàñïðîñòðàíåííûì ìåòîäîì [1]. Ïðè
äåéñòâèè íà äèíàìè÷åñêóþ ñèñòåìó íåîïðåäåëåííûõ âîçìóùåíèé, ïðèíèìàþ-
ùèõ çíà÷åíèÿ èç ýëëèïñîèäàëüíîãî ìíîæåñòâà, äëÿ ïîëó÷åíèÿ îöåíîê ñîñòîÿ-
íèÿ ñèñòåìû íåîáõîäèìî àïïðîêñèìèðîâàòü ñóììó äâóõ ýëëèïñîèäàëüíûõ
ìíîæåñòâ. Ïðè ýòîì ðåøàåòñÿ çàäà÷à îïòèìèçàöèè àïïðîêñèìèðóþùåãî ýëëèï-
ñîèäà â ñìûñëå ìèíèìóìà êàêîé-ëèáî åãî õàðàêòåðèñòèêè. Ðàññìîòðèì îïòè-
ìèçàöèþ ïî êðèòåðèþ ìèíèìóìà îáúåìà. Ðåøåíèå äàííîé çàäà÷è äàíî â [1],
îäíàêî äëÿ ýòîãî òðåáóåòñÿ îäíîâðåìåííàÿ äèàãîíàëèçàöèÿ äâóõ êâàäðàòè÷íûõ
ôîðì è ðåøåíèå çàäà÷è óñëîâíîé ìèíèìèçàöèè ñ èñïîëüçîâàíèåì ìíîæèòåëåé
Ëàãðàíæà. Â äàííîé ñòàòüå ïðåäëîæåíî èíîå ðåøåíèå. Òàêæå ðàññìîòðåí ñëó-
÷àé îäíîâðåìåííîé âûðîæäåííîñòè ìàòðèö ñóììèðóåìûõ ýëëèïñîèäîâ ïðè ðå-
øåíèè çàäà÷è ìèíèìèçàöèè. Ïðåäëàãàåìûé ñïîñîá ðåøåíèÿ ïðèìåíèì è äëÿ
ìèíèìèçàöèè ïðîåêöèè àïïðîêñèìèðóþùåãî ýëëèïñîèäà íà çàäàííîå ïîäïðîñ-
òðàíñòâî [2].
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Äàíû äâà ýëëèïñîèäà: E1 è E2 , çàäàííûå â âèäå
E a Q x R x a Q x a jj j j
n
j j j( , ) : ( ) ( ) , ,� � � � � ��{ }T 1 1 1 2 , (1)
ëèáî
E a Q x R x l a l l Q l l R jj j j
n
j j
n( , ) : , , , ,� � � � � � � � � �{ }T 1 2. (2)
Çäåñü a Rj
n� — öåíòð j-ãî ýëëèïñîèäà â n-ìåðíîì åâêëèäîâîì ïðîñòðàíñòâå;
Q Rj
n n�
— ñèììåòðè÷åñêàÿ âåùåñòâåííàÿ ìàòðèöà j-ãî ýëëèïñîèäà, ïîëîæè-
òåëüíî-îïðåäåëåííàÿ â çàïèñè (1) èëè íåîòðèöàòåëüíî-îïðåäåëåííàÿ â çàïèñè (2).
Çàïèøåì óñëîâèå âêëþ÷åíèÿ ñóììû äâóõ ýëëèïñîèäîâ â àïïðîêñèìèðóþùèé
ýëëèïñîèä E� ñ ìàòðèöåé Q� , âîñïîëüçîâàâøèñü àïïàðàòîì îïîðíûõ ôóíêöèé [3]:
l Q l l Q l l Q l l R nT T T
� � � �1 2 . (3)
 ôîðìóëå (3) ñïðàâà çàïèñàíà ñóììà îïîðíûõ ôóíêöèé ýëëèïñîèäîâ E1 è
E2 , à ñëåâà — îïîðíàÿ ôóíêöèÿ àïïðîêñèìèðóþùåãî ýëëèïñîèäà E� . Íà îñíî-
âå (3) îïðåäåëèì ïàðàìåòðè÷åñêîå âûðàæåíèå, ïîçâîëÿþùåå ïîëó÷àòü ìàòðèöó
Q� ýëëèïñîèäà, îïòèìàëüíîãî ïî çàäàííîìó êðèòåðèþ.
Óòâåðæäåíèå 1. Äëÿ ýëëèïñîèäà, çàäàííîãî ìàòðèöåé
Q Q Q� � �
� �� �� � � � � �1 1 2 2 1 2 1
1
2
10 1, , , (4)
âûïîëíÿåòñÿ âêëþ÷åíèå E E E� � �1 2 .
138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
� À.Â. Øîëîõîâ, 2011
Äîêàçàòåëüñòâî. Ïîñêîëüêó ëåâàÿ è ïðàâàÿ ÷àñòè (3) íåîòðèöàòåëüíû, âîç-
âåäåíèå èõ â êâàäðàò òîëüêî óñèëèò íåðàâåíñòâî
l Q l l Q l l Q ll Q l l Q l l R nT T T T T
� � � � �1 1 2 22 . (5)
 (5) ïîäñòàâèì âìåñòî Q� ïðàâóþ ÷àñòü (4) ñ ó÷åòîì � � �2 1 1
11� � �( ) :
� � �1 1 1 1
1
2 1 1 2 21 2l Q l l Q l l Q l l Q ll Q l l Q lT T T T T T� � � � ��( ) . (6)
Ïåðåãðóïïèðîâàâ ÷ëåíû â (6), ïîëó÷èì
( ) ( )� �1 1 1
1
2 1 21 1 2� � � ��l Q l l Q l l Q ll Q lT T T T . (7)
Èç � � �2 1 1
11� � �( ) è óñëîâèÿ � �1 2 0,
èìååì � 1 1 0�
. Óìíîæèì (7) íà
� 1 1� è ïåðåíåñåì â (7) âñå ÷ëåíû âëåâî:
l Q l l Q ll Q l l Q lT T T T
2 1 1 2 1
2
12 1 1� � � � �( ) ( )� �
� � ��
�
�
�
�
� �( )� 1 1 2
2
1 0l Q l l Q lT T .
(8)
Èç (8) ñëåäóåò ñïðàâåäëèâîñòü íåðàâåíñòâà (6) è óòâåðæäåíèÿ 1.
Ñòàâèòñÿ çàäà÷à: ìèíèìèçèðîâàòü ìíîãîìåðíûé îáúåì àïïðîêñèìèðóþùåãî
ýëëèïñîèäà. Ïîêàæåì, ÷òî ýòó çàäà÷ó ìîæíî ïðåäñòàâèòü êàê ìèíèìèçàöèþ
ñòðîãî âûïóêëîé âíèç ñîáñòâåííîé ôóíêöèè f ( )� 1 [3] ñ ïàðàìåòðàìè èç ýëåìåí-
òîâ Q1, Q2 , äèôôåðåíöèðóåìóþ íà âñåì ìíîæåñòâå çíà÷åíèé 1 1� � �� . Äàëåå
èíäåêñ ïðè � 1 îïóñòèì.
ÌÈÍÈÌÈÇÀÖÈß ÀÏÏÐÎÊÑÈÌÈÐÓÞÙÅÃÎ ÝËËÈÏÑÎÈÄÀ
 ÑÌÛÑËÅ ÌÈÍÈÌÓÌÀ ÎÁÚÅÌÀ
Îáúåì ýëëèïñîèäà ïðîïîðöèîíàëåí åãî îïðåäåëèòåëþ [1], ïîýòîìó äîñòàòî÷íî
áóäåò ìèíèìèçèðîâàòü îïðåäåëèòåëü.
Ñëó÷àé 1. Îäèí èç ýëëèïñîèäîâ âûðîæäåí. Òîãäà (4) çàïèøåì ñëåäóþùèì
îáðàçîì:
Q Q I Q Qn� � � � �� �� � �( ) (( ) )1 11
1 1
1
2 , Q1 0
, Q2 0� (9)
Çäåñü I Rn
n n�
— åäèíè÷íàÿ ìàòðèöà; rank Q m2 � , 0� �m n.
Îïðåäåëèòåëü âûðàæåíèÿ (9) ïðåäñòàâèì êàê
| | ( ) | | | ( ) |Q Q I Q Qn n
n� � � � �� �� � �1 11 1
1
2 . (10)
Èç (10) ñëåäóåò, ÷òî äëÿ ìèíèìóìà | |Q� äîñòàòî÷íî ìèíèìèçèðîâàòü âûðà-
æåíèå � � �n n
nI Q Q( ) | ( ) |� � �� �1 1
1
1
2 . Òîãäà çàïèøåì
f I Q Q
n
n n( )
( )
| ( ) |�
�
�
��
�
� � �
1
1
1
1
2 , (11)
df
d
n
I Q Q
d
d
n
n n
n
n
( )
( )
| ( ) |
( )
�
�
�
�
�
�
� �
�
�
�
� � �
�
�
�
�
1
1 1
1
2
1
1
1
| ( ) |� � � �1
1
1
2I Q Qn . (12)
Äëÿ ïðîèçâîäíîé îïðåäåëèòåëÿ â (12) èñïîëüçóåì ñëåäóþùóþ ôîðìóëó [4]:
d Q
d
Q Q
dQ
d
Q
| ( )|
| ( )| ( )
( )
, | ( )|�
� �
�
�
�
�
� �
�
�
��
�
�
�
�
�
� ��tr 1 0 . (13)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 139
Òîãäà
d
d
I Q Q I Q Q I Qn n n
�
� � �| ( ) | | ( ) | (( )� � � � � � �� � �1 1 1
1
1
2 1
1
2 1
tr 1
2
1Q )� . Âûðà-
æåíèå ( )� � � �1
1
1
2I Q Qn ïðåäñòàâèì â âèäå V I Un(( ) )� � �1 � T , ãäå
U V R n n, �
, VU I n
T � — ìàòðèöû ñîáñòâåííûõ âåêòîðîâ [5] â îáùåì ñëó÷àå
íåñèììåòðè÷íîé ìàòðèöû Q Q
1
1
2
� ; � �
R n n — äèàãîíàëüíàÿ ìàòðèöà ñîá-
ñòâåííûõ ÷èñåë ìàòðèöû Q Q
1
1
2
� , rank rankQ Q Q m n
1
1
2 2
� � � � [5], ñðåäè êîòî-
ðûõ m � 0 è n m� � 0. Ñîáñòâåííûå âåêòîðû, ñîîòâåòñòâóþùèå íóëåâûì ñîá-
ñòâåííûì çíà÷åíèÿì, âûáèðàþòñÿ ïðîèçâîëüíî ñ ñîõðàíåíèåì ñâîéñòâ îðòîãî-
íàëüíîñòè VU I n
T � è åäèíè÷íîé íîðìû. Òàê êàê ó ïðÿìîé ìàòðèöû è
îáðàòíîé ê íåé ñîáñòâåííûå âåêòîðû ñîâïàäàþò, ñîáñòâåííûå ÷èñëà ÿâëÿþòñÿ
âçàèìíî îáðàòíûìè [5], à òàêæå tr tr trT TVAU VU A A� � [5], âûðàæåíèå
tr (( ) )� � � � �1
1
1
2
1I Q Qn ìîæíî ïðåäñòàâèòü êàê ( ) ( )� � �� � � �� �
��
�
�� 1 11 1
11
i
i
m
i
n m
.
Ïðèðàâíÿâ (12) ê íóëþ, âûïîëíèâ ïîäñòàíîâêè è ñîêðàùåíèÿ, ïîëó÷èì
( )( ) ( )n m m
ii
m
� � � � �
� �
�
�
�� � �
� �
1 1
1
1
0
1
. (14)
Ïîêàæåì, ÷òî ôóíêöèÿ (11) ñîáñòâåííàÿ è ñòðîãî âûïóêëàÿ [3]. Ïðåäñòàâèì
(11) â âèäå
f I Q Q m n
n
n n
n
n m i
i
m
( )
( )
| |
( )
( ),�
�
�
�
�
�
� ��
�
� �
�
� ��
�
�
1 1
1
1
2
1
� , � �� �1 . (15)
 ïðàâîé ÷àñòè (15) îïðåäåëèòåëü çàïèñàí êàê ïðîèçâåäåíèå ñîáñòâåííûõ
÷èñåë ìàòðèöû �I Q Qn � �
1
1
2 , êîòîðûå ìîæíî ïðåäñòàâèòü â âèäå � �� i , ãäå � i
îáîçíà÷àåò êàê íóëåâûå ñîáñòâåííûå çíà÷åíèÿ, êîòîðûõ n m� , òàê è îòëè÷íûå îò
íóëÿ. Ïîñêîëüêó îïðåäåëèòåëü | |�I Q Qn � �
1
1
2 ìîæíî çàïèñàòü êàê | | |/Q I n1
1 2� ��
� � �Q Q Q Q
1
1 2
2 1
1 2
1
1 2/ / /| | |, òî ÷èñëà � i áóäóò âåùåñòâåííûìè è íåîòðèöàòåëüíûìè
â ñèëó ñèììåòðè÷íîñòè è íåîòðèöàòåëüíîé îïðåäåëåííîñòè ìàòðèöû
Q Q Q
1
1 2
2 1
1 2� �/ / [5].  ýòîì ñëó÷àå ÷èñëèòåëü ôóíêöèè f ( )� ìîæíî ïðåäñòàâèòü
êàê ïîëèíîì ñòåïåíè n m� ñ ïîëîæèòåëüíûìè âåùåñòâåííûìè êîýôôèöèåíòà-
ìè [6]. Çàïèøåì f ( ) ( ) ( )� � � � �� , ãäå � � � � �( ) ( ) ( )� � �
�
�1
1
n
i
i
m
, � � �( ) ( )� � �n m è
� i � 0. Íà ìíîæåñòâå çíà÷åíèé 0� � �� ôóíêöèÿ � �( ) ñòðîãî âûïóêëàÿ, ïîëîæè-
òåëüíàÿ è âîçðàñòàþùàÿ, à ôóíêöèÿ � �( ) ñòðîãî âûïóêëàÿ, ïîëîæèòåëüíàÿ è óáû-
âàþùàÿ. Ïðîèçâåäåíèå ýòèõ ôóíêöèé ïðåäñòàâëÿåò ñîáîé ñòðîãî âûïóêëóþ ïî-
ëîæèòåëüíóþ ôóíêöèþ [7], ïðè ýòîì lim ( ) .
,
f �
� �� ��
� �� � �� �
0
Òîãäà íà
îñíîâàíèè ñâîéñòâ âûïóêëîé ôóíêöèè ïî òåîðåìå Ðîëëÿ î êîðíÿõ ïðîèçâîäíîé
[8] ôóíêöèÿ f ( )� èìååò åäèíñòâåííóþ òî÷êó, â êîòîðîé åå ïðîèçâîäíàÿ îáðàùàåòñÿ
â íóëü è ôóíêöèÿ f ( )� äîñòèãíåò ìèíèìóìà. Ïî ïîëó÷åííûì ðåçóëüòàòàì ñôîð-
ìóëèðóåì òåîðåìó.
Òåîðåìà 1. Ìàòðèöà ýëëèïñîèäà E� , àïïðîêñèìèðóþùåãî ñóììó äâóõ ýë-
ëèïñîèäîâ, îäèí èç êîòîðûõ ìîæåò áûòü âûðîæäåííûì, èìåþùàÿ ìèíèìàëüíûé
îïðåäåëèòåëü, ïîëó÷àåòñÿ èç ðàâåíñòâà (4), ãäå îïòèìàëüíûå çíà÷åíèÿ � 1,* è
�
�
�
2
1
1 1
,*
,*
,*
�
�
îïðåäåëÿþòñÿ åäèíñòâåííûì ïîëîæèòåëüíûì êîðíåì óðàâíåíèÿ (14).
140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Çàìå÷àíèå 1. Ïîêàæåì, ÷òî óðàâíåíèå (14) ñîîòâåòñòâóåò óðàâíåíèþ â ðàáî-
òå [1]. Ðàçäåëèì (14) íà � è âûïîëíèì ïåðåíîñ ñëàãàåìûõ:
( )
( )( )
�
� �
�
� �
�
� �
�
� �
�
�
�1
1
1
1
1 ii
m n m m
, (16)
ñäåëàåì çàìåíó � �� �1 , ðàçäåëèì (16) íà �, ê ëåâîé è ïðàâîé ÷àñòÿì ïðèáà-
âèì ñëàãàåìîå
n m�
�
è â ëåâîé ÷àñòè âíåñåì åãî ïîä çíàê ñóììû. Ïîñëå ïðå-
îáðàçîâàíèé ïîëó÷èì
1
1
0 1 0
1 � � � �
� �
�
�
�
� � � � � �
�
�
ii
n
i i i
n
i m m i n
( )
; , ; , . (17)
Óðàâíåíèå (17) ïðè çàìåíå îáîçíà÷åíèé ïàðàìåòðîâ ñîâïàäàåò ñ óðàâíåíèåì
äëÿ ïîëó÷åíèÿ îïòèìàëüíîãî ýëëèïñîèäà â ðàáîòå [1].
Ïîêàæåì, ÷òî � i , i n� �1, , , èç óðàâíåíèÿ (16) — êîðíè óðàâíåíèÿ
| |Q Q2 1 0� �� .
Ðåøåíèå ýòîãî óðàâíåíèÿ ïðèâîäèò ê àíàëîãè÷íîìó óðàâíåíèþ â ðàáîòå [1] .
Ïîñêîëüêó îïðåäåëèòåëü ïðîèçâåäåíèÿ ìàòðèö ðàâåí ïðîèçâåäåíèþ îïðåäåëèòå-
ëåé ìàòðèö è èç óñëîâèÿ | |Q1 0
, ìîæíî çàïèñàòü | | | | | |Q Q Q Q Q I n2 1 1 1
1
2 0� � � ��� �
è äàëåå | |Q Q I n1
1
2 0� � �� . Îòñþäà ñëåäóåò èäåíòè÷íîñòü óêàçàííûõ óðàâíåíèé.
Çàìå÷àíèå 2. Çàäà÷à èìååò ãåîìåòðè÷åñêîå òîëêîâàíèå. Ïðåäñòàâèì (4) â âèäå
Q Q I Q Q Q Qn� � �
�
�
�
�
�
�
�� ��
�
1 1
1
2 1
1
1
1
1( )
. (18)
Çäåñü � — êâàäðàòíûé êîðåíü èç ìàòðèöû (ñì. [5]).
Èç (18) ñëåäóåò, ÷òî îäèí èç ýëëèïñîèäîâ (â äàííîì ñëó÷àå E2) ìîæåò áûòü
âûðîæäåííûì. Âûðàæåíèå â ñêîáêàõ îáîçíà÷èì è çàïèøåì â âèäå
P G I Q Q Q I G I B G G G
B n n m� � �
�
� � �� � � �
2
1
1 1
1
2 1
1 1( )
( )
( )( )
�
2 T T . (19)
Çäåñü G Q S� �
1
1
2 2� ; � 2 �
R m m , m Q� rank 2 — äèàãîíàëüíàÿ ìàòðèöà íå-
íóëåâûõ ñîáñòâåííûõ ÷èñåë ìàòðèöû Q2 ; S R n m
2 �
— ìàòðèöà ñîáñòâåííûõ
âåêòîðîâ ìàòðèöû Q2
, ñîîòâåòñòâóþùèõ íåíóëåâûì ñîáñòâåííûì ÷èñëàì, ïðè
ýòîì S S Q2 2 2 2 2� �( )T � ; I Rm
m m�
— åäèíè÷íàÿ ìàòðèöà; B R m m�
�2
— äèàãîíàëüíàÿ ìàòðèöà ñ äèàãîíàëüíûìè ýëåìåíòàìè � i
�
2 1 , i m�1, ,� .
Ïðàâàÿ ÷àñòü (19) — îïåðàòîð ðàñòÿæåíèÿ–ñæàòèÿ [9] ñ êîýôôèöèåíòàìè � i
�1,
i m�1, ,� , ïî m íàïðàâëåíèÿì, îïðåäåëÿåìûì ñòîëáöàìè ìàòðèöû G [10].
Ñîãëàñíî (19) ( ) ( )( )� � � � �� � �1 1 1GG G I B G G Gm
T 2 T T . Ïðåäñòàâèì B �2 êàê
ôóíêöèþ îò �.
Ïðåîáðàçóåì
1
1
1
1
1
( ) ( )
( ) ( )
� ��
�
�
� � �
� �GG GG G G G G G I Bm
T T T T 2
�( )G G GT T1 è ïðèìåì
B I G Gm
� � �
�
2 1
1( )�
T .
(20)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 141
Îïðåäåëèòåëü ìàòðèöû (18) ñ ó÷åòîì (19) è ñâîéñòâà îïåðàòîðà ðàñòÿæåíèÿ– ñæàòèÿ
ïî m íàïðàâëåíèÿì | ( )|P G
B i
i
m
� � �
�
�2
2
1
� [10] çàïèøåì êàê | | | |Q Qn
i
i
m
� � �
�
�� � 2
1
1 .
Îòñþäà ñëåäóåò, ÷òî äëÿ ìèíèìóìà | |Q� íåîáõîäèì ìèíèìóì � �n
i
i
m
�
�
� 2
1
. Òîãäà
f I G G I G Gn
m
n
m m( )
( ) ( )
| ( ) |� �
�
�
�
�� �
�
�
�
� �
1
1 1
1T T . (21)
Ïðîäèôôåðåíöèðóåì (21) ïî �:
df
d
d
d
I G G
n
m m
n
m
( )
( )
| ( ) |
( )
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
�
�
1
1
1
T
�
�
�
�
�
�
�
� �
d
d
I G Gm
�
�| ( ) | .1 T
(22)
Çäåñü
d
d
I G G I G G I G Gm m m
�
� � �| ( ) | | ( ) | (( ) )� � � � � � � �1 1 1 1T T Ttr (ñì. [4]).
Ïðèðàâíÿåì (22) ê íóëþ è ñîêðàòèì îáùèå íå ðàâíûå íóëþ ìíîæèòåëè:
( ) ( ) (( ) )n m n I G Gm� � � � � � ��� � � �1 1 01tr T . (23)
Ïðåäñòàâèì ( ) ( ) (( ) )� � �� � � � � � � �1 1 1I G G I S S S I Sm m P P P P m P
T T T� � .
Çäåñü � P — äèàãîíàëüíàÿ ìàòðèöà ñîáñòâåííûõ ÷èñåë � P i, , i m�1, .., , ìàòðèöû
G GT ; S RP
m m�
— îðòîãîíàëüíàÿ ìàòðèöà S S I
P P m
T � ñîáñòâåííûõ âåêòîðîâ
ìàòðèöû G GT . Ïîñêîëüêó ñîáñòâåííûå ÷èñëà îáðàòíîé ìàòðèöû ÿâëÿþòñÿ îá-
ðàòíûìè ñîáñòâåííûì ÷èñëàì èñõîäíîé ìàòðèöû, ðàâåíñòâî (23) ìîæíî ïåðåïè-
ñàòü â ñëåäóþùåì âèäå:
( )( ) ( )
,
n m m
P ii
m
� � � � �
�
�
�
�� � �
� �
1 1
1
0
1
.
Äîêàæåì, ÷òî � P i, , i m�1, .., , ðàâíû � i , i m�1, .., , èç óðàâíåíèÿ (14), êîòîðûå
ÿâëÿþòñÿ íåíóëåâûìè êîðíÿìè óðàâíåíèÿ | |Q Q2 1 0� �� . Ïðåäñòàâèì | |Q Q2 1� ��
� ��
�
�
�
�
� �� �Q Q Q Q I Qn1 1
1
2 1
1
1 0� è äàëåå íà îñíîâå ñâîéñòâ îïðåäåëèòåëÿ
ïðîèçâåäåíèÿ ìàòðèö [5] çàïèøåì Q Q Q Q I Qn1 1
1
2 1
1
1 0| | | |� � � �� . Ïîñêîëü-
êó ìàòðèöà Q1 ïîëîæèòåëüíî-îïðåäåëåííàÿ ïî óñëîâèþ, òî | |Q1 0
. Òîãäà
Q Q Q I n1
1
2 1
1 0� � � �� . Òàê êàê Q Q Q GG
1
1
2 1
1� � � T è íåíóëåâûå ñîáñòâåí-
íûå ÷èñëà ïðîèçâåäåíèé ìàòðèö G GT è GG T ñîâïàäàþò [5], ðåøåíèåì óðàâíå-
íèÿ Q Q Q I n1
1
2 1
1 0� � � �� áóäóò � i i i m� � �0 1, ; � i m i n� � �0, , ÷òî è òðå-
áîâàëîñü äîêàçàòü.
Ñëó÷àé 2. Îáà ñóììèðóåìûõ ýëëèïñîèäà âûðîæäåíû. Îäèí èç ýëëèïñîèäîâ,
íàïðèìåð ìíîæåñòâà âîçìóùåíèé äâèæåíèÿ äèíàìè÷åñêîé ñèñòåìû, èçíà÷àëüíî ìî-
æåò áûòü âûðîæäåííûì [11]. Îäíàêî íåëüçÿ èñêëþ÷èòü ñèòóàöèè, êîãäà è ýëëèïñî-
èä ìíîæåñòâà âîçìîæíûõ ñîñòîÿíèé ñèñòåìû, ââèäó ïåðèîäè÷åñêîãî ïîëó÷åíèÿ äî-
ïîëíèòåëüíîé èíôîðìàöèè èëè âñëåäñòâèå ñâîéñòâ äèíàìèêè ñèñòåìû, ìîæåò
âûðîäèòüñÿ. Âûðîæäåíèå îáîèõ ýëëèïñîèäîâ ìîæåò áûòü êàê â îáùåì, òàê è â ðàç-
ëè÷íûõ ïîäïðîñòðàíñòâàõ.  ïåðâîì âàðèàíòå ðàçìåðíîñòü îáúåìà ïîíèæàåòñÿ.
142 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Ïóñòü rank Q p n1 � � ñ íåíóëåâûìè ñîáñòâåííûìè ÷èñëàìè �1,i , i p� �1, , ,
è rank Q m n2 � � . Ïðåäñòàâèì Q S D S1 1 1 1
� T ; S R n n
1 �
— íåâûðîæäåííàÿ ìàòðè-
öà òàêàÿ, ÷òî | | ,S S i
i
p
1 1 1
1
T �
�
� � . Ñòîëáöû ìàòðèöû S1 — ñîáñòâåííûå âåêòîðû ìàò-
ðèöû Q1. Òå èç íèõ, êîòîðûå ñîîòâåòñòâóþò íåíóëåâûì ñîáñòâåííûì çíà÷åíèÿì
�1,i ìàòðèöû Q1, èìåþò íîðìó, ðàâíóþ �1,i . Ñîáñòâåííûå âåêòîðû, ñîîòâå-
òñòâóþùèå íóëåâûì ñîáñòâåííûì çíà÷åíèÿì ìàòðèöû Q1, èìåþò åäèíè÷íóþ
íîðìó è îðòîãîíàëüíû îñòàëüíûì âåêòîðàì-ñòîëáöàì ìàòðèöû S1. Ìàòðèöà S
1
1�
ìîæåò áûòü ïîëó÷åíà èç ìàòðèöû S1 äåëåíèåì ñîîòâåòñòâóþùèõ j-õ ñòîëáöîâ íà
�1,i ( )j i� è ïîñëåäóþùèì òðàíñïîíèðîâàíèåì; D R n n
1 �
— äèàãîíàëüíàÿ
ìàòðèöà, äèàãîíàëü êîòîðîé ñîñòîèò èç p åäèíèö, ñîîòâåòñòâóþùèõ íåíóëåâûì
ñîáñòâåííûì çíà÷åíèÿì ìàòðèöû Q1, è n p� íóëåé. Òàê êàê ïðåîáðàçîâàíèå íåâû-
ðîæäåííîå, òî rank rankTS Q S Q m n
1
1
2 1 2
� � � � � . Çàïèøåì (4) ñëåäóþùèì îáðàçîì:
Q S D S Q S S D D S S� �
�
� � �
�
� �
�
�
�
�
�
�
1
1
1
11 1 1 2 1 2 1 2 2 1
(( ) ) (( ) )T T T .
Çäåñü S S S S I Rn
n n
2 2 2 2
T T� � �
— íåâûðîæäåííîå îðòîãîíàëüíîå ïðåîáðàçî-
âàíèå, ïðèâîäÿùåå ìàòðèöó S Q S
1
1
2 1
� �T ê äèàãîíàëüíîìó âèäó D2 , ò.å.
S D S S Q S2 2 2 1
1
2 1
T T� � � ; D R n n
2 �
— äèàãîíàëüíàÿ ìàòðèöà, äèàãîíàëü êîòîðîé
ñîñòîèò èç m ïîëîæèòåëüíûõ ÷èñåë, ñîîòâåòñòâóþùèõ íåíóëåâûì ñîáñòâåí-
íûì çíà÷åíèÿì ìàòðèöû Q2 , è n m� íóëåé. Åñëè ìàòðèöà ( )� � �1 1 2D D âû-
ðîæäåííàÿ, ò.å. íóëåâûå äèàãîíàëüíûå ýëåìåíòû ìàòðèö D1 è D2 ñîâïàäà-
þò, òî ïåðåõîäèì ê ïîíèæåííîé ðàçìåðíîñòè ìàòðèöû Q R k k
� �
, k n� , âû-
÷åðêèâàíèåì ñîâïàäàþùèõ íóëåâûõ ñòðîê è ñòîëáöîâ. Óðàâíåíèå (11)
çàïèøåì êàê f D Dk k( ) ( ) | ( )
~ ~
|� � � �� � � ��1 1 1 2 , ãäå
~
,
~
D D R k k
1 2 �
— ìàòðèöû,
ïîëó÷åííûå èç D1, D2 âû÷åðêèâàíèåì ñîâïàäàþùèõ íóëåâûõ ñòðîê è ñòîë-
áöîâ. Àíàëîãè÷íî (14) ïîëó÷èì
� � �
� �
�
�
�
�
�
�
�
�
�
�
� ��
��k
i ii p
k
i
p
� �
� � �
( ) ~ ~
, ,
1
1
1
1
0
2 211
.
Çäåñü
~
,�2 i äëÿ i p�1, .. , — äèàãîíàëüíûå ýëåìåíòû ìàòðèöû
~
D2 , â òîì ÷èñëå
è íóëåâûå, ñîîòâåòñòâóþùèå åäèíèöàì ãëàâíîé äèàãîíàëè ìàòðèöû
~
D1;
~
,�2 i
äëÿ i p k� �1, ..., — íåíóëåâûå äèàãîíàëüíûå ýëåìåíòû ìàòðèöû
~
D2 , êîòî-
ðûì ñîîòâåòñòâóþò íóëåâûå äèàãîíàëüíûå ýëåìåíòû ìàòðèöû
~
D1.
Ðåøåíèå çàäà÷è àïïðîêñèìàöèè â ñëó÷àå 2 òðåáóåò áîëüøå àðèôìåòè÷åñêèõ
îïåðàöèé. Ïðè îãðàíè÷åííûõ âû÷èñëèòåëüíûõ ðåñóðñàõ è âîçìîæíîñòè âûðîæ-
äåíèÿ îáîèõ ýëëèïñîèäîâ ìîæíî ðåêîìåíäîâàòü ïðèìåíÿòü àëãîðèòì ñîãëàñíî
ñëó÷àþ 1 äî òåõ ïîð, ïîêà áóäåò âûðîæäåí òîëüêî îäèí ýëëèïñîèä. Ïåðåéòè îò
àëãîðèòìà 1 ê àëãîðèòìó 2 ìîæíî, íàïðèìåð, ïî îãðàíè÷åíèþ íà
îáóñëîâëåííîñòü ìàòðèöû Q1.
Ñëó÷àé 3. Äëÿ ìèíèìàëüíîé àïïðîêñèìàöèè ïðîåêöèè ñóììû äâóõ ýëëèï-
ñîèäîâ íà çàäàííîå ïîäïðîñòðàíñòâî [2] âûðàæåíèå (4) çàïèøåì ñëåäóþùèì îá-
ðàçîì:
V Q V V Q V V Q V V R V V I l nn l
l
T T T T
� � � � � �
� �1 1 2 2 , , , .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 143
Çäåñü V — ìàòðèöà èç îðòîãîíàëü-
íûõ âåêòîð-ñòîëáöîâ ñ åäèíè÷íîé
íîðìîé, îïðåäåëÿþùèõ â çàäàííîé
ñèñòåìå êîîðäèíàò òðåáóåìîå ïîä-
ïðîñòðàíñòâî. Ðåøåíèå ýòîé çàäà÷è
àíàëîãè÷íî ïðåäûäóùèì àëãîðèòìàì.
Ïðè ÷èñëåííîì ìîäåëðîâàíèè
â MATLAB áûëè ïðèíÿòû ñëåäóþùèå
çíà÷åíèÿ: Q , ;1 0 625 1� diag { },
Q ; ,2 1 0 25� diag { } — äèàãîíàëüíûå
ìàòðèöû. Ïîëó÷åíà ìàòðèöà Q� �
� diag { }1958 2 675, ; , îïòèìàëüíîãî ïî
ìèíèìóìó îáúåìà ýëëèïñîèäà.
Íà ðèñ. 1 ïîêàçàíû ñóììèðóåìûå
ýëëèïñîèäû E1, E2 , èõ ãåîìåòðè÷å-
ñêàÿ ñóììà è àïïðîêñèìèðóþùèé ýëëèïñîèä E� .
ÇÀÊËÞ×ÅÍÈÅ
Ðåøåíèå çàäà÷è îïòèìàëüíîé ýëëèïñîèäàëüíîé àïïðîêñèìàöèè ïî êðèòåðèþ
ìèíèìóìà îáúåìà ñóììû äâóõ ýëëèïñîèäîâ ïîëó÷åíî áîëåå ïðîñòûì ñïîñî-
áîì, ÷åì â ðàáîòå [1]. Êðîìå òîãî, ðåøåíèå ýòîé çàäà÷è, êîãäà îáà ñóììèðóå-
ìûõ ýëëèïñîèäà âûðîæäåíû, ìîæåò èñïîëüçîâàòüñÿ â ïðàêòè÷åñêèõ ñëó÷àÿõ,
êîãäà èçâåñòíîå ðåøåíèå (ñì. [1]) ïðèìåíèòü íåâîçìîæíî.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. × å ð í î ó ñ ü ê î Ô . Ë . Îöåíèâàíèå ôàçîâîãî ñîñòîÿíèÿ äèíàìè÷åñêèõ ñèñòåì. Ìåòîä
ýëëèïñîèäîâ. — Ì.: Íàóêà, 1988. — 320 ñ.
2. × å ð í î ó ñ ü ê î Ô . Ë . Îá îïòèìàëüíîì ýëëèïñîèäàëüíîì îöåíèâàíèè äëÿ äèíàìè÷åñêèõ
ñèñòåì, ïîäâåðæåííûõ íåîïðåäåëåííûì âîçìóùåíèÿì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2002. — ¹ 2. — Ñ. 85–95.
3. Ï ø å í è ÷ í û é Á . Í . Âûïóêëûé àíàëèç è ýêñòðåìàëüíûå çàäà÷è. — Ì.: Íàóêà, 1980. —
320 ñ.
4. Ì à ã í ó ñ ß . Ð . , Í å é ä å ê ê å ð Õ . Ìàòðè÷íîå äèôôåðåíöèàëüíîå èñ÷èñëåíèå ñ ïðèëîæå-
íèÿìè ê ñòàòèñòèêå è ýêîíîìåòðèêå. — Ì.: Ôèçìàòëèò, 2002. — 496 ñ.
5. Õ î ð í Ð . , Ä æ î í ñ î í × . Ìàòðè÷íûé àíàëèç. — Ì.: Ìèð, 1989. — 655 ñ.
6. Â è í á å ð ã Ý . Á . Êóðñ àëãåáðû. — Ì.: Ôàêòîðèàë Ïðåññ, 2001. — 544 ñ.
7.  è ð ÷ å í ê î Í . À . , Ë ÿ ø ê î È . È . , Ø â å ö î â Ê . È . Ãðàôèêè ôóíêöèé: Ñïðàâî÷íèê. —
Ê.: Íàóê. äóìêà, 1981. — 320 ñ.
8. Ø è ë î â à . Å . Ìàòåìàòè÷åñêèé àíàëèç (ôóíêöèè îäíîãî ïåðåìåííîãî). — Ì.: Íàóêà, 1969.
— ×. 1–2. — 528 ñ.
9. Ø î ð Í . Ç . Ìåòîä îòñå÷åíèÿ ñ ðàñòÿæåíèåì ïðîñòðàíñòâà äëÿ ðåøåíèÿ çàäà÷ âûïóêëîãî
ïðîãðàììèðîâàíèÿ // Êèáåðíåòèêà. — 1977. — ¹ 1. — Ñ. 94–95.
10. Á à ê à í Ã . Ì . , Ê ó ñ ñ ó ë ü Í . Í . , Ø å ë å ñ ò î â À . Þ . Ðàçìûòàÿ ýëëèïñîèäàëüíàÿ èäåí-
òèôèêàöèÿ ïàðàìåòðîâ ìíîãîìåðíûõ ëèíåéíûõ ñòàòè÷åñêèõ îáúåêòîâ // Àâòîìàòèêà. — 1993.
— ¹ 5. — Ñ. 50–60.
11. Á à ê à í Ã . Ì . , Ø î ë î õ î â À . Â . Ê îïðåäåëåíèþ ìíîæåñòâà äîñòèæèìîñòè ëèíåéíîé
óïðàâëÿåìîé ñèñòåìû // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2005. — ¹ 4. — Ñ. 15–24.
Ïîñòóïèëà 10.09.2010
144 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Ðèñ. 1
|
| id | nasplib_isofts_kiev_ua-123456789-84259 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:55:00Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шолохов, А.В. 2015-07-04T14:52:20Z 2015-07-04T14:52:20Z 2011 Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема / А.В. Шолохов // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 138-144. — Бібліогр.: 11 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84259 519.6 Розглянуто задачу еліпсоїдальної апроксимації суми двох еліпсоїдів, оптимальної за мінімумом багатомірного об’єму. Наведено її розв’язок без використання афінних перетворень і подачі у вигляді задачі умовної оптимізації. Розглянуто розв’язок такої задачі при одночасному виродженні доданих еліпсоїдів. Дано геометричну інтерпретацію апроксимації. Наведено результати чисельного моделювання. The problem of the ellipsoidal approximation of the sum of two ellipsoids optimal in the minimum of multidimensional volume is considered. Its solution without use of affinities and representation as a conditional optimization problem is shown. The case of simultaneous degeneracy of the ellipsoids is considered. A geometrical interpretation of the approximation is given. Results of the numerical modeling are presented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема Про еліпсоїдальну апроксимацію суми двох еліпсоїдів за мінімумом об’єму Ellipsoidal approximation of the sum of two ellipsoids by the minimum volume Article published earlier |
| spellingShingle | Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема Шолохов, А.В. Системный анализ |
| title | Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема |
| title_alt | Про еліпсоїдальну апроксимацію суми двох еліпсоїдів за мінімумом об’єму Ellipsoidal approximation of the sum of two ellipsoids by the minimum volume |
| title_full | Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема |
| title_fullStr | Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема |
| title_full_unstemmed | Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема |
| title_short | Об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема |
| title_sort | об эллипсоидальной аппроксимации суммы двух эллипсоидов по минимуму объема |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84259 |
| work_keys_str_mv | AT šolohovav obéllipsoidalʹnoiapproksimaciisummydvuhéllipsoidovpominimumuobʺema AT šolohovav proelípsoídalʹnuaproksimacíûsumidvohelípsoídívzamínímumomobêmu AT šolohovav ellipsoidalapproximationofthesumoftwoellipsoidsbytheminimumvolume |