Учебник - Практические занятия по вычислительной математике - Аристова (1238839), страница 20

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

Текст из файла (страница 20)

Линеаризуем функцию W(τ):nW ()   x( s )   (x( s ) )   fi2 x( s )   (x( s ) ) i 1i 1n2  fi (x( s ) )   fi (x( s ) ) (x( s ) ) .Тогда129V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИnW ( )  2 fi (x( s ) )   fi (x( s ) ) (x( s ) ) fi (x( s ) ) (x( s ) )  0.i 1Оптимальный параметр, определяемый этим уравнением, будетf (x( s ) ) fi (x( s ) ) (x( s ) )(F, J) ,i 1 is 2n(J, J) i 1 fi (x( s) ) (x( s) ) n fгде J   i x j – матрица Якоби вектор-функции F.nf (x) n fi (x) 2  2 fi (x) i ,x j x j i 1x ji 1или  2JT F.Тогда окончательно получаемs 1 (F, JJT F)( s ),2 (JJT F, JJT F)( s )x( s 1)  x( s )  2s  JT (x( s) )  F(x( s) ) .Для нелинейных систем большой размерности метод неэкономичен.V.4.5.

Динамический методРешение стационарной задачи нахождения минимума строится какустановившееся решение динамической задачи.Рассмотрим систему дифференциальных уравнений  du grad (u)  0, grad (u)  .dt ui В этом случае вектор производных u t ортогонален линиямуровня (u) и направлен в сторону убывания значений (u).

Вдоль траектории (u) не возрастает. Формально справедливость этого утверждения следует из неравенстваd du   grad (u),     grad (u),grad (u)   0 .dt dt 130(4.1)V.4.5. Динамический методДругой нестационарный процесс, решение которого при весьма общих предположениях устанавливается к точке минимума (u), описывается системой дифференциальных уравнений видаd 2udt2u grad (u)  0 ,  > 0.t(4.2)Для решений этой системы имеемd  1  du du   du d 2u  du   ,   (u)    , 2    grad (u),  dt  2  dt dt dt   dt dt   du du    ,   0. dt dt (4.3)1  du du  ,   (u) во втором2  dt dt можно рассматривать как энергию материальной системы.

Соотношения(4.1) и (4.3) типа неравенств показывают, что нестационарные процессыхарактеризуются диссипацией энергии. Материальная точка в поле сил сuпотенциалом (u) и трением рано или поздно попадет в точку сtминимумом (u).Для наших целей нужно определить разумный выбор коэффициентатрения . Это проще всего сделать для простейшей модели квадратичнойфункции скалярного аргумента:Функцию (u) в первом случае и( x )  a 2 x 2 / 2 .Динамическое уравнение с потенциалом (x)x  x  a 2 x  0(4.4)имеет характеристическое уравнение22    a 2  0 с корнями 1,2    a2 .24Общим решением уравнения (4.4) будет x  c1e1t  c2e2t .Скоростьубываниярешенияопределяется()  max(Re 1 , Re 2 ) .131величинойV.

ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИПри  2aимеемRe 1  Re 2  ()   / 2  a .При > 2aвеличины22/4 – a2  0,12иивещественны22поэтомуи2Re 1   / 2   / 4  a  Re  2   / 2   / 4  a .Тогда2a2a2(  )  Re 1    a2   a .24/2 / 2  2 / 4  a2График () приведен на рис. 5.5.Качественные выводы, которые можно сделать из этого рассмотрения:1.Если  << 2a, то решение медленно устанавливается к положению равновесия, происходят колебания около положения равновесия.2.Если  >> 2a, то решение тоже медленно устанавливается, т.к.при большом трении не развивается большой скорости движения к равновесию.3.Оптимальное значение  лежит где-то посередине и зависит отсвойств конкретной функции (x).С практической точки зрения можно предложить реализацию алгоритма нахождения минимума исходя из динамической системы уравнений вида (4.2) с помощью явного метода Эйлера (о чем речь подробнеепойдет в главе VIII).

Выберем шаг интегрирования τ и коэффициентуменьшения скорости на каждом шаге . Шаг выбирается максимальновозможным, при котором алгоритм еще устойчив, а коэффициент = 0,995. Выберем начальное приближение к положению равновесия(минимума энергии) и скорость нашей материальной точки: x(0), v(0) = 0.1 ша г. v1/2n  v n 1  (xn 1 ) .2 ша г.v n   v1/2n .Настоящеетрениеприводитксвязи1/2v n  v1/2n  v n , т.е.   1   .3 ша г.

xn  xn 1  v n .Недостатком метода является наличие подгоночных параметров τ и. Достоинство – то, что алгоритм не заботится о значениях минимизируемой функции и о величине градиента. По ходу движения и то и другое может возрастать. Например, при повороте оврага вбок материальная132V.5. Задачи с решениямиточка заезжает на стенки оврага, однако в данном случае это достоинство, т.к. движение в главном идет в нужном направлении.Несколько практических рекомендаций: не занулять скорость привозрастании значения функции, не менять резко величину  с 0.995 до0.8 в окрестности минимума (хоть и хочется, чтобы колебания установились быстрее).Рис.5.5. Зависимость скорости затухания решения от коэффициента трениядля квадратичной функцииV.5. Задачи с решениямиV.5.1.

Свести задачу о нахождении решения системы нелинейных уравнений2 uvu  5 10 e  0,2 (u  v )  0v  5 10 eк вариационной задаче в области Ω = {|u – 0,1| ≤ 0,1; |v – 0,1| ≤ 0,1}.Решение. Решение системы сводится к нахождению условий минимума функционала(u, v)  (u  5 102 euv )2  (u  5 102 e(u v) )2 .V.5.2. СвестизадачуонахожденииминимумафункцииФ(u, v) = u4 + v4 – u2 – v2 в области Ω > {|u| ≤ 1; |v| ≤ 1} к решению системы алгебраических уравнений.133V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИРешение.

Задача о нахождении минимума функции (u,v) сводится к решению системы уравнений 0, 0.uvV.5.3. Найти значения {x, y}, при которых достигается минимум функции f ( x, y)  x3  y3  3xy.f  fи приравня,x  yем их к нулю. Получим систему двух нелинейных уравнений3x2  3 y  0, 3x  3 y 2  0.Решениями этой системы являются пары {0, 0}, {1, 1}. Подстановкой убеждаемся, что вторая точка является точкой глобального минимума.Решение. Вычислим частные производныеV.5.4. Методом деления отрезка пополам найти точку локального минимума для функции f (x) = x3 + e - x - x на отрезке [0, 1] с точностью ε = 10–2.Решение.

Обозначим границы отрезка a0 = 0, b0 = 1 и зададимΔ/2 = δ = 10 – 3. Вычислимf  0.5  (a0  b0  )   0, 2324 и f  0.5  (a0  b0  )   0,2307.Так как второе значение меньше первого, то положим (a1,b1) = (0.4990,1).Продолжая далее, получим(a3,b3) = (0.6238,0.7505), (a4,b4) = (0.6861,0.7505),(a5,b5) = (0.6861,0.7191), (a6,b6) = (0.7016,0.7191),(a7,b7) =( 0.7101,0.7198).V.5.5. С помощью метода Ньютона найти минимум функцииF (t )  sin t  cos t , t0 = – 0,5.Решение. Найдем точку минимума функции F(t) как корень уравнения Fʹ(t) = 0.

Для этого построим итерационный процесс Ньютона:t ( n 1)  t ( n) F (t ( n) ) (0), t = – 0,5.F (t ( n) )134V.5. Задачи с решениямиПриt(0) = – 0,5имеемF (t (0) )  cos t  sin t  0,3982,0,3982 0,7934. Даль0,1357 0,7854 .F (t (0) )   sin t (0)  cos t (0)  1,3570, t (1)  t (0) нейшие вычисления дают t (2)  0,7854, t (3)V.5.6. Методом наискорейшего спуска приближенно вычислить корнисистемы x  x 2  2 yz  0.1,2 y  y  3xz  0.2,2 z  z  2 xy  0.3,расположенные в окрестности начала координат.Решение.

Выберем точку начального приближения в начале координат: u(0) = (0,0,0)T.Нелинейная система уравнений записывается как F(u) = 0, где x  x 2  2 yz  0.1 2 y 1  2 x 2 z2F   y  y  3xz  0.2  , Якобиан J   3z1 2 y3x  . 2y2x1  2 z  z  z 2  2 xy  0.3 Для начального приближения 0.1 1 0 0F (0)   0.2  , J (0)   0 1 0   E . 0.3 0 0 10 1 (F(0) , J (0) J (0)T F(0) )1 (F(0) , F(0) ) 1 ,(0) (0)T (0)T (0)2 (J J F , JJ F ) 2 (F(0) , F(0) ) 21u(1)  u(0)  20  JT (u(0) )  F(u(0) )  u(0)  2 EF(0)  (0.1, 0.2,0.3)T .2Аналогичным образом находим второе приближение:F(1) 0.13  1.2 0.6 0.4 (1)  0.05  , J   0.9 1.4 0.3  , 0.05  0.4 0.2 1.6 135V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИJ(1)T1 u(2)F(1) 0.181  0.2748 (1) (1)T (1)  0.002  , J J F   0.2098  . 0.147  0.1632 1 (F(1) , J (1) J (1)T F(1) )1  0.3719 ,(1) (1)T (1)T (1)2 (J J F , JJ F ) 2u(1) 21  J(1)TF(1) 0.1  0.181   0.0327    0.2   0.379  0.002    0.2007  . 0.3  0.147   0.2453  Для контроля точности вычислим невязку:F(2) 0.032   0.017  . 0.007 V.6.

Теоретические задачиV.6.1. Привести пример функции f (x), заданной на множестве U  R иобладающей следующим свойством: а) глобальный минимум f (x) достигается на счетном множестве точек; б) f (x) имеет бесконечное число точек локального минимума, но глобальный минимум f (x) на U не достигается; в) f (x) ограничена снизу на U, но не достигает минимума.V.6.2. Пользуясь только определением точки минимума, доказать, чтолинейная на отрезке [a, b] функция f (x) = α x + β,   0 может достигатьминимального на этом отрезке значения лишь в точках x = a и x = b.V.6.3.

Привести примеры отрезков, на которых функции x2, – x2, ln x,cos x унимодальны.V.6.4. Доказать следующие свойства унимодальных функций:а) любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [a,b];б) функция унимодальная на отрезке [a,b] является унимодальной и налюбом меньшем отрезке c, d    a, b ;в) пусть f (x)  Q[a, b] и a ≤ x1 < x2 ≤ b; тогда если f (x1) ≤ f (x2), то x*  [a, x2], если f (x1) > f (x2), то x*  [x1, b], где x* –– одна из точек минимума на отрезке [a, b].136V.7. Практические задачиV.6.5.

Доказать, что из выпуклости функции f (x) на отрезке [a, b] следует ее унимодальность на [a, b], ограничиваясь только дифференцируемыми на [a, b] функциями. Верно ли обратное?V.6.6. Привести пример унимодальной, но не выпуклой функции.V.6.7. Пусть функция f (x) дифференцируема на множестве U = R и производная f ʹ(x) обращается в нуль в единственной точке ~x . Доказать, чтоесли lim f ( x)   , то ~x – точка глобального минимума f (x) на U.x V.6.8. Пусть f (x) – дифференцируемая унимодальная на отрезке [a,b]функция, причем |f ʹ(x)| ≤ M. Оценить точность δ(N) определения минимального значения f * методом перебора в результате N вычислений f (x).V.6.9.

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

Список файлов книги