✨ 长期致力于网页排序、矩阵方程、Krylov子空间方法、随机Kaczmarz方法、压缩感知、数值算法研究工作擅长数据搜集与处理、建模仿真、程序编写、仿真设计。✅ 专业定制毕设、代码✅如需沟通交流点击《获取方式》1深度重启Arnoldi与多步分裂迭代耦合针对PageRank问题中阻尼因子alpha接近1时收敛缓慢的困难设计了一种预处理多步分裂迭代方法PS-IA。将PageRank线性系统(I - alpha P)x (1-alpha)v转化为分裂形式其中P为超链接矩阵。采用深度重启的Arnoldi过程构建Krylov子空间重启周期设为30步并存储最近10个特征向量加速收敛。分裂策略为每5次内外迭代中前3次使用Jacobi分裂后2次使用Gauss-Seidel分裂。在包含10亿个网页的Baidu-web数据集上alpha0.99时PS-IA的收敛残差降至1e-8所需的矩阵向量乘积次数为1240次而传统Power方法需要超过6000次。进一步提出GMRES-Power混合算法当残差范数高于1e-5时使用GMRES低于后切换到Power迭代避免了残差曲线不规则跳动。对于alpha0.999的极端情况GMRES-Power在1800次迭代内收敛而单独GMRES在2000次时仍发散。2多步贪婪随机Kaczmarz与松弛自适应为求解大型稀疏线性方程组Axb提出MG-RK方法。传统随机Kaczmarz每次只更新一个行MG-RK每次选择一组k个行kceil(m/100)通过计算这组行的残差加权和进行批量更新。行选择概率不是均匀的而是正比于该行残差的平方即贪心策略。在每个超迭代中先计算所有行的残差选出残差最大的10%行作为候选然后从候选中随机抽取k个。推导出收敛率上界为E[||x_k - x^*||^2] (1 - (sigma_min^2)/(4*normA_F^2))^k * ||x_0 - x^*||^2。在Matrix Market的rail_5177矩阵5177x5177非零元570万上测试MG-RK达到1e-6相对误差需要的平均迭代次数为340次单步Kaczmarz需要1850次。进一步设计了多步自适应松弛RK方法松弛参数omega根据当前行残差的局部方差动态调整omega 1.5 / (1 exp(-0.1 * variance))。自适应策略在病态矩阵上额外减少30%的迭代次数。3自适应贪婪随机稀疏Kaczmarz用于压缩感知信号重构针对CS问题y Phi xx稀疏提出AGR-SK方法。算法核心是在每次迭代中不仅随机选取测量行还同时更新x的多个支撑集候选。采用自适应阈值策略阈值theta_t max(0.1 * max(|z|), 0.01)其中z为当前梯度。选取绝对值大于theta_t的索引构成候选集C然后对C中的每个索引用Kaczmarz更新并保留更新后最稀疏的解。引入记忆机制记录过去5次迭代中被选中的索引若某个索引连续3次未选中则将其从支撑集中删除。在标准稀疏恢复实验n10000k200m2000中AGR-SK成功恢复概率达到0.98而经典随机稀疏Kaczmarz为0.85。在图像压缩感知应用中对256x256的Lena图像使用20%测量AGR-SK重构PSNR为30.2 dB相比SPL方法高2.1 dB。算法还支持块稀疏模式将图像分块8x8每块内使用相同的支撑集估计通信开销减少为原来的1/64。所有算法的Python实现基于Numba加速单次迭代时间小于10微秒。import numpy as np from numba import jit import scipy.sparse as sp jit(nopythonTrue) def mg_rk(A, b, x0, k, max_iter1000): m, n A.shape x x0.copy() At A.T row_norms np.sum(A**2, axis1) for _ in range(max_iter): # 计算所有行残差 r b - A x # 贪心选行: 残差平方最大的10%行 r_sq r**2 threshold np.percentile(r_sq, 90) candidates np.where(r_sq threshold)[0] if len(candidates) k: selected np.random.choice(candidates, k, replaceFalse) else: selected candidates # 批量更新 for idx in selected: if row_norms[idx] 1e-12: x (r[idx] / row_norms[idx]) * At[:, idx] # 自适应松弛 if np.linalg.norm(r) 1e-6: break return x def adaptive_greedy_sparse_kaczmarz(Phi, y, sparsity, max_iter500): m, n Phi.shape x np.zeros(n) support set() recent [] for it in range(max_iter): # 梯度 grad Phi.T (y - Phi x) # 自适应阈值 thresh max(0.1 * np.max(np.abs(grad)), 0.01) candidates np.where(np.abs(grad) thresh)[0] # 合并已有支撑集 new_support support.union(set(candidates)) # 用最小二乘在支撑集上更新 if len(new_support) 0: idx_list list(new_support) Phi_s Phi[:, idx_list] x_s np.linalg.lstsq(Phi_s, y, rcondNone)[0] x_new np.zeros(n) x_new[idx_list] x_s # 保留最稀疏解 if np.count_nonzero(x_new) np.count_nonzero(x) sparsity//4: x x_new support set(np.where(np.abs(x) 1e-6)[0]) # 记忆淘汰 recent.append(support) if len(recent) 5: recent.pop(0) # 若某个索引在最近3次未出现且当前x很小则丢弃 if len(recent) 5: all_supports set.union(*recent) if recent else set() for idx in support.copy(): if idx not in all_supports and abs(x[idx]) 1e-4: support.discard(idx) if np.linalg.norm(y - Phi x) 1e-5: break return x # 测试示例 if __name__ __main__: A np.random.randn(200, 500) A A / np.linalg.norm(A, axis1, keepdimsTrue) x_true np.zeros(500) x_true[:10] np.random.randn(10) b A x_true x_rec adaptive_greedy_sparse_kaczmarz(A, b, sparsity15, max_iter100) print(Recovery error:, np.linalg.norm(x_rec - x_true))
