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

Текст из файла

РЕФЕРАТ

В работе рассматриваются методы нахождения минимума функции одной переменной и функции многих переменных.

Пояснительная записка к курсовой работе состоит из двух основных частей: теоретической и практической.

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

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

Объем пояснительной записки: 1

Количество рисунков: 4

Количество используемых источников: 3

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. Минимум функции одного переменного

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

1.2 Золотое сечение

2. Минимум функции многих переменных

2.1 Рельеф функции

2.2 Спуск по координатам

2.3 Наискорейший спуск

2.4 Случайный поиск

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Приложение 1

Приложение 2

ВВЕДЕНИЕ

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

1. Минимум функции одного переменного

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

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

. (1)

У функции может быть много локальных минимумов. Если же выполняется

, (2)

то говорят о достижении функцией абсолютного минимума на данном множестве .

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

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

Для нахождения абсолютного минимума есть только один способ: найти все локальные минимумы, сравнить их и выбрать наименьшее значение. Поэтому задача (2) сводится к задаче (1), и мы будем в основном заниматься задачей поиска локальных минимумов.

Известно, что решение задачи (1) удовлетворяет уравнению

. (3)

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

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

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

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

1.2 Золотое сечение

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

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

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

a x₁ x₃ x₂ b

Рис. 1

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

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

.

Решение этих уравнений дает

. (4)

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

Запишем алгоритм вычисления. Для единообразия записи обозначим

,

а поочередно вводимые внутренние точки будут На первом шаге полагаем согласно (4)

. (5)

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

. (6)

Затем отбрасываем ту точку, которая более всего удалена³ от ; пусть этой точкой оказалась :

. (7)

Определим порядок расположения оставшихся трех точек на числовой оси; пусть, для определенности,

. (8)

Тогда новую внутреннюю точку введем таким соотношением⁴:

, (9)

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

. (10)

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

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

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

2. Минимум функции многих переменных

2.1 Рельеф функции

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов курсовой работы