《数值分析双语课件第4次课》由会员分享，可在线阅读，更多相关《数值分析双语课件第4次课（43页珍藏版）》请在金锄头文库上搜索。
1、5.3 Triangular Factorization,Linear system :,Diagonal, upper or lower triangular systems are easier to solve,Gaussian Elimination,Upper triangular system,Lower triangular system,They are easy to solve!,Upper/Lower triangular system,LU Factorization,Different forms of LU factorization,Doolittle form
2、Obtained by Gaussian elimination Crout form Cholesky form,Direct (Doolittle ) factorization,The first row of A,The first column of A,The first row of U,The first column of L,Lrk=0, k=r+1, n; Lrr=1,r-th row ofA,r-th row of U,Ukr=0, k=r+1, n;,r-th column of A,r-th column of A,LU factorization r=2, n -
3、Doolittle factorization,A,24,Example 1,Use LU factorization to solve the following line system,solution,1 2 3 4,1 1 1,2 6 12,3 7,6 24,6,U,L,Cholesky factorization,A symmetric and positive definite,If A=LU ,then,Hence (since , ),Obviously, if j i, then lij=0,Else ji,if k j, then ljk=0,Given Ax=b, whe
4、re A is symmetric and positive definite, what does Cholesky factorization to do with solution of Ax=b,Given Ax=b, where A is symmetric and positive definite, what does Cholesky factorization to do with solution of Ax=b,Example 2,solution,A is symmetric and positive definite,Use Cholesky factorizatio
5、n to solve the following line system,Tridiagonal matrix algorithm /Thomas algorithm,Tridiagonal matrix,Tridiagonal System,Example,Use Thomas algorithm to solve the following line system,solution,summary,Vector,matrix,Example,Common vector norms,设 为Rn中一向量序列，,为Rn中任一两种向量范数，若const. a,b, s.t.xRn,有,具有可传递性
6、,Properties of vector norms,Rn中任意两种向量范数 等价,ARnn,若有非负实值函数N(A)满足 A0, A0A=0; (正定性) cA=cA, cR; (齐次) A+BA+ B; (三角不等式) ABAB 则称N(A)是Rnn上的矩阵范数。,example,Frobenius norm,Matrix norm,Def 4 矩阵范数与向量范数相容,xRn,ARnn,若矩阵范数和向量范数满足 Ax Ax -相容性条件 则称矩阵范数与向量范数相容。,Def 5 矩阵的算子范数,xRn,ARnn,给定一种向量范数x p ，例如p=1,2,相应的定义一个矩阵的非负函数,满足
7、矩阵范数条件和相容性条件，称为A的算子范数。,Whats the relation between Ax and A, x ?,check,行范数, p=1,列范数, p=2,2范数, p=3,xRn,ARnn,Common Matrix norms,例,Def 6 矩阵的谱半径,谱半径的性质,1. 矩阵A的谱半径不超过它的任何一种算子范数，包括F-范数,Let i be any eigen-value of A, ui the corresponding eigen-vector,So is an eigen-value of AtA, ui the corresponding eigen-
8、vector,Th1,Suppose det(IB)=0, then,Contradict to,perturbation,perturbation,Its funny that such small perturbations in the coefficients lead to so big change in the solution!,Thats right! its due to the nature of A and Such a system is said to be ill-posed.,Error analysis,由实际问题建立起来的线性方程组Ax=b本身存在模型误差和
9、观测误差，或者是由计算得到的，存在舍入误差等。总之，A,b都会有一定扰动A ,b, 因此实际处理的是A+A或b+b ，我们需要分析A或b的扰动对解的影响。,x exact solution,x+x exact solution,当方程组的系数矩阵A和齐次项b受到扰动A ,b后，其解x会受到怎样的扰动？分三种情况讨论,1. b有扰动b, A无扰动(A=0),解的相对误差,齐次项b的相对误差,当b受到扰动b时，引起的解的相对误差不超过b的相对误差的AA-1倍,2. A有扰动A, b无扰动(b =0),解的相对误差,A的相对误差,设A-1 A1, A充分小,3. A有扰动A, b有扰动b,类似可得,
10、解的相对误差,A的相对误差,b的相对误差,Def 7 矩阵的条件数,A非奇异， ApA-1p =cond(A)p称为矩阵的条件数(p=1,2,),cond(A)p相对较大，称方程组是病态的；否则，若cond(A)p相对较小，称方程组是良态的。,常用的矩阵条件数,1. A A-1 =cond(A),条件数的性质,example,Hilbert matrix,How to verify whether a given linear system is ill posed?,Cond(A)p 1(不易计算) 系数矩阵A 的三角约化中出现小主元 |max(A)|/| min(A)|1 Det(A) 很小，或A的某些行近似线性相关 A的元素间数量级相差很大，且无一定规则。,对病态方程组可采取以下措施： 采用高精度运算，减轻病态影响，例如采用双倍字长运算。 用预处理方法改善A的条件数，即选择非奇异矩阵P,Q,s.t. PAQ(Q-1)x=Pb 与 Ax=b 等价，而 B=PAQ 的条件数比 A 改善，令y= Q-1x, f=Pb,则求出By=f的解y,原方程组的解为x=Qy. 一般选P,Q为对角阵或三角阵。 平衡方法，当A中元素数量级相差很大时，可采用行或列平衡法改善A的条件数。设A非奇异，计算,求Ax=b等价于求DAx=Db, s.t. DA的条件数得到改善。,
