Todd's Matlab讲义第6讲:割线法

割线法

割线法求解方程\(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所示。

Todd's Matlab讲义第6讲:割线法

图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\nrightarrow 0\)。比如,图6.1中的函数,\(a\rightarrow x^\*\),而\(b\nrightarrow 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结果做比较。

上一篇:leetcode[170]Two Sum III - Data structure design


下一篇:UIImage加载图片的区别和渲染模式