Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 20
Текст из файла (страница 20)
К счастью, для ответа на некоторые вопросы можно привлечь машину. Получающиеся адаптивные квадратурные подарограмзгы обсуждаются в следующих двух параграфах. з.4. Адаптивные квадратурные программы Адаптивная квадратуриая программа — это алгоритм численных квадратур, использующий одну или две основные квадратурные формулы и автоматически определяющий величины подынтервалов так, чтобы вычисленный результат удовлетворял предписанной точности. В разных частях интервала могут использоваться сетки различных размеров, сравнительно грубые там, где интегрируемая функция гладкая и меняется медленно, и сравнительно мелкие в областях, где интегрирование становится затруднительным. Таким образом, делается попытка получить результат с предписанной точностью за (по возможности) малое машинное время. Первая адаптивная программа, опубликованная Маккиманом (1962), была основана на формуле Симпсона.
Эта и ей подобные программы оказались очень успешными на практике. Очень полный анализ метода и некоторые предложения относительно модификаций были сделаны Линесом (1969а). Райсу (1975) н Малкольму и Симпсону (!975) принадлежат замечания относительно машинной реализации. В этом параграфе будут обсуждены общие принципы адаптивных программ. В следующем параграфе описывается конкретная такая программа. Пользователь подобной программы указывает конечный интервал (а, Ь), заготавливает подпрограмму, вычисляющую 7(х) для ') Н оригинале — <!е1еггео «рргоео!г 1о Ше 1ипн.— Прим.
л«я««. ь.ь ьдьптивныа квьдгьтгнньш пгогьлммы юв любого х из этого интервала, и выбирает допустимую точность а. Программа пытается вычислить величину 9, такую, что Программа может сделать вывод, что предписанная точность недостижима, получить наилучший возможный для нее результат и выдать оценку реально достигнутой точности.
При оценке эффективности квадратурных программ обычное предположение состоит в том, что большая часть стоимости счета приходится на вычисление подынтегральной функции ((х). Таким образом, если для интегрирования данной функции имеются две подпрограммы и обе дают ответы примерно одинаковой точности, то подпрограмма, требующая меньшего количества вычислений функции, рассматривается как более эффективная для данной конкретной задачи.
Всегда можно сконструировать подынтегральную функцию ((х), которая могла бы одурачить данную программу, приводя к совершенно неверному результату; однако для хороших адаптивных программ класс таких примеров был сужен, насколько это возможно без неоправданного усложнения логики или потери эффективности на разумных задачах. В процессе вычислений интервал (а, Ь) разбивается на подынтервалы (хо х„ь,).
В большинстве программ каждый подынтервал получается делением пополам подынтервала, полученного на более раннем этапе вычислений. Реальное число подынтервалов, так же как их расположение н длины, зависит от подынтегральной функции г(х) и требуемой точности е. При нумерации условливаются, что х,=а, и программа определяет и так, что х„„=Ь. В этом параграфе длина подынтервала будет обозначаться через й;=х,ь,— х,.
Типичная схема применяет к каждому подынтервалу две различные квадратурные формулы, Обозначим соответствующие два результата через Р; и ф. Например, схемы, основанные иа формуле Симпсона, используют основную формулу (два элементарных отрезка) Рг= — '~~(хь)+4~ х;+ — ')+((хь+йь)1 и составную формулу (четыре элементарных отрезка) Яь= —,' ~1(хь)+41(хь+ — "'1+21 (х;+ 2) +4~ (хь+ 4 )+~(хь+Ььь)1 ° в численное интеггиеовхнив ыо Выражения Р; и Я; являются приближениями к "г.~-г Iг=- ~ 1(х)г(х. х,.
Основная идея адаптивной квадратуры состоит в сравнении двух приближений Р; и 9; и получении при этом оценки их точности. Если точность приемлема, то одно из чисел принимается за значение интеграла по данному подынтервалу. Если же точность недостаточна, то подынтервал делится на две пли более частей и процесс повторяется для меньших подынтервалов. Сокращение общего количества вычислений функции обычно достигается тем, что две формулы, дающие Р; и Яо используют значения подынтегральной функции в некоторых общих точках. Например, в случае формулы Симпсона Я, требует пяти значений функции; три из них используются и в Р,. Следовательно, обработка нового подынтервала требует лишь двух новых значений ' функции. В остальной части этой главы будем считать, что 9; получается двукратным применением формулы для Р;, т. е.
применением ее к каждому полуинтервалу. Это общий прием, наиболее упрощающий анализ. Предположим еще, что формула для Р; дает точный результат, если интегрируемая функция есть полипом степени Р— 1, или, другими словами, если р-я производная ~чи(х) тождественно равна нулю. Раскладывая подынтегральную функцию в ряд Тейлора относительно середины подынтервала, можно показать, что для некоторой константы с 1; — Рг=сйл~'~'г' ~хг+ — '~1+.... Показатель 6; равен р+1, а не р, потому что длина подынтервала равна йо Из предположения о том, что Я, есть сумма двух Р, взятых по двум подынтервалам длины й,/2, следует: У.— Я,=с( — ) ~ ~г (х;+ — )+1" (х;+— Поскольку )пгФ (х, + — ') +)пг' (х, + — ') =21<Ф (х,.+ —,' ~) -~-..., то обе ошибки связаны соотношением 1; — Я;= —,((; — Р;)+...
= — (7; — Р;)+.... 2 1 Оно показывает, что деление подынтервала пополам уменьшает ошибку примерно в 2л раз. Разрешая относительно неизвест- Б 4 Адьптивные кеАДРАтуРные пРОГРАммы 111 ного 1г и переупорядочивая члены, получаем гл! ~е (Р! г'гг)+ 1 2Р— 1 Другими словами, ошибка более точного приближения Я! приблизительно в 2Р— 1 раз меньше разности между двумя приближениями, Основная операция типичной программы состоит в делении каждого подынтервала пополам до тех пор, пока не будет выполнено следующее неравенства: (Рг — Яг(«=„— где е — указанная пользователем граница допустимой точности, Если весь интервал [а, Ы можно покрыть и подынтервалами, для которых это справедливо, то программа выдаст результат Комбинируя полученные соотношения и игнорируя члены более высокого порядка, находим ! ь л 1 л г',г — ) 1 (х) г(х ~ = ~ ~ (Я! — 1г) ( ~ ~ Яг 11) что и требовалось.
Зтот анализ предполагает, непрерывность (глг(х) и пропорциональность ошибки величине Ьл 7ггг(х). Лаже если эти предположения не вполне выполняются, программа может тем не менее давать неплохой результат, находящийся в пределах желаемой точности, хотя локальное поведение процесса будет иным. Для простоты мы предположили также, что программа использует критерий абсолютной ошибки, т. е. (Д вЂ” ~~~(е. Во многих ситуациях предпочтительней тот или иной вид ограничения, наложенного на относительную ошибку, которая не зависит от масштабирующих множителей в 1.
Проверка прямого 5.5. ПОДПРОГРАММА ОПАХС8 Такое поведение весьма типично для программы ( НЗАХС8, так же как и для других адаптивных программ. Если бы величина интервалов, необходимая для достижения заданной точности Рик. 5Л. Поведение адаптивной нвадратурной программы. вблизи пиков, использовалась по всему интервалу интегрирования, то вычисления потребовали бы значительно больше времени. З.в. Подпрограмма ОЦАМСВ К 1976 г, было опубликовано около дюжины достаточно эффективных адаптивных квадратурных программ. Среди наиболее широко используемых программ — ЯК)А".нгК, написанная Джеймсом Линесом, и ЯМС7, авторы Дэвид Каханер и Рондэл Джонс. 5.
ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ В этом параграфе будет представлена еще одна адаптивная программа — !"!()АВ)С8. Она обьединяет основные идеи программ Я)(ЗАИК и О)х)С7, но не включает некоторые из их наиболее изощренных особенностей, такие, как контроль ошибки округления и выявление сннгулярностей некоторых типов. Мы полагаем, что программа Я))А)х)С8 достаточно проста для чтения н понимания и что тем не менее ее результаты для широкого круга задач вполне конкурентоспособны с результатами более сложных программ.
Пользователь программы Я()А)х)С8 должен задать подпрограмму-функцию ЛЗ)ч(Х) для подынтегральной функции ((х); нижний и верхний пределы интегрирования А =а и В=(з; и границы абсолютной и относительной ошибок АВВЕЙЙ и ЕЕ1 ЕЙЙ. Выходные параметры программы: ЙЕ8(Л Т =- приближение к интегралу, ЕЙЙЕ8Т =- оценка абсолютной ошибки в )тЕЯ)ЕТ! )т)ОГ())т(= — число требуемых вычислений функции, и ГЕАО =— =-индикатор надежности. Если значение ГВАЛТ равно нулю, то ЙЕЯ)) Т, по всей видимости, имеет требуемую точность. Если значение Г).АО не равно нулю, но мало, значение КЕЯ)) Т все еще может быть приемлемым.
Если же значение ГЕАО велико, то подынтегральная функция принадлежит к одному из типов, неприемлемых для программы. Название (;!()А!ьС8 произведено из слов Опас)га(цге, Адар6- уе, Р)етп)оп-Со(ез' 8-рапе! ". Формулы Ныатона — Котеса — это семейство квадратурных формул, получаемых интегрированием интерполяционных полиномов, построенных по равноудаленным узлам. Формулы прямоугольников, трапеций и Симпсона выводятся интегрированием полиномов соответственно нулевои, первой и второй степени н являются первыми тремя членами этого семейства.
В данном случае формула получается интегрированием полинома восьмой степени, но так же, как и в случае формул прямоугольников и Симпсона, приобретается дополнительная точность, так что формула дает точный результат для многочлеиов степени 9. В случае ннтегрирования по интервалу (О,!) формула дает ! а ) ( (х) с(х ж ~~~, ша( ( — ) . Приближенные значения весов гиа суть ') То есть квадратура, адаптивная, Ньютона — Котеса, 8 элеме»парных отрезков. Словосочетание «8-ране!» мы в дальнейшем переводим как «формула 3-го порядка», имея в виду степень интерполяниоиного полинома, по которому она построена (точность же этой формулы, как указано в тексте, равна 9).— Прим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
