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

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

2、妙地將其變?yōu)镵xi+l=Kxi+b-Axi 的迭代形式來求解。這里的K(來源于作者俄國人Nikolai Krylov姓氏的首字母)是一個構(gòu)造出 來的接近于A的矩陣，而迭代形式的算法的妙處在于，它將復(fù)雜問題化簡為階段性的易于 計算的子步驟。如何取正定矩陣Mk為：Span是什么？：設(shè)e V ，稱它們的線性組合佇內(nèi)氏為向量 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)而言，如果指標(biāo)集1, 2，n)能夠被劃分成兩個不相交 的非空指標(biāo)集J和K,使得對任意的jO和任意的kEK都有ajk=O,則稱矩陣A是可約 的；否則稱矩陣A是不可約的。n階方矩陣A是不可約的當(dāng)?shù)﹥H當(dāng)與矩陣A對應(yīng)的有向圖是強(qiáng)連通的。什么是正交？：在三維向量空間中，兩個向量的內(nèi)枳如果是

4、零，那么就說這兩個向量是正交 的。換句話說，兩個向量正交意味著它們是相互垂直的。若向量a與&正交，則記為a 3。 什么是正交矩陣？：如果：AA=E(E為單位矩陣，甘表示“矩陣A的轉(zhuǎn)置矩陣”。)或A A=E, 則n階實(shí)矩陣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是偶數(shù)。倒著的A:任意的A邏輯合取陳述A A B為真，如果A與B

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

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

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

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

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

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

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

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

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

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

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

16、很大的條件數(shù)的不適定反問題。大 條件數(shù)意味著舍入誤差或其它誤差會嚴(yán)重地影響問題的結(jié)果。什么是不透定問題？：在經(jīng)典的數(shù)學(xué)物理中，人們只研究適定問題。適定問題是指滿足下列 三個要求的問題：解是存在的；解是惟一的；解連續(xù)依賴于定解條件。這三個要求中， 只要有一個不滿足，則稱之為不適定問題。特別，如果條件不滿足，那么就稱為阿達(dá)馬意 義下的不適定問題。一般地說不適定問題，常常是指阿達(dá)馬意義下的不適定問題。什么是殘量？ ： 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的含義是什么？：最通俗的理解：表示使目標(biāo)函數(shù)取最小值時的變量值:=什么意思？ ： x： =y,表示x定義為y的一個名稱。什么是譜條件數(shù)？：什么是主元？：主對角線上的元素，左上角到右下角。不是方陣就是左上角到最下一行，將這一行數(shù)的左下角那些數(shù)化成零，不就是階梯型了嘛。 可以很方便的討論矩陣的解，和矩陣的其他性質(zhì)。什么是共軸？：設(shè)A為n階實(shí)對稱正定矩陣，如果有兩個n維向量S1和S2滿足S1AS2=O (1)則稱向量S1與對于矩陣A共軸。如果A為單位矩陣，則式(1)即成為S1S2,這樣兩個向量的 點(diǎn)積（或稱內(nèi)積）為零，此二向量在幾何上是正交的，它是

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

19、定矩 陣）。如何判定半正定矩陣？：1、對于半正定矩陣來說，相應(yīng)的條件應(yīng)改為所有的主子式非負(fù)。順序主子式非負(fù)并不能推 出矩陣是半正定的。比如以下例子：2、半正定矩陣定義：設(shè)A是實(shí)對稱矩陣。如果對任意的實(shí)非零列矩陣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編程語言寫就， 用于數(shù)值計算的函式集。LAPACK提供了豐富的工具函式，可用于諸如解多元線性 方程式、線性系統(tǒng)方程組的最小平方解、計算特征向量、用于計算矩陣QR分解的 Householder轉(zhuǎn)換、以及奇異值分解等問題。在NetLib亦提供了 API經(jīng)簡化的 Fortran 95版本的LAPACK95。LAPACK以

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

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

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

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

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

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

27、C+語言中,調(diào)用Pardiso函數(shù)，需要注意輸入數(shù)據(jù)的數(shù)組下標(biāo)。C語言中對 應(yīng)的數(shù)組下標(biāo)是從0開始，程序中對應(yīng)于Fortran的下標(biāo)需要減一(比如，手冊中提到， iparm(10)的參數(shù)，在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