# [转载] 割线法的动画图      "割线法是一个求根算法，该方法用一系列割线的根来近似代替函数f的根。割线法比牛顿法 [又称为牛顿-拉弗森方法方法使用函数f(x){\displaystyle f(x)} 泰勒级数的前面几项来寻找方程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}).} (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})}}.} 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.)

• 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}).} • 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.} (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}).} 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})}}.} 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}}} )

• α=1+52≈1.618{\displaystyle \alpha ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618} (The iterates xn{\displaystyle x_{n}} of the secant method converge to a root of f{\displaystyle f} , if the initial values x0{\displaystyle x_{0}} and x1{\displaystyle 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} 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} 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}]} . For example, if f{\displaystyle f} is differentiable on that interval and there is a point where f′=0{\displaystyle f'=0} on the interval, then the algorithm may not converge.)

"

References

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

## 全部精选博文导读

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