3.2.2 矩阵的doolittle分解[优教课堂].ppt
3.2.2 矩阵的doolittle分解,1,课堂教育,定理3.12,L是单位下三角矩阵,U一个上三角矩阵,Gauss消元法的消元过程实际上是对线性代数方程组进行一系列初等行变换的过程。由线性代数知识知,线性代数方程组的初等变换相当于对其增广矩阵实行初等行变换,也即相当于增广矩阵左边乘以一个初等矩阵。,2,课堂教育,3,课堂教育,也可以直接用比较法导出矩阵A的LU分解的计算公式。上式可记为,比较第1行,比较第r行,4,课堂教育,同样,由,比较第r列,5,课堂教育,综合以上分析,有,因此可以推导出,U的第一行,L的第一列,-(1),-(2),6,课堂教育,思考,U的第r行,L的第r列,-(3),-(4),称上述(1) (4)式所表示的分解过程为矩阵A的Doolittle分解,7,课堂教育,function l,u=lu_Doolittle1(A)% 求可逆矩阵的LU分解% A为可逆矩阵,l为单位下三角矩阵,u为上三角矩阵n=length(A);u=zeros(n);l=eye(n);u(1,:)=A(1,:);l(2:n,1)=A(2:n,1)/u(1,1);for k=2:n for j=k:n u(k,j)=A(k,j)-l(k,1:k-1)*u(1:k-1,j); end u(k,k:n)=A(k,k:n)-l(k,1:k-1)*u(1:k-1,k:n); for i=k+1:n l(i,k)=(A(i,k)-l(i,1:k-1)*u(1:k-1,k)/u(k,k); end l(k+1:n,k)=(A(k+1:n,k)-l(k+1:n,1:k-1)*u(1:k-1,k)/u(k,k);end,8,课堂教育,对于线性方程组,系数矩阵非奇异,经过Doolittle分解后,线性方程组可化为下面两个三角形方程组,9,课堂教育,10,课堂教育,上述解线性方程组的方法称为 直接三角分解法的 Doolittle分解,例3.2.1 用Doolittle分解求解方程组,解,下面再用Doolittle分解方法求解,11,课堂教育,12,课堂教育,Doolittle分解在计算机上实现是比较容易的,但如果按上述流程运算仍需要较大的存储空间:,13,课堂教育,因此可按下列方法存储数据:,14,课堂教育,直接三角分解的Doolittle分解可以用以下过程表示:,存储单元(位置),15,课堂教育,Doolittle分解的紧凑格式,16,课堂教育,Doolittle分解的结果与Gauss消元法所得结果完全一样,但却避免了中间过程。,17,课堂教育,定理3.2.3 设矩阵A非奇异,当且仅当矩阵A的所有顺序主子式全非零时,其Doolittle分解式存在,且分解是惟一的。,下面给出Doolittle分解存在惟一的一个充要条件,18,课堂教育,例3.2.2 用紧凑格式的Doolittle分解求解方程组,解,19,课堂教育,20,课堂教育,所以,21,课堂教育,例3.2.3 用Doolittle分解求解方程组,解,直接利用Doolittle分解的紧凑格式算得,22,课堂教育,23,课堂教育,列选主元Doolittle分解,在Doolittle分解(包括紧凑格式)中,会反复用到公式,仍有可能是小主元做除数,为此,也要考虑在算法中加入选取列主元,24,课堂教育,Crout 分解,L为下三角矩阵,U为单位上三角矩阵,25,课堂教育,三、 Cholesky分解与平方根法,对称正定矩阵的三角分解(Cholesky分解),26,课堂教育,27,课堂教育,因此,可以证明这种分解是唯一的,设存在另外的一个分解,则,单位下三角,单位下三角,上三角,上三角,所以:,28,课堂教育,又因为:,即,所以:,即,则:,令:,29,课堂教育,综合以上分析,则有,为了方便我们记:,定理3.2.3 (Cholesky分解),且该分解式唯一,这种关于对称正定矩阵的分解称为Cholesky分解,30,课堂教育,31,课堂教育,-(6),-(7),-(8),32,课堂教育,33,课堂教育,对称正定线性方程组的解法,线性方程组,-(10),-(11),因而线性方程组(10)可化为两个三角形方程组,-(12),-(13),34,课堂教育,例3.2.7,用平方根法解对称正定方程组,解,35,课堂教育,36,课堂教育,即,所以原方程组的解为,37,课堂教育,平方根法的数值稳定性,用平方根法求解对称正定方程组时不需选取主元,由,可知,因此,平方根法是数值稳定的,38,课堂教育,3.2.6 解三对角方程组的追赶法,39,课堂教育,如果矩阵A满足,40,课堂教育,以下先以gauss消元法导出三对角方程组的解法,41,课堂教育,设,经过n-1消元以后,42,课堂教育,再依次回代回去就可以求解了:,43,课堂教育,