Методичка по курсовым и лабораторным работам (1085639), страница 3
Текст из файла (страница 3)
Рис 1.3
Золотое сечение осуществляется двумя точками x1 и x2, расположенными симметрично относительно середины отрезка (рис.1.3, справа). Нетрудно проверить, что
= 
= 
, (1.10)
= 
= . (1.11)
Точка x1 осуществляет золотое сечение не только отрезка [a, b], но и отрезка [a, x2], а точка x2 осуществляет золотое сечение не только отрезка [a, b], но и отрезка [x1, b]. Действительно,
= 
= ,
= 
= .
Из (1.10) и (1.11) получаем:
x1 = a + 
, x2 = a +
. (1.12)
Формулы (1.12) являются основными расчетными формулами метода золотого сечения.
Из (1.12) следует, что x1 + x2 = a + b. Если обозначить r = 
, то формулы (1.12) можно переписать так:
x1 = b – r(b – a), x2 = a + r(b – a) (1.13)
Процедура деления отрезка [a, b] такая же, как и для методов дихотомии и Фибоначчи. Вычисляются значения функции в выбранных точках: f(x1) и f(x2). Определяется новый отрезок локализации [a1, b1] следующим образом:
если f(x1) £ f(x2), то a1 = a, b1 = x2;
если f(x1) > f(x2), то a1 = x1, b1 = b.
Далее процедура деления отрезка [a1, b1] повторяется с использованием формул (1.12) или (1.13).
Так же, как и в методе Фибоначчи, одна из пробных точек x1, x2 станет пробной точкой на новом отрезке локализации. Поэтому на каждой итерации достаточно определить только одно значение f(x), так как другое уже найдено на предыдущей итерации.
В конце вычислений можно взять в качестве приближенного значения x* середину последнего из полученных отрезков.
После выполнения n итераций погрешность удовлетворяет следующему неравенству:
en = 
< 
.
Условием окончания вычислений является выполнение неравенства en <e.
Алгоритм 1.4 (Алгоритм метода золотого сечения).
Шаг 1. Ввести исходные данные: a, b, e. Положить r = , en = 
.
Шаг 2. Определить x1 и x2 по формулам (1.13).
Шаг 3. Вычислить f(x1) и f(x2).
Шаг 4. Проверить критерий окончания вычислений. Если en <e, перейти к шагу 5, иначе – к шагу 6.
Шаг 5. Перейти к новому отрезку локализации и новым пробным точкам. Если f(x1) £ f(x2), то положить b = x2, x2 = x1, f(x2) = f(x1), x1 = b – r(b – a) и вычислить f(x1). Иначе положить a = x1, x1 = x2, f(x1) = f(x2), x2 = a + r(b – a) и вычислить f(x2).
Положить en = ren и перейти к шагу 4.
Шаг 6. Положить x* » 
. Вычислить f * » f(x*).
Пример 1.5.
Методом золотого сечения решим задачу, рассмотренную ранее: f(x) = x4 + e –x ® min, x Î [0, 1], e = 0.1.
Результаты вычислений приведены в табл. 1.6.
Таблица 1.6
| Номер итерации | a | b | en | x1 | x2 | f(x1) | f(x2) | Сравнение f(x1) и f(x2) |
| 1 2 3 4 5 | 0 0.382 0.382 0.382 0.472 | 1 1.000 0.764 0.618 0.618 | 0.5 0.309 0.191 0.118 0.073 | 0.382 0.618 0.528 0.472 | 0.618 0.764 0.618 0.528 | 0.704 0.685 0.668 0.673 | 0.685 0.807 0.685 0.668 | f(x1) > f(x2) f(x1) < f(x2) f(x1) < f(x2) f(x1) > f(x2) |
Вычисления прекращаются после 5-ой итерации, так как требуемая точность достигнута (0.073 < 0.1).
Таким образом, x* » 
» 0.55 и f(x*) » 0.67.
1.7. Метод средней точки.
Все методы, рассмотренные до сих пор, основаны на предположении об унимодальности исследуемой функции. Эти методы используют вычисление значений функции в некоторых точках и не требуют вычисления значений производной функции. Использование информации о производной позволит повысить эффективность решения задачи оптимизации.
Рассмотрим метод средней точки, который называется также методом бисекции или методом деления отрезка пополам.
Пусть f(x) – унимодальная, непрерывно дифференцируемая на отрезке [a, b] функция и на этом отрезке точка x* является единственной стационарной точкой. Сведем задачу нахождения минимума функции f(x) к решению нелинейного уравнения
f '(x) = 0. (1.14)
Положим a0 = a, b0 = b.
Так как функция f '(x) удовлетворяет условию (1.14), то она принимает на концах отрезка [a0, b0] значения разных знаков, т.е.
f(a0)f(b0) < 0.
Разделим отрезок [a0, b0] пополам. Получим точку x0 = 
. Вычислим f '(x0). Если f '(x0) = 0, то x0 – искомый корень, и задача решена. Если f '(x0) ¹ 0, то f '(x0) – число определенного знака: f '(x0) > 0, либо f '(x0) < 0. Тогда либо на концах отрезка [a0, x0], либо на концах отрезка [x0, b0] значения функции f '(x) имеют разные знаки. Обозначим такой отрезок [a1, b1]. Очевидно, что x*Î [a1, b1], и длина отрезка [a1, b1] в два раза меньше, чем длина отрезка [a0, b0]. Поступим аналогично с отрезком [a1, b1]. В результате получим либо корень x*, либо новый отрезок [a2, b2], и т.д. (рис.1.4 ).
Рис. 1.4
Середина n-го отрезка xn = 
. Очевидно, что длина отрезка [an, bn] будет равна 
, а т. к. x*Î [an, bn], то
| xn – x*| £ £ 
. (1.15)
Оценка (1.15) характеризует погрешность метода средней точки и указывает на скорость сходимости: метод сходится со скоростью геометрической прогрессии, знаменатель которой q = 1/2.
Если задана требуемая точность e , то процесс вычислений следует закончить, когда выполнится условие ê f '(xn) ê£ e, после чего полагают x* » xn.
Алгоритм 1.5 (Алгоритм метода средней точки).
Шаг 1. Ввести исходные данные: a, b, e.
Шаг 2. Определить x0 = .
Шаг 3. Вычислить f '(x0).
Шаг 4. Проверить критерий окончания вычислений. Если êf '(x0) ê£ e, , перейти к шагу 6, иначе – к шагу 5.
Шаг 5. Перейти к новому отрезку локализации [a, b]. Если f '(x0) > 0, то положить b = x0. Иначе положить a = x0. Перейти к шагу 2.
Шаг 6. Положить x* » x0. Вычислить f'(x*).
Пример 1.6.
Методом средней точки решим задачу, рассмотренную ранее:
f(x) = x4 + e - x ® min, x Î [0, 1], e = 0.02.
Очевидно, что f '(x) = 4x3 – e –x.
Результаты вычислений приведены в табл. 1.7.
Таблица 1.7
| Номер итерации | a | b | x0 | f '(x0) | Знак f '(x0) |
| 1 2 3 4 5 | 0 0.5 0.5 0.5 0.5 | 1 1.000 0.750 0.625 0.563 | 0.5 0.750 0.625 0.563 0.531 | -0.107 1.215 0.441 0.142 0.012 | – + + + |
Вычисления прекращаются после 5-ой итерации, так как требуемая точность достигнута (0.012 < 0.02).
Таким образом, x* » 0.531 и f(x*) » 0.668.
1.8. Метод Ньютона.
Пусть f(x) – дважды непрерывно дифференцируемая функция, причем f ''(x) > 0. Тогда, как уже указывалось в предыдущем разделе, решение задачи минимизации функции f (x) сводится к решению нелинейного уравнения f '(x) = 0.
Метод Ньютона является наиболее эффективным методом решения нелинейных уравнений.
Пусть корень x* Î [a, b], так, что f '(a)f '(b) < 0. Положим x0 = b. Проведем касательную к графику функции y = f '(x) в точке B0 = (x0, f '(x0)) (рис. 1.5).
Рис. 1.5
Уравнение касательной будет иметь вид:
y – f '(x0) = f"(x0)(x – x0). (1.16)
Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью OX, т. е. положив в (1.16) y = 0, x = x1:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
