解三对角方程组的追赶法课件

1第二章解线性方程组的直接方法

2.3.4解三对角方程组的追赶法在数值计算中，如三次样条插值或用差分方法解常微分方程边值问题，常常会遇到求解以下形式的方程组1第二章解线性方程组的直接方法2.3.4解三对角方程组的2第二章解线性方程组的直接方法如果用矩阵形式简记为其中系数矩阵称为三对角方程组.是一种特殊的稀疏矩阵.它的非零元素集中分布在主对角线及其相邻两条对角线上，称为三对角矩阵.方程(2-23)(2-24)p52第二章解线性方程组的直接方法如果用矩阵形式简记为其中系数3第二章解线性方程组的直接方法Gauss消去法用于三对角方程组时过程可以大大简化.具体地说，第一次消元只要对第2个方程进行，也就是矩阵其中,第一次消元后，第2个方程变成3第二章解线性方程组的直接方法Gauss消去法用于三对角方4第二章解线性方程组的直接方法因而在第二次消元时只要对第3个方程进行消元，即是单位下二对角阵

中.因此类推可以得出,三对角矩阵作三角分解时,矩阵的形式也比较简单，其中4第二章解线性方程组的直接方法因而在第二次消元时只要对第35第二章解线性方程组的直接方法定理2.2

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

是上二对角阵.p25第二章解线性方程组的直接方法定理2.2设矩阵（2-246第二章解线性方程组的直接方法

其中则它可以分解为为矩阵（2-24）中所给出,且分解是唯一的.(2-25)6第二章解线性方程组的直接方法其中则它可以分解为为矩阵（27第二章解线性方程组的直接方法

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

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

再解得方程组（2-23）的解:(2-28)按上述过程求解三对角方程称为追赶法,式（2-26）和式（2-27）结合称为“追”的过程,相当于Gauss消去法中的消元过程.式(2-28)称为“赶”的过程,相当于回代过程.p8711第二章解线性方程组的直接方法再解得方程组（2-23）的12第二章解线性方程组的直接方法2．对1.输入算法2.212第二章解线性方程组的直接方法2．对1.输入算法13第二章解线性方程组的直接方法

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

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

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

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

例用平方根法解线性方程组23第二章解线性方程组的直接方法[解]显然系数矩阵是正定解得由由解得解得由由解得25第二章解线性方程组的直接方法2.4.2改进的平方根法其中为单位下三角矩阵，为对角阵.记定理2.3的证明过程表明，对称正定矩阵A又可以做如下分解：法

)25第二章解线性方程组的直接方法2.4.2改进的平方根法26第二章解线性方程组的直接方法注意到由比较法得26第二章解线性方程组的直接方法注意到由比较法得27第二章解线性方程组的直接方法27第二章解线性方程组的直接方法28第二章解线性方程组的直接方法由比较法可以导出分解的计算公式：

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

再由求具体计算公式为（2-35）p3431第二章解线性方程组的直接方法矩阵作分解后，解方程组可分32第二章解线性方程组的直接方法求解线性方程组的这一方法称为改进平方根法，也叫法.例6

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

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

值方法所求得的用数线性方程组解的误差分析中起着十分由于不同的算法计算效果不同，因此必须进行误差36§2.5误差分析重要的作用。2.5误差分析372.5误差分析2.5.1向量和矩阵的范数就是对向量大小的一种度量，借助于它可以刻画中向量序列的收敛性。

中，向量的模在（一）向量的范数向量的范数是衡量向量大小的度量概念。例如，372.5误差分析2.5.1向量和矩阵的范数就是对向382.5误差分析

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

设对任意向量对任意都有则称为向量x的范数。40382.5误差分析一般地，定义范数如下：按一定的规则392.5误差分析中的一种范数。容易验证，向量的模符合以上三条件，因而它是按定义2.1，向量范数的具体形式可以有多种，（1）2-范数常用的有以下三种：392.5误差分析中的一种范数。容易验证，向量的模符合以402.5误差分析（2）1-范数（3）

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

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

范数是等价的。设则42对两种等价范数而言，同一向量序列有相同的极限。∞-范数是43事实上，中任意两种范数都是等价的。是指任意一种向量范数。今后如果不作说明，2.5误差分析（二）矩阵的范数类似于向量范数的定义，可以定义阶矩阵的范数。43事实上，中任意两种范数都是等价的。是指任意一种向量范数。44定义2.2

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

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

若对任意n方阵定义试证为矩阵A的范数(1-范数或列范数)。48[证明]显然且即当且仅当对所有有于是，对任意有所以2.5492.5误差分析对任意实数于是对于任意两个n阶方阵492.5误差分析对任意实数于是对于任意两个n阶方阵502.5误差分析

所以是A的矩阵范数。502.5误差分析所以是A的矩阵范数。512.5误差分析定理2.4

设

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

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

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

对任意非零实数，有(3)若A为正交矩阵，则(1)对任意n阶方阵A，都有742.5误差分析条件数有以下性质：因为由定义2.2(2752.5误差分析例9

已知方程组的解为若把系数取成2位有效数字的小数，得方程组752.5误差分析例9已知方程组的解为若把系数取成762.5误差分析求解此方程组，并分析所的结果。[解]用Gauss消去求解，第一次消元得762.5误差分析求解此方程组，并分析所的结果。[解]772.5误差分析第二次消元得回代得解比较两个方程组可以看出，它们的右端项系数相同，系数矩阵中元的最大相对误差仅为0.01，而得到的解却严重失重。这表明原方程组“病态”严重。772.5误差分析第二次消元得回代得解比较两个方程组可以782.5误差分析事实上，原方程组的系数矩阵为其逆矩阵为于是有条件数很大，所以方程组“病态”严重。782.5误差分析事实上，原方程组的系数矩阵为其逆矩阵为792.5误差分析原方程组的一般形式为是典型的“病态”方程组，称为Hilbert方程组，