Efficient And Fast Algorithms For Linear And Nonlinear Systems With Toeplitz-Plus-Diagonal Structure

The fractional diffusion equation is widely used to model anomalous diffusion phenomena in finance,biology,image processing and other fields.Compared with the integer-order partial differential equation,this kind of equation can provide a more adequate and accurate description of the anomalous diffusion process.Therefore,there are some scientific merits in studying the fractional diffusion equations.The closed-form analytical solution of the fractional diffusion equation is rarely available,hence learning the numerical methods to get an approximation of the solution is necessary.Direct solutions typically demand significant amounts of storage and take a long time to process.Therefore,new iterative algorithms must be designed and built to accelerate computing efficiency.When the fractional diffusion equation is properly discretized by the finite difference,its coefficient matrix has a diagonal-plus-Toeplitz structure.In this paper,we first consider the trigonometric transform based splitting of Toeplitz matrix T:T=T_C+T_S and the splitting of coefficient matrix.Using the idea of parameter acceleration,we construct the acceleration of quasi-Toeplitz trigonometric transform splitting(AQTTTS)method for linear system with diagonal-plus-Toeplitz structure.Theoretical analysis shows that when the parameters are under certain conditions,the linear iterative method converges to the unique solution of the linear system.The upper bound of the spectral radius of the iterative matrix is analyzed and derived,so that the optimal parameters can be selected to minimize the upper bound of the spectral radius so as to speed up the iterative process.Because the linear and the nonlinear terms are well separated and the former is strongly dominant over the latter,the Picard-AQTTTS and nonlinear AQTTTS-like iterative methods are proposed and applied to solve weakly nonlinear systems with diagonal-plus-Toeplitz structure by comprehensively considering the construction ideas of nonlinear iterative method and linear iterative method.The convergence of the constructed internal and outer iteration methods is theoretically analyzed.Numerical results show that these new methods are effective.In addition,based on the relaxed splitting of matrix T_C and T_S,a relaxed quasi-Toeplitz triangulation splitting(RQTTTS)method which is suitable for linear system with diagonalplus-Toeplitz structure is constructed.The convergence of the constructed RQTTTS method and the selection of optimal parameters are considered.Then the Picard-RQTTTS and nonlinear RQTTTS-like iterative methods are constructed by combining the RQTTTS method as an internal iterative method with the nonlinear external iterative method.Conduct convergence analysis and establish local convergence theorem for these iterative methods.Theoretical analysis and numerical experiments have demonstrated that the developed methods are practical and successful in solving weakly nonlinear system,and when compared to other iterative methods,they require significantly less CPU time and fewer iterative steps.