1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 45
Текст из файла (страница 45)
Поскольку вблизи минимума чаще всего бФ (бх)', то небольшая погрешность функции приводит к появлению довольно большой области неопределенности бх у' бФ. 3. Метод парабол. Метод золотого сечения надежный, но медленный. Если Ф(х) дифференцируема, то можно построить гораздо более быстрые методы, основанные на решении уравнения Ф'(х)=0. Напомним, что корень х этого уравнения является точкой минимума, если Ф" (х) ) О, и точкой максимума при Ф" (х) <О. На практике часто Ф(х) имеет и первую производную и вторую.
Поэтому.для нахождения нулей первой производной применяют метод линеаризации, что приводит к такому итерационному процессу: МИНИМРМ ЮУНКЦИИ ОДНОГО ПЕРЕМЕННОГО тремя членами, т. е. аппраксимируем кривую параболой Ф (х) Ф (х,) + (х — х,) Ф' (х,) + — (х — х,)' Ф" (х,); 1 Ь Ф (х,+51) — Ф (х,— Ь) 2 Ф (х, + Л) — 2Ф (х,) + Ф (х, — Ь) (12) Это эквивалентно замене кривой на интерполяционную параболу, построенную по трем точкам х, — Ь, х„ хх+ Ь.
Обычно выбирают вспомогательный шаг Ь вЂ” 0,1 — 0,01 при ручных расчетах с небольшим числом знаков и Ь 0,01 — 0,001 при расчетах на ЭВМ; то~да характер сходимости вблизи экстремума вплоть до расстояний Ьз практически не отличается от квадратичного. Формула (12) наиболее, часто употребляется в практических расчетах.
Этот способ кажется неэкономным, нбо на каждой итерации надо вычнслять трн значения функцнн. Построейне параболы по трем последовательным итерациям, как это делалось в методе парабол прн нахождении корней много- члена, дает Ф (Х5 «5-1) 2х „т=хх+х ч (х5 хх 1, хз й (16) н требует только одного вычисления функцнн за итерацию. Однако ранее уже отмечалось, что такая замена производных разделенпымн разностямя уменьшаег скорость сходнмостн. Можно показать, используя опнсанную в главе Ъ', 4 2, и.
7 технику, что вблнзн невырождсннога минимума ~ Ф" (х) 1о,заз ) х ., — е, = ! . †, †, ~ 1 х — х /1,ЗЗЗ. 1 6Ф" (х) (14) Во-первых, отсюда видно, что ) хх„,— Е ~ ( ~х,— х 1„только если выполнено условие ~ х,— х ~ ( 6Ф"(Ф5 1; это приблизительно показывает размеры окрестностн корйя, в которой Итерации сходятся. Эта окрестность может быть небольшой, если Ф" (х) неявка. Во-вторых, аснмптотнческая скорость сходнмостн определяется показателем степенн прн ! х, †х , 'в правой части соотношения (14). Этот показатель невелик; позтол1у сходнмость настолько медленна, что трн итерации по этой формуле только немного сильней уменьшают погрешность, чем одна итерация по формуле (12).
А поскольку формула (13) ьедостаточно нспытана на пррктике, то нет уверенности, что ова окажется лучше. минимум этой параболы достигается в точке, определяемой формулой (!1). Итерационный процесс (11) является ньютоновским; вблизи простого корня уравнения Ф'(х) =О, т. е. вблизи экстремума с ненулевой второй производной, он сходится квадратично.
Если же Ф" (х) = О, то сходимость в достаточно малой окрестности экстремума есть, но она1 более. медленная — линейная. Обычно для первой и тем более второй производной получаются очень громоздкие выражения. Поэтому выгоднее заменить их конечно-разностными аппроксимациями. Наиболее часто берут. симметричные разности (З.б) — (3.7) с постоянным шагом, что приводит к формуле ПОИСК МИНИ»1УМА 1гл, чп Заметим, что во всех вариантах метода парабол для успешной работы необходимы «кухонные» поправки к алгоритму.
В ходе вычислений надо проверять, движемся ли мы к минимуму: вторая разность, стоящая в знаменателе формулы (!2), или вторая производная в знаменателе формулы (11) должна быть положительной. Если она отрицательна, то итерации сходятся к максимуму, и надо сделать какой-то шаг в обратном направлении, причем достаточно большой. Вычислив новое приближение, надо обязательно проверить, уменьшилась ли функция. Если оказалось, что Ф (х,ы) ) Ф (х,), то значение х,ы нельзя использовать и надо просто сделать от точки х, какой-то шаг в сторону убывания функции. Обычно делают шаг величиной т(х„,— х,) с т='/» и проверяют условие убывания функции; если оно снова не выполнено, то уменьшают т вдвое и делают шаг опять из точки х„и так до тех пор, пока не добьются убывания функции.
Фактическая скорость работы программы очень сильно зависит от того, насколько тщательно обдуманы эти поправки к алгоритму. Если функция имеет несколько локальных минимумов, то итерационный метод может сойтись к любому из них. Удалять найденные минимумы можно только в том случае, когда мы располагаем явным выражением. для Ф'(х) и решаем не исходную задачу (1), а уравнение Ф'(х) = 0; тогда удаляют уже найденные корни этого уравнения при помощи техники, описанной в главе Ч. Если так сделать не удается, то выбирают несколько начальных приближений в разных участках отрезка 1а, Ь), и из каждого начального приближения проводят какой-нибудь итерационный процесс поиска минимума.
Некоторые из этих итерационных процессов могут сходиться к одному и тому же локальному минимуму, а некоторые — к другим. Остается сравнить найденные локальные минимумы между собой и выбрать наименьший (если это требуется по условиям задачи). Описанный способ не дает гарантии того, что будут найдены все минимумы (и тем самым, что будет найден абсолютный минимум). Но для недостаточно изученной функции такой гарантии не дают никакие способы.
4. Стохастические задачи. Опишем один алгоритм, рассчитанный на стохастические задачи. Он основан на предположении, что ошибки определения функции Ф (х) имеют статистическую природу, т. е. они целиком случайны, а систематической погрешности нет. Тогда можно определить минимум со сколь угодно высокой точностью (фактически игнорируя область неопределенности дх 3 '6Ф), если воспользоваться таким итерационным 20! МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ » 2! процессом: х„„= х„— ф !Ф (хл + Ьл) — Ф (х„— Ьл)1, (16) где ал, Ьл — последовательности положительных чисел, удовлетво- ряющие следующим условиям: а„, Ь,— О, ~), а«=со, ~~ ~ — "") ~со. луп л=! (! 6) й 2. Минимум функции многих переменных 1. Рельеф функции.
Основные трудности многомерного случая удобно рассмотреть на примере функции двух переменных Ф (х, д). Она описывает некоторую поверхность в трехмерном пространстве с координатами х, у, Ф. Задача Ф(х, у) =ш!п означает поиск низшей точки этой поверхности. Как в топографии, изобразим рельеф этой поверхности линиями уровня. Проведем равноотстоящие плоскости Ф=сопз! и найдем линни их пересечения с поверхностью Ф(х, у); проекции этих линий на плоскость х, у называют линиями уровня.
Направление убывания функции будем указывать штрихами, рисуемыми около линий уровня. Полученная картина напоминает топографическое изображение рельефа горнзонталямн. По виду линий уровня условно выделим (три типа рельефа: котловинный, овражный и неупорядоченный. При котловинном рельефе линии уровня похожи на эллипсы (рис. 37, а). В малой окрестности невырожденного минимума рельеф функции котловинный. В самом деле, точка минимума гладкой функции определяется необходимыми условиями — = — =О, (17) и разложение функции по формуле Тейлора вблизи минимума При выполнении этих условий х„-»х с вероятностью единица при п- со (напомним, что стремление с вероятностью единица означает «почти всегда стремится», а не «обязательно стремится»).
Условиям (16) удовлетворяют, например, а„=1!и и Ь,=п-". Этот алгоритм является обобщением алгоритма Роббинса— Монро, описанного в главе Ч, на задачи поиска минимума. Он сходится весьма медленно, ибо изменение аргумента за шаг равно ~хл„— х„~ — 2ал!Ф'(хл)!, а величины ал убывают очень медленно, как видно из второго условия (16). Поэтому применять этот алгоритм к детерминированным задачам невыгодно. 202 поиск минимума )гл, пи имеет вид Ф (х, д) = Ф (л, и) + — „(Лх)а Ф „+ +сзхстУФ„а+ 2 (сту)а Фаз+..., (18) причем квадратичная форма (18) — положительно определенная*), иначе эта точна не была бы невырожденным минимумом.
А линии уровня знакоопределениой квадратичной формы — это эллипсы. д дт .)тг Т л г) Рис. 37. Случай, когда все вторые производные равны в этой точке нулю и минимум определяется более высокими производными, по существу ничего нового не дает, и мы не будем его специально рассматривать (линии уровня вместо эллипсов будут похожими на них кривыми четвертого порядка). Отметим, что условию (17) удовлетворяют также точки максимумов и седловые точки. Но в точках максимумов квадратичная *) Квадратичная форма ~ ам а, ае назмвается положительно определена, а ной, если при любых га (за иснлюченнем обраптаюптихся одновременно в нуль) она положительна, МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ 203 форма (18) отрицательно определенная, а в седловинах она знакопеременна.
Вблизи минимума функция мало меняется при заметных изменениях переменных. Поэтому даже если мы не очень точно определим те значения переменных, которые должны минимизировать функцию, то само значение функции при этом обычно будет мало отличаться от минимального. Рассмотрим овражный тип рельефа. Если линии уровня кусочно-гладкие, то выделим на каждой нз них точку излома. Геометрическое место точек излома назовем истинным оврагом, если угол направлен в сторону возрастания функции, и гребнем— если в сторону убывания (рис. 37, б). Чаще линии уровня всюду гладкие, но на них имеются участки с большой кривизнои; геометрические места точек с наибольшей кривизной назовем разрешимыми оврагами или гребнями (рис.
37, в). Например, рельеф функции Ф(х, у) = 10(у — з(ох)'+0,1х>, (19) изображенный на этом рисунке, имеет ярко выраженный извилистый разрешимый овраг, «дно> которого — синусоида, а низшая точка — начало координат. В физических задачах овражный рельеф указывает на то, что вычислитель не учел какую-то закономерность, имеющую вид связи между переменными. Обнаружение и явный. учет этой закономерности облегчают решение математической задачи. Так, если в примере (19) ввести новые переменные ~=х, «1=у — з(их, то рельеф становится котловинным. Неупорядоченный тип рельефа (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
