Lesson 6 Computational Methods in Physics I - PHY405 PDF

Computational Methods in Physics I :PHY405 Lesson 6 Chapter 9 on Textbook  Review Examples : 1 2 1 3 2 1 − 1 0 4 1 0 symmetric  1 0 5  , uppe...

Computational Methods in Physics I :PHY405 Lesson 6 Chapter 9 on Textbook  Review Examples : 1 2 1 3 2 1 − 1 0 4 1 0 symmetric  1 0 5  , upper triangular  0 0 4 1 − 1 5 4    0 0 0 1 Determinant of a MATRICES Defined for square matrices only Examples :  2 3 − 1   0 5 3 -1 3 -1 det  1 0 5  = 2 -1 -1 5 4 5 4 0 5 − 1 5 4  = 2(−25) − 1(12 + 5) − 1(15 − 0) = −82 2  Systems of Linear Equations A system of linear equations can be presented in different forms 2𝑥𝑥1 + 4𝑥𝑥2 − 3𝑥𝑥3 = 3 2 4 −3 𝑥𝑥1 3 2.5𝑥𝑥1 − 𝑥𝑥2 + 3𝑥𝑥3 = 5 ⇔ 2.5 −1 3 𝑥𝑥2 = 5 𝑥𝑥1 − 6𝑥𝑥3 = 7 1 0 −6 𝑥𝑥3 7 Standard form Matrix form 3  Solutions of Linear Equations  x1  1   x  = 2 is a solution to the following equations :  2   x1 + x2 = 3 x1 + 2 x2 = 5 A set of equations is inconsistent if there exists no solution to the system of equations: 𝑥𝑥1 + 2𝑥𝑥2 = 3 2𝑥𝑥1 + 4𝑥𝑥2 = 5 These equations are inconsistent 4  Solutions of Linear Equations Some systems of equations may have infinite number of solutions x1 + 2 x2 = 3 2 x1 + 4 x2 = 6 have infinite number of solutions  x1   a   x  = 0.5(3 − a ) is a solution for all a  2   5 Graphical Solution of Systems of Linear Equations x1 + x2 = 3 x1 + 2 x2 = 5 Solution x1=1, x2=2 6 Cramer’s Rule 7 Cramer’s Rule 8 Cramer’s Rule 9 Cramer’s Rule 10 Cramer’s Rule 11  Cramer’s Rule is Not Practical !! Cramer' s Rule can be used to solve the system 3 1 1 3 5 2 1 5 x1 = = 1, x2 = =2 1 1 1 1 1 2 1 2 Cramer' s Rule is not practical for large systems. To solve N by N system requires (N + 1)(N - 1)N! multiplications. To solve a 30 by 30 system, 2.38 × 1035 multiplications are needed. It can be used if the determinants are computed in efficient way 12  Naive Gaussian Elimination The basic idea of Gaussian elimination is to transform the original linear equation set to one that has an upper-triangular or lower-triangular coefficient matrix but has the same solution. It consists of two steps  Forward Elimination: the system is reduced to upper triangular form. A sequence of elementary operations is used.  a11 a12 a13   x1   b1  a11 a12 a13   x1   b1  a a22 a23   x  = b  ⇒ 0 a22 ' a23 '  x  = b '  21  2  2   2  2   a31 a32 a33   x3  b3   0 0 a33 '  x3  b3 '  Backward Substitution: Solve the system starting from the last variable. Solve for xn ,xn-1,…x1. 13  Forward Elimination  ai1   aij ← aij −  a1 j (1 ≤ j ≤ n )   a11   To eliminate x1 2 ≤ i ≤ n a   bi ← bi −  i1 b1  a11    ai 2   aij ← aij −  a 2 j (2 ≤ j ≤ n )  a 22   To eliminate x2 3 ≤ i ≤ n a   bi ← bi −  i 2 b2  a 22   14  Forward Elimination a   aij ← aij −  ik a kj (k ≤ j ≤ n)   a kk   To eliminate xk k + 1 ≤ i ≤ n  aik   bi ← bi −  bk  a kk   Continue until xn −1 is eliminated. 15  Backward Substitution bn xn = a n ,n bn −1 − a n −1, n x n x n −1 = a n −1, n −1 bn − 2 − a n − 2, n x n − a n − 2, n −1 x n −1 xn − 2 = a n − 2, n − 2 n bi − ∑ ai , j x j j = i +1 xi = a i ,i 16  Example 1 Forward Elimination Solve using Naive Gaussian Elimination : Part 1 : Forward Elimination ___ Step1 : Eliminate x1 from equations 2, 3 x1 + 2 x2 + 3x3 = 8 eq1 unchanged ( pivot equation) 2 2 x1 + 3x2 + 2 x3 = 10 eq 2 ← eq 2 −  eq1 1  3 3x1 + x2 + 2 x3 = 7 eq3 ← eq3 −  eq1 1 x1 + 2 x2 + 3 x3 = 8 − x2 − 4 x3 = −6 − 5 x2 − 7 x3 = − 17 17  Example 1 Forward Elimination Part 1 : Forward Elimination Step2 : Eliminate x2 from equation 3 x1 + 2 x2 + 3 x3 = 8 eq1 unchanged − x2 − 4 x3 = −6 eq 2 unchanged ( pivot equation)  −5 − 5 x2 − 7 x3 = − 17 eq3 ← eq3 −  eq 2  −1   x1 + 2 x2 + 3 x3 = 8  ⇒  − x2 − 4 x3 = −6  13 x3 =13  18  Example 1 Backward Substitution b3 13 x3 = = =1 a3,3 13 b2 − a2,3 x3 − 6 + 4 x3 x2 = = =2 a 2, 2 −1 b1 − a1, 2 x2 − a1,3 x3 8 − 2 x2 − 3 x3 x1 = = =1 a1,1 a1,1  x1  1  The solution is  x2  = 2  x3  1  19 Example 2 Forward Elimination  6 −2 2 4   x1   16   12 − 8 6 10   x   26    2 =   3 − 13 9 3   x3   − 19        − 6 4 1 − 18 x  4  − 34  Part 1 : Forward Elimination Step1 : Eliminate x1 from equations 2, 3, 4 6 − 2 2 4   x1   16  0 − 4 2 2  x   − 6    2 =  0 − 12 8 1   x3  − 27       0 2 3 − 14  x4   − 18  20  Example 2 Forward Elimination Step2 : Eliminate x2 from equations 3, 4 6 − 2 2 4   x1   16  0 − 4 2 2  x   − 6     2 =  0 0 2 − 5   x3   − 9        0 0 4 − 13  x4  − 21 Step3 : Eliminate x3 from equation 4 6 − 2 2 4   x1   16  0 − 4 2 2   x  − 6    2 =   0 0 2 − 5  x3  − 9       0 0 0 − 3  x4   − 3  21  Example 2 Forward Elimination Summary of the Forward Elimination :  6 −2 2 4   x1   16  6 − 2 2 4   x1   16   12 − 8 6 10   x   26  0 − 4 2 2   x   − 6   2 = ⇒   2 =   3 − 13 9 3   x3   − 19  0 0 2 − 5  x3  − 9             − 6 4 1 − 18  x4  − 34 0 0 0 − 3  x4   − 3 22  Example 2 Backward Substitution 6 − 2 2 4   x1   16  0 − 4 2 2   x   − 6     2 =  0 0 2 − 5  x3  − 9       0 0 0 − 3  x4   − 3 Solve for x4 , then solve for x3 ,... solve for x1 −3 −9+5 x4 = = 1, x3 = = −2 −3 2 − 6 − 2(−2) − 2(1) 16 + 2(1) − 2(−2) − 4(1) x2 = = 1, x1 = =3 −4 6 23 How Many Solutions Does a System of Equations AX=B Have? Unique No solution Infinite det(A) ≠ 0 det(A) = 0 det(A) = 0 reduced matrix reduced matrix reduced matrix has no zero rows has one or more has one or more zero rows zero rows corresponding B corresponding B elements ≠ 0 elements = 0 24  Examples Unique No solution infinte # of solutions 1 2 1  1 2  2 1 2  2 3 4 X = 2  2 4 X =  3  2 4 X =  4             ↓ ↓ ↓ 1 2  1 1 2  2 1 2   2 0 − 2 X = − 1 0 0 X = − 1 0 0  X =  0              solution : No solution Infinite # solutions 0  α  X =  0 = −1 impossible! X =  0.5 1 −. 5 α  25  Determinant The elementary operations do not affect the determinant Example : 1 2 3  1 2 3 A = 2 3 2 Elementary  → A' = 0 − 1 − 4   operations 3 1 2 0 0 13  det (A) = det (A') = −13 26  Exercises Chap. 9 : Ex : 9.9 (page 272)