Свойства функций одной переменной

Теория теоретическая

Функции одной переменной

 

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

 

Определение

Функция f(х) является унимодальной на отрезке а≤ х≤ b в том и только том случае, если она монотонна по обе стороны от единственной на рассматриваемом интервале оптимальной точки х*. Другими словами, если х*— единственная точка минимума f(x) на отрезке а≤ х≤ b, то f(х) оказывается унимодальной на данном интервале тогда и только тогда, когда для точек х₁и х₂

из x*≤ x₁≤ x₂ следует, что f(x*)≤ f(x₁)≤ f(x₂),

и

из x*≥ x₁≥ x₂следует, что f(x*)≤ f(x₁)≤ f(x₂).

 

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

Критерии оптимальности

 

При анализе оптимизационных задач, как правило, возникают два общих вопроса.

1. Вопрос анализа «в статике». Как определить, представляет ли данная точка х* оптимальное решение задачи?

2. Вопрос анализа «в динамике». Если х* не является точкой оптимума, то какая последовательность действий приводит к получению оптимального решения?

В этом разделе основное внимание уделяется решению вопроса анализа «в статике», а именно построению множества критериев оптимальности, позволяющих определить, является ли данное ре­шение оптимальным.

Определения

Функция f(x), определенная на множестве S, достигает своего глобального минимума в точке х** Î S том и только том случае, если

Функция f(x), определенная на множестве S, имеет локальный ми­нимум (относительный минимум) в точке x* Î S в том и только том случае, если

т.е если существует e > 0, такое, что для всех х, удовлетворяющих условию ï х-х*ï < e, выполняется неравенство f(x*) ≤ f(x)

Замечания

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

2. Если функция обладает свойством унимодальности, то ло­кальный минимум автоматически является глобальным минимумом.

 

 

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

На рис. 2.7 точка х₁— точка глобального максимума, х₂ — точка локального минимума, х₃ — точка локального максимума, х₄ — точка глобального минимума, а х₅можно рассматривать и как точку локального минимума, и как точку локального максимума.

Идентификация оптимумов в случае фун­кции одной переменной. Предположим, что функция f(x) одной переменной х определена на открытом интервале (a, b) и n-кратно дифференцируема на этом интервале. Если х*— внут­ренняя точка интервала, то теорема Тейлора позволяет записать изменение функции f при переходе от точки х* к точке (х*+e) в следующем виде:

где через О_n+1(e) обозначена сумма членов, в которых степень e равна (n+1) и выше. Если х*— локальный минимум функции f на (а, b), то по определению должна существовать e-окрестность точки х*, такая, что для всех х из этой окрестности выполняется нера­венство

f(x) ³ f(x*) (2.2)

Из неравенства (2.2) следует, что

При достаточно малом e первое слагаемое доминирует над осталь­ными, а так как e можно выбрать и положительным, и отрицатель­ным, то неравенство (2.3) будет выполняться только в том случае, если:

(2.4)

Рассуждая аналогичным образом, нетрудно установить, что нера­венство (2.3) будет справедливым только тогда, когда

(2.5)

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

Теорема 2.1

Необходимые условия того, что х* является точкой локального минимума (максимума) дважды дифференцируемой функции f на открытом интервале (а, b), выражаются следующими соотношениями:

Эти условия являются необходимыми, т. е. в случае, когда они не выполняются, точка х* неможет быть точкой локального минимума (максимума). С другой сторо­ны, если эти условия выполня­ются, мы не имеем гарантии, что х* является точкой локаль­ного минимума (максимума). Рассмотрим, например, функцию f(x)=x³, график которой пред­ставлен на рис. 2.8. Эта функ­ция удовлетворяет необходимым условиям наличия как локаль­ного минимума, так и локаль­ного максимума в начале коор­динат, однако не имеет ни мак­симума, ни минимума при х*=0.

Определения

Стационарной точкой называется точка х*, в которой

Если стационарная точка не соответствует локальному оптиму­му (минимуму или максимуму), то она является точкой перегиба, или седловой точкой.

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

Теорема 2.2

Пусть в точке х* первые (п—1) производные функции обращаются в нуль, а производная порядка п отлична от нуля.

(1) Если п — нечетное, то х*— точка перегиба.

(2) Если п — четное, то х*— точка локального оптимума.

Кроме того,

(а) если эта производная положительная, то х*— точка локаль­ного минимума;

(б) если эта производная отрицательная, то х*— точка локаль­ного максимума.

Доказательство

Утверждение теоремы нетрудно доказать с помощью разложения в ряд Тейлора, представленного равенством (2.1). Поскольку поря­док первой отличной от нуля производной равен п, формулу (2.1) можно переписать в следующем виде:

Если п — нечетное число, то правая часть (2.6) может принимать как положительные, так и отрицательные значения в зависимости от того, является ли величина e положительной или отрицательной. Это означает, что в зависимости от знака e разность f(x*+e) - f (x*) либо положительная, либо отрицательная. Следовательно, функция не достигает в точке х* своего минимального или максимального значения, т. е. х*— точка перегиба.

Далее рассмотрим случай, когда п — четное число. При этом ве­личина eⁿ всегда положительная, а знак правой части (2.6) опреде­ляется первым слагаемым, если e— достаточно малая величина. Таким образом, если величина (dⁿf /dxⁿ )ï _x=x* положительная, то f(x*+e)- f (х*)> 0 и точка х* соответствует локальному минимуму. Аналогичные рассуждения нетрудно провести также и для локаль­ного максимума.

Для того чтобы применить теорему 2.2 к функции f(x)=x³, гра­фик которой изображен на рис. 2.8, вычислим

Так как порядок первой отличной от нуля производной равен 3 (нечетное число), точка х=0является точкой перегиба.

Замечание

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

Эта функция непрерывна во всех точках действительной оси, но не­дифференцируема при х=2. Функция достигает максимума в точке х=2, которая не является стационарной в соответствии с данным выше определением.

Пример 2.1

Рассмотрим функцию

определенную на всей действительной оси. Первая производная этой функции равна

df /dx =30х^{5 +} 180х⁴+ 330х³— 180х² = 30х² (х—1) (х—2) (х—3).

Ясно, что первая производная обращается в нуль в точках х = 0, 1, 2, 3, и, следовательно, эти точки можно классифицировать как стационарные. Вторая производная функции равна

Вычислив значения второй производной в четырех точках х = 0, 1, 2, 3, получим

 

x	f(x)	d2f /dx2
	27, 5
		-120
	5, 5

 

Отсюда следует вывод, что х=1, 3 — точки локальных минимумов, а х=2— точка локального максимума. Чтобы идентифицировать точку х=0, вычислим третью производную

Так как эта производная отлична от нуля и имеет нечетный порядок, то точка х=0является не точкой оптимума, а точкой перегиба.

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

Максимизировать f(x) при ограничении а ≤ x ≤ b,

где а и b — установленные границы изменения значений перемен­ной х.

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

Шаг 1. Приравнять df/dx=0и найти все стационарные точки.

Шаг 2. Выбрать все стационарные точки, которые располо­жены в интервале [а, b]. Обозначим эти точки через x₁, х₂, ..., х_N.

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

Шаг 3. Найти наибольшее значение f(x) из множества f(а), f(b), f(x₁), ..., f(x_N). Это значение соответствует глобальному максимуму.

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

Пример 2.2

Максимизировать f(x)= - x³+Зх²+9х+10 на интервале -2≤ х ≤ 4. Имеем

Решая это уравнение, получаем две стационарные точки х=3и x= -1, которые расположены внутри заданного интервала.

Для того чтобы найти глобальный максимум, вычислим значения f(x) в точках х = 3, - 1, - 2 и 4:

Таким образом, точка х =3соответствует максимальному значению f на интервале [—2, 4].

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

Пример 2.3

Исследуем свойства функции

При х≤ 1 имеем f" (х)≤ 0, и, следовательно, функция является вог­нутой в указанной области. Если же х³ 1то f" (x)³ 0, т. е. функ­ция является выпуклой в этой области.

Заметим, что функция имеет две стационарные точки х= -¹/₂ и x= ⁵/₂. Поскольку f" (-¹/₂)< 0, функция обладает локальным мак­симумом при х= -¹/₂. В точке x= ⁵/₂ вторая производная f" (⁵/₂)> 0, и, следовательно, функция достигает в этой точке локального ми­нимума. Если ограничить допустимую область неравенством х≤ 1, то f(x) имеет глобальный максимум при х= -¹/₂, так как f(x) — вогнутая функция (в данной области) и х= -¹/₂ — точка локаль­ного максимума. Аналогично если ограничить допустимую область неравенством х³ 1, то f(x) достигает глобального минимума при х= ⁵/₂. Однако если переменная х изменяется на всей действительной оси от -∞ до +∞ , то функция f(x) не имеет конечного глобального максимума или минимума.

Пример 2.4. Задача управления запасами

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

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

Рис. 2.9 иллюстрирует изменение объема запасов с течением времени. В точке А объем запасов равен В; затем объем запасов начинает уменьшаться со скоростью lединиц товара в единицу вре­мени и достигает нулевого значения в точке С. В это время посту­пает новая партия товара, и объем запасов восстанавливается.

Треугольник ABC представляет один цикл управления запасами, который повторяется во времени. Задача заключается в том, чтобы определить оптимальный размер заказа В и продолжительностьинтервала времени между заказами С — А. Обозначим соответ­ствующие переменные через Q и Т.

Поскольку Т есть величина промежутка времени, в течение ко­торого при скорости расходования lистощается запас Q, имеем T=Q/l. Таким образом, задача сводится к нахождению оптималь­ного значения Q. Заметим, что когда Q мало, переменная Т также принимает малое значение. При этом частота заказов велика, что обусловливает большие затраты на выполнение заказов и относи­тельно малые издержки хранения запасов. С другой стороны, нали­чие большого объема запасов (Q велико) приводит к увеличению затрат на хранение запасов и одновременно к снижению издержек, связанных с выполнением заказов на товары. Одна из основных задач управления запасами состоит в определении оптимального значе­ния Q, которому соответствует минимум суммы полных годовых затрат.

Получим аналитическое выражение для функции полных годо­вых затрат (затраты/цикл x количество циклов/год).

Примечание. Затраты на хранение запасов в течение цикла рав­ны затратам на хранение Q/2 единиц товара в течение интервала времени Т.

Таким образом, подлежащая минимизации функция полных затрат есть

Отсюда следует, что f(Q) — выпуклая функция и если существует положительное значение Q*, такое, что f(Q*)=0, то Q* минимизи­рует f(Q).

При этом Т*— интервал времени между заказами =т l. Величина Q* известна в теории управления запасами как наиболее экономичный размер заказа.

Теорема 2.3

Пусть функция f унимодальна на замкнутом интервале а ≤ x ≤ b, а ее минимум достигается в точке х*. Рассмотрим точки x₁ и х₂,. расположенные в интервале таким образом, что а< x₁< x₂< b. Сравнивая значения функции в точках x₁и х₂, можно сделать сле­дующие выводы.

1. Если f(x₁)> f(x₂), то точка минимума f(x) не лежит в интерва­ле (а, х₁), т. е. х* Î (х₁, b) (рис. 2.10).

2. Если f(x₁)< f(x₂), то точка минимума не лежит в интервале: (х₂, b), т. е. х*Î (a, x₂ )(см. рис. 2.10).

Доказательство

Рассмотрим случай, когда f(x₁)> f(x₂). Пусть утверждение тео­ремы неверно, т. е. a≤ х*≤ х₁. Поскольку х*— точка минимума, то по определению f(х*)≤ f (х) для всех х Î (a, b). Получаем двойное неравенство

f(x*)≤ f(x₁)> f(x₂) при x*< x₁< x₂.

Это неравенство не может выполняться, так как унимодальная функ­ция f (x) должна быть монотонной по обе стороны от точки х*. Таким образом, получено противоречие, доказывающее утверждение тео­ремы. Аналогичные рассуждения справедливы также в случае, когда f(x_l)< f(x₂).

Примечание. Если f(x_l)=f(x₂), то можно исключить оба крайних интервала (а, х₁) и (х₂, b); при этом точка минимума должна распо­лагаться в интервале (x_l, x₂).

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

этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содер­жащего точку оптимума;

этап уменьшения интервала, на котором реализуется конечная последовательность преобразований исходного интервала с тем, чтобы уменьшить его длину до заранее установленной величины,

Этап уменьшения интервала

 

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

Метод деления интервала пополам. Рас­сматриваемый метод позволяет исключать в точности половину интервала на каждой итерации. Иногда этот метод называют трех­точечным поиском на равных интервалах, поскольку его реализация основана на выборе трех пробных точек, равномерно распределен­ных в интервале поиска. Ниже приводится описание основных шагов поисковой процедуры, ориентированной на нахождение точки ми­нимума функции f(x) в интервале (а, b).

Шаг 1. Положить х_т=(а+b)/2и L=b—а. Вычислить значе­ние f(x_m).

Ш а г 2. Положить x₁=a+L/4 и х₂=b—L/4. Заметим, что точ­ки x₁, x_m и х₂делят интервал (a, b) на четыре равные части. Вычис­лить значения f(x₁) и f(x₂).

Ш а г 3. Сравнить f(x₁) и f(x_m).

(1) Если f(x₁)< f(x_m), исключить интервал (х_т, b), положив b=х_т. Средней точкой нового интервала поиска становится точка х₁. Сле­довательно, необходимо положить х_т=х₁.

Перейти к шагу 5.

(2) Если f(x₁)> f(x_m), перейти к шагу 4.

Ш а г 4. Сравнить f(x₂) и f(x_m).

(1) Если f(x₂)< f(x_m), исключить интервал (а, х_т), положив а=х_т. Так как средней точкой нового интервала становится точка х₂положить х_т=х₂. Перейти к шагу 5.

(2) Если f(x₂)³ f(x_m), исключить интервалы (a, x₁) и (х₂, b). Поло­жить a=x₁ и b=х₂. Заметим, что х_т продолжает оставаться средней точкой нового интервала. Перейти к шагу 5.

Ш а г 5. Вычислить L=b—а. Если величина |L|мала, закон­чить поиск. В противном случае вернуться к шагу 2.

Замечания

1. На каждой итерации алгоритма исключается в точности по­ловина интервала поиска.

2. Средняя точка последовательно получаемых интервалов всег­да совпадает с одной из пробных точек x₁, x₂или х_т, найденных на предыдущей итерации. Следовательно, на каждой итерации тре­буется не более двух вычислений значения функции.

3. Если проведено п вычислений значения функции, то длина полученного интервала составляет (1/2)^n/2 величины исходного интервала.

4. В работе [2] показано, что из всех методов поиска на равных интервалах (двухточечный, трехточечный, четырехточечный и т. д.) трехточечный поиск, или метод деления интервала пополам, отли­чается наибольшей эффективностью.

Пример 2.6. Метод деления интервала пополам

Минимизировать f(х)=(100—x)² в интервале 60£ x £ 150. Здесь a=60, b=150 и L=150-60=90.

Таким образом, исключаются интервалы (60; 82, 5) и (127, 5; 150). Длина интервала поиска уменьшается с 90 до 45.

Итерация 2

Таким образом, интервал неопределенности равен (93, 75; 116, 25)

Итерация 3

а=93, 75 b=116, 25, х_т=105,

L = 116, 25—93, 75=22, 5,

x₁=99, 375, х₂=110, 625,

f(x₁)=0, 39< f(105)=25.

Таким образом, исключается интервал (105; 116, 25). Новый ин­тервал неопределенности равен (93, 75; 105), его средняя точка есть 99, 375 (точка х₁на итерации 3). Отметим, что за три итерации (шесть вычислений значения функции) исходный интервал поиска длины 90 уменьшился до величины (90)(1/2)³=11, 25.

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

1. Если количество пробных точек принимается равным двум, то их следует размещать на одинаковых расстояниях от середины интервала.

 

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

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

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

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

Рис. 2.12. Интервалы, полученные методом золотого сечения

 

Отсюда следует, что при выборе t в соответствии с условием 1-t =t² симметрия поискового образца, показанного на рис. 2.11, сохраняется при переходе к уменьшенному интервалу, который изображен на рис. 2.13. Решая это квадратное уравнение, получаем

откуда положительное решение t=0, 61803…. Схема поиска, при которой пробные точки делят интервал в этом отношении, известна

под названием поиска с помощью метода золотого сечения. Заметим, что после первых двух вычислений значений функции каждое по­следующее вычисление позволяет исключить подынтервал, величина которого составляет (1—t)-ю долю от длины интервала поиска. Следовательно, если исходный интервал имеет единичную длину, то величина интервала, полученного в результате N вычислений зна­чений функции, равна t^N-1. Можно показать, что поиск с помощью метода золотого сечения является асимптотически наиболее эффек­тивным способом реализации минимаксной стратегии поиска.

 

Пример 2.7. Метод золотого сечения

Опять рассмотрим задачу из примера 2.6, в которой требуется

минимизировать f(х)=(100—х)²в интервале 60£ x £ 150. Для того чтобы перейти к интервалу единичной длины, проведем замену переменной, положив w=(x—60)/90. Таким образом, задача принимает следующий вид:

минимизировать f(w)—(40—90w)²

при ограничении 0£ w £ 1.

Итерация 1. I₁=(0, 1); L₁=l. Проведем два первых вычисления значений функции:

Так как f(w)₂< f(w₁) и w₂< w₁, интервал w≥ w₁ исключается.

Итерация 2. I₂=(0; 0, 618); L₂=0, 618=t. Следующее вы­числение значения функции проводится в точке

Так как f(w₃)> f(w₂) и w₃< w₂, интервал w≤ w₃исключается.

Итерация 3. I₃=(0, 236; 0, 618), L₃=0, 382=t². Следующее вычисление значения функции проводится в точке, расположенной на расстоянии t ´ (длина полученного интервала) от левой гра­ничной точки интервала, или на расстоянии (1—t) ´ (длина ин­тервала) от правой граничной точки. Таким образом,

Так как f(w₄)< f(w₂) и w₄> w₂, интервал w£ w₂ исключается.

В результате получен следующий интервал неопределенности: 0, 382£ w £ 0, 618 для переменной w, или 94, 4£ x £ 115, 6 для перемен­ной х.

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

что соответствует интервалу длины 8, 1 для переменной х. Для срав­нения напомним, что в аналогичной ситуации метод деления интер­вала пополам привел к получению интервала длины 11, 25.

В общем случае если правая и левая граничные точки интервала неопределенности (обозначим их через XR и XL) известны, то ко­ординаты всех последующих пробных точек, получаемых в соответ­ствии с методом золотого сечения, можно вычислить по формулам

w= XR—tⁿ или w= XL + tⁿ

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

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

Метод Ньютона — Рафсона

В рамках схемы Ньютона — Рафсона предполагается, что функ­ция f дважды дифференцируема. Работа алгоритма начинается в точке x₁, которая представляет начальное приближение (или на­чальную оценку) координаты стационарной точки, или корня урав­нения f '(x)=0Затем строится линейная аппроксимация функции f'(x) в точке x₁, и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего

приближения. Если точка x_k принята в качестве текущего прибли­жения к стационарной точке, то линейная функция, аппроксими­рующая функцию f '(x) в точке x_k, записывается в виде

Приравняв правую часть уравнения (2.7) нулю, получим следующее приближение:

Рис. 2.14 иллюстрирует основные шаги реализации метода Ньютона. К сожалению, в зависимости от выбора начальной точки и вида функции алгоритм может как сходиться к истинной стационарной точке, так и расходиться, что отражено на рис. 2.15. Если начальная точка расположена правее х₀, то получаемые в результате последова­тельных приближений точки удаляются от стационарной точки z.

Пример 2.10. Метод Ньютона — Рафсона

Рассмотрим следующую задачу:

минимизировать f(x)=2х²+(16/х).

Для того чтобы определить стационарную точку функции f(x), воспользуемся методом Ньютона — Рафсона, положив x₁=l:

Итерации продолжаются до тех пор, пока не будет выполняться не­равенство |f'(x_k )| < e, где e — заранее установленная величина до­пустимого отклонения.

Метод средней точки

 

Если функция f(x) унимодальна в заданном интервале поиска, то точкой оптимума является точка, в которой f '(х)=0. Если при этом имеется возможность вычислять как значения функции, так и ее производной, то для нахождения корня уравнения f '(х)=0 можно воспользоваться эффективным алгоритмом исключения интервалов, на каждой итерации которого рассматривается лишь одна пробная точка. Например, если в точке z выполняется неравенство f '(z)< 0, то с учетом предположения об унимодальности естественно утверж­дать, что точка минимума не может находиться левее точки z. Дру­гими словами, интервал х≤ z подлежит исключению. С другой сто­роны, если f '(z)> 0, то точка минимума не может находиться правее z и интервал x≥ z можно исключить. Приведенные рассуждения ле­жат в основе логической структуры метода средней точки, который иногда называют поиском Больцано.

Определим две точки L и R таким образом, что f '(L)< 0 и f '(R)> 0. Стационарная точка расположена между L и R. Вычислим значе­ние производной функции в средней точке рассматриваемого интер­вала z=(L+R)/2. Если f '(z)> 0, то интервал (z, R)-можно исключить из интервала поиска. С другой стороны, если f '(z)< 0, то можно исключить интервал (L, z). Ниже дается формализованное описа­ние шагов алгоритма.

Пусть имеется ограниченный интервал а≤ х≤ b и задан параметр сходимости e.

Шаг 1. Положить R=b, L=a; при этом f '(а)< 0 и f '(b)> 0.

Ш а г 2. Вычислить z=(R+L)/2и f '(z).

Ш а г 3. Если |f '(z)|≤ e, закончить поиск. В противном случае, если f '(z)< 0, положить L=z и перейти к шагу 2. Если f '(z)> 0, по­ложить R=z и перейти к шагу 2.

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

Метод секущих

 

Метод секущих, являющийся комбинацией метода Ньютона и общей схемы исключения интервалов, ориентирован на нахождение корня уравнения f '(x)=0в интервале (а, b), если, разумеется, такой корень существует.

12345Следующая ⇒

Поделиться:

Популярное:

1. I. ПРОТОКОЛ К МАДРИДСКОМУ СОГЛАШЕНИЮ О МЕЖДУНАРОДНОЙ РЕГИСТРАЦИИ ЗНАКОВ («МАДРИДСКИЙ ПРОТОКОЛ»)
2. А. НИЦЦКОЕ СОГЛАШЕНИЕ О МЕЖДУНАРОДНОЙ КЛАССИФИКАЦИИ ТОВАРОВ И УСЛУГ ДЛЯ РЕГИСТРАЦИИ ЗНАКОВ
3. Алгоритмы записи произвольной функции, заданной в таблице в виде с помощью элементарных функций.
4. Анатомо-морфологическая база высших психических функций.
5. База данных «Обслуживание работы международной конференции»
6. Белорусское национальное движение в декабре 1917- марте 1918г. Провозглашение Белорусской Народной Республики
7. Биполярность периода холодной войны и ее дезинтеграция
8. Был в одной помещичьей деревне управляющий-немец
9. В одной организации может быть много «локальных» культур.
10. В. ПРИНЦИП МЕЖДУНАРОДНОЙ РЕГИСТРАЦИИ
11. Введение понятия уравнения (неравенства с переменной)
12. Взаимосвязь общих и конкретных функций менеджмента