2. Метод хорд (секущих)

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

Предполагаем, как и в предыдущем разделе, что знаки производной унимодальной функции на концах отрезка различны: ; .

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

(7.4)

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

В качестве примера рассмотрим две итерации вычисления координаты точки максимума функции на отрезке .

.

Итерация 1

; ;

;

; .

Итерация 2

;

; .

3. Метод кубической аппроксимации

В соответствии с этим методом предполагается, что функция , которая подлежит максимизации, хорошо аппроксимируется на отрезке полиномом третьей степени. Построим этот полином по заданным значениям функции и и ее производной и (полином Эрмита) в виде

.

Коэффициенты , , , , определяемые из условий ; ; ; , равны:

; ;

; .

Точку максимума оценим точкой интерполяционного полинома, для чего приравняем производную полинома нулю:

.

Решая это квадратное уравнение, получим

, (7.5)

где ; (7.6)

. (7.7)

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

Исходные данные. – отрезок, содержащий точку максимума , , , , – параметры окончания счета.

1. Если , то , конец.

2. Вычислить по формулам (7.4)-(7.7).

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

4. Если , то , конец.

5. Если , то , , ; перейти к шагу 1.

6. ; ; ; перейти к шагу 1.

Пример 7.6. Найти точку максимума функции на отрезке ; ; .

.

Итерация 1

;

; ;

; ;

;

;

;

; .

Так как , продолжаем расчет.

, следовательно, .

Итерация 2

;

;

;

;

; .

Так как , следовательно, .

7.5. Методы второго порядка. Метод Ньютона-Рафсона

Предполагаем, что унимодальная функция дважды непрерывно дифференцируема. Тогда для решения уравнения можно применить метод касательных (Ньютона) , (7.8)

Алгоритм метода Ньютона-Рафсона

Исходные данные. -начальная оценка координаты стационарной точки, , – параметр окончания счета,

1. .

2. .

3. Если , то , конец.

4. , перейти к шагу 2.

Пример 7.7. Найти точку максимума функции на отрезке , , .

Итерация 1

; ;

; .

Итерация 2

;

; , .

Последовательность (7.8) сходится к стационарной точке лишь при выполнении определенных условий, накладываемых на вид функции и выбор начальной точки (теорема о сходимости метода касательных).

Глава 8. Графический метод решения знп.

8.1. Алгоритм графического метода решения знп

Рассмотрим задачу

(8.1)

(8.2)

(8.3)

(8.4)

где - определенные на функции, из которых хотя бы одна является нелинейной, .

Рассмотрим примеры решения ЗНП с двумя переменными. Так же как и в линейном программирования, они могут быть решены графически.

Алгоритм графического метода решения ЗНП.

Шаг 1. Строим область допустимых решений – область Р, т.е. геометрическое место точек, в котором одновременно удовлетворяются все ограничения ЗНП (8.2-8.4)( если она пуста, то ЗНП не имеет решения).

Шаг 2. Строим линию уровня (гиперповерхность) функции 8.1: .

Шаг 3. Определяем гиперповерхность наивысшего (наинизшего) уровня или устанавливаем неразрешимость ЗНП из-за неограниченности функции 8.1 сверху (снизу) на множестве Р.

Шаг 4. Находим точку области Р, через которую проходит гиперповерхность наивысшего (наинизшего) уровня, и определяем в ней значение функции 8.1.

В отличие от ЗЛП решение ЗНП может достигаться как внутри области Р (пример 8.3), так и на границе: в угловой точке (пример 8.2, 8.3, 8.5) или в неугловой точке (пример 8.1, 8.2, 8,4).