割线法
割线法求解方程\[f(x)=0\]的根需要两个接近真实根\[x^*\]的初值$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结果做比较。