Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 34
Текст из файла (страница 34)
..., х„х,, На первом этапе одновременно выбираются две точки, х» и х» „причем х»,< х». Если !'(х»,)()(х»), то интервал неопределенности сужается до [х» „11, и у нас уже есть опорное значение Г(х») для последующего угпочнения интервала неопределенности. С другой стороны, если ~(х»,)~~'(х»), то интервал неопределенности сужается до [О, х»1, и мы уже знаем Г(х»,). Вот ключ к оптимальному выбору х„, и х». обеспечить, чтобы тестовая точка, унаследованная суженным интервалом неопределенности, находилась в оптимальном для последующего поиска положении.
Полезно определить координату г точки х относительно интервала [а, Ь] как число, равное (х — а)[(Ь вЂ” а). Таким образом, з имеет по отношению к интервалу [а, Ь[ координату О, Ь— 1 координату 1, а средняя точка — координату — . 2 ' Пусть Г» -Г»=1 Г»=2 Г»=3 Г '"5 Гг=8 ° ° ° Г»=Г» — г+ +Г„ ,. Числа Г; — это знаменитые числа Фибоначчи. Опгимальная стратегия последовательного поиска максимума назы° ается поиском Фибоначчи, поскольку она тесно связана с этими числами, При оптимальной стратегии выбирают х»,=-Г» ,[Г» и х» — — Г„ „1Г».
Какой бы из интервалов 1О, х»1 или [х» ,, !1 не стал суженным интервалом неопределенности, унаследованная гочка будет иметь по отношению к новому интервалу одну из двух следующих координат: Г»,„[Г», или Г»,~Г» и Тогда в качестве х» ., выбирается точка, имеющая по отношению к новому интервалу другую из этих координат. Используя )(х»,) и значение функции, унаследованное от прежнего интервала, можно ше сократить интервал неопределенности и передать в наслед"тво одно значение функции. На последнем шаге мы придем к некоторому интервалу неопрехеленности 1а, Ь), причем средняя точка будет унаследованной зт предыдущего шага. Тогда в качестве х, выбирается точка к с одномьянля оптимизлция 199 1 с относительной координатой — +е, и окончательным интервалом 2 1 ! неопределенности будет либо(О, — +е), либо ( —, 1) относительно (а, Ы.
На первом шаге длина интервала неопределенности уменьшилась с 1 до Е„,(Р„. На последующих шагах уменьшениедлин интервалов выражается числами Таким образом, длина окончательного интервала неопределенности равна (! +2е)7Рд. Пренебрегая е, заметим, что асимптотически !/г'ь равно гл при й-»оо, где г =- ж 0.6180. 2 Следовательно, асимптотически, для больших й каждый шаг поиска Фибоначчи сужает интервал неопределенности с коэффициентом 0.6180. Этот результат нужно сравнить с 0.6, коэффициентом сужения интервала неопределенности в методе бисекции для нахождения нуля функции. Для больших значений й координаты точек хь, и х, близки соответственно к 1 — гж0.3820 и г-0.6180, и старт с этих значений близок к оптимальной стратегии.
Чтобы понять, как продолжать дальше, предположим (для определенности), что 7(0.3820)- )~ (0,6180). Тогда, как мы знаем, х находится в интервале [О, 0.6180). Следовательно, нужно вычислять 1 в точках 0.3820» »0.6!80 и 0.6180»0.6!80, Но, поскольку 0.6180»0.6180ж0.3820= жх„с и то в этой точке 7 уже известна. Таким образом, на каждом шаге, начиная со второго, требуется лишь одно вычисление функции, и каждый шаг уменьшает длину интервала неопределенности с коэффициентом 0.6180: В противоположность поиску Фибоначчи, здесь не нужно фиксировать число А до начала поиска.
В связи с исторической известностью числа гж0.6180 этот метод нахождения х называется поиском золотого сечения. Число 1!г=-ср — —.(1+)с'6)/2=1.6180... называется золотым относиением. В гл. 7 было отмечено, что порядок сходимости метода секущих равен числу ср. Золотое отношение ср имеет важное значение и возникает во многих различных задачах. Интересное обсуждение, связанное с этим числом, есть в книге Гарднер (1961). Поиск золотого сечения аналогичен методу бисекции для нахождения действительного нуля функции (гл.
7) в том отношении, что он с гарантией работает даже в самом худшем случае и что платой за эту гарантию является медленная, всего лишь а оптимизация 200 линейная сходимость. Метод золотого сечения не извлекает никаких выгод из возможной гладкости функции 7. Если известно, что 1 имеет непрергявные производные и можно начать достаточно близко к х, то можно сконструировать следующий итерационный процесс: начинаем с трех произвольных действительных чисел пь а„о,. В общем случае имеем числа аь „о„, и и„, Пусть аь„— абсцисса вершины параболы (с вертикальной осью), проходящей через точки (п„((о;)), !=а — 2, а — 1, а.
Продолжаем итерации с числами аь „пь и п„„. Зтот процесс называется паследоаагпельнай параболической интерполяцией. Можно доказать, что для достаточно хороших начальных приближений итерации сходятся со скоростью порядка ж1.324..., при условии, что )'"(х))0 в точке минимума (т, е. !'(х) имеет простой нуль).
В.2. Подпрограмма рМ!й В книге Брент (1973) предложен алгоритм нахождения минимума, в основе которого — комбинация метода золотого сечения и последовательной параболической интерполяции. Алгоритм этот совершенно аналогичен методу нахождения нуля 2ЕКО1Х из гл. 7, который использует комбинацию бисекции и обратной квадратичной интерполяции. В конце этого параграфа помещена трансляция на ФОРТРАН алгоритма Брента, записанного автором на языке АЛГОЛ 60.
Зто — подпрограмма-функция ЕОХСТ10Х РМ!Х (А, В, Е, ТО1.). Здесь [А, В! — исходный интервал, на котором определена функция Г. ТО). это входной параметр, который, грубо говоря, задает желаемую длину интервала неопределенности на выходе. Следовательно, если положить Т01. равным 10-", а результат, полученныи ГМ1Х, имеет величину порядка 1, то этот результат имеет около десяти верных цифр. Если же задать для ТО( значение 10-', а ответ равен (например) 0.00000385746, то, вполне возможно, в этом ответе верных знаков нет вовсе; однако, если вы интерпретируете результат такой величины как нуль, тогда вы не нуждаетесь нн в каких верных цифрах.
ЕМ!Ы использует поиск золотого сечения, переключаясь по возможности на последовательную параболическую интерполяцию. Подпрограммы АЛЕКО!К и ГМ(Ы имеют одни н те же параметры — интервал поиска, вычисляемую функцию и границу погрешности, Обе подпрограммы пытаются уменьшить длину интервала, пока она не станет меньше заданной границы. Есть, однако, важное различие между двумя программами, которое в.а. подпРОРРАмма Рм!и 20! влияет на выбор границ.
Если 1(х) ==О, а Г'(х)4=0, то для малых е 1(х+в) =1(х)+н( (х)+в — +... Св, . 1" (х) где с=('(х). Малые изменения в х вызывают пропорционально малые изменения в Г'(х). Разумно, поэтому, выбирать границу погрешности для УЕКО1Н примерно той же величины, что и ошибки в значениях функции. Зачастую эти ошибки имеют порядок ошибки округления в машине. Однако если мы разыскиваем точку минимума, где ~'(х)=0, а 1" (х)~0, то для малых е )(х+в) =1(х) +ев — +...
жг(х)+се', где с=гп(х)/2. Изменение порядка е в х теперь вызывает изменение в Г(х) порядка ва. Следовательно, было бы неразумно задавать в качестве границы погрешности для ЕМ!К число, меньшее, чем квадратный корень из ошибки в значениях функции. Другими словами, простые ну ли функции часто можно найти с почти полной машинной точностью, а точки, где функция достигает минимума— лишь с примерно половинной' точностью. Если ТОЬ вЂ” заданная граница для ХЕКО1Х или ГМ!1в, а МАСНЕР5 — машинная точность (определяемая самими подпрограммами), то ХЕКО1К никогда не вычисляет значения функции в точках, отстоящих одна от другой меньше, чем на 2 «МАСНЕР8 в АВВ (Х) + ТОЫ2, в то время как ЕМ!И никогда ие вычисляет функцию в точках, отстоящих одна от другой меньше, чем на В() ~Т (МАСН ЕРЗ) в АВЗ (Х) + ТОЬ~З. Таким образом, ЕМ!(н с большей вероятностью, чем ХЕКО1Ы, игнорирует малые значения параметра Т01..
Уннмодальные функции встречаются в практике относительно редко. Часто известно лишь, что 1(х) убывает прн возрастании х от 0 до некоторой неизвестной точки минимума х, после чего 1(х) возрастает '). Желательно как можно быстрее найти приближение к х, причем никакого априорного представления о том, где х находится, нет. Нам не известна какая-либо теория для этой задачи. Программы часто выбирают некоторое а)0 и затем вычисляют 1(0), Г(а), 1(2а), 1(2еа), Г(2'ст) и т, д., пока зна- ') А затем, быть может, снова убывает. В этом смысле уннмодальность отсутствуЕт.— Прим.
перев, 202 я оптимизация чения 1 продолжают убывать; в качестве приближения к х принимается кратное 2ва с наименьшим )(х). Илн же, если )(а)) = Г(0), то программа вычисляет значения ((2-'и), 1(2-'а),..., пока не будет найдено Г(2-"а), такое, что Г(2-'а)(ДО), и тогда 2-'а принимается за приближение к х. Читатель может придумать различные способы улучшения приближений к х, получаемых этими грубыми методами. Во многих приложениях, однако, целесообразно принять подобную грубую оценку для х н затем вернуться к основному алгоритму, для которого одномерный поиск является подпрограммой.
Для программы, иллюстрирующей использование РМ1)Ч, мы взяли ту же функцию )(х)=-х' — 2х — 5, что и для УВК01Ы. Поскольку Т' (х) — квадратный многочлен, то экстремумы можно найти аналитически. Заметьте, что значение параметра Т01., используемое здесь, есть квадратный корень из' величины, заданной для УЕЛО!)Ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
