数值分析复习

误差

截断误差：简化问题带来的误差，如将无穷级数截断为有限项计算。

舍入误差：实际计算是按有限位进行的，计算结果不精确导致的误差。

\(x\) 为准确值，\(x^*\) 为近似值，绝对误差为 \(e=x-x^*\)，相对误差为 \(e_r=\displaystyle \frac{x-x^*}{x}\)。

绝对误差限：\(\displaystyle |x-x^*| \leq \varepsilon\)

相对误差限：\(\displaystyle \frac{|x-x^*|}{|x|} \leq \varepsilon_r\)

四舍五入：四以下舍，五以上入，为五时看前一位，奇进偶不进。

有效数字：从第一个非零数字开始，到误差限对应位的位数。

插值

给定一个函数 \(f(x)\) 和函数在区间 \([a,b]\) 上的一组数据点 \((x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)\)。求一个多项式 \(P(x)\)，使得 \(P(x_i)=y_i\)，\((i=0,1,\cdots,n)\)。

定理：存在唯一的 \(n\) 次的多项式 \(P_n(x)\)，使得 \(P(x_i)=y_i\)，\((i=0,1,\cdots,n)\)。

如果 \(f(x)\) 是一个不超过 \(n\) 次的多项式函数，并且插值节点是唯一的（即所有 \(x_i\) 都不同），由以上定理可知插值多项式 \(P_n(x)\) 与 \(f(x)\) 相同。(作业第 1 题)

拉格朗日插值

\(L_n(x)=\displaystyle \sum_{i=0}^{n}y_i\ell_i(x)\)，其中插值基函数 \(\ell_i(x)=\displaystyle \prod_{j=0,j\neq i}^{n}\frac{x-x_j}{x_i-x_j}\)。

\(n\) 个互异节点可构造 \(n-1\) 次插值多项式，一次插值也称线性插值。

基函数性质

• \(\ell_i(x_i)=1\)，\(\ell_i(x_j)=0\)，\((i\neq j)\)
• \(\sum_{i=0}^{n}\ell_i(x_i)=1\) (作业第 1 题)

截断误差

插值余项 \(R_n(x)=f(x)-L_n(x)=\displaystyle \frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x)\)，其中 \(a\le x_0\le \cdots \le x_n \le b\)，\(\xi \in (a, b)\)

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

截断误差：\(|R_n(x)|\le \displaystyle \frac{M_{n+1}}{(n+1)!} |\omega_{n+1}(x)|\)，其中 \(M_{n+1}=\displaystyle \max_{x\in[a,b]}|f^{(n+1)}(x)|\)

题型：估计插值在给定点的误差

先写出余项和截断误差，然后根据函数的性质找到 \(M_{n+1}\) 的最大值，代入计算即可。

例：估计线性插值计算 \(e^{-2.1}\) 的近似值的误差。

解：\(R_1(x)=f(x)-L_1(x)=\displaystyle \frac{e^{-\xi}}{2!}(x-2)(x-3)\)，\(\xi \in (2,3)\)

因为 \(e^{-x}\) 单调递减，所以 \(|R_1(x)|\le \displaystyle \frac{e^{-2}}{2!} |(x-2)(x-3)|\)

\(|R_1(-2.1)|\le \displaystyle \frac{e^{-2}}{2} |(-2.1-2)(-2.1-3)| \approx 0.006090\)

牛顿插值

差商

零阶差商：\(f[x_0]=f(x_0)\)

一阶差商：\(f[x_0,x_1]=\displaystyle \frac{f(x_0)-f(x_1)}{x_0-x_1}\)

二阶差商：\(f[x_0,x_1,x_2]=\displaystyle \frac{f[x_0,x_1]-f[x_1,x_2]}{x_0-x_2}\)

\(n\) 阶差商：\(f[x_0,x_1,\cdots,x_n]=\displaystyle \frac{f[x_0,x_1,\cdots,x_{n-1}]-f[x_1,x_2,\cdots,x_n]}{x_0-x_n}\)

差商和导数的关系：\(f[x_0,x_1,\cdots,x_n]=\displaystyle \frac{f^{(n)}(\xi)}{n!}\)，其中 \(\xi \in (a,b)\)

差商表

\(x_i\)	\(f(x_i)\)	一阶差商	二阶差商	三阶差商
\(x_0\)	\(f(x_0)\)
\(x_1\)	\(f(x_1)\)	\(f[x_0,x_1]\)
\(x_2\)	\(f(x_2)\)	\(f[x_1,x_2]\)	\(f[x_0,x_1,x_2]\)
\(x_3\)	\(f(x_3)\)	\(f[x_2,x_3]\)	\(f[x_1,x_2,x_3]\)	\(f[x_0,x_1,x_2,x_3]\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)

牛顿插值公式

\(\begin{align}N_n(x)=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\cdots \\ + f[x_0,x_1,\cdots,x_n](x-x_0)(x-x_1)\cdots(x-x_{n-1})\end{align}\)

题型：求解牛顿插值多项式 (作业第 2 题)

1. 计算差商表，先列出 \(x_i\) 和 \(f(x_i)\)，然后计算差商。第 \(i\) 行 \(n\) 阶的差商值是 \(\displaystyle \frac {\text {左上一格}-\text {左边一格}}{x_i-x_{i-n}}\)

2. 写出插值多项式，系数为差商表的对角线元素，因子为该系数行上方的所有 \((x-x_i)\) 的乘积。

Hermite 插值

2 点 3 次 Hermite 插值

给定函数 \(f(x)\) 和 \(f'(x)\) 在 \(x_0\) 和 \(x_1\) 处的值，求一个 3 次多项式 \(H_3(x)\)，使得 \(H_3(x_i)=f(x_i)\)，\(H_3'(x_i)=f'(x_i)\)，\((i=0,1)\)。

\(x\)	\(x_0\)	\(x_1\)
\(f(x)\)	\(y_0\)	\(y_1\)
\(f'(x)\)	\(m_0\)	\(m_1\)

\(\begin{align}H_3(x) &= y_0 \left(1 - 2 \frac{x - x_0}{x_1 - x_0}\right) \ell_0^2(x) + y_1 \left(1 - 2 \frac{x - x_1}{x_1 - x_0}\right) \ell_1^2(x) \\ &\quad + m_0 (x - x_0) \ell_0^2(x) + m_1 (x - x_1) \ell_1^2(x)\end{align}\)

3 点 3 次 Hermite 插值

\(x\)	\(x_0\)	\(x_1\)	\(x_2\)
\(f(x)\)	\(y_0\)	\(y_1\)	\(y_2\)
\(f'(x)\)		\(m_1\)

\(\begin{align}H_3(x) &= y_0 + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) \\ &\quad+ k(x-x_0)(x-x_1)(x-x_2)\end{align}\)

将导数值代入，得到 \(k\) 的值。

也可直接待定系数法求解。

用重节点差商表构造 Hermite 插值

\(\displaystyle f[\underbrace{x,x,\cdots,x}_{n+1}] = \frac{f^{(n)}(x)}{n!}\)

只有当差商中所有的 \(x_i\) 相同时，才用上面公式计算。其余的差商计算方法与 Newton 插值相同。

如 \(f[1,1,1]=\displaystyle \frac{f''(1)}{2!}=0\)，\(f[1,1,2]=\displaystyle \frac{f[1,1]-f[1,2]}{1-2}\)

求解 Hermite 插值多项式时，除计算差商表时需注意重节点外，其余步骤与 Newton 插值相同。

分段线性插值

余项：\(R(x)=\displaystyle \frac{f''(\xi)}{2}(x-x_i)(x-x_{i+1})\)

截断误差：\(\displaystyle |R(x)|\le \frac {h^2}{8} \max_{x\in[a,b]}|f''(x)|\)，其中 \(h\) 为最大的插值节点间距。

函数逼近

内积空间

\(f(x)\) 和 \(g(x)\) 在区间 \([a,b]\) 上的内积：\((f,g) = \displaystyle \int_{a}^{b}\rho(x)f(x)g(x)dx\)，\(\rho(x)\) 为权函数。

内积的性质：

• \((f,g)=(g,f)\)
• \((f+g,h)=(f,h)+(g,h)\)
• \((cf,g)=c(f,g)\)，\(c\) 为常数
• \((f,f)\ge 0\)，当且仅当 \(f(x)=0\) 时 \((f,f)=0\)

欧式范数：\(\|f\|_2=\sqrt{(f,f)}\)

若 \((f,g)=0\)，则 \(f\) 和 \(g\) 在 \([a,b]\) 上带权 \(\rho(x)\) 正交。

最佳平方逼近

找到多项式 \(s^*(x)=\sum_{i=0}^{n}a^*_i\varphi^k(x)\)，使得 \(\|f-s^*\|_2\) 最小，\(s^*(x)\) 为 \(f(x)\) 在 \([a,b]\) 上的最佳平方逼近函数。

题型：求解最佳平方逼近多项式 (作业第 6 题)

实际是求解法方程组：\(\displaystyle \sum_{j=0}^{n}(\varphi_j,\varphi_k)a_j=(f,\varphi_k)\)

一般取函数类 \(\varPhi=\{1,x,x^2,\cdots,x^n\}\)

先计算出内积，然后列出法方程组，解出 \(a_j\) 即可。

题中给定的区间就是内积的积分区间。

正交多项式

\(g_n(x)\) 为 \([a,b]\) 上带权 \(\rho(x)\) 的 \(n\) 次正交多项式 \(\Leftrightarrow\)\(g_n(x)\) 为 \(n\) 次多项式，且与任何次数不超过 \(n-1\) 的多项式在 \([a,b]\) 上带权 \(\rho(x)\) 正交。

性质：

• \(\{g_0,g_1,\cdots,g_n\}\) 线性无关
• \(g_n(x)\) 的零点都是实的、互异的，且都在 \((a,b)\) 内

递推关系：\(g_{n+1}(x)=(x-a_{n+1})g_n(x)-b_ng_{n-1}(x)\)

其中 \(a_{n+1}=\displaystyle \frac{(xg_n,g_n)}{(g_n,g_n)}\)，\(b_0=0\)，\(b_n=\displaystyle \frac{(g_n,g_n)}{(g_{n-1},g_{n-1})}\)

最小二乘曲线拟合

函数类 \(\varPhi=\{\varphi_0(x),\varphi_1(x),\cdots,\varphi_m(x)\}\)

内积 \(\displaystyle (f,g)=\sum_{i=0}^{n}\omega(x_i)f(x_i)g(x_i)\)

法方程组

\(\begin{bmatrix} (\varphi_0,\varphi_0) & (\varphi_0,\varphi_1) & \cdots & (\varphi_0,\varphi_m ) \\ (\varphi_1,\varphi_0) & (\varphi_1,\varphi_1) & \cdots & (\varphi_1,\varphi_m ) \\ \vdots & \vdots & \ddots & \vdots \\ (\varphi_m,\varphi_0) & (\varphi_m,\varphi_1) & \cdots & (\varphi_m,\varphi_m ) \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_m \end{bmatrix} = \begin{bmatrix} (\varphi_0,Y) \\ (\varphi_1,Y) \\ \vdots \\ (\varphi_m,Y) \end{bmatrix}\)，其中 \(Y=(y_1, y_2, \cdots, y_N)^T\)

\(A=\begin{bmatrix} \varphi_0(x_1) & \varphi_1(x_1) & \cdots & \varphi_m(x_1) \\ \varphi_0(x_2) & \varphi_1(x_2) & \cdots & \varphi_m(x_2) \\ \vdots & \vdots & \ddots & \vdots \\ \varphi_0(x_N) & \varphi_1(x_N) & \cdots & \varphi_m(x_N) \end{bmatrix}\)，\(a=(a_0, a_1, \cdots, a_m)^T\)，\(W=\begin{bmatrix} w_1 & 0 & \cdots & 0 \\ 0 & w_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & w_N \end{bmatrix}\)

则法方程组可写成矩阵形式 \(A^TWAa=A^TWY\)

拟合曲线为 \(\varphi(x)=a_0\varphi_0(x)+a_1\varphi_1(x)+\cdots+a_m\varphi_m(x)\)

题型：最小二乘曲线拟合 (作业第 7、8 题)

法一：直接算内积，列出法方程组，解出系数

法二：利用矩阵形式，计算 \(A^TWA\) 和 \(A^TWY\)，解出系数

多项式拟合

函数类 \(\varPhi=\{1,x,x^2,\cdots,x^m\}\)

法方程组

\(\begin{bmatrix} \sum_{i=1}^{N}w_i & \sum_{i=1}^{N}w_ix_i & \cdots & \sum_{i=1}^{N}w_ix_i^m \\ \sum_{i=1}^{N}w_ix_i & \sum_{i=1}^{N}w_ix_i^2 & \cdots & \sum_{i=1}^{N}w_ix_i^{m+1} \\ \vdots & \vdots & \ddots & \vdots \\ \sum_{i=1}^{N}w_ix_i^m & \sum_{i=1}^{N}w_ix_i^{m+1} & \cdots & \sum_{i=1}^{N}w_ix_i^{2m} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_m \end{bmatrix} = \begin{bmatrix} \sum_{i=1}^{N}w_iy_i \\ \sum_{i=1}^{N}w_ix_iy_i \\ \vdots \\ \sum_{i=1}^{N}w_ix_i^my_i \end{bmatrix}\)，题目中常取 \(w_i=1\)。

拟合多项式为 \(\varphi(x)=a_0+a_1x+\cdots+a_mx^m\)

指数型拟合

取对数，转化为多项式拟合。

例：\(y=ae^{bx}\)，取对数得 \(\lg y=\lg a+bx\lg e\)，令 \(u=\lg y\)，\(A=\lg a\)，\(B=b \lg e\)，则 \(u=A+Bx\)，转化为多项式拟合。

正交多项式拟合

基函数正交时，法方程变为 \(Ga=Y\)，其中 \(G=\mathrm{diag}\{(\varphi_0,\varphi_0),(\varphi_1,\varphi_1),\cdots,(\varphi_m,\varphi_m)\}\)

系数容易求解 \(a_k=\displaystyle \frac{(\varphi_k,Y)}{(\varphi_k,\varphi_k)}\)

关键是找到正交多项式，可令 \(\varphi_0(x)=1\)，然后利用递推关系求解。

数值积分

梯形公式：\(\displaystyle \int_{a}^{b}f(x)dx \approx \frac{b-a}{2}[f(a)+f(b)]\)，误差为 \(-\displaystyle \frac{(b-a)^3}{12}f''(\xi)\)

中矩形公式：\(\displaystyle \int_{a}^{b}f(x)dx \approx (b-a)f(\frac{a+b}{2})\)

辛普森公式：\(\displaystyle \int_{a}^{b}f(x)dx \approx \frac{b-a}{6}[f(a)+4f(\frac{a+b}{2})+f(b)]\)，误差为 \(-\displaystyle \frac{(b-a)^5}{2880}f^{(4)}(\xi)\)

一般形式：\(\displaystyle \int_{a}^{b}f(x)dx \approx \sum_{k=0}^{n}A_kf(x_k)\)，\(x_k\) 为求积节点，\(A_k\) 为求积系数。

代数精度

如果积分公式对任意次数不超过 \(m\) 的多项式准确成立，但对 \(m+1\) 次多项式不一定准确成立，则称该积分公式具有 \(m\) 次代数精度。

一般地，要使积分公式具有 \(m\) 次代数精度，只要令它对于 \(f(x)=1,x,x^2,\cdots,x^m\) 成立，即

\(\begin{cases} \displaystyle \sum_{k=0}^{n}A_k=b-a \\ \displaystyle \sum_{k=0}^{n}A_kx_k=\frac{b^2-a^2}{2} \\ \cdots \\ \displaystyle \sum_{k=0}^{n}A_kx_k^m=\frac{b^{m+1}-a^{m+1}}{m+1} \end{cases}\)

梯形公式和中矩形公式具有 1 次代数精度，辛普森公式具有 3 次代数精度。

插值型求积公式

\(\displaystyle \int_{a}^{b}f(x)dx \approx \int_{a}^{b}L_n(x)dx = \sum_{k=0}^{n}A_kf(x_k)\)，其中 \(L_n(x)\) 为 \(f(x)\) 的 \(n\) 次插值多项式。

\(\displaystyle A_k=\int_{a}^{b}\ell_k(x)dx\)，\(\ell_k(x)=\displaystyle \prod_{j=0,j\neq k}^{n}\frac{x-x_j}{x_k-x_j}\)

定理：若 \(A_k>0\)，则求积公式是稳定的

牛顿 - 柯特斯公式

\(I_n=\displaystyle (b-a) \sum_{k=0}^{n}C_k^{(n)}f(x_k)\)，其中 \(x_k=a+\displaystyle kh\)，\(h=\displaystyle \frac{b-a}{n}\)

\(\displaystyle C_k^{(n)}=\frac {1}{b-a}A_k= \frac {1}{b-a}\int_{0}^{n}\ell_k(x)dx=\frac {(-1)^{n-k}}{n\cdot k!(n-k)!}\int_{0}^{n}\prod_{j=0,j\neq k}^{n}(x-j)dx\)

四阶公式 \(\displaystyle C=\frac {b-a}{90}[7f(x_0)+32f(x_1)+12f(x_2)+32f(x_3)+7f(x_4)]\)，称为柯特斯公式，误差为 \(-\displaystyle \frac{2(b-a)}{945}\left(\frac {b-a}{4}\right)^6f^{(6)}(\xi)\)

定理：当 \(n\) 为偶数时，\(I_n\) 至少有 \(n+1\) 次代数精度；当 \(n\) 为奇数时，\(I_n\) 至少有 \(n\) 次代数精度。

复化求积公式

将区间 \([a,b]\) 等分为 \(n\) 个长为 \(h\) 的小区间，在每个小区间用求积公式计算，然后求和。

复化梯形公式：\(\displaystyle T_n=\frac{h}{2}[f(a)+2\sum_{k=1}^{n-1}f(x_k)+f(b)]\)，误差为 \(-\displaystyle \frac{b-a}{12}h^2f''(\xi)\)

记 \(x_{k+1/2}=x_k+h/2\)

复化辛普森公式：\(\displaystyle S_n=\frac{h}{6}[f(a)+4\sum_{k=0}^{n-1}f(x_{k+1/2})+2\sum_{k=1}^{n-1}f(x_k)+f(b)]\)，误差为 \(-\displaystyle \frac{b-a}{180}\left(\frac {h}{2}\right)^4f^{(4)}(\xi)\)

高斯求积公式

利用 \(n+1\) 个互异节点达到 \(2n+1\) 次代数精度的求积公式。这要求在区间上选定特定的求积节点，称为高斯点。

推论：区间 \([a,b]\) 上的带权 \(\rho(x)\) 的正交多项式 \(\varphi_{n+1}(x)\) 的零点就是高斯点。

题型：构造求积公式 (作业第 14 题)

若题中给定了 \(n+1\) 个求积节点，则分别令 \(f(x)=1,x,\cdots,x^{n}\)，\(\int_{a}^{b}f(x)dx=\sum_{k=0}^{n}A_kf(x_k)\)，列出方程组解出 \(A_k\)。

代数精度的检验：从 \(f(x)=x^{n+1}\) 开始，判断 \(\int_{a}^{b}f(x)dx=\sum_{k=0}^{n}A_kf(x_k)\) 是否成立

若要构造高斯求积公式，先用待定系数设出首项系数为 1 的 \(n+1\) 次正交多项式 \(\varphi_{n+1}(x)\)，然后利用它与 \(1,x+a,x^2+bx+c,\cdots\) 之间两两内积为零求出待定系数。进而算出它的零点，再用上面的方法求出 \(A_k\) 即可。

二点高斯 - 勒让德求积公式：\(\displaystyle \int_{-1}^{1}f(x)dx \approx f(-\frac{1}{\sqrt{3}})+f(\frac{1}{\sqrt{3}})\)

三点高斯 - 勒让德求积公式：\(\displaystyle \int_{-1}^{1}f(x)dx \approx \frac{5}{9}f(-\frac{\sqrt{15}}{5})+\frac{8}{9}f(0)+\frac{5}{9}f(\frac{\sqrt{15}}{5})\)

任意区间 \([a,b]\) 上的高斯求积公式，做变量代换 \(x=\displaystyle \frac{b-a}{2}t+\frac{a+b}{2}\)，则

\(\displaystyle \int_{a}^{b}f(x)dx = \frac{b-a}{2}\int_{-1}^{1}f(\frac{b-a}{2}t+\frac{a+b}{2})dt \approx \frac{b-a}{2}\sum_{k=0}^{n}A_kf(\frac{b-a}{2}x_k+\frac{a+b}{2})\)，其中 \(x_k\) 为勒让德多项式的零点。

常微分方程数值解

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

将区间 \([a,b]\) 等分为 \(n\) 个小区间，步长 \(h=\displaystyle \frac{b-a}{n}\)，\(x_n=x_0+nh\)。目的是求出 \(y_n\) 在一系列点处的近似值。

欧拉法

显式欧拉公式：\(y_{n+1}=y_n+hf(x_n,y_n)\)

隐式欧拉公式：\(y_{n+1}=y_n+hf(x_{n+1},y_{n+1})\)

梯形公式：\(y_{n+1}=y_n+\displaystyle \frac{h}{2}[f(x_n,y_n)+f(x_{n+1},y_{n+1})]\)

改进欧拉法

先用欧拉法求出一个近似值 (预报值)\(\overline{y}_{n+1}\)，然后将其代入梯形公式右侧计算校正值，得到 \(y_{n+1}\)。

预报 \(\overline{y}_{n+1}=y_n+hf(x_n,y_n)\)

校正 \(y_{n+1}=y_n+\displaystyle \frac{h}{2}[f(x_n,y_n)+f(x_{n+1},\overline{y}_{n+1})]\)

局部截断误差

设 \(y(x)\) 是微分方程的精确解，\(y_{n+1}\) 是在 \(x_{n+1}\) 处的数值解，\(T_{n+1}=y(x_{n+1})-y_{n+1}\) 为局部截断误差。

若局部截断误差为 \(O(h^{p+1})\)，则称算法有 \(p\) 阶精度。

题型：估计局部截断误差及阶数 (作业第 17 题)

1. 假设 \(y(x_n)=y_n\)，则有 \(y'(x_n)=f(x_n,y_n)\)
2. 将数值解 \(y_{n+1}\) 的表达式代入 \(T_{n+1}=y(x_{n+1})-y_{n+1}\)
3. 将 \(y(x_{n+1})\) 在 \(x_n\) 处展开为泰勒级数
4. 计算出 \(T_{n+1}\) 的表达式，根据表达式判断局部截断误差的阶数

注意：若 \(\displaystyle T_{n+1}=\frac {y''(x_n)}{2}h^2+O(h^3)\)，则局部截断误差为 \(O(h^2)\)，算法有 1 阶精度。其中 \(\displaystyle \frac {y''(x_n)}{2}h^2\) 为局部截断误差的主项。

二元泰勒展开：\(f(x+\Delta x,y+\Delta y)=f(x,y)+\Delta x f_x(x,y)+\Delta y f_y(x,y)+O(\Delta x^2,\Delta y^2)\)

整体截断误差阶数比局部截断误差阶数低 1 阶。

龙格 - 库塔法

思想是确定系数使 \(T_{n+1}\) 的 \(h\) 幂次尽可能高，从而提高精度。

二阶龙格 - 库塔法的推导

\(y_{n+1}=y_n+h(\lambda_1k_1+\lambda_2k_2)\)

\(k_1=f(x_n,y_n)\)

\(k_2=f(x_n+p h,y_n+p hk_1)\)

将 \(k_2\) 展开为泰勒级数，得到 \(k_2=f(x_n,y_n)+p h f_x(x_n,y_n)+p h k_1f_y(x_n,y_n)+O(h^2)\)

因为 \(\displaystyle y''(x)=\frac {d}{dx}f(x,y)=f_x(x,y)+f_y(x,y)f(x,y)\)，所以 \(k_2=y'(x_n)+p h y''(x_n)+O(h^2)\)

将 \(k_2\) 代入 \(y_{n+1}\) 的表达式，得到 \(y_{n+1}=y_n+h\{\lambda_1y'(x_n)+\lambda_2[y'(x_n)+p h y''(x_n)]+O(h^2)\}=y_n+(\lambda_1+\lambda_2)hy'(x_n)+\lambda_2 p h^2 y''(x_n)+O(h^3)\)

与 \(y(x_{n+1})\) 的泰勒展开比较，得到 \(\lambda_1+\lambda_2=1\)，\(\lambda_2 p=\displaystyle \frac{1}{2}\)

满足上述条件的统称为二阶龙格 - 库塔格式。

收敛性与稳定性

对于方法 \(y_{n+1}=y_n+h\varphi(x_n,y_n,h)\)，若增量函数满足 \(\varphi(x,y,0)=f(x,y)\)，则该方法收敛。

题型：求绝对稳定区间 (作业第 17 题)

若未给出 \(f(x,y)\) 的表达式，则将 \(y'=f(x,y)=\lambda y\) 代入数值解法，化为 \(y_{n+1}=E(\lambda h)y_n\) 的形式，要稳定则要求 \(|E(\lambda h)|\le 1\)，解此关于 \(h\) 的不等式即可。

若给出了 \(f(x,y)\) 的表达式，则 \(\lambda = \frac{\partial f}{\partial y}\)，将 \(\lambda\) 代入 \(E(\lambda h)\)，解不等式即可。显式欧拉法的 \(E(\lambda h)=1+\lambda h\)

线性方程组解法

向量范数

向量范数：\(\|X\|\)，满足

• \(\|X\|\ge 0\)，\(\|X\|=0\) 当且仅当 \(X=0\)
• \(\|\alpha X\|=|\alpha|\|X\|\)
• \(\|X+Y\|\le \|X\|+\|Y\|\)

常见范数：

• \(\infty\) 范数：\(\|X\|_{\infty}=\displaystyle \max_{1\le i\le n}|x_i|\)
• 1 范数：\(\|X\|_1=\displaystyle \sum_{i=1}^{n}|x_i|\)
• 2 范数：\(\|X\|_2=\sqrt{\displaystyle \sum_{i=1}^{n}x_i^2}\)
• \(p\) 范数：\(\|X\|_p=\left(\displaystyle \sum_{i=1}^{n}|x_i|^p\right)^{1/p}\)

矩阵范数

矩阵范数：\(\|A\|\)，满足

• \(\|A\|\ge 0\)，\(\|A\|=0\) 当且仅当 \(A=0\)
• \(\|\alpha A\|=|\alpha|\|A\|\)
• \(\|A+B\|\le \|A\|+\|B\|\)
• \(\|AB\|\le \|A\|\cdot\|B\|\)

常用范数：

• 行范数：\(\|A\|_{\infty}=\displaystyle \max_{1\le i\le n}\sum_{j=1}^{n}|a_{ij}|\)，即矩阵各行元素绝对值之和的最大值
• 列范数：\(\|A\|_1=\displaystyle \max_{1\le j\le n}\sum_{i=1}^{n}|a_{ij}|\)，即矩阵各列元素绝对值之和的最大值
• 2 - 范数：\(\|A\|_2=\sqrt{\lambda_{\max}(A^TA)}\)，其中 \(\lambda_{\max}\) 为 \(A^TA\) 的最大特征值
• Frobenius 范数：\(\|A\|_F=\sqrt{\displaystyle \sum_{i,j=1}^{n}a_{ij}^2}\)，即矩阵所有元素平方和的平方根

谱半径：\(\rho(A)=\displaystyle \max_{1\le i\le n}|\lambda_i|\)，其中 \(\lambda_i\) 为 \(A\) 的特征值

误差分析

条件数：\(\mathrm{cond}(A)_p=\|A^{-1}\|_p\|A\|_p\)

原方程组为 \(AX=b\)，误差方程组为 \(A(X+\delta X)=b+\delta b\)，则相对误差 \(\displaystyle \frac {\|\delta X\|}{\|X\|}\le \mathrm{cond}(A)_p\frac {\|\delta b\|}{\|b\|}\)

迭代法

雅可比迭代法

从方程组的的 \(n\) 个方程中分别分离出 \(x_1,x_2,\cdots,x_n\)，然后迭代求解。

例：\(\begin{cases} 10x_1-x_2-2x_3=7.2 \\ -x_1+10x_2-2x_3=8.3 \\ -x_1-x_2+5x_3=4.2 \end{cases}\)

分离变量：\(\begin{cases} x_1=0.1x_2+0.2x_3+0.72 \\ x_2=0.1x_1+0.2x_3+0.83 \\ x_3=0.2x_1+0.2x_2+0.84 \end{cases}\)

建立迭代公式：\(\begin{cases} x_1^{(k+1)}=0.1x_2^{(k)}+0.2x_3^{(k)}+0.72 \\ x_2^{(k+1)}=0.1x_1^{(k)}+0.2x_3^{(k)}+0.83 \\ x_3^{(k+1)}=0.2x_1^{(k)}+0.2x_2^{(k)}+0.84 \end{cases}\)

取初始值 \(x_1^{(0)}=x_2^{(0)}=x_3^{(0)}=0\)，迭代计算即可。

方程组的系数矩阵 \(A=D+L+U\)，其中 \(D\) 为对角矩阵，\(L\) 为严格下三角矩阵，\(U\) 为严格上三角矩阵（严格表示对角线元素为 0）。

迭代公式为 \(X^{(k+1)}=-D^{-1}(L+U)X^{(k)}+D^{-1}b\)

迭代矩阵 \(B_J=-D^{-1}(L+U)\)

高斯 - 赛德尔迭代法

在雅可比迭代法的基础上，每次迭代时用新的值替换旧的值。

迭代公式为 \(\begin{cases} x_1^{(k+1)}=0.1x_2^{(k)}+0.2x_3^{(k)}+0.72 \\ x_2^{(k+1)}=0.1x_1^{(k+1)}+0.2x_3^{(k)}+0.83 \\ x_3^{(k+1)}=0.2x_1^{(k+1)}+0.2x_2^{(k+1)}+0.84 \end{cases}\)

迭代矩阵 \(B_G=-(D+L)^{-1}U\)

收敛性

收敛的充要条件：迭代矩阵的谱半径 \(\rho(B)<1\)

收敛的充分条件：迭代矩阵某一范数 \(\|B\|<1\)

迭代矩阵严格对角占优时，迭代法收敛。(严格对角占优：对角线元素绝对值大于同行其余元素绝对值之和)

非线性方程求根

简单迭代法

将方程 \(f(x)=0\) 变形为 \(x=\varphi(x)\)，然后迭代求解。迭代公式为 \(x_{k+1}=\varphi(x_k)\)。

收敛定理：若 \(\forall x \in [a,b]\) 总有 \(\varphi(x)\in[a,b]\)，存在常数 \(0\le L<1\)，使得 \(\forall x\in[a,b]\) 有 \(|\varphi'(x)|\le L\)，则简单迭代法收敛于方程的根 \(x^*\)

误差估计式：\(|x^*-x_k|\le \displaystyle \frac{L}{1-L}|x_{k+1}-x_k|\) 或 \(|x^*-x_k|\le \displaystyle \frac{L^k}{1-L}|x_1-x_0|\)，\(k\) 为迭代次数

局部收敛性定理：\(\varphi'(x)\) 在 \(x^*\) 的邻近连续，且 \(|\varphi'(x^*)|<1\)，则存在 \(x^*\) 的邻域，使得简单迭代法收敛于 \(x^*\)，即具有局部收敛性。

记迭代误差为 \(e_k=x_k-x^*\)，若存在实数 \(p\ge 1\)，使得 \(\displaystyle \lim_{k\to \infty}\frac{|e_{k+1}|}{|e_k|^p}=c\ne 0\)，则称迭代法具有 \(p\) 阶收敛。

当 \(p=1\) 且 \(0<c<1\) 时，称线性收敛；当 \(p>1\) 时，称超线性收敛；当 \(p=2\) 时，称平方收敛。\(p\) 越大，收敛速度越快。

定理：\(\varphi(x)\) 在 \(x^*\) 的某个邻域内 \(p\) 次连续可微 \((p \ge 2)\)，且 \(\varphi'(x^*)=\varphi''(x^*)=\cdots=\varphi^{(p-1)}(x^*)=0\)，\(\varphi^{(p)}(x^*)\ne 0\)，则当 \(x_0\) 充分靠近 \(x^*\) 时，简单迭代法具有 \(p\) 阶收敛。

牛顿迭代法

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

若牛顿法收敛于方程 \(f(x)=0\) 的根 \(x^*\)，则至少有二阶收敛速度。

定理：\(f(x)\) 在根 \(x^*\) 邻近二阶连续可微，且 \(f'(x^*)\ne 0\)，则当 \(x_0\) 充分靠近 \(x^*\) 时，牛顿法具有二阶收敛。

\(x^*\) 是方程的 \(m\) 重根时：\(x_{k+1}=x_k-m\displaystyle \frac{f(x_k)}{f'(x_k)}\) 收敛且至少有二阶收敛速度。

如果不知道 \(m\)，可设 \(u(x)=\displaystyle \frac{f(x)}{f'(x)}\)，则 \(x^*\) 是 \(u(x)\) 的单零点，问题转化为求解 \(u(x)=0\) 的单根。

迭代函数为 \(g(x)=x-\displaystyle \frac{u(x)}{u'(x)}\)，则迭代公式为 \(x_{k+1}=g(x_k)\)

弦截法：\(x_{k+1}=x_k-\displaystyle \frac{f(x_k)(x_k-x_{k-1})}{f(x_k)-f(x_{k-1})}\)，将 \(f'(x_k)\) 近似用差商代替 \(\displaystyle \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}\)

题型：收敛性判断 (作业第 19、20 题)

1. 判断简单迭代法收敛性：先用零点定理判断区间上有根，再计算 \(\varphi'(x)\)，判断 \(|\varphi'(x)|\) 是否小于 1
2. 判断牛顿法收敛性：二阶连续可微，且 \(f'(x^*)\ne 0\)，局部二阶收敛
3. 收敛阶数：用定义 (泰勒展开) 或迭代函数在 \(x^*\) 处前 \(p-1\) 阶导数为零判断 (极限)