本节书摘来自华章出版社《数值分析（原书第2版）》一 书中的第0章，第0.1节，作者：（美）Timothy Sauer，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
0.1 多项式求值
比如说，当x=1/2时，怎么做才是计算下述多项式的最优方式？P（x）=2x4+3x3-3x2+5x-1假设多项式的系数和x的值1/2都已经保存在内存里，我们试图最小化求值过程中涉及的加法和乘法的计算次数，进而得到多项式的值P（1/2）.为了简化问题，1我们忽略向内存中保存数字以及从内存中读取数字所花费的时间.
方法1 最先想到的直接方法如下：
需要进行的乘法计算的次数是10，还要有4次加法计算.其中的两次加法运算实际上是减法，但是减法运算可以看做是加上数字的负数，因而我们并不担心加法和减法之间的差异.
很显然还有比式（0.1）更好的方法.我们可以事半功倍——通过消除给定输入1/2的重复乘法计算节省运算.更好的策略是先计算（1/2）4，保存部分乘积.这对应下面的方法：
方法2 首先找到输入数字x=1/2的幂，保存幂的值用于后续的计算:
现在我们可以把所有项加起来：
现在只有关于1/2的三次乘法，以及其他的4次乘法运算.总体算起来，我们将乘法运算降低至７次，加法运算的次数仍然是４次保持不变.从１４次到１１次运算次数的减少真的是那么重要的性能提升吗？如果仅仅需要做一次运算，也许这并不是一个重要的改进.不管使用方法１还是方法２，计算结果在手指离开键盘的同时都可以很快得到.但是，如果需要每秒对多个不同输入的ｘ多次计算多项式对应的值，在我们需要信息的时候能够及时获取结果，不同方法的差异可能就显得非常关键.
方法２是对于四阶多项式计算的最好方法吗？难以想象可以再消除３次乘法计算，但实际上可以.下述方法是这类问题的最优的基本求解方法：
方法3（嵌套乘法） 将多项式重写后，可以从内到外对多项式求值:
这里多项式是从前向后写，关于ｘ的幂被分解为与余下的多项式的乘积.我们发现这样写多项式，并不需要额外的计算来进行多项式的重写，所有的系数保持不变.现在从内到外进行计2算：
这种方法被称为嵌套乘法或者霍纳方法，利用4次乘法和4次加法计算多项式的值.一般的d阶多项式可以通过d次乘法和d次加法求值.嵌套乘法和多项式算术中的综合除法关系密切.
多项式求值的例子体现了科学计算方法的所有主题的特征.第一，计算机在做简单计算的时候速度很快.第二，由于简单计算可能会被进行多次，尽可能有效地进行简单计算可能非常重要.第三，最好的计算方式可能不是显而易见的那种方法.在20世纪后五十年，在数值分析和科学计算领域，结合计算机硬件技术，对于常见问题已经开发了有效的求解方法.
虽然标准形式的多项式c1+c2x+c3x2+c4x3+c5x4可以用嵌套的形式写为c1+x(c2+x(c3+x(c4+x(c5))))(0.4)但是一些应用需要更加一般的形式.特别是第3章的插值计算需要如下的形式：c1+(x-r1)(c2+(x-r2)(c3+(x-r3)(c4+(x-r4)(c5))))(0.5)其中我们称r1，r2，r3和r4为基点.需要注意的是，若设置式（0.5）中的参数r1=r2=r3=r4=0，则变成式（0.4）中传统的嵌套形式.
下面的MATLAB代码实现了一般形式的嵌套乘法计算（参照式（0.3））:
运行上面的MATLAB程序需要给出输入数据的值，包括多项式的阶数、系数、需要求值的点ｘ，以及基点数组.例如，式（0.2）中的多项式在x=1/2处利用如下MATLAB命令进行求值：
结果和我们前面手工计算的结果相同.当执行以上命令时，nest.m文件以及本书其他部分展示的MATLAB代码，必须是在MATLAB路径或者当前目录可访问路径下.
如果嵌套命令用于求解式（0.2）（其中所有基点为0），可以使用如下缩减形式的命令：
使用该命令可以得到同样的结果，这是由于在nest.m中对于输入参数的设置.如果输入参数的个数小于4，基点被自动设置为0.
由于MATLAB对于向量表达的无缝处理，嵌套命令可以同时估计一组x对应的多项式的值.下面是一个示例:
最后，第3章中将出现的三阶插值多项式
在x=1的值可以通过下面命令计算得到
例0.1 找出有效方法计算多项式P(x)=4x5+7x8-3x11+2x14的值.
对于多项式的一些重写可以降低求值运算中的计算代价.主要思想是将多项式分解为x5和一个由x3的整数幂构成的多项式的乘积：P(x)=x5(4+7x3-3x6+2x9)=x5(4+x3(7+x3(-3+x3(2))))对于每个输入的x，我们需要首先计算xx=x2,xx2=x3,以及x2*x3=x5.这三个乘积以及关于x5的乘积，与三阶多项式对应的三次乘法和三次加法，构成了原始多项式中每次求值的7次乘法4和3次加法.
0.1节习题
1.将如下多项式重写为嵌套形式，并利用嵌套和非嵌套形式计算该多项式在x=1/3时的值.
(a) P(x)=6x4+x3+5x2+x+1
(b) P(x)=-3x4+4x3+5x2-5x+1
(c) P(x)=2x4+x3-x2+1
2.将如下多项式重写为嵌套形式，并计算该多项式在x=-1/2时的值:
(a) P(x)=6x3-2x2-3x+7
(b) P(x)=8x5-x4-3x3+x2-3x+1
(c) P(x)=4x6-2x4-2x+4
3.计算P(x)=x6-4x4+2x2+1在x=1/2时的值，其中将P（x）转化为由x2构成的多项式，并利用嵌套乘法计算.
4.计算包含基点的嵌套多项式P(x)=1+x(1/2+(x-2)(1/2+(x-3)(-1/2)))当（a） x=5与（b） x=-1时的值.
5.计算包含基点的嵌套多项式P（x）=4+x（4+（x-1）（1+（x-2）（3+（x-3）（2））））当（a） x=1/2与（b） x=-1/2时的值.
6.如何根据给定x计算如下多项式的值，要求使用尽可能少的计算.各自需要多少次的乘法和加法？
(a) P(x)=a0+a5x5+a10x10+a15x15
(b) P(x)=a7x7+a12x12+a17x17+a22x22+a27x27
7.使用一般的嵌套乘法，需要多少次的乘法和加法来计算包含基点的n阶多项式的值？
0.1节编程问题
1.使用函数nest估计P(x)=1+x+…+x50当x=1.00001时的值.（使用MATLAB命令ones以节省键盘录入.）通过和等价表达式Q(x)=(x51-1)/(x-1)进行比较，找出误差.
2.使用nest.m计算多项式P(x)=1-x+x2-x3+…+x98-x99当x=1.00001时的值.寻找更简单等价的表达式，并利用该表达式估计嵌套乘法的误差.
