线性代数方程组.ppt

第2章 线性代数方程组,第2章 线性代数方程组,线性代数方程组,可以写为矩阵形式,其中,第2章 线性代数方程组,求解方法,方法1,计算量为矩阵求逆,矩阵求逆的方法:初等行变换法、伴随矩阵法、高斯约当法,第2章 线性代数方程组,求解方法,方法2 Crammer法则,第2章 线性代数方程组,求解方法,方法2 Crammer法则,第2章 线性代数方程组,2.1 Gauss消去法,2.1.1 消去法,消去法的过程,1.将n元方程组的n-1个方程通过“消元”，形成一个与原方程组等价的新方程组,2.继续将n-1个方程通过“消元”形成与之等价的新方程组,3.直到最后一个方程为一元一次方程为止,4.从最后一个方程中解出最后一个未知量，然后回代得到其它的解,第2章 线性代数方程组,2.1 Gauss消去法,2.1.1 消去法,消去法的基本思想:,将求解n元方程组的问题通过降维,变为等价的n-1元方程组进行求解，逐次进行直至变为一个一元一次方程为止，然后求解，再逐步回代得到其余的解,消去法的基本步骤：消去、回代,第2章 线性代数方程组,2.1 Gauss消去法,2.1.1 消去法,消去过程 对于以下的增广矩阵,第2章 线性代数方程组,2.1 Gauss消去法,2.1.1 消去法,依此类推，消去的第k步，得到矩阵,第2章 线性代数方程组,2.1 Gauss消去法,2.1.1 消去法,经过n-1步消去后，得到,然后，经过回代，得到所有的解,第2章 线性代数方程组,2.1 Gauss消去法,2.1.2 算法组织,算法 Gauss(A,b,n,x) 系数矩阵A存放于数组A中，右端向量放在数组b中,N-1次,N-k次,N-k次,N-1次,N-k次,第2章 线性代数方程组,2.1 Gauss消去法,时间复杂度分析,1.消去算法运算量,2.回代运算量,第2章 线性代数方程组,2.1 Gauss消去法,空间复杂度分析,第2章 线性代数方程组,2.1 Gauss消去法,2.1.3 主元,Gauss消去法可以顺利执行的条件,若在Gauss消去过程中出现以下两种情况,则Gauss消去过程中会出现问题,第2章 线性代数方程组,2.1 Gauss消去法,2.1.3 主元,第1种情况下,(1)若A非奇，则可以通过交换方程组中各方程的行序,可以继续执行消去过程,(2)若A奇异，则不能继续执行消去过程,第2章 线性代数方程组,2.1 Gauss消去法,2.1.3 主元,第2种情况下,真实解为,按Gauss消去法为,第2章 线性代数方程组,2.1 Gauss消去法,2.1.3 主元,原因,则,同理,若有误差,第2章 线性代数方程组,2.1 Gauss消去法,2.1.3 主元,列主元Gauss消去法,若A非奇则可以通过选主元的方式继续执行消去过程,第2章 线性代数方程组,2.1 Gauss消去法,2.1.3 主元,算法 GaussPP(A,b,n,x) 列主元消去法,第2章 线性代数方程组,列主元消去法的特点：,2.1 Gauss消去法,2.1.3 主元,当系数矩阵的行列式不为0时，算法总可以执行完成,算法稳定，在消去过程中计算误差能被有效控制；,当矩阵A是对称正定或严格对角占优，则不选主元，Gauss消去法也是稳定的,第2章 线性代数方程组,2.2 矩阵分解,2.2.1 Gauss消去法的矩阵意义,第一步消去等价于用一个初等下三角阵左乘方程组的两端,第2章 线性代数方程组,2.2 矩阵分解,2.2.1 Gauss消去法的矩阵意义,第2章 线性代数方程组,2.2 矩阵分解,2.2.1 Gauss消去法的矩阵意义,第2章 线性代数方程组,2.2 矩阵分解,2.2.1 Gauss消去法的矩阵意义,第2章 线性代数方程组,2.2 矩阵分解,2.2.2 矩阵的LU分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.2 矩阵的LU分解,由此定理可以得到L和U的计算公式,第2章 线性代数方程组,2.2 矩阵分解,2.2.2 矩阵的LU分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.2 矩阵的LU分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.2 矩阵的LU分解,在迭代过程中，为节省存储空间，可以将每个系数存储在矩阵中,第2章 线性代数方程组,2.2 矩阵分解,2.2.3 其它的三角分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.3 其它的三角分解,推论2.2,第2章 线性代数方程组,2.2 矩阵分解,2.2.3 其它的三角分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.4 对称正定矩阵,定理2.3,第2章 线性代数方程组,2.2 矩阵分解,2.2.4 对称正定矩阵,定理2.4,第2章 线性代数方程组,2.2 矩阵分解,2.2.5 带状矩阵的分解,定理2.5,第2章 线性代数方程组,2.2 矩阵分解,2.2.5 带状矩阵的分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.5 带状矩阵的分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.5 带状矩阵的分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.5 带状矩阵的分解,第2章 线性代数方程组,2.2 矩阵分解,2.2.6 矩阵分解的应用,第2章 线性代数方程组,2.2 矩阵分解,2.2.6 矩阵分解的应用,第2章 线性代数方程组,2.2 矩阵分解,2.2.6 矩阵分解的应用,第2章 线性代数方程组,2.2 矩阵分解,2.2.6 矩阵分解的应用,第2章 线性代数方程组,2.2 矩阵分解,第2章 线性代数方程组,2.3 线性方程组解的可靠性,残向量,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.1 误差向量和范数,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.1 误差向量和范数,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.1 误差向量和范数,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.1 误差向量和范数,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.1 误差向量和范数,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.1 误差向量和范数,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.1 误差向量和范数,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.1 误差向量和范数,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,病态方程组的特征及判别,第2章 线性代数方程组,2.3 线性方程组解的可靠性,2.3.3 误差的代数表征,求解病态方程组的措施,第2章 线性代数方程组,2.4 解线性方程组的迭代法,第2章 线性代数方程组,2.4 解线性方程组的迭代法,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.1 基本迭代法,Jacobi迭代,第2章 线性代数方程组,2.4 解线性方程组的迭代法,Jacobi迭代,2.4.1 基本迭代法,第2章 线性代数方程组,2.4 解线性方程组的迭代法,Gauss-Seidel迭代,2.4.1 基本迭代法,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.2 迭代法的矩阵表示,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.2 迭代法的矩阵表示,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.2 迭代法的矩阵表示,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.2 迭代法的矩阵表示,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.2 迭代法的矩阵表示,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.2 迭代法的矩阵表示,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.2 迭代法的矩阵表示,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.3 收敛性,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.3 收敛性,定理2.6,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.3 收敛性,第2章 线性代数方程组,2.4 解线性方程组的迭代法,2.4.3 收敛性,第2章