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

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

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

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

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

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

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

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

8、,r=deconv(p,q)p=conv(q,k)+r多項式的多項式的求求導導q polyderk=polyder(p) : 多項式多項式 p 的導數；的導數；k=polyder(p,q): p*q 的導數；的導數；k,d=polyder(p,q): p/q 的導數，的導數，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多項式的多項式的值值q 計算計算多項式多

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

10、運算采用的是普通矩陣運算l X 必須是方陣必須是方陣例：已知例：已知 ，則，則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)多項式的多項式的零點零點x=roots(p)：若若 p 是是 n 次多項式，則輸出次多項式，則輸出是是 p=0 的的 n 個根組成的個根組成的 n 維向量。維向量。)()()(21nxxxxxxxp若已知多項式

11、的全部零點，則可用若已知多項式的全部零點，則可用 poly 函數給出該多項式函數給出該多項式p=poly() p=2,-1,0,3; x=roots(p)例：已知例：已知 ，求，求 p(x) 的零點。的零點。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)多項式多項式運算運算小結小結多項式運算中，多項式運算中，使用的是多項式使用的是多項式

12、系數向量，不涉及符號計算！不涉及符號計算！線性方程組求解線性方程組求解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 非線性方程的數值求解非線性方程的數值求解fzero(f,x0)：求方程求方程 f=0 在在 x0 附近的根。附近的根。l 方程可能有多個根，但方程可能有多個根，但 fzero 只給出距離只給出距離 x0 最近的一個最近的一

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

14、程的根根q fzero 的另外一種調用方式的另外一種調用方式fzero(f,a,b)l 方程在方程在 a,b 內可能有多個根，但內可能有多個根，但 fzero 只給出一個只給出一個l 求方程求方程 f=0 在在 a,b 區(qū)間內區(qū)間內的根。的根。q 參數參數 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 不是方程！也不能使用符號表達式！不是方程！也不能使用符號表達式！例：例： 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只能求解單變量的方程，沒法求解復數、只能求解單變量的方程，沒法求解復數、多變量以及方程組等。多變量以及方程組等。在搜索過程中出現在搜索過程中出現inf,nan,復數將會終止計算，復數將會終止計算，就是不能求解復數解，并且每次子返回一個解就是不能求解復數解，并且每次子返回一個解 Matlab 符號方程求解符號方程求解器器s=solve(f,v)：求方程關于

16、指定自變量的解；求方程關于指定自變量的解；s=solve(f)：求方程關于求方程關于默認自變量默認自變量的解。的解。l f 可以是用字符串表示的可以是用字符串表示的方程方程，或符號，或符號表達式表達式；l 若若 f 中不含等號，則表示解方程中不含等號，則表示解方程 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 符號方程求解符號方程求解器器q solve 也可以用來解方程組也可以用來解方程組solve( f1 , f

17、2 , . , fN , v1 , v2 , . , vN)求解由求解由 f1 , f2 , . , fN 確定的方程組關于確定的方程組關于 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 輸出變量的順序要書寫正確！輸出變量的順序要書寫正確！例：解方程組例：解方程組 關于關于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 在得不到解析解時，會給出數值解。在得不到解析解時，會給出數值解。例：解方程組例：解方程組 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)：參數大部分與參數大部分與fzero相同，優(yōu)化參數更多，更靈活。相同，優(yōu)化參數更多，更靈活。注意注意x0的長度必須與變量的個數相等。的長度必須與變量的個數相等。它與它與fzero的區(qū)別是，算法不同，的區(qū)別是，算法不同，fsolve的功能強大多很多，它可的功能強大多很多，它可以直接方便的求解多變量方程組，線性和非線性等，甚至求解復以直接方便的求解多變量方程組，線性和非線性等，甚至求解復數方程。數方程。fun同樣可以是句柄、同樣可以是句柄、inline函數或函數或M文件，但是一般文件，但是一般M文件比較文件比較多，這是由于多，這是由于fsolve是解方程組的，目標函數一般比較煩，直接是解方程組的，目標函數一般比較煩，直接寫比較困難寫比較困難q fsolve一般非線性方程數值解例：解方程組例：解