2AlgebraicproblemsinmatrixformGaussian Elimination AlgorithmPartII:backwardsubstitution(determinationandsubstitutionoftheunknownsX;rowbyrowbackward)·procedureann+1X.annZa,x,ain+1j=i+1i= n-1,n-2....,1Xa.ideterminationoftheunknownx,fromrownannti》rown:annX,=ann+1=Xna. substitution of x, in row n-1 and determination of the unknown Xn-1ann+lan-1 n+1 - an-1 nX.》row n-1:an-1n-1Xn-1 +an-1n X,=an-1 n+1 =Xnannan-1 n-1...substitution ofx2..,Xn in row 1anddetermination of theunknownXiZaiain+1.X-1-2》row 1:a X +a, X,=ain+1 = X =X2...,X.=..allj=241MichaelBeer,EngineeringMathematics
41 Gaussian Elimination Algorithm Part II: backward substitution (determination and substitution of the unknowns xi row by row backward) ● procedure n n 1 nn n n n 1 n nn a ax a x a + + » row n: ⋅= ⇒ = n i n 1 ij j ji1 i ii a ax x , i n 1,n 2,.,1 a + = + − ∑ = =− − ● determination of the unknown xn from row n n n 1 n nn a x a + = n 1 n 1 n 1 n n n n 1 n 1 n 1 n 1 n 1 n n n 1 n 1 n 1 n n 1 n 1 nn a ax a a x a x a x , x a a −+ − + −− − − − + − − − − ⋅ » row n−1: ⋅ + ⋅= ⇒ = = ● substitution of xn in row n−1 and determination of the unknown xn−1 n n 1 n 1 1j j j 2 11 1 1j j 1 n 1 1 2 n j 2 11 a ax a x a x a x , x ,., x . a + = + = − ⋅ ∑ » row 1: ⋅+ ⋅= ⇒ = ∑ = ● substitution of x2, ., xn in row 1 and determination of the unknown x1 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics
2AlgebraicproblemsinmatrixformGaussian Elimination AlgorithmFeatures and capabilities.numerical stability》stablefordiagonally dominantorpositive-definitematrices》usuallystableinpractice》examplesexistfor whichthealgorithmisunstable(ill-conditioned systems)selectpivotelementsofpropermagnitude,normalisesystemsproperly福numerical efficiency》solutionofannxnsystemrequiresapproximately2n3/3operationsapplicability》generally useful forsolvingvarious problems》severalthousandsofunknownscanbehandledverylargesystemswithmillionsorbillionsof unknownsexceedthecapabilities of computationalresources42MichaelBeer,EngineeringMathematics
42 applicability » generally useful for solving various problems » several thousands of unknowns can be handled » very large systems with millions or billions of unknowns exceed the capabilities of computational resources Gaussian Elimination Algorithm Features and capabilities ● numerical stability » stable for diagonally dominant or positive-definite matrices » usually stable in practice » examples exist for which the algorithm is unstable (ill-conditioned systems) select pivot elements of proper magnitude, normalise systems properly ● numerical efficiency » solution of an n×n system requires approximately 2n3/3 operations ! 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics
2AlgebraicproblemsinmatrixformGaussian Elimination AlgorithmExamplestructural system with loading50kN1?》structuralparametersE=2.1.108kN/m2（steel)EI=2.293.10-4m4(HEA320)3A→o(extensionalstiffnessneglected)32》unknownsEXX,:horizontal displacement of nodes 1,2 and 33vyX2:rotation of node 145X3:rotation of node 23m3mX4:rotation of node3equilibrium conditions[501.07010-1.6051-1.6051(E.)X000(E.)06.8099X2·10400(E.)8.02551.6051-1.6051+3(E.)00-1.60511.60518.0255X43MichaelBeer,EngineeringMathematics
43 Gaussian Elimination Algorithm ( ) ( ) ( ) ( ) 1 1 4 2 2 3 3 4 4 1.0701 0 1.6051 1.6051 x 50 E 0 6.8099 0 0 x 0 E 10 = 1.6051 0 8.0255 1.6051 x 0 E 1.6051 0 1.6051 8.0255 x 0 E − − ⋅ ⋅ − − Example ● structural system with loading 3 m 3 m 3 m 3 m 50 kN » structural parameters E = 2.1·108 kN/m2 (steel) I = 2.293·10−4 m4 (HEA 320) A → ∞ (extensional stiffness neglected) 1 2 3 4 5 x y » unknowns x1: horizontal displacement of nodes 1, 2 and 3 x2: rotation of node 1 x3: rotation of node 2 x4: rotation of node 3 ● equilibrium conditions 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics
2AlgebraicproblemsinmatrixformGaussian EliminationAlgorithmExample(cont'd)augmented matrix,with the scaleadjustmentx=104.x(E.)-1.6051-1.6051|501.070100000(E.)6.80990(E.)0-1.60518.02551.60510(E.)01.60518.0255-1.6051forwardelimination,operationsPitoeliminateX,inrowsi=2,3,4a2(E.) → (E,), not necessary as a21 = 0, (E2) is not modified》 P21 : (E)-a.-1.6051a(E.) = (E.)》P31:(E)(E) → (E.)1.0701a,new coefficients inrow 3:-1.6051aa=-1.60511.0701=0X,eliminated in row31.0701-1.6051-1.605100=0,a33=8.0255(-1.6051)=5.6179=a321.07011.070144MichaelBeer,EngineeringMathematics
44 Gaussian Elimination Algorithm ( ) ( ) ( ) ( ) 1 2 3 4 1.0701 0 1.6051 1.6051 50 E 0 6.8099 0 0 0 E 1.6051 0 8.0255 1.6051 0 E 1.6051 0 1.6051 8.0255 0 E − − − − Example (cont'd) ● augmented matrix, with the scale adjustment =104 xˆ ·x ● forward elimination, operations Pi1 to eliminate x1 in rows i = 2, 3, 4 , not necessary as a21 = 0, (E2) is not modified ( ) ( ) ( ) ( ) ( ) 31 31 3 1 3 1 3 11 a 1.6051 P : E E E E E a 1.0701 − − =− → » » ( ) ( ) ( ) 21 21 2 1 2 11 a P : E E E a − → ( ) 31 32 33 1.6051 a 1.6051 1.0701 0 1.0701 1.6051 1.6051 a 0 0 0, a 8.0255 1.6051 5.6179 1.0701 1.0701 − =− − ⋅ = − − =− ⋅= = − ⋅ − = x1 eliminated in row 3 new coefficients in row 3: 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics
2AlgebraicproblemsinmatrixformGaussian Elimination AlgorithmExample (cont'd).forward elimination,operations Pi to eliminate x, in rowsi=2,3,4(cont'd)》 new coefficients in row3:recall:-1.60511.0701 0-1.6051-1.605150a34=1.6051(-1.605100006.80991.0701008.02551.6051-1.6051a34 =-0.8024800-1.60511.60518.0255-1.6051a3s = 050=74.9981.6051a(E)=(E)Pa:(E,)→(E)1.07011.0701a1-1.6051a(E.) = (E)》P41:(E4)(E) →(E4)1.0701o1lnewcoefficientsinrow4:-1.6051a41=-1.60511.0701=0Xieliminatedinrow41.0701a42 =a2=0, a43 = a34 =-0.80248, a44 =a33 =5.6179, a45 =a5 =74.99845MichaelBeer,EngineeringMathematics
45 Gaussian Elimination Algorithm Example (cont'd) ● forward elimination, operations Pi1 to eliminate x1 in rows i = 2, 3, 4 (cont'd) 34 ( ) 34 35 1.6051 a 1.6051 1.6051 1.0701 a 0.80248 1.6051 a 0 50 74.998 1.0701 − = − ⋅ − = − − =− ⋅ = ( ) ( ) ( ) ( ) ( ) 41 41 4 1 4 1 4 11 a 1.6051 P : E E E E E a 1.0701 − − =− → » 41 42 32 43 34 44 33 45 35 1.6051 a 1.6051 1.0701 0 1.0701 a a 0, a a 0.80248, a a 5.6179, a a 74.998 − =− − ⋅ = = = = = − = = = = x1 eliminated in row 4 new coefficients in row 4: » new coefficients in row 3: 1.0701 0 1.6051 1.6051 50 0 6.8099 0 0 0 1.6051 0 8.0255 1.6051 0 1.6051 0 1.6051 8.0255 0 − − − − ( ) ( ) ( ) ( ) ( ) 31 31 3 1 3 1 3 11 a 1.6051 P : E E E E E a 1.0701 − − =− → recall: 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics