2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Алгоритм Риша
Сообщение10.09.2019, 10:30 
Пытаюсь разобраться, на что способен алгоритм Риша поиска первообразной произвольной элементарной функции за конечное число итераций, не вникая в саму суть алгоритма.
Правильно ли я понимаю, что алгоритм позволяет работать только с не параметрически заданными элементарными функциями? И если так, то придуман ли уже алгоритм, позволяющий за конечное число итераций для любой параметрически заданной элементарной функции определить имеется ли элементарная первообразная от тех же параметров для всех (кроме быть может определённого набора случаев) комбинаций значений этих параметров и если имеется, то найти это решение?
(Пока что не очень плаваю в этой теме, так что не судите строго за возможно недостаточно ясную постановку вопроса)

 
 
 
 Re: Алгоритм Риша
Сообщение10.09.2019, 10:43 
Аватара пользователя
Paul Ivanov в сообщении #1414345 писал(а):
придуман ли уже алгоритм, позволяющий за конечное число итераций для любой параметрически заданной элементарной функции определить имеется ли элементарная первообразная от тех же параметров для всех (кроме быть может определённого набора случаев) комбинаций значений этих параметров и если имеется, то найти это решение?

Приведите, пожалуйста, определение "параметрически заданной элементарной функции", чтобы появился предмет разговора.

 
 
 
 Re: Алгоритм Риша
Сообщение11.09.2019, 15:49 
функция, получающаяся с помощью композиции и алгебраических операций из основных элементарных функций и параметров (где параметр - это не конкретное фиксированное число, а любое комплексное число, обозначенное буквой, соответственно и первообразная для такой функции ищется, как функция от главной переменной и этих параметров)

 
 
 
 Re: Алгоритм Риша
Сообщение11.09.2019, 16:28 
Аватара пользователя
Paul Ivanov в сообщении #1414564 писал(а):
первообразная для такой функции ищется, как функция от главной переменной и этих параметров)

Выходит, речь идет о первообразной для функции нескольких переменных, но часть переменных стыдливо названа "параметрами". Как определяется такая первообразная?

 
 
 
 Re: Алгоритм Риша
Сообщение11.09.2019, 17:40 
нет, переменными они не называются, так как интегрирование идёт только по одной переменной x. Все остальные являются параметрами.
Приведу пример: можно искать первообразную от функции $\ln(2e^x+\pi x^2)$ и если она существует, то выражается через $x$ и числа, а можно искать первообразную параметрически заданной функции $\ln(ae^x+\bx^2)$, и она будет выражаться, через $x$, $a$, $b$, где a и b это константы обозначенные через буквы, то есть параметры.

 
 
 
 Re: Алгоритм Риша
Сообщение11.09.2019, 22:56 
Аватара пользователя
Точный ответ на ваш вопрос может дать только узкий специалист, занимающийся реализациями символьного интегрирования. Так как никто не отвечает, то попробую ответить, руководствуясь общими соображениями.
Ответ будет сильно описательным, чтобы он не превратился в научно-популярный обзор.
1. В литературе мне встречались только те подходы к символьному интегрированию, которые реализуют ту или иную вариацию алгоритма Риша.
2. Алгоритм Риша основан на "угадывании" общего вида искомой первообразной, после чего используется метод неопределенных коэффициентов. Предварительно выбираются основное поле элементарных функций спец. вида и основное поле коэффициентов-поле рац. чисел. Затем, исходя из вида коэффициентов и "состава" интегрируемой функции строятся конечные расширения этих полей так, чтобы с помощью элементов этих расширений можно было бы записать первообразную с точностью до неопределенных множителей и коэффициентов.
3. В основе построения расширения поля коэффициентов лежит алгебраическая природа констант, использованных в записи интегрируемой функции. Но нет алгоритма, позволяющего определить по записи действительного числа, алгебраично оно, или трансцендентно. В этом месте (но и не только здесь) алгоритм Риша "ломается", и наступает время эвристики.
Вывод: вряд ли возможно существенное развитие алгоритма, который в определенном месте использует эвристику даже в простой ситуации интегрируемой функции с числовыми коэффициентами.
Как-то так...

 
 
 
 Re: Алгоритм Риша
Сообщение11.09.2019, 23:48 
Тогда три вопроса:
1. Если имеет место эвристика, то правильно ли я понимаю, что для элементарных функций с определённо алгебраическими константами можно доказать, что алгоритм Риша работает?
2. Правильно ли я понимаю, что если константы не алгебраические, то алгоритм не работает? Или алгоритм работает, но с определённой степенью точности? Или нельзя доказать, что он справится с любым подобным примером? Если верно последнее, то существует ли пример с трансцендентными константами, когда алгоритм Риша не работает?
3. В пункте 1. вы сказали, что вам встречались только "те подходы к символьному интегрированию, которые реализуют ту или иную вариацию алгоритма Риша". Правильно ли я понимаю, что строго доказанного алгоритма символьного интегрирования пока не существует? А есть ли для этих подходов символьного интегрирования примеры, когда они неправильно срабатывали?
Прошу прощения за такое большое кол-во вопросов, просто из вашего сообщения я не до конца понял, на что способен этот алгоритм и его вариации.

 
 
 
 Re: Алгоритм Риша
Сообщение12.09.2019, 00:44 
Аватара пользователя
Алгоритм Риша использует метод неопределенных коэффициентов, вследствие чего упирается в проблему алгоритмического определения тождественного равенства нулю выражения (формулы) с элементарными функциями, про которую в некоторых случаях доказано, что она алгоритмически неразрешима. Есть гипотезы, что в важных частных случаях алгоритмическая разрешимость есть, но это пока, видимо, так и не доказано и сейчас представляет основное теоретическое препятствие в обосновании корректности алгоритма.
Тем не менее, он тем или иным способом реализован в пакетах символьных вычислений. В литературе и в сети есть данные о сравнительной эффективности таких реализаций. Но я оставляю вам возможность поискать эти данные.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group