设万维读者为首页 广告服务 技术服务 联系我们 关于万维
简体 繁体 手机版
分类广告
版主:诤友
万维读者网 > 教育学术 > 帖子
科学计算 (Scientific Computing)
送交者: 木桩 2020年08月09日16:58:31 于 [教育学术] 发送悄悄话

 常常碰到网友问我,什么是计算数学?什么是科学计算?这篇文章企图阐明数学在“科学计算”里的作用。

首先,什么是科学计算?在这方面有着不同的定义。在我看来,这应该是用数学作为工具,设计有效的算法,然后在计算机上实现。的确,科学计算和计算机科学有着紧密的联系,但不是一回事。科学计算着重于数学的角色,强调数学的作用。通过数学,保证设计方法的有效性,有足够的精确度,足够的稳定性,而且提高效率。

还是通过几个有名的例子来说明问题吧。

例一:快速傅立叶变换 (Fast Fourier transform, FFT)

我想,这个方法大家都不陌生吧?在很多科学技术领域里,应用的那个部分里,都需要做傅立叶变换,事实上,当今世界上的计算机在运算的时侯,很多都在作快速傅立叶变换。这里,你就可以看到数学对它的贡献了。其实,这仅仅是初等数学,而且还是比较简单的数学。

一维空间:从0  之间,均匀地分布个点。

频谱空间:傅立叶级数展开。 

傅立叶级数的系数和点空间之间是有关系的。这样说吧,如果你知道了这些点值,就能算出这些系数,反之,知道了这些系数,也能算出那些点值。 

计算机在点值和系数的空间来回计算,这是要有代价的。如果已知系数,要算一个点值,这是 N 数量级的工作量;把所有N个点值全算出来  则是 N2 数量级的工作量。反之,如果已知点值,要把所有N个系数全算出来,也  N2  数量级的工作量。当 N 很大时,这是相当大的计算量,这不,如果 N = 100000,再平方一下,这数字太可怕了,而且,计算机的大量运算会产生误差积累,导致算出的结果不够精确。

能不能把 N降下来?能。快速傅立叶变换 ( FFT) 的思想其实很简单:仔细观察公式,发现有很多重复计算。在算点值时,打个比方(纯粹胡说):第一个点,第四个点,第七个点。。。有重复计算。FFT 把重复计算的部分,一次性算好,然后在第一个点,第四个点,第七个点。。。同时使用。就这么点简单的思想,你只要把它做到极致,一个 N2  数量级的工作量就降到了N log N 数量级了,相比于 Nlog N 是一个很小的数,几乎等同于常数。这,是一个革命性的创举。

可以这么说,如果没有得益于快速傅立叶变换( FFT)的应用,各种信号处理,电子工程,绝对不会变得像今天这么广泛。FFT 在数学上是一个很简单的东西,这件事情之所以做得非常漂亮,就是在数学上并没有做新的事情,也没有改变原来的公式,思路也是简单的,只是把傅立叶公式算得很快,多快好省干革命。

FFT的第一篇文章,1965年发表在Mathematics of Computation , 这是美国数学学会的顶级杂志,也是非常古老的计算数学杂志。这篇FFT 论文的影响力是巨大的。 

例二:快速多极法 fast multi-pole method 

这种方法是用来快速计算 N 个粒子之间两两相互作用的效果。 比如,两两粒子间的引力作用。对一个固定的粒子来说,它的运动取决于它和其他所有粒子两两相互作用的效果之和。把这些相互作用都算清楚,需要 N 数量级的工作量。那么,要算好所有 N 个粒子的运动规律,则需要 N2  数量级的工作量。

这次运气不好,和 FFT 不同,我们似乎找不到明显的重复运算 (除了两两相互作用只需算一次,这只能减少一半运算量,没法在数量级上减少)。但这难不倒数学家。数学家们发现,一个粒子和距离它较远的一堆粒子的相互作用,不用两两算清楚,只需要算这个粒子和这一堆粒子(看成一个大粒子)的相互作用,也就八九不离十了。当然,误差是多少,一堆粒子到底可以多大,如何定义 “较远”,这些都要分析清楚。这次没有办法像 FFT 一样得到和原来公式一样的数学效果,但是,如果给定能容忍的误差,比如千分之一,则上述的办法只需要 N log N 数量级的工作量。实际上,如果把算法和分析再做得精细些,工作量能降到 N 数量级。这种方法叫做 “快速多极法”。 

快速多极法的发明,归功于 耶鲁大学的 V. Rokhlin L. Greengard1985 年,他们发表在 Journal of Computational Physics 的一篇文章中,首创性地提出和分析了快速多极法。和FFT 类似,这个方法也在科学和工程中得到广泛的应用。因为这个工作,这两位数学家得到了美国数学学会 2001 年的 一个重量级奖项 (the Leroy P. Steele Prize)。这项奖通常都是授予纯粹数学家的,应用数学家极少得到该奖,这也说明了快速多极法在数学和应用中的双重重要性。

例三:多重网格法 multigrid method

怎样解大型的线性方程组

                         Ax = b 

A N x N矩阵,是向量。这个问题看上去十分简单,用中学学到的Cramer’s Rule 就能得到解。不过,用Cramer’s Rule 的计算量是 N 的阶乘(N!)的数量级。当矩阵很大的时候,比如, N=1000 N! 是个非常庞大的数,不信你在计算器上摁一摁,会发现计算器都无法显示出这么庞大的结果。不管今天的计算机有多快,都无法在短时间内实现这样的计算。所以,Cramer’s Rule 在解大型的线性方程组时,只有理论上的意义,没有实际意义,纸上谈兵也。

用高斯消除法(Gaussian elimination)求解,可以将工作量从 N! 数量级降到N3数量级。这已经大大提高了计算效率。对一般的线性方程组,这经常是实际计算中唯一可行的方法。不过, N3  还是实在太大了,数学家希望再进一步降低工作量。对于一些实际应用中的矩阵,有些特殊的性质,比如对称正定矩阵,何不利用一下?应用数学知识可以设计 N 数量级的算法,如果能如愿以赏,的确是美事一桩,故而发明了“多重网格法”。要知道,不是所有的矩阵都能采用多重网格法,矩阵需要满足特殊的性质。因为哪怕A是对角矩阵,求解也需要 N 数量级的计算,再也没有油水可榨了,N数量级已经达到了极限。

多重网格法的主要贡献者是以色列数学家Achi Brandt , 为此,2005 年,他得到了美国工业与应用数学学会(SIAM)和美国计算机学会 (ACM) 共同授予的 “计算科学和工程奖”  (Prize in Computational Science and Engineering ) 这是个非常了不起的大奖。


向科学家们致以崇高的敬礼!

 


0%(0)
0%(0)
  好文,谢谢介绍,赞一个!  /无内容 - 五十肩 08/09/20 (275)
标 题 (必选项):
内 容 (选填项):
实用资讯
回国机票$360起 | 商务舱省$200 | 全球最佳航空公司出炉:海航获五星
海外华人福利!在线看陈建斌《三叉戟》热血归回 豪情筑梦 高清免费看 无地区限制
一周点击热帖 更多>>
一周回复热帖
历史上的今天:回复热帖
2019: 外国在中国创ࡃ
2019: ▲費加羅報:習近平香港失算
2016: 思想的形成 宇宙图书馆
2016: 如来一心有三身(三)
2015: 作为精神家园的希腊罗马社会规范
2015: bunny2 :“高级范例”的辨析:思维的