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

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

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

Пусть функция Φ(u) дважды непрерывно дифференцируема. Тогда достаточным условием того, чтобы стационарная точкаu* была точкой локального минимума, является положительная определенность матрицы Гессе 22 u1G (u*)   2   um u12 u1um .2  um2 Отметим, что методы отыскания минимума Φ(u) нередко оказываются более эффективными, чем методы численного решения СНАУ.V.2. Метод перебораПусть U = [a, b], т.е. отрезок числовой оси. Разобьем его на n равных частей с узлами в точках ui = a + i (b – a) / n ; i = 0,  , n.Вычислив значение Ф(u) в этих точках, найдем, путем сравненияточку u*, в которой(u*)  min (ui ).0i nДалее полагаем: u*  umin , *  (u*).

Погрешность в определении u* этого простейшего метода не превосходит числаn ba.n(2.1)Этот метод прост, но неэкономичен, особенно когда ищется минимум функции многих переменных. Например, в гиперкубеU = {0 ≤ ui ≤ 1, 1 ≤ i ≤ 10} с разбиением каждого из отрезков (по каждойиз координат) на 10 частей, с быстродействием 10 6 операций в секунду116V.3. Нахождение минимума функции одного переменногопотребуется около 107с (примерно 4 месяца) для нахождения min (u ) ,Uесли предположить, что количество арифметических действий, необходимое для вычисления значений Φ(u) в каждой точке требует тысячиарифметических операций.

Этот метод можно сделать более эффективным, если сначала определить минимум с грубым шагом, затем уже искать минимум с меньшим шагом на том из отрезков [xi, xi+1], на которомпредполагается наличие минимума; можно и далее уточнять решениезадачи таким же образом.Дальнейшим усовершенствованием этого метода в случае поискаминимума функции одного переменного являются методы исключенияотрезков, а именно: дихотомии (деления отрезка пополам) и золотогосечения.V.3. Нахождение минимума функции одного переменногоДля функции одного переменного можно строить эффективные алгоритмы нахождения минимума при условии, что минимум локализованна некотором отрезке [a,b]. Если на данном отрезке локализации расположен не один локальный минимум, а несколько, то алгоритмы нахождения минимума найдут один какой-нибудь, при этом не обязательнобудет выполнено условие (1.2).

Для того чтобы найденный минимум былглобальным минимумом на отрезке локализации, необходимо, чтобыфункция была унимодальной, т.е. была монотонной по обе стороны отточки минимума (непрерывность функции при этом не требуется).V.3.1. Метод деления отрезка пополам (метод дихотомии)В этом методе отрезок [a, b] делится на 3 части выбором внутри отрезка точек u1, u2, в которых вычисляются значения целевой функции.Сравнив ее значения в этих точках можно сократить отрезок поиска точки минимума, перейдя к отрезку [a, u2], если Φ(u1) ≤ Φ(u2) или [u1, b],если Φ(u1) ≥ Φ(u2). Эту процедуру можно продолжить.Если вычисление значения функции стоит недорого, имеет смыслсокращать отрезок как можно сильнее, и тогда в методе дихотомии точки u1, u2 выбираются близко к середине отрезка u1 = (b + a – Δ)/2,u2 = (b + a + Δ)/2, где Δ достаточно мало.

Поскольку отношениеu2  ab  u1близко к 1/2, такой выбор объясняется стремлением,babaобеспечить максимальное относительное уменьшение отрезков.117V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИВ конце вычисления в качестве приближенного значения u* беретсясередина последнего отрезка.

В результате n итераций длина отрезкабудетn ba  11 nnn 12221ba 1     1   ,n22 2n т.е. точность определения u* составляет εn = Δn /2.Находя n из условия εn ≤ ε, получим количество итераций, необходимое для достижения данной точности:n  log 2ba.2  (3.1)Если в предыдущем неравенстве положить Δ малой, то n   b  a  2n1 .(3.2)V.3.2.

Метод золотого сеченияВ случае, когда операция вычисления значения функции являетсядорогостоящей, имеет смысл сокращать отрезки локализации минимуматак, чтобы наиболее эффективно использовать значение в пробной точке, оставшееся от предыдущего шага вычислений на новом отрезке локализации. Найдем расположение точекu1, u2 на [a, b], для чего рассмотрим отрезок [0, 1] и для определенности положим, что при его уменьшении исключается его правая часть. Из соображений симметрии точкиu1, u2 должны быть расположены симметрично относительно серединыотрезка (рис. 5.1):001 u10 ,51u2u1 u 12u2Рис.

5.1u1Пусть u2 = τ, тогда симметрично расположенная относительно центра отрезка точка имеет координату u1 = 1 – τ.118V.3.3. Метод параболПробная точка u1 отрезка [0, 1]перейдет в пробную точку u12  1  нового отрезка [0, τ]. Условием деления отрезков [0, 1] и [0, τ] в одном итом же отношении точками u2 = τ и u12  1   является равенство11 , или 2    1  0,откуда находим положительный кореньт.е. u 1 1     3  5 5  1 2  0,61803,2, u2   5  1 2.Для отрезка [a, b]u1  a  3  5 (b  a) 2; u2  a 1.2.5  1 (b  a) 2Замечания.Точки u1, u2 обладают следующим свойством: каждая из них делитотрезок [a, b] на две неравные части так, что отношение длины всегоотрезка к длине его большей части равно отношению длин большейи меньшей частей. Точки, обладающие таким свойством, называются точками золотого сечения, введенного Леонардо да Винчи.На каждой итерации отрезок поиска минимума уменьшается в одноми том же отношении5  1 2,(3.3)поэтому в результате n итераций длина становится равнойn   n (b  a).(3.4)*Следовательно, точность εn определения точки u после n итераций равна n  n 2  5 1 2n(b  a) / 2;(3.5)а условие окончания вычислительного процесса будет n  .V.3.3.

Метод параболМетоды, использующие исключение отрезков, основаны на сравнениизначений функции в двух точках отрезка локализации, при этом учиты119V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИваются лишь значения функции в этих точках.Учесть информацию о значениях функции между точками позволяют методы полиномиальной аппроксимации. Их основная идея заключена в том, что функция Φ(u) аппроксимируется полиномом, а точка егоминимума служит приближением к u*.

Разумеется, в этом случае, кромесвойства унимодальности, необходимо на Φ(u) наложить и требованиядостаточной гладкости для ее полиномиальной аппроксимации.Для повышения точности поиска u* можно как увеличивать степеньполинома, так и уменьшать пробный отрезок. Поскольку первый приемприводит к заметному увеличению вычислительной работы и появлениюдополнительных экстремумов, обычно пользуются полиномами второй(метод парабол) или третьей (метод кубической интерполяции) степени.Алгоритмпоискаминимумасостоитвследующем.Выбираем на отрезке локализации три точки u1,u2, u3, такие, чтоu1  u2  u3 и u1  u*  u3 .По этим трем точкам построим параболу (квадратичный интерполяционный полином) в форме Ньютона:P2 (u)  0  1 (u  u1 )  2 (u  u1 )(u  u2 ),график которой проходит через точки (u1, (u1 )), (u2 , (u2 )), (u3 , (u3 )).Коэффициенты Δk , k = 1, 2, 3, находим из системы уравненийP2 (u1 )   (u1 ), P2 (u2 )   (u2 ), P2 (u3 )   (u3 ),откуда получаем0  (u1 ), 1 (u2 )  (u1 ),u2  u11  (u3 )  (u2 ) (u2 )  (u1 ) .u3  u1 u3  u2u2  u1Точка u минимума P2(u) находится приравниванием его производной кнулю:2 u   u1  u2  1 2  2 .Далее полагаем: u*  u (очередное приближение точки минимума).Эту процедуру можно продолжить до достижения необходимой точности, выбирая новые точки uk, k = 1, 2, 3.

Для этого можно применять ме-120V.3.4. Модифицированный метод Брендтатоды исключения отрезков, используя в качестве двух пробных точек u2и u , таких, что u2, u  [u1, u3 ].Иногда методом парабол называют метод нахождения нуля производной целевой функции, аналогичный методу секущих. При этом выбираются конкретные точки u1 = u(s) + h, u2 = u(s), u3 = u(s) – h , и тогда новое приближение к положению минимума определяется формулойh (u ( s )  h)   (u ( s )  h)u ( s 1)  u ( s )  .2  (u ( s )  h)  2 (u ( s ) )   (u ( s )  h)Метод критичен к выбору начальной точки и значению третьейпроизводной целевой функции в окрестности минимума: если эта производная мала, есть вероятность, что метод не сойдется вовсе.

Теоретически у метода квадратичная сходимость, как у метода Ньютона.V.3.4. Модифицированный метод БрендтаДля гарантированной сходимости не хуже линейной, а в окрестности минимума – квадратичной, прибегают к модифицированному методуБрендта.Начинают метод, например, с четырех точек золотого сечения напервоначальном отрезке локализации минимума [a,d], расположенных впорядке возрастания аргумента: a < b < c < d, при этомΦa > b,c < d.Построим две параболы так, что первая проходит через точкиP1 = (a, (a)), P2 = (b, (b)), P4 = (d , (d )) , а вторая – черезP1 = (a, (a)), P3 = (c, (c)), P4 = (d , (d )) .

Пусть минимум первой параболы достигается в точке f, а второй в точке e (см. метод парабол). После того как точки f и e найдены, проверяем их на приемлемость.1 ша г. Проверяем, что выполнены два условия для каждой из точек:eab3c  de,24f a  3bcd f .42При невыполнении условий помещаем точки на ближайшую границу разрешенного интервала.2 шаг. Проверяем, что |f – e | > , где  – задаваемая точностьнахождения положения минимума.

В противном случае полагаем, чтоf = e +  или e = f + .121V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИ3 шаг. Упорядочиваем точки a, b, c, d, e, f в порядке возрастания,выбираем из них подряд четыре новые точки, для которых выполненоΦi > i+1,i+2 < i+3.Процесс прекращается, когда отрезок локализации становитсяменьше 2.Трудности, с которыми сталкиваются методы полиномиальной аппроксимации при сильно асимметричной функции, проиллюстрированына рис. 5.1 для нахождения минимума потенциала Леннарда–Джонса:U(r) = 4ε ( (d/r)12 – (d/r)6). Параметры глубины потенциальной ямы ε идиаметра молекулы d были взяты единичными.

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

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