数值分析

2021年6月6日2022年2月5日 numanal 0 个评论刘徽, 微分方程数值解, 教材推荐, 数值分析, 编程语言

什么是数值分析

早在三十年前, 计算数学的先驱之一 L. N. Trefethen 就给出了数值分析的定义:

Numerical analysis is the study of algorithms for the problems of continuous problems.
—- Lloyd N. Trefethen, Cornell University

翻译过来就是: 数值分析是研究连续问题的算法的科学. 其中, 最主要的概念就是算法和连续问题. 首先, 连续问题是从物理或者其它学科中抽象出来的复杂模型问题, 一般是无穷维问题且几乎无法找到解析解. 这些棘手的连续问题就自然成为数值分析的目标对象. 其次, 求解连续问题的算法的设计和分析是数值分析的核心内容, 它们的目的是将连续的无穷维的问题离散化, 得到一个离散的有限维的可解问题, 进而得到近似解. 如果没有数值分析, 现代科学与工程应用研究将很快陷入停滞.

历史背景

最早的关于数值分析的思想之一可以追溯到大约公元前 1800 到公元前 1600 年的一个古巴比伦泥板, 也就是著名的存放在耶鲁大学的 YBC 7289, 记载的关于 $\sqrt{2}$ 的近似. 那时的学者已经明确知道正方形对角线的长度与正方形边的比值是一个平方为 2 的数, 并且找到了近似算法 (尽管现在我们无人得知他们是版得到的), 给出了 $\sqrt{2}\approx \frac{305470}{216000} \approx 1.414213$. 另外, 一块古巴比伦石匾（约公元前 1900 年至公元前 1600 年）清楚地记载了圆周率 $\pi\approx \frac{25}{8}=3.125$. 严格的数学证明自阿基米德之后成为主流, 但是数值近似一直是人们探索这个世界的最久远最常用工具.

中国古代关于数值近似的思想最典型的就是关于圆周率的计算.

《周髀算经》(约公元前 200 年)中的 “径一而周三” 的记载 ($\pi \approx 3$).
汉朝张衡的 $\pi\approx \sqrt{10}$,
公元 263 年刘徽的 “割圆术” 算法 (一种甚于正多边形的迭代算法) 近似得到 $\frac{3927}{1250}\approx 3.1416$.
约公元 480 年, 祖冲之利用同样的方法, 确定了圆周率 $3.1415926 < \pi < 3.1415927$ 并且得到两个近似值密率 $\frac{355}{113}$ 和约率 $\frac{22}{7}$. 使得圆周率的近似到了惊人的小数点后七位, 这个记录保持了 800 年之久, 才由印度数学家 Madhava 的 11 位精度打破, 他利用圆周率的 Madhava-Leibniz 级数展开的前 21 项得到.

这些优秀的结果是数学发展长河中的一个极小的支流, 做出了应有的贡献. 但是遗憾的是, 严谨的数学理论并没有在之后的中国孕育出来. 科学, 直到近代才由西方传入并在中国快速传播发展. 不可否认, 近代我国学者及华人学者对数学和其它学科的发展做出的贡献不可忽视, 并且现代数学的发展中国内及华人学者成为了重要的推动力量. 历史发展一直在证明, 不断交流才能不断进步. 虽然历史没有假设, 但是可以想象如果西方的科学思想可以更早的进入中国, 现代中国又是什么样呢?

基本思想

数值分析主要考虑问题的数值解方面的内容, 包括但不限于数值算法的构建, 误差传播的影响, 计算复杂度的估算以及高效可靠的计算机的实现. 虽然对于不同的问题有不同的数值模型来构建, 但是他们一般都具有一些共同点:

数值分析一般会以线性代数, 高等数学, 实分析和泛函分析等内容为基础或者分析工具;
如果一个问题不能直接求解, 尝试考虑一个近似的可解的问题;
稳定性. 这里的稳定性是指模型问题的解对初始数据的敏感度, 也就是说, 解因为初始数据的微小改变而产生的变化, 变化越小越稳定. 一个典型的多项式问题: $$ p(x) = \prod_{n=1}^7(x-n)=x^7-28x^6+322x^5 -1960x^4-12132x^2+13068x-5040 $$ 多项式 $p(x)$ 的根对系数非常敏感, 例如, 将 28 变为 28.002, 那么原来的根 $x=5,6$ 就变成了两个复数根 $x=5.459\pm 0.54i$. 这种问题通常称为不稳定的或者病态的.
效率. 以线性系统的迭代求解为例, 从传统的 Jacobi 迭代到共轭梯度, 再到各种 Gmres 迭代预处理子, 体现了数值分析追求高效算法的执着. 现代数值分析的发展过程就是不断寻找更加优秀的算法的过程. 另外, 高斯消去求解 $n$-阶线性方程组的算法复杂度为 $O(n^3)$, 与其它算法比较, 是更快还是精度更高? 如果你能发现某个算法比现在的优秀, 那么数值分析学者们是非常感兴趣的.
我们主要的任务就是计算那些典型的理论上不可计算的问题, 并以光速实现它. —- Lloyd N. Trefethen, Cornell University
误差. 当数值离散或者求解一个连续问题时, 理解误差的生成及传播过程成为数值分析过程的重点, 更好的理解可以为减少误差提供突破口. 通常所说的误差分析也称为”前向误差估计”, 它是指数值求解过程中产生的误差, 典型的问题如数值积分, 微分方程数值解等. 例如, 积分 $I=\int_{0}^1 f(x) dx$ 的一个数值近似记为 $I_h$, 那么对误差 $|I-I_h|$ 的估计就是前向估计. 后向误差估计是对算法的反向分析, 将数值解看作是原模型问题的扰动问题的真实解, 也就是说原问题中的变量必须怎样变化才能得到数值解. 后向误差估计作为一般地分析工具, 对理解误差的传播和为改进算法提供了思路, 极具意义. 更多地内容可以参考在后验估计发展中的里程碑人物 J. H. Wilkinson 的工作.
利用已有算法得到的数值解的反馈来改进算法. 一般情况下, 虽然我们不完全清楚数学模型的数学特性, 但是已有的算法提供的近似解可以让我们对问题有一个更趋近真实的理解, 也容易找到改进算法的途径. 例如, 自适应有限元方法就是根据已有的数值解对有限元网格或者多项式次数进行改变, 从而提高求解精度.

研究内容

数值分析的研究领域非常广泛, 并且由于现代种类交叉学科的发展, 数值分析的边界变得越来越模糊. 但是主要的内容包含如下几个方面.

数值线性代数

主要研究内容主要涉及线性方程组算法研究, 特征值和相关数值算法研究.

线性方程组产生于对线性问题的离散或者对非线性问题的线性化离散, 对它的求解成为数值分析的基础内容. 一般来说, 数值方法离散的问题, 如偏微分方程, 会得到一系列大型稀疏线性系统. 对于规模不太大的线性系统直接算法, 如高斯消去方法和它的改进方法类, 比较合适, 他们理论上可以在有限步数内得到精确解. 但是, 因为计算机在表示实数时存在机器误差, 一般不会得到绝对相同的真实解, 并且数值解与真实解的误差一般会随矩阵的规模增大而增大. 对于大型或超大型线性系统, 迭代求解可能是更好的选择. 迭代方法一般会利用合适的预处理子得到一系列数值解, 这些数值解关于迭代次数以某种收敛速度趋于真实解. 比较经典的方法有共轭梯度 (CG), 广义极小残差 (Gmres) 等.

特征值问题是数值分析的最重要课题之一, 其主要目标是寻求高效且稳定的数值算法. 基本问题表述如下: 求 $(x,\lambda)\in \mathbb{R}^n\times \mathbb{R}, \lambda\neq 0$ 使得 $ Ax = \lambda x .$ 特征值问题经常被用在许多数学问题的求解中, 从而对模型问题反应的现象进行解释. 一个简单的应用是一阶常微分方程组的求解过程, 如问题 $$ \textbf{y}^\prime = A \textbf{y},\quad \text{等价为}\ \begin{bmatrix} y_1^\prime\\ y_2^\prime\end{bmatrix}=\begin{bmatrix} -0.02 & 0.02\\ 0.02 & -0.02\end{bmatrix}=\begin{bmatrix} y_1\\ y_2\end{bmatrix}. $$ 利用矩阵特征值和特征向量可以对角化, 从而得到 $A=PDP^{-1}$, 那么定义 $\textbf{x}=P^{-1} \textbf{y}$, 上述问题可以表述为 $$ \textbf{x}^\prime = D \textbf{x} = \begin{bmatrix} \lambda_1 & \\ & \lambda_2 \end{bmatrix}\textbf{x} , $$ 这个问题的通解可以容易得到 $x_1=C_1 e^{\lambda_1 t}, x_2=C_2 e^{\lambda_2 t}$, 然后再利用关系 $\textbf{x}=P^{-1} \textbf{y}$ 就可以得到原问题的通解了.

另外值得说明的是, 很多特征值形式的微分方程数值解法, 如有限元, 得到的线性系统就是一个大规模的矩阵特征值问题, 在许多研究领域如力学问题, 光子晶体等. 经典的数值方法有幂法, QR 方法, Jacobi 方法和 Lanczos 方法等等.

非线性方程组

非线性方程组的求解一般是以一系列近似的线性问题为工具, 经典的方法包括二分法, 不动点迭代, 最速下降法和牛顿法等. 以经典的牛顿法为例, 非线性方程的求根问题 $f(x)=0$, 假设根的一个近似解为 $x_0$, 那么可以利用下面的公式得到一组近似解: $$ x^{(k+1)} = x^{(k)}-\frac{f(x^{(k)})}{f'(x^{(k)})},\quad k=0,1,2,\ldots $$ 因为牛顿法对初值的精度要求比较高, 所以一般可以先利用收敛速度较慢的方法, 如二分法或最速下降法, 得到一个精度相对高的解作为牛顿法的初值, 从而提高求解速度. 当我们求解一个非线性方程组时, 例如 $n$-阶 $\textbf{f}(\textbf{x})=0, \textbf{x}\in \mathbb{R}^n$, 对应的牛顿方法就变成了 $$ \textbf{x}^{(k+1)} = \textbf{x}^{(k)}-[f'(\textbf{x}^{(k)})]^{-1} \textbf{f}(\textbf{x}^{(k)}),\quad k=0,1,2,\ldots $$ 其中, $[f'(\textbf{x}^{(k)})]$ 表示方程的 Jacobian 矩阵, 大小为 $n\times n$. 所以, 每一步牛顿迭代都需要求解一个 $n\times n$ 线性系统.

逼近理论

逼近理论主要考虑如何利用简单的函数来逼近复杂函数, 并且如何给出定量误差估计. 一般情况下逼近问题可以陈述如下:

给定测度空间 $X$ 和它的一个子空间 $Y$, 对某个元素 $x\in X$, 是否存在唯一的元素 $y\in Y$ 使得 $\|x-y\|=\min_{z\in Y}\|x-z\|$?

这样的抽象问题可以适用许多逼近问题, 例如, 考虑函数 $f(x),x\in \mathbb{R}$ 在多项式空间中的最佳逼近问题: $$ \min_{p\in \mathcal{P}_{k}(0,1)} \| f-p\|_{C(a,b)}. $$ 另外, 有限元理论中经常用到多项式的拟最佳逼近性质, 即存在一个常数 $C>0$ 使得如下的收敛性质成立 $$ \min_{p\in \mathcal{P}_{k}(a,b)} \| f-p\|_{L^2(a,b)} \leq C |b-a|^{k+1} |f|_{H^{k+1}(a,b)}; $$ 当把 $|b-a|$ 越小时, 函数越可以被更好的逼近, 误差以 $O(h^{k+1})$ 的速度减小. 理论证明构成了有限元方法收敛的数学基础, 其相关收敛性理论仍在发展完善中.

微分积分方程数值解

产生于自然科学和工程领域的数学模型大部分都基于常微分方程, 偏微分方程和积分方程, 并且绝大部分方程都是不能找到解析解的, 必须利用数值方法求解. 对于常微分方程的初值问题, 数值求解方法和理论分析相对简单, 主要是利用差商代替导数, 最经典的方法有 Euler, Runge-Kutta, Adams 以及预估较正 (Predictor-Corrector) 方法等. 偏微分方程的数值求解相对复杂的多, 方法也多种多样, 其中几乎每一个方法都是一个计算数学研究中比较大的分支, 内容丰富. 通常, 常微分方程的边值问题被认为是偏微分方程问题的一个类型.

偏微分方程的数值解法多样. 有限差分是基于差商代替微商的思想. 有限元方法大体上来说理论上是基于变分原理并利用多项式逼近真实解的一类方法, 具有高精度和高效率的特点; 包含协调元, 混合有限元, 间断有限元, 谱方法, 无网格方法, 多重网格, 域分解方法以及近年来出现的虚拟元方法, 弱有限元方法等等, 内容丰富程度可见一斑. 有限体积法常被用于计算流体领域.

现代发展

应用领域

数值分析因现实问题而生, 也因计算机算力的快速增长, 人类社会和复杂工程的快速发展而蓬勃发展, 在现今和未来的科学发展中扮演越来越重要的角色.

计算机辅助设计 (英语：Computer Aided Design, CAD) 是指运用电脑软件制作并模拟实物设计, 展现实体部件的三维模型或二维图纸的详细工程, 贯穿于整个工程过程. 最早的应用是在汽车制造、航空航天以及电子工业; 现在, CAD已经成为计算机辅助技术中一个特别重要的技术, 具有降低产品开发成本、大大缩短设计周期等优点. CAD 制造是工程领域中的重要工具, 包含极其广泛的数学模型和数值算法实现, 是数值分析的典型应用.

大气建模在模拟大气层行为方面极其重要, 从而也另理解人类对大气的影响成为可能, 当然也使得天气预报越来越准确. 我们引用 Wikipedia 上关于大气建模的描述:

大气模型是围绕控制大气运动的全部原始动力学方程所建立的数学模型. 它可以用湍流扩散、辐射、湿过程(云和降水)、热交换、土壤、植被、地表水、地形运动效应和对流的参数化补充这些方程。大多数大气模型是数值的, 即离散的运动方程. 它们可以预测微尺度的现象, 如龙卷风和边界层涡旋, 建筑上的亚微尺度湍流, 以及天气流和全球流. 模型的水平域可以是覆盖整个地球的全球域，也可以是只覆盖部分地球的区域域(有限区域).>预报是利用大气物理和动力学的数学方程来计算的, 这些方程是非线性的, 不可能精确求解. 因此, 必有使用数值方法求解. 不同的模型使用不同的解决方法. 全球模式通常在水平维度上使用谱方法, 在垂直维度上使用有限差分方法，而区域模式通常在三个维度上都使用有限差分方法. 对于特定地点, 模式输出统计数据使用气候信息、数值天气预测的输出和当前地面天气观测来建立统计关系, 以解决模式偏差和分辨率问题. —-大气模型 (Atmospheric model, Wikipedia).

大气建模一般需要考虑许多个变量, 如速度, 密度, 压力和温度等等, 包含大量的数值分析方法, 包括建模, 计算流体力学和微分方程数值解等等.

计算金融是数值计算的一个重要领域. 现代商业需要利用大量的最优化方法来决定最优的资源分配. “在今天的金融市场上，大量相互依赖的资产由位于不同地点和时区的大量相互作用的市场参与者进行交易。它们的行为具有前所未有的复杂性，这些高度多样化的投资所固有的风险的表征和评估通常基于复杂的数学和计算模型。以封闭的形式精确地解决这些模型，即使在单一的仪器级别，通常是不可能的，因此我们必须寻找有效的数值算法。最近，这一问题变得更加紧迫和复杂，因为信贷危机清楚地表明了级联效应的作用，从单一工具到单一机构的投资组合，甚至到相互关联的交易网络。要理解这一点，需要采用多尺度和整体的方法，将市场、信贷和流动性风险等相互依赖的风险因素在不同的相互关联的尺度上同时建模。—-Wikipedia.”

计算科学与工程 (Computational science and engineering, CSE) 是一种相对新的学科，涉及计算模型和仿真的开发和应用，通常与高性能计算相结合，以解决工程分析和设计（计算工程）中出现的复杂物理问题作为自然现象（计算科学）。 CSE被描述为“第三种发现模式”（理论和实验旁边）。[12]在许多领域，计算机模拟是一体的，因此对业务和研究至关重要。计算机仿真提供了进入传统实验无法访问的字段的能力，或者进行传统的实证查询的情况下非常昂贵。 CSE既不应该与纯电脑科学，也不会与计算机工程混淆，尽管前者中的宽域用于CSE（例如，某些算法，数据结构，并行编程，高性能计算）以及后者中的一些问题用CSE方法建模和解决（作为应用区）。(Wikipedia)

其它的应用领域还包括计算生物学, 城市复杂系统等, 甚至机器学习和人工智能也和数值分析关系密切.

总结

数值分析, 就课程来说, 是研究解决一些数学问题的数值算法的学科, 包括算法分析, 实现, 精度及稳定性等内容; 本科阶段学习的数值分析课程主要内容有: 插值法和函数逼近理论, 数值积分和数值微分, 解线性方程组的直接方法和矩阵迭代法, 逼近特征值, 非线性方程(组)求根, 常微分方程的数值解法等. 还有的教材会介绍求解偏微分方程的差分和有限元方法, 当然几乎每一块内容都可以单独拉出来写本书, 数值分析的标准教材中都会覆盖这些基本内容, 掌握这些基本内容也就打好基础了, 以后学习数值分析的其它进阶课程就容易入门了. 这门课程要求的基础课程不多, 一般来说, 具备数学分析(高等数学)及高等代数(线性代数)的基本内容就可以了, 当然还要熟悉至少一门计算机语言.

就数学分支来说, 数值分析有一个更贴切的名字–计算数学. 如果想继续学习一些深入内容或者延伸学科(如微分方程数值解, 计算物理, 计算生物等), 以下数学课程也是必备的: 实分析, 泛函分析, 常微分方程, 偏微分方程等数学基础课程.

学习建议

本科要求学习的数值分析课程是将来学习计算数学其它分支的基础, 所以本科阶段的主要任务就是熟悉该课程的基本内容, 尤其要掌握一些重要的数值算法, 以便将来遇到问题知道到哪去查找.
重在实践. 数值分析的学习不同于其它理论课程, 它有自己的独特性: 算法的分析与实验验证. 本科遇到的包含算法内容的课程还有最优化理论及运筹学, 这些课程的学习始终离不开上机实验, 所以要有自己擅长的一门计算机语言 (`C`, `Fortran`, `Python` 等), 另外, 利用诸如`MATLAB` 等符号语言做数值验证是非常方便的, 有时候是也是必要的. 如果在本科阶段能适应 Linux 上工作就再好不过了.
数学的学习与其它任何学科的学习都一样, 切记贪多嚼不烂这句话.
广泛阅读相关领域的最新成果, 扩展知识面, 了解最新进展.

教材推荐

数值分析入门教材

Richard, Numerical Analysis (7th) (有影印版,教育部高等教育司推荐,非常适合入门的经典)
M. T. Heath, 科学计算导论(2th), 清华大学出版社, 2005.
(美)杰拉尔德, 应用数值分析(7th), 机械工业出版社, 2006.
Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2nd ed.), New York: John Wiley \& Sons.
Golub, Matrix Computations(4th) (有人说这是数值线性代数中的圣经, 进阶课程).
Trefethen, Numerical Linear Algebra, 也是经典.
李庆扬等, 数值分析 (第5版) 清华大学出版社, 2010.
蒋尔雄, 赵风光, 数值逼近, 复旦大学出版社, 2008.
徐树方等, 数值线性代数 (第2版), 北京大学出版社, 2013.
宋叶志等, Fortran95/2003科学计算与工程, 清华大学出版社, 2010.
张若愚, Python科学计算, 清华大学出版社, 2012.

逼近理论

Achieser, N. I. Theory of Approximation. New York: Dover, 1992.
Lloyd N. Trefethen. Approximation Theory and Approximation Practice, Extended Edition. SIAM, 2019.
Elliott Ward Cheney, William Allan Light. A Course in Approximation Theory. American Mathematical Soc., 2009.
David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
王仁宏. (2012). 数值逼近. 第2版. 高等教育出版社.
蒋尔雄, 赵风光. (1996). 数值逼近. 复旦大学出版社.

微分方程数值解

Quarteroni, A., & Valli, A. (1994). Numerical Approximation of Partial Differential Equations. In Mathematics of Computation (1st ed.).
Hackbusch, W. (2017). Elliptic Differential Equations: Theory and Numerical Treatment (Second Edition). Germany: Springer-Verlag.
Fortin, M., & Brezzi, F. (1991). Mixed and Hybrid Finite Element Methods. In Springer (Vol. 15).
Boffi, D., Brezzi, F., & Fortin, M. (2013). Mixed Finite Element Methods and Applications (Vol. 44).
Brenner, S. C., & Scott, L. R. (2008). The Mathematical Theory of Finite Element Methods (Third).
Jovanović, B. S., & Süli, E. (2014). Analysis of Finite Difference Schemes. In Finite Difference Schemes and Partial Differential Equations.
Di Pietro, D. A., & Ern, A. (2012). Mathematical Aspects of Discontinuous Galerkin Methods.
Rivière, B. (2008). Discontinuous Galerkin Methods for Solving Elliptic and Parabolic Equations.
李荣华, 刘播. (1997). 微分方程数值解法. 东南大学出版社.
陈文斌. (2014). 微分方程数值解. 复旦大学出版社.
石钟慈, 王鸣. (2010). 有限元方法. 北京: 科学出版社.
张铁. (2015). 间断有限元理论与方法. 修订版. 科学出版社.
张文生. (2015). 微分方程数值解:有限差分理论方法与数值计算. 科学出版社.

参考文献

谈谈计算数学
赵金熙: 浅谈计算数学的过去和未来
朱少平. 浅谈科学计算[J]. 物理, 2009(08):545-551.
S. Hammarling and N. Higham. Wilkinson and Backward Error Analysis, NLA Groupe. 2019.
Kendall E. Atkinson. Numerical Analysis.
Approximations of Pi. Wikipedia.
数值分析研究的主要内容列表

分享到:

数值分析大巴

数值分析

什么是数值分析

历史背景

基本思想