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

迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。

迭代法又分为精确迭代和近似迭代。

“二分法”和“牛顿迭代法”属于近似迭代法。

迭代算法是用计算机解决问题的一种基本方法。

它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

例 1 ：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。

如果所有的兔子都不死去，问到第12 个月时，该饲养场共有兔子多少只？分析：这是一个典型的递推问题。

我们不妨假设第 1 个月时兔子的只数为u 1 ，第 2 个月时兔子的只数为u 2 ，第 3 个月时兔子的只数为u 3 ，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有u 1 ＝ 1 ，u 2 ＝u 1 ＋u 1 ×1 ＝ 2 ，u 3 ＝u 2 ＋u 2 ×1＝ 4 ，……根据这个规律，可以归纳出下面的递推公式：u n ＝u n － 1 × 2 (n ≥ 2)对应u n 和u n － 1 ，定义两个迭代变量y 和x ，可将上面的递推公式转换成如下迭代关系：y=x*2x=y让计算机对这个迭代关系重复执行11 次，就可以算出第12 个月时的兔子数。

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(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。

如何取正定矩阵Mk为：Span是什么？:设x_(1,)...,x_m∈V ,称它们的线性组合∑_(i=1)^m?〖k_i x_i \|k_i∈K,i=1,2...m〗为向量x_(1,)...,x_m的生成子空间，也称为由x_(1,)...,x_m张成的子空间。

记为L（x_(1,)...,x_m），也可以记为Span（x_(1,)...,x_m）什么是Jacobi迭代法：什么是G_S迭代法：请见PPT《迭代法求解线性方程组》什么是SOR迭代法：什么是收敛速度：什么是可约矩阵与不可约矩阵？：不可约矩阵（irreducible matrix）和可约矩阵（reducible matrix）两个相对的概念。

定义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 是不可约的。

krylov子空间迭代法Krylov子空间迭代法是一种有效的求解线性方程组的迭代方法，因Krylov于1908年提出而得名。

它是一种基于子空间的迭代方法，可以在较少的计算量下，解决高维线性方程组的较大特征值的问题。

Krylov子空间迭代法的基本思想是：将线性方程组中的高维系数矩阵P划分为n个受限的Krylov子空间，用这些子空间来模拟矩阵P的特征值的变化趋势。

这样，可以使线性方程组的解从低维子空间转移到高维子空间，从而求出线性方程组的解。

Krylov子空间迭代法具有以下优点：（1）采用Krylov子空间技术可以降低计算维度，减少计算量，提高计算效率；（2）将子空间技术与迭代法相结合，实现了近似求解线性方程组的解；（3）Krylov子空间迭代法能有效收敛，解的可靠性高；（4）运行简便，无需调整参数；（5）可用于求解各种类型的线性方程组。

由于Krylov子空间迭代法的优越性，它已经广泛应用于工程、数学、物理、生物等多学科的计算和仿真中。

从根本上讲，Krylov子空间迭代法是一种非常有效的迭代方法，它可以有效地解决线性方程组的特征值问题。

下面我们将介绍Krylov 子空间迭代法的算法步骤：（1）输入高维系数矩阵P、初始向量v、迭代次数m及收敛准则ε；（2）构造Krylov子空间：V＝[v，Pv, Pv,……，P^m-1v]；（3）用V中的向量代替P，将Pv-λv转化为V的线性方程；（4）求解V线性方程组；（5）求出V的特征值λ；（6）利用第4步求出的解v，求出线性方程组的解x；（7）若特征值收敛，则停止迭代；（8）重复第2至第7步，直至特征值收敛；（9）输出计算结果。

以上就是Krylov子空间迭代法的算法步骤。

Krylov子空间迭代法的算法实现起来相对简单，只需要实现以上的几个步骤即可。

由于Krylov子空间迭代法的有效性，它已经被广泛应用于工程、数学、医学、物理、生物等多学科的计算和仿真中。

总之，Krylov子空间迭代法是一种高效的求解线性方程组的迭代方法，它可以有效收敛，具有较高的求解精确度和计算效率。

子空间迭代法
子空间迭代法是一种有效的数值计算求解最优化问题的方法，它的基本思想是：先给定一个初始解，然后在可行解子空间内逐步搜索，最终找到全局最优解。

传统的最优化方法，如曲面拟合或凸优化，是通过在整个解空间内搜索最优解来实现的。

这种方法可能会遇到搜索范围广泛，所需计算量非常大的问题。

此外，由于当前解往往不是最优解，因此可能存在局部最优解，而忽略了全局最优解。

子空间迭代法是一种改进的最优化方法，它不是将整个解空间作为搜索空间，而是从初始解出发，在尽可能小的子空间内搜索，逐步向全局最优解前进。

它能够在较小的时间和空间内找到最优解，并且不易陷入局部最优解而忽略全局最优解。

子空间迭代法的收敛效果一般比传统最优化方法更加可靠。

此外，它的实施过程简单，需要的计算量小，鲁棒性较强；而且由于只搜索可行解子空间，所以更能够节省计算资源。

总的来说，子空间迭代法是解决最优化问题的一种很好的方法，它比传统最优化方法拥有更高的收敛性，更优的时间和空间复杂度，以及更好的鲁棒性。

它已经成为多种工程设计中不可或缺的重要部分，为优化问题的解决提供了一种有效的途径。

迭代法—搜狗百科例1 ：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。

如果所有的兔子都不死去，问到第 12 个月时，该饲养场共有兔子多少只？分析：这是一个典型的递推问题。

我们不妨假设第1 个月时兔子的只数为 u 1 ，第 2 个月时兔子的只数为 u 2 ，第 3 个月时兔子的只数为 u 3 ，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有u 1 = 1 ，u 2 = u 1 + u 1 × 1 = 2 ，u 3 = u 2 + u 2 × 1 = 4 ，……根据这个规律，可以归纳出下面的递推公式：u n = u(n － 1）× 2 (n ≥ 2）对应 u n 和 u(n － 1），定义两个迭代变量 y 和 x ，可将上面的递推公式转换成如下迭代关系：y=x*2x=y让计算机对这个迭代关系重复执行 11 次，就可以算出第 12 个月时的兔子数。

参考程序如下：clsx=1for i=2 to 12y=x*2x=ynext iprint yend例 2 ：阿米巴用简单分裂的方式繁殖，它每分裂一次要用 3 分钟。

将若干个阿米巴放在一个盛满营养参液的容器内， 45 分钟后容器内充满了阿米巴。

已知容器最多可以装阿米巴220,220个。

试问，开始的时候往容器内放了多少个阿米巴？请编程序算出。

分析：根据题意，阿米巴每3 分钟分裂一次，那么从开始的时候将阿米巴放入容器里面，到45 分钟后充满容器，需要分裂45/3=15 次。

而“容器最多可以装阿米巴2^ 20 个”，即阿米巴分裂15 次以后得到的个数是 2^20。

题目要求我们计算分裂之前的阿米巴数，不妨使用倒推的方法，从第 15 次分裂之后的 2^20 个，倒推出第 15 次分裂之前（即第 14 次分裂之后）的个数，再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。

krylov 子空间迭代算法Krylov子空间迭代算法Krylov子空间迭代算法是一种常用的数值方法，用于求解线性方程组和特征值问题。

它的基本思想是通过构建一个Krylov子空间来逼近问题的解，从而实现高效的迭代求解。

Krylov子空间是由向量b和矩阵A的幂次向量组成的，即{b, Ab, A^2b, ..., A^(m-1)b}，其中m是迭代步数。

Krylov子空间的一个重要性质是它能够近似表示线性方程组或特征值问题的解。

因此，通过在Krylov子空间中寻找一个最优近似解，可以有效地求解原始问题。

Krylov子空间迭代算法的核心是通过迭代过程不断扩展Krylov子空间，从而逼近问题的解。

最常用的Krylov子空间迭代算法有雅可比迭代法、Gauss-Seidel迭代法和共轭梯度法等。

雅可比迭代法是最简单的Krylov子空间迭代算法之一。

它的基本思想是通过迭代更新解向量的各个分量，直到满足一定的收敛条件。

每次迭代中，雅可比迭代法只考虑线性方程组的一个分量，并用当前解向量中的其他分量作为已知条件。

这种分量级的更新方式使得雅可比迭代法的收敛速度较慢，但它具有简单易实现的优点。

Gauss-Seidel迭代法是另一种常用的Krylov子空间迭代算法。

它的思想是通过迭代更新解向量的各个分量，并利用已更新的分量来更新其他分量。

与雅可比迭代法不同的是，Gauss-Seidel迭代法在更新解向量的过程中，始终使用最新的可用信息。

这种分量级的更新方式使得Gauss-Seidel迭代法的收敛速度相对较快。

共轭梯度法是一种更高级的Krylov子空间迭代算法，它在求解对称正定线性方程组时具有较好的收敛性能。

共轭梯度法利用了线性方程组的对称性质，通过构建正交的搜索方向和共轭的更新方式，实现了更快的收敛速度。

共轭梯度法的优点在于它不需要存储整个Krylov子空间，只需存储一个搜索方向和一个残差向量，从而减少了内存消耗。

除了线性方程组的求解，Krylov子空间迭代算法还可以用于求解特征值问题。

0 引言随着中国经济的高速发展，对体育馆、交通枢纽、会展中心、文化建筑的需求日益增大，极大地推动了我国空间结构的研究与工程实践的发展，并取得了丰硕的成果[1]。

张涛[2]在济南万象城幕墙支撑结构设计概况中提出，近年来随着商业地产的高速发展，大型商业综合体项目越来越多，产品出现高度同质化，开发商为打造专属的建筑特点，在空间营造上追求“大挑空、大采光、大通透”，一些空间形状复杂、悬挂质量大、系统刚度柔、节点构造复杂的大跨度空间结构体系被广泛应用于幕墙支承结构，其中单层网壳被广泛应用于商业综合体项目采光顶支承结构。

单层网壳属于缺陷敏感型结构，稳定性起主要控制作用[3]。

结构失稳主要分为第一类失稳和第二类失稳两种基本形式。

第一类失稳通常是指结构荷载增加至一定数值时，结构由原来平衡状态变为另外一个平衡状态，该类失稳又称为分支点失稳或平衡分岔失稳；第二类失稳是指结构在大变形和大位移的不稳定的发展过程中，没有新的变形形式出现，失稳时结构平衡形态本质没有发生改变，这类失稳也称极值点失稳。

跳跃失稳与极值点失稳性质类似，通常也被归为第二类失稳问题。

两类稳定问题的主要区别是荷载—位移曲线上是否出现分支点，工程中存在的结构失稳多数是第二类失稳问题[4]。

第一类稳定问题是求解特征值，结构失稳发生在结构变形前，不考虑初始几何缺陷、材料弹塑性对结构极限承载力的影响，采用的是理想模型和小挠度理论，属于弹性阶段的线性分析，《钢结构设计标准》（GB50017-2017）称之为一阶分析法[5]；第二类稳定分析采用的是变形后的非理想模型和大挠度理论，极值失稳发生在结构变形后，考虑初始几何缺陷、材料弹塑性和几何非线性对结构极限承载力的影响，属于非线性分析，与《钢结构设计标准》中提出的二阶分析法存在一定的共同点。

单层网壳属于缺陷敏感型结构，安全性依赖结构具有良好的极限承载力，单层网壳的构件在制作、运输、测量、空间拼装、焊接过程中累积的几何误差及构件材料本身的缺陷会对单层网壳的极限承载力造成重大的影响，以上几何误差及材料缺陷统称初始几何缺陷。

第二章 迭代法的一般原理非线性方程组无论从理论上还是计算方法上，都比线性方程组复杂得多。

一般的非线性方程组很难求出解析解，往往只能求出其数值解，且往往只能借助于迭代法。

本章我们将讨论迭代法的一般原理、迭代法的一般构造及迭代收敛速度的衡量标准。

2-1 迭代法与不动点定理设n n R R D →⊂:f ，考虑方程()0=x f (2-1)若存在D *∈x ，使()0=*x f ，则称*x 为方程(2-1) 的解。

用迭代法求解(2-1) ，先将(2-1)化为等价的方程 ()x g x =(2-2)这里映象n n R R D →⊂:g 。

方程(2-2)的解*x (即()**x g x =)称为映象g 的不动点。

因此用迭代法解方程(2-1)，就是求(2-2)中映象g 的不动点。

这样以及g 是否存在不动点自然就是我们关心的问题。

定理2-1 若n n R R D →⊂:g 为有界闭集D D ⊂0上的严格非膨胀映象，()00D D ⊂g ，则g 在0D 内有唯一不动点。

证 唯一性 设g 在0D 内至少有两个不动点1x ，2x ，则()()2121x x x g x g x x 21-≤-=-α 因1<α，所以由上式推得21x x =。

唯一性得证。

记()()x g x x -=ϕ，由g 及泛数的连续性可知1:R R D n →⊂ϕ连续。

因0D 为有界闭集，故ϕ在0D 上有最小值。

设0D *∈x 为最小点，即()()x g x x -=∈m in 0D x *ϕ则*x 为g 的不动点。

因为若不然，则有()**x g x ≠，再由g 严格非膨胀，可得 ()()()()()***x g g x g x g -=ϕ()()***x x g x ϕ=-<这与*x 为ϕ的最小点相矛盾，故*x 为g 的不动点。

注 定理中0D 的有界闭性、g 的压缩性和g 映0D 入自身，此3个条件缺一不可。

例如，()xx x g 1+=在[)+∞=,D 10上严格非膨胀，但它在0D 中却没有不动点。

子空间迭代法
子空间迭代法也称同时迭代法，它是乘幂法的直接推广，能同时求出模较大的一些特征值和相应的特征向量。

与乘幂法的区别主要在两个方面：第一，同时迭代法是同时用几个（例如p个）线性无关的正交规范向量进行类似于乘幂法的迭代。

若将选代向量看作一个p维子空间的（正交规范）基，则每迭代一次就得到一个新的子空间.第二，在迭代过程中应用Rayleigh-Ritz原理进行加速。

因此，同时迭代法比乘幂法更便于进行自动计算，而且加快了收敛速度，它是求解大型、稀疏矩阵特征值问题的最有效的方法之一。