数值分析赵熙乐老师（化）基础与前沿研究院谭兵-ZhiMap思维导图

谭兵

电子科技大学数值分析复习总结

数值分析
赵熙乐老师（化）
基础与前沿研究院
谭兵
进入思维导图模式
- 数据插值方法
  插值和拟合的异同
  1. 相同: 寻找离散数据背后的规律(函数)
  2. 严格满足插值条件 vs 追求最小残差平方和
  3. 适定方程组求解 vs 不相容方程组求解
  - 多项式插值的存在唯一性定理
    - $(n+1)$ 个互异的插值节点，满足插值条件的 $n$ 次多项式是存在且唯一的
  - 拉格朗日插值
    - $P(x) = {l_0}(x){y_0} + {l_1}(x){y_1} + {l_2}(x){y_2}$
    - 插值基函数： ${l_0}(x) = \frac{{(x - {x_1})(x - {x_2})}}{{({x_0} - {x_1})({x_0} - {x_2})}}$
    - 余项： $\frac{{{f^{(n + 1)}}(\xi )}}{{(n + 1)!}}(x - {x_0})(x - {x_1}) \cdots (x - {x_n})$
  - Runge现象
    - 高次多项式插值的震荡现象
  - 牛顿插值
    - $P(x) = {a_0} + {a_1}(x - {x_0}) + {a_2}(x - {x_0})(x - {x_1}){\rm{ + }} \cdots \\ + {a_n}(x - {x_0})(x - {x_1}) \cdots (x - {x_{n - 1}})$
    - 误差
      - $R_{n}(x)=f[x,x_0,x_1,\cdots,x_{n}]w_{n+1}(x)\\ =\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)$
  - 三次样条插值
    - 插值条件和函数连续条件 $2n$ 个
    - 节点处的一阶导数连续条件共有 $n-1$ 个
    - 节点处的二阶导数连续条件共有 $n-1$ 个
    - 自然边界条件： $S''(x_0)=0,S''(x_n)=0.$
- 非线性方程迭代法
  - 二分法
    - 中点 $x_n$ 满足 $|x_n-x^{*}|\le \frac{b-a}{2^{n+1}}$
  - 迭代框架
    - $f({x^*}) = 0 \Leftrightarrow {x^*} = \varphi ({x^*}) \Rightarrow {x_{n+1}} = \varphi ({x_{n}})$
  - 收敛性
    - $|\varphi '({x^*})| < 1$
    - $\mathop {\lim }\limits_{n \to \infty } |{x_n} - {x^*}| \le \mathop {\lim }\limits_{n \to \infty } {L^n}|{x_0} - {x^*}| = 0(0 < L < 1)$
    - 终止准则： $|{x^*} - {x_n}| \le \frac{L}{{1 - L}}|{x_n} - {x_{n - 1}}|$
  - 收敛速度
    - $\varphi '(x^*) = \varphi ''(x^*) = \cdots = {\varphi ^{(p - 1)}}(x^*) = 0,{\varphi ^{(p)}}(x^*) \ne 0 \quad p\text{阶收敛}$
  - Newton迭代法
    - 迭代格式
      - ${x_{n + 1}} = {x_n} - \frac{{f({x_n})}}{{f'({x_n})}}$
      - $\phi (x) = x - \frac{{f(x)}}{{f'(x)}}$ $\varphi (x) = x - \frac{{f(x)}}{{f'(x)}}$
    - 至少平方收敛
    - 牛顿下山法
      - ${x_{n + 1}} = {x_n} - m\frac{{f({x_n})}}{{f'({x_n})}}$
    - 弦截法
      - $x _ { k + 1 } = x _ { k } - \frac { f \left( x _ { k } \right) } { f \left( x _ { k } \right) - f \left( x _ { k - 1 } \right) } \left( x _ { k } - x _ { k - 1 } \right)$
- 最小二乘法拟合
  - $\mathop {\rm argmin }\limits_x \left\| {Ax - b} \right\|_2^2$
    - 正规方程： ${A^T}Ax = {A^T}b$
  - 拟合系数 $c_0,c_1,\cdots,c_n,y = {c_0} + {c_1}x + \cdots + {c_n}{x^n}$
  - 主特征向量（幂法）： $\bm{{x_n} = {A^n}{x_0}}$
  - 主特征值： $\bm {\lambda = {\dfrac{{x^T}Ax}{{x^T}x}}}$
  - 反幂法：计算 $\bm {A^{−1}}$ 的最大特征值可以得到 $\bm{A}$ 的最小特征值
    $\bm{A$
- 线性方程组的迭代法
  - Jacobi迭代法
    - $x = {D^{ - 1}}[(L + U)x + b]$
      - $B={D^{ - 1}}(L + U)$
  - G-S迭代法
    - $x = {(D - L)^{ - 1}}Ux + {(D - L)^{ - 1}}b$
      - $B = {(D - L)^{ - 1}}U$
  - 松弛技术
    - ${x^{(k + 1)}} = (1 - \omega ){x^k} + \omega {\bar x^{(k + 1)}}$
    - 松弛因子为1时迭代法是GS迭代法
  - 收敛性
    - $\rho (B){\rm{ = }}\mathop {\max }\limits_{1 \le k \le n} |{\lambda _k}|<1$ ，均收敛
    - ${\rm{||}}B{\rm{||}} < 1$ ，均收敛
    - $|{a_{ii}}| > \sum\limits_{\scriptstyle j = 1 \atop \scriptstyle j \ne i}^n {|{a_{ij}}|}$ ，均收敛
    - $A$ 对称正定，G-S收敛
    - 终止准则： $||{x^{(k)}} - {x^{\rm{*}}}|| \le \frac{{||B||}}{{1 - ||B||}}||{x^{(k)}} - {x^{(k - 1)}}||$
  - 初等变分原理
    - 设 $A$ 为实对称矩阵，则 $x$ 使得二次函数 $f(x)=\frac{1}{2}x^{T}Ax-b^{T}x$
      取极小值的充分必要条件是 $x$ 是线性方程组 $Ax=b$ 的解。
  - 最速下降法
    - $\boldsymbol { X } ^ { k + 1 } = \boldsymbol { X } ^ { k } - \frac { \left( \boldsymbol { g } ^ { k } \right) ^ { T } \boldsymbol { g } ^ { k } } { \left( \boldsymbol { g } ^ { k } \right) ^ { T } \boldsymbol { H } ^ { k } \boldsymbol { g } ^ { k } } \boldsymbol { g } ^ { k },\quad \boldsymbol { g } ^ { k }=\nabla f(x^{k})$
- 数值积分与数值微分
  - 插值型求积
    - 左（右、中）矩形积分公式
    - 梯形积分公式： $\int_{a}^{b} {f(x)dx} \approx \frac{{b - a}}{2}[f(a) + f(b)]$
    - Simpson积分公式： $\int_a^b {f(x)dx}=\frac{{b - a}}{6}[1f(a) + 4f(\frac{{a + b}}{2}) + 1f(b)]$
    - $n$ 阶牛顿-柯特斯积分公式： $\int_a^b {f(x)dx} \approx \sum\limits_{j = 0}^n {{A_j}f({x_j})} ,{A_j} = \int_a^b {{l_j}(x)dx}$
  - 高斯型求积
    - 积分节点可以自由选择： $\int_a^b {f(x)dx} \approx {A_0}f({x_0}) + \cdots + {A_n}f({x_n})$
    - 两点高斯-勒让德公式： $\int_{ - 1}^1 {f(x)dx} \approx f( - \frac{1}{{\sqrt 3 }}) + f(\frac{1}{{\sqrt 3 }})$
    - 三点高斯-勒让德公式： $\int_{ - 1}^1 {f(x)dx} \approx {\textstyle{5 \over 9}}f( -\sqrt{{\textstyle{3 \over 5}}} ) + {\textstyle{8 \over 9}}f(0) + {\textstyle{5 \over 9}}f({\sqrt {\textstyle{3 \over 5}}} )$
    - 注意：如果积分区间不是 $[-1,1]$ ，需要先对区间做变量替换！
  - $n$ 阶代数精度
    - 对多项式 $P(x)= 1,x, \cdots, x^n$ 积分公式
      都精确成立 $\int_a^b {P(x)dx} = \sum\limits_{j = 0}^n {{A_j}P({x_j})}$
  - 数值微分
    - 一阶向前（后）差分， $1$ 阶精度，两点中心差分： $2$ 阶精度
    - 松弛方法： $Q = (1 - \omega ){F_1} + \omega F_2$
- 求解线性
  方程组
  - 高斯消元法（LU分解，回代）
    - $A=LU=b,Ly=b;Ux=y$
    - 列主元消元法： $|a_{j1}|=\max \{|a_{11}|,|a_{21}|,\cdots,|a_{n1}|\}$
  - 直接三角分解法
    - Doolittle分解
      - 单位下三角矩阵，上三角矩阵
      - 更新顺序：先行后列
      - 列除行不除
      - 旧元素减去其所在行和列前 $k-1$ $\bm{k-1}$ 个元素
        的对应乘积然后求和
    - Crout分解
      - 下三角矩阵，单位上三角矩阵
      - 更新顺序：先列后行
      - 行除列不除
      - 旧元素减去其所在行和列前 $\bm{k-1}$ 个元素
        的对应乘积然后求和
  - 三对角矩阵的追赶法
    - LU分解
  - 条件数： $\text{cond}(A) = \|A \|\cdot\|A^{-1}\|$
  - 向量和矩阵范数
    - $\|\boldsymbol { X }\| _ { \infty } = \max _ { 1 \leq i \leq n } \left\{ |x _ { i } | \right\},$ ${\left\| A \right\|_\infty } = \mathop {\max }\limits_{1 \le i \le n} \,\,\sum\limits_{j = 1}^n {\left| {{a_{ij}}} \right|}$
    - $\| \boldsymbol { X } \| _ { 1 } = \sum _ { i = 1 } ^ { n } \left| \boldsymbol { x } _ { i } \right|,$ ${\left\| A \right\|_1} = \mathop {\max }\limits_{1 \le j \le n} \sum\limits_{i = 1}^n {\left| {{a_{ij}}} \right|}$
    - $\| \boldsymbol { X } \| _ { 2 } = \sqrt { { x } _ { 1 } ^ { 2 } + { x } _ { 2 } ^ { 2 } + \dots + { x } _ { n } ^ { 2 } },{\left\| A \right\|_2} = {({\lambda _{\max}}({A^T}A))^{{\textstyle{1 \over 2}}}}$
- 常微分方程数值解
  - 数值微分角度： $\frac{{y({x_{n + 1}}) - y({x_n})}}{h} \approx y'({x_n}) = f({x_n},y({x_n}))$
  - 数值积分角度： $\int_{{x_n}}^{{x_{n + 1}}} {y'(x)dx} = \int_{{x_n}}^{{x_{n + 1}}} {f(x,y(x))dx}$
  - Euler公式： ${y_{n + 1}} = {y_n} + hf({x_n},{y_n})$
  - 梯形公式： $y({x_{n + 1}}) - y({x_n}) = \frac{h}{2}[f({x_n},y({x_n})) + f({x_{n + 1}},y({x_{n + 1}}))]$
  - $\text{预报-校正方法(改进Euler公式)：}\\ \text{预报}\qquad \bm{{\tilde y}_{n + 1}} = {y_n} + hf({x_n},\;{y_n})\\ \text{校正}\qquad{y_{n + 1}} = {y_n} + \frac{h}{2}[f({x_n},{y_n}) + f({x_{n + 1}},{\bm{{\tilde y}_{n + 1}}})]$
  - 局部截断误差： $T_{n+1}=y(x_{n+1}) – y_{n+1}$ ，
    若局部截断误差为 $O(h^{p+1})$ ，则方法具有 $\bm{p}$ 阶精度

数值分析赵熙乐老师（化）基础与前沿研究院谭兵

​数据插值方法

​多项式插值的存在唯一性定理

​ (n+1)(n+1)(n+1) 个互异的插值节点，满足插值条件的 nnn 次多项式是存在且唯一的

​拉格朗日插值

​ P(x)=l0(x)y0+l1(x)y1+l2(x)y2P(x) = {l_0}(x){y_0} + {l_1}(x){y_1} + {l_2}(x){y_2}P(x)=l0​(x)y0​+l1​(x)y1​+l2​(x)y2​

​ 插值基函数：l0(x)=(x−x1)(x−x2)(x0−x1)(x0−x2){l_0}(x) = \frac{{(x - {x_1})(x - {x_2})}}{{({x_0} - {x_1})({x_0} - {x_2})}}l0​(x)=(x0​−x1​)(x0​−x2​)(x−x1​)(x−x2​)​

​余项： f(n+1)(ξ)(n+1)!(x−x0)(x−x1)⋯(x−xn)\frac{{{f^{(n + 1)}}(\xi )}}{{(n + 1)!}}(x - {x_0})(x - {x_1}) \cdots (x - {x_n})(n+1)!f(n+1)(ξ)​(x−x0​)(x−x1​)⋯(x−xn​)

​Runge现象

​高次多项式插值的震荡现象

​牛顿插值

​误差

​ Rn(x)=f[x,x0,x1,⋯ ,xn]wn+1(x)=f(n+1)(ξ)(n+1)!wn+1(x)R_{n}(x)=f[x,x_0,x_1,\cdots,x_{n}]w_{n+1}(x)\\ =\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)Rn​(x)=f[x,x0​,x1​,⋯,xn​]wn+1​(x)=(n+1)!f(n+1)(ξ)​wn+1​(x)

​三次样条插值

​插值条件和函数连续条件 2n2n2n 个

​节点处的一阶导数连续条件共有 n−1n-1n−1 个

​节点处的二阶导数连续条件共有 n−1n-1n−1 个

​自然边界条件： S′′(x0)=0,S′′(xn)=0.S''(x_0)=0,S''(x_n)=0.S′′(x0​)=0,S′′(xn​)=0.

​非线性方程迭代法

​二分法

​中点 xnx_nxn​ 满足 ∣xn−x∗∣≤b−a2n+1|x_n-x^{*}|\le \frac{b-a}{2^{n+1}}∣xn​−x∗∣≤2n+1b−a​

​迭代框架

f(x∗)=0⇔x∗=φ(x∗)⇒xn+1=φ(xn)f({x^*}) = 0 \Leftrightarrow {x^*} = \varphi ({x^*}) \Rightarrow {x_{n+1}} = \varphi ({x_{n}})f(x∗)=0⇔x∗=φ(x∗)⇒xn+1​=φ(xn​)

​收敛性

​ ∣φ′(x∗)∣<1|\varphi '({x^*})| < 1∣φ′(x∗)∣<1

lim⁡n→∞∣xn−x∗∣≤lim⁡n→∞Ln∣x0−x∗∣=0(0<L<1)\mathop {\lim }\limits_{n \to \infty } |{x_n} - {x^*}| \le \mathop {\lim }\limits_{n \to \infty } {L^n}|{x_0} - {x^*}| = 0(0 < L < 1)n→∞lim​∣xn​−x∗∣≤n→∞lim​Ln∣x0​−x∗∣=0(0<L<1)

​终止准则： ∣x∗−xn∣≤L1−L∣xn−xn−1∣|{x^*} - {x_n}| \le \frac{L}{{1 - L}}|{x_n} - {x_{n - 1}}|∣x∗−xn​∣≤1−LL​∣xn​−xn−1​∣

​收敛速度

​ φ′(x∗)=φ′′(x∗)=⋯=φ(p−1)(x∗)=0,φ(p)(x∗)̸=0p阶收敛\varphi '(x^*) = \varphi ''(x^*) = \cdots = {\varphi ^{(p - 1)}}(x^*) = 0,{\varphi ^{(p)}}(x^*) \ne 0 \quad p\text{阶收敛}φ′(x∗)=φ′′(x∗)=⋯=φ(p−1)(x∗)=0,φ(p)(x∗)̸=0p阶收敛

​Newton迭代法

​迭代格式

​ xn+1=xn−f(xn)f′(xn){x_{n + 1}} = {x_n} - \frac{{f({x_n})}}{{f'({x_n})}}xn+1​=xn​−f′(xn​)f(xn​)​

​ ϕ(x)=x−f(x)f′(x)\phi (x) = x - \frac{{f(x)}}{{f'(x)}}​ φ(x)=x−f(x)f′(x)\varphi (x) = x - \frac{{f(x)}}{{f'(x)}}φ(x)=x−f′(x)f(x)​

​至少平方收敛

​牛顿下山法

​ xn+1=xn−mf(xn)f′(xn){x_{n + 1}} = {x_n} - m\frac{{f({x_n})}}{{f'({x_n})}}xn+1​=xn​−mf′(xn​)f(xn​)​

​弦截法

​ xk+1=xk−f(xk)f(xk)−f(xk−1)(xk−xk−1)x _ { k + 1 } = x _ { k } - \frac { f \left( x _ { k } \right) } { f \left( x _ { k } \right) - f \left( x _ { k - 1 } \right) } \left( x _ { k } - x _ { k - 1 } \right)xk+1​=xk​−f(xk​)−f(xk−1​)f(xk​)​(xk​−xk−1​)

​最小二乘法拟合

​ argminx∥Ax−b∥22\mathop {\rm argmin }\limits_x \left\| {Ax - b} \right\|_2^2xargmin​∥Ax−b∥22​

​正规方程： ATAx=ATb{A^T}Ax = {A^T}bATAx=ATb

​拟合系数 c0,c1,⋯ ,cn,y=c0+c1x+⋯+cnxnc_0,c_1,\cdots,c_n,y = {c_0} + {c_1}x + \cdots + {c_n}{x^n}c0​,c1​,⋯,cn​,y=c0​+c1​x+⋯+cn​xn

​主特征向量（幂法）： xn=Anx0\bm{{x_n} = {A^n}{x_0}}xn​=Anx0​

​主特征值： λ=xTAxxTx\bm {\lambda = {\dfrac{{x^T}Ax}{{x^T}x}}}λ=xTxxTAx​

​反幂法：计算A−1\bm {A^{−1}}A−1 的最大特征值可以得到 A\bm{A}A 的最小特征值A\bm{A

​线性方程组的迭代法

​Jacobi迭代法

​ x=D−1[(L+U)x+b]x = {D^{ - 1}}[(L + U)x + b]x=D−1[(L+U)x+b]

​ B=D−1(L+U)B={D^{ - 1}}(L + U)B=D−1(L+U)

​G-S迭代法

​ x=(D−L)−1Ux+(D−L)−1bx = {(D - L)^{ - 1}}Ux + {(D - L)^{ - 1}}bx=(D−L)−1Ux+(D−L)−1b

​ B=(D−L)−1UB = {(D - L)^{ - 1}}UB=(D−L)−1U

​松弛技术

​ x(k+1)=(1−ω)xk+ωxˉ(k+1){x^{(k + 1)}} = (1 - \omega ){x^k} + \omega {\bar x^{(k + 1)}}x(k+1)=(1−ω)xk+ωxˉ(k+1)

​松弛因子为1时迭代法是GS迭代法

​收敛性

​ ρ(B)=max⁡1≤k≤n∣λk∣<1\rho (B){\rm{ = }}\mathop {\max }\limits_{1 \le k \le n} |{\lambda _k}|<1ρ(B)=1≤k≤nmax​∣λk​∣<1 ，均收敛

∣∣B∣∣<1{\rm{||}}B{\rm{||}} < 1∣∣B∣∣<1 ，均收敛

​ ∣aii∣>∑j=1j̸=in∣aij∣|{a_{ii}}| > \sum\limits_{\scriptstyle j = 1 \atop \scriptstyle j \ne i}^n {|{a_{ij}}|}∣aii​∣>j̸=ij=1​∑n​∣aij​∣，严格对角占优 ，均收敛

​ AAA 对称正定，G-S收敛

​终止准则： ∣∣x(k)−x∗∣∣≤∣∣B∣∣1−∣∣B∣∣∣∣x(k)−x(k−1)∣∣||{x^{(k)}} - {x^{\rm{*}}}|| \le \frac{{||B||}}{{1 - ||B||}}||{x^{(k)}} - {x^{(k - 1)}}||∣∣x(k)−x∗∣∣≤1−∣∣B∣∣∣∣B∣∣​∣∣x(k)−x(k−1)∣∣

​初等变分原理

​设 AAA 为实对称矩阵，则 xxx 使得二次函数 f(x)=12xTAx−bTxf(x)=\frac{1}{2}x^{T}Ax-b^{T}xf(x)=21​xTAx−bTx 取极小值的充分必要条件是 xxx 是线性方程组 Ax=bAx=bAx=b 的解。

​最速下降法

​数值积分与数值微分

​插值型求积

​左（右、中）矩形积分公式

​梯形积分公式： ∫abf(x)dx≈b−a2[f(a)+f(b)]\int_{a}^{b} {f(x)dx} \approx \frac{{b - a}}{2}[f(a) + f(b)]∫ab​f(x)dx≈2b−a​[f(a)+f(b)]

​Simpson积分公式： ∫abf(x)dx=b−a6[1f(a)+4f(a+b2)+1f(b)]\int_a^b {f(x)dx}=\frac{{b - a}}{6}[1f(a) + 4f(\frac{{a + b}}{2}) + 1f(b)]∫ab​f(x)dx=6b−a​[1f(a)+4f(2a+b​)+1f(b)]

​ nnn 阶牛顿-柯特斯积分公式： ∫abf(x)dx≈∑j=0nAjf(xj),Aj=∫ablj(x)dx\int_a^b {f(x)dx} \approx \sum\limits_{j = 0}^n {{A_j}f({x_j})} ,{A_j} = \int_a^b {{l_j}(x)dx}∫ab​f(x)dx≈j=0∑n​Aj​f(xj​),Aj​=∫ab​lj​(x)dx

​高斯型求积

​积分节点可以自由选择： ∫abf(x)dx≈A0f(x0)+⋯+Anf(xn)\int_a^b {f(x)dx} \approx {A_0}f({x_0}) + \cdots + {A_n}f({x_n})∫ab​f(x)dx≈A0​f(x0​)+⋯+An​f(xn​)

​两点高斯-勒让德公式： ∫−11f(x)dx≈f(−13)+f(13)\int_{ - 1}^1 {f(x)dx} \approx f( - \frac{1}{{\sqrt 3 }}) + f(\frac{1}{{\sqrt 3 }})∫−11​f(x)dx≈f(−3​1​)+f(3​1​)

​注意：如果积分区间不是 [−1,1][-1,1][−1,1] ，需要先对区间做变量替换！

nnn 阶代数精度

​对多项式 P(x)=1,x,⋯ ,xnP(x)= 1,x, \cdots, x^nP(x)=1,x,⋯,xn 积分公式都精确成立 ∫abP(x)dx=∑j=0nAjP(xj)\int_a^b {P(x)dx} = \sum\limits_{j = 0}^n {{A_j}P({x_j})}∫ab​P(x)dx=j=0∑n​Aj​P(xj​)

​数值微分

​一阶向前（后）差分， 111 阶精度，​两点中心差分： 222 阶精度

​松弛方法： Q=(1−ω)F1+ωF2Q = (1 - \omega ){F_1} + \omega F_2Q=(1−ω)F1​+ωF2​

​求解线性方程组

数值分析
赵熙乐老师（化）
基础与前沿研究院
谭兵

数据插值方法

多项式插值的存在唯一性定理

$(n+1)$ 个互异的插值节点，满足插值条件的 $n$ 次多项式是存在且唯一的

拉格朗日插值

$P(x) = {l_0}(x){y_0} + {l_1}(x){y_1} + {l_2}(x){y_2}$

插值基函数： ${l_0}(x) = \frac{{(x - {x_1})(x - {x_2})}}{{({x_0} - {x_1})({x_0} - {x_2})}}$

余项： $\frac{{{f^{(n + 1)}}(\xi )}}{{(n + 1)!}}(x - {x_0})(x - {x_1}) \cdots (x - {x_n})$

Runge现象

高次多项式插值的震荡现象

牛顿插值

误差

$R_{n}(x)=f[x,x_0,x_1,\cdots,x_{n}]w_{n+1}(x)\\ =\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)$

三次样条插值

插值条件和函数连续条件 $2n$ 个

节点处的一阶导数连续条件共有 $n-1$ 个

节点处的二阶导数连续条件共有 $n-1$ 个

自然边界条件： $S''(x_0)=0,S''(x_n)=0.$

非线性方程迭代法

二分法

中点 $x_n$ 满足 $|x_n-x^{*}|\le \frac{b-a}{2^{n+1}}$

迭代框架

$f({x^}) = 0 \Leftrightarrow {x^} = \varphi ({x^*}) \Rightarrow {x_{n+1}} = \varphi ({x_{n}})$

收敛性

$|\varphi '({x^*})| < 1$

$\mathop {\lim }\limits_{n \to \infty } |{x_n} - {x^}| \le \mathop {\lim }\limits_{n \to \infty } {L^n}|{x_0} - {x^}| = 0(0 < L < 1)$

终止准则： $|{x^*} - {x_n}| \le \frac{L}{{1 - L}}|{x_n} - {x_{n - 1}}|$

收敛速度

$\varphi '(x^) = \varphi ''(x^) = \cdots = {\varphi ^{(p - 1)}}(x^) = 0,{\varphi ^{(p)}}(x^) \ne 0 \quad p\text{阶收敛}$

Newton迭代法

迭代格式

${x_{n + 1}} = {x_n} - \frac{{f({x_n})}}{{f'({x_n})}}$

$\phi (x) = x - \frac{{f(x)}}{{f'(x)}}$ $\varphi (x) = x - \frac{{f(x)}}{{f'(x)}}$

至少平方收敛

牛顿下山法

${x_{n + 1}} = {x_n} - m\frac{{f({x_n})}}{{f'({x_n})}}$

弦截法

$x _ { k + 1 } = x _ { k } - \frac { f \left( x _ { k } \right) } { f \left( x _ { k } \right) - f \left( x _ { k - 1 } \right) } \left( x _ { k } - x _ { k - 1 } \right)$

最小二乘法拟合

$\mathop {\rm argmin }\limits_x \left\| {Ax - b} \right\|_2^2$

正规方程： ${A^T}Ax = {A^T}b$

拟合系数 $c_0,c_1,\cdots,c_n,y = {c_0} + {c_1}x + \cdots + {c_n}{x^n}$

主特征向量（幂法）： $\bm{{x_n} = {A^n}{x_0}}$

主特征值： $\bm {\lambda = {\dfrac{{x^T}Ax}{{x^T}x}}}$

反幂法：计算 $\bm {A^{−1}}$ 的最大特征值可以得到 $\bm{A}$ 的最小特征值
$\bm{A$

线性方程组的迭代法

Jacobi迭代法

$x = {D^{ - 1}}[(L + U)x + b]$

$B={D^{ - 1}}(L + U)$

G-S迭代法

$x = {(D - L)^{ - 1}}Ux + {(D - L)^{ - 1}}b$

$B = {(D - L)^{ - 1}}U$

松弛技术

${x^{(k + 1)}} = (1 - \omega ){x^k} + \omega {\bar x^{(k + 1)}}$

松弛因子为1时迭代法是GS迭代法

收敛性

$\rho (B){\rm{ = }}\mathop {\max }\limits_{1 \le k \le n} |{\lambda _k}|<1$ ，均收敛

${\rm{||}}B{\rm{||}} < 1$ ，均收敛

$|{a_{ii}}| > \sum\limits_{\scriptstyle j = 1 \atop \scriptstyle j \ne i}^n {|{a_{ij}}|}$ ，均收敛

$A$ 对称正定，G-S收敛

终止准则： $||{x^{(k)}} - {x^{\rm{*}}}|| \le \frac{{||B||}}{{1 - ||B||}}||{x^{(k)}} - {x^{(k - 1)}}||$

初等变分原理

设 $A$ 为实对称矩阵，则 $x$ 使得二次函数 $f(x)=\frac{1}{2}x^{T}Ax-b^{T}x$
取极小值的充分必要条件是 $x$ 是线性方程组 $Ax=b$ 的解。

最速下降法

数值积分与数值微分

插值型求积

左（右、中）矩形积分公式

梯形积分公式： $\int_{a}^{b} {f(x)dx} \approx \frac{{b - a}}{2}[f(a) + f(b)]$

Simpson积分公式： $\int_a^b {f(x)dx}=\frac{{b - a}}{6}[1f(a) + 4f(\frac{{a + b}}{2}) + 1f(b)]$

$n$ 阶牛顿-柯特斯积分公式： $\int_a^b {f(x)dx} \approx \sum\limits_{j = 0}^n {{A_j}f({x_j})} ,{A_j} = \int_a^b {{l_j}(x)dx}$

高斯型求积

积分节点可以自由选择： $\int_a^b {f(x)dx} \approx {A_0}f({x_0}) + \cdots + {A_n}f({x_n})$

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

注意：如果积分区间不是 $[-1,1]$ ，需要先对区间做变量替换！

$n$ 阶代数精度

对多项式 $P(x)= 1,x, \cdots, x^n$ 积分公式
都精确成立 $\int_a^b {P(x)dx} = \sum\limits_{j = 0}^n {{A_j}P({x_j})}$

数值微分

一阶向前（后）差分， $1$ 阶精度，两点中心差分： $2$ 阶精度

松弛方法： $Q = (1 - \omega ){F_1} + \omega F_2$

求解线性
方程组