數(shù)值分析Gauss消去法課件.ppt

1、,解線性方程組的直接法 /* Direct Method for Solving Linear Systems */,求解,1 高斯消元法 /* Gaussian Elimination */, 高斯消去法 ：,消元,記,Step k：設(shè) ，計(jì)算因子 且計(jì)算,共進(jìn)行 ？ 步,n 1,Gauss消去法,消元過(guò)程（1）,消元過(guò)程（1）,消元過(guò)程（1）,消元過(guò)程（1）,消元過(guò)程（2）,消元過(guò)程（2）,消元過(guò)程（2）,消元過(guò)程（3）,消元過(guò)程（4）,回代過(guò)程（1）,回代過(guò)程（2）,回代過(guò)程（3）,若A的所有順序主子式 /* determinant of leading principal submat

2、rices */ 均不為0，則高斯消元無(wú)需換行即可進(jìn)行到底，得到唯一解。,回代,No unique solution exists.,What if we cant find such k ?,No unique solution exists.,定理,注：事實(shí)上，只要 A 非奇異，即 A1 存在，則可通過(guò)逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。, 運(yùn)算量 /* Amount of Computation */,由于計(jì)算機(jī)中乘除 /* multiplications / divisions */ 運(yùn)算的時(shí)間遠(yuǎn)遠(yuǎn)超過(guò)加減 /* additions / subtractions *

3、/ 運(yùn)算的時(shí)間，故估計(jì)某種算法的運(yùn)算量時(shí)，往往只估計(jì)乘除的次數(shù)，而且通常以乘除次數(shù)的最高次冪為運(yùn)算量的數(shù)量級(jí)。, Gaussian Elimination:,(n k) 次,(n k)2 次,(n k) 次,消元乘除次數(shù)：,1 次,(n i +1) 次,回代乘除次數(shù)：,Gaussian Elimination 的總乘除次數(shù)為 ，運(yùn)算量為 級(jí)。,計(jì)算量,消元過(guò)程 回代過(guò)程 Gauss消去法的計(jì)算量為 數(shù)量級(jí), 列主元Guass消去法,例：?jiǎn)尉冉夥匠探M,用Gaussian Elimination計(jì)算：,8個(gè),小主元 /* Small pivot element */ 可能導(dǎo)致計(jì)算失敗。, 列主元消去法 /* Partial Pivoting