线性方程组数值解法素材.pptx

《线性方程组数值解法素材.pptx》由会员分享，可在线阅读，更多相关《线性方程组数值解法素材.pptx（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、若矩阵 非奇异，即 的行列式 ，根据克莱姆（Gramer）法则，方程组有唯一 解：其中 为系数矩阵，为解向量，为右端常向量。其中 表示 ，表示 中第 列换成 后所得的行列式。第1页/共93页 当阶数较高时用这种方法求解是不现实的。阶行列式有 项，每项又是 个数的乘积。对较大的 ，其计算量之大，是一般计算机难以完成的。而且，这时的舍入误差对计算结果的影响也较大。例如，求解一个20阶线性方程组，用加减消元法需3000次乘法运算，而用克莱姆法则要进行 次运算，如用每秒1亿次乘法运算的计算机要30万年。第2页/共93页线性代数方程组的计算机解法常用方法：直接法 迭代法消去法消去法矩阵三角分解法矩阵三角

2、分解法第3页/共93页直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法 迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题第4页/共93页3.1 消去法消去法的基本思想：是通过将一个方程乘或除以某个常数，以及将两个方程相加减，逐步减少方程中的变元数，最终使每个方程只含一个变元，从而得出所求的解。消去法常用方法：高斯消去法选主元消去法高斯约旦消去法第5页/共93页高斯消去法属于直接法，一般由高斯消去法属于直接法，一般由“消元过程”和和“回代过程”两部分组成

3、。两部分组成。先举几个简单实例，再对一般先举几个简单实例，再对一般n n阶方程组说明高阶方程组说明高斯消去法的基本思想。斯消去法的基本思想。消去法3.1 高斯消去法 按自然顺序进行的消元法第6页/共93页例例 1 用高斯消元法求解方程组用高斯消元法求解方程组 解解 用第一个方程削去后两个方程中的用第一个方程削去后两个方程中的 得得 再用第再用第2个方程消去第个方程消去第3个方程中的个方程中的 得得第7页/共93页最后，经过回代求得原方程组的解为最后，经过回代求得原方程组的解为 例例 2 解方程组解方程组第8页/共93页解：消元回代得第9页/共93页消去法下面讨论一般下面讨论一般 n n 阶线性

4、方程组的高斯消去法。阶线性方程组的高斯消去法。记记 为为 ，和和 的元素的元素分别记为分别记为 和和 ，系数上标，系数上标 代表第代表第1 1次消元之前的状态。次消元之前的状态。第第1 1次消元时，设次消元时，设 对每行计算乘数对每行计算乘数 第10页/共93页 用用 乘以第乘以第1 1个方程，加到第个方程，加到第 个方程，个方程，消去第消去第 2 2个方程到第个方程到第 个方程的未知数个方程的未知数 ，得得 即即:其中其中：第11页/共93页 第第 次消元次消元 时，设第时，设第 次消元次消元已完成，即有已完成，即有 其中：其中：设设 ，计算乘数，计算乘数 第12页/共93页 只要只要 ，消

5、元过程就可以进行下去，直到经，消元过程就可以进行下去，直到经过过 消元之后，消元过程结束，得消元之后，消元过程结束，得 也即也即这是一个与原方程组等价的这是一个与原方程组等价的上三角形上三角形方程组。把方程组。把经过经过 n-1n-1次消元将线性方程组化为上三角形方程组的次消元将线性方程组化为上三角形方程组的计算过程称为计算过程称为消元过程消元过程。第13页/共93页 当当 时，对上三角形方程组自下而上逐步回时，对上三角形方程组自下而上逐步回代解方程组，计算代解方程组，计算 ,即即 ,称为各次消元的主元素，称为各次消元的主元素，主元素所在的行称为主元素所在的行称为主行主行。第14页/共93页高

6、斯消去法的计算步骤为高斯消去法的计算步骤为：1 1消元过程消元过程 设设 ，对，对 ，计算，计算 2 2回代过程回代过程第15页/共93页高斯消去法的计算机运算和存储方式的特点：高斯消去法的计算机运算和存储方式的特点：1 1按消元规则进行运算后，对角线以下元素为按消元规则进行运算后，对角线以下元素为0 0。故对于对角线以下元素不用作计算，减小了计算量。故对于对角线以下元素不用作计算，减小了计算量。2 2对角线以下元素对回代求解无影响，故可将乘对角线以下元素对回代求解无影响，故可将乘数放在该处，即数放在该处，即以节省存储单元。以节省存储单元。第16页/共93页3 3对角线以上元素和常数变换后的元

7、素仍放在原来对角线以上元素和常数变换后的元素仍放在原来的位置以节省存储单元。的位置以节省存储单元。4 4回代后的数值仍放在常数项存储单元回代后的数值仍放在常数项存储单元 这时这时 单元中存放的就是输出值单元中存放的就是输出值第17页/共93页定理2 Ax=b 可用高 斯消元法求解的充分必要条件是：系数矩阵 A 的各阶顺序主子式均不为零。高斯消元法的条件定理1 如果在消元过程中A的主元素 (k=1,2,n),则可通过高斯消元法求出Ax=b 的解。引理 A的主元素 (k=1,2,n)的充要条件是矩阵A的各阶顺序主子式不为零，即第18页/共93页定理定理：高斯消去法求解：高斯消去法求解n n 阶线性

8、方程组共需乘除法阶线性方程组共需乘除法次数近似为次数近似为 。证明：见书证明：见书P61P61 高斯消去法的计算量讨 论：在求解线性方程组时其系数矩阵绝大部分都是非奇在求解线性方程组时其系数矩阵绝大部分都是非奇异的，但可能出现主元素异的，但可能出现主元素 消去法消去法无法进行；或|akk(k)|1时，带来舍入误差的扩散。如何处理？第19页/共93页例例 1 解方程组解方程组 解法一解法一 用高斯消元法求解（取用高斯消元法求解（取5位有效数字），用第位有效数字），用第 一个方程消去第二个方程中的一个方程消去第二个方程中的3.1.2 高斯主元素消元法第20页/共93页因而再回代，得因而再回代，得

9、而精确值为而精确值为 显然该解与精确值相差太远，显然该解与精确值相差太远，为了控制误差，采用另一种消元过程。为了控制误差，采用另一种消元过程。解法二解法二 为了避免绝对值很小的元素作为主元，先交为了避免绝对值很小的元素作为主元，先交换两个方程，得到换两个方程，得到 第21页/共93页消去第二个方程中的消去第二个方程中的 得得 再回代，解得再回代，解得 结果与准确解非常接近。这个例子告诉我们，在采用高斯消元法解方程组时，用做除法的小主元素可能使舍入误差增加，主元素的绝对值越小，则舍入误差影响越大。固应避免采用绝对值小的主元素，同时选主元素尽量的大，可使该法具有较好的数值稳定性。第22页/共93页

10、 为避免上述错误，可在每一次消元之前增加一个选主元的过程，将绝对为避免上述错误，可在每一次消元之前增加一个选主元的过程，将绝对值大的元素交换到主对角线的位置。根据交换的方法可分成值大的元素交换到主对角线的位置。根据交换的方法可分成全选主元全选主元和和列选主元列选主元两种方法。两种方法。列主元素消元法 列选主元是当变换到第列选主元是当变换到第k k 步时，从步时，从k k列的列的 及及以下的各元素中选取绝对值最大的元素，然后通过行以下的各元素中选取绝对值最大的元素，然后通过行交换交换将其交换到将其交换到 的位置上。交换系数矩阵中的两的位置上。交换系数矩阵中的两行（包括常数项），相当于两个方程的位

11、置交换了。行（包括常数项），相当于两个方程的位置交换了。第23页/共93页例：例：求解线性方程组求解线性方程组 解法一：用列主元素消元法，方程组增广矩阵为：解法一：用列主元素消元法，方程组增广矩阵为：交换交换1 1、3 3行（行（列选主列选主）第24页/共93页消元消元消元消元回代计算解为回代计算解为选主元选主元第25页/共93页全选主元素消元法 全选主元是当变换到第全选主元是当变换到第k k 步时，从右下角步时，从右下角 n-k+1n-k+1阶子阵中选取绝对值大的元素，然后通过阶子阵中选取绝对值大的元素，然后通过行行交换交换与与列交换列交换将其交换到将其交换到a a kkkk 的位置上，并且

12、保留的位置上，并且保留交换的信息，以供后面调整解向量中分量的次序交换的信息，以供后面调整解向量中分量的次序时使用。时使用。第26页/共93页交换交换1 1、3 3行行交换交换1 1、3 3列列第27页/共93页回代计算得回代计算得从而原方程的解为从而原方程的解为消元消元消元消元第28页/共93页3.1.3 高斯-约当(Jordan)消去法 消元时将主元上方元素也消为0，最后系数矩阵化为对角矩阵。这种算法只有消元，没有回代，这种方法称做高斯-约当(Jordan)消去法。第29页/共93页第30页/共93页第31页/共93页第32页/共93页第33页/共93页 比较而言,Gauss顺序消去法条件苛

13、刻,且数值不稳定;Gauss全主元消去法工作量偏大，算法复杂；对于Gauss-Jordan消去法形式上比其他消元法简单，且无回代求解，但计算量大。因此从算法优化的角度考虑，Gauss列主元消去法比较好。消去法小结第34页/共93页3.2 矩阵三角分解法3.2.1 3.2.1 矩阵三角分解原理矩阵三角分解原理 应用高斯消去法解应用高斯消去法解 阶线性方程阶线性方程 经过经过 步消去后得出一个等价的上三角形方程组步消去后得出一个等价的上三角形方程组 ，对上三角形方程组用逐步回代就可以求出解来。，对上三角形方程组用逐步回代就可以求出解来。这个过程也可通过矩阵分解来实现。这个过程也可通过矩阵分解来实现

14、。将非奇异阵分解成一个下三角阵将非奇异阵分解成一个下三角阵 和上三角阵和上三角阵 的乘积的乘积 ：称为称为对矩阵对矩阵 的三角分解的三角分解，又称，又称 分解分解。高斯消去法解线性代数方程组的一种变形解法。高斯消去法解线性代数方程组的一种变形解法。第35页/共93页杜里特尔分解：杜里特尔分解：把把 分解成一个分解成一个单位下三角阵单位下三角阵 和一个上三角阵和一个上三角阵 的乘积。的乘积。克劳特分解克劳特分解:把把 分解成一个下三角阵分解成一个下三角阵 和一个和一个单位上三角阵单位上三角阵 的乘积。的乘积。若矩阵若矩阵 各阶主子式不为零，则可各阶主子式不为零，则可唯一地分唯一地分解成一解成一个

15、单位下三角阵个单位下三角阵 和一个非奇异的上三角阵和一个非奇异的上三角阵 的的乘积。乘积。定定 理理：第36页/共93页杜里特尔分解 A=LU第37页/共93页杜里特尔分解第38页/共93页杜里特尔分解(一般算法)由矩阵乘法规则即：即：由此可得 的第一行元素和 的第一列元素第39页/共93页 当已得出 的前 行元素和 的前 列元素，则对于 ，由又可得计算 的第 行元素和 的第 列元素的公式:第40页/共93页例例 求矩阵求矩阵的LU分解。u11=2 u12=1 u13=4 第41页/共93页所以所以第42页/共93页 有了矩阵 A 的LU分解计算公式，当求解线性方程组 时，等价于求解 。这时可

16、归结为利用递推计算相继求解两个三角形方程组（系数矩阵为三角矩阵）。用顺代，由 求出 ，再利用回代，由 求出 。3.2.2 解线性方程组的三角分解法用杜里特尔三角分解法解线性方程组 的计算方法：第44页/共93页对于 ，计算 和 。求解 ，即计算求解 ，即计算。计算 和 。克劳特克劳特分解求方程组步骤分解求方程组步骤：略第45页/共93页第46页/共93页第47页/共93页第48页/共93页第49页/共93页第50页/共93页其它矩阵分解法求解特殊的线性方程组：平方根法：主要用于求解正定矩阵的线性方程组追赶法：主要用于求解特殊矩阵的三对角方程组 见书 P78P87第51页/共93页用LU 直接分

17、解的方法求解线性方程组的计算量为 ，和高斯消去法的计算量的数量级基本相同。消去法和矩阵三角分解法比较消去法和矩阵三角分解法比较当方程组系数矩阵不变，只有右侧向量b变化时，用LU分解法比消去法速度快。因为右侧向量b的改变不影响LU的变化。高斯消去法和LU分解法是等价的，其关键是把一般方程组变为三角方程组，只是实现途径不同。第52页/共93页3.4 向量与矩阵的范数向量与矩阵的范数 问题的提出 向量范数概念是三维欧氏空间中向量长度概念的推广,在数值分析中起着重要作用.为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对 （n维向量空间）中向量及 （维矩阵空间）中矩阵的“大小”及“距离”引

18、进某种度量向量与矩阵范数的概念.第53页/共93页平面向量 x 大小：用 距离 反映。3.4 向量与矩阵的范数向量与矩阵的范数 引入范数的目的：实数大小：用绝对值反映复数大小：用模反映高维空间向量 x“大小”用 反映？将度量长度数值的计算方法引入高维空间，用来反映空间向量的大小，就是范数的概念。为了研究线性方程组近似解的误差估计和迭为了研究线性方程组近似解的误差估计和迭代法的收敛性等。代法的收敛性等。第54页/共93页 非负性|x|0，等号仅当 x=0 时成立；齐次性 对任何实数 ,|x|=|x|；三角不等式|x+y|x|+|y|；则称|x|为向量 x 的范数。定义 对任意 n 维向量 x R

19、n，若对应非负实数|x|，满足 3.4.1 向量的范数第55页/共93页 由定义可知，向量 的范数 是按一定规律与 对应的实数，该实数的值没有确定，但只要满足这三个条件，这个实数就是向量 的一种范数。因此定义中的三个条件称为范数公理。当 时，向量范数 有如下性质证：利用条件，有 证：第56页/共93页它们分别叫做向量的-范数、1-范数、2-范数、p-范数（0p+）。p-范数是以上范数的统一表达形式。常用的向量范数:满足定义的范数不是唯一的.设设 x=(x1,x2,xn)T ，常用的向量范数有，常用的向量范数有 第57页/共93页 对于范数，有当 时，有 ，只有当 时，才有 对任意实数 ，因为

20、，所以 。对任意向量 ，有因此因此 是是n n维空间的维空间的一种范数一种范数例：范数的证明第58页/共93页可以证明这几种范数满足下述关系可以证明这几种范数满足下述关系事实上，对 Rn 上任意两种向量范数|x|,|x|，都存在与 x 无关的正常数 c1,c2 使 这种性质称为向量范数的等价性。第59页/共93页定理：设Rn上的任意两种范数|x|a,|x|b,都存在与x无关的正常数c1,c2使得称满足不等式的两种范数称满足不等式的两种范数|x|a,|x|b 是等价的。是等价的。推论：推论：有限维有限维Rn上的不同范数是等价的。上的不同范数是等价的。第60页/共93页设给定 中的向量序列 ，其中

21、 若对任何 ，都有，则向量 称为向量序列 的极限，或者说向量序列收敛于向量 ，记为：向量收敛的定义：第61页/共93页向量序列收敛性定理：向量序列收敛(即 )的充要条件是 ，其中 为向量的任一种范数。按不同方式规定的范数,其值一般不同。但在各种范数下考虑向量序列收敛性的结论是一致的。即向量序列如对某一种范数收敛则对其它范数也收敛，且有相同的极限。这样，在研究某一具体问题时，可以选择一较易简单的范数。第62页/共93页矩阵范数是用于定义矩阵“大小”的量。由于在大多数与估计误差有关的问题中,矩阵和向量的乘积经常出现,所以希望引进一种矩阵的范数,它与向量范数有某种关系。3.4.2 矩阵的范数第63页

22、/共93页 定义：设 ，定义矩阵 的范数 对于每一种向量范数 ，相应的矩阵范数 为其中 是指 的最大可能值。即遍取所有不为0的 ，比值 中最大的，定义为 的矩阵范数。第64页/共93页矩阵范数的性质：,且仅当 时，；对任意实数 ，；对同维方阵 ，有:相容性条件：由矩阵范数的定义可直接得到 ，即有 ，称为相容性条件。即所给的矩阵范数与向量范数是相容的。证明 p92第65页/共93页矩阵范数与向量范数的关系：矩阵范数与向量范数密切相关，向量范数有相应的矩阵范数，即：（如 ）常用的矩阵范数有（矩阵范数的求取）常用的矩阵范数有（矩阵范数的求取）它们分别叫做矩阵的-范数、1-范数、谱范数。（谱范数）表示

23、的最大特征值。第67页/共93页例例4 设设则则求相应各范数。求相应各范数。解验证相容性验证相容性第68页/共93页3.5 方程组的性态 前几节讨论了求解线性代数方程组的直接法.给出系数矩阵A和自由项b,求未知向量x.实践中,A和b往往是实验观测数据或是计算所得结果.因此我们处理的线性方程组 实际上变成了的关系怎样,是人们十分关心的问题.3.5.1 方程组的性态和矩阵的条件数第69页/共93页例例 1 解方程组解方程组 其中其中 现用绝对精确的计算（即不带任何舍入误差的计算）现用绝对精确的计算（即不带任何舍入误差的计算）求解，可以看出求解，可以看出此时，我们发现对于两组不同的自由项此时，我们发

24、现对于两组不同的自由项第70页/共93页它的差只有它的差只有而所得解而所得解 与与 之差却是之差却是两组不同的右端其分量之差不过是两组不同的右端其分量之差不过是 可是解的差高可是解的差高 达达 之之1860倍像这样的方程组或矩阵倍像这样的方程组或矩阵A 就叫做病态的就叫做病态的 定义1 若方程组 Ax=b 的系数矩阵 A 或右端向量 b 的微小变化（小扰动）引起解产生巨大变化,则称此方程组为病态方程组;A称为病态矩阵,否则称为良态方程组,A 称为良态矩阵。第71页/共93页定理：设 非奇异，且 则 为了定量地刻划方程组的“病态”程度，下面就一般方程组 进行讨论。首先考察右端项b 的扰动对解的影

25、响。第72页/共93页证：设x为Ax=b的准确解，当方程组右端有小扰动b而A准确时,受扰解为 x+x,即 A(x+x)=b+b 因为 Ax=b 所以 x=A-1 b 又由得得因此所以所以第73页/共93页此不等式表明,解的相对误差不超过b的相对误差的|A|A-1|倍.若系数矩阵A也有小扰动A,则还可进一步导出更一般的误差估计式第74页/共93页定义定义2 设设A 为非奇异矩阵，称数为非奇异矩阵，称数cond(A)=|A|A-1|为为A 矩阵的条件数矩阵的条件数矩阵的条件数与范数有关，通常使用的条件数有 所以，Cond(A)越大,A的病态程度越严重。对任何非奇异矩阵对任何非奇异矩阵A，都有，都有

26、 。不难证明，条件数具有如下不难证明，条件数具有如下性质性质第75页/共93页例例 求矩阵求矩阵A 的条件数，其中的条件数，其中解：解：于是于是 从而从而所以A是病态的第76页/共93页 由于计算条件数涉及到计算逆矩阵，很麻烦。因此实际计算中一般通过可能产生病态的现象来判断。若在消元过程中出现小主元，则 A可能是病态矩阵。但病态矩阵未必一定有这种小主元。若解方程组时出现很大的解，则A可能是病态矩阵。但病态矩阵也可能有一个小解。从矩阵本身看，若元素间数量级相差很大且无一定规律；或者矩阵的某些行或列近似相关，这样的矩阵则有可能是病态矩阵。第77页/共93页3.5.2 直接法的精度分析定理：设 是方

27、程组 的一个近似解，其精确解记为 ，为 的余量，则有求得方程组 的一个近似解 后，希望能判断其精度。检验精度的一个简单办法是将近似解再回代到原方程组去求其余量 。如果 很小，就认为解 是相当准确的。第78页/共93页该定理给出了方程组近似解的相对误差界。即相对误差的事后估计证：由于 ，而 ，故有 所以第79页/共93页生成向量序列 x(k)，若称为迭代格式（1）的迭代矩阵。则有x*=Bx*+f，即x*为原方程组Ax=b 的解，B迭代法基本思想：将方程组 Ax=b(|A|0)转化为与其等价的方程组 x=Bx+fx(k+1)=Bx(k)+f （k=0,1,2,)(1)取初始向量 x(0)按下列迭代

28、格式3.6 3.6 迭代法迭代法第80页/共93页雅可比迭代法 对线性方程组可以建立不同的迭代格式。下面介绍构造迭代格式的几种常用方法，雅克比迭代法和高斯塞德尔迭代法。设方程组第81页/共93页其中 aii0(i=1,2,n)分别从上式n个方程中分离出n个变量，如下：等价方程组等价方程组第82页/共93页建立迭代格式称为雅可比(Jacobi)迭代法又称简单迭代法。第83页/共93页 高斯塞德尔迭代法在 Jacobi 迭代中,用已有的迭代新值代替旧值，即：建 立 迭 代 格 式第84页/共93页或缩写为称为高斯塞德尔（Gauss Seidel）迭代法。例1 用雅可比迭代法解方程组第85页/共93

29、页 取计算如下 雅雅克克比比迭迭代代格格式式第86页/共93页Gauss-Seidel 迭代格式为 例2 用GaussSeidel 迭代法解上题。第87页/共93页取 x(0)=(0,0,0)T 计算如下：第88页/共93页 以上介绍的两种迭代法，一般地说，高斯塞德尔以上介绍的两种迭代法，一般地说，高斯塞德尔比雅克比要好，但也不完全是这样。比雅克比要好，但也不完全是这样。关于迭代法的一些问题关于迭代法的一些问题：为了使迭代法计算加速，可采用为了使迭代法计算加速，可采用松弛法松弛法。（略）。（略）迭代法存在收敛性问题。（略）迭代法存在收敛性问题。（略）第89页/共93页要求熟练掌握的内容：高斯消

30、去法原理、算法、计算步骤；主元消去法的意义、算法、计算步骤；矩阵三角分解法解方程组的意义、算法、计算步骤向量和矩阵范数的定义、性质和计算方法；矩阵条件数的定义,并能估计直接法的误差.要求掌握的内容：采用雅可比迭代解线性方程组；采用高斯塞德尔迭代解线性方程组；本章要求第90页/共93页人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。第91页/共93页第92页/共93页感谢您的观看！第93页/共93页