Implement the Conjugate Gradient Method for Solving Linear Systems

HardLinear Algebra

Task: Implement the Conjugate Gradient Method for Solving Linear Systems

Your task is to implement the Conjugate Gradient (CG) method, an efficient iterative algorithm for solving large, sparse, symmetric, positive-definite linear systems. Given a matrix A and a vector b, the algorithm will solve for x in the system $Ax = b$ .

Write a function conjugate_gradient(A, b, n, x0=None, tol=1e-8) that performs the Conjugate Gradient method as follows:

A: A symmetric, positive-definite matrix representing the linear system.
b: The vector on the right side of the equation.
n: Maximum number of iterations.
x0: Initial guess for the solution vector (the zero vector if not given).
tol: Stop as soon as the residual norm $\lVert b - Ax \rVert_2$ is below tol.

The function should return the solution vector x.

Example:

Input:

A = np.array([[4, 1], [1, 3]])
b = np.array([1, 2])
n = 5

print(conjugate_gradient(A, b, n))

Output:

[0.09090909, 0.63636364]

Reasoning:

The Conjugate Gradient method is applied to the linear system Ax = b with the given matrix A and vector b. The algorithm iteratively refines the solution to converge to the exact solution.

Learn About topic

Contributors:

paddywardle

Contribute

Task: Implement the Conjugate Gradient Method for Solving Linear Systems

Ax = b

Write a function conjugate_gradient(A, b, n, x0=None, tol=1e-8) that performs the Conjugate Gradient method as follows:

A: A symmetric, positive-definite matrix representing the linear system.

b: The vector on the right side of the equation.

n: Maximum number of iterations.

x0: Initial guess for the solution vector (the zero vector if not given).

tol: Stop as soon as the residual norm

\lVert b - Ax \rVert_2

is below tol.

The function should return the solution vector x.