Skip to content

w03-g02-conjugate-gradient

Conjugate Gradient

The goal of this exercise is to find the value of x^{T}=(x, y) which minimizes the quadratic function S(\boldsymbol{x}) defined by the equation:

S(\boldsymbol{x}) = \boldsymbol{x}^{T} \left(\begin{array}{cc}8 & 2 \\ 2 & 6 \end{array}\right)\boldsymbol{x} - \boldsymbol{x}^{T} \left( \begin{array}{c}1 \\ 2\end{array}\right)

Minimization of S(x,y)

The conjugate gradient (CG) method is one of the many known iterative techniques for solving sparse symmetric definite systems of linear equations. For this exercise, implement the CG method to find the minimizer of the quadratic function

S(\boldsymbol{x}) = \dfrac{1}{2}\boldsymbol{x}^{T}\boldsymbol{A}~\boldsymbol{x}-\boldsymbol{x}^{T}\boldsymbol{b}

The minimizer of the above function is also the solution of the linear system of equation

\boldsymbol{A}~\boldsymbol{x} = \boldsymbol{b}

Please refer to the following wikipedia link for a detailed explaination of CG method along with the algorithm. https://en.wikipedia.org/wiki/Conjugate_gradient_method

Implementation

Your code should be named conjugate_gradient.cpp and be placed into the tehpc/basics/ directory. It should have following functionalities and variables for the implementation of CG method:

  1. A for loop, that iterates for i = 1,2,3,...,max_iter where max_iter is the maximum number of iterations to reach the convergence.

  2. A check that can be performed on the values of residual r_i, at each iteration step i, to tell when it is below the tolerance value \epsilon. Print a message, displaying the values of (x,y), when convergence is succesfully reached within the given number of iterations.

  3. Print a error message, displaying Convergence not reached when number of iterations exceed the maximum iterations max_iter

Use the following variable naming:

max_iter for the maximum number of iterations to reach the convergence

epsilon tolerance value acceptable for a converged solution

x_prev a 1D array that stores the values of (x, y) at i-1 step

x_next a 1D array that stores the values of (x, y) at i step

r_prev a 1D array that stores the values of residual r at i-1 step

r_next a 1D array that stores the values of residual r at i step

A a 2D array to store the second derivative of function S(x,y)

Notes:

Compile and run your code by:

  1. going into the tehpc/build/basics/ folder
  2. compile with the following command: g++ -Werror -Wpedantic -g -o conjugate_gradient ../../basics/conjugate_gradient.cpp
  3. run code with ./conjugate_gradient