Conjugate Gradient Step from Residual

Problem

Perform one iteration of the conjugate gradient method for A*x = b starting from x.

Compute the residual r = b - A*x, set the direction p = r, and the step alpha = (r . r) / (p . A*p). Return x + alpha*p. If p . A*p is 0, return x unchanged.

Hint

The first conjugate direction is just the residual; the optimal step minimizes the energy norm.

Test cases

case 1

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

expected: [0.25,0.5]

case 2

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

expected: [1,2]

case 3

in: [[[1,0],[0,1]],[1,1],[0,0]]

expected: [1,1]

case 4

in: [[[4,1],[1,3]],[5,4],[1,1]]

expected: [1,1]

Starter codePython

def conjugate_gradient_step(A, b, x):
    # Your code here
    pass

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