预处理子空间迭代法的一些基本概念

CG算法的预处理技术：、为什么要对A进行预处理：其收敛速度依赖于对称正定阵A的特征值分布特征值如何影响收敛性：特征值分布在较小的范围内，从而加速CG的收敛性特征值和特征向量的定义是什么？（见笔记本以及收藏的网页）求解特征值和特征向量的方法：Davidson方法：Davidson方法是用矩阵(D-θI)-1(A-θI)产生子空间，这里D是A的对角元所组成的对角矩阵。θ是由Rayleigh-Ritz过程所得到的A的近似特征值。什么是子空间法：Krylov子空间叠代法是用来求解形如Ax=b的方程，A是一个n*n的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi的迭代形式来求解。这里的K(来源于作者俄国人NikolaiKrylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。如何取正定矩阵Mk为：Span是什么？:设𝑥1,…,𝑥𝑚∈𝑉,称它们的线性组合∑𝑘𝑖𝑥𝑖|𝑘𝑖∈𝐾,𝑖=1,2…𝑚𝑚𝑖=1为向量𝑥1,…,𝑥𝑚的生成子空间，也称为由𝑥1,…,𝑥𝑚张成的子空间。记为L（𝑥1,…,𝑥𝑚），也可以记为Span（𝑥1,…,𝑥𝑚）什么是Jacobi迭代法：什么是G_S迭代法：请见PPT《迭代法求解线性方程组》什么是SOR迭代法：什么是收敛速度：称收敛速度。度，简为迭代法的渐近收敛速)(ln)(:5定义BBR什么是可约矩阵与不可约矩阵？：不可约矩阵（irreduciblematrix）和可约矩阵（reduciblematrix）两个相对的概念。定义1：对于n阶方阵A而言，如果存在一个排列阵P使得P'AP为一个分块上三角阵，我们就称矩阵A是可约的；否则称矩阵A是不可约的。定义2：对于n阶方阵A=(aij)而言，如果指标集{1，2，...，n}能够被划分成两个不相交的非空指标集J和K，使得对任意的j∈J和任意的k∈K都有ajk=0,则称矩阵A是可约的；否则称矩阵A是不可约的。n阶方矩阵A是不可约的当且仅当与矩阵A对应的有向图是强连通的。什么是正交？：在三维向量空间中，两个向量的内积如果是零，那么就说这两个向量是正交的。换句话说，两个向量正交意味着它们是相互垂直的。若向量α与β正交，则记为α⊥β。什么是正交矩阵？：如果：AA'=E（E为单位矩阵，A'表示“矩阵A的转置矩阵”。）或A′A=E，则n阶实矩阵A称为正交矩阵，若A为单位正交阵，则满足以下条件:1)AT是正交矩阵2)（E为单位矩阵）3)A的各行是单位向量且两两正交4)A的各列是单位向量且两两正交5)(Ax,Ay)=(x,y)x,y∈R6)|A|=1或-1倒着写的A和E都是什么意思啊？：反着的E:谓词逻辑存在量词∃x:P(x)意味着有至少一个x使P(x)为真。n∈N:n是偶数。倒着的A:任意的∧逻辑合取陈述A∧B为真，如果A与B二者都为真；否则为假。n4∧n2⇔n=3当n是自然数的时候。与命题逻辑∨逻辑析取陈述A∨B为真，如果A或B(或二者)为真；如果二者都为假，则陈述为假。n≥4∨n≤2⇔n≠3当n是自然数的时候。迭代法与直接法比较优劣是什么？：对称正定的定义是什么？：设M是n阶方阵，如果对任何非零向量z，都有z'Mz0，其中z'表示z的转置，就称M正定矩阵。判定定理1：对称阵A为正定的充分必要条件是：A的特征值全为正。判定定理2：对称阵A为正定的充分必要条件是：A的各阶顺序主子式都为正。迭代法求解稀疏矩阵时是否有填充元问题？：CG法求解线性矩阵时有无误差问题？：有。误差可能导致收敛变慢甚至无法求解。什么是Krylov子空间法？：设要求解线性代数方程组Ax=b，取00010(,)(,,...,)mmmKKArSpanrArAr，其中00rbAx，且0x为初始解，从0mxK中寻找近似解mx，使相应的残向量与另某个子空间mL正交，即mmmrbAxL则称mK为Krylov子空间，且上述方法称为Krylov子空间方法。GMRES方法的缺点是什么？：因为它实际上求式AZ=r的解等价在在Krylov子空间中极小化残余向量的||.||范数。但GMRES会有失去超线性收敛性、可能产生停滞、GMRES每迭代一步都要进行Arnoldi过程中都要消耗大量的计算时间、随着子空间维数的增大，引起存储空间过多的需求，每次迭代正交化过程所需代价显著增长等缺点。矩阵右上角有个H，这是什么矩阵呢？（有个T是转置，有个H是什么）:一般来讲A^T表示转置，A^H表示转置共轭，对实矩阵而言是一回事，对复矩阵而言转置共轭比单纯的转置更常用一些，比如酉变换、Hermite型等。什么是正交投影法和斜投影法？：从n维向量空间中找出一个子空间，从其中寻找近似解，子空间常称为搜索空间。如果dimm，则为在中求出一个近似解，显然要有m个闲置条件，通常采用m个正交性条件，特别地，可以采用残向量rbAx与m个线性无关向量正交的条件，这m个线性无关向量就定义了另外一个m维子空间，通常称之为限制子空间或左子空间，同时称该限制条件为Petrov-Galerkin条件。当时，称对应的投影法为斜交投影法，否则称为正交投影法。什么是Hessenberg矩阵？：假设一个N*N矩阵A，在ij+1时，它的a（i,j）=0。（A的i,j项=0），那么这个矩阵A就叫做HESSENBERGMATRIX。常用范数有哪些？：这里以Cn空间为例，Rn空间类似。最常用的范数就是p-范数。若，那么可以验证p-范数确实满足范数的定义。其中三角不等式的证明不是平凡的，这个结论通常称为闵可夫斯基(Minkowski）不等式。当p取1，2，∞的时候分别是以下几种最简单的情形：1-范数：║x║1=│x1│+│x2│+…+│xn│2-范数：║x║2=（│x1│2+│x2│2+…+│xn│2）1/2∞-范数：║x║∞=max（│x1│，│x2│，…，│xn│）共轭梯度法的原理是什么？：请见PPT《共轭梯度法》自己理解的预条件技术？：对线性方程组AX=b，对A进行一些变换，例如LAL-1，使LAL-1的特征值变得相对集中，提高投影算法（CG，PCG）的收敛性。对A进行的变化就称为预条件技术。什么是Petrov-Galerkin条件？：预条件技术有几种？：有五种（1）对角预处理法：若A是严格对角占优的矩阵，则可以选择M=diag（a11，a22，…ann）,可以通过初等矩阵变换，将A变换成M矩阵的形式。（2）基于经典迭代的预处理方法（矩阵分裂法）：Jacobi，GS，Sor（3）多项式预处理方法：选择一个多项式s（x）预处理矩阵选择为M-1=s(A)，具体做法如下：将预处理矩阵取为一个低次的矩阵多项式M-1=s(A)，原方程变为：s(A)Ax=s(A)b，然后用迭代法求解。（见张兰的论文）（4）无填充不完全分解预处理法：以系数矩阵的因子分解为基础得到的预处理，这是一种比较有效的预处理方程，主要有不完全LU分解，不完全Cholesky分解以及相应的块不完全分解等。（5）子结构、区域分裂、EBE预处理途径（见张永杰论文）。什么是左预条件？：如果将迭代方法应用于M-1Ax=M-1b,则称之为左预条件技术什么是右预条件？：如果将迭代方法应用于AM-1z=b，再通过Mx=z，求出解x，则称之为右预条件技术。什么是cond（）？：Cond(A)称作矩阵A的条件数，为矩阵A的范数与A的逆矩阵的范数的乘积。cond(A)=‖A‖·‖A-1‖。从线性代数的分析可知，矩阵的条件数总是大于1.正交矩阵的条件数等于1，奇异矩阵的条件数为无穷大，而病态矩阵的条件数则为比较大的数据。什么是线性无关？：向量v1,v2,...,vn线性无关，当且仅当它们满足以下条件：如果a1,a2,...,an是K的元素，适合：a1v1+a2v2+...+anvn=0，那么对所有i=1,2,...,n都有ai=0。什么是hermite矩阵即厄米特矩阵？：厄米特矩阵（HermitianConjugateMatrix，又译作“埃尔米特矩阵”或“厄米矩阵”），指的是自共轭矩阵。矩阵中每一个第i行第j列的元素都与第j行第i列的元素的共轭相等。对称矩阵是hermite矩阵的特例。如果判断线性方程组是病态？：一般当det（A）的绝对值很小时，方程组Ax=b就可能是病态。为什么预处理方法备受关注？：对不同的矩阵情况，有不同的预处理方案，没有一种通用的预处理方案，于是出现了很多种预处理方法。预处理矩阵与迭代矩阵是什么关系？：M为预条件矩阵，G为迭代矩阵。有G=M-1N。什么是表征矩阵性态的条件数？：系数矩阵的最大特征值和最小特征值之比。为什么PCG算法强于CG算法？：虽然共轭梯度法在理论上最多n次迭代就可以达到精度解，但由于舍入误差的存在和矩阵A的一些病态特性，使{p1，p2，。。。，pk}A正交性以及{r1,r2,…,rk}的正交性随着k增加而变差。故xn一般不是精确解，而且降低了收敛的速度。何况对于大型和超大型的线性方程组，即使n次迭代收敛，也是实际计算中不能接受的。于是出现了PCG，它通过适当的预处理方法引入预处理矩阵M，使矩阵的特征值分布更为集中，降低矩阵条件数，改善矩阵病态特性，已达到提高收敛速度的目的。矩阵谱半径定义？:设A是n×n矩阵,λi是其特征值,i=1,2,…,n.称ρ(A)=max{|λi|,i=1,2,……n}为A的谱半径。共轭梯度法的推导？：（1）采用泛函多项式的推导过程请见：网页《共轭梯度法》。（2）用矩阵知识进行推导的过程请见：张永杰的论文p34页。什么是BEM（边界元方法）？：边界元法（boundaryelementmethod）是一种继有限元法之后发展起来的一种新数值方法，与有限元法在连续体域内划分单元的基本思想不同，边界元法是只在定义域的边界上划分单元，用满足控制方程的函数去逼近边界条件。所以边界元法与有限元相比，具有单元个数少，数据准备简单等优点。但用边界元法解非线性问题时，遇到同非线性项相对应的区域积分，这种积分在奇异点附近有强烈的奇异性，使求解遇到困难。什么是引理？：引理（lemma）是数学中为了取得某个更好的结论而作为步骤被证明的命题，其意义并不在于自身被证明，而在于为达成最终目的作出贡献。一个引理可用于证明多个结论。数学中存在很多著名的引理，这些引理可能对很多问题的解决有帮助。例如欧几里得引理，乌雷松引理，德恩引理，法图引理，高斯引理，中山引理，庞加莱引理，里斯引理和佐恩引理等。引理和定理没有严格的区分。什么是谱半径的相似不变性？：什么是正则化？：正则化(regularization)，是指在线性代数理论中，不适定问题通常是由一组线性代数方程定义的，而且这组方程组通常来源于有着很大的条件数的不适定反问题。大条件数意味着舍入误差或其它误差会严重地影响问题的结果。什么是不适定问题？：在经典的数学物理中，人们只研究适定问题。适定问题是指满足下列三个要求的问题：①解是存在的；②解是惟一的；③解连续依赖于定解条件。这三个要求中，只要有一个不满足，则称之为不适定问题。特别，如果条件③不满足，那么就称为阿达马意义下的不适定问题。一般地说不适定问题，常常是指阿达马意义下的不适定问题。什么是残量？：r=b-AX，其中r为残量什么是Z-矩阵，L-矩阵，M-矩阵？：如果一个n*n的矩阵A=（aij）满足ij时，0ija，称A为Z-矩阵；如果A是Z-矩阵，且0iia，称A为L-矩阵；如果A是L-矩阵且10A，称A为M-矩阵。ARGMIN的含义是什么？：最通俗的理解：表示使目标函数取最小值时的变量值：=什么意思？：x：=y，表示x定义为y的一个名称。什么是谱条件数？：什么是主元？：主对角线上的元素，左上角到右下角。不是方阵就是左上角到最下一行，将这一行数的左下角那些数化成零，不就是阶梯型了嘛。可以很方便的讨论矩阵的解，和矩阵的其他性质。什么是共轭？：设A为n阶实对称正定矩阵，如果有两个n维向量S