Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 33
Текст из файла (страница 33)
Вспомним, что, согласно анализу, лй и=— лз где Π— угол, Если принять образуемый кривой с какой-нибудь фиксированной прямой. зту прямую за ось л денартавой системы координат, то Нл — =соя 8 бз вагона, не превышающей 11 футов? Заметьте, что каждый конец рейки закрепляется в 6-дюймовом жестком вертикальном паве. Укозолилз тонкие деревянные рейки при столь сильнык прогибах подчиняются закону Гука линейной упругости и хорошо моделируются эгасглилами, или упругими линиями. Известна, что для такой линии кривизна и удов- !93 УПРАЖНЕНИЯ вЂ” =з)п 8.
йу йэ Вследствие симметрии относительно вертикальной оси, данная задача превращается в краевую задачу, которая может быть решена методом стрельбы. Удобно выбрать координатную систему так, как показано на рисунке. Тот факт, что концы рейки зафиксированы в жестких пазах, дает краевое условие к(0)=0. Симметрия требует, чтобы верх (центр) рейки был горизонтальным, так что 8(5)+8(0)= —. Для стрельбы имеются два параметра: 8(0) и 2' (йи)йэ) (0). Поэтому нужны две копии подпрограммы ЛЕИО!)ч', и одну из них придется переименовать. Можно избежать повторных вызовов библиотечных функций 31Х и СОЗ.
заметив, что й й8 — (щп8) = 8 — = ° 8, йэ йэ й8 — (сов 8) = — з! п 8 — = — н з|п 8. с(э оз Таким образом, для вычисления синусов и косинусов можно интегрировать вместе с другнмн и эти два дополнительных дифференциальных уравнения. Цель этого задания — заставить вас удивиться тому, что люди смогли за. селить запад, не имея компьютеров. 7.9. Решите следующую нелинейную краевую задачу относительно у(х) на интервале 0 ах<1: д"=д 1, д(О)=О, д(!)=-!. а) Примените метод стрельбы, описанный в 56.6, используя УЕЛО!)л) и ККГ45.
б! Изучив 5 7.Ь, попробуйте решить задачу иначе. Разбейте заданный интервал на и равных подыптервалов: О=ха < хл < х «... х г < х = 1. Замените дифференциальное уравнение разностными уравнениями с и — 1 не- известнылш рм у,... „У„г, где у! аппроксимирует у(хг): у г 2у ь у л Л (уэг 1) л 1 2 п 1 ре=О, р„=!. Решите эту нелинейную трехдиагональную систему, скажем, для л — 50 а) В качестве третьего возможного подхода, попробуйте следующее. Заметим, что у"=уэ — 1 можно переписать в виде Отсюда (р'Р 9" — — — +у=с 2 3 для некоторой константы с. Поскольку у(0)=0, то 9'(0)= У 2с. Следовательно, если бы мы могли вычислить с, то краевая задача превратилась бы в задачу 7. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 194 Коши, Интегрирование полученного уравнения дает ; ~" (~+ "з'-у~"' Используйте подпрограммы 2ЕК01Р1 и 1,111ЛгзС8, чтобы найти с из уравнения 7 оу уа з 177 Г72 ~ с+ — — у) ) о '~ З а затем с помощью ЯКг45 постройте искомое решение.
8. оптимизщия Часто встречающаяся в научных вычислениях задача состоит в определении максимума или минимума (и соответствующих аргументов) действительной функции Дхь..., х„) от и действительных переменных на множестве 5 и-мерного пространства. Слово оптимизация означает либо минимизацию, либо максимизацию функции. Иногда 5 совпадает со всем л-мерным пространством; в этом случае задача оптимизации называется безусловной. В противном случае задача имеет ограничения, именно условия, определяющие множество 5. Обычно 5 определяется совокупностью нелинейных функций, удовлетворяющих уравнениям или неравенствам.
Другими словами, точна х принадлежит 5 тогда и только тогда, когда х удовлетворяет неравенствам д,(х) ~ )О, ( = 1, ..., п„ где д, — заданные функции от х. Задачи с ограничениями, где д; — нелинейные функции, обычно гораздо труднее решать, чем соответствующие безусловные задачи. Если функция ) и все ограничения д; являются линейными фунициями, то говорят о задаче линейного программирования. Можно показать, что решение лежит в вершине выпуклого многогранника, определяемого ограничениями в л-мерном пространстве.
Обычный метод решения состоит в поиске нужной вершины, осуществляемом перемещением от очередной вершины к смежной. Трудные проблемы линейного программирования по существу связаны с решением задач очень высокого порядка п, которое приводит к разреженным матричным задачам. В основе трудности таких задач лежит комбинаторная сложность общего и-мерного многогранника. Если функция 1 либо какое-нибудь из ограничений нелинейно, то говорят о задаче нелинейного программирования.
Задачи линейного и нелинейного программирования выходят за рамки этой книги. Интересующийся читатель должен обратиться, например, к книгам Орчард-Хейс (1968) или Данциг а. оптимизация 196 (1963). Мы ограничимся обсуждением задач либо безусловных, либо относящихся к интервалу. Оптимизационные задачи часто возникают непосредственно в контексте поисков наилучшей конструкции какого-либо объекта.
Например, можно искать значения некоторых и параметров системы, которые минимизируют ее стоимость, выраженную как функция этих параметров. Иногда оптимизационные задачи возникают опосредованно как средство решения какнх-то других задач. Стандартный пример — сведение задачи решения системы и нелинейных уравнений 1,(х„..., х„) =О, ~, (х„..., х„) =-О, ..., 1„(х„..., х„) =О к минимизации функции д (х„..., х ) = ~ (1; (х„..., х„) ('. Очевидно, что точки минимума д с нулевыми значениями есть а точности решения системы. (Могут быть также посторонние ненулевые локальные минимумы.) Однако эту задачу обычно не решают общими алгоритмами минимизации, поскольку в данном случае можно извлечь особую выгоду из типа минимизируемой функции. Как и в гладком одномерном анализе, легче отыскать относительные или локальные минимумы функции, чем найти ее абсолютный или глобальный минимум во всей области.
И в саком деле, в настоящее время не существует практичных алгоритчов для вычисления глобального минимума для п)2 или 3. Даже чтобы найти приближенное значение глобального минимума в и-мерном единичном кубе, потребовалось бы вычислять функцию в точках густой решетки, помещенной в куб, при условии априорного знания о том, что функция достаточно гладкая, чтобы не иметь выбросов между точками решетки. Но густая решетка в и-мерном кубе содержит слишком много точек для того, чтобы ее можно было обрабатывать. Если, к примеру, и — !О, го беря ! О абсцисс на каждом измерении, получим всего 1О" точек.
Таким образом, на практике единственный способ найти глобальный минимум состоит в том, чтобы получить из самой задачи информацию о его местоположении, а затем искать локальный минимум. Поэтому мы сосредоточим свое внимание на нахождении локальных минимумов и максимумов. Методы вычисления минимумов тривиально переносятся на задачу максииизации (поскольку минимумы 1 есть максимумы для — 1), н иы будем говорить попеременно о той и другой задаче. ае ОднОмеРнАя Оптнмнзлция 8.1. Однемерная оптимизация Предположим, что ( — действительная функция, определенная на !О, 1!.
Предположим, далее, что имеется единственное значение х, такое, что )(х) — максимум !(х) на !О, 11, и что )(х) строго возрастает для х(х и строго убывает для х(х. Такая функция называется унимодальной: для ее графика имеются три возможные формы, показанные на рнс. 8.!. Заметим, что унимодальная функция не обязана быть гладкой или даже непрерывной. о л' о=х 1 о 1=Х Из предположений немедленно следует, что для любых точек интервала х„х„таких, что х, ( х, е х, справедливо )(х,)< ~Дх,).
Аналогично, если х(х„<х„то )'(х,) ("(хА). Обратно, если х,~х, и ~(х,)()(х,„), то А1(х(1, а если )(х,))((х,), то О~х~х,. (Конечно, если 7(х,)=)(х,), то мы получаем дополнительную информацию: х,(х "х„но нам не придется этим пользоваться.! Задача состоит в том, чтобы найти множество абсцисс х„х„... хю в которых вычисляется функция, такое, что оптимальное значение 7 лежит при некотором ! в интервале х;,( (л(х~~,.
Такой интервал называется интервалом неопределен- НОС~ПИ. Алгоритм выбора абсцисс х,(!.=1,..., /г) называется планом поиска. Если известно только то, что 7 унимодальна, то какова оптимальная стратегия для нахождения ху При заданном количестве вычислений функции оптимальным планом поиска будет тот, который приводит к наименьшему интервалу неопределенности.
В некоторык ситуациях, таких, как физический эксперимент или счет на параллельных процессорах, приходится одновременно вычислять функцию 7 во всех точках х;. Можно показать, что оптимальный план поиска выражается формулами (! + А) 1() +1))2! ( ~ ~+! 1 где ( р ) — целая часть числа у. При й вычислениях функции получается интервал неопределенности длины !+Е Й)2)т ) ' 8 Оптимиз»ция В этих формулах е выбирается из условия, чтобы Г(х)Ф~(х+е) для любой точки х Е [О, 11, находящейся от х на расстоянии, не меньшем е. Более подробное обсуждение методов одновременного поиска можно найти в книге Вильде (1964).
В остальной части этой главы мы будем считать, что значения функции вычисляются последовательно. Предположим, что разрешено последовательно вычислять функцию Ь раз, где Ь)! — заданное число. Как использовать эти вычисления так, чтобы заключить х в наименьший возможный интервал неопределенностиу Соответствующая теория была начата работами Кифера (Л. К!е[ег) в первой половине пятидесятых годов. Алгоритм оптимальной стратегии последовательно строит й тестовых точек, которые мы предпочитаем занумеровать в обратном порядке х», х» ь...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
