ВУЗ:
Составители:
Рубрика:
96
После нахождения вектора
k
s
определим шаг корректировки решения
0
arg min ( ).
kk
k
x
x
s
λϕλ
≥
=+
Затем осуществляем итеративный переход
1kk k
k
x
xs
λ
+
=+ .
Задание 1. Пусть вектор
k
x
не является решением исходной
системы (38), вектор
k
s
является решением вспомогательной задачи (41),
(42). Доказать, что при некотором 0
α
> для всех (0, ]
β
α
∈
0( )().
kk k
hx s hx
β
≤+<
Задание 2. Доказать, что если выполняется условие (40) и задача
(41), (42) имеет решение, то
1
()().
kk
hx hx
+
<
Задание 3. Пусть система (38) совместна. Множество
{
}
0
:() ( )
n
L
x R hx hx=∈ ≤
ограниченное, на всех итерациях вектор
k
x
не является решением
системы (38), при этом вспомогательная задача (41), (42) имеет решение
на всех итерациях. Тогда
lim ( ) 0,
k
h
hx
→∞
=
последовательность векторов
k
x
сходится при h→∞ к множеству
решений системы (38).
Для решения вспомогательной задачи (41), (42) можно
воспользоваться задачей поиска вектора
m
uR
∈
из условия
() min, 0
k
uu
ϕ
→≥ (43)
где
2
2
() ( ) (1 , )
kT k
k
uA bu
ϕ
=+−
.
Данная задача всегда имеет решение. Пусть оно составляет вектор
k
u .
Если
() 0
k
u
ϕ
> ,
то согласно приведенным во второй части предыдущего параграфа фактам
0,
k
ρ
>
где
1,
kk
bu
ρ
=− .
Решение вспомогательной задачи (41), (42) может быть получено по
формуле
1
() .
kkTk
k
s
Au
ρ
−
=
После нахождения вектора s k определим шаг корректировки решения
λk = arg min ϕ ( x k + λ s k ).
x≥0
Затем осуществляем итеративный переход
x k +1 = x k + λk s k .
Задание 1. Пусть вектор x k не является решением исходной
системы (38), вектор s k является решением вспомогательной задачи (41),
(42). Доказать, что при некотором α > 0 для всех β ∈ (0, α ]
0 ≤ h( x k + β s k ) < h( x k ).
Задание 2. Доказать, что если выполняется условие (40) и задача
(41), (42) имеет решение, то
h( x k +1 ) < h( x k ).
Задание 3. Пусть система (38) совместна. Множество
{
L = x ∈ R n : h( x ) ≤ h( x 0 ) }
ограниченное, на всех итерациях вектор x k не является решением
системы (38), при этом вспомогательная задача (41), (42) имеет решение
на всех итерациях. Тогда
lim h( x k ) = 0,
h →∞
последовательность векторов x k сходится при h → ∞ к множеству
решений системы (38).
Для решения вспомогательной задачи (41), (42) можно
воспользоваться задачей поиска вектора u ∈ R m из условия
ϕk (u ) → min, u ≥ 0 (43)
где
2
ϕk (u ) = ( Ak )T + (1 − b k , u ) 2 .
Данная задача всегда имеет решение. Пусть оно составляет вектор u k .
Если
ϕk (u ) > 0 ,
то согласно приведенным во второй части предыдущего параграфа фактам
ρ k > 0,
где
ρ k = 1 − bk , u .
Решение вспомогательной задачи (41), (42) может быть получено по
формуле
−1
s k = k ( Ak )T u k .
ρ
96
