Методы решения задачи минимизации квадратичной функции. Проблемы сходимости. Григорьева К.В. - 14 стр.

UptoLike

ВУЗ: 

СПбГАСУ | Санкт-Петербург

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

Рубрика: 

14
случае графику ПО квадратичной формы соответствует поверх-
ность, которая называется эллиптическим параболоидом. Линии
уровня этой поверхности – концентрические эллипсы. Канониче-
ское уравнение эллипса
1
2
2
2
2
2
1
2
1
=+ axax
, где a
1
и a
2
– его по-
луоси. Перепишем выражение (2.2) в виде x
T
Ax =
()
∑
=
λ
n
i
ii
y
1
2
1
.
Очевидно, что длины полуосей эллипсоида (эллипса) обрат-
но пропорциональны квадратным корням из собственных чисел.
Если одно собственное число много меньше всех остальных, то
ему соответствует полуось, длина которой много больше длин
других полуосей, т. е. эллипсоид (эллипс) будет иметь сильно вы-
тянутую форму. Отношение длины большей оси к длине меньшей
оси равно
() () ()
AAA eigEIG=ν
– числу обусловленности матри-
цы А. Очевиден вывод: чем отношение
() ()
AA eigEIG
больше,
тем ярче выражен овражный характер квадратичной функции,
тем медленнее сходимость метода.
Теорема 3.1. Пусть А – симметричная ПО матрица и миними-
зируется квадратичная функция (2.1). Тогда при любом выборе
начального приближения МНГС сходится к точке x
*
минимума
функции (2.1) со скоростью геометрической прогрессии, знаме-
натель которой
() ()( ) () ()()
.eigEIGeigEIG AAAAq +−=
Причем если
()
Aeig
и
()
AEIG
близки, т. е.
() ()
1eigEIG ≈AA
,
то q мало, тогда метод сходится достаточно быстро. Если же
()
AEIG >>
()
Aeig
, то
1≈q
и следует ожидать медленной сходи-
мости метода.
Теорема 3.2. Оценка расстояния от произвольной точки
nk
Rx ∈
до точки минимума x
*
функции f (x) может быть пред-
ставлена в виде
m
xx
k
≤−
1
*
Ax
k
b+
. (3.10)
3.7. Примеры
Пример 3.1. Решить задачу минимизации квадратичной функ-
ции
()
21
2
2
2
121
442, xxxxxxf −−+=
с помощью метода наиско-
рейшего спуска.
23
7. Практическая реализация методов
минимизации квадратичной функции
средствами Microsoft Offi ce Excel 2007
Рассмотрим реализацию методов минимизации квадратичной
функции средствами Microsoft Offi ce Excel 2007 на примерах 3.1
и 3.2.
Для начала откроем книгу программы Microsoft Offi ce Excel
2007 и переименуем листы 1, 2 и 3 в «МНГС», «МПКС», «МСГ»
соответственно, как показано на рис. 7.1 и 7.2.
Рис. 7.1
Рис. 7.2
1. МНГС
На листе «МНГС» Книги 1 введем матрицу A, вектор b и соот-
ветствующие комментарии, как показано на рис. 7.3.
Рис. 7.3

Страницы