非线性方程的数值解法

划界法

• 方程的根

使用如下条件判断重根

设函数f(x)有m阶连续导数，方程f(x)=0有m重根x^*的充要条件是

$$f(x^*) = f'(x^*) = \cdots = f^{(m-1)}(x^*) = 0, \quad f^{(m)}(x^*) \neq 0$$

逐步搜索法

设单值连续函数f(x)在有根区间[a,b]，不妨假定f(a)<0，从x₀=a出发，按预定步长h（譬如取h=(b-a)/N，N为正整数），检查点x_k=a+kh，k=1,2,…上的函数值f(x_k)的符号，一旦发现x_k处与a处函数值异号，即f(x_k)>0，则可确定一个缩小了的有根区间[x_k-1,x_k]，其宽度等于预定的步长h。可能有f(x_k)=0，这时x_k即为所求的根

二分法

将有根区间[a,b]用中点x₀=(a+b)/2分成两半，计算函数值f((a+b)/2)。若f((a+b)/2)=0，就得到方程的实根x^*=(a+b)/2，否则检查f(x₀)与f(a)是否同号，如同号，说明所求的根x^*在x₀的右侧，这时令a₁=x₀，b₁=b；否则，x^*在x₀的左侧，这时令a₁=a，b₁=x₀，这样新的有根区间[a₁,b₁]的长度为原有根区间[a,b]的一半

误差

$$\left| x^* - x_k \right| \leq \frac{1}{2} (b_k - a_k) = \frac{1}{2^{k+1}} (b - a)$$

若事先给定误差为ε，则只需

$$\left| x^* - x_k \right| \leq \frac{1}{2^{k+1}} (b - a) < \varepsilon$$

收敛速度与比值为1/2的等比数相同

局限性：只能求单根

迭代法

对于一般连续函数方程f(x)=0，改写成等价形式方程x=φ(x)

迭代法收敛才能用

• 全局收敛性

设函数φ(x)在区间[a,b]上具有连续的一阶导数，且满足

1.对所有的x∈[a,b]有φ(x)∈[a,b]

2.存在0<L<1，使所有的x∈[a,b]，有

$$|\varphi'(x)|\leq L$$

则方程x=φ(x)在区间[a,b]上的解x^*存在且唯一，对任意的x₀∈[a,b]，迭代过程x_k+1=φ(x_k)均收敛于x^*

且L越小，收敛速度越快

• 局部收敛性

设φ(x)在x=φ(x)的根x^*邻域有连续的一阶导数，且

$$\left| \varphi'(x^*) \right| < 1$$

则迭代过程x_k+1=φ(k)具有局部收敛性

收敛速度

设迭代过程x_k+1=φ(x_k)收敛于x=φ(x)的根x^*，令迭代误差e_k=x_k-x^*，若存在常数p(p≥1)和c(c＞0)，使

$$\lim_{k\rightarrow+\infty}\frac{\left|e_{k+1}\right|}{\left|e_{k}\right|^{p}}=c$$

则称序列{x_k}是p级收敛的，c称渐进误差常数

---

对迭代过程x_k+1=φ(x_k)，若φ^(p)(x)在所求根x^*的邻域连续，且

$$\varphi'(x^*) = \varphi''(x^*) = \cdots = \varphi^{(p-1)}(x^*) = 0, \quad \varphi^{(p)}(x^*) \neq 0$$

则迭代过程在x^*邻域是p阶收敛的

p=1,0<c<1时称线性收敛，p=2时称平方收敛，p>1时称超线性收敛

迭代过程的收敛速度依赖于迭代函数φ(x)的选取。当φ’(x^*)≠0时，则该迭代过程最多是线性收敛，当φ’(x^*)=0时，迭代过程至少是平方收敛

迭代加速

埃特金加速

设序列{x_k}线性收敛到x^*，记

$$\bar{x}_{k+1} = x_k - \frac{(\Delta x_k)^2}{\Delta^2 x_k}, \quad k = 0, 1, \ldots$$

其中△x_k=x_k+1-x_k是x_k点的一阶差分，△²x_k=x_k+2-2x_k+1+x_k是x_k点的二阶差分

斯蒂芬森迭代

当把不动点迭代法和埃特金加速法结合起来即得到斯蒂芬森迭代法，即

$$\begin{cases} y_k = \varphi(x_k) \\ z_k = \varphi(y_k) \\ x_{k+1} = x_k - \frac{(y_k - x_k)^2}{z_k - 2y_k + x_k} \end{cases}$$

即

$$x_{k+1} = x_k - \frac{(f(x_k) - x_k)^2}{f(f(x_k)) - 2f(x_k) + x_k}$$

不收敛的迭代可用斯蒂芬森让其至少平方收敛

牛顿迭代法

$$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$$

设函数f(x)满足f(x^*)=0,f'(x^*)≠0，且f''(x)在x^*邻域连续，则牛顿迭代法在x^*局部收敛，且至少二阶收敛。并有

$$\lim_{k\rightarrow+\infty} \frac{e_{k+1}}{e_k^2} = \frac{f''(x^*)}{2f'(x^*)}$$

优点：收敛性速度快

缺点：每次要计算导数f'(x_k)，计算量大

牛顿下山法

要求迭代过程对所选的初值能达到使函数值单调下降，即要满足下山条件|f(x_k+1)|＜|f(x_k)|

$$x_{k+1} = x_k - \lambda \frac{f(x_k)}{f'(x_k)}$$

其中λ称为下山因子。通过适当选取下山因子λ保证函数值f(x_k)能单调下降。下山因子的选择是逐步探索进行的，从λ=1开始反复将 λ的值减半进行试算

λ≠1时只有线性收敛速度

当重根数已知时，设x^*是f(x)=0的m重根(m≥2)，即满足

$$f(x^*) = f'(x^*) = \cdots = f^{(m-1)}(x^*) = 0, \quad f^{(m)}(x^*) \neq 0$$

则牛顿迭代法迭代过程是线性收敛，不是平方收敛

---

• 修正的牛顿迭代法：

$$x_{k+1} = x_k - m \frac{f(x_k)}{f'(x_k)}$$

此时平方收敛，但是需要预知重根数m的值

• 无需知道重根数的修正牛顿迭代法：

$$x_{k+1} = x_k - \frac{f'(x_k) f(x_k)}{f'(x_k)^2 - f(x_k) f''(x_k)}, \quad k = 0, 1, \ldots$$

弦截法

为了避免计算导数，改用差商代替导数。弦截法又分单点弦法和双点弦法。双点弦法的收敛速度低于牛顿迭代法，但又高于不动点迭代法

单点弦截法

设方程f(x)=0，在区间[x0,x1]上有唯一根x^*，选f(x)=0上的两点(x0,f(x0))和(x1,f(x1))作弦（直线），则有两点式方程

$$f(x) = f(x_1) + \frac{f(x_1) - f(x_0)}{x_1 - x_0}(x - x_1)$$

写成迭代格式

$$x_{k+1} = x_k - \frac{f(x_k)}{f(x_k) - f(x_0)}(x_k - x_0), \quad k = 1, 2, \cdots$$

几何意义：过两个点作弦，这个弦和x轴的交点即是根的新的近似值，因为弦的一个端点(x₀, f(x₀))始终不变，只有另一个端点变动，所以这种方法称为单点弦法

双点弦法

用差商(f(x_k)-f(x_k-1))/(x_k-x_k-1)替代牛顿迭代公式中的导数f’(x)，导出

$$x_{k+1} = x_k - \frac{f(x_k)}{f(x_k) - f(x_{k-1})}(x_k - x_{k-1}), \quad k = 1, 2, \ldots$$

称为双点弦法

双点弦法收敛速度比单点弦截法快，仅稍慢于牛顿法，是超线性收敛