非线性方程数值解法_计算方法

0 绪论

1 非线性方程数值解法

1.1 二分法

使用的条件

1. 区间首尾异号
2. 区间内连续
3. 仅有一个根

步骤

先判断是否满足使用的条件，再使用
误差限的计算

1.2 迭代法

单点迭代法

将 $f(x)=0$f(x)=0 改写成 $x=\phi(x)$x=ϕ(x)，
建立迭代公式 $x_{k+1}=\phi(x_k)$xk+1​=ϕ(xk​)，
在根附近任取一点$x_0$x0​，若得到的序列收敛于$\alpha$α且$\phi(x)$ϕ(x)连续

多点迭代法

$x_{k+1}=\phi(x_{k-n+1}, ..., x_{k-2}, x_{k-1}, x_k)$xk+1​=ϕ(xk−n+1​,...,xk−2​,xk−1​,xk​)

迭代法的收敛性

全局收敛性：设$\alpha$α为$f(x)=0$f(x)=0的根，如果$\forall x_0 \in [a, b]$∀x0​∈[a,b] ，由迭代法产生的序列都收敛于根$\alpha$α， 则称该迭代法是全局收敛的；
局部收敛性：设方程$x=\phi(x)$x=ϕ(x)有根$α$α, 如果存在$α$α的某个邻域$\Delta: |x-\alpha| < \delta$Δ:∣x−α∣<δ，对任意初值$x_0 \in \Delta$x0​∈Δ，迭代过程所产生的序列均收敛于根$α$α，则称该迭代法是局部收敛的。

迭代过程的收敛速度

$Def.$Def. 记$e_k=\alpha-x_k$ek​=α−xk​，若$\displaystyle \lim_{k \to \infty}\frac{|e_{k+1}|}{|e_k|^p}=C\neq0$k→∞lim​∣ek​∣p∣ek+1​∣​=C​=0，则称迭代过程是p阶收敛的；
特别地，当p=1时，称为线性收敛;
当p>1时，称为超线性收敛，
当p=2时，称为平方收敛.

迭代过程的效率指数

$Def.$Def.$EI=p^{1 \over \theta}$EI=pθ1​
为效率指数. 其中$p$p表示迭代的收敛阶，$\theta$θ表示每步迭代的计算量.
$EI$EI越大，计算效率越高.

1.2.1 不动点迭代法

Th1.1 设$\phi(x)$ϕ(x)满足：
1）当$x\in[a, b]$x∈[a,b]时，$\phi(x)\in[a, b]$ϕ(x)∈[a,b]；
2）$\forall x_1, x_2 \in [a, b]$∀x1​,x2​∈[a,b]，有$|\phi(x_1)-\phi(x_2)| \leq L|x_1-x_2|,L<1$∣ϕ(x1​)−ϕ(x2​)∣≤L∣x1​−x2​∣,L<1，
则对任意初值$x_0\in[a,b]$x0​∈[a,b]，迭代过程$x_{k+1}=\phi(x_k)$xk+1​=ϕ(xk​)收敛于$x=\phi(x)$x=ϕ(x)在$[a, b]$[a,b]上的唯一根 ，且有误差估计式：$|\alpha-x_k|\leq \frac L {1-L}|x_k-x_{k-1}|$∣α−xk​∣≤1−LL​∣xk​−xk−1​∣$|\alpha-x_k|\leq \frac {L^k} {1-L}|x_1-x_0|$∣α−xk​∣≤1−LLk​∣x1​−x0​∣

Th1.2 设$\phi(x)$ϕ(x)在$[a,b]$[a,b]上具有一阶导数，且
1）当$x\in [a,b]$x∈[a,b]时，有$\phi(x)\in[a,b]$ϕ(x)∈[a,b]；
2）$\forall x \in [a,b]$∀x∈[a,b]，有$|\phi'(x)| \leq L < 1$∣ϕ′(x)∣≤L<1，
则对任意初值$x_0\in[a,b]$x0​∈[a,b]，迭代过程$x_{k+1}=\phi(x_k)$xk+1​=ϕ(xk​)收敛于$x=\phi(x)$x=ϕ(x)在$[a, b]$[a,b]上的唯一根。

Th1.3 若$\phi(x)$ϕ(x)在方程$x=\phi(x)$x=ϕ(x)的根$\alpha$α的邻域内有一阶连续的导数，且$|\phi'(x)| < 1$∣ϕ′(x)∣<1，则迭代过程$x_{k+1}=\phi(x_k)$xk+1​=ϕ(xk​)具有局部收敛性。

Th1.4 若$\phi(x)$ϕ(x)在方程$x=\phi(x)$x=ϕ(x)的根$\alpha$α的邻域内有充分阶连续的导数，则迭代过程$x_{k+1}=\phi(x_k)$xk+1​=ϕ(xk​)在$\alpha$α的邻域是$p$p阶收敛的充要条件是$\phi^{(j)}(\alpha)=0, \quad j=1,2,...,p-1$ϕ(j)(α)=0,j=1,2,...,p−1$\phi^{(p)}(\alpha) \neq 0$ϕ(p)(α)​=0

1.2.2 牛顿迭代法

设有方程$f(x)=0$f(x)=0，在$f(x)=0$f(x)=0的根$α$α附近任取一点$x_0$x0​作为初始近似根，由迭代公式$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} \quad (k=0,1,2...)$xk+1​=xk​−f′(xk​)f(xk​)​(k=0,1,2...)逐次逼近方程$f(x)=0$f(x)=0的根$α$α，这种求根算法称为Newton法（切线法）。

局部收敛性：
$Th$Th Newton法的迭代函数是$\phi(x)=x-\frac{f(x)}{f'(x)}$ϕ(x)=x−f′(x)f(x)​，
若$\alpha$α是$f(x)=0$f(x)=0的一个单根，则在根α附近Newton法是局部二阶收敛的,即 $p=2$p=2；
若$\alpha$α是$f(x)=0$f(x)=0的一个重根，则在根α附近Newton法是局部线性收敛的,即 $p=1$p=1。

全局收敛性：
$Th1.5$Th1.5 设$f(x)$f(x)在有根区间$[a, b]$[a,b]上二阶导数存在，且满足：
1）$f(a)f(b)<0$f(a)f(b)<0；
2）$f'(x) \neq 0,\quad x \in [a,b]$f′(x)​=0,x∈[a,b]；
3）$f''(x)$f′′(x)不变号$,\quad x \in [a,b]$,x∈[a,b]；
4）初值$x_0 \in [a,b]$x0​∈[a,b]且使$f''(x_0)f(x_0)>0$f′′(x0​)f(x0​)>0，
则 Newton迭代法收敛于$f(x)=0$f(x)=0在$[a, b]$[a,b]内的唯一根。

简化Newton迭代法
Newton下山法

1.2.3 弦截法

线性方程数值解法