Solving Systems of Linear Equations

Solving systems of linear equations
See, in addition to regular course material,
sections 2.1-2.5 of our supplemental book Numerical
Computing in Matlab by Cleve Moler.

e.g.

Suppose can write A as product of lower L and upper U triangular matrices:

Ax = b -> LUx = b
Let
y = Ux (1)
->
Ly = b (2)

Solve (2) by forward substitution :

Then, solve (1) by backward-substition, exactly as above.

First step in finding L and U : recall matrix-matrix multiplication

SPECIAL CASE:

In general, multiplying by

Example of LU decomposition:

MATLAB IMPLEMENTATION: backslash \
operator :

To solve Ax = b, using a hierarchy of methods ,
including LU decomposition and forward
/ back substitution:

x = A \ b
>> A = [2 1 1 ; 4 3 3 ; 8 7 9]
A =

>> b=[1 ; 2 ; 3]
b =
1
2
3
\newpage
>> x=A\b

x =
0.500000000000000
0.500000000000000
-0.500000000000000

If have a new b, implement again:

>> b=[3 ; 3 ; 3]
b =
3
3
3
>> x=A\b
x =
3
-3
0

To generate L, U, P matrices: [L,U,P]=lu(A)

[L,U,P]=lu(A)

b =
3
3
3

>> y=L\(P*b)
y =
3.0000
2.2500
0

>> x=U\y
x =
3
-3
0

To generate L, U matrices, where L is a
permuted version of a lower -triangular matrix
(can still forward-solve in O(N²))

>> [L,U]=lu(A)

LUx = b -> solve Ly = b
b =
3
3
3

>> y=L\b
y =
3.0000
2.2500
0
solve Ux = y
>> x=U\y
x =
3
-3
0