设万维读者为首页 万维读者网 -- 全球华人的精神家园 广告服务 联系我们 关于万维
 
首  页 新  闻 视  频 博  客 论  坛 分类广告 购  物
搜索>> 发表日志 控制面板 个人相册 给我留言
帮助 退出
     
  木桩的博客
  我来自金星
网络日志正文
科学计算 (Scientific Computing) 2020-08-09 16:58:27

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

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

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


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

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

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

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

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

计算机在点值和系数的空间来回计算,这是要有代价的。如果已知系数要算一个点值,这是 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 ) 这是个非常了不起的大奖。


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


 


浏览(5238) (5) 评论(22)
发表评论
文章评论
作者:老任1104 留言时间:2020-09-15 08:56:13

冯康是中国本土计算数学的传奇:

https://mp.weixin.qq.com/s/RT3g59Z9hvdomRDZKAg72g


回复 | 0
作者:msc 回复 木桩 留言时间:2020-08-16 12:37:00

Get it, thanks.

回复 | 0
作者:木桩 留言时间:2020-08-13 17:21:25

The link does not seem to show in this website. You can google

"shu gottlieb gibbs" and the first item is the review paper.

回复 | 0
作者:木桩 回复 msc 留言时间:2020-08-13 17:15:29

Thank you very much for the link, which looks amazing :)

I have put this link at the end of my article. If you are interested in Fourier series and Gibbs phenomenon, there is a review paper that you might be interested:


回复 | 0
作者:msc 留言时间:2020-08-12 20:32:14

https://www.youtube.com/watch?v=ds0cmAV-Yek

What is a Fourier Series? (Explained by drawing circles)


回复 | 0
作者:msc 留言时间:2020-08-12 20:29:36

Swarm system are examples of decentralized systems, which depends on interaction and communications between each pair of entities. 快速多极法 is a good fit. Unfortunately, I could not show off here due to the nature of work.

回复 | 0
作者:木桩 回复 老冬儿 留言时间:2020-08-11 17:39:07

谢冬儿驻足留言,遥祝阖家夏安!

子曰:“温故而知新,可以为师矣”。

回复 | 0
作者:老冬儿 留言时间:2020-08-10 20:58:39

上午就悄悄来过。 给木桩MM致以崇高的敬礼。我早就把傅里叶级数还给老师了。

回复 | 0
作者:木桩 回复 木秀于林 留言时间:2020-08-10 20:22:12

非常感谢木秀先生,码下这么多的字,花了这么多精力,为我的文章补充内容。我正在思考写一篇有关微分方程的文章,贴出来后,望先生再来议论和评定。

回复 | 0
作者:Laober 回复 木秀于林 留言时间:2020-08-10 18:22:11

老闲人一点数学都不会,吹起牛来还是一套接一套的!

人才啊!哈哈哈哈!

回复 | 0
作者:木秀于林 回复 木桩 留言时间:2020-08-10 17:26:19

另外,傅立叶变换、源于傅立叶级数,确实是数学界或科学界的一个里程碑式的突破。

原因在于,它以数学证明的方式,证明了不可琢磨的世界可以用无限逼近的方法实现,以反映自然世界的原貌,为科学界提供了一种无限逼近的科学可靠思想方法,并且这种方法是无懈可击的。

最早的傅立叶级数的应用是任意波形皆可以用频率不同的正选波叠加而成。而正选波是可以很方便的计算的。

从这个角度看,有限元法和傅立叶变换不能相提并论,差太远。

回复 | 0
作者:木秀于林 留言时间:2020-08-10 17:04:10

举个例子,为大型变压器厂(沈阳变压器场)计算变压器周围的电场和磁场。在有数值计算之前,生产一款新型变压器考模拟实验,也就是按比例缩小原大型变压器的尺寸和相应参数……即费钱又费力,精确度也低。

用于计算回旋加速器的磁场,原子能所也是首次。

回复 | 0
作者:木秀于林 回复 木桩 留言时间:2020-08-10 16:52:58

先生原来也是计算数学学者,握手!……

热烈握手,学者不敢当,专家还凑合。一般学者往教授发展,专家往工程师发展。

以我的专题为例,电磁场数值计算要解决实际问题。当时的研究生课主要有线性代数、矩阵论、场论、工程数学(常微分方程、偏微分方程),离散数学(模糊数学选修),计算机语言两门,C语言和fortran语言。

所谓偏微分方程,又叫数学物理方程。

拉普拉斯方程用来计算无源场,泊松方程用来计算有源场。在电磁场的应用中,场源有两种,一是电荷,一是电流在磁场中运动。所以有源场派生出有旋场。梯度、散度、旋度是常用词。

除去有限元法,还有一种边界元发,在解数学物理方程时,需输入边界条件,有限元、边界元无非是尽量方便、精确的输入边界条件的一种方法。

回复 | 0
作者:西石槽7号 回复 木秀于林 留言时间:2020-08-10 15:52:29

立此存照,看看你自己说得话。上次发给你,被你删除,这次在别人地盘儿上,你删不了。


作者:木桩 回复 木秀于林

留言时间:2020-06-21 22:24:29

木秀先生,从你的留言中,感觉到你是那动荡年代的过来人,是时代的见证者。你又是出生贫下中农,制度下的受惠者,但你能站在正义的立场上说公道话,这就非常不容易了。这又让我想起你那善良的老母亲,有其母必有其子,虎母哪来犬子?

作者:木秀于林 回复 西石槽2020-07-08 14:37:49

黑五类,就欠当初被共产党整死。

中共流氓政权“平凡、昭雪”骗人把戏的牺牲品、以“受迫害”、“挨整”为荣。人渣而已。

是。根红苗正,哈哈………专门整治黑五类滴…<span style="font-size:19px;font-family:"&color:black">…


回复 | 0
作者:木桩 回复 msc 留言时间:2020-08-10 14:54:48

Thanks for your comment and good luck for your research.

回复 | 0
作者:木桩 回复 gugeren 留言时间:2020-08-10 14:46:44

冯康【1920年9月9日-1993年8月17日】

谢谢先生解惑。

冯康的生日和“毛伟人”的忌日相同的巧合,让我记起网上看到的一个数学题,求在同一班上的学生,同年同月同日的概率。常识猜测觉得可能性极小,但算出来的概率却蛮大的,可见有些事件出现的概率,并不是人们所想象的那样。


回复 | 0
作者:msc 留言时间:2020-08-10 09:01:18

Thanks for introductionn of 快速多极法. We are looking for method for control of swarming systems and their M&S.

回复 | 0
作者:gugeren 回复 木桩 留言时间:2020-08-09 20:06:32

查了一下,很有意思,冯康的生卒月份靠得很近:

https://zh.wikipedia.org/wiki/%E5%86%AF%E5%BA%B7

冯康【1920年9月9日-1993年8月17日】

2020年,那就是冯康诞生100周年了。

还有一个有趣的事是:9月9日是那位“毛伟人”的忌日哦,呵呵!


回复 | 0
作者:木桩 回复 木秀于林 留言时间:2020-08-09 19:18:30

先生原来也是计算数学学者,握手!

有限元是解决微分方程的工具,先生提醒了我,下一篇文章应该写有关微分方程了。

冯康是中国有限元的父亲,今年国内的应用数学界在纪念他,我没搞清楚,到底是纪念冯康的诞生日,还是殇日?

回复 | 0
作者:木桩 回复 gugeren 留言时间:2020-08-09 19:09:09

是的,应用数学的出路很广,大到宇宙,小到量子。如果学术界走不通,还可以有广阔的工业界,不怕找不到工作。

回复 | 0
作者:木秀于林 留言时间:2020-08-09 18:11:44

在我看来,这应该是用数学作为工具,设计有效的算法,然后在计算机上实现。……

依木桩主所言,我的老本行就是科学计算了。

我研究生的论文题目是《电磁场数值计算》,计算实例是为中科院原子能所计算回旋加速器轨道磁场。最后的精确度达到千分之十六。按以往规矩,磁场计算的精度在10%依哪就相当不错了。

用的是C语言,有限元法。最后归结为解36*36的线性方程组,在当时的“大型计算机”(内存4.5兆)上,足足计算了45分钟。大型计算机,原子能所也只有两台。

回复 | 0
作者:gugeren 留言时间:2020-08-09 17:25:50

现在应用数学已经走到非常实用的阶段的了,学习应用数学是一个很好的出路,特别是对即将高中毕业的孩子们。

回复 | 0
我的名片
木桩
注册日期: 2014-11-04
访问总量: 522,897 次
点击查看我的个人资料
Calendar
分类目录
【教育与学术-1】
· 格林威治 -- 国际标准时间
· 美国的福利保险费是怎样算出来的
· 美国的401(K)养老金
· 关于量子保密通讯
· 揭露中国学者在期刊上造假作弊
· 中国和美国教育学术界的若干比较
· 计算数学家在干些什么?
· 学术杂志的“影响因子”
· 有感中国人的高校情结
· 首尔-2014世界数学家大会
【教育与科学 - 2】
· 飞机安全吗?--- 分析几次重大空
· 谈谈世界顶尖科学家的排名榜
· 公益贴 --- 再谈疫苗
· 公益帖 --- 新冠疫苗的最新发展
· 公益贴 --- 谈谈疫苗
· 科学计算 (Scientific Computing
· 从三峡大坝想到水利工程
· 检测新冠病毒的3 种方法 --- 分
· 波音737- MAX8 出事原因在哪里?
· 介绍一个美国顶级应用数学系
【教育与学术 - 3】
【回国感想】
· 北京感想
· 2016 - 相会在上海
· 2015 回国见闻 - 爽爽贵阳
· 2015 回国见闻 - 贵州织金洞
· 2015 回国见闻-黄果树大瀑布
· 2015 回国见闻 -云南石林
· 回国见闻 -上海受骗上当记
· 回国见闻 -国内的几个有趣现象
【芸芸众生】
· 为生活在战争中的人们祈祷 !
· 深秋的祭念
· Memorial Day - 告慰全世界新冠
· 20世纪最大的艺术伪造案 -米格伦
· 先生已逝,精神长存 --- 怀念张
· “天鹅之死” -我的油画
· 庞氏骗局
· 从数学家纳什联想到 。。。
· 我的露露和咪咪
【茗香茶语】
· 天鹅的梦呓
· 母亲节,樱花又开了
· 礼轻情意重
【回忆录】
· 童年的回忆
· 西南联大逸闻轶事
· 魂萦上海滩(5)-文革中的那些邻居
· 魂萦上海滩(4)--我的母亲
· 魂萦上海滩(3)-妈妈给我的礼物
· 魂萦上海滩(2)–绿房子里的故事
· 魂萦上海滩(1)-万航渡路
· 童年旧事 -我的小提琴老师
· 父亲留下的传家宝
· 父亲的住房情结
【艺术-1】
· 艺术座谈 (2) - 艺术的两重性
· 艺术座谈 (1) --- 怎样理解音乐
· 艺术也能变戏法
· 我的艺术创作 --- 雕塑, 油画,
· 话说故宫
· 漫谈艺术——西方画 vs 中国画
· 装修设计 - 让电脑为人类服务
· 家庭住宅的装修和设计
· 浅谈人体雕塑
【艺术-2】
· 芭蕾舞 --- 四只小天鹅翩翩起舞
· 摄影练习 — 日本的风俗人情
【钢琴演奏】
· 爱吧!能爱就爱吧!—- 李斯特的
· 聆听古典音乐,欣赏现代建筑
· 肖邦夜曲,情愁凄美,孤独浪漫
· 介绍钢琴夜曲的祖宗 John Field
· 舒曼的钢琴曲--《异国陌人》
· 音乐和数学 - 十二平均律
· 2015 圣诞之夜-《少女的祈祷》
· 钢琴独奏 -《 梦幻》
【钢琴演奏 -2】
【世界各地】
· 伦敦白金汉宫皇家卫队换岗仪式
· 希腊罗德岛太阳神巨像失踪之谜
· 巴西--写在2016 夏季奥运会之前
· 西班牙的小偷和斗牛士
· 法国的香农舍 -女人的城堡
· 印度的硅谷
· 莫斯科之行
· 巴黎的墓地
【歌剧】
· 庚子年 --- 妈妈,生日快乐!
· 二首上海经典老歌给万维朋友拜年
· 祝万维朋友 平安夜好!圣诞快乐
· 歌剧中的咏叹调《我亲爱的爸爸》
· 歌剧欣赏 (2)-我听歌剧的体会
· 歌剧欣赏(1)- 什么是歌剧
· 一首日本民歌 —《爱的礼物》
【诗词歌赋】
· 七言绝句三首 -《春天的思念》
· 七言绝句二首 - 《访友》
· 枫叶又红了 ---- 七言 . 思君
· 名家诵读 --- 唐诗二首
【高山流水论坛年庆】
· 【金牛贺春】贝多芬钢琴奏鸣曲《
· 【金猪贺岁】上海怀旧老歌《月圆
· 【金狗旺旺】— 献给爱丽丝
· 【高山年庆】-- 向朋友们致敬!
【核桃树 --- 万维博客科学沙龙】
· 艺术也能变戏法
· 纪念切尔诺贝利核事故三十周年:
· 疯子数学家 -- 约翰.纳什
 
关于本站 | 广告服务 | 联系我们 | 招聘信息 | 网站导航 | 隐私保护
Copyright (C) 1998-2024. CyberMedia Network /Creaders.NET. All Rights Reserved.