列主元素消去法求解方程组
[摘 要]在自然科学和工程中有很多问题的解决归结为求解线性方程组或者非线性方程组的数学问题。例如，电学中的网络问题，用最小二乘法求实验数据的曲线拟合问题，三次样条的插值问题等等。求解线性方程组的直接法主要有选主元高斯消去法、平方根法、追赶法等。列主元素消去法既是选主元高斯消去法的一种，也是实际计算中常用的部分选主元消去法。本文即是讨论利用列主元素消去法求解线性方程组问题。
[关键词］按列选主元 交换 消元 回代
一 列主元素消去法背景
在科学研究和工程技术中有许多问题可归结为求解线性代数方程组，其中所产生的线性方程组，其系数矩阵大致可分为两种：一种是低阶稠密矩阵；另一类是大型稀疏矩阵（此类矩阵阶数高，但零元素较多）。对于这两种矩阵,我们可以把线性代数方程组的数值解法大致的分为两类：直接法和迭代法。迭代法一般用来求解大型稀疏矩阵方程组（本文不予讨论)；直接法是目前计算机上解低阶稠密矩阵的有效方法,如果计算过程中没有舍入误差，则此种方法通过有限步四则运算可求的方程组的精确解,但实际计算中由于舍入误差的存在和影响，这种方法也只能求得方程组的近似解。直接法主要有选主元素高斯消去法、平方根法、追赶法等。本文所要讨论的列主元素消去法就是选主元素高斯消去法中的一种。
高斯消去法是一个古老的求解线性方程组的方法,也是解线性方程组问题中较为常见的一种数值方法。但在采取高斯消去法解方程组时，当采用绝对值很小的主元素时,可能导致计算结果的失败，故在消去法中应避免采用绝对值很小的主元素。对于一般的线性方程组,需要引进选主元的技巧，即在高斯消去法的每一步应该在系数矩阵或消元后的低价矩阵中选取绝对值最大的元素作为主元素，保持乘数1 ik m ，以便减少计算过程中舍入误差对计算解的影响。
选主元素消元法则是对高斯消去法的改进,是解低价稠密矩阵方程组的有效方法。选主元素消元法则避免了采用绝对值很小的主元素。选主元素消去法主要有完全主元素消去法与列主元素消去法两种。完全主元素消去法即是每次按行列选取绝对值最大的元素作为主元素,进行行列交换,之后再完成消元计算。在完全主元素消去法计算过程中舍入误差能得到有效的控制，对计算的影响较小,具有更好的数值稳定性。
列主元素消去法则是对完全主元素消去法的又一次改进。列主元素消去法在完全主元素消去法的基础上减少了在选主元素时所要花费的一定的计算时间。此论文将介绍列主元消去法的基本思想和原理。
二 列主元素消去法的理论基础
设有线性方程组
b =Ax
其中,A 为非奇异矩阵。
方程组的增广矩阵为
???????
??
??
?????=n nn
n n k i n n b a a a a b a a a b a a a A
2
12222
211112111]b ,[ 首先在A 的第1列选取绝对值最大的元素作为主元素，即选择 0max 111,1≠=≤≤i n
i i a a
然后交换A 的第１行与第1i 行（交换后增广矩阵为简单起见仍记为]b ,[A ,其元素仍记为
i j i b a ,)。经过第１次消元计算得到与原方程组等价的方程组
(2))2(b x =A 其中
??
?????
???????=??????
???????
?=)
2()2(2)1(1)2()2()2(2
)2(2)2(22)
1(1)1(12)1(11)
2(b n nn n n
n b b b a a a a a a a A
， 上述过程可记为 ]
2[)2()2(]
b ,[]b ,[A A →
重复上述计算过程,现假设已完成第1-k 步的选主元素过程,交换两行并进行消元计 此时]b ,[A 约化为
????
??
???
?
??
?
??????
?=)()
()()()()
()2(2)2(2)
2(22)1(1)
1(1)1(12)1(11)
()(]b ,[k n k nn
k nk k k k kn
k kk n
n k k b a a b a a b a a b a a a A
其中)(k A 的元素仍记为j i a ，)(b k 的元素仍记为i b ．
第k 步选主元素（在)(k A 右下角方阵的第1列内选）,即确定k i ,使 0max ,≠=≤≤ik n
i k k i a a k
交换]b ,[)()(k K A 第k 行与)1,,2,1(-=n k i k 行的元素,再进行消元计算，最后将原线性方程组化为
??
???
?
??????=?????????????????????
?
??n n nn n n b b b x x x a a a a a a 212122211211
回代可求解得 ??
??
?-=-==∑+=)
1,2,,1(/)(/1 n i a x a b x a b x ii
n
i j j ij i i nn n n
算法描述:
对于1,,2,1-=n k 做到（４）。 （1） 按列选主元，即确定k i 使 0max ,≠=≤≤ik n
i k k i a a k
（2） 如果0,=k i k a ，则A 为奇异矩阵，停止计算。 （3） 如果k i k ≠，则交换]b ,[A 第k i 行与第k 行元素。 （4） 消元计算：
)
,,1(),,1,(),,1(/n k i b m b b n k j i a m a a n k i a a m a k
ik i i kj
ik ij ij kk
ik ik ik ???+=*-←???+=*-←???+==← （5） 回代计算：
?????-=-←≠←∑+=)1,2,,1(/)(0/1 n i a b a b b a a b b ii n
i j j ij i i
nn nn n n ）
（当
三 通过计算机利用列主元素消去法求解线性方程组
计算机在科学和工程设计中应用日益广泛。把科学和工程设计中的具体问题抽象为数学问题,建立起能描述并等价代替该实际问题的数学问题,编制出计算机程序，就能够使得复杂问题得到妥善的解决。下面及描述列主元消去法的程序过程。
对于已给定的]b,
[A，其程序框图如下:
（注：n为矩阵的行数；ε为输入的一精度，用于判断A的行列式是否约等于0)
例 求下面解方程组
??????????
????????????=???????????????????????????????????????????
?28221713108712
34
5671123456111234511112341111123111111211111117654321x x x x x x x 利用列主元素消去法求解此方程组的程序见附件1，其结果如下图：
利用完全主元素消去法求解此方程组的程序见附件2,其结果如下图
:
容易看出此方程组的精确解T x )1,1,1,1,1,1,1(=，由上面两图可看出列主元素消去法与完全主元素消去法的结果都接近于精确解。二种方法的精度差不多。
四 总结
列主元素消去法的提出有效的控制了舍入误差的扩散，且相对于完全主元素消去法,其选主元素比较方便。，利用列主元素消去法解线性方程组时仅需要选出每列中绝对值最
大的元素,计算量为2)
1(3323-+-+n n n n n ，利用完全主元素消去法时则需要按行列选取绝对值最大的元素,其计算量为6
)
12138)(1(33223+--+-+n n n n n n 。可看出列主元素消去法比完全主元素消去法减少了计算时间。总之,列主元素消去法是解低阶稠密矩阵的有效方
法。
从上面的例题可看出，利用计算机来求解方程组大大的减少了计算时间。当然，利用计算机来解决工程实际和科学技术中的复杂问题,也是21世纪现代化的要求。把建立好的数学模型用计算机描述出来，这不仅使问题变得简单化，还大大的缩减了计算所需的时间,体现了数学与计算机的紧密结合。在以后的工作生活中我们要学会善于利用计算机与数学的关系,把复杂的问题简单化，减少计算时间，提高工作的效率。
列主元消去法只是求解线性方程组的一种方法,但由于篇幅的限制,对于解决线性方程组的其他方法就不一一叙述了。
［参考文献]
［1]Burd ｅｎ R Ｌ,Fair ｅs Ｊ D,R ｅyno ｌds A Ｃ． Numeric ａl Ana ｌysis. Alpine Ｐress,19８１ [2]易大义,沈云宝，李有法编.计算方法.杭州:浙江大学出版社,2002 [3]易大义，陈道琦编．数值分析引论.杭州:浙江大学出版社,1998
[4]李庆阳，王能超，易大义编.数值分析(第四版）．北京：清华大学出版社，施普林格出版社,2０01 [５]冯康等编.数值计算方法．北京:国防工业出版社，1978
The Ｍain Ｅｌem ｅnts Of T ｈe Colum ｎ El ｉmi ｎａｔion F ｏｒ So ｌ
ｖｉｎg Eq ｕa ｔio ｎｓ
[Ａｂstr ａｃｔ] In t ｈe natural scie ｎces ａnd engineerin ｇ， ｔｈｅre are ｍany p ｒo ｂlems b ｏｉｌed ｄo ｗn to solv ｉng ｌi ｎear e ｑua ｔion ｓ or nonline ａｒ equ ａtions ｏf m ａthema ｔica ｌ p ｒｏble ｍs ． Such a ｓ, th ｅ ｐr ｏblems of netwo ｒk in the ｅle ｃtricit ｙ， the c ｕr ｖe f ｉtting figuring out t ｈｅ e ｘp ｅrimen ｔal data with the ｌeast sq ｕａre method, c ｏmputing of ｃu ｂic spline ｉnterp ｏl ａｔi ｏn, e ｔc. Ｔhe direct met ｈｏds t ｏ ｓo ｌv ｅ the lin ｅa ｒ eq ｕａti ｏn ｓ are Ｐｉvo ｔing Gau ｓs ｉan E ｌimin ａti ｏn Meth ｏd, Squ ａr ｅ Ro ｏt M ｅt ｈod, C ａtc ｈｉng Met ｈod, etc. T ｈe m ａin el ｅm ｅnts of t ｈｅ ｃｏl ｕm ｎ e ｌiminati ｏｎ b ｅlon ｇs t ｏ Pi ｖoting Ｇa ｕss ｉan Elimi ｎat ｉon Ｍethod, an ｄ also ｉs u ｓe ｄ ｃomm ｏnly i ｎ ｔｈe c ａｌculat ｉon of the actual pi ｖotin ｇ e ｌimi ｎat ｉon. This article is di ｓｃu ｓsing ｔｈe ｕse of the main e ｌements o ｆ t ｈe ｃｏlumn ｅli ｍinat ｉo ｎ in so ｌｖing lin ｅar equati ｏns proble ｍs.
[Key Ｗｏｒd ｓ] By colum ｎ ｐiv ｏtin ｇ，Excha ｎge ，Ｅli ｍｉnat ｉon ，Back s ｕb ｓtitut ｉon
附件1:
＃incｌuｄe<ｓtdio.ｈ>
#inｃlｕdｅ
ｖoｉd main（)
{int n=7,ｋ，j,p,i；ｆｌoat E，deｔ＝１.０，ｍ,z;
ｆlｏａt b[7]=｛7,8,1０,13,1７,22，28｝，c0,ｔemp；
ｆｌoat A[7］[7]={{1,1，1,1,1,1,1},｛2，1，1,1，１，1，１}，{３,2，1,１,1,1,1},｛4，３,２,1,1,1,１},{5，4,3,2,１,1,１｝,｛6,5,4，3,２，1，1},{7,6,5,４,３,2,１}};
ｐｒiｎｔf（"输入Ｅ的值:");scａnf(＂%f＂,&E);
fｏｒ(ｋ＝０;k {c0=A[k］[k]; fｏr(i=k；ｉ<７；i＋+) ?if(Ａ［i］[k］>ｃ0){ｃ0=Ａ[i][k］;ｐ=i；｝ ｉf(ｆaｂs(ｃ0) eｌse {ｉf(p！=ｋ){ ｆor(j=0；ｊ<7;j++)｛ teｍｐ＝Ａ［ｐ][j];A［p]［ｊ]=A［ｋ][j］;A［ｋ][j]=teｍp;} temｐ=ｂ[ｐ];ｂ［ｐ]=b［k]；b[k]=tｅmp; dｅt=-ｄet;} for（i=k+1;i＜7;ｉ++） {ｍ=Ａ[i]［k]／Ａ[ｋ][k]; for（j＝k;j<7;j＋+）A［ｉ][j]=A[ｉ][ｊ]-m*Ａ［k]［j］； ｂ[i]=ｂ[i]-m＊b[k]; } dｅt=A[k][k]＊dｅt; } } c０＝Ａ[5］［5]; for(i=5;i<7；i+＋) ?ｉｆ(A［i］［5]>c0){c0=A[ｉ]［５];p=i;} ｉf(p!＝5) {foｒ（j=0;j<7；j+＋) {temｐ=A[p］［j];A[p]［ｊ］＝A[５][j];A［5］［j]=teｍp;} temｐ=b[p］;b[p]=b[5];b[5]=tｅmp; det=-det; } ｉf(A[6］［6]!=0)b[6]=ｂ[6]／A[6]［6]; fｏr（i=n-２;ｉ＞=0;i--) {ｚ=0；for(ｊ=ｉ＋１;j b［i］=（b[i]-z)/A[i][i]； } ｄeｔ=Ａ[6][6]*det;?ｐｒｉｎtf("输出的ｘ值:\n"）; for(i=0；ｉ<7;i++)printf（"x(%d)=%ｆ＼n",i＋1,ｂ[ｉ]); } 附件2 ＃incｌude ＜stdio．h> ＃includｅ ｖoid main() {iｎt n＝7,k,j,ｐ,i,l;float Ｅ,ｄet＝１.0,m,z; floaｔb[7]={7,8,10,13，１７,22，28},c0,teｍp; ｆｌoatA［7][7]={{1，1,1,1,１,1，1｝，｛２，1，1,１,1，１,１},{3,2,1,1,１，1,１｝,{4,3,2,1,1，１,1},｛5,4,3,2,1，1，1}, {6,5,４，３，2，１,1},｛７，6，5,4,3,2,1}}; prinｔｆ(＂输入E的值："); scanf("％f",＆E); ｆor（k＝0;k＜n-２;k＋+) {c0=A[k][k]; for(ｉ=k;i＜７;i++) ??fｏr(j=k；j<7;j++） ??if(Ａ［ｉ］[j]>ｃ0){c0＝Ａ[i]［j];p=i;l=ｊ;} if（ｆａｂs（ｃ０) else { if(p！=k）{ for(j=0；ｊ＜7；j++）{tｅmp=A[p][j］;A[ｐ]［j]＝Ａ[ｋ][j]；A[k][j]=ｔemp;} teｍp＝b［p];b[p]＝b[k];b［k］=tｅｍp; deｔ＝-det；} ?if(l！＝ｋ){ ?ｆor（j=0;j<７;ｊ++){ｔemp＝Ａ[ｊ][l];Ａ[j］[l]=A[j][k];Ａ[j]［k］＝teｍp;｝ ?} } ｆoｒ(i=k+１;i<7;i++) ｛m=A[i］[k］／Ａ[k]［k]; fｏｒ(j=k;ｊ<7;j++)A［i][j]=A[i][j]－m*A［k]［j］； b[i]=b［i]-ｍ*b[k];} dｅｔ=A［k]［k]*dｅt; } c０=A[5]［５]; for(i=5;i<７;i+＋)if(A[ｉ]［５]>c0){c0=A[i][５];p=i；} ｉf(ｐ!＝5） {foｒ(j=0;j<7;j+＋)｛ｔemｐ=A[p][j];A[p]［j］=Ａ[5][ｊ];A［5][j］=ｔemｐ;} tｅmp=ｂ[p];b[p]＝ｂ[5];b[５]=temｐ; det＝-det; } ｉf（A[6][6]!=0)b［6］=ｂ［６]／A[6][6]； for(i=n-２;i>＝0;ｉ-－) {z＝０; foｒ（j=ｉ+1;j ｂ[i]=(b[i]－ｚ)/A［i]［ｉ];｝ dｅt=A[6］[6]*ｄet;? prｉntf(＂输出的x值:\n")； for(i＝0;i<7;i+＋) priｎtｆ（"ｘ(%d）＝％f\n＂,ｉ+1,ｂ[i])；｝ 实验一 列主元消去法 【实验内容】 1．掌握列主元消去法的基本思路和迭代步骤 2．并能够利用列主元的高斯消去法解任意阶数的线性方程组； 3、从课后题中选一题进行验证，得出正确结果，交回实验报告与计算结果。 【实验方法与步骤】 1．列主元消去法基本思路 设有线性方程组Ax b =，设A 是可逆矩阵。列主元消去法的基本思想就是通过列主元的选取将初等行变换作用于方程组的增广矩阵[]|B A b =，将其中的A 变换成一个上三角矩阵，然后求解这个三角形方程组。 2．列主元高斯消去法算法描述 将方程组用增广矩阵[]()(1)|ij n n B A b a ?+==表示。 步骤1：消元过程，对1,2,,1k n =-L （1） 选主元，找{},1,,k i k k n ∈+L 使得 ,max k i k ik k i n a a ≤≤= （2） 如果,0k i k a =，则矩阵A 奇异，程序结束；否则执行（3）； （3） 如果k i k ≠，则交换第k 行与第k i 行对应元素位置，k kj i j a a ?， ,,1j k n =+L ； （4） 消元，对,,i k n =L ，计算/,ik ik kk l a a =对1,,1j k n =++L ，计算 .ij ij ik kj a a l a =- 步骤 2：回代过程： （1） 若0,nn a =则矩阵奇异，程序结束；否则执行（2）； （2） ,1/;n n n nn x a a +=对1,,2,1i n =-L ，计算 ,11/n i i n ij j ii j i x a a x a +=+??=- ??? ∑ [实验程序] #include 2013-2014（1）专业课程实践论文题目：高斯列主元素消去法 一、算法理论 1. 消元过程：消元结果冲掉A ，行乘数冲掉(k)ik a i >，det 存放行列式。 （1）1det ?。 （2）对于1,2,n-1k =…，做①~⑤： ①按列选主元k c ，即确定k i 使 |||| max k k i k ik k i n c a a ≤≤==。 ②若0k c =，则输出错误信息；停机。 ③若k i k =转④，否则执行换行 ,,,1,,,;det det. k k kj i j k i a a j k k n b b ?=+?-= ④消元计算： ,,+1,ik ik ik kk a l a i k k n a = ?= ，, ,,1,,.,1,,. ij ik ik ij i ik k i a l a a i j k n b l b b i k n -?=+-?=+ ⑤ det det kk a ??。 （3）若0nm a =，则判断n b 是否等于零： ①0n b ≠，则输出“无解”信息；停机。 ②0n b =，则输出“非唯一解”，停机。 若0nm a ≠，则det det nn a ??。 2. 回带过程：解冲掉b . 1,,1,,2,1.n n n nm n i ij j j i i j ij b x b a b a b x b i n a =+= ???- ? ??=?=-∑ 3. 输出12,,,n x x x 及det 。det 值的大小可以作为方程组是否病态的参考。 #include %利用高斯列主元消去法求如下线性方程组的解 clear all; A=[3 -2 1 -1;4 0 -1 2;0 0 2 3;0 0 0 5]; b=[8;-3;11;15]; function [X,XA] = UpGaussFun(A,b) %利用高斯列主元消去法求如下线性方程组的解 %A为一个n阶上三角非奇异矩阵 %b为线性方程组的阐述向量 %X为线性方程组AX=b的解 %XA为消元后的系数矩阵 N=size(A); n=N(1); index=0; for i=1:(n-1) me=max(abs(A(1:n,i)));%选列主元 for k=i:n if(abs(A(k,i))==me) index=k; break; end; end; end; temp=A(i,1:n); A(i,1:n)=A(index,1:n); A(index,1:n)=temp; bb=b(index); b(index)=b(i); b(i)=bb;%交换主行 for j=(i+1):n if(a(i,i)==0) disp('?????a???a0￡?'); return; end; l=A(j,i); m=A(i,i); A(j,1:n)=A(j,1:n)-l*A(i,1:n)/m; b(j)=b(j)-l*b(i)/m; end; X=UpTriangleFun(A,b); XA=A; ----------------------------------------------------------------------------------------------------------------------------- % 函数定义 function [X,XA]= UpGaussFun(A,b) %利用高斯列主元消去法求如下线性方程组的解 %A为一个n阶上三角非奇异矩阵 %b为线性方程组的阐述向量 %X为线性方程组AX=b的解 %XA为消元后的系数矩阵 [N,M]=size(A); %N=sizes(A); n=N; index=0; for i=1:(n-1) me=max(abs(A(1:n,i))); %选列主元 for k=i:n if(abs(A(k,i))==me) index=k; break; end; end; temp=A(i,1:n); A(i,1:n)=A(index,1:n); A(index,1:n)=temp; bb=b(index); b(index)=b(i); b(i)=bb; %交换主行 for j=(i+1):n if(A(i,i)==0) disp('?????a???a0￡?'); return; end; l=A(j,i); m=A(i,i); A(j,1:n)=A(j,1:n)-l*A(i,1:n)/m; b(j)=b(j)-l*b(i)/m; end; end; 一、 列主元素Gauss 消去法、Jacobi 迭代法原理及计算方法 1. 列主元素Gauss 消去法： 1.1 Gauss 消去法基本原理 设有方程组Ax b =，设A 是可逆矩阵。高斯消去法的基本思想就是将矩阵的初等行变换作用于方程组的增广矩阵[]B A b = ，将其中的A 变换成一个上三角矩阵，然后求解这个三角形方程组。 1.2 列主元Gauss 消去法计算步骤 将方程组用增广矩阵[]()(1)ij n n B A b a ?+== 表示。 1). 消元过程 对1,2,,1k n =- (1) 选主元，找{},1,,k i k k n ∈+ 使得 ,max k i k ik k i n a a ≤≤= (2) 如果,0k i k a =，则矩阵A 奇异，程序结束；否则执行(3)。 (3) 如果k i k ≠，则交换第k 行与第k i 行对应元素位置，k kj i j a a ?，,,1j k n =+ 。 (4) 消元，对,,i k n = ，计算/,ik ik kk l a a =对1,,1j k n =++ ，计算 .ij ij ik kj a a l a =- 2). 回代过程 (1) 若0,nn a =则矩阵奇异，程序结束；否则执行(2)。 (2) ,1/;n n n nn x a a += 对1,,2,1i n =- ，计算,11/n i i n ij j ii j i x a a x a +=+??=- ??? ∑ 2. Jacobi 迭代法 2.1 Jacobi 迭代法基本原理 Jacobi 迭代法的基本思想是对n 元线性方程组b Ax =，.,n n R b R A ∈∈将其变形为等价方程组f Bx x +=，其中.,,n n n n R x R f R B ∈∈∈?B 成为迭代矩阵。从某一取定的初始向量)0(x 出发,按照一个适当的迭代公式 ,逐次计算出向量f Bx x k k +=+)()1( （ 1,0=k ）,使得向量序列}{)(k x 收敛于方程组的精确解. 贵州师范大学数学与计算机科学学院学生实验报告 课程名称：数值分析班级：数本（一）班实验日期：年月日 学号： 0098（81）姓名：吴胜指导教师：杨一都 实验成绩：一、实验名称 实验五:线性方程组的数值解法 二、实验目的及要求 1. 让学生掌握用列主元gauss消去法、超松弛迭代法求解线性方程组. 2. 培养Matlab编程与上机调试能力. 三、实验环境 每人一台计算机，要求安装Windows XP操作系统，Microsoft office2003、(或. 四、实验内容 1. 编制逐次超松弛迭代(SOR迭代)函数(子程序),并用于求解方程组 ???????=-++=+-+=++-=+++-1 4141414432143214 3214321x x x x x x x x x x x x x x x x 取初始向量T x )1,1,1,1()0(=,迭代控制条件为 5)1()(102 1 ||||--?≤-k k x x 请绘制出迭代次数与松弛因子关系的函数曲线,给出最佳松弛因子.SOR 迭代的收敛速度是否一定比Gauss-Seidel 迭代快 2. 编制列主元 Gauss 消去法函数(子程序),并用于解 ??? ??=++-=-+-=+-6 15318153312321 321321x x x x x x x x x 要求输出方程组的解和消元后的增广矩阵. 注：题2必须写实验报告 五、算法描述及实验步骤 Gauss 消去法： 功能 解方程组b Ax = . 输入 n ,n n ij a A ?=)(,T n b b b b ),,,(21 =. 输出 方程组的解T n x x x x ),,,(21 =或失败信息. 步1 对1,,2,1-=n k 执行步2→步4 . 步2 调选列主元模块 . 一、实验目的与要求 了解Guass列主元消去法及其应用，掌握利用Guass列主元消去法解方程，解决实际问题 二、模型求解 0.x+0.4y+0.3z+60000=x 0.3x+0.1y+0.2z+30000=y 0.2x+0.1y+0.2z+50000=z 三、源代码： #include void swap(double &a,double &b)//换行 { double temp; temp=a; a=b; a=temp; } void gauss(double a[][N],double b[N],int n)//gauss求解 { int i,j,k,l; double temp,m; for(k=0;k<=n-2;k++) { temp=fabs(a[k][k]); //选主元 l=k; for(i=k+1;i temp=fabs(a[i][k]); l=i; } } if(fabs(a[l][k]) 高斯列主元消元法解线性方程组 一、题目：用Gauss 列主元消去法解线性方程组Ax b =，其中， A=17.031 -0.615 -2.991 1.007 -1.006 0.000-1.000 34.211 -1.000 -2.100 0.300 -1.7000.000 0.500 13.000 -0.500 1.000 -1.5004.501 3.110 -3.907 -61.705 12.170 8.9990.101 -8.012 -0.017 -0.910 4.918 0.1001.000 2.000 3.000 4.500 5.000 21.803?? ? ? ? ? ? ? ? ??? 0.230 -52.322 54.000 240.236 29.304 -117.818b ?? ? ? ?= ? ? ? ? ??? T X=(0.907099 -1.961798 3.293738 -4.500708 3.029344 -5.255068) 二、原理及步骤分析 设 n n ij R a A ?∈=][)1(，n n R b b b b ∈=],,,[)1()2(2)1(1 。若约化主元素 ),,2,1(0)(n k a k kk =≠，则通过高斯消元法将方程b AX =约化为三角形方程组求解。 如果在消元过程中发现某个约化主元0) (=k kk a , 则第K 次消元就无法进行。此外，即 使所有约化主元全不为零，虽然可以完成方程组的求解，但也无法保证结果的可靠性，因为计算过程中存在舍入误差。 为减少计算过程中的舍入误差对解的影响，在每次消元前，应先选择绝对值尽可能大的元作为约元的主元，如果在子块的第一列中选取主元，则相应方法称为列主元消元法。相应过程为： （1）选主元：在子块的第一列中选择一个元) (k k i k a 使) (max k ik n i k k k i a a k ≤≤= 并将第k 行元与第k i 行元互换。 （2）消元计算：对k=1,2,……n-1依次计算 ()()()?? ?? ?????++=-=++=-=++==++n k k i b m b b n k k j i a m a a n k k i a a m k k ik k i k i k kj ik k ij k ij k kk k ik k ik ,,2,1,,2,1,,,2,1) ()()1() ()()1()() ()( （3）回代求解 实验一 列主元消去法 【实验内容】1. 掌握列主元消去法的基本思路和迭代步骤 2. 并能够利用列主元的高斯消去法解任意阶数的线性方程组； 【实验方法与步骤】列主元消去法编写程序 1．列主元消去法基本思路 设有线性方程组Ax b =，设A 是可逆矩阵。列主元消去法的基本思想就是通过列主元的选取将初等行变换作用于方程组的增广矩阵[]|B A b =，将其中的A 变换成一个上三角矩阵，然后求解这个三角形方程组。 2．列主元高斯消去法算法描述 将方程组用增广矩阵[]()(1)|ij n n B A b a ?+==表示。 步骤1：消元过程，对1,2,,1k n =- （1） 选主元，找{},1,,k i k k n ∈+ 使得 ,max k i k ik k i n a a ≤≤= （2） 如果,0k i k a =，则矩阵A 奇异，程序结束；否则执行（3）； （3） 如果k i k ≠，则交换第k 行与第k i 行对应元素位置，k kj i j a a ?， ,,1j k n =+ ； （4） 消元，对,,i k n = ，计算/,ik ik kk l a a =对1,,1j k n =++ ，计算 .ij ij ik kj a a l a =- 步骤 2：回代过程： （1） 若0,nn a =则矩阵奇异，程序结束；否则执行（2）； （2） ,1/;n n n nn x a a +=对1,,2,1i n =- ，计算 ,11/n i i n ij j ii j i x a a x a +=+??=- ??? ∑ 习题3第一题程序如下 #include 《Gauss列主元消去法》实验报告 实验名称：Gauss列主元消去法程序设计？？？成绩：_________ 专业班级：数学与应用数学1202班？姓名：王晓阳？??学号： 实？验？日？期：？2014?年11月10日 实验报告日期：？2014年？11月10日 一.实验目的 1. 学习Gauss消去法的基本思路和迭代步骤. 2. 学会运用matlab编写高斯消去法和列主元消去法程序，求解线性方程组. 3. 当绝对值较小时，采用高斯列主元消去法? 4. 培养编程与上机调试能力. 二、实验内容 用消去法解线性方程组的基本思想是用逐次消去未知数的方法把原线性方程组Ax二b 化为与其等价的三角形线性方程组，而求解三角形线性方程组可用回代的方法求解 1. 求解一般线性方程组的高斯消去法? (1) 消元过程： 设a kk k-0 ,第i个方程减去第k个方程的m ik Tk k倍，("k 1^1, n)，得到 A k1x=b k1. 经过n-1次消元，可把方程组A1^b1化为上三角方程组A n x=b n. ⑵回代过程: 以解如下线性方程组为例测试结果 2. 列主元消去法 由高斯消去法可知，在消元过程中可能出现a kk k =0的情况，这是消去法将无法进行, 即使主元素a kk k-0但很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠.这时就需要选取主元素，假定线性方程组的系数矩阵A是菲奇异的. (1)消元过程： 对于k =1,2,川,n -1，进行如下步骤: 1) 按列选主元，记 2) 交换增广阵A的p,k两行的元素 A(k,j)=A(p,j) ( j=k,…,n +1) 3) 交换常数项b的p,k两行的元素。 b(k)=b(p) 4) 计算消元 (2) 回代过程 (3) 以解如下线性方程组为例测试结果 三、实验环境 MATLAB R2014a 四、实验步骤 列主元素消去法求解方程组 [摘 要]在自然科学和工程中有很多问题的解决归结为求解线性方程组或者非线性方程组的数学问题。例如，电学中的网络问题，用最小二乘法求实验数据的曲线拟合问题，三次样条的插值问题等等。求解线性方程组的直接法主要有选主元高斯消去法、平方根法、追赶法等。列主元素消去法既是选主元高斯消去法的一种，也是实际计算中常用的部分选主元消去法。本文即是讨论利用列主元素消去法求解线性方程组问题。 [关键词]按列选主元 交换 消元 回代 一 列主元素消去法背景 在科学研究和工程技术中有许多问题可归结为求解线性代数方程组，其中所产生的线性方程组，其系数矩阵大致可分为两种：一种是低阶稠密矩阵；另一类是大型稀疏矩阵（此类矩阵阶数高，但零元素较多）。对于这两种矩阵，我们可以把线性代数方程组的数值解法大致的分为两类：直接法和迭代法。迭代法一般用来求解大型稀疏矩阵方程组（本文不予讨论）；直接法是目前计算机上解低阶稠密矩阵的有效方法，如果计算过程中没有舍入误差，则此种方法通过有限步四则运算可求的方程组的精确解，但实际计算中由于舍入误差的存在和影响，这种方法也只能求得方程组的近似解。直接法主要有选主元素高斯消去法、平方根法、追赶法等。本文所要讨论的列主元素消去法就是选主元素高斯消去法中的一种。 高斯消去法是一个古老的求解线性方程组的方法，也是解线性方程组问题中较为常见的一种数值方法。但在采取高斯消去法解方程组时，当采用绝对值很小的主元素时，可能导致计算结果的失败，故在消去法中应避免采用绝对值很小的主元素。对于一般的线性方程组，需要引进选主元的技巧，即在高斯消去法的每一步应该在系数矩阵或消元后的低价矩阵中选取绝对值最大的元素作为主元素，保持乘数1 ik m ，以便减少计算过程中舍入误差对计算解的影响。 选主元素消元法则是对高斯消去法的改进，是解低价稠密矩阵方程组的有效方法。选主元素消元法则避免了采用绝对值很小的主元素。选主元素消去法主要有完全主元素消去法与列主元素消去法两种。完全主元素消去法即是每次按行列选取绝对值最大的元素作为 实验内容 1．编写用高斯消元法解线性方程组的MATLAB程序，并求解下面的线性方程组，然后用逆矩阵解方程组的方法验证. （1） 123 123 123 0.101 2.304 3.555 1.183 1.347 3.712 4.623 2.137 2.835 1.072 5.643 3.035 x x x x x x x x x ++= ? ? -++= ? ?-++= ? （2） 123 123 123 528 28321 361 x x x x x x x x x ++= ? ? +-= ? ?--= ? MATLAB计算源程序 1. 用高斯消元法解线性方程组b AX=的MATLAB程序 输入的量：系数矩阵A和常系数向量b； 输出的量：系数矩阵A和增广矩阵B的秩RA,RB, 方程组中未知量的个数n 和有关方程组解X及其解的信息. function [RA,RB,n,X]=gaus(A,b) B=[A b]; n=length(b); RA=rank(A); RB=rank(B);zhica=RB-RA; if zhica>0, disp('请注意：因为RA~=RB，所以此方程组无解.') return end if RA==RB if RA==n disp('请注意：因为RA=RB=n，所以此方程组有唯一解.') X=zeros(n,1); C=zeros(1,n+1); for p= 1:n-1 for k=p+1:n m= B(k,p)/ B(p,p); B(k,p:n+1)= B(k,p:n+1)-m* B(p,p:n+1); end end b=B(1:n,n+1);A=B(1:n,1:n); X(n)=b(n)/A(n,n); for q=n-1:-1:1 X(q)=(b(q)-sum(A(q,q+1:n)*X(q+1:n)))/A(q,q); end else disp('请注意：因为RA=RB 2012-2013（1）专业课程实践论文 完全主元素消去法 董健0818180101，R数学08-1班 陈泊宇0818180116，R数学08-1班 一、算法理论 设方程组的增广矩阵为 ????????? ? ????? ?????=n nn nj n n i n i j i i i n j n j b a a a a b a a a a b a a a a b a a a a B i 1 111111121 2122222211111211 首先在A 中选取绝对值最大的元素作为主元素，例如0max 1111≠=≤≤≤≤ij n j n i j i a a ，然后交 换B 的第一行与第1i 行，第1列于第1j 列，经第一次消元计算得 ()().,,)2()2(b A b A → 重复上述过程，设已完成第k-1步的选主元素，交换两行及交换两列，消元计算，（A ，b ）约化为 () ????????? ? ?? ??? ???? ?=n nn nk k kn kk n n k k b a a b a a b a a b a a a b A 2222111211)()(,， 其中)(k A 元素仍记作ij a ，)(k b 元素仍记作().1,.2,1-=n k b i 第K 步选主元素（在)(k A 右下角方框内选），即确定k k j i ,使 .0m a x ≠=≤≤≤≤ij n j k n i k j i a a k k 交换())()(,k k b A 第k 行与k i 行元素交换())(k A 第k 列与k j 列元素，将k k j i a 调到（k,k ）位置，在进行消元计算，最后将原方程组化为 ,212122211211? ???? ? ??????=????????????????????????n n nn n n b b b y y y a a a a a a 其中n y y y ,,,21 的次序为未知数n x x x ,,21调换后的次序。回代求解得 数学与计算机学院数值计算实验报告 年级 2011 学号 2011434061 姓名张硕硕成绩 专业信息与计算科学实验地点主楼402 指导教师高少芹 实验项目 Gauss列主元素消去法实验日期 2013.11 一、实验题目 Gauss列主元素消去法 二、需求分析 (1) 本实验使用的相关开发工具为MATLAB (2) 输入的形式和输入值的范围以及输出的形式 输入的形式:A=[1 -1 2 -1;2 -2 3 -3;1 1 1 0;1 -1 4 3]; b=[-8 -20 -2 4]; 输出的形式： b = -7.0000 3.0000 2.0000 2.0000 (3) 程序所能达到的功能 通过输入矩阵的形式，实现计算机计算计算线性方程组的解。 (4) 测试数据： 在实验结果中给出 三、程序流程图 四、数据结构及算法描述 1.输入矩阵A，右端向量b 2.对于k=1:n-1, （1）|A(u,k)|=max|A(i,k)| (k<=i<=n); %选主元 （2）如果|A(u,k)|=0则停止; %控制最小主元 （3）如果u=k则转（4），否则 A(k,k:n+1)A(u,k:n+1); %换行 （4）A(k+1:n,k):=A(k+1:n,k)/A(k,k), A(k+1:n,k+1:n):=A(k+1:n,k+1:n)-A(k+1:n,k)*A(k,k+1:n), %消元按行进行 b(k+1:n)’:=b(k+1:n)’-A(k+1:n,k)*b(k) 3.如果A(n,n)=0则停止 %无解 4.b(n):=b(n)/A(n,n), 对于i=n-1:-1:1, b(i):=[b(i)-A(i,i+1:n)*b(i+1:n)’]/A(i,i) %回代求解 5.输出b 五、调试分析 内容包括： (1)在调试过程中，会出现精度问题以及数字的显示格式带来的误差，通过百度学习修改这 些问题。 (2)根据算法中的（4），消元过程中，第k步运算做乘法(n-k)(n-k+1)次,做除法n-k次，完成 n-1步消元共需做乘除法的总次数为：n3/3+n2/2-5n/6, 由算法的第4步知，回代过程的乘除法运算次数为：n2/2+n/2， 故算法运算的总次数为：MD=n3/3+n2-n/3， 当n很大时，约为n3/3。 (3)通过上机计算使我学会了程序的录入和Matlab的使用操作；通过计算结果的比较，使我 了解求线性方程组的精度不但与方法有关，而且与问题的性态有关，也让我更进一步了解Gauss列主元素消去法。 六、使用说明 使用列主元消元法解方程组c语言代码 # include t=A[i][h]; A[i][h]=A[k][h]; A[k][h]=t; } } } else { printf("A是非奇异矩阵！\n"); break; } /* 消去过程*/ for (m=i+1;m 计算方法实验报告1 【课题名称】 用列主元高斯消去法和列主元三角分解法解线性方程 【目的和意义】 高斯消去法是一个古老的求解线性方程组的方法，但由它改进得到的选主元的高斯消去法则是目前计算机上常用的解低阶稠密矩阵方程组的有效方法。 用高斯消去法解线性方程组的基本思想时用矩阵行的初等变换将系数矩阵A 约化为具有简单形式的矩阵（上三角矩阵、单位矩阵等），而三角形方程组则可以直接回带求解 用高斯消去法解线性方程组b Ax =（其中A ∈Rn ×n ）的计算量为：乘除法运算步骤为 32(1)(1)(21)(1)(1)262233n n n n n n n n n n n MD n ----+= +++=+-，加减运算步骤为 (1)(21)(1)(1)(1)(25) 6226n n n n n n n n n n AS -----+= ++= 。相比之下，传统的克莱姆 法则则较为繁琐，如求解20阶线性方程组，克莱姆法则大约要19 510?次乘法，而用高斯消去法只需要3060次乘除法。 在高斯消去法运算的过程中，如果出现abs(A(i,i))等于零或过小的情况，则会导致矩阵元素数量级严重增长和舍入误差的扩散，使得最后的计算结果不可靠，所以目前计算机上常用的解低阶稠密矩阵方程的快速有效的方法时列主元高斯消去法，从而使计算结果更加精确。 2、列主元三角分解法 高斯消去法的消去过程，实质上是将A 分解为两个三角矩阵的乘积A=LU ，并求解Ly=b 的过程。回带过程就是求解上三角方程组Ux=y 。所以在实际的运算中，矩阵L 和U 可以直接计算出，而不需要任何中间步骤，从而在计算过程中将高斯消去法的步骤进行了进一步的简略，大大提高了运算速度，这就是三角分解法 采用选主元的方式与列主元高斯消去法一样，也是为了避免除数过小，从而保证了计算的精确度 【计算公式】 1、 列主元高斯消去法 设有线性方程组Ax=b ，其中设A 为非奇异矩阵。方程组的增广矩阵为 第1步（k=1）：首先在A 的第一列中选取绝对值最大的元素 1 l a ，作为第一步的主元素: 111211212222112[,]n n n l n nn n a a a a b a a a b a a a b ?????? ?? =?????? ?? ????a b 列主元消去法MATLAB程序： function [RA,RB,n,X]=liezhu(A,b) B=[A b]; n=length(b); RA=rank(A); RB=rank(B);zhica=RB-RA; if zhica>0, disp('??×￠òa￡oòò?aRA~=RB￡??ùò?′?·?3ì×é?T?a.') return end if RA==RB if RA==n disp('??×￠òa￡oòò?aRA=RB=n￡??ùò?′?·?3ì×éóD?¨ò??a.') X=zeros(n,1); C=zeros(1,n+1); for p= 1:n-1 [Y,j]=max(abs(B(p:n,p))); C=B(p,:); B(p,:)= B(j+p-1,:); B(j+p-1,:)=C; for k=p+1:n m= B(k,p)/ B(p,p); B(k,p:n+1)= B(k,p:n+1)-m* B(p,p:n+1); end end b=B(1:n,n+1);A=B(1:n,1:n); X(n)=b(n)/A(n,n); for q=n-1:-1:1 X(q)=(b(q)- sum(A(q,q+1:n)*X(q+1:n)))/A(q,q); end else disp('??×￠òa￡oòò?aRA=RB 列主元消除法，M文件 a=[2.51 1.48 4.53;1.48 0.93 -1.30 ;2.68 3.04 -1.48]; b=[0.05;1.03;-0.53]; [RA,RB,n,X]=liezhu(a,b) 运行结果； 数值分析大作业 －－――（高斯列主元消去法求解线性方程组） 课程名称：数值分析 授课老师：宋国乡 指导导师：丁振国 学生：王伟伟 学号：0425121523 日期：2004/11/20 高斯列主元消去法解线性方程组 一：问题的提出 我们都知道，高斯列主元素消去法是计算机上常用来求解线性方程组的一种直接的方法。就是在不考虑舍入误差的情况下，经过有限步的四则运算可以得到线性方程组的准确解的一类方法。实际运算的时候因为只能有限小数去计算，因此只能得到近似值。在实际运算的时候，我们很多时候也常用高斯消去法。但是高斯消去法在计算机中运算的时候常会碰到两个问题。 1．一旦遇到某个主元等于0，消元过程便无法进行下去。 2．在长期使用中还发现，即使消元过程能进行下去，但是当某个主元的绝对值很小时，求解出的结果与真实结果相差甚远。 为了避免高斯消去法消元过程中出现的上述两个问题，一般采用所谓的选择主元法。其中又可以分为列选主元和全面选主元两种方法。目前计算机上常用的按列选主元的方法。因此我在这里做的也是列选主元高斯消去法。 二、算法的基本思想 大家知道，如果一个线性方程组的系数矩阵是上三角矩阵时，即这种方程组我们称之为上三角方程组，它是很容易求解的。我们只要把方程组的最下面的一个方程求解出来，在把求得的解带入倒数第二个方程，求出第二个解，依次往上回代求解。然而，现实中大多数线性方程组都不是上面所说的上三角方程组，所以我们有可以把不是上三角的方程通过一定的算法化成上三角方程组，由此我们可以很方便地求出方程组的解。高斯消元法的目的就是把一般线性方程组简化成上三角方程组。于是高斯消元法的基本思想是：通过逐次消元将所给的线性方程 《数值分析》实验报告 实验编号：实验二 课题名称：列主元Gauss消去法 一、算法介绍 1、输入矩阵的阶数n，方程组的增广矩阵A； 2、对k=0,1,…,n-2，循环：选取列中绝对值最大的元素，将主元所在的行的元素保存在 数组temp[n+1]中。若主元为零，则系数矩阵奇异，计算停止；否则，顺序进行。如果绝对值最大的元素就在矩阵的对角线上，则进行普通高斯消元法的第一大步，否则将方程组系数换行之后再进行普通高斯消元法的第一大步； 3、然后利用回代法求解线性方程组。 二、程序代码 #include 数值分析计算实习题 第5章解线性方程组的直接方法 【选题 列主元高斯消去法解线性方程组。 书上的计算实习题1、2、3都要求用列主元高斯消去法解线性方程组，所以考虑写一个普适的程序来实现。 对于线性方程组Ax二b,程序允许用户从文件读入矩阵数据或直接在屏幕输入数据。 文件输入格式要求: (1)第一行为一个整数n (2<=n<=100)，表示矩阵阶数。 (2)第2~n+l行为矩阵A各行列的值。 (3)第n+2~n+n+2行为矩阵b各行的值。 屏幕输入：按提示输入各个数据。 输出：A. b、det(A).列主元高斯消去计算过程、解向量X。 【算法说明】 设有线性方程组Ax=b,其中设A为非奇异矩阵。方程组的增广矩阵为 ?12 ?21 [Nb] = 第1步（k=l ）：首先在A的第一列中选取绝对值最大的元素?I,作为第一步的主元素: ?|| H0 然后交换（A, b）的第1行与第I行元素，再进行消元计算。 设列主元素消去法已经完成第1步到第k?l步的按列选主元，交换两行，消元计算得到与原方程组等价的方程组 A（k）x=b（k） 4? …4;) …唸) ? 忒 ? ? 輕 ■ [A.b]T[A ⑹,b")] = ??■ 咲■ ■ ■ ■ ■ * *■ 〃伏) ?? - % ■ 第k步计算如下: 对于 k=l, 2, ?…，0-1 （1）按列选主元：即确定t使 （2）如果tHk,则交换［A, b］第t行与第k行元素。（3）消元计算 5 4* J 叫=一鱼(=^ + 1,…,H) % 吗 <-?y + 〃如伽 (fJ = R + l,…/) b- <-勺+加汝仇， (i = /c + l,…,《) 消元乘数mik 满足: n (%-D 内) X1 < ------ -- ---- 9(j = ? 一 1,?一2■…J)tk M 1,(,=斤 +1, ???,?) fet e (4)回代求解数值分析列主元消去法的实验报告
高斯列主元素消去法
利用高斯列主元消去法求如下线性方程组的解
列主元素Gauss消去法Jacobi迭代法原理及计算方法
Gauss列主元消去法
Guass列主元消去法及其应用
高斯列主元消元法解线性方程组
列主元消去法
Gauss列主元消去法程序设计
列主元素消去法求解方程组
高斯消元法 主元消去法
完全主元素消去法
Gauss列主元素消去法
使用列主元消元法解方程组 c语言代码
列主元高斯消去法和列主元三角分解法解线性方程
列主元消去法MATLAB程序
高斯列主元消去法
数值分析实验二(列主元Gauss消去法)
数值分析计算实习题列主元高斯消去法解线性方程组
相关主题
文本预览