第2章解线性方程组的直接解法_313007480

1、第章 解线性方程组的直接解法§0 引言若非奇异，即，方程组有唯一解。由Cramer法则，其解其中为用代替中第列所得的矩阵。当大时，个行列式计算量相当大，实际计算不现实。§1 Gauss消去法（I）Gauss消去法的例子（1）（2） 方程组与方程组同解得（3）由（3）得（3）的系数矩阵为，上三角矩阵。（II）Gauss消去法，矩阵三角分解 令第1次消去 ,令 作运算： 表示第个方程（第行） 如果令令 进行k-1步后，得 以上完成了消去过程，A非奇异；倒着求解这称为回代过程。消去过程和回代过程结合起来称为（顺序）Gauss消去法，从消去过程可以得出。其中是一个上三角阵。记此矩阵

2、是对角线元素为1的下三角矩阵，称其为单位下三角阵。 定义1.1 设 令是1至阶行列式，称为A的顺序主子式。Gauss消去过程能进行下去的条件应为，而此条件必在消去过程中才能知道。定理1.2 全不为零的充分必要条件是A的顺序主子式，其中 证明“”（必要性）设，则可进行消去过程的步，每步由A逐次实行的运算得到，这些运算不改变相应顺序主子式的值，所以有“充分性”设命题对于k-1成立，现设。由归纳假设有，Gauss消去可以进行k-1步。化为其中为对角元为的上三角阵。由于是由A经“一行（方程）乘一数加至另一行（方程）”逐步得到的，因此A的k阶顺序主子式等于的k阶顺序主子式，即由 。 Gauss消去过程其

3、中L为单位下三角阵，为上三角阵。以后记为U，那么A=LU定理1.3非奇异矩阵，若其顺序主子式，那么存在唯一的单位下三角阵L和上三角阵U，使得A=LU。证明 Gauss消去过程已给出L，U。下面证明唯一性设A有两个分解，其中为单位下三角阵，为上三角阵，因A非奇异都可逆。仍为上三角阵，也是上三角阵，为单位下三角阵 可以证明，当A为奇异阵时，定理仍成立，A的LU分解，L为单位下三角阵，U为上三角阵，此分解称Doolittle分解。若将上三角阵，其中D为对角阵，为单位上三角阵，并记 那么有其中为下三角阵，为单位上三角阵，此分解称为Crout分解。其中L为单位下三角阵，D为对角阵，U为单位上三角阵，此称

4、为A的LDU分解。定理1.4 非奇异阵有唯一的LDU分解（D为对角阵，L为单位下三角阵，U为单位上三角阵）的充分必要条件是A的顺序主子式皆是非零。如果A奇异，上述定理也成立。§2 列主元Gauss消去法例2.1 用三位十进制浮点运算求解解 用（顺序）Gauss消去法在3位十进制运算的限制下，得代回第一个方程得，此解不对 求解不对的原因是用小数作除数，使是个大数，在计算的值完全被掩盖了：如果对方程组先作变换，再用Gauss消去法可以得。列主元消去法 进行第1步消去之前，在A的第1列中选出绝对值最大的元素 即，其中。由于A非奇异，有，这一步骤称为选主元。如果， 则消去过程与顺序Gauss

5、消去法一样如果，则先进行换行，然后再Gauss消去运算，得。进行了k-1步选主元，换行和消去的步骤，得，第k步先选主元，使 由于非奇异，有若，则进行顺序Gauss消去法的第k步若，则对先换行： ，然后再进行类似顺序Gauss消去法的运算。如上进行n-1步选主元，换行与消去法运算，得，此方程组与Ax=b等价。为上三角阵，再回代求解。例2.2 用列主元法解方程组Ax=b，计算过程取5位数字，其中解 选主元，换行再作行变换得到 对选列主元，作换行，计算再作行变换，得到消去过程完。回代计算得解此题精确解为而不用列主元的顺序Gauss消去法有§3 直接三角分解方法（I）Doolittle分解法

6、根据A的元素来确定L.U中的元素 L，U的元素可由n步直接计算定出，其中第k步定出U的第k行，L的第k列。第1步 ，得出U的第1行元素。得出L的第1列的元素。第k步：假定已定出U的第1行到第k-1行的元素与L的第1列到第k-1列的元素。利用矩阵乘法有计算U的第k行 （1）对于 计算L的第k列 （2）由第1步，第2步，第n-1步就完成A=LU，解方程组 Ax=b , LUX=b 分两步 Ly=b y=L-1b其实，L为单位下三角阵，逐次向前代入 Ux=y x=U-1y 其实，U为上三角阵，逐次向后回代定理3.1非奇异,，那么Ax=b可用直接分解方法来求解。例3.2求矩阵 的LU分解 解 先求出U

7、的第1行 求出L的第1列： U的第2行 L的第2列 U的第3行定理3.3 非奇异阵，若其顺序主子式皆非零，则存在唯一的单位下三角阵L和上三角阵U，使得A=LU同样地有A有唯一的分解，A=LDU；A非奇异条件不加，定理还真，L为单位下三角阵，D为对角阵，U为单位上三角阵。单位上三角阵A=LU（L单位下三角阵，U上三角阵），此分解称为Doolittle分解。如果把A=LDU（LD）U=LU（L下三角阵，U单位上三角阵），此分解称crout分解（II）直接三角分解法解线性代数方程组A非奇异，令 求解 等价于求解 例3.4 用Doolittle分解法解方程组 Ax=b, 其中解 （III） 三对角方程

8、组的追赶法设方程组 A为三对角矩阵如果A满足LU分解条件，那么可以进行Doolittle分解。A是三对角阵，L，U有如下形式利用A=LU，及矩阵乘法有依次计算 解原来方程组可分成两步 计算公式为：这个过程称为解三对角方程线的追赶法。例 用追赶法解利用矩阵乘法有 追赶法在西方用Thomas算法的名称定理3.5 其元素满足 A非奇异，A分解中元素满足定理可以看出，0， 用追赶法可以进行计算。又有的估计式，即追赶法中，中间变量有界，不会产生很大变化，由此可以有效计算出结果，即计算是稳定的。定理条件即为追赶法稳定计算的条件。（IV）对称正定矩阵的cholesky分解解法 称A正定A对称正定A的全部特征

9、值为正A对称正定A的顺序主子式;由于A对称正定，因此A有唯一的LU分解，定理3.6 ，对称，且A的顺序主子式 ，那么A可以唯一分解为 ，其中D为对角阵，L为单位下三角阵证 ，L为单位下三角阵，为单位上三角阵,由于 由LU分解的唯一性，从而有定理3.7 设 对称正定，则存在唯一的对角元为正的下三角阵L使 这种分解称为Cholesky分解证 利用上一定理知A有唯一分解 ，其中为单位下三角阵。 A对称正定，A的顺序主子式 。而 ，从而有 令 ，那么有 。具体分解方法当 时 由于求解过程中，需开方，因此称其为平方根法。方程组求解（1） （2） 例3.8 用Cholesky方法求解方程组其中解 A对称，

10、 ；A对称正定 ， §4 矩阵范数（I）向量范数定义 如果向量（或）的某个实值函数，满足条件：（1）充分必要条件（2）（3） ，三角不等式则称是上的一个向量范数（或上的一个范数），一般用表示。 常用的向量范数向量的-范数 向量的1-范数 向量的2-范数例 计算向量 的范数。解 定理 4.1 ，非奇异，上一个范数，令 ，那么上的一个范数证 满足条件 任 ； （A非奇异） 对任 上的一个范数定理4.2 设为上的一个向量范数，那么是的分量的连续函数。定义4.3 设为上两个向量范数，若存在使得对任 有那么称是等价的。可以证明（II）矩阵范数定义4.4 设 上实值函数，对任有唯一的数相对应，如

11、果满足条件（1） （2）（3）（4）那么称为上矩阵范数定理4.5 设是上的向量范数，那么定义4.6 对于上的任一种向量范数，由定理4.5确定的矩阵范数称为从属于向量范数的矩阵范数，即称从属范数，也称算子范数。由定理可以得出满足此条件，称所给的矩阵范数与向量范数是相容的。设，如果对于R（或C）中一个数，存在中非零向量使得那么称为矩阵A的特征值，称为A的属于特征值的一个特征向量。 称为A的特征多项式。为A特征值 为特征多项式的根。为其特征值，令 称为A的谱半径。定理4.7 证：设为A的任一特征值，为相应的特征向量，那么有由定理4.5 可以得出，单位矩阵 有；常用范数有定理4.8 设 ，那么有 （1

12、） ， 行范数 （2） ， 列范数 （3） 证：（1）对任 由于 的任意性，有下面将证明 存在 使取 满足推论4.9 如果A是对称 称为对称；设为A的特征值，为相应的特征向量 例4.10 求解 的特征多项式 Jordan标准形设，矩阵称为属于特征值的Jordan块(阶)。由若干个Jordan块，所构成的分块对角阵 称为一个Jordan形矩阵定理4.11 复数域上每一个矩阵都相似于一个Jordan形矩阵，这个Jordan形矩阵除了其中Jordan块的排列次序外是由原矩阵唯一确定的，称这个Jordan形矩阵为原矩阵的Jordan标准形。定义4.12 ，如果存在可逆矩阵使得则称A与B是相似的 。定理

13、4.13 对任，实数，那么至少存在一种算子范数（从属范数）使得证明 对任 ，存在非奇异阵 使J为A的Jordan标准形。对于给定 ，定义对角矩阵令 其中 取的范数注意到是非奇异阵。引入新的向量范数（定理4.1）由定理4.1 ， 为向量范数。令 。对于引入的范数，令 。矩阵范数还具有如下性质： 是A的元素的连续函数 （等价性）对于上任两范数，存在常数使得对于常用矩阵范数有定理4.14 设 是上的算子范数，矩阵满足，那么非奇异，并且证 用反证法。设I+B为奇异阵，那么存在使得。 为B的一个特征值。从而有，并，矛盾于定理条件，所以I+B非奇异。令 §5 误差分析（I）引言准确解 若A，b作

14、微小的扰动准确解 A， b的微小扰动 。引起B， 了解的很大变化，其原因？（II）条件数定义5.1 设为可逆矩阵，为一种矩阵的算子范数。称为A的条件数如果矩阵范数取为，那么记同样地， ， 逆矩阵定义5.2 ，划去A的元所在的第行，第列，剩下的个元素按原来排法组成的n-1级矩阵的行列式称为A的元的余子式，记为。令称是矩阵A的元的代数余子式定义5.3 设是级方阵，用表示A的元的代数余子式，矩阵称为A的伴随矩阵。记为例5.4 求 解 解 例5.5 ，求解 ； 定义5.6 设 ，如果A的条件数是一个大数，那么称A是坏条件的或称A为病态的。条件数性质 证： 若A为正交阵 ，那么证： 设U为正交阵，那么有证： 它们特征值相同，所以有 设分别为A的按模最大与最小的特征值，那么 特别，A对称，那么有 证 注意 为A的特征值 为的特征值A对称时 （III）扰动方程组解的误差估计如果有一个扰动，有一个扰动，那么方程组的解必扰动，即有 分析 对的影响，即的大小。定义5.7 如果 很小，而很大，那么称是病态方程组。反之，如果很小，也很小，那么称是良态方程组。定理5.8 设非奇异， ，；（常数向量b的扰动引起解的扰动的一种估计）证： ， 对于 例5.9 其解 假定b有扰动。 解 解之 可以看出，是很大的。方程组是病态的。