(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211204591.5 (22)申请日 2022.09.23 (71)申请人 中国科学院重庆绿 色智能技 术研究 院 地址 400714 重庆市北碚区水土镇水土高 新园方正大道 266号 申请人 方成玲 (72)发明人 刘江　雷超　方成玲　 (51)Int.Cl. G06F 17/16(2006.01) G06F 17/11(2006.01) (54)发明名称 基于最小残差拓展的带状线性系统的迭代 求解方法 (57)摘要 本发明公开了基于最小残差拓展的带状线 性系统的迭代 求解方法， 属于计算机矩阵求解领 域。 本方法包括以下步骤： S1： 给定 带状线性系统 的初始解， 并设定迭代求解方法的终止阈值； S2： 将带状矩阵分裂； S3： 根据结构来设定带状线性 系统关于待定对角矩阵的残差迭代格式； S4： 确 定对角线条数， 设定迭代的待定对角矩阵的格 式； S5： 根据最小化残差思想， 建立关于待定对角 矩阵中待定系数的块箭型线性矩阵方程并求解； S6： 按照残差迭代格式， 重复步骤S4～步骤S5进 行迭代计算， 直到求解结果符合终止阈值为止， 并输出求得的解。 本发明既能降低算法达到同一 精度的迭代 步数， 又能降低算法达到同一精度的 迭代时间， 适用于高效、 高精度数值求解大规模 带状线性系统。 权利要求书2页 说明书7页 附图2页 CN 115544446 A 2022.12.30 CN 115544446 A 1.基于最小残差拓展的带状线性系统的迭代求解方法， 其特征在于， 该方法包含以下 步骤： S1： 给定带状线性系统A ·x＝b的初始解x0， 并设定迭代求 解方法的终止阈值； S2： 将带状矩阵A分裂为A＝M ‑Q； S3： 根据A·M‑1的结构来设定带状线性系统关于待定对角矩阵Dk的残差迭代格式； S4： 根据带状矩阵A ·M‑1或A的非零半区域的对角线条数d， 设定第k次迭代的待定对角 矩阵Dk的格式； S5： 根据最小化残差思想， 建立关于待定对角矩阵Dk中待定系数的块箭型线性矩阵方 程， 并求解出Dk； S6： 按照残差迭代格 式， 重复步骤S4～步骤S5进行迭代计算， 直到求解结果符合迭代求 解方法的终止阈值 为止， 并输出求得的解； 其中， A为n×n的带状矩阵； x为n ×1的未知数向量； b为n ×1的偏置向量； d≥1是带状矩 阵非零半区域的对角线条数； M为n ×n的可逆矩阵； M‑1为M的逆矩阵； Dk＝diag(s1，…， sl‑1， α1， sl+1，…， s2d‑1， s1，…， sl‑1， α2， sl+1，…， s2d‑1，…)为n×n的对角矩阵， 其中， 待定系数为 s1，…， sl‑1， sl+1，…， s2d‑1和α1，…， αt， 为向上取整， l为从1到2d ‑1之间随机 选取的整数； 所述的终止阈值包含终止残差阈值RT和终止残差差分阈值RD， 当||rk||＜RT或||rk‑ rk‑1||＜RD时， 迭代中止； 其中， rk＝b‑A·xk， k≥1为迭代次数， ||||为取二范数操作， xk表示 第k次迭代的解； 所述的最小化残差思想即为求解残差二范数最小min||rk+1||的优化问题， 根据残差迭 代格式来 求解使得残差二范 数最小的待定对角矩阵Dk的待定系数。 2.根据权利要求1所述的基于最小残差拓展的带状线性系统的迭代求解方法， 其特征 在于， 步骤S2所述的带状矩阵A分裂为A＝M ‑Q的方法有雅克比迭代格式分裂(Jacobi)、 高 斯‑赛德尔迭代分裂(Gaus s‑Seidel)、 SOR迭代分裂， 或共 轭转置分裂。 3.根据权利要求1所述的基于最小残差拓展的带状线性系统的迭代求解方法， 其特征 在于， 步骤S3所述的残差迭代格式根据A ·M‑1的结构可以分为两种： (1)当A ·M‑1为带状矩 阵时， 残差迭代格式为： xk+1＝xk+M‑1·Dk·rk， rk+1＝rk‑A·M‑1·Dk·rk； (2)当A·M‑1不为带 状矩阵时， 残差迭代格式为： xk+1＝xk+Dk·M‑1·rk， rk+1＝rk‑A·Dk·M‑1·rk。 4.根据权利要求1所述的基于最小残差拓展的带状线性系统的迭代求解方法， 其特征 在于， 步骤S4所述的非零半区域的对角线条数d优先取决于带状矩阵A ·M‑1， 当A·M‑1为非 带状矩阵时， 才选择A。 5.根据权利要求1所述的基于最小残差拓展的带状线性系统的迭代求解方法， 其特征 在于， 由于待定对角矩阵Dk在每次迭代都是不同的， 不同的待定对角矩阵Dk选取不同的l， 所 产生的加速效果也是不一样的， 因而， 所述的待定对角矩阵Dk中l可以采用启发式方法选 取， 具体的为： (1)初始时刻设定启发式迭代的终止上界mi n_sum＝+∞； (2)取j∈[1， m]， 选出rk中对应位置下标Idx＝(j， m+j， 2m+j， …)的t个元素， 然后进行绝权　利　要　求　书 1/2 页 2 CN 115544446 A 2对值求和， 得到 其中m＝2d ‑1； (3)如果sum[j]＜mi n_sum， 此时， mi n_sum←sum[j]， l ←j， 其中，←为更新赋值操作； (4)重复步骤(2)～步骤(3)， 依次遍历j∈[1， m]中的所有整数， 最终可以得到待定对角 矩阵Dk对应的最优的l。 6.根据权利要求1所述的基于最小残差拓展的带状线性系统的迭代求解方法， 其特征 在于， 步骤S5的具体过程 为： (1)当A·M‑1为带状矩阵时， 设定n ×n中间系数矩阵Ar＝(ai， j)1≤i≤n， 1≤j≤n＝A·M‑1， n×1 中间系数向量vk＝(rk)T＝(vk[1]，…， vk[n])； 当A·M‑1不为带状矩阵时， 设定n ×n中间系数 矩阵Ar＝(ai， j)1≤i≤n， 1≤j≤n＝A， n×1中间系数向量vk＝(M‑1·rk)1＝(vk[1]，…， vk[n])； 其中， ()T为转置操作； (2)根据残差迭代格式， 根据最小残差的思想， 求使得残差二范数最小min||rk‑Ar· Dk·vk||成立的Dk， 令Dk的对角线向量为dk， 则根据优化理论可知dk是线性方程组VkArTArVkdk ＝VkArTrk的解， 其中Vk是对角线为向量vk的对角矩阵； (3)将线性方程组的方程位置与变元位置进行置换， 可以将其转化为块箭型线性矩阵 方程 的形式； 其中， 变元向量s＝(s1，…， sl‑1， sl+1，…， s2d‑1)T， 变元向量α ＝( α1，…， αt)T， 为块 箭型矩阵， 为偏置向量， B为(2d ‑2)×(2d‑2)的矩阵， Y为t ×(2d‑2)的矩阵， Q为(2d ‑2) ×t的矩阵， I为t ×t的单位矩阵， e1为(2d‑2)×1的列向量， e2为t×1的列向量， 都可以由方 程位置与变元位置的置换推导得 出； (4)根据舒尔补(Sc hur Complement)方法求 解块箭型线性矩阵方程的解： 其中， C＝B ‑Q·Y。权　利　要　求　书 2/2 页 3 CN 115544446 A 3