1.9. Применение и особенности численных методов минимизации функций одной переменной

Среди рассмотренных в работе численных методов решения задач минимизации наиболее широкую сферу применения имеют методы равномерного перебора и золотого сечения. Их можно использовать для минимизации непрерывных функций. Чтобы применять метод половинного деления требуется наличие и непрерывность производной у минимизируемой функции. А чтобы использовать метод парабол необходимо наличие трех непрерывных производных. Поэтому метод парабол имеет наиболее узкую сферу применения [8]. Для применения метода последовательного перебора необходимо знать константу Липшица. В результате рассмотрения этого метода было получено:

1. Если функция монотонно убывает на, то шаг разбиенияостается постоянным и равным;

2. Если функция монотонно убывает, а затем монотонно возрастает на, то шаг разбиенияв первом случае (см. 1) остается постоянным, а во втором случае начинает расти в следствии роста величины(см. метод последовательного перебора).

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

Несмотря на некоторые недостатки, рассмотренные методы являются наиболее эффективными при решении нелинейных задач.

Глава 2. Реализация методов равномерного перебора, последовательного перебора.

В данной главе представлено описание программ, реализующих такие методы, как: метод равномерного перебора, метод последовательного перебора. Также рассмотрен пример решения задачи минимизации аналитическим методом и программно, рассмотренными численными методами. За основу была взята книга [8] из списка литературы.

2.1. Реализация методов

Описанные методы минимизации функций одной переменной были реализованы в виде функций программы minimum в приложении.

Метод Равномерного перебора

Описание и назначение этого метода было представлено выше (см. гл. 1.4), а сам метод был реализован в функции Ravnom_perebor в программе minimum.

Исходные данные:

–концы отрезка на котором решается задача;

–заранее найденная константа Липшица, равная;

–заданная точность искомого приближенного значения точки минимума;

–функция.

Результаты:

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

Метод последовательного перебора.

Описание метода:

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

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

Сам метод был реализован в среде Borland Delphi 6.

Исходные данные:

–концы отрезка на котором решается задача;

–константа Липшица, равная ;

–заданная точность искомого приближенного значения точки минимума;

–функция.

Результаты:

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

- значение функции в точке .