线性方程组的直接解法 A 线性方程组的直接 解法 主讲:王开荣 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 线性方程组的直接 解法 主讲：王开荣 11 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(线性方程组的直接解法 第二章线性方程组的直接解法 §1引 很多工程问题的计算最终都归结为解线性方程组.虽 然有些数学模型中不直接表现为解线性方程组但其数 值解法中将问题“离散化”或“线性化”将成为线性方程组 线性方程组的求解是数值分析课程中最基本的、最重 要的内容之 82 Gauss消去法 Gaus消元法的基本思想 Gauss消去法的基本思想是对方程组所对应的增广 矩阵进行一系列的初等行变换,将其转化为上三角矩 阵,通过回代求得线性方程组的解 2 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 22 第二章 线性方程组的直接解法 §1 引 言 很多工程问题的计算最终都归结为解线性方程组. 虽 然有些数学模型中不直接表现为解线性方程组,但其数 值解法中将问题“离散化”或“线性化”将成为线性方程组 . 线性方程组的求解是数值分析课程中最基本的、最重 要的内容之一. 一、Gauss消元法的基本思想 §2 Gauss消去法 Gauss消去法的基本思想是对方程组所对应的增广 矩阵进行一系列的初等行变换, 将其转化为上三角矩 阵, 通过回代求得线性方程组的解. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的直接解法 二、 Gauss消元法公式 (k) =k+1,…,n.(乘数因子) (k) j=k+1,k+2,…,n (k+1) k) i=k+1,k+2,……,n Gauss消去法的条件 定理 Gauss消去法消元过程能进行到底的充要条件是 系数阵A的1到n-1阶顺序主子式不为零;Ax=b能用 Gauss消元法解的充要条件是A的各阶顺序主子式不 为零 3 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 33 二、 Gauss消元法公式 ( ) ( ) ( 1) ( ) ( ) ( 1) ( ) ( ) , 1, , , , 1, 2, , . , 1, 2, , . k ik ik k kk k k k ij ij ik kj k k k i i ik k a l i k n a a a l a i j k k n b b l b i k k n + + ì = = + ï ï ï í = - = + + ï = - = + + ï ï î L L L .（乘数因子) 三、 Gauss消去法的条件 定理 Gauss消去法消元过程能进行到底的充要条件是 系数阵A的1到n-1阶顺序主子式不为零；Ax=b能用 Gauss消元法解的充要条件是A的各阶顺序主子式不 为零. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的直接解法 §3 Gauss主元素法 列主元消元法 算法( Gaussi列主元素法) 1.选主元,对k=1,2,,n-1确定i使(k=maxa k: 若a1k=0则A为奇异矩阵,停机 2.若i=k,转3.否则换行 b,(≤j≤m) 3消元 a1,<a,-a,a 6.<6 k+1,k+2 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 44 §3 Gauss主元素法 一 、 列主元消元法 算法(Gauss列主元素法) max k i k ik k i n a a £ £ 1. 选主元, 对k=1,2,··· ,n-1确定i = k , 使 若aikk=0则A为奇异矩阵, 停机. , ,( ) k k kj i j k i a « a b « b k £ £j n 2. 若ik =k, 转3. 否则换行 ik ik kk a a a ¬ i = k + + 1, k n 2, , L , ij ij ik kj a ¬ - a a a i i ik k b ¬ - b a b 3.消元 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的直接解法 4若an=0,停机 5回代求解 ∑a b.< 丿=1+1 6输出(b1,b2…,bn) 二、 Gauss全主元消去法 在Gs消去法中,若每次选主元不局限在方框列 中,而在整个子矩阵 (k) kk (k) (k) PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 4.若ann =0, 停机． 1 , , 1, 2, , 3, 2,1 n i ij j n j i n i nn ii b a b b b b i n n a a = + - ¬ ¬ = - - å L 5.回代求解 6.输出(b1 ,b2 , ··· ,bn ) T 二、 Gauss全主元消去法 在Gauss消去法中, 若每次选主元不局限在方框列 中, 而在整个子矩阵 ú ú ú û ù ê ê ê ë é ( ) ( ) ( ) ( ) k nn k nk k kn k kk a a a a L M M L PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的直接解法 中选取便称为全主元Gas消去法,此时增加的步骤为 ①a|=maxq,确定i,若a1=0给出=0的信息 k 停止计算 ②作如下行交换和列交换 行交换:a)4>aW,b4b6,(≤j≤m) 列交换:ak)4a),(≤i≤n) 需要注意的是,在全主元的消去法中,由于进行了列 交换,x各分量的顺序已被打乱。因此必须在每次列交 换的同时,让机器存储列交换的信息,在回代得出解后再 将x的各分量换回到原来相应的位置处 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 中选取,便称为全主元Gauss消去法,此时增加的步骤为: ( ) ( ) , max k k k k i j ij k i j n a a £ £ = ( ) ( ) ( ) ( ) , , ( ) k k k k k k kj i j k i a « a b « b k £ £j n ( ) ( ) , ( ) k k k ik ij a « a k £ £i n 66 ②作如下行交换和列交换 行交换: 列交换: ① , 确定ik , jk ,若aikjk =0 ,给出|A|=0的信息 停止计算. 需要注意的是, 在全主元的消去法中, 由于进行了列 交换, x各分量的顺序已被打乱。因此必须在每次列交 换的同时,让机器存储列交换的信息,在回代得出解后再 将x的各分量换回到原来相应的位置处. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的直接解法 §4 Gauss-Jordan消去法 、 Gauss-Jordan消去法 Gauss消去法是消去对角线元素下方的元素,若同时 也消去对角线元素上方的元素,而且将对角线元素化为 1.就是Gaus- Jordan消去法 Gauss-Jordan消去法的消元过程比 Gauss消去法 复杂,但省去了回代过程,它的计算量约为m3/2,大于 Gauss消去法.也称为无回代的 Gauss消元法.应用中 Gauss- Jordan消去法常用来求逆矩阵. 二、求方阵的逆 Gauss-Jordan消去法解方程组并不比Gaus消去法 优越,但用于矩阵求逆是适宜的,实际上它是初等变换 方法求逆的一种规范化算法. PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 77 §4 Gauss-Jordan消去法 一、Gauss-Jordan消去法 Gauss消去法是消去对角线元素下方的元素, 若同时 也消去对角线元素上方的元素, 而且将对角线元素化为 1. 就是Gauss-Jordan消去法. Gauss-Jordan消去法的消元过程比Gauss消去法 复杂, 但省去了回代过程,它的计算量约为n 3 /2, 大于 Gauss消去法. 也称为无回代的Gauss消元法. 应用中 Gauss-Jordan消去法常用来求逆矩阵. Gauss-Jordan消去法解方程组并不比Gauss消去法 优越,但用于矩阵求逆是适宜的,实际上它是初等变换 方法求逆的一种规范化算法. 二、 求方阵的逆 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的直接解法 §5矩阵的LU分解 定理设n阶方阵A的各阶顺序主子式不等于零,则 A可以进行唯一的 Doolittle分解和 Crout分解 Doolittles分解 Doolittles分解可以用Gaus消去法完成,也可以用矩阵 乘法原理推出计算公式来完成,其结果是一致的.设 l:= 1.2 (2)ln1=an1u1,i=2,3,…,n k,k+1, r=l k-1 ak-∑llnk =k+1,k+2,…,n PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 88 §5 矩阵的LU分解 定理 设 n 阶方阵 A的各阶顺序主子式不等于零, 则 A可以进行唯一的Doolittle分解和Crout分解. 一、Doolittle分解 Doolittle分解可以用Gauss消去法完成, 也可以用矩阵 乘法原理推出计算公式来完成, 其结果是一致的. 设 (1) u1j =a1j , j=1, 2, ··· , n. (2) l i1 =ai1 /u11, i=2, 3, ··· , n. (3) 1 1 , , 1, , . k kj kj kr rj r u a l u j k k n - = = -å = + L 1 1 , 1, 2, , k ik ir rk r ik kk a l u l i k k n u - = - = = + + å (4) L PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的直接解法 b (5) b2-∑ly,k=2,3, kr“r k+1 X k=n-1..2.1 kk 、 Crout分解 (2)uy=a/l1n,j=2,3,…,n PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 99 (5) 1 1 1 1 , 2,3, , . k k k kr r r y b y b l y k n - = ì = ï í = - = ï î å L (6) 1 , 1, , 2 , 1. n n nn n k kr r r k k kk y x u y u x x k n u = + - ì = ï ïï í - ï ï = = ïî å L 二、Crout分解 (1) l i1 =ai1 , i=1, 2, ··· , n. (2) u1j =a1j /l11, j=2, 3, ··· , n. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
线性方程组的直接解法 (3)从k=a-∑ll,i=k,k+ ∑ (4)vg ,j=k+1,k+2,…,n y (5) ∑y VK k=2,3,…,n (6) ∑unx,k k+1 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
线性方程组的直接解法 1010 (3) 1 1 , , 1, , . k ik ik ir rk r l a l u i k k n - = = -å = + L 1 1 , 1, 2, , k kj kr rj r kj kk a l u u j k k n l - = - = = + + å (4) L 1 1 11 1 1 , 2,3, , . k k kr r r k kk b y l b l y y k n l - = ì = ï ïï í - ï ï = = ïî å L (5) 1 , 1, , 2,1. n n n k k kr r r k x y x y u x k n = + - ì = ï í = - = ï î å L (6) PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com