数值分析笔记

发表于 Waline： 阅读次数：

本文向量、矩阵符号均不以粗体标识，从上下文推断

线性代数

特征值

求矩阵 \(A\) 的特征值 \(\lambda_i\) 以及特征向量 \(x\)：求解方程 \(|A-\lambda I|=0\)

二次型

设 \(A\) 是对称正定阵，\(\forall x\neq 0 \in R^n\) 二次型 \(x^{\mathrm T}Ax > 0\)

存在可逆矩阵 \(L\) 使 \(A = LL^T\)

\(A\) 特征值、顺序主子式均大于零

范数

向量范数

向量范数 \(f(x)=\|x\|\) 定义：

  1. 非负 \(\|x\|\geq 0, \|x\|=0\iff x=0\)
  2. 线性 \(\forall \alpha \in R, \|\alpha x\|=|\alpha|\|x\|\)
  3. 三角不等式 \(\|x+y\|\leq\|x\|+\|y\|\)

常用向量范数

  • 1 范数 \(\|x\|_1=\sum_{i=1}^{n} |x_i|\)
  • 2 范数 \(\|x\|_2=\left(\sum_{i=1}^{n} x_i^2\right)^{\frac{1}{2}}\)
  • \(\infty\) 范数 \(\|x\|_{\infty}=\max_{1\leq i\leq n}|x_i|\)

向量范数等价性：\(\exists c_1>0, c_2>0, \mathrm{s.t.} \forall x\in R^n, c_1\|x\|_q\leq\|x\|_p\leq c_2\|x\|_q\)

矩阵范数

定义：

  1. 非负
  2. 线性
  3. 三角不等式
  4. \(\|AB\|\leq\|A\|\|B\|\)

相容性：\(\|Ax\|\leq \|A\|\|x\|\)

算子范数（与对应向量范数相容）

\[ \|A\|_p=\max_{x\neq 0}\frac{\|Ax\|_p}{\|x\|_p}=\max_{\|x\|_p=1}{\|Ax\|_p} \] 常用矩阵范数

  • 列范数 \(\|A\|_1=\max_{1\le j \le n}\left\{\sum_{i=1}^n|a_{ij}|\right\}\)
  • 谱范数 \(\|A\|_2=\sqrt{\lambda_{max}(A^{\mathrm T}A)}\)，矩阵 \(A^{\mathrm T}A\) 最大的特征值开根号
  • 行范数 \(\|A\|_\infty=\max_{1\le i \le n}\left\{\sum_{j=1}^n|a_{ij}|\right\}\)
  • F 范数（与 2 范数相容）\(\|A\|_F=\sqrt{\sum_{a_{ij}\in A}a_{ij}^2}\)

谱半径

对于矩阵 \(A\)，\(\lambda_i\) 是它的特征值，谱半径 \(\rho(A)=\max_{1\le i\le n}\{|\lambda_i|\}\)

谱半径不超过任意一种范数

条件数

\[ \mathrm{Cond}(A)\triangleq \|A\|\|A^{-1}\| \]

条件数大的矩阵称为“病态”矩阵，反之“良态”

线性方程组

高斯消元

高斯消元的第 \(k-1\) 步：

\[ A^{(k-1)}x=b^{(k-1)} \]

其中 \[ A^{(k-1)}= \begin{pmatrix} a_{11}^{(0)} & a_{12}^{(0)} & \cdots & a_{1k}^{(0)} & \cdots & a_{1n}^{(0)} \newline & a_{22}^{(1)} & \cdots & a_{2k}^{(1)} & \cdots & a_{2n}^{(1)} \newline & & \ddots & \vdots & & \vdots \newline & & & a_{kk}^{(k-1)} & \cdots & a_{kn}^{(k-1)} \newline & & & \vdots & & \vdots \newline & & & a_{nk}^{(k-1)} & \cdots & a_{nn}^{(k-1)} \newline \end{pmatrix} , b^{(k-1)}= \begin{pmatrix} b_1^{(0)} \newline b_2^{(1)} \newline \vdots \newline b_k^{(k-1)} \newline b_n^{(k-1)} \newline \end{pmatrix} \]

有

\[ a_{ij}^{(k)} = a_{ij}^{(k-1)}-\frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}a_{kj}^{(k-1)} = a_{ij}^{(k-1)}-l_{ik}a_{kj}^{(k-1)} \]

回代过程公式很显然

消元过程乘除法运算量 \(\frac{n^3}{3}+\frac{n^2}{2}-\frac{5n}{6}\)

回代过程乘除法运算量 \(\frac{n^2}{2}+\frac{n}{2}\)

高斯消元顺利进行的条件：\(a_{kk}^{(k-1)}\neq 0 \iff D_k \neq 0\)，其中 \(D_k\) 为 \(k\) 阶顺序主子式

另外的充分条件：\(A\) 是对称正定阵；\(A\) 是严格对角占优阵

列主元高斯消元法：将最大方程与当前方程交换

LU 分解

高斯消元每一步其实是乘单位下三角矩阵 \(L_k\)

LU 分解的唯一性：\(L=\prod_k L_k\)

杜利特尔分解：单位下三角矩阵 \(L\) 与上三角矩阵 \(U\)；反之为克劳特分解

\[ \begin{cases} u_{1j}=a_{1j} &, j = 1, 2, \cdots,n, \newline l_{i1}=\dfrac{a_{i1}}{u_{11}} &, i = 2,3,\cdots,n, \newline u_{ij}=a_{ij}-\sum\limits_{k=1}^{i-1}l_{ik}u_{kj} &, i = 2,3,\cdots,n; j=i,i+1,\cdots, n,\\ l_{ij}=\dfrac{a_{ij}-\sum\limits_{k=1}^{j-1}l_{ik}u_{kj}}{u_{jj}} &,j=2,3,\cdots,n-1;i=j+1,j+2,\cdots,n. \end{cases} \]

LU 分解解方程组 \(Ax=b \iff LUx=b \iff Ly=b,Ux=y\)，均类似回代；乘除法运算次数与高斯消元法相同

LU 分解时分解增广矩阵即可直接解出 \(y\)

平方根法

对称正定阵 \(A=LDL^{\mathrm T}\)，其中 \(D\) 为 LU 分解中 \(U\) 取对角元的矩阵

楚列斯基分解：\(A=LDL^{\mathrm T}=LD^{\frac{1}{2}}D^{\frac{1}{2}}L^{\mathrm T}=(LD^{\frac{1}{2}})(LD^{\frac{1}{2}})^{\mathrm T}\triangleq GG^{\mathrm T}\)

\[ G\triangleq \begin{pmatrix} g_{11} \newline g_{21} & g_{22} \newline g_{31} & g_{32} & g_{33} \newline \vdots & \vdots & & \ddots \newline g_{n1} & g_{n2} & \cdots & g_{n,n-1} & g_{nn} \newline \end{pmatrix} \]

分解公式

\[ \begin{cases} g_{11}=\sqrt{a_{11}} &, \newline g_{i1}=\dfrac{a_{i1}}{g_{11}} &, i = 2,3,\cdots,n, \newline g_{jj}=\left(a_{jj}-\sum\limits_{k=1}^{j-1} g_{jk}^2\right)^\frac{1}{2} &, i = 2,3,\cdots,n,\\ g_{ij}=\dfrac{a_{ij}-\sum\limits_{k=1}^{j-1}g_{ik}g_{jk}}{g_{jj}} &,j=2,3,\cdots,n-1;i=j+1,j+2,\cdots,n \newline \end{cases} \]

发现 \(y_i\) 与 \(g_{ij}\) 的计算方式一致，可以在 LU 分解时分解增广阵直接算出 \(y\)

该分解是稳定的，平方根法回代同 LU 分解，总乘除法次数 \(\frac{n^3}{6}+n^2-\frac{n}{6}\)

改进平方根法

对称正定阵 \(A=LDD^{-1}U=LDL^{\mathrm T}\)，

\[ \begin{cases} u_{1j}=a_{1j} &, j = 1, 2, \cdots,n, \newline l_{i1}=\dfrac{a_{i1}}{u_{11}} &, i = 2,3,\cdots,n, \newline u_{ij}=a_{ij}-\sum\limits_{k=1}^{i-1}l_{ik}u_{kj} &, i = 2,3,\cdots,n; j=i,i+1,\cdots, n,\\ l_{ij}= \dfrac{u_{ji}}{u_{ii}} &,j=2,3,\cdots,n-1;i=j+1,j+2,\cdots,n. \end{cases} \]

总乘除法次数 \(\frac{n^3}{6}+\frac{3n^2}{2}-\frac{2n}{3}\)

追赶法

三对角方程组 \(Ax=d\) 的 LU 分解

\[ A= \begin{pmatrix} b_1 & c_1 & & & \newline a_2 & b_2 & c_2 & & \newline & \ddots & \ddots & \ddots & \newline & & a_{n-1} & b_{n-1} & c_{n-1} \newline & & & a_{n} & b_n \newline \end{pmatrix} = \begin{pmatrix} 1 & & & & \newline l_2 & 1 & & & \newline & \ddots & \ddots & & \newline & & l_{n-2} & 1 & \newline & & & l_{n-1} & 1 \newline \end{pmatrix} \begin{pmatrix} u_1 & c_1 & & & \newline & u_2 & c_2 & & \newline & & \ddots & \ddots & \newline & & & u_{n-2} & c_{n-1} \newline & & & & u_{n-1} \newline \end{pmatrix} \]

公式

\[ \begin{cases} u_1 = b_1 &, \newline l_i = \dfrac{a_i}{u_{i-1}} &, i = 2, 3, \cdots, n, \newline u_i=b_i-l_ic_{i-1} &, i = 2, 3, \cdots, n. \newline \end{cases} \]

\(Ly=b,Ux=y\)，回代得

\[ \begin{cases} y_1=d_1\\ y_i=d_i-l_iy_{i-1} \end{cases} , \begin{cases} x_n=\dfrac{y_n}{u_n}\\ x_i=\dfrac{y_i-c_ix_{i+1}}{u_i} \end{cases} \]

发现 \(y_i\) 与 \(u_i\) 的计算方式一致，可以在 LU 分解时分解增广阵直接算出 \(y\)

乘除法次数 \(5n-4\)

插值法

多项式插值法截断误差估计式：设 \(f^{(n)}(x)\) 在 \([a,b]\) 上连续，\(f^{(n+1)}(x)\) 在 \((a,b)\) 上存在，\(p_n(x)\) 是满足插值条件的 \(n\) 次插值多项式，则存在 \(\xi=\xi(x)\in(a,b)\)，使

\[ R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)(\xi)}}{(n+1)!}(x-x_0)(x-x_1)\cdots(x-x_n) =\frac{f^{(n+1)(\xi)}}{(n+1)!}\pi_{n+1}(x) \]

截断误差实用估计式：设 \(p_n(x)\)，\(\tilde p_n(x)\) 分别是节点 \(x_0,x_1,\cdots,x_n\)，\(x_1,x_2,\cdots,x_{n+1}\) 构造的插值多项式

\[ \begin{cases} f(x)-p_n(x)\approx \dfrac{\tilde p_n(x)-p_n(x)}{x_{n+1}-x_0}(x-x_0) \newline f(x)-\tilde p_n(x)\approx \dfrac{\tilde p_n(x)-p_n(x)}{x_{n+1}-x_0}(x-x_{n+1}) \end{cases} \]

拉格朗日插值多项式

有形式 \(L_n(x)=\sum_{i=1}^n l_i(x)y_i\)，其中 \(l_i(x)\) 为 \(n\) 次多项式且只在 \(x_i\) 处为一，其他插值节点处为零点 \[ L_n(x)=\sum_{i=1}^n \frac{(x-x_0)(x-x_1)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_n)}{(x_i-x_0)(x_i-x_1)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)}y_i \]

牛顿插值多项式

差商

\[ \begin{cases} f[x_i]=f(x_i) \newline f[x_i,x_{i+1},\cdots,x_{i+k}]=\dfrac{f[x_{i+1},\cdots,x_{i+k}]-f[x_i,\cdots,x_{i+k-1}]}{x_{i+k}-x_i} \end{cases} \]

差商表

\(x_i\) \(f[x_i]\) \(f[x_{i-1},x_i]\) \(f[x_{i-2},x_{i-1},x_{i}]\) \(f[x_{i-3},x_{i-2},x_{i-1},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}]\)

牛顿插值多项式 \(N_n(x)\)，（其中 \(\pi_{0}(x)=1\)） \[ N_n(x)=\sum_{i=0}^{n}f[x_0,\cdots,x_i]\pi_{i}(x) \] 误差与实用误差估计式

\[ R_n(x)=f(x)-N_n(x)=f[x_0,x_1,\cdots,x_n,x]\pi_{n+1}(x)\approx f[x_0,x_1,\cdots,x_n,x_{n+1}]\pi_{n+1}(x) = N_{n+1}(x)-N_n(x) \]

差商的性质 \[ f[x_0,x_i,\cdots,x_n]=\sum_{i=0}^n\frac{f(x_i)}{(x-x_0)(x-x_1)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_n)} \] 差商与导数的关系（误差项相等） \[ f[x_i,x_i,\cdots,x_{i+k}]=\frac{f^{(k)}(\xi)}{k!} \] 其中 \(\xi\) 在 \(x_i,x_{i+1},\cdots,x_{i+k}\) 之间

\(k\) 阶差商对应 \(k\) 阶导数

设 \(f(x)\) 是 \(k\) 次多项式，\(f[x_0,x_1,\cdots,x_{k-1}, x]\) 是 \(x\) 的 \(n-k\) 次多项式（\(k>n\) 时为零）

埃尔米特多项式

牛顿型：利用差商和导数的关系填入差商表不定式位置，该表有多重节点

三次样条插值

二阶导数连续

在子区间 \([x_{i-1},x_{i}]\) 上的表达式

\[ S(x)= \frac{(x_i-x)^3}{6h_i}M_{i-1} + \frac{(x-x_{i-1})^3}{6h_i}M_{i} + \left(y_{i-1}-\frac{h_i^2}{6}M_{i-1}\right)\frac{x_i-x}{h_i} + \left(y_{i}-\frac{h_i^2}{6}M_{i}\right)\frac{x_i-x_{i-1}}{h_i} \]

其中 \(h_i=x_i-x_{i-1}\)，\(f''(x_i)=M_{i}\)

第一种边界条件三弯矩方程（边界二阶导已知）

\[ \begin{bmatrix} 2 & \lambda_1 & & & \newline \mu_2 & 2 & \lambda_2 & & \newline & \ddots & \ddots & \ddots & \newline & & \mu_{n-2} & 2 & \lambda_{n-2} \newline & & & \mu_{n-1} & 2 \newline \end{bmatrix} \begin{bmatrix} M_1 \newline M_2 \newline \vdots \newline M_{n-2} \newline M_{n-1} \newline \end{bmatrix} = \begin{bmatrix} d_1 - \mu_1 M_0 \newline d_2 \newline \vdots \newline d_{n-2} \newline d_{n-1} - \lambda_{n-1} M_n \newline \end{bmatrix} \]

其中 \(\mu_i = \dfrac{h_i}{h_i+h_{i+1}}\)，\(\lambda_i=1-\mu_i\)，\(d_i=6f[x_{i-1},x_{i},x_{i+1}]\)

第二种边界条件三弯矩方程（边界一阶导已知）

\[ \begin{bmatrix} 2& 1\\ \mu_1& 2 & \lambda_1 & & & & \newline & \mu_2 & 2 & \lambda_2 & & & \newline & & \ddots & \ddots & \ddots & & \newline & & & \mu_{n-2} & 2 & \lambda_{n-2}& \newline & & & & \mu_{n-1} & 2 & \lambda_{n-1} \newline & & & & & 1 & 2 \end{bmatrix} \begin{bmatrix} M_0\\ M_1 \newline M_2 \newline \vdots \newline M_{n-2} \newline M_{n-1} \newline M_n\\ \end{bmatrix} = \begin{bmatrix} d_0\\ d_1\\ d_2 \newline \vdots \newline d_{n-2} \newline d_{n-1}\\ d_n \end{bmatrix} \]

其中 \(d_0=6f[x_{0},x_{0},x_{1}]\)，\(d_n=6f[x_{n-1},x_{n},x_{n}]\)

第三种边界条件三弯矩方程（周期函数二阶导连续）

\[ \begin{bmatrix} 2 & \lambda_1 & & & \lambda_1 \newline \mu_2 & 2 & \lambda_2 & & \newline & \ddots & \ddots & \ddots & \newline & & \mu_{n-1} & 2 & \lambda_{n-1} \newline \mu_n & & & \mu_{n} & 2 \newline \end{bmatrix} \begin{bmatrix} M_1 \newline M_2 \newline \vdots \newline M_{n-1} \newline M_{n} \newline \end{bmatrix} = \begin{bmatrix} d_1 \newline d_2 \newline \vdots \newline d_{n-1} \newline d_{n} \newline \end{bmatrix} \]

其中 \(d_n=6f[x_{n-1},x_{n},x_{1}]\)

函数最优逼近

函数线性相关定义（略）

\(n+1\) 维线性子空间 \(V=\mathrm{span}\{\phi_0(x),\phi_1(x),\cdots,\phi_n(x)\}\)

连续函数 \(f,g\in C[a,b]\) 内积 \[ (f,g)=\int_a^b w(x)f(x)g(x)\ \mathrm dx \] 内积性质：交换律，线性，分配律，自乘非负性

内积定义函数范数（略）

正交多项式

\(g_0(x),g_1(x),\cdots,g_k(x),\cdots\)，称为正交函数族，若 \[ (g_i,g_j)=\begin{cases} 0&, j\neq i,\\ \gamma_i > 0&, j=i. \end{cases} \] 标准正交函数族：\(\gamma_i=1\)；正交多项式：\(g_k\) 是 \(k\) 次多项式

最高项系数为 \(1\) 的正交多项式三项递推关系

\[ \begin{cases} g_0=1\\ g_1(x)=x-\frac{\beta_0}{\gamma_0}\\ g_{k+1}(x)=\left(x-\frac{(xg_k,g_k)}{(g_k,g_k)}\right)g_k(x)-\frac{(g_k,g_k)}{(g_{k-1},g_{k-1})}g_{k-1}(x) \end{cases} \]

常记 \(\gamma_k=(g_k,g_k)\)，\(\beta_k=(xg_k,g_k)\)，\(b_k=\dfrac{\beta_k}{\gamma_k}\)，\(c_k=\dfrac{\gamma_k}{\gamma_{k-1}}\)

常用正交多项式

  • 三角函数系 \(1,\cos x,\sin x,\cos 2x, \sin 2x,\cdots\)：\([-\pi,\pi]\) 上关于 \(w(x)=1\)
  • 勒让德多项式：\([-1,1]\) 上关于 \(w(x)=1\)
  • 拉盖尔多项式：\([0,+\infty]\) 上关于 \(w(x)=\mathrm e^{-x}\)
  • 埃尔米特多项式：\((-\infty,+\infty)\) 上关于 \(w(x)=\mathrm e^{-x^2}\)
  • 切比雪夫多项式：\([-1,+1]\) 上关于 \(w(x)=\frac{1}{\sqrt{1-x^2}}\)

最优平方逼近

使用广义多项式 \(p(x)=c_0\phi_0(x)+c_1\phi_1(x)+\cdots\) 逼近给定函数 \(f(x)\)，若 \(f(x)\) 是列表函数则是最小二乘逼近，误差 \(\|p-f\|_2\) 最小

正规方程组（对称正定阵）

\[ \begin{pmatrix} (\phi_0,\phi_0) & (\phi_0,\phi_1) & \cdots & (\phi_0,\phi_n) \newline (\phi_1,\phi_0) & (\phi_1,\phi_1) & \cdots & (\phi_1,\phi_n) \newline \vdots & \vdots & & \vdots \newline (\phi_n,\phi_0) & (\phi_n,\phi_1) & \cdots & (\phi_n,\phi_n) \newline \end{pmatrix} \begin{pmatrix} c_0\\ c_1\\ \vdots\\ c_n \end{pmatrix}= \begin{pmatrix} (\phi_0,f)\\ (\phi_1,f)\\ \vdots\\ (\phi_n,f) \end{pmatrix} \]

选取广义多项式的方法：

  1. 选取一组线性无关的基函数
  2. 利用三项递推关系构造
  3. 利用已知正交多项式变量替换

最优一致逼近

使用广义多项式逼近使偏差 \(E=\|f-p_n\|_\infty\) 达到最小

偏差点 \(\tilde x\)：\(|f(\tilde x)-p_n(\tilde x)|=E\)

切比雪夫定理：\(p_n(x)\) 是 \(f(x)\) 的最优一致逼近，充分必要条件是在 \([a,b]\) 上至少有 \(n+2\) 个依次正负的偏差点（切比雪夫交错点组）

定理：若 \([a,b]\) 上连续则唯一性；若 \([a,b]\) 上 \(n+1\) 阶可导且 \(f^{(n+1)}(x)\) 在 \((a,b)\) 定号则端点属于交错点组

构造方法为求解极值方程组：

\[ \begin{cases} f(\tilde x_i)-p_n(\tilde x_i)=(-1)^{i}\mu &, i=0,2,\cdots,n+1, \newline f'(\tilde x_i)-p'(\tilde x_i)=0 &, i=1,2,\cdots, n. \end{cases} \]

近似最优一致逼近

最大误差达到最小的多项式

切比雪夫插值多项式法

所使用的插值节点是 \(n+1\) 次切比雪夫多项式 \(T_{n+1}(x)\) 的零点时，\(\max\limits_{-1\le x\le 1} |\pi_{n+1}(x)|\) 取最小值 \(\dfrac{1}{2^n}\)，误差估计式 \(\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\dfrac{1}{2^n}\)

\(T_{n+1}(x),\ x\in[-1,1]\) 的零点 \(x_i=\cos\left[\dfrac{2i+1}{2(n+1)\pi}\right],\ i=0,1,\cdots,n\)

数值积分

\[ I[f]=\int_a^b f(x)\ \mathrm dx=\int_a^b p(x)\ \mathrm dx+\int_a^b R(x)\ \mathrm dx = Q[f]+R[f] \]

牛顿-科茨求积公式

\(p(x)\) 为等距节点插值多项式

令 \(h=\dfrac{b-a}{n}\)，\(x_i=a+ih,\ i-0,1,\cdots,n\)

求积系数 \(A_i\)：\(Q[f]=\sum_i\left(\int_a^bl_i(x)\ \mathrm dx\right)f(x_i)=\sum_iA_if(x_i)\)

梯形求积公式（\(n=1\)）

\[ Q[f]=\frac{b-a}{2}[f(a)+f(b)] \]

截断误差（使用广义积分中值定理）

\[ R_1[f]=\int_a^b\frac{f''(\xi)}{2!}(x-a)(x-b)\ \mathrm dx=-\frac{(b-a)^3}{12}f''(\eta) \]

辛普森求积公式（\(n=2\)）

\[ Q[f]=\frac{h}{3}[f(x_0)+4f(x_1)+f(x_2)]=\frac{b-a}{6}\left[f(a)+4\left(\frac{a+b}{2}\right)+f(b)\right] \]

截断误差 \(R_2[f]=-\frac{h^5}{90}f^{(4)}(\eta)=-\frac {(b-a)^5} {2880}f^{(4)}(\eta)\)，代数精度 \(m=3\)

科茨求积公式（\(n=4\)）

\[ Q[f]=\frac{b-a}{90}\left[7f(a)+32f(x_1)+12f(x_2)+32f(x_3)+7f(b)\right] \]

截断误差 \(R_4[f]=-\frac{8h^7}{945}f^{(6)}(\eta)=-\frac {(b-a)^7}{1935360}f^{(6)}(\eta)\)

复化求积公式

设 \([a,b]\) 划分 \(n\) 个等长子区间，\(nh=b-a\)，分别使用牛顿-科茨求积公式

连续函数介值定理得截断误差，复化梯形 \(R_{T_n}[f]=\frac{h^3}{12}nf''(\eta)\)；其他类似

变步长积分法：\(n\) 翻倍直到 \(|T_{2n}-T_n|\le \varepsilon\)

龙贝格积分法

\[ \begin{align} T_0 & =\frac{b-a}{2}(f(a)+f(b)) \nonumber\newline T_{2^{k+1}} & =\frac{1}{2} T_{2^k}+\frac{b-a}{2^{k+1}}\sum _{i=1}^{2^{k}}f\left(a+(2i-1)\frac{b-a}{2^{k+1}}\right) \nonumber\newline S_{2^k} & =T_{2^{k+1}}+ \frac{1}{4^{1}-1} (T_{2^{k+1}}-T_{2^k}) \nonumber\newline C_{2^k} & =S_{2^{k+1}}+ \frac{1}{4^{2}-1} (S_{2^{k+1}}-S_{2^k}) \nonumber\newline R_{2^k} & =C_{2^{k+1}}+ \frac{1}{4^{3}-1} (C_{2^{k+1}}-C_{2^k}) \nonumber \end{align} \]

直到 \(|R_{2^{k+1}}-R_{2^k}|<\varepsilon\)

待定系数法

代数精度 \(m\)：对于任意次数小于等于 \(m\) 的多项式截断误差为零而对 \(m+1\) 次多项式不为零

待定系数法：节点 \(x_i\) 给定后，求解方程组 \(R[x^k]=0,\ k=0,1,\cdots,m\)

广义皮亚诺定理：\(R[f(x)]=R[e(x)]\)，其中 \(e(x)=\dfrac{f^{(m+1)}(\xi)}{(m+1)!}(x-\tilde x_0)\cdots(x-\tilde x_m)\)，其中 \(\tilde x_i\) 为任意插值节点，\(\xi\) 为区间内与 \(x,\tilde x_i\) 有关的点；计算时选取 \(\tilde x_i\) 为插值节点可以使 \(Q[e]=0\)

高斯型求积公式

有 \(n+1\) 个插值节点且代数精度达到 \(2n+1\) 的求积公式

求解方法：

  • 取 \(f(x)=1,x,\cdots,x^{2n+1}\) 求解非线性方程组
  • 节点 \(x_i\) 为 \([a,b]\) 上关于权函数 \(w(x)\) 正交的 \(n+1\) 次正交多项式 \(g_{n+1}\) 的零点

求积系数 \[ A_i=\frac{\gamma_n}{g'_{(n+1)}(x_i)g_n(x_i)} \] 截断误差 \[ R[f]=\frac{\gamma_{n+1}}{(2n+2)!}f^{(2n+2)}(\eta),\ a\le \eta\le b \]

数值积分稳定性

当求积系数均为正时是稳定的，例外如：\(n>8\) 的牛顿-科茨求积公式

数值微分

插值型数值微分公式

两点型

\[ \begin{cases} f'(x_0)=\dfrac{f(x_1)-f(x_0)}{h}-\dfrac{h}{2}f''(\xi) \newline f'(x_1)=\dfrac{f(x_0)-f(x_1)}{h}+\dfrac{h}{2}f''(\xi) \newline \end{cases} \]

三点型

\[ \begin{cases} f'(x_0)=\dfrac{-3f(x_0)+4f(x_1)-f(x_2)}{2h}+\dfrac{h^2}{3}f''(\xi) \newline f'(x_1)=\dfrac{f(x_2)-f(x_0)}{2h}+\dfrac{h^2}{6}f'''(\xi) \newline f'(x_2)=\dfrac{f(x_0)-4f(x_1)+3f(x_2)}{2h}+\dfrac{h^2}{3}f''(\xi) \newline \end{cases} \]

求二阶导

\[ \begin{cases} f''(x_0)=\dfrac{f(x_0)+-2f(x_1)+f(x_2)}{h^2}-hf'''(\xi)+\dfrac{h^2}{6}f^{(4)}(\bar \xi) \newline f''(x_1)=\dfrac{f(x_0)+-2f(x_1)+f(x_2)}{h^2}+\dfrac{h^2}{12}f^{(4)}(\bar \xi) \newline f''(x_2)=\dfrac{f(x_0)+-2f(x_1)+f(x_2)}{h^2}+hf'''(\xi)+\dfrac{h^2}{6}f^{(4)}(\bar \xi) \newline \end{cases} \]

待定系数法

代数精度与数值积分定义一致 \[ R[f]=f^{(k)}-\sum_{i=0}^kA_kf(x_k) \] 或埃尔米特插值（略）

外推求导法

由泰勒公式导出

\[ \begin{cases} h_i = \dfrac{h}{2^i} \newline T_0^i = T(h_i)=\dfrac{f(x+h_i)-f(x-h_i)}{2h_i}\\ T_k^i=T_{k-1}^{i+1}+\dfrac{1}{4^k-1}(T_{k-1}^{i+1}-T^i_{k-1}) \end{cases} \]

截断误差 \[ R[f]=O(h^{2(k+1)}) \]

三次样条求导法

顾名思义

非线性方程（组）迭代法

解单变量方程 \(f(x)=0\) 的迭代法，记 \(x^*\) 为该方程的根

局部收敛定理：根邻域内选取 \(x_0\) 收敛

全局收敛定理：含根区间 \([a,b]\) 内选取 \(x_0\) 收敛

收敛速度：若 \(\lim\limits_{k\to\infty}\dfrac{|x^*-x_{k+1}|}{|x^*-x_k|^p}=c\ne 0\) 则称迭代序列 \(p\) 阶收敛；\(p=1\) 线性收敛；\(p>1\) 超线性收敛；\(p=2\) 二阶/平方收敛

收敛阶定理：\(\phi(x)\) 在不动点邻域内有连续的 \(p>1\) 阶导数，则迭代序列 \(p\) 阶收敛的充分必要条件是 \(\phi'(x^*)=\phi''(x^*)=\cdots=\phi^{(p-1)}(x^*)=0,\ \phi^{(p)}\ne 0\)

二分法

收敛速度慢

简单迭代法

修改为同解方程 \(x=\phi(x)\)，构造迭代格式 \(x_{k+1}=\phi(x_k)\)

收敛定理：\(\phi(x)\) 一阶连续可微且 \(x\in[a,b]\) 时 \(\phi(x)\in [a,b]\)；\(\exists\ 0<L<1, \ \mathrm{s.t.}\ \forall\ x\in[a,b]\ |\phi'(x)|\le L < 1\)

后验误差估计式：\(|x^*-x_k|\le\dfrac{1}{1-L}|x_{k+1}-x_k|\le\dfrac{L}{1-L}|x_{k}-x_{k-1}|\)

先验误差估计式：\(|x^*-x_k|\le\dfrac{L^k}{1-L}|x_{1}-x_0|\)

牛顿迭代法

迭代格式 \(x_{k+1}=x_k-\dfrac{f(x_k)}{f'(x_k)}\)

改进牛顿法 1：泰勒公式忽略三阶导得 \((x^*-x_k)\) 的二次方程，取近根作迭代格式

改进牛顿法 2：设反函数 \(g(y)\) 三阶连续可微，将其展开得迭代格式 \(x_{k+1}=x_k-\dfrac{f(x_k)}{f'(x_k)}-\dfrac{f''(x_k)}{2f'^3(x_k)}f^2(x_k)\)

简化牛顿法：将导数代换为常数

牛顿下山法：\(x_{k+1}=x_k-\lambda\dfrac{f(x_k)}{f'(x_k)}\)，试算下山因子 \(\lambda\) 使 \(|f(x_{k+1})|<|f(x_k)|\) 成立

局部收敛定理：二阶连续可微，\(f'(x)\ne 0\)

全局收敛定理：二阶连续可微且

  1. \(f(a)f(b)< 0\)
  2. \(f'(x)\ne 0,\ \forall\ x\in[a,b]\)
  3. \(f''(x)\) 不变号 \(,\ \forall\ x\in[a,b]\)
  4. \(x_0\in[a,b]\ \wedge\ f(x_0)f''(x_0)>0\)

由收敛定理及收敛阶定理得牛顿法二阶收敛

弦割法

两点弦割法：\(x_{k+1}=x_k-\dfrac{f(x_k)(x_k-x_{k-1})}{f(x_k)-f(x_{k-1})}\)，应用中改写避免相近数相减

单点弦割法：\(x_{k+1}=x_k-\dfrac{f(x_k)(x_k-x_{0})}{f(x_k)-f(x_{0})}\)

改进弦割法：作反函数的二次牛顿插值多项式

局部收敛定理：二阶连续可微，\(f'(x)\ne 0\)

全局收敛定理：在牛顿法全局收敛定理的条件下 \(f(x_1)f''(x_1)<0\)

收敛阶 \(p=\dfrac{1+\sqrt{5}}{2}\)

加速收敛技术

松弛加速法，应选取松弛因子 \(\omega\) 使 \(\psi'(x^*)=0\) \[ x_{k+1}=\psi(x_{k+1})=\frac{\phi(x_k)-\omega x_k}{1-\omega} \] 艾特肯加速法，由于 \(\dfrac{x^*-x_{k+1}}{x^*-x_k}\approx \dfrac{x^*-x_k}{x^*-x_{k-1}}\)

\[ \bar x_{k+1}=x_{k+1}-\frac{(x_{k+1}-x_k)^{2}}{x_{k+1}-2x_k+x_{k-1}} \]

非线性方程组迭代法

记 \(x=(x_1,x_2,\cdots,x_n)^{\mathrm T}\)，\(f(x)=(f_1(x),f_2(x),\cdots,f_n(x))^{\mathrm T}\)

简单迭代法（雅可比迭代法）：\(x^{(k+1)}=\phi(x^{(k)})\)

高斯-赛德尔迭代格式：\(x_i^{(k+1)}=\phi_i(x_1^{(k+1)},\cdots,x_{i-1}^{(k+1)},x_i^{(k)},\cdots,x_n^{(k)})\)

牛顿法：先求解关于 \(\Delta x^{(k)}\) 的方程组 \(J_f(x^{(k)})\Delta x^{(k)}=-f(x^{(k)})\)，再按下式计算

\[ \begin{cases} J(x^{(k)})\Delta x^{(k)}=-f(x^{(k)}),\\ x^{(k+1)}=x^{(k)}+\Delta x^{(k)}.\\ \end{cases} \]

全局收敛性定理：空间 \(D\subset R^n\)，\(\phi: D\to D\)，在闭区域 \(D_0\subset D\) 满足

  1. \(\phi(x)\subset D_0\)，\(\forall\ x \in D_0\)
  2. \(\exists\ 0 <L<1\)，\(\forall\ x, y\in D_0\)，\(\|\phi(x)-\phi(y)\|\le L\|x-y\|\)

局部收敛定理：设映射 \(\phi\) 有不动点 \(x^*\)，谱半径 \(\rho(J_\phi(x^*)) <1\)

弦割法：（略）

布洛依登法：使用矩阵 \(A_k\) 代替牛顿法雅可比矩阵得 \(x^{(k+1)}=x^{(k)}-A^{-1}f(x^{k})\)

常微分方程数值解法

一阶常微分方程初值问题

\[ \begin{cases} y'(x)=f(x,y(x)) &, a\le x\le b\\ y(a)=y_0. \end{cases} \] 解存在且唯一性定理（Lipschitz 条件）：\(f(x,y)\) 在区域 \(D=\{(x,y)|a\le x\le b, -\infty<y<\infty\}\) 且 \(\exists L\) 使 \[ |f(x,y)-f(x,\bar y)|\le \left|\frac{\partial f}{\partial y}(y-\bar y)\right|\le L|y-\bar y| \] 对任意 \(x,y,\bar y\) 均成立

高阶常微分方程化为一阶常微分方程组

\[ \begin{cases} y^{m}=f(x,y',y'',\cdots,y^{(m-1)}) &, a\le x\le b\\ y(a)=y_0,y'(a)=y_0',\cdots,y^{(m-1)}(a)=y_0^{(m-1)} \end{cases} \iff \begin{cases} y_1'=y_2 \newline y_2'=y_3 \newline \ \ \ \ \ \ \vdots \newline y_{m-1}'=y_m \newline y'_m=f(x,y_1,\cdots,y_m)\\ y_1(a)=y_0,y_2(a)=y_0',\cdots,y_m(a)=y_0^{(m-1)}. \end{cases} \]

\(p\) 阶方法：局部截断误差 \(R[f]=O(h^{p+1})\)

隐式法无法直接得迭代格式，则使用简单迭代法、牛顿法、改进欧拉法（预测-校正）得到格式

收敛性：格式 \(y=\phi(x,y,h)\) 关于 \(y\) 满足 Lipschitz 条件

绝对稳定性：每一步误差引起的后续误差缩小 \(|e_j|<|e_i|\)

绝对稳定区域：一般考察求解试验方程 \(y'=\lambda y\)，\(\mathrm{Re}(\lambda)<0\) 关于 \(\lambda,h\) 的稳定性

数值微分法

欧拉法（一阶） \[ y_{i+1}=y_i+hf(x_i,y_i) \] 局部截断误差 \(R[y]=\dfrac{h^2}{2}y''(\xi_i)\)

后退欧拉法（一阶） \[ y_{i+1}=y_i+hf(x_{i+1},y_{i+1}) \] 隐式法，写出格式后反解 \(y_{i+1}\)，局部截断误差 \(R[y]=-\dfrac{h^2}{2}y''(\xi_i)\)

中点法（二阶） \[ y_{i+1}=y_{i-1}+2hf(x_i,y_i) \] 局部截断误差 \(R[y]=-\dfrac{h^3}{3}y'''(\xi_i)\)

数值积分法

使用求积公式求解

梯形法（二阶） \[ y_{i+1}=y_{i}+\frac{h}{2}[f(x_i,y_i)+f(x_{i+1},y_{i+1})] \] 辛普森法（四阶） \[ y_{i+1}=y_{i-1}+\frac{h}{3}[f(x_{i-1},y_{i-1})+4f(x_i,y_i)+f(x_{i+1},y_{i+1})]-\frac{h^5}{90}y^{(5)}(\xi_i) \] 亚当斯显式法（设 \(k+1\) 个数据点，插值 \(f(x,y)=L_k(x)+R_k(x)\) 积分） \[ y_{i+1}=y_i+\frac{h}{A}(b_0f_i+b_1f_{i-1}+\cdots+b_kf_{i-k})+B_kh^{k+2}y^{(k+2)}(\xi_i) \] 亚当斯隐式法 \[ y_{i+1}=y_i+\frac{h}{A^*}(b_0^*f_{i+1}+b_1^*f_{i}+\cdots+b_k^*f_{i-k+1})+B_k^*h^{k+2}y^{(k+2)}(\xi_i) \] 经典四级四阶 R-K 法（将局部截断误差 \(R[y]=y(x_{i+1})-y_{i+1}\) 在 \(x_i\) 处泰勒展开）

\[ \begin{align} y_{i+1}&= y_i + \frac{1}{6}\left( K_1+2 K_2+2 K_3+ K_4\right) \nonumber\newline K_1&=h f\left(x_i, y_i\right) \nonumber\\ K_2&=h f\left(x_i+\frac{1}{2}h, y_i+\frac{1}{2} K_1\right) \nonumber\\ K_3&=h f\left(x_i+\frac{1}{2}h, y_i+\frac{1}{2} K_2\right) \nonumber\\ K_4&=h f\left(x_i+h, y_i+ K_3\right) \nonumber\newline \end{align} \]

边值问题数值解法

二阶常微分方程

\[ y''=f(x,y,y'),\ a < x < b \] 第一边值条件 \(y(a)=\alpha\)，\(y(b)=\beta\)

第二边值条件 \(y'(a)=\alpha\)，\(y'(b)=\beta\)

第三边值条件 \(y'(a)-\alpha_0y(a)=\alpha_1\)，\(y'(b)-\beta_0y(b)=\beta_1\)

有限差分法：区间 \([a,b]\) 划分为有限小区间使用数值微分法给出三对角方程组