Finite Difference Matrix

Many matrices in scientific computing contain mostly zeros, particularly those arising from the discretisation of partial differential equations (PDEs). Here we will construct a sparse matrix using scipy.sparse that is derived from the finite difference discretisation of the Poisson equation. In 1D, Poisson equation is

The central FD approximation of $u_{xx}$ is:

We will discretise $u_{xx} = 0$ at $N$ regular points along $x$ from 0 to 1, given by $x_1$, $x_2$:

Using this set of point and the discretised equation, this gives a set of $N$ equations at each interior point on the domain:

where $v_i \approx u(x_i)$.

To solve these equations we will need additional equations at $x=0$ and $x=1$, known as the boundary conditions. For this example we will use $u(x) = g(x)$ at $x=0$ and $x=1$ (also known as a non-homogenous Dirichlet bc), so that $v_0 = g(0)$, and $v\_{N+1} = g(1)$, and the equation at $x_1$ becomes:

and the equation at $x_N$ becomes:

We can therefore represent the final $N$ equations in matrix form like so:

The relevant sparse matrix here is $A$, given by

As you can see, the number of non-zero elements grows linearly with the size $N$, so a sparse matrix format is much preferred over a dense matrix holding all $N^2$ elements!

For more on the Finite Difference Method for solving PDEs:

K. W. Morton and D. F. Mayers. Numerical Solution of Partial Differential Equations: An Introduction. Cambridge University Press, 2005.