=================================== 数值分析 =================================== 0. 要点汇总 ==================== 本篇文章的要点整理如下 - 绝对误差：\|x - x*|，近似值与真实值的差的绝对值 - 相对误差：\|x - x*\|/\|x|，绝对误差与真实值的比值 - 有效数字：从第一个非零数字开始，到误差不超过半个单位的那一位为止 - 截断误差：用有限过程近似无限过程产生的误差，如用有限项级数近似无限级数 - 舍入误差：由于计算机有限字长产生的误差 - 误差传播：运算过程中误差的累积和放大 - 条件数：衡量问题对输入误差敏感程度的指标 - 病态问题：条件数很大，输入误差会被严重放大的问题 - 二分法：利用区间缩减法求根，收敛速度较慢但稳定 - 牛顿法：利用函数的切线逼近，收敛速度快（二阶收敛） - 割线法：用差商近似导数，不需要计算导数 - 高斯消元法：将方程组化为上三角形式，然后回代求解 - LU分解：将矩阵分解为下三角矩阵和上三角矩阵的乘积 - 迭代法：通过迭代逐步逼近解，如雅可比迭代、高斯-赛德尔迭代 - 条件数cond(A) = \|\|A\|\| · \|\|A⁻¹\|\|，衡量线性方程组对误差的敏感度 - 拉格朗日插值：利用多项式通过所有已知点 - 牛顿插值：利用差商构造插值多项式，便于增加节点 - 样条插值：用分段多项式进行插值，保证平滑性 - 数值微分：用差商近似导数 - 数值积分：用求和近似积分，如梯形公式、辛普森公式 - 高斯求积：选择最优的求积节点和权重，提高精度 - 欧拉法：最简单的数值解法，一阶精度 - 龙格-库塔法：高精度的数值解法，常用四阶龙格-库塔（RK4） - 亚当斯方法：多步法，利用前几步的信息 - 刚性方程：解中包含变化极快和变化极慢的分量 - 稳定性：数值方法在步长趋于零时能否收敛到精确解 - 绝对稳定性：数值方法能否控制舍入误差的增长 1. 误差分析 =================================== 1.1 误差的基本概念 --------------------- **误差的来源** 在科学计算中，误差主要来源于以下几个方面： 1. **模型误差**：数学模型是对实际问题的简化，与真实情况存在差异 2. **观测误差**：实验数据本身包含测量误差 3. **截断误差**：用有限过程近似无限过程产生的误差 4. **舍入误差**：由于计算机有限字长产生的误差 **绝对误差** 设x是精确值，x*是近似值，则绝对误差定义为： .. math:: e_a = |x - x^*| **相对误差** 相对误差定义为： .. math:: e_r = \frac{|x - x^*|}{|x|} 相对误差更能反映近似的精度，特别是在处理数量级差异较大的数据时。 **有效数字** 如果近似值x*的绝对误差不超过某一位数字的半个单位，则从该位数字起，到x*的最左端非零数字止的所有数字都称为有效数字。 例如：π ≈ 3.14159，绝对误差为0.000005，因此3.14159有6位有效数字。 1.2 误差传播 --------------------- **算术运算的误差传播** 设x和y的近似值为x*和y*，误差为e(x)和e(y)，则： 1. **加法**： :math:`e(x + y) ≈ e(x) + e(y)` 2. **减法**： :math:`e(x - y) ≈ e(x) + e(y)` （注意：相近数相减会严重损失精度） 3. **乘法**： :math:`e(xy) ≈ |y|e(x) + |x|e(y)` 4. **除法**： :math:`e(x/y) ≈ e(x)/|y| + |x|e(y)/y²` **函数的误差传播** 对于函数y = f(x₁, x₂, ..., xₙ)，误差传播公式为： .. math:: e(y) \approx \sum_{i=1}^{n} \left|\frac{\partial f}{\partial x_i}\right| e(x_i) **条件数** 条件数衡量问题对输入误差的敏感程度。对于函数f(x)，条件数定义为： .. math:: \text{cond}(f) = \frac{|x \cdot f'(x)|}{|f(x)|} 条件数大的问题称为病态问题，输入的微小误差会导致输出的巨大误差。 1.3 舍入误差分析 --------------------- **浮点数表示** 计算机中的浮点数采用IEEE 754标准 ，表示为： .. math:: x = \pm d_0.d_1d_2\cdots d_{p-1} \times \beta^e 其中： - β是基数（通常为2） - p是精度（有效数字位数） - e是指数 **机器精度** 机器精度ε是满足1 + ε > 1的最小正数，它反映了浮点数的表示精度。 对于双精度浮点数，ε ≈ 2.22 × 10^(-16)。 **舍入误差** 由于计算机只能表示有限精度的数，实际计算中的舍入误差约为O(ε)。 **避免舍入误差的策略** 1. 避免两个相近数相减（会产生灾难性抵消） 2. 避免大数加小数（小数会被"吃掉"） 3. 选择数值稳定的算法 4. 使用高精度计算 2. 非线性方程求根 =================================== 2.1 二分法 --------------------- **基本原理** 二分法利用连续函数的介值定理：如果f(x)在区间[a, b]上连续，且f(a)f(b) < 0，则f(x)在(a, b)内必有零点。 **算法步骤** 1. 给定区间[a, b]，满足f(a)f(b) < 0 2. 计算中点c = (a + b)/2 3. 如果f(c) = 0或区间长度足够小，停止迭代 4. 如果f(a)f(c) < 0，则b = c；否则a = c 5. 返回步骤2 **收敛性** 二分法必定收敛，且每次迭代将区间长度减半。经过n次迭代后，误差不超过： .. math:: |x_n - x^*| \leq \frac{b - a}{2^n} **收敛速度** 二分法的收敛速度是线性的（阶数为1）。 **优缺点** 优点： - 算法简单 - 必定收敛 - 对函数性质要求低（只需连续） 缺点： - 收敛速度慢 - 不能求重根 - 需要已知有根区间 2.2 牛顿法 --------------------- **基本原理** 牛顿法利用函数的切线逼近零点。在点xₙ处作切线，切线与x轴的交点作为新的近似值。 **迭代公式** .. math:: x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} **收敛速度** 如果f'(x*) ≠ 0，牛顿法的收敛速度是二阶的： .. math:: |x_{n+1} - x^*| \approx \frac{|f''(x^*)|}{2|f'(x^*)|}|x_n - x^*|^2 这意味着每次迭代有效数字大约翻倍。 **优缺点** 优点： - 收敛速度快（二阶收敛） - 算法简单 缺点： - 需要计算导数 - 对初始值敏感，可能不收敛 - 不能求重根（收敛速度退化为线性） .. container:: example-box **例题** 用牛顿法求f(x) = x² - 2 = 0的正根。 f'(x) = 2x 迭代公式：x_(n+1) = x_n - (x_n² - 2)/(2x_n) = (x_n + 2/x_n)/2 取x₀ = 1： x₁ = (1 + 2/1)/2 = 1.5 x₂ = (1.5 + 2/1.5)/2 ≈ 1.4167 x₃ ≈ 1.4142 x₄ ≈ 1.4142（已收敛） 2.3 割线法 --------------------- **基本原理** 割线法用差商近似导数，避免计算导数。利用两个点(xₙ, f(xₙ))和(x_(n-1), f(x_(n-1)))的割线与x轴的交点作为新的近似值。 **迭代公式** .. math:: x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})} **收敛速度** 割线法的收敛速度约为1.618（黄金分割比），介于线性和二阶之间。 **优缺点** 优点： - 不需要计算导数 - 收敛速度较快 缺点： - 需要两个初始值 - 收敛速度不如牛顿法 2.4 收敛性分析 --------------------- **收敛阶** 迭代法x_(n+1) = g(xₙ)的收敛阶p定义为满足以下关系的最小正数： .. math:: \lim_{n \to \infty} \frac{|x_{n+1} - x^*|}{|x_n - x^*|^p} = C 其中C ≠ 0。 - p = 1：线性收敛 - p > 1：超线性收敛 - p = 2：二次收敛 **收敛条件** 如果|g'(x*)| < 1，则迭代法局部收敛。 如果|g'(x*)| = 0且g''(x*) ≠ 0，则迭代法二阶收敛。 3. 线性方程组的数值解法 =================================== 3.1 高斯消元法 --------------------- **基本思想** 通过行变换将系数矩阵化为上三角矩阵，然后回代求解。 **算法步骤** 1. 消元过程：将系数矩阵A化为上三角矩阵U 2. 回代过程：从最后一行开始，依次求解各变量 **选主元** 为了避免数值不稳定，需要进行选主元： - **部分选主元**：在当前列中选择绝对值最大的元素作为主元 - **完全选主元**：在未处理的子矩阵中选择绝对值最大的元素作为主元 **计算复杂度** 高斯消元法的计算复杂度为O(n³)。 .. container:: example-box **例题** 用高斯消元法求解方程组： 2x₁ + x₂ - x₃ = 1 4x₁ + 3x₂ - x₃ = 3 8x₁ + 7x₂ - 3x₃ = 7 增广矩阵： [2 1 -1 | 1] [4 3 -1 | 3] [8 7 -3 | 7] 消元： [2 1 -1 | 1] [0 1 1 | 1] [0 3 1 | 3] [2 1 -1 | 1] [0 1 1 | 1] [0 0 -2 | 0] 回代：-2x₃ = 0 → x₃ = 0 x₂ + x₃ = 1 → x₂ = 1 2x₁ + x₂ - x₃ = 1 → 2x₁ = 0 → x₁ = 0 3.2 LU分解 --------------------- **基本思想** 将矩阵A分解为下三角矩阵L和上三角矩阵U的乘积：A = LU **LU分解的形式** .. math:: \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix} **求解方程组** 解Ax = b等价于解LUx = b： 1. 解Ly = b（前向替换） 2. 解Ux = y（回代） **优势** 当需要求解多个具有相同系数矩阵但不同右端项的方程组时，LU分解特别有效，因为只需要分解一次。 **计算复杂度** LU分解的计算复杂度为O(n³)，但分解后求解每个方程组只需O(n²)。 3.3 迭代法 --------------------- **雅可比迭代** 对于方程组Ax = b，将A分解为A = D - L - U，其中D是对角矩阵，L是下三角矩阵，U是上三角矩阵。 雅可比迭代公式： .. math:: x^{(k+1)} = D^{-1}(L + U)x^{(k)} + D^{-1}b 分量形式： .. math:: x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j \neq i} a_{ij}x_j^{(k)}\right) **高斯-赛德尔迭代** 高斯-赛德尔迭代利用最新更新的值： .. math:: x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j < i} a_{ij}x_j^{(k+1)} - \sum_{j > i} a_{ij}x_j^{(k)}\right) **收敛条件** 如果A严格对角占优（每行对角元素的绝对值大于该行其他元素绝对值之和），则雅可比迭代和高斯-赛德尔迭代都收敛。 **比较** - 高斯-赛德尔迭代通常比雅可比迭代收敛更快 - 高斯-赛德尔迭代可以并行化程度较低 3.4 条件数与稳定性 --------------------- **矩阵的条件数** 矩阵A的条件数定义为： .. math:: \text{cond}(A) = \|A\| \cdot \|A^{-1}\| 常用的矩阵范数是2-范数（谱范数）： .. math:: \|A\|_2 = \sqrt{\lambda_{\max}(A^TA)} 其中λ_max是最大的特征值。 **条件数的意义** 条件数反映了线性方程组Ax = b对误差的敏感程度。 如果cond(A)很大，则称矩阵A是病态的，右端项b的微小误差会导致解x的巨大误差。 **误差估计** .. math:: \frac{\|\Delta x\|}{\|x\|} \leq \text{cond}(A)\frac{\|\Delta b\|}{\|b\|} .. container:: example-box **例题** 对于Hilbert矩阵Hₙ（H(i,j) = 1/(i + j - 1)），条件数随n增长极快。 H₃的条件数约为524 H₄的条件数约为1.5 × 10⁴ H₅的条件数约为4.8 × 10⁵ 这说明Hilbert矩阵是严重病态的。 4. 插值与逼近 =================================== 4.1 拉格朗日插值 --------------------- **基本思想** 给定n + 1个点(x₀, y₀), (x₁, y₁), ..., (xₙ, yₙ)，构造n次多项式Pₙ(x)通过所有这些点。 **拉格朗日基函数** .. math:: L_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} 基函数满足：Lᵢ(xⱼ) = δᵢⱼ（克罗内克δ） **插值多项式** .. math:: P_n(x) = \sum_{i=0}^{n} y_i L_i(x) **性质** - Pₙ(x)是次数不超过n的多项式 - Pₙ(xᵢ) = yᵢ（插值条件） - 插值多项式唯一 **误差估计** 如果f(x)在[a, b]上n + 1阶连续可导，则： .. math:: |f(x) - P_n(x)| \leq \frac{M}{(n + 1)!}|\omega_{n+1}(x)| 其中M是|f^(n+1)(x)|在[a, b]上的最大值，ω_(n+1)(x) = ∏(x - xᵢ)。 **龙格现象** 当插值节点增多时，插值多项式在区间边缘可能出现剧烈振荡。这种现象称为龙格现象。 4.2 牛顿插值 --------------------- **基本思想** 利用差商构造插值多项式，便于增加节点。 **差商的定义** 零阶差商：f[xᵢ] = f(xᵢ) 一阶差商：f[xᵢ, xⱼ] = (f(xⱼ) - f(xᵢ))/(xⱼ - xᵢ) 二阶差商：f[xᵢ, xⱼ, xₖ] = (f[xⱼ, xₖ] - f[xᵢ, xⱼ])/(xₖ - xᵢ) **牛顿插值公式** .. math:: P_n(x) = f[x_0] + f[x_0, x_1](x - x_0) + f[x_0, x_1, x_2](x - x_0)(x - x_1) + \cdots **优势** - 增加节点时不需要重新计算所有系数 - 便于分析误差 4.3 样条插值 --------------------- **基本思想** 用分段低次多项式进行插值，保证连接处的光滑性。 **三次样条** 三次样条插值在每个区间[xᵢ, x_(i+1)]上用三次多项式Sᵢ(x)，满足： 1. 插值条件：Sᵢ(xᵢ) = yᵢ，Sᵢ(x_(i+1)) = y_(i+1) 2. 连续性：Sᵢ(x_(i+1)) = S_(i+1)(x_(i+1)) 3. 一阶导数连续：Sᵢ'(x_(i+1)) = S_(i+1)'(x_(i+1)) 4. 二阶导数连续：Sᵢ''(x_(i+1)) = S_(i+1)''(x_(i+1)) 5. 边界条件：S₀''(x₀) = S_(n-1)''(xₙ) = 0（自然样条） **优势** - 避免了龙格现象 - 光滑性好（二阶连续可导） - 逼近精度高 4.4 最小二乘逼近 --------------------- **基本思想** 当数据点较多时，不要求多项式通过所有点，而是最小化误差的平方和。 **问题表述** 给定数据点(x₁, y₁), (x₂, y₂), ..., (xₙ, yₙ)，求m次多项式Pₘ(x)使得： .. math:: \min \sum_{i=1}^{n} [P_m(x_i) - y_i]^2 **正规方程** 设Pₘ(x) = a₀ + a₁x + ... + aₘxᵐ，则系数满足： .. math:: \begin{bmatrix} n & \sum x_i & \sum x_i^2 & \cdots & \sum x_i^m \\ \sum x_i & \sum x_i^2 & \sum x_i^3 & \cdots & \sum x_i^{m+1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \sum x_i^m & \sum x_i^{m+1} & \sum x_i^{m+2} & \cdots & \sum x_i^{2m} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_m \end{bmatrix} = \begin{bmatrix} \sum y_i \\ \sum x_i y_i \\ \vdots \\ \sum x_i^m y_i \end{bmatrix} **应用** 最小二乘法广泛应用于数据拟合、参数估计、机器学习等领域。 5. 数值积分与微分 =================================== 5.1 数值微分 --------------------- **基本思想** 用差商近似导数。 **向前差分** .. math:: f'(x) \approx \frac{f(x + h) - f(x)}{h} 误差：O(h) **中心差分** .. math:: f'(x) \approx \frac{f(x + h) - f(x - h)}{2h} 误差：O(h²) **二阶导数** .. math:: f''(x) \approx \frac{f(x + h) - 2f(x) + f(x - h)}{h^2} 误差：O(h²) **Richardson外推法** 通过组合不同步长的差分近似，提高精度。 **误差分析** 数值微分的误差来源于两方面： 1. 截断误差：用差商近似导数 2. 舍入误差：由于计算机有限精度 最优步长需要平衡这两种误差。 5.2 牛顿-科特斯公式 --------------------- **基本思想** 用插值多项式的积分近似函数的积分。 **梯形公式** .. math:: \int_a^b f(x)dx \approx \frac{b - a}{2}[f(a) + f(b)] 误差：-[(b - a)³/12]f''(ξ) **辛普森公式** .. math:: \int_a^b f(x)dx \approx \frac{b - a}{6}[f(a) + 4f\left(\frac{a + b}{2}\right) + f(b)] 误差：-[(b - a)⁵/2880]f⁽⁴⁾(ξ) **复合公式** 为了提高精度，将积分区间分割成若干子区间，在每个子区间上应用基本公式。 **复合梯形公式** .. math:: \int_a^b f(x)dx \approx \frac{h}{2}[f(a) + 2\sum_{i=1}^{n-1}f(x_i) + f(b)] 其中h = (b - a)/n，xᵢ = a + ih。 误差：-[(b - a)/12]h²f''(ξ) **复合辛普森公式** .. math:: \int_a^b f(x)dx \approx \frac{h}{3}[f(a) + 4\sum_{i=1}^{n/2}f(x_{2i-1}) + 2\sum_{i=1}^{n/2-1}f(x_{2i}) + f(b)] 误差：-[(b - a)/180]h⁴f⁽⁴⁾(ξ) 5.3 龙贝格积分 --------------------- **基本思想** 通过Richardson外推法加速梯形公式的收敛。 **算法步骤** 1. 计算梯形近似T₀₀, T₁₀, T₂₀, ... 2. 外推：Tₖⱼ = Tₖⱼ₋₁ + (Tₖⱼ₋₁ - Tₖ₋₁ⱼ₋₁)/(4ʲ - 1) 3. 继续外推直到满足精度要求 **优势** - 收敛速度快 - 精度高 - 自适应性强 5.4 高斯求积 --------------------- **基本思想** 选择最优的求积节点和权重，使求积公式对于尽可能高次的多项式精确成立。 **高斯-勒让德求积** 在区间[-1, 1]上的高斯求积公式： .. math:: \int_{-1}^{1} f(x)dx \approx \sum_{i=1}^{n} w_i f(x_i) 其中xᵢ是勒让德多项式Pₙ(x)的零点，wᵢ是对应的权重。 **性质** n个节点的高斯求积公式对2n - 1次多项式精确成立。 **推广** 通过变量替换，可以将高斯求积推广到任意区间[a, b]。 6. 常微分方程的数值解法 =================================== 6.1 欧拉法 --------------------- **基本思想** 用导数在当前点的值近似下一时刻的函数值。 **迭代公式** .. math:: y_{n+1} = y_n + hf(x_n, y_n) 其中h是步长。 **误差分析** - 局部截断误差：O(h²) - 全局截断误差：O(h) **改进欧拉法** .. math:: \tilde{y}_{n+1} = y_n + hf(x_n, y_n) .. math:: y_{n+1} = y_n + \frac{h}{2}[f(x_n, y_n) + f(x_{n+1}, \tilde{y}_{n+1})] 局部截断误差：O(h³)，全局截断误差：O(h²) .. container:: example-box **例题** 用欧拉法求解y' = y，y(0) = 1，h = 0.1 y₁ = y₀ + hf(x₀, y₀) = 1 + 0.1 × 1 = 1.1 y₂ = y₁ + hf(x₁, y₁) = 1.1 + 0.1 × 1.1 = 1.21 精确解：y = eˣ，y(0.2) ≈ 1.2214 误差：1.2214 - 1.21 ≈ 0.0114 6.2 龙格-库塔方法 --------------------- **二阶龙格-库塔（RK2）** .. math:: k_1 = hf(x_n, y_n) .. math:: k_2 = hf(x_n + h, y_n + k_1) .. math:: y_{n+1} = y_n + \frac{1}{2}(k_1 + k_2) **四阶龙格-库塔（RK4）** .. math:: k_1 = hf(x_n, y_n) .. math:: k_2 = hf(x_n + \frac{h}{2}, y_n + \frac{k_1}{2}) .. math:: k_3 = hf(x_n + \frac{h}{2}, y_n + \frac{k_2}{2}) .. math:: k_4 = hf(x_n + h, y_n + k_3) .. math:: y_{n+1} = y_n + \frac{1}{6}(k_1 + 2k_2 + 2k_3 + k_4) **误差分析** - 局部截断误差：O(h⁵) - 全局截断误差：O(h⁴) **优势** - 高精度 - 稳定性好 - 自适应步长容易实现 .. container:: example-box **例题** 用RK4求解y' = y，y(0) = 1，h = 0.2 k₁ = 0.2 × 1 = 0.2 k₂ = 0.2 × e^0.1 ≈ 0.2 × 1.1052 = 0.2210 k₃ = 0.2 × e^0.1105 ≈ 0.2 × 1.1169 = 0.2234 k₄ = 0.2 × e^0.2234 ≈ 0.2 × 1.2502 = 0.2500 y₁ = 1 + (0.2 + 2 × 0.2210 + 2 × 0.2234 + 0.2500)/6 = 1 + 1.3888/6 ≈ 1.2315 精确解：y(0.2) = e^0.2 ≈ 1.2214 误差：1.2315 - 1.2214 ≈ 0.0101 6.3 线性多步法 --------------------- **基本思想** 利用前几步的信息来计算下一步的值。 **亚当斯-巴什福特方法（显式）** 二阶亚当斯-巴什福特： .. math:: y_{n+1} = y_n + \frac{h}{2}[3f(x_n, y_n) - f(x_{n-1}, y_{n-1})] 四阶亚当斯-巴什福特： .. math:: y_{n+1} = y_n + \frac{h}{24}[55f(x_n, y_n) - 59f(x_{n-1}, y_{n-1}) + 37f(x_{n-2}, y_{n-2}) - 9f(x_{n-3}, y_{n-3})] **亚当斯-莫尔顿方法（隐式）** 二阶亚当斯-莫尔顿： .. math:: y_{n+1} = y_n + \frac{h}{2}[f(x_{n+1}, y_{n+1}) + f(x_n, y_n)] 四阶亚当斯-莫尔顿： .. math:: y_{n+1} = y_n + \frac{h}{24}[9f(x_{n+1}, y_{n+1}) + 19f(x_n, y_n) - 5f(x_{n-1}, y_{n-1}) + f(x_{n-2}, y_{n-2})] **预测-校正法** 用显式方法预测，用隐式方法校正。 6.4 稳定性分析 --------------------- **绝对稳定性** 数值方法的绝对稳定性是指当应用于测试方程y' = λy（Re(λ) < 0）时，数值解是否趋于零。 **稳定域** 对于步长h，如果|hλ|落在稳定域内，则数值方法绝对稳定。 **刚性方程** 刚性方程是指解中包含变化极快和变化极慢的分量。对于刚性方程，需要使用隐式方法（如隐式龙格-库塔、BDF方法）。 **A-稳定性** 如果稳定域包含整个左半平面（Re(hλ) < 0），则称数值方法是A稳定的。隐式欧拉法和梯形法是A稳定的。 7. 矩阵特征值问题 =================================== 7.1 幂法 --------------------- **基本思想** 通过矩阵与向量的乘法迭代，求出矩阵的主特征值（模最大的特征值）和对应的特征向量。 **算法步骤** 1. 给定初始向量v₀ 2. 迭代：v_(k+1) = Avₖ 3. 归一化：v_(k+1) = v_(k+1)/||v_(k+1)|| 4. 计算特征值近似：λ ≈ (Avₖ)ᵀvₖ/(vₖᵀvₖ) 5. 重复直到收敛 **收敛速度** 幂法的收敛速度取决于次大特征值与主特征值的比值|λ₂/λ₁|。比值越小，收敛越快。 **应用** - PageRank算法 - 主成分分析 - 社交网络分析 7.2 QR算法 --------------------- **基本思想** 通过QR分解迭代，将矩阵转化为上三角矩阵（Schur形式），从而得到特征值。 **算法步骤** 1. 初始化：A₀ = A 2. 对Aₖ进行QR分解：Aₖ = QₖRₖ 3. 构造新的矩阵：A_(k+1) = RₖQₖ 4. 重复直到Aₖ收敛到上三角矩阵 **收敛性** 在适当条件下，Aₖ收敛到上三角矩阵，对角元素就是特征值。 **加速技巧** - 位移策略：Aₖ - μₖI，加速收敛 - 隐式QR算法：避免显式计算位移 7.3 雅可比方法 --------------------- **适用范围** 雅可比方法适用于对称矩阵，可以同时求出所有特征值和特征向量。 **基本思想** 通过一系列正交相似变换（Givens旋转），将矩阵对角化。 **算法步骤** 1. 选择非对角元素绝对值最大的位置(p, q) 2. 构造旋转矩阵Gₚq，使得变换后该位置为零 3. 更新矩阵：A = GᵀₚqAGₚq 4. 重复直到矩阵对角化 **收敛性** 雅可比方法必然收敛，但收敛速度可能较慢。 8. 最优化方法 =================================== 8.1 无约束优化 --------------------- **梯度下降法** .. math:: x_{k+1} = x_k - \alpha_k \nabla f(x_k) 其中αₖ是步长（学习率）。 **牛顿法** .. math:: x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1}\nabla f(x_k) 其中∇²f是Hessian矩阵。 **共轭梯度法** 利用共轭方向，避免重复搜索方向。 8.2 约束优化 --------------------- **拉格朗日乘数法** 对于等式约束g(x) = 0，构造拉格朗日函数： .. math:: L(x, \lambda) = f(x) - \lambda g(x) 求解∇L = 0。 **惩罚函数法** 将约束问题转化为无约束问题： .. math:: \min f(x) + \mu \sum [g_i(x)]^2 **序列二次规划（SQP）** 将非线性约束优化问题转化为一系列二次规划子问题。 9. 应用领域 =================================== 9.1 科学计算 --------------------- **流体动力学** 求解Navier-Stokes方程，模拟流体流动。 **天气预报** 数值求解大气动力学方程。 **天体物理** 模拟星系演化、黑洞等。 9.2 工程应用 --------------------- **结构分析** 有限元方法分析结构受力。 **电路仿真** SPICE仿真电路行为。 **控制系统** 设计控制器，分析系统稳定性。 9.3 数据科学 --------------------- **机器学习** 梯度下降、牛顿法等优化算法用于训练模型。 **数据拟合** 最小二乘法、样条插值等用于数据拟合。 **信号处理** 傅里叶变换、小波变换等用于信号分析。 9.4 金融工程 --------------------- **期权定价** 数值求解Black-Scholes方程。 **风险管理** 蒙特卡洛方法计算VaR（风险价值）。 **投资组合优化** 求解最优投资组合。 10. 总结与展望 =================================== 数值分析是连接数学理论与实际应用的桥梁，为科学计算、工程设计、数据分析等领域提供了强有力的工具。 **核心价值** - 提供了求解数学问题的数值方法 - 分析了算法的收敛性和稳定性 - 控制了计算误差 - 提高了计算效率 **学习建议** - 理解算法的基本思想，而不仅仅是记忆公式 - 重视误差分析和稳定性分析 - 多做编程练习，实现各种数值算法 - 将理论应用于实际问题 **进阶方向** - 并行计算 - 自适应算法 - 高性能计算 - 机器学习优化 - 量子计算 数值分析不仅是数学的一个分支，更是科学和工程的基础，掌握它将为你的学习和研究提供强大的支持。