3 часть (1081356), страница 46
Текст из файла (страница 46)
х 17.26. 1(х) = хг — 2х+ е, [1; 1,5], е = 0,05. 17.27. ((х) = Гдх — 2ашх, [О; х774], е = 0,03. 17.28. 7'(х) = ь71 + хг + е г*, [О; Ц, е = 0,1. 17.29. 1(т) = ха+ 4тг — 32х+ 1 [1 5 2] е = 0 05 7 3 г 17.30. 7(х) = — хт — х)+ -хг — х, [1; 1,5], е = 0,05. 17.31. 1(х) = хз — Ззшх, [0,5; Ц е = 0,05 17.32. [(х) = 5хг — 8ха1л — 20х, [3; 3,5], е = 0,02.
1 17.33. )'(71) = — хз — 5х+ х1п х, [1,5; 2], е = 0,02. 17.34. Пусть у (х) - — унимодальная дифференцируемая на [а; 6] функция, причем ])'(х)[ < М при х Е [а; 6]. Оценить погрешность Ьи нахождения минимума Х*, методом перебора при разбиении отрезка [а; Ь] на п частей. Метод перебора, предполагающий предварительный выбор точек х„ 1 = О, 1,..., и, называется также пассивной стра1лсгией поиска точки минимума х".
На практике точки х; выбира1отся заранее, когда удобно провести и+ 1 независимых зкспериментов по измерению значений 7'(х), а последовательное намерение этих значений трудоемко или невозможно, например ввиду нехватки времени. Однако использование уже получен- ной в предыдущих вкспсрилгентах информации о функции )(х) для вы- бора очередной тачки х, измерения (вычисления) у(х) приводит к более эффективному поиску точки х'. Методы минимизации, в которых точки х1 определяются в процессе поиска точки минимума с помощью най- денных ранее значений функции )'(х), называются последовательными методами.
Метод делскил отрезка пополам является простейшим последо- вательным методом минимиаации. Он позволяет для любой функции )'(х) Е 0[а; 6] построить последовательностьвложенных отрезков (а; Ь] З З [а1, 61] 3 З [а„1, Ь„1] З [а„; 6„], каждый из которых содержит хотя бы одну цз точек минимума х" функции 7(х). Пусть е ) 0 — тре- буемая точность определения точки х*. Выбрав Б Е (О; 2е), построим последовательности (а„), (6„), (х,")) и (х~~"~), п = О, 1, ..., используя рекуррентные формулы ао = а, Ьо = Ь, 3 1.
Численные методы минимизации функций одной переменной 329 а 1 1) п, х, х) Ь„,х 11)1 а а„) хлх) х) 1!„1 х а„х* Ь„ л„х" Ь„ Риг. 23 Рис. 22 Полагая х" (а„+ 6„)/2, находим х' с абсолютной погрешностью, не прсвосходпшей величины е„= (6„— а„)/2 = (6 — о — Ь)/2" ы + б/2. (3) Испольауя условие ск < с, из последнего выражении можно найти необходимое число шагов и длц обеспечения требуемой точки е. Однако на практике часто поступают иначе: определив границы отрезка [а„; Ь„], вычисляют с„по формуле (3) и сравнивают с заданной точностью е. Пример 5.
Решить пример 4 методом делении отрезка пополам. з Положим Ь = О, 02 < 2с = О, 1. Построим последовательность вложенных отрезков [о„; 6„] по формулам (2), записывал результаты вычислений в таблицу 1.2; Таблица 1.2 Переход от отрезка [о„), 6„!] к атрсаку [асд 6„] методом деления отрезка пополам иллюстрирустсл на рис. 22, если /()с,' ) < /()с " ), и на рис. 23, сели /(х," ) ) /(л~" )). Гл. 17.
Методы оптимизации ЗЗО Следовательно, х' 1,72, и У'* - ((1,72) = 92, 13. ~> Для увеличения скорости стодилюсти метода величину б е (О; 2е) целссообраано выбирать как можно меньшей, однако зтог выбор ограничен снизу используемым количеством всрныт десятичных знаков при задании аргумента х. В любом случае б должно быть больше машинного нуля применяемого вычислительного средства. 17.35. Показать, что каждый из отрезков [а„; 6„], и = 1, 2, ..., полученных методом деления отрезка пополам, содержит хотя бы одну из точек минимума функции у (х) Е Я[а; 6]. 17.36. Показать, что для У(х) Е Я(а; 6] и шагов метода деления отрезка пополам обеспечивает вычисление точки минимума х* на отрезке [а: 6] с абсолютной погрешностью, не превосходящей 17.37. Найти число шагов я метода деления отрезка пополам, необходимое для определения точки минимума функции у(х) Е Е Я[а; 6] на отрезке [а; 6] с точностью е > О.
17.38. Достаточно ли вычисления 10 значений функции у (х) Е Е 9[0; 1] для определения ее точки минимума на отрезке [О; 1] с точностью е = О, 02 методом деления отрезка пополам? 17.39*. Сравнить необходимые количества вычисленных значений Мл и М„функции у(х) при поиске ее точки минимума на отрезке длины 1 с точностью е = 10 ~ методами деления отрезка пополам и перебора соответственно. В задачах 17.40-17.48 методом деления отрезка пополам найти точку минимума х' функции у'(х) на отрезке [а; 6] с точностью е и минимум у*: 1 17.40.
У(х) = х + —., [1; 2], е = 0,02. 17.41. у'(х) = х а1их + 2 сов х, [ — 5; — 4], е = 0,02. 17.42. ('(х) = х4+ 8хз — бх~ — 72х+ 90, [1,5: 2], е = 0,05. 17.43. у'(~) = ха+ Зхт+ Π— 1, [ — 1; 0], = 0,1. , 2 17.44. у'(х) = 10х!п х — —, [0,5; 1], е = 0,05. 17.45. у(х) = хз + 2 (х!8 — — 2), [1,5; 2], е = О, 01. е 17.46. У'(х) = Зх4 — 10хз + 21хз + 12х, [О; 0,5], е = 0,01. 2х 17.47.
У(х) = — — 2х~, [ — 3,5; 4,5], е = 0,02. 1и2 17.48. 7(х) = е' — — хз+ 2х, [ — 1,5; — 1], е = 0,01. 3 Ц 1. '1нслелные методы минимизации фгнкций одной переменной 331 И(с!с!од зояотоео осчеяиш также лвллстгл погледовнтгшысыы методом лсинцмизацпи. Опираясь ца свойства золотого ссчснил огрслзсас, зтот лсстод использ) ст найсдснныс значения ((х) более рационально, чем лкстод дслснпл отрезка пополал! (см.
задачу 17.53), что позволяет переходить к очередному отрезку, галс'ржшцему точку .г после вычисления одного, а нс двух зна сепий ) (х). Деление отрезка на две нсравныс части так,что отношение длиюл всего отрез!а и длине большей его части равно отношению длины большей части к длине меньшей части, называстсл зояаггсым сечением этого отрезка. Золотое сечение отрезка [а: 6] осусцествллстгл двумя тачками 3 — ос 5 сссб — 1 х! — — а+ (6 — а), хг = а+ (6 — а), (4) причем х! сеть вторая точка золотого сечснил отрезка [а; хг], а хг— первзл точка золотого сечения отреака [хс; 6]. Знал одну пз точек золотого сечения отрезка [а; 6], другую можно найти по одной иа формул (5) т! = а + 6 — хг, .тг = а + 6 — х!. Пусть 1(х) Е („)[а; 6] и требуется найти то шу минимума х" функпии ((сг) на [а; 6]. Построссм погледоватсльногтн (аи), (6и] и (хи], и = = 1, 2, ..., следующим образом: (и — !) (и — !) (и-с! (и-!) аи ие аи,, 6„= х,, хи = т, сели с" (:г! ) < )"(ссл ); (и — !) (и — !) (и-!) (и — с) аи — хс, 6и = 6и с, ти = хг, (.'глн,)(х! ) ),) (з'г ), (б) (и-!) (и-!) и = 2, 3,..., где а! = а, 6! — — 6, х, и хг — первая н сгорал точки золотого сечения (4) отрезка [аи !) 6и с].
Для определения чисел аи, би, х„по найденным аи с, би,,;ги ! необходимо выполнить следующие операции: 1) найти одну из точек зачатого сечении отрезка [аи (; 6и (] по известной другой точке х„с, используя формулы (5) '); 2) вы шслить значсннс ((х) во вновь найденной тоске золотого сечения (аначснис в л)изгой точке хи ! улке вьгсислсно на одном ич предыдуших шагов); 3) сРавпить значения ((х,и ) и ('(з!.,и ) и найти аи, би, хи по формулам (5). Такпы образом, на каждом шаге определения аи, 6и и хи н = 2,3,..., трсбуетгл вычисление одного значенил ("(х). Положив т," хи, найдем ! ) Прн определении х" г большой точностью,чтобы избегать накопления ошибок округления, обычно точки золотого сечения отрезка [а„; 6и] находят по формупалс (4) н о качестве х, н хг используют х„! н ту из найденных †!) ( — !) точек, которая больше отяпчзстся от х 332 Гл.
17. Методы оптимизации точку минимума х' с точностью е„: [х" — х„[ < е„= !Ь вЂ” а), У х/5 — 1! 2 откуда следует, что число шагов и метода золотого сечения, обеспечивающее заданную точность е нахождения точки х*, должно удовлетворять неравенству я ) !и ( — ): )и -2,1!и [ — ~. [7) 1Ь вЂ” а) ~ 2 ) ' 1Ь вЂ” а! Пример 6. Решить пример 4 методом золотого сечения. а Вычисления проведем по формулам !6), представив результаты в таблице 1.3, где стрелками отмечены сохраняюшиеся при переходе к следуюшему шагу значения.
Таблица 1.3 Из таблицы 1.3 получаем х* хь = 1,736, У'* Дхь) = — 92, 138. Заметим, что если воспользоваться формулой !7), то необходимое число шагов п можно определить заранее. В нашем случае и > 4,79, т.е. п = 5, и отпадает необходимость во втором столбце таблицы 1.3 3 — ~/5 17.49. Показать, что каждая из точек х! = а+ [Ь вЂ” а) 2 ,'5-1 и хз = а+ [Ь вЂ” а) осуществляет золотое сечение отрезка 2 [а; Ь!. 1. Численные методы минимизации ф>наций одной переменной 333 17.50. Пусть х> и хг — точки золотого сечения отрезка [а; 6]. Показать, что х> являстсн второй точкой золотого сечения отрезка [а; хг], а хг — первой точкой золотого сечения отрезка [х>, 6].
17.51. Пусть х> и хг — точки золотого сечения отрезка [а; 6]. а) Доказать, что справедливы равенства т> = а, + 6 — хг, хг = = а+6 — х>. б) Найти длины отрезков [а,; хг] и [х>, 6]. 17.52. Найти длину Ь„отрезка [а„; 6„], полученного методом золотого сечения при поиске точки минимума х* функции на от(>/5 — 1 1 резке [а; 6], и показать, что ]х* — хв] < (6 — и), где 2 х„— одна из точек золотого сечении отрезка [а„; 6„]. 17.53. Сравнить необходимьн> количества вычисленных значений >>л и )1>, функции у (х) при се минимизации на отрезке длины 1 с точностьн> с = 10 ' методами делении отрезка пополам и золотого сечении соответственно.
В задачах 17.54 — 17.62 методом золотого сечения найти точку минимума х* функции у(х) на отрезке [а; 6] с точностью я и минимум у*: 1 17.54. у!х) = 2х+ —, [О; Ц, е = 0,1. х' 17.55. у'(х) = х~ + 2хг + 4х + 1, [ — 1; О], я = 0,1. 17.56. у'(х) = хз — 5хз + 10хг — 5х [ — 3 — 2] я = 0 1 17.57. 1(х) = ха + Зт(1пх — 1), [0,5; Ц, с = 0,05. 17.58. у(х) = хг — 2х — 2созх, [0,5; Ц, е = 0,05. 17.59.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
