ПРОГРАММИРОВАНИЕ, 2013, No 2, с. 15 20
КОМПЬЮТЕРНАЯ АЛГЕБРА
У л :
НЕОПРЕДЕЛЕННОЕ ИНТЕГРИРОВАНИЕ КАК ПЕРЕПИСЫВАНИЕ ТЕРМОВ: ИНТЕГРАЛЫ, СОДЕРЖАЩИЕ
ТАНГЕНС *
© 2013 г. X. Ху, И. Хоу, А.Д. Рич и Д.Д. Джеффри,
Факультет прикладной математики, Вестерн университет N6A 5В7Канада, Онтарио, Лондон, ул. Ричмонд, д. 1151 E-mails: junruihu@gmail.com, yhou26@uwo.ca, Albcrt_Rich@msn.com, djcjfrcy@uwo.ca
Поступила в редакцию 02.07.2012
Рассказывается о проекте разработки системы правил переписывания термов для неопределенного интегрирования. Описывается модуль для подынтегральных выражений, содержащих тангенс.
1. ВВЕДЕНИЕ
Используемые в системах компьютерной алгебры стили программирования часто рассматриваются как основанные либо на переписывании термов, либо на вычислении выражений.
Например, Матнематюа часто рассматривается как система, основанная на переписывании термов fl], a Maple — гораздо реже. Различие, конечно же, в соотношении этих стилей, так как во всех доступных системах заметны элементы их обоих. Двойственность отчетливо проявляется в неопределенном интегрировании. Наиболее известные алгоритмы основаны на вычислениях. Например, алгоритмы Риша [7] и Ротштейна-Трагера-Лазара-Риобо [8, 9, 5] — вычислительные. Но эти алгоритмы не универсальны, и для многих интегралов приходится (или оказывается более предпочтительным) применять системы переписывающих правил. Некоторые из таких ситуаций мы обсудим ниже.
Несмотря на высказанные сомнения [2], современные методы переписывающих правил становятся все более алгоритмичными и детерминированными, и мы отдаем предпочтение этим методам для нашей схемы интегрирования. Мы учли успех и популярность программ, которые могут показывать пошаговые вычисления. Такие программы называются 'показать шаг' или 'один шаг'. Они предлагаются, например,
*Перевод с английского Е.С. Шемяковой.
в WolpramAlpha, Derive и в ряде учебных программ для изучения основ математического анализа.
Предложенная в [6] схема основана на системе правил переписывания термов и состоит из правил преобразований, хранящихся в открытом для доступа репозитории вместе с утилитами, которые можно использовать в различных системах компьютерной алгебры. Этот репозито-рий представляет собой не таблицу интегралов, а небольшое множество правил. Корректность преобразований — не единственная цель нашего проекта. Качество интегральных выражений оценивается с помощью нескольких критериев, которые позволяют решить, включать ли правило интегрирования в репозиторий. Предположим, что подынтегральное выражение f (x) имеет первообразную F (x). Тест для включения основан на следующих критериях, которые мы обсудим подробнее в следующем разделе.
• Корректность: требуем, чтобы выполнялось F' (x) = f (x).
•
для интеграла. У нас прагматический подход и наша цель — получить наиболее короткое по длине выражение.
•
выражение было непрерывным в максимально возможной области [4].
выбора математически красивых формул.
• Использование: правила должны быть подходящими для стиля 'показать шаг' (см. раздел 2.5).
•
быть, насколько это возможно, прямым, а множество правил — компактным.
Ниже наш репозиторий будет обрисован подробнее.
2. ОБСУЖДЕНИЕ КРИТЕРИЯ ВЫБОРА ПРАВИЛ
Следующий пример позволит обсудить несколько аспектов цели нашего проекта. Рассмотрим пять возможных выражений для одного и того же интеграла:
У V—2 tan x dx = — 2 ln (2 — 2 tan x — 2V—2 tan x)
— arctan (yj—2 tan x — 1) + 2 ln (2 — 2 tan x + 2V—2 tan x)
— arctan (V—2 tan x + 1) ,
(1)
У V—2 tan x dx =
л/—Ta n[x] 2^Ta n[x]
+2ArcTan
(2)
2
1 — V2^Tan[x]
1 + V2^Tan[x]
+ Log [1 — V2^Tan[x] + Tan[x] —Log 1 + V2^Tan[x] + Tan[x] = lncos x + ln(1 + V—2 tan x — tan x)
(3)
+ arctan
1 + tan x
= arctan
л/—2 tan x V—2 tan x
(4)
= arctan
1 + tan x 1 + tan x
+ arctanh
V—2 tan x
л/—2 tan x
+ arctanh
1 — tan x
(5)
1 tan x
л/—2 tan x
(6)
Выражение (1) получено в Марье 16; выражение (3) получено в Матнематюа 8; выражения (4) - (6) получены в рамках нашего подхода. Рассмотрим эти выражения с точки зрения сформулированных критериев.
2.1. Корректность
Обозначим через / и Р подынтегральное выражение и первообразную. Проверка равенства р' = / требует дифференцирования. В компьютерной алгебре существуют давние разногласия по поводу выбора из двух возможностей
dx
ln x , ,
x I ln |x| , вещественный случай.
(7)
В репозитории все правила преобразований верны для комплексного случая. В нашем примере подынтегральная функция становится чисто мнимой на интервалах (пп, пп + п/2), где п € Ъ.
Отметим, что проверка равенства Р = /, основанная на использовании какой-то системы компьютерной алгебры, может быть нетривиальной задачей. Например, Марье не может полностью проверить (4).
2.2. Простота
Последние три выражения в нашем примере, очевидно, короче и проще, чем первые два. Постоянная проблема систем компьютерной алгебры — рост размера выражений. Системы компьютерной алгебры очень часто не дают максимального упрощения выражений, которые содержат интегралы. Во-первых, потому, что самая короткая форма может отличаться на константу от данного выражения, и таким образом только алгебраические упрощения не приведут к цели. Во-вторых, точки ветвления могут сделать данное выражение алгебраически отличным от его короткой формы. Другими словами, два выражения могут различаться на кусочно-постоянное выражение.
Таким образом, интегрирующая система должна искать наиболее простые формулы, не рассчитывая на успех алгебраического упрощения. Это, в частности, видно по результатам применения алгоритма интегрирования Риша, которые получаются без учета ветвления.
2.3. Непрерывность
Подынтегральное выражение V—2 tan x имеет особенность при x = nn + п/2 и непрерывно в
НЕОПРЕДЕЛЕННОЕ ИНТЕГРИРОВАНИЕ КАК ПЕРЕПИСЫВАНИЕ ТЕРМОВ
17
других точках. При x = nn функция меняется от действительной к мнимой, но она непрерывна в этих точках. Таким образом, выражение для ее интеграла должно быть непрерывным, за исключением, возможно, точек x = (n + 1/2)п. Мы видим, что выражение (5) имеет разрывы в tan x = ±1. Поэтому другие выражения более предпочтительны. Объединив непрерывность с простотой, мы можем сократить диапазон выбора предпочтительного выражения до (6), (4). Дополнительно отметим, что подынтегральное выражение интегрируемо в особых точках, и можно было бы потребовать, чтобы интегральное выражение было бы там непрерывно. Ни одно из выражений не имеет определенного значения при x = nn + п/2, потому определенные интегралы с пределами интегрирования в этих точках должны быть получены с использованием односторонних пределов.
Далее отметим, что условия непрерывности и простоты могут конфликтовать. Рассмотрим пример использования алгоритма Лазара-Риобу [5]:
мощью Maple 16:
x2 + 2 x
dx = arctan ■
x4 - 3x2 + 4 2 - x2 '
= arctan ^2x + + arctan ^2x — V7^j
(8)
J vsianx dx =
Vtan x cos x arccos (cos x — sin x)
v¡
cos x sin x
(9)
Выражение с разрывами короче, и будет казаться более простым большинству пользователей. При росте степеней полиномов разница между длинами выражений возрастает.
2.4. Эстетика
Красота — важнейший критерий. Уродству нет места в математике. (Г.Х. Хар-ди [3])
Сравнивая (4) и (6), мы видим, что (6) содержит две родственные функции: агсйап и агс^апЬ. Хотя агсйапЬ можно выразить через логарифмы, выражение (6) с его симметриями математически красивее, чем остальные выражения.
Аналогичный принцип касается связи между формами подынтегрального выражения и интеграла. Следующий интеграл был получен с по-
— ln ^cos x + V^Vtan x cos x + sin xj .
(10)
В отличие от (1), полученного тоже с помощью Maple, эта формула содержит целый набор функций, не входящих в подынтегральное выражение. Кроме того, связывающая проблемы (1) и (10) очевидная симметрия x ^ —x не видна в ответах.
Мы предпочитаем в таких случаях формулу, которая функционально ближе к подынтегральному выражению.
2.5. Использование
Способ записи правил отражается на каждом шаге при пошаговом выполнении. Некоторые системы используют многочисленные подстановки в процессе решения. Это отражает то, как человек решал бы эту задачу, но такой подход труден для восприятия, так как пользователю придется следить за всеми заменами. Простым примером является интеграл вида J f (ax + b) dx. Хотя человек может сразу написать y = ax + b, а затем работать с y, мы предпочитаем работать с более длинной формой и освободить пользователей от необходимости следить за заменами.
3. ФОРМА ПРАВИЛ
Каждая запись в репозитории состоит из трех функциональных частей, в совокупности они определяют правило:
1. Преобразование. Отображает интеграл в выражение, которое содержит как термы, свободные от интегралов, так и новые (более простые) интегралы.
2. Условия достоверности. (Так как интегралы в части 1 обычно содержат параметры, эти условия обеспечивают корректность преобразований.)
3. Условия упрощения. Подтверждают, что преобразование является желательным, и что любой новый интеграл или интегралы после дальнейших преобразований приведут к решению исходной проблемы.
Записи могут содержать и не имеющие функциональной роли сведения, такие, как ссылки на литературу.
Одна из задач нашего проекта — добиться того, чтобы условия, определяющие правила, взаимно исключали друг друга. Это означает, что если заданы все параметры для любого подынтегрального выражения, то только один набор условий оказывается выполненным, и, таким образом, только одно правило может быть применено.
4. ВЫРАЖЕНИЯ, СОДЕРЖАЩИЕ ТАНГЕНС
Наш новый модуль работает с выражениями вида
1апт(с + ^ж)(а + Ь 1ап(с + ^ж))га
* (А + В 1ап(с + ^ж) + С 1ап2(с + ^ж))
где а, Ь, с, А, В, С € С и т, п € М — произвольные параметры. Это выражение не всегда интегрируемо. Цель состоит в том, чтобы найти все случаи, в которых оно интегрируемо. Не исключается, что а и в останутся символьными.
Стоит прокомментировать этот выбор подынтегрального выражения, особенно наличие в нем последнего множителя. Приложение в конце статьи содержит набор рекурренций, которые позволяют упрощать подынтегра
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.