Civil Engineering Reference
In-Depth Information
until we reach the equation. Now that
y
has been found‚ solving
U
x
=
y
is similarly easy. Since
U
is upper triangular‚ one may start from the last
equation to find then proceed to the second last equation‚ and so on until
the first equation‚ to find the in
backward
order‚ and this explains why the
procedure is referred to as backward substitution.
Example
For the system of equations (2.61)‚ we solve
L
y
=
b
using forward
substitution to obtain the elements of
y
as Next‚
applying backward substitution we find the elements of
x
from
U
x
=
y
as
Pivoting
During the process of LU factorization‚ it is very possible that a diagonal
element with a value of zero may be encountered. If so‚ this would result
in a division by zero. This may be avoided by the use of
pivoting‚
whereby
by exchanging the rows in which equations are placed‚ or by exchanging the
columns that represent any given variable‚ a nonzero diagonal element‚ referred
to as the pivot‚ may be obtained‚ and the processing can continue.
For instance‚ for the system of equations
the first diagonal element is zero. One may exchange the first two equations to
obtain
which now has a nonzero at the first diagonal element. Alternatively‚ the first
and second variables may be swapped to obtain
In general‚ it is possible to perform a sequence of row and column exchanges
to use any arbitrary nonzero in the matrix as a pivot. the element at the (3‚3)
position in the original matrix may be brought to the first diagonal through a
combination of a row exchange and a column exchange to obtain:
For efficiency‚ the choice of pivots may be restricted to the elements of the
same column (“column pivoting”)‚ elements of the same row (“row pivoting”)‚
or elements along the diagonal (“diagonal pivoting”).
Computational complexity issues
