数值分析final 木灵的炼金工作室

久远妈妈!(不是

以下是总复习的记录:

误差

  1. 有效数字:若$x^$的绝对误差小于 $x^$ 某一位上数字的半个单位,且该位直到 $x^$ 的首个非零数字一共有 $n$ 位数字,则称近似值 $x^$ 有 $n$ 位有效数字.
\[\vert x - x^* \vert \leqslant \frac{1}{2} \times 10^{-m} \tag{1}\]
  1. *不借助误差(由于真实值实际上不可知)的有效数字估测手段

若以$c$进制表示的估计值$x^*$的相对误差限可以取到:

\[\epsilon_r(x^*) = \frac{1}{2(a_1+1)}\times c^{-n+1}\tag{2}\]

那么$x^*$至少具有$n$位有效数字

  1. 复合量$c^=f(x_1^,x_2^,x_3^,…,x_n^*)$中,每一个分量的相对误差贡献是
\[e_i=\frac{\partial f}{\partial x_i}e(x_i^*)\tag{3}\]
  1. 减小误差的数个方法 i. 避免两个相近的数相减 ii. 优先计算较小数 iii. 避免小数除大数 iv. 简化运算次数

Gauss消元法衍生的若干矩阵分解法

  1. Doolittle分解:
\[LU = A\tag{4}\]

$L$是一个单位下三角矩阵,用于记录Gauss消元的过程. $U$是不归一化的Gauss消元的结果.

算法,分解:

\[a_{ij} = \sum_{k = 1}^{n}l_{ik}u_{kj}\tag{5}\]

算法,解方程:

\[\left\{ \begin{aligned} Ly = b\\ Ux = y \end{aligned} \right.\tag{6}\]
  1. Cholesky分解,正定二次型:
\[A = CC^T \tag{7}\]

$C$是一个下三角矩阵.

算法完全同上.

  1. 改进的平方根法,LDP分解,避免上述算法中的开平方运算:
\[A = LDP = LDL^T \tag{8}\]

$D$是对角阵. 首先将$LD$组合为一个新的矩阵$U$行Doolittie分解,再提取$P$的对角元.

解:

\[Ax = b\] \[LDL^Tx=b\] \[Ly = b, L^Tx=D^{-1}b\]

赋范空间

  1. 范数之性质
    1. $\Vert x\Vert=0$当且仅当$x=0$(正定性)
    2. $\forall x \in \mathbb{D}, \alpha \in \mathbb{R}, \Vert\alpha x \Vert=\vert\alpha\vert \Vert x \Vert$(绝对齐次性)
    3. $\forall x,y \in \mathbb{D}, \Vert x + y \Vert \leqslant \Vert x \Vert + \Vert y \Vert$(三角不等式)
  2. 向量范数之定义
    1. 1-范数:距离总和
    2. 2-范数:方和根
    3. $\infin$-范数:最远值
  3. 矩阵范数:(相容性$\Vert AB \Vert \leqslant \Vert A \Vert\Vert B \Vert$)
    1. 1-范数:最大的列距离总和
    2. 2-范数:$A^TA$的最大特征值之方根
    3. $\infin$-范数:最大的行距离总和
  4. 条件数:
\[cond(A) = \Vert A^{-1} \Vert\Vert A \Vert\]

线性方程组数值解法

  1. Jacobi迭代法:
\[\left\{ \begin{aligned} &a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + ... + a_{1n}x_n=b_1\\ &a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + ... + a_{2n}x_n=b_2\\ &a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + ... + a_{3n}x_n=b_3\\ &...\\ &a_{n1}x_1 + a_{n2}x_2 + a_{n3}x_3 + ... + a_{nn}x_n=b_n\\ \end{aligned} \right.\]

移项:第$i$个方程左边只留下$x_i$:

\[\left\{ \begin{aligned} &x_1 = (b_1-a_{12}x_2 - a_{13}x_3 - ... + a_{1n}x_n)/a_{11}\\ &x_2 = (b_2-a_{21}x_1 - a_{23}x_3 - ... + a_{2n}x_n)/a_{22}\\ &x_3 = (b_3-a_{31}x_1 - a_{32}x_2 - ... + a_{3n}x_n)/a_{33}\\ &...\\ &x_n = (b_n-a_{n1}x_1 - a_{n2}x_3 - ... + a_{n,n-1}x_{n-1})/a_{nn}\\ \end{aligned} \right.\]

上式可以转写为$x = Mx+g$,其中

\[g = (b_1/a_{11}, b_2/a_{22}, ..., b_i/a_{ii}, ..., b_n/a_{nn})^T\] \[M = \begin{pmatrix} 0&-a_{12}/a_{11}& ... & -a{ij}/a_{ii} &... & -a{1n} / a_{11}\\ -a_{21}/a_{22}&0& ... & -a{ij}/a_{ii} &... & -a{2n} / a_{22}\\ -a_{31}/a_{33}&-a{32}/a_{33}& ... & -a{ij}/a_{ii} &... & -a{2n} / a_{22}\\ \vdots&\vdots&-a{ij}/a_{ii}&\vdots& &\vdots\\ -a_{n1}/a_{nn}&-a{n2}/a_{nn}& ... & -a{ij}/a_{ii} &... & 0\\ \end{pmatrix}\]

易知$x = Mx+g$与$Ax=b$同解.

  1. Gauss-Seidel迭代法

拆分Jacobi迭代法的$M$矩阵为$LU$,$L$下三角矩阵,$U$上三角矩阵

\[x^{(k+1)} = Lx^{(k+1)}+Ux^{(k)}+g\]
  1. 迭代法收敛的判断:若$M$的任意范数$\Vert M\Vert < 1$,则收敛;若方阵是严格对角占优阵或者不可约的弱对角占优阵,则Jacobi和G-S必收敛

特征值

  1. 幂法:
\[x^{(k+1)} = Ax^{(k)}\]

每一步应对$x$行最远值归一化处理,后取任意对应分量作比即得特征值

函数插值法

  1. Lagrange法:
\[f(x) = \sum_{i = 0}^n y_il_i(x)\] \[{l_i(x), i\in [0,n]}, s.t:l_i(x) = \frac{\prod_{j=0, j\not ={i}}^n(x-x_j)}{\prod_{j=0, j\not ={i}}^n(x_i-x_j)}\]

要轮换的项目永远在负号的一侧.

截断误差:

\[K(x) = \frac{f^{n+1}(\xi)}{(n+1)!}, \xi \in (a,b)\]
  1. Newton法:

差商:

  1. $f[a, b] = \frac{f(a) - f(b)}{a-b}$
  2. $f[a, a_1, …, b_1, b] = \frac{f[a,…,b_1]-f[a_1,…,b]}{a-b}$,”$…$”可以为空且$a_1, b_1$可以相同(即本式支持三个及以上项目)
\[f^*(x) = \sum_{i=0}^n l_i(x)\] \[l_i(x) = f[x_0\ to.\ x_i]\prod_{j=0}^{i-1}(x-x_j)\]

截断误差:

\[K(x) = \frac{f^{n+1}(\xi)}{(n+1)!}, \xi \in (a,b)\]

记得有等距节点这回事儿就行了

\[f^*(x) = f(x_0)+\frac{\Delta_{1,0}^1f}{1!h^1}(x-x_0)+\frac{\Delta_{2,0}^2f}{2!h^2}(x-x_0)(x-x_1)+\frac{\Delta_{3,0}^3f}{3!h^3}(x-x_0)(x-x_1)(x-x_2)+...\]
  1. Hermite插值

基法:

\[H(x) = \sum_{i=0}^n \{y_i[1-2l'_i(x_i)(x-x_i)]l_i^2(x)+y_i'(x-x_i)l_i^2(x)\}\]

降阶法:

\[H(x)-N(x) = P(x)\prod_{i=0}^n(x-x_i)\]

$N(x)$为仅维持原值的插值多项式

函数逼近

  1. 最小二乘法
\[MA=b\] \[M = \begin{pmatrix} \sum_{(x,y)\in P}1&\sum_{(x,y)\in P}x&\sum_{(x,y)\in P}x^2 & ... & \sum_{(x,y)\in P}x^n\\ \sum_{(x,y)\in P}x&\sum_{(x,y)\in P}x^2&\sum_{(x,y)\in P}x^3 & ... & \sum_{(x,y)\in P}x^{n+1}\\ \vdots & \vdots& \vdots &&\vdots \\ \sum_{(x,y)\in P}x^k&\sum_{(x,y)\in P}x^{k+1}&\sum_{(x,y)\in P}x^{k+2} & ... & \sum_{(x,y)\in P}x^{k+n}\\ \vdots & \vdots& \vdots &&\vdots \\ \sum_{(x,y)\in P}x^n&\sum_{(x,y)\in P}x^{n+1}&\sum_{(x,y)\in P}x^{n+2} & ... & \sum_{(x,y)\in P}x^{2n}\\ \end{pmatrix}\] \[b = \begin{pmatrix} \sum_{(x,y)\in P}y\\ \sum_{(x,y)\in P}xy\\ ...\\ \sum_{(x,y)\in P}x^ky\\ ...\\ \sum_{(x,y)\in P}x^ny \end{pmatrix}\]

数值微分

  1. 一次
\[f'^*(x_0) = \frac{f(x_1)-f(x_0)}{x_1-x_0}\]
  1. 二次

    1. $x=x_0$,$\phi’(x)=\frac{1}{2h}[-3f(x_0)+4f(x_1)-f(x_2)]$
    2. $x=x_1$,$\phi’(x)=\frac{1}{2h}[-f(x_0)+f(x_2)]$,中心差商公式
    3. $x=x_2$,$\phi’(x)=\frac{1}{2h}[f(x_0)-4f(x_1)+3f(x_2)]$

数值积分

  1. Newton-Cotes积分法

    1. $\int_b^af(x)dx\approx\frac{a-b}{2}[f(a)+f(b)]$,二次方区间长度误差
    2. $\int_b^af(x)dx\approx\frac{1}{6}[f(b)+4f(\frac{a+b}{2})+f(a)(a-b)$,四次方区间长度误差
  2. 代数精度

  3. 复化积分,逐次分半算法


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn