割線法
另外一個求單變數函數零點的零次方法叫做「割線法(secant method)」，或者有的書稱此方法為「線性內差法(linear interpolation method)」。如圖3所示，割線法顧名思義，是在函數上前兩次迭代點之間畫一條割線，來近似這個單變數函數，並求出這條割線與橫軸的交點，作為下一次迭代點。割線法的迭代定義如下式：
(1)
其中fk、fk-1便是第k、k-1次迭代的函數值，xk為第k次迭代的設計點，xk+1是割線與橫軸的交點，也就是下一次迭代的新設計點。
圖3. 割線法求函數零點
割線法亦可寫成如下虛擬程式：
algorithm 2 Secant Method;
begin
input: 
;
while 
do
do
begin
;
end;
output 
, 
;
, ;
end.
割線法的「收斂速率(convergence rate)」較二分法為快（此處將不對演算法的收斂速率作正式、理論性的討論），但其主要問題是，如果xk和xk-1在函數零點的同側，也就是xk和xk-1形成的割線所求出與橫軸的交點xk+1是線性外差而非內差，如圖3中的點x4為x2、x3的線性外差，那麼割線法很可能會發散。
割線法概念上屬於「序列近似法(sequential approximation method)」，不斷用兩點間的割線來近似原先的曲線。序列近似法的概念和二分法中不斷有系統地減小搜尋的不確定區間的想法，也正是下面介紹單變數函數最小值搜尋演算法兩種不同的體系。
https://www.codewithc.com/c-program-for-secant-method/
Below is a short and simple C programming source code for Secant method to find the root of x^3 – 4 or x*x*x – 4.
f(x) = x*x*x – 4
Source Code for Secant Method in C:
#include<stdio.h>
float f(float x)
{
return(x*x*x-4); // f(x)= x^3-4
}
float main()
{
float a,b,c,d,e;
int count=1,n;
printf("\n\nEnter the values of a and b:\n"); //(a,b) must contain the solution.
scanf("%f%f",&a,&b);
printf("Enter the values of allowed error and maximun number of iterations:\n");
scanf("%f %d",&e,&n);
do
{
if(f(a)==f(b))
{
printf("\nSolution cannot be found as the values of a and b are same.\n");
return;
}
c=(a*f(b)-b*f(a))/(f(b)-f(a));
a=b;
b=c;
printf("Iteration No-%d x=%f\n",count,c);
count++;
if(count==n)
{
break;
}
} while(fabs(f(c))>e);
printf("\n The required solution is %f\n",c);
}
Input/Output:
輸入資料
2 3
0.0005 20
輸出資料
Enter the values of a and b:
Enter the values of allowed error and maximun number of iterations:
Iteration No-1 x=1.789474
Iteration No-2 x=1.690998
Iteration No-3 x=1.599075
Iteration No-4 x=1.588127
Iteration No-5 x=1.587406
The required solution is 1.587406
2 3
0.0005 20
輸出資料
Enter the values of a and b:
Enter the values of allowed error and maximun number of iterations:
Iteration No-1 x=1.789474
Iteration No-2 x=1.690998
Iteration No-3 x=1.599075
Iteration No-4 x=1.588127
Iteration No-5 x=1.587406
The required solution is 1.587406
沒有留言:
張貼留言