594 Appendix A
corresponding to neighbouring or identical grid points. In two dimensions with a
grid constanthwe obtain
∇^2 ψ(r)→1
h^2(ψi+1,j+ψi−1,j+ψi,j+ 1 +ψi,j− 1 − 4 ψi,j). (A.118)In numerical problems involving sparse matrices, it usually pays off to exploit the
sparseness: this enables us in many cases to reduce the effort involved in solving
matrix problems fromO(N^3 )toO(N).
As an example, let us consider a tridiagonal matrix. This arises when discretising
the one-dimensional Laplace operator on a grid with fixed boundary conditions. The
tridiagonal matrix has the form
A=
a 1 b 1 0 ··· 000
c 2 a 2 b 2 ··· 000
..
...
.
..
.
..
.
..
.
..
.
..
.
000 ··· cN− 1 aN− 1 bN− 1
000 ··· 0 cN aN
, (A.119)
and we want to solve the equationAx=d. This is done as in the previous sub-
section, by first zeroing the lower diagonal followed by backward substitution.
Implementation is straightforward. Only subdiagonal elements are to be eliminated
and there is only one candidate row to be subtracted off the row containing that
subdiagonal element: the row just above it. All steps amount to orderN.
Dedicated algorithms exist for matrices with different patterns (e.g. band-
diagonal, scattered, striped) of nonzero elements. There exist also methods which
rely exclusively on simple matrix operations such as a matrix–vector multiplication.
You only have to supply an efficient routine for multiplying the matrix under con-
sideration with an arbitrary vector to such a sparse matrix routine. An example
is the conjugate gradient method for solving the problemAx = b.Wehave
encountered the conjugate gradient method for minimising an arbitrary smooth
function inAppendix A4, and as a sparse-matrix method inAppendix A7.2.
A8.2 Matrix diagonalisationWe now turn to another important problem in linear algebra: that of finding the
eigenvalues and eigenvectors of a matrixA. This problem is commonly referred to
as theeigenvalue problemfor matrices. Expressing the matrix with respect to the
basis formed by its eigenvectors, it assumes a diagonal form. In physics, solving the
eigenvalue problem for general operators occurs frequently (solving the stationary
Schrödinger equation is an eigenvalue problem for example) and in computational
physics, it is usually transformed into matrix form in order to solve it efficiently in
a computer.