ringill's Journal
 
[Most Recent Entries] [Calendar View] [Friends View]

Tuesday, January 15th, 2008

    Time Event
    12:09p
    Symbolic integration
    Искать первообразную труднее, чем производную, это всем известно. Но насколько сложно для компьютера взять неопределённый интеграл (или определить, что его нет)?

    В XIX в. известный математик Жозеф Лиувилль вывел общую формулу интегрируемых функций. Однако, алгоритма приведения произвольной функции к этой формуле известно не было; в 1916 г. Г. Х. Харди предположил, что его и не может быть. Он ошибался: алгоритм придумал Роберт Риш в 1968 году (Харди к тому времени 20 лет как не было в живых).

    Алгоритм Риша вычисляет интеграл элементарной функции через элементарные функции или определяет, что это невозможно. К элементарным функциям относятся экспонента, логарифм, алгебраические функции и композиции элементарных функций. Речь идёт о пространстве комплексных чисел, т.е. все тригонометрические функции также элементарны.

    Прекрасно, но забывать навсегда о символьном интегрировании рано. Отрезвляющая критика машинных методов звучала в Usenet со стороны Мануэля Бронштейна и Ричарда Фейтмана.
    Бронштейн был одним из ведущих разработчиков Axiom, до своей смерти в 2005 году, вслед за основателем Axiom Дженксом.
    Фейтман — один из ведущих разработчиков Macsyma и позже Maxima.

    Они сообщали, что:
    1. Алгоритм Риша весьма непросто запрограммировать полностью, и во всех системах компьютерной алгебры (CAS) он представлен лишь частично. Наиболее полная имплементация находится в Axiom; написал её Бронштейн в паре с Барри Трагером.
    2. Алгоритм Риша не является алгоритмом в строгом смысле этого слова; он опирается на эвристику, по которой можно определить, является ли элементарное выражение константой (типа arctan(x)+arctan(1/x)). Эвристику — потому что алгоритма для этой задачи (Constant Problem) не может существовать в принципе, а значит и алгоритма Риша как такового нет.

    Примеры, показывающие несостоятельность процедур символьного интегрирования в современных математических пакетах, есть. Интеграл функции

    x/sqrt(x^4 + 10*x^2 — 96*x — 71)

    не может найти ни Mathematica 6, ни Maple 11, ни Matlab R2007a, ни Maxima. Находит только Axiom. Интеграл функции

    exp(arcsin(x))

    находят только Mathematica и Axiom.

    << Previous Day 2008/01/15
    [Calendar]
    Next Day >>

About LJ.Rossia.org