应用数值分析

线性代数方程组数值解法一一直接法一、n阶线性代数方程组q=baa—a「x]b11121n11aa—axb21222n2=2..........•aa—axbn1n2nnnn二、上（下）方程组与回代（前推）过程1、上三角方程组aa1112a22a「x]baa1112a22a「x]b1n11axb2n2=2......axbnnnn2、回代过程=b/a厂nnn=b/a厂nnnn=b<i-Xaxj=i+1jj>\xn1x.Iii,(i=n-1,•••2,1)3、下三角方程组「a「x]b1111aaxb21222=2..........••aa—axbn1n2nnnn4、前推过程11i-1]Eaxijjj=1/aii,(i=1,2,•••n)三、顺序Gauss消去法1、消元过程(1)n阶方程组经k-1次消元后，得到的新的系数矩阵A(k)具有如下形式：a⑴11a(1)…12a(2)•••22.a(1)1na(2)2nA(k)=.•a(k)・••kk..•.a(k)kn.a(k)・••nka(k)nn(2)在第k次，计算乘数m=a(k)..•''a(k),(i=k+1,n)，则a(k+1)ikik'kk元素的计算公式为：a(k+1)=a(k)-ma(k),(i,j=k+1,•••n)1ijijikkj[b(k+1)=b(k)一m^b(k),(i=k+1,…n)(3)完成n-1次消元后：a⑴11a⑴12a(2)22——•・.a(1)1na2?.「X]1X2.—=b⑴1b22)2.a(n)Xb(n)—nnnn2、回代过程Xn1Xk=b(n)■■■a(n)♦"""n)=b(k)一£a(k)xIk广k+ikJa*),(k=n-1,•••2,1)3、计算量估计(1)第k次消兀需要进行(n-k)(n-k+1)次乘法和(n-k)次除法:(2)£(n-k)+£1(n-k)(n-k+1)=+"5〃32k=1k=1回代过程乘除法次数：(3)£1(n-k)+n二牛+%22k=1乘数法总次数:MD(4)加减法总次数:ASn3n25n3264、要求：系数矩阵A的所有顺序主子式^k。0(k=1,2,n-1,n)四、列主元Gauss消去法1、对于非奇异矩阵A，在第一步消元时，即使A的第一个元素为零，但是A的第一列元素中至少有一个不为零，把这个不为零的元素所在的行与第一行交换位置，即可进行消元。也就说，只要人是非奇异的，必要时加上换行步骤，Gauss消去过程总是可以进行下去的。2、3、4、要求：系数矩阵人非奇异主元素：消去过程中的元素a/）（k=1,2,...n-1）和回代过程中的2、3、4、要求：系数矩阵人非奇异列主元素法：在消元过程的每一步之前，不管主元素是否为零，均从该元素及其所在列的下方元素中选出绝对值最大的元素，然后将该行与主元素所在行进行交换，再开始消元计算。新的主元素a（k）满足:ikk五、直接三角法1、矩阵A的三角分解（LU分解）：（1）Dooliter分解：设A为n阶非奇异矩阵，如果人的顺序主子式A.。0（i=1,2,n-1），则A可分解为一个单位下三角阵L和一个上三角阵U的乘积，且这种分解是唯一的（U的第一行与A的第一行是相同的）。aa,.・a■1uu.u11121n11121naa,.・al1u.u21222n=21222n..................•••••aa—all.1uLn1n2nnn1n2—11—nn（2）Crout分解：设A为n阶非奇异矩阵，如果A的顺序主子式A.。0（i=1,2,…〃-1），则A可分解为一个下三角阵L和一个单位上三角阵U~的乘积，且这种分解是唯一的。（3）LDU分解：设A为n阶非奇异矩阵，如果A的顺序主子式A,。0（i=1,2,...n-1），则A可分解为一个单位下三角阵L、一个对角矩阵D和一个单位上三角阵u的乘积，且这种分解是唯一的。2、解法步骤：（1）令已知A=LU，通过人的元素直接计算出L和U的元素；（2）由已知的L和D解出Ly=b（下三角方程组，前推过程）中的y；（3）由已知的U和y解出U==y（上三角方程组，回代过程）中的x。3、要求：系数矩阵A非奇异，顺序主子式△上。0（k=1,2,n-1）六、追赶法1、三对角方程组：系数矩阵除了对角线的“三斜行”以外的元素均为零。2、采用Doolitter分解：把三对角方程组的系数矩阵A分解为A=LU，其中L为单位下三角矩阵，两斜行，主对角元素为1，其下方的斜行元素待定；U为上三角矩阵，两斜行，主对角元素待定，其上方斜行元素与A的对应的斜行元素相同。bcr1〕uc1111abci1uc222222・..----.••=....・・・・・・・abcl[ucn-1n-1n-1n-1n-1n-1abl1unnnn3、解三对角方程组追赶法（Thomas算法）步骤:（1）利用矩阵乘法规则求出L和U:u=bl=a/u,u=b一lc(i=2,3,•••n)ii'i-1iiii-1求解Ax=LUx=Ly=d，得:y1=d1y=d-ly(i=2,3,n)iiii-1求解Ux=y，得：x=y；ux=(y.-cx)/u(i=n-1,…2,1)(4)要求：三对角矩阵AeRnxn非奇异，顺序主子式A•。0(i=1,2•••n-1)4、(1)严格对角占优矩阵：矩阵A的每个对角元素的绝对值都比所在行的非对角元素的绝对值的和要大，即aiiaij+zaiiaijj=i+1对角占优的三对角矩阵无零元素时能实现追赶法计算。（充分非必要）（2）弱对角占优矩阵:aii+zaiij=i+1

至少有一个不等式取等号成立。七、平方根法1、设系数矩阵AeRnxn对称正定，则存在一个实的下三角矩阵L,使得

A=LLT当L的元素只取正时，此分解是唯一的。a11a21:a21a22..•,.・,.・..•an1an2.—r11112.1122..•1.r111121122——..•111n1:aa—a11—11L1n2nnnn1n2nn1—nn2、解三对角方程组平方根法（Cholesky算法）步骤:（1）由矩阵乘法规则求出L1=(Q-£12)2Vjjjjjk1=(a-£11)/l(i=j+1,-n)ijijikj^!jjk=1（2）由Ly=力，求出y要求矩A序0正=阵2,•••n-主定）i（3）由Ltx=y，求出x系A要求矩A序0正=阵2,•••n-主定）i再把a（k）所在这一列的除a（k）的其它元素都消为0，并约化kkkka以）=1。2、求逆矩阵的计算机算法：为求n阶可逆矩阵A的逆矩阵A-1，作nx2n阶矩阵lA:I］（其中I为n阶单位矩阵），作初等行变换，当lA:I］的左一半化为I时，右一半就是A-1。3、计算量：（1）乘数法总次数:（2（2）加减法总次数:AS九、改进的平方根算法1、设系数矩阵AGRnxn对称且顺序主子式△。0（i=1,2...n），则存在一个单位下三角矩阵£和对角矩阵D,使得A=LDLt且此分解是唯一的。2、改进平方根算法步骤：（1）将A直接分解为A=LDLt，根据矩阵乘法规则，求出L和D（2）由Ly=b，求出y（3）由Ltx=D-iy，求出x3、要求：系数矩阵AgRnxn对称且顺序主子式△丰0（i=1,2•••n）十、直接法误差分析1、扰动误差分析：对于方程组Ax=b，（AgRnxn非奇异，bgRn且b。0），设A有误差8A，b有误差8b，因此引起解x有误差8x，即：—―k（A+8A）（x+8x）=b+8b（1）A与b分别有扰动8A和8b时：沮〈上虬（四+Fli-IA』|网IIaII（2）A精确（8A=0），b有扰动8b时：

b精确(8b=0),A有扰动8a时:IN当IA-1|18A||很小时，0<〜〜0<〜〜2、条件数:（1）设AGRnXn为非奇异阵，称o(At)o(At)D=dA-1AH，(d=1,2或8)为矩阵A的条件数。（2）如果矩阵A的条件数cond（A）相对大，就称A是坏条件的或是病态矩阵，对应的方程组Ax=b为病态方程组；否则