方程的根的求法——交叉法，疊代法
疊代法
一、疊代法基本原理介紹
-
疊代法的基本思想
将方程改寫成某種等價形式，由等價形式構造出相應的疊代公式，然後選擇方程的某個初始近似根x_0，代入疊代公式，反複矯正，逼近所求的根的近似值，直到達到滿足的精度為止。
給定一個方程f(x)=0，要求求出這個方程的一個近似的根。我們給出計算過程：
- 将方程改寫成為x=g(x)的等價形式。比如改寫成：x=x+f(x)②（右邊的x+f(x)就相當于g(x)）。
- 給定一個初值x_0代入②式的右端，得到x_1=g(x_0 ),x_2=g(x_1 ),x3=g(x_2)……
- 通過（2），本質是一個遞推式，即上述的疊代公式：x_(k+1)=g(x_k ),k=0,1,2,3……進而我們得到一個序列{x_k }，即{x_0,x_1,x_2……x_k……}。
- 如果序列{x_k}有極限x*，那麼x*即是所求的方程的近似根。或者說按照所給的精度（比如0.001）如果偏差|x_(k+1)-x_k|<ε，ε≤0.001，那麼就保證了疊代誤差|x-x_k|足夠小。是以|x_(k+1)-x_k|<ε往往作為疊代結束的條件。
-
此方法的幾何意義：
y=x與y=g(x)的圖像的交點——
數值計算方法——第一節方程的根的求解方程的根的求法——交叉法，疊代法 -
給出一個例子：求方程：x^3-x-1=0的根
我們将上述方程改寫成為它的一個等價形式：x=∛(x+1)
選擇初始值x_0=1.5
4. 關于疊代法中g(x)的選擇的問題
雖然疊代法的思想簡單，但是并不是每次都能得到根的值：g(x)的選擇是關鍵點。還是以方程x^3-x-1=0為例，假如我們将方程改寫成為另外一種形式：
我們仍取初值x_0=1.5，然後建立疊代公式：
經過疊代我們發現𝑥1=2.375，𝑥2=12.3976……一直疊代下去并沒有發現序列收斂。是以𝑔(𝑥)的選擇是很重要的。
有定理：設方程x=g(x)，在(a,b)内有根x，滿足李普希茲(Lipschitz)條件：即對(a,b)内任意的x_1，x_2 都有：
其中q為一個确定的正數，且q<1。那麼方程在(a, b)内有唯一的根。
且疊代公式：
對于任意初始近似值x_0均收斂于方程的根x
需要說明三點：
①要驗證g(x)滿足李普希茲條件是比較困難的，若g(x)可微，可以利用充分條件
來替代李普希茲條件。否則不一定能滿足求出收斂的根x*。
②疊代的終止條件：|x_(k+1)-x_k|<ε。
③在上面我們已經說過，确定g(x)是比較重要的。選取不當的話，疊代的結果不會收斂。最一般地，g(x)可以寫成這種形式：
x+α(x)f(x)；
即方程x=x+α(x)f(x)的形式，這樣可以通過選取α(x)，使其滿足①中給出的充分條件。
二、常用的确定g(x)的方法
1.牛頓法（Newton-Raphson Method）
（1）在牛頓法中，我們選擇
（2）疊代公式：
（3）牛頓法确定g(x)的幾何意義：做x_0這點的切線，切線與x軸交點為x_1，後面以此類推……
2.弦截法（Secant Method）
（1）在弦截法中，遞推公式為：
交叉法
一、交叉法概述
這是一類求根方法，對于連續的𝑓(𝑥), 現在已知𝑓(x_1)𝑓(x_2) < 0，那麼在x_1與x_2之間一定有一點𝑥滿足𝑓(𝑥) = 0，即 𝑥 ∈ (x_1, x_2)，（這裡不妨設x_1 < x_2） 我們可通過不斷減小這個區間的範圍,進而找到𝑥的數值解。
二、 交叉法的具體方法
- 逐漸求根法
- 二分法
- 比例求根法
方法過程：
- 設𝑓(𝑎) < 0, 𝑓(𝑏) > 0
-
對于上述的三種方法：
逐漸求根法：
c=a+h (h為步長)
二分法：
c=(a+b)/2
比例求根法：
數值計算方法——第一節方程的根的求解方程的根的求法——交叉法，疊代法 -
計算𝑓(c）
若𝑓(c）> 0，則令a=c
若𝑓(c）< 0, 則令b=c
若𝑓(c）= 0, 則x=c，結束
- 傳回步驟2
三、例題分析
例1：分别用二分法、牛頓法、弦截法求下列方程的根，并分别畫出幾種方法所求根的收斂速 度對比圖（即畫出相對誤差随疊代步數的變化趨勢圖）以下給出Matlab代碼。
- f(x)=cosx-x
function y=f(x)
%編輯方程式
y=cos(x)-x;
①二分法：
function [c,k,iteration]=half(a,b,epsilon)
%預設取中點為數值解
iteration=zeros(19,1);
k=0;%疊代次數
result=test;
% result是零點，即方程的解
myResult=0;
c=0;
while(abs(myResult-result)>epsilon)
c=(a+b)/2;
if f(a)*f(c)<0
b=c;
elseif f(b)*f(c)<0
a=c;
end
myResult=c;
k=k+1;
iteration(k)=abs(myResult-result)/result;
end
x=1:k;
plot(x,iteration,'-b');
grid on
xlabel('疊代次數');
ylabel('相對誤差');
legend('二分法求解');
②牛頓法
function [k,x1]=newton(x0,epsilon)
%牛頓法求根
result=test;
%result為根的值；
syms x
g=cos(x)-x;
f1=subs(diff(g),x,x0);
x1=x0-f(x0)/f1;
k=1;
iterater=zeros(5,1);
while (abs(x0-x1)>=epsilon)
x0=x1;
f1=subs(diff(g),x,x0);
x1=x0-f(x0)/f1;
myResult=x1;
iterater(k)=abs(myResult-result)/result;
k=k+1;
end
k1=1:k;
plot(k1,iterater,'-.r')
③ 弦截法
function secant(x0,x1,epsilon)
%弦截法求根
x2=x1-(x1-x0)*f(x1)/(f(x1)-f(x0));
k=1;
while(abs(x2-x1)>=epsilon)
x0=x1;
x1=x2;
x2=x1-(x1-x0)*f(x1)/(f(x1)-f(x0));
end
k
x2