Abstract: 本文介绍多项式求值的相关内容。
Keywords: 多项式求值，霍纳方法

多项式求值

在高中的时候就学过这类知识，但是当时确实不知道怎么用，因为那时候多项式分解成递归形式是数学课上讲的，那时候的教材刚把Basic语言放在书里，老师当然是数学老师，虽然高中数学老师在数学方面非常厉害，但是编程当然不行啦，所以他没说过这个是用在计算机里面的，可能他也不清楚，或者我没听到。但是从今天的课程中，我们能发现，这种递归的分解多项式能有效减少计算量。

多项式求值

计算机最核心部分就是中央计算单元，只能进行加法和乘法的计算，以及逻辑计算，为什么？你去看看数字电路的数，乘法器和加法器是最好实现的，而通过加法和乘法又可以实现多项式计算（减法和除法被我们看成加法和乘法的一种形式），多项式可以用来近似各种函数，所以得出揭露：
计算机计算各类函数都可以转换成多项式计算。
所以多项式之于计算机数学计算，相当于砖之于房子。
每一块砖都达到了最结实状态，房子才能达到最坚固状态。
每个多项式性能最优，整体才能性能最优。
所以我们首先就研究多项式

三种方法

方法1:

$$
P(x)=2x^4+3x^3-3x^2+5x-1
$$
当我们把所有这些都放在寄存器里了，包括 $x$ 的值（这步告诉我们不考虑内存事务的延迟，只考虑计算），假设 $x=\frac{1}{2}$ 我们常规的计算是：
$$
P(\frac{1}{2})=2\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}
+3\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}
-3\times \frac{1}{2}\times \frac{1}{2}
+5\times \frac{1}{2}-1
$$

这是最直观的做法，所有人都会。

1
2
3

统计下计算次数：
乘法—— 10次
加法—— 4 次

计算机完成减法和加法的速度是一致的，这里不需要担心减法的影响，当然除法就有些特殊了，他比乘法要慢很多很多（详情可以参考《深入理解计算机系统》）

方法2:

我们发现这里有不少是重复计算的，减少重复计算是我们提高性能最直接的方法，我们观察发现
$$
x^4=x\times x^3\\
x^3=x\times x^2\\
\vdots
$$
那么我们先计算
$$
\frac{1}{2}\times \frac{1}{2}
$$
并保存为结果啊，然后计算 $\frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}$ 时，就可以计算
$$
\frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}=\frac{1}{2}\times a
$$
消耗一个多于存储空间但是计算量能减少不少。
只计算了 $\frac{1}{2}$ 相乘的3次，加上系数相乘的4次，以及4次加法。

1
2
3

统计下计算次数：
乘法—— 7 次
加法—— 4 次

乘法降低了3次，加法次数不变，只减少了3次乘法，用处大吗？
如果你就计算一次，当然没啥影响，nm级别的优化等于没优化，但是如果大量使用几十亿或者更多次，那就有影响了，而几十亿次好像经常被使用。
或者从相对加速的角度看，我们忽略加法计算，原因是加法计算的耗时相对于乘法来说比较小，我们忽略其影响，然后我们得到了 $\frac{10-7}{10}\times 100\%=30\%$ 的性能提升,这个看起来就很可观了。
那么还能提高么？
答案当然是能：
方法3:

调整多项式的形式：
$$
\begin{aligned}
P(x)
&=2x^4+3x^3-3x^2+5x-1\\
&=-1+x(5-3x+3x^2+2x^3)\\
&=-1+x(5-x(3+3x+2x^2))\\
&=-1+x(5-x(3+x(3+2x)))\\
\end{aligned}
$$

这个分解方式被称为 嵌套乘法 或者 霍纳方法 其直观表现就是 $n$ 阶多项式可以分解成只有 $n$ 次乘法，以及 $n$ 次加法的形式。

1
2
3

统计下计算次数：
乘法—— 4 次
加法—— 4 次

深入理解这个例子

这个方法不止解决了多项式问题，作为一个例子体现了我们科学计算方法中的所有特征：

• 计算机在简单计算的时候速度极快
• 简单计算会被多次重复执行，所以高效的简单计算非常重要
• 最好的计算方法并不是最显而易见的那种。

20世纪后五十年，结合计算机硬件，常见问题已经开发出了许多有效的求解方法（也就是利用计算机帮我们高效的完成数学计算）。
根据霍纳方法，我们可以直接把任意多项式套用到
$$
c_1+x(c_2+x(c_3+x(\dots)))
$$
中去，但是有时候需要点特殊形式，比如后面的插值可能就要用到这种形式
$$
c_1+(x-r_1)(c_2+(x-r_2)(c_3+(x-r_3)(\dots)))
$$
这里面新加的参数 $r_i \text{ for }i=1,2,3,\dots$ 被叫做基点，令其全为0，就回到了我们上面的霍纳方法的最初形式了。

编程实现

然后我们用Matlab实现以下：

1
2
3
4
5
6

function y=nest(d,c,x,b)
if nargin<4, b=zeros(d,1);end
y=c(d+1);
for i=d:-1:1
    y=y.*(x-b(i))+c(i);
end

运行结果：

1
2
3
4
5

>> nest(4,[-1 5 -3 3 2],1/2,[0 0 0 0])

ans =

    1.2500

Matlab的代码比较简单，虽然我们写过matlab的代码，但是这段似乎挺简单，但是这语法，写C太久，看别的语言总感觉语法混乱/(ㄒoㄒ)/~~

1

if nargin<4, b=zeros(d,1);end

这句是判断参数的，如果小于4， $b$ 用0填充
Matlab还可以同时输入多个 $x$ 真的很神奇 😓

1
2
3
4
5

>> nest(4,[-1 5 -3 3 2],[-2 -1 0 1 2])

ans =

   -15   -10    -1     6    53

一个插值的例子，也就是 $b$ 不为空

$$
P(x)=1+x(\frac{1}{2}+(x-2)(\frac{1}{2})+(x-3)(-\frac{1}{2}))
$$

1
2
3
4
5

>> nest(3,[1 1/2 1/2 -1/2],1,[0 2 3])

ans =

     0

总结

多项式是所有计算的基础，但是第一课就写他的原因更多的是其优化开发过程非常具有代表性，代表了数值分析的基本过程和特性，所以作为第一课共大家参考。