一類按行稀疏存儲結構的稀疏線性代數方程組的快速求解

時間：2024-09-01 18:39:15 數學畢業論文

目錄
摘要………………………………………………………………………………………………...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方法，這些方法的收斂速度較未進行預處理時提高了很多。
近代代數里幾乎到處都能看到線性代數的身影，而許多數學物理問題的數學模型最終歸結為求解如下線性代數方程組的解的問題：

【一類按行稀疏存儲結構的稀疏線性代數方程組的快速求解】相關文章：

預測蛋白質二級結構的快速方法10-04

高動態突發擴頻信號的快速捕獲結構研究08-17

談快速公交對城市空間結構的優化作用10-07

當前求解三對角線性方程組兩類并行算法的特點07-19