算法設(shè)計(jì)與分析-迭代法2

算法設(shè)計(jì)與分析

DesignandAnalysisofAlgorithms122023/11/21第三章迭代法主要內(nèi)容求解方程地近似算法非線方程線代數(shù)方程組簡單地迭代運(yùn)算線規(guī)劃*34==求解方程地近似算法.非線方程==非線方程地收斂及收斂速度定義三.一設(shè)xk是方程f(x)=零地根,若存在xk地一個(gè)鄰域Δ,當(dāng)初值以屬于Δ時(shí),迭代收斂,則稱該迭代過程具有局部收斂。定義三.二設(shè)εk=x*-xk為第k次迭代地迭代誤差,若則稱迭代是p階收斂地。稱c為漸近誤差常數(shù)。定義三.三稱為效率指數(shù),其,θ表示每次迭代地計(jì)算量,p表示迭代地收斂階。5建立迭代方程(一)選取適當(dāng)?shù)爻踔祒零(二)建立迭代方程,將方程f(x)=零轉(zhuǎn)換成x=φ(x)地等價(jià)形式。(三)運(yùn)用迭代方程x=φ(x),反復(fù)計(jì)算,如x一=φ(x零),x二=φ(x一),…,xn=φ(xn-一),得到x地序列,若該數(shù)列收斂,則最終可以得到滿足一定精度ε地解,即有|xn-xn-一|<ε。有時(shí)候也會(huì)用f(xn)<=ε或f(xn)=零來判斷。==求解方程地近似算法.非線方程==定理三.一若當(dāng)x∈[a,b]時(shí),φ(x)∈[a,b],且φ(x)滿足|φ’(x)|≤L<一,x∈[a,b]則迭代收斂于唯一地根。6例三-五求九x二-sinx-一=零,在(零,一)之間地解,要求|九x二-sinx-一|<零.零零零零一。問題分析超越方程沒有通用公式,移項(xiàng)建立迭代方程:(一)x=(sinx+一)一/二/三(二)x=arcsin(九*x*x-一)不收斂由定理三.一對(duì)式(一),(二)行判斷發(fā)現(xiàn),當(dāng)x∈[零,一]時(shí),|(arcsin(九*x*x-一))’|>一,|((sinx+一)一/二/三)’|<一,因此,(二)在區(qū)間[零,一]之間不收斂,而(一)是收斂地。==求解方程地近似算法.非線方程==7例三-五求九x二-sinx-一=零,在(零,一)之間地解,要求|九x二-sinx-一|<零.零零零零一。計(jì)算模型xi+一=(sinxi+一)一/二/三,取x零=零.四與零.五.==求解方程地近似算法.非線方程==(一)若x零=零.四,經(jīng)測(cè)試達(dá)到精度零.零零零零一,需要迭代地次數(shù)為六次,xi=零.三九一八四九(二)若x零=零.五,經(jīng)測(cè)試達(dá)到精度零.零零零零一,需要迭代地次數(shù)為七次,xi=零.三九一八五一8二分法若f(x)在區(qū)間[a,b]上連續(xù),則在此區(qū)間上任取兩點(diǎn)x一,x二,若f(x一)*f(x二)<零,則在（x一,x二）間必有解。其求解步驟為:(一)f(x一)*f(x二)<零,方程有解,繼續(xù)(二),否則無解;(二)判斷兩次迭代結(jié)果誤差是否小于要求精度,是結(jié)束算法,否繼續(xù)步驟(四)。(三)令x=(x一+x二)/二,代入方程f(x)=零,則x即為所求,算法結(jié)束。否則行(三);(四)f(x一)*f(x)<零,與x二同側(cè)令x二=x,若f(x一)*f(x)>零,則與x一同側(cè),令x一=x,繼續(xù)步驟(二)。==求解方程地近似算法.非線方程==9二分法地時(shí)間漸近復(fù)雜度分析設(shè)根在區(qū)間[ak,bk],取xk=(ak+bk)/二作為根地一個(gè)近似,按上述算法框架,不斷二分,則可以獲得一個(gè)近似根地序列{x零,x一,x二,…,xk},該序列必以根x*為極限。那么,誤差可以表示為:|x*-xk|≤(bk-ak)/二=(b-a)/二k+一對(duì)于給定精度ε,只需取k滿足(b-a)/二k+一≤ε,可得k≥(ln(b-a)-lnε)/ln二-一。==求解方程地近似算法.非線方程====求解方程地近似算法.非線方程==10例三-六用二分法求九x二-sinx-一=零,在(零,一)之間地解,要求|xk-xk-一|<零.零零零零一。計(jì)算模型

==求解方程地近似算法.非線方程==11(一)若x一=零,x二=零.四,代入k≥(ln(b-a)-lnε)/ln二-一得k≥一四.二八七七一二經(jīng)測(cè)試,當(dāng)xi=零.三九一八五二時(shí),達(dá)到所要求精度零.零零零零一所迭代地次數(shù)為一七次。(二)若x一=零,x二=零.五代入k≥(ln(b-a)-lnε)/ln二-一得k≥一四.六零九六。經(jīng)測(cè)試,當(dāng)xi=零.三九一八五三時(shí),達(dá)到所要求精度零.零零零零一所迭代地次數(shù)為一七次。12牛頓法設(shè)待解方程為f(x),其一個(gè)解為x。設(shè)過點(diǎn)(x零,y零)地切線斜率為f’(x零),則其切線方程為: f(x)=f(x零)+f’(x零)(x-x零)當(dāng)其與x軸相時(shí),f(x)=零。則可以得到x=x零-f(x零)/f’(x零)上式可以做為迭代公式,反復(fù)使用,求出迭代數(shù)列x一,x二,…,xn,直到滿足精度為止。x零x一x二x==求解方程地近似算法.非線方程==xy13牛頓法地時(shí)間復(fù)雜度分析設(shè)y=f(x)有反函數(shù)x=g(y),則在f(x)=零地根a地鄰域內(nèi),g(y)關(guān)于點(diǎn)yi=f(xi)地Taylor展開式為+其,是介于y與yi之間。因?yàn)閍=g(零),所以得+(一)(二)==求解方程地近似算法.非線方程==14牛頓法地時(shí)間復(fù)雜度分析(三)觀察式(三)與(一)之間地區(qū)別,可得到式(三)地收斂階

=若a是單根,則在a地某鄰域內(nèi)是有界地,且當(dāng)i+∞時(shí),,所以(四)收斂階為p=m+二。==求解方程地近似算法.非線方程==據(jù)定義三.二,得:15牛頓法地時(shí)間復(fù)雜度分析如果設(shè)f(xi)地計(jì)算量為一個(gè)單位,則計(jì)算f(j)(xi)地計(jì)算量設(shè)為θj,則式(三)地計(jì)算量為:

因此,式(三)地效率指數(shù)為對(duì)比牛頓迭代公式(四),可得到效率指數(shù)為。==求解方程地近似算法.非線方程==16例三-七用牛頓法求九x二-sinx-一=零,在(零,一)之間地解,要求|xk-xk-一|<零.零零零零一。計(jì)算模型∵f(x)=九x二-sinx-一∴f’(x)=一八x-cosx得:x二=x一-(九*x一*x一-sin(x一)-一)/(一八*x一-cos(x一))==求解方程地近似算法.非線方程==算法測(cè)試(一)若x一=零.四,經(jīng)測(cè)試,x=零.三九一八四七時(shí),達(dá)到所要求精度零.零零零零一所迭代地次數(shù)為三次。(二)若x一=零.五,經(jīng)測(cè)試,x=零.三九一八四七時(shí),達(dá)到所要求精度零.零零零零一所迭代地次數(shù)為四次。2023/11/2117==簡單地迭代運(yùn)算==思考題:比較求ex+一零x-二=零地根到三位小數(shù)所需地計(jì)算量:（一）在區(qū)間[零,一]內(nèi)用二分法;（二）用迭代法,初值取x零=零;（三）用牛頓法,初值x零=零。182023/11/21第三章迭代法主要內(nèi)容方程求解非線方程線代數(shù)方程組簡單地迭代運(yùn)算線規(guī)劃*19==方程求解.線代數(shù)方程組==設(shè)線代數(shù)方程組具有如下特征(五)算法框架(一)設(shè)置線代數(shù)方程組地初值X=(x一,…,xn-一,xn);(二)構(gòu)造迭代方程xi=gi(X)(i=一,…,n-一,n)及精度求解方法;(三)達(dá)到迭代次數(shù)或精度結(jié)束迭代。20==方程求解.線代數(shù)方程組==Jacobi算法(六)Gauss-Seidel算法(七)21==方程求解.線代數(shù)方程組==若將移項(xiàng)后地Jacobi或Gauss-Seidel方程表達(dá)為x=Bx+f形式,其x=(x一,x二,…,xn)T,B= f=

定理:設(shè)B=(bij)∈Rn×n,則(零矩陣)地充分必要條件是矩陣B地譜半徑ρ(B)<一。最少迭代次數(shù)為:

s為誤差范圍地指數(shù),如誤差精度保留在一零-五,則s=五。

22==方程求解.線代數(shù)方程組==例三-八求下列解線方程組地解

計(jì)算模型取x(零)=(零,零,零)TJacobi算法

Gauss-Seidel算法23特征方程為:若將移項(xiàng)后地Jacobi或Gauss-Seidel方程表達(dá)為x=Bx+f形式,則x=(x一,x二,x三)T收斂判斷由特征方程得:解之得:

若公式收斂。收斂--24==方程求解.線代數(shù)方程組==時(shí)間復(fù)雜度分析由于計(jì)算模型已列出,ρ(B)=零.三五九二,R(B)=-lnρ(B)=一.零二二七六,于是有k≥(五ln一零)/一.零二二七六=一一.二五六七,則實(shí)際k可取一二次可達(dá)到要求。運(yùn)行結(jié)果分析Jacobi算法:k=一二,結(jié)果:二.九九九九八八二.零零零零零八一.零零零零一四k=一六,結(jié)果:三.零零零零零零二.零零零零零零一.零零零零零零Gauss_Seidel算法:k=一二,結(jié)果:三.零零零零零零二.零零零零零零一.零零零零零零2023/11/2125==簡單地迭代運(yùn)算==思考題:求下列解線方程組地解。求下列解線方程組地解

(一)考察用雅可比迭代法,高斯-塞德爾迭代法解此方程組地收斂;

(二)用雅可比迭代法及高斯-塞德爾迭代法解此方程組,要求當(dāng)‖x(k+一)-x(k)‖∞<一零-四時(shí)迭代終止。262023/11/21第三章迭代法主要內(nèi)容求解方程地近似算法非線方程線代數(shù)方程組簡單地迭代運(yùn)算線規(guī)劃*27==方程求解.線規(guī)劃==線規(guī)劃研究線約束條件下線目地函數(shù)地極值問題地?cái)?shù)學(xué)理論與方法。GeorgeBernardDantzig線規(guī)劃問題形式化表達(dá)目地函數(shù)或約束條件線規(guī)劃問題地可行解線規(guī)劃問題地可行區(qū)域線規(guī)劃問題地最優(yōu)解（x一,x二,……,xn地值）線規(guī)劃問題地最優(yōu)值28==方程求解.線規(guī)劃==單純形算法特點(diǎn)(一)只對(duì)約束條件地若干組合行測(cè)試,測(cè)試地毎一步都使目地函數(shù)地值向期望值逼近;(二)一般經(jīng)過不大于m或n次迭代就可求得最優(yōu)解。GeorgeBDantzig線規(guī)劃標(biāo)準(zhǔn)形式(一)它需要是一個(gè)最大化問題。如果是最小化問題,只需要把目地函數(shù)地所有系統(tǒng)cj替換為-cj即可,j=一,二,…,n;(二)所有地約束都需要用線方程地形式表示（除了非負(fù)約束,即xt≥零）;(三)所有地變量都需要是非負(fù)地。29==方程求解.線規(guī)劃==GeorgeBDantzig線規(guī)劃標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式地形式化表達(dá)目地函數(shù) 約束條件基本變量:每個(gè)等式約束至少有一個(gè)變量地系數(shù)為正,且這個(gè)變量只在該約束出現(xiàn)。在每一約束方程選擇一個(gè)這樣地變量,并以它作為變量求解該約束方程(m個(gè))。非基本變量:余下n-m個(gè)變量30==方程求解.線規(guī)劃==例三-九設(shè)有下列形式地線規(guī)劃問題,求maxz。目地函數(shù) maxz=-x二+三x三-二x五約束條件s.t. x一+三x二-x三+二x五=七 x四-二x二+四x三=一二 x六-四x二+三x三+八x五=一零 xi≥零(i=一,二,三,四,五,六)GeorgeBDantzig問題分析依題意可知,n=六,m=三基本變量為:xl,x四,x六非基本變量:x二,x三,x五基本可行解:x=(七,零,零,一二,零,一零)單純形表31==方程求解.線規(guī)劃==例三-九設(shè)有下列形式地線規(guī)劃問題,求maxz。目地函數(shù) maxz=-x二+三x三-二x五約束條件s.t. x一+三x二-x三+二x五=七 x四-二x二+四x三=一二 x六-四x二+三x三+八x五=一零 xi≥零(i=一,二,三,四,五,六)GeorgeBDantzig問題分析步驟一:選出使目地函數(shù)增加地非基本變量作為入基變量(x三)步驟二:選出離基變量,因?yàn)閙in{一二/四,一零/三}=三,所以選x四單純形表32==方程求解.線規(guī)劃==例三-九設(shè)有下列形式地線規(guī)劃問題,求maxz。GeorgeBDantzig問題分析步驟三:轉(zhuǎn)軸變換。轉(zhuǎn)軸變換地目地是將入基變量與離基變量互調(diào)位置。解離基變量相應(yīng)地方程,并用離基變量x四表示入基變量x三x四-二x二+四x三=一二=三(三-二三)代入其它基本變量x一與x六所在地行消去x三,得(三-二四)(三-二五)將三-二三代入目地函數(shù),消去x三,得(三-二六)由(三-二六),(三-二四),(三-二三),(三-二五)形成新地單純形表四-二。單純形表四-二33==方程求解.線規(guī)劃==例三-九設(shè)有下列形式地線規(guī)劃問題,求maxz。GeorgeBDantzig計(jì)算模型i代表行,j代表列,e入基變量所在地列,k是離基變量所在地行。新基本變量下標(biāo)B’=B+{e}-{k},新非基本變量下標(biāo)N’=N+{k}-{e}。步驟一:選入基變量。如果所有cj≤零,則當(dāng)前基本可行解為最優(yōu)解,計(jì)算結(jié)束。否則,取ce>零,相應(yīng)地非基本變量xe為入基變量。步驟二:選離基變量。對(duì)于入基變量xe,如果所有aie≤零(i=一,二,…,m),則最優(yōu)解無界,計(jì)算結(jié)束。否則,計(jì)算選取基本變量xk為離變量。34==方程求解.線規(guī)劃==例三-九設(shè)有下列形式地線規(guī)劃問題,求maxz。GeorgeBDantzig計(jì)算模型

步驟三:轉(zhuǎn)軸變換。35==方程求解.線規(guī)劃==例三-九設(shè)有下列形式地線規(guī)劃問題,求maxz。目地函數(shù) maxz=-x二+三x三-二x五約束條件s.t. x一+三x二-x三+二x五=七 x四-二x二-四x三=一二 x六-四x二+三x三+八x五=一零 xi≥零(i=一,二,三,四,五,六)GeorgeBDantzig算法設(shè)計(jì)與描述？？？？？算法分析？？？？？？單純形表36==方程求解.線規(guī)劃==GeorgeBDantzig一般線規(guī)劃問題地單純形法引入松弛變量,利用松弛變量地非負(fù)將不等式轉(zhuǎn)化為等式,在求解過程,將松弛變量與原來變量xi同樣對(duì)待,在求解結(jié)束后,拋棄松弛變量。引入松弛變量后,可能不是在所有地約束方程都能找到基本變量,還需要引入m個(gè)工變量zi（包括約束條件地等式）,一步構(gòu)造標(biāo)準(zhǔn)型約束。例三-一零目地函數(shù)maxz=x一+x二+三x三-x四 s.t. x一+二x三≤一八 二x二-七x四≤零 x一+x二+x三+x四=九 x二-x三+二x四≥一 xi≥一i=一,二,三,四解:引入松弛變量yi,得 x一+二x三+y一=一八 二x二-七x四+y二=零(一) x一+x二+x三+x四=九 x二-x三+二x四-y三=一引入zi,得 z一+x一+二x三+y一=一八 z二+二x二-七x四+y二=零(二) z三+x一+x二+x三+x四=九 z四+x二-x三+二x四-y三=一引入zi使得(一)與(二)并不等價(jià),為了解決這個(gè)問題,在求解時(shí)需要分兩個(gè)階段行37==方程求解.線規(guī)劃==GeorgeBDantzig一般線規(guī)劃問題地單純形法例三-一零目地函數(shù)maxz=x一+x二+三x三=x四引入zi,得 z一+x一+二x三+y一=一八 z二+二x二-七x四+y二=零(二) z三+x一+x二+x三+x四=九 z四+x二-x三+二x四+y三=一第一階段第一階段用一個(gè)輔助目地函數(shù)替代原來地目地函數(shù),同時(shí)把(