預處理子空間迭代法的一些基本概念

1、CG算法的預處理技術:、 為什么要對A進行預處理：其收斂速度依賴于對稱正定陣A的特征值分布 特征值如何影響收斂性：特征值分布在較小的范闈內，從而加速CG的收斂性 特征值和特征向量的定義是什么？(見筆記本以及收藏的網頁)求解特征值和特征向量的方法:Davidson方法：Davidson方法是用矩陣(D- 0 I)-1( A - 0 I) 產生子空間，這里D是A的對角元所組成的對角矩陣。e是由Rayleigh-Ritz過程所得到 的A的近似特征值。什么是子空間法:Krylov子空間疊代法是用來求解形如Ax=b的方程,A是一個n*n的矩陣， 當n充分大時，直接計算變得非常困難，而Krylov方法則巧

2、妙地將其變?yōu)镵xi+l=Kxi+b-Axi 的迭代形式來求解。這里的K(來源于作者俄國人Nikolai Krylov姓氏的首字母)是一個構造出 來的接近于A的矩陣，而迭代形式的算法的妙處在于，它將復雜問題化簡為階段性的易于 計算的子步驟。如何取正定矩陣Mk為：Span是什么？：設e V ，稱它們的線性組合佇內氏為向量 xlt的生成子空間，也稱為由xlt.,xm張成的子空間。記為L (xL ,也可以記為Span (%i, 什么是Jacobi迭代法： 什么是G_S迭代法：請見PPT迭代法求解線性方程組 什么是SOR迭代法：什么是收斂速度:定義5 :片($) = -lnp()為迭代法的漸近收斂讖，簡

3、 稱收斂速度。什么是可約矩陣與不可約矩陣?:不可約矩陣(irreducible matrix)和可約矩陣(reducible matrix )兩個相對的概念。定義1：對于n階方陣A而言，如果存在一個排列陣P使得PAP為一個分塊上三角陣， 我們就稱矩陣A是可約的；否則稱矩陣A是不可約的。定義2：對于n階方陣A=(aij)而言，如果指標集1, 2，n)能夠被劃分成兩個不相交 的非空指標集J和K,使得對任意的jO和任意的kEK都有ajk=O,則稱矩陣A是可約 的；否則稱矩陣A是不可約的。n階方矩陣A是不可約的當旦僅當與矩陣A對應的有向圖是強連通的。什么是正交？：在三維向量空間中，兩個向量的內枳如果是

4、零，那么就說這兩個向量是正交 的。換句話說，兩個向量正交意味著它們是相互垂直的。若向量a與&正交，則記為a 3。 什么是正交矩陣？：如果：AA=E(E為單位矩陣，甘表示“矩陣A的轉置矩陣”。)或A A=E, 則n階實矩陣A稱為正交矩陣，若A為單位正交陣，則滿足以下條件：AT是正交矩陣(E為單位矩陣)A的各行是單位向量且兩兩正交A的各列是單位向量且兩兩正交(Ax,Ay)=(x,y)x,yER|A| =1或-1倒著寫的A和E都是什么意思??？：反著的E:謂詞邏輯存在量詞m x: P(x)意味著有至少一個 x使P(x)為真。n G N:n是偶數。倒著的A:任意的A邏輯合取陳述A A B為真，如果A與B

5、二者都為真;否則為假。n2 = n = 3當n是自然數的時候。與命題邏輯V邏輯析取陳述A V B為真，如果A或B (或二者)為真；如果二者都為假, 則陳述為假。n4 V nW2 =n = 3當n是自然數的時候。迭代法與直接法比較優(yōu)劣是什么？：對稱正定的定義是什么？：設M是n階方陣，如果對任何非零向量z,都有zMz 0,其中 z*表示z的轉置，就稱M正定矩陣。判定定理1：對稱陣A為正定的充分必要條件是：A的特征值全為正。判定定理2：對稱陣A為正定的充分必要條件是：A的各階順序主子式都為正。迭代法求解稀疏矩陣時是否有填充元問題？：CG法求解線性矩陣時有無誤差問題？：有。誤差可能導致收斂變慢甚至無法

6、求解。什么是Krylov子空間法？：設要求解線性代數方程組Ax=b ,取 Kta=Km(Ar) = Span(rq,.,*r),其中r = b-Ax,且x為初始解，從+電中尋找近似解使相應的殘向量與另某個子空間L正交，艮Prm = b-n則稱Km為Krylov子空間，且上述方法稱為Krylov子空間方法。GMRES方法的缺點是什么？：因為它實際上求式AZ=i的解等價在在Krylov子空間中極小化 殘余向量的|.|范數。但GMRES會有失去超線性收斂性、可能產生停滯、GMRES每迭代 一步都要進行Arnoldi過程中都要消耗大量的計算時間、隨著子空間維數的增大，引起存儲 空間過多的需求，每次迭代

7、正交化過程所需代價顯著增長等缺點。矩陣右上角有個H,這是什么矩陣呢？(有個T是轉置，有個H是什么)：一般來講AAT表 示轉置，AH表示轉置共軸，對實矩陣而言是一回事，對復矩陣而言轉置共軸比單純的轉置 更常用一些，比如酉變換、Hermite型等。什么是正交投影法和斜投影法？：從n維向量空間中找出一個子空間方，從其中尋找近似解, 子空間力常稱為搜索空間。如果dim = m,則為在方中求出一個近似解，顯然要有勿個 閑置條件，通常采用個正交性條件，特別地，可以采用殘向量r = b- Ax與0個線性 無關向量正交的條件，這勿個線性無關向量就定義了另外一個以維子空間通常稱之為限 制子空間或左子空間，同時稱

8、該限制條件為Petrov-Galerkin條件。當方。時，稱對應的投 影法為斜交投影法，否則稱為正交投影法。什么是Hessenberg矩陣？：假設一個N*N矩陣A,在ij+l時，它的a (ij) =0。(A的ij 項=0),那么這個矩陣A就叫做HESSENBERG MATRIXo常用范數有哪些？：這里以Cn空間為例，Rn空間類似。最常用的范數就是P-范數。若，那么可以驗證p-范數確實滿足范數的定義。其中三角不等式的證明不是平凡的，這個結論通常 稱為閔可夫斯基(Minkowski)不等式。當p取1, 2, 8的時候分別是以下幾種最簡單的情形：1-范數：| x | 1= | xl | + | x2

9、 | + | xn |2-范數：| x | 2= ( | xl | 2+ | x2 | 2+ | xn | 2) 1/28-范數：| x | =max ( | xl | , | x2 | ,，| xn | )共銅梯度法的原理是什么？：請見PPT共銅梯度法自己理解的預條件技術？：對線性方程組AX=b,對A進行一些變換，例如LAL%使LAL 的特征值變得相對集中，提高投影算法(CG, PCG)的收斂性。對A進行的變化就稱為預條 件技術。什么是 Petrov-Galerkin 條件?:預條件技術有幾種？：有五種對角預處理法：若A是嚴格對角占優(yōu)的矩陣,則可以選擇M=diag (an, a22, .an

10、n), 可以通過初等矩陣變換，將A變換成M矩陣的形式?；诮浀涞念A處理方法(矩陣分裂法)：Jacobi, GS, Sor多項式預處理方法：選擇一個多項式s (x)預處理矩陣選擇為M=s(A),具體做法如 卜，：將預處理矩陣取為一個低次的矩陣多項式M=s(A),原方程變?yōu)椋簊(A)Ax=s(A)b,然后用迭代法求解。(見張?zhí)m的論文)無填充不完全分解預處理法：以系數矩陣的因子分解為基礎得到的預處理，這是一種 比較有效的預處理方程，主要有不完全LU分解，不完全Cholesky分解以及相應的塊不完全 分解等。子結構、區(qū)域分裂、EBE預處理途徑(見張永杰論文)。什么是左預條件？：如果將迭代方法應用于

11、M1Ax=M1b/則稱之為左預條件技術什么是右預條件？：如果將迭代方法應用于AMz=b,再通過Mx=z,求出解x,則稱之為右 預條件技術。什么是cond () ? ： Cond(A)稱作矩陣A的條件數，為矩陣A的范數與A的逆矩陣的范數的 乘積。cond(A)= II A II - II A1 II o從線性代數的分析可知,矩陣的條件數總是大于1.正交矩 陣的條件數等于1，奇異矩陣的條件數為無窮大，而病態(tài)矩陣的條件數則為比較大的數據。什么是線性無關？：向量1/1, V2,V,線性無關,當旦僅當它們滿足以下條件：如果涌，a2, a”是K的元素，適合：m + a2v2 + . + anvn = 0,

12、那么對所有/ = 1, 2,，都有a；= 0o什么是hermite矩陣即厄米特矩陣？：厄米特矩陣(Hermitian Conjugate Matrix, 乂譯作“埃爾米特矩陣”或“厄米矩陣”)，指的是自共輒矩陣。矩陣中每一個第i 行第j列的元素都與第j行第i列的元素的共軸相等。對稱矩陣是hermite矩陣 的特例。如果判斷線性方程組是病態(tài)？： 一般當det (A)的絕對值很小時，方程組Ax=b就可能是病 態(tài)。為什么預處理方法備受關注？：對不同的矩陣情況，有不同的預處理方案，沒有一種通用的 預處理方案，于是出現了很多種預處理方法。預處理矩陣與迭代短陣是什么關系？： M為預條件矩陣，G為迭代矩陣。

13、仃G=MN。什么是表征矩陣性態(tài)的條件數？：系數矩陣的最大特征值和最小特征值之比。為什么PCG算法強于CG算法？：雖然共軸梯度法在理論上最多n次迭代就可以達到精度解, 但由于舍入誤差的存在和矩陣A的一些病態(tài)特性，使p】,P2,。，PkA正交性以及山叼，,rk 的正交性隨著k增加而變差。故Xn一般不是精確解，而且降低了收斂的速度。何況對于大 型和超大型的線性方程組，即使n次迭代收斂，也是實際計算中不能接受的。于是出現了 PCG,它通過適當的預處理方法引入預處理矩陣M,使矩陣的特征值分布更為集中，降低矩 陣條件數，改善矩陣病態(tài)特性，己達到提高收斂速度的目的。矩陣譜半徑定義？：設A是nXn矩陣，入i是

14、其特征值,i=L2，,n.稱p (A)=max|入i|,i=l,2, n為A的譜半徑。共軸梯度法的推導？ ：(1)采用泛函多項式的推導過程請見：網頁共軸梯度法。用矩陣知識進行推導的過程請見：張永杰的論文p34頁。什么是BEM (邊界元方法)?:邊界元法(boundary element method)是一種繼有限元法 之后發(fā)展起來的一種新數值方法，與有限元法在連續(xù)體域內劃分單元的基本思想不同，邊界 元法是只在定義域的邊界上劃分單元，用滿足控制方程的函數去逼近邊界條件。所以邊界元 法與有限元相比，具有單元個數少，數據準備簡單等優(yōu)點。但用邊界元法解非線性問題時, 遇到同非線性項相對應的區(qū)域枳分，這

15、種積分在奇異點附近有強烈的奇異性，使求解遇到困 難。什么是引理？：引理(lemma)是數學中為了取得某個更好的結論而作為步驟被證明的命題， 其意義并不在于自身被證明，而在于為達成最終目的作出貢獻。一個引理可用于證明多個結 論。數學中存在很多著名的引理，這些引理可能對很多問題的解決有幫助。例如歐幾里得引 理，烏雷松引理，德恩引理，法圖引理，高斯引理，中山引理，龐加萊引理，里斯引理和佐 恩引理等。引理和定理沒有嚴格的區(qū)分。什么是譜半徑的相似不變性？：什么是正則化？：正則化(regularization),是指在線性代數理論中，不適定問題通常是由一 組線性代數方程定義的，而且這組方程組通常來源于有著

16、很大的條件數的不適定反問題。大 條件數意味著舍入誤差或其它誤差會嚴重地影響問題的結果。什么是不透定問題？：在經典的數學物理中，人們只研究適定問題。適定問題是指滿足下列 三個要求的問題：解是存在的；解是惟一的；解連續(xù)依賴于定解條件。這三個要求中， 只要有一個不滿足，則稱之為不適定問題。特別，如果條件不滿足，那么就稱為阿達馬意 義下的不適定問題。一般地說不適定問題，常常是指阿達馬意義下的不適定問題。什么是殘量？ ： r=b-AX,其中r為殘量什么是Z-矩陣,L-矩陣,M-矩陣？：如果一個n*n的矩陣A=(a)滿足，。J,時，弓 0,稱A為Z-矩陣;如果A是Z-矩陣，旦 0,稱A為L-矩陣;如果A是

17、L-矩陣旦4一】 0, 稱A為M-矩陣。ARGMIN的含義是什么？：最通俗的理解：表示使目標函數取最小值時的變量值:=什么意思？ ： x： =y,表示x定義為y的一個名稱。什么是譜條件數？：什么是主元？：主對角線上的元素，左上角到右下角。不是方陣就是左上角到最下一行，將這一行數的左下角那些數化成零，不就是階梯型了嘛。 可以很方便的討論矩陣的解，和矩陣的其他性質。什么是共軸？：設A為n階實對稱正定矩陣，如果有兩個n維向量S1和S2滿足S1AS2=O (1)則稱向量S1與對于矩陣A共軸。如果A為單位矩陣，則式(1)即成為S1S2,這樣兩個向量的 點積（或稱內積）為零，此二向量在幾何上是正交的，它是

18、共銅的一種特例。設A為對稱正定矩陣，若一組非零向量SI, S2, -Sn滿足SiASj=O （#j） （2）則稱向量系Si （i=l,2, -n）為關于矩陣A共輒。共扼向量的方向稱為共銅方向。什么是嚴格對角占優(yōu)？：如果A的每個對角元的絕對值都比所在行的非對角元的絕對值的 和要大，即|a_ii|sum（j!=i|a_ij|對所有的i成立，那么稱A是（行）嚴格對角占優(yōu)陣。如果ZV是行嚴格對角占優(yōu)陣，那么稱A是列嚴格對角占優(yōu)陣。什么是半正定矩陣？：如果對任何非零向量x,都有xAx0 （或x，AxO）成立，且有非零向 量xO,使xOAxO=O,則稱f為半正定（半負定）二次項，矩陣A稱為半正定矩陣（半負

19、定矩 陣）。如何判定半正定矩陣？：1、對于半正定矩陣來說，相應的條件應改為所有的主子式非負。順序主子式非負并不能推 出矩陣是半正定的。比如以下例子：2、半正定矩陣定義：設A是實對稱矩陣。如果對任意的實非零列矩陣X有XT*A*X0.就稱A為半正定矩 陣。3、AEMn （K）是半正定矩陣的充要條件是：A的所有主子式大于或等于零。什么是主子式？ ： n階行列式的i階主子式為：在n階行列式中，選取行號（如1、3、7行），再選取相同行號的列號（1、3、7列），則 有行和列都為i個的行列式即為n階行列式的i階主子式，也可以說由上述選取的行列交匯 處的元素所組成的新的行列式就稱為n階行列式的一個i階主子式。

20、什么是順序主子式？：特殊的：n階行列式的i階順序主子式：上述i階主子式中定義中，由1i行和1i列所確定的子式即為“n階行列式的i階順序主 子式市面上求解線性方程組的求解器有哪些？LAPACKSLAPACK,其名為Linear Algebra PACKage的縮寫，是一以Fortran編程語言寫就， 用于數值計算的函式集。LAPACK提供了豐富的工具函式，可用于諸如解多元線性 方程式、線性系統(tǒng)方程組的最小平方解、計算特征向量、用于計算矩陣QR分解的 Householder轉換、以及奇異值分解等問題。在NetLib亦提供了 API經簡化的 Fortran 95版本的LAPACK95。LAPACK以

21、BSD授權的方法釋出。Intel PardisoIntel MKL提供了針對稀疏矩陣求解的PARDISO接I I,它是在共享內存機器上，實 現的稀疏矩陣的直接求解方法，對于一些大規(guī)模的計算問題,PARDISO的算法表現 了非常好的計算效率與并行性。一些數值測試表明，隨著計算節(jié)點數目增加, PARDISO具有接近線性的加速比例。IML with sparselib from NISTSparseLib+ 是一個 C+類庫?？赏ㄟ^不同的計算平臺有效的計算稀疏矩陣。軟件包包含存儲格式(如壓縮行，壓縮列和坐標格式)，并提供基本的功能來管理稀 疏矩陣。BIAS工具包用于進行高效的內核數學運算(如稀疏矩陣

22、向量乘法等)。 通過一個計算機體系結構，提高可移植性和性能。SAMG解算器最新版的代數多網格法的SAMG解算器系統(tǒng)己經被實現，這對于己經證明由 SCAI-Franhofer研究院開發(fā)的SAMG計算器，運用與中等規(guī)模模型時要比傳統(tǒng)的 PCG解算器快3-11倍，并旦對于包含一百萬或更多網格單元的大規(guī)模模型更快。Hypreform LLNLHypre(High Performance Preconditioners,高性能預條件子)由美國加州大學(UC) 和勞倫斯-利弗莫爾國家實驗室(LLNL)應用計算中心(CASC)開發(fā)的。該軟件包 主要用于大規(guī)模并行計算機上求解大型稀疏線性方程組組，主要目的是為

23、用戶提供 高級并行預條件子。它具有強壯性、易用性、適應性和互動性。FASP from BiCMR幾何/代數多重網格法，以及迭代器Blitzpak from landmark結構化網格油藏求解器，只在UNIX環(huán)境下可用。 PARDIS。對應求解過程包括如下步驟：矩陣重排與符號分解(Reordering and Symbolic Factorization)： PAR DISO Solver 根據不 同的矩陣類型，計算不同類型的行列交換矩陣P與對角矩陣D,對A矩陣進行交換重排。 新得到的矩陣分解后會包括盡量少的非零元素。矩陣LU分解：對進行LU分解。方程求解與迭代：根據LU分解的結果，求解方程，如

24、果對結果的精度有進一步要 求，使用迭代法進一步提高解精度。迭代結束，釋放計算過程的內存。使用PARDISO的時候，可能會有一些常見的問題：第一，Paridso提示內存不足：出現這類問題的時候，可以首先檢查一下Pardiso對求解該問題的內存需求,Pandis。 計算時，可以通過下面的數據求得：max(iparm(15), iparm(16)+iparm(17)可以對比一下這個數據，查看系統(tǒng)的內存是否滿足需求。Paridso同時支持，in-coe與out-of-core的計算。如果，計算的數據太大，而不能 完全在內存求解的時候，可以的使用out-of-core的pardiso (設置iparm(

25、60)參數)。 Out-of-core的計算會將中間計算數據保存于硬盤上，從而能夠解決一些大的計算問題 HYPERLINK 。實際中，還常常遇到的一個問題是，許多應用是32位的程序，這樣，即使使用 out-of-core的pardiso來求解，仍然會受到32位的地址空間的限制。如果計算數據非常的 大，需要改寫為64位的計算程序。第二，檢查輸入數據的合法性：使用Pardiso在進行計算的時候，常常會出現中間計算錯誤。由于Pardiso采用CSR 格式的壓縮存儲的矩陣。很多情況卜，計算錯誤是由于輸入了不合法的計算數據而導致。對 于這類問題，可以在調用Pardiso的時候，進行輸入數據的檢查(設置i

26、parm(27)的參數)， Pandso如果發(fā)現輸入數據的錯誤，會給出錯誤提示。這類檢查，可以幫助發(fā)現一些簡單的, 特別是與輸入數據的索引相關的輸入錯誤。第三，使用缺省參數：Pardiso中提供了豐富的輸入參數選項。用戶在調用的時候，需要確保正確的輸入參數。 很多在計算過程中發(fā)生的錯誤，往往與不正確的輸入參數相關。一個常用的檢查方法是輸入 缺省的paridso的參數(iparm=0), Parids。使用缺省參數進行計算，來檢驗程序的正 確性。第四，在C/C+語言的調用Pardiso：在Intel MKL函數手冊中，Pardiso相關參數的說明是以Fortran語言的形式給出。如 果我們在C/

27、C+語言中,調用Pardiso函數，需要注意輸入數據的數組下標。C語言中對 應的數組下標是從0開始，程序中對應于Fortran的下標需要減一(比如，手冊中提到， iparm(10)的參數，在C程序中,需要寫為iparm9) IML with sparselib from NIST.SparseLib+ is a C+ class library for efficient sparse matrix computations across various computational platforms. The software package consists of matrix class

28、es encompassing several sparse storage formats (e.g. compressed row, compressed column and coordinate formats), and providing basic functionality for managing sparse matrices. The Sparse BLAS Toolkit is used to for efficient kernel mathematical operations (e.g. sparse matrix-vector multiply) and to

29、enhance portability and performance across a wide range of computer architectures. Included in the package are various preconditioners commonly used in iterative solvers for linear systems of equations. The focus is on computational support for iterative methods (for example, see IML+), but the spar