《结构工程中的数学方法》课程教学课件（讲稿）Topic_2_Algebra

2AlgebraicproblemsinmatrixformSystemsof Equationsin EngineeringExamplesstructural analysis:evaluation of eguilibrium conditionsreliabilityanalysis:responsesurfacemethodsstructural design:determination of optimum dimensions.material modelling:determination of parameters from dataForm of eguations.linear/nonlinearexplicit/implicitalgebraic/transcendental.homogeneous/non-homogeneousbasic cases and common applicationsexplicit linear algebraicequationsSolution methodsdirectmethodsiterativemethods31MichaelBeer,EngineeringMathematics

Michael Beer, Engineering Mathematics 31 2 Algebraic problems in matrix form Systems of Equations in Engineering Examples ● structural analysis: evaluation of equilibrium conditions ● reliability analysis: response surface methods ● structural design: determination of optimum dimensions ● material modelling: determination of parameters from data basic cases and common applications explicit linear algebraic equations Form of equations ● linear / nonlinear ● explicit / implicit ● algebraic / transcendental ● homogeneous / non-homogeneous Solution methods ● direct methods ● iterative methods

2AlgebraicproblemsinmatrixformSystemsofLinearEquationsSystem structure.n equations for the determination of n unknowns x,(E.)b,x+x十ainxn+aix++(E,)b,=ax+a22x2+..+a2,X,+.+ax主:::：S(E)= b,a,x,十a.x,a,x,a,X2十十十..：..:：:b.(E.)anx,annxnan2x,anx++aj: constant coefficients, e.g., stiffness elementsb,:constant values (right-hand side),e.g.,loads(atleastoneb,+Otoformanon-homogeneoussystem)X,:unknowns,e.g.,displacementsthreecasesforsolution(graphicalrepresentationforn=2):2)nosolution1)singlesolution3)infinitelymanysolutionsE1EiEE2E2E232Michael Beer,Engineering Mathematics

32 Systems of Linear Equations System structure ● n equations for the determination of n unknowns xn aij: constant coefficients, e.g., stiffness elements bi : constant values (right-hand side), e.g., loads (at least one bi ≠ 0 to form a non-homogeneous system) xn: unknowns, e.g., displacements ( ) ( ) ( ) ( ) 11 1 12 2 1j j 1n n 1 1 21 1 22 2 2 j j 2n n 2 2 n i1 1 i2 2 ij j in n i i n1 1 n2 2 nj j nn n n n a x a x . a x . a x b E a x a x . a x . a x b E S a x a x . a x . a x b E a x a x . a x . a x b E  + ++ ++ =   + ++ ++ =   =  + ++ ++ =     + ++ ++ =            ● three cases for solution (graphical representation for n=2): 1) single solution 2) no solution 3) infinitely many solutions E1 E2 E1 E2 E1 E2 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics

2AlgebraicproblemsinmatrixformSystems of Linear EquationsSystem structure (cont'd)matrixformanaina12a,[b,](E.)X1(E,)b2a21a2na22aziX2........：：：.(E.)b,X,a.iai2aainintroductory:目...：：example:bn(E.)Xnanan2annaAb真a1la12an=b,a.(E,)a(E,)a21=b,a22aa2na2n+representationwith：..augmented matrix(E.)a.n+1 =baiaina,2a.iA=[A /b]目：::::(E.)=b.a.an2annaniann+1n133Michael Beer,EngineeringMathematics

33 Systems of Linear Equations System structure (cont'd) ● matrix form ( ) ( ) ( ) ( ) 11 12 1j 1n 1 1 1 21 22 2 j 2n 2 2 2 i1 i2 ij in i i i n n n n1 n2 nj nn a a . a . a x b E a a . a . a x b E a a . a . a x b E a a . a . a x b E             ⋅ =                         A xb ⋅ = ( ) ( ) ( ) ( ) 11 12 1j 1n 1 n 1 1 1 21 22 2 j 2n 2 n 1 2 2 i1 i2 ij in i n 1 i i n n1 n2 nj nn n n 1 n a a . a . a a b E a a . a . a a b E a a . a . a a b E a a . a . a a b E + + + +   =   = = =             representation with augmented matrix ˆ =   A Ab   2 Algebraic problems in matrix form introductory example Michael Beer, Engineering Mathematics

2AlgebraicproblemsinmatrixformSystems of Linear EquationsSolvabilitysolvable if and only if rk(A) = rk(A)exactly one(unique)solution if,further,rk(A)=n》rk(A):rankofthematrixAofcoefficientsrk(A):rankoftheaugmentedmatrixAofcoefficients》n:number of unknownsX,rankof a matrix A = maximal number of linearly independent rows of Arow vectors (aii, ai2, ..., aij, .., ain) are linearly independentif the solution to Za. (a,aiz...,ay..,a..) = o is , = O, i = 1, .., n, only."quadratic"system of equations:uniquesolutionifandonly ifdet(A)+0》 det(A):determinant of matrix Adet(A)=Zsgn(βi,β2..,β.).aieap,.angm(n!summands)B1.P2....,Bn(βi,β2,...,βn):permutationsof indicessgn(βi,β2,..,βn):signatureof permutation(alternating+1and-1)34Michael Beer, Engineering Mathematics

34 Solvability ● solvable if and only if rk(A) = rk(Â), exactly one (unique) solution if, further, rk(Â) = n » rk(A): rank of the matrix A of coefficients » rk(Â): rank of the augmented matrix  of coefficients » n: number of unknowns xi ● "quadratic" system of equations: unique solution if and only if det(A) ≠ 0 » det(A): determinant of matrix A rank of a matrix A = maximal number of linearly independent rows of A row vectors (ai1, ai2, ., aij, ., ain) are linearly independent if the solution to ( ) is λi = 0, i = 1, ., n, only. n i i1 i2 ij in i 1 a ,a ,.,a ,.,a = ∑ λ = 0 ( ) ( ) 12 n 12 n 12 n 1 2 n , ,., det sgn , ,., a a . a ββ β ββ β A = ββ β ⋅ ⋅ ⋅ ⋅ ∑ (β1, β2, ., βn): permutations of indices sgn(β1, β2, ., βn): signature of permutation (alternating +1 and −1) (n! summands) Systems of Linear Equations 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics

2AlgebraicproblemsinmatrixformSystems of LinearEquationsSolvability.exampleproblem interpretation:(E) stipulates X + 2·X2 + X3 = 31213(E1)consequently,2.(x+2.x2+x3)shouldyield2.3=62421(E2)but (E2) demands 2X1 + 4·X2 + 2·X3 = 1 + 6-212-3(E3)whichis a contradictionnosolutionexists》rankofmatrixA21 (1,2,1) + 22 :(2,4,2) + 23 (-3, -2,1)= 0 for 21 = 2, 22 = -1, 23 = 0lineardependencybetween vectorsin rows1 and2ofmatrixA=rk(A)=2》rank of augmented matrixA21 (1,2,1,3) +22 (2,4,2,1)+ 23 (-3, -2,1,2) = 0 for 2, = 0, i = 1,2,3, onlythe three row vectors in matrix A are linearly independent =rk(A)=3rk(A) + rk(A) no solution exists》determinantofmatrixAdet (A) = 1·4·1 + 2·2·(-3) + 1·2·(-2) - 1·4·(-3) - 1·2·(-2) - 2·2·1 = 0no unique solution exists (no solution OR infinitelymany solutions)also:det(A)= O if a row ora column in A contains zeros only35MichaelBeer,EngineeringMathematics

35 Solvability ● example 1 213 2 421 3 212         − −   (E1) (E2) (E3) λ ⋅ +λ ⋅ +λ ⋅ − − = 12 3 (1,2,1 2,4,2 3, 2,1 ) ( ) ( ) 0 for λ1 = 2, λ2 = −1, λ3 = 0 linear dependency between vectors in rows 1 and 2 of matrix A ⇒ rk(A) = 2 » rank of matrix A problem interpretation: (E1) stipulates x1 + 2·x2 + x3 = 3 consequently, 2·(x1 + 2·x2 + x3) should yield 2·3 = 6 but (E2) demands 2·x1 + 4·x2 + 2·x3 = 1 ≠ 6 which is a contradiction no solution exists λ ⋅ +λ ⋅ +λ ⋅ − − = 12 3 (1,2,1,3 2,4,2,1 3, 2,1,2 ) ( ) ( ) 0 the three row vectors in matrix  are linearly independent ⇒ rk(Â) = 3 » rank of augmented matrix  for λi = 0, i = 1,2,3, only rk(A) ≠ rk(Â) no solution exists » determinant of matrix A det (A) = 1·4·1 + 2·2·(−3) + 1·2·(−2) − 1·4·(−3) − 1·2·(−2) − 2·2·1 = 0 no unique solution exists (no solution OR infinitely many solutions) !also: det(A) = 0 if a row or a column in A contains zeros only Systems of Linear Equations 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics

2AlgebraicproblemsinmatrixformSystemsofLinearEquationsDirect solutiondesired structure of the system of equationsaua1z0ain(E.)X1[b]simple solution0(E2)bza2nX2a22a2istep-by-step：:...0......fromrownb,(E)0X.backwardtorow1aina.(backward elimination,目......0：：backwardsubstitution)(E.)b.X.0000apossibleoperationsonthesystemofequations》multiplyingrowswithaconstantfactorc+(C·E) → (E)introductory》addingmultiplesofrowstootherrowsexample(E+ZCkEK)→(E)》switching rowsinorder(Ek) (E)systematic application of operations to achieve the desired structure36MichaelBeer,EngineeringMathematics

36 Direct solution ● desired structure of the system of equations » multiplying rows with a constant factor c ≠ 0 (c·Ei ) → (Ei ) » adding multiples of rows to other rows (Ei + Σck·Ek) → (Ei ) » switching rows in order (Ek) ↔ (Ei ) systematic application of operations to achieve the desired structure ( ) ( ) ( ) ( ) 11 12 1j 1n 1 1 1 22 2 j 2n 2 2 2 i i i ij in n n n nn a a . a . a x b E 0 a . a . a x b E 0 0 . 0 a . a x b E 0 0 0 . 0 0 a x b E             ⋅ =                       ● possible operations on the system of equations simple solution step-by-step from row n backward to row 1 (backward elimination, backward substitution) Systems of Linear Equations 2 Algebraic problems in matrix form introductory example Michael Beer, Engineering Mathematics

2AlgebraicproblemsinmatrixformGaussian EliminationAlgorithmPart I:forward elimination (elimination of unknownsx,row by row).procedureaij =pivot element[aa12ainain+=b,arj(E.)foroperationsPi,i=j+1,...,n(E)a2 n+1 = bza21azna22aziwith the requirement ai + 0：主：：8If a=0 (better:if laillaikl(E.)a, n+1 = b,aiai2arain.forsomeof theaik),目：...！:thensearchforthesmallest(E.)integerp,j<p≤n,withapi0anian2=bania..a.andswitchtherows (E,)(E,)(E)(E.) →(E), i= j+1,.,n, j = 1,.,n-1Py:asequenceofoperationsPitoeliminateX,inrowsi=2,...n(thenew coefficientsaii,i=2,...,n, arebroughttozero)2(E) → (E,), i= 2, j=1》 P21: (E2)elimination of x, inrow 2o23(E)→(E), i=3, j=1(E,)eliminationofxinrow3》P:(ar137MichaelBeer,EngineeringMathematics

37 Gaussian Elimination Algorithm Part I: forward elimination (elimination of unknowns xi row by row) ● procedure ( ) ( ) ( ) ( ) 11 12 1j 1n 1 n 1 1 1 21 22 2 j 2n 2 n 1 2 2 i1 i2 ij in i n 1 i i n n1 n2 nj nn n n 1 n a a . a . a a b E a a . a . a a b E a a . a . a a b E a a . a . a a b E + + + +   =   = = =             ( ) ( ) ( ) ij ij i j i jj a P : E E E , i j 1,.,n, j 1,.,n 1 a − → =+ = − ( ) ( ) ( ) 21 21 2 1 2 11 a P : E E E , i 2, j 1 a − → == ● sequence of operations Pi1 to eliminate x1 in rows i = 2, ., n (the new coefficients ai1, i = 2, ., n, are brought to zero) elimination of x1 in row 2 ( ) ( ) ( ) 31 31 3 1 3 11 a P : E E E , i 3, j 1 a − → == elimination of x1 in row 3 » » ajj = pivot element for operations Pij, i = j+1, ., n with the requirement ajj ≠ 0 If ajj = 0 (better: if |ajj| «|aik| for some of the aik), then search for the smallest integer p, j < p ≤ n, with apj ≠ 0 and switch the rows (Ep) ↔ (Ej ). 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics

2AlgebraicproblemsinmatrixformGaussian EliminationAlgorithmPartI:forwardelimination (cont'd)sequenceof operationsPito eliminatex,in rowsi=2,...,n (cont'd)(the new coefficients ai,i = 2, .., n, are brought to zero)：> P : (E,)-(E) →(E,), i=n, j=1eliminationof x,inrownmodified system of equationswithnew coefficients afori=2,...,no+1=b,a12aiiainain+(E)0(E.)a2 n+1 = b,a22azna2i.：：：(E)0ain+1 = baizaan目目目：：(E,)0anza.anHThe unknownx, is present in row 1 exclusively!38Michael Beer, EngineeringMathematics

38 Gaussian Elimination Algorithm ( ) ( ) ( ) ( ) 11 12 1j 1n 1 n 1 1 1 22 2 j 2n 2 n 1 2 2 i2 ij in i n 1 i i n n2 nj nn n n 1 n a a . a . a a b E 0 a . a . a a b E 0 a . a . a a b E 0 a . a . a a b E + + + +   =   = = =             ( ) ( ) ( ) n1 n1 n 1 n 11 a P : E E E , i n, j 1 a − → == elimination of x1 in row n modified system of equations with new coefficients aij for i = 2, ., n The unknown x1 is present in row 1 exclusively ! Part I: forward elimination (cont'd) ● sequence of operations Pi1 to eliminate x1 in rows i = 2, ., n (cont'd) (the new coefficients ai1, i = 2, ., n, are brought to zero) »  2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics

2AlgebraicproblemsinmatrixformGaussianEliminationAlgorithmPart I:forward elimination (cont'd)sequenceof operationsPtoeliminateX,inrowsi=3,...,n(thenew coefficientsai2,i=3,...,n,arebroughttozero)> P2 : (E,)- 22(E,) →(E,), i= 3, j= 2 eliminationof Xinrow 3a22..a2(E,) → (E,), i=n, j= 2》 Pnz : (E.)eliminationofx,inrown222modified system of equations with new coefficients a, fori =3,..., nai1ai2ain+1 = b,a13aljain(E.)0a221 = b,(E,)aaa2azn00：0a.d(E)00=bai3aina.a......:(E.)00nan3ania.aTheunknownx2ispresentinrows1and2exclusively!39Michael Beer, Engineering Mathematics

39 Gaussian Elimination Algorithm ( ) ( ) ( ) ( ) 11 12 13 1j 1n 1 n 1 1 1 22 23 2 j 2n 2 n 1 2 2 33 3 j 3n i i3 ij in i n 1 i n n3 nj nn n n 1 n a a a a . a a b E 0 a a a . a a b E 0 0 a a . a 0 0 a a . a a b E 0 0 a a . a a b E + + + +   =   = = =         ( ) ( ) ( ) 32 32 3 2 3 22 a P : E E E , i 3, j 2 a − → == elimination of x2 in row 3 modified system of equations with new coefficients aij for i = 3, ., n The unknown x2 is present in rows 1 and 2 exclusively ! Part I: forward elimination (cont'd) ● sequence of operations Pi2 to eliminate x2 in rows i = 3, ., n (the new coefficients ai2, i = 3, ., n, are brought to zero) »  ( ) ( ) ( ) n2 n2 n 2 n 22 a P : E E E , i n, j 2 a − → == elimination of x2 » in row n 2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics

2AlgebraicproblemsinmatrixformGaussian Elimination AlgorithmPart I:forward elimination (cont'd)further operations P,to eliminate X,in rows i= j+1,...,n(the new coefficients ai,i = j+1, ..., n, are brought to zero):final operation Pin-ito eliminateXn-1 in rowi=n(thenew coefficient ann-i isbroughttozero)an-(E.1) → (E,), j = n -1, i= n》Pnn-1 : (E,)-a.-10-1modified system of equations with new coefficients ann, an n+1ainai n+1 = b,aiain-1a(E.)E0a2 n+1 = b,.Rowncontains0'.,ainain-1ajtheunknownX,only!(E)00a, n+1 = b,an-2nan-2. n-2an-2 n-1001an-1 n-1an-1n(E,)0001=b.annd40MichaelBeer,EngineeringMathematics

40 Gaussian Elimination Algorithm ( ) ( ) ( ) ( ) 11 1j 1 n 1 1n 1 n 1 1 1 2 n 1 2 2 ij i n 1 in i n 2 n 2 n 2 n 1 n 2 n i n 1 i n 1 n 1 n 1 n n nn n n 1 n a . a . a a a b E 0 . a b E 0 . a a a 0 . 0 a a a a b E 0 . . 0 a a 0 . . 0 0 a a b E − + + − −− −− − + −− − +   =   = =   =       modified system of equations with new coefficients ann, an n+1 Row n contains the unknown xn only ! Part I: forward elimination (cont'd) ● further operations Pij to eliminate xj in rows i = j+1, ., n (the new coefficients aij, i = j+1, ., n, are brought to zero) ( ) ( ) ( ) − − − − − − → =− = n n 1 n n 1 n n 1 n n 1 n 1 a P : E E E , j n 1, i n a ● final operation Pi n−1 to eliminate xn−1 in row i = n (the new coefficient an n−1 is brought to zero) »  2 Algebraic problems in matrix form Michael Beer, Engineering Mathematics