Conjugate gradient Method
Numerical Methods for PDEs
Spring 2007
Jim E. Jones
Computational Science and Engineering Seminar This Friday, March 23, 3 pm, S402
Dr. Charles Fulton
Computation of Points of Spectral Concentration for One-Dimensional Schroedinger Equations on the Half Line
Points of Spectral Concentration are points where the spectral density function has local maxima, and can be computed using recent algorithms for numerical approximation of spectral density functions for the continuous range of the spectrum. In Quantum Chemistry applications these points are related to resonant energies of atoms and molecules.
Equivalent Problems
Solve Ax=b, where A is symmetric positive definite (SPD)
Find x to minimize the quadratic form
Steepest Descent
Minimize f in the direction of –f '(x)=r=b-Ax
Choose a to minimize f
Steepest Descent Convergence Problems
Successive search directions (gradients or residuals) are orthogonal. So for a 2x2 matrix, search directions point in one of 2 directions. The method can take a long zig-zag path to the solution.
Trond Hjorteland : http://trond.hjorteland.com/thesis/node26.html
Building the Conjugate Gradient Method:
A-othogonal search directions
Let's choose a set of search directions {p(0),p(1), …,p(n-1)}
which are A-orthogonal, that is
Then the kth step of our method will be to minimize f in the
direction p(k-1)
We'll use each direction only once.
Building the Conjugate Gradient Method:
picking a to minimize f
Subtracting true solution x from both sides
Choose a to minimize f
Building the Conjugate Gradient Method:
picking a to minimize f (continued)
Subtracting true solution x from both sides
Choose a to minimize f
Building the Conjugate Gradient Method:
convergence in n steps
In the kth step we force the error, e(k), to be A-orthogonal to the (k-1)th search direction, p(k-1). Since future search directions are A-orthogonal to p(k-1) , the error remains A-orthogonal to p(k-1). We have for all j < k

下一页