Skip to content

Mathematics Qualifying Exam Question Bank

Department of Mathematics

Question

Math 6610 • Analysis of Numerical Methods I

Spring 2016 • Question 4

Question

Math 6610 • Analysis of Numerical Methods I Spring 2016 • Question 4

CG Method

a) Formulate the Conjugate Gradient (CG) algorithm for the solution of the linear system \(Ax=b\), where \(A\in \mathbb {R}^{n\times n}\) is symmetric positive definite matrix.

b) Show that for any initial guess \(x_0\in \mathbb {R}^n\), Conjugate Gradient algorithm converges to the solution \(x\) of the linear system \(Ax=b\) in at most \(n\) steps.

Raw LaTeX

{CG Method}

\textbf{a)} Formulate the Conjugate Gradient (CG) algorithm for the solution of
the linear system \(Ax=b\), where \(A\in\R^{n\times n}\) is symmetric positive
definite matrix.

\textbf{b)} Show that for any initial guess \(x_0\in\R^n\), Conjugate Gradient
algorithm converges to the solution \(x\) of the linear system \(Ax=b\) in at most
\(n\) steps.

Topic Tags

Cholesky Factorization and SPD Matrices Iterative Methods for Linear Systems Linear Programming and Optimization