false

Class Notes
(839,076)

United States
(325,760)

Georgia Institute of Technology
(1,487)

ECE 3043
(1)

Smith
(1)

Lecture

Department

Electrical & Computer Engr

Course Code

ECE 3043

Professor

Smith

Description

Computational Physics
Solving Linear Systems of Equations
Lectures based on course notes by Pablo Laguna and Kostas
Kokkotas
revamped by Deirdre Shoemaker
Spring 2014 Introduction
In many instances we need to solve A ▯ x = b, where
0 a a a ▯▯▯ a 1 0 x 1 0 b 1
11 12 13 1N 1 1
B a21 a22 a23 ▯▯▯ a2NC B x2 C B b2C
B a31 a32 a33 ▯▯▯ a3NC B x3 C B b3C
A =B . C x =B . C b =B . C
@ . A @ . A @ . A
aN1 aN2 N3 ▯▯▯ aNN xN bN
This requires
Finding A, the inverse of the matrix
Computing the determinant of a matrix A
The eigenvalues and eigenvectors of a matrix A. That is,
A ▯ v = ▯v, Gauss Elimination Method
Consider A ▯ x = b with A a N ▯ N matrix with det(A) 6= 0. That is,
a x + a x + a x + ::: + a x = b
11 1 12 2 13 3 1N N 1
a21 1 a x22 2 x 23 3: + a 2NxN = b 2
a31 1 a x32 2 x 33 3: + a 3NxN = b 3
.
.
aN1x1+ a N2x2+ a N3x3+ ::: + NNxN = b N
We will try to transform it into an upper-triangular linear system.
a11 1 +a12 2 +a 13 3 +::: +a^1NxN = b^1
^
0 +a22 2 +a 23 3 +::: +a^2NxN = b 2
0 +0 +a x +::: +a^ x = b^
33 3 3N N 3
.
.
0 +0 +0 +::: +a^ x = b^
NN N N Given 0 1
a11 a12 a13 ▯▯▯ a1N
B a21 a22 a23 ▯▯▯ a2N C
B C
A = B a31 a32 a33 ▯▯▯ a3N C
B . C
@ . A
aN1 aN2 aN3 ▯▯▯ aNN
construct
0 1 0 0 ▯▯▯ 0 1
a21
B ▯a11 1 0 ▯▯▯ 0 C
B ▯a31 0 1 ▯▯▯ 0 C
M 1 B a11 C
B . C
@ . A
▯aN1 0 0 ▯▯▯ 1
a11
and compute M1A ▯ x =1M b where
0 1
a11 a12 a13 ▯▯▯ a1N
B 0 a22▯ a2a 12 a23▯ a2a13 ▯▯▯ a2N▯ a21a1N C
B a31 a31 a31 C
M A = B 0 a32▯ a11 12 a33▯ a1113 ▯▯▯ a3N▯ a11a1N C
1 B . C
@ . A
a a a
0 aN2▯ N1a12 aN3▯ Na13 ▯▯▯ aNN▯ N1a1N
11 a11 a11
0 a a a ▯▯▯ a 1
11 12 13 1N
B 0 a22(1) a23(1) ▯▯▯ a2N(1)C
B (1) (1) (1)C
M 1 = B 0 a32 a33 ▯▯▯ a3N C
B . C
@ . A
(1) (1) (1)
0 aN2 aN3 ▯▯▯ aNN
and 0 1
0 1 (1)
b1 b1
B b2▯ 21b1 C B b (1)C
B 31 C B 2 C
M b = B b3▯ 11b1 C = B b3(1)C
1 B . C B . C
@ . A @ . A
aN1 .
bN▯ a111 bN(1)
(1)
The procedure can be repited to elimin32e now a Gauss Method
After N ▯ 1 steps we get the the desired upper-triangular system:
a 11 1a x 12 2x + 13 3+ a 1N xN = b1
a(1x + a (1)x + ▯▯▯ + a(1)x = b(1)
22 2 23 3 2N N 2
(2) (2) (2)
a33 x3+ ▯▯▯ + a3N xN = b3
.
.
(N▯1) (N▯1)
a NN xN = bN
The Nth (last) equation above yields :
(N▯1)
b N (N▯1)
xN= (N▯1) for aNN 6= 0
a NN
while the rest of the values can be calculated via the relation:
N
(i▯1) P (i▯1)
bi ▯ aik xk
k=i+1 (i▯1)
xi= (i▯1) for aii 6= 0
aii The number of arithmetic operations needed is
(4N + 9N ▯ 7N)=6.
If a matrix is transformed into an upper-triangular or
lower-triangular or diagonal form then the determinant is simply
N
Y
detA = a 11▯ 22 ▯ 33▯▯▯a NN = a ii
i=1 Pivoting
(i▯1)
Notice that there is trouble when a ii = 0
(i▯1) PN (i▯1)
bi ▯ aik x k
k=i+1 (i▯1)
xi= (i▯1) for aii 6= 0
a
ii
The number a in tii position (i;i) that is used to eliminate x in rows i
i + 1, i + 2, ... ,N is called the ith pivotal element and the ith row is
called the pivotal row.
(i)
If a = 0, row i cannot be used to eliminate, the elements in column i
ii (i)
below the diagonal. It is neccesary to ﬁnd a row j, where a ji 6= 0 and
j > i and then interchange row i and j so that a nonzero pivot element
is obtained. The Jacobi Method
Any system of N linear equations with N unknowns can be written in
the form:
f1(x1;x2;:::;N ) = 0
f (x ;x ;:::;x ) = 0
2 1 2 N
:::::
f (x ;x ;:::;x ) = 0
n 1 2 N
▯ ▯
One can always rewrite the system in the form x = gix ; ihaj is,
x1 = g 1x 2x 3:::;x N
x2 = g 2x 1x 3:::;x N
:::
xN = g Nx 1x ;2::;x N▯1 )
or
XN
x = b i▯ 1 a x
i a a ijj
ii iij=1 ; j6=i Therefore, by giving N initial guesses x (0;x (0;:::;x (0, we create the
1 2 N
recurrence relation
(k+1) (k) (k)
xi = g ix1 ;:::;N )
N
bi 1 X (k)
= ▯ a ij
a ii a ii j
j=1 ; j6=i

More
Less
Unlock Document

Related notes for ECE 3043

Only pages 1,2,3,4 are available for preview. Some parts have been intentionally blurred.

Unlock DocumentJoin OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.