MATH 304Linear AlgebraLecture 2:Gaussian elimination.System of linear equationsa11x1+ a12x2+ ··· + a1nxn= b1a21x1+ a22x2+ ··· + a2nxn= b2·········am1x1+ am2x2+ ··· + amnxn= bmHere x1, x2, . . . , xnare variables and aij, bjareconstants.A solution of the system is a common solution of allequations in th e system.A system of line ar equations can have one solution,infinitely many solutions, or no solution at all.xyx − y = −22x + 3y = 6x = 0, y = 2xy2x + 3y = 22x + 3y = 6inconsistent system(no solutions)xy4x + 6y = 122x + 3y = 6⇐⇒ 2x + 3y = 6Solving systems of linear equationsElimination method always works for systems oflinear e quations.Algorithm: (1) p ick a variable, solve one of theequations for it, and eliminate it from the otherequations; (2) put aside t he equation used in theelimination, and retu rn to step (1).x − y = 2 =⇒ x = y + 22x − y − z = 5 =⇒ 2(y + 2) − y − z = 5After the e limination is completed, the system issolved by back substitution.y = 1 =⇒ x = y + 2 = 3Gaussian eliminationGaussian elimination is a modification of theelimination method t hat allows only so-calledelementary operations.Elementary operations for systems of linear equations:(1) t o multiply an equation by a nonzero scalar;(2) t o add an equation multiplied by a scalar toanother equation;(3) t o interchange two equations.Theorem Applying elementary operations t o asystem of linear equ ations does not change thesolution set of t he system.Operation 1: multiply the ith e quation by r 6= 0.a11x1+ a12x2+ ··· + a1nxn= b1············ai1x1+ ai2x2+ ··· + ainxn= bi············am1x1+ am2x2+ ··· + amnxn= bm=⇒a11x1+ a12x2+ ··· + a1nxn= b1············(rai1)x1+ (rai2)x2+ ··· + (rain)xn= rbi············am1x1+ am2x2+ ··· + amnxn= bmTo undo the operation, multiply the ith equat ion by r−1.Operation 2: add r times the ith equation to thejth equation.············ai1x1+ ai2x2+ ··· + ainxn= bi············aj1x1+ aj2x2+ ··· + ajnxn= bj············=⇒············ai1x1+ ··· + ainxn= bi············(aj1+ rai1)x1+ ··· + (ajn+ rain)xn= bj+ rbi············To undo t he operation, add −r times the ithequation to t he jth equation.Operation 3: interchange the ith and jth equations.············ai1x1+ ai2x2+ ··· + ainxn= bi············aj1x1+ aj2x2+ ··· + ajnxn= bj············=⇒············aj1x1+ aj2x2+ ··· + ajnxn= bj············ai1x1+ ai2x2+ ··· + ainxn= bi············To undo t he operation, apply it once more.Example.x − y = 22x − y − z = 3x + y + z = 6Add −2 times the 1st eq uation to the 2nd equation:x − y = 2y − z = −1x + y + z = 6R2 := R2 − 2 ∗ R1Add −1 times t he 1st equation to the 3rd equation:x − y = 2y − z = −12y + z = 4Add −2 times the 2nd equation to the 3rd equation:x − y = 2y − z = −13z = 6The elimination is completed, and we can solve thesystem by back substitution. However we may aswell proceed with elementary operations.Multiply t he 3rd equation by 1/3:x − y = 2y − z = −1z = 2Add the 3rd equation to the 2nd equ ation:x − y = 2y = 1z = 2Add the 2nd e quation to the 1st equation:x = 3y = 1z = 2System of linear equations:x − y = 22x − y − z = 3x + y + z = 6Solution: (x, y , z) = (3, 1, 2)Another example.x + y − 2z = 1y − z = 3−x + 4y − 3z = 1Add the 1st equ ation to the 3rd equation:x + y − 2z = 1y − z = 35y − 5z = 2Add −5 times the 2nd equation to the 3rd equation:x + y − 2z = 1y − z = 30 = −13System of linear equations:x + y − 2z = 1y − z = 3−x + 4y − 3z = 1Solution: no solution (inconsistent system).Yet another example.x + y − 2z = 1y − z = 3−x + 4y − 3z = 14Add the 1st equ ation to the 3rd equation:x + y − 2z = 1y − z = 35y − 5z = 15Add −5 times the 2nd equation to the 3rd equation:x + y − 2z = 1y − z = 30 = 0Add −1 times the 2nd equation to the 1st equation:x − z = −2y − z = 30 = 0⇐⇒x = z −2y = z + 3Here z is a free variable.It follows th atx = t − 2y = t + 3z = tfor some t ∈ R.System of linear equations:x + y − 2z = 1y − z = 3−x + 4y − 3z = 14Solution: (x, y , z) = (t −2, t + 3, t), t ∈ R.In vector form, (x, y , z) = (−2, 3, 0) + t(1, 1, 1).The set of all solutions is a line in R3passingthrough the point (−2, 3, 0) in the direction(1, 1, 1).MatricesDefinition. A matrix is a rectangular array of numbers.Examples:2 7−1 03 3,2 7 0.24.6 1 1,3/55/84, (√2, 0, −√3, 5),1 10 1.dimensions = (# of rows) × (# of columns)n-by-n: square matrixn-by-1: column vector1-by-n: row vectorSystem of linear equations:a11x1+ a12x2+ ··· + a1nxn= b1a21x1+ a22x2+ ··· + a2nxn= b2·········am1x1+ am2x2+ ··· + amnxn= bmCoefficient matrix and column ve ctor of theright-hand sides:a11a12. . . a1na21a22. . . a2n............am1am2. . . amnb1b2...bmSystem of linear equations:a11x1+ a12x2+ ··· + a1nxn= b1a21x1+ a22x2+ ··· + a2nxn= b2·········am1x1+ am2x2+ ··· + amnxn= bmAugmented matrix:a11a12. . . a1nb1a21a22. . . a2nb2...............am1am2. . . amnbmElementary operations for systems of linearequations c orrespond to elementary row operationsfor augmente d matrices:(1) t o multiply a row by a nonzero scalar;(2) t o add the ith row multiplied by some r ∈ R tothe jth row;(3) t o interchange two rows.Remark. Rows are add ed and multiplied by scalarsas ve ctors (namely, row
View Full Document
Unlocking...