Размещено на http://www.allbest.ru/

Кафедра Высшей математики Курсовая работа по информатике

Тема: Поиск минимума функции многих переменных методом наискорейшего спуска

Нижний Новгород 2007

Содержание

1. Постановка задачи

1.1 Безусловная минимизация многомерных функций

1.2 Минимизация функций методом наискорейшего спуска

2. Методика решения задачи

2.1 Алгоритм метода наискорейшего спуска

2.2 Вычислительная схема

3. Блок-схемы алгоритма

4. Текст программы на языке Pascal

Вывод

Литература

1. Постановка задачи

1.1 Безусловная минимизация многомерных функций

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

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

F(X)=f(x₁, x_2, x₃, … x_n)

Минимум дифференцируемой функции F(X)=f(x₁, x_2, x₃, … x_n) можно найти, исследуя ее значения в критических точках, которые определяются из решения системы дифференциальных уравнений

…,

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

Существуют специальные методы поиска минимума функции многих переменных, основанные на целенаправленном поиске. Их называют методами спуска.

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

Решается задача минимизации функции F(X)=f(x₁, x_2, x₃, … x_n) на всем пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности Х⁰, Х¹, Х²,…, Х^К. В качестве начального приближения выбирается любая точка Х^0Î E_n. Последовательные приближения Х¹, Х²,… строятся по следующей схеме:

1. в точке Хⁱ выбирают направление спуска – Sⁱ

2. находят (i+1) приближение по формуле

Хⁱ⁺¹= Х^{i –} pⁱ Sⁱ

Направление Sⁱ выбирают таким образом, чтобы обеспечить неравенство F(Хⁱ⁺¹)<F(Хⁱ) по крайней мере, для малых значений величины pⁱ. На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет.

Число pⁱ определяет расстояние от точки Хⁱ до точки Хⁱ⁺¹. Это число называется длиной шага или просто шагом. Основная задача при выборе величины pⁱ – это обеспечить выполнение неравенства F(Хⁱ⁺¹)<F(Хⁱ).

Одним из наиболее простых способов определения направления спуска является выбор в качестве направления спуска Sⁱ одного из координатных векторов ±e₁, ±e₂, …, ±e_n, вследствие чего у Хⁱ на каждой итерации изменяется лишь одна из компонент. Методы спуска, основанные на выборе пути оптимизации вдоль координатных векторов, называются методами покоординатного спуска.

Другим способом определения направления спуска является выбор в качестве направления спуска Sⁱ направления наибольшего убывания функции. Известно, что направление наибольшего возрастания функции характеризуется ее градиентом. Следовательно направление, противоположное градиентному, укажет путь, ведущий к минимуму функции.

Методы, основанные на выборе пути оптимизации с помощью градиента, называются градиентными. К ним относится и метод наискорейшего спуска.