Текст подпрограммы и версий ( Фортран )
mnb2r.zip 		Тексты тестовых примеров ( Фортран )
tmnb2r.zip
Текст подпрограммы и версий ( Си )
mnb2r_c.zip 		Тексты тестовых примеров ( Си )
tmnb2r_c.zip
Текст подпрограммы и версий ( Паскаль )
mnb2r_p.zip 		Тексты тестовых примеров ( Паскаль )
tmnb2r_p.zip

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

Назначение

Минимизация функции многих переменных по заданному направлению на заданном отрезке методом деления пополам (дихотомический поиск).

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

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

     min  φ (x0 + λ s) ,   a0 ≤ λ ≤ b0 ,
       λ

где  x0, s ∈ En,   a0, b0, λ ∈ E1, используется метод деления отрезка пополам.

Hа каждой итерации метода строится очередной отрезок  [ak, bk] такой, что  [ak bk] ⊂ [ak - 1, bk - 1] ⊂ ... ⊂ [a0, b0] и  λ* ∈ [ai, bi] для всех  i, где λ* - точка минимума  φ (x) по направлению  S.

Вычисления заканчиваются, если для некоторого  k длина отрезка  [ak, bk] меньше заданного числа  ε > 0. Функция  φ предполагается строго квазивыпуклой по направлению  S.

B.A.Березнев. Алгоритм дихотомического поиска минимума унимодальной функции на отрезке. - Оптимизация и упpавление. М.: МГУ, 1982.

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

    SUBROUTINE  MNB2R (N, X, S, XX, A, B, EPS, C, FC, MAXK,
                                             FUN, IERR) 
   Параметры
N - разность пространства переменных (тип: целый);
X - вещественный вектоp длины  N, задающий начальную точку поиска минимума по направлению;
S - вещественный вектоp длины  N, задающий направление одномерной минимизации;
XX - вещественный вектоp длины  N, используемый в подпрограмме как рабочий;
A - вещественная переменная, задающая нижнюю гpаницу исходного отрезка неопределенности;
B - вещественная переменная, задающая верхнюю границу исходного отрезка неопределенности;
EPS - заданная точность вычисления точки минимума (тип: вещественный);
C - вещественная переменная, содержащая на выходе шаг по направлению  S до вычисленной точки минимума;
FC - вещественная переменная, содержащая на выходе минимальное значение функции по направлению;
MAXK - заданное максимальное допустимое число вычислений функции (тип: целый);
FUN - имя подпрограммы вычисления значения функции (см. замечания по использованию);
IERR - целая переменная, указывающая пpичину окончания процесса:
IERR= 0 - получено решение с заданной точностью EPS;
IERR=65 - выполнено MAXK вычислений функции;
IERR=66 - функция не является строго квазивыпуклой. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
  1. 

Длина очередного отрезка неопределенности на  k - й итерации метода pавна (B - A)/2k, поэтому нетpудно определить число вычислений функции, необходимое для сокращения исходного отрезка до длины, меньшей EPS. Параметр MAXK в связи с этим целесообразно задавать на несколько единиц большим необходимого числа вычислений функции, чтобы избежать зацикливания.

  2. 

Подпрограмма FUN составляется пользователем. Первый оператор подпрограммы должен иметь вид: 

           SUBROUTINE  FUN (X, F, FE)

        Параметры
        X  - точка, в которой вычисляется значение функции;
        F   - вычисленное значение функции;
        FE - точность, с которой вычисляется значение  F.
Имя подпрограммы вычисления функции должно быть определено в вызывающей программе в операторе EXTERNAL. Параметp FE не должен переопределяться в теле подпрограммы FUN.

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

    min  φ (x) ,   -2 ≤ x ≤ 1 ,

    φ (x)  =  log(-x) ,  если  x ≤ -1 , 
    φ (x)  =  x3 + 1 ,  если  x > -1.

       DIMENSION  X(1), S(1), XX(1)
       INTEGER  N, MAXK, IERR
       REAL  X, S, XX, A, B, EPS, C, FC
       EXTERNAL  FUNC
       DATA  N, A, B, X(1), S(1), EPS, MAXK /1, -2., 1., 0., 1., 1.E-05, 20/
       CALL  MNB2R (N, X, S, XX, A, B, EPS, C, FC, MAXK, FUNC, IERR)

       SUBROUTINE  FUNC (X, F, FE)
       DIMENSION  X(1)
       IF(X(1) + 1.) 10, 10, 2
  10 F = ALOG10(-X(1))
       GO TO 30
  20 F = X(1)**3 + 1.
  30 RETURN
       END

Результаты:

      IERR  =   0
      C        =  -1.00000095
      FC      =   4.14175E-7