Class Notes (839,076)
United States (325,760)
ECE 3043 (1)
Smith (1)
Lecture

# Chapter_02.pdf

22 Pages
82 Views

Department
Electrical & Computer Engr
Course Code
ECE 3043
Professor
Smith

This preview shows pages 1,2,3,4. Sign up to view the full 22 pages of the document.
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

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

Unlock Document
###### You're Reading a Preview

Unlock to view full version

Unlock Document
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.