Такое рассечение интервала новой точкой может быть точно рассчитано. Забегая  вперед, запишу эту пропорцию:

      

                         а             х₁         х₂                  b

      Точки х₁ и х₂ расположены симметрично относительно середины интервала (a, b).

      b-x₁              x₂-a             -1+

                   =                   =                 »   0.618

       b-a                b-a                 2                                 .

      Такое рассечение интервала и получило название золотого сечения.

      Введем  обозначения:

      D¹ = b-a – исходный интервал.

      D² – интервал, полученный после уменьшения интервала D¹ отбрасыванием его левого или правого подинтервала.

      D^К+1 – интервал, полученный после уменьшения интервала D^К.

      Рассмотрим  теперь метод золотого сечения формально. Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение всего отрезка к большей части равнялось отношению большей части к меньшей.

      Золотое сечение отрезка [a, b] производится двумя симметрично расположенными точками (х₁ и х₂).

      Т.е. (b-a)/(b-x₁)=(b-x₁)/(x₁-a)=g   и (b-a)/(x₂-a)=(x₂-a)/(b-x₂)=g.

       Можно показать, что g = (1+Ö5)/2»1.618.

      Примечательно то, что точка х₁ в свою очередь производит золотое сечение отрезка [a, x₂], т.е. (x₂-a)/(x₁-a) = (x₁-a)/(x₂-x₁) = g.

      Аналогично, точка х₂ производит золотое сечение отрезка [x₁, b].

      Итак, метод золотого сечения состоит  в том, что длины последовательных интервалов берутся в фиксированном  отношении:

      D¹/D²  =  D²/D³ = … =g.

      Из  соотношений

      D^К/D^K+1 = D^K+1/D^K+2 = g    и   D^K = D^K+1 + D^K+2

      Получаем:

      D^K/D^K+1 = (D^K+1+D^K+2)/D^K+1=1+D^K+2/D^K+1

      g = 1 + 1/g    или g² - g -1 = 0.

      Корнем  этого уравнения является золотое  сечение.

      g=(Ö5+1)/2 » 1.618   t = 1/g = (Ö5-1)/2 » 0.618.

      Можно записать формулы для точек х₁ и х₂, производящих золотое сечение на интервале [a, b]:

      x₁ = a+(1-t)(b-a) x₂ = a+t(b-a)

      Алгоритм  метода золотого сечения.

1. Ввести a, b, e-точность вычисления, t=(Ö5-1)/2
2. Вычислить:

      x₁ =b – (b-a)t;   x₂ =a + (b-a)t

3. Вычислить:

      y₁ = f(x₁);  y₂ = f(x₂)

4. если y₁£y₂, то для дальнейшего деления оставляют интервал [a, x₂]

      и выполняют следующее:

      b: = x₂;   x₂: = x₁;    y₂: = y₁;     x₁ := b-(b-a)t     y₁ := f(x₁)

      в противном случае (если y₁ > y₂), для дальнейшего деления оставляют интервал [x₁, b] и выполняют следующее:

      a := x₁;    x₁ := x₂;   y₁ := y₂;    x₂ := a+(b-a)t;    y₂ :=f(x₂);

5. Сравнение длины интервала неопределенности с заданной точностью e:

      Если (b-a)£e, то положить x* := (b-a)/2 (точка минимума), иначе (если (b-a)<e) перейти к п.4.

 

      Поиск экстремумов функции  нескольких переменных

      В этом разделе будем рассматривать  методы, используемые при поиске безусловных  минимумов функций нескольких переменных.

      Многомерная задача оптимизации формулируется  следующим образом:

      f(x)®min, xÎ Rⁿ,  Rⁿ-n-мерное пространство

      (т.е.  ограничения на х отсутствуют),

      где х=(x₁, x₂,…, x_n)^T – вектор управляемых переменных размерностью n,  f  -  скалярная целевая функция.

       Точка х является точкой глобального  минимума, если для всех xÎ Rⁿ, выполняется неравенство:  Df = f(x)-f(x)³0  (1).

      Точку глобального минимума будем обозначать х**.

      Если  формула (1) справедлива лишь в некоторой d-окрестности точки х, т.е. для всех х, таких, что ||x-x||<d, при заданном d>0, то х есть точка локального минимума.  Ее будем обозначать х*. Норма (модуль, длина) вектора

       ||x||=Ö(x, x)=Öx^T x=Öx₁² + x₂² + … +x_n²

      (x, x)=x^T x – скалярное произведение х на себя x^T = (x₁, x₂, …, x_n)

       Если же выполняется Df = f(x) - f(x) £ 0, (2)

       то х есть точка максимума (локального или глобального в соответствии с данными ранее определениями).

      Исключение  знака равенства из формул (1) и (2) позволяет определить точку строгого минимума или максимума.

       В случае, когда Df принимает как положительные и отрицательные, так и нулевые значения в зависимости от выбора точек из d - окрестности, точка х представляет собой седловую точку.

      Точка х, в которой находится минимум  или максимум, или седловая точка, должна удовлетворять условию стационарности:

       Ñf(x) = 0 (x – стационарная точка)

                        ¶f    ¶f            ¶f    ^T

      Ñf(x) =    ¶x₁,  ¶x₂,  …, ¶x_n     - градиент функции f(x) = f(x₁, x₂, …, x_n)

            Приведем некоторые  сведения из линейной алгебры.

            Квадратичной формой называется функция n переменных вида:

      A(x₁, x₂, …, x_n) = A(x) = _i=1åⁿ_j=1åⁿ q_ijx_ix_j = x^TQx, где

                x

      x =    x   , Q_(n*n) = [q_ij] – матрица.

              …

               x

      Q будем считать симметрической матрицей.

      Определения:

      1. матрица Q является положительно определенной тогда и только тогда, когда   x^TQx > 0  для всех х ¹ 0.

      2. матрица Q является положительно полуопределенной тогда и только тогда, когда значения квадратичной формы x^TQz ³ 0, для всех х и существует вектор х ¹ 0 такой, что x^TQz = 0.

      3. матрица Q является отрицательно определенной тогда и только тогда, когда -Q есть положительно определенная матрица. Другими словами – тогда и только тогда, когда x^TQx < 0 для всех х ¹ 0.

      4.  матрица Q является отрицательно полуопределенной тогда и только тогда, когда -Q есть положительно полуопределенная матрица.

      5. матрица Q является неопределенной, если квадратичная форма x^TQx может принимать как положительные, так и отрицательные значения.

      Справедливы следующие утверждения:

       1) Стационарная точка х есть  точка минимума, если H_f(x) = Ѳf(x)  - положительно полуопределенная матрица.

      H_f(x) = Ѳf(x) = [¶²f/(¶x_i¶x_j)] – матрица Гессе (гессиан)

      2) Стационарная точка х есть  точка максимума, если H_f(x) = Ѳf(x)  - отрицательно полуопределенная матрица.

1. Стационарная точка х есть седловая точка, если H_f(x) = Ѳf(x)  - неопределенная матрица.

      Необходимые условия: для наличия в точке  х* локального минимума необходимо, чтобы  выполнялось равенство:

      Ñf(x*) = 0 (чтобы точка х* была стационарной)

      и матрица H_f(x*) = Ѳf(x*) была положительно полуопределенной. (неотрицательно определенной)  H_f(x) = Ѳf(x) = [¶²f/(¶x_i¶x_j)] – матрица Гессе (гессиан).