数值分析.md

Chapter 2

不动点法

收敛的充分条件：[a,b]内所有x满足|g'(x)| < k, (0 < k < 1)

收敛速度: $ |p_{n+1} - p{n}| <= k * |p_n - p{n-1}|$ , k越小越快

牛顿法

用泰勒展开的前两项作为函数近似，求该近似函数的零点，在零点处再求函数近似，迭代。

$ p \approx p_0 - \frac{f(p_0)}{f'(p_0)} $

牛顿法的k在p点处是0，所以收敛非常快

迭代法误差分析

$ lim \frac{p_{n+1} - p}{|p_n - p|^a} = \lambda $

pn收敛于p, a越大，收敛速度越快

a = 1, linearly convergent

a = 2, quadratically convergent

$ g'(p) \neq 0$ 则最少是 linear convergent，拉格朗日中值定理可退

$ g'(p) = 0$ 时（如牛顿法） g不等于0的最高阶导数阶数a

牛顿法是二阶收敛的

quadratica newtom method

有重根（几重根都可以）的时候令 $ \mu(x) = \frac{f(x)}{f'(x)} $

然后再做牛顿法 $ g(x) = x - \frac{\mu(x)}{\mu'(x)} $

Aitken's Method (Steffensen’s Method)

原理：$ p_{n+2} = p_n - \frac{( \Delta p_n )^2}{ \Delta ^ 2 p_n }$

$ p_1 = g(p_0) $

$ p_2 = g(p_1) $

$ p = p_0 - \frac{( p_1 - p_0 )^2}{ ( p_2 - 2 p_1 + p_0 ) }$

$ p_0 = p $

Chapter 6

LU 分解

如果矩阵不需要行交换就能高斯消元成上三角矩阵则可以LU分解（中间有0的话LU分解会没法进行）

复杂度$ n^3 / 3$

1. L对角线为1， U对角线为原始元素
2. 1. 算U的第i行
   2. 算L的第i列
   3. goto 1

Pivoting Strategies

每次找一列中最大的元素，把最大元素所在的行交换到当前行

Complete Pivoting

到第i行时的时候在i右下角的矩阵里找最大的元素，然后通过交换行、交换列，换到$a_{ii}$

Strictly Diagonally Dominant Matrix

对角线上的元素严格大于此行其他元素之和

LU factorization of a positive define Matrix

正定矩阵可以分解成$ L * L^t$ 的形式，L是下三角的L加上对角线替换为根号对角线

Crout Reduction of Tridiagonal LInear System

1. 先LU分解, $LUx = f$ 分步求解, 设$y = Ux$
2. $Ly = f$
3. $Ux = y $

Chapter 7

Norms 范数:

定义：满足三个条件

1. 正定性
2. 同质性
3. 满足三角不等式

一阶范数：绝对值之和

二阶范数：欧拉距离

无穷范数：最大的元素绝对值

负无穷范数：最小的元素绝对值

在某范数下收敛于x即与x的差的范数一致小于$\epsilon$

实空间里所有范数等价（在任意范数下收敛则所有范数下收敛）

Natural Norm

无穷范数：元素绝对值每一行的和的最大值

第一范数：元素绝对值每一列的和的最大值

第二范数：$\sqrt{\lambda_{max}(A^TA)}$ 即$A^TA$这个矩阵最大的特征值的平方根，也就是谱半径，对于方阵来说就是特征值绝对值的最大值

Spectral Radius

$\rho(A) = max|\lambda| \leq ||A||$

谱半径等于特征值绝对值的最大值，小于等于列元素绝对值和的最大值

$|\lambda|\cdot||x|| = ||\lambda x|| = ||Ax|| \leq ||A||\cdot ||x||$

Jacobi Iterative Method

$Ax = b$

把A分为D, -L, -U三个矩阵相加

$(D - L - U)x = b$

$Dx = (L +U)x + b$

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

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

$C = D^{-1}b$

$x = Tx + c$

具体计算：

$ X_i = \frac{b_i - \sum_{j=1,j\neq i}^n{(a_{ij}X0_j)}}{a_{ii}}$

Gauss - Seidel Iterative Method

不储存X0，每次直接用更新完的计算$X_{i+1}$

Convergency of Iterative Methods

: The following statements are equivalent:

(1) A is a convergent matrix;

(2) $ lim_{n\to\infty} ||A^n|| = 0$ for some natural norm;

(3) $ lim_{n\to\infty}||A^n|| = 0$ for all natural norms;

(4) ☆ $\rho(A) &lt; 1$; 常用

(5) $ lim_{n\to\infty} A^nx = 0$

error bounds:

$||x - x_k|| \approx \rho (T)^k ||x - x_0||$

T是Jaccobi的T

Relaxation Methods

$X_ i^k = X_i^{k-1} - \omega(\frac{r_i^k}{a_{ii}})$

$r_i^k = b_i - \sum_{j&lt;i}{a_{ij}x_j^k} - \sum_{j\ge i}{a_{ij}x_j^{k-1}} $

$\omega = 1$时即为 Gauss - Seidel Iterative Method

$T = I + \omega A$

Chapter 3

拉格朗日基：

第i个基在第i个插值点为1，其他插值点为0

$L_{}n,i(x)= \prod_{j = 0, j \neq i}^n \frac{x - x_j}{x_i -x_j} $

n是次数，从0开始

$P_n(x) = \sum {L_{n,i}(x) y_i}$

Rolle's Theorem:

n个零点所在的区间里必有一个点的n-1阶导数为0

Remainder

$ R(x) = f(x) - P_n(x) $

$ g(t) = R(t) - K(x) \prod (t - x_i) $ 这个x是不等于xi的任意固定值

根据Rolle's Theorem存在一个$\zeta_x$满足$g^{(n+1)}(\zeta_x)=0$ ，带入上述两式，又因为$P^{(n+1)}(\zeta_x)= 0$，推出

☆ $R_n(x) = \frac{f^{(n+1)(\zeta_x)}}{(n+1)!}\prod_{i=0}^n(x - x_i)$

但是$\zeta_x$不一定能求得，常用 $f^{(n+1)}(\zeta_x)$ 的一个上界来估算 $R_n(x)$

Chapter 7

Condition number

$||A||\cdot ||A^{-1}||$ is the key factor of error amplification, and is called the condition number K(A). K(A)越大越难获得精确解

$A(x+dx) = b + db$

$\frac{||\delta x||}{||x||} \leq K(A) \cdot \frac{||\delta b||}{||b||} $

Refinement

1. $Ax = b$
2. $r = b - Ax$
3. $Ad = r$
4. $x = x + d$

Chapter 9

Power method

$x^k = Ax^{k-1}$

相当于把一个随机向量塞到面团里，然后拉拉面，最后这个向量会跟拉面平行，即最大特征值对应的特征向量方向

要求只能由一个最大特征值，不能有相等的

$\lambda \approx \frac{x_i^k}{x_i^{k-1}}$

Normalization

1. $ u^{k-1} = \frac{x^{k-1}}{|x^k-1|}$
2. $x^{k} = Au^{k-1}$
3. $\lambda = max(x^k_i)$

Rate of Convergence

收敛速率是$|\lambda 2 / \lambda 1|$，更快的收敛速率要尽量让$\lambda 2$小，调整原点位置到$(\lambda 2 + \lambda n) / 2$ 可以再不产生新的$\lambda2$的情况下让$\lambda 2 $最小

Inverse Power Method

可以求得绝对值最小的特征值

求$p_0$附近的特征值：

1. $B= A- p_0 I$
2. $x^k = B^{-1}x^{k-1}$
3. $\frac 1 \lambda = x^k / x^{k-1}$

Chapter 3

一般内插比外插要准确

拉格朗日插值如果新增加一个插值点需要全部重算

下面两种方法都更方便于添加插值点

Neville's Method:

用两个同阶的p合并可以得到更高阶的p

$p_{1,2,3,4}(x) = \frac{(x -x_4)p_{1,2,3} - (x - x_1)p_{2,3,4}}{x_1 - x_4}$

Newton's Interpolation

$ f[x, x_0… x_{n-1}] = f[x_ 0 … x_n] + (x - x_n)f[x, x_0 ... x_n] $

Hermite Interpolation

插值满足在n个点出给出的值和m个点处给出的斜率

$ H(x) = \sum_{i=0}^n f(x_i)h_i(x) + \sum_{i=0}^{m}f'(x_i)\hat h_i(x)$

where $h_i(x_i) = (i == j)$, $h'_i(x_j) = 0$, $\hat h_i(x_j) = 0$, $\hat h'_j(x_j) = (i == j) $

Cubic Spline Interpolation

解决了随着插值点的增多插值函数并不收敛于原函数的问题

方法是用子区间三阶插值来拟合原函数