概述#

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

[!NOTE] 材料依据与边界本版已重新逐章读取你上传的 Chapter1–Chapter9 原始笔记，并与《25–26 计算方法期末复习提纲》、lesson15 后半段复习课、两套样卷及答案、24–25 回忆卷交叉核对。符号原则上服从各章原笔记；当样卷或公式表采用另一套记号时，会明确给出对应关系。

[!SUCCESS] 本次修订重点

重要公式后均补充“符号说明”，解释每个量的含义、上下标和使用条件；

补全了 LU 多右端项、部分选主元对比、CG 两步、Legendre 连续逼近、四点 Gauss、二分法最终误差、隐式 Euler 联立 Newton 等原先过于简略的例题；

统一 Chapter1–9 的记号，并在存在教材/公式表双记号时给出明确对应关系；

例题尽量按“题目—公式—代入—最终答案”写全，便于直接照着练习。

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

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

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

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

[!IMPORTANT] 全文统一记号

$x^*$ ：标量真值或方程真根； $x^{(k)}$ ：第 $k$ 次迭代得到的向量或标量近似。二者上标含义不同。

符号粗细服从各章原笔记：Chapter 2–4 常用普通 $x,b,r,d$ 表示向量；Chapter 6、8 为避免与标量混淆，使用 $\boldsymbol a,\boldsymbol y,\boldsymbol x,\boldsymbol F,\boldsymbol J$ 。

$A^T$ ：矩阵 $A$ 的转置； $I$ ：单位矩阵； $\langle u,v\rangle=u^Tv$ ：实向量内积。

$\|u\|_2$ ：二范数； $\|u\|_\infty=\max_i|u_i|$ ：无穷范数。

$O(h^p)$ ：当 $h\to0$ 时，误差的主量级至多与 $h^p$ 同阶。

Chapter 3 的 CG 统一使用搜索方向 $d^{(k)}$ 、步长 $\lambda_k$ 、方向系数 $\beta_k$ 。原笔记常用的 $\alpha_k$ 与这里的 $\lambda_k$ 表示同一个“步长”。

Chapter 4 幂法统一使用 $x^{(k)}$ 表示归一化向量、 $y^{(k+1)}=Ax^{(k)}$ 表示未归一化向量、 $m_{k+1}$ 表示归一化因子。

Chapter 6 统一使用 $\varphi_j(x)$ 表示基函数、 $a_j$ 表示待定系数；题目若使用 $c_j$ ，只需作同名替换。

Chapter 9 一般公式使用自变量 $x$ ；具体时间问题仍可写成 $t$ 。

复习范围与优先级#

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

LU 分解、前代回代、部分选主元；
CG 法前两步；
幂法、反幂法或移位反幂法；
Householder 与 Givens 变换；
Lagrange、Newton 插值和插值误差；
离散最小二乘正规方程、连续最佳平方逼近；
中心差商、复合梯形公式、高斯积分；
Newton 法、非线性方程组 Newton 法；
显式/隐式 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 公式和割线法。本笔记保留与现行范围仍有关的思想或简要补充，但不将它们放在最高优先级。

一页式答题原则#

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

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

1.1 章节主线#

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

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

设 $x$ 为真值， $x^*$ 为近似值：

e(x^*)=x-x^*, \qquad |e(x^*)|=|x-x^*|,

e_r(x^*)=\frac{x-x^*}{x}, \qquad |e_r(x^*)|=\frac{|x-x^*|}{|x|}.

[!TIP] 符号说明

$x$ ：准确值或真值；

$x^*$ ：用于代替真值的近似值；

$e(x^*)$ ：绝对误差，可正可负；

$|e(x^*)|$ ：绝对误差大小；

$e_r(x^*)$ ：相对误差，表示误差相对真值的比例；

若真值未知，常用 $|x^*|$ 暂时代替分母作估计，并应注明“近似相对误差”。

若只能证明

|x-x^*|\le \varepsilon,

则 $\varepsilon$ 称为绝对误差限，真值满足

x\in[x^*-\varepsilon,\;x^*+\varepsilon].

[!TIP] 符号说明

$\varepsilon>0$ ：给定或估计得到的误差上界；

区间端点 $x^*\pm\varepsilon$ ：真值可能落入的范围。

有效数字判定#

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

|x-x^*| \le \frac12\,10^{m-n+1}.

[!TIP] 符号说明

$m$ ：近似值第一位非零数字所在的十进制位阶。例如 $12.340$ 的第一位非零数字 $1$ 位于 $10^1$ ，故 $m=1$ ；

$n$ ：希望保证的有效数字位数；

右端是保证 $n$ 位有效数字所允许的最大绝对误差。

例如 $x^*=12.340$ ：

保证 4 位有效数字： $\frac12 10^{1-4+1}=0.005$ ；
保证 5 位有效数字： $\frac12 10^{1-5+1}=0.0005$ 。

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

例 1：已知真值#

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

解：

e(x^*)=\pi-3.14\approx 0.00159265,

|e_r(x^*)|=\frac{0.00159265}{\pi}\approx 5.0696\times 10^{-4}.

$3.14$ 的首位在 $10^0$ 位：

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

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

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

已知 $x^*=12.340$ ，且

12.338\leq x\leq 12.342.

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

解：

e(x^*)=x-12.340\in[-0.002,0.002],\qquad |e(x^*)|\leq 0.002.

相对误差满足

e_r(x^*)=1-\frac{12.340}{x}.

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

|e_r(x^*)|\leq \max\left\{\frac{0.002}{12.338},\frac{0.002}{12.342}\right\} \approx 1.621\times 10^{-4}.

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

易错点#

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

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

对多元函数

z=f(x_1,\ldots,x_n),

一阶误差传播公式为

\Delta z \approx \sum_{i=1}^{n} \frac{\partial f}{\partial x_i} \Delta x_i.

若只知道各输入误差的大小，通常估计

|\Delta z| \lesssim \sum_{i=1}^{n} \left| \frac{\partial f}{\partial x_i} \right| |\Delta x_i|.

[!TIP] 符号说明

$x_i$ ：第 $i$ 个输入量；

$\Delta x_i$ ：第 $i$ 个输入量的微小扰动或误差；

$z=f(x_1,\ldots,x_n)$ ：由输入量计算得到的输出；

$\Delta z$ ：输入误差传播到输出后引起的变化；

$\partial f/\partial x_i$ ：输出对第 $i$ 个输入的敏感程度；

$\lesssim$ ：一阶近似意义下受右侧控制，忽略了二阶及更高阶小量。

例 1：乘积的误差传播#

已知

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

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

解：

z=2\times3^2=18.

\frac{\partial z}{\partial x}=y^2=9,\qquad \frac{\partial z}{\partial y}=2xy=12.

所以

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

相对误差约为

\frac{|\Delta z|}{|z|}\lesssim \frac{0.33}{18}=1.833\%.

也可直接使用相对形式：

\frac{\Delta z}{z}\approx \frac{\Delta x}{x}+2\frac{\Delta y}{y}.

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

设

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

解：

f=2.5,

\frac{\partial f}{\partial x}=\frac1y=\frac14, \qquad \frac{\partial f}{\partial y}=-\frac{x}{y^2}=-\frac{10}{16}.

故

|\Delta f|\lesssim \frac14(0.02)+\frac{10}{16}(0.01) =0.01125.

相对误差限约为

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

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

把

x=1.2345, \qquad y=2.71828

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

解：

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

原乘积为

xy\approx 3.35571666,

舍入后乘积为

\hat x\hat y\approx 3.35710050.

实际舍入传播误差为

\hat x\hat y-xy\approx 0.00138384.

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

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

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

例 1：二次方程小根#

方程

x^2+1000x-1=0

的正根为

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

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

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

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

例 2：平方根之差#

直接计算

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

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

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

例 3： $1-\cos x$ #

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

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

于是

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

更适合小 $x$ 数值计算。

本章检查清单#

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

Chapter 2 高斯消去与 LU 分解#

2.1 章节主线#

高斯消去把线性方程组

Ax=b

化为上三角方程组。若把消去乘子保存下来，就得到

A=LU.

其中 $L$ 为单位下三角矩阵， $U$ 为上三角矩阵。求解时分两步：

Ly=b, \qquad Ux=y.

若使用部分选主元，则分解形式为

PA=LU,

相应的求解顺序为

Ly=Pb, \qquad Ux=y.

[!TIP] 符号说明

$A\in\mathbb R^{n\times n}$ ：原系数矩阵；

$x\in\mathbb R^n$ ：待求未知向量；

$b\in\mathbb R^n$ ：右端向量；

$L$ ：对角元全为 1 的下三角矩阵，其下三角元素保存消去乘子；

$U$ ：消元后得到的上三角矩阵；

$y$ ：前代过程中引入的中间向量；

$P$ ：记录行交换的置换矩阵；左乘 $P$ 会按同样顺序交换 $A$ 和 $b$ 的行。

一般前代公式为

y_i = b_i' - \sum_{j=1}^{i-1}l_{ij}y_j, \qquad i=1,2,\ldots,n,

其中无选主元时 $b'=b$ ，部分选主元时 $b'=Pb$ 。

一般回代公式为

x_i = \frac{1}{u_{ii}} \left( y_i-\sum_{j=i+1}^{n}u_{ij}x_j \right), \qquad i=n,n-1,\ldots,1.

[!TIP] 符号说明

$l_{ij}$ ： $L$ 的第 $(i,j)$ 个元素；

$u_{ij}$ ： $U$ 的第 $(i,j)$ 个元素；

$b_i'$ ：换行后的右端向量第 $i$ 个分量；

前代按 $i=1\to n$ 计算；回代按 $i=n\to1$ 计算。

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

通用手算规则#

第 $k$ 步消去乘子为

l_{ik} = \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}, \qquad i=k+1,\ldots,n.

相应更新为

a_{ij}^{(k+1)} = a_{ij}^{(k)} - l_{ik}a_{kj}^{(k)}, \qquad j=k+1,\ldots,n.

[!TIP] 符号说明

$k$ ：当前消元步，也是当前主元所在的行、列编号；

$a_{kk}^{(k)}$ ：第 $k$ 步开始时的主元；

$a_{ik}^{(k)}$ ：第 $k$ 步开始时，第 $i$ 行第 $k$ 列待消元素；

$l_{ik}$ ：用第 $k$ 行消去第 $i$ 行时的乘子；

上标 $(k)$ 表示“经过前 $k-1$ 轮更新后的元素”，不表示乘方。

消去后的上三角系数进入 $U$ ；
消去乘子进入 $L$ 的对应位置；
$L$ 的对角线全为 1。

例 1：三对角矩阵#

设

A= \begin{bmatrix} 2&-1&0\\ -1&2&-1\\ 0&-1&2 \end{bmatrix}.

第一步：

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

第二行更新后：

[0,\frac32,-1].

第二步：

l_{32}=\frac{-1}{3/2}=-\frac23.

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

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

所以

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\times3$ 矩阵#

设

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

第一列：

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

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

第二列：

l_{32}=1.

得到

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}.

易错点#

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

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

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

求解

Ax= \begin{bmatrix}1\\0\\1\end{bmatrix}.

先解 $Ly=b$ ：

y_1=1,

-\frac12y_1+y_2=0\Rightarrow y_2=\frac12,

-\frac23y_2+y_3=1\Rightarrow y_3=\frac43.

再解 $Ux=y$ ：

\frac43x_3=\frac43\Rightarrow x_3=1,

\frac32x_2-x_3=\frac12\Rightarrow x_2=1,

2x_1-x_2=1\Rightarrow x_1=1.

所以

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

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

题目： 已知

A= \begin{bmatrix} 1&2&0\\ 2&5&1\\ 0&1&3 \end{bmatrix} = \underbrace{ \begin{bmatrix} 1&0&0\\ 2&1&0\\ 0&1&1 \end{bmatrix}}_{L} \underbrace{ \begin{bmatrix} 1&2&0\\ 0&1&1\\ 0&0&2 \end{bmatrix}}_{U}.

利用同一组 $L,U$ ，分别求解

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

解第一个右端项：

先解

Ly= \begin{bmatrix}1\\4\\5\end{bmatrix}.

逐行前代：

y_1=1,

2y_1+y_2=4 \Rightarrow y_2=2,

y_2+y_3=5 \Rightarrow y_3=3.

所以

y=(1,2,3)^T.

再解 $Ux=y$ ：

2x_3=3 \Rightarrow x_3=\frac32,

x_2+x_3=2 \Rightarrow x_2=\frac12,

x_1+2x_2=1 \Rightarrow x_1=0.

因此

\boxed{x=\left(0,\frac12,\frac32\right)^T}.

解第二个右端项：

先解

Lw= \begin{bmatrix}3\\8\\8\end{bmatrix}.

逐行前代：

w_1=3, \qquad 2w_1+w_2=8\Rightarrow w_2=2,

w_2+w_3=8\Rightarrow w_3=6.

所以 $w=(3,2,6)^T$ 。再解 $Uz=w$ ：

2z_3=6\Rightarrow z_3=3,

z_2+z_3=2\Rightarrow z_2=-1,

z_1+2z_2=3\Rightarrow z_1=5.

因此

\boxed{z=(5,-1,3)^T}.

[!TIP] 本题要点 $A$ 只分解一次。更换右端项时，重新做的工作只有一次前代和一次回代；这正是 LU 分解对多个右端项的优势。

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

部分选主元在第 $k$ 列的第 $k$ 行及其下方选择

p=\arg\max_{k\le i\le n}|a_{ik}^{(k)}|,

并交换第 $p$ 行与第 $k$ 行。

[!TIP] 符号说明

$p$ ：当前列中绝对值最大元素所在的行号；

$\arg\max$ ：返回“使目标量最大时的下标”；

交换后必须同步交换右端向量，以及此前已经存入 $L$ 的相关乘子位置。

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

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

题目： 在保留 4 位有效数字的情况下，比较不选主元与部分选主元求解

Cx=g, \qquad C= \begin{bmatrix} 10^{-4}&1\\ 1&1 \end{bmatrix}, \qquad g= \begin{bmatrix}1\\1.600\end{bmatrix}.

不选主元#

第一步主元为 $10^{-4}$ ，消去乘子

l_{21} = \frac{1}{10^{-4}} = 10^4.

于是

C=L_0U_0,

L_0= \begin{bmatrix} 1&0\\ 10^4&1 \end{bmatrix}, \qquad U_0= \begin{bmatrix} 10^{-4}&1\\ 0&-9999 \end{bmatrix}.

前代 $L_0y=g$ ：

y_1=1,

10^4y_1+y_2=1.600 \Rightarrow y_2=-9998

（按 4 位有效数字保留）。

回代 $U_0x=y$ ：

x_2 = \frac{-9998}{-9999} \approx 0.9999,

x_1 = \frac{1-x_2}{10^{-4}} \approx 1.000.

因此不选主元得到

x_{\mathrm{np}} \approx (1.000,\;0.9999)^T.

部分选主元#

交换两行：

P= \begin{bmatrix}0&1\\1&0\end{bmatrix}, \qquad PC= \begin{bmatrix} 1&1\\ 10^{-4}&1 \end{bmatrix}, \qquad Pg= \begin{bmatrix}1.600\\1\end{bmatrix}.

此时消去乘子

l_{21}=10^{-4}.

分解为

PC=L_1U_1,

L_1= \begin{bmatrix} 1&0\\ 10^{-4}&1 \end{bmatrix}, \qquad U_1= \begin{bmatrix} 1&1\\ 0&0.9999 \end{bmatrix}.

前代：

\widetilde y_1=1.600,

10^{-4}\widetilde y_1+\widetilde y_2=1 \Rightarrow \widetilde y_2=0.9998.

回代：

x_2 = \frac{0.9998}{0.9999} \approx 0.9999,

x_1 = 1.600-x_2 \approx 0.6001.

所以

x_{\mathrm p} \approx (0.6001,\;0.9999)^T.

精确解约为

x^* = (0.600060,\;0.999940)^T.

因此部分选主元结果可靠，而不选主元的第一分量明显失真。

[!TIP] 原因不选主元时 $l_{21}=10^4$ ，会把前面数值中的舍入误差放大，并在回代时出现相近数相减后再除以 $10^{-4}$ ；选主元后 $l_{21}=10^{-4}$ ，误差放大显著减弱。

例 2：零主元必须换行#

设

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

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

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

此时可取 $L=I$ 、 $U=PA$ 。若右端项为 $b$ ，必须同时变为 $Pb$ 。

答题模板#

当前列主元过小/为零，因此交换第 $k$ 行与第 $p$ 行。记交换矩阵为 $P$ ，得到 $PA=LU$ 。求解时先计算 $Pb$ ，再依次解 $Ly=Pb$ 和 $Ux=y$ 。

本章检查清单#

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

Chapter 3 线性方程组迭代法#

3.1 章节主线#

对线性方程组

Ax=b,

若能等价改写为不动点形式

x=Mx+g,

则从初值 $x^{(0)}$ 出发构造

x^{(k+1)} = Mx^{(k)}+g, \qquad k=0,1,2,\ldots.

若序列收敛到 $x^*$ ，则 $x^*=Mx^*+g$ ，从而 $x^*$ 是原方程组的解。

[!TIP] 符号说明

$x^{(k)}$ ：第 $k$ 次迭代近似；

$x^{(0)}$ ：初始猜测；

$M$ ：迭代矩阵，由 $A$ 的具体分裂方式决定；

$g$ ：与右端向量 $b$ 有关的常向量；

$x^*$ ：方程组的精确解；

上标 $(k)$ 是迭代编号。

误差满足

x^{(k)}-x^* = M^k\bigl(x^{(0)}-x^*\bigr).

因此一般定常迭代法收敛的充要条件为

\rho(M)<1,

其中 $\rho(M)$ 是 $M$ 的谱半径，即所有特征值模的最大值。本学期不要求复杂谱半径计算，但要理解该结论。

本章重点：

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

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

设

a_{ii}x_i+\sum_{j\ne i}a_{ij}x_j=b_i.

Jacobi#

x_i^{(k+1)}= \frac1{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right).

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

Gauss-Seidel#

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#

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).

[!TIP] 三种格式中的符号

$a_{ij}$ ：矩阵 $A$ 的第 $(i,j)$ 个元素； $a_{ii}$ 是第 $i$ 个对角元；

$b_i$ ：右端向量第 $i$ 个分量；

$x_i^{(k)}$ ：第 $k$ 轮迭代向量的第 $i$ 个分量；

Jacobi 的右端全部使用第 $k$ 轮旧值；

Gauss-Seidel/SOR 中， $j<i$ 的分量已在本轮更新，使用 $x_j^{(k+1)}$ ； $j>i$ 尚未更新，使用 $x_j^{(k)}$ ；

$\omega$ ：松弛因子。

$\omega=1$ ：退化为 Gauss-Seidel；
$0<\omega<1$ ：低松弛；
$1<\omega<2$ ：超松弛。

例 1：Jacobi 与 Gauss-Seidel 两步#

求解

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

迭代格式为

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

（Jacobi）。

第一步：

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

第二步：

x^{(2)}=\frac{9-2.3333}{4}\approx1.6667,

y^{(2)}=\frac{7-2.25}{3}\approx1.5833.

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

x^{(1)}=2.25,

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

第二轮：

x^{(2)}=\frac{9-1.5833}{4}=1.8542,

y^{(2)}=\frac{7-1.8542}{3}=1.7153.

例 2：SOR 一步#

对

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

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

x_1^{(1)}=(1-\omega)x_1^{(0)}+ \frac{\omega}{3}(5-x_2^{(0)}) =\frac56.

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 重点题型二：判断适用性与收敛条件#

常用结论：

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

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

例 1：由严格行对角占优判断收敛性#

题目： 判断 Jacobi 法和 Gauss-Seidel 法用于下列矩阵时是否有常用充分条件保证收敛：

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

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

例 2：判断非奇异矩阵能否直接使用 CG#

题目： 判断下列矩阵是否满足标准 CG 法的适用条件：

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

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

例 3：判断矩阵是否对称正定#

题目： 判断下列矩阵能否直接使用 CG：

A= \begin{bmatrix} 2&-1\\ -1&2 \end{bmatrix}.

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

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

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

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

CG 直接适用于 $A$ 为对称正定矩阵的线性方程组 $Ax=b$ 。本文统一采用课程复习提纲中的 $d^{(k)},\lambda_k,\beta_k$ 记号。

初始化：

r^{(0)}=b-Ax^{(0)}, \qquad d^{(0)}=r^{(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,\ldots$ ：

r^{(k)}=b-Ax^{(k)},

\beta_{k-1} = -\frac{\langle r^{(k)},Ad^{(k-1)}\rangle} {\langle d^{(k-1)},Ad^{(k-1)}\rangle},

d^{(k)} = r^{(k)}+\beta_{k-1}d^{(k-1)},

\lambda_k = \frac{\langle r^{(k)},d^{(k)}\rangle} {\langle d^{(k)},Ad^{(k)}\rangle}, \qquad x^{(k+1)} = x^{(k)}+\lambda_kd^{(k)}.

[!TIP] 符号说明

$r^{(k)}=b-Ax^{(k)}$ ：第 $k$ 步残差，也是目标二次函数在 $x^{(k)}$ 处的负梯度；

$d^{(k)}$ ：第 $k$ 步搜索方向；

$\lambda_k$ ：沿 $d^{(k)}$ 前进的步长；Chapter3 原笔记常用 $\alpha_k$ 表示同一量；

$\beta_{k-1}$ ：把新残差与旧方向组合成新共轭方向的系数；

$\langle u,v\rangle=u^Tv$ ：欧氏内积；

$Ad^{(k)}$ ：矩阵与搜索方向的乘积，CG 每步的主要计算量。

搜索方向满足 $A$ -共轭性：

\langle Ad^{(i)},d^{(j)}\rangle=0, \qquad i\ne j.

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

[!NOTE] 等价实现公式常见程序形式写作
$\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)}}.$
这里 $\alpha_k=\lambda_k$ 。考试时以卷末公式表的记号为准。

例 1：CG 第一步并验证残差正交#

题目：

A= \begin{bmatrix} 1&0\\0&4 \end{bmatrix}, \qquad b= \begin{bmatrix}1\\2\end{bmatrix}, \qquad x^{(0)}=(0,0)^T.

执行 CG 第一步，求 $r^{(0)},d^{(0)},\lambda_0,x^{(1)},r^{(1)}$ ，并验证 $r^{(1)}\perp r^{(0)}$ 。

解：

r^{(0)} = b-Ax^{(0)} = \begin{bmatrix}1\\2\end{bmatrix}, \qquad d^{(0)}=r^{(0)}.

Ad^{(0)} = \begin{bmatrix}1\\8\end{bmatrix}.

\lambda_0 = \frac{1^2+2^2}{1\cdot1+2\cdot8} = \frac5{17}.

x^{(1)} = x^{(0)}+\lambda_0d^{(0)} = \begin{bmatrix}5/17\\10/17\end{bmatrix}.

r^{(1)} = b-Ax^{(1)} = \begin{bmatrix}12/17\\-6/17\end{bmatrix}.

验证：

(r^{(1)})^Tr^{(0)} = \frac{12}{17} + \left(-\frac6{17}\right)2 = 0.

因此

\boxed{r^{(1)}\perp r^{(0)}}.

例 2：CG 完整两步#

题目：

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

执行两步 CG，写出每一步的残差、方向、步长和近似解。

第 0 步：

r^{(0)}=d^{(0)}=(1,2)^T, \qquad Ad^{(0)}=(6,7)^T.

\lambda_0 = \frac{(r^{(0)})^Tr^{(0)}}{(d^{(0)})^TAd^{(0)}} = \frac5{20} = \frac14.

x^{(1)} = \left(\frac14,\frac12\right)^T,

r^{(1)} = b-Ax^{(1)} = \left(-\frac12,\frac14\right)^T.

第 1 步：

\beta_0 = -\frac{(r^{(1)})^TAd^{(0)}}{(d^{(0)})^TAd^{(0)}} = -\frac{-5/4}{20} = \frac1{16}.

d^{(1)} = r^{(1)}+\beta_0d^{(0)} = \left(-\frac7{16},\frac38\right)^T.

Ad^{(1)} = \left(-\frac{11}{8},\frac{11}{16}\right)^T.

\lambda_1 = \frac{(r^{(1)})^Td^{(1)}}{(d^{(1)})^TAd^{(1)}} = \frac4{11}.

x^{(2)} = x^{(1)}+\lambda_1d^{(1)} = \left(\frac1{11},\frac7{11}\right)^T.

最后检查：

Ax^{(2)} = \begin{bmatrix}1\\2\end{bmatrix} =b, \qquad r^{(2)}=0.

因此

\boxed{x^*=\left(\frac1{11},\frac7{11}\right)^T}.

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

最速下降法每一步都取

d^{(k)}=r^{(k)},

步长为

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

[!TIP] 符号说明

搜索方向始终等于当前残差；

$\lambda_k$ 使当前直线方向上的二次目标函数达到最小；

它可能出现“之”字形；CG 通过 $A$ -共轭方向避免重复修正已经优化过的方向。

本章检查清单#

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

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

4.1 章节主线#

本章包含两条线：

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

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

特征值问题为

Ax=\lambda x, \qquad x\ne0.

[!TIP] 符号说明

$A$ ：待研究矩阵；

$\lambda$ ：特征值；

$x$ ：与 $\lambda$ 对应的非零特征向量。

幂法#

若

|\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n|

且初始向量含有主特征向量方向的非零分量，则迭代

y^{(k+1)}=Ax^{(k)},

m_{k+1}=y_p^{(k+1)}, \qquad |y_p^{(k+1)}| = \|y^{(k+1)}\|_\infty,

x^{(k+1)} = \frac{y^{(k+1)}}{m_{k+1}}.

[!TIP] 符号说明

$x^{(k)}$ ：第 $k$ 步归一化后的向量；

$y^{(k+1)}=Ax^{(k)}$ ：乘矩阵后尚未归一化的向量；

$p$ ： $y^{(k+1)}$ 中绝对值最大分量的下标；

$m_{k+1}$ ：该最大分量，保留其符号；

$\|y\|_\infty=\max_i|y_i|$ ：无穷范数；

当迭代收敛时， $m_{k+1}$ 逼近按模最大的特征值， $x^{(k)}$ 逼近对应特征向量方向。

收敛速度主要由

\left|\frac{\lambda_2}{\lambda_1}\right|

控制：该比值越小，主特征方向越快占优。

反幂法#

反幂法每一步解

Ay^{(k+1)}=x^{(k)},

再按

m_{k+1}=y_p^{(k+1)}, \qquad x^{(k+1)}=\frac{y^{(k+1)}}{m_{k+1}}

归一化，并估计

\lambda_{\min,|\cdot|} \approx \frac1{m_{k+1}}.

[!TIP] 符号说明

$\lambda_{\min,|\cdot|}$ ：按绝对值最小的特征值；

反幂法等价于对 $A^{-1}$ 做幂法；

实际计算只解线性方程组 $Ay=x$ ，不显式求 $A^{-1}$ ；

若 $A$ 固定，可先做一次 LU 分解，每一步重复前代、回代。

移位反幂法#

给定移位 $\mu$ ，每一步解

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

归一化后，邻近特征值可估计为

\lambda \approx \mu+\frac1{m_{k+1}}.

[!TIP] 符号说明

$\mu$ ：人为选定的移位，应接近想寻找的特征值；

$I$ ：单位矩阵；

$(A-\mu I)^{-1}$ 的最大模特征值对应 $A$ 中离 $\mu$ 最近的特征值；

$m_{k+1}$ 仍是解向量中绝对值最大的有符号分量。

例 1：幂法计算三步#

题目：

A= \begin{bmatrix} 2&1\\1&2 \end{bmatrix}, \qquad x^{(0)}=(1,0)^T.

使用有符号最大分量归一化，计算三步幂法。

第 1 步：

y^{(1)}=Ax^{(0)}=(2,1)^T, \qquad m_1=2,

x^{(1)}=(1,1/2)^T.

第 2 步：

y^{(2)} = A x^{(1)} = \left(\frac52,2\right)^T, \qquad m_2=\frac52,

x^{(2)}=(1,4/5)^T.

第 3 步：

y^{(3)} = A x^{(2)} = \left(\frac{14}{5},\frac{13}{5}\right)^T, \qquad m_3=\frac{14}{5}=2.8,

x^{(3)} = \left(1,\frac{13}{14}\right)^T.

因此特征值估计依次为 $2,2.5,2.8$ ，趋向主特征值 $3$ ；向量方向趋向 $(1,1)^T$ 。

例 2：普通反幂法一步#

题目：

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

完成一步反幂法，并判断趋向哪个特征值。

解

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

得

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

最大有符号分量为 $m_1=1$ ，故

x^{(1)} = \left(1,\frac13,\frac16\right)^T, \qquad \lambda\approx\frac1{m_1}=1.

第一分量占优，因此迭代趋向按模最小特征值 $1$ 及其特征向量 $(1,0,0)^T$ 。

例 3：移位反幂法一步#

题目：

A=\operatorname{diag}(1,3,6), \qquad \mu=2.8, \qquad x^{(0)}=(1,1,1)^T.

完成一步移位反幂法并估计邻近特征值。

A-\mu I = \operatorname{diag}(-1.8,0.2,3.2).

解

(A-\mu I)y^{(1)}=x^{(0)}

得

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

最大有符号分量为 $m_1=5$ ，于是

x^{(1)} = \left(-\frac19,1,\frac1{16}\right)^T,

\lambda \approx 2.8+\frac15 = 3.

因为 $2.8$ 离特征值 $3$ 最近，第二分量迅速占优。

易错点#

题目要求“用幂法估计”时，直接写精确特征值不能代替迭代过程；
归一化因子若保留符号，可同时估计特征值符号；若只除以无穷范数，则需另行判断符号；
反幂法和移位反幂法都要解线性方程组，不应先求逆矩阵。

4.3 重点题型二：Householder 反射#

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

Hx=\alpha e_1, \qquad |\alpha|=\|x\|_2.

取

u=x-\alpha e_1, \qquad w=\frac{u}{\|u\|_2},

则 Chapter4 原笔记中的 Householder 公式为

H=I-2ww^T.

等价地，也可直接使用未单位化向量 $u$ ：

H = I-2\frac{uu^T}{u^Tu}.

[!TIP] 符号说明

$x$ ：待变换的非零向量；

$e_1=(1,0,\ldots,0)^T$ ：第一坐标轴单位向量；

$\alpha$ ：目标轴向量的第一分量，满足 $|\alpha|=\|x\|_2$ ；

$u=x-\alpha e_1$ ：未单位化的反射法向量；

$w=u/\|u\|_2$ ：单位法向量，与 Chapter4 原笔记记号一致；

$H$ ：Householder 反射矩阵；

$ww^T=uu^T/(u^Tu)$ ：沿法向量方向的正交投影矩阵。

$H$ 具有

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

例 1：二维反射#

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

取

u=x-5e_1=(-2,4)^T, \qquad u^Tu=20.

H=I-\frac1{10}uu^T = \begin{bmatrix} \frac35&\frac45\\ \frac45&-\frac35 \end{bmatrix}.

验证：

H \begin{bmatrix}3\\4\end{bmatrix} = \begin{bmatrix}5\\0\end{bmatrix}.

例 2：三维反射#

把

x=(0,3,4)^T

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

u=x-5e_1=(-5,3,4)^T, \qquad u^Tu=50.

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, \qquad H^TH=I.

因此该 $H$ 确实把 $x$ 反射到第一坐标轴正方向。

选 $\alpha$ 的技巧#

实际数值计算常取

\alpha=-\operatorname{sign}(x_1)\|x\|_2

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

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

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

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

取

G= \begin{bmatrix} c&s\\-s&c \end{bmatrix},

[!TIP] 符号说明

$a$ ：希望保留在上方的分量；

$b$ ：希望通过旋转消去的下方分量；

$r=\sqrt{a^2+b^2}$ ：旋转后第一分量；

$c=\cos\theta=a/r$ 、 $s=\sin\theta=b/r$ ；

$G$ ：二维 Givens 旋转矩阵；在高维中嵌入单位阵使用。

则

G \begin{bmatrix}a\\b\end{bmatrix} = \begin{bmatrix}r\\0\end{bmatrix}.

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

例 1：用 Givens 做 QR 分解#

设

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

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

c=\frac35, \qquad s=\frac45,

G= \begin{bmatrix} \frac35&\frac45\\ -\frac45&\frac35 \end{bmatrix}.

则

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

因为 $G$ 正交， $Q=G^T$ ，故

A=QR, \qquad Q= \begin{bmatrix} \frac35&-\frac45\\ \frac45&\frac35 \end{bmatrix}.

例 2：做一步 QR 迭代#

QR 算法：

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

[!TIP] 符号说明

$A^{(k)}$ ：第 $k$ 次 QR 迭代矩阵；

$Q_k$ ： $A^{(k)}$ 的正交因子，满足 $Q_k^TQ_k=I$ ；

$R_k$ ： $A^{(k)}$ 的上三角因子；

$A^{(k+1)}=Q_k^TA^{(k)}Q_k$ ，因此与 $A^{(k)}$ 相似，特征值不变。

利用上一例：

A^{(1)}=RQ = \begin{bmatrix} \frac{119}{25}&-\frac{67}{25}\\[2pt] \frac8{25}&\frac6{25} \end{bmatrix} = \begin{bmatrix} 4.76&-2.68\\ 0.32&0.24 \end{bmatrix}.

由于

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

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

Householder 与 Givens 的关系#

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

本章检查清单#

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

Chapter 5 插值法#

5.1 章节主线#

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

(x_0,y_0),\ldots,(x_n,y_n),

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

P_n(x_i)=y_i.

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

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

5.2 重点题型一：Lagrange 插值#

基函数

l_k(x)= \prod_{\substack{i=0\\i\ne k}}^n \frac{x-x_i}{x_k-x_i}.

满足

l_k(x_i)=\delta_{ki}.

插值多项式

L_n(x) = \sum_{k=0}^{n}y_kl_k(x).

[!TIP] 符号说明

$x_0,\ldots,x_n$ ：互不相同的插值节点；

$y_k=f(x_k)$ ：第 $k$ 个节点上的已知函数值；

$l_k(x)$ ：第 $k$ 个 Lagrange 基函数，在 $x_k$ 处等于 1，在其他节点处等于 0；

$L_n(x)$ ：次数不超过 $n$ 的 Lagrange 插值多项式；

$\delta_{ki}$ ：Kronecker 符号， $k=i$ 时为 1，否则为 0。

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

题目： 已知三个节点如下，构造二次 Lagrange 插值多项式，并计算 $L_2(1.5)$ 。

节点为

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

l_0(x)=\frac{(x-1)(x-2)}{2},

l_1(x)=-x(x-2),

l_2(x)=\frac{x(x-1)}2.

所以

L_2(x)=l_0(x)+3l_1(x)+7l_2(x).

化简得

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

于是

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

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

节点

x_0=-1, \quad x_1=0, \quad x_2=2,

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

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

l_0(1)=-\frac13, \qquad l_1(1)=1, \qquad l_2(1)=\frac13.

故

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

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

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

一阶差商

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

高阶差商

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 形式

N_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).

[!TIP] 符号说明

$f[x_i]$ ：零阶差商，即 $f(x_i)$ ；

$f[x_i,\ldots,x_{i+m}]$ ：由这些节点构成的 $m$ 阶差商；

$N_n(x)$ ：Newton 形式的插值多项式，与同一节点上的 $L_n(x)$ 完全相同；

第 $m$ 阶差商前恰有 $m$ 个因子 $(x-x_0)\cdots(x-x_{m-1})$ 。

例 1：由差商表构造 Newton 多项式#

题目： 对下列节点列出差商，并构造 Newton 二次插值多项式。

仍用节点

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

零阶差商：

1, \quad3, \quad7.

一阶差商：

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

二阶差商：

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

所以

N_2(x)=1+2x+x(x-1)=x^2+x+1.

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

例 2：非等距节点的 Newton 插值#

题目： 对下列非等距节点构造 Newton 二次插值多项式，并估计 $f(3)$ 。

节点

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

一阶差商：

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

二阶差商：

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

Newton 多项式为

N_2(x)=2+(x-1)-\frac23(x-1)(x-2).

求 $f(3)$ ：

N_2(3)=2+2-\frac23(2)(1)=\frac83.

易错点#

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

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

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

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

其中 $\xi$ 位于节点和 $x$ 所在区间内。

误差上界：

|R_n(x)| \leq \frac{M_{n+1}}{(n+1)!} \left|\prod_{i=0}^n(x-x_i)\right|,

M_{n+1} = \max_{\xi\in[a,b]} |f^{(n+1)}(\xi)|.

[!TIP] 符号说明

$R_n(x)=f(x)-P_n(x)$ ：在待求点 $x$ 处的插值误差；

$f^{(n+1)}$ ：原函数的第 $n+1$ 阶导数；

$\xi$ ：位于所有插值节点与待求点所覆盖区间内的某个未知点；

$M_{n+1}$ ：该区间内第 $n+1$ 阶导数绝对值的最大值；

$\prod_{i=0}^n(x-x_i)$ ：由节点位置决定的误差因子。

例 1：直接代余项公式#

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

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

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

|R_2(1)| \leq\frac{12}{3!}|(1+1)(1-0)(1-2)| =\frac{12}{6}\times2=4.

例 2： $e^x$ 的插值误差#

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

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

M_3=e.

所以

|R_2(1/4)| \leq \frac e6 \left|\frac14\left(-\frac14\right)\left(-\frac34\right)\right| =\frac e{128} \approx0.02124.

例 3：如何选择节点#

余项中节点影响因子是

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

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

5.5 Runge 现象#

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

典型函数：

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

避免方法：

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

关于 Hermite 插值#

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

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

本章检查清单#

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

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

6.1 章节主线#

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

离散最小二乘#

给定 $m$ 个数据点 $(x_i,y_i)$ ，选取 $n+1$ 个基函数 $\varphi_0,\ldots,\varphi_n$ ，令

p(x) = \sum_{j=0}^{n}a_j\varphi_j(x).

离散残差平方和为

S(a_0,\ldots,a_n) = \sum_{i=1}^{m} \left[ y_i-\sum_{j=0}^{n}a_j\varphi_j(x_i) \right]^2.

构造设计矩阵

A_{ij}=\varphi_j(x_i),

系数向量和数据向量为

\boldsymbol a=(a_0,\ldots,a_n)^T, \qquad \boldsymbol y=(y_1,\ldots,y_m)^T.

目标写成

\min_{\boldsymbol a} \|A\boldsymbol a-\boldsymbol y\|_2^2,

正规方程为

A^TA\boldsymbol a = A^T\boldsymbol y.

[!TIP] 符号说明

$m$ ：数据点个数； $n$ ：拟合多项式或逼近空间的最高编号，未知系数共有 $n+1$ 个；

$\varphi_j(x)$ ：已知基函数；

$a_j$ ：待求系数；

$A\in\mathbb R^{m\times(n+1)}$ ：设计矩阵，第 $i$ 行记录所有基函数在 $x_i$ 处的值；

$A\boldsymbol a-\boldsymbol y$ ：拟合残差向量；

上标 $T$ ：矩阵转置。

连续最佳平方逼近#

在函数区间 $[a,b]$ 上定义带权内积

\langle f,g\rangle = \int_a^b f(x)g(x)w(x)\,dx, \qquad w(x)>0.

相应平方范数为

\|f\|_2^2 = \langle f,f\rangle.

设

p(x) = \sum_{j=0}^{n}a_j\varphi_j(x),

最佳平方逼近满足正交条件

\langle f-p,\varphi_i\rangle=0, \qquad i=0,\ldots,n,

即法方程

\sum_{j=0}^{n} a_j \langle\varphi_j,\varphi_i\rangle = \langle f,\varphi_i\rangle.

[!TIP] 符号说明

$f(x)$ ：被逼近的已知连续函数；

$p(x)$ ：在给定有限维空间中的最佳逼近函数；

$w(x)$ ：权函数，未给出时通常取 $w(x)=1$ ；

$\langle f,g\rangle$ ：函数空间内积；

$f-p$ ：误差函数；

正交条件表示误差函数与整个逼近空间正交。

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

例 1：中心化基函数的离散最小二乘#

题目： 对下列数据，用 $p(x)=a_0+a_1(x-1)$ 作最小二乘拟合，并求残差平方和。

数据为

$x_i$	0	1	2
$y_i$	2	2	4

用

y=a_0+a_1(x-1)

拟合。

设计矩阵

A= \begin{bmatrix} 1&-1\\ 1&0\\ 1&1 \end{bmatrix}, \qquad y= \begin{bmatrix}2\\2\\4\end{bmatrix}.

A^TA= \begin{bmatrix}3&0\\0&2\end{bmatrix}, \qquad A^T\boldsymbol y= \begin{bmatrix}8\\2\end{bmatrix}.

正规方程

\begin{bmatrix}3&0\\0&2\end{bmatrix} \begin{bmatrix}a_0\\a_1\end{bmatrix} = \begin{bmatrix}8\\2\end{bmatrix}.

故

a_0=\frac83, \qquad a_1=1.

拟合函数

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

残差 $y-A\boldsymbol a$ 为

\left(\frac13,-\frac23,\frac13\right)^T,

残差平方和

\frac19+\frac49+\frac19=\frac23.

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

题目： 对下列数据用 $p(x)=a_0+a_1x$ 作最小二乘拟合，并求残差平方和。

数据

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

用 $p(x)=a_0+a_1x$ 拟合。

A= \begin{bmatrix} 1&-1\\1&0\\1&1 \end{bmatrix}, \qquad A^TA= \begin{bmatrix}3&0\\0&2\end{bmatrix},

A^T\boldsymbol y= \begin{bmatrix}2\\0\end{bmatrix}.

所以

a_0=\frac23, \qquad a_1=0.

最优直线为

\boxed{p(x)=\frac23}.

残差平方和为

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

为什么正规方程成立#

最优残差

\boldsymbol r = \boldsymbol y-A\boldsymbol a.

必须与 $A$ 的所有列正交：

A^T\boldsymbol r=0.

因此

A^T(\boldsymbol y-A\boldsymbol a)=0 \Rightarrow A^TA\boldsymbol a=A^T\boldsymbol y.

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

设

p(x) = \sum_{j=0}^{n}a_j\varphi_j(x).

法方程为

\sum_{j=0}^{n} a_j\langle\varphi_j,\varphi_i\rangle = \langle f,\varphi_i\rangle, \qquad i=0,\ldots,n.

[!TIP] 符号说明

$i$ ：当前法方程编号；

$j$ ：求和中的基函数编号；

$\langle\varphi_j,\varphi_i\rangle$ ：Gram 矩阵元素；

$\langle f,\varphi_i\rangle$ ：原函数在第 $i$ 个基方向上的投影右端项。

矩阵形式为

G\boldsymbol a=\boldsymbol b,

其中

G_{ij} = \langle\varphi_j,\varphi_i\rangle, \qquad b_i = \langle f,\varphi_i\rangle.

[!TIP] 符号说明

$G$ ：Gram 矩阵；

$G_{ij}$ ：第 $j$ 个基函数与第 $i$ 个基函数的内积；

$\boldsymbol b$ ：投影右端向量，与线性方程组原来的右端 $b$ 只是同类记号，具体含义由上下文决定；

若基函数线性无关，则 $G$ 通常正定，法方程有唯一解。

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

题目： 在内积 $\langle f,g\rangle=\int_0^1f(x)g(x)\,dx$ 下，求 $x^2$ 在 $\operatorname{span}\{1,x\}$ 中的最佳平方逼近。

设

p(x)=a+bx.

正交条件：

\int_0^1(x^2-a-bx)\,dx=0,

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

得到

a+\frac b2=\frac13,

\frac a2+\frac b3=\frac14.

解得

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

因此

\boxed{p(x)=x-\frac16}.

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

题目： 在内积 $\langle f,g\rangle=\int_{-1}^1f(x)g(x)\,dx$ 下，求 $x^2$ 在 $\operatorname{span}\{1,x\}$ 中的最佳平方逼近。

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

\langle x^2,x\rangle=0,

所以 $b=0$ 。

a=\frac{\langle x^2,1\rangle}{\langle1,1\rangle} =\frac{2/3}{2}=\frac13.

因此

\boxed{p(x)=\frac13}.

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

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

若基函数两两正交：

\langle\varphi_i,\varphi_j\rangle=0, \qquad i\ne j,

则系数可直接分开计算：

a_k = \frac{\langle f,\varphi_k\rangle} {\langle\varphi_k,\varphi_k\rangle}.

[!TIP] 符号说明

$\varphi_k$ ：第 $k$ 个正交基函数；

$a_k$ ： $f$ 在 $\varphi_k$ 方向上的投影系数；

分子衡量 $f$ 与该基方向的相关程度，分母用于消除基函数长度的影响。

在 $[-1,1]$ 上：

P_0(x)=1, \qquad P_1(x)=x, \qquad P_2(x)=\frac12(3x^2-1).

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

题目： 在 $[-1,1]$ 上求 $x^5$ 在 $\operatorname{span}\{1,x\}$ 中的最佳平方逼近。

设

p(x)=a+bx.

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

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.

故

\boxed{p(x)=\frac37x}.

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

题目： 在 $[0,2]$ 上用至多二次多项式最佳平方逼近 $f(x)=e^x$ 。题目只给出 $[-1,1]$ 上的 Legendre 多项式

P_0(t)=1, \qquad P_1(t)=t, \qquad P_2(t)=\frac12(3t^2-1).

第一步：区间变换

令

t=x-1, \qquad x=t+1, \qquad dx=dt.

于是 $x\in[0,2]$ 对应 $t\in[-1,1]$ ，且

f(x)=e^{t+1}=e\,e^t.

设

p(x) = a_0P_0(t)+a_1P_1(t)+a_2P_2(t), \qquad t=x-1.

由于 Legendre 基正交，

a_k = \frac{\langle e\,e^t,P_k\rangle} {\langle P_k,P_k\rangle}.

[!TIP] 符号说明

$t$ ：标准区间 $[-1,1]$ 上的新变量；

$P_k(t)$ ：第 $k$ 个 Legendre 多项式；

$a_k$ ： $f$ 在 $P_k$ 方向上的正交投影系数；

内积均在 $t\in[-1,1]$ 上计算。

第二步：计算 $a_0$

\langle P_0,P_0\rangle = \int_{-1}^{1}1\,dt = 2,

\langle e\,e^t,P_0\rangle = e\int_{-1}^{1}e^t\,dt = e(e-e^{-1}) = e^2-1.

所以

a_0=\frac{e^2-1}{2}.

第三步：计算 $a_1$

\langle P_1,P_1\rangle = \int_{-1}^{1}t^2\,dt = \frac23.

利用

\int te^t\,dt=e^t(t-1),

有

\langle e\,e^t,P_1\rangle = e\int_{-1}^{1}te^t\,dt = e\left[e^t(t-1)\right]_{-1}^{1} = 2.

所以

a_1 = \frac{2}{2/3} = 3.

第四步：计算 $a_2$

Legendre 正交性给出

\langle P_2,P_2\rangle=\frac25.

又因为

P_2(t)=\frac12(3t^2-1),

并利用

\int t^2e^t\,dt=e^t(t^2-2t+2),

可得

\begin{aligned} \langle e\,e^t,P_2\rangle &= \frac e2 \int_{-1}^{1}(3t^2-1)e^t\,dt\\ &= e^2-7. \end{aligned}

因此

a_2 = \frac{e^2-7}{2/5} = \frac52(e^2-7).

最终答案：

\boxed{ p(x) = \frac{e^2-1}{2} + 3(x-1) + \frac52(e^2-7) \cdot \frac{3(x-1)^2-1}{2} }.

[!WARNING] 最容易丢分之处 Legendre 多项式给在 $[-1,1]$ ，原问题在 $[0,2]$ ，必须先作 $t=x-1$ 。直接把 $P_k(x)$ 套入原区间会得到错误内积。

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

项目	离散最小二乘	连续最佳平方逼近
数据	有限个 $(x_i,y_i)$	已知完整函数 $f(x)$
目标	$\sum_i r_i^2$ 最小	$\int_a^b r(x)^2w(x)dx$ 最小
内积	向量点积/求和	积分内积
方程	$A^TA\boldsymbol a=A^T\boldsymbol y$	$\langle f-p,\varphi_i\rangle=0$
正交	残差向量与列空间正交	误差函数与逼近空间正交

本章检查清单#

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

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

7.1 章节主线#

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

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

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

向前差商：

D_+f(x) = \frac{f(x+h)-f(x)}{h} = f'(x)+O(h).

向后差商：

D_-f(x) = \frac{f(x)-f(x-h)}{h} = f'(x)+O(h).

中心差商：

D_0f(x) = \frac{f(x+h)-f(x-h)}{2h} = f'(x)+O(h^2).

[!TIP] 符号说明

$h$ ：非零步长；

$D_+,D_-,D_0$ ：分别表示向前、向后、中心差商算子；

$f'(x)$ ：希望近似的真实导数；

$O(h)$ 、 $O(h^2)$ ：截断误差阶；在相同步长下，中心差商通常更精确；

端点只能获得单侧数据时用单边差商，区间内部优先考虑中心差商。

推导中心差商误差#

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)+\frac{h^2}{2}f''(x)-\frac{h^3}{6}f^{(3)}(\xi_2).

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

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

已知

\ln0.9=-0.1053605, \quad \ln1=0, \quad \ln1.1=0.0953102.

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

(\ln x)'\big|_{x=1} \approx \frac{\ln1.1-\ln0.9}{0.2} =1.0033535.

精确值为 1。

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

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

向前差商：

\frac{e^{0.1}-1}{0.1}\approx1.051709.

中心差商：

\frac{e^{0.1}-e^{-0.1}}{0.2}\approx1.001668.

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

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

由

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

可得

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

所以近似值减真值为

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

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

将 $[a,b]$ 等分为 $n$ 段：

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

复合梯形公式：

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

误差形式：

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

误差限：

|I-T_n| \leq \frac{b-a}{12}h^2 \max_{x\in[a,b]}|f''(x)|.

[!TIP] 符号说明

$I=\int_a^bf(x)\,dx$ ：精确积分；

$n$ ：将 $[a,b]$ 等分的子区间数；

$h=(b-a)/n$ ：子区间步长；

$x_i=a+ih$ ：第 $i$ 个节点；

$T_n$ ：复合梯形近似；

端点权重为 1，内部节点权重为 2；

误差界中的最大值须在整个 $[a,b]$ 上寻找。

例 1：手算复合梯形#

用 $n=4$ 计算

\int_0^1x^2dx.

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

0, \quad0.0625, \quad0.25, \quad0.5625, \quad1.

T_4=\frac{0.25}{2} [0+2(0.0625+0.25+0.5625)+1] =0.34375.

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

I-T_4=-\frac1{96}\approx-0.0104167.

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

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

计算

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

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

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

所以

\max_{[0,1]}|f''(x)|=\frac14.

$h=1/n$ ，故

|I-T_n| \leq\frac1{12}\frac1{n^2}\frac14 =\frac1{48n^2}.

令

\frac1{48n^2}\leq10^{-3},

得

n\geq4.565.

因此至少取

n=5.

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

代数精度#

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

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

2n-1.

标准形式：

\int_{-1}^{1}f(t)\,dt \approx \sum_{k=1}^{n}A_kf(t_k).

[!TIP] 符号说明

$n$ ：Gauss 节点个数；

$t_k$ ：标准区间 $[-1,1]$ 上的第 $k$ 个 Gauss-Legendre 节点；

$A_k$ ：与节点 $t_k$ 对应的权重；

$n$ 点 Gauss-Legendre 公式的代数精度为 $2n-1$ ；

节点、权重通常查表获得。

一般区间变换#

对 $[a,b]$ ，令

x=\frac{a+b}{2}+\frac{b-a}{2}t, \qquad dx=\frac{b-a}{2}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.

进一步得到

\int_a^bf(x)\,dx \approx \frac{b-a}{2} \sum_{k=1}^{n} A_k f\left( \frac{a+b}{2} + \frac{b-a}{2}t_k \right).

[!TIP] 符号说明

$t\in[-1,1]$ ：标准变量；

$x=(a+b)/2+(b-a)t/2$ ：从标准区间映射回原区间的变量；

$(b-a)/2$ ：Jacobian 因子，来自 $dx=(b-a)dt/2$ ，最容易漏乘；

原区间上的实际节点为 $x_k=(a+b)/2+(b-a)t_k/2$ 。

例 1：推导一点 Gauss 公式#

设

\int_{-1}^{1}f(x)dx\approx Af(\xi).

令 $f(x)=1$ ：

2=A.

令 $f(x)=x$ ：

0=A\xi\Rightarrow \xi=0.

所以

\int_{-1}^{1}f(x)dx\approx2f(0).

该公式代数精度为 1。

对

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

近似值为

2f(0)=2.

精确值为

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

因此不精确。

例 2：推导两点 Gauss 公式#

利用对称性设

\int_{-1}^{1}f(x)dx \approx A[f(-\xi)+f(\xi)].

对 $1$ 精确：

2A=2\Rightarrow A=1.

对 $x^2$ 精确：

2\xi^2=\frac23 \Rightarrow \xi=\frac1{\sqrt3}.

所以

\int_{-1}^{1}f(x)dx \approx f\left(-\frac1{\sqrt3}\right) +f\left(\frac1{\sqrt3}\right).

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

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

题目： 使用四点 Gauss-Legendre 公式近似计算

I=\int_0^2\frac1{1+x^2}\,dx,

并指出代数精度。

第一步：区间变换

由一般公式

x=\frac{0+2}{2}+\frac{2-0}{2}t=1+t, \qquad dx=dt,

得到

I = \int_{-1}^{1} \frac1{1+(1+t)^2}\,dt.

第二步：查四点表

$t_k$	$A_k$
$-0.8611363$	$0.3478548$
$-0.3399810$	$0.6521452$
$0.3399810$	$0.6521452$
$0.8611363$	$0.3478548$

原区间节点为

x_k=1+t_k,

即约为

0.1388637,\quad 0.6600190,\quad 1.3399810,\quad 1.8611363.

第三步：加权求和

\begin{aligned} I &\approx 0.3478548\frac1{1+(1-0.8611363)^2}\\ &\quad+ 0.6521452\frac1{1+(1-0.3399810)^2}\\ &\quad+ 0.6521452\frac1{1+(1+0.3399810)^2}\\ &\quad+ 0.3478548\frac1{1+(1+0.8611363)^2}\\ &\approx 1.106740. \end{aligned}

精确值为

I=\arctan 2\approx1.107149.

四点 Gauss-Legendre 公式的代数精度为

2n-1=2\times4-1=7.

因此

\boxed{I\approx1.106740,\qquad \text{代数精度}=7}.

高斯积分的答题顺序#

写区间变换；
写 $dx$ 的系数；
写变换后的被积函数；
查节点和权重；
对称节点逐项代入；
写代数精度 $2n-1$ 。

本章检查清单#

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

Chapter 8 非线性方程求根#

8.1 章节主线#

本章方法可分为：

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

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

适用条件：

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

每次取中点

c_k=\frac{a_k+b_k}{2},

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

二分 $n$ 次后区间长度为

b_n-a_n = \frac{b-a}{2^n}.

若用第 $n$ 次保留区间的中点

x_n=\frac{a_n+b_n}{2}

作为近似根，则

|x_n-x^*| \le \frac{b-a}{2^{n+1}}.

[!TIP] 符号说明

$[a,b]$ ：初始含根区间；

$[a_n,b_n]$ ：二分 $n$ 次后保留的含根区间；

$x^*$ ：区间内的真根；

$x_n$ ：当前区间中点近似；

计数方式可能因教材而异，答题时写明所用误差公式即可。

例 1：做三步二分#

求

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

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

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

三步后含根区间为

[1.25,1.375].

取该区间中点作为最终近似：

x\approx\frac{1.25+1.375}{2}=1.3125.

误差上界为半个区间长度：

|x-x^*| \le \frac{0.125}{2} = 0.0625.

因此三步后的完整结论为

\boxed{x^*\approx1.3125,\qquad |x-x^*|\le0.0625}.

例 2：确定迭代次数#

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

要求

\frac1{2^{n+1}}\leq5\times10^{-5}.

即

n+1\geq\log_2(20000)\approx14.288.

因此至少需要

n=14

次二分。

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

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

Newton 迭代：

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

[!TIP] 符号说明

$f(x)=0$ ：待求根方程；

$x_k$ ：第 $k$ 次根的近似；

$f'(x_k)$ ：曲线在当前点的切线斜率，必须避免过小或为 0；

$x_{k+1}$ ：当前切线与 $x$ 轴交点；

对单根且初值充分接近时通常二次收敛。

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

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

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

例 1：多项式 Newton 两步#

题目： 对 $f(x)=0$ 从给定初值出发做两步 Newton 迭代。

f(x)=x^3-3x+1, \qquad x_0=0.

f'(x)=3x^2-3.

第一步：

x_1=0-\frac1{-3}=\frac13.

第二步：

f\left(\frac13\right)=\frac1{27},

f'\left(\frac13\right)=-\frac83.

x_2=\frac13-\frac{1/27}{-8/3} =\frac13+\frac1{72} =\frac{25}{72} \approx0.34722.

例 2：求 $\sqrt2$ #

令

f(x)=x^2-2.

Newton 格式化简为

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

取 $x_0=1$ ：

x_1=1.5,

x_2=\frac12\left(1.5+\frac2{1.5}\right) =\frac{17}{12} \approx1.416667.

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

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

Newton 法：

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

误差 $e_k=x_k-1$ 满足

e_{k+1}=\frac12e_k.

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

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

恢复更快收敛。

收敛阶定义#

若

\lim_{k\to\infty} \frac{|e_{k+1}|}{|e_k|^p}=C, \qquad 0<C<\infty,

[!TIP] 符号说明

$x^*$ ：迭代收敛到的真根；

$e_k=x_k-x^*$ ：第 $k$ 步误差；

$p$ ：收敛阶；

$C$ ：渐近误差常数，要求 $0<C<\infty$ 。

则称迭代具有 $p$ 阶收敛：

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

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

设

\boldsymbol F(\boldsymbol x) = \begin{bmatrix} f_1(x_1,\ldots,x_n)\\ \vdots\\ f_n(x_1,\ldots,x_n) \end{bmatrix} = \boldsymbol0.

Jacobi 矩阵为

\boldsymbol J(\boldsymbol x) = \left[ \frac{\partial f_i}{\partial x_j} \right]_{n\times n}.

每一步解线性方程组

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

再更新

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

[!TIP] 符号说明

$\boldsymbol x=(x_1,\ldots,x_n)^T$ ：未知向量；

$\boldsymbol F$ ：由 $n$ 个非线性方程组成的向量函数；

$\boldsymbol J$ ：Jacobi 矩阵，第 $(i,j)$ 元是 $\partial f_i/\partial x_j$ ；

$\Delta\boldsymbol x^{(k)}$ ：第 $k$ 步需要求解的增量；

实际计算直接解增量方程，不显式计算 $\boldsymbol J^{-1}$ 。

例 1：圆与直线的一步 Newton 迭代#

题目： 从 $(x^{(0)},y^{(0)})=(1,1)$ 出发，对下列方程组做一步 Newton 迭代。

\boldsymbol F(x,y)= \begin{bmatrix} x^2+y^2-1\\x-y \end{bmatrix}.

\boldsymbol J(x,y)= \begin{bmatrix} 2x&2y\\1&-1 \end{bmatrix}.

从 $(1,1)$ 出发：

\boldsymbol F(1,1)= \begin{bmatrix}1\\0\end{bmatrix}, \qquad \boldsymbol J(1,1)= \begin{bmatrix}2&2\\1&-1\end{bmatrix}.

解

\begin{bmatrix}2&2\\1&-1\end{bmatrix} \begin{bmatrix}\Delta x\\\Delta y\end{bmatrix} = \begin{bmatrix}-1\\0\end{bmatrix}.

得到

\Delta x=\Delta y=-\frac14.

所以

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

例 2：圆与三次曲线的一步 Newton 迭代#

题目： 从 $(x^{(0)},y^{(0)})=(1,1)$ 出发，对下列方程组做一步 Newton 迭代。

\boldsymbol F(x,y)= \begin{bmatrix} x^2+y^2-4\\x^3-y \end{bmatrix}, \qquad (x^{(0)},y^{(0)})=(1,1).

\boldsymbol J(x,y)= \begin{bmatrix} 2x&2y\\3x^2&-1 \end{bmatrix}.

在 $(1,1)$ ：

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

解

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

得

\Delta x=\frac14, \qquad \Delta y=\frac34.

所以

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

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

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

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

[!TIP] 符号说明

$x_{k-1},x_k$ ：最近两次根的近似，因此割线法需要两个初值；

分母 $f(x_k)-f(x_{k-1})$ 不能过小；

单根附近的收敛阶约为 $(1+\sqrt5)/2\approx1.618$ ，不需要导数。

例 1：割线法计算一次更新#

题目： 对下列方程和两个初值，用割线法计算 $x_2$ 。

f(x)=x^3-3x+1, \qquad x_0=0, \qquad x_1=1,

f(0)=1, \qquad f(1)=-1.

x_2=1- (-1)\frac{1-0}{-1-1} =0.5.

例 2：Newton 与割线的比较#

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

本章检查清单#

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

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

9.1 章节主线#

考虑一阶初值问题

\begin{cases} y'(x)=f(x,y),\\ y(a)=y_0. \end{cases}

将区间离散为

x_n=a+nh, \qquad n=0,1,\ldots,N, \qquad h=\frac{b-a}{N},

并计算

y_n\approx y(x_n).

[!TIP] 符号说明

$x$ ：独立变量；若问题描述时间，可把它写成 $t$ ；

$y(x)$ ：微分方程的精确解函数；

$x_n$ ：第 $n$ 个离散节点；

$h$ ：步长；

$y_n$ ：数值方法计算出的近似值，与精确值 $y(x_n)$ 要区分；

$f(x,y)$ ：微分方程右端函数，也给出当前位置的斜率。

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

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

y_{n+1} = y_n+h f(x_n,y_n).

[!TIP] 符号说明

$x_n,y_n$ ：当前节点及当前数值近似；

$f(x_n,y_n)$ ：当前点的斜率；

$h f(x_n,y_n)$ ：沿切线前进一步造成的纵向增量；

$y_{n+1}$ ：下一节点的数值近似；

右端全是已知量，因此这是显式格式。

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

例 1：显式 Euler 法计算两步#

题目： 用显式 Euler 法计算 $y_1,y_2$ 。

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

$t_0=0,y_0=1$ ：

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

$t_1=0.25,y_1=0.5$ ：

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

例 2：非自治方程的显式 Euler 两步#

题目： 用显式 Euler 法计算 $y_1,y_2$ 。

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

第一步：

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

第二步：

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

易错点#

第二步必须使用 $t_1=t_0+h$ 和刚算出的 $y_1$ ；
$y_n$ 是数值近似， $y(t_n)$ 是真解；
写结果时最好标注 $y_n\approx y(t_n)$ 。

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

y_{n+1} = y_n+h f(x_{n+1},y_{n+1}).

[!TIP] 符号说明

$x_{n+1}=x_n+h$ ：下一节点；

$y_{n+1}$ ：下一节点的未知数值，同时出现在等式两边；

因而每一步要解代数方程，属于隐式格式；

若 $f$ 对 $y$ 非线性，通常用 Newton 法求解。

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

例 1：线性方程的隐式 Euler 两步#

题目： 对下列初值问题，用隐式 Euler 法计算 $y_1,y_2$ 。

仍取

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

第一步：

y_1=1+0.25(-2y_1+0.25).

1.5y_1=1.0625 \Rightarrow y_1=0.708333.

第二步：

y_2=y_1+0.25(-2y_2+0.5).

1.5y_2=y_1+0.125 =0.833333,

y_2=0.555556.

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

题目： 对下列初值问题，写出隐式 Euler 第一步方程，并用两次 Newton 更新求 $y_1$ 。

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

隐式 Euler 第一步：

y_1=1+0.1(y_1^2-0.1).

令

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

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

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

取初值 $z^{(0)}=y_0=1$ 。

第一次 Newton 更新：

g(1)=-0.09, \qquad g'(1)=0.8,

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

第二次更新：

g(1.1125) = -0.001265625,

g'(1.1125) = 1-0.2(1.1125) = 0.7775,

z^{(2)} = 1.1125 - \frac{-0.001265625}{0.7775} \approx 1.1141278.

再检查

|g(z^{(2)})| \approx 2.65\times10^{-7},

故可取

\boxed{y_1\approx1.11413}.

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

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

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

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

对向前 Euler，定义

R_{n+1} = y(x_{n+1}) - \left[ y(x_n)+hf(x_n,y(x_n)) \right].

[!TIP] 符号说明

$R_{n+1}$ ：从精确值 $y(x_n)$ 出发，只推进一步后产生的局部截断误差；

$y(x_{n+1})$ ：下一节点的精确值；

方括号内：把精确的 $y(x_n)$ 代入 Euler 格式得到的一步结果；

局部截断误差不包含前面步骤的误差积累。

由于

f(x_n,y(x_n))=y'(x_n),

Taylor 展开：

y(x_n+h) =y(x_n)+hy'(x_n)+\frac{h^2}{2}y''(\xi_n).

所以

R_{n+1}=\frac{h^2}{2}y''(\xi_n)=O(h^2).

显式 Euler 的：

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

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

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

真解 $y(x)=e^x$ 。从 $x_n$ 做一步显式 Euler：

y(x_{n+1})-[y(x_n)+hy(x_n)] =e^{x_n}(e^h-1-h).

利用

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

得

R_{n+1} =e^{x_n}\frac{h^2}{2}+O(h^3) =O(h^2).

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

隐式 Euler 使用

y(x_n)+hy'(x_{n+1}).

在 $x_{n+1}$ 向后展开：

y(x_n) =y(x_{n+1})-hy'(x_{n+1})+\frac{h^2}{2}y''(\xi).

所以

y(x_{n+1})-[y(x_n)+hy'(x_{n+1})] =-\frac{h^2}{2}y''(\xi)=O(h^2).

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

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

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

本章检查清单#

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

综合易错点与交叉联系#

1. Taylor 展开贯穿多章#

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

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

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

2. 正交思想贯穿多章#

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

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

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

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

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

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

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

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

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

这一部分仍保留“公式速查”功能，但每组公式下面同时注明符号。

误差#

e(x^*)=x-x^*, \qquad e_r(x^*)=\frac{x-x^*}{x}.

$x$ 为真值， $x^*$ 为近似值； $e$ 为绝对误差， $e_r$ 为相对误差。

LU#

A=LU \quad\text{或}\quad PA=LU,

Ly=Pb, \qquad Ux=y.

$P$ 记录行交换；无换行时可取 $P=I$ 。 $y$ 是前代中间向量。

Jacobi / Gauss-Seidel / SOR#

x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right).

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).

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).

$i$ 是分量编号， $k$ 是迭代编号； $\omega$ 是 SOR 松弛因子。Jacobi 全用旧值，GS/SOR 及时使用本轮新值。

CG#

r^{(0)}=b-Ax^{(0)}, \qquad d^{(0)}=r^{(0)}.

\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)}.

\lambda_k = \frac{\langle r^{(k)},d^{(k)}\rangle} {\langle d^{(k)},Ad^{(k)}\rangle}, \qquad x^{(k+1)} = x^{(k)}+\lambda_kd^{(k)}.

$r^{(k)}$ 是残差， $d^{(k)}$ 是搜索方向， $\lambda_k$ 是步长， $\beta_k$ 是方向修正系数。 $A$ 必须对称正定。

幂法 / 反幂法#

y^{(k+1)}=Ax^{(k)}, \qquad x^{(k+1)} = \frac{y^{(k+1)}}{m_{k+1}}.

Ay^{(k+1)}=x^{(k)} \quad\text{或}\quad (A-\mu I)y^{(k+1)}=x^{(k)}.

$x^{(k)}$ 是归一化向量， $y^{(k+1)}$ 是未归一化向量， $m_{k+1}$ 是最大有符号分量， $\mu$ 是移位。

Householder / Givens#

u=x-\alpha e_1, \qquad w=\frac{u}{\|u\|_2}, \qquad H=I-2ww^T = I-2\frac{uu^T}{u^Tu}.

r=\sqrt{a^2+b^2}, \qquad c=\frac ar, \qquad s=\frac br, \qquad G= \begin{bmatrix}c&s\\-s&c\end{bmatrix}.

Householder 中 $u$ 是未单位化法向量、 $w$ 是单位法向量；Givens 中 $(a,b)^T$ 是待旋转的两个分量，目标是把 $b$ 消成 0。

插值#

l_k(x) = \prod_{i\ne k} \frac{x-x_i}{x_k-x_i}, \qquad L_n(x) = \sum_{k=0}^{n}y_kl_k(x).

N_n(x) = f[x_0] + \sum_{k=1}^{n} f[x_0,\ldots,x_k] \prod_{i=0}^{k-1}(x-x_i).

R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n}(x-x_i).

$x_i$ 为节点， $y_i=f(x_i)$ ， $l_k$ 为 Lagrange 基函数，方括号表示差商， $\xi$ 位于节点与待求点覆盖的区间内。

最小二乘#

A^TA\boldsymbol a = A^T\boldsymbol y.

\langle f-p,\varphi_i\rangle=0, \qquad a_i = \frac{\langle f,\varphi_i\rangle} {\langle\varphi_i,\varphi_i\rangle} \quad (\text{正交基}).

离散问题中的 $A$ 是设计矩阵；连续问题中的 $\varphi_i$ 是基函数， $a_i$ 是投影系数。

数值微分与积分#

D_0f(x) = \frac{f(x+h)-f(x-h)}{2h} = f'(x)+O(h^2).

T_n = \frac h2 \left[ f(a) + 2\sum_{i=1}^{n-1}f(x_i) + f(b) \right], \qquad h=\frac{b-a}{n}.

|I-T_n| \le \frac{b-a}{12}h^2 \max_{[a,b]}|f''(x)|.

n\text{ 点 Gauss-Legendre 的代数精度}=2n-1.

$D_0$ 为中心差商； $T_n$ 为复合梯形近似； $I$ 为精确积分；Gauss 的 $n$ 表示节点数。

非线性方程#

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

\boldsymbol J(\boldsymbol x^{(k)}) \Delta\boldsymbol x^{(k)} = -\boldsymbol F(\boldsymbol x^{(k)}), \qquad \boldsymbol x^{(k+1)} = \boldsymbol x^{(k)}+\Delta\boldsymbol x^{(k)}.

标量 Newton 中 $x_k$ 是根的近似；方程组 Newton 中 $\boldsymbol J$ 是 Jacobi 矩阵， $\Delta\boldsymbol x^{(k)}$ 是增量。

Euler#

y_{n+1} = y_n+hf(x_n,y_n),

y_{n+1} = y_n+hf(x_{n+1},y_{n+1}).

R_{n+1}=O(h^2), \qquad \text{全局误差}=O(h).

第一式是向前 Euler，第二式是向后 Euler； $x_n=a+nh$ ， $y_n\approx y(x_n)$ ， $R_{n+1}$ 是局部截断误差。

最后半天复习安排#

第一轮：2–3 小时#

按顺序快速阅读：

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

第二轮：3–4 小时#

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

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

第三轮：1–2 小时#

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

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

最终自测问题#

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

为什么部分选主元更稳定？
Jacobi 与 Gauss-Seidel 的核心区别是什么？
CG 为什么要求对称正定？
反幂法为什么要求解线性方程组？
Householder 与 Givens 都在做什么？
Lagrange 与 Newton 为什么得到相同多项式？
插值和最小二乘有什么区别？
离散最小二乘与连续最佳平方逼近怎样区分？
中心差商为什么比单边差商高一阶？
$n$ 点 Gauss 公式的代数精度是多少？
Newton 法怎样推广到方程组？
Euler 法的局部误差和全局误差分别是什么阶？

概述#

目录#

复习范围与优先级#

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

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

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

一页式答题原则#

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

1.1 章节主线#

有效数字判定#

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

例 1：已知真值#

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

易错点#

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

例 1：乘积的误差传播#

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

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

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

例 1：二次方程小根#

例 2：平方根之差#

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

本章检查清单#

Chapter 2 高斯消去与 LU 分解#

2.1 章节主线#

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

通用手算规则#

例 1：三对角矩阵#

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

易错点#

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

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

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

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

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

不选主元#

部分选主元#

例 2：零主元必须换行#

答题模板#

本章检查清单#

Chapter 3 线性方程组迭代法#

3.1 章节主线#

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

Jacobi#

Gauss-Seidel#

SOR#

例 1：Jacobi 与 Gauss-Seidel 两步#

例 2：SOR 一步#

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

例 1：由严格行对角占优判断收敛性#

例 2：判断非奇异矩阵能否直接使用 CG#

例 3：判断矩阵是否对称正定#

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

例 1：CG 第一步并验证残差正交#

例 2：CG 完整两步#

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

本章检查清单#

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

4.1 章节主线#

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

幂法#

反幂法#

移位反幂法#

例 1：幂法计算三步#

例 2：普通反幂法一步#

例 3：移位反幂法一步#

易错点#

4.3 重点题型二：Householder 反射#

例 1：二维反射#

例 2：三维反射#

选 α\alphaα 的技巧#

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

例 1：用 Givens 做 QR 分解#

例 2：做一步 QR 迭代#

Householder 与 Givens 的关系#

本章检查清单#

Chapter 5 插值法#

5.1 章节主线#

5.2 重点题型一：Lagrange 插值#

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

例 3： $1-\cos x$ #

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

例 2：一般 $3\times3$ 矩阵#

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

选 $\alpha$ 的技巧#

例 2： $e^x$ 的插值误差#

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

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

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

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

例 2：求 $\sqrt2$ #