close

Вход

Забыли?

вход по аккаунту

?

2001-0109-0-01

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Санкт-Петербургский
государственный университет аэрокосмического приборостроения
?. ?. ????????
??????
????????????
??????????????
????? ??????
Санкт-Петербург
2001
??? 681.3.06
??? 32.965
?66
???????? ?. ?.
?66 ?????? ???????????? ??????????????: ????? ?????? / ???????.
???., 2001. 169 ?.: ??.
??????????? ???????? ??????? ? ??????????? ???????????????
????????? ?????? ???????????, ????????? ??????? ???????????????
????????????????, ???????????? ??? ?????????????? ???????? ? ??????. ?????? ? ?????????????? ??????????? ????? ??????? ????????????? ?????????? ??????? ? ?????????? ??????????? ??? ??????? ????????? ?????.
????? ?????? ???????????? ????????? ????????????? 2203 "???????
????????????? ??????????????" ? ?????? ?????????? "??????????? ?
????". ??? ????????? ????????? ???????????? ???????? ??????? ????????? ? ????????? ??????? ???????????? ?????, ??????????? ??????
????????? ???????, ?????????? ?????? ?, ???????, ??????????? ?????????? ??????? ?? ???.
??????????:
????? ????????????? ???? ?? "????????";
???????? ??????????? ???? ?????? ?. ?. ???????
??????????
???????????-???????????? ??????? ????????????
? ???????? ?????? ??????
© ?????-?????????????
??????????????? ???????????
???????????????? ???????????????, 2001
©
2
?. ?. ????????, 2001
???????????
????? ??????? ???????? ????????? ??????????????, ?. ?. ?????????????? ????????? ?? ??? ???? ???????. ????? ??????????, ???????????? ??????? ????? ???????????? ?????: ??????? ????? ?????? ???????, ??????????? ????????????????.
? ????? ?p???? ?p?????? ?p?????p?????? ??????????? ?????? ??????
??????? ? ???, ????? ???p??? ???????? ?p?????????????? ??p???? ??????????? ??????????? ???????. ?p????, ??? ?p?????, ?? ?????????????? ?????? ??????? ???????? ??p?????????? ??p?????, ?????? ??
????p?? ???-?? ?????, ? ???-?? ???? ?p????. ????????? ??????? ? ???,
??? ?????? ??p???? ????? ????????, ? ? ???????????? ??????? ?????
??????????? ?????? ???????.
??? ?? ?????? p??p???????? ????????? ????????? ???????? ??
??p????p??????, ???p??????? ????p?? ???????? ???p?????????? ???????? ??????? ? ???????? ??? ?????????? ?? ????????. ?????
?p?????????? ???????? ??????????? ????? ?????????? ??p????p????????
? ????????????? ??p????????, ?. ?. ?p???????? ???? ?? ????p?????.
???p???p, ?p???????? ?? ?????????? ????? ??????????? (??? ?????? ????????) ????? ???? ?????????? ?? ???? ?????????? ??????? ???????.
?????? ??????????? ??????? ??????? ?????????? ?? ?????? ??????????? ? ????????????? ???????????, ? ?????? ???, ??? ?????????
?????? ???????? ??????????? ???????. ??? ?????? ????? ??????, ????????? ? ??????????????? ???????. ? ????? ????????????? ????? ????? ??????? ????????, ?????? ??????? ??????????? ????? ?????????????????? ????? ? ?????? ????????? ????????, ???????? ???????????? ???
????? ?????? ???????????? ? ??., ?????? ??????????? ???????????? (?
????????, ?????? ????????? ???????????????? (??)) ??? ???????????? ?? ???????? ???????, ?? ???????????????? ????????. ????????? ??????? ??????????? ????? ????????????? ?? ????????? ????????????? ?????????: ???????????? ?????? ??????? ? ??????????? ?????????, ???????????? ?????????? ?? ?????????? ???????, ??????????? ???????? ???????????? ? ?. ?. ? ???????? ???????? ?????????????
3
?i ?? ?????????? ????? ????????? ??????? ???? ??????? i-?? ???????,
??????????? ???????????? ??? ????????? ? ?. ?. ? ??????? ?? ?????
???? ??????? ?????? ???????????? ?????????? ?????? ???????? ?????, ??????????? ??????? ???????, ?????????? ?????? ????????? ????? ? ??.
?????? ????????????? ???????????????? ????? ??????????? ???
??????? ?????, ??? ?????????? ????????????? ??????? ???????????? ?
???????????? ??? ?? ???????. ????? ???????? ????? ???????? ??????
?????? ??????? ??????? ?????? ???????????? ??? ??????? ?????????
?? ?????? ???????????? ?????????? ???????, ????????????? ????????? ????? ???????? ?? ????????????? (????????, ????? ???????? ??????? ??????? ? ???????? ??????), ?? ????????? ???????????? ?? ???????, ???????????? ?????????? ?????? ????????.
?????? ???????????? ???????????? ???????? ???????? ?????? ??????????, ??????? ??????????? (?????????? ? ???????????? ????????????????) ??? ???????????? ??????? (????????????? ??????). ?????
?????????? ????????? ??????? ? ???????? ????????????????, ??????????? ?????? ?????? ???.
???????? ??????????? ????????????? ???????????? ????????? ?????????? ????, ?????????, ??????? ?? ?????????? ?????????? ??????? ??
???????????? ? ????????. ??????????? ??????? ??????? ???? ????? ?????????? ?????? ?????????? ????????.
?????? ??????????? ???????????????? ????????? ??? ????? ?????,
??? ?????????? ??????????? (????????????) ? ?????? ????????????????? ?????? (? ??????????, ????????), ??? ??????????? ????????? ??????? ?? ???????, ??????????? ????????? ?????????? ?????????? (?????? ????????????) ? ?????? ??.
????? ?????? ???????????? ? ?????? ????????? ????????????? 2203
«??????? ??????????????????? ??????????????», ?????????? ???????????????? ????????? ???????. ? ???? ????? ????????? ??????? ???
???????? ???????? ??? ?????: ?? ?????????? ?????? ?? ???????????
??????????. ????? ??????? ????????? ????????? ?????. ?????? ? ?????????????? ?????????, ??????? ???????? ???????? ??????? ? ??????????????? ????????? ?????? ???????????, ????????? ??????? ??????????????? ????????????????, ???????????? ??? ??????????????
???????? ? ??????, ???????? ??????? ????? ???????? ?????????????
?????????? ??????????????? ????????.
4
1. ?????? ???????????? ?????????????? ? ????
???? ???????????, ?????????? ? ???????????, ? ?? ? ????? ?????????? ????????? ????????????? ??????, ??????? ??????????? ??????????? ??????????????.
??????? ?????????????? ????? ??????????? ? ???? ????? ?????
(p??. 1), ?? ??????? ?????, ??? ?? ??????????? ??????????? ? ???????
? ??p??p?????p??????? ?? ??? ???, ???? ?p???? ?? ????? ?????????p???
??p????????? ? ????? (?p????????? ??) ? ?? ?????? ? ??????p?? ?????? ???????????. ????? ???????? ??? ?p???? ??????????? ? ?p??????
?p?????p??????.
?????? ?p????? ??????? ? ?????? ????????? ??????????? ????,
?p?????? ???????? ??. ??? ???????? ??????????????? ???? ? ??????,
??? ???????, ???????? ? ?????????????? ?????????? ??????. ? ???????? ?p??p?????? ?????p??? ????? ?p????????? ???????????????
1
1 ? ??????
2
2 ? ????? ????????? ?????????? ??
3 ? ???????????? ??
3
4 ? ??????????? ??????
4
5 ? ??????????????? ??????
5
6 ? ?????? ?????????????
6
?
7
?
8
9
7 ? ????????????? ??????????????
8 ? ?????
9 ? ??????????
???. 1
5
?????p???? ???????, ?????????? ???? ??????? ?p??????? p??????.
???????, ??? ??p??? ? ???????????? ?????p??? ?????????? ?????????
????????????? ?????????? (?p????? ?????????, ?p??? ????????????).
????? ??p??p????? ??p??????????? ??p???? ???????????? ???????
(??), ? ????p?? ?????p??????? ?p???????? ? ???????? ??????????? ??
(??????? p????????????????). ???????, ??? ?????? ??????? ? ?p??????
?p?????p?????? ????? ??pp????p??????? ?? ??? ??p, ???? ?? ??????????? ? ????????????? ???????. ?p? p??p?????? ?? ????? ??p?????? ? ?????????????. ? ?????????, ???? ????? ????????? ????????? ????????? ??????????? ??, ????p?? ?p??????? ?????????p???. ???, ???p???p,
????? ?????????? ??p???? ??p?? ?? ??????????? ?????? ?????, ?????????? ?????????? ???????? ????? ??????? ???????? ?p????????
???p???? ?p? ??? ?p?????p??????.
1.1. ??????? ? ??p????p??? ? ??p????p??????? ???????
?p????? ????p?????? ?p?????p?????? ???????? ? ????:
? ??p????p??? ??????, ??????? ??????? ? ??????????? ??????? ????? ??????????? ?? ? ??????? ?? ????? ????? ?????; ????? ????????? ?????????, ?????, ? ????? ? ??????????????? ?? ??????????????
?????? ? ?????? ?????????? ?p?????? ????????;
? ??p????p??????? ??????, ????p?? ??????????? ? ??p???????? ???????? ???????? ??p????p?? (???????? ?? ??p????p?) ????????? ? p?????
???????? ??p????p?, ? ??????? p???????????????? ?? ????????
??p????p?????? ??.
?????????? ?p??????? p?????? ??????????? ? ??????????????
?p??????? ?p?????p ???????, ?? ?????? ????p?? ?p????????? p??????
? ?????? ?? ???p????????? ?p?????? ??? ??p??p?????p?????? (???????? ????????? ?p??????? ???????? ? ?????? ??).
?p???? ??????????? ?? ??????? ??p????p??? ? ??p????p??????? ???????????, ???????????? ? ????. ????? ????????, ??? ??? p??????
?????? ???????????? ??????? ???? ????? ?????? ???????? ???????? ??,
??????? ????? ???? ?????????? ???????? ? ?????????? p?????? ??????
???????????????? ???????. ? ?????? ???p???, ?????? ??p????p????????
??????? ????? ???? p????? ?????? ?p? ???????? ??p????p? ??. ?????
?? ????????????: ??p????p??? ? ??p????p??????? ?????? ??????
p??????p??????? ? ?????? ?????????????? ???????? ? ? ??????????
????????? ???????????? ?p?????p??????.
6
?????? ??p????p??? ??????????? ? ?????? ?? p??????
?????? ?????????????? ???????? ?????????? ????????? ? ??????p??
?????????? ???p???? ??? ??????????. ????????? ????????? ??????
???????????? ??????.
1. ????p ????????? ?????????, ?????????p????? ?p??????
????p????? ?? ? ?p????????? ??.
2. ????p ???? ????????? (?????? ?? ?? ?????????? ?????????).
3. ????p ??p?? ?????????????? ????????? ? ?? (?????? ?? ???????
??????, p???????? ?????????? ?p?p??? ????? ??????????).
????????? ???? p?????? ???? ?????:
? ?????? ??p???p (???????? ?p?????????? ?????? ?????????????
??p???p? ???? ?????????? ????????? ?????????) ? ???p??????;
? ???p??????? ??p???p (???????????? ?????? ?????????? ??????,
??????, ????? ?????? ????? ???????????, ????????? ????????? ?????
????p??????);
? ?????p???? ??????.
???? ?? ????????? ????? ??????? ??????? ? ?????????. ?????????
????? ??????????? ???????? ???? ?-??? ???????? ? ????????? ??????????????? ?????? (????. 1.1 ? 1.2).
??????? 1.1
???
??????? ???????
???????
???????
?????-??????? ?????????????? ???????????
?
?
?
?
?
??????? ????????? ???????????? ???????????? ? ????. 1.2.
??????? 1.2
K1
K2
K3
K1
K11
K21
K31
K2
K12
K22
K32
?
?
K23
?
?????, ???????????? ?????? ??????? ?? ?????? ???? ??????? ??????? ? ????? ???????????? ?????????, ???????? K11K23. ???? ???????
????????????? ? ???????????? ????????????? ?? ????????? ??????
? ?. ?.: ??p??????? ??????, ??????????? ????????????? ????????
???????????? ???????.
7
????????? ??????????? ?? ?????? ????????????? ??????? ?????????? ???????????, ????p?? ?p??????????, ??? ??p??p????? ?????????? ??p????p? ?????? ?? ????p????? ?????????.
?p???????? ??????? ????p?????? ???????????????? (????? ???,
???p???p, ?????? ? ??????????p?, ? ???p????, ? ?????????? ? ?. ?.)
??????? ? ??????? ?????????????? ?????????? ??p???p??? ?????.
????????? ??????? p?????? ????????????, ??? ??? ?p??????????
?????? ??????????????? p????? ? p????p?????? (??????? ?p???????
?p?????????? ????p????). ? ???????? ??????p???? p??????p?? ????????? ?p???p.
?????? ? ??????????p? (p????????? ??p????? ?? ??????? ??p??)
??????????p ?????? ???????? ??????p?? ????????? ??p???? (p??. 2, ?
? ?). ?????? ??????? ? ???, ????? ????? ?p???????? ???????, ??????
???????? ?? ????? ??????? ?? ??? ?????? ?? ????? ?????? ???? ?
????????? ? ???????? ????? (??p?? ? ? ???????? ?????).
?p? ??????? ??????? p?????? ???? ?????? ??????? ????p?p???
??? ????????? ??p????????? ??p????. ???? ?????????? ??????????
? ????????, ????p?? ?? ????? ?p???? ????? ????? ????? (?
??????p?? ??????? ?????? ??? ????? p??), ????? ???p???? ??? ?????????? ? ?p??? ?????????? ?????? ?p???????? ??p?p??. ????????? ????? ????p???? O(n!).
? ????? ?????????? ????????? ????p???? ????????? ?????
?p?????????? p??????, ? ??????, ? ?????? ??????: ??????? ? ?, ????????? ??p?? ????????? ??p??, ?. ?. b, ? ????? e. ?????, ???? ??????? d, ?? ??????? ????? ??????. ????? ?p?????? ? ????????????
p??????, ? ????p?? ????? ???? p???? 16 (????????????? ???????????). ????? ????p??? ????? ??? ?????????????? ?????????.
?????? ??p????p??????? ???????????
? ??????? ??p????p??????? ??????????? ????????? ?????????
???????? ??????:
? ??p???????? ??????????? ???????? ??p????p??;
? ?????????? ??????????? ???????? ?? ??p????p? ?? ?????????????? ?????? ? ???????? ??p????????? ?? ?????????? ????????;
? ??p????p??????? ????????????? (????????? ??p????p?? ? ?????? ????? ??????? ?p?????p?????? ?? ?????? ?????? ?????????).
8
1.2. ?p???p? ?????????? ????? ??p????p??????? ???????????
1. ????? ?p??????? ??p?????p????? ????????p ? ??p?? ?p????????????
??p???????????? ??????? V = 1 ?3 ? ??p?????????? ??????? ?????????. ?p? ?????????? ??????? ?????? ??????? ?????? ???? ??????????, ?. ?. ????? ??????
S = 2( x1 x2 + x2 x3 + x1 x3 ) ? min .
x1x2 x3
?? ???????????-????????? ????? ????????? ???? ??p???????
V = x1 x2 x3 = 1; x2 =
?
1
1 1 ?
; S = 2 ? x1 x2 + + ? .
x1 x2
x1 x2 ?
?
? ?????????? ??????? ??????? ?????????? ????????? ???????
x1* = x2* = 1 ?; x3* = 1 ?.
(?. ?. ??????????? ??p??? ???????? ???).
????? ????????? ??????, ???p???p, ????? ????????p ??? ?? ?????
2 ? ?????? (????? ???????? ??p????????: x1? 2).
2. ?????? p????? (?????? ??????? ?????? ??????? ???????
??p???????)
T
? n(t ) dt ? min.
n
0
??p????????: ??? y (t ) + mg = n (t ), t[0, T ]
n (t ) ? b, y (T ) = y , y (0) = 0,
??? y ? ??????, ?? ????p?? ?????? ????????? p????? ?? ?p??? T; n(t) ?
????, ??????????? ?? ?????? ? ???????????? ???????????.
?p?????? ??? ????????? ?????????? ??????: ??p??????? ??????????? ???p???, ????p?? ???? ???p????? ?? ????????? p????? ?? ??????
y(T) ?? ???? ????p? ??p??????? n(t) ? ??????????????? ??? ?p?????p??
y(t)
f ( y , n ) ? min;
k
K
? nk
k =1
? min.
k
9
???? p?????? ??p???? [0, T] ?? k ????p????? ????? d, ?? ?????
???p??????p????? ?????? ?p? ???????
y1,k ? y1,k ?1 = y2,k ?1 , k = 1, K ;
y2,k ? y2,k ?1 = uk ? mg ; uk ? b; y1,0 = y1,2 = 0; y1,k = y;
? ????? ????? ??p??????? n(t), ?p? ????p?? ?????? ??????? y ?????
????????????
f ( y , n ) = ? y ? min("? ", ??? ??? f = ? max( ? f )).
n
3. ??p????p??????? ?????????????:
?????????? ????????? ????????
+ k ? + c? = ?mgl sin(?).
ml2 ?
??????? ? ?????????? ????? ?????
y'1 = ?
=y2;
y'2 = f(m, l, k, c).
????? ????? ????????????????? ?????? (???. 2, ?). ?????? ? ???, ?????
??????? ??????????? ????????? ?? ?????? ?????? ????????????.
?)
?
t
?)
4
b
3
a
2
1
4
d
c
e
1
1
5
f
???. 2
????? m, l ??????, ? k ? c ? ??????????. ????????? ?????? ????
?????? ??????
J=
10
N
? ( y1(ti , k , c) ? ? i )2 ? min.
k ,c
i =1
???????, ??? ????????? ?????? ???????? ??? ??????? ????????????????? ??????, ? ?????????, ? ???????? ????????????? ??????? ??????? ???????? ??, ??????? ?????????? ??????????. ???????, ??? ????
? ?????????? ??????? ???????? ?????? ??, ?? ?? ?????? ????? ????????? ????? ????????????, ??????? ?????? ??? ?????????? ??????????? ?? ??????? ???????.
???????p?? ???p????? ?????????????????? ?????????? ?p???????
?p?????p, ????????? ? ??????????? ??p????p??????? ???????? ?p?
?p?????p?????? ?p???p?? (p??. 3). ?????????? ??????????? ? ??????????? ?????: ?????:
1 ? ??????;
2 ? ??????????? ??;
3 ? ????p ??p????p? ???????????? ????? ???????;
4 ? ????p????? ??p??p??? ?????????????? ??????(?????????????
??p??????, ???????? ??p????p??);
5 ? ??????p?????? ?????????? ?
6 ? ??????p?????? ? ??????;
7 ? ?????????? ?? ??pp????p????? ???p?????? (??)?;
8 ? ?????? ?? (??p????p??? ? ??p????p??????? ???????????);
9 ? ?????? ?? ???????? ?;
10 ? ????? ?????? ??p????p??????? ???????????????? (????p ???????? ??p????p??)?;
11 ? ?????? ????????????????;
12 ? ??????????? ??p????p??;
13 ? ??????? ??????????? p???????;
14 ? ??? ????? ?p???p? ???????????;
15 ? ??p???????? ?????????? ????????????? (??) ????? ?p???p?;
16 ? ?????????? ????????????? (??) ????????????? ???
17 ? ?????;
18 ? p??p?????? ? ???????????? ?????? ?p???p?;
19 ? ??p???????? ?? ?????;
20 ? ?? ????????????? ???
21 ? ??p????p??????? ?????????????.
??? ?? ??????????
?? =
? ????????????? ?????????????
=
.
S
C????????
11
1
2
3
4
?
5
?
6
7
?
?
10
8
?
11
9
12
13
?
?
14
?
15
18
16
?
?
19
?
6
???. 3
?
20
?
17
12
?
21
1.3. ??p????????? ?p?????? ?p?????? ??????????? p??????.
?????????????? ?????? ??
???p??????? ?????? ????? ???? ? ????p?????? ???? ????? ???????
??:
1. ?????????????-??p????p??? (?????? ? ?????? ?????????? ????????? ??). ??????? ??? ???????? ????? ?????? ???????? ?p????????????
?????, ???????p????, ????p?? ????? ??????? ???p?????? ?? ?????
p????? ??????;
2. ?????????????? ??????? (??), ??????? ????? ??????? ?? ??????????? ????????, ???????????? ???????, ??????????????? ????? ??????????????. ????? ??????? ????? ???????? ????? ??????????????, ????????? ?p????p??? ?????????? ?? ?? ???? ????? ? ??? ?????????????? ??? ????p????? ???? ???????????? ?????p?? ?p?????? ?? ??????
????p???????? ?????????????? ???p????, ?? ? ? ?????????????
?p??????? p??????????.
???????? ???????, ????p?? ????? ??p??p???????, ??????????
??p????????? ??p????p???. ??? ??p????p? ???????????? ? ?????p
x = ( x1 , ..., xn )T ,
(???p?????????, ??? ??? ????? ?? ??p??p?????, ??? ?????? ??
??p????p??????). ????????? ??p????p? ????? ???? ??????????? ???
?????????? ??????????. ?????p x ??p????p????? ??????? ? ????? ?p????
p??p???????? ??.
???????? ??????? ?p???, ???????? ?? ?? ?????????? ????????
??p????p???. ??????? ??p????p?, ??????? ? ????? ??????, ????????? ?p?p???, ?????? ? ?????p
? = ( ?1 ,..., ?l )T ,
????????, ??????? ???????????, ??????????? ? ?. ?.
????????, ??????????????? ?????????????? ???????? ???????????
??, ?????????? ????????????????
? = (?1, ..., ?m).
? ???????? ?p???p? ????? ??????? ????? ??p????p?, ??? ???p????????
????????, ????????, ?????????, ???????? ? ?. ?. ?? ????? ????????, ??
??????????????? ???????? ?????? (???p???p, ??? ???? ?????????? ???????? ?? ????????? ? ???????? ?????????). ?????p ? ??p????p?????
??????? ? ????? ?p???? ?????????.
13
??? ?? ?? ????? ???????? ????p?????? ????? ????? ??????????? ??p????p??
{x, ?} ? {?},
????p?? ????? ???? ?????? p????????? ????????? (????????????,
?????p??????????? ???????????, ????p????????? ? ?. ?.), ? ?????????,
??? ?????????????? ???????????:
?1 = ?1 ( x1 ,..., xn ; ?1 ,..., ?l );
?m = ?m ( x1 ,..., xn ; ?1 ,..., ?l ).
???????, ??? ??? ??????? ?? ????? ????p???? ????????? ?? ????????? ??????? ??????????? ? ??????????? ?? ???? (??????) ??????????????, ?????????? ????????? ????????, ???????????? ? ??????
????p????? ????????. ????????? p?????? ? ???? ?p????????? ?? ?????? ??, ???????????? ?????? p???????? ?? ??p??????? ???????p?????
p??????????, ?????????? ? ?p?????? ?p?????p??????.
1.4. ???????????? ???????-???????????????? ??????????,
????????????? ? ??????? ??????????????
??????????, ?????????? ?? ??, ??????? ?????????? ? ??????? ?????????????, ??????? ???????????????? ? ?????? ??????? ????? ????
?????? ? ????
x ?j ? x j ? x +j , j = 1, n;
x ?j ( xk ) ? x j ? x +j ( xk ), j ? k ;
?i? ? ?i ( x ) ? ?i+ , i = 1, m.
????????? ?????? ?????????? ???????????? ????? ? ????
g ( x) ? 0 ,
???
???i ( x ) ? ?i? , ?i? ? ?i ( x );
gi ( x ) = ?
+
+
???i ? ?i ( x ), ?i ( x ) ? ?i .
??????????? ???? ????????? g (?) = 0, ???? ??????????, ????? ????
???????? ? ?????? ?????????? ? ????
14
? g k ( x ) ? 0;
?
? ? g k ( x ) ? 0.
? ?????? ???????, ??????????? ?i ( x ) ? ?i+ ????? ???? ????????????? ? ????????? ????????? ?????????????? ??????????
gi ( x ) = ?i ( x ) ? ?i+ + zi2 = 0 .
? ???????? ?????????????? ???????????? ??????? ?????? ?? ???????? ??????? ?, ??????? ??????????? ????????? D (?????????? ???????,
??????? ?????????????????)
{
D=D? ? Dy;
Dx = x | xi? ? x j ? xi+ , j = 1, n ;
{
}
D y = x | yi ( x ) ? 0, j = 1, m .
????? ?????? x ? D ? ??????????????? ??????? ??. ??????? ????????? ???????????, ?????? ??? ???????? ??????? D.
1. ?????????? ????????? D.
????????? ?????, ?????????? ??????? ?????????? ??????? D, ?????????? ???????? ??????????, ???? ??? ????? ???? ????? x (1) , x (2) ? D
??????? ??????, ??????????? ?? x = ?x (1) + (1 ? ?) x (2) , ????? ??????????? ??????? D (???. 4, ?, ?), ?. ?., ???? ??? ????? x (1) ? x (2) ? D ?????
????? ??????? ?????? ??????????? D, ?? D ? ???????? ???????.
2. ???????????? ?????????.
?????????, ??????? ??????? ?? ?????????? ?????? (???. 4, ?) ?????????? ????????????
?? y1 ( x ) = ?0,25 + x2 ? 1 ? 0;
?
2
?? y2 ( x ) = ? x2 + x1 ? 4 x1 + 4 ? 0, ??? x1 ? 0, x2 ? 0.
???? ? ??????? ??????????? ?????? ?????????????? gi, ????????? ??
?????????? ????????? n (?????, ??????????? ? ?. ?.), ?. ?. gi ( x, ?) ? 0
??? ?????? v ? ? ? ? , ? + ? , ?? ????? ????????? ??????????? ?????
?
?
? ? = ?1 < ... < ? s = ? + ???????? ? ??????
gi ( x ) = min gi ( x, ? k ) ? 0,
1? k ? s
?. ?. gi(?) ?? ??????? ?? ?.
15
1.5. ?????????????? ?????? ???????? ??????????? ???????
1. ????? ?????? ?????????????? ??????????? ? ??????? ????????????????? ?? ???? ? = ?( x ). ???? ? ??????? D ??????? ?????? ????
???????? ??????? ?????????? ?, ?? ???????? ???????? ??????? ?? ????????? (????????, ???? x = const). B ??? ???????, ????? ??????????????? ??????? ?? ????????????, ??? ????????? ????????? ? ?????? ??
??? ?????????? (? ????????? ??????) ?????????? ?????? ??????? ????
(???????? ????????????? f = f (?( x )) = f ( x ) ? ??????????), ????????
b
f ( x ) = x (t ) dt ,
?
a
????????????? ???????? ??????? ??????? ???????? ????????????? ???????? ???????-?????????????? ?????????? ??. ???? ???????? ??????????
????????????? ???????????? ?????? ???????? ?? ????????? ? ???????,
?????????? ???? ?????????????? ? ?????? ? ???????? ? ? ???????? D ???????? ?????????????? ?????? ???????? ???????????? ???????, ??????? ???????? ??????? ??????????????? ??????????? f ( x )* = min f ( x ) (? ????????
x?D
f ????? ???????????? ????? ??????????????, ??? ?????, ????????, ????????? ????????? ??????, ??????? ? ?. ?.).
????? ???????, ??????? ?????? ???????? ? ?????? ??????????? ?????????? ?*, ????????????? ?????????? ??????? ? ???????????? ??????? ???????? ????????????? f(x) (???????, ??? max f = ?min(?f)).
?) x 2
x2
?)
x1
D
x1
x2
?)
x1
x2
?)
x1
x1
?) f(x)
x1
D2
D1
d
D
x1
f
f1
x1
?) x 2 g =b
2
2
f2
x2
x2
D
x2
x
g 4=b 4
g 1=b 2
g 3=b 3
x1
x
???. 4
16
)
2. ? ??????????? ?? ???? f(x) ??????????? ??????? x* ????? ????
?????? ?????????? ??? ??????????? ????????.
?????? x* ?????????? ?????? ?????????? (??????????????) ????????, ???? ??? ???? ????? x, ????????????? ?-??????????? d ( x* , ?) ????
?????, ??????? f(x) ?? ????????? ???????? ????????, ?. ?. f ( x* ) ? f ( x )
??? ???? x ? d ( x* , ?).
? ?????? ??????????? ???????? (???????????) f ( x* ) ? f ( x ) ???
???? ??D, ?. ?. ?????????? ??????? ? ??? ?????????? ?? ???? ????????? (???. 4, ?).
3. ???? ?????????? ???????? ????????? ???????? ???????????? ???
?????????? ?????????, ????????????? ????????? ???????? ????????????? f ( x ) = ( f1 ( x ),..., f s ( x )) (????? s ????? ??????????????). ?????? ????????? ???????????
f ( x* ) = min f ( x ) = min f1 ( x ); min f 2 ( x ),..., min f s ( x ).
x?D
x?D
x?D
x?D
??????????? ??????? ???? ??????, ? ????? ??????, ?? ????????
?????? ???????? ?? ??? ?????? ?? ??????? ????????? (??? ???????,
fi ?????????????). ??????????? ??????? ?????????? ???, ????? ?????????? ?????????? ????? ???????? ??????????, ??? ??? ?????????? ????? ?? ??? ???????? ? ?????????? ??????. ?????? x* ? ????
?????? ?????????? ???????????? ????????. ???? ?? ????? ??????? ???? ?????? ??????? ? ???????? ?? ? ?????????????????.
4. ??? ???????????? ????????????? ?????? ?? (?. ?. ????????????
????????? ??????? ??????? ?) ?????? ???????? ??????? ????????? ?
????????? (????????, ??????????????? ??????? ???????? ?? ?????????). ???? ? ??????? ???????????? ? ????????, ??? ?? ??????????? ????????? ??????? D? (?????? ????????????????), ?????
?
?
min f ( x ) = min ? max f ( x, ?) ? ,
x?D
x?D ? ??D?
?
??
??
?
?
??? D = ? x | gi ( x ) = ? min gi ( x, ?) ? ? 0, i = 1, n ? , ?. ?. ??????????? ??
??
??
? ??D?
?
???????????. ?????? ??????? ? ????????? ?????????? ?????????? ??
? ? ????????? ?????? ?? ???????????????? ?. ???????, ??? ???????
??????? ??????????? ?? ???? ? ????? ?????? ????????? ???????
???????.
17
1.6. ????????????? ????????????? ?????,
??????????? ??????? ???????? ??????????? ???????
? ??????????? ?? ????? n ??????????? ?????????? ?, ????????? ??????? ?????????? ??????? D ? ???? ???????? ????????????? f(x), ??????
??????????? ?????????? ? ????????? ??????? ????????????? ?????.
1. ???? n = 1 ? ?????????? ??????.
f ( x ) ? min (????? ???????? ???????? ?????? ?? ?????????).
a ? x ?b
???? n ? 2? ???????????????????? ??????.
2. ???? f(x) ????? ? ??????? D ???????????? ????????? ???????,
?? ?????? f ( x ) ? min ?????????? ???????????? (?????????????????)
a ? x ?b
??????? ???????????, ? ????????? ?????? ? ?????????????????? ???????.
3. ??? ?????????? ??????????? ?? ??????????? ????????? ? ? ?????????????? ?(x) ???????? ? ?????? ??????????? ??????????? min f ( x ).
x?R n
???????????????????? ?????? ??????????? f ( x ) ? min ? ????????x?D
????? ???? ???????? ??????????, ???
{
}
Dx = x | x ?j ? x j ? x +j , j = 1, n ,
????? ???? ??????? ? ?????? ??????????? ??????????? ????????????
?????????? zj, j = 1, n ? ??????? ??????????????
x j = xi? + ( xi+ ? xi? )sin 2 z j ,
j = 1, n.
??? ??????? ?????????? ??????????? ?????? ??????????????? ??????????? ?????????? ??????? ??????????? ???????????????? (? ?????? ????????????)
min f ( x ), ??? gi ( x ) ? 0, i = 1, m.
x
? ????????? ??????? ??????? ????? ?????? ??????? ?????? ? ??????
??????????? ??????????? ? ??????? ??????? ?????????????? xi=ri(zi)
(zi ? ????? ??????????). ????????, ???? ???????
?? n
??
z
1
D = ? x | xi 2 = 1? , ?? xi = ri ( z ) = i , i = 1, n ? 1, xn = rn ( z ) = ,
?
?
?? i =1
??
?
18
1
? n ?1 2 ? 2
??? ? = ?? 1 + zi ?? .
? i =1 ?
???????? ?????? ?????? ? ?????? ??????????? ???????????, ??????? ??????? ????????? ????? (??? ?????????????? ????? ????? ? [4]).
??????? ??????? ?????? ??????????? ???????????????? ????????
?????? ? ????????????? ???? ????????
?
min f ( x ), ??? gi ( x ) = bi , i = 1, m < n.
x
? ?????? ??????????? ???????????????? ??? ???????????? ??????? (??? ????? ?????????? ??? ??????????? ????????) ??????? ?? ?????? ?? ???? f(x), ?? ? ?? ????, ???????? ?? D ???????? ??????????.
4. ?????? ??????????? ????????????????, ????????? ? ???????????? ???????? ??????? f(x), ??????? ?????? ?? ???????? ????????? D,
?????????? ??????? ????????? ????????????????. ??????????? ??????? x* ?????? ????????? ???????????????? ???????? ? ????????? ????????, ??????? ???????? ? ?? ?? ????? ?????????? ?????????.
??????? f(x) ???????? ?? ???????? ??????? D, ???? ??? ????? ????
????? (x 1, x 2 )? D ??????????? ??????????? f ( ?x2 + (1 ? ?) x1 ) ?
? ?f ( x2 ) + (1 ? ?) f ( x1 ) .
? ?????????, ? ?????? ??????? ????? ?????????? ??????? ??????? (????),
???? ????? ???? ?????, ??????????? ????? ????? ??????? (???. 4, ?).
????????, ??? ???? ?????????? ??????? ?????? ????????????? gi(x) ? b,
? gi(x), i = 1, m ? ???????? ???????, ?? ?????????? ??????? ????????
(???. 4, ?). ??????????? ???????? ???????? ???? ???????? ?????????
(????????!).
5. ?????? ????????? ???????????????? (??????? ??????? ?? ???????? ?????????) ?????????? ??????? ????????? ????????????????
(??), ???? ???????? ? ??????????? ? ???????? ????? ?? ???????????
?????????? ?
n
??
??
min ? ci xi ? , ???
x ?
? i =1
??
?
n
? aki xi ? bk ,
xi ? 0, k = 1, m, i = 1, n
i =1
? ?????? ?? ??????? D ?????? ??????? (????????!).
?????????? ?????? ?? ???????? ?????? ?????????????? ????????????????, ? ??????? ???????? ????????????? ? ??????????? ????? ???
???? ?? n ?????????? ??????? ?????? ?????? ???????????
19
n
min
x
?
i =1
n
ri ( xi ), ???
? hki ( xi ) ? bk ,
xi ? 0; k = 1, m; i = 1, n.
i =1
? ???? ??????? ????? ??????????? ??????? ?? ?????? ?? ? ??????
?????????????? ????????????????.
6. ?????? ??????????????? ??????????? ? ?????????????? ???????????, ????? ??????????? ????????? ? ????????? ?????? ??????????
????????, ?????????? ??????? ?????????? ??????????? (D ? ?????????? ?????????). ???? ??? ??????????? ????????? ?, i = 1, n ????? ????
?????? ?????? ???????????????? ???????, ?? ?????? ?????????? ??????????? ?????????? ??????? ?????????????? ????????????????. ?
???????? ??????? ???????? ?????? ? ?????.
?????? ?????????????? ????????? ???????????????? ? ????????
??????????? (0 ??? 1) ?????????? ??????? ? ??????? (? ????????), ????
?? n
??
f ( x ) = ? ? ci xi ? ? max ???
x
?? i =1
??
n
? ai xi ? b,
i = 1, n; xi = 0 ??? 1.
i =1
????????? ????? ????, ????????, ?????. ?????? ??????????? ?????????? n ????????? ?????. ??????? i-?? ???? ??????????????? ????? ? ? ?????????? (???????????) ?i. ???????????? ???????????????? ??????? (???)
b. ????????? ????????? ?????? ?????????? ???, ????? ???????????????
??????? ?????????? f ? ?? ????????? ?????????? ????????????????. ?
?????? ??????, ???? ?i = 0, ?? ??? ????????? i-?o ????, ? i= 1 ? ????.
1.7. ??????? ???? ???????????? ???????????????? ???????
1. ??????????? ????????????? ??
f1(1) ( x ) = ?( x ) ? min,
x?D
(1.1)
??? ? ???????? ????????????? ????? ?????????, ????????, ????????????
????????, ??????? ????? ? ??.
f1(2) ( x ) =
N
? ?( x, pi ) ? min,
x?D
i
??? pi ? ???????? (?????, ???????, ???????????).
2. ?????? ?????????????.
20
(1.2)
??????????? ??????? ???????? ?????????????? ???????? ? ????????? ???????? (? ?????????, ? ?????????????????)
f 2(1) ( x ) = (?( x ) ? ? ? )2 ? min;
x?D
f 2(2) ( x ) =
1
N
(1.3)
N
? ?i (?( x, pi ) ? ?? )2 ? min,
x?D
i =1
(1.4)
??? ?i ? ??????? ???????????? (???. 5, ?).
3. ?????????????? ?????????? ????????
?0, ? H ? ? ( x ) ? ? B ,
B
?
?
?
?
H 2
(1)
f 3 ( x ) = ?(?( x ) ? ? ? ) , ?( x ) > ? ?H ? min,
x?D
?
2
?
?
??(? ? ? ?( x )) , ?( x ) < ? ? ,
f ( x ) = max ?i | ?( x, pi ) ? ?i? |? min (???. 5, ?).
x?D
i =1, N
(1.5)
(1.6)
???????, ??? ??????????? ???? (1.3), (1.4) ???????? ????????? ???????????. ???? ?(?, ?) ?????? ?????????? ??????????????? ?? ?, ??
???? ?? ????????? ???????? ? ??????????? f(?), ??? ??????????? ????????? ????????? ???????????.
???????????? ???????? ????????????? ????????? ?????????. ?. ?.
?????? ????????????? ? ????????? ?????? ?? i, ????? ???????????????? ??????? ????????? ? ?????? ??????. ???? ?????????? ???????? ?
???????? (1.6), ???????, ? ?????????, ?? ????????? ????????? ??????? ?(?, ?) (??????? ???? ????????, ?. ?. ?? ????? ????????????????
?? ?), ??? ??????? ??????????? ??????????? ??????? ???????????.
??????? ????? ?????????? ??????? ??????????????? ?????????????
???????????? ???????? f4(x)
f5 ( x ) =
?
N
? ?i? ( x ) ? min,
x?D
? = 2,3, ... ,
(1.7)
i =1
??? ?i ( x ) = ?i | ?( x, p ) ? ?im | .
??? ?????????? ??????? ????????? ? ??????? ????? (1.6) ? (1.7)
????? ?????????, ??? ??? ???????????
21
1
? N ? ??
?? ?i ?? ? max ?i , ?i ? 0.
? i =1 ?
???????? ?????????? ????? ?? ?????? ?? ??????????? ????? ????????.
?????????? f5 ????????? ??????????? f2 ? f4. ??????? ??????? ??? f2, ??
? ?? ?? ????? ?? ????????? ???????????? ?????????? ???????? ????????????? ? ????????? ?????? (?????? ??????????? ?, ??????? ? ? = 2).
?
1.8. ?????? ?????????? ??????????? ??? ??????????????
??, ??????????? ???????? ????????? ?????? ????????, ?????
????? ???? ???????????? ? ???? ?????? ???????????? ???????????????? ????????? (????), ????????? ??????? ??????? ?????? ????????? ??????? ???????? ????. ????? ?? ????? ???
y = F( y , t , p ), y ? R n , p ? R m ,
??? ? ? ??????????? ?????????, ??????? ??? ??????????.
???? ???????? ?????? ????????????? ???? ???????? ????????? ???????? ?????????? ym(t) ?? ???? ?????? ??????? ?, ?? ? ???? ???????
??????? ???? ?? ?????? ?????????? ?????????????? ???????? ??????? ?
???????? ???????????, ????????? ????????????? ??????. ??? ???? ??????? ???????????????? ?????????? ??????????????? ???????????.
????? ??? ???????? ? ???????? ??????? ?????? ????????? ????????. ?????, ????????? ?????????????? ???????? ??????????,
yi (t ) =
ri
ri
k =1
k =1
? aik ?ik t ) = ? aik e?
ik t
( Aik cos ?ik t + Bik sin ?ik t ).
????? bik = ( Aik , Bik , aik , ?ik , ?ik ) ? ???????? ??????? ???????? ????????????? b = (b1, ?, bs) ????????? ?????????? ???????.
????? ??????????? yi ? ???? ???????? ??????? ??????????????
????????? ? ??????? ?i (b, p, t ) ? 0, i = 1, n . ????? ?????????? ???????
????? ?? ???????? (?? ?????? ?????????? ? ???? ??????? ???????????
? ? ? ?
?
??????? ??????? t = ? 0, , , , ..., ? ??????? ????????????????
? ? 2? 3?
?
??????? ? j (b, p ) ? 0, j = 1, N .
?????? ??????? ?????? ????????????? ????? ???? ??????? ? ??????????? ????? ????????? ???????, ?. ?. ?i2 (b, p ) ? min .
?
i
22
p
1.9. ??????? ?????? ??p???????
???????p?? ?????? f(x) ?min, x?Rn. ?????????? ? p?? ?????p? ???
??????? f(x) ? ????? x ????? ???
1
f(x) = f( x ) + ?f(x)?x + ?xT? f(x)?x + 0(?x),
2
??? ?x= x ?x;
T
? df
df ?
,...,
?f = ?
? ?p?????? f(x);
dxn ??
? dx1
? d2 f ?
?2 f = ?
? ? ???p??? ????? (???????)
?? dxi dx j ??
(??????p??????? ???p???, n Ч n);
?f =f(x) ? f( x )? 0.
???? ??? ??p???????? ??????????? ??? ???? x?R, ?? x ? ????? ??????????? ????????, ???? ???? ? ??????p?? ? ? ??p???????? ?????, ?? x ?
????? ?????????? ???????? x*.
??? ????????, ??? ??????? ? ????? x ?????????? ???????? (???????????? p??????) ?????????? ? ??????????, ????? ?f( x *) = 0 ? ?2f( x *)
???? ????????????-??p????????? ???p????, ?. ?. ????p??????? ??p??
Q = ?xT ?2f(x)?x > 0 ??? ????? ?x ? 0.
?)
?
?
? ??
?) ?(x)
Pi
?
Pi
?)
D2
D1
x
???. 5
23
?????? ?????????????? ??????????? ?????????? ????????, ?? ????
??????? ????????, ??? Q > 0 ??? ???? x, ?? f(x) ?????????? ????????
????????, ? ????????? ??????? ??????????? ?????????? (???. 5, ?).
??? ????????? ????????? ??????? ???? ??????????? ???????? ???????????? ?????. ????????, ??? ???????? ????? ????????? ? ??????????
1
??????? ?????, ?. ?. A = ?2f(x).
2
1.10. ?p???p?? ????????????? ??p??????????? ???p??
1. ???p??? A ?????????? ????????????-??p?????????, ???? ??? ??
??????????? ???????? ?i > 0 (??? ???? ???????????? ??? ??p?? ??
??p????p??????????? ?p???????).
?p???p
f(x1, x2 )= 2x1 + 6x2 ? 2 x12 ? 3 x22 + 4x1 x2;
1
1 ?4 4 ? ? ?2 2 ?
=
A = ?2 f ( x ) = ??
;
2
2 ? 4 ?6?? ?? 2 ?3??
?2 ? ?
2 ?
= 0;
det ( A ? ?I ) = det ??
?
? ? ??
2
3
?
(
)
? 2 + 5? + 2 = 0;
1
????? ?1,2 = ?5 ± 17 ? ??p?????????, ?????????????, ??????? ???2
?????.
???????, ??? ??? ????p??????? ??????? ???p??? ????? ?? ???????
?? ?????, ? ????p?? ??? ?????????.
2. ?p???p?? ????????p? ???????? ????????? ???????. ??????p?????
???p??? A ???????? ????????????-??p?????????, ???? ??? ??????? ??????? ????p? ????????????.
2 1?
, ?1 = 2 > 0, ?2 = 3 > 0 ? ??p?????????-??p?????????,
A = ??
1
? 2 ??
???? ????? ??????? ??????? ????p?? ??p???????, ?p???? ????? ???????? ????p?? ??p?????????.
3. ?p???????? ????p??????? ??p?? Q(x) ? ????? ?????? ????p????
(??p?? ???p????)
1. Q(x) = a x12 + 2 b x1 x2 + c x12 = (a2 x12 + 2 a b x1 x2 ) + c x22 =
24
=
1 2 2
(a x1 + 2 a b x x ) + c x22 =
a
1
= (a2 x12 + 2 a b x1 x2 + b2 x22 ? b2 x22 ) + c=
a
1
= (a x1 + b x2)2 + (a c ? b2) x22 ;
a
1
q(x) > 0, ???? > 0;
a
a c ? b2 > 0.
2. ??????, ?????????? ?? LU ? p?????????:
A = L D U,
??? U ? ??p???? ?p????????? ???p???; D ? ???????????? ???p???. ???
??????p????? ???p??? A = UT D U
Q(x) = xT A x = xT UT D U x = (U x)T D (U x).
?????? ????? ??p??????? z = U x, Q(x) = Q(z) = zT D z =
n
? dii zi2
i =1
(????? ??p????, ?????????? ????? ???p??? U ? D).
???????p?? ?????? ?p???p???????? A ? ??p???? ?p????????? ???p???.
?????
a b?
.
A = ??
? b c ??
??p??? ??p??? ??????? ?? a, p???????? ?????????? ?? b ? ??????????
??p??? ?????????? ?? ???p?? ??p???, ?. ?.
b ?
?
?1
a ?.
?
2?
?0 c ? b ?
??
a ??
????? ??????? ???p?? ??p??? ?? ???????????? ??????? ????????
???p??? U
?1 b ?
U=?
a ?.
??0 1 ??
25
?? ?????????, ?? ????p?? ??????, ???????? ???????????? ???p???
0 ?
?a
?
1
?
D=
b2 ? ; z = Ux = ?
?0 c ? ?
?0
?
a?
?
????p? ????????, ??? Q ( x ) =
b?
a ?.
1 ??
n
? dii zi2 ,
i =1
b
b2 2
)x .
Q(x) = a (x1 + x2 )2 + (c ?
a
a 2
????, ????? Q ????????????-??p?????????, ???? ????? ?????????
???p??? D ?????? ????. ????? ??p????, ?p? ????????????? ???????
??????? f(x) ????? ????? ??p??????? ??p????p ?? ????????? ?? ???p???
??p??.
?p???p
f(x)=x1 + 2 x3 + x2 x3 ? x12 ? x22 ? x32 ? min.
???????? ?? ????p???????? ????????p??? ????? x(*) =(1/2, 2/3, 4/3)T ?
???? ??, ?? ?????? max ??? min?
?p???p
???????? ?? ???????
f(x)= 2 x12 + x22 + 3 x32 ? x1 x2 + 2 x1 x3 ? x2 x3 ?????????
???????
?1/ 2
2
1
?1/ 2 .
1
A = ?1/ 2
?1/ 2
1
3
?????????? ????? ?????????? ??????
1 ?1/ 4 1/ 2
1 ?1/ 4 1/ 2
1 ?1/ 4 1/ 2
? 0 7 / 8 ?1/ 4 ? 0
1
2/7 ? 0
1
2 / 7 = U;
0 ?1/ 4 5/ 2
0
0
17 / 7
0
0
1
2 0
0
D = 0 7/8
0 .
0 0 17 / 8
26
2. ?????? ??????????? ???????????
???? ??????????? ?p?????????? ????? ????p??? ??p????????, ???????? ??????? ??????????? ??????????? ????? ? ?????????? ?????
?p????. ???, ???p???p, ?????? ????p???? p?????? ?????? ? ??p?????????? ?p?????????? ???????? ? ?????????????????? ????? ??????????? ??????????? ? ??????? ?????????? ???p???? ??? ? ???????
??p????? ? ??p??p??? ???????.
2.1. ???????? ????? ??? ????????????? ?p?????????
??????p??? ????? ? ?????? ?????? ????p????? ??? p?????? ?????
??????????? ?p??p????p??????.
?????? ????p???? ??????????? ???????????????? ?p??????????
????? ????????? ?p?????p?. ?? k-? ???? ???????? ????? xk, ??p????????? ?????p ???p??????? dk ? ????????? p????????? ?k ? ???p???????
dk, ????? ??????????? ????? ????? xk+1= xk+ ?k d k ? ?p????? ?????p?????.
??p???????? ?k ??????????? p??????? ?????? min f(xk + ?k dk), ????????? ?? ?k. ??? ?????? ??????p???? ??????.
???? ?? ????? ??????????? ?(?) = f(x + ?d) ? p????? ?? = 0 ? ??????
????? ?. ?????? ???? f ???????p????p????, ?? ? ? ???????p????p????.
? ?p??????? ??????, ??(?) = dT?f(x+?d), ?. ?. ??? ??p???????? ? ????
p????? ?p??????? dT ?f(x+?d)=0, ????p?? ?????? ????????? ?? ?. ????? ????, ??(?) = 0 ?? ??????????? ?????????? ??????? ??????? ?(?).
??? ????? ???? ????????? ??????? ??? ????????. ???????, ???
?p?????, ?p????????? ????????? ?p?????p? ??????????? ?.
1. ????? ??????? f(x) ??????????? ?? ????p???? a ? x ? b, ? ?? ??????? ??????????? ? ????? x (p??. 6, ?). ???? ?????? ??? ????? x1 ? x2 ?
f(x1) > f(x2), ?? ????? ???????? ????? ? [a, x1], ?. ?. ???? ????p??? ????? ?????????. ??? ????????? ????????? ?????? ??p???p ???? ?????????? ?????.
2. ??????? ??? ?????:
? ???????????? ?p???? (????? ?p???? ?????????? ??p?????
????p????);
27
? ???? ?????????? ????p???? (????????? ??? ????? ?? ??p???? ????????????? ????????).
???????????? ?p????
??p?????????? ?????? ???????? ????????? ???????. ????p??? ???????? ????? x0 (?p????????????, ??? ?????? ??????????????? ????p??????? ??p???????? ?? ??p??????? x, ?. ?. ????p??? [a, b] ? h =hmin).
???? f(x0?|h|)? f(x0)? f(x0 +|h|), ?? ????? (????p??? ?? ??????). ??p???????
???p??????? ????????. ???? h ??p?????????? ????? ?p??????? ????????:
f(x0), f(x0+ |h|) ? f(x0? |h|).
???? f(x0? |h|) ? f(x0) ? f(x0+ |h|), ?? ????? ???????? ?p???? x0 ? h ?
???????????? (p??. 6, ?). ???? h ?????????? ?????? ? ??p???????? x0.
???? ???????? ????? ?????????? ?? ?p?????????????, ?? h ?
??p?????????. ???p???? ??????????? ?? ??p????
xk+1 = xk+ h, k = 0, 1, 2, ...,
???? ?? ??????? f(xk+1? |h|) ? f(xk+1)? f(xk+1+|h|), ?. ?. ????? ????????
????? ????? xk+1 ? |h| ? xk+1+ |h| ? ????? ?p??????? ????? ????p???.
???? f(xk+1? |h|)? f(xk+1)? f(xk+1+|h|), ?? ??????? ?????????????.
???????? ????? ?????? ??????? ?????????? ??????-???? ????????
?? [a, b], ???? ?? ???? ??????? ?? ?????????, ? ????? ?? ?p?????
????p????.
?????????? ????p????
???????p??? ?????: ??????? ????p??? ?? N ?????? ? ???p??? ???????.
????? ?????????
??????? ??????? ????????? ????????? ???????? ????p???? ?? ?????? ???p????.
????p???
a+b
; L = b ?a; ????? f(xm).
1. x2 =
2
L
L
2. x1 = a + x2 = b + ;
4
4
f(x1), f(x2).
3. ?p?????? f(x1) ? f(xm).
???? f(x1) < f(x2), ?? ????????? (xm, b), ??????? b = xm.
28
f(x)
?)
a
?
?)
0
0
b
1??
1
2
1??
?2
2
1??
?
?)
1??
a
?)
x 0 ?h x 0 x0+h
b
x* x2
x1
?)
1
?
?
1
???. 6
??p????? ????p???? ??p???????? ? ????? x1.
xm= x1, ??p???? ? ?. 5;
f(x1) ?f(xm), ??p???? ? ?. 4.
4. f(x2) < f(xm), ????????? (a, xm), ??????? a = xm.
xm= x2, ??p???? ? ?. 5;
f(x2) ?f(xm), ????????? (a, x1) ? (x2, b);
a = x1 b = x2, ??p???? ? ?. 5.
5. L = b ? a.
???? |L| < ? ? ?????????, ????? ??p???? ? ?. 2.
??????????: ???????? ????p????? ? ????? ?? ???p??????? ????p????.
????? ???????? ???????
???????p?? ??????p????? p??????????? ?p????? ????? ?? ???????? ????p???? ????????? ?????. ?p????? ????? ??????? ?? ?p???? ??
p????????? ?-? ????? ?? ????? ????p????, ?. ?. ? ?????? ??? p?????????
p???? ? = ? ? 1 (p??. 6, ?). ?p? ????? p??????????? ????? ???????????
????? ?????????? ????p???? ?????? p???? ? ? (????? ????p????), ?????????? ?? ????, ????? ?? ???????? ??????? ? ?p????? ?????? ????????? ??????.
????? ??????????? ?????? ????p???, ????? ?????????? ????p??? ????
?p????? ?????, ?????????? p???? (?? ?? ??????????) (p??. 6, ?). ???
???? ????? ??????p?? ???p???????, p????????? (1 ? ?) ?????? ??????29
???? ? ????? ????? ????p????, p????? ?, ?. ?. ?2. ????? ??p????, ????????? ?p????? ????? p?????????? ?? p????????? ?2 ?? ?p???? ?p?????
???????????? ????p???? (p??. 6, ?). ? ???? ??????p?? ????? ?p???????
1 ? ? = ?2, ?????? ? = (?1± 5 )/2 = 0,618 (?p? ????? ? ??? ???????????).
??p??? ???????? ???????? ?p??????? ?? ???????? ????????? ??????????? ????p?????
L j ?1
Lj
=
Lj
L j +1
=
L j +1
L j +2
= ... = ?,
????p?? ? ???? ?????? ?????????? ????????. Lj-1 ??????? ?? 2 ????? ???,
??? ????????? ?????? ? ??????? ????? p???? ????????? ??????? ????? ? ???????, ?. ?. p???? ????????? ??????????
?
? ?
1
= ... = ? .
=
, ? ????? ?????? =
? 1? ?
? ?
????? ?????????
??p?????? ?????? ??????? ? ?????????????? ????? ?????????,
????p?? ????? ???????? ?? p???pp??????? ?p???????
uk = uk?1+ uk?2, k = 2, 3,...
u0 = u1 = 1.
??p??? ????? ????? p???
k 012345
uk 1 1 2 3 5 8
? ??????? ?? ?????? ???????? ???????, ????? ???p?????? ????p????
????p??????????? ???????? ?? ???p???? ? ???p????.
?p? n = 14 (????? ?????) ??????p??p??? ????p??? ????p???????????
?p???????????? ? 5 p?? ??????, ??? ?????????? ?? ?????? ???????
???????.
??????????: ?????????? ?????? ????? ????? n, ??? ??? ??? ???
??p???????? ??p??? ????? ???? ????? ????????? ????? ?????????
un?1/un (n ????? ??????? ?? ??p???????? un > L1 / Ln, ???? ???? ?????
?????????). ???????, ??? ????? ????????? ???????? ????????? ???????? ????p??? ?????? ?? 17 % ??????, ??? ????? ????????? ? ?p?
??????? n ?????? ?p????????? ?????????.
30
??????
x1=0; x2=1
x3= x1+(1?p)(x2? x1)
f1=f(x3)
x4= x1?x2? x3
f2=f(x4)
f2>f1
x2= x3; x3= x4
f1=f2
x1= x2; x2= x4
?
End
?
x1= x3 ; f= f1
?????
x1
f2
f1
x4
x3
x2
???. 7
??? ????????? ?????????? ?? ? ????? ?????????????? ?p?????p?
(p??. 7)
?u / u , ????? ?????????,
p = ? n2?1 n +1
? ? , ????? ???????? ???????.
? ??????????? ?? ????? p??????? f(x3) ? f(x4) ????????? ????p?????
?? k-? ? k?1-? ?????
31
? x3 ? x1
?? x ? x ;
tk = ? 2 1
x ? x4
? 2
;
?? x2 ? x1
f ( x3 ) > f ( x4 );
?????,
tk = 1 ? p,
??? ??? x3 ? x1 = x2 ? x4. ?????? ????????? ? ??????? ??p???????, ????
1/2 <tk< 2/3.
?????????????? ???p?????????
???? ??????? ? ???????????? ???p????????? ??????? ??????? ????????? ? ?????????????? ????? ???????? ??? ?????? ???p?????? ????????. ??-?p??????, ?p???????????? ?????????????? ???????. ???????? ?????? ???????? ????? ????????, ??????? ??p???? ???????? ? ????????
????p??? ???p????????? (??? ????? ?p?????????????, ??? ??? ???? 3-??
??p???? ? p???????????? c ?????????????? ????? ?p????).
????p??????? ???p?????????
??? ?p???????? ??? ???p?????????, ? ????p?? ?p????????????, ???
??????? ????? ?p???????? ????p??????? ?????????.
???? ???????? 3 ?????: x1, x2, x3 ? ??????????????? ?? ????????
???????: f1, f2, f3, ?? ????? ??p??????? ?????????? ????????: a0, a1, a2
???, ??? ???????? ???p??????p????? ??????? g(x) = a0 + a1(x ? x1) + a2
(x ? x1)(x ? x2) ???????? ?? ????????? f(x) ? ?p?? ???????? ??????. ??????? ??? ???????, ????????, ??? f1 = f(x1) = g(x1) = a0, ?. ?. a0 = f1. ????????, ??? f2 = f(x2) = g(x2) = f1 + a1 (x2 ? x1), ????? a1 = (f2? f1)/(x2? x1).
??? ??? f3 = f(x3) = g(x3) = f1+((f2? f1)/(x2 ? x1))(x3? x1)+a2(x3? x1)(x3? x1),
?????
a2 =
1 ? f 3 ? f1 f 2 ? f1 ?
?
?
?.
x3 ? x2 ? x3 ? x1 x2 ? x1 ?
????? ???????? ????p??????? ??????? ??????? ?? ???????
dg
= 0 = a1 +a2(x?x2)+a2(x?x1),
dx
??????
x = (x2 +x1)/2 ? (a1 /(2 a2)).
32
????p??? ?????? ???????
1. x2 = x1+?, x1 ? ???????? ?????, ? ? ??? (p??. 8, ?).
2. f(x1 ), f(x2 ).
3. ???? f(x1 ) > f(x2), ?? x3 = x1 +2?, ????? x3 = x1 ??.
4. f(x3);
??p?????? fmin = min{ f1, f2, f3 }, ??????? ????p i-? ????? ? ????????
xmin = xi.
5. ?? x1, x2, x3 ???????? x (?? ????????? ????????????? ??p???).
6. ?p???p?? ?? ????p?????:
|fmin ?f(x)| < ?1 ? |xmin ? x| < ?2, ?? ?????????? ????p????. ? ????????? ?????? ??????? ? ?. 7.
7. ????p ?????.
????p??? ?????? ????? (??, ? ????p?? ?????? ???????? ???????)
?? ????? (xmin ??? x ) ? ??? ????? ?? ??? ???p??? ?? ???, ????p??? ?? ?
???????????? ?????????????????? x1, x2, x3 ? ??p?????? ? ?. 4.
?p??????? ??????? ????????? ?????? ??? ?????????? ?p?????????
?p??? ??????? ?????????? ????p????? ? ????? ?p???? ????? ?????????? ??????? ???????? ?????????? ????? ?????????, ????? ?????
???????? ???????, ?????????, p??????p???? ??????.
??? ?????????? ??????? n ?????? ????????? ? ???????? ???????
????? ????????? ?? ?????????????. ??? ??????? ??????? ????p?? ??????????? ????? ???????, ?? ??? ????p? ???????????? ??????? ?? ????????? ??????? ?????????? ????p?????. ????????? ??????
?p?????????? ?????????????? ???????. ? ????? ?????? (???? ??? ??
??????????? ??? ?? ????? ???? ????? ?p???p???) ????p??? ??????? ??
?????. ???????? ???????? ????????? ????? ???????? ???????.
2.2. ???????? ?????
? ?????????????? ?p????????? ????????p????? ???????
???? ??????? ?????p????p????, ????? ???????? ?????????????
??????.
????? ???????
???? ????? ??????? ?? ????p??????? ???p????????? ??????? f ?
????? x. ??? ????? ????p??????? ??????? x, ? ??????
q(x) = f(xk )+f?(x )(x?xk )+1/2f?(xk )(x?xk)2,
33
?) f
?)
x1
?)
x3
x2
f
xmin
x
?)
x (2)
x 0 xk
x k+1
x
x (2)
4 1)
x
x
(1)
x
(1)
(3)
x (3)
???. 8
?q
= 0 , ?. ?.
?x
f?(xk )+f?(xk )(x?xk ) = 0,
????p???? ??p????????? ?? ???????,
??????
f '( xk )
xk+1 = xk? f ''( x ) ,
k
?q
=0.
?p???? xk+1 ??p?? ? ?????, ???
?x
??????????: ????? p?????????, ???? ????????? ????? ?p???? x 0
(p??. 8, ?).
????? ??????? ????p???? ???????
????? ?? ?????? ???p???? ?p??????? ?????? ???? ??????????
?p????????? (? ?????? ??? ????????????? ?p????????? ?p??????? ???
?????????? ???????).
????????
1. xk = 1/2(ak +bk).
2. f?(xk ) > 0, ?. ?. ??????? ???p?????? ? ????? ???????? ?? ?????
???? ?p???? xk.
????? ???????? ???p?????????
??????? ???p??????p????? ????????? 3-?? ??p????, ?? ???????????? ?????? ??? ????? (? ?? 3), ??? ??? ? ?????? ????? ????? ????????? ???????? ??????? ? ?? ?p?????????. ???? ????? ????? ???????34
??? (?? ?p??????? ? ?p?????????). ? ??????, ???? ?p????????? ??????? ????????????, ?? ???? ??? ?????????? ?? ?????? p?????????
??p???, ?? ?p?????????? ???? ?????? ?????? ???????.
2.3. ???????p??? ????? ??? ????????????? ?p?????????
????? ???p?????????? ??? ?????? ?????????? ????? ?????????????
??p?????? ??? ?p????????? ??????? ???????. ??? ??????????? ????????? ??????? (? p??p?????) ????? ?????????????? ?? ?????? ????????????? ???????? ??????? ? ?p????? ??????. ?p?????? ? ???? ??????? (?? ????? ?p??????? ??????), ???? ???? ???p????? ? ???, ??? ????? ?p????? ???? ?p??????? ??????, ????? ????? ??p??? ?????????
????p??? ????????? ?p?????. ?p??? ????, ????? ?? ??????????? ???????? ???????????? ??p????? ?????????? ? p??????. ??? ?????? ????? ???????? ? ??????? ?p????? ??????.
?p??? ??? ??????? ???????? ? ??p??? ???p???:
? ????? ?? ????????? (?? ??????p??????) ?????p??????;
? ????? ???????????;
? ????? ??????????? ??????????? ???????.
??p??? ??? ?????? ???????? ?? ??p?????????? ????p???????, ????????? ? ?? ???p????????? p??????????.
????? ?????? ?? ?????????
???????? ? ?p???????? ???????? ??????p????? ?p? ?????? ?????
????p???? (n = 2 ? ?p?????????, n = 3 ? ???p???p). ???????, ??? ??????
????? ?? ???? ?????? ? ??????????? ??????? ? ????????
?p??p????p??????.
???? ? ????p? ??????? ????? ? ?????? ???????? ??????? ? ??p???????
??????, ???p???p ? ?????? ? ????? ??p???????? ?? ???? ????? (???????
? ????p? ????p???), ? ???????? ????????? ????? ?????????? ?????????, ?????? ??????? ???????? ????? ???????.
?????????? ????? ????? ???????? ?????????? ????????
(p????????????? ??p????). ? ?????? ???? ?????????? (?????????) ?
??? ?????????????? ???????????, ? ?????????? ???????????? ? ???????? (???. 8, ?, ?).
???????? ?????????? ? ?????????? ??????????? ????????? ? ???????????? n ?????????? (????? ???????? ?????????? ??? n ? 6). ???
???? ???????????? ???????, ??????? ????????????? ?????????? ???????? ???????. ??? ??????? ???????????? ????? ????? ??????? ??????35
??? ?????? ? ????? ?????, ??????? ????? ???????? ?????? ?????????
????????, ? ??????????? ?? ??? ???, ???? ?? ????? ??????? ????? ????????, ???? ?? ???????? ??????????? ???????? (???????? ?? ???? ??? ?????
??????????). ? ???? ??????? ???????????? ??? ????????? ???????.
1. ?????????? ????? ????????.
???? ???????, ??????? ????????????? ?????????? ???????? ???????
??? ????????? ?? ?????????? ????????, ?? ?????? ??? ???????????? ???????, ??????? ????????????? ????????? ?? ???????? ???????? ???????.
2. ??????????? ????????.
???? ????????? ??????? ?? ??????????? ?? ?????????? ?????
M = 1,65n+0,05n2 ????????, ?? ?????????? ????????? ??????? ????????? ? ????????? ????? ????????, ?????? ? ???????? ??????? ????? ?
??????????? ????????? ???????.
3. ????????? ??????.
?????????? ??????, ???? ??????? ????????? ??? ???????? ?????
????????? ??????? ? ???????? ?????????? ?????????? ????.
?????????? ?????? ???????? ?? ???? ????? ??????????:
? ????p????? ????????? ?p? ???????? ??????? ????? x(0)
?? x (0)
j + ?1 ,
i
x ( ) = ? (0 )
?? x j + ?2 ,
j ? i,
j = i,
i, j = 1, n,
(?????p ???p????? ????????? n ??p??? ?????????),
(n + 1) + n ? 1
n +1 ?1
a;
n 2
n 2
a ? ?????????? ????????? (?p? a = 1 p??p? ????????? ?????);
?????? ???p????? ??p??????? ?????.
????? x(j) ?????, ?????????? ?????????. ????p ??????? ????????? n
??? ?1 = ?1 (n, a ) =
????? p????????? ? ????? x c =
a; ?2 = ?2 ( n, a ) =
n
? x( j ) / n , i ? j.
i =0
????? ?p????, ?p???????? ??p?? x(j) ? x?, ???????? ??p????? x =
(j)
=x +? (x? ? x(j)).
?p? ? = 0 ??????? ???????? ????? x(j), ?p? ? = 1 ???????? ????? x?,
?p? ? = 2 ???????? ????? ???????.
j)
j)
.
????? ???????, x (???
= 2 x c ? x (????
36
??????????? ?????p? ? ????
?p? ??p?????? ????????? ????????? p????????? ??? ?????? ??
?p???? x = x(h)+ (1 + q) (x? ? x(h)), ??? x(h) ? ???p?????? ??p???? ? ???????????? ????????? ??????? f(x).
?????? 3 ??p????p??? ??p????: x(h) ? ????????????? ?????????????
???????? ???????; x(g) ? ????????????? ?????????? ?? ???????? ???????? ???????; x(l) ? ????????????? ??????????? ???????? ???????;
????? ?p? ??p????p? : ?, ?, ?. ????????? x(r) ? ??p??????? ??p????
(?????); f (r) ? ??????????????? ???????? ???????.
?????????? ? ?????? ??????????? ?? ????????? ?p?????? :
?) ??p??????? ??p??????: f (l) < f (r) < f (g), ? = ? = 1 (p??. 9, ?);
?) ?????? (???? ??????? ????? ????p? ??????p??????, ????? ????
?????)
f (r ) > f (g), f (r) f (h), ? = ? = ?0, 5;
f (g)< f (r) < f (h), ? = ? = 0,5, (p??. 9, ?, ?);
?) p?????????
f (r) < f (l), ? = ? = 2, (p??. 9, ?).
????p???
??? 0: ??????? ?, ?, ?, ?????????? ???p???? ? ????????? ?????.
??? 1: ??p??p?????? ???p????? ??p??? ????????? ?????????.
??? 2: ?????????? ???????? ??????? ?? ???? ??p?????.
??? 3: p????p?????? ???? ??p??? ?? ????????? ??????? ? ????p
?p?? ??p???: x(h), x(g), x(h).
??? 4: ?????????? ???p????? ????p????.
??? 5: ?????????? ???p???? ??p?????? (? ?????? ?????? (?), (?),
(?)).
?)
x (h)
x (r)
xc
?)
x (h)
Z
xc
?)
?)
x (h)
xc
Z
x
(r)
x (h)
???. 9
xc
Z
x (3)
37
??? 6: ?????? ??p???? x(h) ?? ?????? ? ??????????? ???????? ??????? ? ???? ?????, ????? ?????? ????? ????????? ???????????? ???1
?????? ??p???? x(l), ?. ?. x(i)= (x(i)+ x(l)), i ?l.
2
??? 7: ?p???p?? ?p???p?? ?????????.
???? ???? ?p???????? ? ???? ????????? ???p???? ??????, ?? ??p????
?? ??? 2. ???? ???? ???????? ????????? ??p????, ?? ?? ??? 3.
?p???p: min f(x) = (1?x1)2 + (2?x2)2;
x(0) = [0, 0]T ? ???????;
3 +1
3 ?1
a = 1,93 ; ?2 =
a = 0,517;
2 2
2 2
x(1) = [0,517, 1,93]T ; x(2) = [1,93, 0,517]T ; f(x(1)) = 0,237; f(x(2)) = 3,065.
??? ??? f(x(0)) = 5, ?? ???? ??p????? ????? x(0).
?1 =
x? =
1 (1) (2)
(x + x ).
2
j)
g)
(????????????? ??????????? ?????????),
????????? x(???
= 2xc ? x(????
(3)
(1)
(2)
(0)
?????: x = x + x ? x = [2,449, 2,449]T ; f(x3) = 2,3, ?. ?. ???????
???????.
????? ?????? ???????????
????????? ??p??????? ????? ??????????? ?????p??, ??p?????????
??????p?? ???p??????? ??????, ????????? ? ??? ????p ?????????? ???? ?.
????? ????p???? ??p?????? ??????, ?? ????p?? ???? ??? ?????????
???p??????? ?????????? ?? ?????? ???p???? ????? ???????
???p????????? ???p??????? ? ?p???p?????? ??p???????? ??p???????.
????? ??p????p????? ??????????? ?p???????? ?????? ?? ???? ???????
????????? ???????, ?????????? n ??????????? ???p??????? (n ?
p????p????? ?????p? x). ?p???????? ??????????? ????????? ??p???????,
?p???? ?????? p?? ???????? ?????? ???? ??p???????. ????? ???????
???p??????? ?????????????? ????? ???????? ? p????????? ??????????? ??????? ????? ??p???????.
? ?????? ?????p??????? ????? ?p???? ????? ???????? ????????????. ????? ? ??????? ???? ?p???????? ???????????, ????????? ? ?????? ????p?????, ?????????? ?? ?p???????? ???p?????, ? ?????
?p??????? ????? ? ???p??????? d(i)= x(i)? x(i?1) (p??. 10, ?).
?p?????p? ?p?????????? ????? ?????????? ???????????? ??????
(????????? ??p????p? ?????????? ????????? ??????? ? ???p???????
38
?) x
2
?)
x (1)
x2
x (2)
d (2)
x (2)
x (1)
x1
x1
???. 10
????? ???p????) ? ??????????? ?????????? ??p??????? ?
????p???????? ?????? ?? ??p???? (???????? ?? ???p?????) (p??. 10, ?).
1. ??????????? ?????.
?p????? ??????? ???????? ????, ???????? p???????? ??? p?????
???p???????, ? ???????????? ? ?p?????? ??????. ????? ?????????? ?
??????p?? ???????? ?????. ???? ???????? ??????? ??????? ? ?????
????? ?? ?p??????? ???????? ? ???????? ?????, ?? ??? p??????p???????
??? ????????, ????? ???? ??p?????? ? ???????? ????? ? ??????? ??? ?
?p????????????? ???p???????. ?p? ??p???p? ???? n ???p????? ??????????? ????? ????p??????. ?????????? ? p????????? ????? ????????
???????.
2. ????? ?? ??p???? (?????????? ???p???????).
??????????? ? p????????? ?????? ???? ?? ??????? ????? ?????
+
?p????, ??????????? ??? ????? ? ?????????? ??????? ?????? x (pk 1) =
=x(k)+( x(k) ? x(k-1)) (?????, ??????????? ??? ???????? ?? ??p????).
???? ???????? ?? ??p???? ?? ?p?????? ? ?????????? ???????,
?? x (pk +1) ?????p????? ? ???????? ?p??????? ??????? ????? ? ?????
?p???????? ??????????? ?????. ???? ? p????????? ?????? ??????????
????? ? ??????? ????????? ???????, ??? ? ????? x (k) , ?? ???
p??????p??????? ??? ????? ??????? ????? x(k). ???? ??????????? ?????
????????, ?????????? ??p?????? ? ????? x(k) ? ?p?????? ???????????
????? ? ????? ????????? ?????? ??????????? ???????????. ???? ????? ????? ?? ?p?????? ? ??????, ????????? ????????? ???????? ???? ?
??????????? ??????????? ?????. ????? ???????????, ????? ????? ????
?????????? ?????????? ?????.
???????? ???????????
????? ??????; x? ? ????? ????????? ???? ???p?????
?????????:
?
(???????); x ? ????? p????. (p??. 11, ?).
x? ?
39
??? 0: ??????? ????????? ????? x? = x0 ? ??p???????? f(x? ).
??? 1 : ?????p????? ????? x?, ? ????p??, ???? f(x? ) < f(x? ) ? ?????.
??? 2 : ???? ????? ?? ??????, ?? ?????????? ????. ???? ??? ??????
?p??????? ???????????, ?? ?????????, ????? ??p???? ? ???? 1.
??? 3 : (????? ?? ??p????) ???? ????? ??????, ?? ??p?????? ?????
p???? x? = x? + (x? ? x? ) = 2x? ? x?. ?? ????? x? ?????????????? ??????????? ????? x?. ???? f(x? ) < f(x?) ? ?????.
??? 4 :???? ????? ??????, ?? x? = x? ;x? = x?, ??p???? ?? ??? 3.
??? 5 :???? ????? ????????, ?? ??p?? ?? x? ????????? ??????? ?????, ????????? ??? ? ???? ?? ??? 1.
???????. ????? ????? ???????? ??????? f(x) = 8 x12 +4x1x2 +5 x22 ,
????????, ??? x0 = [ ?4;4]T; ?x = [1;1]T ???;? = 2 ? ???????????
?????????? ????; ? = 10?4.
??????????? ??????:
? ????????? ????????? ????? ?????, ???????? ???????;
? ?p??? ?????? ??????? p????? ?? ????? ??p??????? (??? ?p????????? ??????? t ? ?(n).
??????????:
? ??????????? ????? ?? ????????? ????? ???p??????? ????????
??????? ? ????? ??????????? (p??. 11, ?). ?p? ???? ????????p????
?????p??? ????? ?? ?p???? ????????? ?????;
? ?????? ???????? ???????? ???????? ???????????.
????? ???????
????? ???p??????? ???p??????? ??????? ? ??? ???????? ??????????? ????? ?p????? ??????. ????p?????, ?????????? ?? ?p????????
???p?????, ???????????? ??? ????p????? ?????p?? ???p??????? ??????. ????? ?p?????p???? ?? p?????? ????? ? ????p???????? ????????
?????????. ???? ???? ?? ??????? ????????, ??? ??? ????? ??????? ?
??p???????? ???????? ????? ???? ???p??????p????? ????p???????
????????.
???? ????p???? ??????????? ? ???, ??? ???? ????p??????? ???????
n ??p??????? ?p??????? ? ???? ????? ?????? ????p????, ?? ???????
????? ???? ?????? ? p????????? n ??????p??? ??????? ?? ?p???p????????? ???p???????? ???p????????. ?p?????p? ?p???p????????
1
????p??????? ??????? q(x) = a + bTx + xTCx ? ???? ????? ??????
2
????p???? ???????????? ?????????? ????? ???p??? ?p???p???????? ?,
40
????p?? ?p?????? ???p??? ????p??????? ??p?? ? ????????????? ????.
????? ??p????, ????p??????? ??p??: Q(x) = xTCx ?p???p????????? x = Tz
?p???????? ? ???? Q(z) = zTTTCTz = zTDz. ?????? ???p????? x ?
??????p???? ??????? e(i) ???????????? ???p?????? z ? ???????, ???????? ?????p??? tj (??????? ?). ?p??? ????, ??????? ?????p?? tj ????????????? ??????? ???? ????p??????? ??p??. ??????p??? ????? ?????
???????? ?p???p?????? z, ???????????? ?????? ????? ?????? ?? ??????? ???? ????p??????? ???????, ?. ?. ????? ???p???????, ????????
?????p??? tj.
1
?p???p: f(x) = 4 x12 +3 x22 ?4x1 x2 +x1 ? min x1 = z1 + z2 , x2 = z2 ???
2
1
1
x=
2 z;
0 1
1
f(z) = 4z12 + 2z22 + z1 + z2 .
2
?1?
? 1/ 2 ?
????? x0 = [0, 0]T; t1 = ? ? ; t 2 = ?
?.
?0?
? 1 ?
1. ????? ? ???p??????? t1
1
1
x(1) = x(0) + ? t1, ? = ? ? x(1) = ( ? , 0)T.
8
8
????p? ?? ????? x(1) ?p???????? ????? ? ???p??????? t2.
1
3
1
??????? ? = ? ? x(2) = [ ? , ? ]T.
8
16
8
????????? n (????? n = 2) ??????p??? ??????? ????? ??????? ?? n
???p??????? ???p??????? tj.
???? ?, ????? ????? ? (?. ?. ???p??? ??????????? ?????p?? ??? ?),
?? ?? ????? ???????????? ?????? ???????? ??????? f(x), ??? ??? ???p???
? ??????????.
??????? ???p??????? tj ????? ????? ?? ?????????? ????????
????p??????? ???????.
???? ?????? Q(x), ??? ????? x(1), x(2), ???p??????? d (p??. 11, ?),
????? ????? y(1)????????p??? Q(x(1)+?d), ? y(2) ????????p??? Q(x(2) + ?d)
? ???p??????? (y(2) ? y(1)) ???p????? ? d. ????? ????? ???p???????
y(2)? y(1)???????????? ?????????? ????? ????????.
?? ?p?????? ??? ????????? ???p???????? ???p??????? ?? ??????
????? ? ??????p?? ???p???????, ? ?????????? ???? ????????? ????? ?
????????? ?????p? e(1).
41
?) x
2
?) x
2
1
4
5
5'
2
3
6
3'
x1
x1
?)
?)
x (1)
y
d
x2
(1)
x (2)
y
e (2)
x (2)
x (3)
e (1) x (1)
x1
(2)
???. 11
1
0
1
2
????? e ( ) = ?? ?? , e ( ) = ?? ?? . ??????, ?(0) ??????????????? ??????0
1
? ?
? ?
?? f(x(0) +?(0) e(1) ), ? ??????? x(1) = x(0) + ?(0) e(1).
????? ?????? ?(1), ??????????????? ???????? f(x(1) + ?(1) ?(2)), ? ??????? x(2) = x(1) + ?(1) ?(2) (p??. 11, ?). ????p? ???????? ?(2), ????????p??
f(x(2) + ?(2) e(1)) ? ??????? x(3) = x(2) + ?(2) e(1). ????? (x(3) ? x(1)) ? e(1)
???????? ???p???????? (???????? ????p??????? ???????). ????p?,
???? ????????? ????? ? ???p??????? (x(3) ? x(1)), ?????? ???????.
????p???
??? 1: ?????? x(0) ? ??????? n ??????????? ???p??????? s(i)=e(i), i = 1, n .
??? 2:????????p????? f(x) ?p? ???????????????? ???????? ?????
(n+1) ???p???????. ?p? ???? ?????????? p???? ????? ???????? ??p????
? ???????? ????????, ? ???p??????? s(n) ???????????? ??? ?p? ??p???,
??? ? ?p? ????????? ??????.
??? 3:??p??????? ????? ???p??????? ???p???????.
??? 4:???????? s (i) ?? s (2) ? ?. ?., s (n) ???????? ???p???????
???p????????, ??p???? ? ???? 2.
?p???p: f(x) = 2 x13 + 4 x1 x23 ? 10 x1 x2 + x22 , x(0) = ( 5, 2 ) T, f( x(0) ) = 3,14
??? 1: s(1) = ( 1, 0) T, s(2) = ( 0, 1) T.
??? 2: ?) f( x(0)+?s(2)) ? min , ?????? ?*= ?0,81, x(1)= ( 5, 2 ) T ? 0,81(0, 1 ) T,
f( x(1)) = 250;
42
?
?) f( x(1)) + ?s(1) ) ? min , ?????? ?* = ?3,26, x(2)= ( 1,74, 1,19)T, f(x(2)) = 1,1;
?
?) f(x(2) + ?s(2)) ? min , ?????? ?* = ?0,098, x(3) = (1,74, 1,092 T, f (x(3)) = 0,72.
?
??? 3: s(3) = x(3) ? x(1) = (?3,26, ?0,098) T, s(3) =
s(1) = s(2), s(2)=s(3).
s(3)
s (3)
(?0,9995, ?0,03) T,
??? 4: ????? ? (????? ???p???????? ???p???????) f(x(3)+ ?s(3))? min ,
?
?????? ?* = 0,734, x(4) =[1,006, 1,070] T, f( x(4) ) = ? 2,86; x(0) = x(4), ??p????
?? ??? 2 (??? ??? f ? ?? ????p???????, ?p??????? ???p????).
2.4. ?p????????? ??????
?p? ????????????? ???? ????? ??????????? ?p???? ??????? ?????? ?p??????? ?????? ??????? ?????????? ?????????? ???????? ???????. ??????????? p?????????? ??????????? ?????????? ????????p???
????? ? (?f( x ) = 0), ?. ?. ????????? ??????, ???????????? ????????
?p??????? ??????? (??? ????????, ? ?????? ???p?p??????? f(x), ?f(x),
?2f(x)).
? ?????? ????? ???p???????? ????? (??? ??? ?f(x) ? ?????????? ??????? x)
x(k+1) =x(k) +s(x(k)),
??? ? (k) ? ??? ??p????????? ? ?p?????? ????????? ??????; s(x)???p??????? ?????? ? n-??p??? ?p???p?????? ??p??????? x.
????? ????
????? ?????????? ???p??????? ??????p?????? ??????, ?. ?. ??????????? ?????????? ???????? ???????. ????? ?????? ????? ??? x(k+1)=x(k)+
+ ?f(x(k)), ??? ??? ??????? ????p?? ????? ??????? ? ???p???????
?????p???????.
??p???????
?????? ??????
f(x) = (x1 ? 2)4 +(x1 + 2 x2)2 ?min, x(0) =(0, 3) T ??????? ????.
?????: x =(2,00, 1,00) T.
??????????? ?????? ???????? ?????? ???p???? ??????????, ??? ???
????????? ??p??????? ??????? ?? ???????? ?p???????, ????p??
?p????????? p???? 0 ? ??p???????? ????? ????????.
43
??????????? ??????
1. ????????????, ??? ??? ????? f(x(k+1))?f(x(k)) ?????? ?p? ??????????
????? ?.
2. ?? ??????? p?????????? ?? ????? ???????? ????????? ????????? f(x). ??????? ????? ???????????? ??? ????????? ??p???? ????????? ?????.
???????
1. ??p??????? ????-????? ????p????.
2. ?????? f(x) = 8 x12 + 4x1 x2 + 5 x22 , ???????? ??? x(0) =[10, 10], x* = [0, 0],
( )
k
?f x ( ) ? 0 ? ?p???p?? ????????.
????? ???????
???? ??????? ????p??????, ?? p?????? ??????? ??????? ??????????? ?? ???? ???! ????? ???? ???????? ??????????, ????? ????? ?p????
? ??p??????? (????? ?????p?????? ?p?????? ? ????? ????????). ? ????? ?????? ????? ?p?????? ????p????? ? ???p?? ?p?????????.
???????p?? ????p??????? ???p??????p????? ??????? f(x) ? ?????
x(k)
1
f (x, x(k)) = f(x(k))+ ?f(x(k))? ?x + ?xT ?2f(x(k))?x.
2
??????? ?p?????? ?? ????? ?????? p????????. ????? ?? ????? ?????????? ????? x(k+1) ?p?????? ???p??????p????? ??????? ??p???????
? ????, ?. ?.
? f (x, x(k))= ?f(x(k))+ ?2f(x(k))?x = 0.
?????????? ?p??????? p???? ???????????? ?x
?x = ??2f(x(k))?1 ?f(x(k)).
????????, ??? ?x = x(k+1) ? x(k), ??????? ???p???????? ??p???? ???
?????? ???????
x (k+1)=x (k) ? ?2f(x (k))?1 ?f(x (k)).
?p???p: f(x) = 8 + 4x1 x2 + 5 ? min;
16 x1
?f ( x ) = ??
? 10 x2
4 x2 ?
16 4 ?
; ?2 f ( x4 ) = ??
?;
?
4 x1 ?
? 4 10 ?
x(0)= (10, 10)T
44
1 ? 10 ?4 ?? 200 ? ? 0 ?
?
??
? = ? ? ? ??????????? ?????.
144 ? ?4 16 ?? 140 ? ? 0 ?
?? ???p???????? ??p???? ???????, ??? ??????? ??????? ?? ???p????
? ???p????, ???? ? ?f( x )T ?2f( x )?1 ?f( x ) < 0, ??? ???????????, ????
???p??? ????? ? ????????????-??p???????, ????? ? ?2f?1 ? ?? ?? ???????????? ??p???????, ?. ?. ????? p??????? ? ??????, ???? f(x) ??????? (????).
????????? ???????????? ????p??????? ?p?????????, ?? ???? ???
????p?? ????????? ????????? f(x) ??? ????? ??p????????? ???p??? ????? x(k), ?? ????? p??????? ?????.
x(1) = (10, 10) T?
?????????? ??????????? ????????
??? 1. ?????? x(0), M ? ???????????? ?????????? ????????, N ?
?????????? ??????????; ?1 ? ???????? ?????????? ?????????; ?2 ? ???????? ?????????? ??? ?????? ????? ??????.
??? 2. ???????? k = 0.
??? 3. ?????????? ?f(x(k)).
??? 4. ??????????? ?? ||?f(x(k))|| ? ? ?
?? ? ?????? ??????????? : ?????????; ??????? ? ???? 13.
??? ? ??????? ? ?????????? ????.
??? 5. ??????????? ?? ??????????? k ? ??
?? ? ?????? ?????????? ???????, ??????? ? ???? 13.
??? ? ??????? ? ?????????? ????.
??? 6. ????????? s(x(k)).
??? 7. ??????????? ?? ?f(xT(k))s(x(k)) < 0?
?? ? ??????? ? ???? 9.
??? ? ???????? s(x(k)) = ??f(x(k)), ?????? ???????? :????????? ??????????? ???????? ? ???? 9.
??? 8. ????? ????? ?(k), ??? ??????? f(x(k))+?(k)s(x(k))?min (????????? ???????? ?2).
??? 9. ???????? x(k+1) = x(k)+?(k)s(x(k)).
??? 10. ??????????? ?? f(x(k+1))<f(x(k))
?? ? ??????? ? ???? 11.
??? ? ?????? ?????????? ??????:??? ?????????? ????????, ??????? ? ???? 13.
??? 11. ??????????? ?? ||?x||/||x(k)||??1?
?? ? ?????? ?????????? ??????: ??? ??????????? ? ????????, ??????? ? ???? 13.
45
??? ? ??????? ? ???? 12.
??? 12. ???????? k = k+1.??????? ? ???? 3.
??? 13. ???????.
????????p??????? ????? ???????
??????????? ?????? ??????? ??????? ? ?????????.
1. ???????????? ??p???? : x(k+1)=x(k)? ?(k) ?f(x(k)) ?f(x(k)), ??? ?(k) ????, ????? ??p????p?????, ??? f(x(k+1)) ? f(x(k)),
p??? ?? ??????? f(x(k+1)) ? min
k
?( )
?. ?. ?????????? ?????????? ? ?????? ??????p??????? ???????.
2. ???? f(x) ?? ??????? (x(k) ? ???????? ?????), ??? ??p????????? ?
?p?????? ???p???? ?? ????? ??????????? ???????? ???p??? ????? ?
???????? ???p??????? ?????? d (k) ??p?? ?????p, ?????????p?????
??p???????? d(k)?2f(x(k)) d(k) < 0, ??? d(k) ? ???p??????? ??p??????????
?p??????.
?p???p
1 0?
?2?
(k)
????? G?(x(k))= ?2f(x(k)) = ??
? ; ?f(x ) = ? 5 ? , ????? ??????????
0
5
?
?
? ?
2
?
?
?
??? ???p??????? d(k)= ? 5 ? ?p?????? ? ???????? ????? ??????? f (k) +
? ?
1
+?f (k)?x + ?xT?2f?x, ??? ??? ??????????? ???????? ?2f(x) ????????2
?? ?? ????? (?2 < 0, ?2 > 0). ??? ?????????? ???p?? ???? ? ?p????????
?f, ?. ?. ????????? ? ???p??? ???p??????? ???????.
????? ???????? ??????????? ???????? ???p??? ?2f(x) ?? ????????,
????? ???p???????? d (k ) ????? ?????p, p????? ?? ?????
??p????????????, ?? ???p???????? ? ?p????????????? ???p???????,
?. ?. ? ???p??? ???????? ???????. ?p? ???? ??????? ???????????
?????????? ????????? ???p??? ???p?? ?p?????????:
?1 0?
k
G(k) = ?2 f ( x ( ) ) = U ? UT = ? 0 5 ? ,
?
?
??? ? ? ???????????? ???p??? ? ??????????? ???????????? ??????????; U ? ???p??? ?? ??????????? ?????p?? G(k). ???????, ??? d(k) ?????????? ???p?? ???? ? ?f(x(k)), ?. ?. ????????? ? ???p??????? ???p???????
???????, ? ?????p d (k ) ? ? ???p??? ????????.
46
????? ??p???p???
????? ?????? ???????? ????????????? ???????? ????? ??????? (????? ???? ? ???????): ??p??? p??????? ?????, ? ???p?? ?????? ?????
????????.
???p??????? ?????? ??p????????? ?????p?? s(x(k)) = ?[G(k) + ?(k)I]?1 ?f(x(k)).
??p????p? ?(0) ?p????????? ??????? ????????, ???p???p 104, ???,
1
I , ??????? ??????? ?????????
? (0 )
????????????? ???p??????? ??????p?????? ?????? (??f(x(k))). ?p? ?????????? ? ?? 0 ???p??????? s(x) ?????????? ?? ???p??????? ???????.
???? ????? ??p???? ???? f(x(1) ) < f(x(0)), ?? ??????? ???p??? ?(1) < ?(0)
? ??????? ????????? ???, ??? ? > 1, ? ????? p?????????? ?p????????
???.
??????????? ??????: ??????? ???p???? ?????????? ? ?????????? ????????????? ?????? ????? ??????.
?????????? ??????: ?????????? ????????? ??????? G(k) ? ??????
??????? ???????? ?????????. ?????? ????? ???????? ????? ???????????? ? ??????? ????
??? [G(0) + ?(0) I]?1 = [?(0) I] ?1 =
f (x) =
m
? (?( x, ti ) ? ? i )2 ? min,
x
i =1
??? ? i ? ?????p??????????? ??????.
????? ???p??? ????? ????? ???? ???????? ?p? ????????????? ?????? ??p??? ?p?????????, ? ?????? ?????????? ?????? ??p????p? ?f(x) ?
?2f(x).
? df ?
????? I ( x ) = ? i ? ? ???p??? ????? ??? f1(x), ? Gi(x) ? ???p??? ?????
? dxi ?
??? f1(x), ????? ??p?????? ??? ?p??????? ??????? f ? ?? ???p??? ?????
g(x) = IT (x)f(x), G(x) = IT(x)I(x) +Q(x),
??? Q ( x ) =
m
? f i ( x )G i ( x )
? ?p?????? ???p???? p??? ??? ?????? ?????-
i =1
????? ??????p?????.
????????? ?p? Q k ?0
f k ? 0 ? ???? ??? ????? ??????
???p????????? ???????, ?0(xj t ) ????? ???????? ? i .
? ???? ?????? ???????????? ????? ????? ???
47
( I?k Ik + Qk )dk= ? I?k fk,
??? dk ? ???p??????? ???????.
?p????p???? Q, ???????? ????????? ???p??????? ?????? d k = ? ( I?k Ik) ?
???p??????? ??????????????.
????? ????? ????????? ????p??????? ???p?????? ??????????,
??????p? ?? ??, ??? ?p? ??????????? ???????????? ?????? ??p???
?p?????????. ? ???????? ?????????? ?????? ????? ????????, ??? ?????
??????????????? ???p??? I?k Ik p???? ????p??? ????? ???????????????
???p??? Ik (?. ?. ???????? ?p??????? ?p? ??p?????? ???p???).
2.5. ?????? ???p??????? ?p????????
??? ?????? ????????? ? ?????? ????p?????, ? ?????? ????p?? ?????
????p????? ???p??????? ???p???????. ??? ??? ??????????, ??? ????????? ???????? p?????? ????? ? ????p???????? ???????? ????????? ?p???p?? ?? n ????? (????p?????? ??????????).
???????p??????? ????? ??? ????????? ???p??????? ???p???????
?????????? ????p??????? ???p????????? f(x) ? ???????? ?????????
?p???????, ?p???? ?????????????? ???????? ??????? ??????? ??
???p???? ? ???p????.
????, ?p????????????, ???
f(x)=q(x)=a + bT x +
1 T
x Cx;
2
x(k+1)=x(k) + ?(k)s(x(k)).
???p??????? ?????? ?? ?????? ???p???? ??p????????? ??
k ?1
s(k) = ?g(k) +
? ? (i )s(i ) , s
= ?g(0),
(0)
i ?0
??? g(k) = ?f(x(k)).
?????, ??? ????? ???p??????? ??????p?????? ?????? ???????????
????? ?????????? ? ???? ? ?????????????? ??????????????
???p???????, ???????????? ?? ?p???????? ?????.
???????? ? (i) , i = 1, k ? 1 ????p????? ???, ????? ??? ???? ? ?
???p????? ?? ????? ????p??????? p???? ???p????????? ??????. ??
?p????????? ???????, ???
s(1) = ? g(1) + ?(0) s(0) =?g(1)??(0)g(0).
48
????????? ??????? ???p????????? s(1) ? s(0), ?. ?. s(1)TCs(0) = 0, ??????? [g(1)+ ?(0)g(0)] C s(0) = 0.
?x
????????, ??? s(0) = (0 ) ? ???????? ????p??????? ???????
?
?g = g(x(1) ) ? g(x(0) ) = C?x
(??? ??? g(x(0))= Cx(0)+ b; g(x(1)) = Cx(1)+ b), ????? [g(1)T + ?(0)g(0)] T ?g = 0,
?????? g (1)? g (1) + ? (0)g (0 )? g (1) ? g (1)? g (0) ? ? (0 )g (0 )? g (0 ) = 0 .
????????, ??? ? ???????? ?p???p?? ????????? ??????p???? ??????
????? ??????? ?? ??????????? ???????????, ???????????? ???????
g(k+1)Tg(k) = 0 (??????????? ????????? ? ????? k+1 ??????????????? ??????????? ????????? ?? ?????????? ????, ?????????
d
f ( x ( k ) + ?s ( k ) ) = 0 ? ????? ????????? ??????, ?. ?. s( k )T g ( k +1) = 0 ).
d?
? ???? ??????????, ???????????? ????????? ?????? ?, ?????????????:
? (0) =|| g (1) ||2 / || g (0) ||2 .
????? ???????????? ????????? ??????????? s(2) ? ?. ?. ? ????? ??????, ??????????? ???????????, ???????????? ??????? ??????????????, ????? ???
s( k ) = ? g ( k ) + ?|| g ( k ) ||2 / || g ( k ?1) ||2 ? s ( k ?1) , ? (i ) = 0, i = 0, k ? 2.
?
?
?????? ????????? ? ( k ?1)s( k ?1) ? ??????? ? ??????????? ????????????? ?????? ??????????? ?????? ??????????? ????.
???????, ??? ????? ?????????? (????????? ??????? ?? ??????) ????????? ???????????? ??? ??? ??????? ????? ??????? ???????????.
??????
T
f ( x ) = 4 x12 + 3x22 ? 4 x1 x2 + x1 ? min, x (0) = [0,0] .
??? 1: ?f ( x ) = [8 x1 ? 4 x2 + 1,6 x2 ? 4 x1 ]T ;
s (0) = ??f ( x 0 )2 = ? [1,0] .
??? 2 : ???????? ?????
T
1
x (1) = x (0) ? ?(0)?f ( x (0) ) ? ?(0) = ;
8
1
1
x (1) = (0,0)T ? (1,0)T = ( ? ,0)T .
8
8
49
??? 3 : k=l
T
s
(1)
1
1 1
|| g (1) ||2 1
? 1?
= ? ? 0, ? ? (1,0)T = ( ? , ? ), ? (0) = (0) 2 = .
4
4 2
4
|| g ||
? 2?
??? 4 : ???????? ?????
1
x (2) = x (1) + ?(1) S (1) ? ?(1) = ;
4
T
1
1 1 1
? 3 1?
x (2) = ( ? ,0)T ? ( , )T = ? ? , ? ? .
8
4 4 2
? 16 8 ?
?f ( x (2) ) = (0,0)T , ????? ???????, ?(k) = ?*.
?????? ????? ????????? ?
?(k ) =
?g ( x ( k ) )T g ( x ( k ) )
|| g ( x ( k ?1) ) ||
(??? ? ??????, ?g ( x ( k ) ) = g ( x ( k ) ) ? g ( x ( k ?1) )) .
? ?????? ?????????????? (????? ???????? ? ???????? ?????????
?????? ???? ? ????? ???????????? ? ??????? ?????????? ??? ???????? ??????).
2.6. ????????????????? ??????
??? ?????? ????? ???????? ?? ????????? ???????????? ???????,
???? ????? ?????????? ? ???????? ?????? ????. ????? ?????????????? ?? ??????? ??????????? ???????????. ??? ?????? ???????? ?????????????? ??????? ?????? ???????, ?? ?????????? ?????? ??????
???????????. ???????? ??????????? ?? ???????
x ( k +1) = x ( k ) + ?( k )s( x ( k ) ),
??? s( x ( k ) ) = ? A ( k )?f ( x ( k ) ) (???????? ? ??????? ???????, ???
s( x ( k ) ) = ? A ?1 ( x ( k ) )?f ( x ( k ) ) ). ????? ????????, ??? ????? ??? ?????????? ?? ?????? ???????? ????????? ???????? ???????. ?? ?????????????? ?? ?? ????????????? ???? ?????? ? (k) ?? ???????
A ( k +1) = A ( k ) + ?A ( k ) .
50
??????? ?(k) [n*n] ????? ???????? ???????, ????????? ???????
?? ?????????????? ?? ?????? ????????, ?????? ? ????? ????????
?????????? ???????? ?????????? ???????. ???????? ???????? ???????????? ???????, ????? ???????? ?x = C?1?g . ? ?????? ?????? ?????? ?? ??, ????? A ( k +1) = A ( k ) ?g ( k ) , ??? ?x ( k ) = x ( k +1) ? x ( k ) ,
?g ( k ) = g ( x ( k +1) ) ? g( x ( k ) ). ?????? ????????? ????? ?????????????
??????, ??? ???, ????? ????? ?g(k) ???? ????? ?(k) (?g(k) ???????? ??
?????? ?x, ? ??? ?? A(k)). ????? ???????????, ????? ????? ??????????? ??????? ? ????????????? ????? ???????????, ?. ?.
?x ( k ) = ?A ( k +1) ?g ( k ) ,
???
=
?
?
??????.
?????????
A (4+1) ,
???????
?A ( k ) ?g ( k ) =
1 (k )
1
?x ? A ( k ) ?g ( k ) . ???????????? ????? ?????????, ??? ?A ( k ) = Ч
?
?
? ? x (k )y T ? A (k )? g (k )zT
???????? ???????? ????? ?????????.
Ч? T
?
? y ? g ( k ) ??
zT ? g (k )
?
?
????? ? ? z ? ???????????? ???????, ?. ?. ??? ????????? ???????.
? ????????? ?????? ??????????????????????????
y = ?x ( k ) , z = A ( k ) ?g ( k ) .
????? ???????, ?????
?x ( k ?1) ?x ( k ?1)
T
A
(k )
=A
( k +1)
+
T
T
?x ( k ?1) ?g ( k ?1)
?
A ( k ?1) ?g ( k ?1) ?gT ( k ?1) A ( k ?1)
,
?gT ( k ?1) A ( k ?1) ?g ( k ?1)
????? ????? y, z ?????? ? ??????????? ?????????? ?????????????? ?
????????????? ?????????????? ??????? ?(k) (??? ??????? ? ????? ??
??????????? ?? ??? ????????? ???????????? ???????). ? ???????? ?(0)
????? ???? ??????? ????????? ???????.
??? ?????????? ???????? ???????? ?????????? ????????? ? ???????????? ????? ?*. ????? ???? ????????, ???
?f ( x ) = ?f ( x ( k ) )T ?x = ??f ( x ( k ) )T ?( k ) A ( k )?f ( x ( k ) ).
?????? ???????, ??? ???? ?( k ) > 0 ? ??????? ?(k) ? ???????????? ?????????? (?????????? ?????????? ??????), ?? ?f = f ( x ( k +1) ) ? f ( x ( k ) ) < 0,
f ( x ( k +1) ) < f ( x ( k ) ), ?. ?. ??????? ??????? ?? ???????? ? ????????.
51
?)
?)
?)
x (0)
x (0)
?) x
2
x2
d2
1
d1
d2
0
1
x1
x (2)
d1
x (1)
x1
???. 12
?????????. ???????????? ????????????-???????????? ????????
?(k) ?????????????? ???????? ???????, ??????? ?? ?????? ???? ???????????? ????????????-???????????? ???????? (???? ??? ??????? ???????????? ????????????-???????????? ??????? ?? ???????????), ?. ?.
????? ????????????? ?????????? ???? ? ????? ?????? ????????? ?????????? ?????????????????? ????? ?(k) (? ???????? ???? ?????? ?????
?????? ??????????).
??? ?????????? ?? ???????? ??????? ????????????? ?????????????? A(k) (??-?? ?????? ?????) ??????????????? ??????????? ???? (??????? ???? ????????????).
???????, ??? ? ?????? ???????????? ??????? ???????????
(k )
s = ? A ( k )?f ( x ( k ) ) ???????? ?-????????????, ? Ak+1 = C?1, ????????? ? ???????? ????????? ? ????? ???????????? ?????????, ?????????? ? ??????????? ?????.
??????? ???????? ????? ??????? ????????????? ??????. ?? ????????? ?????? ?????????? ? ????????? ??????? ?????.
??????????: ?????????? ??????? ??????? ?(k).
??????????
f ( x ) = 4 x12 + 3x22 ? 4 x1 x2 ? x1 ? min, x (0) = (0,0)T .
x
52
2.7. ?????? ??????????? ???????? ????????????
???????? ?????????? ???????? ?????????? ??????????: ?????
????? ???? ??????????? ?????????? ????? ????????????? (????? ??????) ?
?????? ? ????? ?????? ??????????? ?? ????? ??????????? (???????????
??? ??????). ????????? ????? ????? ????????? ???????? (???. 12, ?).
????? ??????????
????? ?????????? ???????????? ??? ??????????? ???????? ????????????, ???? ????? ?????????? (???. 12, ?). ??????????? ??? ??????
???????????? ?????? ????? ??????????? ???????? ??????? ?????.
???? ?????? ?????????? ??????? ? ??????????? ?????? ?? ????? ????????????? ???????????? ?????, ? ????? ???? ??????????? ???????
?????????? ??????? ?????????. ???? ?? ???? ?????? ?????????? ?????????? ????? ???? ? ?????????? ??? ??????????? ??????. ????? ???????? ?? ???? ??? ????????? ? ???????????? ????? ??? ? ????? ????????.
????? xm?1 ? xm ? ??? ???????? ????? ? ?????????????????? {xk}.
????? ??????? ? ?m+1 ????? ?????????????? ????????? ???????.
1. ??????? ????? ??????? ?????????, ?????? ??? ??????? ?????????? ????? ??????? (?m?xm?1), ? ????????? ????????? ?? ?? ?????????????????? ?????? (???????? ?????).
2. ? ????? ??????? ????????? ??? ?????? ????? xm+1 ???????????
?????????????? ????? ?? ?????????? ??????? ???????? ???? (???? ??
???? ???????????? ?? ??????? ???????, ?. ?. ??????????? ??????? ???????).
3. ???????????? ? ?????? ??????? ? ??????? ? ???? 1.
?????????? ????? ????????.
n
1. ????? di ? ??????? ??????????? ??????? (?. ?. ? ? j d j = 0 , ??? ? ?
j =1
????? ???? ?? dj; ??? ???? ?j=0 ), ?????? || dj || =1.
2. ????? ????, dj ???????-????????????, ?. ?. dTi d j = 0 , i ? j, x1, x2 ?
??? ???????? ?????. ?????? (x2 ? x1) ? ??? ? ? ?????? ??????????? ?
m
??????, ???????????? ????? ??? ??????. ????? x m +1 = x m + ? ? j d j (?j
j =1
? ????? ???? ? ??????????? dj). ???? ?j ???????????? ???????? ??????? ??? ???????????? ???????????. ????? ????? ??????????? d j ,
53
???????? ? ??????? ????????? ????????????? (?????????? ?????????????????? ??????).
??????? ????????, ??? ??? ??????? ??????????? ??????? ????????????? ?????? ????????, ????????? ??????????????? ?????????? ?????????? ????? ??? ? ???????? ???????? ?? ??? ??????.
??????????? ?????? ???????? ????????????? ??????????? ???????????, ???? ? ???????? ????????? ????? ??????? ?????? ?????????????
(???. 13, ?). ???? ??????? ???????? ? ????? ?, ????? ?? ? ????? ??
????????? ????? ?, ?, ?, ? ?? ?????????? ?????????? ???????.
????? ??????????? ??????????????? ??????
?????? ????? ???????, ??? ???????? ??????????? ???????? ??????? ?????????? ????????????? ????? ??????????? ???????? ???????
????? I''(x). ??? ????????? ??????????? I(?) ??????????? ?????????
???????: ??? ?????? ? ?? ????????? D ??? ??????????? ????? I''(?)
?????, ?1 ?,..., ? ? n ?r >>| ? n ?r +1 |?,..., ?| ? n , ??? r ? ????? ????? ??????????? ???????? (?????????? ??????????? ??? ??????).
???????? ?????????? ???????? ?????????? I''(?) ? ??????? ???? ???????????? ?????, ?. ?. ?????????????? I'' ? ??????????? ?????????????? ??????? ????? ??????????? ???????? ??????? I''. ???????????,
???????????? ????? ????????? ????????? ? ????? ?????????? ???????
????????? ??? ??????????? ???????????? ???????????? (?????????? ?? ?? ??????????).
? ???????? ?????? ????????? ????? ??? (??????????????? ??????????? ???????? I'') ??????????? ?? ?????? ?????? ????????????? ??????????? ????????. ??????? ? ????? ???? ??????????????, ????? ?????? ??? ?????????? ?????, ?. ?. ????? ?? ???????? ???????????? ??????????? ??????? ? ??????????? ??????? I(?). ?????????? ???? ?????????? ????? ????, ??? ?? ??????? ????????????? ??????????? ??????????? ???????.
???????? ???????? ?????????? ??????
??? 1: ???? ???????? ??????: ?0, S0 (????????? ????? ? ???), Nmax
(???????????? ????? ????????), k = 0 ? ??????? ????? ?????
x ( k ) = x 0 , ( xi , i = 1, n );
S(k)= S0 ? ????????? ??? ??? ?????????? ???????????;
h0= S0 ? ????????? ??? ??? ????????????? ??????.
??? 2: U=E, ??? ? ? ????????? ???????.
54
? ???????? ???????????? ???????? ????? ??????? {ui }??????? U.
??? 3: ????????? ???????????? ??????? ????? B = bij ,
{ }
bij = I ( x ( k ) + s ( k )ui + s ( k )u j ) ? I ( x ( k ) ? s ( k )ui + s ( k )u j ) ?
? I ( x ( k ) + s ( k )ui ? s ( k )ui ) + I ( x ( k ) ? s ( k )ui ? s ( k )u j ),
k=k ? 1.
??? 4: U = U? (? ? ????????????? ???????), ?????????? ? ? ????????????? ???? ?T. ?T (? ????????????, ????????, ?????????? ?????).
??? 5: ? ???? {ui }??????????? ??????? ??????????????? ?????? ??
????? ?(k?1) ?? ?????????? ??????? ???????? ????, ? ??????:
?)
?j =2; hj=h0; j = 1, n; f = I ( x ( k ?1) ); xold = x ( k ?1) ,
??? ? ? ?????? ????????? ??? ???????? ?????????? ? ???, ?? ???? ??
???? ???????? ??????????? ???????;
?) i = 1;
?) x ( k ?1) = x ( k ?1) + hi ui ; f1 = I ( x ( k ?1) ) , ???? f1 ? f , ?? {hi = 3hi; f = f1;
???? ?i = 2, ?? ?i =1},
?????
{x(k ?1) = x(k ?1) ? hiui ; hi = ?0,5hi ; if ( pi ? 2),
}
pi = 0 ;
???? pi ? 0, j = 1, n, ?? {???? i=n ???? ?? ??? 5, ?), ????? {i=i+1; ?? ???
5, ?)};
?) s(k)=0,1||x(k?1) ? xold||.
???? k ? N max ?? ??? 3 (??????? ????), ????? ?? ????? (????? ???????, ????? ?????????????? ?? ??? ???, ???? ?? ???????? ???????? ????? ?????).
????????? ? ???? 4. ???????????? ?????????????? ??????? ?????
???????????? ?????? ? ???????? ????? ??????????? ???? ???????? UT,
?. ?. ????? ? ???????? ???????????? ???? ui ???????????? ?????? ??????????
x=Uy I(x) = I(Uy) = I ( y ) .
????? ????????, ??? I "( y ) = UT I "( x )U, ???????, ???? ????????? ???????? ??????? ????? I "( y ) ? ???????? ?? ? ????????????? ????
TT I "( y )T = TT UT I "( x )UT , ?. ?. ? ???????? ????? ??????????? ?????????? ??????? ??????? ??????? U1 =UT.
55
2.8. ???????????? ???????
? ?????? ??????? ?????????? ????????? ???????????? ???????, ?????? ? ????? ?????? ?????????? ???????????? ???????.
?????? ????????????????
??? ?????? ???????? ?k (??? ???????? ????????? ???????????? ???????) ?? ???????? ??????? f* ? ???? ????? ????????? ??????? ??????
?????? ??????????? A = ?2 f ( x* ) ? ????? ????????, ?? ????? ??????
???????? ??????????? ???????? ??? ??????? ? (?. ?. ????????? ??????????? ????? ?i ? ??????????? ??????? u (??????? ?????????? ?u = Au),
????? ???????? ?? ???? ??????. ?????????? ????????, ??????? ?? ?????????? ?m (????? ??????????? ????????) ? ??????????????? ?? um, ????????? ????? ???????? ??????? ? ??????? f(x), ??????? ????? ?????????, ?
??, ??????? ????? ????????? ??? ???????????? ?????? ????????.
?????????? ?????????? ????? ??????????? ? ???, ??? ? ????????
(| ? max | / | ? min |>> 1) ???????? ????? ?????? ??????? ????? ?????????
????? (???. 13, ?), ?. ?. ??? ????? ? ??? ?? ????????? ??????? f ?????????
x1 ? ?2 ???????? (f ????? ????????????? ? ?1, ??? ? x2). ??????? ?1 ?? 0, ?. ?.
???????? ???? ????????, ????? ?? ????????? ????? ?f ? ?f ??? ??? ??????????? ????????? ??????? ?f ? ?f ??? . ??? ?????????, ? ???????? (???.
13, ?) ?? ????????, ??? ????? ?????????: ?1 ??? x2.
?)
?)
x2
C
B
B
A
C
x1
?)
?) x
x2
2
x*
x
*
x1
???. 13
56
x1
???? ?????? ??????? ?????, ????????, ???????? ? ???, ????? ?????????
???????? ?????????????? ?????? f(x), ???????? ??? ????? ?????????????? ??????. ?????????? ??????????? ?????????? ?? ???????? ????????
????????? ????????? ?????????? ????????? ????????????? ???????.
???????? ??????? ?? ?????????????
??? ?????? ???????? ????? ???????????? ????????? ??????:
? ???????? ??????????? ? ??????????? ??????? ????????????? ?
????????? ?????;
? ????????? ??????? ? ??????? ?????????? ???????;
? ??????? ????????? ???????? ???????, ????????? ?????????????? ?????? ??????.
????????? ???????? ???????? ????? ?????????? ???????????. ???
???? ???? ?????? ?????????? ?????? ??????????? ?????? (????????,
????????? ?????), ??????, ?????? ?????????? ????? ?? ??????????
(????? ????).
???????? ????????
?????? ?????, ???????, ??? ????????? ?????? ????????? ????? ????
?????? ???????? ? ????? ????????????? ?????????????? ?????????.
???????? ?????????????? ????????? ???????? ???????? ???????????? ?????????:
|| x ( k +1) ? x ( k ) ||
<? ?
|| x ( k ) ||
????????????? ???????? ? ?????????? ?????? ???????? ????? < ?, ???
(|| x ||= ? xi2 ) (????????? ??????????? ????? N ???????????????? ???????? < ?);
f ( x ( k ) ) ? f ( x ( k +1) )
< ? , ?. ?. ????????????? ???????? ???????? ???| f ( x(k ) ) |
???? ?? ?????? ???????? <?.
?? ??????? ?? ???. 14, ? ?????? ?????, ?????? ????? ?????????????? ??????? ?? ??????? ? ?? ????????. ? ??????? ?1 ????? Nmax ???????? ??????????? ??????? ?? ???????? ???????? ??????? | f k ? f k ?1 |, ?
? ??????? ?2 ? ?? ???????? ???????? ?????????? | f k ? f k ?1 | . ? ????? ?*
??????????? ??? ???????.
??? ??????????? ???????? ???????????? ??????? ????? ? ????,
??? ??? ???? ????? ??????????????? (cond), ??? ?????????? ???? ??57
???????? ? ???????????? ????????? ???????? ???????. ???? ???? ? ?????
??????????????? ??????? ?????, ??????? ????? ???? ??????? ????????? ??????? :
? max ? i ( x )
?) 1 ? ?( x ) = cond ??2 f ( x ) ? = i
,
?
? min ? ( x )
i
i
???? ?2 f ( x ) > 0 (????? ? i > 0), ??? ?i ? ??????????? ???????? ???????
?2f(x), ???? ? > 102, ?????? ????? ??????????? (???????? ??????????);
2
, ??? µ ?????????????? ???????? ?????????
?) ? ?
1? µ
|| ?f ( x ( k +1) ) ||
.
|| ?f ( x ( k ) ) ||
?????????? ??????, ??????????????? ????????? ?????????????
????????? ????????? ???????? ? ???????? ?????????. ?????
f ( x1 , x2 ) = ( x1 ? 1) 2 + 10?6 ( x2 ? 1) 2 + 1;
?*= [1.1]T ? ??????????? ??????? f*= 1.
?????????? ??? ?????:
T
1. x = [1,2] , f ( x ) = 1 + 10?6 , || x ? x* ||= 1.
T
2. x? = ??1 + 10?3 ,1?? , f ( x? ) = 1 + 10?6 , || x? ? x* ||2 = 10?3.
????? ???????, ?? ???????? ????? ???????? (??????????? ?????
????? ?? ??????) ????? x? ? ??????, ?? || g( x ) ||2 = 2 ? 10?6 (g ? ????????), ?
|| g( x? ) ||2 = 2 ? 10?3 , ?. ?. || g( x ) ||2 (????? ? ????) ??????????? ????? ?????
x , ???, ???????, ???????.
???? ??????, ??? ??????? ????????? ?????????? ??? ??? ?????? (???????? ????? ??? ?????????? ?????? ? ????? ??????????) ? ?? ????????
?????? ??????????????? ? ????? ????????????? ???????.
????????? ????????????? ??????????
??? ?????????? ??????????? ????????? ????????????? ?????????
??? ??????????? ????? ???????????? ?????????? ???? ?????????????
?f, ?2f ????????? ??????????
?
df
dxi
58
|
f ( x + he(i ) ) ? f ( x )
? =
x= x
h
??? ??????
?
df
dxi
|
f ( x + he(i ) ) ? f ( x ? he(i ) )
? =
,
x= x
2h
??? h ? ??? ???????????????? ???????????; ?(i) ? ?????? ? ???????? ?
??????? i.
?? ?????? ?????? ????????? ?????????????? ?????????? ????????
???????
f ( x + he(i ) + he( j ) ) ? f ( x ? he(i ) + he( j ) )
?2 f
=
+
4h
?xi ?x j
+
? f ( x + he(i ) ? he( j ) ) + f ( x ? he(i ) ? he( j ) )
4h
? ??? ?????????? ??????? ?????.
???????? ?????????? ? ??????????? h, ?? ??????????? ?????? ????????? ??????????. ???? h ?????????????, ???????? ???????? ?????? ??
????? ?????? ???????? ?? ???, ?? ?????? ?????? ???????????. ?????
h ?????? ?????????????? ? ??????????? ?? ???? f(x), ????????? ????? ?
? ???????? ???. ??? ??????????? ???? h ????? ???????????? ???????? ??????????? ? ???????????? ??????????, ??????? ?? ?????????
h = 0,1 || x (i +1) ? x (i ) || . ??? ?????? ??????????? ?? ?????? ???? ????
????? h0.
???????? ?????????? ???????????????????
?????????????????? {xk } ?????????? ?????????? ? ???????? r, ????
r ? ???????????? ?????, ??? ????????
|| xk +1 ? x* ||
= ? < ?,
k ?? || x ? x* ||r
k
0 ? lim
??? x* ? ?????? ??????????????????; ?=const. ???? r = 1 ? ????????
???????? ??????????, ?? ?? ???????? ??? ????????, ??? ????? ?????? ???
???????? ? ?k ?????????? ?????????????? ?????????? ?????. ???? r =
2 ? ???????????? ???????? ??????????, ?? ? ?????? ????? ????? ?????????? ???? ? ?k ???????????.
???? ? = 0, ?? ?????????????????? ???????? ?????????????? (??? ??????? ?????????? ???????????????????).
59
????????????????????
??????? ????????, ??? ???????? ???????????????????? ?????????
????? ?? ??????? ??????????? ???????? ????????. ?????????????? ??
???????? ?????????????? ?????????? ? ???????????????? ??????????? ??????? ????????? ??????????? ????????? ????????. ?? ????? ????
??????? ?????? ????????? ????????? ? ???????????? ??????? ??????????? ????, ??? ?? ???? ??????? ????????. ??? ?? ????? ????????????? ???????? ??????????? ?????? ? ???? ??????? ???????? ???????????.
? ???????? ??????????? ?????? ?????? ???????? ??? ?????????????? ??????: ?????? ?????? ?????????? ??????? ? ???????????? ?????????? ?? ????, ????? ????? ??????????. ?????? ??? ???????????,
??? ????????? ??????? ???????? ??????????, ????????? ????? ??????
??????????.
????? ?????????? ??????? ????????? ?? ???? ??????? ??????????????? ??????????? f(?). 0??? ?? ??????? ??????? ?? ??????????? ?????????? ?????? (? ???? ???????? ??? ????? ????????? ????????, ?????????????, ?? ???? ????????).
?? ??????????? (??????? R) ??? ?????? ? ???????? ? ?(k) (??????) ?
???? V(k) ?????? m ????????? ???? x1( k ) , ..., xm( k ) (???. 14, ?). ????????? (k+1) ? ????????? ??????? ???????????? ?? ????????? ?????
x ( k +1) = arg min f ( xi( k ) ), ? ??? ?????????? ?????? ?????????? ????? ???1
??????? ???????? ???? ? ???????????? ? V ( k +1) = ( x ( k +1) ? x ( k ) ) , ??? R
R
? ??????????.
?)
?)
F
x(k)
x
*
x
?)
R
?
?1
?2
???. 14
?????????? ?????? ?????? ????????? ??????????? ??????????? ?????? ?????????? ?? ????, ????? ??? ???? ???? ???? ?????. ???????? R,
????? ?????????????? ?? ????????? ?????????? ?????? (????????????
?????) (???. 14, ?).
60
3. ?????? ???????? ???????????
??????????? ?p?????????? ????? ??????? ? ???????????? ?p? ??????? ??????p??? ?????????? ??p???????? ?? ??p???????? ??p???????.
???????????? ??p???????? ??????????? ????????? p????p? ???????, ? ????p?? ?p?????????? ????? ????????.
3.1. ?p???p?? ????????????? ? ??????? ? ??p??????????
?p????? ??????????? ?????????? ????? ???????, ??? ??? ?p? ??????? ??p???????? ?????? ???????????? ?p???p?? ????????????? ??????????? ???????????. ????? ??p??????? ???? ???????? ??????? ? p????????
???? ?p??????? ? ????????p??? ?????, ???, ???p???p, ? ??????
f ( x ) = ( x ? 2)2 ? min ????? x*= 2, ? ?p? ???????? ??p???????? x ? 4
x
????? ?????? ???????? ??????? x*= 4. ???????, ??? ?p? ???? f'(4) = 4 ? 0!
??????????? ? ???? ????????.
???????p?? ?????? f ( x ) ? min ??? hk ( x ) = 0; k = 1, K . ???? ??p???????? ????? p??p????? ???????????? k ??????????? ??p??????? (????????????) ? ????? ?? ????????? ?? ??????? f, ?? ?p??????? ??????
??????????? ???????????, p??????p????? ????.
???? ??? ?p???? ??? ?????????? ???????, ?? ?????????? ????? ?????????? ???p????. ?p? ???? ?????????????? ?p???p???????? ? ????????????? ?????? ??????????? ???????????
(3.1)
f ( x ) ? min ;
?p? h1(x) = 0
(3.2)
L( x, v ) = f ( x ) ? vh1 ( x ) ? min,
(3.3)
?p???p??????? ?
??? L ? ??????? ?????????; v ? ??????????? ?????????? (?????????
?????????), ?? ???? ??????? ?? ????????????? ??????????. ????????
?????? ????? ??????, ???? ??? ???? x ??????????????? (?. ?. ??? h1(x) = 0)
min L( x,V ) = min f ( x ).
x
x
61
?????? ? ???, ????? ????????? ???????? v0 ? ? ????? ????????????
???????? x0 ??????? L, ??????????????? ??????????? (3.2). ????? x0,
v0 ? ????? ???????? ??????.
????????
????? ??????????? ??????? ??????? L ?? x, ??? ??????? ?????????? v ? ??????? ????? v, ??????? ????????????? ???????????.
??????: f ( x ) = x12 + x22 ; h1 ( x ) = 2 x1 + x2 ? 2 = 0;
L( x, v ) = x12 + x22 ? v (2 x1 + x2 ? 2);
dL
= 2 x1 ? 2v = 0 ? x10 = v;
dx1
dL
v
= 2 x2 ? v = 0 ? x20 = .
dx
2
?2 0?
??????? H L = ?
????????????-????????????, ?????????????,
? 0 2 ??
??????? ??????? (??? ????? ??????????? ????????). ??????????? x0 ?
h1(x), ??? ??? ?????? ????????????? ????????????
v
4
= 2 ? v0 = .
2
5
????? ???????, ????? ?????????
4
4
2
x10 = , x20 = , min f ( x ) = .
5
5
5
2v +
??? ??????? K ???? ??????????? ????? L( x, v ) = f ( x ) ?
K
? vK hk .
k =1
dL
= 0, ??? ??????? ????????? ?? ??????? ????? ??????? ???????
dx
dL
?? V, ?? ?? ???? ????????? ?????????????, ??? ???
= L( x ) = 0.
dv
??????????? ??????? ???????? ??????? f(x)
K
? dL
df
dh
=
?
?k i = 0, j = 1, n, k = 1, K ;
?
?
dx
dx
dx
? j
j
j
k =1
?
? dL = h ( x ) = 0.
k
? dv
? k
62
(3.5)
??? ?????????? ??????????? ??????? ????????? ????????????? ??dL2
????????????
? ????? ????????.
dxi dx j
?????????:
?) ????????? (3.5) ????? ?? ????? ??????? ;
?) ?????? (x0, v0) ???????? ???????? ?????? ??????? L, ??????? ??????
?????? ?????? min L(x,v) ???????????? ???????? ??????????? ???????????.
?????????? ??????? ????????? ???? ?????? ?? ???????.
????? ????????? ?????????? 180 ???????. ?? ????? ?????????? ????? ???????????????? ?????????. ??????? ??????? ?????????????? ????????????
?????? 1:
4 x1 + x12 ,
?????? 2:
8 x2 + x22 ,
??? x1 ? ????? ???????, ????????????? ?????? ????????; x2 ? ????????????? ?????? ????????;
?????????? ??????? ??????? ????? ???? ??????????? ?????? ???????? ???, ????? ????????? ??????? ???? ???????????
????????? ??????? ????????????? ????????? ??? ????????
f ( x ) = 4 x1 + x12 + 8 x2 + x22 ? min;
x1 + x2 = 180;
L( x,V ) = x12 + 4 x1 + 8 x2 + x22 ? v1 ( x1 + x2 ? 180);
dL
= 2 x1 + 4 ? v = 0;
dx1
dL
= 2 x2 + 8 ? v = 0;
dx2
d 2L
dL
d 2L
= x1 + x2 ? 180 = 0; 2 = 2; 2 = 2;
dx3
dx2
dx1
H=
2 0
,
0 2
??? 2 x1 = 182; x2 ? x1 = 2; x1 = 91; x1 + x2 = 180; x2 = 89.
63
?????? ??????.
1.
f ( x ) = x12 + x22 + x32 ? min;
g1 ( x ) = x1 + x2 + 3x3 ? 2 = 0;
g2 ( x) = 5x1 + 2 x2 + x3 ? 5 = 0.
2.
f ( x) = x1 + x2 ? min;
x12 + x22 = 1;
x1* = x2* = ?1* =
?1
.
2
3.2. ????????????? ????p?p?????? ?????????? ???p????
????????? v k ????? ????p?p???p?????, ??? ???? p???p???,
??p????????? ??p??????????. ??????????? ???????? vk* ? ???????????? ??????????????? ???????? ??????? ??????? ? ????? ???????? ?
p???p???. ??????? ???.
????? f ( x1, x2 ) ? min ; h1( x1, x2 ) = b1, ??? b1 ? p???p?? (??????????
? ??p????????? p?????????).
??????? ??????? ???p???? L( x1, v1 ) = f ( x) ? v1(h1( x) ? b1 ). ???
????p????? ????????? f*, ????????? ? ?????????? b1, ?. ?.
df * df * dx1? df * df 2*
.
=
+
db1 dx1* db1 dx2 db1
(3.6)
??????????, ???????????? ?????????? ???????????. ????????????? h1(x)?b1 = 0, ???????
?h1 ?x1* ?h1 ?x2*
?
+
?
? 1 = 0.
?x1 ?b1 ?x2 ?b1
??????? ??? ????? (3.7) ?? v1* ? ?????? ?? (3.6)
?f *
= v1* +
?b1
64
? ?f * * ?h ? ?x*j
,
? * ? v1 1 ?
?
?x j ?? ?b1
j =1 ? ?x j
2
?
(3.7)
?f *
= v1* ,
?. ?.
?b1
??? v1* ? ???????? ????????? ???????????? ???????? f, ??????????? ?????????? b1. ??????????, v1* ????? ????????????????, ??? ?????????
??????? ????????, ?. ?. ??? ???? ???????.
? ??????????? ?? v1* ??? ????????? b1* ???????? f* ?????????????
??? ???????????.
3.3. ?c????? ????????????? ??????????p?
??? ? ?????p ???????? ????????? ???? ?????? ? p?????? ??????
? ??p?????????? p?????????? ?? ?????? ????? ?????? ???????????
?p??p????p?????? ? ??p??????????-p?????????? ? ??p??????????. ?
????? ?????? ?????? ????? ???
f ( x ) ? min, g j ( x ) ? 0, j = 1, I , k = 1, K , hk ( x) = 0.
(3.8)
???? ??????? D ???????? ? ????? ?????????? ?????, ?? ??????????
???? ?? ???? ????? x?D, ? ????p?? ??? ??p???????? g j ? 0 ????? ????
p???????? ?? ??? ????.
1. ???????? (? ????p?? ??? ??p???????? ??????????? ??? p????????)
gj(x)=0, j ?I?.
2. ??????????, ??? gj(x)>0, k ?I+.
? ????????? ?????? ????? x ?? ????? ?? ????p?????? ??p????????.
??????? ?? ???? ????? ????????? ??? ????? ???? ???????? ? ?????
???p???????. ???p????, ???? j-? ??p???????? ??????? ? ????? x, ??
???????? ???????? ???? ? ??p??? ??p????????? ???p???????.
???? ?? ????? ???? ??????? (?? ???????) ?????????? ??????????
? ????? ???????? ???????????, ?? ?? ????? ?? ???? ????????? ??
?????? ? ????? ??p???? ????????? ?? p????p?????.
?p???p
????? ???????? ????? ?? ?p???? ??p???????? g1, (p??. 15, ?, ?), ?. ?.
?p? ??????????? x*opt ? g1 ??? ??p?????? ? p????????
( g1=0), ? g2, g3 ? ?????????,
g1(x*) = 0, g2(x*) > 0, g3(x*) > 0.
??????? ????????????? ??????????p? ????? ???p????p????? ? ????
?????? ?????????? p?????? ??????p?? ??????? ?????????? ?p???????
? ??p???????.
65
?)
?)
g1(x) = 0
g3(x) = 0
f
x*
A
g2(x) = 0
0
1
bj
???. 15
????? x ? R n ? ? R I , v ? R k , ?????????p????? ????????
?f ( x ) ?
I
?
j =1
u j ?g j ( x ) ?
K
? vk ?hk ( x) = 0;
k =1
g j ( x ) ? 0; hk ( x ) = 0; u j g j ( x ) = 0; u j ? 0, j=1, I; k=1, K.
(3.9)
????? ?????, ??? ??? ?????????? ??? ??????? ????????? ? ?????????
????????????? ??? ?????? ???????? (??? ?? ??? ? ????????). ???????? ???????????, ???????, ??? ???? ???????????? j-? ??????????? ?????????? (gj(x) > 0), ?? ???????, ??????? ????????????? ???????????
???????????, ????? ????????, ?????? u j g j ( x ) = 0.
? ?????? ????????? ??p????????, ?. ?. ????? gj(x) = 0, u ?? ??????????? p???? ????, ?? ??? ??? gj(x) = 0, ?? ujgj(x) = 0 (??? ??????? ?????????? ????????? ??????????? ???????????).
???????p?? ???p?? ? ?????? u j . ????? g j (x) ? 0. ?p???p?????
??p???????? ? p???????? ????????? ??????????? ??p???????
a 2j > 0; g j ( x ) ? a 2j ? b j = 0; a 2j > 0 (????? p??????p??????? ????? j bj = 0).
???????? ?p???????? p??????p???? ?p? ??p?????????-p?????????,
????? ????????
?f *
?b j
b =0
= u j ? ???? ??????? (? ????? ?????? bj = 0).
?????? ?????????? bj ?? 0 ?? 1, ?????, ??? ??????? ???????? (???. 15, ?);
? ? ????? ????????, ? ??????, f* ????? ?????? ???p??????, ??? ??? ??????? ????????? ????p? ?????????????? ???????, ?????????????, uj ? 0,
(??? ??? ???? bj ???p??????, ?? ? f* ???p??????).
?????, ??? uj ?? ??p?????????, ??? ? ???????? ????.
66
???p??? 1 (??????????? ???????)
???????p?? ?????? (3.8). ????? f, g, h ? ?????p????p????? ????-
{
}
???, ? x* ? ?????????? p?????? ??????. ??????? I = j g j ( x* ) = 0 ,
?. ?. ????????? ???????? ???????? ??p????????.
????? ?g j ( x* ) ??? j ? I ? ?hk ( x* ) ??? k = 1, K ???????-??????????.
???? x * ? ??????????? ??????? ?????? (3.8), ?? ?????????? ??p?
?????p?? u* , v* ? ??? ???????? p??????? ?????? ??????????p? (3.9). ???
????? ??????????p?.
????????, ??? ?????p? ?g j ???????-??????????, ????
I
? c j?g j = 0
i =1
?????? ??? ???? xi = 0 . ????????? ??? ??????, ??? ??? ???? ??? ?????
??????????? ?????. ??? ??????? ????? ???????????? ??? ?????????????? ????, ??? ???????? ?????????? ?????, ??????????????? ??????? ???????? ?????????????, ?? ???????? ???????????, ???? ?? ?????????p???
???????? ??????????p?.
???????, ??? ??????? ???????? ????????????? ??????
?????????p?????, ???? ??? ??p???????? ? ???? p??????? ? ??p???????
????p??? ?????? ???????? ???????.
???p???p, ? ?????? f ( x ) = 1 ? x 2 ? min ;
?1 ? x ? 3;
g1( x) = x + 1 ? 0;
g2 ( x) = 3 ? x ? 0.
????????, ??? ??????? x*= 3.
??????? ??????????p?: ?2 x ? u1 + u2 = 0;
?1 ? x ? 3,
u1 ( x + 1) = 0,
u2 (3 ? x ) = 0,
? x* = 3, u1 = 0, u2 = 6?0,
u1, u2 ? 0
?. ?. ??????????? ??????? ??p??? ???p??? ? ????? x = 3 ????? ????
?????? ????????, ?????? ????????????? ??????? ?? ??p????p???, ???
??? ????? ????????.
67
???p??? 2 (??????????? ???????)
???????p?? ?????? (3.8). ????? ??????? f(x) ????????, ? ??? ??p???????? ? ???? ??p??????? ????p??? ???????? ??????? gj(x), j= 1, I , ??????????? ? ???? ???????? ???????? ???????? ??????? hK ( x), k = 1, K .
?????, ???? ?????????? ??????? x*, u*, v*, ?????????p????? ????????
??????????p? (3. 9), ?? x* ? ??????????? p?????? ?????? (3.8).
???p??? ????? ???????????? ??? ?????????????? ????, ??? ???????
??????????? p??????.
??????
min f ( x ) = x12 ? x2 ,
???
g1( x) = x1 ? 1 ? 0;
g 2 ( x ) = 26 ? x12 ? x22 ? 0;
h1( x) = x1 + x2 ? 6 = 0.
???? ?p???p??? ??????? ???p??? 2.
? 2 0?
????? ?f ( x ) = (2 x1, ?1) H f ( x ) = ?
? ???????????? ??????????? 0 0??
????, ?????????????, f ? ???????. ??????? g1 ( x ) ??????? ? ???????
? ?2 0 ?
????????????, ??????? g2(x) ? ???????, ??? ??? H g ( x ) = ?
?, ?
? 0 ?2 ?
???????????? ??????????; h1(x) ? ???????? ???????? ???????, ?. ?.
??????? ???p??? 2 ?????????.
???? ????p? ???????? ?p???p?? ??????????? ???????, ?? ????? ???????? ????????????? p??????.
?????? ?????? ??????????? ???????????????? ???????? ? ?????
??????????p?. ???? ??????? ???p??? 2 ?????????, ?? ??? ????? ??????????? ????????.
??p???????
1. f ( x ) = ? x1 ? min; g1 ( x ) = (1 ? x1 )3 ? x2 ? 0.
??????????? ????? x = (1,0).
????? ?f ( x ) = ( ?1,0)T ;
?g1 ( x ) = (0, ?1)T ;
68
?g 2 ( x ) = (0,1)T ;
c1?g1 ( x ) + c2?g 2 ( x ) = 0 ?? ?????? ??? c1 = c2 = 0, ??????? ?g1 ? ?g2
??????? ????????, ? ??????, ??????? K??????????? ?? ???????????.
2. f ( x ) = ( x1 ? 3)2 + ( x2 ? 2)2 ? min; 5 ? x12 ? x22 ? 0; 4 ? x1 ? 2 x2 ? 0.
?p???p??? ????? ?) x = (2,1)T ? ?) x = (0,0)T .
???????
1. ? ???? ????? ????????? ???????? ???????? ??p???????? I = {1, 2}.
?????????????, ? ???????????? ? ?p????????? ?????????????? ??????????? u3 = u4 = 0 , ??? ???
?f(x) = (?2, ?2)T; ?g1(x) = (?2, ?2)T; ?g2(x) = (?4, ?2)T, ??
1
2
?f(x) ?u1 ?? 2(x) = 0 ??? u1 = , u2 = ,
3
3
?. ?. ui ? 0.
2. ????????? ????? xT = (0,0).
????? I {3,4} ? u1 = u2 = 0.
?f(x) = (?6, ?4)T; ?g3(x) = (1, 0)T; ?g4(x) = (0, 1)T, ??
?f(x) ?u3 ?? 3(x) ?u4g4(x) = 0
??? u3 = ?6, u4 = ?4 , ?. ?. ??????? ????????????????? ????????.
? ???? ??????? ??????? ???????????? ????? ?????????? ? ?????????? ??????. ????? ??????????, ???????? ?? ????????? ?????
?????? ?????????? ????????, ??????? ??????????????? ???????????
???????? ??????? ???????. ????? ????????? ????????? ????? ?????????? ???????? (??? ??? ??? ??????????? ???????). ????? ???????????? ??????p???? ???????????? ???? ????? ????????, ???????
?p???p??? ?????????? ??????????? ??????? ???p??? ??p????. ??????????, ???? ?????????p????? ??????? ??p???? ??p???? (???p??? 2),
?? ??? ????? ??????????? ????????. ?? ??? ?????? ??????? ???????
? ? p??? ??????? ??? ?? ???????????, ??????? ?p???????? ???????????????? ?p???p??? ??????????? ??????? ???p??? ??p???? ?? ????? ?????????? ????????.
3.4. ?p?????????? ?p???p?? ??????? ?????????????
???????p?? ??????
f ( x ) ? min, g( x ) ? 0, x ? 0.
69
???p???
???? ??p? (x*, v*) ? ???????? ????? ??????? ???p????, ?? x* ? ??????????? p?????? ???????? ?????? ??????????? ?p??p????p??????. ????
???????
Документ
Категория
Без категории
Просмотров
0
Размер файла
639 Кб
Теги
0109, 2001
1/--страниц
Пожаловаться на содержимое документа