Северин В.П. Методы ОП

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

1)титульный лист установленного образца с указанием организации, названия учебной дисциплины, темы работы, номера варианта, исполнителя и принимающего, города, года;

2)постановка задачи минимизации целевой функции, включающая задание функции, начальную точку и точку минимума;

3)теоретическое описание метода уменьшения интервала;

4)алгоритм метода;

5)распечатки используемых компьютерных программ;

6)табличное представление процесса минимизации и его итоги – количество вычислений значений целевой функции, минимальное значение функции и соответствующее ему значение точки минимума, достигнутую точность;

7)двумерный график траектории поиска со всеми точками;

8)анализ полученных результатов;

9)выводы о проделанной лабораторной работе.

Контрольные вопросы

1.Чем отличается пассивная стратегия поиска?

2.Какое назначение метода равномерного поиска?

3.Опишите метод равномерного поиска.

4.Как оценивается эффективность метода равномерного поиска?

5.Какие преимущества и недостатки метода равномерного поис-

ка?

6. Чем отличаются последовательные методы одномерного поис-

ка?

7.Какое назначение метода дихотомии?

8.Какие основные принципы метода дихотомии?

9.Опишите метод дихотомии.

10.Как оценивается эффективность метода дихотомии?

11.Какого порядка метод дихотомии?

12.В чем заключаются преимущества и недостатки метода дихо-

81

томии?

13.Какое назначение метода деления интервала пополам?

14.Опишите метод деления интервала пополам.

15.Как оценивается эффективность метода деления интервала пополам?

16.Какого порядка метод деления интервала пополам?

17.Какие достоинства и недостатки метода деления интервала пополам?

18.Какая задача привела к открытию чисел Фибоначчи?

19.По какой рекуррентной формуле определяются числа Фибона-

ччи?

20.Запишите 10 первых чисел Фибоначчи.

21.Укажите свойства чисел Фибоначчи.

22.Выведите формулу Бине для чисел Фибоначчи.

23.Какое назначение метода Фибоначчи?

24.Опишите метод Фибоначчи.

25.Выведите общую формулу для длин интервалов неопределенности в методе Фибоначчи.

26.Как начинается поиск минимума в методе Фибоначчи?

27.Как оценивается эффективность метода Фибоначчи?

28.Какого порядка метод Фибоначчи?

29.В чем заключаются преимущества и недостатки метода Фибо-

наччи?

30.Какая задача привела к открытию золотого сечения?

31.Выведите уравнение золотого сечения.

32.Приведите численное представление золотого сечения.

33.Опишите способ геометрического построения золотого сечения с использованием линейки и циркуля.

34.Укажите алгебраические свойства золотого сечения.

35.Какова особенность золотой прогрессии?

36.Какова связь между числами Фибоначчи и золотым сечением?

37.Какое назначение метода золотого сечения?

38.Опишите метод золотого сечения.

82

39.В чем заключается сходство и различие методов Фибоначчи и золотого сечения.

40.Как начинается поиск минимума в методе золотого сечения?

41.Как оценивается эффективность метода золотого сечения?

42.Сравните эффективность методов Фибоначчи и золотого сече-

ния.

43.Какого порядка метод золотого сечения?

44.Какие преимущества и недостатки метода золотого сечения?

45.Какое назначение метода адаптации шага?

46.Опишите метод адаптации шага.

47.По какому правилу изменяется шаг поиска в методе адаптации

шага?

48.Как оценивается эффективность метода адаптации шага?

49.Какого порядка метод адаптации шага?

50.Какие достоинства и недостатки метода адаптации шага?

51.На какие группы можно разделить методы уменьшения интервала неопределенности?

52.Сравните эффективность методов уменьшения интервала неопределенности.

83

где коэффициенты , и определяются по трем точкам, получен-

ным с помощью алгоритма метода Свенна – (a, fa ) , (x, fx ) и (b, fb ) ,

где a x b . Дифференцируя уравнение параболы (4.1), имеем

y 2x .

По необходимому условию существования экстремума y 0 получим точку минимума параболы

Для определения этой точки достаточно определить лишь параметры и уравнения (4.1). Подставляя в уравнение параболы (4.1)

координаты трех известных точек функции f (x) , составим систему уравнений:

Вычитая из второго уравнения первое, а из третьего – второе, имеем:

Решим полученную систему по правилу Крамера:

85

[a, b] , как и в большинстве методов предыдущего раздела, делится двумя точками x и z на три части. По правилу исключения интервалов на основании сравнения значений целевой функции во внутренних точках интервала неопределенности fx f (x) и fz f (z) та часть, которая заведомо не содержит минимума, отбрасывается, и интервал [a, b] уменьшается. Для оставшегося интервала с известной одной внутренней точкой опять применяется квадратичная интерполяция по формуле (4.4). Итерации продолжаются до тех пор, пока либо расстояние между точками x и z не станет меньше заданной наперед величины , либо длина интервала неопределенности не станет меньше допустимой погрешности.

Вследствие ошибок округления при вычислениях может оказаться, что значение z , вычисленное по формуле (4.4), окажется вне ин-

86

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

Рассмотренный метод нулевого порядка называется методом квадратичной интерполяции с тремя точками. На основании рабочих формул (4.3) и (4.4) составлен алгоритм метода квадратичной интерполяции.

А л г о р и т м м е т о д а к в а д р а т и ч н о й и н т е р п о л я ц и и

87

4.2. Метод кубической интерполяции с четырьмя точками

Метод кубической интерполяции основан на аппроксимации минимизируемой функции f (x) полиномом третьей степени

Четыре неизвестных параметра полинома (4.5) определим по четырем точкам минимизируемой функции f (x) : (x1, y1) , (x2 , y2 ) , (x3, y3 ) , (x4 , y4 ) . Три из этих точек получим в результате поиска интервала неопределенности методом Свенна, а четвертую точку – с помощью квадратичной интерполяции по первым трем точкам. Подставляя в равенство (4.5) координаты четырех точек, составим систему из четырех линейных алгебраических уравнений

88

Для рационального вычисления этих определителей введем обозначения:

89

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

Рассмотренный метод нулевого порядка называется методом кубической интерполяции с четырьмя точками. На основании формул (4.7)–(4.13) составлен алгоритм метода кубической интерполяции.

А л г о р и т м м е т о д а к у б и ч е с к о й и н т е р п о л я ц и и с

1.Вычислить p (x a)( fb fx ) , q (b x)( fa fx ) , s p q .

2.Если s 0 , то перейти к шагу 32.

3.Вычислить y 0,5 ( p(a x) q(b x)) / s .

4.Если y a или y b , то перейти к шагу 32.

90