4

背景

我需要在 Fortran90/95 中使用Horner 方案求解多个变量中的多项式。这样做的主要原因是在使用霍纳方案评估多项式时提高了效率和准确性。

我目前有一个实现单变量/单变量多项式的霍纳方案。然而，使用霍纳的方案开发一个函数来评估多元多项式被证明超出了我的范围。

一个示例二元多项式是： 12x^2y^2+8x^2y+6xy^2+4xy+2x+2y 将分解为 x(x(y(12y+8))+y(6y+4)+2 )+2y，然后评估 x 和 y 的特定值。

研究

我做了研究，发现了一些论文，例如：
staff.ustc.edu.cn/~xinmao/ISSAC05/pages/bulletins/articles/147/hornercorrected.pdf
citeseerx.ist.psu.edu/viewdoc/download ?doi=10.1.1.40.8637&rep=rep1&type=pdf
www.is.titech.ac.jp/~kojima/articles/B-433.pdf

问题

但是，我不是数学家或计算机科学家，所以我在用于传达算法和想法的数学方面遇到了麻烦。

据我所知，基本策略是将多元多项式转换为单独的单变量多项式并以这种方式计算。

谁能帮我？如果有人可以帮助我将算法转换为我自己可以在 Fortran 中实现的伪代码，我将不胜感激。

4

2 回答 2

6

对于两个变量，可以将多项式系数存储在 rank=2 矩阵K(n+1,n+1)中，其中 n 是多项式的阶。然后观察以下模式（在伪代码中）

p(x,y) =     (K(1,1)+y*(K(1,2)+y*(K(1,3)+...y*K(1,n+1))) +
           x*(K(2,1)+y*(K(2,2)+y*(K(2,3)+...y*K(2,n+1))) +
         x^2*(K(3,1)+y*(K(3,2)+y*(K(3,3)+...y*K(3,n+1))) +
         ...
         x^n*(K(n+1,1)+y*(K(n+1,2)+y*(K(n+1,3)+...y*K(n+1,n+1)))

就 而言，每一行都是一个单独的本垒打方案，就 而言，y总之是一个最终的本垒打方案x。

FORTRAN要使用任何语言进行编码，请创建一个中间向量z(n+1)，使得

z(i) = homers(y,K(i,1:n+1))

和

p = homers(x,z(1:n+1))

其中homers(value,vector)是使用存储在 中的多项式系数的单变量评估的实现vector。

于 2010-07-14T21:36:19.897 回答
0

我在 Python 中实现了这个：multivar_horner ( publication )

您可以查看那里使用的方法并将其移植到 Fortran。

参考：

一些相关出版物（包括上面提到的）的作者声称已经实现了他们提出的算法，但我无法找到任何公开可用的算法。

关于“最佳”霍纳因式分解：不是使用启发式方法来选择下一个因式，而是可以允许搜索所有可能的（有意义的）因式分解，以达到最小的霍纳因式分解。

我将此功能包含在multivar_horner：文档中

于 2018-11-08T19:55:10.070 回答