Thursday, May 1, 2014

Jacobian method for solving linear systems

Jacobian method for solving linear systems

Jacobian method is an iterative method for solving linear systems.

I have no idea why this works, but you have x on both sides, it looks like an iterative approach is possible:

And the error for the ith iteration $e_{(i)}$ can converge to zero, i.e. the ith solution $x_{(i)}$ can converge to the true solution, under the condition that $\max(|\lambda_i|) < 1$, where $\lambda_i$ is the ith eignevalue of $B$. And $\max(|\lambda_i|)$ is called spectral radius of $B$.

The following demonstration in matlab shows how the Jacobian method works by solving the following system:

\begin{align*} \begin{pmatrix} 3 & 2 \\ 2 & 6 \\ \end{pmatrix} x &= \begin{pmatrix} 2 \\ -8 \end{pmatrix} \end{align*}
Solving Ax = b with Jacobian method (matlab code)
Click to toggle code (may have to try twice)
a = [3 2; 2 6];
b = [2; -8];
d = diag(diag(a));
e = a - d;
invd = inv(d);
B = - invd * e;
eig(B);
z = invd * b;
x = rand(2, 1);
xtrack = x;
while 1
    x1 = B*x + z;
    xtrack = horzcat(xtrack, x1);
    xdiff = abs(x1 - x);
    if max(xdiff(:)) < 0.00001
        x = x1;
        break
    end
    x = x1;
end
plot(xtrack(1,:), xtrack(2,:))
hold on
scatter(xtrack(1,:), xtrack(2,:))

0 comments: