【数值分析】0.1 多项式求值

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

res-1

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

res-2

一个插值的例子,也就是 $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

总结

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

0%