解三对角方程组的追赶法

解三对角方程组的追赶法第1页，共90页，2023年，2月20日，星期四2第二章解线性方程组的直接方法如果用矩阵形式简记为其中系数矩阵称为三对角方程组.是一种特殊的稀疏矩阵.它的非零元素集中分布在主对角线及其相邻两条对角线上，称为三对角矩阵.方程(2-23)(2-24)p5第2页，共90页，2023年，2月20日，星期四3第二章解线性方程组的直接方法Gauss消去法用于三对角方程组时过程可以大大简化.具体地说，第一次消元只要对第2个方程进行，也就是矩阵其中,第一次消元后，第2个方程变成第3页，共90页，2023年，2月20日，星期四4第二章解线性方程组的直接方法因而在第二次消元时只要对第3个方程进行消元，即是单位下二对角阵

中.因此类推可以得出,三对角矩阵作三角分解时,矩阵的形式也比较简单，其中第4页，共90页，2023年，2月20日，星期四5第二章解线性方程组的直接方法定理2.2

设矩阵（2-24）满足下列条件：

是上二对角阵.p2第5页，共90页，2023年，2月20日，星期四6第二章解线性方程组的直接方法

其中则它可以分解为为矩阵（2-24）中所给出,且分解是唯一的.(2-25)第6页，共90页，2023年，2月20日，星期四7第二章解线性方程组的直接方法

[证明]将式(2-25)右端按乘法规则展开,并与A进行比较,得如果，则由上式可得（2-26）p11第7页，共90页，2023年，2月20日，星期四8第二章解线性方程组的直接方法按Gauss消去法步骤易得，经过次消元后,方程组（2-23）的系数矩阵变成第8页，共90页，2023年，2月20日，星期四9第二章解线性方程组的直接方法其中

由A满足条件（*），显然有又因为从而有于是第9页，共90页，2023年，2月20日，星期四10第二章解线性方程组的直接方法故且矩阵仍满足条件（*）.依次类推可得出因此由式(2-26)唯一地确定了L和U当矩阵（2-24）按式（2-26）可化为求解方程组和解得（2-27）计算进行三角分解后,求解方程组（2-23）第10页，共90页，2023年，2月20日，星期四11第二章解线性方程组的直接方法

再解得方程组（2-23）的解:(2-28)按上述过程求解三对角方程称为追赶法,式（2-26）和式（2-27）结合称为“追”的过程,相当于Gauss消去法中的消元过程.式(2-28)称为“赶”的过程,相当于回代过程.p87第11页，共90页，2023年，2月20日，星期四12第二章解线性方程组的直接方法2．对1.输入算法2.2第12页，共90页，2023年，2月20日，星期四13第二章解线性方程组的直接方法

5．输出4.对,停机.追赶法的基本思想与Gauss消去法及三角分解法相同,只是由于系数中出现了大量的零，计算中可将它们撇开,从而使得计算公式简化，也大大地减少计算量.其乘除运算量为第13页，共90页，2023年，2月20日，星期四14第二章解线性方程组的直接方法§2.4平方根法与改进的平方根法的对角元素皆为正数。工程实际问题的计算中，线性方程组的系数矩阵常常具有对称正定性，矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法。2.4.1平方根法（Cholesky分解法）定理2.3设是对称正定矩阵,则存在唯一的非奇异下三角阵使得（2-29）且第14页，共90页，2023年，2月20日，星期四15第二章解线性方程组的直接方法[证明]因为A由定理2.1,矩阵A

其中角矩阵,且为单位下三角矩阵。则为上三角阵，令因为对称正定,其各阶顺序主子式大于零,存在Doolitle分解，即为单位上三对称，故有第15页，共90页，2023年，2月20日，星期四16第二章解线性方程组的直接方法由Doolitle分解的唯一性，得对任意非零向量于是由即正定，所以的对角元素均为正数。令即是正定的第16页，共90页，2023年，2月20日，星期四17第二章解线性方程组的直接方法其中唯一性。假设存在非奇异下三角阵则为非奇异下三角阵,且对角元素皆为正数.元素皆为正数，且使得其对角于是有第17页，共90页，2023年，2月20日，星期四18第二章解线性方程组的直接方法因为是上三角阵，即，与假设矛盾。

上式必得是下三角阵,故由矩阵的这种分解称为Cholesky分解。用比较法可以导出设的计算公式.p14第18页，共90页，2023年，2月20日，星期四19第二章解线性方程组的直接方法的对角元素皆为正数。2.4.1平方根法（Cholesky分解法）定理2.3设是对称正定矩阵,则存在唯一的非奇异下三角阵,使得（2-29）且矩阵的这种分解称为Cholesky分解。用比较法可以导出设的计算公式.第19页，共90页，2023年，2月20日，星期四20第二章解线性方程组的直接方法比较与这里规定计算顺序是按列进行，即

的相应元素，可得（2-30）第20页，共90页，2023年，2月20日，星期四21第二章解线性方程组的直接方法当矩阵A完成Cholesky分解后，求解方程组就转化为依次求解方程组它们的解分别为即第21页，共90页，2023年，2月20日，星期四22第二章解线性方程组的直接方法Cholesky分解法。这种方法无需选主元，计算过程也是单元也少，只要存贮A的下三角部分和右端项b中存放在A的存贮单元，y,x存放在b但这种方法在求L时需作n了计算量.求解线性方程组的上述方法称为平方根法，也称为稳定的.由于A的对称性,平方根法的乘除运算量为数量级，约是Gauss消去法的一半.上机计算时,所需存贮,计算的存贮单元.次开方运算，这样又增加第22页，共90页，2023年，2月20日，星期四23第二章解线性方程组的直接方法[解]显然系数矩阵是正定矩阵,设

例用平方根法解线性方程组第23页，共90页，2023年，2月20日，星期四解得由由解得第24页，共90页，2023年，2月20日，星期四25第二章解线性方程组的直接方法2.4.2改进的平方根法其中为单位下三角矩阵，为对角阵.记定理2.3的证明过程表明，对称正定矩阵A又可以做如下分解：法

)第25页，共90页，2023年，2月20日，星期四26第二章解线性方程组的直接方法注意到由比较法得第26页，共90页，2023年，2月20日，星期四27第二章解线性方程组的直接方法第27页，共90页，2023年，2月20日，星期四28第二章解线性方程组的直接方法由比较法可以导出分解的计算公式：

对（2-33）计算顺序如下：第28页，共90页，2023年，2月20日，星期四29第二章解线性方程组的直接方法按式（2-33）进行Cholesky分解约增多一倍，乘除总运算量又变成计算是重复的。引进辅助量分解,虽然避免了开方运算,但在计算每个元时多了相乘的因子，故乘法运算次数比数量级，仔细分析式（2-33）可以看出，式中有许多，则式（2-33）可改写成第29页，共90页，2023年，2月20日，星期四30第二章解线性方程组的直接方法（2-34）按式（2-34）进行分解相当，且避免了开方运算。分解，乘除运算量与Cholesky第30页，共90页，2023年，2月20日，星期四31第二章解线性方程组的直接方法矩阵作分解后，解方程组可分两步进行：先解方程组

再由求具体计算公式为（2-35）p34第31页，共90页，2023年，2月20日，星期四32第二章解线性方程组的直接方法求解线性方程组的这一方法称为改进平方根法，也叫法.例6

用改进平方根法求解方程组[解]容易验证，系数矩阵

第32页，共90页，2023年，2月20日，星期四33第二章解线性方程组的直接方法按式（2-34）计算分解式，得为对称正定阵。（2-34）第33页，共90页，2023年，2月20日，星期四34第二章解线性方程组的直接方法按式（2-35）计算，得（2-35）第34页，共90页，2023年，2月20日，星期四35第二章解线性方程组的直接方法所以，方程组的解为称正定线性方程组的好办法。平方根法与改进的平方根法不仅计算量仅是Gauss消去法的一半，其数值稳定性良好，是求解中小型稠密对第35页，共90页，2023年，2月20日，星期四36§2.5误差分析重要的作用。2.5误差分析分析。向量和矩阵的范数及矩阵的条件数在研究

值方法所求得的用数线性方程组解的误差分析中起着十分由于不同的算法计算效果不同，因此必须进行误差第36页，共90页，2023年，2月20日，星期四372.5误差分析2.5.1向量和矩阵的范数就是对向量大小的一种度量，借助于它可以刻画中向量序列的收敛性。

中，向量的模在（一）向量的范数向量的范数是衡量向量大小的度量概念。例如，第37页，共90页，2023年，2月20日，星期四382.5误差分析

一般地，定义范数如下：按一定的规则有若满足且=0，当且仅当对任意实数都有一实数与之对应，记为定义2.1

设对任意向量对任意都有则称为向量x的范数。40第38页，共90页，2023年，2月20日，星期四392.5误差分析中的一种范数。容易验证，向量的模符合以上三条件，因而它是按定义2.1，向量范数的具体形式可以有多种，（1）2-范数常用的有以下三种：第39页，共90页，2023年，2月20日，星期四402.5误差分析（2）1-范数（3）

下面以∞-范数为例进行验证。满足是显然的。由实数绝对值的性质，对任意实数，都有。

∞-范数故对任意向量（1）2-范数第40页，共90页，2023年，2月20日，星期四41有所以成立。如果中有两个范数和存在实数使得对任意n维向量x，都有2.5误差分析则称这两种范数是等价的。第41页，共90页，2023年，2月20日，星期四42对两种等价范数而言，同一向量序列有相同的极限。∞-范数是等价的。有不难证明，1-范数，2-范数和例如，由式（2-36）与式（2-38），对任意2.5误差分析所以，2-范数与∞-

范数是等价的。设则第42页，共90页，2023年，2月20日，星期四43事实上，中任意两种范数都是等价的。是指任意一种向量范数。今后如果不作说明，2.5误差分析（二）矩阵的范数类似于向量范数的定义，可以定义阶矩阵的范数。第43页，共90页，2023年，2月20日，星期四44定义2.2

对任意n阶方阵A，按一定的规则有一实数若满足当且仅当

A=0；对任意实数都有与之对应，记为对任意两个n阶方阵A，B都有2.5误差分析且（相容性条件）为矩阵A的范数.则称第44页，共90页，2023年，2月20日，星期四45~是向量范数定义的直接推广，条件则使矩阵范数在数值计算中使用更为方便。这里2.5误差分析常用的矩阵范数:为n阶方阵。设（1）1-范数或列范数第45页，共90页，2023年，2月20日，星期四462.5误差分析(2)∞-范数或行范数其中表示矩阵(3)2-范数或谱范数的最大特征值(4)Frobenius范数可以证明这四种范数都满足矩阵范数的定义,且第46页，共90页，2023年，2月20日，星期四定义:对任意的n阶方阵和n维向量若不等式成立,则称矩阵范数与向量范数是相容的.47p51第47页，共90页，2023年，2月20日，星期四48[证明]显然且即当且仅当对所有有于是，对任意有所以2.5误差分析例7

若对任意n方阵定义试证为矩阵A的范数(1-范数或列范数)。第48页，共90页，2023年，2月20日，星期四492.5误差分析对任意实数于是对于任意两个n阶方阵第49页，共90页，2023年，2月20日，星期四502.5误差分析

所以是A的矩阵范数。第50页，共90页，2023年，2月20日，星期四512.5误差分析定理2.4

设

A为n阶方阵，是中的向量范数，则是一种矩阵范数，称其为由向量范数诱导出的矩也称算子范数。阵范数，显然有p55(2-39)第51页，共90页，2023年，2月20日，星期四522.5误差分析为单位向量，故显然若则反之，若即对任意非零向量，有由定义2.1之，得所以。[证明]设为任意n阶方阵，x为任意n维非零向量。因为第52页，共90页，2023年，2月20日，星期四532.5误差分析对任意实数，由式（2-39）及定义2.1有对任意两个n阶方阵A和B第53页，共90页，2023年，2月20日，星期四542.5误差分析由式（2-39），对任意n维非零向量x有即于是所以式（2-39）是矩阵A的范数。（2-39）第54页，共90页，2023年，2月20日，星期四552.5误差分析由定理2.4的证明知，由向量范数诱导出的矩阵范，还满足性质对任意n维向量，都有这一性质称为矩阵范数与向量范数的相容性，数除满足定义2.2中的（2-40）在误差分析中经常会用到。第55页，共90页，2023年，2月20日，星期四562.5误差分析常用的矩阵范数有三种，是由三种常用的向量范数为n阶方阵。诱导出的矩阵范数：设(1)1-范数(2)∞-范数第56页，共90页，2023年，2月20日，星期四572.5误差分析其中是矩阵的最大特征值。证明可参考[3]。矩阵的行向量的1-范数的最大值，故它们又分别的特征值有关，所以又称为谱范数。由式（2-37）和式（2-38），矩阵的1-范数为矩阵的列向量的1-范数的最大值，矩阵的-范数为被称为矩阵的列范数和行范数。2-范数与(3)2-范数第57页，共90页，2023年，2月20日，星期四582.5误差分析这三种范数中，1-范数与2-范数有一些好性质，故在理论证明常用它。-范数的计算比较简单，而2-范数较复杂，要计算矩阵的特征值。但数值计算中还有一种常用的范数(4)F-范数第58页，共90页，2023年，2月20日，星期四592.5误差分析矩阵的F-范数可以认为是向量2-范数的直接推广，阵的F-范数与向量的2-范数相容，但F-范数不是对任意一种由向量范数诱导出的矩阵范数都有即将n阶方阵看作维向量所得到.可以证明，矩由向量范数诱导出的矩阵范数.而因为如果将矩阵范数看作向量范数的等价性可得矩阵范数的等价性。空间上的向量范数，则由第59页，共90页，2023年，2月20日，星期四602.5误差分析是A的近似矩阵，分别称为的关于范数与相对误差。矩阵的误差可用矩阵范数表示.设的绝对误差第60页，共90页，2023年，2月20日，星期四612.5误差分析即有扰动，从而使计算结果产生误差，因此需的解为2.5.2方程组的状态与条件数一个实际问题化为数学问题，初始数据往往会有误差，要研究扰动对解的影响。例8:容易看出，方程组第61页，共90页，2023年，2月20日，星期四622.5误差分析而方程组

的解为比较这两个方程组可以看出，它们只是右端项有微，但它们的解小的差别，最大相对误差为却大不相同，解分量的相对误差至少为第62页，共90页，2023年，2月20日，星期四632.5误差分析当一个方程组，由于系数矩阵或右端项的微小扰动，就系数矩阵或右端项分别有扰动的两种情况进有扰动相应的解x的扰动记为而引起解发生巨大变化时，称该方程组是“病态”的，为了定量刻画方程组“病态”的程度，下面对方程组行讨论。的扰动对解的影响。设首先考察右端项b即第63页，共90页，2023年，2月20日，星期四642.5误差分析由，得从而有两边取范数，得又因为所以（2-41）第64页，共90页，2023年，2月20日，星期四652.5误差分析式（2-41）表明，当右端项有扰动时，解的相对误如果右端项无扰动，系数矩阵A有扰动相应的扰动仍记为则消去得差不超过右端项的相对误差的倍。的解第65页，共90页，2023年，2月20日，星期四662.5误差分析如果充分小，使得则由上式得因而有第66页，共90页，2023年，2月20日，星期四672.5误差分析式（2-42）表明，当系数矩阵有扰动时，解的扰动仍与有关。一般地，若系数矩阵A有扰动右端项有扰动相应的解x有扰动且则有越大，解的扰动就可能也越大。第67页，共90页，2023年，2月20日，星期四682.5误差分析综合上述各式可以得出，当系数矩阵或右端项有控制了解的扰动程度。也就是定义2.3

对非奇异矩阵A，称数为矩阵A的条件数，记为扰动时，数说，数可以反映方程组的状态。第68页，共90页，2023年，2月20日，星期四692.5误差分析引入条件数后，式（2-41）和式（2-42）可改写为第69页，共90页，2023年，2月20日，星期四702.5误差分析因此，系数矩阵A的条件数刻画了方程组的“病态”程度，条件数越大，“病态”越严重。定义:设线性方程组如果系数矩阵A非奇异,且条件数cond(A)很大,则称是病态方程组或称A为病态矩阵.如果条件数cond(A)相对很小,则称为良态方程组,或称A为良态矩阵.第70页，共90页，2023年，2月20日，星期四712.5误差分析矩阵的条件数与所取范数有关，最常用的条件数有(2-43)(2-44)其中分别为矩阵的的最大的特征值和又称为谱条件数。最小特征值，故第71页，共90页，2023年，2月20日，星期四72特别地，如果A为实对称矩阵，为A的特征值，且则2.5误差分析第72页，共90页，2023年，2月20日，星期四732.5误差分析例8中，方程组的系数矩阵为其逆矩阵为于是有条件数很大，所以方程组是“病态”的。第73页，共90页，2023年，2月20日，星期四742.5误差分析条件数有以下性质：因为由定义2.2(2)

对任意非零实数，有(3)若A为正交矩阵，则(1)对任意n阶方阵A，都有第74页，共90页，2023年，2月20日，星期四752.5误差分析例9

已知方程组的解为若把系数取成2位有效数字的小数，得方程组第75页，共90页，2023年，2月20日，星期四762.5误差分析求解此方程组，并分析所的结果。[解]用Gauss消去求解，第一次消元得第76页，共90页，2023年，2月20日，星期四772.5误差分析第二次消元得回代得解比较两个方程组可以看出，它们的右端项系数相同，系数矩阵中元的最大相对误差仅为0.01，而得到的解却严重失重。这表明原方程组“病态”严重。第77页，共90页，2023年，2月20日，星期四782.5误差分析事实上，原方程组的系数矩阵为其逆矩阵为于是有条件数很大，所以方程组“病态”严重。第78页，共90页，2023年，2月20日，星期四792.5误差分析原方程组的一般形式为是典型的“病态”方程组，称为Hilbert方程组，n越大，“病态”越严重。如n=6时，严重“病态”的方程组，即使用主元素法求解也是数值不稳定的。第79页