解线性方程组的直接法
许多科学技术问题要归结为解含有多个未知量x1, x2, …, xn的线性方程组
EMBED Equation.3 EMBED Equation.3 （3.1）
这里aij (i, j = 1, 2, …, n)为方程组的系数，bi（i = 1, 2, …, n）为方程组自由项。方程组（3.1）的矩阵形式为：
AX = b
其中
EMBED Equation.3
线性方程组的数值解法可以分为直接法和迭代法两类。所谓直接法，就是不考虑舍入误差，通过有限步骤四则运算即能求得线性方程组（3.1）准确解的方法。如克莱姆法则，但通过第一章的分析，我们知道用克莱姆法则来求解线性代数方程组并不实用，因而寻求线性方程组的快速而有效的解法是十分重要的。
本章讨论计算机上常用而有效的直接解法――高斯消去法和矩阵的三角分解等问题。为方便计，设所讨论的线性方程组的系数行列式不等于零。
§1 高斯消去法
高斯（Gauss）消去法是解线性方程组最常用的方法之一，它的基本思想是通过逐步消元，把方程组化为系数矩阵为三角形矩阵的同解方程组，然后用回代法解此三角形方程组得原方程组的解。下面先讨论三角形方程组的解法。
1．三角形方程组的解法
三角形方程组是指下面两种形式的方程组
EMBED Equation.3 （3.2）
和
EMBED Equation.3 （3.3）
方程组（3.2）叫做下三角形方程组，方程组（3.3）叫做上三角形方程组，三角形方程组的求解是很简单的。
如果aii( 0，i = 1, 2,…, n，则（3.2）的解为
EMBED Equation.3 k = 2, 3,…, n （3.4）
如何学习手绘此过程称为前推过程。
同样地，若aii ( 0, i = 1, 2,…, n，则（3.3）的解为
EMBED Equation.3 （3.5）
此过程称为回代过程。
从上面的公式来看，求出xk，需要作k – 1次乘法和加减法及一次除法，总共完成 EMBED Equation.3 次乘法、加法及n次除法。
从（3.4）、（3.5）可以看出，求解三角形方程组是很简单的，只要把方程组化成了等价的三角形方程组，求解过程就很容易完成。
2．高斯消去法
交通培训为便于叙述，先以一个三阶线性方程组为例来说明高斯消去法的基本思想。
EMBED Equation.3
把方程（I）乘（ EMBED Equation.3 ）后加到方程（II）上去，把方程（I）乘（ ）后加到方程（III）上去，即可消去方程（II）、（III）中的x1，得同解方程组
EMBED Equation.3
将方程（II）乘（ EMBED Equation.3 ）后加于方程（III），得同解方程组：
EMBED Equation.3
由回代公式（3.5）得 x3 = 2 x2 = 8 x1 = -13
下面考察一般形式的线性方程组的解法，为叙述问题方便，将bi写成ai, n+1，i = 1, 2,…,n。
EMBED Equation.3 （3.6）
如果
a11 ( 0，将第一个方程中x1的系数化为1，得
EMBED Equation.3
姿势近义词其中 EMBED Equation.3 j = 1, …, n + 1
（记 EMBED Equation.3 i = 1, 2, …, n; j = 1, 2, …, n + 1）
从其它n –1 个方程中消x1，使它变成如下形式
EMBED Equation.3 （3.7）
其中 EMBED Equation.3
EMBED Equation.3
由方程（3.6）到（3.7）的过程中，元素 EMBED Equation.3 起着重要的作用，特别地，把 EMBED Equation.3 称为主元素。
如果（3.7）中 EMBED Equation.3 ，则以 EMBED Equation.3 为主元素，又可以把方程组（3.7）化为：
EMBED Equation.3 （3.8）
针对（3.8） 继续消元，重复同样的手段，第k步所要加工的方程组是：
EMBED Equation.3
设 EMBED Equation.3 ，第k步先使上述方程组中第k个方程中xk的系数化为1：
EMBED Equation.3
然后再从其它（n - k）个方程中消xk，消元公式为：
EMBED Equation.3 (3.9)
按照上述步骤进行n次后，将原方程组加工成下列形式：
EMBED Equation.3
回代公式为：
EMBED Equation.3 （3.10）
综上所述，高斯消去法分为消元过程与回代过程，消元过程将所给方程组加工成上三角形方程组，再经回代过程求解。
由于计算时不涉及xi, i = 1, 2, …, n，所以在存贮时可将方程组AX = b，写成增广矩阵（A, b）存贮。
下面，我们统计一下高斯消去法的工作量；在（3.9）第一个式子中，每执行一次需要 EMBED Equation.3 次除法，在（3.9）第二个式子中，每执行一次需要 EMBED Equation.3 次除法。因此在消元过程中，共需要
EMBED Equation.3
次乘作法。此外，回代过程共有
EMBED Equation.3
次乘法。汇总在一起，高斯消去法的计算量为：
EMBED Equation.3
次乘除法。
3．主元素消去法
前述的消去过程中，未知量是按其出现于方程组中的自然顺序消去的，所以又叫顺序消去法。实际上已经发现顺序消去法有很大的缺点。设用作除数的 EMBED Equation.3 为主元素，首先，消元过程
中可能出现 EMBED Equation.3 为零的情况，此时消元过程亦无法进行下去；其次如果主元素 EMBED Equation.3 很小，由于舍入误差和有效位数消失等因素，其本身常常有较大的相对误差，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，使得所求的解误差过大，以致失真。
我们来看一个例子：
例
EMBED Equation.3
它的精确解为：
EMBED Equation.3
EMBED Equation.3
用顺序消去法，第一步以0.0001为主元，从第二个方程中消x1后可得：
海生EMBED Equation.3
回代可得 x1 = 0.00
显然，这不是解。
造成
这个现象的原因是：第一步主元素太小，使得消元后所得的三角形方程组很不准确所致。
如果我们选第二个方程中x1的系数1.00为主元素来消去第一个方程中的x1，则得出如下方程式：
1.00 x1 = 1.00 x1 = 1.00
这是真解的三位正确舍入值。
从上述例子中可以看出，在消元过程中适当选取主元素是十分必要的。误差分析的理论和计算实践均表明：顺序消元法在系数矩阵A为对称正定时，可以保证此过程对舍入误差的数值稳定性，对一般的矩阵则必须引入选取主元素的技巧，方能得到满意的结果。
列主元消去法
在列主元消去法中，未知数仍然是顺序地消去的，但是把各方程中要消去的那个未知数的系数按绝对
值最大值作为主元素，然后用顺序消去法的公式求解。
例：用列主元高斯消去法求解方程
EMBED Equation.3
由于解方程组取决于它的系数，因此可用这些系数（包括右端项）所构成的“增广矩阵”作为方程组的一种简化形式。对这种增广矩阵施行消元手续：
EMBED Equation.3
第一步将4选为主元素，并把主元素所在的行定为主元行，然后将主元行换到第一行得到
EMBED Equation.3
消元过程的结果归结到下列三角形方程组：
EMBED Equation.3
回代，得
EMBED Equation.3
列主元消去法计算步骤：
输入矩阵阶数 EMBED Equation.3 ，增广矩阵 EMBED Equation.3
对 EMBED Equation.3
按列选主元：选取 EMBED Equation.3 使
EMBED Equation.3
如果 EMBED Equation.3 ，交换 EMBED Equation.3 的 第k行与底l 行元素
消元计算 ：
EMBED Equation.3
EMBED Equation.3
回代计算：
EMBED Equation.3
4、输出解向量 EMBED Equation.3 。
4．无回代过程的主元消去法
设有线性代数方程组
AX = b
其中A为n ( n阶非奇异矩阵，b为n ( 1阶矩阵（列向量），由A-1AX = A-1b得X = A-1b。
因此，只要求出A-1就可以得到解X。另外，有许多问题需要求矩阵的逆，例如常用的回归分析方法中，要求出相关矩阵的逆，因此，有必要讨论在计算机上常用的求逆方法。
步骤：
第一步选主元，在第一列中选绝对值最大的元素 EMBED Equation.3 ，设第k行为主元行，将主元行换至第一行，将第一个方程中x1的系数变为1，并从其余n – 1个方程中消去x1。
第二步：在第二列后n – 1个元素中选主元，将第二个方程中x2的系数变为1，并从其它n – 1个方程中消去x2。
…
…
依此类推，直到每个方程中仅有一个变量为止。此过程进行到第k – 1步后，方程组将变成如下形式：
EMBED Equation.3
第k步：在第k列后n – k个元素中选主元，换行，将第k个方程xk
的系数变为1，从其它方程中消去变量xk，消元公式为：
EMBED Equation.3 （3.11）
EMBED Equation.3
对k = 1, 2, …, 按上述步骤进行到第n步后，方程组变为：
EMBED Equation.3
即为所求的解
5．无回代消去法的应用
（1）解线性方程组系
设要解的线性方程组系为：
AX = b1, AX = b2, AX = bm
其中
EMBED Equation.3
正月里可以剪头发吗上述方程组系可以写为
AX = B = (b1, …, bm)
因此 X = A-1B
即为线性方程组系的解。在计算机上只需要增加几组右端常数项的存贮单元，其结构解一个方程组时一样。
行 系数
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
（2）求逆矩阵
设A = (aij)n(n是非奇矩阵，(A( ( 0，且令
EMBED Equation.3
由于 AA-1 = AX = I
因此，求A-1的问题相当于解下列线性方程组
EMBED Equation.3
也就是相当于（I）中m = n, B = I的情形。
（3）求行列式的值
由于行列式任意一行(列)的元素乘以同一个数后，加到另一行（列）的对应元素上，其行列式的值不变；任意对换两行（列）的位置其值反号；三角矩阵的行列式之值等于其主对角元素的乘积。因此，可用高斯消去法将 (A(化成
EMBED Equation.3
§2 解三对角方程组的追赶法
在实际问题中，经常遇到以下形式的方程组
EMBED Equation.3 （3.12）
这种方程组的系数矩阵称为三对角矩阵
EMBED Equation.3
以下针对这种方程组的特点提供一种简便有效的算法—追赶法。
追赶法实际上是高斯消去法的一种简化形式，它同样分消元与回代两个过程。
先将（3.12）第一个方程中x1的系数化为1
EMBED Equation.3
记 EMBED Equation.3 （3.13）
有 EMBED Equation.3
注意到剩下的方程中，实际上只有第二个方程中含有变量x1，因此消元手续可以简化。利用（3.13）可将第二个方程化为
EMBED Equation.3
这样一步一步地顺序加工（3.12）的每个方程，设第k – 1个方程已经变成
EMBED Equation.3 （3.14）
再利用（3.14）从第k个方程中消去xk-1，得：
EMBED Equation.3
同除 EMBED Equation.3 ，得
EMBED Equation.3
记
EMBED Equation.3
则有 EMBED Equation.3
这样做n – 1步以后，便得到：
EMBED Equation.3
将上式与（3.12）中第11个方程联立，即可解出
xn = yn
这里
EMBED Equation.3
于是，通过消元过程，所给方程组（3.12）可归结为以下更为简单的形式：
EMBED Equation.3 （3.15）
这种方程组称作二对角型方程组，其系数矩阵中的非零元素集中分步在主对角线和一条次主对角线上
EMBED Equation.3
吃脑虫对加工得到的方程组（3.15）自下而上逐步回代，即可依次求出xn，xn-1，…，x1，计算公式为：
EMBED Equation.3 （3.16）
上述算法就是追赶法，它的消元过程与回代过程分别称作“追”过程与“赶”过程。综合追与赶的过程，得如下计算公式：
EMBED Equation.3 （3.17）
EMBED Equation.3 （3.18）
矩阵的三角分解及其在解方程组中的应用
下面我们进一步用矩阵理论来分析高斯消去法，从而建立矩阵的三角分解定理，而这个定理在解方程组的直接解法中起着重要作用，我们将利用它来推导某些具有特殊的系数矩阵方程组的数值解法。
考虑线性方程组
AX = b A(Rn(n
设解此方程组用高期消去法能够完成（不进行变换两行的初等变换），由于对A施行初等变换相当于用初等矩阵左乘A，于是，高斯消去法的求解过程用矩阵理论来叙述如下：
记：
EMBED Equation.3
其中 EMBED Equation.3 记 EMBED Equation.3
于是
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
如此继续下去，到n – 1步时有：
EMBED Equation.3
也就是说
EMBED Equation.3
南通市住房公积金
记
EMBED Equation.3
则有 A = LU
其中L为单位下三角矩阵，U为上三角矩阵。
总结上述讨论得到重要性定理
定理1：（矩阵的三角分解）设A为n ( n实矩阵，如果解AX = b用高斯消去法能够完成（限制不进行行的交换，即 EMBED Equation.3 ），则矩阵A可分解为单位下三角矩阵L与上三角知阵U的乘积。
A = LU
且这种分解是唯一的。
证明：由上述的讨论，存在性已得证，现在证唯一性。
设 A = L1 U1 = LU
其中L1，L1为单位下三角阵，U1，U为上三角阵，设 EMBED Equation.3 存在，于是有
EMBED Equation.3
上式右端为上三角矩阵，左边为单位下三角阵，故应为单位矩阵。即
L1 = L U1 = U 证完
那么矩阵A在什么条件下才能保证约化主元素 EMBED Equation.3 （k = 1, 2, …, n）？为此给出以下
定理2：约化主元素 EMBED Equation.3 （i = 1, 2, …, k）
充要条件是矩阵A的顺序主子式
EMBED Equation.3
EMBED Equation.3
由上述讨论知，解 AX = b的高斯消去法相当于实现了A的三角分解，如果我们能直接从矩阵A的元素得到计算L，U的元素的公式，实现A的三角分解，而不需要任何中间步骤，那么求解AX = b的问题就等价于求解两个三角形矩阵方程组
（1）Ly = b 求y
（2）UX = y 求x
下面来说明L、U的元素可以由A的元素直接计算确定。显然，由矩阵乘法。
闺蜜EMBED Equation.3
得到U的第一行元素；由 EMBED Equation.3 得
EMBED Equation.3
即
L的第一列元素。设已经求出U的第1行~第r – 1行元素，L的第1列~第r – 1列元素，由矩阵乘法可得：
EMBED Equation.3
EMBED Equation.3
即可计算出U的第r行元素，L的第r列元素。
综上所述，可得到用直接三角分解法解AX = b的计算公式。
（1） EMBED Equation.3 （3.19）
EMBED Equation.3 （3.20）
对于r = 2, 3, …, n计算
（2）计算U的第r行元素
***[JimiSoft: Unregistered Software ONLY Convert Part Of File! Read Help To Know How To Register.]***
.3
l21 = 2 l 31 = 3
（2）对于r = 2，利用（3.21）计算
EMBED Equation.3 = 5 – 2 ( 2 = 1
EMBED Equation.3 = 2 – 2 (3 = -4
EMBED Equation.3
（3）r = 3
EMBED Equation.3
于是
EMBED Equation.3
（4）求解：
Ly = b 得到
y1 = 14
y 2 = b2 – l21y1 = 18 – 2 ( 14 = -10
y3 = b3 – (l31y1 + l32y2) = 20 – (3( 14 + (-5)(-10)) = - 72
从而 y = (14, -10, -72)T
由Ux= y 得到
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
§4 平方根法
1．矩阵的LDR分解
以上介绍了矩阵的三角分解及唯一性定理，为使分解式规范化，我们给出矩阵LDR分解。
定理3：如果n阶方程A的所有顺序主子式均不等于零，则矩阵A存在唯一的分解式
A = LDR其中L和R分别是n阶单位下三角阵和单位上三角阵，D是n阶对角元素的不为零的对角阵，上述分解也称为A的LDR分解。
证明：充分性：因为A的顺序主子式均不为零，Gauss消去法得以完成，即实现了一个Doolittle分解A = LU（或Crout分解 EMBED Equation.3 ）U的对角元素 EMBED Equation.3 EMBED Equation.3 ，这时，令
EMBED Equation.3 则
EMBED Equation.3
其中 EMBED Equation.3
存在性得证。
唯一性：当A非奇时，L、D、R皆非奇，若还存在另一个LDR分解A = L1D1R1，这里L1, D1, R1也非奇，则有
LDR = L1D1R1
即 EMBED Equation.3
上式左端是单位下三角矩阵，右端是上三角矩阵，所以应该是单位矩阵，即
EMBED Equation.3
EMBED Equation.3 EMBED Equation.3
从而必有 EMBED Equation.3
也即R1 = R D1 = D 唯一性得证。
必要性：假定A有唯一的LDR分解，且L, D, R均非奇，从而LiDiRi均非奇i = 1, 2,…, n，而Ai = LiDiRi，所以Ai (i = 1, 2,…, n)也非奇。 证完
2．平方根法
在科学研究和工程技术的实际计算中遇到的
