Системы линейных неравенств. Зоркальцев В.И - 95 стр.

UptoLike

ВУЗ: 

ИГУ | Иркутск

Составители: 

Рубрика: 

95
Метод линеаризации. Пусть задано некоторое начальное
приближение – вектор
0 n
x
R
∈
. С этого вектора начинается
вычислительный процесс.
Обозначим 0,1, 2,k
=
K – номера итераций. В начале -ойk итерации
считается заданным вектор
kn
x
R
∈
. Если этот вектор удовлетворяет
условию (38)
()0,
k
gx
≤
то вычисления заканчиваются.
Иначе, т.е. если
()0,
k
hx > (40)
осуществляется итеративный переход. Для этого сначала найдем
направление корректировки решения. Обозначим его
k
s
.
Направление корректировки решения
k
s
определяется как решение
задачи поиска вектора
n
s
R∈ из условий
2
1
min,
2
s →
(41)
при ограничении
kk
A
sb≥ . (42)
Здесь
(),
kk
bgx=
k
– матрица размерности mn
×
, строки которой состоят из векторов
(), 1, .
k
i
gx i m−∇ = K .
В качестве пояснения отметим, что условие (42) является
линеаризацией в точке
k
x
исходного условия (38). Действительно,
неравенство (42) является матричной формой записи следующей системы
линейных неравенств относительно
n
s
R
∈
() (), 0, 1,,.
kk
ii
gx gx s i m+∇ ≤ = K
Конечно, если вектор
s
– решение системы (42), то не обязательно
вектор
k
x
s+
будет решением исходной системы (38). Линеаризация имеет
погрешность – она не является точным выражением исходной функции.
Чем дальше отстоит вектор
k
x
s
+
от вектора
k
x
, тем менее точно условие
(42) выражает исходное условие (38). Этим объясняется введение целевой
функции (41) во вспомогательную задачу поиска направления
корректировки решения. В силу непрерывности производных функций
i
g
можно ожидать, что с уменьшением расстояния от вектора
k
x
до вектора
k
x
s+ будут уменьшаться погрешности линеаризации.
Если система линейных неравенств (42) совместная, то задача (41),
(42) имеет единственное решение. 
    Метод линеаризации. Пусть задано некоторое начальное
приближение – вектор x 0 ∈ R n . С этого вектора начинается
вычислительный процесс.
    Обозначим k = 0,1, 2, K – номера итераций. В начале k -ой итерации
считается заданным вектор x k ∈ R n . Если этот вектор удовлетворяет
условию (38)
                             g ( x k ) ≤ 0,
то вычисления заканчиваются.
     Иначе, т.е. если
                             h( x k ) > 0,                      (40)
осуществляется итеративный переход. Для этого сначала найдем
направление корректировки решения. Обозначим его s k .
     Направление корректировки решения s k определяется как решение
задачи поиска вектора s ∈ R n из условий
                             1 2
                                 s → min,                       (41)
                             2
при ограничении
                             Ak s ≥ b k .                       (42)
Здесь
                             b k = g ( x k ),
Ak – матрица размерности m × n , строки которой состоят из векторов
−∇gi ( x k ), i = 1,K m. .
    В качестве пояснения отметим, что условие (42) является
линеаризацией в точке x k исходного условия (38). Действительно,
неравенство (42) является матричной формой записи следующей системы
линейных неравенств относительно s ∈ R n
                           gi ( x k ) + ∇gi ( x k ), s ≤ 0, i = 1,K, m.
     Конечно, если вектор s – решение системы (42), то не обязательно
вектор x k + s будет решением исходной системы (38). Линеаризация имеет
погрешность – она не является точным выражением исходной функции.
Чем дальше отстоит вектор x k + s от вектора x k , тем менее точно условие
(42) выражает исходное условие (38). Этим объясняется введение целевой
функции (41) во вспомогательную задачу поиска направления
корректировки решения. В силу непрерывности производных функций gi
можно ожидать, что с уменьшением расстояния от вектора x k до вектора
 x k + s будут уменьшаться погрешности линеаризации.
       Если система линейных неравенств (42) совместная, то задача (41),
(42) имеет единственное решение.


                                      95

Страницы