一類按行稀疏存儲(chǔ)結(jié)構(gòu)的稀疏線性代數(shù)方程組的快速求解
目錄
摘要………………………………………………………………………………………………...1
Abstract……………………………………………………………………………….…………..2
1 引言和預(yù)備知識(shí)………………………………………………………………………..3
1.1 引言……………………………………………………………………………………….3
1.2 稀疏線性代數(shù)方程組的定義…………………………………………………………….4
1.3 稀疏存儲(chǔ)的概念………………………………………………………………………….4
1.4 行稀疏存儲(chǔ)格式……………………………………………………………………….…4
2 稀疏線性代數(shù)方程組的共軛梯度（CG）法…………………………………………..6
2.1 共軛梯度法原理……………………………………………………………………...…..6
2.2 算法描述…………………………………………………………………………….…..6
3 稀疏線性代數(shù)方程組的預(yù)條件共軛梯度(PCG)法…………………………………...9
3.1預(yù)條件共軛梯度法的算法簡(jiǎn)介………………………………………………………….9
3.2 共軛梯度法的幾個(gè)重要問(wèn)題…………………………………………..………………12
3.2.1 等價(jià)問(wèn)題…………………………………………………………………………12
3.2.2 最速下降法………………………………………………………………………12
3.2.3 共軛梯度法………………………………………………………………………14
3.3 小結(jié)………………………………………………………………………………..17
4 例題分析………………………………………………………………………………..18
5 總結(jié)……………………………………………………………………………………………20
參考文獻(xiàn)………………………………………………………………………………………...21
致謝………………………………………………………………………………………………22
附錄……………………………………………………………………………………………....23
摘要
本畢業(yè)主要包含兩部分內(nèi)容。第1部分針對(duì)1類稀疏線性代數(shù)方程組，利用目前國(guó)際上使用比較頻繁的處理稀疏矩陣的按行稀疏存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)了求解稀疏線性代數(shù)方程組的共軛梯度（CG）法，并分析計(jì)算復(fù)雜度。第2部分為這類線性代數(shù)方程組設(shè)計(jì)了1種基于不完全LU分解的預(yù)條件共軛梯度（PCG）法，并給出了計(jì)算實(shí)例，驗(yàn)證程序設(shè)計(jì)的正確性。在本次設(shè)計(jì)最后還附上了詳細(xì)的程序代碼。
關(guān)鍵詞 稀疏存儲(chǔ)結(jié)構(gòu); 不完全LU分解; 共軛梯度法(CG); 預(yù)條件共軛梯度法（PCG）; 行存儲(chǔ)
Abstract
This thesis mainly 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 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 design.
keywords Store the structure sparsely; Incomplete analysis of LU; Conjugation gradient method (CG); Preconditioned conjugate gradient method (PCG); Storage by row
1 引言和預(yù)備知識(shí)
1.1 引言
自從計(jì)算機(jī)出現(xiàn)以來(lái)，人們的生活越來(lái)越依賴于計(jì)算機(jī)。計(jì)算機(jī)擁有人類無(wú)法比擬的計(jì)算速度，比如在氣象預(yù)報(bào)上，沒(méi)有計(jì)算機(jī)的幫助是幾乎不可能做到及時(shí)準(zhǔn)確的預(yù)報(bào)氣象信息。但是計(jì)算機(jī)并非擁有類似人類的思維，它所能做的只是按照預(yù)先設(shè)置好的方法計(jì)算。計(jì)算機(jī)的計(jì)算速度受硬件限制，但其所用的計(jì)算方法卻是人設(shè)計(jì)的。目前電子計(jì)算機(jī)運(yùn)算的速度已經(jīng)接近極限，而計(jì)算機(jī)的計(jì)算效率除了計(jì)算速度以外還受計(jì)算方法的制約，好的計(jì)算方法可以快速而有效的計(jì)算出需要的結(jié)果來(lái)，從某種意義上來(lái)說(shuō)。設(shè)計(jì)1個(gè)好的計(jì)算方法相當(dāng)于變相的提高了計(jì)算機(jī)的計(jì)算速度，效率也得到了相應(yīng)的提高。所以目前尋找好的計(jì)算方法已經(jīng)為越來(lái)越多的人所重視。
計(jì)算機(jī)需要計(jì)算的大部分都是方程組，本文只討論線性代數(shù)方程組。而解方程組主要有直接法和迭代法2種， 到目前為止，直接法由于其很好的健壯性和可估計(jì)性而得到廣泛應(yīng)用，在很多情況下往往優(yōu)于迭代法。所謂直接法，它是1類精確方法，即若不考慮計(jì)算過(guò)程中的舍入誤差，通過(guò)有限步計(jì)算就可以獲得方程組的精確解。所謂迭代方法，就是構(gòu)造某種極限過(guò)程去逐步逼近方程組的解。20世紀(jì)60年代到70年代，大型線性代數(shù)方程組的求解取得了兩個(gè)重要的革命性的進(jìn)步。首先是認(rèn)識(shí)到如能利用系數(shù)矩陣的稀疏性設(shè)計(jì)1些特殊的直接法，效率將大大提高；其次是預(yù)處理技術(shù)的產(chǎn)生，將預(yù)處理技術(shù)與Krylov子空間迭代法結(jié)合可以給出許多高效的1般化的程序。近年來(lái)，產(chǎn)生了各種好的迭代法，如適用于系數(shù)矩陣對(duì)稱正定情形的共軛梯度法（CG法），用來(lái)解非對(duì)稱正定問(wèn)題的GMRES方法，它們都是基于Krylov子空間得到的迭代法，將預(yù)處理技術(shù)與上述方法結(jié)合又產(chǎn)生了預(yù)條件共軛梯度法（PCG方法）及預(yù)條件GMRES方法，這些方法的收斂速度較未進(jìn)行預(yù)處理時(shí)提高了很多。
近代代數(shù)里幾乎到處都能看到線性代數(shù)的身影，而許多數(shù)學(xué)物理問(wèn)題的數(shù)學(xué)模型最終歸結(jié)為求解如下線性代數(shù)方程組的解的問(wèn)題：
【一類按行稀疏存儲(chǔ)結(jié)構(gòu)的稀疏線性代數(shù)方程組的快速求解】相關(guān)文章：
預(yù)測(cè)蛋白質(zhì)二級(jí)結(jié)構(gòu)的快速方法10-04
高動(dòng)態(tài)突發(fā)擴(kuò)頻信號(hào)的快速捕獲結(jié)構(gòu)研究08-17
談快速公交對(duì)城市空間結(jié)構(gòu)的優(yōu)化作用10-07
當(dāng)前求解三對(duì)角線性方程組兩類并行算法的特點(diǎn)07-19
試析現(xiàn)代網(wǎng)絡(luò)存儲(chǔ)技術(shù)08-05
智能網(wǎng)絡(luò)存儲(chǔ)方案２07-28
物體平衡問(wèn)題的求解方法08-02