割线法

割线法求解方程

的根需要两个接近真实根

的初值$x_0$和$x_1$，于是得到函数$f(x)$上两个点$(x_0,y_0=f(x_0))$和$(x_1,y_1=f(x_1))$，连接这两点得到一条直线（割线）：

\begin{equation*}
y-y_1=\frac{y_1-y_0}{x_1-x_0}(x-x_1)
\end{equation*}

由于我们要求解$f(x)=0$，因此设$y=0$，由上式解出$x$，作为下次迭代的初值。这个过程一直进行下去，有如下迭代关系：

\begin{equation}
x_{i+1}=x_i-\frac{x_i-x_{i-1}}{y_i-y_{i-1}}y_i
\tag{6.1}\label{6.1}
\end{equation}

其中$y_i=f(x_i)$。以上过程如图6.1所示。

图6.1 割线法求根

割线法需要两个初值，但是不需要求函数的导数。割线法程序如下：

function x = mysecant (f,x0 ,x1 ,n)
% Solves f(x) = 0 by doing n steps of the secant method
% starting with x0 and x1.
% Inputs : f -- the function , input as an inline function
% x0 -- starting guess , a number
% x1 -- second starting geuss
% n -- the number of steps to do
% Output : x -- the approximate solution
y0 = f(x0 );
y1 = f(x1 );
for i = 1:n % Do n times
x = x1 - (x1 -x0 )* y1 /(y1 -y0) % secant formula .
y=f(x) % y value at the new approximate solution .
% Move numbers to get ready for the next step
x0=x1;
y0=y1;
x1=x;
y1=y;
end

盈不足术

盈不足术是割线法和二分法的综合。如二分法，我们先选定两个初始点$a$和$b$，且保证$f(a)$和$f(b)$异号。然后我们根据割线法，得到新的迭代结果，

\begin{equation*}
x =b-\frac{b-a}{f(b)-f(a)}f(b)
\end{equation*}

然后我们按照二分法，判断$f(x)$的符号，如果$f(x)$与$f(a)$同号，则把$x$设为新的$a$，否则，把$x$设为新的$b$。注意到，一般情况下，$a$和$b$其中之一逐渐趋近于$x^*$，而不大可能二者共同趋近于$x^*$，因此$b-a$不大可能会趋近于$0$。比如，图6.1中的函数，$a\rightarrow x^*$，而$b$不趋近于$x^*$。

收敛性

如果我们选的初值$x_0$比较好，牛顿法会很快收敛到$x^*$。割线法要比牛顿法慢一些，盈不足术会更慢。二分法是收敛最慢的。

如果我们选的初值或初始区间不够好，割线法——如牛顿法一样——可能会不收敛。盈不足术——如二分法一样——总是收敛的，因为盈不足术会一直保证根在一个确定的区间内。

模拟和实验

尽管牛顿法最快，但有些情况下，牛顿法不太好用，甚至根本不能用。比如难以导出$f'(x)$表达式的情况。在科学和工程中的一些问题中，甚至连$f(x)$的表达式都没有，$f(x)$是实验和模拟的结果时就是这样的情况。在这样的情况下，割线法一般是最佳选择。

练习

6.1 用纸和计算器对方程$f(x)=x^3-4=0$应用三次盈不足术迭代，初始区间$[1,3]$，计算各次迭代结果的误差和相对误差，并与练习3.3和5.2结果做比较。

6.2 写出函数程序myregfalsi，实现盈不足术，并使残量绝对值小于给定公差，并将程序解方程$f(x)=2x^3+3x-1=0$，初始区间为$[0,1]$，公差为$10^{-8}$。程序需要迭代多少步？与练习5.1结果做比较。