Gradient Methods
摘要
This chapter introduces several fundamental gradient-based iterative methods for solving linear systems and optimization problems, including the conjugate gradient method, the Jacobi method, and the heavy ball method. We begin with the conjugate gradient method for symmetric positive definite matrices, presenting the derivation of the iteration formulas, orthogonality properties, and the underlying vector space structure. The method is shown to converge to the exact solution in at most m steps for an m-dimensional system. Next, we discuss one-step iterative methods, including the Jacobi and gradient descent methods, and analyze their convergence using eigenvalue techniques. The concept of a learning rate is introduced, and we formulate a minimax optimization problem to determine the optimal learning rate for the fastest convergence. Finally, the chapter extends these ideas to two-step methods, or heavy ball methods, which incorporate a momentum term to accelerate convergence. We analyze the spectral radius of the associated iteration matrix and present a minimax problem to optimize both the learning rate and momentum parameter.