3. 线性方程组

§3线性方程组一、含n 个未知量n 个方程的线性方程组的解法[齐次和非齐次线性方程组] 含n 个未知量n 个方程的线性方程组取如下形式：⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a 22112222212111212111 （1） 当常数项b 1,b 2,...,b n 不全为零时，（1）称为非齐次线性方程组；当b 1,b 2,...,b n 全为零时，（1）称为齐次线性方程组. 如果记A =(a ij )=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡nn n n n n a a a a a a a a a 212222111211（系数矩阵）x =(x 1,x 2,...,x n )τ b =(b 1,b 2,...,b n )τ （常数项矢量）式中τ表示转置，那末线性方程组（1）可写成矩阵形式A x =b （2）[逆矩阵法] 当⎪A ⎪≠0时，线性方程组（2）的解为x =1-A b式中1-A 是系数矩阵A 的逆矩阵，x 称为（2）的解矢量.[克莱姆法则] 若⎪A ⎪≠0，则方程组（1）的解为Ax 11∆=,Ax 22∆=, ... , Ax nn ∆=式中nnn nn n a a b a a b a a b 2222211211=∆, nnnnn nn a a a a b a a b a a b a213123221131112=∆, ... ,nn n n n n n n b b b a a a a a a a a a211,211,222211,11211---=∆这里∆j (j=1,2,...,n)是以常数项矢量b 替换A 中第j 列矢量后得到的n 阶行列式.特别 1° 二阶线性方程组⎩⎨⎧=+=+222111c y b x a c y b x a 的解为∆∆=x x , ∆∆=y y式中02211≠=∆b a b a , 2211b c b c x =∆, 2211c a c a y =∆2° 三阶线性方程组⎪⎩⎪⎨⎧=++=++=++333322221111d z c y b x a dz c y b x a d z c y b x a 的解为∆∆=xx , ∆∆=y y ,∆∆=zz 式中0333222111≠=∆c b a c b a c b a , 333222111c bd c b d c b d x =∆ 333222111c d a c d a c d a y =∆, 333222111d b a d b a d b a z =∆ [有回代过程的主元素消去法（高斯消去法）] 对于n 阶线性方程组),2,1(1,1n i a x an i nj j ij==+=∑可用矩阵表成⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡+++1,1,21,121212222111211n n n n n nn n n n n a a a x x x a a a a a aa a a消元步骤：（1）在系数矩阵中找出绝对值最大的元素（这元素称为主元素），不妨设a 11（第1行第1列元素）为主元素，（不然，如果ij a 为主元素，可先将第i 个方程与第1个方程互换位置，再把未知数x 1和x j 的次序调换，那末得到新的系数矩阵，其主元素必在第1行第1列上）.将第1个方程乘以111a a i -，分别与第i 个方程相加（i =2,3,...,n ）,得到新的n 阶线性方程组，用矩阵表示如下 ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡++++1,1,31,21,13213233332223221131211000n n n n n n nn n n n n n b b b a x x x x b b b b b b b b b a a a a（2）在除第1行外的系数矩阵中找出主元素，不妨设b 22为主元素.再将第二个方程乘以222b b i -分别与第i 个方程相加(i=3,4,...n ),得到新的n 阶线性方程组，用矩阵表示如下 ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡++++1,1,31,21,1321333322322113121100000n n n n n n nn n n n n c c b a x x x x c c c c b b ba a a a(3）按照（1），（2）的方法进行n 2-次以后，在第1至n 2-行外的系数矩阵⎥⎦⎤⎢⎣⎡----n n n n n n n n e e e e ,1,,11,1 中找出主元素，不妨设1,1--n n e 为主元素，将第n 1-个方程乘以1,11,----n n n n e e 与第n 个方程相加，得到新的n 阶线性方程组，用矩阵表示如下⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡++-+++-------1,1,11,31,21,11321,11,131,333,21,2232211,113121100000000n n n n n n n n n nn n n n n n n n n n n m e c b a x x x x x m e e c c c b b b ba a a a a这样做完n 1-次之后，消元过程结束.原来系数矩阵已经化成上三角形矩阵（这时未知数的次序已做了若干次调换）. 回代步骤：由第n 个方程解出nnn n n m m x 1,+=将x n 代入第n 1-个方程，解出1-n x ，再将1-n x ， x n 代入第n 2-个方程解出2-n x ，...，最后将已解出的x 2，x 3，...，x n 代入第一个方程解出x 1. 注意，这里每当找出主元素后，都经过行与行互换和未知数次序调换等手续，也可以把调换未知数次序的步骤放到第n -1步之后一起去做，同样可以得到三角形的系数矩阵. 例1 用主元素消去法解方程组⎪⎩⎪⎨⎧-=+-=++-=--1220112332311321321321x x x x x x x x x 解 方程组用矩阵表示为：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡----103221111232311321x x x 解的步骤如下：(1) 第2 行第1列的元素－23是主元素，用□框起来，并用矩阵表示成⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-----122101112332311把矩阵第2行乘以2311加到第1行上，把第2行乘以231加到第3行上，得到矩阵⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡----12347233500111233233523520在除第2行外的系数矩阵中找到第二个主元素在第1行第2列上为2352.(2)把第1行乘以5235加到第3行上，得到矩阵 第二行互换第一行与⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡--525352530001233233523520⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡--52535253003233553520011123(3)由第三个方程解出13=x ，将3x 代入第二个方程，解出22=x ，将2x ,3x 代入第一个方程，解出11=x .于是方程组的解为(1,2,1). [无回代过程的主元素消去法] 这种方法与上法基本一样，不同之处在于每次消元时，都用某一方程去消去其余所有n -1个方程的未知数，例如上面方法的消元步骤（2）中，改成将第二个方程乘以222b b i -分别与第i 个方程相加，i=1,3,4,...,n （共n -1个，与上面方法不同的是，这里包括i =1,并设a 12=b 12），得到新的系数矩阵是⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡nn n n n n c c c c b b bc c a 33332232211311000000而最后得到对角系数矩阵是：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡nn m c b a000000000000332211因此不需经过回代过程，即可直接解出各个未知数来. 无回代过程的主元素消去法运算量比有回代过程的大，但在电子计算机上编制程序较为简单. 为了减少运算量，便于编制程序，第一步可在系数矩阵的第1列找出绝对值最大的元素为列主元素，消元后，第二步从系数矩阵的第2列找出列主元素进行消元，等等.这种消元法称为列主元素消去法，它也可达到较好的精确度. [简单迭代法] 一般步骤： （1） 将线性方程组),,2,1(1n i b x ainj j ij==∑=改写成),,2,1(1n i d x c x nj ij ij i =+=∑=（2）任意选取一组初始近似值,,,,)0()0(2)0(1n x x x 作为方程的第0次近似解.（3）依次使k =1,2,3,...,用公式),,2,1(1)1()(n i d x c xnj i k j ij k i=+=∑=-求出方程的第k 次近似解，直至满足ε≤--≤≤)1()(1max k i k i ni x x为止，式中ε>0为预先给定的允许误差.于是第k 次近似解)()(2)(1,,,k nk k x x x 在允许误差ε的范围内满足方程组.注意这里的允许误差不是指近似解与精确解之间的最大绝对误差.例2 用简单迭代法求方程组⎪⎩⎪⎨⎧-=+-=++-=--1220112332311321321321x x x x x x x x x 的解，其允许误差002.0＝ε. 解 根据例1可化为方程组⎪⎪⎪⎩⎪⎪⎪⎨⎧'-=+-'=-'=++-)3(123472335)2(323352352)1(011233232321x x x x x x x 分别由)3(),2(),1(''',可得迭代方程(满足收敛条件)⎪⎩⎪⎨⎧-=+=++=-----4894.07447.03269.16731.00100.01100.07700.0)1(2)(3)1(3)(2)1(3)1(2)1(1)(1k k k k k k k k x x x x x x x x 选取初始值1)0(3)0(2)0(1===x x x ,逐次迭代得出一系列近似解：迭代19次后得到9943.0)19(1=x ,0000.2)19(2=x ,9985.0)19(3=x 在允许误差002.0＝ε范围内满足方程组.[赛得尔迭代法] 把简单迭代法的步骤（3）中的迭代公式改成),,2,1()1(11)()(n i d x c xc xinij k j ij i j k jij k i=++=∑∑=--=其他步骤同简单迭代法. 在一般情况下，赛得尔迭代法比简单迭代法收敛得快些.例3 用赛得尔迭代法求例2中方程组的解.解 选取初始值1)0(3)0(2)0(1===x x x ,并代入方程)1('计算出8900.0)1(1=x再将1,1,8900.0)0(3)0(2)1(1===x x x 代入方程)2('计算出0000.2)1(2=x再将1,0000.2,8900.0)0(3)1(2)1(1===x x x 代入方程)3('计算出0000.1)1(3=x再将0000.1,0000.2,8900.0)1(3)1(2)1(1===x x x ,按赛得尔迭代法继续迭代可以发现，,,2,1,0000.1,0000.2)(3)(2 ===k x x k k 因此只需考虑方程)1(',10100.021100.07700.0)1(1)(1⨯+⨯+=-k k x x即解方程 2300.07700.011+=x x 得出0000.11=x ,因此方程组的解为0000.11=x ，0000.22=x ，0000.13=x[松弛迭代法] 把简单迭代法的迭代公式改成),,2,1()1()()1(1)1(11)()(n i x d x cxc xk i i ni j k j iji j k jij k i=ω-+++ω=-+=--=∑∑其他步骤同简单迭代法.上式中ω是常数，称为松弛因子.适当选取ω可以提高收敛速度，通常ω取为1.5~2（当取ω∈(1,2)时，称为超松弛迭代法，当取ω∈(0,1)时，称为低松弛迭代法）. [共轭斜量法] 线性方程组A x =b可按下面步骤解出： （1）首先选取适当的近似解为初始值：τ),,,()0()0(2)0(1)0(n x x x x =（2）计算初次残差矢量r (0)=b -A x (0)和矢量 p (0)=A τr (0) 式中A τ为A 的转置矩阵. （3）对i =0,1,2,...,N -1,依次按下列公式迭代),(),(),(),(),(),()()()()()()()()()()()()(i i i i i i i i i i i i i Ap Ap r A r A Ap Ap r A p Ap Ap r Ap a τττ=== x (i+1)=x (i)+a i p (i)r (i+1)=r (i)-a i Ap (i) ),(),()()()1()1(1i i i i i r A r A r A r A ττττβ+++= p (i+1)=A τr (i+1)+βi+1p (i)式中（a ,b ）表示矢量a 和b 的内积（见第八章）. 这一过程只要进行到r (N)足够小即可停止. [追赶法解实三对角线性方程组] 实三对角线性方程组⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡βαγββαγβαγβ--n n n n 000113322211 ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡n x x x 21=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡n b b b 21可按下面步骤解出： 首先计算111βγ=λ,111βb d =再对k =2,3,...,n -1,依次按下列公式迭代1--=k k k k k a λβγλ,11----=k k k k k k k a d a b d λβ最后得到线性方程组的解为⎪⎩⎪⎨⎧--=-=--=+--)1,,2,1(λλβ111 n n k x d x a d a b x k k k k n n n n n nn例4 用追赶法解方程组⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---221410241014321x x x － 解 按上述公式依次计算得到411-=λ, 411=d 15841)1(421-=⎪⎭⎫⎝⎛----=λ, 5341)1(441)1(22=⎪⎭⎫ ⎝⎛-----=d ⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎨⎧⎪⎭⎫ ⎝⎛--=⎪⎭⎫ ⎝⎛-==⎪⎭⎫ ⎝⎛-----=21141411431585343158)1(453)1(2333＝＝－x x x [平方根法解正定矩阵的线性方程组] 设A 为正定矩阵，则线性方程组Ax=b可按下面步骤解出： （1）计算l ij （分解A =LL τ,L =(l ij )为实非奇异下三角形矩阵）),,2,1()(21112n i l a l i k ik ii ii =-=∑-=⎪⎪⎭⎫⎝⎛-==-=∑-=1,,1,,2)(111i j n i l l a l l j k jk ik ij jj ij 式中n 为矩阵A 的阶数.（2）计算y i （解方程组Ly =b ）),,2,1()(111n i y l b l y i k k ik i ii i =-=∑-=（3）计算x i （解方程组L τx =y ）)1,,1,()(11-=-=∑+=n n i x l y l x n i k k ki i ii i[正定带型矩阵的线性方程组解法] 设A =(a ij )为一正定带型矩阵，满足 a ij =0, ⎪i-j ⎪>m (m 为正整数)则线性方程组A x=b可按下面步骤解出： (1) 计算λij .为了节省存储单元，充分利用矩阵的对称和带型特点，只需存储对角线和对角线下的带中元素，这时可以改变a ij 的下标，令a ij =a i,m-i+j例如当n =4,m =2的对称带型矩阵的存储格式为4241323122211244433433322322211211000000a a a a a a a a a a a a a a a a a → 然后按下列公式计算λij ： 当i ≤m 时，),,2,1(21112m i a m i m k ik im im =⎪⎭⎫⎝⎛-=∑-+-=λλ)1,,1;,,2(111,,-+-==⎪⎪⎭⎫ ⎝⎛-=∑-+-=-++-+-m i m j m i a j i m k j m k j m i ik ij m j m i ij λλλλ 当i >m 时，),,1(2112n m i a m k ik im im +=⎪⎭⎫ ⎝⎛-=∑-=λλ)1,,0;,,1(110,,-=+=⎪⎭⎫ ⎝⎛λλ-λ=λ∑-=-++-+-m j n m i a j k j m k j m i ik ij m j m i ij（2）计算y i . 令l ij =λi,m-i+j且按下列公式计算y i ：)()(111m i y l b l y i k k ik i ii i ≤-=∑-=)()(11m i y l b l y i mi k k ik i ii i >-=∑--=（3）计算x i .)()(11m n i x l y l x m i i k k ki i ii i -<-=∑++=)()(11m n i x l y l x n i k k ki i ii i -≥-=∑+=这方法只有当m 远小于n 时才显示出优越性，否则选用其他方法.本公式利用了矩阵的对称性与带型特点，便于在电子计算机上存储，并进行计算.二、一般情形的线性方程组含n 个未知量m 个方程的线性方程组取如下形式⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++mn mn m m n n n n b x a x a x a b x a x a x a b x a x a x a 22112222212********* （1） 记A =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡mn m m n n a a a a a a a a a 212222111211x =(x 1,x 2,...,x n )τ b =(b 1,b 2,...,b m )τ则给定线性方程组的矩阵形式为A x=b（1） 相应的齐次方程组为A x=0（2）A 称为方程组（1）的系数矩阵，C =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡m mn m m n n b b b a a a a a a a a a 21212222111211称为方程组（1）的增广矩阵. [线性方程组有解的判别定理] 以r (A ),r (C )分别表示系数矩阵A 与增广矩阵C 的秩，则有 1° 当m =n 且r (A )= r (C )=n （或⎜A ⎜≠0）时，方程组（1）有唯一解；2° 当r (A )< r (C )时，方程组（1）无解，这时（1）称为矛盾方程组； 3° 当r (A )= r (C )=r <n （或⎜A ⎜=0）时，方程组（1）有无穷多组解；4° 齐次线性方程组（2）有非零解的充分必要条件是：r (A )<n （0=A ）.[线性方程组的解的结构]1° 当r (A )=r <n 时，齐次方程组A x =0的任一非零解x =(x 1,x 2,...,x n )τ都可用它的n -r 个线性无关解x (i)=()),,2,1(,,,)()(2)(1r n i x x x i n i i -=τ的线性组合来表示. 这n -r 个线性无关解称为方程组的基础解系，它不是唯一的.2° 设x (0)=()τ)0()0(2)0(1,,,n x x x 是线性方程组A x=b 的一个特解，则它的任一解x =(x 1,x 2,...,x n)τ都可以表示为x=x (0)+η式中η=τ⎪⎭⎫ ⎝⎛'''n x x x ,,,21 是它相应的齐次方程组A x =0的一个解.三、整系数线性齐次方程组的整数解假设(a ij )m ⨯n 是m ⨯n 整数矩阵，m <n .令A i =∑==nj ijm i a 1),,2,1(那末整系数线性齐次方程组∑===nj j ijm i x a1),,2,1(0的整数解x 1,x 2,...,x n 满足])[(},,,max{012121mn m n A A A x x x -≤<式中[ ]表示整数部分.四、一类线性不等式组的解（克莱姆法则）假设A =(a ij )为n ⨯n 非奇异矩阵，那末线性不等式组i nj j ijb x a≤∑=1b i ≥0 (i =1,2,...,n )的解为),,2,1(det 1n j AA bx ni ijij =≤∑=式中A ij 为矩阵A 的第i 行第j 列元素的代数余子式.。