數(shù)值分析讀書筆記（4）求非線性方程的數(shù)值求解
1.關(guān)于非線性方程的根的定位以及二分法
我們直接介紹二分法
將有根區(qū)間
用中點(diǎn)
將它平分, 如果
不是
的零點(diǎn), 則再做搜索, 檢查
和
是否同號(hào), 然后即可知根落在左側(cè)還是右側(cè), 用這個(gè)中點(diǎn)來(lái)代替掉原來(lái)的端點(diǎn), 然后得到一個(gè)新的區(qū)間, 如此反復(fù)迭代下去之后, 我們會(huì)發(fā)現(xiàn)區(qū)間收斂到接近一個(gè)數(shù)
二分法簡(jiǎn)單易懂,我們只要不斷去計(jì)算中點(diǎn),然后判斷符號(hào),從而來(lái)判斷根的位置
但是二分法有著收斂速度慢的缺點(diǎn),我們一般是用二分法來(lái)找到一個(gè)合適的初始值,然后再用其他收斂速度比較快的算法進(jìn)行計(jì)算
我們可以用代碼來(lái)實(shí)現(xiàn)一下二分法
public class NumericalTest {
public static void main(String[] args){
double a=0,b=2,mid=(a+b)/2,fa,fb,fmid;
for(int i=0;i<100;i++){
System.out.println(mid);
fa=function(a);
fb=function(b);
fmid=function(mid);
if(fa*fmid>0){
a=mid;
}else{
b=mid;
}
mid=(a+b)/2;
}
}
public static double function(double x){
return Math.pow(x,3)+2*Math.pow(x,2)-4;
}
}
給出最后的輸出結(jié)果
1.1303954347672787
1.1303954347672787
1.1303954347672787
1.1303954347672787
1.1303954347672787
1.1303954347672787
1.1303954347672787
2.基于不動(dòng)點(diǎn)原理的迭代法
類似于之前關(guān)于迭代法求解線性方程組時(shí)所講過(guò)的Gauss-Seidel迭代以及Jacobi迭代等迭代的方法,我們對(duì)于非線性方程也可以使用這種基于不動(dòng)點(diǎn)原理的迭代法,這時(shí)我們的目的即是構(gòu)造出一個(gè)等價(jià)的非線性方程
我們用簡(jiǎn)單的代碼來(lái)模擬一下
public class NumericalTest {
public static void main(String[] args){
double x=0;
for(int i=0;i<100;i++){
x=function(x);
System.out.println(x);
}
}
public static double function(double x){
return Math.sqrt((4-Math.pow(x,3))/2);
}
}
上面的代碼是對(duì)進(jìn)行轉(zhuǎn)換, 并且建立迭代格式
最后可以看出來(lái)應(yīng)該是收斂的,給出最后的幾個(gè)輸出
1.1303954901953999
1.1303953877755042
1.130395474606742
1.1303954009915165
1.1303954634022533
1.1303954104906446
這里給出不動(dòng)點(diǎn)迭代的三個(gè)基本要求
- 適定性: 要保證序列
始終在
的定義域中,才能使迭代不中斷
- 收斂性: 要求迭代收斂
- 收斂率: 要求收斂速度盡可能高
接下來(lái)我們來(lái)研究一下不動(dòng)點(diǎn)的存在性以及迭代法的全局收斂性
關(guān)于不動(dòng)點(diǎn)的存在性,給出一個(gè)Lipschitz條件,且給出不動(dòng)點(diǎn)存在與唯一性定理
設(shè)迭代函數(shù)
, 且同時(shí)滿足
1. 定義域條件:,
**2. Lipschitz條件:存在Lipschitz常數(shù),使得對(duì)任意
有
**
則不動(dòng)點(diǎn)迭代函數(shù)在
需要注意的是,這是不動(dòng)點(diǎn)存在且唯一的一個(gè)充分條件,卻不是必要的,
也就是說(shuō)如果不滿足這兩個(gè)條件或不滿足其中一個(gè)條件者,可能存在不動(dòng)點(diǎn)
下面給出不動(dòng)點(diǎn)迭代收斂與誤差估計(jì)的定理
設(shè)迭代函數(shù)
滿足上述的定義域條件以及Lipschitz條件,則對(duì)任意的
, 由不動(dòng)點(diǎn)迭代格式產(chǎn)生的序列
必收斂于
,并有誤差估計(jì)
上述兩個(gè)不等式,有時(shí)稱前者為先驗(yàn)估計(jì),后者為后驗(yàn)估計(jì)
利用上面的不等式,我們可以計(jì)算出給定誤差界限所需要迭代的步數(shù)
其中為給定的誤差界限
給出一個(gè)推論
設(shè)迭代函數(shù)
,
在
則之前給出的不動(dòng)點(diǎn)唯一定理以及后續(xù)的收斂定理均成立
以上給出的條件可能是基于全局收斂的,如果滿足的條件只是限制在某個(gè)領(lǐng)域之中的話,那么就是局部收斂,對(duì)于局部收斂,也只需證明局部滿足上述條件,需要提一下的是,不動(dòng)點(diǎn)的迭代方案,在全局的情況下屬于線性收斂
3.Newton切線法
解非線性方程組,除了我們之前講述的迭代法以及二分法,還有Newton切線法,這一種方法是解非線性方程組常用的有效方法,特別的,當(dāng)初始值充分接近方程的根的時(shí)候,收斂的很快,基本思想是以直代曲,近似成線性方程來(lái)求解,下面給出迭代的格式
這里直接給出代碼來(lái)進(jìn)行模擬
public class NumericalTest {
public static void main(String[] args){
double x=1;
for(int i=0;i<20;i++){
System.out.println(x);
x=x-(function(x)/function2(x));
}
}
public static double function(double x){
return Math.pow(x,3)+2*Math.pow(x,2)-4;
}
//求導(dǎo)后的函數(shù)
public static double function2(double x){
return 3*Math.pow(x,2)+4*Math.pow(x,2);
}
}
比起二分法或者迭代法,它的收斂速度還是較為快速的,特別是當(dāng)初始值接近根的情況,更加明確的說(shuō),Newton切線在充分接近單根的情況下二次收斂,其他情況下線性收斂,充分接近重根的情況下線性收斂
下面針對(duì)Newton切線需要計(jì)算導(dǎo)數(shù)的這一缺點(diǎn),給出另外一種類似的方法,即割線法
這里直接給出迭代的格式
給出代碼的實(shí)現(xiàn)
public class NumericalTest {
public static void main(String[] args){
double x1=1,x2=0,temp;
for(int i=0;i<20;i++){
System.out.println(x2);
temp=x2;
x2=x2-(x2-x1)*(function(x2)/(function(x2)-function(x1)));
x1=temp;
}
}
public static double function(double x){
return Math.pow(x,3)+2*Math.pow(x,2)-4;
}
}
割線法的速度也是十分快,而且避免了導(dǎo)數(shù)的運(yùn)算
對(duì)于非線性方程求根還有同倫算法,擬牛頓法等,待補(bǔ)充
