Conjugate Gradient Step on a Quadratic

Problem

Perform one conjugate gradient step on the quadratic f(x) = 0.5 * x^T A x - b^T x.

Compute Ap = A p, then alpha = (r dot r) / (p dot Ap), x_new = x + alpha * p, r_new = r - alpha * Ap, and beta = (r_new dot r_new) / (r dot r). Return [x_new, r_new, p_new] with p_new = r_new + beta * p.

Hint

alpha comes from r dot r over p dot Ap; update r before computing beta.

Test cases

case 1

in: [[0,0],[1,2],[1,2],[[4,1],[1,3]],[1,2]]

expected: [[0.25,0.5],[-0.5,0.25],[-0.4375,0.375]]

case 2

in: [[1,1],[0,2],[0,2],[[2,0],[0,2]],[2,4]]

expected: [[1,2],[0,0],[0,0]]

case 3

in: [[0.5,-0.5],[1,1],[1,1],[[3,0],[0,2]],[1,-2]]

expected: [[0.9,-0.09999999999999998],[-0.20000000000000018,0.19999999999999996],[-0.16000000000000014,0.24]]

Starter codePython

def cg_step(x, p, r, A, b):
    # Returns [x_new, r_new, p_new]
    # Your code here
    pass

3 test cases · run your code against them in the editor