mymath的个人博客分享 http://blog.sciencenet.cn/u/mymath

博文

高斯与数值分析

已有 5901 次阅读 2009-4-7 14:16 |个人分类:数学故事|系统分类:科普集锦

高斯是介于古典数学与现代数学之间的一个人,我通常认为他是连接古典与现代的一座桥梁。这可从他在代数、几何等领域的工作看出来。在代数方面,高斯给人印象深刻的是代数基本定理的发现;在几何方面,高斯曲率的出现让人耳目一新,高斯也称高斯曲率的内蕴性质是“奇妙”的定理。而这直接促使了黎曼几何的诞生,后者在现代数学中扮演着极为重要的角色。
高斯的一个研究风格是不分纯粹与应用,他本人也对应用科学,例如电磁学,做了极大的贡献,并长期研究天文学与大地测量学。(我一向对兴趣广泛的数学家是极为欣赏的)
 
而我今天想要说的是高斯对数值分析的一些贡献。当然,这些贡献对当年的高斯来说也许微不足道,但其重要性却超过高斯大多在纯粹数学里的工作,这也许是高斯当年所未预料的。(我下面介绍三个比较重要的例子,有其它方面的疏漏也请大家补充)
 
第一个就是大家熟知的高斯消元法。用它来求解线性方程组,从我们今天的观点来看,当真是朴素的不能再朴素。但高斯消元法的故事却远比我们想象的丰富。如果用矩阵的形式来表达高斯消元法就是所谓的LU分解。这个简单的分解在很多矩阵研究里极为重要。不过有趣的是,很多时候我们说高斯消元法时,大家都是很熟悉的,但是当我们提到LU分解的时候,并非所有人立即感觉熟悉与亲切。
 
高斯消元法的算法复杂度延伸则是数值分析里的一个核心问题。我们知道,倘若矩阵的规模是nby n,那么高斯消元法的复杂度则是n^2. 那么,这个复杂度是可以降低的吗?如果可以, 最低可降到多少?
这个问题也可归结为矩阵求逆的最低复杂度为多少?用高斯消元求逆,算法复杂度为n^3. 1969年,Strassen在一篇不足三页的论文里介绍了一个新算法,其复杂度可以降为n^log7. 这让人第一次意识到高斯消元法,从复杂度角度来看,并非最优的。如今,这一算法被称为Strassen算法。随后,人们这一算法进行了改进,复杂度可进一步降低。这些算法并不实用,一是算法不具备数值稳定性,二是虽然复杂度从理论上降低,但隐藏在其中的常数却很大,也就是说只有对充分大的n,这个算法的优越性才能体现。
但无论如何,这一问题的理论上确是极为吸引人的。主要问题是,对于矩阵求逆而言,最低的复杂度为多少?我们能降到n^2logn吗?如今,这仍然是数值分析里边一个极为重要的问题。(对于矩阵相乘而言,也有类似的复杂性问题,但可以证明这和矩阵求逆是等价的)
 
高斯对数值分析第二个比较重要的贡献是高斯积分公式。也就是说,当我们对函数f(x)在区间[0,1]上进行数值积分的时候,积分点如何选择才是最优的?高斯给了一个极好的选择方式(为一类直角多项式的零点),如今这些点被称为高斯点。如今,高斯积分公式在球面、单纯形及各种区域上的推广,依旧是一个极为重要与热门的研究课题。
 
高斯对数值分析的第三个比较重要的贡献是快速Fourier变换。这个变换可将复杂度从n^2降到nlogn.这一点的改进使得Fourier变换变得极为实用。今天,这一快速算法的多元推广也是引人关注的研究课题。(也许这一算法不应该归于Gauss,虽然他最先发现这一算法,但是他并没有公开出版。后来被Cooley,Tukey重新发现,并被人们广泛采用,所以人们通常认为,这一算法应归功于Cooley,Tukey.)


http://blog.sciencenet.cn/blog-240898-224807.html

上一篇:开通博客
下一篇:欧拉的想象力

2 黄富强 杨华磊

发表评论 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-11-22 12:29

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部