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 find 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

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

Log In


OR

Join OneClass

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

Sign up

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.

Reset Password

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

Add your courses

Get notes from the top students in your class.


Submit