C語(yǔ)言編程牛頓迭代法求方程1

1、牛頓迭代公式設(shè)r是f(x)=(的根，選取x0作為r初始近似值，過(guò)點(diǎn)(xO,f(xO)做曲線(xiàn)y=f(x)的切線(xiàn)L,L的方程為y=f(x0)+f(x0)(x-x0),求出L與x軸交點(diǎn)的橫坐標(biāo)x1=x0-f(x0)/f(x0),稱(chēng)x1為r的一次近似值。過(guò)點(diǎn)(xl,f(xl)做曲線(xiàn)y=f(x)的切線(xiàn)，并求該切線(xiàn)與x軸交點(diǎn)的橫坐標(biāo)x2=xl-f(xl)/f(xl),稱(chēng)x2為r的二次近似值。重復(fù)以上過(guò)程,得r的近似值序列,其中x(n+l)=x(n)f(x(n)/f(x(n)，稱(chēng)為r的n+1次近似值，上式稱(chēng)為牛頓迭代公式。解非線(xiàn)性方程f(x)=0的牛頓法是把非線(xiàn)性方程線(xiàn)性化的一種近似方法。把f(x)在x0點(diǎn)

2、附近展開(kāi)成泰勒級(jí)數(shù)f(x)=f(x0)+(xx0)f(x0)+(xx0)人2*f(x0)+.取其線(xiàn)性部分，作為非線(xiàn)性方程f(x)=0的近似方程，即泰勒展開(kāi)的前兩項(xiàng)，則有f(x0)+f(x0)(x-x0)-f(x)=0設(shè)f(x0)#0則其解為xl=x0f(x0)/f(x0)這樣，得到牛頓法的一個(gè)迭代序列：x(n+l)=x(n)f(x(n)/f(x(n)。牛頓迭代法又稱(chēng)牛頓切線(xiàn)法，它采用以下方法求根：先任意設(shè)定一個(gè)與真實(shí)的根接近的值X0作為第一個(gè)近似根，由x0求出f(x0),過(guò)(x0,f(x0)點(diǎn)做f(x)的切線(xiàn)，交X軸于X,把它作為第二次近似根，再由X求出f(X),再過(guò)(X,f(X)點(diǎn)做f(x)

3、的切線(xiàn)，交X軸于X2，再求出f(x2)，再作切線(xiàn)如此繼續(xù)下去，直到足夠接近真正的X*為止。2八x0)=f八x0)=0-xxl0因此，x=x一l0就是牛頓迭代公式。例用牛頓迭代法求方程2x3-4x2+3x-6=0在.5附近的根。本題中，f(x)=2x3-4x2+3x-6=(2x-4)x+3)x-6f(x)=6x2-8x+3=(6x-8)x+3#includestdio.h#includemath.hvoidmain()floatx1,x0,f,f1;x1=1.5;dox0=x1;f=(2*x0-4)*x0+3)*x0-6;f1=(6*x0-8)*x0+3;x1=x0-f/f1;while(fab

4、s(x1-x0)=1e-5);printf(THerootofequationis%5.2fn,x1);例題2#includemain()floatx,x0,d,f,fd;x0=0;dof=2*x0*x0*x0-4*x0*x0+3*x0-6;fd=6*x0*x0-8*x0+3;d=f/fd;x=x0-d;x0=x;while(fabs(d)1e-3);printf(x=%fn,x);X+=X-=X*X賦值表達(dá)式此表達(dá)式為自右向左賦值，如X的初值為12,此表達(dá)式賦值步驟如下：先進(jìn)行“X-=X*X”的運(yùn)算，它相當(dāng)于X=X-X*X,X的值為12-144=-132再進(jìn)行“X+=-132”的運(yùn)算，相當(dāng)于

5、X=X+(-132),X的值為-132-132=264。直接選擇排序的具體算法如下：選擇排序(SelectionSort)的基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。常用的選擇排序方法有直接選擇排序和堆排序。voidSelectSort(SeqListR)inti，j，k；for(i=1;ivn;i+)做第i趟排序(Isisn-1)k=i；for(j=i+1;jv=n;j+)/在當(dāng)前無(wú)序區(qū)Ri.n中選key最小的記錄Rkif(Rj.keyvRk.key)k=j;/k記下目前找到的最小關(guān)鍵字所在的位置if(k!=i)交換Ri和R

6、kRO=Ri；Ri=Rk；Rk=R0；/R0作暫存單元/endif/endfor/SeleetSort選擇排序法選擇排序的基本思想是：每一趟在n-i+1(i=l,2，n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。我們主要介紹簡(jiǎn)單選擇排序、樹(shù)型選擇排序和堆排序。簡(jiǎn)單選擇排序的基本思想：第i趟簡(jiǎn)單選擇排序是指通過(guò)n-i次關(guān)鍵字的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄進(jìn)行交換。共需進(jìn)行iT趟比較，直到所有記錄排序完成為止。例如：進(jìn)行第i趟選擇時(shí)，從當(dāng)前候選記錄中選出關(guān)鍵字最小的k號(hào)記錄，并和第i個(gè)記錄進(jìn)行交換。圖9.5給出了一個(gè)簡(jiǎn)單選擇排序示例，說(shuō)明了前三趟選

7、擇后的結(jié)果。當(dāng)前已經(jīng)排好序的記錄。圖中大括號(hào)內(nèi)為當(dāng)前候選記錄，大括號(hào)外為排序示例，說(shuō)明了前三趟選擇后的結(jié)果。當(dāng)前已經(jīng)排好序的記錄。圖中大括號(hào)內(nèi)為當(dāng)前候選記錄，大括號(hào)外為48623548623577551435981462357755483598ik1435627755483598ffik選擇排序示例fikfffik1435357755486298簡(jiǎn)單選擇排序的算法具體描述如下voidSelectSort(RecordTyper,intlength)/*對(duì)記錄數(shù)組r做簡(jiǎn)單選擇排序，length為數(shù)組的長(zhǎng)度*/n=length;for(i=1;i=n1;+i)k=i；for(j=i+1;j=n;+

8、j)if(rj.keyrk.key)k=j；if(k!=i)x=ri；ri=rk；rk=x;/*SelectSort*/編輯本段編輯本段算法簡(jiǎn)單選擇排序算法分析：在簡(jiǎn)單選擇排序過(guò)程中，所需移動(dòng)記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄。最壞情況下，即待排序記錄初始狀態(tài)是按逆序排列的，則需要移動(dòng)記錄的次數(shù)最多為3(n-1)。簡(jiǎn)單選擇排序過(guò)程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無(wú)關(guān)。當(dāng)i=1時(shí)，需進(jìn)行n-1次比較；當(dāng)i=2時(shí)，需進(jìn)行n-2次比較；依次類(lèi)推，共需要進(jìn)行的比較次數(shù)是工=(n-l)+(n-2)+2+l=n(n-l)/2,即

9、進(jìn)行比較操作的時(shí)間復(fù)雜度為0(n2)。選擇排序法是對(duì)定位比較交換法的一種改進(jìn)。在講選擇排序法之前我們先來(lái)了解一下定位比較交換法。為了便于理解，設(shè)有10個(gè)數(shù)分別存在數(shù)組元素a0a9中。定位比較交換法是由大到小依次定位a0a9中恰當(dāng)?shù)闹?和武林大會(huì)中的比武差不多)，a9中放的自然是最小的數(shù)。如定位a0,先假定a0中當(dāng)前值是最大數(shù)，a0與后面的元素比較，如果a4更大，則將a0、a4交換，a0已更新再與后面的a5a9比較，如果a8還要大，則將a0、a8交換，a0又是新數(shù)，再與a9比較。一輪比完以后，a0就是最大的數(shù)了，本次比武的武狀元誕生了，接下來(lái)從a1開(kāi)始，因?yàn)闋钤菹⒘耍賮?lái)一輪a1就是次大的數(shù)

10、，也就是榜眼，然后從a2開(kāi)始，比出探花，真成比武大會(huì)了，當(dāng)比到a8以后，排序就完成了。下面給大家一個(gè)例子：main()inta10;inti,j,t;for(i=0;i10;i+)scanf(%d,&ai);/*輸入10個(gè)數(shù)，比武報(bào)名，報(bào)名費(fèi)用10000*/for(i=0;i9;i+)for(j=i+1;j10;j+)if(aiaj)t=ai;ai=aj;aj=t;/*打不過(guò)就要讓出頭把交椅，不過(guò)ai比較愛(ài)面子，不好意思見(jiàn)aj，讓t幫忙*/for(i=0;i10;i+)printf(%4d,ai);/*顯示排序后的結(jié)果*/好啦，啰嗦了半天總算把定位比較排序法講完了，這個(gè)方法不錯(cuò)，容易理解，就是

11、有點(diǎn)麻煩，一把椅子換來(lái)?yè)Q去，哎所以就有了下面的選擇排序法，開(kāi)始的時(shí)候椅子誰(shuí)也不給，放在一邊讓大家看著，找個(gè)人k記錄比賽結(jié)果，然后發(fā)椅子。具體來(lái)講呢就是，改進(jìn)定位比較排序法，但是這個(gè)改進(jìn)只是一部分，比較的次數(shù)沒(méi)變，該怎么打還是怎么打，就是不用換椅子了。每次外循環(huán)先將定位元素的小標(biāo)i值記錄到K，認(rèn)為ak是最大元素其實(shí)k=i還是ai最大，ak與后面的元素一一比較，該交換的也是也不換，就是把K的值改變一下就完了，最后在把a(bǔ)k與ai交換，這樣a就是最大的兀素了。然后進(jìn)入下一輪的比較。選擇排序法與定位比較排序法相比較，比的次數(shù)沒(méi)變，交換的次數(shù)減少了。下面也寫(xiě)個(gè)例子：由大到小時(shí)：main()inta10;inti,j,t,k;for(i=0;i10;i+)scanf(%d,&ai);輸/*入10個(gè)數(shù)，比武報(bào)名，報(bào)名費(fèi)用10000Y八*/for(i=0;i9;i+)k=i;/*裁判AND記者實(shí)時(shí)追蹤報(bào)道比賽情況/for(j=i+1;j10;j+)if(akaj)k=j;if(k！=i)t二ai;ai=ak;ak=t;/*發(fā)放獎(jiǎng)品*/for(i=0;i10;i+)printf(%4d,ai);顯/*示排序后的結(jié)果*/由小到大時(shí)：main()inta10;inti,j,t,k;for(i=0;i10;i+)scanf(%d,&ai);輸/*