数值算法研究

【摘 要】数值算法是计算机算法的重要组成部分，在科学计算领域有着广泛的应用。本文介绍了基本并包含重要算法思想的数值算法，在体系和针对性方面做些探讨研究。杨辉三角针对动态规划思想应用；多项式求值Horner法则针对多项式求值的算法效率；大整数乘法针对计算机数字限制性；矩阵的求逆运算针对理论算法与实际算法之差别等。

【关键词】数值算法；研究

数值计算方法，是一种研究并解决数学问题的数值近似解方法，是在计算机上使用的解数学问题的方法，简称数值算法。数值算法既有数学类课程中理论上的抽象性和严谨性，又有实用性和实验性的技术特征，数值算法是一门理论性和实践性都很强的学科。计算机主要使用的数值算法有：杨辉三角；多项式求值Horner法则；大整数乘法；矩阵的求逆等。杨辉三角就是动态规划思想应用的很好例子；多项式求值Horner法则大大提高了多项式求值的算法效率；大整数乘法是处理计算机数字表示限制性的很好示范；矩阵的求逆运算体现了理论算法与实际算法的差别。

一、杨辉三角：所谓的“杨辉三角”也西方也被称为贾宪三角形，帕斯卡三角，是用来计算二项式展开系数的一个数学工具

著名的“二项展开式”如下：

同时，这也是多项式(a+b)^n打开括号后的各个项的二次项系数的规律。因此，杨辉三角第x层第y项直接就是（y nCr x）。我们也不难得到，第x层的所有项的总和为2^(x-1)(即(a+b)^x中a，b都为1的时候)。上述y^x指y的x次方，(a nCr b)指组合数。

简单的说，就是两个未知数和的幂次方运算后的系数问题，比如（x+y）系数是1，2，1这是杨辉三角的其中一行，立方，四次方，运算的结果成为各项的系数。这就是杨辉三角，（Pascal’sTriangle）。二项式定理与杨辉三角形是一对天然的数形趣遇，它把数形结合带进了计算数学。求二项式展开式系数的问题，实际上是一种组合数的计算问题。用系数通项公式来计算，称为“式算”；用杨辉三角形来计算，称作“图算”。常数项产生在展开后的第5、6两项.用“错位加法”很容易“加出”杨辉三角形第8行的第5个数。如下：

1 4 6 4 1

1 5 10 10 5 1

…… 15 20 15 6 …

1 …… 35 35 21 ……

… 70 56 …

得到=70，==56.

故求得展开式中常数项为702×56=42

“式算”与“图算”趣遇，各扬所长，各补所短。杨辉三角形本来就是二项式展开式的算图.对杨辉三角形熟悉的考生，比如他熟悉到了它的第6行：1，6，15，20，15，6，1。

杨辉三角形强调“多想少算”、“逻辑思维与直觉思维并重”的结果。

二、多项式求值

给定形式的多项式，如：

所谓的“多项式求值”是指对于特定的x时，求出p（x）的值的问题。下面首先给出了多项式求值的一般算法，其后再利用所谓的Horner法则，给出多项式求值的一个更好的算法。

1、一般算法

对于给定的多项式以及给定值求多项式的值

输入：n阶多项式对应的系数，给定值x

输出：多项式在x处的值

保存计算过程中间结果：

for i n downto 0 do

power 1 //初始化

for j 1 to i do

power power * x //计算在x处的值

p p + P[i]*power //计算的值并加到前面的计算结果中

返回p

2、二进制求幂算法

从左到右逐位扫描算法：

从右到左逐位扫描算法：

三、大整数乘法

在分析一个算法的计算复杂性时，如果算法的基本操作是加法和乘法，那么用加法或者乘法操作执行次数衡量算法效率的前提是：计算机执行一次加法操作或者乘法操作所需的计算时间是一个常数，这个常数仅取决于计算机硬件处理速度。

然而，这个假定基于仅在计算机硬件能对参加运算的整数直接表示和处理的时候才是合理的。在某些情况下，如果待处理加法运算或者乘法运算是作用在很大的整数，那么使用加法或者乘法运算次数作为算法效率的衡量有时候是不公平的。

1、算法思想

由于计算机能够处理的最大整数是有限制的，例如C语言中的长整型（long）可以表示数的范围是-2147483648~2147483647。

如果乘法处理的整数大于计算机可以表示的范围，最直观的解决办法是把整数分段，分别求出每段的乘积以及两段之间的一些关系，再进一步求得这两个大整数的乘积。

2、算法伪代码

计算两个n位的大整数乘积

输入：n位长的大正整数x和y

输出：xy的乘积

if n = 1 return x*y

else

a1 ；a0 a-a1*

b1 ；b0 b-b1*

m2 MultiInteger( a1，b1，n/2)

m1 MultiInteger( a1+a0，b1+b0，n/2)

m0 MultiInteger( a0，b0，n/2)

return m2*+(m1-m2-m0)* +m0

3、算法分析

对于n位大整数的乘法，如果使用递归求解，那么每次递归需要调用3次n/2位的大整数乘法操作，也就是说：

四、线性方程组与高斯消元法

科学计算中通常需要解多个变量的方程组，这些方程组当中最简单的是线性方程组，也就是变量的次数均为1次的。求解线性方程的方法通常有两种，也就是利用高斯消元的直（下转第86页）（上接第83页）接法以及迭代法。这里仅仅给出高斯消元法解线性方程组的介绍，它还可以应用到后面的矩阵的求逆运算以及矩阵行列式的计算。

1、线性方程组

一般的线性方程组是指形式为：

2、高斯消元法

算法伪代码：

ALGORITHM GaussElimination(A[1，2，…，n]，b[1，2，…，n])

应用高斯消元法求解n阶线性方程组

输入：系数矩阵A及常数项b

输出：与输入线性方程组增广矩阵等价的上三角矩阵

for i 1 to n do

把常数项加为系数矩阵最后一列，构成线性方程组的增广矩阵

A[i][n+1] b[i]

for i 1 to n-1 do

for j i+1 to n do

for k i to n+1 do

A[j][k] A[j][k] A[i][k]*A[j][i]/A[i][i]

3、矩阵的LU分解

四、小结

数值计算在科学计算等领域中有广泛的应用，其中数学的基本运算、杨辉三角及多项式的求解、矩阵的基本运算以及方程与方程组的求解是其中的基础内容。矩阵的LU分解以及矩阵的求逆与行列式运算都是基于高斯消元算法的，能够根据算法的过程对小规模的线性方程组应用高斯消元法需要重点掌握，区别使用不同算法，具有实用价值。