如何实现Horner的多元多项式方案？

Question

背景

我需要在Fortran90/95中使用Horner方案解决多个变量中的多项式.这样做的主要原因是使用Horner方案评估多项式时出现的效率和准确度提高.

我目前有一个针对单变量/单变量多项式的Horner方案的实现.然而,开发一个使用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的伪代码,我将非常感激.

Answer 1

对于两个变量,可以将多项式系数存储在秩= 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.