【OpenSEES】浅析Newton迭代（三）：基于Krylov优化迭代算法

“小容差的线搜索优化效果优于克雷洛夫”

本推送是迭代三部曲的最后一篇。第一篇推送【OpenSEES】浅析Newton迭代（一）：减少刚度重构工作量与减少迭代次数谁更有意义？分享了几类基础的牛顿迭代算法；第二篇推送【OpenSEES】浅析Newton迭代（二）：基于LineSearch优化迭代算法分享线搜索在牛顿迭代中的应用。本次推送将和大家分享克雷洛夫子空间优化迭代算法（Krylov-Newton）的原理及其相应的实例。点击“阅读原文”可下载本推送的算例模型、相应工具源码及参考资料。

数学中的Krylov

Krylov是一种“降维打击”手段，通过牺牲精度来换取求解速度。当求解线性方程组KU=F（K为刚度矩阵，U为未知的位移向量，F为不平衡力向量）时，一般思路是如式（1）所示直接对刚度矩阵K求逆，之后即可求解未知位移向量U。

但当刚度矩阵K为大型稀疏矩阵时，求逆则异常困难。Krylov想出一种聪明的方法来代替矩阵求逆，如式（2）所示。式中Betai为未知量，m为Krylov子空间维度（需小于刚度矩阵k的维度）。如此处理，便不用再对大型系数矩阵求逆，只要求出方程中Betai的值便齐活！

将式（2）带入式（1）获得式（3）。由于子空间维度m常小于刚度矩阵k的维度，出现了方程组总数大于未知数的情况。

针对这种情况，最常用的方法之一是最小二乘法，对Betai偏导得式（4）进而求解Betai，顺利将高维矩阵求解转化为m个方程m个未知数的方程组问题。

OpenSEES中的Krylov

Krylov-Newton基于常刚度假定认为每次迭代的雅可比矩阵均为A，并假定前m个迭代步位移增量都为本迭代步位移增量的向量子空间，分别如式（5）及式（6）所示。

将式（5）及式（6）合并可得式（7），与前述式（3）近似。式中m为子空间维度，Betai为未知量。同样引入最小二乘法来求解未知量，如式（8）所示。而最小二乘法的引入，恰好将求解f(x)=0的问题转化为求极小值min(f(x))问题（带线搜索的牛顿法同样也是求极小值问题）。由于最小二乘法仅是近似解，因此最后需通过修正的牛顿法（MNR）消除误差。

模型与实例

采用与推送【OpenSEES】浅析Newton迭代（一）：减少刚度重构工作量与减少迭代次数谁更有意义？相同的测试模型。为让每个迭代算法均各尽其能，简单补充了小算法：当分析不收敛时自动缩短积分补步长并增加最大迭代次数（点击“阅读原文”可下载，包含于“1_Function.tcl”）。