第九講--求代數(shù)方程的近似根(解)

1、求代數(shù)方程的近似根(解)數(shù)學(xué)實(shí)驗(yàn)q 問題背景和實(shí)驗(yàn)?zāi)康膗 解方程（代數(shù)方程）是最常見的數(shù)學(xué)問題之一，也是眾多應(yīng)用領(lǐng)域中不可避免的問題之一。u 目前還沒有一般的解析方法來求解非線性方程，但如果在任意給定的精度下，能夠解出方程的近似解，則可以認(rèn)為求解問題已基本解決，至少可以滿足實(shí)際需要。u 本實(shí)驗(yàn)主要介紹一些有效的求解方程的數(shù)值方法：對(duì)分法，迭代法 和 牛頓法。同時(shí)要求大家學(xué)會(huì)如何利用Matlab 來求方程的近似解。相關(guān)概念相關(guān)概念0( )f x u 如果如果 f(x) 是一次多項(xiàng)式，稱上面的方程為是一次多項(xiàng)式，稱上面的方程為線性方線性方程程；否則稱之為；否則稱之為非線性方程非線性方程。q 線性方

2、程線性方程 與與 非線性方程非線性方程q 基本思想基本思想對(duì)分法對(duì)分法將有根區(qū)間進(jìn)行對(duì)分，判斷出解在某個(gè)分段內(nèi)，然后再將有根區(qū)間進(jìn)行對(duì)分，判斷出解在某個(gè)分段內(nèi)，然后再對(duì)該段對(duì)分，依次類推，直到滿足給定的精度為止。對(duì)該段對(duì)分，依次類推，直到滿足給定的精度為止。q 適用范圍適用范圍求有根區(qū)間內(nèi)的求有根區(qū)間內(nèi)的 單根單根 或或 奇重實(shí)根奇重實(shí)根。q 數(shù)學(xué)原理：數(shù)學(xué)原理：介值定理介值定理設(shè)設(shè) f(x) 在在 a, b 上連續(xù)，且上連續(xù)，且 f(a) f(b)0，則由介值定，則由介值定理可得，在理可得，在 (a, b) 內(nèi)至少存在一點(diǎn)內(nèi)至少存在一點(diǎn) 使得使得 f( )=0。q 具體步驟具體步驟對(duì)分法對(duì)分

3、法設(shè)方程在區(qū)間設(shè)方程在區(qū)間 a,b 內(nèi)連續(xù)，且內(nèi)連續(xù)，且 f(a)f(b)0，給定，給定精度要求精度要求 ，若有，若有 |f(x)| ，則則 x 就是我們所需要就是我們所需要的的 f(x) 在區(qū)間在區(qū)間 (a,b) 內(nèi)的內(nèi)的 近似根近似根。；，計(jì)算令)( 2/ )( ) 1 (00 xfbax；輸出結(jié)果停止計(jì)算，的近似根，就是我們所要，則若000 | )(| )2(xxxxf；否則令，令若bbxaxbaaxfaf1010110, ;, 0)()( )3(；輸出結(jié)果，則停止計(jì)算，若令11111 | )(|, 2/ )( )4(xxxfbax；否則令，令若1212121211, ;, 0)()(

4、bbxaxbaaxfaf. .q 收斂性分析收斂性分析對(duì)分法收斂性對(duì)分法收斂性=11111 11|()()()22 22kkkkkkxbababa 設(shè)方程的根為設(shè)方程的根為 x* (ak , bk ) ，又，又 ，所以，所以2kkkabx 0(k )對(duì)分法總是收斂的對(duì)分法總是收斂的u 但對(duì)分法的收斂速度但對(duì)分法的收斂速度較慢較慢u 通常用來試探實(shí)根的通常用來試探實(shí)根的分布區(qū)間分布區(qū)間， 或給出根的一個(gè)較為或給出根的一個(gè)較為粗糙的近似粗糙的近似。根據(jù)上面的算法，我們可以得到一個(gè)每次縮小一半的根據(jù)上面的算法，我們可以得到一個(gè)每次縮小一半的區(qū)間序列區(qū)間序列 ak , bk ，在，在 (ak , bk

5、 ) 中含有方程的根。中含有方程的根。迭代法迭代法q 基本思想基本思想u 構(gòu)造構(gòu)造 f (x) = 0 的一個(gè)等價(jià)方程：的一個(gè)等價(jià)方程： ( )xx u 從某個(gè)近似根從某個(gè)近似根 x0 出發(fā)，計(jì)算出發(fā)，計(jì)算得到一個(gè)迭代序列得到一個(gè)迭代序列 0kkx 1()kkxx k = 0, 1, 2, . . (x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)f (x) = 0 x = (x)等價(jià)變換等價(jià)變換f (x) 的零點(diǎn)的零點(diǎn)u 若若 收斂，即收斂，即 ，假設(shè)，假設(shè) (x) 連續(xù)，則連續(xù)，則q 收斂性分析收斂性分析迭代法的收斂性迭代法的收斂性 1limlim ()limkkkkkkxxx lim*kkxx *x( *)x k

6、x*( *)xx ( *)0f x 即即注：若得到的點(diǎn)列發(fā)散，則迭代法失效！注：若得到的點(diǎn)列發(fā)散，則迭代法失效！q 定義：定義：迭代法收斂性判斷迭代法收斂性判斷q 定理定理 2：如果定理如果定理 1 的條件成立，則有如下估計(jì)的條件成立，則有如下估計(jì)10|* |1kkqxxxxq 11|* |1kkkxxxxq 如果存在如果存在 x* 的的某個(gè)某個(gè) 鄰域鄰域 =(x*- , x* + ), 使使得對(duì)得對(duì) x0 開始的迭代開始的迭代 xk+1 = (xk) 都收斂都收斂, 則稱該迭代法在則稱該迭代法在 x* 附近附近局部收斂局部收斂。q 定理定理 1：設(shè)設(shè) x* = (x*)，的的某個(gè)某個(gè) 鄰域鄰

7、域 內(nèi)連續(xù)，且對(duì)內(nèi)連續(xù)，且對(duì) x 都有都有 | (x)| q 1, 則對(duì)則對(duì) x0 ，由由迭迭代代 xk+1 = (xk) 得到的點(diǎn)列都收斂。得到的點(diǎn)列都收斂。迭代法收斂性判斷迭代法收斂性判斷10|* |1kkqxxxxq q 定理定理 3：已知方程已知方程 x = (x)，且且(1) 對(duì)對(duì) x a, b，有有 (x) a, b；對(duì)對(duì) x a, b，有有| (x)| q p=2,-1,0,3; q=2,1; k=conv(p,q); q 多項(xiàng)式除法運(yùn)算：多項(xiàng)式除法運(yùn)算：k,r = deconv(p,q)其中其中 k 返回的是多項(xiàng)式返回的是多項(xiàng)式 p 除以除以 q 的商的商，r 是余式是余式。k

8、,r=deconv(p,q)p=conv(q,k)+r多項(xiàng)式的多項(xiàng)式的求求導(dǎo)導(dǎo)q polyderk=polyder(p) : 多項(xiàng)式多項(xiàng)式 p 的導(dǎo)數(shù)；的導(dǎo)數(shù)；k=polyder(p,q): p*q 的導(dǎo)數(shù)；的導(dǎo)數(shù)；k,d=polyder(p,q): p/q 的導(dǎo)數(shù)，的導(dǎo)數(shù)，k 是分子，是分子，d 是分母是分母 k1=polyder(2,-1,0,3); k2=polyder(2,-1,0,3,2,1); k2,d=polyder(2,-1,0,3,2,1);例：已知例：已知 ， ， 求求32)(23xxxp12)( xxq)/( ,)( , qpqpp多項(xiàng)式的多項(xiàng)式的值值q 計(jì)算計(jì)算多項(xiàng)式多

9、項(xiàng)式在給定點(diǎn)的值在給定點(diǎn)的值u 代數(shù)多項(xiàng)式代數(shù)多項(xiàng)式求值求值y = polyval(p,x): 計(jì)算多項(xiàng)式計(jì)算多項(xiàng)式 p 在在 x 點(diǎn)的值點(diǎn)的值注：若注：若 x 是向量或矩陣，則采用是向量或矩陣，則采用數(shù)組運(yùn)算數(shù)組運(yùn)算 (點(diǎn)運(yùn)算點(diǎn)運(yùn)算)！ p=2,-1,0,3; x=2; y=polyval(p,x) x=-1, 2;-2,1; y=polyval(p,x)例：已知例：已知 ，分別取，分別取 x=2 和一個(gè)和一個(gè) 2 2 矩陣，矩陣， 求求 p(x) 在在 x 處的值處的值32)(23xxxp多項(xiàng)式的多項(xiàng)式的值值u 矩陣多項(xiàng)式矩陣多項(xiàng)式求值求值Y=polyvalm(p,X)l 采用的是普通矩陣

10、運(yùn)算采用的是普通矩陣運(yùn)算l X 必須是方陣必須是方陣?yán)阂阎阂阎?，則，則32)(23xxxppolyvalm(p,A) = 2*A*A*A - A*A + 3*eye(size(A) polyval(P,A) = 2*A.*A.*A - A.*A + 3*ones(size(A) p=2,-1,0,3; x=-1, 2;-2,1;polyval(p,x) polyvalm(p,x)多項(xiàng)式的多項(xiàng)式的零點(diǎn)零點(diǎn)x=roots(p)：若若 p 是是 n 次多項(xiàng)式，則輸出次多項(xiàng)式，則輸出是是 p=0 的的 n 個(gè)根組成的個(gè)根組成的 n 維向量。維向量。)()()(21nxxxxxxxp若已知多項(xiàng)式

11、的全部零點(diǎn)，則可用若已知多項(xiàng)式的全部零點(diǎn)，則可用 poly 函數(shù)給出該多項(xiàng)式函數(shù)給出該多項(xiàng)式p=poly() p=2,-1,0,3; x=roots(p)例：已知例：已知 ，求，求 p(x) 的零點(diǎn)。的零點(diǎn)。32)(23xxxp poly2sym(p,x) k = conv(p,q)k,r = deconv(p,q) k = polyder(p) k = polyder(p,q)k,d = polyder(p,q) y = polyval(p,x) Y = polyvalm(p,X) x = roots(p)多項(xiàng)式多項(xiàng)式運(yùn)算運(yùn)算小結(jié)小結(jié)多項(xiàng)式運(yùn)算中，多項(xiàng)式運(yùn)算中，使用的是多項(xiàng)式使用的是多項(xiàng)式

12、系數(shù)向量，不涉及符號(hào)計(jì)算！不涉及符號(hào)計(jì)算！線性方程組求解線性方程組求解q 線性方程組求解線性方程組求解linsolve(A,b)：解線性方程組解線性方程組 bAx 例：解方程組例：解方程組 A=1 2 1; 1 0 1; 1 3 0; b=2;3;8; x=linsolve(A,b)22338xyzxzxy b是列向量！是列向量！非線性方程的非線性方程的根根q Matlab 非線性方程的數(shù)值求解非線性方程的數(shù)值求解fzero(f,x0)：求方程求方程 f=0 在在 x0 附近的根。附近的根。l 方程可能有多個(gè)根，但方程可能有多個(gè)根，但 fzero 只給出距離只給出距離 x0 最近的一個(gè)最近的一

13、個(gè)l fzero 先找出一個(gè)包含先找出一個(gè)包含 x0 的區(qū)間，使得的區(qū)間，使得 f 在這個(gè)區(qū)間在這個(gè)區(qū)間兩個(gè)端點(diǎn)上的函數(shù)值異號(hào)，然后再在這個(gè)區(qū)間內(nèi)尋找方程兩個(gè)端點(diǎn)上的函數(shù)值異號(hào)，然后再在這個(gè)區(qū)間內(nèi)尋找方程 f=0 的根；如果找不到這樣的區(qū)間，則返回的根；如果找不到這樣的區(qū)間，則返回 NaN。l x0 是一個(gè)標(biāo)量，不能缺省是一個(gè)標(biāo)量，不能缺省l 由于由于 fzero 是根據(jù)函數(shù)是否穿越橫軸來決定零點(diǎn)，因是根據(jù)函數(shù)是否穿越橫軸來決定零點(diǎn)，因此它無法確定函數(shù)曲線僅觸及橫軸但不穿越的零點(diǎn)，如此它無法確定函數(shù)曲線僅觸及橫軸但不穿越的零點(diǎn)，如 |sin(x)| 的所有零點(diǎn)。的所有零點(diǎn)。非線性方程的非線性方

14、程的根根q fzero 的另外一種調(diào)用方式的另外一種調(diào)用方式fzero(f,a,b)l 方程在方程在 a,b 內(nèi)可能有多個(gè)根，但內(nèi)可能有多個(gè)根，但 fzero 只給出一個(gè)只給出一個(gè)l 求方程求方程 f=0 在在 a,b 區(qū)間內(nèi)區(qū)間內(nèi)的根。的根。q 參數(shù)參數(shù) f 可通過以下方式給出：可通過以下方式給出：l fzero(x3-3*x+1,2); l f=inline(x3-3*x+1); fzero(f,2)l fzero(x)x3-3*x+1,2);l f 不是方程！也不能使用符號(hào)表達(dá)式！不是方程！也不能使用符號(hào)表達(dá)式！例：例： fzero(sin(x),10) fzero(sin,10) fz

15、ero(x3-3*x+1,1) fzero(x3-3*x+1,1,2) fzero(x3-3*x+1=0,1)X fzero(x3-3*x+1,-2,0) f=inline(x3-3*x+1); fzero(f,-2,0)注意：注意：fzero只能求解單變量的方程，沒法求解復(fù)數(shù)、只能求解單變量的方程，沒法求解復(fù)數(shù)、多變量以及方程組等。多變量以及方程組等。在搜索過程中出現(xiàn)在搜索過程中出現(xiàn)inf,nan,復(fù)數(shù)將會(huì)終止計(jì)算，復(fù)數(shù)將會(huì)終止計(jì)算，就是不能求解復(fù)數(shù)解，并且每次子返回一個(gè)解就是不能求解復(fù)數(shù)解，并且每次子返回一個(gè)解 Matlab 符號(hào)方程求解符號(hào)方程求解器器s=solve(f,v)：求方程關(guān)于

16、指定自變量的解；求方程關(guān)于指定自變量的解；s=solve(f)：求方程關(guān)于求方程關(guān)于默認(rèn)自變量默認(rèn)自變量的解。的解。l f 可以是用字符串表示的可以是用字符串表示的方程方程，或符號(hào)，或符號(hào)表達(dá)式表達(dá)式；l 若若 f 中不含等號(hào)，則表示解方程中不含等號(hào)，則表示解方程 f=0。q solve例：解方程例：解方程 x3-3*x+1=0 syms x; f=x3-3*x+1; s=solve(f,x) s=solve(x3-3*x+1,x) s=solve(x3-3*x+1=0,x)Matlab 符號(hào)方程求解符號(hào)方程求解器器q solve 也可以用來解方程組也可以用來解方程組solve( f1 , f

17、2 , . , fN , v1 , v2 , . , vN)求解由求解由 f1 , f2 , . , fN 確定的方程組關(guān)于確定的方程組關(guān)于 v1 , v2 , . , vN 的解的解例：解方程組例：解方程組 x,y,z=solve(x+2*y-z=27,x+z=3, . x2+3*y2=28,x,y,z)222273 328 xyzxzxy 輸出變量的順序要書寫正確！輸出變量的順序要書寫正確！例：解方程組例：解方程組 關(guān)于關(guān)于y,z的解的解y,z=solve(u*y2+v*z+w=0,y+z+w=0,y,z )S=solve(u*y2+v*z+w=0,y+z+w=0,y,z )disp(S.

18、y),disp(S.y),disp(S.z),disp(S.z)200uyvzwyzw solve 在得不到解析解時(shí)，會(huì)給出數(shù)值解。在得不到解析解時(shí)，會(huì)給出數(shù)值解。例：解方程組例：解方程組 x,y,z=solve(x+2*y-z=27,x+z=3, . x5+3*y2=28,x,y,z)522273 328 xyzxzxy x,fval,flag,out=fsolve(fun,x0,options)：參數(shù)大部分與參數(shù)大部分與fzero相同，優(yōu)化參數(shù)更多，更靈活。相同，優(yōu)化參數(shù)更多，更靈活。注意注意x0的長(zhǎng)度必須與變量的個(gè)數(shù)相等。的長(zhǎng)度必須與變量的個(gè)數(shù)相等。它與它與fzero的區(qū)別是，算法不同，的區(qū)別是，算法不同，fsolve的功能強(qiáng)大多很多，它可的功能強(qiáng)大多很多，它可以直接方便的求解多變量方程組，線性和非線性等，甚至求解復(fù)以直接方便的求解多變量方程組，線性和非線性等，甚至求解復(fù)數(shù)方程。數(shù)方程。fun同樣可以是句柄、同樣可以是句柄、inline函數(shù)或函數(shù)或M文件，但是一般文件，但是一般M文件比較文件比較多，這是由于多，這是由于fsolve是解方程組的，目標(biāo)函數(shù)一般比較煩，直接是解方程組的，目標(biāo)函數(shù)一般比較煩，直接寫比較困難寫比較困難q fsolve一般非線性方程數(shù)值解例：解方程組例：解