### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CSCI 124 with Professor Vora at GW (2)

### View Full Document

## 26

## 0

## Popular in Course

## Popular in Department

This 7 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 26 views.

## Reviews for Class Note for CSCI 124 with Professor Vora at GW (2)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/07/15

Gaussian Elimination Notes for CSci 124 Poorvi L Vora September 24 2006 Gaussian Elimination is a simple algorithm for nding the solution to a set of linear equations It is one of the most used of all algorithms for solving linear equations because of its ease of implementation and robustness to error in the equations Let us look at one example where the set of equations has exactly one solution 3u5vw 477771 6u11v4w 177772 73uv72w 677773 We rst use equation 1 to eliminate the variable u from equations 2 and 3 We do this by rst identifying the pivot which is the coef cient of u in equation 1 This should be nonzero In this case it is 3 We then subtract from equation 2 2 times equation 1 this guarantees that the coef cient of u will be zero in the new equation 2 which is 6 27gxlv2w7777772 In class we used 2 to denote this equation but as the number of equations grows large this becomes cumbersome so we retain the numbers as they are Similarly we subtract from equation 3 73 times equation 1 this guarantees that the coef cient of u will be zero in the new equation 3 which is 73 37x l6v7w1077773 Our new equations are now 3U 51 w 4 7 7 77 1 U 2w 77 7 7 77 2 61 7 w 10 7 7 77 3 We repeat this process to identify a pivot l and a new equation for equation 3 to get 3U 51 w 4 7 7 77 1 U 2w 77 7 7 77 2 7 13w 52 7 7 77 3 Gaussian EliminationVoraGWU 2 As the last equation contains only one nonzero term we now backsubstitute starting with the last equation 3 52 w Tl 74 and substituting this value into all other equations Bu 51 47748 7777 l v 7772x74 7777 2 That is Bu 51 8 77771 U l 7 7 77 2 Then we go to the next equation up that is to 2 1 7 7 1 U 1 and substitute its value back into all previous equations 3u875x1377771 to get only one unsolved equation Bu 3 7 7 7 71 Going to this next 3 1 u 7 3 And the solution is u 11 1 w 74 1 More Formally Suppose you have the following m equations in n unknowns where m1 m2 denote the un knowns 111951 0112962 aina n bi i i 1 121951 0122962 1mm 52 i i i 2 am11 am z amna n bm r r m 11 Algorithm Gaussian Elimination We rst examine the algorithm where the equations are such that exactly one solution exists In particular this requires that m 71 though this is not all that is required Gaussian EliminationVomGWU 3 fori 1 to n 71 pivot a Assuming exactly one solution exists pivot 7 0 Use it to eliminate the 2 column in all later equations That is eliminate a 1 for all other rows k greater than 2 Do this by subtracting a pivot times the 2 row for k 1 to 71 am factor pl UOt rowk rowk 7 factor gtk rowk endfor endfor Back substitute fori n downto 1 g ml 7 Mi fork i 7 1downto 1 bk7 xi aim endfor Writing the algorithm in the above form also helps us count the main steps required to perform gaussian elimination we count only multiplications or divisions Consider the outer loop in the elimination For the rst value of i 1 the inner loop is performed 71 7 1 n 7 i times for the n 7 i rows following the ith row The operation in the inner loop consists of subtracting a multiple of the 2 row from the nonzero terms in the other rows That is it consists of n 1 n 7 i 2 operations including the operations on the right hand sides of the equations This is because there are n 7 i 1 nonzero terms on the lhs and 1 on the rhs Hence the total number of operations performed in the elimination loop is l i n n71 2n7in7i2 jj2 i1 1 thnm mjlg g 6 2 3 x H When n is large the n3 term dominates That is when n is large doubling its size multiplies the number of computations by about eight 12 Exercises Solve the following sets of linear equations using gaussian elimination 1 Qu 61 7 4w 18 Bu 101 7 9w 27 5U 7 101 10w 710 Gaussian Eliini39nationVomGWU 4 2 31 81 4w 7 31 101 7 2w 73 6U 7 101 10w 78 3 u U 2w 2 5U 101 9w 4 Qu 7 81 3w 13 13 When the Algorithm of Section 12 Fails The algorithm of section 12 fails when the value of pivat is zero and it is not possible to divide by it In this case the rst step is to nd an equation with a nonzero pivot for the variable to swap the positions of the equations and to proceed Consider the following example u 21 7 4w 72 31 61 7 9w 73 5U 7 101 10w 720 This reduces to u 21 7 4w 72 3w 3 7 201 30w 710 The second pivot is zero Swap the second and third equations to get u 21 7 4w 72 7 201 30w 710 3w 3 and a pivot of 720 However as the third equation does not have a term with u this is the nal form note that if there were four or more equations the others would have terms with v The solution is easily seen to be u 721 2 and w 1 On the other hand if there is no remaining equation with a nonzero pivot for the variable then the set of equations is singular It either has no solutions or an in nite number of solutions In this case proceed to the next variable and proceed with elimination At the very end you will be left with at least two equations each consisting of the same one unknown Reduce the equations as you normally would If all equations that do not contain unknowns are of the form 0 0 you have a set of consistent equations with an in nite number of solutions See the following example u 21 7 4w 72 31 61 7 9w 73 5U 101 10w 20 Gaussian Eliini39nationVomGWU 5 This reduces to u 21 7 4w 72 3w 3 30w 30 Notice that there is no other equation with a nonzero coef cient for 1 hence the set of equations is singular Proceed as you would looking now for a pivot for the next variable w u2v74w72 3w3 0 0 and the set of equations is consistent with and in nite number of solutions w l and u 212 2 If the previous set of equations had been slightly different however say u 21 7 4w 72 31 61 7 9w 73 5U 101 10w 25 It would reduce to u 21 7 4w 72 3w 3 30w 35 and u 21 7 4w 72 3w 3 0 5 If there is any equation of the form 0 c 7 O the set of equations is inconsistent and has no solutions This set of equation is inconsistent and has no solutions 14 Exercises To be done Gaussian EliminationVoraGWU 2 Solutions Section 12 1 21 31 51 2u 2u Backsubstitute w 1 113 10v 101 61 25v 2u6v 2u 142Solutionisu2v3w1 2 31 31 61 31 31 Backsubstitute w 2 111 31 81 10v 101 8U 21 26v 8U 21 31 u 7312 1 and w 2 is the solution 4w 18 9w 27 10w 710 4w 18 3w 0 20w 755 4w 18 3w 0 55w 755 22 3 4 4w 7 2w 73 10w 78 4w 7 6w 710 2w 72 4w 7 6w 710 76w 7152 71 2 79 Gaussian EliminationVomGWU 3 u U 1 2w 2 5U 10U 1 9w 4 2U 8U 1 3w 13 u U 1 2w 2 5U w 76 7 10U w 9 u U 1 2w 2 5U w 76 3w 73 w 1 u U 0 5U 75 1171 u 1 u 1 U 71 andw 1 is the solution

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.