【转】布伦特方法(Brent‘s method)---求根方法

本文主要是介绍【转】布伦特方法(Brent‘s method)---求根方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 解方程（Solving Equations）

1.1 二分法（The Bisection Method）

定义1.1 对于方程

f(x)

，如果有

f(r) = 0

，则说

x = r

是

f(x)

的一个根。

定理1.2 令

是

[a, b]

上的连续函数，满足

f(a)f(b) < 0

, 则

在

和

之间存在一个根。

二分法算法流程：

二分法误差：

在区间

[a, b]

，

次二分之后，得到最终区间

$[a_{n}, b_{n}]$

其长度为

$(b - a) / 2^{n}$

。选取中间点

$x_{c} = (a_{n} + b_{n}) / 2$

最为根

的最有估计，则误差为：

定义1.3 如果误差小于

$0.5 \times 10^{-p}$

，则称其精确到小数点后

位。

二分法迭代次数：

只要确定了期望的精度，就可以依据二分法误差计算公式得到所需要的迭代次数。

1.2 不动点迭代（Fixed-Point Iteration）

定义1.4 对于方程

，存在

，使得

g(r) = r

，就称

是方程

的不动点。

例如：

FPI 算法流程：

当方程可写作

g(x) = x

的形式时，则使用初值

$x_{0}$

进行 FPI：

FPI 可能收敛，也可能不收敛，如果收敛到

，则

就是

的不动点，也是

f(x) = g(x) - x = 0

的解。

不同的

x = g(x)

形式

同一个方程写成不同的

x = g(x)

，由于

g(x)

的不同，其能不能收敛，收敛快慢也不同：

例：对于

x^3 + x - 1 = 0

，其

g(x)

可写成：

g(x) = 1 - x^3

(a)

$g(x) = \sqrt[3]{1 - x}$

(b)

$g(x) = \frac{1 + 2x^3}{1 + 3x^2}$

(c)

令

$x_{0} = 0.5$

，分别进行 FPI，其每次迭代数值，及 cobweb 图 ：

(a) 不收敛

(b) 收敛较慢

不动点迭代（FPI）的线性收敛

通过对

g(x)

几何观察，其不动点

附近的斜率的绝对值，即

$|{g}'(\tilde{r})|$

如果小于 1，则FPI收敛，大于 1，则FPI不收敛。

定义1.5 令

$e_{i}$

表示FPI过程中第

步的误差，如果：

则满足线性收敛，收敛率为

。

注: 关于线性收敛，超线性收敛，r阶收敛；以及 Rate of convergence；令见下文 定义1.10。

定理1.6 设

连续可微，

g(r) = r

，且

S = |g'(r)| < 1

。那么就称对于一个足够接近

的初值估计，FPI以速度

线性收敛到不动点

定义1.7 如果一个迭代方法，能够以一个足够接近

的初值估计收敛到

，则称该方法局部收敛（Locally Convergent）。

例：使用FPI计算

$\sqrt{2}$

$x = \sqrt{2} \Rightarrow x^2 - 2 = 0 \Rightarrow x + \frac{2}{x} -2x =0 \Rightarrow \frac{x + \frac{2}{x}}{2} = x$

，即求

$g(x) = \frac{x + \frac{2}{x}}{2}$

的不动点，运用FPI，收敛到 1.414215686

分析此时

$g(x) = \frac{x + \frac{2}{x}}{2}$

导数

$g' = \frac{1}{2} - x^{-2}$

，收敛率

$S = |\frac{1}{2} - (\sqrt{2}^{-2})| = 0$

，收敛，且收敛很快。

终止条件（Stopping Criteria）

不同于二分法，FPI无固定的误差公式，无法预测收敛所需步数，故而需要给出终止条件

（1.18）中

$\theta > 0$

通常用于解在 0 附近的情况。

另外，好的FPI（代码）实现通常要设置最大迭代次数，以防止收敛失败。

二分法和FPI比较

	二分法	FPI
收敛性	保证线性收敛	局部收敛时，则线性收敛
每步计算	每步只需一次函数求值	一次
速度	每步去掉1/2不确定性	不确定性会乘上，故而可能更慢或更快，要看比1/2大还是小
其他		牛顿方法是FPI的改善，其

1.3 精度（Accuracy）

前向误差和后向误差 (Forward error & Backward error)

定义1.8 设

是方程

的一个根，即满足

f(r) = 0

，

$x_{a}$

是根

的近似值，对于求解根的问题，该近似解

$x_{a}$

的前向误差是

$|r - x_{a}|$

，后向误差是

$|f(x_{a})|$

。

关于“前向”和“后向”：

“Backward error is on the left or input (problem data) side. It is the amount we would need to change the problem (the function f ) to make the equation balance with the output approximation

$x_{a}$

. This amount is

$|f(x_{a})|$

. Forward error is the error on the right or output (problem solution) side. It is the amount we would need to change the approximate solution
to make it correct, which is

$|r - x_{a}|$

.”

思考：对于方程

f(x) = 0

有根

，写成

g(x) = x

的形式，即有

g(r) = r

，设

$x_{a}$

为近似值，则对应的：

前向误差：

$|r - x_{a}|$

；

后向误差：

$|x_{a} - g(x_{a})|$

相对前向误差（relative forward error）：

$\frac{|r - x_{a}|}{|r|}$

相对后向误差（relative backward error）：

$\frac{|x_{a} - g(x_{a})|}{|x_{a}|}$

定义1.9 设

是可微函数

的一个根，即满足

f(r) = 0

，如果有：

就称

在

处有

重数（multiplicity m）。如果重数大于1，则称

在

处有重根（multiple root），当重数为1时，称为单根（simple）。

Wilkinson多项式

由式（1.19）可知根为1 到 20 的实数。但是若是给出的是式（1.20），使用迭代方法求解，“its evaluation suffers from cancellation of nearly equal, large numbers.” 小误差导致最终的大误差。

根求解的敏感性（Sensitivity of root-finding）

当输入小的误差，导致求解后大的输出误差时，这一情况被称作敏感性。

根的敏感性公式：

误差放大因子（error magnification factor）:

即： 相对前向误差 / 相对后向误差

条件数（condition number）

"The condition number of a problem is deﬁned to be the maximum error magniﬁcation over all input changes, or at least all changes of a prescribed type." 条件数是误差放大的一总度量。

下图来自维基百科-条件数：