A8 Linear algebra problems 593redundant and we are allowed to put the diagonal elements ofLequal to 1. In that
case we have
a 11 a 12 ··· a 1 N
a 21 a 22 ··· a 2 N
..
...
.
..
.
aN 1 aN 2 ··· aNN
=
10 ··· 00
l 21 1 ··· 00
l 31 l 32 ··· 00
..
...
.
..
.
..
.
lN−1,1 lN−1,2 ··· 10
lN 1 lN 2 ··· lN,N− 1 1
u 11 u 12 ··· u1,N− 1 u 1 N
0 u 22 ··· u1,N− 1 u 2 N
..
.0..
.
..
.
..
.0
..
.
..
.
00 ··· uN−1,N− 1 uN−1,N
00 ··· 0 uNN
,
(A.115)
lijanduijbeing the matrix elements ofLandUrespectively. The decomposition
matricesLandUare now easily determined: multiplying the first row ofLwith
the columns ofUand putting the result equal toa 1 iit is found that the first row of
Uis equal to the first row ofA. We then proceed, determiningl 21 by multiplying
the second row ofLwith the first column ofU, and then finding the elements of
the second row ofUand so on.
Having theLUdecomposition forA, it is easy to solve for an unknown vectorx
in the linear equation(A.110). First we search for the vectoryobeying
Ly=b (A.116)and then for a vectorxwhich satisfies
Ux=y. (A.117)UsingA=LU, it then immediately follows thatAx=b. Both problems can be
solved using back-substitution, and thus require onlyO(N^2 )calculations [finding
LandUrequiresO(N^3 )steps].
Sparse matricesDifferential operators, which frequently occur in physics, can be discretised on a
finite difference grid, leading to the differential operator being represented by a
sparsematrix: the overwhelming majority of the matrix elements are equal to zero.
A typical example is the discrete Laplacian mentioned previously in the context
of partial differential equations. There, space was discretised on a grid and the
discrete Laplacian coupled nearest neighbour points on the grid only, so that the
matrix representation of this operator contains only nonzero elements for indices