Defining a big matrix for iterative algorithm

I'll illustrate with a smaller example, using the Jacobi method. Since the matrix is sparse it makes sense to use the SparseArray structure from the Wolfram Language.

a = b = 10.;
n = 16;
mat = SparseArray[{{i_, i_} -> a, {i_, j_} /; j == i - 1 :> 
     1., {i_, j_} /; j == i + 1 :> 1., {i_, j_} /; j == i + 2 :> 1/b}, n];
rhs = N@Range[n];

For the iterations we separate the (dominant) diagonal and the rest of the matrix.

diag = Normal[Diagonal[mat]];
rest = mat - DiagonalMatrix[diag];

We'll initialize a result and do a few Jacobi iterations.

x[0] = ConstantArray[0., n];
Do[x[j] = 1/diag*(rhs - rest.x[j - 1]), {j, 4}];

What is this approximated result now?

(* In[512]:= *)x[4]

(* Out[512]= {0.0809433, 0.1635632, 0.2460271, 0.328511, 0.4109949, \
0.4934788, 0.5759627, 0.6584466, 0.7409305, 0.8234144, 0.9059, \
0.988435, 1.071278, 1.15244, 1.2357, 1.47554} *)

Here is what a direct linear solver gives.

soln = LinearSolve[mat, rhs]

(* Out[518]= {0.0811406188159, 0.163937166886, 0.24656644955, \
0.329212627692, 0.411857099219, 0.494501743134, 0.577146369797, \
0.659790996402, 0.742435624897, 0.825080412827, 0.90772341803, \
0.990368288034, 1.07317118838, 1.15422513249, 1.23694695631, \
1.47630530437} *)

We can see they are already not too far apart.

Norm[x[4] - soln]

(* Out[522]= 0.00519376049093 *)

A better iteration would use e.g. FixedPoint and stop when the change is less than some epsilon.

By the way, this can be carried out in exact arithmetic as well. Expect large numerators and denominators...


New Method

n = 100;
method2[n_] := SparseArray[{
 {i_, i_} -> a,
 {i_, j_} /; (i == j + 1 || i == j - 1) -> 1,
 {i_, j_} /; i == j - 2 -> 1/b},
 {n, n}
]

method1[n].Array[x, n] // RepeatedTiming;
method2[n].Array[x, n] // RepeatedTiming;
{#[[;; , 1]], SameQ @@ #[[;; , 2]]} &@Out[{-2, -1}]

{{0.020, 0.0062}, True}

Original Method

n = 10;
method1[n_] := Table[
 Which[i == j, a, i == j + 1, 1, i + 1 == j, 1, i + 2 == j, 1/b, True, 0],
 {i, n}, {j, n}
];
method1[n].Array[x, n] // TableForm
(* a x[1]+x[2]+x[3]/b
x[1]+a x[2]+x[3]+x[4]/b
x[2]+a x[3]+x[4]+x[5]/b
x[3]+a x[4]+x[5]+x[6]/b
x[4]+a x[5]+x[6]+x[7]/b
x[5]+a x[6]+x[7]+x[8]/b
x[6]+a x[7]+x[8]+x[9]/b
x[7]+a x[8]+x[9]+x[10]/b
x[8]+a x[9]+x[10]
x[9]+a x[10] *)

As for the resources on iterative methods, I'll keep looking.


An alternative way to construct a SparseArray using Band:

sa[n_] := SparseArray[{Band[{1, 1}] -> a, 
     Band[{2, 1}] -> 1, 
     Band[{1, 2}] -> 1,
     Band[{1, 3}] -> 1/b},
   {n, n}]

Array[x, 10] # & /@ sa[10] // MatrixForm // TeXForm

$\small\left( \begin{array}{cccccccccc} a x(1) & x(2) & \frac{x(3)}{b} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x(1) & a x(2) & x(3) & \frac{x(4)}{b} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & x(2) & a x(3) & x(4) & \frac{x(5)}{b} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & x(3) & a x(4) & x(5) & \frac{x(6)}{b} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & x(4) & a x(5) & x(6) & \frac{x(7)}{b} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & x(5) & a x(6) & x(7) & \frac{x(8)}{b} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & x(6) & a x(7) & x(8) & \frac{x(9)}{b} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & x(7) & a x(8) & x(9) & \frac{x(10)}{b} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & x(8) & a x(9) & x(10) \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & x(9) & a x(10) \\ \end{array} \right)$

Note: Using Band is faster than method2 in ThatGravityGuy's answer:

n = 100;
sa[n].Array[x, n]; // RepeatedTiming// First

0.00051

method2[n].Array[x, n]; //RepeatedTiming// First

0.0071