博文
高斯与数值分析
||
高斯是介于古典数学与现代数学之间的一个人，我通常认为他是连接古典与现代的一座桥梁。这可从他在代数、几何等领域的工作看出来。在代数方面，高斯给人印象深刻的是代数基本定理的发现；在几何方面，高斯曲率的出现让人耳目一新，高斯也称高斯曲率的内蕴性质是“奇妙”的定理。而这直接促使了黎曼几何的诞生，后者在现代数学中扮演着极为重要的角色。
https://blog.sciencenet.cn/blog-240898-224807.html
上一篇：开通博客
下一篇：欧拉的想象力
高斯的一个研究风格是不分纯粹与应用，他本人也对应用科学，例如电磁学，做了极大的贡献，并长期研究天文学与大地测量学。（我一向对兴趣广泛的数学家是极为欣赏的）
而我今天想要说的是高斯对数值分析的一些贡献。当然，这些贡献对当年的高斯来说也许微不足道，但其重要性却超过高斯大多在纯粹数学里的工作，这也许是高斯当年所未预料的。（我下面介绍三个比较重要的例子，有其它方面的疏漏也请大家补充）
第一个就是大家熟知的高斯消元法。用它来求解线性方程组，从我们今天的观点来看，当真是朴素的不能再朴素。但高斯消元法的故事却远比我们想象的丰富。如果用矩阵的形式来表达高斯消元法就是所谓的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.）
https://blog.sciencenet.cn/blog-240898-224807.html
上一篇：开通博客
下一篇：欧拉的想象力
扫一扫，分享此博文
全部作者的精选博文
全部作者的其他最新博文
- • 0.999……为什么等于1
- • 武松为什么“醉”打蒋门神
- • 跨越时空的求和
- • 关于数学的几个梦境
- • 样条空间维数传奇
- • 高斯函数---最接近上帝的函数