Conjugate Gradient Method Single Iterationhard

Conjugate Gradient Method Single Iteration

hard Math for ML 20-25 min

NumPy allowed · plain Python earns 10 bonus points

Loss moves downhill

The update rule changes the parameters on each step.

Open lesson →

01parameters

02prediction

03loss

04gradient

θ = 4.000loss = 16.000∂L/∂θ = 8.000

θ ← θ − 0.14 · ∂L/∂θ

Execute a single iteration of the linear Conjugate Gradient algorithm for symmetric positive-definite systems.

Related Skills

Conjugate Gradient

Task

Implement conjugate_gradient_step(A, b, x, r, p): calculate matrix-vector product A p, step size alpha = (r . r) / (p . A p), updated solution x_next = x + alpha * p, updated residual r_next = r - alpha * A p, conjugate direction factor beta = (r_next . r_next) / (r . r), and new search direction p_next = r_next + beta * p. Return {"x": list, "r": list, "p": list} rounded to 4 decimals.

Function Signature

conjugate_gradient_step(A: list[list[float]], b: list[float], x: list[float], r: list[float], p: list[float]) -> dict[str, list[float]]

Examples

Example 1: Initial 2x2 Iteration
Input: A = [[4, 1], [1, 3]]
b = [1, 2]
x = [0, 0]
r = [1, 2]
p = [1, 2]
Output: {'x': [0.25, 0.5], 'r': [-0.5, 0.25], 'p': [-0.4375, 0.375]}
Explanation: First iteration of CG algorithm.

Example 2: Diagonal Matrix Step
Input: A = [[2, 0], [0, 5]]
b = [2, 5]
x = [0, 0]
r = [2, 5]
p = [2, 5]
Output: {'x': [0.4361, 1.0902], 'r': [1.1278, -0.4511], 'p': [1.2296, -0.1967]}
Explanation: Diagonal matrix CG step.

Constraints

A is symmetric positive-definite n x n.
x, b, r, p have length n.

Python3Saved ✓

def conjugate_gradient_step(A: list[list[float]], b: list[float], x: list[float], r: list[float], p: list[float]) -> dict[str, list[float]]:

"""Compute a single iteration of the Conjugate Gradient algorithm for A x = b.

alpha = (r^T r) / (p^T A p); x_next = x + alpha * p; r_next = r - alpha * A p.

beta = (r_next^T r_next) / (r^T r); p_next = r_next + beta * p.

Return {'x': list, 'r': list, 'p': list} rounded to 4 decimals."""

# Your implementation here

pass

Case 1: Initial 2x2 Iteration

Input: A = [[4, 1], [1, 3]]
b = [1, 2]
x = [0, 0]
r = [1, 2]
p = [1, 2]

Expected: {'x': [0.25, 0.5], 'r': [-0.5, 0.25], 'p': [-0.4375, 0.375]}

Case 2: Diagonal Matrix Step

Input: A = [[2, 0], [0, 5]]
b = [2, 5]
x = [0, 0]
r = [2, 5]
p = [2, 5]

Expected: {'x': [0.4361, 1.0902], 'r': [1.1278, -0.4511], 'p': [1.2296, -0.1967]}