Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 49
Текст из файла (страница 49)
Этот факт далее существенно используется. Очередная (х + 1)-я итерация метода золотого сечения производится аналогично (х + 1)-й итерации метода деления отрезка пополам. В отличие от него точки а< ">,,У "> находятся по формулам <1< Й) — <<< ><) 2 я<>) —,<Ь) + 2 д < й) 3+,6 1+ 45 Важно то, что какой бы из отрезков [<><"), Ь<") ~ или [а<"), Ь< ">~ не был бы выбран за очередной отрезок локализации, тОчка х<><'" (в первом случае х<~ ') = а<"), а во втором случае х'"+') =,У")) совпадает с одной из точек <т< ь '>, >у<><+>).
Поэтому на очередном шаге дос- ) Термин ".золотое сечение" ввел Леонардо да Винчи. Принципы золотого сечения широко испольэовали сь прн композиционном построении многих произведений мирового искусства (в особенности, архитектурных сооружений античности и эпохи Возрождения). ЛЗ величину, не превышающую 1+ 45 2 [ х< п) х ~ ~,/), < и) —,<) < и+1) 1+ )/5 (9.12) которую можно использовать для апостериорной оценки погрешности.
Заметим, что каждая итерация сокращает длину отрезка локализации в (/5 + 1)/2 раз. Поэтому Ь'и' — а<п' = Ь<п) = (2/(45 + 1))п Ь и справедлива следующая априорная оценка погрешности: и+< 1х<п) — х! ~ (9.13) Таким образом, метод золотого сечения сходится со скоростью геомет- рической прогрессии, знаменатель которой 9 = 2/()<5 + 1) п 0.62.
Пример 9.10. Найдем методом золотого сечения с точностью е = 10 2 точку г х локального минимума функции )-(х) = х~ — х + е х, локализованную на отрезке [О, 1]. и а<о) = О, Ь<о) = 1. 1 и т е р а ц и я. 1. Вычислим а<о) = а<о) + 2 (Ь<о) а<о)) и 3 +,5 и 0.381985, Д<о) = а< ) + 2 (Ь<о) — а<о)) и 0.018034. 1 +,/5 2. Вычислим У(а< о) ) и 0.358280, )'(,0<о) ) и 0.157037. 3. Так как ~(а<о)) > )"(0<о)), то положим [а<<), Ь")] = [а<о), Ь<о)]. П и т е р а ц и я. 1. Учтем, что а<<) =,Уо) )) 0.518034, и вычислим ,<)<') = а<)) + 2 (Ь<)) — а«') и 0.783936.
1+ ф 2. Вычислим ~(ф<)) ) и О, 147725. 3. Так как )'(а«)) = 7(<)<о)) > ) (р<<)), то положим [а<2), Ь<2)] — [а<1) Ь<1! ] Результаты остальных итераций приведены в табл. 9.5. таточно вычислить значение функции лишь в одной недостающей точке. Заметим, что точка х' и) отстоит от концов отрезка [а < п), Ь < п) ] на 2 Ь<п).
Поэтому верна оценка Таблица 9.5 (1( ))) ~(<~())) ) (ю) ~(ф(п) ) а())) 5( а! 0.618 0.382 0.236 0.146 0.090 0.056 0.034 0.021 0.013 0.008 Так как (1(»о» < е, то итерации следует прекратить и положить х в а(8) ))» и 0.703182. Таким образом,,г = 0.70 й 0.01. Отметим, что для достижения точ- ности е = 10 2 потребовалось 10 вычислений значений функции, как и в методе Фибоначчи. Ь.
Эффективность методов прямого поиска. Эффективность указанных методов можно оценивать, например, тем, во сколько раз уменьшается после использования У вычислений значений функции первоначальная длина Ь отрезка локализации. Другой критерий — величина гарантированной оценки погрешности. Табл. 9.6 позволяет сравнить по этим критериям рассмотренные выше методы. Как видно, очень неэффективен пассивный поиск.
Метод деления отрезка пополам уступает почти эквивалентным по эффективности методам Фибоначчи и золотого сечения. 0.000000 1.000000 0.381966 1.000000 0.618034 1.000000 0.618034 0.854102 0.618034 0.763936 0.673764 0.763936 0.673764 0.729493 0.695051 0.729493 0,695051 0.716337 0.695051 0.708204 0.381966 0.356280 0.618034 0.157037 0.763936 0.147725 0.708204 0.139526 0.673764 0.141883 0.708204 0.139526 0.695051 0.139774 0 708204 0.139526 0.703182 0.139525 0.618034 0,157037 0.763936 О.
147725 0.854102 О. 194622 0.763936 0.147725 0.708204 0.139526 0.729493 0.140868 0.708204 0.139526 0.716337 0.139782 0.708204 0.139526 Таблица 96 Величина гарантированной оценки погрешности Длина отрезка локализации Метод прямого поиска Оптимальный пассивный 2 поиск Ф+ 1 Метод деления отрезка пополам (У вЂ” четное, величиной 6 1 пренебрегаем) lг 2 Метод Фибоначчи — Ь ~ 1.7. (0.62)л Ь 2 Гдь1 1 Ф+ 1 Ф-1 Ь м1.6 (0.62)л' Ь ( 2 Метод золотого сечения (— Я+1 Приведем еще одну таблицу (табл. 9.7), из которой видно, сколько вычислений функции 7" нужно сделать для того, чтобы достичь точности е. Предполагается, что начальный отрезок локализации имеет единичную длину. Таблица 97 Число Упри заданном Е Метод прямого поиска я=10' к=10' я=10' я=10' 6=10' Оптимальный пассивный 9 99 999 9999 99999 18 26 6 12 32 5 10 15 19 24 5 10 15 20 24 6.
Влияние погрешности вычислений. Одна из самых распространенных ошибок при обращении к стандартным программам, реализующим тот или иной метод на ЭВМ, состоит в завышении требуемой точности. Необходимо понимать, что при наличии погрешностей в вычислении значений функции 7 достижимая точность а методов пря- 256 поиск Метод деления отрезка пополам (6 < е) Метод Фибоначчи Метод золотого сечения в 0.5.
(0.71)к' 6 ~ 0.85 (0.62)л' Ь ~ (0.62)л. Ь $9.4. Метод Ньютона и другие методы минимизации гладких функций Отметим, что применение рассмотренных выше методов деления отрезка пополам, Фибоначчи и золотого сечения не позволяет извлечь никакой выгоды из возможной гладкости функции. Существуют методы, которые могут оказаться более эффективными, если минимизируемая функция достаточно гладкая. Часть из них является просто модификациями известных методов решения нелинейных уравнений (см.
гл. 4) применительно к уравнению (9.14) У'(х) = О. 1. Метод бисекции. Пусть ~ — унимодальная непрерывно дифференцируемая на отрезке [а>'>, Ь! О>] = [а, Ь] функция и на отрезке [а, Ь] точка х является единственной стационарной точкой. Применительно к решению уравнения (9.14) одна итерация ае»>ода бисекции выглядит следующим образом. Пусть отрезок локализации [а'">, Ь>п>] известен и найдено значение х<п> = (а<п> + Ь(п>)/2. Тогда производят следующие действия.
1О. Вычисляют значение >"'(х' и'). 2О. Если ~'(х'и>) < О, то полагают [а'и+>>, Ь>п" ] = [х<п>, Ь'">]. В противном случае полагают [а'и+'>, Ь> и+>>] = [а'"', х'"']. 30, Вычисляют х(п+>> = (а(п+>> ~ Ь<п+>>)~2 В рассматриваемом случае метод сходится с оценкой погрешности ~х'и> - х] ~ — „„ (9.15) и обладает всеми присущими методу бисекции решения нелинейных уравнений достоинствами и недостатками (см.
$4.3). Возникает лишь дополнительная проблема, связанная с необходимостью вычисления производной ~'. мого поиска ограничена снизу величиной е» К(Я/Г'(х), где е— радиус интервала неопределенности (см. ~ 9.2). Это означает, например, что прямые методы не позволяют найти на 6-разрядной десятичной ЭВМ точку хх локального экстремума функции ~(х) = х~ — х + е х с точностью к < е2» 2.10 4. Задание е < а2 приведет лишь к бесполезной трате машинного времени. 2. Метод Ньнттона. Для решения уравнения (9.14) можно попытаться воспользоваться методом Ньютона (см.
з 4.6), расчетная формула которого в данном случае принимает вид х(и+)) — х(и) — ' ', и 1 О. Г( (и)1 Г(х< и) ) (9.16) Следствием теоремы 4.6 является следующее утверждение. Т е о р е и а 9.1. Пусть в некоторой окресп)ностпи точки х функ <1ия / трижды непрерывно дифференцируемв и выполняется условие /"(х) > О. Тоьдв найдется такая малая о-окрестность корня х, что ири проиэвольном выборе начально(о приближения х'0) из этой о-окрестности метод Иьютона (9.16) сходится авадратично.
В силу сверхлинейной сходимости для метода Ньютона можно использовать следующий критерий окончания итераций: (х(и) — х'и )) ~ ( Е. (9.17) Пример 9.11. Используя метод бисекции, найдем с точностью е = 10 2 точку локального минимума функции у(х) = ьз — х + е х, локализованную на отрезке [О, 11. Положим а О) — 0 Ь(О) — 1 х(О) — (а(О) + Ь(О))/2 = 0.5. Заметим, что Г(х) = Зхт — 1 — е х. 1 и т е р а ц и я.
1. Вычислим Г(х< О) ) и -0.856531. 2. Так как Г(х(0)) ( 0 то [а(1), Ь(1)1 — [х<0), Ь(0)] 3. Вычислим х<)' = (а<)) + Ь<)))/2 = 0.75. Результаты остальных итераций приведены в табл. 9.8. Таблица 98 а( и) Ь( и) х( и) Г(х'и)) (Ь<и)-а<и))/2 После выполнения шести итераций вычисления можно прекратить и поло- жить х н точности х(е).
Таким образом, х = 0.71 т 0.01. Отметим, что для достижения 10 2 потребовалось шесть вычислений значения производной Г(х) 258 0.000000 0.500000 0.500000 0.625000 0.687500 0.687500 0.703125 1.000000 1.000000 0.750000 0.750000 0.750000 0.718750 0.718750 0.500000 0.750000 0.625000 0.687500 0.718750 0.703125 0.710938 О.856531 0.215133 -0.363386 -0.084863 0.062444 -0.011882 0.500 0.250 0.125 0.063 0.031 0.016 0.008 11ример 9.12. Используя метод Ньютона, найдем с точностью е = 10 е очку локальйого минимума функции у (х) = хз — х + е х, локализованную на грезке (О, 1].
Положим х' о> = 0.5. Результаты вычислений по формуле (9.16), имеющей в данном случае вид 2 < л) 3(х<а) ) — 1 — е х х« "'> = х<а> <») 6х< Я! + ех приведены в табл. 9.9. Таблица 99 ~ х< и) х<»-1) ) х< ») При» = 4 итерации прерываются. Можно считать, что х = 0.705642 ~ 10 е. Заметим, что точность е = 10 З была достигнута уже после выполнения двух итераций. 3.
Метод последовательной параболической интерполяции. Этот метод предназначен для минимизации гладких функций, но в отличие от методов бисекции и Ньютона не требует вычисления производных. Опишем одну итерацию простейшего варианта этого метода. Предположим, что уже известны три предыдущих приближения х<1 2>, х<>«>, х<><> к точке х. Пусть у = Р2(х) = <т)< "> + п<><>(х — х< ">) + + р< "'(х — х'"> )т — уравнение параболы, проходящей через три точки плоскости с координатами (х<" т>, ~(х<12>)), (х<" ", 1(х«<»)), (х'"', ~(х<"')). Здесь х<><-) > .<Ь У(.< ><>) У ( < <)-г>) >в<~> = ~(х<~>), и<<<> = < )>, 2, < >, г> + х<<с) х<й-2> у(х< ><-<) ) у (х<й) ) И 1 У(х< >> 1> ) — У (х<><) ) У(х< й) ) — У (х< <<-2>) ' —;~~~ —;~~г— ~ 0 0,5000000 1 0.7374944 2 0.7062126 3 0,7056421 4 0.7056419 2 ° 10 ) 310~ 6 101 2, 10-т .< )> л< > .< > <-т> 259 За очередное приближение х< Ь " к х принимается та точка, в которой функция Рр(х) достигает минимума.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
