Вычислительная математика: Методические указания к практическим и лабораторным работам, страница 17

Примечания:

1) при выполнении работы студенты должны составить головную программу, в которой необходимо осуществить:

а) обращение к подпрограмме N1YPFI, в которой производится выбор варианта, определение истинных значений минимума целевой функции и проектного параметра, а также задание начальной длины интервала неопределенности, что осуществляется с помощью подпрограммы N1YIIN и параметра DK,

б) ввод значения параметра останова e,

в) обращение к подпрограмме GLS, где реализован алгоритм "золотого сечения",

г) обращение к подпрограмме N1YWFP, в которой определяются погрешности e и e₀ между оценками , u() и истинными значениями проектного параметра x_* и целевой функции u(x_*),

д) запись полученных результатов в файлы данных (см. табл. 6.1 ¸ 6.5);

2) все расчеты в подпрограммах производятся с удвоенной точностью, следовательно вещественные данные в головной программе должны быть описаны как REAL*8.

Содержание отчета

1. Цель работы.

2. Постановка задачи.

3. Метод "золотого сечения".

4. Листинг головной программы.

5. Результаты вычислений (см. табл. 6.1 ¸ 6.5).

6. График целевой функции u(x).

7. График зависимости KM = f(DK).

8. Графики зависимостей lg Eо = f(lg e), KM = f(lg e).

9. Графики = f(k) (сходимость оценки проектного параметра к истинному значению x_*) и d = f(k) (изменение длины интервала неопределенности) на одном рисунке.

10. Выводы.

Методические указания

1.  Основные теоретические положения, необходимые для выполнения работы

Метод золотого сечения является одним из самых эффективных методов одномерной оптимизации, используемых при решении практических задач. Последовательное уменьшение интервала неопределенности осуществляется за счет вычисления целевой функции на каждом шаге (кроме первого) лишь в одной, выбираемой специальным образом, точке, которая называется золотым сечением. Геометрически это иллюстрирует рис. 6.1, где ищется минимум целевой функции. Пусть на нулевом шаге длина интервала неопределенности [a,b] задана в виде d = b – a = x₂₀ – x ₁₀ . Внутри [a,b] выбираются две точки x₁ и x₂ и вычисляются u(x₁) и u(x₂). Оказывается, что u(x₁) < u(x₂), следовательно, искомый минимум располагается между x₁₁ = x₁₀ и x₂₁ = x₂ . В полученном новом интервале неопределенности [x₁₁,x₂₁] длиной d₁ = x₂₁ – x₁₁  необходимо опять выбрать две точки, но одна из них x₁ уже есть, поэтому выбирается точка x₃ и вычисляется u(x₃) < u(x₁). Границы нового интервала неопределенности x₁₂ = x₁, x₂₂ = x₂₁, а  d₂ = x₂₂ –x₁₂ .

      Описанная процедура продолжается до тех пор пока не будет выполнено соотношение

 d_k = x_2k – x_1k £ e×d₀, k = 0, 1, 2, ....

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

l₂/ l = l₁/ l₂ ,

где l = l₁ + l₂ представляет собой длину интервала неопределенности. Проделав элементарные преобразования с приведенным выше соотношением

получим

l₁ = r₁×l,   r₁ = (3 – )/2 » 0,381966,

l₂ = r₂×l,   r₂ = ( – 1)/2 » 0,618034.

          Таким образом, метод золотого сечения можно представить в виде итерационного процесса, на каждом k–ом (k = 1, 2, ...) шаге которого выполняются следующие операции:

          1) определяется k–е значение x_1k в виде

x_1k = x_1(k–1) + r₁×d_(k–1)

и вычисляется u_1k = u(x_1k);

          2) определяется k–е значение x_2k в виде

x_2k = x2_(k–1) + r₂×d_(k–1)

и вычисляется u_2k = u(x_2k);

          3) определяется k–й интервал неопределенности [x_1k, x_2k] согласно следующим соображениям

          – если u_1k £ u_2k, то принимается x_1k = x_1(k–1), а x_2k вычислено в операции 2),

          – если u_1k > u_2k, то принимается x_2k = x_2(k–1), а x_1k вычислено в операции 1);

          4) находится длительность k–го интервала неопределенности

d_k = x_2k – x_1k = ×d₀

и производится сравнение

          – если d_k > e×d₀, то осуществляется переход на (k + 1)–й шаг,