数值计算与算法分析.ppt

数值计算的一般原理介绍目录数学问题与数值计算数值问题与算法算法分类一个面向计算机，计算复杂性好，又有可靠理论分析的
算法就是一个好算法。例1：计算多项式P(x)=a0xn+a1xn-1+…+an-1x+an的值。这两种方法的计算复杂性比较见下表人类计算能力等于计算工具的性能与计算方法效率的乘积。数值计算的共同思想与方法迭代法求解线性方程组AX=b观点以直代曲用一般的n次多项式Pn(x)=a0+a1x+…+anx逼近函数f(x)。
其中包括泰勒展开、内插法和其他数值逼近方法。在此基础
上，方程求根、定积分计算、常微分方程数值求解等都能导
出各种不同的数值算法。化整为零例如，计算定积分I=的梯形公式为
I≈T(h)=(1)
当h—>0时，
T(h)=I+O(h2)=I+c1h2+c2h4+…(2)
其中c1，c2不依赖于h，若用步长h’=2h计算，则
T(2h)=I+c1(2h)2+c2(2h)4+…(3)
用(3)-4x(2)得到
T(2h)-I=4[T(h)-I]+O(h4)
忽略O(h4)得到新的数值计算公式：
I≈T(h)+[T(h)-T(2h)]/3（4）
(4)式具有更高的计算精度。数值计算中的精确度分析例：对n=0，1，…，8计算积分yn=。n
建议算法分析与设计实例假定数组的大小对于维A、B、C分别是40,400,4000，并将A、b、C分成4等分。1D方块：A、B、C，由1）的结果间接计算；
0D方块，ABC的所有数据的统计结果通过扫描块1到4可以计算出b0c0，此时分配给b0c0的内存
可以分给下一个块b1c0，在完成对ABC的4个块（5到8）的扫
描后，计算出b1c0。如此继续下去，可以计算整个BC方体，
因此，对于BC中所有块的计算，一次只需一个BC块在内存。在BC方体的计算中，我们将扫描64块中的每一块。
“为计算其它方体，如AB和AC，有没有办法避免重新扫
描所有的块？”下面考虑，
不同的块扫描次序和方体计算次序对整个数据立方体
的计算效率的影响。下面的讨论，我们都假定扫描次序为1到64。假定块的扫描次序为1，17，33，49，5，21，37，53，…。
即是，假定计算扫描次序是
首先向AB平面，
然后向AC平面，
最后向BC平面聚集。
保持二维平面在块内存的最小内存需求量为：
（整个BC平面）+（AC平面的一行）+（AB平面的一块）
400×4000+40×1000+10×100=1641000类似地，我们可以算出1D和0D方体多路计算的最小内存需求量。参考文献：
【1】数值计算原理，李庆扬、关治等清华大学出版社
【2】数值方法（MATLAB版），JohnH.Mathews，电子工业出版社
【3】计算方法引论（第三版），徐萃薇孙绳武，高等教育出版社
【4】数值分析，钟尔杰黄廷祝，高等教育出版社
【5】计算方法，李信真，西北工业大学出版社
【6】数学手册，高等教育出版社