数值计算
序言。
第一部分：一元方程根
| 介值定理与二分法 | 数值求解一般都是采用迭代的方式不断接近解，二分法就是其中一种常用的方法。它有一个重要的特性，就是一定收敛，但会比较慢。 [Bisection] |
| 中值定理与牛顿法 | 牛顿法的逻辑甚至比二分法更简单，只要一直调用迭代关系式就可以了。它不一定能收敛，但只要初值选的合适，收敛起来就很快。 [NewtonRaphson] |
|
巴拿赫不动点定理 (Banach Fixed-Point Theorem) |
对于一个求方程根 \(f(x) = 0\) 的问题，我们可以有无数种方案，将其转换成一个不动点 \(x = g(x)\) 的问题。 上一节中介绍的牛顿法，实际上就是这种不动点的迭代过程。 [NaiveFixedPoint] [AitkenSteffensen] |
| Brent求根方法 | Brent 方法在效率和可靠性之间做了完美的取舍，不需要求导数，各大主流科学计算平台和工程软件库都在使用它。本文我们从割线法开始，不断改进，直至 Brent 方法。 [SecantRoot] [FalsePosition] [DekkerRoot] [BrentRoot] |
第二部分：一元多项式
| 一元多项式 | 本节我们介绍计算多项式函数值的嵌套乘法，初步讨论利用收缩约化技术求解多项式方程所有根的方法，以及一元二次多项式方程的求根公式。 [Polynomial] |
| 多项式的四则运算 | 加法和减法互为逆运算，定义和实现也很简单。乘法与加法构成分配率，也比较直观。除法并不是乘法的逆运算，它对多项式并不是封闭的，概念相对复杂一些。 [加] [减] [乘] [长除] [综合除] |
| 多项式方程求根 | Müller 算法通过二次插值公式提供了求解复数根的方法，在复数域上每次只能求出一个根，但可以通过综合除法约简，逐个计算出所有根。 [实数域Müller] [复数域Müller] [复数域AllRoots] |
| 拉格朗日多项式 | 给定一组采样点，可以很容易构造出 Lagrange 插值多项式。它可以将复杂的函数转化为易于处理的插值多项式，是数值积分和微分的理论基础。 [LagrangeInterpolation] [LagrangePolynomial] [龙格现象] |
| 重心拉格朗日插值 | 本文对传统的拉格朗日多项式做了简单变形，得到了重心 Lagrange 插值公式。该公式不仅在数学上很优雅，在工程上它也是十分高效，并且极致稳定。 [BarycentricLagrange] |
| 牛顿差商多项式 | 和重心拉格朗日一样， 牛顿差商也需要 \(O(n^2)\) 的初始化，之后就可以在 \(O(n)\) 的时间里完成插值运算了。只是牛顿差商的初始化过程是在构造差商表，求值的时候是通过嵌套乘法完成的。 [NewtonDividedDifference] |
| Hermite插值多项式 | Hermite 插值多项式不仅要求在采样点上与原函数相同，还要求它们的一阶导数也相同，即所谓的 \(C^1\) 连续性。这样通过多个插值低次多项式拼接的时候再连接点处就会丝滑过渡。 [HermiteInterpolation] [HermiteDividedDifference] |
| 分段三次Hermite插值 | 在工程实际中，出于数值稳定性以及龙格现象的考虑，常用分段的低次多项式来完成插值。 由于 Hermite 插值多项式可以保证 \(C^1\) 的连续性，人们常用它在两个采样点之间构造三次多项式。 [PieceCubicHermite] |
| 三次样条插值 | 三次样条插值是一种典型的由工业驱动的数学建模。它本质上仍然是分段三次 Hermite 插值，只是并不需要提供采样点的一阶导数， 而是根据 \(C^2\) 连续的约束求解线性方程组得到的。 [CubicSpline] |
第三部分：数值积分
| 数值微分与Richardson外展 | 本文一方面是体会一下数值计算中的截断误差和舍入误差， 另一方面是介绍 Richardson 外展的思想，它将在数值积分问题中大放异彩。 [NumericalDifference] |
| Lagrange多项式数值积分 | 数值积分通过对离散数据点的加权求和来近似计算连续的定积分。插值多项式是最经典的构造数值积分的方法。 本节我们借助拉格朗日多项式来初步探讨一下数值积分。 [LagrangePolynomialIntegral] [CompositeTrapeRule] [CompositeSimpsonRule] |
| Romberg积分 | 由于数值积分并不需要除以本身就很微小的采样步长 \(h\)，所以数值稳定，Richardson 外展能在这个问题上发挥极大的作用。Romberg 积分就是这样的数值积分方法。 [RombergIntegration] |
| 高斯积分 | 高斯积分抛弃了固定的采样步长，以勒让德多项式的零点作为采样点，取得了 \(2n - 1\) 的代数精度。 [LegendrePolynomial] [GaussianIntegration] |