Chebyshev Iteration Step

Problem

Perform one Chebyshev (optimal Richardson) iteration step for A*x = b given the spectral interval [lam_min, lam_max] of A.

The optimal constant step is tau = 2 / (lam_min + lam_max). Return [tau, x + tau*(b - A*x)].

Hint

The optimal step is the reciprocal of the midpoint of the spectrum.

case 1

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

expected: [0.25,[0.25,0.5]]

case 2

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

expected: [1,[2,4]]

case 3

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

expected: [0.5,[0,0]]

case 4

in: [[[3,0],[0,5]],[3,5],[0,0],3,5]

expected: [0.25,[0.75,1.25]]

Starter codePython

def chebyshev_step(A, b, x, lam_min, lam_max):
    # Your code here
    pass

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