【正文】 1. 2 1 , 2 , ... , / 1 , 2 , ..., .1 1kkik k k ikij ik k j ijIF or k nI f a t he n st opF or i k k na a af or j k k na a a a??? ? ??? ? ???消 去輸 出 錯 誤 信 息.2 .3 i ik k ia? ? ??? N1次 Nk次 Nk次 N1次 Nk次 .[ ] 2. 1 / 2. 2 1 , 2 , .. ., 1 2. 2. 1 2. 2. 2 1 , 2 , .. ., 2. 2. 3 /n nn nkk j jk k kIIaxf or k n nSFo r j k k nS a x SS a x?????? ? ???回 代第 2章 線性代數(shù)方程組 Gauss消去法 時間復雜度分析 1n分 為 步 1 1 1 , , ...,nnx x x n求 需 做 次 浮 點 運 算 求 需 做 2 次 浮 點 運 算 求 需 次浮 點 運 算 因 此 所 需 浮 點 運 算 次 數(shù) :3 212 33nnN N N n? ? ? ? ?因 此 , 3 ( )on即 , 運 算 量 為111( ) ( 2 )nkN n k n k??? ? ? ??,k n k第 步 變 換 行:求 倍 數(shù) , 1 nk?再 從 個 元 素 中 減 去k第 行 對 應(yīng) 列 的 倍 數(shù),因 此 所 需 浮 點 運 算 次 數(shù) :32 53 2 6n n n? ? ?2( 1 )1 2 .. .2nnNn ?? ? ? ? ?第 2章 線性代數(shù)方程組 Gauss消去法 空間復雜度分析 )(,)1( 22 nonA 則空間復雜度為占用空間為系數(shù)矩陣)(,)2( nonb 則空間復雜度為占用空間為常量)(,)3( nonx 則空間復雜度為占用空間為變量用額外存儲空間消去過程中認為沒有使)4()(, 2no度為消去法的總的空間復雜因此第 2章 線性代數(shù)方程組 Gauss消去法 主元 Gauss消去法可以順利執(zhí)行的條件 ( 1) 0kkka ? ?若在 Gauss消去過程中出現(xiàn)以下兩種情況 ( 1 )( 1 ) 0 kkka ? ?則 Gauss消去過程中會出現(xiàn)問題 ( 2) 1 , ..., k k ika a i k n? ? ? ?( 1 )kkkak?這 里 , 將 稱 為 第 步 的 主 元第 2章 線性代數(shù)方程組 Gauss消去法 主元 第 1種情況下 (1)若 A非奇，則可以通過交換方程組中各方程的行序 ,可以繼續(xù)執(zhí)行消去過程 (2)若 A奇異，則不能繼續(xù)執(zhí)行消去過程 231 2 31 2 3 5 22140xxx x xx x x???? ? ? ??? ? ? ??1 2 3231 2 321 5 240x x xxxx x x? ? ??? ???? ? ? ??交 換 第 1 行 和 第 2 行 ,0 :)1( ??kkka， 在消去過程中有當系數(shù)矩陣非奇時性質(zhì)第 2章 線性代數(shù)方程組 Gauss消去法 主元 第 2種情況下 121( 1 0 , 5 , 1 0 , 1 0 )22xFx?? ?? ???? ???? ????????51 0 2例 : 在 浮 點 數(shù) 系 下 , 求 解 3 真實解為 按 Gauss消去法為 * 0 .2 5 0 0 0 1 8 7 50 .4 9 9 9 9 8 7 4 9x??? ????6214 1 1 0 . 2 0 0 0 0 * 1 01 1 10 . 1 0 0 0 0 * 1 0 0 . 2 0 0 0 0 * 1 0 0 . 1 0 0 0 0 * 1 00 . 2 0 0 0 0 * 1 0 0 . 3 0 0 0 0 * 1 0 0 . 2 0 0 0 0 * 1 0l???? ??????????4 1 1660 . 1 0 0 0 0 * 1 0 0 . 2 0 0 0 0 * 1 0 0 . 1 0 0 0 0 * 1 00 . 4 0 0 0 0 * 1 0 0 . 2 0 0 0 0 * 1 0???? ?000 .0 0 0 0 0 * 1 0 0 .5 0 0 0 0 * 1 0 Tx ?第 2章 線性代數(shù)方程組 Gauss消去法 主元 原因 則 jj??? ? ??? jj??? ? ???ij ij ik k jl? ? ???()ij ik k jl? ? ?? ? ?ij ik k j ikll? ? ?? ? ?ij ikl????ij ij ikl? ? ???同理 倍誤差將會被放大在消去的過程中 ikl,若有誤差 第 2章 線性代數(shù)方程組 Gauss消去法 主元 列主元 Gauss消去法 若 A非奇則可以通過選主元的方式繼續(xù)執(zhí)行消去過程 ? ?消去法這種方法稱為列主元的消去過程然后繼續(xù)執(zhí)行并且交換相應(yīng)的行作為步選擇第消去法中在G a u s s，G a u s s，ankiakG a u s skkkik,...,1,m a x , )1(???第 2章 線性代數(shù)方程組 Gauss消去法 主元 kkkkkk a m a x 0 。1 , ..., )ijjiiiminj n n???????其 中 L D UTA L D M?因 此 稱 為 矩 陣 的 分 解第 2章 線性代數(shù)方程組 矩陣分解 其它的三角分解 A , TTL D M A L D M?當 的 各 階 順 序 主 子 式 不 為 零 時 存 在 唯 一 的 單 位 下 三角 矩 陣 對 角 陣 和 單 位 上 三 角 矩 陣 滿 足111111 ( ) 1[ ( ) ]:1[ ( ) ) ] ( 2 13) 1 , 2 , ..., , 1 , 2 , ...,kk k k k p p k ppkik ik ip p k ppkkik k i k p p ippkd l d ml l d mdm l d mdk n i k k n??????????????????? ???? ? ? ?????計 算 公 式3 3no fl o p??????計 算 量 : 次 ? ?3 on即 :推論 第 2章 線性代數(shù)方程組 矩陣分解 其它的三角分解 ,TTA A A L D MMLA L D L??? 特 別 地 , 當 為 對 稱 矩 陣 時 存 在 的 分 解 式則 有 因 此 有 分 解 式 3 6no flo p??????計 算 量 : ? ?3 on即 :第 2章 線性代數(shù)方程組 矩陣分解 對稱正定矩陣 , TALD A L D L?若 是 對 稱 正 定 矩 陣 則 存 在 單 位 下 三 角 矩 陣 和 對 角 元 全 部 為正 數(shù) 的 對 角 矩 陣 滿 足D由 于 的 對 角 元 全 部 為 正因 此C hole sk y稱 為 分 解Cho le sk yG 稱 為 三 角 陣12 G LD?其 中12 12( , , . . . , )nD d ia g d d d?,記TGG?TA LDL?1122 TLD D L? 12 G L D?記定理 第 2章 線性代數(shù)方程組 矩陣分解 對稱正定矩陣 , TA G A G G?任 何 對 稱 正 定 矩 陣 都 存 在 唯 一 的 下 三 角 陣 滿 足1121 2212n n nngggGg g g?????????計 算 公 式 1 kik ip k ppi k g g???? ?當 有1112 1 / 2kk11 g ( )iik ip k ppkkkk k k ppg g i kgg??????? ??? ? ?? ??? ???? ??????ikg因 此 , 3 6no fl o p??????計 算 量 : 次n還 有 次 的 開 平 方 運 算定理 第 2章 線性代數(shù)方程組 矩陣分解 帶狀矩陣的分解 當 矩 陣 中 大 量 元 素 為 零 元 , 非 零 元 只 占 很 小 比 例 的 矩 陣稱 為定 義稀 疏 矩 陣( ) , , 0.ijijA n n p qj i q i j pA q p???? ? ? ? ? 設(shè) 是 階 方 陣 對 小 于 的 正 整 數(shù) 和當 或 時 , 有則 稱 是 具 有 上 帶 寬 和 下 帶 寬 的 帶定狀 矩 陣義,n A L U A L U A qp L p U q? 設(shè) 階 矩 陣 有 分 解 如 果 是 上 下 帶 寬 分 別 為和 的 帶 狀 矩 陣 則 是 帶 寬 為 的 下 三 角 陣 是 帶 寬 為 的 上 三 角 陣. 以 帶 狀 矩 陣 為 系 數(shù) 矩 陣 的 方 程 組 稱 為 帶 狀 方 程 組定理 第 2章 線性代數(shù)方程組 矩陣分解 帶狀矩陣的分解 1ijm a x{ 1 , , }1m a x{ 1 , , }, , 1 , .. ., m in{ , } 1( ) , 1 , .. ., m in{ , }iij it tjt i p j qik i k i it tjt k p i qiil j i i n i ql l k i n i p? ? ?????? ? ??? ? ??? ? ? ? ????? ? ? ? ? ?????計 算 公 式 222211,26 11,26npq pq p pn p qTnpq qp q qn p q?? ? ? ???? ?? ? ? ? ???運 算 量 3,3pqno ??????當 和 都 不 大 時其 運 算 量 比 小 很 多第 2章 線性代數(shù)方程組 矩陣分解 帶狀矩陣的分解 112 2 23 3 3 1 1 11 nnnnnpqbca b ca b cTa b cab???????????????當 時 , 此 時 的 帶 狀 矩 陣 稱 為 三 對 角 陣 T L U?由 定 理 知 , 存 在 分 解 第 2章 線性代數(shù)方程組 矩陣分解 帶狀矩陣的分解 112 2 23111111nnnnrlrL l Url??????? ? ? ?? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ?? ? ? ?其 中 1 1 1 111, ,