logo标签列表

程序能用来简化代数表达式吗？

algorithmmathexpressionalgebrasymbolic-math
6
我们知道1+2+...+n等于n(n+1)/2。但是如果我们不提前知道这个结果，我们能否通过编程得到相同的结果呢？关于为什么我有这样的问题，请考虑一个更复杂的情况：X1+X2+...+Xk=n，其中Xi是整数且>=0。那么X1^2+...Xk^2的期望是多少呢？仅仅凭一眼之力就无法得出结论，因此我们需要将其输入程序，以便在计算期望的(冗长)数学表示式后简化代数运算。
3
你的修改使得它变得相当不清楚了... - starblue
@starblue，这是关于开发一个能够发现显式公式的程序。 - Je Rog
3
我认为程序无法找到任意求和式的通项公式。首先，并非所有求和式都有仅涉及基本函数的通项公式。其次，算法上能够简化任意表达式似乎与能够算法地确定图灵机是否在某个输入下停机非常接近... 我会思考这是否正确，以及如果是，则我是否能证明它。 - Patrick87
1
@Patrick：确定一个依赖于一个变量的任意算术表达式是否为零等价于停机问题。 - Alexandre C.
2
@Patrick：对于积分，存在一种算法（Risch算法），当且仅当原函数的闭式反导数（以初等函数表示）存在时，该算法会终止。不幸的是，它需要判断两个表达式是否相等，这是不可判定的。在无限级数中的对应算法是Karr算法。 - Alexandre C.
根据理查德森定理，看起来是不可判定的。https://en.wikipedia.org/wiki/Richardson%27s_theorem - yters
3个回答
6

也许你在想计算机代数系统（CAS）？ WolframAlpha 是一个免费在线的CAS，它在后台使用了非常强大的Mathematica系统。在这里，你可以看到它计算/简化你的表达式：WolframAlpha。

你的例子只是平方和，它有一个相当简单的显式公式：n(n+1)(2n+1)/6。更一般地，你可以使用Faulhaber公式来计算n^p的和。

n(n+1)(2n+1)/6 是用于计算 1^2+2^2+...n^2 的公式，我的例子比这个复杂得多。 - Je Rog
除非您定义序列X_k，否则您将无法获得显式公式。通常情况下，对于这种求和，很难获得简单的闭合形式表达式。只有像这样的简单求和才能轻松简化。 - tskuzzy
你能谈谈WolframAlpha的算法吗？它只是一系列硬编码的数学公式吗？ - Je Rog
Mathematica已经开发多年。它支持的算法众多，足以填满书籍（实际上可能已经填满了）。你应该使用现成的解决方案或限制你的问题。 - Jens Schauder
1
不，它实际上在后台进行符号数学运算。CAS是计算机科学中非常高级的主题，可能需要多年的研究才能构建出非平凡的东西。为了让你有一个大致的概念，Mathematica花费了22年时间才达到现在的水平。我认为这不是可以在SO上充分讨论的东西。 - tskuzzy
显示剩余2条评论
4

好的，首先是关于数学部分的一些建议，然后是关于软件开发的建议。

有一个由Marko Petkov·sek、Herbert S. Wilf和Doron Zeilberger编写的电子书"A=B"，它处理解决（或显示没有解决方案）比多项式更困难的求和问题。Ian Wanless的书评值得快速阅读。这本电子书可以免费下载，但精装版可以购买，例如从Amazon购买。

2004年AMS论文《C-有限序列的封闭形式求和》由Greene和Wilf撰写，也可在线获取。

一般来说，您需要一些基本的计算机代数系统软件来实现这些算法，而且似乎目标是自己开发这样的软件。我建议学习一些开源的计算机代数软件包，比如Maxima或Axiom，以了解所涉及的范围。当然，可能只需要这些相对成熟和高端的软件包实现的一小部分就可以满足一个狭窄的应用，但是鉴于当前问题的表述，我不认为我可以指引您走更具针对性的道路。
如果您的项目范围包括表达式的“期望”，那么除了纯代数操作之外，还有许多复杂的问题。人们肯定需要能够指定概率密度函数来支持期望值，并且可能需要一些积分软件（尽管限制参数化分布的选择可能会导致简化问题，即查找这些分布的矩）。我认为这是一个特别好的应用程序，因为随机变量的看似简单的表达式（求和、最大/最小值）可能会导致令人噩梦般的情况考虑，非常适合计算机的耐心。
1
OP似乎处理整数值随机变量，对于这种情况积分会变成潜在的无限级数。这些肯定比积分要棘手，但如果它们是有限的，那么你指向的材料可能有效（"超几何级数的线性组合"实际上非常广泛）。 - Alexandre C.
1
@Alexandre C.：OP提到限制为整数是个好观点。我正在思考您对Patrick87的评论，“一个依赖于一个变量的任意算术表达式”可以表示一个不可判定问题。据我所知，这个问题的丢番图方程版本需要多于一个变量，但也许我错过了最近的发展。 - hardmath
我忘了提到这个变量是实数，并且你还需要一些常用的函数。这是根据里斯定理编写的（该定理解决了原函数问题，前提是你能证明这些表达式为零）。 - Alexandre C.
1

编辑，由于您最近对帖子进行的澄清。

除非您有整个博士团队和数年时间来解决问题，否则手工制作的解决方案无法胜任。我能给出的最好建议是购买Mathematica（或其他）许可证，并将其与您的程序接口。

如果您是Lisp程序员，使用Maxima是另一个可能的（免费的）解决方案。

如果您想了解求和算法现状的背景，可以从this paper开始阅读。

X1+X2+...+Xk=n，其中Xi是整数且>=0。
X1^2+...Xk^2的期望是多少？
这种问题让很多人都在纸上思考如何解决。
我们以k=2为例。那么X_1 + X_2 = n，得到X_2 = n - X_1。
因此要计算的期望是E = X_1^2 + (n - X_1)^2 = 2 X_1^2 -2n X_1 + n^2。
这可以表示为：
E = sum(p_k * (2 * k^2 - 2 * n * k + n^2), k = 0..infinity)

其中p_k = Prob(X_1 = k)。这种依赖于p_k的求和通常非常难以计算。我认为这个问题甚至比计算封闭形式的积分更困难（对于这种情况，没有软件完全实现可用但不可判定的Risch算法）。

为了让自己信服，可以取p_k = 1 / (log(k) * k^4)。

找到一个公式（或公式生成器）至少是一个非常困难的研究问题。

“K”不是无穷大，而是一个固定的常数。+1，因为这是唯一一个涉及到一些细节的答案，其他人都在谈论符号代数的历史/故事，而我并不是在问这个。 - Je Rog
@Je Rog：然后有限求和算法可以在这本书中解释。尽管如此，你最好不要亲自实现它（除非你碰巧有很多空闲时间）。 - Alexandre C.
我不想自己实现它，但是我想要理解它是如何被实现的，而不仅仅是听故事或历史。 - Je Rog
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接