Математика программирования: как расширить функцию

Question

Допустим, у меня есть математическая функция, которая определяется рекурсивно. Вот так:

T(1)(x) = 1
T(n)(x) = 2x*T(n-1)(x)-1

Итак:

T(1)(x) = 1
T(2)(x) = 2x*1-1 = 2x-1
T(3)(x) = 2x*(2x-1)-1 = 4x^2 - 2x - 1
/* and so on... */

В принципе, я знаю, как написать программу, которая будет считать T(15)(x), если дано x. Это не проблема. Однако меня интересует, как написать программу, которая даст мне многочлен для типа T (10) (x) (который выглядит примерно так: 16x^4 + 3x^3 ...).

В двух словах: как я могу рекурсивно считать математическое выражение, но используя x в качестве переменной (не задано).

Любая помощь будет принята с благодарностью,

Пол

Answer 1

Основываясь на комментариях, я считаю, что есть четыре варианта в порядке сложности.

Во-первых, вы можете просто реализовать явную формулу для данного искомого многочлена, если он существует. В случае полиномов Чебышева, явная формула (3 ^rd сумма сверху), соответствующая вашим потребностям, существует.

Если, однако, вы ищете что-то более общее, то есть более чем один тип полинома, вы можете создать явный список полиномов с точностью до некоторого абсурдного порядка и выполнить замену строки, используя предоставленное пользователем имя переменной. В большинстве систем это не займет много памяти.

В-третьих, если вы хотите остаться общим и все еще рекурсивно производить полиномы, вы можете использовать систему компьютерной алгебры, такую ​​как Mathematica. Например, вы можете получить доступ к Mathematica через MathLink , или использовать экземпляр webMathematica , или даже очистить вывод из WolframAlpha . Хотя, я думаю, вы столкнетесь с проблемами авторского права с последним.

Наконец, самым сложным и наиболее общим будет создание абстрактного синтаксического дерева . Если вы можете использовать c ++, я бы посмотрел на boost.proto , который по сути делает это для вас. Но если вы создадите его самостоятельно, у вас будет три типа бинарных операций: add, multiply и power и два типа листовых узлов: coefficient и variable. Теперь, чтобы втиснуть дерево в форму, в которой вы можете его использовать, вам нужно пройтись по дереву и применить правила преобразования: заменить поддерево и поменять местами родительский и дочерний. Замена заменит дерево, применяя стандартные математические правила, такие как 2 + 2 становится 4, а x * x становится x ² . Но настоящая работа заключалась бы в обмене родительским и дочерним узлами, поскольку это использовалось бы для применения закона распределения (mult -> add getting add -> mult) и предоставления возможностей для использования замены.

Первые два варианта, безусловно, самые простые, и я бы выбрал первый, если он доступен. Тем не менее, мне было бы гораздо интереснее реализовать интерфейс MathLink или дерево синтаксиса.

Редактировать : чтобы уточнить, что я имею в виду под взаимозаменяемостью родителя с его ребенком, рассмотрим случай n = 2.

, который влияет на 4 узла: «Плюс», «Времена» и коэффициент 1. Но легко увидеть, что это уменьшит общее количество узлов, исключив второй «Времена».

Answer 2

Я думаю, что ваш тег Mathematica может быть неправильным, но в любом случае.Mathematica имеет встроенную функцию RSolve, чтобы справиться с этим:

   RSolve[{a[n] == 2  x a[n - 1] - 1, a[1] == 1}, a[n], n]  

Результат:

   a[n] = (x + 2^n (-1 + x) x^n)/(x (-1 + 2 x))    

Как ожидается

   a[3] = -1 - 2 x + 4 x^2

HTH