在數值分析中,割線法是一個求根算法,該方法用一系列割線的根來近似代替函數f的根。
方法
割線法的最初兩個疊代。紅色曲線表示函數f,藍色曲線表示割線。
割線法由以下的遞迴關係定義:
![{\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}f(x_{n}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/493e82a4208e2216c27c62f1e97dd3376f5dd012)
從上式中可以看出,割線法需要兩個初始值x0和x1,它們離函數的根越近越好。
方法的推導
給定xn−1和xn,我們作通過點(xn−1, f(xn−1))和(xn, f(xn))的直線,如右圖所示。注意這條直線是函數f的割線,或弦。這條割線的點斜式直線方程式為:
![{\displaystyle y-f(x_{n})={\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}(x-x_{n}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c65cc0bd1903cdddc77798a89bdaa90079687c1)
我們現在選擇xn+1為這條割線的根,因此xn+1滿足以下的方程式:
![{\displaystyle f(x_{n})+{\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}(x-x_{n})=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94a89517b8f020c143d163e4527da6449aa54537)
解這個方程式,便可以得出割線法的遞迴關係。
收斂
如果初始值x0和x1離根足夠近,則割線法的第n次疊代x收斂於f的一個根。收斂速率為α,其中:
![{\displaystyle \alpha ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b28434b40806fe30c07646d42c51ce100b48808)
是黃金比。特別地,收斂速率是超線性的。
這個結果只在某些條件下才成立,例如f是連續的二階可導函數,且函數的根不是重根。
如果初始值離根太遠,則不能保證割線法收斂。