WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 |
Министерство образования Российской Федерации РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ С.С.Михалкович, А.В.Олифер, А.М.Столяр ЧИСЛЕННЫЕ МЕТОДЫ Выпуск III Оптимизация. Системы нелинейных уравнений.

Методические указания к выполнению индивидуальных заданий на ЭВМ для студентов 2 курса физического факультета Ростов-на-Дону 2000 Введение Настоящие методические указания являются продолжением [1],[2] и содержат изложение теоретического материала, а также индивидуальные задания по следующим темам курса “Численные методы”: одномерная и многомерная оптимизация, решение систем нелинейных уравнений.

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

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

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

1 Одномерная оптимизация 1.1 Задание Найти все локальные минимумы и максимумы функции y=f(x) и точки, в которых они достигаются:

a) методом Ньютона;

b) методом золотого сечения.

Определить, сколько итераций потребуется в каждом методе для достижения точности = 10-3,10-5,10-7 при одних и тех же начальных приближениях.

Включить в отчет ответы на вопросы, сформулированные в пункте “Тестовый пример”.

Рекомендуемая литература: [4], с.407–421; [6].

1.2 Тестовый пример Для функции F(x) = x3 - 8x2 + 2x - 5 + sin x xmin = 5.17574239, F(xmin ) = –71.20016030691437 ;

xmax = 0.19334459, F(xmax ) =–4.712997997082332.

В методе Ньютона определите, при каких начальных приближениях итерационный процесс сходится к минимуму, а при каких – к максимуму. Проследите, как ведет себя итерационный процесс при задании начального приближения в окрестности точки перегиба, вычисляемой в системе Maple с помощью команды evalf(solve(DDF(x)=0)).

В методе золотого сечения определите, к чему сходится итерационный процесс, если вызвать процедуру gold (см. пункт 1.5.2) с интервалом [a,b], содержащим как точку минимума, так и точку максимума.

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

Пусть дана вещественная функция n вещественных переменных F(x), x = (x1,..., xn ), определенная в замкнутой области S Rn. Требуется найти maxF(x) minF(x) (1) xS xS и точку x* S, в которой он достигается.

Заметим, что поиск максимума функции F(x) эквивалентен поиску минимума функции -F(x). Поэтому далее сконцентрируем внимание именно на задаче минимизации.

Множество S выражает ограничения задачи. Например, во многих физических задачах требуется, чтобы переменные были неотрицательны: S = {x: xi 0}. Если S совпадает с Rn, то говорят о задаче безусловной оптимизации, в противном случае говорят об условной оптимизации.

Определим также следующие два термина. Будем говорить, что F(x) имеет в точке x* S глобальный минимум, если F(x)F(x*) для любого xS. Аналогично, F(x) имеет в точке x* S локальный минимум, если F(x)F(x*) для всех xS D(x*), где D(x*) – некоторая окрестность точки x*.

Если локальный минимум достигается во внутренней точке x* области S и функция F(x) дифференцируема в этой точке, то x* является критической точкой, т.е. выполняются условия:

F (x*) = 0, i = 1,...,n. (2) xi Обратное неверно: критическая точка не обязана быть экстремальной.

Например, в одномерном случае для функции y = x3 точка x=0 является критической, но не является точкой экстремума. В двумерном случае для функции F(x, y) = x2 - y2 критической является точка (0,0). Она также не реализует экстремум, поскольку одномерная функция F(x,0) имеет минимум при x = 0, а одномерная функция F(0, y) – максимум при y = 0.

Если же локальный минимум достигается на границе области S, то точка минимума не обязана быть критической. Например, функция f (x) = x достигает на отрезке [1,2] минимум в точке x*=1, но f (1) = 1 0.



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

Опишем два основных алгоритма одномерной оптимизации. Метод золотого сечения использует для своей работы только значения функции, сходится всегда, но обеспечивает лишь линейную скорость сходимости ([1], с.15). Метод Ньютона использует значения первой и второй производных функции F(x), имеет квадратичную скорость сходимости, но может расходиться при плохом выборе начального приближения. Обычно в реальных задачах комбинируют оба метода, применяя для локализации корней метод золотого сечения, а затем на заключительном этапе – метод Ньютона.

1.4 Метод Ньютона 1.4.1 Идея метода В основе метода Ньютона лежит приближение F(x) квадратичной функцией, экстремум которой находится явно и используется в качестве следующего начального приближения.

Зададимся некоторым начальным приближением x0 и выпишем первые три члена ряда Тейлора функции F(x) в окрестности этой точки:

F (x0) F(x0 + x) F(x0) + F (x0) x + (x)2. (3) Экстремум квадратичной функции в правой части (3) достигается при x = - F (x0) F (x0). Поэтому в качестве следующего приближения можно выбрать точку x1 = x0 - F (x0) F (x0). Получаем итерационный процесс xk +1 = xk - F (xk ) F (xk ), k = 0,1,..., (4) дающий алгоритм метода Ньютона.

Отметим, что при выборе начального приближения достаточно близко к точке экстремума метод Ньютона гарантированно сходится.

Отметим также, что метод Ньютона может сходиться как к локальному минимуму, так и к локальному максимуму, поэтому в полученной точке экстремума x* требуется дополнительно вычислить F (x*). Если F (x*) > 0, то мы имеет дело с локальным минимумом, если же F (x*) < 0 – с локальным максимумом. Наконец, заметим, что если для некоторого xk окажется F (xk ) = 0, то метод Ньютона завершится делением на 0.

1.4.2 Замечания по численной реализации Так как в точке экстремума x* выполняется условие F (x*) = 0, то в ее окрестности F (x*) F = F(x * +x) - F(x*) (x)2. (5) Поэтому, если величина F (x*) порядка единицы, то, например, при погрешности вычисления функции F 10-12 погрешность решения x составит 10-6. Таким образом, при использовании типа real в языке Turbo Pascal не рекомендуется задавать погрешность вычислений < 10-6. В системе Maple по умолчанию количество значащих цифр при работе с вещественными числами равно 10, поэтому для вычисления решения с погрешностью 10-6 необходимо выполнить присваивание Digits:=12;

где Digits – переменная среды Maple.

Процедура метода Ньютона должна иметь следующие параметры:

x0 – начальное приближение;

eps – точность;

niter – количество итераций (выходной параметр).

Найденное значение корня должно быть возвращаемым значением процедуры (в Maple процедуры могут возвращать значения, в Паскале для этого используются функции). Желательно передавать также функцию F(x) в качестве функционального параметра. Наконец, если метод Ньютона расходится, то для распознавания такой ситуации можно возвращать niter=0.

Дадим несколько рекомендаций по работе в системе Maple.

1) Несколько связанных команд лучше набирать в одной командной строке Maple (она начинается с символа ">"). Если команды разделяются символом ":", то промежуточные результаты не отображаются.

При нажатии в конце строки комбинации клавиш Shift-Enter создается новая строка текста без перехода к следующей командной строке.

2) Функции, задаваемые выражением, описываются в Maple либо с помощью функционального оператора:

F:=x->x^3-x^2;

либо с помощью команды unapply:

F:=unapply(x^3-x^2,x);

3) Производные вычисляются c помощью оператора D:

DF:=D(F): DDF:=D(DF);

4) Описание процедуры в системе Maple имеет вид:

newton:=proc(x0,eps::numeric,F::procedure, niter::evaln) local x,n,...

global...

x:=x0;

...

niter:=n;

x;

end;

Описание используемых локальных и глобальных переменных в процедурах Maple необязательно, но весьма желательно. Параметры, передаваемые по значению (например, x0), нельзя менять в теле процедуры;

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

5) При необходимости выводить на экран промежуточные результаты внутри процедуры используйте функцию print:

print(n,x,F(x));

6) Во избежание зацикливания в методе Ньютона используйте смешанный оператор цикла:

for n from 1 to 50 while abs(x-xold)>eps do 1.5 Метод золотого сечения 1.5.1 Идея метода Пусть функция F(x) определена на отрезке [a,b], строго убывает при x < x * (x*[a,b]) и строго возрастает при x > x *. Такая функция называется унимодальной на отрезке [a,b] и имеет на [a,b] единственный минимум. Заметим, что унимодальная функция не обязана быть непрерывной.

Назовем интервал, на котором функция заведомо имеет минимум, интервалом неопределенности (ИН). Вначале ИН совпадает с отрезком [a,b]. Наша цель – уменьшить длину ИН до достижения заданной точности. Для этого вычислим функцию F(x) в точках x1, x2 [a,b], x1 < x2.





F(x ) F(x ) F(x ) F(x ) 1 x 2 x a x 1 a x b b Рис. 1 Рис. Если F(x1) < F(x2) (рис.1), то отрезок [a, x2 ] заведомо содержит минимум, поэтому его можно выбрать в качестве нового ИН. В противном случае (рис.2) – в качестве нового ИН выбирается отрезок [x1,b]. Для каждого последующего ИН функцию достаточно вычислять в одной точке, поскольку ее значение в другой точке внутри интервала известно с предыдущего шага. Например, в случае, изображенном на рис.1, сле дует выбрать точку x3 [a, x2] и сравнить F(x1) и F(x3). Этот процесс следует продолжать, пока длина интервала не окажется меньше наперед заданной точности.

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

Золотое сечение отрезка m l - m l Рис. Пусть у нас имеется отрезок длины l (рис.3). Разобьем его на части длины m и l–m (m > l–m) таким образом, что отношение длины большей части к длине всего отрезка равно отношению длины меньшей части к длине большей, т.е. выполняется пропорция золотого сечения:

m l - m =. (6) l m Учитывая, что m > 0 и l > 0, из (6) нетрудно получить:

m 5 - r = = 0.6180.

l Число 1 r 1.6180 называется золотым сечением и является фундаментальным числом, возникающим во многих областях науки и техники.

В методе золотого сечения точки x1 и x2 выбираются так, что b - x1 x2 - a = = r, (7) b - a b - a откуда x1 = b - r(b - a), x2 = a + r(b - a) или x2 = b + a - x1. Нетрудно виx1 - a b - xдеть, что при этом выполняются соотношения = = r, т.е.

x2 - a b - xточка x2 для отрезка [x1,b] выполняет ту же роль, что и точка x1 для отрезка [a,b], а точка x1 для отрезка [a, x2] – ту же роль, что и точка x2 для [a,b].

Из (7) также следует, что длина ИН уменьшается на каждом шаге в 1 r раз. Таким образом, за пять итераций метода золотого сечения длина интервала неопределенности уменьшается в (1 r)5 11.1 раз, т.е. примерно на порядок.

1.5.2 Замечания по численной реализации Приведем полную реализацию процедуры метода золотого сечения в системе Maple, учитывая все сделанные выше замечания.

> gold:=proc(a,b,eps::numeric, f::procedure,niter::evaln) local n,aa,bb,ab,xa,xb,fa,fb,fxa,fxb,r;

global DEB;

r:=evalf(sqrt(5)-1)/2;

fa:=f(a); fb:=f(b);

aa:=a; bb:=b;

xa:=bb-r*(bb-aa); xb:=r*(bb-aa)+aa;

fxa:=f(xa); fxb:=f(xb);

for n from 1 to while (abs(bb-aa)>eps) do if (fxb

xa:=xb; fxa:=fxb;

xb:=bb+aa-xa;

fxb:=f(xb);

else bb:=xb; fb:=fxb;

xb:=xa; fxb:=fxa;

xa:=bb+aa-xb;

fxa:=f(xa);

fi;

ab:=(aa+bb)/2;

if DEB=1 then print(n,ab,f(ab)); fi;

od;

niter:=n-1;

ab;

end:

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

Заметим, что при поиске максимального значения условие fxbfxa. Однако, условие “ищется минимум или максимум” можно передавать в качестве параметра.

Для использования процедуры gold требуется, чтобы на отрезке [a,b] находилась ровно одна экстремальная точка функции F(x). Выбор такого отрезка называется локализацией экстремума. В простейших ситуациях его можно производить непосредственно по виду графика функции F(x). Однако, мы рекомендуем автоматизировать процесс локализации.

Пусть на некотором отрезке [A,B] требуется найти все экстремумы. Разобьем его точками xi на N равных частей. При выполнении условий F(xi ) > F(xi-1), F(xi ) > F(xi+1) на отрезке [xi-1, xi+1] находится локальный максимум, при выполнении же условий F(xi ) < F(xi-1), F(xi ) < F(xi+1) – локальный минимум. Число N следует выбирать так, чтобы длина каждой части была заведомо меньше половины расстояния между соседними локальными экстремумами (в этом случае на каждом участке монотонности функции будет как минимум две точки xi и мы не “проскочим” минимум) и в то же время не слишком большим (для сокращения объема вычислений).

2 Многомерная оптимизация 2.1 Задание Найти локальный минимум (максимум) функции двух переменных F(x,y) и точку, в которой он достигается:

а) методом покоординатного спуска;

б) методом наискорейшего градиентного спуска.

Определить, сколько итераций потребуется в каждом методе для достижения точности = 10-3,10-5,10-7 при одних и тех же начальных приближениях.

В Maple построить график функции z=F(x,y) и график ее линий уровня. При реализации в системе Maple на последнем графике построить также ломаную, соединяющую все последовательные приближения к решению.

Рекомендуемая литература: [3], с.290, 292–293, 329–337;

[4], с. 424–427; [6].

2.2 Тестовый пример f (x, y) = x2 + 2x + y2 - sin(xy);

min f (x, y) = –1.274688296;

(x, y)min = (–1.2053533, –0.4975176).

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

Алгоритм любого метода спуска дается формулой:

= xk + hkvk, xk +где xk – k-тое приближение к решению, vk – некоторый вектор, hk – длина шага в направлении vk.

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.