Dr jiapu ZHANG分享 http://blog.sciencenet.cn/u/jiapuzhang

博文

[转载] 割线法的动画图

已有 1787 次阅读 2019-10-4 12:13 |系统分类:图片百科|文章来源:转载

Secantaa.gif

"割线法是一个求根算法,该方法用一系列割线的根来近似代替函数f的根。割线法比牛顿法 [又称为牛顿-拉弗森方法方法使用函数f(x){\displaystyle f(x)}f(x)泰勒级数的前面几项来寻找方程f(y)=0{\displaystyle f(y)=0}{\displaystyle f(y)=0}的根] 早3000年。" -- https://zh.wikipedia.org/wiki/割线法  https://en.wikipedia.org/wiki/Secant_method

"

割线法由以下的递推关系定义:

  • xn+1=xn−xn−xn−1f(xn)−f(xn−1)f(xn).{\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}f(x_{n}).}{\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}f(x_{n}).}

从上式中可以看出,割线法需要两个初始值x0x1,它们离函数的根越近越好。

(The secant method is defined by the recurrence relation

  • xn=xn−1−f(xn−1)xn−1−xn−2f(xn−1)−f(xn−2)=xn−2f(xn−1)−xn−1f(xn−2)f(xn−1)−f(xn−2).{\displaystyle x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}={\frac {x_{n-2}f(x_{n-1})-x_{n-1}f(x_{n-2})}{f(x_{n-1})-f(x_{n-2})}}.}{\displaystyle x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}={\frac {x_{n-2}f(x_{n-1})-x_{n-1}f(x_{n-2})}{f(x_{n-1})-f(x_{n-2})}}.}

As can be seen from the recurrence relation, the secant method requires two initial values, x0 and x1, which should ideally be chosen to lie close to the root.)

给定xn−1xn,我们作通过点(xn−1, f(xn−1))和(xn, f(xn))的直线。注意这条直线是函数f割线,或弦。这条割线的点斜式直线方程为:

  • y−f(xn)=f(xn)−f(xn−1)xn−xn−1(x−xn).{\displaystyle y-f(x_{n})={\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}(x-x_{n}).}{\displaystyle y-f(x_{n})={\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}(x-x_{n}).}

我们现在选择xn+1为这条割线的根,因此xn+1满足以下的方程:

  • f(xn)+f(xn)−f(xn−1)xn−xn−1(x−xn)=0.{\displaystyle f(x_{n})+{\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}(x-x_{n})=0.}{\displaystyle f(x_{n})+{\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}(x-x_{n})=0.}

解这个方程,便可以得出割线法的递推关系。

(Starting with initial values x0 and x1, we construct a line through the points (x0, f(x0)) and (x1, f(x1)), as shown in the picture above. In slope–intercept form, the equation of this line is

  • y=f(x1)−f(x0)x1−x0(x−x1)+f(x1).{\displaystyle y={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{1})+f(x_{1}).}{\displaystyle y={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{1})+f(x_{1}).}

The root of this linear function, that is the value of x such that y = 0 is

  • x=x1−f(x1)x1−x0f(x1)−f(x0).{\displaystyle x=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}.}{\displaystyle x=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}.}

We then use this new value of x as x2 and repeat the process, using x1 and x2 instead of x0 and x1. We continue this process, solving for x3, x4, etc., until we reach a sufficiently high level of precision (a sufficiently small difference between xn and xn−1):

  • x2=x1−f(x1)x1−x0f(x1)−f(x0),x3=x2−f(x2)x2−x1f(x2)−f(x1),⋮xn=xn−1−f(xn−1)xn−1−xn−2f(xn−1)−f(xn−2).{\displaystyle {\begin{aligned}x_{2}&=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}},\\[6pt]x_{3}&=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}},\\[6pt]&\,\,\,\vdots \\[6pt]x_{n}&=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}.\end{aligned}}}{\displaystyle {\begin{aligned}x_{2}&=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}},\\[6pt]x_{3}&=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}},\\[6pt]&\,\,\,\vdots \\[6pt]x_{n}&=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}.\end{aligned}}})

如果初始值x0x1离根足够近,则割线法的第n次迭代x收敛于f的一个根。收敛速率为α,其中:

  • α=1+52≈1.618{\displaystyle \alpha ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618}{\displaystyle \alpha ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618}

黄金比。特别地,收敛速率是超线性的。

这个结果只在某些条件下才成立,例如f是连续的二阶可导函数,且函数的根不是重根。

如果初始值离根太远,则不能保证割线法收敛。

(The iterates xn{\displaystyle x_{n}}x_{n} of the secant method converge to a root of f{\displaystyle f}f, if the initial values x0{\displaystyle x_{0}}x_{0} and x1{\displaystyle x_{1}}x_{1} are sufficiently close to the root. The order of convergence is φ , where

  • φ=1+52≈1.618{\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618}{\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618}

is the golden ratio. In particular, the convergence is superlinear, but not quite quadratic.

This result only holds under some technical conditions, namely that f{\displaystyle f}f be twice continuously differentiable and the root in question be simple (i.e., with multiplicity 1).

If the initial values are not close enough to the root, then there is no guarantee that the secant method converges. There is no general definition of "close enough", but the criterion has to do with how "wiggly" the function is on the interval [x0,x1]{\displaystyle [x_{0},x_{1}]}[x_{0},x_{1}]. For example, if f{\displaystyle f}f is differentiable on that interval and there is a point where f′=0{\displaystyle f'=0}{\displaystyle f'=0} on the interval, then the algorithm may not converge.)

"


References

https://web.archive.org/web/20081017171843/http://math.fullerton.edu/mathews/a2001/Animations/RootFinding/SecantMethod/Secantaa.html  
https://web.archive.org/web/20081017171848/http://math.fullerton.edu/mathews/a2001/Animations/RootFinding/SecantMethod/Secantbb.html  
https://web.archive.org/web/20081017170102/http://math.fullerton.edu/mathews/a2001/Animations/RootFinding/SecantMethod/Secantcc.html  
https://web.archive.org/web/20081017171853/http://math.fullerton.edu/mathews/a2001/Animations/RootFinding/SecantMethod/Secantdd.html  
https://web.archive.org/web/20081026042452/http://math.fullerton.edu/mathews/a2001/Animations/RootFinding/SecantMethod/Secantee.html  
https://web.archive.org/web/20081026051330/http://math.fullerton.edu/mathews/a2001/Animations/RootFinding/SecantMethod/Secantff.html  



http://wap.sciencenet.cn/blog-498408-1200576.html

上一篇:[转载] Hadamard矩阵
下一篇:[转载]<<Molecular Structures and Structural Dynamics of PrP>>9月书评

0

评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

全部作者的精选博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-8-14 02:09

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部