目錄
摘要………………………………………………………………………………………………...1
Abstract……………………………………………………………………………….…………..2
1 引言和預備知識………………………………………………………………………..3
1.1 引言……………………………………………………………………………………….3
1.2 稀疏線性代數方程組的定義…………………………………………………………….4
1.3 稀疏儲存的概念………………………………………………………………………….4
1.4 行稀疏儲存格式……………………………………………………………………….…4
2 稀疏線性代數方程組的共軛梯度（CG）法…………………………………………..6
2.1 共軛梯度法原理……………………………………………………………………...…..6
2.2 演算法描述…………………………………………………………………………….…..6
3 稀疏線性代數方程組的預條件共軛梯度(PCG)法…………………………………...9
3.1預條件共軛梯度法的演算法簡介………………………………………………………….9
3.2 共軛梯度法的幾個重要問題…………………………………………..………………12
3.2.1 等價問題…………………………………………………………………………12
3.2.2 最速下降法………………………………………………………………………12
3.2.3 共軛梯度法………………………………………………………………………14
3.3 小結………………………………………………………………………………..17
4 例題分析………………………………………………………………………………..18
5 總結……………………………………………………………………………………………20
參考文獻………………………………………………………………………………………...21
致謝………………………………………………………………………………………………22
附錄……………………………………………………………………………………………....23
摘要
本畢業論文主要包含兩部分內容。第1部分針對1類稀疏線性代數方程組，利用目前國際上使用比較頻繁的處理稀疏矩陣的按行稀疏儲存結構，設計了求解稀疏線性代數方程組的共軛梯度（CG）法，並分析計算複雜度。第2部分為這類線性代數方程組設計了1種基於不完全LU分解的預條件共軛梯度（PCG）法，並給出了計算例項，驗證程式設計的正確性。在本次設計最後還附上了詳細的程式程式碼。
關鍵詞 稀疏儲存結構; 不完全LU分解; 共軛梯度法(CG); 預條件共軛梯度法（PCG）; 行儲存
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 引言和預備知識
1.1 引言
自從計算機出現以來，人們的生活越來越依賴於計算機。計算機擁有人類無法比擬的計算速度，比如在氣象預報上，沒有計算機的幫助是幾乎不可能做到及時準確的預報氣象資訊。但是計算機並非擁有類似人類的思維，它所能做的只是按照預先設定好的.方法計算。計算機的計算速度受硬體限制，但其所用的計算方法卻是人設計的。目前電子計算機運算的速度已經接近極限，而計算機的計算效率除了計算速度以外還受計算方法的制約，好的計算方法可以快速而有效的計算出需要的結果來，從某種意義上來說。設計1個好的計算方法相當於變相的提高了計算機的計算速度，效率也得到了相應的提高。所以目前尋找好的計算方法已經為越來越多的人所重視。
計算機需要計算的大部分都是方程組，本文只討論線性代數方程組。而解方程組主要有直接法和迭代法2種， 到目前為止，直接法由於其很好的健壯性和可估計性而得到廣泛應用，在很多情況下往往優於迭代法。所謂直接法，它是1類精確方法，即若不考慮計算過程中的舍入誤差，通過有限步計算就可以獲得方程組的精確解。所謂迭代方法，就是構造某種極限過程去逐步逼近方程組的解。20世紀60年代到70年代，大型線性代數方程組的求解取得了兩個重要的革命性的進步。首先是認識到如能利用係數矩陣的稀疏性設計1些特殊的直接法，效率將大大提高；其次是預處理技術的產生，將預處理技術與Krylov子空間迭代法結合可以給出許多高效的1般化的程式。近年來，產生了各種好的迭代法，如適用於係數矩陣對稱正定情形的共軛梯度法（CG法），用來解非對稱正定問題的GMRES方法，它們都是基於Krylov子空間得到的迭代法，將預處理技術與上述方法結合又產生了預條件共軛梯度法（PCG方法）及預條件GMRES方法，這些方法的收斂速度較未進行預處理時提高了很多。
近代代數裡幾乎到處都能看到線性代數的身影，而許多數學物理問題的數學模型最終歸結為求解如下線性代數方程組的解的問題：