[PDF] [PDF] Gaussian Elimination and Back Substitution

[PDF] 3 Matrix Algebra and Applications - Mathematical Sciences : UTEP

Chapter 3 Matrix Algebra and Applications 3 2 Matrix Multiplication Suppose we buy 2 CDs at $3 each and 4 Zip disks at $5 each We calculate our total cost

[PDF] 4048_y18_sy Maths O Level for 2018 - SEAB

An approved calculator may be used in both Paper 1 and Paper 2 multiplication and division of simple algebraic fractions such as:

[PDF] Cours de mathématiques M22 Algèbre linéaire

3 fév 2014 · Multiplication de matrices Inverse d'une matrice : systèmes linéaires et matrices élémentaires 29 6 FR exo7 emath 2 720 58 This will involve using a calculator or a table of trigonometric functions

[PDF] MATHEMATICS SYLLABUSES

9 4 problems involving addition, subtraction and multiplication of matrices calculation of the standard deviation for a set of data (grouped and ungrouped)

[PDF] NumPy Reference - Numpy and Scipy Documentation

18 oct 2015 · Mathematical functions with automatic domain (numpy emath) Warning: In place operations will perform the calculation using the precision decided by It has certain special operators, such as * (matrix multiplication) and

[PDF] NumPy Reference - Numpy and Scipy Documentation

15 mai 2011 · 3 25 Mathematical functions with automatic domain (numpy emath) For 2-D arrays it is equivalent to matrix multiplication, and for 1-D arrays to inner product of vectors By default, calculate the product of all elements:

[PDF] Water ninja trolling motor - Squarespace

rational expressions free algebra equation solver download Mortgages Graduate how matrix eBooks permutation and the combination of how to use the ti 83 Emath ks3 paper 1, math expressions in third class, how to graph decimal using 

[PDF] Gaussian Elimination and Back Substitution

Multiplying both sides of an equation by a scalar By working with the augmented matrix instead of the original system, there is no need to continually

[PDF] matrix multiplication calculator online

[PDF] matrix multiplication calculator with steps

[PDF] matrix multiplication calculator with variables

[PDF] matrix multiplication calculator wolfram

[PDF] matrix multiplication example

[PDF] matrix multiplication properties

[PDF] matrix operations

[PDF] matrix power

[PDF] matrix representation of graphs

[PDF] matrix row reduction

[PDF] matrix rref calculator wolfram

[PDF] matrix simultaneous equation calculator

[PDF] matrix solver

[PDF] matrix ti 89

[PDF] matrix vector multiplication c++

Jim Lambers

MAT 610

Summer Session 2009-10

Lecture 4 Notes

These notes correspond to Sections 3.1 and 3.2 in the text.

Gaussian Elimination and Back Substitution

The basic idea behind methods for solving a system of linear equations is to reduce them to linear equations involving a single unknown, because such equations are trivial to solve. Such a reduction is achieved by manipulating the equations in the system in such a way that the solution does not change, but unknowns are eliminated from selected equations until, nally, we obtain an equation involving only a single unknown. These manipulations are calledelementary row operations, and they are dened as follows:

Multiplying both sides of an equation by a scalar

Reordering the equations by interchanging both sides of theith andjth equation in the system Replacing equationiby the sum of equationiand a multiple of both sides of equationj The third operation is by far the most useful. We will now demonstrate how it can be used to reduce a system of equations to a form in which it can easily be solved.

ExampleConsider the system of linear equations

x

1+ 2x2+x3= 5;

3x1+ 2x2+ 4x3= 17;

4x1+ 4x2+ 3x3= 26:

First, we eliminatex1from the second equation by subtracting 3 times the rst equation from the second. This yields the equivalent system x

1+ 2x2+x3= 5;

4x2+x3= 2;

4x1+ 4x2+ 3x3= 26:

Next, we subtract 4 times the rst equation from the third, to eliminatex1from the third equation as well: x

2+ 2x2+x3= 5;

1

4x2+x3= 2;

4x2x3= 6:

Then, we eliminatex2from the third equation by subtracting the second equation from it, which yields the system x

1+ 2x2+x3= 5;

4x2+x3= 2;

2x3= 4:

This system is inupper-triangular form, because the third equation depends only onx3, and the second equation depends onx2andx3. Because the third equation is a linear equation inx3, it can easily be solved to obtainx3=2. Then, we can substitute this value into the second equation, which yields4x2= 4. This equation only depends onx2, so we can easily solve it to obtainx2=1. Finally, we substitute the values ofx2andx3into the rst equation to obtainx1= 9. This process of computing the unknowns from a system that is in upper-triangular form is calledback substitution.2 In general, a system ofnlinear equations innunknowns is in upper-triangular form if theith equation depends only on the unknownsxi;xi+1;:::;xn, fori= 1;2;:::;n. Now, performing row operations on the systemAx=bcan be accomplished by performing them on theaugmented matrix Ab=2 6 664a

11a12a1njb1

a

21a22a2njb2......j...

a n1an2annjbn3 7 775:
By working with the augmented matrix instead of the original system, there is no need to continually rewrite the unknowns or arithmetic operators. Once the augmented matrix is reduced to upper triangular form, the corresponding system of linear equations can be solved by back substitution, as before. The process of eliminating variables from the equations, or, equivalently, zeroing entries of the corresponding matrix, in order to reduce the system to upper-triangular form is calledGaussian elimination. The algorithm is as follows: forj= 1;2;:::;n1do fori=j+ 1;j+ 2;:::;ndo m ij=aij=ajj fork=j+ 1;j+ 2;:::;ndo a ik=aikmijajk 2 end b i=bimijbj end end

This algorithm requires approximately

23
n3arithmetic operations, so it can be quite expensive ifn is large. Later, we will discuss alternative approaches that are more ecient for certain kinds of systems, but Gaussian elimination remains the most generally applicable method of solving systems of linear equations. The numbermijis called amultiplier. It is the number by which rowjis multiplied before adding it to rowi, in order to eliminate the unknownxjfrom theith equation. Note that this algorithm is applied to the augmented matrix, as the elements of the vectorbare updated by the row operations as well. It should be noted that in the above description of Gaussian elimination, each entry below the main diagonal is never explicitly zeroed, because that computation is unnecessary. It is only necessary to update entries of the matrix that are involved in subsequent row operations or the solution of the resulting upper triangular system. This system is solved by the following algorithm forback substitution. In the algorithm, we assume thatUis the upper triangular matrix containing the coecients of the system, andyis the vector containing the right-hand sides of the equations. fori=n;n1;:::;1do x i=yi forj=i+ 1;i+ 2;:::;ndo x i=xiuijxj end x i=xi=uii end This algorithm requires approximatelyn2arithmetic operations. We will see that when solving systems of equations in which the right-hand side vectorbis changing, but the coecient matrix Aremains xed, it is quite practical to apply Gaussian elimination toAonly once, and then repeatedly apply it to eachb, along with back substitution, because the latter two steps are much less expensive. We now illustrate the use of both these algorithms with an example.

ExampleConsider the system of linear equations

x

1+ 2x2+x3x4= 5

3x1+ 2x2+ 4x3+ 4x4= 16

4x1+ 4x2+ 3x3+ 4x4= 22

2x1+x3+ 5x4= 15:

3 This system can be represented by the coecient matrixAand right-hand side vectorb, as follows: A=2 6

641 2 11

3 2 4 4

4 4 3 4

2 0 1 53

7

75;b=2

6 645
16 22
153
7 75:
To perform row operations to reduce this system to upper triangular form, we dene the augmented matrix

A=Ab=2

6

641 2 11 5

3 2 4 4 16

4 4 3 4 22

2 0 1 5 153

7 75:

We rst dene

~A(1)=~Ato be the original augmented matrix. Then, we denote by~A(2)the result of the rst elementary row operation, which entails subtracting 3 times the rst row from the second in order to eliminatex1from the second equation:

A(2)=2

6

641 2 11 5

04 1 7 1

4 4 3 4 22

2 0 1 5 153

7 75:
Next, we eliminatex1from the third equation by subtracting 4 times the rst row from the third:

A(3)=2

6

641 2 11 5

04 1 7 1

041 8 2

2 0 1 5 153

7 75:
Then, we complete the elimination ofx1by subtracting 2 times the rst row from the fourth:

A(4)=2

6

641 2 11 5

04 1 7 1

041 8 2

041 7 53

7 75:
We now need to eliminatex2from the third and fourth equations. This is accomplished by sub- tracting the second row from the third, which yields

A(5)=2

6

641 2 11 5

04 1 7 1

0 02 1 1

041 7 53

7 75;
4 and the fourth, which yields

A(6)=2

6

641 2 11 5

04 1 7 1

0 02 1 1

0 02 0 43

7 75:
Finally, we subtract the third row from the fourth to obtain the augmented matrix of an upper- triangular system,

A(7)=2

6

641 2 11 5

04 1 7 1

0 02 1 1

0 0 01 33

7 75:
Note that in a matrix for such a system, all entries below themain diagonal(the entries where the row index is equal to the column index) are equal to zero. That is,aij= 0 fori > j. Now, we can perform back substitution on the corresponding system, x

1+ 2x2+x3x4= 5;

4x2+x3+ 7x4= 1;

2x3+x4= 1;

x4= 3;quotesdbs_dbs20.pdfusesText_26