计算方法课件第三章线性代数方程组的数值解法.ppt

,第三章 线性代数方程组的数 值解法,3.1 引言3.2 解线性方程组的消去法3.3 解线性方程组的矩阵分解法3.4 解线性方程组的迭代法,3.1 引言,给定一个线性方程组,求解向量 x。,第一类是直接法。即按求精确解的方法运算求解。第二类是迭代法。其思想是首先把线性方程组(3-1)等价变换为如下形式的方程组：,数值解法主要有两大类：,然后构造迭代格式,这称为一阶定常迭代格式，M 称为迭代矩阵。,3.2 解线性方程组的消去法,3.2.1 高斯消去法与高斯若当消去法,例1,第一步：先将方程（1）中未知数 的系数2除（1）的两边，得到下列方程组：,再将第二个方程减去第一个方程的4倍，第三个方程减去第一个方程的2倍。,第二步：将方程 中第二个方程的两边除以 的系数4,将第三个方程减去第二个方程：,第三步：为了一致期见，将第三个方程中的 系数变为1，除以,我们来分析一下上述过程：整个过程分两大步。一是用逐次消去未知数的方法，把原来的方程组化为与其等价的三角形方程组。用矩阵的观点来看，就是用初等变换的方法将方程组的系数矩阵进行初等变换，即,这样就将系数阵化为单位三角阵，这个过程称为“消元过程”。二是解三角形方程组，称为“回代过程”，整个过程称为“有回代过程的顺序消元法”。,下面我们来讨论一般的解n阶方程组的高斯消去法，且就矩阵的形式来介绍这种新的过程：,一般地，第k步：即将矩阵变为如下,第n步：得到：,经过上述n步过程后，原系数矩阵A变为一个单位上三角矩阵，即原方程组化为一个和它完全等价的三角形方程组，即,高斯消去法：（1）消元过程：对k=1,2,n 依次计算,(2)回代过程：,例3.1 试用高斯消去法求解线性方程组,消元过程为,解,即把原方程组等价约化为,据之回代解得,为了避免回代的计算，我们可在消元过程中直接把系数矩阵A约化为单位矩阵I，从而得到解，即,相应地，计算公式可表述为：,从而得到解,这一无回代的消去法称为高斯-若当（Jordan）消去法,二、高斯-若当（Jordan）消去法,解,例 2 试用高斯-若当消去法求解例3.1的线性方程组。,因为,解,一般公式：,高斯约当消去法是一个具有消去过程而无回代过程的算法。以上两种消去法都是沿系数矩阵的主对角线元素进行的，即第k次消元是用经过前k-1次消元之后的系数阵位于（k,k)位置的元素作除数，这时的(k,k)位置上的元素可能为0或非常小，这就可能引起过程中断或溢出停机。因此：,3.2.2 消去法的可行性和计算工作量,推论 若系数矩阵严格对角占优，即有,定理 3.2 求解 n 阶线性方程组(3-1)的高斯消去法的乘除工作量约为，加减工作量约为；而高斯-若当消去法的乘除工作量约为，加减工作量约为。,由式（3-4）知，高斯消去法在消元过程中第k步的工作量为,所以，消元过程的总工作量为,证,回代过程中的乘除和加减工作量均为,总工作量为,类似可得，高斯-若当消去法的工作量为,例 3.3 试用高斯-若当消去法求解如下矩阵方程,因为,解,$2 选主元素的消去法,主元素的选取通常采用两种方法，一种是全主元消去法,另一种是列主元消去法。下面以例介绍选主元的算法思想,例 3.4 试用选主元消去法解线性方程组,（1）用全主元高斯消去法,回代解出：,还原得：,解,（2）用全主元高斯-若当消去法,故得解为,（3）用列主元高斯消去法,回代解得,3.3 解线性方程组的矩阵分解法,一、非对称矩阵的三角分解法,对于给定的线性方程组,矩阵分解法的基本思想是：,（1）分解,显见S是一个可逆的下三角阵,解两个三角形方程组。,Crout分解（以四阶为例）,2.利用三角分解法解方程组,例1.试用克洛特分解法解线性方程组,例2 试用克洛特分解法解线性方程组,解,3.3.2 解三对角型线性方程组的追赶法,1.用LU分解矩阵A,3.3.3 对称正定矩阵的三角分解,定义 3.1 若n 阶方矩阵 A 具有性质 且对任何n 维向量 成立，则称 A 为对称正定矩阵。,定理3.4 若A 为对称正定矩阵，则(1)A的k阶顺序主子式(2)有且仅有一个单位下三角矩阵L和对角矩阵D 使得（3-16）这称为矩阵的乔里斯基（Cholesky）分解。(3)有且仅有一个下三角矩阵，使（3-17）这称为分解矩阵的平方根法。,（1）首先由A 对称正定知,由惟一性得,证,以下推导平方根法和乔里斯基分解法的计算公式。,由此可建立平方根法的递推计算公式如下：,类似地，由 得,从而可建立乔里斯基分解法的递推计算公式为,对于 依次计算,例 3.7 试分别用平方根法和乔里斯基分解法分解矩阵,解,把平方根法应用于解方程组，则把 Ax=b 化为等价方程,相应的求解公式为,把乔里斯基分解法应用于解方程组，则 Ax=b 化为等价方程,相应的求解公式为,例3.8 试用平方根法求解对称线性方程组,解,由此，可先由上三角形线性方程组,再由下三角形线性方程组,例3.9 试用乔里斯基分解法解线性方程组,解,3.4 解线性方程组的迭代法,3.4.1 雅可比迭代法与高斯-塞德尔迭代法,对（3-23）,以分量表示即,约化便得,从而可建立迭代格式,则雅可比迭代格式（3-24）可用矩阵表示为,用矩阵表示为,对雅可比迭代格式修改得,例3.10 分别用雅可比迭代法和高斯-塞德尔迭代法求解 线性方程组,解,高斯-塞德尔迭代,雅可比迭代,令 取四位小数迭代计算,由雅可比迭代得,由高斯-塞德尔迭代得,相应的迭代公式为,3.4.2 迭代法的收敛性,定理 3.5 若一阶定常迭代格式（3-26）的迭代矩阵 满足条件,则该迭代格式对任何初始向量 均收敛。,证,定理得证。,相减得,定理 3.7 若雅可比迭代法的迭代矩阵 满足条件（3-28）或（3-29），则雅可比迭代法与相应的高斯-塞德尔迭代法对任何初始向量 均收敛。,定理 3.8 一阶定常迭代格式 对任何初始向量均收敛的充分必要条件为其迭代矩阵的谱半径小于1，即,这里 为 M 的特征值,定理 3.9 若线性方程组（3-1）的系数矩阵A对称正定，则相应的高斯-塞德尔迭代法必收敛。,3.4.3 迭代法的应用说明,(1)若系数矩阵非严格对角占优，采用等价变换使之约化为系数矩阵严格对角占优的线性方程组，然后用雅可比迭代法或高斯-塞德尔迭代法求解。,(3)在实际计算时，由于无法知晓 x*，因此计算的终止原则通常近似地采用以下条件关系式,(2)特殊情况可特殊处理，以减少工作量。,