第一单元 线性代数方程组的直接解法.pptVIP

§2 LU分解法 §2 LU分解法 应用LUGauss函数求方程Ax=b解： Function b=LUM(kk,a,b) n=tength(b); for k=1:n-1 tb=b(k); b(k)=b(kk(k)); b(kk(k))=tb; end 执行[kk,a]=LUGauss(a)得到kk,a for i=k+1:n b(i)=b(i)-a(i,k)*b(k); end b(n)=b(n)/a(n,n); for i=n-1:1 t=0; for j=i+1:n t=t+a(i,j)*b(j); end b(i)=(b(i)- t)/a(i,i); end §2 LU分解法 形成PA=LU： §3 三对角矩阵方程的追赶法 三对角且主对角严格占优矩阵方程是一类来源丰富的问题。比如，微分方程数值解或样条插值等问题中的正规方程组。解这种问题必须考虑其矩阵稀疏的特征，减少算法的计算量。 三对角矩阵形如： §3 三对角矩阵方程的追赶法 T的LU分解具有形式：T=LU §3 三对角矩阵方程的追赶法 算法： §3 三对角矩阵方程的追赶法 乘除运算量：5n §4 对称正定矩阵方程的cholesky分解法 对称正定矩阵方程的来源比较丰富，比如线性回归、拟合等问题。解这类问题必须考虑其矩阵对称的特征，减少算法的计算量。 §4 对称正定矩阵方程的cholesky分解法 A必有cholesky分解： §4 对称正定矩阵方程的cholesky分解法 §4 对称正定矩阵方程的cholesky分解法 a的主对角线为D； a的上三角并把主对角线换为1即是L的转置 * School of mathematics physics * * * * * School of mathematics physics 第一章 求解线性代数方程组的直接方法 由线性代数的理论： 很多实际问题最终要化为线性代数方程组的求解！ 实现过程：第一步，消元 进行到第k步时必有 §1 Gauss消去法 §1 Gauss消去法 a(k,k)作为主元，第k行依次乘a(i,k)/a(k,k)加到第i行,i=k+1:n。总共n-1步完成。 §1 Gauss消去法 例1：用顺序Gauss消去法在假想的五位十进制计算机计算： 解： 回代解： 当a(k,k)=0，则顺序Gauss消去法无法进行，或当其绝对值相对太小可能会出现大的计算误差。选主元法可避免这种情况。下面介绍常用的按列选主元的Gauss法。 §1 Gauss消去法 列主元Gauss法 §1 Gauss消去法 第一章 求解线性代数方程组的直接方法 由线性代数的理论： 很多实际问题最终要化为线性代数方程组的求解！ 运算量 (只考虑乘除运算）： 第k步=n-k次除法+n-k次乘法+（n-k)*(n-k)次乘法; 总的乘除运算量= §1 Gauss消去法 例2：用列主元Gauss消去法在假想的五位十进制计算机计算： 解： 回代解： §1 Gauss消去法 第二步：回代求解 §1 Gauss消去法 §2 LU分解法 为什么要进行A的LU分解？ 矩阵分解：将矩阵A转换为两个以上简单矩阵的乘积。 LU分解：PA=LU,其中P为交换矩阵，L为单位下三角 矩阵，U为山三角矩阵。 §2 LU分解法 显然，对于线性方程组Ax=b，如果需要多次求解不同的非齐次项b，此时LU分解的效率将大大超过高斯消去法。 MATLAB命令： [l,u,p]=lu(A) §2 LU分解法 LU分解的算法: 记P(i,j)为单位矩阵i行于j行交换后的矩阵： §2 LU分解法 记 称之为Gauss变换 §2 LU分解法 列主元消去法过程可表示为： §2 LU分解法 §2 LU分解法 §2 LU分解法 由 得： §2 LU分解法 §2 LU分解法 综合上述，将列主元高斯消去法稍加改造即是LU分解算法。 §2 LU分解法 1、LU分解运算量和高斯消去法一样。 2、输出向量kk确定了P 3、输出向量a确定了L和U §2 LU分解法