1.5. Классический метод решения задач минимизации функции одной переменной

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

Алгоритмическая схема классического метода решения задач минимизации и максимизации функции на:

1. Определить все точки подозрительные на экстремум.

2. Для каждой точки подозрительной на экстремум установить, действительно ли в этой точке функция имеет локальный экстремум или нет. Если да, то определить вид экстремума (локальный минимум или локальный максимум).

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

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

1.6. Метод половинного деления

Если функция дифференцируема, то в точках локального и глобального минимума и максимума производнаяобращается в0. Таким образом, точки локального и глобального минимума и максимума в этом случае находятся среди корней уравнения. Это обстоятельство позволяет решать некоторые задачи минимизации и максимизации, используя известные численные методы решения уравнений с одним неизвестным (половинного деления, касательных и т.п.). Следующие два метода минимизации получены именно таким способом и являются аналогами методов половинного деления и касательных. Условия применения этих методов должны обеспечить существование и единственность корня уравненияна, выполнение условий применимости соответствующего метода решения уравнений, а также то, что указанный корень уравнения совпадает именно с точкой минимума функциина,а не с точкой максимума или стационарной точкой (что тоже может быть) [8].

Пусть функция является непрерывно дифференцируемой на, причемвозрастает на, ,. Тогда функциябудет иметь наединственную точку глобального и локального минимума. В этой точке производнаяобращается в 0. Поэтому для отыскания точки минимумамы будем решать уравнениена

Легко видеть, что выполняются все условия применимости метода половинного деления, применительно к решению уравнения на(насуществует единственный кореньуравнения,непрерывна и имеет на концах отрезка значения разных знаков).

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

Дляопределенияприближенного значения точки минимума строится последовательность приближений.

рис. 6.1.

Разделимпополам точкойи выберем из двух половин, ту половину отрезка, на концах которой функция имеет значения разных знаков. Обозначимэту половину (рис. 6.1).

Разделим пополам точкойи выберем из двух половин,ту половину отрезка, на концах которой функцияимеет значения разных знаков. Обозначим эту половину(рис. 6.1) и т. д. Продолжая этот процесс будем получать остальные члены последовательностейи последовательности приближений. Вычисления членов этих последовательностей продолжают до тех пор, пока не будет выполненоусловие окончания итераций:

.

После этого вычисляется приближенное значение точки минимума

.