计算方法-3

null计算计算方法Computational Method第三章 线性代数方程组的解法第三章 线性代数方程组的解法在自然科学和工程技术中，有很多问题的求解都可以直接或间接地归结为线性代数方程组的求解问题。例如，电学中的网络问题，根据观测数据求样条插值或曲线拟合问题，解非线性方程组问题等等。 研究 —— 研究求解线性代数方程组的一些数值解法 研究对象 —— n 阶线性代数方程组（方程个数 = 未知量个数） **第三章 线性代数方程组的解法第三章 线性代数方程组的解法一般，n 阶线性代数方程组具有如下形式： 其中， **AX = b≠ 0当A非奇异，即det (A) ≠ 0时，方程组有唯一解。 根据Cramer法则： 其中， Ai是A的第i列用b代替所得。第三章 线性代数方程组的解法第三章 线性代数方程组的解法尽管Cramer法则在理论上有着重大意义，但在实际应用中却存在着很大的困难。 主要原因 —— 利用Cramer法则求解方程组时，所需乘除法的运算量大约为 (n+1)!+n 次。 如：当n = 20时，每秒 1亿次运算速度的计算机要算30多万年！ 为解决这一困难，本章将重点讨论求解线性代数方程组的一些有效的数值方法。**第三章 线性代数方程组的解法第三章 线性代数方程组的解法求解线性代数方程组的方法主要有两类 —— 直接法 在没有舍入误差影响的情况下，经过有限步算术运算就可以得到方程组精确解的方法。 但在实际计算中，由于舍入误差不可避免，因此只能求得近似解。 迭代法 通过构造适当的近似解向量序列，用某种极限过程去逐步逼近精确解的方法。 实际计算中，根据精度要求控制计算有限步终止，从而获得满足精度的近似解。**高斯消去法、三角分解法等雅可比迭代法、高斯-赛德尔迭代法等§3.1 高斯(Gauss)消去法§3.1 高斯(Gauss)消去法高斯(Gauss)消去法是求解线性代数方程组的一种最古老、最基本的直接法。 基本思想 —— 消元 即按一定的规则逐步消去未知量，将方程组化为等价的上三角形方程组； 回代 即由上三角形方程组逐个求出 xn, xn-1, …, x2, x1。 典型算法 —— 顺序高斯消去法 选主元高斯消去法**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法例题：用顺序高斯消去法求解下列方程组。 【解】 ** 消元r2 - r1r3 - 2r1r3 + 2r2？？？？？ ？？ ？§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法 回代 **§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法一般情形下的计算过程 设方程组为AX = b，且A非奇异。为便于讨论，记 第1列消元 **即§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法第2列消元 按照上述方法依次类推。**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法第 k 列消元 一般，在第 k – 1 列消元后，增广矩阵为 ——**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法经过 n – 1 次消元后，最终得到 消元过程至此结束。从而得到与原方程 AX = b 同解的上三角形方程组 A(n)X = b(n)，即**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法回代过程**一般，由第 k 个方程可得：xn-1 = …§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法综上所述，顺序高斯消去法的计算步骤如下： 消元过程：对 k = 1, 2, … , n-1 依次计算 回代过程：**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法顺序高斯消去法算法步骤**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法例题：用顺序高斯消去法求解下列方程组。 【解】 消元 **r2 – l21r1r3 – l31r1r3 – l32r2§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法 回代 因此，方程组的解为**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法顺序高斯消去法的计算量 由于计算机上加减运算远快于乘除运算，因此常用乘除法运算次数来说明求解线性代数方程组的计算工作量。 对 k = 1, 2, … , n-1，在第 k 次消元中 ——**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法顺序高斯消去法的适用条件 方程组能用顺序高斯消去法进行求解的前提 —— 记 Ak 为 A 的 k 阶顺序主子阵，则 其中，det Ak 称为 A 的 k 阶顺序主子式。**§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法顺序高斯消去法的适用条件 **定理3-1 对于方程组 AX = b ，顺序消元过程能进行到底的充要条件是系数矩阵 A 的前 n – 1 个顺序主子阵 Ak ( k = 1, 2, … , n – 1 )非奇异。而方程组 AX = b 能用顺序高斯消去法求解的充要条件是系数矩阵 A 的一切顺序主子阵均非奇异。§3.1.1 顺序高斯消去法§3.1.1 顺序高斯消去法顺序高斯消去法的数值稳定性 例题：用顺序高斯消去法求解以下方程组，用 3 位有效数字计算（假定机器字长为 3）。 回代求解得到 x1 = – 5.00，x2 = 20.1。 方程组准确值 x1 = 5.00，x2 = 20。**r2 – l21r1l21 = 1000【解】|εr (x1)| = 200% 结果严重失真！ 原因： 用0.02作除数！§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法选主元高斯消去法是对顺序高斯消去法的一种改进。 基本思想 —— 每次消元前，在系数矩阵中按一定的范围选取绝对值最大的元素作为主元素，以便减少舍入误差的影响。 常用算法 —— 列主元消去法 全主元消去法**§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法列主元消去法 第 k 列消元时 ——**第k列第k行第r行r > k§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法全主元消去法 第 k 列消元时 —— **第k行第r行第k列第s列§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法例题：用选主元高斯消去法求解下列方程组(用三位有效数字计算)。 【解】列主元消去法 ——**r1  r3r2 – l21r1 r3 – l31r1l21 = –0.2 l31 = 0.002§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法 消元过程完成，得到等价的上三角形方程组 回代可得方程组的解为**r2  r3r3 – l32r2§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法【解】全主元消去法 —— **r1  r3r2 – l21r1 r3 – l31r1l21 = –0.2 l31 = 0.002c2  c3§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法 得到等价的上三角形方程组 回代可得方程组的解为 **r3 – l32r2§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法 **§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法练习：用列主元高斯消去法求解下列方程组。 【解】**r2 – l21r1 r3 – l31r1l21 = 1/2 l31 = –1/2r2  r3r3 – l32r2l32 = –1/5§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法列主元高斯消去法的算法步骤**§3.1.2 选主元高斯消去法§3.1.2 选主元高斯消去法用消去法计算矩阵行列式 假设在消元过程中做了 p 次行交换或列交换，则根据行列式性质，可知： 如：列主元消去法计算过程中，有 2 次行交换，消元结束后主元为5，2.01，1.78，则**§3.1.3 高斯-约当消去法§3.1.3 高斯-约当消去法与前述的高斯消去法相比，高斯-约当(Jordan)消去法是一种无回代过程的消去算法。 基本思想 —— 每次消元时，把主元素(按列选主元或全选主元)调换到主对角线上，然后将该列中除主元素以外的其它元素全部化为 0 。消元过程结束后，系数矩阵变为对角阵。 **§3.1.3 高斯-约当消去法§3.1.3 高斯-约当消去法用Gauss-Jordan消去法求解矩阵逆阵 当det A ≠ 0时，A存在逆矩阵，设 因此，求A-1就相当于同时求解上面的 n 个线性方程组。**§3.1.3 高斯-约当消去法§3.1.3 高斯-约当消去法具体实现 —— 令**消元时，利用主元将其所在列的其余元素全部化为0，然后用 (k, k) 位置的主元去除其所在行的各元素，使主元位置为1。消元过程结束后，系数矩阵变为单位对角阵。A-1§3.2 追赶法§3.2 追赶法追赶法 —— 用于求解三对角线性方程组 若三对角矩阵 A 满足条件： 则三对角矩阵 A 是非奇异的。**三对角矩阵§3.2 追赶法§3.2 追赶法计算步骤 —— 第 k 列消元时，增广矩阵的第 k 、k +1两行为： 消元过程 ——  归一化处理，即将第 k 行除以 bk ，使主元素化为 1 ；  用第 k+1 行减去第 k 行的 ak+1 倍，使 ak+1 化为 0 ； **01§3.2 追赶法§3.2 追赶法消元的一般计算公式可归纳为 回代过程 ——**令 cn = 0追赶§3.2 追赶法§3.2 追赶法计算量 —— 因此，“追”过程所需乘除运算次数为 4n – 2。 优点 —— 节省存储空间 只需占用4n个单元，而一般方程组需占n2 + n个单元； 减少计算量 一般高斯消元过程需O(n3) 次乘除法运算，而“追”过程只需4n – 2次乘除运算。**追11§3.3 三角分解法§3.3 三角分解法矩阵的三角分解 定义 —— 把一个 n 阶的矩阵 A 分解成两个三角形矩阵乘积的形式称为矩阵的三角分解。 形式 —— A = LU 分类 —— L 为单位下三角阵，U 为上三角阵 —— Doolittle分解； L 为下三角阵，U 为单位上三角阵 —— Crout分解。**上三角阵下三角阵§3.3 三角分解法§3.3 三角分解法分解过程 从矩阵的初等变换来看，对矩阵进行一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。 以顺序高斯消去法为例，若引入如下矩阵 —— 其中**第 k 行A(k)A(k+1)ri – likrkLk A(k) = A(k+1)k = 1, 2, … , n-1§3.3 三角分解法§3.3 三角分解法 因 Lk 可逆(其逆阵只需将 – lik 改为 lik 即可)，故 其中， 顺序高斯消去法的消元过程实质就是矩阵A的Doolittle分解过程。**A = A(1)A(n)消元Ln-1 Ln-2 … L2 L1 A = A(n)单位下三角阵上三角阵§3.3 三角分解法§3.3 三角分解法分解条件 问题1：若一个矩阵存在三角分解，其分解是否惟一？ 答 案：不惟一！ 原 因：设 A = LU 是 A 的一种三角分解，任取一个与 A 同阶的非奇异对角阵 D ，则 A = (LD)(D-1U) = L1U1 也是矩阵 A 的一种三角分解。 问题2：在什么条件下，矩阵存在惟一的三角分解？ 答 案：n 阶矩阵 A 存在惟一的Doolittle分解或Crout分解的充要条件是 A 的前 n – 1 个顺序主子式均不为零 。 原 因：存在性 —— 若顺序高斯消元过程能进行到底，则矩阵 A 存在Doolittle分解。**§3.3 三角分解法§3.3 三角分解法 而顺序高斯消元过程能进行到底的前提就是 A 的前 n – 1 个顺序主子式均不为零。 惟一性 —— 假设矩阵 A 有两种Doolittle分解形式，即 A = L1U1 和 A = L2U2 则 **L1U1 = L2U2上三角阵单位下三角阵等式两端只能是单位阵§3.3 三角分解法§3.3 三角分解法LDU分解 如果矩阵 A 可以分解为 A = LDU，其中，L 为单位下三角阵，U 为单位上三角阵，D 为对角阵。则称此分解为LDU分解。 推论 —— n 阶矩阵 A 存在惟一的LDU分解式的充要条件是 A 的前 n – 1 个顺序主子式均不为零 。**A = LDU若令 L(DU) = LU1 —— Doolittle分解 若令 (LD)U = L1U —— Crout分解§3.3 三角分解法§3.3 三角分解法LU分解方法 L、U 中元素的确定，可不用通过顺序消去过程进行，而直接利用矩阵乘法规则即可。 例题：试求矩阵 的Doolittle分解，Crout分解以及LDU分解。 【解】设 A 的Doolittle分解为 比较两端对应元素，可依次求得**§3.3 三角分解法§3.3 三角分解法A 的Doolittle分解为 将Doolittle分解的后一矩阵继续分解，即 故 A 的LDU分解为 将LDU分解的前两个矩阵相乘，可得 A 的Crout分解为**§3.3 三角分解法§3.3 三角分解法用三角分解法解线性方程组 基本思想 —— 对于线性方程组 AX = b，若其系数矩阵 A 非奇异，且存在三角分解 A = LU，则 例题：用Doolittle分解法求解下列方程组。 **AX = bLUX = bYXAbY§3.3 三角分解法§3.3 三角分解法【解】 对 A 进行Doolittle分解 A = LU ，即 由第 1 行可得： 由第 1 列可得： 由第 2 行可得： 由第 2 列可得： 由第 3 行可得：**§3.3 三角分解法§3.3 三角分解法故  解方程组 由 LY = b，可得 再由 UX = Y ，可得**§3.3 三角分解法§3.3 三角分解法计算机上的求解公式 设 A 的Doolittle分解式为 根据矩阵乘法，用比较上式两端对应元素的方法逐行逐列求解出 L、U 中的各元素。**§3.3 三角分解法§3.3 三角分解法  比较第 1 行元素  比较第 1 列元素  比较第 2 行元素  比较第 2 列元素 按此方法依次类推。**§3.3 三角分解法§3.3 三角分解法假设 U 的前 k – 1 行和 L 的前 k – 1 列已求出。 欲求 U 的第 k 行元素 ukj ( j ≥ k )，通过比较方程两端的第 k 行第 j 列元素( j ≥ k )，有 故**已求得§3.3 三角分解法§3.3 三角分解法再求 L 的第 k 列元素 lik ( i > k )，通过比较方程两端的第 k 列对应元素，有 故 至此，就可得到 L 和 U 了。**前 k 项§3.3 三角分解法§3.3 三角分解法然后，便可求解方程组 LY = b 和 UX = Y ，即 **§3.3 三角分解法§3.3 三角分解法综上所述，利用Doolittle分解法求解方程组 AX = b 的计算步骤可归纳如下： 三角分解 对k = 1,2, … , n, 按以下算式依次计算 L 和 U 中的元素。 求解方程组  解 LY = b。对 k = 1,2,…,n，计算  解 UX = Y。对k = n, n-1,…,1，计算**§3.3 三角分解法§3.3 三角分解法算法实现 —— 计算机上实现时，如果初始矩阵 A 无需保留的话，可以采用紧凑格式存储 L 和 U 的元素。 此外，yk 可存入 bk 所占的单元，然后 xk 再取代 yk 存入最初 bk 所占的单元。**§3.3 三角分解法§3.3 三角分解法程序框图**§3.3 三角分解法§3.3 三角分解法 **§3.3 三角分解法§3.3 三角分解法乔累斯基(Cholesky)分解法 Cholesky分解法是一种针对对称正定矩阵的特殊的三角分解法，其分解过程无需选主元，有良好的数值稳定性。 设 A 是对称正定矩阵，则 A = LLT 称为对称正定矩阵 A 的Cholesky分解，或 LLT 分解。 [说明]由 A 对称正定，可知 A 的各阶顺序主子式均大于零。因此根据Doolittle分解条件，易知 A 有唯一分解。 **L：对角元全为正数的下三角阵§3.3 三角分解法§3.3 三角分解法若方程组 AX = b 的系数矩阵 A 为对称正定矩阵，则可利用 A 的 LLT 分解来求解方程组，这种解法称为 Cholesky解法或平方根法。 计算过程 ——  计算分解式 A = LLT ；  依次求解三角形方程组 LY = b 及 LTX = Y 。**AX = bLLTX = bLY = bLTX = Y§3.3 三角分解法§3.3 三角分解法Cholesky具体的分解方法 例题：用Cholesky分解法求解下列方程组： 【解】设 A = LLT ，即**§3.3 三角分解法§3.3 三角分解法 采用自左向右逐列计算的方法 —— 第 1 列 第 2 列 第 3 列**§3.3 三角分解法§3.3 三角分解法解方程组 —— **§3.3 三角分解法§3.3 三角分解法计算机用Cholesky分解法求解方程组的步骤 设  实现Cholesky分解 由矩阵乘法规则，利用对应元素相等可得**§3.3 三角分解法§3.3 三角分解法 求解三角形方程组 Cholesky分解法的优缺点 优点： 工作量约为LU分解法的一半；  数值稳定；  存储单元少。 缺点：存在开方运算，可能会出现根号下负数。**LY = bLTX = Y§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数为了研究线性方程组近似解的误差估计和迭代法的收敛性，以下引入一种度量Rn中向量或Rnn中矩阵大小的方法 —— 向量和矩阵的范数。 Rn —— 实数域上全体 n 维向量构成的线性空间，简称 n 维向量空间； Rnn —— 实数域上全体 n 阶矩阵构成的线性空间。 **§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数向量范数**§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数常用向量范数 设向量  l1范数(1-范数).  l2范数(2-范数).  l∞范数(∞-范数). 上述 3 种向量范数统称为 lp 范数( p -范数)，即**§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数向量范数的性质 Rn上任意两种范数 || · ||a 和 || · ||b 是等价的，即存在与 x 无关的数 m、M，使 如：**§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数向量序列的收敛性 **§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数定理3-2的证明 —— 必要性 当序列{ x(k) }收敛于向量 x* 时，有 x(k) - x* → 0。 故 充分性 当存在一种范数 || · ||，使得 由向量范数的等价性可知，总存在常数 m、M，使得 由夹逼定理易知， 即{ x(k) }收敛于向量 x* 。**§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数矩阵范数 简单来说，矩阵 A 的范数 || A ||a 是指函数 || Ax ||a 在约束条件 || x ||a = 1下的最大值。 显然 —— 零矩阵的范数 || 0 || = 0 ； 单位矩阵的范数 || I || = 1 。**§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数矩阵范数满足以下性质：** 非负性：‖A‖≥ 0，ARnn ； 当且仅当 A = 0 (零矩阵)时,‖A‖= 0；  齐次性：‖A‖=｜｜·‖A‖, ARnn , R；  三角不等式：‖A+B‖≤‖A‖+‖B‖, A , BRnn ；  与向量范数的相容性：存在某种向量范数 || · ||a , 使得 || Ax ||a ≤ || A || || x ||a , ARnn , xRn ；  对于矩阵乘法的相容性： ‖AB‖≤‖A‖‖B‖, A , BRnn .§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数常用矩阵范数 **定理3-3 设 A = (aij)nnRnn ，则从属于向量 l1 , l2 , l∞ 范数的矩阵范数分别为  矩阵的 1-范数  矩阵的 2-范数  矩阵的∞-范数§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数 【解】 由 可得 于是 因此**§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数矩阵的谱半径 【解】** ( 0 ) = 0， ( I ) = 1，  ( Am ) = [  (A) ]m §3.4 向量和矩阵的范数§3.4 向量和矩阵的范数矩阵谱半径的性质**证明：设为A的特征值，x是对应于 的特征向量，则 x = Ax 对上式两边取范数，得到 || x || = || Ax || 由于 x ≠ 0 ，故 |  | ≤ || A || ，即  (A) ≤‖A‖。|  | · || x || = ≤ || A || · || x || 常被用来估计矩阵特征值的上界§3.4 向量和矩阵的范数§3.4 向量和矩阵的范数矩阵序列的收敛性 **§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法简单迭代法 基本思想 —— 构造适当的迭代公式，任选一个初始向量 X (0) 进行迭代计算，使生成的向量序列 X (0) , X (1) , … , X (k) , … 逐步逼近方程组的精确解。 一般形式 —— 与用迭代法求解非线性方程近似根的方法类似。 **AX = bX = MX + gX (k+1) = MX (k) + g , k = 0,1,2,…简单迭代公式 M：迭代矩阵A 非奇异§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法对于简单迭代公式 X (k+1) = MX (k) + g , k = 0,1,2,… 若设 则可得简单迭代公式的分量形式为**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法迭代法的收敛性 对于给定的方程组可以构造各种迭代公式。但是，一般的迭代公式不一定收敛。**什么条件下，迭代公式会收敛？§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法迭代公式的收敛条件之一 —— 充要条件 证明：必要性 设迭代公式收敛于 X *，则有 X * = MX * + g。 若记 e(k) = X(k) - X *，则 且**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法由于e(0)可以是任意向量，故 又 因此， (M) < 1 成立。 充分性 设  (M) < 1，则 > 0，使得  (M)+ < 1。 根据定理3-5，存在某种矩阵范数‖·‖，使 ‖M‖≤  (M) +  于是，当 k → ∞ 时， 所以， e(k)收敛于零向量，即X(k)收敛于 X *。**< 1‖M k‖≤‖M‖k → 0M k → 0§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题：用迭代法求解线性方程组 【解】解法一**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法解法二 可以证明， (M) 越小，则收敛速度越快！**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法迭代公式的收敛条件之二 —— 充分条件 证明： 收敛性 故迭代公式 X (k+1) = MX (k) + g 收敛。** (M) ≤‖M‖ (M) < 1 §3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法 误差估计 **§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法根据定理3-8，可得如下几个结论 ——  条件‖M‖< 1 是迭代公式收敛的充分条件而非必要条件。当‖M‖≥ 1时，迭代法可能收敛也可能发散。  迭代结束方式 ‖M‖越小，则收敛速度越快。**事先指定的精度要求近似解§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法雅可比(Jacobi)迭代法 设方程组 AX = b 的系数矩阵 A 非奇异，且其主对角元 aii ≠ 0 , i = 1,2, … ,n 则该方程组的第 i 个方程为 从中解出 xi ，得到 建立迭代格式**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法Jacobi迭代公式的矩阵形式 —— Jacobi迭代法是一种简单迭代法。**Jacobi 迭代矩阵§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法如果将方程组 AX = b 的系数矩阵 A 分解为 A = L + D + U 其中， 则可得Jacobi迭代矩阵BJ 的另一种达形式，即**BJgJ§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题：用Jacobi迭代法求解下列方程组 精度要求为 ε = 0.005。 【解】 **§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法迭代结果如下：**所以 X(5) 满足精度要求。§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法上例中Jacobi迭代公式的迭代矩阵是什么？ 收敛性判断 —— **Jacobi迭代公式收敛§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法高斯-赛德尔(Gauss-Seidel)迭代法 Gauss-Seidel迭代公式（简称GS迭代公式） GS迭代公式的矩阵形式**BG：GS迭代矩阵§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题：用Gauss-Seidel迭代法求解下列方程组 精度要求为 ε = 0.005。 【解】**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法 由于 故X(3)即为满足精度的近似解，于是 x1=0.999 94 , x2=0.999 93 , x3=0.999 99**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法上例中Gauss-Seidel迭代公式的迭代矩阵 收敛性判断 —— **GS迭代公式收敛§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法需要注意的是，多数情况下，GS 迭代法比 Jacobi 迭代法收敛快些。但在某些情况下，这两种方法可能一种收敛而另一种发散，或者两者都发散！ 判断Jacobi 迭代法和GS迭代法收敛的充分条件 ——**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法判定Jacobi 迭代法和GS迭代法收敛的基本方法 —— **§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题：试判断以下简单迭代公式的收敛性。**迭代公式收敛迭代公式收敛迭代公式发散§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题：设方程组 AX = b 的系数矩阵为 试判断用Jacobi迭代法和GS迭代法求解时的收敛性。 【解】因为 故 A 是严格对角占优阵，于是用Jacobi迭代法和GS迭代法求解方程组时都收敛。**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题：试判断用Jacobi迭代法和GS迭代法求解下列方程组时的收敛性。 【解】显然，系数矩阵对称正定，故GS迭代法一定收敛。 Jacobi迭代矩阵为**Jacobi迭代法发散§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题：试判断用Jacobi迭代法和GS迭代法求解下列方程组时的收敛性。 【解】Jacobi迭代矩阵为 GS迭代矩阵为**Jacobi迭代法收敛GS迭代法发散§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题： 设方程组 AX = b 的系数矩阵为 其中 a 为参数。问 a 为何值时，Jacobi迭代法收敛？ 【解】 Jacobi迭代矩阵为 **Jacobi迭代法 收敛 收敛条件较弱分析：   (BJ) < 1  ||BJ ||∞ < 1§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法例题：对以下方程组建立收敛的Jacobi迭代格式和GS迭代格式。 【解】 (1) 调整方程次序，得到等价方程组 显然，系数矩阵 A 是严格对角占优阵，故Jacobi和GS迭代公式一定收敛。**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法 Jacobi迭代矩阵 —— Jacobi迭代格式 ——**Jacobi迭代公式收敛§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法 GS迭代矩阵 —— **GS迭代公式发散不能建立收敛的GS迭代格式§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法算法的计算机实现 Jacobi迭代算法 ——**§3.5 解线性方程组的迭代法§3.5 解线性方程组的迭代法算法的计算机实现 GS迭代算法 ——**§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数由实际问题得到的方程组，其系数矩阵或常数项本身会存在一定的误差；这些初始数据的误差在计算过程中会向前传播，从而影响方程组的解。 初始数据误差和方程组近似解误差之间的关系 例如：考察方程组 当系数矩阵和右端常数项有微小扰动时，方程组的解将如何变化？**§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数  设系数矩阵有微小扰动，即  设右端常数项有微小扰动，即**§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数  设系数矩阵和右端常数项均有微小扰动，即 上例说明，该方程组的解对初始元素的扰动非常敏感。**§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数误差分析 —— 设方程组为AX = b，系数矩阵 A、右端常数项 b 和方程组解 X 产生的扰动分别记为 A、 b 和 X，则 绝对误差：|| A||，|| b||，|| X|| 相对误差： 前面的例子 ——   **如果一个方程组的系数矩阵或常数项的微小扰动会引起解的巨大变化，则称这样的方程组是病态的，否则称之为是良态的。 病态方程组对任何算法都将产生数值不稳定性。§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数条件数 设方程组 AX = b 中仅 b 有扰动 b，则 设方程组 AX = b 中仅 A 有扰动 A，则**AX = b—— 刻画方程组的病态程度§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数 若矩阵范数取 1-范数，则得到 1-条件数 —— 若矩阵范数取 ∞ -范数，则得到 ∞ -条件数 —— 若矩阵范数取 2-范数，则得到谱条件数 —— 由范数性质可知，**称 为矩阵 A 的条件数，记作§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数条件数 cond (A) 反映了方程组原始数据的相对误差在解中可能被放大的倍数。 当条件数较小时，原始数据的误差对解的影响不会很大，此时方程组是良态的； 当 cond (A) >> 1时，解对于原始数据的扰动可能很敏感，此时方程组是病态的。 例如：方程组 则 故该方程组是病态的。**§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数病态方程组求解时需要注意的问题 常用的几种判定方程组为病态的经验方法 当det (A) 相对来说很小时，或者矩阵 A 的某些行(列)近似线性相关时，可能为病态； 矩阵在采用选主元消去法求解方程组时，在消元过程中出现很小的主元，可能为病态； 解方程组得到了一个很大的解，或者特征值相差大数量级，可能为病态； 当系数矩阵的元素间数量级相差很大，且无一定规则时，可能为病态。**§3.6 方程组的性态及条件数§3.6 方程组的性态及条件数病态方程组求解时需要注意的问题 求解病态方程组时，常用的几种处理原则 采用高精度的算术运算； 采用预处理方法； 采用某些特殊的数值方法求解； 重新寻找出现病态的原因，改变原问题的提法。**数值算法小故事 —— 蝴蝶效应数值算法小故事 —— 蝴蝶效应蝴蝶效应是气象学家洛伦兹1963年提出来的。 其大意为：一只南美洲亚马孙河流域热带雨林中的蝴蝶，偶尔扇动几下翅膀，可能在两周后引起美国德克萨斯引 起一场龙卷风。**南美洲美国病态问题数值算法小故事 —— 蝴蝶效应数值算法小故事 —— 蝴蝶效应蝴蝶效应在社会学界用来说明： 一个坏的、微小的机制，如果不加以及时地引导、调节，会给社会带来非常大的危害，戏称为“龙卷风”或“风暴”； 一个好的、微小的机制，只要正确指引，经过一段时间的努力，将会产生轰动效应，称为“革命”。**