線性方程組的數(shù)值解法及其計算機實現(xiàn)畢業(yè)論文

1、大連大學(xué)DALIAN UNIVERSITY2014屆畢業(yè)論文（設(shè)計）題目名稱：線性方程組的數(shù)值解法及其計算機實現(xiàn)所在學(xué)院： 信息工程學(xué)院 專業(yè)（班級）： 信息與計算科學(xué)10級1班 學(xué)生姓名： 李國慶 指導(dǎo)教師： 董學(xué)東 評閱人： 于萬波 院 長 ： 裴炳南 線性方程組的數(shù)值解法及其計算機實現(xiàn) 總計：畢業(yè)論文 43 頁 表 格 0 表 插 圖 11 幅指導(dǎo)老師 ：董學(xué)東（教授）評 閱 人 ：于萬波完成日期 ：2014年 5 月 21日摘 要現(xiàn)在在工程技術(shù)、自然和社會科學(xué)中常常會碰到許多問題，比如用最小二乘法來擬合實驗數(shù)據(jù)的曲線、電學(xué)中相關(guān)的網(wǎng)絡(luò)題目、計算建筑與機器中的策劃問題以及大地中的測量和經(jīng)

2、濟中的投入產(chǎn)出問題，最后均可歸納為求解線性方程組。因此，在解決實際問題時，求解線性方程組起著不可替代的作用。由于在實際問題中，方程組的未知數(shù)個數(shù)多達上百個，用克萊姆法則解決起來過于麻煩，借助計算機來解決是一個非常可行而有效地方法。本文主要研究求解線性方程組的直接解法和迭代解法這兩種數(shù)值解法，并且利用Matlab編寫程序來實現(xiàn)這些方程組的求解。關(guān)鍵詞：線性方程組；數(shù)值解；直接法；迭代法；MatlabABSTRACTNow in engineering, natural sciences and social sciences, many of the problems which frequen

3、tly encountered can be attributed to the solution of linear equations final, such as the problems of curve fitting with experimental data for using the least squares method, network topics in the electrical, the design of building structures and the calculation of machine, measuring the earth and th

4、e economic operation of the input-output.Therefore, it is extremely significant to solve linear equations for practical problems. However, these equations are made of several hundred of unknown number, it will be viable and effective if solve linear equations using computer than Cramers rule. This a

5、rticle main researches the two numerical solutions of linear equations, including direct methods and iterative methods, and uses Matlab to achieve the solution of these equations.Keyword: Linear Equations; Numerical Solution; direct method; iterative methods; Matlab目 錄 TOC o 1-3 h z u HYPERLINK l _T

6、oc388781736 摘要 PAGEREF _Toc388781736 h I HYPERLINK l _Toc388781737 ABSTRACT PAGEREF _Toc388781737 h II HYPERLINK l _Toc388781738 緒論 PAGEREF _Toc388781738 h 1 HYPERLINK l _Toc388781739 1線性方程組數(shù)值解法的提出和定義 PAGEREF _Toc388781739 h 2 HYPERLINK l _Toc388781740 提出 PAGEREF _Toc388781740 h 2 HYPERLINK l _Toc38

7、8781741 定義 PAGEREF _Toc388781741 h 2 HYPERLINK l _Toc388781742 2.線性方程組的直接解法及其計算機實現(xiàn) PAGEREF _Toc388781742 h 3 HYPERLINK l _Toc388781743 2.1 高斯消去法 PAGEREF _Toc388781743 h 3 HYPERLINK l _Toc388781744 2.1.1 高斯消去法的定義及算法構(gòu)造 PAGEREF _Toc388781744 h 3 HYPERLINK l _Toc388781745 用Matlab 作高斯消去法 PAGEREF _Toc3887

8、81745 h 5 HYPERLINK l _Toc388781746 2.1.3 列主元消去法的定義與算法 PAGEREF _Toc388781746 h 6 HYPERLINK l _Toc388781747 用Matlab 作列主元消去法 PAGEREF _Toc388781747 h 7 HYPERLINK l _Toc388781748 矩陣三角分解法 PAGEREF _Toc388781748 h 8 HYPERLINK l _Toc388781749 直接三角分解法的定義及算法構(gòu)造 PAGEREF _Toc388781749 h 8 HYPERLINK l _Toc3887817

9、50 2.2.2 直接三角分解法的適用條件 PAGEREF _Toc388781750 h 10 HYPERLINK l _Toc388781751 2.2.3 用Matlab 作直接三角分解法 PAGEREF _Toc388781751 h 10 HYPERLINK l _Toc388781752 平方根法與改進的平方根法 PAGEREF _Toc388781752 h 12 HYPERLINK l _Toc388781753 平方根法的定義 PAGEREF _Toc388781753 h 12 HYPERLINK l _Toc388781754 改進的平方根法的定義 PAGEREF _To

10、c388781754 h 13 HYPERLINK l _Toc388781755 2.3.3 用Matlab 作改進的平方根法 PAGEREF _Toc388781755 h 14 HYPERLINK l _Toc388781756 2.4 解三對角線方程組的追趕法 PAGEREF _Toc388781756 h 15 HYPERLINK l _Toc388781757 追趕法的定義 PAGEREF _Toc388781757 h 15 HYPERLINK l _Toc388781758 2.4.2 用Matlab 實現(xiàn)追趕法 PAGEREF _Toc388781758 h 16 HYPER

11、LINK l _Toc388781759 3. 線性方程組的迭代解法及其計算機實現(xiàn) PAGEREF _Toc388781759 h 19 HYPERLINK l _Toc388781760 3.1 迭代法的定義 PAGEREF _Toc388781760 h 19 HYPERLINK l _Toc388781761 3.2 雅克比迭代法 PAGEREF _Toc388781761 h 19 HYPERLINK l _Toc388781762 3.2.1 雅克比迭代法定義 PAGEREF _Toc388781762 h 19 HYPERLINK l _Toc388781763 3.2.2 用Ma

12、tlab 實現(xiàn)雅克比迭代法 PAGEREF _Toc388781763 h 20 HYPERLINK l _Toc388781764 3.3 高斯-賽德爾迭代法 PAGEREF _Toc388781764 h 21 HYPERLINK l _Toc388781765 高斯-賽德爾迭代法的定義 PAGEREF _Toc388781765 h 21 HYPERLINK l _Toc388781766 用Matlab 實現(xiàn)高斯-賽德爾迭代法 PAGEREF _Toc388781766 h 22 HYPERLINK l _Toc388781767 3.4 超松弛迭代法 PAGEREF _Toc3887

13、81767 h 23 HYPERLINK l _Toc388781768 超松弛迭代法的定義 PAGEREF _Toc388781768 h 23 HYPERLINK l _Toc388781769 迭代法的收斂性 PAGEREF _Toc388781769 h 25 HYPERLINK l _Toc388781770 向量范數(shù)和矩陣范數(shù) PAGEREF _Toc388781770 h 25 HYPERLINK l _Toc388781771 迭代法的收斂性判斷 PAGEREF _Toc388781771 h 26 HYPERLINK l _Toc388781772 4.結(jié)論 PAGEREF

14、_Toc388781772 h 28 HYPERLINK l _Toc388781773 參考文獻 PAGEREF _Toc388781773 h 29 HYPERLINK l _Toc388781774 附錄一 PAGEREF _Toc388781774 h 30 HYPERLINK l _Toc388781775 附錄二 PAGEREF _Toc388781775 h 38 HYPERLINK l _Toc388781776 致謝 PAGEREF _Toc388781776 h 43 HYPERLINK l _Toc388781777 大連大學(xué)學(xué)位論文版權(quán)使用授權(quán)書 PAGEREF _To

15、c388781777 h 44緒論對于線性方程組的求解，在中國古代的九章算術(shù)里面，解線性方程組的“方程術(shù)”方法是世界上最完備、最先的求解方法，而劉徽則提出了相對系統(tǒng)的方程理論。線性方程組的研究在西方是在17世紀由萊布尼茨最先開始的。1-2隨著現(xiàn)在科學(xué)技術(shù)的不斷發(fā)展，有效地求解線性方程組在解決實際問題中越來越重要。由于在工程技術(shù)、科學(xué)研究中、實驗設(shè)計等很多的方程組中，未知量往往過多，只能借助計算機才能快速解決，線性方程組的數(shù)值解法就是比較重要的方法。求解線性方程組的數(shù)值解的應(yīng)用非常廣泛，如：在建立物理現(xiàn)象的數(shù)學(xué)模型中，會間接出現(xiàn)一些數(shù)學(xué)模型的數(shù)值解。而在非線性方程組、常微分方程邊值間題、最優(yōu)化問

16、題數(shù)值解等問題都涉及到求解線性方程組，故在科技、醫(yī)藥和經(jīng)濟等各個領(lǐng)域，線性方程組的數(shù)值解法都有廣泛的應(yīng)用。3-5從參考文獻中可以看出，很多先者已對線性方程組的數(shù)值解法有所研究，比如關(guān)于病態(tài)線性方程組的迭代解法6、線性方程組解結(jié)構(gòu)的歷史研究、線性方程組的迭代解法及其Matlab實現(xiàn)程序7等。但是，幾乎都沒有對直接方法和迭代方法給出詳細的解法程序，又由于大學(xué)生在長期的學(xué)習(xí)中對于計算機的實踐環(huán)節(jié)往往忽視，不重視如何將編程語言與教材中給出的算法結(jié)合起來，這樣就很難對一些問題有較為深刻的理解，所以，使用計算機編程完成求解線性方程組，無論是對提高大學(xué)生實踐能力還是對解決實際問題都是非常必要的。1線性方程組

17、數(shù)值解法的提出和定義求解線性方程組是代數(shù)里的非常重要的一個部分，廣泛應(yīng)用于數(shù)學(xué)以及其它科學(xué)領(lǐng)域?，F(xiàn)代工程技術(shù)、科學(xué)研究中、實驗設(shè)計等很多計算，最后都化為求解線性方程組，而這些方程組中的未知量往往多達幾百個，故不能用克萊姆法則來求解，只有借助計算機。因此，我們介紹兩種線性方程組的數(shù)值解法：直接法和迭代法，并進行一些探討。線性方程組的數(shù)值解法一般有兩類：直接法和迭代法直接法：便是通過有限步算術(shù)的運算，可求得方程組的精確解的方法（如果計算過程當(dāng)中沒有舍入誤差），比如克萊姆法則就是一種直接法，高斯(Gauss)消去法是直接法最中具有代表性的算法。迭代法: 便是用某種極限過程去逐步的逼近線性方程組的精確

18、解的方法。也就是從解的某一個近似值出發(fā)，然后通過構(gòu)造一個無窮序列去逼近精確解的方法。8(一般有限步內(nèi)是得不到精確解)。常見的線性方程組的形式是方程個數(shù)以及未知量個數(shù)相同的都為n階的線性方程組，一般形式為： 簡記為Ax=b，其中下面介紹幾種線性方程組的直接方法：高斯消去法、列主元消去法、直接三角分解法、改進的平方根法和追趕法。2.1 高斯消去法 高斯消去法的定義及算法構(gòu)造我們知道，線性方程組的矩陣表示為：第一步：設(shè)，把方程組的實數(shù)矩陣的第一列元素消為零，令用乘以第一個方程后加到第i個方程上去，消去第2n個方程的未知數(shù)，得到，即其中：即為其中： 只有,消元過程才能夠繼續(xù)進行下去,直到經(jīng)過n-1次消

19、元后，消元過程結(jié)束后，會得到與原方程組等價的上三角形方程組,記為，或?qū)懗杉吹诙剑夯卮^程，便是對上三角方程組從下到上逐步回代求解方程組，即： 高斯消去法的算法： 若，覆蓋，消去：對于，(1)若，則計算停止 (2)對于 (i) (ii)對于 2.回代：對于， (1) (2)對于，(3) 用Matlab 作高斯消去法這是順序高斯消去法的M文件：function x=gauss(A,b)n=length(b);A=A,b;for k=1:(n-1) A(k+1):n,(k+1):(n+1)=A(k+1):n,(k+1):(n+1). -A(k+1):n,k)/A(k,k)*A(k,(k+1):(n

20、+1); A(k+1):n,k)=zeros(n-k,1);endx=zeros(n,1);x(n)=A(n,n+1)/A(n,n);for k=n-1:-1:1 x(k,:)=(A(k,n+1)-A(k,(k+1):n)*x(k+1):n)/A(k,k);end取A=1 -1 1;5 -4 3;2 1 1; b=-4 -12 11 運行結(jié)果為： 列主元消去法的定義與算法一般線性方程組在用高斯消去法求解時，消元過程當(dāng)中有可能存在的情況，這時候消去法將沒法進行；即便，如果它的絕對值很小時，用其作除數(shù)，將會致使其余元素的數(shù)量級的嚴重增加以及舍入誤差的擴散，這將嚴重影響計算結(jié)果的精度。在實際計算時必

21、須避免這種情形的產(chǎn)生。而主元素消去法就可填補這個弊端。主元素：經(jīng)過方程或交換變量的次序，使其在對角線位置上獲取絕對值盡可能大的系數(shù)作為，稱這樣的 即為主元素。9-10主元素法：使用主元素的消元法為主元素法。按照主元素選取范圍分為：列主元素法、行主元素法、全主元素法。下面主要講解列主元素法。列主元素法：在待消元的所在列中選取主元，經(jīng)過方程的行交換，置主元素于對角線位置后再進行消元的方法。列主元素的計算方法與高斯消去法完全的一樣,差別是在每步消元之前都要按列選出主元。det1 對于k=1,2，n-1按列選主元 假如=0，則計算停止(det(A)=0）如果=k則轉(zhuǎn)(4) 換行： 消元計算 對于， 對

22、于， 用Matlab 作列主元消去法下面是列主元消去法的M文件：function x=gausslzy(A,b)n=length(b);A=A,b;for k=1:(n-1) Ap,p=max(abs(A(k:n,k);p=p+k-1; if pk, t=A(k,:);A(k,:)=A(p,:);A(p,:)=t; end A(k+1):n,(k+1):(n+1)=A(k+1):n,(k+1):(n+1). -A(k+1):n,k)/A(k,k)*A(k,(k+1):(n+1); A(k+1):n,k)=zeros(n-k,1);endx=zeros(n,1);x(n)=A(n,n+1)/A(

23、n,n);for k=n-1:-1:1 x(k,:)=(A(k,n+1)-A(k,(k+1):n)*x(k+1):n)/A(k,k);end取A=1 -1 1;5 -4 3;2 1 1; b=-4 -12 11 運行結(jié)果為：圖直接三角分解法的定義及算法構(gòu)造矩陣三角分解法是以高斯消去法解線性方程組為基礎(chǔ)的一種變形解法。應(yīng)用高斯消去法去解n階線性方程組Ax=b,再通過n步消元之后, 將會得出一個等價的上三角型方程組A(n) x=b(n),然后對上三角形方程組用逐步回代就可以求出解來。上述過程可通過矩陣分解來實現(xiàn)。將非奇異陣A分解成一個下三角陣L以及一個上三角陣U的乘積A=LU稱為對矩陣A的三角分解

24、，又稱LU分解。11-13 其中 將A分解成一個單位上三角陣L和一個下三角陣U的乘積，稱為杜利特爾（Doolittle）分解。其中：若把A分解成一個下三角陣L和一個單位上三角陣U的乘積稱為克洛特分解Crout）。 其中 ：在求解線性方程組Ax=b時,要先對非奇異矩陣A進行LU分解使A=LU，則方程組就化為LUx=b。那么原方程組轉(zhuǎn)化為求解兩個簡單的三角方程組：Ly=b求解y，Ux=y求解x。這就是求解線性方程組的三角分解法的基本思想。14下面只介紹杜利特爾（Doolittle）分解法。 設(shè)A=LU為： 由矩陣乘法規(guī)則：由此可得U的第1行元素以及L的第1列元素：再確定U的第k行元素和L的第k列元

25、素,對于k=2,3, ,n計算：計算U的第k行元素 （j=k,k+1,n） 計算L的第k列元素 （i=k,k+1,n） 利用上述計算公式即可逐步求出U與L的各元素求解 Ly=b , 即計算: 求解 Ux=y , 即計算： 直接三角分解法的適用條件很明顯, 當(dāng)時,解Ax=b直接三角分解法計算才有可能實現(xiàn)。設(shè)A為非奇異矩陣, 當(dāng)時計算將中斷或當(dāng)絕對值很小時，按分解公式計算可能會引起舍入誤差的積累，于是可采用與列主元消去法相似的方法，對矩陣進行行交換，則再實現(xiàn)矩陣的三角分解。 用Matlab 作直接三角分解法下面是直接三角分解法的M文件：function x=LU(A,b)A=1 2 3;2 5 2

26、;3 1 5;b=14 18 20;n=length(b);x=zeros(n,1);A(2:n,1)=A(2:n,1)./A(1,1);for i=2:n-1 A(i,i)=A(i,i)-sum(A(i,1:i-1).*A(1:i-1,i); for j=i+1:n A(i,j)=A(i,j)-sum(A(i,1:i-1).*A(1:i-1,j); A(j,i)=(A(j,i)-sum(A(j,1:i-1).*A(1:i-1,i)/A(i,i); endendA(n,n)=A(n,n)-sum(A(n,1:n-1).*A(1:n-1,n);AU=A;L=A;for i=1:n L(i,i)=

27、1;endfor i=1:n-1 for j=i+1:n L(i,j)=0; endendLfor i=2:n for j=1:i-1 U(i,j)=0; endendUy=zeros(n,1);y(1)=b(1);for i=2:n y(i)=b(i)-sum(L(i,1:i-1).*y(1:i-1);endyx(n)=y(n)/U(n,n);for i=n-1:-1:1 x(i)=(y(i)-sum(U(i,i+1:n).*x(i+1)/U(i,i);endx運行結(jié)果為：圖圖在工程現(xiàn)實情況中,線性方程組的系數(shù)矩陣經(jīng)常具有對稱正定性，其各階順序主子式及全部特征值均大于0。矩陣的這一特性使它的

28、三角分解具備更簡單的形式，從而導(dǎo)出一些特殊的解法，比如平方根法與改進的平方根法。平方根法的定義由于A是正定矩陣, A的順序主子式i0, i=1,2,n ，因此存在惟一的分解A=LU，L是單位下三角陣, U是上三角陣, 將U再分解： 其中D為對角陣, U0為單位上三角陣，因此A = L U = L D U0，又A = AT = U0TD LT ，由分解惟一性, 即得U0T=L，A=L D LT 。記：又由于det(Ak)0,(k=1,2,n),因此，于是對角陣D還可分解：，其中為下三角陣。將A=LLT展開，寫成按矩陣乘法展開，可逐行求出分解矩陣L的元素，計算公式是對于i=1,2,n ， ， j=

29、i+1, i+2,n ，這一方法稱為平方根法,又稱喬累斯基(Cholesky)分解。改進的平方根法的定義因為平方根法解正定方程組的弊端是要進行開方運算。為避免開方運算，我們改用單位三角陣作為分解陣，把對稱正定矩陣A分解成的形式，其中為對角陣，而是單位下三角陣,這里分解公式為利用這類矩陣分解法,方程組Ax=b即可歸結(jié)為求解兩個上三角方程組和。其計算公式分別為： 求解方程組的上述算法稱為改進的平方根法。 用Matlab 作改進的平方根法下面是改進的平方根法的M文件：function x=gaijin(A,b,n) A=2 -1 1;-1 -2 3;1 3 1;b=4 5 6;n=length(b)

30、;L=zeros(n,n); D=diag(n,0); S=L*D; for i=1:n L(i,i)=1;end for i=1:n for j=1:n if (eig(A)p|e-p x1=b*x+g; e1=x1(1,1)-x(1,1); e2=x1(2,1)-x(2,1); e3=x1(3,1)-x(3,1); e4=min(e1,e2); e5=min(e1,e3); e=min(e4,e5); x=x1;end for(i=1:n) fprintf(x%d=%fn,i,x(i,1);end運行結(jié)果是：圖3.3 高斯-賽德爾迭代法高斯-賽德爾迭代法的定義在雅克比的迭代法中，每次迭代只

31、用到前一次的迭代值，若每次迭代充分利用當(dāng)前的最新的迭代值，即在求時用新分量取代舊分量就會得到高斯-賽德爾迭代法。其迭代法格式為： (i=1,2,n k=0,1,2,)將A分裂成A =D-L-U，則等價于(D-L-U )x = b，則高斯塞德爾迭代過程，故，令，則則高斯-塞德爾迭代形式為：。用Matlab 實現(xiàn)高斯-賽德爾迭代法下面是高斯賽德爾迭代法的M文件：function x=GSdiedai(A,b)A= 8 -3 2;4 11 -1;6 3 12;b=20 33 36;N=length(b); fprintf(庫函數(shù)計算結(jié)果：);x=inv(A)*bx=zeros(N,1);D=diag

32、(diag(A);L=-tril(A,-1); U=-triu(A,1); B=inv(D-L)*U;g=inv(D-L)*b;eps=0.001;for k=1:100 fprintf(第%d次迭代,k); y=B*x+g; if norm(x-y)eps break; end x=yendx運行結(jié)果為：圖3.4 超松弛迭代法超松弛迭代法的定義超松弛迭代法的目的是為了提升迭代法的收斂速度，在高斯塞德爾迭代公式的基礎(chǔ)上做一些修改。這種方法是將前一步結(jié)果和高斯-塞德爾迭代方法的迭代值適當(dāng)?shù)募訖?quán)平均，希望能得到更好的近似值。超松弛迭代法是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應(yīng)用。17-1

33、8用高斯塞德爾迭代法定義輔助量：把取為與的加權(quán)平均，即：合并表示為：其中稱為松弛因子，當(dāng)=1時，便是高斯-塞德爾迭代法。為了保證迭代過程收斂性，必須要有0 2。 當(dāng)0 1時，低松弛法；當(dāng)1 2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。19設(shè)線性方程組Ax=b的系數(shù)矩陣A為非奇異，且主對角元素, 則將A分裂成A=d-L-U, 那么超松弛迭代公式用矩陣表示為： 或故 明顯，對任何一個值,(D+L)非奇異, (因為假定)于是超松弛迭代公式為：。令 則超松弛迭代可寫成：。用Matlab 實現(xiàn)超松弛迭代法下面是超松弛迭代法的M文件：function x=chaosongchi(A,b)A=8,-3

34、,2;4,11,-1;6,3,12;b=20,33,36;N=length(b); fprintf(庫函數(shù)計算結(jié)果：);x=inv(A)*b x=zeros(N,1);D=diag(diag(A);L=-tril(A,-1);U=-triu(A,1);w=1.5;B=inv(D-w*L)*(1-w)*D+w*U;g=w*inv(D-w*L)*b;eps=0.00001;for k=1:100 fprintf(第%d次迭代： ,k); y=B*x+g; if abs(x-y),稱A為嚴格對角占優(yōu)矩陣。弱對角占優(yōu)矩陣：設(shè)A=，假如A的元素滿足 ,，且上式至少有一個不等式嚴格成立，則稱A為弱對角占優(yōu)

35、矩陣?？杉s與不可約矩陣：設(shè)A= ，如果存在置換矩陣P使 ，其中為r階矩陣，為n-r階矩陣（），則A為可約矩陣，否則如果不存在這樣的置換矩陣P是其成立，則稱A為不可約矩陣。定理3. 設(shè)Ax=b,如果A為嚴格對角占優(yōu)矩陣，則解Ax=b的雅克比迭代法，高斯賽德爾迭代法均收斂。如果A為弱對角占優(yōu)矩陣，且A為不可約矩陣，則解Ax=b的雅克比迭代法，高斯賽德爾迭代法均收斂。定理4. 設(shè)矩陣A對稱，且對角元，則解線性方程組Ax=b的雅克比迭代法收斂的充分必要條件是A及2D-A均為正定矩陣，其中。解線性方程組Ax=b的高斯-賽德爾法收斂的充分條件是A正定。定理5. 對于線性方程組Ax=b，若A為對稱正定矩陣，

36、則當(dāng)02時，超松弛迭代法收斂。定理6. 對于線性代數(shù)方程組Ax=b， 若A按行(或列)嚴格對角占優(yōu)，或按行(或列)弱對角占優(yōu)不可約；則當(dāng)0w1時，超松弛迭代法收斂。求解線性方程組是代數(shù)里的一個非常重要的部分。現(xiàn)代工程技術(shù)、科學(xué)研究中、實驗設(shè)計等很多計算，最后都化為求解線性方程組。本論文總結(jié)了直接方法中的高斯消去法、列主元消去法、直接三角分解法、改進的平方根發(fā)和追趕法；迭代方法中的雅克比迭代法、高斯塞德爾迭代法、和超松弛迭代法，并討論迭代法的收斂性和收斂速度的問題。在此基礎(chǔ)上應(yīng)用Matlab程序?qū)崿F(xiàn)這些方法，給出了直接方法和迭代方法詳細的解法程序，這對提高大學(xué)生實踐能力和解決實際問題有所幫助。參

37、考文獻1李慶揚.數(shù)值分析第五版M.清華大學(xué)出版社，2008.2丙辛. 線性方程組的解法J.數(shù)學(xué)通報，1961，（1）:32-36.3曹學(xué)濱. 線性方程組解結(jié)構(gòu)的歷史研究D.山東:山東大學(xué)數(shù)學(xué)系基礎(chǔ)數(shù)學(xué)，2009.4王永寶.關(guān)于病態(tài)線性方程組的迭代解法J.航空計算技術(shù)，1995，(3): 20-25.5周建興，豈興明，矯津毅，張延偉.MATLAB從入門到精通（第2版）M.人民郵電出版社，2012.6 Wilkinson J H. Rounding errors in algebraic prentices. London: H. M. Stationery office, 1963.7Golub

38、 G H, Van Loan C F. Matrix computations. 3rd ed. Johns Hopkins University Press, Baltimore MD, 1996.8Young D M. Iterative solution of large linear systems. New York: Academic, 1971.9Hackbusch W. Iterative solution of large sparse systems of equation. New York: Springer-Verlag, 1994.10姜啟源.數(shù)學(xué)建模方法及其應(yīng)用M

39、.北京:高等教育出版社，2003.11杜廷松.數(shù)值分析及實驗M.科學(xué)出版社，2006.12陳延梅.計算方法指導(dǎo)M.科學(xué)出版社，2003.13龐遼軍,姜正濤,王育民. 基于一般訪問結(jié)構(gòu)的多重秘密共享方案J.計算機研究與發(fā)展， 2006, 43(1): 33-38. 14曹戈,MATLAB教程及實訓(xùn)M,機械工業(yè)出版社,2014.15周義倉、赫孝良.數(shù)學(xué)建模實驗M.西安:西安交通大學(xué)出版社，1999.16黃進陽. 論線性方程組的數(shù)值解法J. 邵陽高專學(xué)報，1995，(4): 292-297.17 HYPERLINK :/www /KCMS/detail/%20%20%20%20%20%20%20%2

40、0%20%20%20%20%20%20%20%20/kcms/detail/search.aspx?dbcode=CJFQ&sfield=au&skey=%e6%9d%a8%e5%87%a4%e9%9c%9e&code=06450745; t _blank 楊鳳霞. 線性方程組的數(shù)值解法J. 滄州師范?？茖W(xué)校學(xué)報，2000，(3): 38-40.18 Xuedong Dong，Liqiang Hou，Yan Zhang，Public Key Cryptosystem and Signature Schemes over the Ring of Eisenstein Integers，2013

41、Fourth International Conference on Intelligent Control and Information Processing (ICICIP) June 9 11, 2013, Beijing, China.19童小紅,秦新強.線性方程組的解法探討及MATLAB實現(xiàn)J.數(shù)學(xué)學(xué)習(xí)與研究，2013，(13): 23-25.20花威.線性方程組的迭代解法及其Matlab實現(xiàn)程序J. 長江工程職業(yè)技術(shù)學(xué)院學(xué)報,2009,(4): 12-14.附錄一 在愛森斯坦整數(shù)環(huán)下的公鑰密碼體制和簽名方案董學(xué)東摘要在本文中，使用愛森斯坦整環(huán)模愛森斯坦素數(shù)的有限域的乘法群，給出了

42、恢復(fù)信息的擴展的ElGamal公鑰密碼體制和數(shù)字簽名方案。這種方法比經(jīng)典的ElGamal密碼體制和數(shù)字簽名方案的優(yōu)點多。文中給出許多例子說明所給出的ElGamal公鑰密碼體制和數(shù)字簽名方案的有效性。一引言基于整數(shù)環(huán)模素數(shù)的單位群的離散對數(shù)問題，ElGamal1提出公鑰密碼體制和數(shù)字簽名方案。ElGamal加密方案和數(shù)字簽名方案可以很容易地推廣到任何有限循環(huán)群中。群G應(yīng)慎重選擇，使在群G中的運算相對容易以便提高效率。在計算G中離散對數(shù)時，樸素的算法是增加G的生成元的冪，直到所需的元素被找到。該算法需要G群的線性空間，因此是群G的指數(shù)冪。因此，若G的階是足夠大，G中的離散對數(shù)問題應(yīng)該是計算上不可行

43、的，以確保使用的ElGamal公鑰密碼體制和數(shù)字簽名方案的協(xié)議的安全性。在密碼學(xué)中最感興趣的群是有限域的乘法群。把ElGamal公鑰密碼體制推廣到高斯整數(shù)環(huán)已在文2中給出。ELKamchouchi等在文34中提出了高斯整數(shù)環(huán)上的擴展RSA密碼體制和數(shù)字簽名方案。注意到高斯整數(shù)環(huán)是分圓域的代數(shù)整數(shù)環(huán)，艾森斯坦整數(shù)環(huán)是分圓域的代數(shù)整數(shù)環(huán)，我們想知道ElGamal公鑰密碼體制和數(shù)字簽名方案是否可以擴展到艾森斯坦整數(shù)環(huán)。愛森斯坦的環(huán)像整數(shù)環(huán)和高斯整數(shù)環(huán)有許多良好的性質(zhì)（5,6,7）。在艾森斯坦整數(shù)環(huán)求最大公約數(shù)有高效的算法8。本文給出了艾森斯坦整數(shù)環(huán)上的ElGamal公鑰密碼體制和數(shù)字簽名方案。這種方

44、法具有很多優(yōu)點。首先，如果在擴展的ElGamal密碼系統(tǒng)中使用的循環(huán)群是艾森斯坦整數(shù)環(huán)模具有形式的素數(shù)，則其階是比在古典ElGamal密碼所使用的平方大。其次，由于艾森斯坦整數(shù)環(huán)的運算，一個素數(shù)的擴展歐拉函數(shù)是，而在整數(shù)環(huán)中相應(yīng)的歐拉函數(shù)是。由于加冪指數(shù)是被選擇的與擴展的歐拉函數(shù)互質(zhì)，所以它比經(jīng)典的ElGamal密碼系統(tǒng)更安全。第三，如果模數(shù)是兩個非實的艾森斯坦素數(shù)的乘積，分解模的難度提高，因為在艾森斯坦整數(shù)環(huán)中，元素的分解比在整數(shù)環(huán)元素的分解更復(fù)雜。最后，所使用的運行模式與使用整數(shù)環(huán)是相似的，可以使用負整數(shù)。文中給出許多例子說明所給出的ElGamal公鑰密碼體制和數(shù)字簽名方案的有效性。本文的

45、其余部分安排如下：在第2節(jié)，我們給出關(guān)于艾森斯坦整數(shù)環(huán)的一些預(yù)備知識。在第3節(jié)，我們在艾森斯坦整數(shù)環(huán)構(gòu)建ElGamal公鑰密碼體制。在第4節(jié)，在艾森斯坦整數(shù)環(huán)中給出了擴展ElGamal數(shù)字簽名方案。最后，第5節(jié)給出了結(jié)束語。二預(yù)備知識定義域是一個包括兩個操作：，叫加，和，所謂乘法的集合，滿足下列公理。如果在+下有零元，并記為零，集合是一個阿貝爾群。的所有非零元素的集合*，如果有幺元，記為1，那么也是阿貝爾群，在除法之上的乘法分布。滿足相同公理的乘法分布交換環(huán)作為一個定義域，除了非零元素不一定有乘法的逆。一個交換環(huán)的元素被稱為劃分如果中的元素（符號：）存在使。中的元素被稱為有聯(lián)系的，如果并且，交

46、換環(huán)R的元素是素數(shù)，條件是：（1）是非零并且沒有任何乘法逆；(2) 或。艾森斯坦整數(shù)環(huán)是,是它的 三重復(fù)根。一個艾森斯坦整數(shù)的范數(shù)被定義為，表示它的共軛復(fù)數(shù)，有6個元逆素，。元素與有聯(lián)系。愛森斯坦素數(shù)和它的相關(guān)素數(shù)，理性素數(shù)和它的相關(guān)素數(shù)，考慮的理性素數(shù)，其中。前幾個艾森斯坦素數(shù)等于一個天然素3k+2：2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, 239, 251, 257, 263, 269, 281, 293

47、, 311, 317, 347, 353, 359, 383, 389, 401, 419, 431, 443, 449, 461, 467, 479, 491, 503, 509, 521, 557, 563, 569, 587。一些非實數(shù)的艾森斯坦素數(shù)是。下圖1顯示了小艾森斯坦素數(shù)9。那些綠色軸是與天然素數(shù)形式是相關(guān)聯(lián)的。其它的是絕對值平方等于天然素數(shù)。一個艾森斯坦整數(shù)表達成艾森斯坦素數(shù)的乘積是獨一無二的，除了素數(shù)的順序，相關(guān)素數(shù)之間的逆元素存在，存在著歧義。對于，其中是有理數(shù)，令，符號表示最大整數(shù)小于或等于，。接下來我們用來表示，令，表示，其中，是的共軛復(fù)數(shù)。如果是艾森斯坦素數(shù)，這樣，是

48、有理元素，然后這很容易證明是和的一個同構(gòu)。特別的，如果是的一個原始的元素，那么是的一個原始的元素。費馬大定理對的模擬如下。定理1：讓是艾森斯坦素數(shù)，其中和沒有直接關(guān)系，。然后對于任何艾森斯坦整數(shù)成立，其中，對于任何艾森斯坦整數(shù)成立。證明，應(yīng)為是艾森斯坦素數(shù)，商環(huán)分別是有限域與元素和10,p.14。假設(shè)是艾森斯坦整數(shù)，注意，艾森斯坦整數(shù)環(huán)是歐幾里德域。因此，任何兩個整數(shù)愛森斯坦有最大公約數(shù)。如果，那么，因此，因為和沒有直接關(guān)系，它遵從,因此。如果或2，然后，。因此我們有，如果，那么。這就是定理的證明。三在艾森斯坦整數(shù)環(huán)下的ElGamal公鑰密碼體制密碼學(xué)的基本目標(biāo)是為了讓兩個人，通常被稱為Ali

49、ce和Bob，在不安全的信道進行交流，這種方法使對手Eve不明白你在說什么。ElGamal加密系統(tǒng)中基于離散對數(shù)問題。離散對數(shù)問題在有限域內(nèi)一直是許多研究的對象。如果質(zhì)數(shù)是經(jīng)過精心選擇的，該問題通常被認為是困難的。特別是，沒有已知的多項式的時間算法的離散對數(shù)問題。為了阻止已知的攻擊，應(yīng)該至少有一個“大”的主要因素。離散對數(shù)問題在一個加密設(shè)置的效用是，發(fā)現(xiàn)離散對數(shù)是（可能）困難，但求冪的相反操作可以有效地利用平方和乘法的方法進行計算。在本節(jié)ElGamal公鑰加密方案擴展到艾森斯坦整數(shù)環(huán)。這種方法的優(yōu)點是，在對擴展ElGamal加密中使用的環(huán)狀基團具有一個順序比的，在傳統(tǒng)的ElGamal加密在某些

50、情況下使用的較大的正方形。算法和舉例說明這些修改會被給出。假設(shè)Alice想要發(fā)送一個消息m給Bob。Bob選擇了一個 Eisenstein 素數(shù)，至少有一個大素數(shù)因子。然后，商環(huán)是一個在加法和乘法模型下的有限域?，F(xiàn)在，乘法群的發(fā)生器被選中，并注意有發(fā)生器。假設(shè)如果不是一個合理的素數(shù)，那么是一個整數(shù)，如果不是一個合理的素數(shù)，那么。如果m較大將其分為較小的塊。Bob也隨機選擇一個正整數(shù)a，其中，并且計算。是公開的。系統(tǒng)的安全性建立在a是保密的前提下。對于外熱來說決定來自的a是困難的，因為離散對數(shù)問題被認為在Eisenstein整數(shù)環(huán)中是較難的。為了能讓Alice把信息m送出去，她必須做一下幾件事：

51、下載。選擇一個秘密的隨機整數(shù)k，它滿足，并計算。計算。送給Bob。Bob通過計算來解密。這是因為。如果有另一個正整數(shù),，當(dāng)不是一個合理素數(shù)時，當(dāng)是一個合理素數(shù)時，并且當(dāng)，。如果不是一個合理素數(shù)，是一個合理素數(shù)，因此。不過這意味著s=m。如果是一個合理素數(shù)，因此從可以得出和s=m。 如果Eve也想決定a，他可以使用Bob使用過的程序來解密。因此，Bob保守秘密是很重要的。由于k是一個隨機的整數(shù)，所以是一個隨機非零的 Eisenstein整數(shù)。因此是隨機的。因此沒有Eve任何有關(guān)m的信息。從中難以確定整數(shù)k，因為這又是一個離散對數(shù)問題。然而，如果Eve發(fā)現(xiàn)k，她就可以計算，這個值就是m。每個信息使

52、用不同的k是有用的。如果Alice把信息和像Bob加密，并且對每個信息使用相同的k值。那么對于每個信息都是相同的。因此，密文將是和。將有一個Eisenstein整數(shù)， ，因為在環(huán)中和是互質(zhì)的。如果Eve發(fā)現(xiàn)明碼文本，他也可以決定，因為。當(dāng)被選作為合理的素數(shù)：其循環(huán)群用擴展的Elgamal密碼體制具有一階比，用經(jīng)典的方Elgamal體制與需要沒有額外的努力尋找素數(shù)p。例子1：為了生成公鑰，Bob選擇一個Eisenstein素數(shù)p=17=3.5+2和屬于乘法群的生成器。乘法群的階是，比經(jīng)典Elgamal體制使用的乘法群的平方階171大。Bob也選擇一個合理的正整數(shù)a=135并且計算。因此，Bob的

53、公鑰是，私人密碼是a=135。為了加密信息m=10，Alice選擇一個合理的整數(shù)k=115并且計算 和。然后Alice送 給Bob。Bob可以通過計算得到。例子2.Bob選擇了一個艾森斯坦素數(shù)并且和乘法集的發(fā)生器。Bob選擇一個合理的正整數(shù)a=15并且計算。因此Bob的公鑰是，私人密碼是a=15。為了加密信息m=50，Alice選擇了一個合理的整數(shù)k=67，并計算和。然后Alice送給Bob。Bob可以通過計算來解釋明白。 四.在艾森斯坦整數(shù)環(huán)擴展ElGamal數(shù)字簽名方案延長ElGamal數(shù)字簽名方案附錄假設(shè)Alice想要發(fā)送信息，該消息不容易從回收的簽名而且該消息必須被包括在驗證過程。開始

54、，她選擇艾森斯坦素數(shù)，因此應(yīng)該至少有一個“大”素因子，和沒有聯(lián)系，然后計算，然后他選了一個愛森斯坦整數(shù)，暗示。Alice接下來抽了一個任意的正整數(shù)a，并計算得。設(shè)H是一個公共加密散列函數(shù)，該函數(shù)將產(chǎn)生任意長度的消息，并產(chǎn)生一個指定大小的消息摘要。將會作為公共參數(shù)被公開。事實上該系統(tǒng)的安全性是和是保密的。對手很難從中做出決定，因為離散對數(shù)問題被認為是困難的。為了讓Alice發(fā)消息m，她將執(zhí)行以下操作：選擇一個加密指數(shù)e，使得e是互質(zhì)的擴展歐拉函數(shù)即，計算用擴展歐幾里德算法計算唯一的整數(shù)來自的h單位計算該簽名的消息是三個未知量。Bob可以驗證簽名如下：（1）下載Alice的公共鑰匙（2）計算（3）

55、如果，那么簽名將會被宣布有效我們現(xiàn)在證明該驗證程序的工作原理。假設(shè)簽名是有效的，因為，我們通過理論 有和。持續(xù)一個秘密是非常重要的。如果Eve發(fā)現(xiàn)a的值，那么她可以執(zhí)行簽名程序，并在任何需要的文件產(chǎn)生Alice的簽名。如果Eve還有另外一個消息m，她不能計算出相應(yīng)的S，因為她不知道a和h。假設(shè)她試圖通過選擇一個s滿足驗證方程繞過這一步。這意味著她需要S來滿足這是一個離散對數(shù)問題。例3. Alice想簽消息m。假設(shè)H(m)=12345。開始，她選擇艾森斯坦素數(shù)和并計算了，。然后她選擇了艾森斯坦整數(shù)和一個任意的正整數(shù)a=311，并計算了，作為一個公共參數(shù)被公開。為了讓Alice簽消息m，她將執(zhí)行以下操作：（1）選擇一個加密指數(shù)e=1391，并計算（2）使用擴展歐幾里德算法計算唯一的整數(shù)來自的（3）計算該簽名的消息是三個未知量。Bob可以驗證簽名如下：（1）下載Alice的公共鑰匙（2）計算（3）因為，那么簽名將會被宣布有效。例4. Alice想簽消息m。假設(shè)H(m)=12345。開始，她選擇艾森斯坦素數(shù),和并計算了，。然后她選擇了艾森斯坦整數(shù)和一個任意的正整數(shù)a=311，并計算。作為一個公共參數(shù)被公開。為了讓Alice簽消息m，她將執(zhí)行以下操作