9195 字
46 分钟
Final：计算方法课程重点
2026-06-27
课程笔记
计算方法

概述#

这份笔记按 Chapter 1–9 组织，目标是在半天至一天内完成一轮系统复习与典型题训练。

[!NOTE] 材料依据与边界 本笔记以《25–26 计算方法期末复习提纲》、lesson15 后半段复习课、两套样卷及答案、24–25 回忆卷为主要依据，并结合本项目中 Chapter 1–9 的过往讨论摘要补全理解与易错点。早先生成的 Chapter 1–9 原始 .md 文件当前无法逐字读取，因此未做逐行合并。

本课程期末考试的核心特点是：

以算法理解和手算为主，证明要求较少；公式即使给出，也必须知道何时使用、每个量如何计算。

根据本学期复习提纲、lesson15 复习课和样卷，考试大概率由约 8 道综合计算题构成，每题对应一个或相邻两个章节。老师明确强调：

  • LU 分解会考；要会消去、写出 L,UL,U、前代、回代和部分选主元；
  • CG 法要会按公式计算；
  • 幂法、反幂法、Householder、Givens 要会手算；
  • Lagrange、Newton 插值及余项误差要会；
  • 离散最小二乘和连续最佳平方逼近必须区分；
  • 数值微分与数值积分都要会，高斯积分是重点；
  • Newton 迭代是重点；
  • 第 9 章会考 Euler 法及局部截断误差；
  • 编程题不考，复杂证明不作为主要要求。

目录#

复习范围与优先级#

第一优先级：必须能独立完成#

  1. LU 分解、前代回代、部分选主元；
  2. CG 法前两步；
  3. 幂法、反幂法或移位反幂法；
  4. Householder 与 Givens 变换；
  5. Lagrange、Newton 插值和插值误差；
  6. 离散最小二乘正规方程、连续最佳平方逼近；
  7. 中心差商、复合梯形公式、高斯积分；
  8. Newton 法、非线性方程组 Newton 法；
  9. 显式/隐式 Euler 法和局部截断误差。

第二优先级：应掌握概念和一步计算#

  • 有效数字、误差传播和稳定表达式；
  • Jacobi、Gauss-Seidel、SOR 格式；
  • QR 算法的迭代逻辑；
  • 二分法误差估计；
  • 收敛阶的判断；
  • Runge 现象及规避方法。

当前考试范围内可降低优先级或不复习的内容#

根据本学期复习提纲和 lesson15：

  • IEEE 754 浮点表示细节；
  • Cholesky 分解；
  • 预条件 CG、IC/ILU 等进阶预条件技术；
  • GMRES 等高级迭代法；
  • Rayleigh 商迭代；
  • Hermite 插值的详细计算、样条插值；
  • Chebyshev 逼近、三角逼近；
  • Romberg 积分和其他类型 Gauss 求积；
  • 改进 Euler、Runge-Kutta、多步法、稳定性分析的详细计算；
  • 定理的复杂证明和编程实现。

历年回忆卷中出现过最速下降法、Hermite 插值、四点 Gauss 公式和割线法。本笔记保留与现行范围仍有关的思想或简要补充，但不将它们放在最高优先级。

一页式答题原则#

  1. 题目指定方法时必须使用指定方法。 用 Lagrange 做 Newton 题，即使最终函数值正确，也会损失构造过程分。
  2. 先写公式，再代数值。 计算方法按步骤给分，只有结果通常拿不到完整分数。
  3. 迭代法必须标清上标。 x(k)x^{(k)} 表示第 kk 次迭代，不能写成幂。
  4. 误差题区分误差本身和误差限。 e=x−x∗e=x-x^* 可正可负，∣e∣|e| 才是绝对误差大小。
  5. 部分选主元后右端项也要换行。 由 PA=LUPA=LU 得到 Ly=PbLy=Pb。
  6. 反幂法的核心是解方程组。 不要真的先求 A−1A^{-1}。
  7. 连续逼近与离散拟合不能混用。 一个用积分内积，一个用数据点求和。
  8. Gauss 积分先检查区间。 标准节点在 [−1,1][-1,1]，其他区间必须变换。
  9. Newton 方程组实际计算用线性方程。 解 J(x(k))Δx(k)=−F(x(k))J(x^{(k)})\Delta x^{(k)}=-F(x^{(k)})，再更新。
  10. Euler 局部误差是 O(h2)O(h^2)，全局误差是 O(h)O(h)。

Chapter 1 误差分析与数值稳定性#

1.1 章节主线#

数值计算得到的是近似值。第一章回答三个问题：

  1. 近似值离真值多远；
  2. 输入误差如何传到输出；
  3. 怎样改写公式，减少舍入误差和有效数字损失。

设真值为 xx，近似值为 x∗x^*：

e=x−x∗,∣e∣=∣x−x∗∣,e=x-x^*,\qquad |e|=|x-x^*|,er=x−x∗x,∣er∣=∣x−x∗∣∣x∣.e_r=\frac{x-x^*}{x},\qquad |e_r|=\frac{|x-x^*|}{|x|}.

若只有误差限 ∣x−x∗∣≤ε|x-x^*|\leq \varepsilon，应写成“绝对误差不超过 ε\varepsilon”。

有效数字判定#

若 x∗x^* 的第一位非零数字位于 10m10^m，要保证至少有 nn 位有效数字，一个常用充分条件是

∣x−x∗∣≤1210m−n+1.|x-x^*|\leq \frac12 10^{m-n+1}.

例如 x∗=12.340x^*=12.340 的第一位非零数字在 10110^1 位：

  • 保证 4 位有效数字需要 ∣e∣≤0.005|e|\leq 0.005；
  • 保证 5 位有效数字需要 ∣e∣≤0.0005|e|\leq 0.0005。

1.2 重点题型一：绝对误差、相对误差与有效数字#

例 1：已知真值#

用 x∗=3.14x^*=3.14 近似 π\pi，求绝对误差、相对误差，并判断能保证几位有效数字。

解：

e=π−3.14≈0.00159265,e=\pi-3.14\approx 0.00159265,∣er∣=0.00159265π≈5.0696×10−4.|e_r|=\frac{0.00159265}{\pi}\approx 5.0696\times 10^{-4}.

3.143.14 的首位在 10010^0 位：

  • 3 位有效数字的误差限为 12100−3+1=0.005\frac12 10^{0-3+1}=0.005；
  • 4 位有效数字的误差限为 0.00050.0005。

现有误差 0.00159265<0.0050.00159265<0.005，但大于 0.00050.0005，因此可保证 3 位有效数字。

例 2：真值只知道在区间中#

已知 x∗=12.340x^*=12.340，且

12.338≤x≤12.342.12.338\leq x\leq 12.342.

求误差范围和可保证的有效数字。

解：

e=x−12.340∈[−0.002,0.002],∣e∣≤0.002.e=x-12.340\in[-0.002,0.002],\qquad |e|\leq 0.002.

相对误差满足

er=1−12.340x.e_r=1-\frac{12.340}{x}.

在给定区间内其绝对值最大约为

∣er∣≤max⁡{0.00212.338,0.00212.342}≈1.621×10−4.|e_r|\leq \max\left\{\frac{0.002}{12.338},\frac{0.002}{12.342}\right\} \approx 1.621\times 10^{-4}.

因为 0.002<0.0050.002<0.005，但 0.002>0.00050.002>0.0005，可保证 4 位有效数字。

易错点#

  • 相对误差分母按定义是真值 xx；若真值未知，可用近似值代替作近似估计，但要说明。
  • “保留 5 位小数”和“有 5 位有效数字”含义不同。

1.3 重点题型二：误差传播#

对多元函数

z=f(x1,…,xn),z=f(x_1,\ldots,x_n),

一阶误差传播公式为

Δz≈∑i=1n∂f∂xiΔxi.\Delta z\approx \sum_{i=1}^{n}\frac{\partial f}{\partial x_i}\Delta x_i.

若只知道误差限，通常估计

∣Δz∣≲∑i=1n∣∂f∂xi∣∣Δxi∣.|\Delta z|\lesssim \sum_{i=1}^{n}\left|\frac{\partial f}{\partial x_i}\right||\Delta x_i|.

例 1：乘积的误差传播#

已知

x=2.00±0.01,y=3.00±0.02,x=2.00\pm0.01,\qquad y=3.00\pm0.02,

计算 z=xy2z=xy^2 的近似值和误差限。

解：

z=2×32=18.z=2\times3^2=18.∂z∂x=y2=9,∂z∂y=2xy=12.\frac{\partial z}{\partial x}=y^2=9,\qquad \frac{\partial z}{\partial y}=2xy=12.

所以

∣Δz∣≲9(0.01)+12(0.02)=0.33.|\Delta z|\lesssim 9(0.01)+12(0.02)=0.33.

相对误差约为

∣Δz∣∣z∣≲0.3318=1.833%.\frac{|\Delta z|}{|z|}\lesssim \frac{0.33}{18}=1.833\%.

也可直接使用相对形式：

Δzz≈Δxx+2Δyy.\frac{\Delta z}{z}\approx \frac{\Delta x}{x}+2\frac{\Delta y}{y}.

例 2：函数值的线性化误差#

设

f(x,y)=xy,x=10±0.02,y=4±0.01.f(x,y)=\frac{x}{y},\qquad x=10\pm0.02,\quad y=4\pm0.01.

解：

f=2.5,f=2.5,∂f∂x=1y=14,∂f∂y=−xy2=−1016.\frac{\partial f}{\partial x}=\frac1y=\frac14, \qquad \frac{\partial f}{\partial y}=-\frac{x}{y^2}=-\frac{10}{16}.

故

∣Δf∣≲14(0.02)+1016(0.01)=0.01125.|\Delta f|\lesssim \frac14(0.02)+\frac{10}{16}(0.01) =0.01125.

相对误差限约为

0.011252.5=0.0045=0.45%.\frac{0.01125}{2.5}=0.0045=0.45\%.

例 3：舍入误差的实际传播#

把

x=1.2345,y=2.71828x=1.2345, \qquad y=2.71828

分别保留到小数点后 3 位和 4 位，再计算乘积。

解：

x^=1.235,y^=2.7183.\hat x=1.235, \qquad \hat y=2.7183.

原乘积为

xy≈3.35571666,xy\approx 3.35571666,

舍入后乘积为

x^y^≈3.35710050.\hat x\hat y\approx 3.35710050.

实际舍入传播误差为

x^y^−xy≈0.00138384.\hat x\hat y-xy\approx 0.00138384.

若题目要求“估计误差限”，应使用偏导数和每次舍入的最大误差；若题目给出具体舍入值并问实际差异，可直接相减。

1.4 重点题型三：避免有效数字损失#

当两个很接近的数相减时，前面大量有效数字消去，后面原本不可靠的位被放大，这称为 相消误差。

例 1：二次方程小根#

方程

x2+1000x−1=0x^2+1000x-1=0

的正根为

x=−1000+10000042.x=\frac{-1000+\sqrt{1000004}}{2}.

分子是两个接近 10001000 的数相减，数值不稳定。分子有理化：

x=21000+1000004.x= \frac{2}{1000+\sqrt{1000004}}.

新公式只含同号数相加，稳定性更好。

例 2：平方根之差#

直接计算

x+1−x\sqrt{x+1}-\sqrt{x}

在 xx 很大时会发生相消。改写为

x+1−x=1x+1+x.\sqrt{x+1}-\sqrt{x} =\frac{1}{\sqrt{x+1}+\sqrt{x}}.

例 3：1−cos⁡x1-\cos x#

当 xx 很小时，cos⁡x≈1\cos x\approx1，直接算 1−cos⁡x1-\cos x 会损失有效数字。利用恒等式

1−cos⁡x=2sin⁡2x2,1-\cos x=2\sin^2\frac{x}{2},

于是

1−cos⁡xx2=12(sin⁡(x/2)x/2)2,\frac{1-\cos x}{x^2} =\frac12\left(\frac{\sin(x/2)}{x/2}\right)^2,

更适合小 xx 数值计算。

本章检查清单#

  • 能区分误差、误差绝对值和误差限；
  • 能判定有效数字；
  • 能写一阶误差传播公式；
  • 看到相近数相减时会进行有理化、恒等变形或调整顺序。

Chapter 2 高斯消去与 LU 分解#

2.1 章节主线#

高斯消去把 Ax=bAx=b 化成上三角系统。若把消去乘子保存下来，就得到

A=LU,A=LU,

其中 LL 为单位下三角矩阵，UU 为上三角矩阵。

求解过程分成两步：

Ly=b,Ux=y.Ly=b,\qquad Ux=y.

若使用部分选主元，则

PA=LU,PA=LU,

求解时必须使用

Ly=Pb,Ux=y.Ly=Pb, \qquad Ux=y.

2.2 重点题型一：由消去过程写出 L,UL,U#

通用手算规则#

第 kk 步消去乘子为

lik=aik(k)akk(k),i>k.l_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}},\qquad i>k.
  • 消去后的上三角系数进入 UU；
  • 消去乘子进入 LL 的对应位置；
  • LL 的对角线全为 1。

例 1：三对角矩阵#

设

A=[2−10−12−10−12].A= \begin{bmatrix} 2&-1&0\\ -1&2&-1\\ 0&-1&2 \end{bmatrix}.

第一步：

l21=−12=−12.l_{21}=\frac{-1}{2}=-\frac12.

第二行更新后：

[0,32,−1].[0,\frac32,-1].

第二步：

l32=−13/2=−23.l_{32}=\frac{-1}{3/2}=-\frac23.

第三行更新后最后一个元素为

2−(−23)(−1)=43.2-\left(-\frac23\right)(-1)=\frac43.

所以

L=[100−12100−231],U=[2−10032−10043].L= \begin{bmatrix} 1&0&0\\ -\frac12&1&0\\ 0&-\frac23&1 \end{bmatrix}, \qquad U= \begin{bmatrix} 2&-1&0\\ 0&\frac32&-1\\ 0&0&\frac43 \end{bmatrix}.

例 2：一般 3×33\times3 矩阵#

设

A=[120251013].A= \begin{bmatrix} 1&2&0\\ 2&5&1\\ 0&1&3 \end{bmatrix}.

第一列：

l21=2,l31=0.l_{21}=2, \qquad l_{31}=0.

消去后第二行为 [0,1,1][0,1,1]，第三行为 [0,1,3][0,1,3]。

第二列：

l32=1.l_{32}=1.

得到

L=[100210011],U=[120011002].L= \begin{bmatrix} 1&0&0\\ 2&1&0\\ 0&1&1 \end{bmatrix}, \qquad U= \begin{bmatrix} 1&2&0\\ 0&1&1\\ 0&0&2 \end{bmatrix}.

易错点#

  • LL 记录的是“消去时使用的乘子”，不是消去矩阵中的负乘子；
  • 每一步计算乘子时要用已经更新过的矩阵元素；
  • 若中途交换行，普通 A=LUA=LU 形式通常失效，应写 PA=LUPA=LU。

2.3 重点题型二：利用 LU 解一个或多个右端项#

例 1：继续使用三对角矩阵#

求解

Ax=[101].Ax= \begin{bmatrix}1\\0\\1\end{bmatrix}.

先解 Ly=bLy=b：

y1=1,y_1=1,−12y1+y2=0⇒y2=12,-\frac12y_1+y_2=0\Rightarrow y_2=\frac12,−23y2+y3=1⇒y3=43.-\frac23y_2+y_3=1\Rightarrow y_3=\frac43.

再解 Ux=yUx=y：

43x3=43⇒x3=1,\frac43x_3=\frac43\Rightarrow x_3=1,32x2−x3=12⇒x2=1,\frac32x_2-x_3=\frac12\Rightarrow x_2=1,2x1−x2=1⇒x1=1.2x_1-x_2=1\Rightarrow x_1=1.

所以

x=(1,1,1)T.x=(1,1,1)^T.

例 2：同一 AA 解两个右端项#

已知上一例的 A=LUA=LU。分别求解

Ax=[145],Az=[388].Ax= \begin{bmatrix}1\\4\\5\end{bmatrix}, \qquad Az= \begin{bmatrix}3\\8\\8\end{bmatrix}.

对第一个右端项：

Ly=b⇒y=(1,2,3)T,Ly=b\Rightarrow y=(1,2,3)^T,Ux=y⇒x=(0,12,32)T.Ux=y\Rightarrow x=\left(0,\frac12,\frac32\right)^T.

对第二个右端项：

Lw=(3,8,8)T⇒w=(3,2,6)T,Lw=(3,8,8)^T\Rightarrow w=(3,2,6)^T,Uz=w⇒z=(5,−1,3)T.Uz=w\Rightarrow z=(5,-1,3)^T.

意义： AA 只需分解一次，每个新右端项只做一次前代和回代。这是 LU 相对直接重复消去的主要优势。

2.4 重点题型三：部分选主元与稳定性#

部分选主元在第 kk 列的第 kk 行及其下方选取绝对值最大的元素作为主元，并交换到第 kk 行。

目的：避免除以过小主元，使消去乘子过大并放大舍入误差。

例 1：小主元导致误差放大#

设

C=[10−4111],g=[11.600].C= \begin{bmatrix} 10^{-4}&1\\ 1&1 \end{bmatrix}, \qquad g= \begin{bmatrix}1\\1.600\end{bmatrix}.

不选主元时

m21=104,m_{21}=10^4,

乘子极大。保留 4 位有效数字时，消去中会出现大数相减，得到的第一分量可能严重失真。

部分选主元先交换两行：

P=[0110],PC=[1110−41].P= \begin{bmatrix}0&1\\1&0\end{bmatrix}, \qquad PC= \begin{bmatrix}1&1\\10^{-4}&1\end{bmatrix}.

此时

m21=10−4,m_{21}=10^{-4},

乘子很小，得到近似解

x≈(0.6001,0.9999)T,x\approx(0.6001,0.9999)^T,

与精确解接近。

例 2：零主元必须换行#

设

A=[0211].A= \begin{bmatrix} 0&2\\ 1&1 \end{bmatrix}.

第一步无法用 a11=0a_{11}=0 作主元。交换两行后

PA=[1102].PA= \begin{bmatrix} 1&1\\ 0&2 \end{bmatrix}.

此时可取 L=IL=I、U=PAU=PA。若右端项为 bb，必须同时变为 PbPb。

答题模板#

当前列主元过小/为零，因此交换第 kk 行与第 pp 行。记交换矩阵为 PP，得到 PA=LUPA=LU。求解时先计算 PbPb，再依次解 Ly=PbLy=Pb 和 Ux=yUx=y。

本章检查清单#

  • 会从高斯消去乘子写出 LL；
  • 会完整写前代和回代；
  • 多个右端项时不会重新分解；
  • 会写 PA=LUPA=LU 和 Ly=PbLy=Pb；
  • 能解释部分选主元控制乘子、提高稳定性。

Chapter 3 线性方程组迭代法#

3.1 章节主线#

直接法试图有限步得到解；迭代法从初值 x(0)x^{(0)} 出发，构造

x(k+1)=Bx(k)+f,x^{(k+1)}=Bx^{(k)}+f,

逐步逼近精确解。

本章重点包括：

  • Jacobi；
  • Gauss-Seidel；
  • SOR；
  • 共轭梯度法 CG。

3.2 重点题型一：写出 Jacobi、Gauss-Seidel、SOR 格式#

设

aiixi+∑j≠iaijxj=bi.a_{ii}x_i+\sum_{j\ne i}a_{ij}x_j=b_i.

Jacobi#

xi(k+1)=1aii(bi−∑j≠iaijxj(k)).x_i^{(k+1)}= \frac1{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right).

所有新分量统一使用上一轮数据。

Gauss-Seidel#

xi(k+1)=1aii(bi−∑j<iaijxj(k+1)−∑j>iaijxj(k)).x_i^{(k+1)}= \frac1{a_{ii}} \left( b_i- \sum_{j<i}a_{ij}x_j^{(k+1)}- \sum_{j>i}a_{ij}x_j^{(k)} \right).

已经算出的新分量立即使用。

SOR#

xi(k+1)=(1−ω)xi(k)+ωaii(bi−∑j<iaijxj(k+1)−∑j>iaijxj(k)).x_i^{(k+1)}=(1-\omega)x_i^{(k)}+ \frac{\omega}{a_{ii}} \left( b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}- \sum_{j>i}a_{ij}x_j^{(k)} \right).
  • ω=1\omega=1：Gauss-Seidel；
  • 0<ω<10<\omega<1：低松弛；
  • 1<ω<21<\omega<2：超松弛。

例 1：Jacobi 与 Gauss-Seidel 两步#

求解

{4x+y=9,x+3y=7,x(0)=(0,0)T.\begin{cases} 4x+y=9,\\ x+3y=7, \end{cases} \qquad x^{(0)}=(0,0)^T.

迭代格式为

x(k+1)=9−y(k)4,y(k+1)=7−x(k)3x^{(k+1)}=\frac{9-y^{(k)}}4, \qquad y^{(k+1)}=\frac{7-x^{(k)}}3

（Jacobi）。

第一步：

x(1)=2.25,y(1)=73≈2.3333.x^{(1)}=2.25, \qquad y^{(1)}=\frac73\approx2.3333.

第二步：

x(2)=9−2.33334≈1.6667,x^{(2)}=\frac{9-2.3333}{4}\approx1.6667,y(2)=7−2.253≈1.5833.y^{(2)}=\frac{7-2.25}{3}\approx1.5833.

Gauss-Seidel 第一轮立即使用新 xx：

x(1)=2.25,x^{(1)}=2.25,y(1)=7−2.253=1.5833.y^{(1)}=\frac{7-2.25}{3}=1.5833.

第二轮：

x(2)=9−1.58334=1.8542,x^{(2)}=\frac{9-1.5833}{4}=1.8542,y(2)=7−1.85423=1.7153.y^{(2)}=\frac{7-1.8542}{3}=1.7153.

例 2：SOR 一步#

对

{3x1+x2=5,x1+2x2=5,\begin{cases} 3x_1+x_2=5,\\ x_1+2x_2=5, \end{cases}

取 ω=12\omega=\frac12，x(0)=(0,0)Tx^{(0)}=(0,0)^T。

x1(1)=(1−ω)x1(0)+ω3(5−x2(0))=56.x_1^{(1)}=(1-\omega)x_1^{(0)}+ \frac{\omega}{3}(5-x_2^{(0)}) =\frac56.x2(1)=(1−ω)x2(0)+ω2(5−x1(1))=14(5−56)=2524.x_2^{(1)}=(1-\omega)x_2^{(0)}+ \frac{\omega}{2}(5-x_1^{(1)}) =\frac14\left(5-\frac56\right) =\frac{25}{24}.

3.3 重点题型二：判断适用性与收敛条件#

常用结论：

  1. 若 AA 严格行对角占优，则 Jacobi 和 Gauss-Seidel 均收敛；
  2. 若 AA 对称正定，则 Gauss-Seidel 收敛；SOR 在 0<ω<20<\omega<2 时收敛；
  3. CG 直接适用于 对称正定矩阵；仅有非奇异性不够。

不要笼统写“对称正定保证所有迭代法收敛”。对 Jacobi 仍应依据其具体条件判断。

例 1：对角占优判断#

A=[4123].A= \begin{bmatrix} 4&1\\ 2&3 \end{bmatrix}.

第一行 4>14>1，第二行 3>23>2，严格行对角占优，因此 Jacobi 与 Gauss-Seidel 均收敛。

例 2：非奇异不代表可用 CG#

A=[1221].A= \begin{bmatrix} 1&2\\ 2&1 \end{bmatrix}.

AA 对称且非奇异，但特征值为 3,−13,-1，不是正定矩阵。因此不能直接套用标准 CG 收敛结论。

例 3：对称正定判断#

A=[2−1−12].A= \begin{bmatrix} 2&-1\\ -1&2 \end{bmatrix}.

A=ATA=A^T，且顺序主子式

2>0,det⁡A=3>0,2>0, \qquad \det A=3>0,

故 AA 对称正定，可使用 CG；Gauss-Seidel 收敛，SOR 在 0<ω<20<\omega<2 时收敛。

3.4 重点题型三：共轭梯度法 CG#

本课程复习提纲给出的 CG 格式为：

r(0)=b−Ax(0),d(0)=r(0),r^{(0)}=b-Ax^{(0)}, \qquad d^{(0)}=r^{(0)},λ0=⟨r(0),r(0)⟩⟨d(0),Ad(0)⟩,x(1)=x(0)+λ0d(0).\lambda_0= \frac{\langle r^{(0)},r^{(0)}\rangle} {\langle d^{(0)},Ad^{(0)}\rangle}, \qquad x^{(1)}=x^{(0)}+\lambda_0d^{(0)}.

对 k=1,2,…k=1,2,\ldots：

r(k)=b−Ax(k),r^{(k)}=b-Ax^{(k)},βk−1=−⟨r(k),Ad(k−1)⟩⟨d(k−1),Ad(k−1)⟩,\beta_{k-1}= -\frac{\langle r^{(k)},Ad^{(k-1)}\rangle} {\langle d^{(k-1)},Ad^{(k-1)}\rangle},d(k)=r(k)+βk−1d(k−1),d^{(k)}=r^{(k)}+\beta_{k-1}d^{(k-1)},λk=⟨r(k),d(k)⟩⟨d(k),Ad(k)⟩,x(k+1)=x(k)+λkd(k).\lambda_k= \frac{\langle r^{(k)},d^{(k)}\rangle} {\langle d^{(k)},Ad^{(k)}\rangle}, \qquad x^{(k+1)}=x^{(k)}+\lambda_kd^{(k)}.

精确算术下，也常见下面的等价写法：

αk=(r(k))Tr(k)(d(k))TAd(k),βk=(r(k+1))Tr(k+1)(r(k))Tr(k).\alpha_k=\frac{(r^{(k)})^Tr^{(k)}}{(d^{(k)})^TAd^{(k)}}, \qquad \beta_k=\frac{(r^{(k+1)})^Tr^{(k+1)}}{(r^{(k)})^Tr^{(k)}}.

两套记号对应同一算法。考试时优先照卷末公式表的 λk,βk\lambda_k,\beta_k 版本写，避免记号错位。

核心性质：

(d(i))TAd(j)=0,i≠j.(d^{(i)})^TAd^{(j)}=0, \qquad i\ne j.

精确算术下，对 n×nn\times n 对称正定矩阵，理论上至多 nn 步得到精确解。

例 1：CG 第一步与残差正交#

设

A=[1004],b=[12],x(0)=0.A= \begin{bmatrix} 1&0\\0&4 \end{bmatrix}, \qquad b= \begin{bmatrix}1\\2\end{bmatrix}, \qquad x^{(0)}=0.r(0)=d(0)=(1,2)T,Ad(0)=(1,8)T.r^{(0)}=d^{(0)}=(1,2)^T, \qquad Ad^{(0)}=(1,8)^T.λ0=12+221⋅1+2⋅8=517.\lambda_0=\frac{1^2+2^2}{1\cdot1+2\cdot8}=\frac5{17}.x(1)=517(1,2)T=(517,1017)T.x^{(1)}=\frac5{17}(1,2)^T =\left(\frac5{17},\frac{10}{17}\right)^T.r(1)=b−Ax(1)=(1217,−617)T.r^{(1)}=b-Ax^{(1)} =\left(\frac{12}{17},-\frac6{17}\right)^T.

验证

(r(1))Tr(0)=1217−2617=0.(r^{(1)})^Tr^{(0)}=\frac{12}{17}-2\frac6{17}=0.

相邻残差正交。

例 2：完整两步#

设

A=[4113],b=[12],x(0)=0.A= \begin{bmatrix} 4&1\\1&3 \end{bmatrix}, \qquad b= \begin{bmatrix}1\\2\end{bmatrix}, \qquad x^{(0)}=0.

初始：

r(0)=d(0)=(1,2)T,Ad(0)=(6,7)T.r^{(0)}=d^{(0)}=(1,2)^T, \qquad Ad^{(0)}=(6,7)^T.λ0=520=14.\lambda_0=\frac5{20}=\frac14.x(1)=(14,12)T,x^{(1)}=\left(\frac14,\frac12\right)^T,r(1)=b−Ax(1)=(−12,14)T.r^{(1)}=b-Ax^{(1)}= \left(-\frac12,\frac14\right)^T.β0=−(r(1))TAd(0)(d(0))TAd(0)=−−5/420=116.\beta_0 =-\frac{(r^{(1)})^TAd^{(0)}}{(d^{(0)})^TAd^{(0)}} =-\frac{-5/4}{20} =\frac1{16}.d(1)=r(1)+116d(0)=(−716,38)T.d^{(1)}=r^{(1)}+\frac1{16}d^{(0)} =\left(-\frac7{16},\frac38\right)^T.

计算

Ad(1)=(−118,1116)T,Ad^{(1)}= \left(-\frac{11}{8},\frac{11}{16}\right)^T,λ1=(r(1))Td(1)(d(1))TAd(1)=411.\lambda_1=\frac{(r^{(1)})^Td^{(1)}}{(d^{(1)})^TAd^{(1)}} =\frac4{11}.x(2)=x(1)+411d(1)=(111,711)T.x^{(2)}=x^{(1)}+\frac4{11}d^{(1)} =\left(\frac1{11},\frac7{11}\right)^T.

这就是精确解。

低优先级补充：最速下降法#

最速下降法也取 d(k)=r(k)d^{(k)}=r^{(k)}，步长

αk=(r(k))Tr(k)(r(k))TAr(k).\alpha_k=\frac{(r^{(k)})^Tr^{(k)}}{(r^{(k)})^TAr^{(k)}}.

它每次沿当前负梯度方向走，可能出现“之”字形；CG 通过构造 AA-共轭方向，通常更快。

本章检查清单#

  • 能区分 Jacobi 的旧值与 GS 的新值；
  • 会写 SOR，知道 ω=1\omega=1 的含义；
  • 知道 CG 需要对称正定；
  • 能连续计算 r,d,λ,β,xr,d,\lambda,\beta,x；
  • 不把普通正交与 AA-共轭混淆。

Chapter 4 矩阵特征值计算与正交变换#

4.1 章节主线#

本章包含两条线：

  1. 用幂法、反幂法迭代求特征值；
  2. 用 Householder 或 Givens 构造 QR 分解，再进行 QR 迭代。

4.2 重点题型一：幂法、反幂法与移位反幂法#

幂法#

若 ∣λ1∣>∣λ2∣≥⋯|\lambda_1|>|\lambda_2|\geq\cdots，且初始向量含有主特征向量分量，则

w(k+1)=Av(k).w^{(k+1)}=Av^{(k)}.

选取下标 pp 使

∣wp(k+1)∣=∥w(k+1)∥∞,|w_p^{(k+1)}|=\|w^{(k+1)}\|_\infty,

并取有符号归一化因子

μk+1=wp(k+1),v(k+1)=w(k+1)μk+1.\mu_{k+1}=w_p^{(k+1)}, \qquad v^{(k+1)}=\frac{w^{(k+1)}}{\mu_{k+1}}.

此时 μk\mu_k 可逼近主特征值；若公式表直接用 ∥w(k+1)∥∞\|w^{(k+1)}\|_\infty 归一化，则得到的是主特征值的模，符号需另行判断。

收敛速度主要受

∣λ2λ1∣\left|\frac{\lambda_2}{\lambda_1}\right|

控制，比例越小，收敛越快。

反幂法#

Ay(k+1)=v(k).Ay^{(k+1)}=v^{(k)}.

若取 mk+1m_{k+1} 为 y(k+1)y^{(k+1)} 中绝对值最大的有符号分量，并令

v(k+1)=y(k+1)mk+1,v^{(k+1)}=\frac{y^{(k+1)}}{m_{k+1}},

则

λmin⁡, ∣⋅∣≈1mk+1.\lambda_{\min,\,|\cdot|}\approx\frac1{m_{k+1}}.

它相当于对 A−1A^{-1} 做幂法，因此趋向按模最小特征值对应的特征向量。

移位反幂法#

(A−μI)y(k+1)=v(k).(A-\mu I)y^{(k+1)}=v^{(k)}.

若归一化因子为 mk+1m_{k+1}，则邻近特征值可估计为

λ≈μ+1mk+1.\lambda\approx\mu+\frac1{m_{k+1}}.

它趋向离 μ\mu 最近的特征值。

计算时解线性方程组，不显式求逆。

例 1：幂法一步一步逼近#

A=[2112],v(0)=(1,0)T.A= \begin{bmatrix} 2&1\\1&2 \end{bmatrix}, \qquad v^{(0)}=(1,0)^T.

第一步：

w(1)=(2,1)T,μ1=2,v(1)=(1,0.5)T.w^{(1)}=(2,1)^T, \qquad \mu_1=2, \qquad v^{(1)}=(1,0.5)^T.

第二步：

w(2)=(2.5,2)T,μ2=2.5,v(2)=(1,0.8)T.w^{(2)}=(2.5,2)^T, \qquad \mu_2=2.5, \qquad v^{(2)}=(1,0.8)^T.

主特征值为 33，迭代值正向 33 靠近，向量趋向 (1,1)T(1,1)^T。

例 2：普通反幂法#

A=diag⁡(1,3,6),v(0)=(1,1,1)T.A=\operatorname{diag}(1,3,6), \qquad v^{(0)}=(1,1,1)^T.

解

Ay(1)=v(0)Ay^{(1)}=v^{(0)}

得

y(1)=(1,13,16)T.y^{(1)}=\left(1,\frac13,\frac16\right)^T.

归一化后

v(1)=(1,13,16)T.v^{(1)}=\left(1,\frac13,\frac16\right)^T.

本步归一化因子 m1=1m_1=1，故

λ≈1m1=1.\lambda\approx\frac1{m_1}=1.

第一分量占优，迭代趋向特征值 11。

例 3：移位反幂法#

仍取

A=diag⁡(1,3,6),μ=2.8,v(0)=(1,1,1)T.A=\operatorname{diag}(1,3,6), \qquad \mu=2.8, \qquad v^{(0)}=(1,1,1)^T.A−μI=diag⁡(−1.8,0.2,3.2).A-\mu I=\operatorname{diag}(-1.8,0.2,3.2).

解

(A−μI)y(1)=v(0)(A-\mu I)y^{(1)}=v^{(0)}

得

y(1)=(−59,5,516)T.y^{(1)}=\left(-\frac59,5,\frac5{16}\right)^T.

以无穷范数 5 归一化：

v(1)=(−19,1,116)T.v^{(1)}= \left(-\frac19,1,\frac1{16}\right)^T.

本步归一化因子 m1=5m_1=5，所以

λ≈2.8+15=3.\lambda\approx2.8+\frac15=3.

因为 2.82.8 离特征值 33 最近，第二分量迅速占优。

易错点#

  • 题目要求“用幂法估计”时，直接写精确特征值不能替代迭代过程；
  • 归一化因子带符号还是取绝对值，应按课堂或公式表约定；
  • 反幂法归一化因子的倒数与特征值估计之间要结合具体定义判断，不能机械套一个符号。

4.3 重点题型二：Householder 反射#

对非零向量 xx，希望构造正交矩阵 HH，把它反射到坐标轴方向：

Hx=αe1,∣α∣=∥x∥2.Hx=\alpha e_1, \qquad |\alpha|=\|x\|_2.

取

u=x−αe1,u=x-\alpha e_1,H=I−2uuTuTu.H=I-2\frac{uu^T}{u^Tu}.

HH 具有

HT=H,HTH=I,H−1=H.H^T=H, \qquad H^TH=I, \qquad H^{-1}=H.

例 1：二维反射#

把 x=(3,4)Tx=(3,4)^T 变成 (5,0)T(5,0)^T。

取

u=x−5e1=(−2,4)T,uTu=20.u=x-5e_1=(-2,4)^T, \qquad u^Tu=20.H=I−110uuT=[354545−35].H=I-\frac1{10}uu^T = \begin{bmatrix} \frac35&\frac45\\ \frac45&-\frac35 \end{bmatrix}.

验证：

H[34]=[50].H \begin{bmatrix}3\\4\end{bmatrix} = \begin{bmatrix}5\\0\end{bmatrix}.

例 2：三维反射#

把

x=(0,3,4)Tx=(0,3,4)^T

变成 (5,0,0)T(5,0,0)^T。

u=x−5e1=(−5,3,4)T,uTu=50.u=x-5e_1=(-5,3,4)^T, \qquad u^Tu=50.H=I−125uuT=[03545351625−122545−1225925].H=I-\frac1{25}uu^T = \begin{bmatrix} 0&\frac35&\frac45\\ \frac35&\frac{16}{25}&-\frac{12}{25}\\ \frac45&-\frac{12}{25}&\frac9{25} \end{bmatrix}.

直接相乘可得

Hx=(5,0,0)T.Hx=(5,0,0)^T.

选 α\alpha 的技巧#

实际数值计算常取

α=−sign⁡(x1)∥x∥2\alpha=-\operatorname{sign}(x_1)\|x\|_2

以避免 x1x_1 与 ∥x∥2\|x\|_2 相减造成相消。若考试明确要求映射到正方向，则按题目给定目标构造。

4.4 重点题型三：Givens 旋转、QR 分解与 QR 迭代#

对向量 (a,b)T(a,b)^T，令

r=a2+b2,c=ar,s=br.r=\sqrt{a^2+b^2}, \qquad c=\frac a r, \qquad s=\frac b r.

取

G=[cs−sc],G= \begin{bmatrix} c&s\\-s&c \end{bmatrix},

则

G[ab]=[r0].G \begin{bmatrix}a\\b\end{bmatrix} = \begin{bmatrix}r\\0\end{bmatrix}.

在大矩阵中，把这个 2×22\times2 块嵌入单位阵，便可消去某个非对角元素。

例 1：用 Givens 做 QR 分解#

设

A=[3142].A= \begin{bmatrix} 3&1\\4&2 \end{bmatrix}.

为消去 a21=4a_{21}=4，取

c=35,s=45,c=\frac35, \qquad s=\frac45,G=[3545−4535].G= \begin{bmatrix} \frac35&\frac45\\ -\frac45&\frac35 \end{bmatrix}.

则

R=GA=[5115025].R=GA= \begin{bmatrix} 5&\frac{11}{5}\\ 0&\frac25 \end{bmatrix}.

因为 GG 正交，Q=GTQ=G^T，故

A=QR,Q=[35−454535].A=QR, \qquad Q= \begin{bmatrix} \frac35&-\frac45\\ \frac45&\frac35 \end{bmatrix}.

例 2：做一步 QR 迭代#

QR 算法：

A(0)=A,A(k)=QkRk,A(k+1)=RkQk.A^{(0)}=A, \qquad A^{(k)}=Q_kR_k, \qquad A^{(k+1)}=R_kQ_k.

利用上一例：

A(1)=RQ=[4.76−2.680.320.24].A^{(1)}=RQ = \begin{bmatrix} 4.76&-2.68\\ 0.32&0.24 \end{bmatrix}.

由于

A(1)=QTAQ,A^{(1)}=Q^TAQ,

A(1)A^{(1)} 与 AA 相似，特征值不变。反复迭代后，在适当条件下矩阵趋向上三角，其对角元逼近特征值。

Householder 与 Givens 的关系#

  • 二者都构造正交矩阵，都可用于 QR 分解；
  • Householder 一次可消去一列中的多个元素；
  • Givens 一次只消去一个元素，但适合稀疏矩阵或局部更新；
  • QR 分解是目标，Householder、Givens、Gram-Schmidt 是不同实现方式。

本章检查清单#

  • 会按无穷范数完成幂法归一化；
  • 反幂法会解方程组；
  • 能解释移位为何锁定附近特征值；
  • Householder 会写 uu 和 HH 并验证；
  • Givens 会从 (a,b)(a,b) 算 c,sc,s；
  • 知道 Ak+1=RkQkA_{k+1}=R_kQ_k 与相似变换的关系。

Chapter 5 插值法#

5.1 章节主线#

给定 n+1n+1 个互异节点

(x0,y0),…,(xn,yn),(x_0,y_0),\ldots,(x_n,y_n),

存在唯一一个次数不超过 nn 的多项式 Pn(x)P_n(x) 满足

Pn(xi)=yi.P_n(x_i)=y_i.

Lagrange 与 Newton 是同一个插值多项式的两种构造方式：

  • Lagrange 直接按节点构造；
  • Newton 用差商逐项增加节点，更适合递推和增添数据。

5.2 重点题型一：Lagrange 插值#

基函数

lk(x)=∏i=0i≠knx−xixk−xi.l_k(x)= \prod_{\substack{i=0\\i\ne k}}^n \frac{x-x_i}{x_k-x_i}.

满足

lk(xi)=δki.l_k(x_i)=\delta_{ki}.

插值多项式

Ln(x)=∑k=0nyklk(x).L_n(x)=\sum_{k=0}^ny_kl_k(x).

例 1：构造完整二次多项式#

节点为

(0,1),(1,3),(2,7).(0,1),(1,3),(2,7).l0(x)=(x−1)(x−2)2,l_0(x)=\frac{(x-1)(x-2)}{2},l1(x)=−x(x−2),l_1(x)=-x(x-2),l2(x)=x(x−1)2.l_2(x)=\frac{x(x-1)}2.

所以

L2(x)=l0(x)+3l1(x)+7l2(x).L_2(x)=l_0(x)+3l_1(x)+7l_2(x).

化简得

L2(x)=x2+x+1.L_2(x)=x^2+x+1.

于是

L2(1.5)=1.52+1.5+1=4.75.L_2(1.5)=1.5^2+1.5+1=4.75.

例 2：只计算某点函数值#

节点

x0=−1,x1=0,x2=2,x_0=-1, \quad x_1=0, \quad x_2=2,

对应函数值为 2,1,52,1,5。求 p2(1)p_2(1)。

只需算基函数在 x=1x=1 的值：

l0(1)=−13,l1(1)=1,l2(1)=13.l_0(1)=-\frac13, \qquad l_1(1)=1, \qquad l_2(1)=\frac13.

故

p2(1)=2(−13)+1+5(13)=2.p_2(1)=2\left(-\frac13\right)+1+5\left(\frac13\right)=2.

若题目只要求某点值，没有必要先完全展开多项式。

5.3 重点题型二：Newton 插值与差商表#

一阶差商

f[xi,xi+1]=f(xi+1)−f(xi)xi+1−xi.f[x_i,x_{i+1}] =\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}.

高阶差商

f[xi,…,xi+m]=f[xi+1,…,xi+m]−f[xi,…,xi+m−1]xi+m−xi.f[x_i,\ldots,x_{i+m}] = \frac{f[x_{i+1},\ldots,x_{i+m}]-f[x_i,\ldots,x_{i+m-1}]} {x_{i+m}-x_i}.

Newton 形式

Pn(x)=f[x0]+f[x0,x1](x−x0)+⋯+f[x0,…,xn]∏i=0n−1(x−xi).P_n(x)=f[x_0]+ f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{i=0}^{n-1}(x-x_i).

例 1：由差商表构造#

仍用节点

(0,1),(1,3),(2,7).(0,1),(1,3),(2,7).

零阶差商：

1,3,7.1, \quad3, \quad7.

一阶差商：

f[0,1]=2,f[1,2]=4.f[0,1]=2, \qquad f[1,2]=4.

二阶差商：

f[0,1,2]=4−22−0=1.f[0,1,2]=\frac{4-2}{2-0}=1.

所以

P2(x)=1+2x+x(x−1)=x2+x+1.P_2(x)=1+2x+x(x-1)=x^2+x+1.

与 Lagrange 结果相同，因为满足同一组插值条件的次数不超过 2 的多项式唯一。

例 2：非等距节点#

节点

(1,2),(2,3),(4,1).(1,2),(2,3),(4,1).

一阶差商：

f[1,2]=1,f[2,4]=−1.f[1,2]=1, \qquad f[2,4]=-1.

二阶差商：

f[1,2,4]=−1−14−1=−23.f[1,2,4]=\frac{-1-1}{4-1}=-\frac23.

Newton 多项式为

P2(x)=2+(x−1)−23(x−1)(x−2).P_2(x)=2+(x-1)-\frac23(x-1)(x-2).

求 f(3)f(3)：

P2(3)=2+2−23(2)(1)=83.P_2(3)=2+2-\frac23(2)(1)=\frac83.

易错点#

  • 高阶差商分母是最右节点减最左节点；
  • Newton 第 mm 阶项包含前 mm 个因子；
  • 节点不等距也可以使用差商，不能误用有限差分表。

5.4 重点题型三：插值余项与误差上界#

若 f∈Cn+1[a,b]f\in C^{n+1}[a,b]，则

Rn(x)=f(x)−Pn(x)=f(n+1)(ξ)(n+1)!∏i=0n(x−xi),R_n(x)=f(x)-P_n(x) =\frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n(x-x_i),

其中 ξ\xi 位于节点和 xx 所在区间内。

误差上界：

∣Rn(x)∣≤Mn+1(n+1)!∣∏i=0n(x−xi)∣,|R_n(x)| \leq \frac{M_{n+1}}{(n+1)!} \left|\prod_{i=0}^n(x-x_i)\right|,Mn+1=max⁡∣f(n+1)(x)∣.M_{n+1}=\max|f^{(n+1)}(x)|.

例 1：直接代余项公式#

节点为 −1,0,2-1,0,2，且

∣f(3)(x)∣≤12.|f^{(3)}(x)|\leq12.

估计 x=1x=1 处二次插值误差。

∣R2(1)∣≤123!∣(1+1)(1−0)(1−2)∣=126×2=4.|R_2(1)| \leq\frac{12}{3!}|(1+1)(1-0)(1-2)| =\frac{12}{6}\times2=4.

例 2：exe^x 的插值误差#

用节点 0,12,10,\frac12,1 作二次插值，估计 x=14x=\frac14 处误差。

因为 f(x)=exf(x)=e^x，在 [0,1][0,1] 上

M3=e.M_3=e.

所以

∣R2(1/4)∣≤e6∣14(−14)(−34)∣=e128≈0.02124.|R_2(1/4)| \leq \frac e6 \left|\frac14\left(-\frac14\right)\left(-\frac34\right)\right| =\frac e{128} \approx0.02124.

例 3：如何选择节点#

余项中节点影响因子是

ωn+1(x)=∏i=0n(x−xi).\omega_{n+1}(x)=\prod_{i=0}^n(x-x_i).

为了降低最大误差，需要让 max⁡∣ωn+1(x)∣\max|\omega_{n+1}(x)| 尽量小。高次等距节点常在端点附近导致 ∣ω∣|\omega| 很大；Chebyshev 型非等距节点能减轻端点振荡。

5.5 Runge 现象#

Runge 现象：在较大区间上使用高次等距节点插值时，插值多项式可能在端点附近剧烈振荡，增加节点数也不一定改善整体效果。

典型函数：

f(x)=11+25x2,x∈[−1,1].f(x)=\frac{1}{1+25x^2}, \qquad x\in[-1,1].

避免方法：

  • 使用分段低次插值；
  • 使用更合理的非等距节点；
  • 不盲目提高单个多项式次数。

关于 Hermite 插值#

Hermite 插值同时匹配函数值和导数值。若给出 n+1n+1 个节点，每个节点同时给 f(xi)f(x_i) 和 f′(xi)f'(x_i)，共有 2n+22n+2 个条件，通常构造次数不超过 2n+12n+1 的多项式。

本学期复习提纲明确不要求 Hermite 详细计算，掌握“条件数决定多项式最高次数”的基本思想即可。

本章检查清单#

  • 会写每个 Lagrange 基函数；
  • 会构造完整差商表；
  • 知道 Lagrange 与 Newton 结果相同；
  • 会用余项估计误差；
  • 能解释 Runge 现象和规避办法。

Chapter 6 函数逼近与最小二乘#

6.1 章节主线#

插值要求“每个节点完全通过”；最小二乘允许有残差，目标是让总体平方误差最小。

本章必须区分：

离散最小二乘#

给定有限数据点 (xi,yi)(x_i,y_i)，最小化

S(c)=∑i=1m[yi−∑j=0ncjϕj(xi)]2.S(c)=\sum_{i=1}^{m} \left[y_i-\sum_{j=0}^{n}c_j\phi_j(x_i)\right]^2.

写成矩阵：

min⁡c∥Ac−y∥22,\min_c\|Ac-y\|_2^2,

正规方程：

ATAc=ATy.A^TAc=A^Ty.

连续最佳平方逼近#

在函数空间中最小化

∥f−p∥22=∫ab[f(x)−p(x)]2w(x) dx.\|f-p\|_2^2 =\int_a^b[f(x)-p(x)]^2w(x)\,dx.

若

p(x)=∑j=0ncjϕj(x),p(x)=\sum_{j=0}^{n}c_j\phi_j(x),

则正交条件为

⟨f−p,ϕi⟩=0,i=0,…,n.\langle f-p,\phi_i\rangle=0, \qquad i=0,\ldots,n.

6.2 重点题型一：离散最小二乘正规方程#

例 1：中心化基函数#

数据为

xix_i012
yiy_i224

用

y=c0+c1(x−1)y=c_0+c_1(x-1)

拟合。

设计矩阵

A=[1−11011],y=[224].A= \begin{bmatrix} 1&-1\\ 1&0\\ 1&1 \end{bmatrix}, \qquad y= \begin{bmatrix}2\\2\\4\end{bmatrix}.ATA=[3002],ATy=[82].A^TA= \begin{bmatrix}3&0\\0&2\end{bmatrix}, \qquad A^Ty= \begin{bmatrix}8\\2\end{bmatrix}.

正规方程

[3002][c0c1]=[82].\begin{bmatrix}3&0\\0&2\end{bmatrix} \begin{bmatrix}c_0\\c_1\end{bmatrix} = \begin{bmatrix}8\\2\end{bmatrix}.

故

c0=83,c1=1.c_0=\frac83, \qquad c_1=1.

拟合函数

p(x)=83+(x−1)=x+53.p(x)=\frac83+(x-1)=x+\frac53.

残差 y−Acy-Ac 为

(13,−23,13)T,\left(\frac13,-\frac23,\frac13\right)^T,

残差平方和

19+49+19=23.\frac19+\frac49+\frac19=\frac23.

例 2：用直线拟合对称数据#

数据

(−1,1),(0,0),(1,1)(-1,1),(0,0),(1,1)

用 p(x)=c0+c1xp(x)=c_0+c_1x 拟合。

A=[1−11011],ATA=[3002],A= \begin{bmatrix} 1&-1\\1&0\\1&1 \end{bmatrix}, \qquad A^TA= \begin{bmatrix}3&0\\0&2\end{bmatrix},ATy=[20].A^Ty= \begin{bmatrix}2\\0\end{bmatrix}.

所以

c0=23,c1=0.c_0=\frac23, \qquad c_1=0.

最优直线为

p(x)=23.p(x)=\frac23.

残差平方和为

(1−23)2+(0−23)2+(1−23)2=23.\left(1-\frac23\right)^2+ \left(0-\frac23\right)^2+ \left(1-\frac23\right)^2 =\frac23.

为什么正规方程成立#

最优残差

r=y−Acr=y-Ac

必须与 AA 的所有列正交：

ATr=0.A^Tr=0.

因此

AT(y−Ac)=0⇒ATAc=ATy.A^T(y-Ac)=0 \Rightarrow A^TAc=A^Ty.

6.3 重点题型二：连续最佳平方逼近——一般基函数#

设

p(x)=c0ϕ0(x)+⋯+cnϕn(x).p(x)=c_0\phi_0(x)+\cdots+c_n\phi_n(x).

法方程为

∑j=0ncj⟨ϕj,ϕi⟩=⟨f,ϕi⟩.\sum_{j=0}^n c_j\langle\phi_j,\phi_i\rangle = \langle f,\phi_i\rangle.

矩阵中的

Gij=⟨ϕj,ϕi⟩G_{ij}=\langle\phi_j,\phi_i\rangle

称为 Gram 矩阵。

例 1：x2x^2 在 [0,1][0,1] 上的最佳一次逼近#

设

p(x)=a+bx.p(x)=a+bx.

正交条件：

∫01(x2−a−bx) dx=0,\int_0^1(x^2-a-bx)\,dx=0,∫01x(x2−a−bx) dx=0.\int_0^1x(x^2-a-bx)\,dx=0.

得到

a+b2=13,a+\frac b2=\frac13,a2+b3=14.\frac a2+\frac b3=\frac14.

解得

a=−16,b=1.a=-\frac16, \qquad b=1.

因此

p(x)=x−16.p(x)=x-\frac16.

例 2：x2x^2 在 [−1,1][-1,1] 上的最佳一次逼近#

仍设 p(x)=a+bxp(x)=a+bx。由于 x2x^2 为偶函数、xx 为奇函数，

⟨x2,x⟩=0,\langle x^2,x\rangle=0,

所以 b=0b=0。

a=⟨x2,1⟩⟨1,1⟩=2/32=13.a=\frac{\langle x^2,1\rangle}{\langle1,1\rangle} =\frac{2/3}{2}=\frac13.

因此

p(x)=13.p(x)=\frac13.

这说明利用奇偶性可以大幅简化积分。

6.4 重点题型三：正交基与 Legendre 多项式#

若基函数两两正交：

⟨ϕi,ϕj⟩=0,i≠j,\langle\phi_i,\phi_j\rangle=0, \qquad i\ne j,

则系数可直接分开计算：

ck=⟨f,ϕk⟩⟨ϕk,ϕk⟩.c_k=\frac{\langle f,\phi_k\rangle}{\langle\phi_k,\phi_k\rangle}.

在 [−1,1][-1,1] 上：

P0(x)=1,P1(x)=x,P2(x)=12(3x2−1).P_0(x)=1, \qquad P_1(x)=x, \qquad P_2(x)=\frac12(3x^2-1).

例 1：x5x^5 投影到 span⁡{1,x}\operatorname{span}\{1,x\}#

设

p(x)=a+bx.p(x)=a+bx.

由于 x5x^5 为奇函数，a=0a=0。

b=⟨x5,x⟩⟨x,x⟩=∫−11x6dx∫−11x2dx=2/72/3=37.b=\frac{\langle x^5,x\rangle}{\langle x,x\rangle} =\frac{\int_{-1}^1x^6dx}{\int_{-1}^1x^2dx} =\frac{2/7}{2/3}=\frac37.

故

p(x)=37x.p(x)=\frac37x.

例 2：区间变换后的 Legendre 基#

要在 [0,2][0,2] 上用二次多项式逼近 exe^x，而题目只给出 [−1,1][-1,1] 上的 Legendre 多项式。

令

t=x−1,t=x-1,

则 x∈[0,2]x\in[0,2] 对应 t∈[−1,1]t\in[-1,1]，dx=dtdx=dt。

采用基函数

1,t=x−1,12(3t2−1).1, \qquad t=x-1, \qquad \frac12(3t^2-1).

设

p(x)=c0P0(t)+c1P1(t)+c2P2(t).p(x)=c_0P_0(t)+c_1P_1(t)+c_2P_2(t).

因为 ex=et+1=e ete^x=e^{t+1}=e\,e^t，计算可得

c0=e2−12,c_0=\frac{e^2-1}{2},c1=3,c_1=3,c2=52(e2−7).c_2=\frac52(e^2-7).

因此

p(x)=e2−12+3(x−1)+52(e2−7)⋅3(x−1)2−12.p(x)= \frac{e^2-1}{2} +3(x-1) +\frac52(e^2-7) \cdot\frac{3(x-1)^2-1}{2}.

本题最容易丢分的地方是：直接把 [−1,1][-1,1] 上的 Pk(x)P_k(x) 套到 [0,2][0,2]，忘记变量平移。

6.5 离散拟合与连续逼近的区别#

项目离散最小二乘连续最佳平方逼近
数据有限个 (xi,yi)(x_i,y_i)已知完整函数 f(x)f(x)
目标∑iri2\sum_i r_i^2 最小∫abr(x)2w(x)dx\int_a^b r(x)^2w(x)dx 最小
内积向量点积/求和积分内积
方程ATAc=ATyA^TAc=A^Ty⟨f−p,ϕi⟩=0\langle f-p,\phi_i\rangle=0
正交残差向量与列空间正交误差函数与逼近空间正交

本章检查清单#

  • 会从基函数搭建设计矩阵；
  • 会算 ATAA^TA 和 ATyA^Ty；
  • 会计算残差平方和；
  • 连续问题会写积分正交条件；
  • 正交基会直接算投影系数；
  • 区间不同时会先作变量变换。

Chapter 7 数值微分与数值积分#

7.1 章节主线#

本章以 Taylor 展开为统一工具：

  • 用附近函数值近似导数；
  • 用离散节点的加权和近似积分；
  • 通过 Taylor 展开判断截断误差阶；
  • 通过选择特殊节点，提高代数精度。

7.2 重点题型一：差商公式与截断误差#

向前差商：

f′(x)≈f(x+h)−f(x)h,O(h).f'(x)\approx\frac{f(x+h)-f(x)}h, \qquad O(h).

向后差商：

f′(x)≈f(x)−f(x−h)h,O(h).f'(x)\approx\frac{f(x)-f(x-h)}h, \qquad O(h).

中心差商：

f′(x)≈f(x+h)−f(x−h)2h,O(h2).f'(x)\approx\frac{f(x+h)-f(x-h)}{2h}, \qquad O(h^2).

推导中心差商误差#

f(x+h)=f(x)+hf′(x)+h22f′′(x)+h36f(3)(ξ1),f(x+h)=f(x)+hf'(x)+\frac{h^2}{2}f''(x)+\frac{h^3}{6}f^{(3)}(\xi_1),f(x−h)=f(x)−hf′(x)+h22f′′(x)−h36f(3)(ξ2).f(x-h)=f(x)-hf'(x)+\frac{h^2}{2}f''(x)-\frac{h^3}{6}f^{(3)}(\xi_2).

两式相减并除以 2h2h，偶次项消去，因此误差为 O(h2)O(h^2)。

例 1：用中心差商求 ln⁡x\ln x 的导数#

已知

ln⁡0.9=−0.1053605,ln⁡1=0,ln⁡1.1=0.0953102.\ln0.9=-0.1053605, \quad \ln1=0, \quad \ln1.1=0.0953102.

在 x=1x=1 处取 h=0.1h=0.1：

(ln⁡x)′∣x=1≈ln⁡1.1−ln⁡0.90.2=1.0033535.(\ln x)'\big|_{x=1} \approx \frac{\ln1.1-\ln0.9}{0.2} =1.0033535.

精确值为 1。

例 2：比较向前与中心差商#

取 f(x)=exf(x)=e^x，在 x=0x=0、h=0.1h=0.1。

向前差商：

e0.1−10.1≈1.051709.\frac{e^{0.1}-1}{0.1}\approx1.051709.

中心差商：

e0.1−e−0.10.2≈1.001668.\frac{e^{0.1}-e^{-0.1}}{0.2}\approx1.001668.

中心差商明显更接近精确值 11，原因是其一阶误差项被对称抵消。

例 3：推导向前差商误差#

由

f(x+h)=f(x)+hf′(x)+h22f′′(ξ),f(x+h)=f(x)+hf'(x)+\frac{h^2}{2}f''(\xi),

可得

f(x+h)−f(x)h=f′(x)+h2f′′(ξ).\frac{f(x+h)-f(x)}h =f'(x)+\frac h2f''(\xi).

所以近似值减真值为

h2f′′(ξ)=O(h).\frac h2f''(\xi)=O(h).

7.3 重点题型二：复合梯形公式与误差#

将 [a,b][a,b] 等分为 nn 段：

h=b−an,xi=a+ih.h=\frac{b-a}{n}, \qquad x_i=a+ih.

复合梯形公式：

Tn=h2[f(a)+2∑i=1n−1f(xi)+f(b)].T_n= \frac h2 \left[ f(a)+2\sum_{i=1}^{n-1}f(x_i)+f(b) \right].

误差形式：

I−Tn=−b−a12h2f′′(ξ).I-T_n=-\frac{b-a}{12}h^2f''(\xi).

误差限：

∣I−Tn∣≤b−a12h2max⁡[a,b]∣f′′(x)∣.|I-T_n| \leq \frac{b-a}{12}h^2 \max_{[a,b]}|f''(x)|.

例 1：手算复合梯形#

用 n=4n=4 计算

∫01x2dx.\int_0^1x^2dx.

h=0.25h=0.25，节点函数值为

0,0.0625,0.25,0.5625,1.0, \quad0.0625, \quad0.25, \quad0.5625, \quad1.T4=0.252[0+2(0.0625+0.25+0.5625)+1]=0.34375.T_4=\frac{0.25}{2} [0+2(0.0625+0.25+0.5625)+1] =0.34375.

精确值为 1/31/3，实际

I−T4=−196≈−0.0104167.I-T_4=-\frac1{96}\approx-0.0104167.

由于 f′′(x)=2>0f''(x)=2>0，梯形连线位于凸函数图像上方，因此 T4>IT_4>I。

例 2：由误差要求确定等分数#

计算

∫011+x dx\int_0^1\sqrt{1+x}\,dx

要求梯形误差不超过 10−310^{-3}。

f′′(x)=−14(1+x)3/2,f''(x)=-\frac1{4(1+x)^{3/2}},

所以

max⁡[0,1]∣f′′(x)∣=14.\max_{[0,1]}|f''(x)|=\frac14.

h=1/nh=1/n，故

∣I−Tn∣≤1121n214=148n2.|I-T_n| \leq\frac1{12}\frac1{n^2}\frac14 =\frac1{48n^2}.

令

148n2≤10−3,\frac1{48n^2}\leq10^{-3},

得

n≥4.565.n\geq4.565.

因此至少取

n=5.n=5.

7.4 重点题型三：Gauss-Legendre 求积#

代数精度#

若求积公式对所有次数不超过 mm 的多项式均精确，而对某个 m+1m+1 次多项式不精确，则代数精度为 mm。

nn 点 Gauss-Legendre 公式具有最高代数精度

2n−1.2n-1.

标准形式：

∫−11f(t)dt≈∑k=1nAkf(tk).\int_{-1}^{1}f(t)dt \approx \sum_{k=1}^{n}A_kf(t_k).

一般区间变换#

对 [a,b][a,b]，令

x=a+b2+b−a2t,dx=b−a2dt.x=\frac{a+b}{2}+\frac{b-a}{2}t, \qquad dx=\frac{b-a}{2}dt.

于是

∫abf(x)dx=b−a2∫−11f(a+b2+b−a2t)dt.\int_a^bf(x)dx = \frac{b-a}{2} \int_{-1}^{1} f\left(\frac{a+b}{2}+\frac{b-a}{2}t\right)dt.

例 1：推导一点 Gauss 公式#

设

∫−11f(x)dx≈Af(ξ).\int_{-1}^{1}f(x)dx\approx Af(\xi).

令 f(x)=1f(x)=1：

2=A.2=A.

令 f(x)=xf(x)=x：

0=Aξ⇒ξ=0.0=A\xi\Rightarrow \xi=0.

所以

∫−11f(x)dx≈2f(0).\int_{-1}^{1}f(x)dx\approx2f(0).

该公式代数精度为 1。

对

f(x)=x6+2x+1,f(x)=x^6+2x+1,

近似值为

2f(0)=2.2f(0)=2.

精确值为

27+0+2=167,\frac27+0+2=\frac{16}{7},

因此不精确。

例 2：推导两点 Gauss 公式#

利用对称性设

∫−11f(x)dx≈A[f(−ξ)+f(ξ)].\int_{-1}^{1}f(x)dx \approx A[f(-\xi)+f(\xi)].

对 11 精确：

2A=2⇒A=1.2A=2\Rightarrow A=1.

对 x2x^2 精确：

2ξ2=23⇒ξ=13.2\xi^2=\frac23 \Rightarrow \xi=\frac1{\sqrt3}.

所以

∫−11f(x)dx≈f(−13)+f(13).\int_{-1}^{1}f(x)dx \approx f\left(-\frac1{\sqrt3}\right) +f\left(\frac1{\sqrt3}\right).

由于对称性，奇次多项式自动精确，因此代数精度达到 3。

例 3：四点 Gauss 公式与区间变换#

计算

I=∫0211+x2dx.I=\int_0^2\frac1{1+x^2}dx.

令

x=1+t,t∈[−1,1],dx=dt.x=1+t, \qquad t\in[-1,1], \qquad dx=dt.I=∫−1111+(1+t)2dt.I= \int_{-1}^{1} \frac1{1+(1+t)^2}dt.

四点节点和权重：

t=±0.8611363,±0.3399810,t=\pm0.8611363, \quad \pm0.3399810,A=0.3478548,0.6521452A=0.3478548, \quad0.6521452

（对称节点权重相同）。

代入

I≈∑k=14Ak1+(1+tk)2≈1.106740.I\approx \sum_{k=1}^4 \frac{A_k}{1+(1+t_k)^2} \approx1.106740.

精确值为 arctan⁡2≈1.107149\arctan2\approx1.107149。四点 Gauss 公式代数精度为

2×4−1=7.2\times4-1=7.

高斯积分的答题顺序#

  1. 写区间变换；
  2. 写 dxdx 的系数；
  3. 写变换后的被积函数；
  4. 查节点和权重；
  5. 对称节点逐项代入；
  6. 写代数精度 2n−12n-1。

本章检查清单#

  • 会用 Taylor 展开推差商误差；
  • 知道中心差商是 O(h2)O(h^2)；
  • 会写复合梯形权重 1,2,…,2,11,2,\ldots,2,1；
  • 会用误差界反求 nn；
  • Gauss 积分会先变换区间；
  • 会推一点、两点公式并判断代数精度。

Chapter 8 非线性方程求根#

8.1 章节主线#

本章方法可分为：

  • 区间法：二分法，稳健但较慢；
  • 开放法：Newton 法、割线法，收敛快但依赖初值；
  • 非线性方程组 Newton 法：每一步解一个线性方程组。

8.2 重点题型一：二分法与误差估计#

适用条件：

f∈C[a,b],f(a)f(b)<0.f\in C[a,b], \qquad f(a)f(b)<0.

每次取中点

ck=ak+bk2,c_k=\frac{a_k+b_k}{2},

根据符号保留含根子区间。

二分 nn 次后区间长度：

b−a2n.\frac{b-a}{2^n}.

若用区间中点作近似根，则误差不超过

b−a2n+1.\frac{b-a}{2^{n+1}}.

例 1：做三步二分#

求

f(x)=x3−x−1=0f(x)=x^3-x-1=0

在 [1,2][1,2] 内的根。

  • 第 1 步：c1=1.5c_1=1.5，f(c1)=0.875>0f(c_1)=0.875>0，新区间 [1,1.5][1,1.5]；
  • 第 2 步：c2=1.25c_2=1.25，f(c2)=−0.296875<0f(c_2)=-0.296875<0，新区间 [1.25,1.5][1.25,1.5]；
  • 第 3 步：c3=1.375c_3=1.375，f(c3)=0.224609>0f(c_3)=0.224609>0，新区间 [1.25,1.375][1.25,1.375]。

三步后区间长度为

123=0.125.\frac{1}{2^3}=0.125.

例 2：确定迭代次数#

初始区间长度为 1，希望中点误差不超过 5×10−55\times10^{-5}。

要求

12n+1≤5×10−5.\frac1{2^{n+1}}\leq5\times10^{-5}.

即

n+1≥log⁡2(20000)≈14.288.n+1\geq\log_2(20000)\approx14.288.

因此至少需要

n=14n=14

次二分。

有些教材把“第一个中点”记为第 0 次或第 1 次。答题时写清所用误差公式，可以避免计数争议。

8.3 重点题型二：标量 Newton 法与收敛阶#

Newton 迭代：

xk+1=xk−f(xk)f′(xk).x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}.

几何意义：在 (xk,f(xk))(x_k,f(x_k)) 处作切线，切线与 xx 轴交点作为下一次近似。

对单根 α\alpha，在适当条件和足够近初值下通常二次收敛：

∣ek+1∣≈C∣ek∣2.|e_{k+1}|\approx C|e_k|^2.

例 1：多项式 Newton 两步#

f(x)=x3−3x+1,x0=0.f(x)=x^3-3x+1, \qquad x_0=0.f′(x)=3x2−3.f'(x)=3x^2-3.

第一步：

x1=0−1−3=13.x_1=0-\frac1{-3}=\frac13.

第二步：

f(13)=127,f\left(\frac13\right)=\frac1{27},f′(13)=−83.f'\left(\frac13\right)=-\frac83.x2=13−1/27−8/3=13+172=2572≈0.34722.x_2=\frac13-\frac{1/27}{-8/3} =\frac13+\frac1{72} =\frac{25}{72} \approx0.34722.

例 2：求 2\sqrt2#

令

f(x)=x2−2.f(x)=x^2-2.

Newton 格式化简为

xk+1=12(xk+2xk).x_{k+1}=\frac12\left(x_k+\frac2{x_k}\right).

取 x0=1x_0=1：

x1=1.5,x_1=1.5,x2=12(1.5+21.5)=1712≈1.416667.x_2=\frac12\left(1.5+\frac2{1.5}\right) =\frac{17}{12} \approx1.416667.

例 3：重根时收敛阶下降#

f(x)=(x−1)2.f(x)=(x-1)^2.

Newton 法：

xk+1=xk−(xk−1)22(xk−1)=xk+12.x_{k+1}=x_k-\frac{(x_k-1)^2}{2(x_k-1)} =\frac{x_k+1}{2}.

误差 ek=xk−1e_k=x_k-1 满足

ek+1=12ek.e_{k+1}=\frac12e_k.

所以只有线性收敛。若已知重数 m=2m=2，可用修正 Newton 法

xk+1=xk−mf(xk)f′(xk),x_{k+1}=x_k-m\frac{f(x_k)}{f'(x_k)},

恢复更快收敛。

收敛阶定义#

若

lim⁡k→∞∣ek+1∣∣ek∣p=C,0<C<∞,\lim_{k\to\infty} \frac{|e_{k+1}|}{|e_k|^p}=C, \qquad 0<C<\infty,

则称迭代具有 pp 阶收敛：

  • p=1p=1：线性；
  • 1<p<21<p<2：超线性；
  • p=2p=2：二次。

8.4 重点题型三：非线性方程组 Newton 法#

设

F(x)=[f1(x1,…,xn)⋮fn(x1,…,xn)]=0.F(x)= \begin{bmatrix} f_1(x_1,\ldots,x_n)\\ \vdots\\ f_n(x_1,\ldots,x_n) \end{bmatrix}=0.

Jacobian 矩阵

J(x)=[∂fi∂xj].J(x)= \left[\frac{\partial f_i}{\partial x_j}\right].

每一步解

J(x(k))Δx(k)=−F(x(k)),J(x^{(k)})\Delta x^{(k)}=-F(x^{(k)}),

再更新

x(k+1)=x(k)+Δx(k).x^{(k+1)}=x^{(k)}+\Delta x^{(k)}.

不要实际计算 J−1J^{-1}。

例 1：圆与直线#

F(x,y)=[x2+y2−1x−y].F(x,y)= \begin{bmatrix} x^2+y^2-1\\x-y \end{bmatrix}.J(x,y)=[2x2y1−1].J(x,y)= \begin{bmatrix} 2x&2y\\1&-1 \end{bmatrix}.

从 (1,1)(1,1) 出发：

F(1,1)=[10],J(1,1)=[221−1].F(1,1)= \begin{bmatrix}1\\0\end{bmatrix}, \qquad J(1,1)= \begin{bmatrix}2&2\\1&-1\end{bmatrix}.

解

[221−1][ΔxΔy]=[−10].\begin{bmatrix}2&2\\1&-1\end{bmatrix} \begin{bmatrix}\Delta x\\\Delta y\end{bmatrix} = \begin{bmatrix}-1\\0\end{bmatrix}.

得到

Δx=Δy=−14.\Delta x=\Delta y=-\frac14.

所以

(x(1),y(1))=(34,34).(x^{(1)},y^{(1)})= \left(\frac34,\frac34\right).

例 2：圆与三次曲线#

F(x,y)=[x2+y2−4x3−y],(x(0),y(0))=(1,1).F(x,y)= \begin{bmatrix} x^2+y^2-4\\x^3-y \end{bmatrix}, \qquad (x^{(0)},y^{(0)})=(1,1).J(x,y)=[2x2y3x2−1].J(x,y)= \begin{bmatrix} 2x&2y\\3x^2&-1 \end{bmatrix}.

在 (1,1)(1,1)：

F(1,1)=(−2,0)T,J(1,1)=[223−1].F(1,1)=(-2,0)^T, \qquad J(1,1)= \begin{bmatrix}2&2\\3&-1\end{bmatrix}.

解

{2Δx+2Δy=2,3Δx−Δy=0,\begin{cases} 2\Delta x+2\Delta y=2,\\ 3\Delta x-\Delta y=0, \end{cases}

得

Δx=14,Δy=34.\Delta x=\frac14, \qquad \Delta y=\frac34.

所以

(x(1),y(1))=(54,74).(x^{(1)},y^{(1)})= \left(\frac54,\frac74\right).

8.5 低优先级补充：割线法#

当 f′(x)f'(x) 难以计算时，用两点割线斜率代替导数：

xk+1=xk−f(xk)xk−xk−1f(xk)−f(xk−1).x_{k+1} =x_k- f(x_k) \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}.

例 1#

对

f(x)=x3−3x+1,x0=0,x1=1,f(x)=x^3-3x+1, \qquad x_0=0, \qquad x_1=1,f(0)=1,f(1)=−1.f(0)=1, \qquad f(1)=-1.x2=1−(−1)1−0−1−1=0.5.x_2=1- (-1)\frac{1-0}{-1-1} =0.5.

例 2：Newton 与割线的比较#

  • Newton 每步需要一个函数值和一个导数值，单根附近二次收敛；
  • 割线法每步使用两个函数值，不需导数，收敛阶约为 1.6181.618；
  • 二分法收敛最稳健，但仅线性收敛。

本章检查清单#

  • 会用区间长度反求二分次数；
  • Newton 会写切线公式并手算两步；
  • 知道单根二次、重根可能线性；
  • 方程组会写 Jacobian 并解增量方程；
  • 不把 x(k+1)x^{(k+1)} 直接写成 −J−1F-J^{-1}F 而漏掉 x(k)x^{(k)}。

Chapter 9 常微分方程初值问题#

9.1 章节主线#

考虑初值问题

y′=f(t,y),y(t0)=y0.y'=f(t,y), \qquad y(t_0)=y_0.

数值解不试图写出完整函数表达式，而是在网格

tn=t0+nht_n=t_0+nh

上计算近似值

yn≈y(tn).y_n\approx y(t_n).

本学期考试重点限于 Euler 法及局部截断误差。老师在 lesson15 中说明：复杂 Runge-Kutta、多步法与稳定性分析不考；隐式 Euler 可能与 Newton 法结合。

9.2 重点题型一：显式 Euler 法#

yn+1=yn+hf(tn,yn).y_{n+1}=y_n+h f(t_n,y_n).

几何意义：从当前点沿当前切线斜率走一步。

例 1：线性方程两步#

y′=−2y+t,y(0)=1,h=0.25.y'=-2y+t, \qquad y(0)=1, \qquad h=0.25.

t0=0,y0=1t_0=0,y_0=1：

y1=1+0.25(−2)=0.5.y_1=1+0.25(-2)=0.5.

t1=0.25,y1=0.5t_1=0.25,y_1=0.5：

y2=0.5+0.25[−2(0.5)+0.25]=0.3125.y_2=0.5+0.25[-2(0.5)+0.25] =0.3125.

例 2：非自治方程#

y′=y−t2+1,y(0)=0.5,h=0.2.y'=y-t^2+1, \qquad y(0)=0.5, \qquad h=0.2.

第一步：

y1=0.5+0.2(0.5−0+1)=0.8.y_1=0.5+0.2(0.5-0+1)=0.8.

第二步：

y2=0.8+0.2(0.8−0.22+1)=0.8+0.2(1.76)=1.152.y_2=0.8+0.2(0.8-0.2^2+1) =0.8+0.2(1.76) =1.152.

易错点#

  • 第二步必须使用 t1=t0+ht_1=t_0+h 和刚算出的 y1y_1；
  • yny_n 是数值近似，y(tn)y(t_n) 是真解；
  • 写结果时最好标注 yn≈y(tn)y_n\approx y(t_n)。

9.3 重点题型二：隐式 Euler 法#

yn+1=yn+hf(tn+1,yn+1).y_{n+1}=y_n+h f(t_{n+1},y_{n+1}).

右侧含未知的 yn+1y_{n+1}，每一步需要解方程。

例 1：线性隐式 Euler#

仍取

y′=−2y+t,y(0)=1,h=0.25.y'=-2y+t, \qquad y(0)=1, \qquad h=0.25.

第一步：

y1=1+0.25(−2y1+0.25).y_1=1+0.25(-2y_1+0.25).1.5y1=1.0625⇒y1=0.708333.1.5y_1=1.0625 \Rightarrow y_1=0.708333.

第二步：

y2=y1+0.25(−2y2+0.5).y_2=y_1+0.25(-2y_2+0.5).1.5y2=y1+0.125=0.833333,1.5y_2=y_1+0.125 =0.833333,y2=0.555556.y_2=0.555556.

例 2：非线性隐式方程与 Newton 法#

y′=y2−t,y(0)=1,h=0.1.y'=y^2-t, \qquad y(0)=1, \qquad h=0.1.

隐式 Euler 第一步：

y1=1+0.1(y12−0.1).y_1=1+0.1(y_1^2-0.1).

令

g(z)=z−1−0.1(z2−0.1).g(z)=z-1-0.1(z^2-0.1).

求 g(z)=0g(z)=0。Newton 迭代为

z(m+1)=z(m)−z(m)−1−0.1[(z(m))2−0.1]1−0.2z(m).z^{(m+1)} =z^{(m)}- \frac{z^{(m)}-1-0.1[(z^{(m)})^2-0.1]} {1-0.2z^{(m)}}.

取初值 z(0)=y0=1z^{(0)}=y_0=1：

z(1)=1−−0.090.8=1.1125.z^{(1)}=1-\frac{-0.09}{0.8}=1.1125.

再迭代一次可得约

y1≈1.1142.y_1\approx1.1142.

考试若把隐式 Euler 与 Newton 结合，结构通常就是：

  1. 写隐式格式；
  2. 整理为 g(yn+1)=0g(y_{n+1})=0；
  3. 对 gg 做一到两步 Newton。

9.4 重点题型三：局部截断误差#

局部截断误差考察：假设第 nn 步输入的是精确值 y(tn)y(t_n)，只执行一步数值格式后产生多少误差。

对显式 Euler，定义

Tn+1=y(tn+1)−[y(tn)+hf(tn,y(tn))].T_{n+1} =y(t_{n+1})- [y(t_n)+hf(t_n,y(t_n))].

由于

f(tn,y(tn))=y′(tn),f(t_n,y(t_n))=y'(t_n),

Taylor 展开：

y(tn+h)=y(tn)+hy′(tn)+h22y′′(ξn).y(t_n+h) =y(t_n)+hy'(t_n)+\frac{h^2}{2}y''(\xi_n).

所以

Tn+1=h22y′′(ξn)=O(h2).T_{n+1}=\frac{h^2}{2}y''(\xi_n)=O(h^2).

显式 Euler 的：

  • 一步局部截断误差：O(h2)O(h^2)；
  • 全局误差：O(h)O(h)；
  • 方法阶数：1 阶。

例 1：对具体方程写局部误差#

y′=y,y(0)=1.y'=y, \qquad y(0)=1.

真解 y(t)=ety(t)=e^t。从 tnt_n 做一步显式 Euler：

y(tn+1)−[y(tn)+hy(tn)]=etn(eh−1−h).y(t_{n+1})-[y(t_n)+hy(t_n)] =e^{t_n}(e^h-1-h).

利用

eh=1+h+h22+O(h3),e^h=1+h+\frac{h^2}{2}+O(h^3),

得

Tn+1=etnh22+O(h3)=O(h2).T_{n+1} =e^{t_n}\frac{h^2}{2}+O(h^3) =O(h^2).

例 2：隐式 Euler 的局部误差#

隐式 Euler 使用

y(tn)+hy′(tn+1).y(t_n)+hy'(t_{n+1}).

在 tn+1t_{n+1} 向后展开：

y(tn)=y(tn+1)−hy′(tn+1)+h22y′′(ξ).y(t_n) =y(t_{n+1})-hy'(t_{n+1})+\frac{h^2}{2}y''(\xi).

所以

y(tn+1)−[y(tn)+hy′(tn+1)]=−h22y′′(ξ)=O(h2).y(t_{n+1})-[y(t_n)+hy'(t_{n+1})] =-\frac{h^2}{2}y''(\xi)=O(h^2).

显式和隐式 Euler 的局部截断误差阶相同，稳定性表现不同；本学期不要求展开稳定性分析。

局部误差与实际累计误差#

  • 局部截断误差假设上一步没有误差，只看新一步格式造成的误差；
  • 实际全局误差包含前面所有误差的传播和累积；
  • 因此局部 O(h2)O(h^2) 并不代表最终结果是二阶，Euler 的全局阶仍为 1。

本章检查清单#

  • 显式 Euler 会连续算两步；
  • 隐式 Euler 会整理方程；
  • 非线性隐式方程会结合 Newton；
  • 会从 Taylor 展开推出局部 O(h2)O(h^2)；
  • 能区分局部误差 O(h2)O(h^2) 与全局误差 O(h)O(h)。

综合易错点与交叉联系#

1. Taylor 展开贯穿多章#

Taylor 展开是以下误差分析的共同来源：

  • Chapter 1：稳定表达与误差线性化；
  • Chapter 5：插值余项；
  • Chapter 7：差商和积分公式误差；
  • Chapter 8：Newton 收敛阶；
  • Chapter 9：Euler 局部截断误差。

看到“误差阶”“余项”“截断误差”，优先考虑 Taylor 展开。

2. 正交思想贯穿多章#

  • 最小二乘：残差与列空间正交；
  • 连续最佳平方逼近：误差与逼近空间正交；
  • CG：残差正交、搜索方向 AA-共轭；
  • Householder/Givens：构造正交矩阵；
  • Legendre：基函数正交；
  • Gauss：节点来自正交多项式零点。

3. 解方程组是多个算法的内部步骤#

  • LU：直接解线性方程组；
  • 反幂法：每一步解 (A−μI)y=v(A-\mu I)y=v；
  • 非线性方程组 Newton：每一步解 JΔx=−FJ\Delta x=-F；
  • 隐式 Euler：每一步可能解标量或非线性方程。

因此 Chapter 2 的前代回代是后面多个算法的基础。

4. 插值、拟合、逼近三者区分#

  • 插值：必须通过全部给定数据点；
  • 离散拟合：允许偏离数据点，使离散残差平方和最小；
  • 连续逼近：使整个区间上的积分平方误差最小。

5. “方法精度”常见结论#

方法误差/代数精度
向前、向后差商O(h)O(h)
中心差商O(h2)O(h^2)
复合梯形全局 O(h2)O(h^2)
nn 点 Gauss-Legendre代数精度 2n−12n-1
Newton 法（单根附近）二次收敛
二分法线性收敛
显式 Euler 局部误差O(h2)O(h^2)
显式 Euler 全局误差O(h)O(h)

考前必须能默写或识别的公式#

误差#

e=x−x∗,er=x−x∗x.e=x-x^*, \qquad e_r=\frac{x-x^*}{x}.

LU#

A=LU,PA=LU,Ly=Pb,Ux=y.A=LU, \qquad PA=LU, \qquad Ly=Pb, \qquad Ux=y.

Jacobi / GS / SOR#

xi(k+1)=1aii(bi−∑j≠iaijxj(k)).x_i^{(k+1)}=\frac1{a_{ii}} \left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right).xi(k+1)=1aii(bi−∑j<iaijxj(k+1)−∑j>iaijxj(k)).x_i^{(k+1)}=\frac1{a_{ii}} \left(b_i- \sum_{j<i}a_{ij}x_j^{(k+1)}- \sum_{j>i}a_{ij}x_j^{(k)}\right).xi(k+1)=(1−ω)xi(k)+ω×(GS 新值).x_i^{(k+1)}=(1-\omega)x_i^{(k)}+ \omega\times(\text{GS 新值}).

CG#

r(0)=b−Ax(0),d(0)=r(0),r^{(0)}=b-Ax^{(0)}, \qquad d^{(0)}=r^{(0)},λ0=⟨r(0),r(0)⟩⟨d(0),Ad(0)⟩,x(1)=x(0)+λ0d(0).\lambda_0=\frac{\langle r^{(0)},r^{(0)}\rangle} {\langle d^{(0)},Ad^{(0)}\rangle}, \qquad x^{(1)}=x^{(0)}+\lambda_0d^{(0)}.βk−1=−⟨r(k),Ad(k−1)⟩⟨d(k−1),Ad(k−1)⟩,d(k)=r(k)+βk−1d(k−1),\beta_{k-1}=-\frac{\langle r^{(k)},Ad^{(k-1)}\rangle} {\langle d^{(k-1)},Ad^{(k-1)}\rangle}, \qquad d^{(k)}=r^{(k)}+\beta_{k-1}d^{(k-1)},λk=⟨r(k),d(k)⟩⟨d(k),Ad(k)⟩,x(k+1)=x(k)+λkd(k).\lambda_k=\frac{\langle r^{(k)},d^{(k)}\rangle} {\langle d^{(k)},Ad^{(k)}\rangle}, \qquad x^{(k+1)}=x^{(k)}+\lambda_kd^{(k)}.

幂法 / 反幂法#

wk+1=Avk,vk+1=wk+1∥wk+1∥∞.w_{k+1}=Av_k, \qquad v_{k+1}=\frac{w_{k+1}}{\|w_{k+1}\|_\infty}.(A−μI)yk+1=vk.(A-\mu I)y_{k+1}=v_k.

Householder / Givens#

H=I−2uuTuTu.H=I-2\frac{uu^T}{u^Tu}.G=[cs−sc],c=aa2+b2,s=ba2+b2.G= \begin{bmatrix}c&s\\-s&c\end{bmatrix}, \qquad c=\frac a{\sqrt{a^2+b^2}}, \qquad s=\frac b{\sqrt{a^2+b^2}}.

插值#

Ln(x)=∑k=0nyk∏i≠kx−xixk−xi.L_n(x)=\sum_{k=0}^ny_k \prod_{i\ne k}\frac{x-x_i}{x_k-x_i}.Pn(x)=f[x0]+f[x0,x1](x−x0)+⋯ .P_n(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots.Rn(x)=f(n+1)(ξ)(n+1)!∏i=0n(x−xi).R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n(x-x_i).

最小二乘#

ATAc=ATy.A^TAc=A^Ty.⟨f−p,ϕi⟩=0.\langle f-p,\phi_i\rangle=0.

数值微分与积分#

f′(x)≈f(x+h)−f(x−h)2h.f'(x)\approx\frac{f(x+h)-f(x-h)}{2h}.Tn=h2[f(a)+2∑i=1n−1f(xi)+f(b)].T_n=\frac h2 \left[f(a)+2\sum_{i=1}^{n-1}f(x_i)+f(b)\right].∣I−Tn∣≤b−a12h2max⁡∣f′′∣.|I-T_n| \leq\frac{b-a}{12}h^2\max|f''|.n 点 Gauss 的代数精度=2n−1.n\text{ 点 Gauss 的代数精度}=2n-1.

非线性方程#

xk+1=xk−f(xk)f′(xk).x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}.J(x(k))Δx(k)=−F(x(k)),x(k+1)=x(k)+Δx(k).J(x^{(k)})\Delta x^{(k)}=-F(x^{(k)}), \qquad x^{(k+1)}=x^{(k)}+\Delta x^{(k)}.

Euler#

yn+1=yn+hf(tn,yn).y_{n+1}=y_n+hf(t_n,y_n).yn+1=yn+hf(tn+1,yn+1).y_{n+1}=y_n+hf(t_{n+1},y_{n+1}).Tn+1=O(h2),全局误差=O(h).T_{n+1}=O(h^2), \qquad \text{全局误差}=O(h).

最后半天复习安排#

第一轮：2–3 小时#

按顺序快速阅读：

  1. Chapter 2：LU；
  2. Chapter 3：CG；
  3. Chapter 4：幂法、反幂法、两种正交变换；
  4. Chapter 5：两种插值和余项；
  5. Chapter 6：离散与连续两类最小二乘；
  6. Chapter 7：Gauss、梯形、中心差商；
  7. Chapter 8：Newton；
  8. Chapter 9：Euler；
  9. 最后回看 Chapter 1。

第二轮：3–4 小时#

每章至少独立完成以下一道题：

  • 一道 LU 分解并求解；
  • 一道 CG 两步；
  • 一道幂法或移位反幂法；
  • 一道 Householder 或 Givens；
  • 一道 Lagrange、一套差商表；
  • 一道离散最小二乘、一道连续投影；
  • 一道梯形误差反求 nn、一道 Gauss 区间变换；
  • 一道非线性方程组 Newton；
  • 一道 Euler 两步和局部截断误差。

第三轮：1–2 小时#

做一套样卷，严格控制在 120 分钟内。检查：

  • 是否写出了过程公式；
  • 是否误用旧值/新值；
  • 是否漏乘区间变换的 (b−a)/2(b-a)/2；
  • 是否在部分选主元后忘记变换 bb；
  • 是否把连续逼近写成离散正规方程；
  • 是否把 Euler 局部 O(h2)O(h^2) 写成全局二阶。

最终自测问题#

若下面每个问题都能在 30 秒内回答，基础框架已经完整：

  1. 为什么部分选主元更稳定？
  2. Jacobi 与 Gauss-Seidel 的核心区别是什么？
  3. CG 为什么要求对称正定？
  4. 反幂法为什么要求解线性方程组？
  5. Householder 与 Givens 都在做什么？
  6. Lagrange 与 Newton 为什么得到相同多项式？
  7. 插值和最小二乘有什么区别？
  8. 离散最小二乘与连续最佳平方逼近怎样区分？
  9. 中心差商为什么比单边差商高一阶？
  10. nn 点 Gauss 公式的代数精度是多少？
  11. Newton 法怎样推广到方程组？
  12. Euler 法的局部误差和全局误差分别是什么阶？
Final：计算方法课程重点
https://www.sleepyfish2031.top/posts/课程笔记/计算方法/计算方法课程重点/
作者
Sleepyfish
发布于
2026-06-27
许可协议
CC BY-NC-SA 4.0
FinalPLUS：计算方法课程重点
Chapter9：常微分方程数值解法
© 2026 Sleepyfish. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari