РЕФЕРАТ
В работерассматриваются методы нахождения минимума функции одной переменной и функциимногих переменных.
Пояснительнаязаписка к курсовой работе состоит из двух основных частей: теоретической ипрактической.
Втеоретической части рассматривается поиск минимума функции одной переменнойметодом золотого сечения, поиск минимума функции многих переменных – методамипокоординатного спуска, наискорейшего спуска и случайного поиска.
Практическаячасть содержит разработку программного обеспечения вычисления локальногоминимума функции Химмельблау методом покоординатного спуска, реализованную наязыке 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) называют задачей наминимум функционала.
Длянахождения абсолютного минимума есть только один способ: найти все локальныеминимумы, сравнить их и выбрать наименьшее значение. Поэтому задача (2)сводится к задаче (1), и мы будем в основном заниматься задачей поискалокальных минимумов.
Известно,что решение задачи (1) удовлетворяет уравнению
/>. (3)
Еслимножество /> естьчисловая ось, то написанная здесь производная является обычной производной, итогда уравнение (3) есть просто одно (нелинейное) уравнение с однимнеизвестным. Для />-мерного векторного пространствасоотношение (3) оказывается системой нелинейных уравнений />. Для пространствафункций уравнение (3) является дифференциальным или интегро-дифференциальным. Впринципе такие уравнения можно решать итерационными методами. Однако этиуравнения нередко имеют сложный вид, так что итерационные методы их решениямогут очень плохо сходиться или вообще не сходиться. Поэтому в данной главе мырассмотрим численные методы, применимые непосредственно к задаче (1), безприведения ее к форме (3).
Пусть/> являетсянекоторым множеством, принадлежащим какому-то пространству. Тогда (1) называютзадачей на минимум в ограниченной области. В частности, если множество /> выделено изпространства с помощью ограничивающих условий типа равенств, то задачу (1)называют задачей на условный экстремум; такие задачи методом неопределенныхмножителей Лагранжа часто можно свести к задачам на безусловный экстремум.Однако при численном решении обычно удобнее иметь дело непосредственно с исходнойзадачей (1), хотя при ее решении в ограниченной области возникают своитрудности.
Функция/> можетиметь на множестве /> более одного локального минимума.В конкретных прикладных задачах далеко не всегда удается заранее исследоватьсвойства функции. Поэтому желательно, чтобы численный алгоритм позволялопределить число минимумов и их расположение и аккуратно найти абсолютныйминимум.
Задачуназывают детерминированной, если погрешностью вычисления (илиэкспериментального определения) функции /> можно пренебречь. В противномслучае задачу называют стохастической. Мы будем рассматривать в основномдетерминированные задачи. Для решения стохастических задач есть специальныеметоды, но они очень медленные, и применять их к детерминированным задачамневыгодно.
1.2 Золотое сечение
Вэтом параграфе мы рассмотрим задачу нахождения минимума функции однойдействительной переменной. Эта одномерная задача нередко возникает впрактических приложениях. Кроме того, большинство методов решения многомерныхзадач сводится к поиску одномерного минимума.
Сейчасмы рассмотрим метод золотого сечения, применимый к недифференцируемым функциям.Будем считать, что /> задана и кусочно-непрерывна наотрезке />,и имеет на этом отрезке (включая его концы) только один локальный минимум.Построим итерационный процесс, сходящийся к этому минимуму.
/>Вычислим функцию наконцах отрезка, а также в двух внутренних точках />, сравним все четыре значенияфункции между собой и выберем среди них наименьшее. Пусть наименьшим оказалось />. Очевидно,минимум расположен в одном из прилегающих к нему отрезков (см. рис. 1). Поэтомуотрезок /> можноотбросить и оставить отрезок />. Первый шаг процесса сделан./> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
/>/>/>/>/>a x1 x3 x2 b
Рис.1
Наотрезке /> снованадо выбрать две внутренние точки, вычислить в них и на концах отрезка значенияфункции, и сделать следующий шаг процесса. Но на предыдущем шаге вычислений мыуже нашли /> наконцах нового отрезка /> и в одной его внутренней точке />. Поэтомудостаточно выбрать внутри /> еще одну точку />, определить в нейзначение функции и провести необходимые сравнения. Это вчетверо уменьшает объемвычислений на одном шаге процесса.
Каквыгодно размещать точки? Всякий раз мы делим оставшийся отрезок на три части(причем одна из точек деления уже определена предыдущими вычислениями) и затемотбрасываем один из крайних отрезков. Очевидно, надо, чтобы следующий отрезокбыл поделен подобно предыдущему. Для этого должны выполняться соотношения
/>.
Решениеэтих уравнений дает
/>. (4)
Послепроведения очередного вычисления отрезок сокращается в /> раза; после /> вычислений функции онсоставляет /> долюпервоначальной величины (три первых вычисления в точках /> еще не сокращаютотрезок). Следовательно, при /> длина оставшегося отрезкастремится к нулю как геометрическая прогрессия со знаменателем />, т. е. метод золотогосечения всегда сходится, причем линейно.
Запишемалгоритм вычисления. Для единообразия записи обозначим
/>,
апоочередно вводимые внутренние точки будут /> На первом шаге полагаем согласно(4)
/>. (5)
Послесравнения может быть отброшена точка с любым номером, так что на следующихшагах оставшиеся точки будут перенумерованы беспорядочно. Пусть на данномотрезке есть четыре точки /> из которых какие-то две являютсяконцами отрезка. Выберем ту точку, в которой функция принимает наименьшеезначение; пусть это оказалась />:
/>. (6)
Затемотбрасываем ту точку, которая более всего удалена[3]от />; пустьэтой точкой оказалась />:
/>. (7)
Определимпорядок расположения оставшихся трех точек на числовой оси; пусть, дляопределенности,
/>. (8)
Тогдановую внутреннюю точку введем таким соотношением[4]:
/>, (9)
иприсвоим ей очередной номер. Минимум находится где-то внутри последнегоотрезка, />.Поэтому итерации прекращаем, когда длина этого отрезка станет меньше заданнойпогрешности />:
/>. (10)
Методзолотого сечения является наиболее экономичным аналогом метода дихотомииприменительно к задачам на минимум. Он применим даже к недифференцируемымфункциям и всегда сходится; сходимость его линейна. Если на отрезке /> функция имеетнесколько локальных минимумов, то процесс сойдется к одному из них (но необязательно к наименьшему).
Этотметод нередко применяют в технических или экономических задачах оптимизации,когда минимизируемая функция недифференцируема, а каждое вычисление функции –это дорогой эксперимент.
Методзолотого сечения рассчитан на детерминированные задачи. В стохастическихзадачах из-за ошибок эксперимента можно неправильно определить соотношениемежду значениями функций в точках; тогда дальнейшие итерации пойдут по ложномупути. Поэтому если различия функций в выбранных точках стали того же порядка,что и ошибки эксперимента, то итерации надо прекращать. Поскольку вблизиминимума чаще всего />~/>, то небольшая погрешность функцииприводит к появлению довольно большой области неопределенности />~/>.
2. Минимум функции многихпеременных
2.1 Рельеф функции
Основныетрудности многомерного случая удобно рассмотреть на примере функции двухпеременных />.Она описывает некоторую поверхность в трехмерном пространстве с координатами />. Задача /> означает поискнизшей точки этой поверхности.
/>/>/>Изобразим рельеф этойповерхности линиями уровня. Проведем равноотстоящие плоскости /> и найдем линии ихпересечения с поверхностью />; проекции этих линий на плоскость/> называютлиниями уровня. Направление убывания функции будем указывать штрихами,рисуемыми около линий уровня. Полученная картина напоминает топографическоеизображение рельефа горизонталями. По виду линий уровня условно выделим тритипа рельефа: котловинный, овражный и неупорядоченный.
/>/>
а)б)/> /> /> /> /> /> />
в)
Рис.2 г)
Прикотловинном рельефе линии уровня похожи на эллипсы (рис. 1, а). В малойокрестности невырожденного минимума рельеф функции котловинный. В самом деле,точка минимума гладкой функции определяется необходимыми условиями
/>, (11)
иразложение функции по формуле Тейлора вблизи минимума имеет вид
/>, (12)
причемквадратичная форма (12) – положительно определенная[5],иначе эта точка не была бы невырожденным минимумом. А линии уровнязнакоопределенной квадратичной формы – это эллипсы.
Случай,когда все вторые производные равны в этой точке нулю и минимум определяетсяболее высокими производными, по существу ничего нового не дает, и мы не будемего специально рассматривать (линии уровня вместо эллипсов будут похожими наних кривыми четвертого порядка).
Отметим,что условию (11) удовлетворяют также точки максимумов и седловые точки. Но вточках максимумов квадратичная форма (12) отрицательно определенная, а вседловинах она знакопеременна.
Вблизиминимума функция мало меняется при заметных изменениях переменных. Поэтому дажеесли мы не очень точно определим те значения переменных, которые должны минимизироватьфункцию, то само значение функции при этом обычно будет мало отличаться отминимального.
Рассмотримовражный тип рельефа. Если линии уровня кусочно-гладкие, то выделим на каждойиз них точку излома. Геометрическое место точек излома назовем истиннымоврагом, если угол направлен в сторону возрастания функции, и гребнем – если всторону убывания (рис. 2, б). Чаще линии уровня всюду гладкие, но на нихимеются участки с большой кривизной; геометрические места точек с наибольшейкривизной назовем разрешимыми оврагами или гребнями (рис. 2, в). Например,рельеф функции
/>, (13)
изображенныйна этом рисунке, имеет ярко выраженный извилистый разрешимый овраг, «дно»которого – синусоида, а низшая точка – начало координат.
Вфизических задачах овражный рельеф указывает на то, что вычислитель не учелкакую-то закономерность, имеющую вид связи между переменными. Обнаружение иявный учет этой закономерности облегчает решение математической задачи. Так,если в примере (13) ввести новые переменные />, то рельеф становитсякотловинным.
Неупорядоченныйтип рельефа (рис. 2, г) характеризуется наличием многих максимумов, минимумов иседловин. Примером может служить функция
/>, (14)
рельефкоторой изображен на этом рисунке; она имеет минимумы в точках с координатами /> и максимумы вточках, сдвинутых относительно минимумов на /> по каждой координате.
Всеэффективные методы поиска минимума сводятся к построению траекторий, вдолькоторых функция убывает; разные методы отличаются способами построения такихтраекторий. Метод, приспособленный к одному типу рельефа, может оказатьсяплохим на рельефе другого типа.
2.2 Спуск по координатам
Казалосьбы, для нахождения минимума достаточно решить систему уравнений типа (11)методом линеаризации или простых итераций и отбросить те решения, которыеявляются седловинами или максимумами. Однако в реальных задачах минимизации этиметоды обычно сходятся в настолько малой окрестности минимума, что выбратьподходящее нулевое приближение далеко не всегда удается. Проще и эффективнеепровести спуск по координатам. Изложим этот метод на примере функции трехпеременных />.
Выберемнулевое приближение />. Фиксируем значения двухкоординат />.Тогда функция будет зависеть только от одной переменной />; обозначим ее через />. Найдем минимумфункции одной переменной /> и обозначим его через />. Мы сделалишаг из точки /> в точку /> по направлению, параллельному оси/>; на этомшаге значение функции уменьшилось.
Затемиз новой точки сделаем спуск по направлению, параллельному оси />, т. е. рассмотрим />, найдем ееминимум и обозначим его через />. Второй шаг приводит нас в точку />. Из этой точкиделаем третий шаг – спуск параллельно оси /> и находим минимум функции />. Приход вточку /> завершаетцикл спусков.
Будемповторять циклы. На каждом спуске функция не возрастает, и при этом значенияфункции ограничены снизу ее значением в минимуме />. Следовательно, итерации сходятсяк некоторому пределу />. Будет ли здесь иметь месторавенство, т. е. сойдутся ли спуски к минимуму и как быстро?
Этозависит от функции и выбора нулевого приближения. На примере функции двухпеременных легко убедиться, что существуют случаи сходимости спуска покоординатам к искомому минимуму и случаи, когда этот спуск к минимуму несходится.
Будемдвигаться по выбранному направлению, т. е. по некоторой прямой в плоскости />. В техучастках, где прямая пересекает линии уровня, мы при движении переходим отодной линии уровня к другой, так что при этом движении функция меняется(возрастает или убывает, в зависимости от направления движения). Только в тойточке, где данная прямая касается линии уровня (рис. 3, а), функция имеетэкстремум вдоль этого направления. Найдя такую точку, мы завершаем в ней спускпо первому направлению, и должны начать спуск по второму направлению (посколькунаправления мы сейчас выбираем параллельно координатным осям, то второе направлениеперпендикулярно первому).
Пустьлинии уровня образуют истинный овраг. Тогда возможен случай (рис. 3, б), когдаспуск по одной координате приводит нас на «дно» оврага, а любое движение последующей координате (пунктирная линия) ведет нас на подъем. Никакой дальнейшийспуск по координатам невозможен, хотя минимум еще не достигнут; процесс спускапо координатам в данном случае не сходится к минимуму.
Наоборот,если функция достаточно гладкая, то в некоторой окрестности минимума процессспуска по координатам сходится к этому минимуму. Пусть функция имеетнепрерывные вторые производные, а ее минимум не вырожден. Для простоты опятьрассмотрим функцию двух переменных />. Выберем некоторое нулевоеприближение /> ипроведем линию уровня через эту точку. Пусть в области />, ограниченной этой линией уровня,выполняются неравенства, означающие положительную определенность квадратичнойформы (12):
/>. (15)
Докажем,что тогда спуск по координатам из данного нулевого приближения сходится кминимуму, причем линейно.
Значенияфункции вдоль траектории спуска не возрастают; поэтому траектория не можетвыйти из области />, и неравенства (15) будутвыполняться на всех шагах. Рассмотрим один из циклов, начинающийся в точке /> (рис. 3, а).Предыдущий цикл окончился поиском минимума по направлению />, следовательно, /> и />. Первый шагнового цикла спускает нас по направлению /> в точку />, в которой /> и />. Поскольку вторыепроизводные непрерывны, можно применить теорему о среднем; получим
/>
гдечерез /> обозначенырасстояния между точками. Отсюда получаем />. Выполним второй шаг цикла –спуск по направлению /> в точку />, после которого /> и />. Аналогичныерассуждения дают соотношение с />. Объединяя эти неравенства,найдем
/>.
Следовательно,за один цикл /> уменьшается в /> раз; то же справедливодля />, еслирассмотреть цикл, сдвинутый на один шаг, т. е. начинающийся в точке /> и кончающийсяв точке />.
Значит,когда число циклов />, то все первые производныелинейно стремятся к нулю:
/> и />~/>.
Первыепроизводные одновременно обращаются в нуль в точке минимума и вблизи негоявляются линейными однородными функциями приращений координат. Поэтомукоординаты точек спуска линейно стремятся к координатам точки минимума, т. е. вданном случае спуск по координатам сходится, причем линейно.
Случай(15) заведомо реализуется в достаточно малой окрестности невырожденногоминимума, ибо эти условия эквивалентны требованию положительной определенностиквадратичной формы (12). Такими образом, вблизи невырожденного минимумадостаточно гладкой функции спуск по координатам линейно сходится к минимуму. Вчастности, для квадратичной функции этот метод сходится при любом нулевомприближении.
Фактическаяскорость сходимости будет неплохой при малых />, когда линии уровня близки кэллипсам, оси которых параллельны осям координат. Для эллипсов, сильновытянутых под значительным углом к осям координат, величина /> и сходимость оченьмедленная.
Еслисходимость медленная, но траектория уже попала в близкую окрестность минимума,то итерации можно уточнять процессом Эйткена; разумеется, при этом надо брать вкачестве исходных значения не на трех последних спусках, а на трех циклахспусков (т. е. не точки />, а точки /> и третья точка, которой нет нарис. 3, а).
Разрешимыйовраг напоминает сильно вытянутую котловину (см. рис. 3, б). При попаданиитраектории спуска в такой овраг сходимость становится настолько медленной, чторасчет практически невозможно вести. Отметим, что в стохастических задачахналичие ошибок эквивалентно превращению истинных оврагов и гребней вразрешимые; расчет при этом можно продолжать, хотя практическая ценность такогорасчета невелика: сходимость очень медленная.
Методспуска по координатам несложен и легко программируется на ЭВМ. Но сходится онмедленно, а при наличии оврагов – очень плохо. Поэтому его используют вкачестве первой попытки при нахождении минимума.
Пример.Рассмотрим квадратичную функцию /> и выберем нулевое приближение />. Выполняявычисления, получим
/>.
Уточнениепо Эйткену дает />, т. е. точное положение минимума(заметим, что делать уточнение с использованием нулевого приближения нельзя).
2.3 Наискорейший спуск
Спускатьсяможно не только параллельно осям координат. Вдоль любой прямой /> функция зависит толькоот одной переменной, />, и минимум на этой прямой можнонайти.
Наиболееизвестным является метод наискорейшего спуска, когда выбирается />, т. е. направление, вкотором функция быстрее всего убывает при бесконечно малом движении из даннойточки. Спуск по этому направлению до минимума определяет новое приближение />. В этой точкеснова определяется градиент и делается следующий спуск.
Однакоэтот метод значительно сложнее спуска по координатам, ибо требуется вычислятьпроизводные и градиент и переходить к другим переменным. К тому же, посходимости наискорейший спуск не лучше спуска по координатам. При попаданиитраектории в истинный овраг спуск прекращается, а в разрешимом овраге сильнозамедляется.
Еслифункция является положительно определенной квадратичной функцией
/>, (16)
тоформулы наискорейшего спуска приобретают несложный вид. Вдоль прямой /> функция (16)квадратично зависит от параметра />:
/>. (17)
Изуравнения /> легконаходим ее минимум
/>, (18)
дающийнам следующую точку спуска:
/> (19)
направлениенаискорейшего спуска определяется градиентом квадратичной функции (16):
/>. (20)
Подставляяэто значение в формулы (18) – (19), получим окончательные выражения длявычисления последовательных спусков.
Есливоспользоваться разложением всех движений по базису, состоящему из собственныхвекторов матрицы />, то можно доказать, что дляквадратичной функции метод наискорейшего спуска линейно сходится, причем
/>, где />; (21)
здесь/> –собственные значения положительно определенной матрицы /> (они вещественны и положительны).Если />, чтосоответствует сильно вытянутым эллипсам – линиям уровня, то /> и сходимость может бытьочень медленной.
Естьтакие начальные приближения (рис. 4), когда точно реализуется наихудшаявозможная оценка, т. е. в (21) имеет место равенство.
Причинынетрудно понять. Во-первых, в данной точке любую прямую, в том числе невыгоднуюдля спуска, можно сделать направлением градиента, если специально подобратьизменение масштабов по осям. Во-вторых, каждый спуск кончается в точке, где егонаправление касается линии (поверхности) уровня. Градиент перпендикуляренповерхности уровня. Следовательно, в методе наискорейшего спуска каждый спускперпендикулярен предыдущему. В двумерном случае это означает, что мы совершаемспуск по координатам, повернутым так, что одна ось параллельна градиентуначальной точки.
Дляулучшения метода наискорейшего спуска предлагают «кухонные» поправки калгоритму – например, совершают по каждому направлению спуск не точно доминимума. Наиболее любопытным представляется такое видоизменение алгоритма.Будем делать по направлению, противоположному градиенту, только бесконечномалый шаг и после него вновь уточнять направление спуска. Это приводит кдвижению по кривой />, являющейся решением системыобыкновенных дифференциальных уравнений:
/>. (22)
Вдольэтой кривой />, т. е. функция убывает, и мыдвижемся к минимуму при />. Уравнение (22) моделируетбезынерционное движение материальной точки вниз по линии градиента. Можнопостроить и другие уравнения – например, дифференциальное уравнение второгопорядка, моделирующее движение точки при наличии вязкого трения.
Однакоот идеи метода еще далеко до надежного алгоритма. Фактически системудифференциальных уравнений (22) надо численно интегрировать. Если интегрироватьс большим шагом, то численное решение будет заметно отклоняться от линииградиента. А при интегрировании малым шагом сильно возрастает объем расчетов.Кроме того, если рельеф имеет извилистые овраги, то трудно ожидать хорошейсходимости этого метода.
Алгоритмынаискорейшего спуска и всех его видоизменений сейчас недостаточно отработаны.Поэтому метод наискорейшего спуска для сложных нелинейных задач с большимчислом переменных (/>) редко применяется, но в частныхслучаях он может оказаться полезным.
2.4 Случайный поиск
Методыспуска неполноценны на неупорядоченном рельефе. Если локальных экстремумовмного, то спуск из одного нулевого приближения может сойтись только к одному излокальных минимумов, не обязательно абсолютному. Тогда для исследования задачиприменяют случайный поиск.
Предполагают,что интересующий нас минимум (или все минимумы) лежит в некоторой замкнутойобласти; линейным преобразованием координат помещают ее внутрь единичного />-мерного куба.Выбирают в этом кубе /> случайных точек.
Дажепри миллионе пробных точек вероятность того, что хотя бы одна точка попадет внебольшую окрестность локального минимума, ничтожно мала. В самом деле, пустьдиаметр котловины около минимума составляет /> от пределов изменения каждойкоординаты. Тогда объем этой котловины составляет /> часть объема />-мерного куба. Уже при /> ни одна точкав котловину не попадет.
Поэтомуберут небольшое число точек /> и каждую точку рассматривают какнулевое приближение. Из каждой точки совершают спуск, быстро попадая вближайший овраг или котловину; когда шаги спуска сильно укорачиваются, егопрекращают, не добиваясь высокой точности. Этого уже достаточно, чтобы судить овеличине функции в ближайшем локальном минимуме с удовлетворительной точностью.
Сравнивая(визуально или при помощи программы) окончательные значения функции на всехспусках между собой, можно изучить расположение локальных минимумов функции исопоставить их величины. После этого можно отобрать нужные по смыслу задачиминимумы и провести в них дополнительные спуски для получения координат точекминимума с высокой точностью.
Обычнов прикладных задачах нужно в первую очередь добиться того, чтобы исследуемаяфункция приняла минимальное или почти минимальное значение. Но вблизи минимумазначение функции слабо зависит от изменения координат. Зачем тогда нужнонаходить координаты точки минимума с высокой точностью? Оказывается, что этоимеет не только теоретический, но и практический смысл.
Пусть,например, координаты – это размеры деталей механической конструкции, аминимизируемая функция есть мера качества конструкции. Если мы нашли минимумточно, то мы находимся в самом центре котловины около минимума. В этом случаевариации координат влияют на функцию слабее, чем в точках, расположенных ближек краям котловины. А безопасные вариации координат имеют в данном примере смыслдопусков на точность обработки деталей. Значит, при аккуратном вычислениикоординат минимума мы можем разрешить большие допуски, т. е. удешевитьобработку деталей.
Методслучайного поиска зачастую позволяет найти все локальные минимумы функции от10-20 переменных со сложным рельефом. Он полезен и при исследовании функции сединственным минимумом; в этом случае можно обойтись заметно меньшим числомслучайных точек. Недостаток метода в том, что надо заранее задать область, вкоторой выбираются случайные точки. Если мы зададим слишком широкую область, тоее труднее детально исследовать, а если выберем слишком узкую область, томногие локальные минимумы могут оказаться вне ее. Правда, положение несколькооблегчается тем, что при спусках траектории могут выйти за пределы заданнойобласти и сойтись к лежащим вне этой области минимумам.
ЗАКЛЮЧЕНИЕ
В работерассматривались методы нахождения минимума функции одной переменной и функции многихпеременных. Поиск минимума функции одной переменной осуществлялся методомзолотого сечения, поиск минимума функции многих переменных представлен методамипокоординатного спуска, наискорейшего спуска и др.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Калиткин Н.Н. Численныеметоды. М.: Наука, 1978. 512с.
2. Амосов А.А., Дубинский Ю.А.,Копченова Н. В. Вычислительные методы для инженеров. М.: Высшая школа, 1994.543с.
3. Ракитин В.И., Первушин В.Е.Практическое руководство по методам вычислений. М.: Высшая школа, 1998. 383с.
Приложение1
Листингпрограммы:
{Методомпокоординатного спуска найти точки локального минимума функции Химмельблау f(x)=(x1*x1+x2-11)*(x1*x1+x2-11)+(x1+x2*x2-7)*(x1+x2*x2-7) с точностью e=0.01}
programspusk;
usescrt;
constn=2; k=2;
typevector=array[1..n] of real;
vari:integer;
d,e,e1,h,h1,z:real;
x:vector;ch:char;
procedurepausa;
begin
writeln;
writeln('Для выхода нажмите любую клавишу…');
repeatch:=readkey until ch '';
end;
functionf(x:vector):real;
vara,b:real;
begina:=x[1]*x[1]+x[2]-11;
b:=x[1]+x[2]*x[2]-7;
f:=a*a+b*b;
end;
procedurescan (i:integer);
vara:boolean;
d1,z1:real;
beginz:=f(x);
repeatd1:=abs(h1); x[i]:=x[i]+h1; z1:=f(x); a:=(z1>=z);
ifa then h1:=-h1/k;
z:=z1;
untila and (d1
end;
begin
clrscr;
writeln ('Введите координатыначального вектора (x1,x2):');
fori:=1 to n do read (x[i]);
writeln ('Задайте точностьнахождения точки min f(x):');
read(e);
h:=0.2;e1:=e/k;
repeatd:=abs(h);
fori:=1 to n do
begin
h1:=h;scan (i);
end;
h:=h/k;
untild
writeln ('Точка минимума: x1=',x[1]:9:6,' ','x2=',x[2]:9:6);
writeln('Погрешность:',e:9:6);
pausa;
end.
Приложение2
Результатработы программы:
Введитекоординаты начального вектора (x1,x2):
1
2
Задайтеточность нахождения точки min f(x):
0.01
Точкаминимума: x1= 2.996875 x2= 2.000000
Погрешность:0.010000
Для выходанажмите любую клавишу.