非線性方程求根

14:01:22NumericalAnalysis1本章內容非線性方程求解二分法不動點迭代法及其加速牛頓法、弦截法、拋物線法求根問題的敏感性與多項式的零點非線性方程組的數值求解14:01:22NumericalAnalysis2本講內容迭代格式加速算法收斂性非線性方程求解介紹二分法及其收斂性不動點迭代及其加速14:01:22NumericalAnalysis3非線性方程數值解法考慮方程若f(x)是一次多項式，則稱為線性方程；否則稱為非線性方程f(x)=0若f(x)=a0+a1x+...+anxn，則稱為代數方程n=1,2,3,4時有相應的求根公式，n

5時不存在求根公式非線性方程可能有(無窮)多個解，求解時必須強調求解區間非線性方程一般沒有直接解法，通常都使用迭代算法求解14:01:22NumericalAnalysis4非線性方程數值解法幾個基本概念實根與復根

根的重數f(x)=(x–x*)m

·

g(x)且

g(x*)

0,則x*為f(x)=0的

m

重根有根區間：[a,b]上存在f(x)=0

的一個實根研究內容：在有根的前提下求出方程的近似根14:01:22NumericalAnalysis5二分法（對分法）基本思想將有根區間進行對分，找出根所在的小區間，然后再對該小區間對分，依次類推，直到有根區間的長度滿足給定的精度為止

數學原理：介值定理設

f(x)

在[a,b]

上連續，且f(a)f(b)<0，則由介值定理可得，在

(a,b)

內至少存在一點

使得f(

)=0

適用范圍求有根區間內的單重實根或奇重實根，即f(a)f(b)<0用二分法求根，通常先給出f(x)

草圖以確定有根區間14:01:22NumericalAnalysis6二分法算法：(二分法)(1)計算

f(a)，f(b)，若

f(a)

f(b)>0

，則停止計算(2)對k=1,2,...,maxit

計算

f(x)，其中若|f(x)|<

或b-a<

，停止計算，輸出近似解x若f(a)·f(x)<0，則令

b

=

x;否則令a

=

x優點：簡單易用，總是收斂缺點：收斂速度慢，不能求復根和偶數重根總結：一般用來計算解的一個粗糙估計14:01:22NumericalAnalysis7誤差分析記a1=a,b1=

b,第k步的有根區間為[ak,bk]結論：二分法總是收斂的14:01:22NumericalAnalysis8不動點迭代基本思想構造

f(x)=0

的一個等價方程：

(x)

的不動點f(x)=0x=

(x)等價變換f(x)

的零點14:01:22NumericalAnalysis9不動點迭代具體過程任取一個迭代初始值x0，計算得到一個迭代序列：x0，x1，x2，...，xn，...

k=0,1,2,......幾何含義：求曲線y=

(x)與直線y=x

的交點14:01:22NumericalAnalysis10xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=

(x)y=

(x)y=

(x)y=

(x)x0p0x1p1x0p0x1p1

x0p0x1p1

x0p0x1p1

x2

14:01:22NumericalAnalysis11連續性分析設

(x)

連續，若收斂，即，則即收斂性分析性質：若，則不動點迭代收斂，且x*是f(x)=0的解；否則迭代法發散。14:01:22NumericalAnalysis12解的存在唯一性定理：設

(x)

C[a,b]且滿足證明：P216對任意的x

[a,b]有

(x)

[a,b]存在常數0<L<1，使得任意的x,y

[a,b]有則

(x)

在[a,b]上存在唯一的不動點

x*解的存在唯一性14:01:22NumericalAnalysis13收斂性分析定理：設

(x)

C[a,b]且滿足證明：P217對任意的x

[a,b]有

(x)

[a,b]存在常數0<L<1，使得任意的x,y

[a,b]有則對任意初始值x0

[a,b]，不動點迭代xk+1=

(xk)收斂，且不動點迭代的收斂性14:01:22NumericalAnalysis14收斂性分析不動點迭代的收斂性若

(x)

C1[a,b]且對任意x

[a,b]有

|

’(x)|

L<1則上述定理中的結論成立。收斂性結論表明：收斂性與初始值的選取無關全局收斂14:01:22NumericalAnalysis15舉例例：求f(x)=x3–x–1=0

在區間[1,2]

中的根

(1)(2)

14:01:22NumericalAnalysis16局部收斂定義：設x*是

(x)的不動點，若存在x*的某個

-鄰域U(x*)

=[x*-

,x*+

]，對任意

x0

U(x*)，不動點迭代

xk+1=

(xk)

產生的點列都收斂到x*，則稱該迭代局部收斂。定理：設x*是

(x)的不動點，若

’(x)

在x*的某個鄰域內連續，且

|

’(x*)|<1則不動點迭代xk+1=

(xk)

局部收斂證明：P218局部收斂14:01:22NumericalAnalysis17收斂速度定義：設迭代xk+1=

(xk)

收斂到

(x)的不動點x*，記ek=xk

x*，若其中常數C>0，則稱該迭代為p階收斂。當p=1時稱為線性收斂，此時C<1

當p=2時稱為二次收斂，或平方收斂

當p>1時稱為超線性收斂二分法是線性收斂的若

’(x*)0，則不動點迭代xk+1=

(xk)線性收斂14:01:22NumericalAnalysis18收斂速度定理：設x*是

(x)

的不動點，若

(p)(x)在x*

的某鄰域內連續，且則迭代xk+1=

(xk)

是p階收斂的。證明：P21914:01:22NumericalAnalysis19Aitken加速Aitken加速若

’(x)變化不大，則可得：14:01:22NumericalAnalysis20Aitken加速收斂性：超線性收斂14:01:22NumericalAnalysis21Steffenson加速Steffenson加速將Aitken加速技巧與不動點迭代相結合k=0,1,2,...迭代函數：14:01:22NumericalAnalysis22Steffenson加速定理：若x*是

(x)

的不動點，則x*是

(x)

的不動點。反之，若x*是

(x)

的不動點，且

”(x)存在，

’(x*)1，則x*是

(x)

的不動點，且Steffenson加速迭代是二階收斂的。若原迭代是p

階收斂的，則Steffenson加速后p+1

階收斂

原來不收斂的迭代，Steffenson加速可能收斂14:01:22NumericalAnalysis23舉例例：用Steffenson加速法求f(x)=x3–x–1=0

在區間[1,2]

中的根（取

(x)=x3–1）clear;clcf=inline('x^3-x-1','x');g=inline('x^3-1','x');fprintf('Truesolution:x=%.4f\n',fzero(f,[1,2]))n=5;%設置迭代步數x=1.5;%迭代初始值%不動點迭代fprintf('普通不動點迭代\n')fork=1:nx=g(x);fprintf('k=%d,x=%.4f\n',k,x);end%Steffenson加速x=1.5;%迭代初始值fprintf('Steffenson加速迭代\n')fork=1:nx1=g(x);x2=g(x1);x=x-(x1-x)^2/(x2-2*x1+x);fprintf('k=%d,x=%.4f\n',k,x);end14:01:22NumericalAnalysis24例：用Steffenson加速法求f(x)=3x2–ex=0

在區間[3,4]

中的根（取

(x)=2ln(x)

+ln3）clear;clcf=inline('3*x^2-exp(x)','x');g=inline('2*log(x)+log(3)','x');xt=fzero(f,[3,4]);fprintf('Truesolution:x=%.7f\n',xt)n=50;%設置迭代步數tol=1e-6;%不動點迭代x=3.5;%迭代初始值fprintf('普通不動點迭代\n')fork=1:nx=g(x);fprintf('k=%2d,x=%.7f\n',k,x);ifabs(x-xt)<tol,break,endend

%Steffenson加速x=3.5;%迭代初始值fprintf('Steffenson加速迭代\n')fork=1:nx1=g(x);x2=g(x1);x=x-(x1-x)^2/(x2-2*x1+x);fprintf('k=%2d,x=%.7f\n',k,x);ifabs(x-xt)<tol,break,endend14:01:22NumericalAnalysis25本講內容

Newton法及其收斂性牛頓下山法弦截法與拋物線法14:01:22NumericalAnalysis26Newton法基本思想將非線性方程線性化設xk

是f(x)=0的近似根，將f(x)在xk

處Taylor展開令：條件：

f’(x)014:01:22NumericalAnalysis27Newton法xyx*xkxk+114:01:22NumericalAnalysis28Newton法算法：(Newton法)(1)任取迭代初始值

x0(2)對k=1,2,...,maxit，計算判斷收斂性，若收斂，則停止計算，輸出近似解14:01:22NumericalAnalysis29收斂性k=0,1,2,...迭代函數牛頓法至少二階局部收斂14:01:22NumericalAnalysis30舉例例：用Newton法求f(x)=xex

–1=0

的解%Newton迭代clear;clcf=inline('x*exp(x)-1','x');df=inline('exp(x)*(1+x)','x');n=10;tol=1e-6;x0=0.5;%迭代初始值fork=1:nx=x0-f(x0)/df(x0);fprintf('k=%2d,x=%.7f\n',k,x);ifabs(x-x0)<tol,break,endx0=x;end14:01:22NumericalAnalysis31舉例例(P224)：用Newton法求f(x)=x2

–C=0

的正根解：對任意x0>0，總有|q|<1，即牛頓法收斂14:01:22NumericalAnalysis32牛頓法

牛頓的優點牛頓法是目前求解非線性方程(組)的主要方法至少二階局部收斂，收斂速度較快，特別是當迭代點充分靠近精確解時。

牛頓的缺點

對重根收斂速度較慢（線性收斂）

對初值的選取很敏感，要求初值相當接近真解先用其它算法獲取一個近似解，然后使用牛頓法

需要求導數！14:01:22NumericalAnalysis33簡化的Newton法線性收斂簡化的Newton法

基本思想：用f’(x0)

替代所有的f’(xk)14:01:22NumericalAnalysis34Newton下山法下山因子的取法：

從

=1開始，逐次減半，直到滿足下降條件基本思想：要求每一步迭代滿足下降條件具體做法：加下山因子

Newton下山法保證全局收斂14:01:22NumericalAnalysis35重根情形且

解法一：直接使用Newton法線性收斂

解法二：改進的Newton法二階收斂缺點：需要知道m

的值重根情形14:01:22NumericalAnalysis36重根情形令x*是

(x)=0的單重根

解法三：用Newton法解

(x)=0迭代格式：14:01:22NumericalAnalysis37舉例例：求x4-4x2＋

4=0

的二重根(1)普通Newton法(2)改進的Newton法(3)用Newton法解

(x)=014:01:22NumericalAnalysis38%重根clear;clcf=inline('x^4-4*x^2+4','x');g1=inline('x-(x^2-2)/(4*x)','x');g2=inline('x-(x^2-2)/(2*x)','x');g3=inline('x-x*(x^2-2)/(x^2+2)','x');fprintf('Truesolution:x=%.7f\n',sqrt(2));n=10;x0=1.5;%迭代初始值x1=x0;x2=x0;x3=x0;fork=1:nx1=g1(x1);x2=g2(x2);x3=g3(x3);fprintf('k=%2d,x1=%.7f,x2=%.7f,x3=%.7f\n',k,x1,x2