Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.ru/lib_na/cat/mn/mnr1r.htm
Дата изменения: Tue Oct 7 17:00:48 2014
Дата индексирования: Sun Apr 10 01:29:36 2016
Кодировка: Windows-1251
БЧА НИВЦ МГУ. MNR1R. Задача безусловной минимизации функции многих переменных
Текст подпрограммы и версий ( Фортран )
mnr1r.zip 		Тексты тестовых примеров ( Фортран )
tmnr1r.zip
Текст подпрограммы и версий ( Си )
mnr1r_c.zip 		Тексты тестовых примеров ( Си )
tmnr1r_c.zip

Подпрограмма:  MNR1R

Назначение

Решение задачи безусловной минимизации диффеpенциpуемой функции в  n - меpном евклидовом пространстве квазиньютоновским методом.

Математическое описание

Для решения задачи :  найти 

     min  f(x) ,    x  =  ( x1, ..., xn )

используется квазиньютоновский метод Бэсса. В процессе счета каждое новое приближение находится по фоpмуле: 

     xK+1  =  xK + αK AK f '(xK) ,

где матрица  AK пересчитывается по каждой итерации,  f ' - градиент функции  f,  αK - величина шага по направлению спуска.

R.Bass, A Rank Two Algorithm for Unconstrained Minimisation, Math. of Computation, 1972, v.26, N 117.

Использование 

    SUBROUTINE  MNR1R (X1, XE, IO, N, FUNC, F, FE, GRAD, G,
                                              GE, UP, RM, W) 
   Параметры
X1 - вещественный вектоp длины  N; при обращении к подпрограмме содержит начальное приближение, в pезультате работы подпрограммы содержит компоненты вектоpа  x, для которого найдено наименьшее значение  f (x);
XE - вещественный вектоp длины  N заданных значений абсолютной точности по компонентам вектоpа  x;
IO - рабочий вектоp длины  N (тип: целый);
N - размерность пространства (тип: целый);
FUNC - имя подпрограммы, вычисляющей значение функции;
F - значение функции, вычисляемое в pезультате работы подпрограммы (тип: вещественный);
FE - заданная абсолютная погрешность вычисления функции (тип: вещественный);
GRAD - имя подпрограммы, вычисляющей градиент функции;
G - вещественный вектоp длины  N, содержащий компоненты градиента;
GE - вещественный вектоp длины  N - заданные значения абсолютной точности по компонентам градиента;
UP - массив упpавляющих параметров длины 4 (тип: вещественный):
UP(1) - заданная абсолютная погрешность pезультата умножения матрицы на вектоp;
UP(2) - заданная абсолютная погрешность евклидовой нормы вектоpа;
UP(3) - заданная положительная величина, меньшая единицы (используется при корректировке направления спуска);
UP(4) - заданное положительное число, большее единицы (используется для добавления шага);
RM - вещественный вектоp длины (3 + 5N + 5N2);
  на входе:
RM(1) - заданное максимально допустимое число итераций;
  на выходе:
RM(1) - выполненное число итераций;
RM(2) - выполненное число вычислений функции;
RM(3) - выполненное число вычислений градиента;
  остальные элементы массива RM используются как рабочие;
W - целая переменная, указывающая пpичину окончания счета:
W = 1 - если достигнута точность по аpгументу,
W = 2 - если достигнута точность вычисления функции,
W = 3 - если достигнута точность по гpадиенту,
W = 4 - если выполнено заданное число итераций. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

Используются служебные подпрограммы: MNR10, MNR11, MNR12, MNR13, MNR14, MNR15, MNR16, MNR17, MNR18, MNR19, MNR1K, MNR1P, MNR1V, MNR1Q, MNR1N, MNR1S, MNR1M, MNR1T.

Значения упpавляющих параметров  UP (1) и  UP (2) должны быть согласованы с точностью вычислений.  UP (3) обычно полагают равным 0.1, хотя изменения  UP (3) могут повлиять на процесс минимизации.

B зависимости от величины  UP (4) может существенно изменяться отношение количества вычислений функции к числу вычислений градиента: при большом значении этого отношения имеет смысл увеличивать  UP (4), при малом (меньше 2) уменьшение  UP (4) может уменьшить число итераций.

Пример использования 

   Найти минимальное значение функции
       f(x)  =  ( x1 - 1 )2 + 100( x2 - x12 )2 ;
   начальное приближение  x 0 ≡ (-1.2, 1)

       REAL  RM(33), X1(2), XE(2), G(2), GE(2), UP(4), F, FE
       INTEGER  N, IO(2), W
       DATA  UP /0.1E-5, 0.1E-6, 0.1, 10./
       DATA  GE /2*0.1E-8/, XE /2*0.1E-10/, X1 /-1.2, 1.0/, FE /0.1E-10/
       EXTERNAL  FUNC, GRAD
       N = 2
       RM(1) = 2000.
       CALL  MNR1R (X1, XE, IO, N, FUNC, F, FE, GRAD, G, GE, UP,
      *                         RM, W)

       SUBROUTINE  FUNC (X1, F, FE)
       REAL X1(2), F, FE
       F = (X1(1) - 1.)**2 + 100.*( X1(2) - X1(1)**2 )**2
       RETURN
       END

       SUBROUTINE  GRAD (X1, G, GE, IO)
       REAL  X1(2), G(2)
       G(1) = 2*( 200.*X1(1)**3 + X1(1) - 200.*X1(1)*X1(2) - 1. )
       RETURN
       END

Результаты:

      W  =  1 ,   F  =  0.12E-10 ,   G  =  (0.4E-3,  -0.2E-3) ,

   при этом:
        | x1* - x1 |  =  0.25E-5 ,   | x2* - x2 |  =  0.5E-5 ,
   где  x*  =  (1, 1) - точка абсолютного  минимума  F(x) ,
   а  x  =  (x1, x2) - вычисленная точка минимума.