1、第二章 非線性方程數(shù)值解法 /* Numerical Solutions of Nonlinear Equations*/本章主要內(nèi)容：1、二分法2、不動點(diǎn)迭代結(jié)構(gòu)及其收斂性鑒定（重點(diǎn)）3、Newton和Steffensen迭代4、弦割法與拋物線法第1頁第1頁歷史背景 代數(shù)方程求根問題是一個古老數(shù)學(xué)問題。理論上， 次代數(shù)方程在復(fù)數(shù)域內(nèi)一定有 個根(考慮重?cái)?shù))。早在16世紀(jì)就找到了三次、四次方程求根公式，但直到19世紀(jì)才證實(shí)不小于等于5次普通代數(shù)方程式不能用代數(shù)公式求解，而對于超越方程就復(fù)雜多，假如有解，其解也許是一個或幾種，也也許是無窮多個。普通也不存在根解析表示式。因此需要研究數(shù)值辦法求得滿

2、足一定精度要求根近似解。 第2頁第2頁求方程 幾何意義基本定理 假如函數(shù) 在 上連續(xù)，且則至少有一個數(shù) 使得 ，若同時 一階導(dǎo)數(shù) 在 內(nèi)存在且保持定號，即 (或 )則這樣 在 內(nèi)唯一。 abx*第3頁第3頁1 二分法 /* Bisection Method */原理：若 f Ca, b，且 f (a) f (b) 0，則 f 在 (a, b) 上至少有一實(shí)根?；舅枷耄褐鸩綄^(qū)間分半，通過判別區(qū)間端點(diǎn)函數(shù)值符號，進(jìn)一步搜索有根區(qū)間，將有根區(qū)間縮小到充足小，從而求 出滿足給定精度根 近似值。終止法則？abx1x2abWhen to stop?或不能確保 x 精度x*第4頁第4頁 二分法算法給定區(qū)

3、間a,b ，求f(x)=0 在該區(qū)間上根x.輸入: a和b; 允許誤差 TOL; 最大對分次數(shù) Nmax.輸出: 近似根 x.Step 1 Set k = 1;Step 2 Compute x=f(a+b)/2);Step 3 While ( k Nmax) do steps 4-6 Step 4 If |x| TOL , STOP; Output the solution x. Step 5 If x*f(a)0 , Set b=x; Else Set a=x; Step 6 Set k=k+1; Compute x=f(a+b)/2);Go To Step 3 ;Step 7 Output

4、 the solution of equation: x; STOP.第5頁第5頁3、由二分法過程可知：4、對分次數(shù)計(jì)算公式：1、2、令第6頁第6頁解：例1：用二分法求方程 在區(qū)間 上根，誤差限為 ，問至少需對分多少次？第7頁第7頁簡樸; 對f (x) 要求不高(只要連續(xù)即可) .無法求復(fù)根及偶重根收斂慢 注：用二分法求根，最好先給出 f (x) 草圖以擬定根大約位置?；蛴盟阉鞒绦?，將a, b分為若干小區(qū)間，對每一個滿足 f (ak)f (bk) 0 區(qū)間調(diào)用二分法程序，可找出區(qū)間a, b內(nèi)多個根，且不必要求 f (a)f (b) 0 。長處缺點(diǎn)第8頁第8頁2 迭代法理論 /* Theory

5、of Iteration Method*/f (x) = 0 x = g (x)（迭代函數(shù)）等價變換思緒從一個初值 x0 出發(fā)，計(jì)算 x1 = g(x0), x2 = g(x1), , xk+1 = g(xk), 若 收斂，即存在 x* 使得 ，且 g 連續(xù)，則由 可知 x* = g(x* )，即x* 是 g 不動點(diǎn)，也就是f 根。f (x) 根g (x) 不動點(diǎn)一、不動點(diǎn)迭代 /*Fixed-Point Iteration*/第9頁第9頁xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1x0p0 x1p1

6、x0p0 x1p1x0p0 x1p1幾何意義第10頁第10頁例2：已知方程 在 上有一個根（正根）下面選取5種迭代格式：1、即2、即3、即4、即5、即第11頁第11頁取計(jì)算結(jié)果下列：法1法4法3法2法5第12頁第12頁Lipschitz條件成立充足條件考慮方程 x = g(x), 若( I ) 當(dāng) xa, b 時， g(x)a, b；( II ) 0 L 1 使得 對 xa, b 成立。則任取 x0a, b，由 xk+1 = g(xk) 得到序列 收斂于g(x) 在a, b上唯一不動點(diǎn)。并且有誤差預(yù)計(jì)式：( k = 1, 2, )且存在極限連續(xù)時第13頁第13頁證實(shí)： g(x) 在a, b上存在不動點(diǎn)？令有根 不動點(diǎn)唯一？反證：若不然，設(shè)尚有 ，則在和之間。而 當(dāng)k 時， xk 收斂到 x* ？第14頁第14頁L 越 收斂越快可用 來控制收斂精度小注：條件 ( II ) 可改為 在a, b 滿足Lipschitz條件,定理結(jié)論仍然成立(定理2.3)。第15頁第15頁 算法: 不動點(diǎn)迭代給定初始近似值 x0 ，求x = g(x) 解.輸入: 初始近似值 x0; 允許誤差 TOL; 最大迭代次數(shù) Nmax.輸出: 近似解 x 或失敗信息.Step 1 Set i = 1;Step 2 While ( i Nmax) do steps 3-6Step 3 Set x = g(x0