Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 47
Текст из файла (страница 47)
е. х ~ 1, ~~(х) ~ 1, ~"(х) 1, то соотношение (9.3) можно записать в терминах относительных погрешностей так: в/г Отсюда следует, что если б(~) 10 ", то б(х~)" 10 . Иными словами, если значения функции вычисляются с тв верными значащими цифрами, то приближенное значение точки минимума можно найти примерно лишь с т(2 верными значащими цифрами. Таким образом, точность определения положения точки минимума гладкой функции существенным образом зависит от точности вычисления функции ~ При этом если для поиска х используются только приближенные значения ~(г), вычисляемые для различных х, то неизбежна потеря примерно половины верных значащих цифр. Предположим теперь, что для отыскания точки локального минимума можно использовать вычисляемые каким-либо образом приближенные значения (~ ) (х) производной функции ~ Как уже отмечалось в з 9.1, в рассматриваемом случае задача минимизации эквивалентна задаче отыскания корня х нелинейного уравнения Ях) = О.
Из ре- зультатов ~ 4.2 вытекает, что последняя задача обладает значительно 243 меньшей чувствительностью к ошибкам. В частности, справедлива следующая оценка границы абсолютной погрешности: (9.4) Сравнение (9.4) с оценкой (9.3) показывает, что алгоритмы, исполь- зующие для отыскания решения х уравнения (9.1) вычисление значений производной, могут достигать более высокой точности, чем алгоритмы, использующие для минимизации функции ~только вычисление ее значений. Пример 9.5.Оценим радиус интервала неопределенности для каждой из точек х8 88 -3,7, х2 818 0.7 локального минимума функции ~ (х) = хз — х + е х в случае, когда вычисление функции производится на $-разрядной десятичной ЭВМ'.
Заметим, что ~(х~) Ф ~(-3.7) м -6.5, ~(х2) 22 ~(0.7) й 0.14. Так как для используемой ЭВМт ам = 5 10 7, то в малой окрестности точки х8 верхняя граница Ь1 абсолютной погрешности вычисления ~ приближенно равна е„/Х(х1) ~ 88 5 10 ~ 6.5 = 3.25 10 е. Аналогично, Ь2 в е, ~~(хт)~ 5.
10 7'0.14 = 7'10 8. Вычисляя значения второй производной ~ (х) = 6х + е х при х = х1, х = = х2, получаем,1"(х1) 88 16, ~"(хг) в 4.7. В силу формулы (9.2) радиусы интервалов неопределенности оцениваются следующим образом: гг 2Д~~~(ку) 2 О8.28 ° 1О г/18 г 8.10 г, гг г 2~Ьг/У '4~71 " 2 477'18 ~14 1 " 2'1О 4. Следовательно, точку хт можно найти с большей точностью, чем точку х1, если использовать сравнение вычисляемых на 6-разрядной десятичной ЭВМ значе- ' Напомним, что 6-разрядной десятичной ЭВМ мы условились называть гипотетическую ЭВМ, имеющую 6 десятичных разрядов мантиссы и производяющую округление по дополнению.
т Напомним, что через е„обозначено машинное эпсилон — величина„характеризующая относительную точность представления чисел в ЭВМ. 244 ккй функции Х При этом каждую из точек можно найти с точностью е = 10 з, но вряд ли удастся найти с точностью е = 10 ~.
Пример 9.6. Пусть теперь точки х1 и хт локального минимума функции /(х) = г~ — х + е х ищутся как решения нелинейного уравнения /'(х) = Зхт - 1 - е х = О. (9.5) Оценим в этом случае радиус интервала неопределенности для каждой из точек х1, хт, если вычисления ведутся на той же ЭВМ, что и в предыдущем примере.
Оценим сначала границу абсолютной погрешности вычисления производной исходя из приближенного равенства Ь = Ь(У') = Ь(Зхт) + Ь(1) + Ь(е-х) я ем(Зхт + е х). Тогда Ь1 и ем(Зх7~ + е ) н 4 ° 10 5, Ьг и ем(Зхт + е ) и 10-в На основании формулы (9.4) имеем е1 п Ь1/~ (х1) и 2. 10 в, вт и Ь2/У (хт) н 2 ° 10 т. (9,6) Заметим, что погрешности представления чисел х1, хт на б-разрядной десятичной ЭВМ таковы: й„~ х~ ~ и 2 ° 10 в, ем~ хг~ и 4 ° 10 т.
Поэтому получ~сные оценки (9.6) означают, что, решая уравнение (9.5), можно найти точки х1 н х2 с максимальной для используемой ЭВМ точностью, равной соответственно 2 10 в и 4 ° 10 т (ср. с результатом предыдущего примера). з 9.3. Методы прямого поиска. Оптимальный пассивный поиск. Метод деяния отрезка пополам. Методы Фибоначчи и золотого сечения Ряд методов минимизации основан на сравнении значений функции .ь вычисляемых в точках х1, хг, ..., ху Эти методы часто называют методами прямота поиска, а точки х; — пробными пточками.
Прежде чем перейти к изложению некоторых из наиболее известных методов прямого поиска, уточним постановку задачи. Будем счи- 245 ра точки х' = ц, справедливы неравенства У (х~-1) Э ~ (хь) и 7 (ц,) ~ 7" (х1 ~). Поэтому из п. Зо предложения 9.2 следует, что х Е ~х~-1, хь,1]. Значит, ] х— — х1,~ < шах (х~ — х~-П ц, 1 — хД. Так как положение точки минимума х на отрезке [а, о] заранее неизвестно„то для х' = хь справедлива лишь следующая гарантированная оценка погрешности: ~х-х'~ 4 шах ~х;-х,1~. (9.7) 1( и(К+1 Рис. 0.8 Можно показать, что величина, стоящая в правой части неравенства (9.7), станет минимальной, если точки х1, х2, ..., ху расположить на отрезке [а, о] равномерно в соответствии с формулой х, = а + 1Ь, где й = Ь/(У + 1), Ь = о — а. Метод с таким выбором пробных точек называется оптимальным пассивным поиском.
Гарантированная оценка погрешности для него выглядит твк: ~х-х'~ 4 У+1 У+ 1' (9.8) Пример 9.7. Используем оптимальный пассивный поиск для того, чтобы найти с точностью е = 0.1 точку х локального минимума функции г" (х) = язв — х + е х, локализованную на отрезке [0, 1]. Из формулы (9.8) следует, что для решения задачи потребуется вычислить значения функции в девяти пробных точках вида х; = 0.1в', где 1 = 1, 2, ..., 9. Приведем таблицу этих значений: 246 тать, что требуется найти приближение х' к точке минимума х унимо дальной на отрезке 1а, о] функции 7.
Предположим также, что число пробных точек У заранее фиксируется и за приближение х' к точке минимума принимается одна из этих точек. 1. Оптимальный пассивный поиск. Метод решения поставленной ' задачи, в котором задается правило вычисления сразу всех пробных точек х1, хт, ..., ху и за х' принимается та точка хь, для которой У(х~) = ппп ~(х;), называется ме~подом пассивно1о поиска. Соот 1~ КК ветствующая геометрическая иллюстрация приведена на рис. 9.8. Оценим погрешность этого метода. Для удобства положим хо — а, ху,1 — 6. В силу выбо- Таблица 92 к 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 у 0.81 0.63 0.47 0.33 0.23 0.17 0.14 0.16 0.24 Так как минимальное значение достигается в точке зт= 0.7, то з = 0.7й0.1.
Если бы мы попытались найти к с точностью я = 10 з, то оптимальный пассивный поиск потребовал бы вычисления значений функции уже в 99 точках. 2. Метод деления отрезка попонам. Пусть для решения поставленной задачи последовательно вычисляются значения функции >' в У пробных точках х>, з2, ..., к>>>, причем для определения каждой из точек к>, можно использовать информацию о значениях функции во всех предыдущих точках к>, зг, ..., х»->. Соответствующие методы называют я>етодая>и посяедоватеяьното поиска.
Рассмотрим простейший из методов этого семейства — л>етод деления отрезка»о»олая>. В нем, как н в двух других рассматриваемых в этом параграфе методах (методах Фибоначчи и золотого сечения), используется принцип последовательного сокращения отрезка локализации, основанный на предложении 9.2 и на следующем простом утверждении. П р е д л о ж е н и е 9.3. Если фуякт>ия уния>одальна на отрезке [а, Ь], тпо она унилсодальиа и на л>обо а отрезке [с, И] С [а, Ь].
Для удобства изложения обозначим отрезок [д. Ь] через [а(о>, Ь(о>]. Поиск минимума начинают с выбора на отрезке [а>о>, 6~о'] двух симо>о> + Ь>о> метрично расположенных точек а> о> 2 — 6,,6> о> д>о> + Ь>о> Ь вЂ” а 2 + в. Здесь 0 < Ь <, 6 — параметр метода.
Далее 2 вычисляют значения > (а>о>) и 1" (>!1'о>). Сравнение этих значений в силу предложения 9.2 позволяет сократить отрезок локализации следующим образом: если у(п>о>) ~ у(>7>о>) то х ~ [а»> ц»] — [а>о> >7[о>]. есл, У(,„>о>) ~ У(>по>) то з Е [д<>> Ь»>] — [„>о> Ь>о>] Если описанную процедуру принять за одну итерацию метода и продолжить аналогичные операции для образования последовательности сокращающихся отрезков локализации, то получим итерационный метод.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
