計算方法課件1.ppt

1、第一章 解線性方程組的直接法,直接法: 經(jīng)過有限步運算后可求得方程組精確解的方法(不計舍入誤差!) 迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列去逼近精確解的方法。分為兩類： 逐次逼近法(一般有限步內(nèi)得不到精確解) 共軛斜量法（不考慮計算過程的舍入誤差，只用有限步就收斂于方程組的精確解）,解線性方程組的兩類方法, 運算量 （Amount of Computation）,用克萊姆（Cramer）法則求解n階線性方程組,每個行列式由n!項相加，而每項包含了n個因子相乘，乘法運算次數(shù)為(n-1)n !次.,僅考慮乘(除)法運算,計算解向量包括計算n+1個行列式和n次除法運算,乘(除)法運算次數(shù)

2、N=(n+1)(n-1)n!+n.,當(dāng)n=8時,N2,540,128；當(dāng)n=20時,N9.7*1020,“天河二號”每秒33.86千萬萬億次計算，計算時間約為2.8*104秒，約8個小時,1.1 解線性方程組的消去法 ( Direct Method for Solving Linear Systems),高斯消去法 (Gaussian Elimination),將增廣矩陣的第 i 行 - li1 第1行，得到：,消去過程：,第一步：設(shè) ，計算因子,第k步：設(shè) ，計算因子,將增廣矩陣的第 i 行 - lik 第k行，得到：,其中,定理：若A的所有順序主子式 均不為0，則高斯消去法能順序進(jìn)行消元，

3、得到唯一解。,回代過程：,共進(jìn)行 n 1步，得到,高斯消去法的運算量,第1個消去步， 計算li1(i=2,3，n)， 有n-1次除法運算. 使aij(1)變?yōu)?aij(2) 以及使bi(1)變?yōu)閎i(2)有n(n-1)次乘法運算.,第k個消去步，有n-k次除法運算、(n-k+1)(n-k)次 乘法運算.,乘法運算總次數(shù)為：,除法運算總次數(shù)為: (n-1)+1=n(n-1)/2,回代過程的計算,除法運算次數(shù)為n次. 乘法運算的總次數(shù)為 (n-1)+1=n(n-1)/2次,Gauss消去法 除法運算次數(shù)為:n(n-1)/2+n=n(n+1)/2， 乘法運算次數(shù)為: n(n-1)(n+1)/3+n(

4、n-1)/2=n(n-1)(2n+5)/6， 總乘除運算量為 n(n2+3n-1)/3,通常也說Gauss消去法的運算次數(shù)與n3同階，記為O(n3),例 用高斯消去法 求解方程組,解為,二、 選主元消去法,在高斯消去法消去過程中可能出現(xiàn) 的情況，這時 高斯消去法將無法進(jìn)行；即使主元素 但很小， 其作除數(shù) ，也會導(dǎo)致其它元素數(shù)量級的嚴(yán)重增長和舍入 誤差的擴(kuò)散,例：單精度解方程組,用Gauss消去法計算：,8個,小主元 /* Small pivot element */ 可能導(dǎo)致計算失敗。,列主元消去法,在第k 步消元前，在系數(shù)矩陣第k 列的對角線以下的元素中找出絕對值最大的元。,列主元Gauss

5、消去法保證了lik1 (i=k+1,k+2,，n).,為避免這種情況的發(fā)生, 可通過交換方程的次序， 選取絕對值大的元素作主元. 基于這種思想導(dǎo)出了 “選主元消去法”,全主元消去法,在第k步消去前， 在系數(shù)矩陣右下角的n-k+1階主子陣中，選絕對值最大的元素作為主元素。,(1) If p k then 交換第 k 行與第p行; If q k then 交換第 k 列與第 q 列;,(2) 消元,注：列交換改變了 xi 的順序，須記錄交換次序，解完后再換回來。,高斯約當(dāng)消去法,前面所述的消去法均要進(jìn)行兩個過程,即消元過程和回代過程。但對消元過程稍加改變可以把方程組化為對角形,此時求解就不要回代了。這種無回代過程的主元素消去法稱為 高斯約當(dāng)(Jordan)消去法。 特別是方程組(321)還可化為,(322),顯然等號右端即為方程組的解。 對于n階線性方程組(31),其增廣矩陣為,首先把主元素(按列選主元或全選主元)調(diào)換到主對角線上,并化為1,再將主元素所在列的其它元素消為0,則第一次消元