线性方程组的数值解法.ppt

《线性方程组的数值解法.ppt》由会员分享，可在线阅读，更多相关《线性方程组的数值解法.ppt（97页珍藏版）》请在金锄头文库上搜索。

1、 n n阶线性代数方程组的一般形式为阶线性代数方程组的一般形式为：第三章第三章 线性方程组的数值解法线性方程组的数值解法问题的提出问题的提出：写成矩阵写成矩阵- -向量形式向量形式 若矩阵若矩阵 非奇异，即非奇异，即 的行列式的行列式 ，根，根据克莱姆（据克莱姆（Gramer）法则，方程组有唯一）法则，方程组有唯一 解：解：其中其中 为系数矩阵，为系数矩阵， 为解向量，为解向量， 为右端常向量。为右端常向量。其中其中 表示表示 ， 表示表示 中第中第 列换成列换成 后所得的行列式。后所得的行列式。 当阶数较高时用这种方法求解是不现实的。当阶数较高时用这种方法求解是不现实的。 阶行阶行列式有列式

2、有 项，每项又是项，每项又是 个数的乘积。对较大的个数的乘积。对较大的 ，其，其计算量之大计算量之大，是一般计算机难以完成的。而且，是一般计算机难以完成的。而且，这时的这时的舍入误差舍入误差对计算结果的影响也较大。对计算结果的影响也较大。例如，求解一个例如，求解一个20阶线性方程组，用加减消元法需阶线性方程组，用加减消元法需3000次乘法运算，而用克莱姆法则要进行次乘法运算，而用克莱姆法则要进行 次运算，如用每秒次运算，如用每秒1亿次乘法运算的计算机要亿次乘法运算的计算机要30万年。万年。线性代数方程组的计算机解法常用方法：线性代数方程组的计算机解法常用方法：直接法直接法 迭代法迭代法消去法消

3、去法矩阵三角分解法矩阵三角分解法直接法直接法：经过有限步算术运算，可求得方程组：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）的精确解的方法（若在计算过程中没有舍入误差）迭代法迭代法：用某种极限过程去逐步逼近线性方程：用某种极限过程去逐步逼近线性方程组精确解的方法组精确解的方法 迭代法具有占存储单元少，程序设计简单，原迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题敛性及收敛速度等问题3.1 消去法消去法消去法的基本思想：消去法的基本思想：是通过将一个方程乘或除以是通过

4、将一个方程乘或除以某个常数，以及将两个方程相加减，逐步减少方程中某个常数，以及将两个方程相加减，逐步减少方程中的变元数，最终使每个方程只含一个变元，从而得出的变元数，最终使每个方程只含一个变元，从而得出所求的解。所求的解。消去法在线性代数中已有详细的讨论，在此只给消去法在线性代数中已有详细的讨论，在此只给出一些说明以及算法的具体描述出一些说明以及算法的具体描述。消去法常用方法：消去法常用方法：高斯消去法高斯消去法选主元消去法选主元消去法高斯约旦消去法高斯约旦消去法高斯消去法属于直接法，一般由高斯消去法属于直接法，一般由高斯消去法属于直接法，一般由高斯消去法属于直接法，一般由“消元过程消元过程”

5、和和和和“回代过程回代过程”两部分组成。先举几个简单实例，两部分组成。先举几个简单实例，两部分组成。先举几个简单实例，两部分组成。先举几个简单实例，再对一般再对一般再对一般再对一般n n n n阶方程组说明高斯消去法的基本思想。阶方程组说明高斯消去法的基本思想。阶方程组说明高斯消去法的基本思想。阶方程组说明高斯消去法的基本思想。 消去法消去法3.1 高斯消去法高斯消去法 按自然顺序进行的消元法按自然顺序进行的消元法例例 1 用高斯消元法求解方程组用高斯消元法求解方程组 解解 用第一个方程削去后两个方程中的用第一个方程削去后两个方程中的 得得 再用第再用第2个方程消去第个方程消去第3个方程中的个

6、方程中的 得得最后，经过会代求得原方程组的解为最后，经过会代求得原方程组的解为 例例 2 解方程组解方程组解：解：消元消元回代回代得得消去法消去法下面讨论一般下面讨论一般下面讨论一般下面讨论一般 n n n n 阶线性方程组的高斯消去法。阶线性方程组的高斯消去法。阶线性方程组的高斯消去法。阶线性方程组的高斯消去法。 记记记记 为为为为 ， 和和和和 的元素的元素的元素的元素分别记为分别记为分别记为分别记为 和和和和 ， ，系数上标，系数上标，系数上标，系数上标 代表第代表第代表第代表第1 1 1 1次消元之前的状态。次消元之前的状态。次消元之前的状态。次消元之前的状态。 第第第第1 1 1 1

7、次消元时，设次消元时，设次消元时，设次消元时，设 对每行计算乘数对每行计算乘数对每行计算乘数对每行计算乘数 用用用用 乘以第乘以第乘以第乘以第1 1个方程，加到第个方程，加到第个方程，加到第个方程，加到第 个方程，消去个方程，消去个方程，消去个方程，消去第第第第 2 2个方程到第个方程到第个方程到第个方程到第 个方程的未知数个方程的未知数个方程的未知数个方程的未知数 ，得得得得 即即即即: :其中其中其中其中： 第第第第 次消元次消元次消元次消元 时，设第时，设第时，设第时，设第 次消元已次消元已次消元已次消元已完成，即有完成，即有完成，即有完成，即有 其中：其中：其中：其中：设设设设 ，计算

8、乘数，计算乘数，计算乘数，计算乘数 只要只要只要只要 ，消元过程就可以进行下去，直到经，消元过程就可以进行下去，直到经，消元过程就可以进行下去，直到经，消元过程就可以进行下去，直到经过过过过 消元之后，消元过程结束，得消元之后，消元过程结束，得消元之后，消元过程结束，得消元之后，消元过程结束，得 也即也即也即也即这是一个与原方程组等价的这是一个与原方程组等价的这是一个与原方程组等价的这是一个与原方程组等价的上三角形上三角形上三角形上三角形方程组。把方程组。把方程组。把方程组。把经过经过经过经过 n-1n-1n-1n-1次消元将线性方程组化为上三角形方程组的次消元将线性方程组化为上三角形方程组的

9、次消元将线性方程组化为上三角形方程组的次消元将线性方程组化为上三角形方程组的计算过程称为计算过程称为计算过程称为计算过程称为消元过程消元过程消元过程消元过程。 当当当当 时，对上三角形方程组自下而上逐步回时，对上三角形方程组自下而上逐步回时，对上三角形方程组自下而上逐步回时，对上三角形方程组自下而上逐步回代解方程组，计算代解方程组，计算代解方程组，计算代解方程组，计算 , , , ,即即即即 , , , ,称为各次消元的主元素，称为各次消元的主元素，称为各次消元的主元素，称为各次消元的主元素， 主元素所在的行称为主元素所在的行称为主元素所在的行称为主元素所在的行称为主行主行主行主行。高斯消去法

10、的计算步骤为高斯消去法的计算步骤为高斯消去法的计算步骤为高斯消去法的计算步骤为：1 1 1 1消元过程消元过程消元过程消元过程 设设设设 ，对，对，对，对 ，计算，计算，计算，计算 2 2 2 2回代过程回代过程回代过程回代过程 综上所述，高斯消去法的框图如图综上所述，高斯消去法的框图如图综上所述，高斯消去法的框图如图综上所述，高斯消去法的框图如图3-13-13-13-1所示。从所示。从所示。从所示。从中可看出高斯消去法的计算机运算和存储方式的特点：中可看出高斯消去法的计算机运算和存储方式的特点：中可看出高斯消去法的计算机运算和存储方式的特点：中可看出高斯消去法的计算机运算和存储方式的特点：

11、1 1 1 1按消元规则进行运算后，对角线以下元素为按消元规则进行运算后，对角线以下元素为按消元规则进行运算后，对角线以下元素为按消元规则进行运算后，对角线以下元素为0 0 0 0。故对于对角线以下元素不用作计算，减小了计算量。故对于对角线以下元素不用作计算，减小了计算量。故对于对角线以下元素不用作计算，减小了计算量。故对于对角线以下元素不用作计算，减小了计算量。 2 2 2 2对角线以下元素对回代求解无影响，故可将乘对角线以下元素对回代求解无影响，故可将乘对角线以下元素对回代求解无影响，故可将乘对角线以下元素对回代求解无影响，故可将乘数放在该处，即数放在该处，即数放在该处，即数放在该处，即以

12、节省存储单元。以节省存储单元。以节省存储单元。以节省存储单元。3 3 3 3对角线以上元素和常数变换后的元素仍放在原来对角线以上元素和常数变换后的元素仍放在原来对角线以上元素和常数变换后的元素仍放在原来对角线以上元素和常数变换后的元素仍放在原来的位置以节省存储单元。的位置以节省存储单元。的位置以节省存储单元。的位置以节省存储单元。 4 4 4 4回代后的数值仍放在常数项存储单元回代后的数值仍放在常数项存储单元回代后的数值仍放在常数项存储单元回代后的数值仍放在常数项存储单元 这时这时这时这时 单元中存放的就是输出值单元中存放的就是输出值单元中存放的就是输出值单元中存放的就是输出值定理定理2 Ax

13、=b 可用高可用高 斯消元法求解的充分必要条件是：斯消元法求解的充分必要条件是：系数矩阵系数矩阵 A 的各阶顺序主子式均不为零。的各阶顺序主子式均不为零。高斯消元法的条件高斯消元法的条件定理定理1 如果在消元过程中如果在消元过程中A的主元素的主元素 (k=1,2,n) ,则可通过高斯消元法求出则可通过高斯消元法求出Ax=b 的解。的解。引理引理 A的主元素的主元素 (k=1,2,n) 的充要的充要条件是矩阵条件是矩阵A的各阶的各阶顺序主子式顺序主子式不为零，即不为零，即定理定理定理定理：高斯消去法求解：高斯消去法求解：高斯消去法求解：高斯消去法求解 阶线性方程组共需乘除法阶线性方程组共需乘除法

14、阶线性方程组共需乘除法阶线性方程组共需乘除法次数近似为次数近似为次数近似为次数近似为 。证明：见书证明：见书证明：见书证明：见书P64P64 高斯消去法的计算量高斯消去法的计算量讨讨 论论：在求解线性方程组时其系数矩阵绝大部分都是非奇在求解线性方程组时其系数矩阵绝大部分都是非奇在求解线性方程组时其系数矩阵绝大部分都是非奇在求解线性方程组时其系数矩阵绝大部分都是非奇异的，但可能出现主元素异的，但可能出现主元素异的，但可能出现主元素异的，但可能出现主元素 消去法消去法消去法消去法无法进行；无法进行；或或| akk(k) |1时，带来舍入误差的扩散。时，带来舍入误差的扩散。如何处理如何处理？ 例例

15、1 解方程组解方程组 解法一解法一 用高斯消元法求解（取用高斯消元法求解（取5位有效数字），用第位有效数字），用第 一个方程消去第二个方程中的一个方程消去第二个方程中的3.1.2 高斯主元素消元法高斯主元素消元法因而再回代，得因而再回代，得 而精确值为而精确值为 显然该解与精确值相差显然该解与精确值相差太远，为了控制误差，采用另一种消元过程。太远，为了控制误差，采用另一种消元过程。解法二解法二 为了避免绝对值很小的元素作为主元，先交为了避免绝对值很小的元素作为主元，先交换两个方程，得到换两个方程，得到 消去第二个方程中的消去第二个方程中的 得得 再回代，解得再回代，解得 结果与准确解非常接近。

16、这个例子告诉我们，在采用高结果与准确解非常接近。这个例子告诉我们，在采用高斯消元法解方程组时，用做除法的小主元素可能使舍入斯消元法解方程组时，用做除法的小主元素可能使舍入误差增加，误差增加，主元素的绝对值越小，则舍入误差影响越大主元素的绝对值越小，则舍入误差影响越大。固应避免采用绝对值小的主元素，同时选主元素尽量的固应避免采用绝对值小的主元素，同时选主元素尽量的大，可使该法具有较好的数值稳定性。大，可使该法具有较好的数值稳定性。 为避免上述错误，可在每一次消元之前增加一为避免上述错误，可在每一次消元之前增加一为避免上述错误，可在每一次消元之前增加一为避免上述错误，可在每一次消元之前增加一个选主

17、元的过程，将绝对值大的元素交换到主对角个选主元的过程，将绝对值大的元素交换到主对角个选主元的过程，将绝对值大的元素交换到主对角个选主元的过程，将绝对值大的元素交换到主对角线的位置。根据交换的方法可分成线的位置。根据交换的方法可分成线的位置。根据交换的方法可分成线的位置。根据交换的方法可分成全选主元全选主元全选主元全选主元和和和和列选列选列选列选主元主元主元主元两种方法。两种方法。两种方法。两种方法。列主元素消元法列主元素消元法 列选主元是当变换到第列选主元是当变换到第列选主元是当变换到第列选主元是当变换到第k k 步时，从步时，从步时，从步时，从k k列的列的列的列的 及以及以及以及以下的各元

18、素中选取绝对值最大的元素，然后通过行下的各元素中选取绝对值最大的元素，然后通过行下的各元素中选取绝对值最大的元素，然后通过行下的各元素中选取绝对值最大的元素，然后通过行交交交交换换换换将其交换到将其交换到将其交换到将其交换到 的位置上。交换系数矩阵中的两行的位置上。交换系数矩阵中的两行的位置上。交换系数矩阵中的两行的位置上。交换系数矩阵中的两行（包括常数项），相当于两个方程的位置交换了。（包括常数项），相当于两个方程的位置交换了。（包括常数项），相当于两个方程的位置交换了。（包括常数项），相当于两个方程的位置交换了。例：例：求解线性方程组求解线性方程组 解法一：用列主元素消元法，方程组增广矩阵

19、为：解法一：用列主元素消元法，方程组增广矩阵为：交换交换交换交换1 1、3 3行（行（行（行（列选主列选主列选主列选主）消元消元消元消元消元消元消元消元回代计算解为回代计算解为选主元选主元选主元选主元全选主元素消元法全选主元素消元法 全选主元是当变换到第全选主元是当变换到第全选主元是当变换到第全选主元是当变换到第k k 步时，从右下角步时，从右下角步时，从右下角步时，从右下角 n-k+1n-k+1阶子阵中选取绝对值大的元素，然后通过阶子阵中选取绝对值大的元素，然后通过阶子阵中选取绝对值大的元素，然后通过阶子阵中选取绝对值大的元素，然后通过行行行行交换交换交换交换与与与与列交换列交换列交换列交换

20、将其交换到将其交换到将其交换到将其交换到a a kkkk 的位置上，并且保留的位置上，并且保留的位置上，并且保留的位置上，并且保留交换的信息，以供后面调整解向量中分量的次序交换的信息，以供后面调整解向量中分量的次序交换的信息，以供后面调整解向量中分量的次序交换的信息，以供后面调整解向量中分量的次序时使用。时使用。时使用。时使用。交换交换交换交换1 1、3 3行行行行交换交换交换交换1 1、3 3列列列列回代计算得回代计算得从而原方程的解为从而原方程的解为消元消元消元消元消元消元消元消元 比较而言比较而言,Gauss,Gauss顺序消去法条件苛刻顺序消去法条件苛刻, ,且且数值不稳定数值不稳定;

21、 Gauss; Gauss全主元消去法工作量偏大，全主元消去法工作量偏大，算法复杂；对于算法复杂；对于Gauss-JordanGauss-Jordan消去法形式上消去法形式上比其他消元法简单，且无回代求解，但计算比其他消元法简单，且无回代求解，但计算量大。因此从算法优化的角度考虑，量大。因此从算法优化的角度考虑， GaussGauss列主元消去法比较好。列主元消去法比较好。消去法小节消去法小节3.2 矩阵三角分解法矩阵三角分解法3.2.1 3.2.1 矩阵三角分解原理矩阵三角分解原理矩阵三角分解原理矩阵三角分解原理 应用高斯消去法解应用高斯消去法解应用高斯消去法解应用高斯消去法解 阶线性方程阶

22、线性方程阶线性方程阶线性方程 经过经过经过经过 步消去后得出一个等价的上三角形方程组步消去后得出一个等价的上三角形方程组步消去后得出一个等价的上三角形方程组步消去后得出一个等价的上三角形方程组 ，对上三角形方程组用逐步回代就可以求出解来。，对上三角形方程组用逐步回代就可以求出解来。，对上三角形方程组用逐步回代就可以求出解来。，对上三角形方程组用逐步回代就可以求出解来。这个过程也可通过矩阵分解来实现。这个过程也可通过矩阵分解来实现。这个过程也可通过矩阵分解来实现。这个过程也可通过矩阵分解来实现。 将非奇异阵分解成一个下三角阵将非奇异阵分解成一个下三角阵将非奇异阵分解成一个下三角阵将非奇异阵分解成

23、一个下三角阵 和上三角阵和上三角阵和上三角阵和上三角阵 的乘积的乘积的乘积的乘积 ： 称为称为称为称为对矩阵对矩阵对矩阵对矩阵 的三角分解的三角分解的三角分解的三角分解，又称，又称，又称，又称 分解分解分解分解。 高斯消去法解线性代数方程组的一种变形解法。高斯消去法解线性代数方程组的一种变形解法。高斯消去法解线性代数方程组的一种变形解法。高斯消去法解线性代数方程组的一种变形解法。杜里特尔分解：杜里特尔分解：杜里特尔分解：杜里特尔分解：把把把把 分解成一个分解成一个分解成一个分解成一个单位下三角阵单位下三角阵单位下三角阵单位下三角阵 和一个上三角阵和一个上三角阵和一个上三角阵和一个上三角阵 的乘

24、积。的乘积。的乘积。的乘积。克劳特分解克劳特分解克劳特分解克劳特分解: : : : 把把把把 分解成一个下三角阵分解成一个下三角阵分解成一个下三角阵分解成一个下三角阵 和一个和一个和一个和一个单位上三角阵单位上三角阵单位上三角阵单位上三角阵 的乘积。的乘积。的乘积。的乘积。若矩阵若矩阵若矩阵若矩阵 各阶主子式不为零，则可各阶主子式不为零，则可各阶主子式不为零，则可各阶主子式不为零，则可唯一地分唯一地分唯一地分唯一地分解成一解成一解成一解成一个单位下三角阵个单位下三角阵个单位下三角阵个单位下三角阵 和一个非奇异的上三角阵和一个非奇异的上三角阵和一个非奇异的上三角阵和一个非奇异的上三角阵 的的的的

25、乘积。乘积。乘积。乘积。定定定定 理理理理：证明：略（证明：略（证明：略（证明：略（P71P71） 杜里特尔分解杜里特尔分解 A=LU杜里特尔分解杜里特尔分解杜里特尔分解杜里特尔分解(一般算法一般算法)由矩阵乘法规则由矩阵乘法规则即：即：即：即：由此可得由此可得 的第一行元素和的第一行元素和 的第一列元素的第一列元素 当已得出当已得出 的前的前 行元素和行元素和 的前的前 列元素，则对于列元素，则对于 ，由，由又可得计算又可得计算 的第的第 行元素和行元素和 的第的第 列元列元素的公式素的公式: :例例 求矩阵求矩阵的的LU分解。分解。 u11=2 u12=1 u13=4 所以所以 有了矩阵有

26、了矩阵 A A 的的LULU分解计算公式，当求解线性方分解计算公式，当求解线性方程组程组 时，等价于求解时，等价于求解 。这时可归结为。这时可归结为利用递推计算相继求解两个三角形方程组（系数矩利用递推计算相继求解两个三角形方程组（系数矩阵为三角矩阵）。阵为三角矩阵）。用顺代，用顺代，由由 求出求出 ，再，再利用利用回代，回代，由由 求出求出 。3.2.2 解线性方程组的三角分解法解线性方程组的三角分解法用用杜里特尔杜里特尔三角分解法解线性方程组三角分解法解线性方程组 的的计算方法计算方法：对于对于 ，计算，计算 和和 。求解求解 ，即计算，即计算求解求解 ，即计算。，即计算。计算计算 和和 。

27、克劳特克劳特克劳特克劳特分解求方程组步骤分解求方程组步骤分解求方程组步骤分解求方程组步骤：略略其它其它矩阵分解法矩阵分解法求解特殊的线性方程组：求解特殊的线性方程组：平方根法：主要用于求解平方根法：主要用于求解正定矩阵正定矩阵的线性方程组的线性方程组追赶法：主要用于求解特殊矩阵的三对角方程组追赶法：主要用于求解特殊矩阵的三对角方程组 见书见书 P78P87用用LU LU 直接分解的方法求解线性方程组的计算量为直接分解的方法求解线性方程组的计算量为 ，和高斯消去法的计算量的数量级基本相同，和高斯消去法的计算量的数量级基本相同。消去法和矩阵三角分解法比较消去法和矩阵三角分解法比较消去法和矩阵三角分

28、解法比较消去法和矩阵三角分解法比较当方程组系数矩阵不变，只有右侧向量当方程组系数矩阵不变，只有右侧向量b b变化时，变化时，用用LULU分解法比消去法速度快。因为右侧向量分解法比消去法速度快。因为右侧向量b b的的改变改变不影响不影响LULU的变化。的变化。高斯消去法和高斯消去法和LU分解法是等价的，其关键是把一般分解法是等价的，其关键是把一般方程组变为三角方程组，只是实现途径不同方程组变为三角方程组，只是实现途径不同。设给定设给定 中的向量序列中的向量序列 ，其中其中 若对任何若对任何 ，都有，都有，则向量则向量 称为向量序列称为向量序列 的极限，的极限，或者说向量序列收敛于向量或者说向量序

29、列收敛于向量 ，记为：，记为： 向量收敛的定义向量收敛的定义：3.6 3.6 迭代法迭代法迭代法迭代法生成向量序列生成向量序列 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)按下列按下列迭代格式迭代格式雅可比迭代法雅可比迭代法 对线性方程组可以建立不同

30、的迭代格式。下面对线性方程组可以建立不同的迭代格式。下面介绍构造迭代格式的几种常用方法介绍构造迭代格式的几种常用方法，雅克比迭代雅克比迭代法法和和高斯塞德尔迭代法高斯塞德尔迭代法。设方程组设方程组其中其中 aii(i) 0 ( i=1 , 2 , , n)分别从上式分别从上式n个方程中分离出个方程中分离出n个变量，如下：个变量，如下：等价方程组等价方程组等价方程组等价方程组建立迭代格式建立迭代格式称为称为雅可比雅可比(Jacobi)迭代法迭代法又称又称简单迭代法简单迭代法。 高斯高斯塞德尔迭代法塞德尔迭代法在在 Jacobi 迭代中迭代中,用已有的用已有的迭代新值代替旧值迭代新值代替旧值，即：

31、，即：建建 立立 迭迭 代代 格格 式式或缩写为或缩写为称为称为高斯高斯塞德尔塞德尔（Gauss Seidel）迭代法迭代法。 例例1 用雅可比迭代法解方程组用雅可比迭代法解方程组 取取计算如下计算如下 雅雅雅雅克克克克比比比比迭迭迭迭代代代代格格格格式式式式Gauss-Seidel 迭代格式为迭代格式为 例例2 用用GaussSeidel 迭代法解上题。迭代法解上题。取取 x(0)=(0,0,0)T 计算如下：计算如下： 以上介绍的两种迭代法，一般地说，高斯塞德尔以上介绍的两种迭代法，一般地说，高斯塞德尔以上介绍的两种迭代法，一般地说，高斯塞德尔以上介绍的两种迭代法，一般地说，高斯塞德尔比雅

32、克比要好，但也不完全是这样。比雅克比要好，但也不完全是这样。比雅克比要好，但也不完全是这样。比雅克比要好，但也不完全是这样。关于迭代法的一些问题关于迭代法的一些问题关于迭代法的一些问题关于迭代法的一些问题： 为了使迭代法计算加速，可采用为了使迭代法计算加速，可采用为了使迭代法计算加速，可采用为了使迭代法计算加速，可采用松弛法松弛法松弛法松弛法。（略）。（略）。（略）。（略） 迭代法存在收敛性问题。（略）迭代法存在收敛性问题。（略）迭代法存在收敛性问题。（略）迭代法存在收敛性问题。（略）3.3 向量与矩阵的范数向量与矩阵的范数 问题的提出问题的提出 向量范数向量范数概念是三维欧氏空间中向量长度概

33、念的概念是三维欧氏空间中向量长度概念的推广推广, ,在数值分析中起着重要作用在数值分析中起着重要作用. . 为了研究线性方程组近似解的误差估计和迭代法为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对的收敛性，我们需要对 （n n维向量空间）中向量维向量空间）中向量及及 （ 维矩阵空间）中矩阵的维矩阵空间）中矩阵的“大小大小”及及“距离距离”引进某种度量引进某种度量向量与矩阵范数向量与矩阵范数的概念的概念.平面向量平面向量 x 大小：用大小：用 距离距离 反映。反映。3.3 向量与矩阵的范数向量与矩阵的范数 引入范数的目的：引入范数的目的： 实数大小：用绝对值反映实数大小：用绝对值

34、反映复数大小：用模反映复数大小：用模反映高维空间向量高维空间向量 x “大小大小” 用用 反映？反映？ 将将度量长度数值度量长度数值的计算方法引入高维空间，的计算方法引入高维空间，用来反映空间向量的大小，就是用来反映空间向量的大小，就是范数范数的概念的概念。为了研究线性方程组近似解的误差估计和迭为了研究线性方程组近似解的误差估计和迭为了研究线性方程组近似解的误差估计和迭为了研究线性方程组近似解的误差估计和迭代法的收敛性等。代法的收敛性等。代法的收敛性等。代法的收敛性等。 非负性非负性 |x| 0 ，等号仅当，等号仅当 x=0 时成立；时成立； 齐次性齐次性 对任何实数对任何实数 , | x|=

35、| | |x|； 三角不等式三角不等式 |x+y| |x| +|y| ； 则称则称 |x| 为向量为向量 x 的范数。的范数。定义定义 对任意对任意 n 维向量维向量 x Rn，若对应非负实数，若对应非负实数 |x| ， 满足满足 3.3.1 向量的范数向量的范数 由定义可知，向量由定义可知，向量 的范数的范数 是按一定规律是按一定规律与与 对应的实数，该实数的值没有确定，但只要满对应的实数，该实数的值没有确定，但只要满足这三个条件，这个实数就是向量足这三个条件，这个实数就是向量 的一种范数。的一种范数。因此定义中的三个条件称为因此定义中的三个条件称为范数公理范数公理。当当 时时，向量范数向量

36、范数 有如下性质有如下性质证：利用条件证：利用条件，有，有 证：证：它们分别叫做向量的它们分别叫做向量的 -范数范数、1-范数范数、2-范数范数、p -范数（范数（0p+ ）。 p -范数是以上范数的统一表范数是以上范数的统一表达形式。达形式。常用的向量范数常用的向量范数: 满足定义的范数不是唯一的满足定义的范数不是唯一的.设设 x = ( x1 , x2 , , xn)T ，常常用用的的向向量量范范数数有有 对于对于范数，有范数，有当当 时，有时，有 ， 只有当只有当 时，才有时，才有 对任意实数对任意实数 ，因为，因为 ，所以，所以 。对任意向量对任意向量 ，有，有因此因此因此因此 是是是

37、是n n维空间的一种范数维空间的一种范数维空间的一种范数维空间的一种范数例：例：范数的证明范数的证明向量序列收敛性定理：向量序列收敛性定理： 向量序列向量序列收敛收敛 ( (即即 ) )的充要条件是的充要条件是 ，其中，其中 为向量的任一种范数。为向量的任一种范数。 按按不同方式规定的范数不同方式规定的范数, ,其值一般不同。但在各种其值一般不同。但在各种范数下考虑向量序列范数下考虑向量序列收敛性的结论是一致的收敛性的结论是一致的。即向量。即向量序列如对某一种范数收敛则对其它范数也收敛，且有序列如对某一种范数收敛则对其它范数也收敛，且有相同的极限。这样，在研究某一具体问题时，可以选相同的极限。

38、这样，在研究某一具体问题时，可以选择一较易简单的范数。择一较易简单的范数。矩阵范数是用于定义矩阵矩阵范数是用于定义矩阵“大小大小”的量。的量。由于在大多数与估计误差有关的问题中由于在大多数与估计误差有关的问题中,矩矩阵和向量的乘积阵和向量的乘积经常出现经常出现,所以希望引进一种矩所以希望引进一种矩阵的范数阵的范数,它与向量范数有某种关系。它与向量范数有某种关系。3.3.2 矩阵的范数矩阵的范数 定义定义：设：设 ， ，定义矩阵，定义矩阵 的范数的范数 对于每一种向量范数对于每一种向量范数 ，相应的矩阵范数，相应的矩阵范数 为为其中其中 是指是指 的最大可能值。即遍取所有不为的最大可能值。即遍取

39、所有不为0 0的的 ，比值比值 中最大的中最大的，定义，定义为为 的矩阵范数的矩阵范数。 矩阵范数的性质矩阵范数的性质： , ,且仅当且仅当 时，时， ； 对任意实数对任意实数 ， ； 对同维方阵对同维方阵 ，有，有: : 相容性条件：相容性条件： 由矩阵范数的定义可直接得到由矩阵范数的定义可直接得到 ，即有，即有 ，称为，称为相容性条件。即相容性条件。即所给的所给的矩阵范数与向量范数是相容的。矩阵范数与向量范数是相容的。证明证明 p92矩阵范数与向量范数的关系矩阵范数与向量范数的关系： 矩阵范数与向量范数密切相关，向量范数有相应矩阵范数与向量范数密切相关，向量范数有相应的矩阵范数，即：的矩阵

40、范数，即： （如（如 ）常用的矩阵范数有（矩阵范数的求取）常用的矩阵范数有（矩阵范数的求取）它们分别叫做矩阵的它们分别叫做矩阵的 -范数范数、1-范数范数。 例例4 设设则则求相应各范数。求相应各范数。解解验证相容性验证相容性验证相容性验证相容性3.4 3.4 方程组的性态方程组的性态 前几节讨论了求解线性代数方程组的直接法前几节讨论了求解线性代数方程组的直接法. .给出给出系数矩阵系数矩阵A A和自由项和自由项b,b,求未知向量求未知向量x.x.实践中实践中,A,A和和b b往往往是实验观测数据或是计算所得结果往是实验观测数据或是计算所得结果. .因此我们处理因此我们处理的线性方程组的线性方

41、程组 实际上变成了实际上变成了的关系怎样的关系怎样, ,是人们十分关心的问题是人们十分关心的问题. .3.4.1 3.4.1 方程组的性态和矩阵的条件数方程组的性态和矩阵的条件数例例 1 解方程组解方程组 其中其中 现用绝对精确的计算（即不带任何舍入误差的计算）现用绝对精确的计算（即不带任何舍入误差的计算） 求解，可以看出求解，可以看出此时，我们发现对于两组不同的自由项此时，我们发现对于两组不同的自由项它的差只有它的差只有而所得解而所得解 与与 之差却是之差却是两组不同的右端其分量之差不过是两组不同的右端其分量之差不过是 可是解的差高可是解的差高 达达 之之1860倍像这样的方程组或矩阵倍像这

42、样的方程组或矩阵A 就叫做病态的就叫做病态的 定义定义1 若方程组若方程组 Ax=b 的系数矩阵的系数矩阵 A 或或右端向量右端向量 b 的微小变化（小扰动）引起解产生巨大变化的微小变化（小扰动）引起解产生巨大变化,则则称此方程组为称此方程组为病态方程组病态方程组; A称为称为病态矩阵病态矩阵, 否则否则称为称为良态方程组良态方程组, A 称为称为良态矩阵良态矩阵。 定理定理：设：设 非奇异，非奇异， ，且且 则则 为了定量地刻划方程组的为了定量地刻划方程组的“病态病态”程度，下程度，下面就一般方程组面就一般方程组 进行讨论。首先考察右端进行讨论。首先考察右端项项b b 的扰动对解的影响的扰动

43、对解的影响。证证： 设设x为为Ax=b的准确解，当方程组右端有小扰动的准确解，当方程组右端有小扰动 b而而A准确时准确时,受扰解为受扰解为 x + x , 即即 A(x + x)=b+ b 因为因为 Ax=b 所以所以 x=A-1 b 又由又由得得因此因此所以所以所以所以此此不不等等式式表表明明,解解的的相相对对误误差差不不超超过过b的的相相对对误误差差的的 |A| |A-1| 倍倍.若系数矩阵若系数矩阵A也有小扰动也有小扰动 A ,则还可进一步导出更一则还可进一步导出更一般的误差估计式般的误差估计式定义定义2 设设A 为非奇异矩阵，称数为非奇异矩阵，称数cond(A)= |A| |A-1|

44、为为A 矩阵的条件数矩阵的条件数矩阵的条件数与范数有关，通常使用的条件数有矩阵的条件数与范数有关，通常使用的条件数有 所以，所以，Cond(A)越大越大,A的病态程度越严重。的病态程度越严重。 对任何非奇异矩阵对任何非奇异矩阵A，都有，都有 。不难证明，条件数具有如下不难证明，条件数具有如下性质性质例例 求矩阵求矩阵A 的条件数，其中的条件数，其中解：解：于是于是 从而从而所以所以A是病态的是病态的 由于计算条件数涉及到计算逆矩阵，很麻烦。由于计算条件数涉及到计算逆矩阵，很麻烦。因此实际计算中一般通过可能产生病态的现象来判断。因此实际计算中一般通过可能产生病态的现象来判断。 若在消元过程中出现

45、小主元，则若在消元过程中出现小主元，则 A A可能是病态可能是病态矩阵。但病态矩阵未必一定有这种小主元。矩阵。但病态矩阵未必一定有这种小主元。 若解方程组时出现很大的解，则若解方程组时出现很大的解，则A A可能是病态矩可能是病态矩阵。但病态矩阵也可能有一个小解。阵。但病态矩阵也可能有一个小解。 从矩阵本身看，若元素间数量级相差很大且无从矩阵本身看，若元素间数量级相差很大且无一定规律；或者矩阵的某些行或列近似相关，这样的一定规律；或者矩阵的某些行或列近似相关，这样的矩阵则有可能是病态矩阵。矩阵则有可能是病态矩阵。3.4.2 直接法的精度分析直接法的精度分析定理定理：设：设 是方程组是方程组 的一

46、个近似解，的一个近似解，其精确解记为其精确解记为 ， 为为 的余量，则有的余量，则有求得方程组求得方程组 的一个近似解的一个近似解 后，希望能判后，希望能判断其精度。检验精度的一个简单办法是将近似解断其精度。检验精度的一个简单办法是将近似解再回代到原方程组去求其余量再回代到原方程组去求其余量 。如果。如果 很很小，就认为解小，就认为解 是相当准确的。是相当准确的。该定理给出了方程组近似解的相对误差界。该定理给出了方程组近似解的相对误差界。即相对误差的事后估计即相对误差的事后估计证：证：由于由于 ，而，而 ，故有，故有 所以所以要求熟练掌握的内容：要求熟练掌握的内容：高斯消去法原理、算法、计算步

47、骤；高斯消去法原理、算法、计算步骤；主元消去法的意义、算法、计算步骤；主元消去法的意义、算法、计算步骤；矩阵三角分解法解方程组的意义、算法、计算步骤矩阵三角分解法解方程组的意义、算法、计算步骤向量和矩阵范数的定义、性质和计算方法；向量和矩阵范数的定义、性质和计算方法； 矩阵条件数的定义矩阵条件数的定义,并能估计直接法的误差并能估计直接法的误差.要求掌握的内容要求掌握的内容：采用雅可比迭代解线性方程组；采用雅可比迭代解线性方程组；采用高斯塞德尔迭代解线性方程组；采用高斯塞德尔迭代解线性方程组；本章要求本章要求 在工程实际中，线性方程组大多数的系数矩阵为在工程实际中，线性方程组大多数的系数矩阵为对

48、称正定对称正定这一性质，因此利用对称正定矩阵的三这一性质，因此利用对称正定矩阵的三角分解式（即角分解式（即乔累斯基分解乔累斯基分解）是求解对称正定方）是求解对称正定方程组的一种有效方法。其分解过程无需选主元，且程组的一种有效方法。其分解过程无需选主元，且计算量比高斯消去法、计算量比高斯消去法、LU分解法要小，还有良好分解法要小，还有良好的数值稳定性。的数值稳定性。 3.3 对称正定矩阵的乔累斯基分解对称正定矩阵的乔累斯基分解了解内容了解内容了解内容了解内容 A对称：对称：AT=A A正定：正定：A的各阶顺序主子式均大于零。的各阶顺序主子式均大于零。即即 n定义定义：对称正定矩阵：对称正定矩阵定

49、理：定理：设设A A为对称正定矩阵，则存在唯一分解为对称正定矩阵，则存在唯一分解这种分解称为乔累斯基分解。这种分解称为乔累斯基分解。其中其中L L为具有主对角元素为正数的下三角矩阵。为具有主对角元素为正数的下三角矩阵。缺点：存在开方运算，可能会出现根号下负数。缺点：存在开方运算，可能会出现根号下负数。证明、分解方法（略）证明、分解方法（略）n乔累斯基分解乔累斯基分解利用利用乔累斯基分解求解乔累斯基分解求解对称正定方程组称为对称正定方程组称为平方根法平方根法A=LDLT (L为单位下三角矩阵）为单位下三角矩阵）n改进乔累斯基分解改进乔累斯基分解利用改进利用改进乔累斯基分解求解乔累斯基分解求解对称正定方程组称为对称正定方程组称为改进平方根法改进平方根法利用改进平方根法求方程组利用改进平方根法求方程组计算公式计算公式：