共轭梯度法中预条件子的优化

Optimization of Preconditioner in Conjugate Gradient Method

摘要: 为了降低方程组求解中共轭梯度法系数矩阵的条件数，提高收敛速度，常用预处理方法将原方程进行等价转化，同时预条件子既要接近原系数矩阵，又要容易求其逆矩阵。本文从寻求对角预条件子出发，用矩阵的特征值分解方法解出了预处理后系数矩阵特征值矩阵的显式表达，得到对角预条件子矩阵的最优选择，并予以证明。给出了三个p-范数预条件子，将之与常用的预条件子进行对比，实例检验表明三个p-范数预条件子的作用更优越，且使算法收敛更快。

Abstract: For decreasing the conditional number of the coefficient matrix in solving the linear equations with conjugate gradient methods and accelerating the convergence, it is common to use preconditioned methods to find the equivalent equations, whose conditional numbers are smaller. It is required that the preconditioners should be as close as possible to the original coefficient matrix and their inverse matrices can be easily computed. Starting from diagonal preconditioners, we first compute the eigenvalue decomposition of the coefficient matrix, and obtain the optimal preconditioner. However, it is of high computational complexity to do the eigenvalue decomposition. In this paper, we introduce three p-norm preconditioners to approximate the optimal preconditioner. Comparing with the existing preconditioners, the experimental results show that the proposed three diagonal p-norm preconditioners converge much faster, which demonstrates the advantages of the proposed family of preconditioners.