多项式函数插值：多项式形式函数求值的Horner嵌套算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了多项式函数插值：多项式形式函数求值的Horner嵌套算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1396字，纯文字阅读大概需要2分钟。

内容图文

　　设代数式序列 $q_1(t), q_2(t), ..., q_{n-1}(t)$ ，由它们生成的多项式形式的表达式（不一定是多项式）：

$$p(t)=x_1+x_2q_1(t)+...x_nq_1(t)q_2(t)..q_{n-1}(t)=\sum\limits_{i=1}^n(x_i\prod\limits_{j=1}^{i-1}q_j(t))$$　　一般来讲，按照这个形式计算函数在 $t_0$ 点的取值的复杂度为：n-1次 $q_i(t)$ 求值，n-1次浮点数乘法（生成n个不同的乘积），n-1次乘积和常系数浮点数乘法，n-1次浮点数加法 $\Rightarrow$ 总计n-1次 $q_i(t)$ 求值和 $T(n)\approx 3n$ 次浮点数运算。这需要在计算过程中存储保留一个 $\prod\limits_{j=1}^{i-1}q_j(t)$ 的结果，避免重复运算（那样将会使得生成乘积的n次浮点乘法变成$n^2/2$ 次）。

　　利用Horner嵌套算法，可以在 $T(n)\approx 3n$ 的基础上再进一步。Horner嵌套算法的表达式是：$$p(t)=x_1+q_1(t)(x_2+q_2(t)(x_3+q_3(t)(...(x_{n-1}+q_{n-1}(t)x_n)...)))$$　　迭代的伪代码可以写成：

$poly = x_n\\for\quad i = n -1 to 1\\ \quad poly = x_i+q_i(t)\times poly\\ end$

　　Horner嵌套算法需要n-1次 $q_i(t)$ 求值（这是免不了的），n-1次浮点数乘法，和n-1次浮点数加法，这将把复杂度再削减到n次求值和 $T(n)\approx 2n$ 次浮点数运算。考虑到函数求值是非常普遍和基本的操作，即使只是在复杂度上打个折扣也是非常可观的事情。因此形如上式的多项式型表达式，只要可以使用Horner嵌套算法就应当使用。

　　Horner嵌套算法适用于通过单项式表达的多项式求值，即 $p(t)=x_1+x_2t+x_3t^2+...+x_nt^{n-1}$ ，此处 $q_1(t)=q_2(t)=...=q_n(t)=t$；同样也适用于通过牛顿插值表达的多项式，即 $p(t)=x_1+x_2(t-t_1)+...+x_n(t-t_1)..(t-t_n)$ ，此处 $q_i(t)=t-t_i$ 。

内容总结

以上是互联网集市为您收集整理的多项式函数插值：多项式形式函数求值的Horner嵌套算法全部内容，希望文章能够帮你解决多项式函数插值：多项式形式函数求值的Horner嵌套算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---