Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 48
Текст из файла (страница 48)
Опишем очереднук> его итерацию исходя из того, что отрезок локализации [а>>'>, Ь~ ">] уже найден. Выполняют следующие действия: а< Ь> + Ь(Ь> а()(> + Ь()() 10. Вычисляют а("> = — б,,У("> = + б. 2 20. Находят значения У(а! )>>) и У(,0< ">). 30. Новый отрезок локализации определяют по правилу: если ~(а<х>) ~ ~(()<х>), [а<" <>, Ь<" <>] = [а<Ь>, ф< ">]; (А )~А' Р~ о(Ф если ~(а<Ь)) > ~(,0(Ь>), т() [а'"+'>, Ь(Ь+<>] = [а< ">, Ь<"'].
В первом случае за очередное приближение к точке минимума /7ооАго о <учоо принимают х("'<' = а()'>, а в() ,<~о ~и+о~) а о Ьа'о с,(у(ои ((о)оооу втором случае х' "+" =,У "' (рнс. 9.9). Рис. 9.9 Обозначим через Ь < и> = Ь ' и'— — а(и> длину отрезка [а<и>, Ь'и)]. Как нетрудно заметить, справедливо равенство ~> (и) ~( и+) >— 2 (9.9) Поэтому, если параметр 6 достаточно мал (6 < Ь<") ), то длина вновь полученного отрезка почти вдвое меньше длины предыдущего отрезка.
Отсюда — и название метода. Используя равенство (9.9), с помощью метода математической индукции легко показать, что ~ ( и) 2" видной оценки погрешности [х< и) — х~ С Ь(и> следует, что значение х действительно можно найти с точностью е и справедлив следующий критерий окончания итерационного процесса. Вычисления следует прекратить, как только окажется выполненным неравенство (9.10) ~(и) ~ е Тогда за приближение к х с точностью е можно принять х' = х< "'.
Заметим, что Ь(и) убывает и при и ~ 0 стремится к величине 2Ь, оставаясь при каждом и больше этой величины. Поэтому сделать пр« некотором и длину Л< "> отрезка локализации [а<и>, Ь< ">] меньше заданного е > 0 можно лишь, выбрав Ь с е/2. В этом случае из оче- Э а м е ч а н и е. При реализации метода на ЭВМ необходимо учитывать, что вычисления значений функции ~ будут производиться с погрешностью.
Для того чтобы знак разности ~'(а("))— — Г()8[™) совпадал со знаком разности Х(а(")) — У(У(")), необходимо, чтобы выполнялось условие б > з (см. равенство (9.2)). Поэтому 5 нельзя задавать слишком малым, Пример 9.8. Применяя метод деления отрезка пополам, найдем с точностью ь = 10 ~ точку,т локального минимума функции у (т) = аз —,т + е ~, локализованную на отрезке [О, Ц. Вычисления будем вести на 6-разрядной десятичй эвм, Задад„м Ь вЂ” 10-3 а(о) — 0 Ь(о) „(о) + Ь(о) 1 и т е р а ц и я.
1. Вычислим а(Ш 2 — — 0.499, а(о) + Ь(о) р(о) = 2 + б = 0.501. 2. Определим значения у (а( о) ) ()) 0.232389, у (ф( о) ) и 0.230676. 3. Так как у(о(о)) > у(о(о)) то следует положить [ а(1), Ь(1)1 .= [0.499, Ц. Результаты следующих итераций приведены в табл.
9.3. Таблица 9.3 (т())) л( ))) ~(а) У(а("') УСУ"') а( л) Ь( и) 0.000000 1.000000 0.499000 1.000000 0.499000 0.750500 0.623750 0.750500 0.686125 0.750500 0.686125 0.719088 0.701607 0.719088 0.710141 0.719813 ОА99000 0.232389 0.748500 0.143924 0.623750 0.154860 0.686125 0.140403 0.717088 0.139821 0.701607 0 139549 0.708348 0.139543 0.501000 1.000 0.230676 0.750500 0.501 0.144350 0.625750 0.252 О. 154131 0.688125 0.125 0.140230 0.719088 0.063 0.139940 0.703607 0.033 0.139520 0.711348 0.017 0.139587 0,010 Так как Ь<т> ~ 6, то при и = 7 итерации прекратим и положим х» <><,<3< "> = 0.711348. Таким образом, 2 = 0.71 1 0.01. Заметим, что дла достижения точности е = 10 2 потребовалось 14 вычислений функции.
3. Метод Фибоначчи. Заметим, что метод деления отрезка пополаи требует на каждой итерации вычисления двух новых значений функ ции, так как найденные на предыдущей итерации в точках а< "> Д< "> значения далее не используются. Обратим теперь внимание на то, что одна из этих точек (обозначенная в предыдущем параграфе через к< и>) является внутренней для отрезка [а' и', Ь< ">] и поэтому дальнейшее сокращение отрезка можно произвести, вычислив дополнительно значение функции лишь в одной новой точке. Это наблюдение приводит к методам, требующим на каждой итерации (кроме первой) расчета лишь одного нового значения функции ~ Два наиболее известных среди них — методы Фибоначчи и золотого сечения.
Метод Фибоиаччи> является оптимальным последовательным методом, т. е. методом, обеспечивающим максимальное гарантированное сокращение отрезка локализации при заданном числе У вычислений функции. Этот метод основан на использовании чисел Фибоначчи Г„, задаваемых рекуррентной формулой «и — «и-> + Гп-2 (и ~ 2) и начальными значениями Го — — 1, Г> —— 1. Укажем несколько первых чисел: Го — — 1, Г> — 1> Г2 — 2> Гз = 3 Г4 = 5, Ге = 8, Ге — 13, Гт — 21, Г8 = 34, Г>> = 55, Г>.> = 89 Гп = 144. Метод Фибоначчи состоит из У вЂ” 1 шагов. Очередной (Ь + 1)-й шаг выполняют здесь аналогично (Й + 1)-й итерациии метода деления отрезка пополам. В отличие от него точки а« "',,7< "' здесь находят по формулам <т<><> = а'"' + Ь< "> >у< "> = а'"' + Г Г Г>»-ь > ' Гл>->.> Новый отрезок локализации определяют по тому же правилу: если у(а< ">) ч 1ф< ">), то [а<ь" >, Б<" "] = [а< ">,,В<"']; если > (а< ">) > ~(~У< ">), то [а<" '>, Ь<" '>] = [а<Ь>, Ь<Ь>].
> Фибоначчи (Леонардо Пизан кий) (1180 — 1240) — итальянский математик 250 В первом случае за очередное приближение к точке минимума принимают х<Ь ') = а<Ь), а во втором случае х<)е <) =,д<") (рис. 9.10). Важно то, что в любом случае точка х< Ь~<) совпадает с одной из точек Ьа) а!")) Ь<е~l) ПеРбый ееу чаи а<" " — й<" " + ~1<)"<), Г ГК-Ь йюрай ееуе<ги Рис 9.10 Поэтому на очередном шаге достаточно вычислить значение функции лишь в одной недостающей точке. В результате выполнения К вЂ” 1 шагов отрезок локализации уменьшается в Г)))ъ)/2 раз, а точка х<)<) <) оказывается центральной для последнего отрезка локализации [а< )«'), Ь< )<)') ]. Поэтому для х<)<) <) справедлива следующая оценка погрешности: х< ~-<) ) Г)<ь) (9.11) Пример 9.9. Применяя метод Фибоначчи, найдем с точностью е = 10 д точку х локального минимума функп))<и ~(х) = хз — х + е х, локализованную на отрезке [О, 1].
Вычисления будем вести на 6-разрядной десятичной ЭВМ. Первым среди чисел Фибоначчи, для которого выполняется условие <<<!'Гу,< ( е (где Ь = 1), является число Ги = 144, отвечающее Х = 10. Зададим а<о) = О, Ь<о) = 1, П е р в ы й ш а г. 1. Вычислим а< о) = а< о! + (Ь< о) — а< о) ) — = — <)< Гд 55 Гы 144 и 0.381944 д<о) — а<о) + (Ь<о) а<о!) — <о = — я 0,618056. Гп 144 2. Определим значения ~ (а< о) ) и 0.356308, ~(д< о) ) ю О. 157028. 3. Так как ~(а<о)) > ~()У<о) ) то положим [а<<), Ь<<)] = [а<о), Ь<о)].
В т о р о й ш а г. 1. Учитывая, что а<<) = )д<о) и 0.618056, вычислим )д~ ~) = а<') + (Ь<') — а< ")Гд/Г<о )<) 0.763889. 2. Вычислим значение ~(д< )) ) )< 0.147712. 3. Так как ~(а<<)) > ~(д<<)), то положим [а<т) Ь<д)] = [а<)), Ь<<)]. Результаты остальных шагов приведены в табл. 9.4. Таблица 94 а) "' ,Ь)( о) ~(а( а) ) ~(ф())) ) Ь) "' а( и) После 9 шагов вычисления прекращаем и полагаем г и,У8) = 0.708334. Та- ким образом, г = 0.71 х 0.01. Заметим, что для достижения точности е = 10 2 потребовалось 10 вычислений значения функции, в то время как при исполь- зовании метода деления отрезка пополам необходимо 14 вычислений, Хотя метод Фибоначчи и оптимален в указанном выше смысле, зачастую он неудобен для использования. В частности, зто касается возможного применения поиска Фибоначчи для решения одномерных подзадач в алгоритмах многомерной минимизации.
Здесь нередко эффективность алгоритма одномерной минимизации оценивается не по тому, какая точность в значении х получена, а совсем по другим критериям, к которым метод плохо приспособлен. Например, бывает важно достичь минимального значения функции ~с некоторой относительной точностью б либо уменьшить значение ~на определенную величину. 4. Метод золотого сечения. Из-за указанных недостатков вместо 252 0.000000 1.000000 0.381944 1.000000 0.618056 1.000000 0.618056 0.854167 0.618056 0.763889 0.673611 0.763889 0.673611 0 729167 0.694445 0.729167 0.694445 О.Т 15278 0.701389 0.715278 0.381944 0.356308 0.618056 0.157028 0.763889 0.147712 0.708334 0.139527 0.673611 0.141905 0.708334 0.139527 0 694445 0.139805 0.708334 0.139527 0.701389 0.139553 0,708334 0.618056 1.000 0.157028 0.763889 0.618 0.147712 0.854167 0.382 0.194672 О.Т63889 0.236 0.147712 0.708334 0.119 0.13952? 0.729167 0.090 0.140830 0.708334 0.056 0.139527 0.715278 0.035 0.139731 0.708334 0.021 0.139527 0.708334 0.014 метода Фибоначчи чаще используется теоретически почти столь же эффективный мствод эоло)т>ото сечент<я.
Напомним, что золотыл сечекиелд отрезка называется такое раз биение отрезка на две неравные части, что отношение длины всего отрезка к длине его большей части равно отношению длины большей части к длине меньшей части отрезка. Золотое сечение отрезка [а, Ь[ осуществляется каждой из двух симметрично расположенных относительно центра отрезка точек а= а+ 2 (Ь вЂ” а), )з = а+ 2 (Ь вЂ” а) З+Ф 1+4Ь (рис. 9.11). Действительно, как нетрудно проверить, — «Ь — а1+ф~ — ар — а1+ф — а а — а 2 ' р — а Ь вЂ”,Ь< 2 Замечательно то, что точка а осуществляет золотое сечение не только отрезка [а, Ц, но и отрезка [а,,Ы). >9 — а а — а 1+ ф Действительно, <т — а Р— а 2 Рис. 9.11 Точно так же точка,У осуществляет золотое сечение не только отрезка [а, Ь1, но и отрезка [<т, Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
