Guess, Correct, Repeat

Elimination solves $A\mathbf{x} = \mathbf{b}$ in one pass. A different family of solvers never eliminates anything: it starts from a guess and improves it, again and again, until the guess stops changing. Each improvement is cheap, which is why large solvers often work this way.

The idea is to rearrange each equation so that one unknown stands alone. Equation $i$ ,

a_{i0}x_0 + a_{i1}x_1 + \dots + a_{i,n-1}x_{n-1} = b_i,

becomes

x_i = \frac{b_i - \sum_{j \ne i} a_{ij}\,x_j}{a_{ii}}

If you knew every other unknown, this would hand you $x_i$ exactly. You don't, so you plug in your current guess for them and get a better value for $x_i$ . Doing that once for every unknown, in the order $x_0, x_1, \dots, x_{n-1}$ , is one sweep.

There are two classic ways to run a sweep. They differ in just one thing: where the values of the other unknowns come from.

method	when computing $x_i$ , the other unknowns are taken from…
Jacobi	the guess as it stood at the start of this sweep. New values only take over once the sweep is finished.
Gauss–Seidel	the latest values. Any $x_j$ already updated earlier in this sweep is used straight away.

For example, take $4x_0 + x_1 = 9$ and $2x_0 + 5x_1 = 9$ with the starting guess $(0, 0)$ . Both methods begin with $x_0 = 9/4 = 2.25$ . Jacobi then computes $x_1 = (9 - 2 \cdot 0)/5 = 1.8$ from the old $x_0$ , while Gauss–Seidel computes $x_1 = (9 - 2 \cdot 2.25)/5 = 0.9$ from the new one.

Task: write sweep_solve(A, b, x0, sweeps, method).

A is an $n \times n$ list of lists, and b and x0 are lists of length $n$ . x0 is the starting guess.
Perform exactly sweeps sweeps (possibly 0) with method, which is either "jacobi" or "gauss-seidel".
Return the final guess as a list of floats, each rounded to 4 decimal places. With sweeps = 0 that is just x0, as floats.

Every diagonal entry $a_{ii}$ in the tests is non-zero, and every test system is one where both methods close in on the true solution.

Guess, Correct, Repeat

Examples

Hints