一類按行稀疏存儲結(jié)構(gòu)的稀疏線性代數(shù)方程組的快速求解

1、一類按行稀疏存儲結(jié)構(gòu)的稀疏線性代數(shù)方程組的快速求解 目錄摘要.1abstract.21 引言和預(yù)備知識.31.1 引言.31.2 稀疏線性代數(shù)方程組的定義.41.3 稀疏存儲的概念.41.4 行稀疏存儲格式.42 稀疏線性代數(shù)方程組的共軛梯度（cg）法.62.1 共軛梯度法原理.6    2.2  算法描述.63 稀疏線性代數(shù)方程組的預(yù)條件共軛梯度(pcg)法.93.1預(yù)條件共軛梯度法的算法簡介.93.2 共軛梯度法的幾個重要問題.12  3.2.1 等價問題123.2.2 最速下降法12    3.2.3 共軛梯

2、度法143.3 小結(jié).174 例題分析.185 總結(jié)20參考文獻(xiàn).21致謝22附錄.23摘要本畢業(yè)論文主要包含兩部分內(nèi)容。第1部分針對1類稀疏線性代數(shù)方程組，利用目前國際上使用比較頻繁的處理稀疏矩陣的按行稀疏存儲結(jié)構(gòu)，設(shè)計了求解稀疏線性代數(shù)方程組的共軛梯度（cg）法，并分析計算復(fù)雜度。第2部分為這類線性代數(shù)方程組設(shè)計了1種基于不完全lu分解的預(yù)條件共軛梯度（pcg）法，并給出了計算實例，驗證程序設(shè)計的正確性。在本次設(shè)計最后還附上了詳細(xì)的程序代碼。關(guān)鍵詞 稀疏存儲結(jié)構(gòu); 不完全lu分解; 共軛梯度法(cg); 預(yù)條件共軛梯度法（pcg）; 行存儲 abstractthis thesis main

3、ly contains two parts. one points at a sequence of one sparse linear algebra system of equation ,utilizing frequent treatment sparse matrix data structure at present that is according to the competent store structure, design the law of conjugation gradient method (cg) which solves the equation group

4、 of the sparse linear algebra of asking analyses the complexity of calculating. the other designs the law of the preconditioned conjugate gradient method (pcg) that is based upon the incomplete analysis of lu for this kind of linear algebraic equation, testing the correctness of this procedure desig

5、n.  keywords   store the structure sparsely; incomplete analysis of lu; conjugation gradient method (cg); preconditioned conjugate gradient method (pcg);  storage by row1 引言和預(yù)備知識1.1 引言自從計算機(jī)出現(xiàn)以來，人們的生活越來越依賴于計算機(jī)。計算機(jī)擁有人類無法比擬的計算速度，比如在氣象預(yù)報上，沒有計算機(jī)的幫助是幾乎不可能做到及時準(zhǔn)確的預(yù)報氣象信息。但是計算機(jī)并非擁有類似人類的思維，

6、它所能做的只是按照預(yù)先設(shè)置好的方法計算。計算機(jī)的計算速度受硬件限制，但其所用的計算方法卻是人設(shè)計的。目前電子計算機(jī)運算的速度已經(jīng)接近極限，而計算機(jī)的計算效率除了計算速度以外還受計算方法的制約，好的計算方法可以快速而有效的計算出需要的結(jié)果來，從某種意義上來說。設(shè)計1個好的計算方法相當(dāng)于變相的提高了計算機(jī)的計算速度，效率也得到了相應(yīng)的提高。所以目前尋找好的計算方法已經(jīng)為越來越多的人所重視。計算機(jī)需要計算的大部分都是方程組，本文只討論線性代數(shù)方程組。而解方程組主要有直接法和迭代法2種， 到目前為止，直接法由于其很好的健壯性和可估計性而得到廣泛應(yīng)用，在很多情況下往往優(yōu)于迭代法。所謂直接法，它是1類精確方法，即若不考慮計算過程中的舍入誤差，通過有限步計算就可以獲得方程組的精確解。所謂迭代方法，就是構(gòu)造某種極限過程去逐步逼近方程組的解。20世紀(jì)60年代到70年代，大型線性代數(shù)方程組的求解取得了兩個重要的革命性的進(jìn)步。首先是認(rèn)識到如能利用系數(shù)矩陣的稀疏性設(shè)計1些特殊的直接法，效率將大大提高；其次是預(yù)處理技術(shù)的產(chǎn)生，將預(yù)處理技術(shù)與krylov子空間迭代法結(jié)合可以給出許多高效的1般化的程序。近年來，產(chǎn)生了各種好的迭代法，如適用于系數(shù)矩陣對稱正定情形的共軛梯度法（cg法），用來解非對稱正定問題的gmres方法，它們都是基于krylov子空間得到的迭代法，將預(yù)處理技術(shù)與上述方法結(jié)合又