Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет ringill ([info]ringill)
@ 2008-01-15 12:09:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
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.


(Добавить комментарий)


[info]gaz_v_pol@lj
2008-03-23 09:21 (ссылка)
Тема весьма интересная, спасибо, [info]ringill@lj! Как водится, чем более содержательный текст, тем меньше у него комментариев ;-).

По сути вопроса: мне ситуация кажется не такой безнадежной. Посмотрим внимательней, что именно доказал Ричардсон:

Если есть функция f(x), получающаюяся с помощью сложения, умножения и композиции из синуса, экспоненты и модуля, а коэффициенты f(x) используют рациональные числа, Pi и ln(2), то задача проверки утверждения "f(x) тождественно равна нулю" алгоритмически неразрешима.

Прочитайте утверждение еще раз - Вам ничего слух не режет? Ему нужна функция модуль. Судя по статье (см. ниже), модуль существенен - Ричардсон доказывает алгоритмическую неразрешимость задачи определения "верно ли, что всегда f(x)>0", а потом модулем неравенство превращает в равенство.

При интегрировании модуль не нужен. Алгоритм Риша имеет дело с неупорядоченным полем, а в доказательстве Ричардсона поле принципиально упорядоченнное. Это дает надежду, что для более узкого класса функций (без модуля) алгоритм проверки равенства все-таки существует. Сам Ричардсон тоже надеется, см. 1 (http://portal.acm.org/citation.cfm?id=190429) и 2 (http://portal.acm.org/citation.cfm?id=29205.29217).

И последнее: позвольте рекомендовать Вам писать такие содержательные сообщения не только в свой ЖЖ, но и в группу [info]ru_math@lj. Там хорошо ;-).

Image

(Ответить) (Ветвь дискуссии)


[info]ringill@lj
2008-03-23 10:10 (ссылка)
Спасибо, комментарий не мене содержательный. Буду тоже теперь надеяться, по примеру Ричардсона.

А ru_math я не читаю, потому что не понимаю там половины, так чего я буду там постить.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]gaz_v_pol@lj
2008-03-23 10:20 (ссылка)
Ну, там, наверное, каждый не понимает половину (я уж точно), но если помещать сообщения, то часто люди откликаются, проверено.

(Ответить) (Уровень выше)

Аффтар, пеши исчо!! Пость в разные группы!
[info]v_v_bondarenko@lj
2008-03-30 09:59 (ссылка)
"И последнее: позвольте рекомендовать Вам писать такие содержательные сообщения не только в свой ЖЖ, но и в группу ru_math."

Аффтар жжот! :)

Голосую "за" двумя руками, двумя ногами... ;-)

Мне очень понравилось, говорю от души!

(Ответить) (Уровень выше)

Интеграл от x/sqrt(x^4 + 10*x^2 — 96*x — 71)
[info]v_v_bondarenko@lj
2008-03-30 09:54 (ссылка)
"Интеграл функции x/sqrt(x^4 + 10*x^2 - 96*x - 71)
не может найти ни Mathematica 6, ни Maple 11"

Maple 11 вычисляет этот интеграл. Ответ занимает 4 K.


Cheers,

Vladimir Bondarenko

http://www.cybertester.com

---------------------------------------------------------------

2*(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4))*((RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2))*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)))^(1/2)*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2))^2*(-(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 3))/(-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 3)+RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)))^(1/2)*((RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4))/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)))^(1/2)/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2))/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/((x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2))*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 3))*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)))^(1/2)*(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)*EllipticF(((RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2))*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)))^(1/2),((RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 3))*(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4))/(-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 3)+RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)))^(1/2))+(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2))*EllipticPi(((RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2))*(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(x-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)))^(1/2),(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)),((RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 3))*(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4))/(-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 3)+RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 1))/(RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 2)-RootOf(_Z^4+10*_Z^2-96*_Z-71,index = 4)))^(1/2)))

(Ответить) (Ветвь дискуссии)

Re: Интеграл от x/sqrt(x^4 + 10*x^2 — 96*x — 71)
[info]ringill@lj
2008-03-30 10:00 (ссылка)
Ответ занимает 4 K.

О том и речь (сходите по ссылке).
Все эти EllipticF и EllipticPi не являются элементарными функциями,
в то время как ответ является элементарной функцией.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Интеграл от x/sqrt(x^4 + 10*x^2 — 96*x — 71)
[info]v_v_bondarenko@lj
2008-03-30 10:45 (ссылка)
О боже.... нельзя столько работать... докатился я до ручки сегодня.... Вот цитата про меня :)

"Знаете, - сказал Остап, - вам не надо было подписывать так называемой сухаревской конвенции. Это умственное упражнение, как видно, сильно вас истощило."

Еще сообщу, что Maple 11.02 при вычислении интеграла

int(z/sqrt(z^4+10*z^2-96*z-71), z= 0..1);

дает формально правильный ответ размером 3 мегабайта (!!)
что, конечно же является багом...

тогда как вот он, весь ответ

-I*arctan((7810781*sqrt(71)-5038848*sqrt(39))/92741665)/8

:)

(Ответить) (Уровень выше)