直接法算法设计中矩阵分解技巧的应用VIP

直接法求解线性方程组,直接法的适用范围直接法算法设计中矩阵分解技巧的应用特殊线性方程的算法设计与分析直接法所得“精确解”的精度分析,1.直接法的适用范围,直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。直接法这个“直接”往往代表着解法思想简单，直接了当。它往往能求各种方程，是一种通吃的解法，像克莱姆法则、高斯(Gauss)消去法，它们很强大，但也有缺点。这个缺点往往是致命的，有些方程它能解，但人们往往不敢用它去解。,为什么呢？它们在计算高阶方程组计算量太大啦所以直接法比较适合解中低阶的矩阵对于大型矩阵我们往往采取其它方法。如迭代法,在实际应用中选择算法往往从三个方面考虑：(1)解的精度高；(2)计算量小；(3)所需计算机内存小。但这些条件相互间是矛盾而不能兼顾的，因此实际计算时应根据问题的特点和要求及所用计算机的性能来选择算法。一般说，系数矩阵为中、小型满矩阵，用直接法较好；当系数矩阵为大型、稀疏矩阵时，有效的解法是下节要讨论的迭代法。,2.直接法算法设计中矩阵分解技巧的应用,矩阵三角分解法矩阵三角分解法是高斯消去法解线性方程的变形解法,矩阵三角分解原理,应用高斯消去法解n阶线性方程组Ax=b,经过n步消元之后,得出一个等价的上三角型方程组A(n)x=b(n),对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。将非奇异阵A分解成一个下三角阵L和一个上三角阵U的乘积A=LU称为对矩阵A的三角分解，又称LU分解。,其中,方程组Ax=b的系数矩阵A经过顺序消元逐步化为上三角型A(n),相当于用一系列初等变换左乘A的结果。事实上，第1列消元将A(1)=A化为A(2)，若令：,则根据距阵左乘有L1A(1)=A(2),第2列消元将A(2)化为A(3)，若令：,经计算可知L2A(2)=A(3),依此类推,一般有LkA(k)=A(k+1),于是矩阵经过消元化为上三角阵的过程可表示为上述矩阵是一类初等矩阵,它们都是单位下三角阵，且其逆矩阵也是单位下三角阵,只需将改为,就得到。即,于是有,其中,L为由乘数构成的单位下三角阵，U为上三角阵，由此可见，在的条件下，高斯消去法实质上是将方程组的系数矩阵A分解为两个三角矩阵的乘积A=LU。这种把非奇异矩阵A分解成一个下三角矩阵L和一个上三角矩阵U的乘积称为矩阵的三角分解，又称LU分解。显然，如果,由行列式的性质知，方程组系数矩阵A的前n-1个顺序主子矩阵非奇异，即顺序主子式不等于零，即,其中,（A的主子阵）,反之,可用归纳法证明,如果A的顺序主子式,则,于是得到下述定理：,把A分解成一个单位上三角阵L和一个下三角阵U的乘积称为杜利特尔（Doolittle）分解。其中,若把A分解成一个下三角阵L和一个单位上三角阵U的乘积称为克洛特分解Crout）其中,用三角分解法解方程组,求解线性方程组Ax=b时,先对非奇异矩阵A进行LU分解使A=LU，那么方程组就化为LUx=b从而使问题转化为求解两个简单的的三角方程组Ly=b求解yUx=y求解x这就是求解线性方程组的三角分解法的基本思想。下面只介绍杜利特尔（Doolittle）分解法。设A=LU为,由矩阵乘法规则,由此可得U的第1行元素和L的第1列元素,再确定U的第k行元素与L的第k列元素,对于k=2,3,n计算：计算U的第k行元素,（j=k,k+1,n）,计算L的第k列元素,（i=k,k+1,n）,利用上述计算公式便可逐步求出U与L的各元素求解Ly=b,即计算:,求解Ux=y,即计算：,显然,当时,解Ax=b直接三角分解法计算才能完成。设A为非奇异矩阵,当时计算将中断或者当绝对值很小时，按分解公式计算可能引起舍入误差的积累，因此可采用与列主元消去法类似的方法，对矩阵进行行交换，则再实现矩阵的三角分解。用直接三角分解法解Ax=b大约需要次乘除法。,例3.8用三角分解法解方程组,求解Ly=b得y=2，2，1T求解Ux=y得x=-1，0，1T所以方程组的解为,特殊方程的算法设计与分析,1平方根法2改进平方根法,平方根法,1简介平方根法又叫Cholesky分解法，是求解对称正定线性方程组最常用的方法之一。我们知道，对于一般方阵，为了消除LU分解的局限性和误差的过分积累，而采用了选主元的方法。但对于对称正定矩阵而言，选主元却是完全不必要的。而平方根法就可以简便的解决这类问题。,平方根法的算法设计与分析,若线性方程组Ax=b的系数矩阵是对称正定的，我们可按如下的步骤求其解：1.求A的Cholesky分解：A=LLT；2.求解Ly=b得到y，3