0 ratings0% found this document useful (0 votes) 36 views14 pagesDirectmethod Sys Eq
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here.
Available Formats
Download as PDF or read online on Scribd
Chapter 3
Linear System of Algebraic
Equations
Consider a system of n linear algebraic equations in n unknowns
Myre + yay + +++ + Ainity = by
ayy + agyta 4 Agyty = ba
yyy + gia ++ + dyn = by
where aij, 7 = 1,2,....n, 7 = 1,2,...yn are the known coofficients, b;, ¢ =
1,2,....n are the known right hand side values and 2, i = 1,2,...,n are the
unknowns to be determined
In matrix notation,
Ar =,
where,
ay ay By a by
an an aay, ™ ba
A= z= and b=
an Ona Oy Zn by
30 Numerical Methods
* The matrix [Al}], obtained by appending the column 6 to the matrix A is called
the augmented matrix. That is
a ay = aie | by
an ae im | ba
(ay = |S“ “
dna ta 2+ an | On
1. The system of equations is consistent (has at least one solution), if
rank(A) = rank[A|b] =r
@ ifr =n, then the system has unique solution,
¢ ifr pR; or R; © Ri ~ pR;
Note: These row operations change the form of A, but do not change the row-rank
of A
3. Gauss Elimination Method: The method is based on the idea of reducing
the given system of equations Ax = 6, to an upper triangular system of equations
Us: — 2, using elementary row operations. This reduced system Ur = 2, is then
solved by the back substitution method to obtain the solution vector
Manoj Kumar 32 Numerical Methods
Consider the 3 x 3 system
anti + ate + aes
any) + agate + aaats = by
gyi + agate + dats = by
[Ale] Set imino a)
First stage of elimination: We assume a1, £ 0. This element ay; in the 1 x 1
position is called the first pivot. Then we are performing the elementary row
operations
Reh =r,
an
RRR,
a
respectively. We get
alin, + ozs + az, <0
ny + ons = WP
alien + ons = 0?
Second stage of elimination, We assume a‘) 4 0, This clement a in the 2 x 2
position is called the second pivot. Then we are performing the elementary row
operations:
we
ROR SR
ay
We get
ny + aay + oz, = 8
ain + afrs = OP
on, = 6
Manoj Kumar 33 Numerical Methods
‘The element af!) # 0 is called the third pivot. The solution vector x is now
obtained by back substitution
se
ante,
O33
WP ae)
” aw
2) gy, — alt
(OU = ays = ayy x2)
Ty
ayy
a
In the elimination process, if any one of the pivot elements a}, a3), and af,
vanishes or becomes very small compared to other elements in that row then we
altempt Lo rearrange the remaining rows so as to obtain a non-vanishing pivot or
to avoid the multiplication by a large number. This strategy is called pivoting,
The pivoting is of the following two types.
* Partial Pivoting:
Choose j, the smallest integer for which
9
lal?| = mala], kin
and interchange rows f and j
* Complete Pivoting:
Choose | and m_as the smallest integers for which,
“)
laf! | = mazlal)|, k SO Jaw f=
ie
A real matrix A is said to be a positive definite matrix, if x’Az > 0 for any vector
x #0 and 2! = (x)".
Manoj Kumar a4 Numerical Methods
Example: 3.1.1 Solve the system of equations
10x, ~ arp + 2x3 =4
21 + 10x, ~ 23 =3
2x, + 30, + 2025 = 7
using the Gauss elimination method.
Solution: The system is diagonally dominant and no pivoting is necessary. The
augmented matrix,
io -1 2 | 4
1 143
2.3 2% | 7
we get
om |
op we It,
The second stage elimination,
@)
a 2
Rye Ry- Ra = Ry- Ry
a Tor
we get
w-1 2 | 4
0 Blt
oo muse | Se
Manoj Kumar 35 Numerical Methods
using back substitution, we get
ary = 0.269
rrp = 0.289
ny = 0.375.
Example: 3.1.2 Solve the system of equations
Solve the system of equations
2 +2, +225 =6
Bary + Bara + Airs = 20
Quy 4 a 1 3x3 = 13
using the Gauss elimination method.
‘The augmented matrix,
11i|6
3.34 | 20
213/18
‘The first stage elimination,
Ree Ry
nem = mB
wwe get
11 iis
oo 1|2
o-1ij.
Manoj Kumar 36 Numerical Methods
Here the pivot in the second equation is zero and so we can not proceed as usual.
We interchange the equations (or row) two and third before the second step elim-
ination, We obtain the upper triangular matrix.
which has the solutions
ty=2, 0
Example: 3.1.3 Solve the system
2 + 10x, — 23 =3
Dory + Bary + 205 = 7
10x) ~ ay + 205
using the Gauss elimination method.
Solution:
‘The augmented matrix,
Here the pivot in the first equation is very small and so we can not proceed as
usual
Ro Rs,
we get
214
23 07
1 WW 1/3
Manoj Kumar 37 Numerical Methods
‘The first stage elimination,
Rr Ry
0 32 196 | 62
0 101 -12 | 26
Here the pivot in the second equation is very small and so we can not proceed as
usual
Ry © Ry
we get
1-1 2 | 4
0 101 -12 | 26
0 32 196 | 62
‘The second stage of elimination,
2) 2
a 3.2
Rye Re a= Ra
Ro Ry Ti = Bo any
we get
wo -1 2 | 4
0 101 -12 26
|
0 0 19.98020 | 5.37624
Back substitution gives the solution
5.37624 0 544
5 = Teopgg = 0.26008
1
2 = (26 — 1.23) = 0.289
Tp (28 — 1.25) = 0.28940
ay = A (44-25 — 204) = 0.97512
1
4, LU Decomposition Method: In this method, the coefficient matrix A of
the system of equations is decomposed or factorized into the product of a lower
Manoj Kumar 38 Numerical Methods
triangular matrix Z and an upper triangular matrix U. We write as
where
hy 0 0 0
In ln 0 0
L= ly be bss 0
ba tna tas ban
0 ua urs, Uap
U=10 0 us Usp
o 0 0 thon
Choose either uj; = 1 or y= 1, i= 1,2,....n. Using the matrix multiplication
rule to multiply the matrices Zand U and comparing the elements of the resulting,
matrix with those of A we
de
‘ermined the matrices J and U. Then the system of
equations becomes
LUr=b
te as the following two systems of equations
Ur=2
Lz=b
‘The unknowns z:22,...,2, are determined from the system Lz = 6 by forward
substitution and the unknowns 2,2, 2%, from the system Ur = 2 are obtained
by back substitution.
Manoj Kumar 39 Numerical Methods
Example: 3.1.4 Consider the system of equations
ay bata =
day + 322 ~ 25
3x, + 5x, +325 =4
Use the decomposition method to salve the system.
We write
Tota ts
43 -1]=]ln In 0} JO 1 wm
oo 1
fa = Llay = 4b = 38,
2 = Ltus = 1
lap = =I la = 2
as = Bylss = 10.
Thus we have
10 0 laid
L=|4 -1 0 |U=|o15
3.2 -10 ool
Using the forward substitution, we have
1
Li=boz=| 2
1/2
Using the back substitution, we have
1
Ur=2>2= | 1/2
1/2
Manoj Kumar 40 Numerical Methods
Example: 3.1.5
by the method of LU decomposition.
Solution: We obtain,
1 00 23 1
L=|05 1 0f/U=|o0 05 25
15-7 1 o 0 WB
Then the equation Lz = b gives the solution
Finally, the matrix equation Ux = z gives the required solution
Load
z= |161
0.278
3.2 ill and well-conditioned systems
Let « is the exact solution of the system and @ is the corresponding approximation
solution. Then, satisfy the foll inequality,
[ust , wal
Tel TAI
le
lel]
16A])
where the quantity K(A) = ||A™| ||Al| is called the condition number of the
matrix A and is denoted by cond(A)
If K(A) is small (near unity) then the small changes in A or 6 produce only small
Manoj Kumar AL SS Nrmerical Methods
changes in x, and the system of equations Ax = b is called well-conditioned. If
AK(A) is large then small changes in A or 6 will produce large changes in x, and
b is called ill-conditioned.
the system of equations Ar
Let A= [aij] and
si [ah tak te + al)?
If we define
det A
S820 80
then the system is ill-conditioned if k is very small compared to unity. Otherwise,
it is well-conditioned
Example: 3.2.1 The system
Qe +y=2
e+ 1.0ly = 2.01
has the solution
05, y=1
But the system
Qnty =2
201r + y = 2.05
has the solution
Also,
All, = 3.165, ||A~*|] = 158.273.
Therefore, condition number cond(A) =
‘A }||||Al| = 500.874. Hence the system
is ill-conditioned. Also,
det(A) = 0.02
si = V5, 9) = 2.24
Manoj Kumar 2 Numerical Methods
So,
0.02
b= = 4.408 x 10-8
VB x 2.24
Hence the system is ill-conditioned.
Example: 3.2.2 Find the condition number of the system
SE)
Solution:
51 = VEE S 18 = 2.766, sy = 8.157.
0.03
k= = 0.001329,
Hence the system is ill-conditioned,
3.3 Iterative Methods
We start with an initial approximation to the solution vector x = zp, to solve
the system of equations Ax = , and obtain a sequence of approximate vectors
9,71; -4Tky--, Which in the limit as k + oo, converges to the exact solution
veetor x = Ab,
A general linear iterative method for the solution of the system of equations
Ar = b, can be written in matrix form as
2) = Hal + 6k =0,1,2,
where 2") and 2)
are the approximations for x at the (k + 1)!* and k'* itera
tions respectively. HT is called the iteration matrix, which depends on A and c is,
a column vector, which depends on A and 6
Manoj Kumar 43
