### Create a StudySoup account

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

Already have a StudySoup account? Login here

# NUMERICAL LINEAR ALGEBRA MATH 526

GPA 3.51

### View Full Document

## 37

## 0

## Popular in Course

## Popular in Mathematics (M)

This 2 page Class Notes was uploaded by Cassidy Grimes on Monday October 26, 2015. The Class Notes belongs to MATH 526 at University of South Carolina - Columbia taught by Staff in Fall. Since its upload, it has received 37 views. For similar materials see /class/229542/math-526-university-of-south-carolina-columbia in Mathematics (M) at University of South Carolina - Columbia.

## Reviews for NUMERICAL LINEAR ALGEBRA

### 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: 10/26/15

MATLAB LAB FOR MATH 526 Project 2 ITERATIVE METHODS AND CONJUGATE GRADIENT Additional Notes ITERATIVE METHODS We now return to the semester7s rst problem7 solving Ax b when A is n by n and invertible The unique solution is7 of course7 x A lb7 but computing A 1 is too costly when n is large Gaussian elimination and LU factorization are cheaper7 but their cost is still on the order of n3 ops unless A takes a special form These methods are called direct methods because they start computing the exact solution directly without any intermediate steps lterative methods take a different approach and start with an initial guess to the solution and then use a relatively cheap method to improve that solution This process is then iterated7 and the approximation hopefully converges to the true solution Section 93 discusses three important iterative methods7 the Jacobi method7 Gauss Seidel method7 and successive overrelaxation SOR CONJUGATE GRADIENT METHOD This project focuses on one particular iterative algorithm known as the Conjugate Gradient method CG It is part of a broader class of iterative methods known as Krylov subspace methods We will treat the matrix A as a black box algorithm where we assume that we can use a subroutine to multiply A times a vector but we do not have access to the individual entries of A CG is generally the fastest method to solve Ax b when A is known to be symmetric positive de nite The so called k th Krylov subspace Kk of A and b is de ned as the span of the vectors b7 Ab7 A2b77 Ak lb It is a subspace of R usually with dimension k For each k CG nds xk the projection of the true solution x onto Kk As k increases7 typically Kk is a larger subspace7 and so eventually when k n7 Kn R and so xn is the true solution Do you see why this is not always true The advantage to these methods is that generally as k increases7 xk is a better approximation of the true solution x7 and so we can sometimes stop when k is much smaller than n This gives us a reasonably good approximation to the true solution but at a cost on the order of only knz ops instead of 713 The Conjugate Gradient algorithm can be optimized so that in each iteration the only costs are one matrix vector multiplication7 two dot products7 and three vector plus a scalar times another vector operations See Activity and Assignment problem 1 CONJUGATE GRADIENT VECTOR Conjugate gradient vector is the gradient in the sense that it is the search vector That is7 to compute xk we start at xk1 and go in the pk direction Recall from vector calculus that the gradient vector is the direction in which the function is increasing most rapidly The distance we go in that direction is chosen to minimize the norm of the residual I39k This minimization is with respect to the A l norm HI39HAil rTA lr Any symmetric positive de nite matrix de nes a norm The most common norm is April 15 2009

### 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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "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."

#### "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.