这学期开了一门我很喜欢的课程《数值分析》，我感觉它讨论的都是如何控制误差，还有如何提高算法效率。

教科书上的例子，计算定积分I(n)=e^-1Sx^ne^xdx[0,1] 积分区间[0,1]并估计误差。

首先是找到递推公式I(n)=1-nI(n-1)，然后求出I(0)=1-1/e，用泰勒公式以部分和近似代替取值为0.6321，且知道误差限为0.25*10^-4，然后以递推公式算I(1),I(2),...I(n)，并求它们的误差限，结果是求到I(8)的时候出现了负值，从原始积分看不可能为负值，于是就考虑误差从哪里‘积累’起来了？

原来是递推公式有问题，这样的东西以前从来没考虑过，从操作次数和效率上看这个递推式是不错的算法，但从误差角度看很烂，可以算出e(n)=n!*e(0)=n!*0.25*10^-4，阶乘啊，多么恐怖，即使是e(0)有非常大的精确度，在阶乘面前也是弱不禁风，算不了几下，指数效应就出来了，所以整个算法彻底失败。

误差的累积是算法上的问题，所以要控制误差就需要改进算法，做的改进是，将它反过来，化成：

I(n-1)=(1-I(n))/n

一眼看去，反过来不是很好的办法，如果我要求I(n)就要先求I(n+1)，如此没有个头了，其实不然，从原积分看知道I(n)单调减，且有下界，所以它的I-n图是一个无穷趋于0的图像，所以取一个很大的n，比如n=1000，设I(1000)=0，那误差也是很小的，然后反过来递推，由于这里误差没有累积，所以算1000前面的所有值，误差也可以在控制之中，有相当的精准度，而整个算法也是线性的，相当巧妙。

评论