### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Special Topics CS 8803

GPA 3.81

### View Full Document

## 6

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 8803 at Georgia Institute of Technology - Main Campus taught by Chongwoo Park in Fall. Since its upload, it has received 6 views. For similar materials see /class/234087/cs-8803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

## Reviews for Special Topics

### 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: 11/02/15

CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 23 November 27 2007 Linear Programming Fundamental Theory EX max4cl 5332 St H1 2 4331 5332 S 56 H2 5331 3332 g 105 H3 331 2332 S 56 331 Z 0 332 Z 0 Set defined by linear inequalities 3 possibilities 1 No feasible region 2 Feasible and unbounded 3 Feasible and bounded Want to minimize linear objective function 2 over all feasible region If the constraints from a feasible and bounded set min value of z is obtained at a vertex an extreme point CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0113 Linear Programming Fundamental Theory Standard Form LP min 0T3 max 0T3 gt min CTc 331 0 332 0 StAcbcZO Z 3quot 0 Change of variables If ij Z bj bj 0 let 33339 bj If cjiS free then scy my 2 0 and 223 2 0 If M1331 6112332 39 39 39 ainivn 2 51561 2 0 then M1331 Clin82 amicn 9239 5239 33239 Z 091 Z 0 6111331 6112562 39 ainch 3 61331 2 0 gt 6111331 a12 2 39 39 39 ainlvn 91 523331 2 079239 Z 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0213 Linear Programming Fundamental Theory For simplicity will assume 5 2 0 and rankM m A m x n m lt 72 Consider equality constraint Ax b A m x 72772 lt n rankA m infinitely many solutions underdetermined Basic solution to Ax 9 pick any linearly independent m columns of A say aj E JB Let B m x m matrix where m column of B are ajj 6 JB Then B is nonsingular can solve BxB b and 33 is unique CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0313 Linear Programming Fundamental Theory EX 4331 332 333 2 56 5331 3332 334 105 61 2322 335 56 331 4 1 1 32 56 5 3 1 63 105 1 2 1 34 56 335 Ex1 JB 345 B 13 B333 5 x3 5 c 005610556T EX2 JB 2 145 14 4 56 14 0 B 5 1 B EB 105 c3 35 c 0 1 1 56 42 35 42 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0413 Linear Programming Fundamental Theory Basis any set of m column of A which forms an m x m nonsingular matrix B Basic solution solution to BxB b All nonbasic 323 0 j g JB Basic feasible solution any basic solution for which 323 2 0 Degenerate BFS a BFS for which one or more 323 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0513 Linear Programming Fundamental Theory Fundamental Theorem of Linear Programming p19 Luenberger Given a linear program in standard form min 0T3 St An b a Z 0 where A m X n rankA m 1 If El a feasible solution El a basic feasible solution For example we can find a solution to an underdetermined system Ax b RART 0QTcb based on the QRD of AT AT 2 Q 0 LetQTzcz 9 Z RT 0bRTyb CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0613 Linear Programming Fundamental Theory Proof Assume exactly p of 33 are greater than 0 mm cpap b a a1 ap are linear independent then p g m ifp m done ifp lt m then can find m p vectors from A st they form m linearly independent columns Since rankM m set 33 0 for these extra columns CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0713 Linear Programming Fundamental Theory b m ap are linear dependent 3 711 7 m E R Si mm 312 ypap 0 Can assume at least one yi gt 0 We have mm cpap b eylal eygag eypap O 5 31 591 5 32 530 2 39 39 39 3319 59pap b for any 6 gt 0 331 y1 is a solution to a1 ap c bfor any 6 3371 6971 Since at least one yi gt O as 6 increases at least one component will decrease Let 6 min yi gt 0 then a 63 with this 6 is feasible and has at most p 1 positive variables coefficients of ai S Repeating the process can eliminate positive variable until we have feasible solution with linear independent columns CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0813 Linear Programming Fundamental Theory 2 If 3 an optimal feasible solution 3 an optimal basic feasible solution 3 Equivalence of extreme points and basic solutions A m X n m lt n meA m K cAc 656 2 O c iS an extreme point ofK iffzc is a BPS to An 63 2 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0913 Linear Programming Simplex Method Pivoting Basic Idea Assume that given a BFS we can test whether it is the desired optimal solution If not obtain another BFS by choosing one of the nonbasic column of A Le choosej e JB and use it to replace one the basic columns Suppose we have B and 333 st BxB b 333 2 0 We replace one column of B say ap p 6 JB with aq q e JB and get a new basis matrix B New basis vector 333 will satisfy B scB I But 5ch 2 0 lfp and q are chosen properly then 333 2 0 Objective function z 0T3 2 0161 With B39 as a basis B39mB 6 z cglchI i1 Test for minimal solution assume we have a basis B and corresponding BFS 63 Z 0 then B330 2 b zo ch0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01013 Linear Programming Simplex Method Suppose we increase mg q g JB from its current value seq 2 0 So BxB cqaq b where 333 is a vector and mg is a scalar B333 2 b cqaq gt 63 B1b ch1aq Let we have 333 330 5 3qu Suppose cq gt 0 then T z 0363 Cqscq T CB 5 30 mqu qucq T zO 33qCByq Cq5 3q zO Cq zq cq where T zq 03 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01113 Linear Programming Simplex Method So we can only decrease 2 by increasing cq if cg zq lt 0 if cg zq 2 0 for all q g JBthen seq 2 0 is correct and q should stay as nonbasic Let zj egg33339 e JB where yj B laj If 03 zj 2 Ofor allj e JB the current B and 323 B lb 2 0 gives the min solution with z chB 20 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01213 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 12 October 2 2007 Classical GramSchmidt CGS for Reduced QRD Given linear independent vectors a1 an E Rm find an orthonormal basis for spana1 an ie compute the reduced QRD forA a1 an LetQ1 q1 qn FromAQ1R 7 11 7 17 l 1 an 2 11 In T7177 r11 0 al 11 In T11Q1 0 r12 7 22 a2 11 In 0 T12 11 T22 12 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0117 Classical GramSchmidt CGS for Reduced QRD Fork 2 1 n we have ah 2 1ajkqj 1 Since qgs are orthogonal qgak qglt lrijj me i 1 k We assume that TankA n so TM 5 0 From 1 qk 31k Sig 11mm Consider qk as a unit vector qk H2 1 in the direction of Zk We ng qfami CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0217 Classical Gram Schmidt CGS for Reduced QRD Exw2 abazQMIz r r gt 0 r22 1 21 it a 3201 normalized 2 0qu r12 Iier WIqu qiraz gt 0 a qiraz P2 112 Giff12W P2 32 22 12 lpzllz 5555mch Numeuca Me m mEamnuutmna smenceandEnnmeevmn MmuxcamnmmmmrnlW Classical GramSchmidt CGS for Reduced QRD CGS Classical GramSchmidt Algorithm Fork1n Fori1k 1 1 Tile qipak end Zk Gk 211 Tiin 2 We H Zk H2 3 1k zkTkk 4 end Show that CGS takes 2mm2 flops 2mZZ1U 1 2mZZ1U 1 2m m m 2214k 1 3 x 2mm2 flops CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0417 Classical GramSchmidt CGS for Reduced QRD In the k th step the k th column of Q and the k th column of R are computed Numerically unstable since nearly equal numbers can be involved in subtraction Ex pzlf g Ir I9391 0 is small ie when a1 and 12 are almost linearly dependent CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0517 QR Factorization 64 QRD by GramSchmidt a1an6 Rm gt q1 qn orthogonal gComputeQ q1 an 1 m a1 llalllg 2 Z2 2 a2 02q1 0 qul qifag agqipql gt 012 qlTag Q2 z2 WM 3 Z3 2 a3 181m 2q2 0 qsz3 qlTag lqqul 2q1Tq2 0 qu3 q2Ta3 51q2Tq1 2q2Tq2 23 as q1Ta3ql qgmm Q z3 stllg CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0617 QR Factorization qull2 012 i Compute R Hz2H2 Hznlb a1 9111611112 a2 012m 122Hg Q2 a1 a2 q1 q2 Hq1H2 21 ie orthogonal 2 uppertriangular CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0717 QR Factorization 65 QRD by Modified GramSchmidt 651 Comparison between CGS and MGS 3 CGS In the kth step kth column of Qland kth column of R are computed a1 anlzhl qn T11 quot Mn a1q1 qn I Tllql a2 11 qn 0 T12q1r22q2 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0817 QR Factorization i MGS In the kth step kth column and kth row of R are computed MT a1 anlzlql gm 2 T n Wit where 7quot is the Ms 39L 1 T ith row of R l CGS amp MGS where we can only get reduced QRD no full QRD E Form 2 2 MGSCGS l M68 is numerically more stable than CGS CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0917 QR Factorization 652 MGS Method ilntuition T1 72 AQ1R2gta1 anq1 In 22ng a quot1 a a a eg A E R5 R c c a a a a a a a a a Q1T1T a 3 a as a a a a a a a a a a a CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01017 QR Factorization a 01313 a 0133 q2r2T c 03333 0332 a 0133 c 0cc 3932 39003 c 0033 qsa c 0013 0013 a 001 c 00c 333356 01313 0033 3 333356 01313 0013 AZqinT 33313 0133 0033 i1 333356 01313 0013 333356 01313 0033 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01117 QR Factorization I Algorithm Define A the kiteration intermediate result by k l n 0 AU A ZQinZQiTK i1 izk where O E Rmxk 1 and A E Rmx k1 Consider the k th column 0 Akek qirg kk izk liter 63k Qk1rg1 k t angek qk7 kkOOO CS 8803 NMC Numerical Methods in Computational Science and Endineerind Matrix Comoutations 01217 QR Factorization 130 Aw gamer qk1rf1 Inn I If A z B where z E RmX1 and B E Rmx k then since 7 qk39rkk we have we Z H2 and qk Zrkk and since qf0 z B 773 we have Tkk1 Iquotkn qu 0 Altk1 Z Mir ik1 TL T T qm 1ka izk O z B qkOO Tkk Tkk1 Tkn Altk1 B qk l kk1 Tim CS 8803 NMC Numerical Methods in Computational Science and Enaineerina Matrix Computations 01317 QR Factorization MGS Algorithm for k 1 n m 12 This E 03k 1 i1 forz 1 m aik ailsrisk 2 end forj k 1 n Tkj Z aikaij 3 i1 fori 1 2 m cm Cw aikaj 4 end end end Computational complexity 1 2mn 2 mn 34 221 4mm k m 2mn2 fbps CS 8803 NMC Numerical Methods in Computational Science and Endineerind Matrix Computations 01417 QR Factorization Comparison Between HouseholderGivens amp CGSMGS I Householder and Givens methods generate Q that is numerically more orthogonal than Q generated by M68 and CGS Imll or Imll C39 H S looog In or IQMQE In x cpK2A where K2 is the 2nd norm where QH Householder QG Givens QOCGS QMMGS I Householder and Givens are more expensive if we want Q1 Have to accumulate entire Q to get Q1 The computation complexity of CGSMGSz 2mn2 CS 8803 NMC Numerical Methods in Computational Science and Endineerind Matrix Computations 01517 Least Squares Problem Properties of QRD Theorem If A a1 an E Rm has rankA n and QRD of A is AzQ R whereQQ1 Q291quot39Qn 0 V V then A 2 CAR and spana1ak spanq1 qk for all k 1 n RangeA RangeQ1 and RangeiA RangeQ2 P0AQlt f gt Q1Q2 Q1R T11 Tm T7277 ak 21 gm 6 spanq1qk gt 31an Gk C spanq1 gig and dimltspana1ak dimq1qk k CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01617 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 6 September 6 2007 Symmetric Positive De nite amp Cholesky Decomp 5 Symmetric Positive Definite amp Cholesky Decomp 51 Symmetric Positive Definite Matrix A symmetric positive definite SPD Q AT 2 A and cTAzc gt 0 for any 330 5 1 e A g 1 4 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0110 Symmetric Positive De nite amp Cholesky Decomp Lemma In a SPD matrix max aij lies on diagonal and all 1 SiSnJ Sj lt77 diagonal elements are positive In 2 61 en Since A is symmetric positive definite am 6Aei gt Oforanyz39 1 n 80am gt0 6i ejTAei 6939 aii ajj 2am gt 0 6i jTA i 6939 Clii Cljj 261 gt 0 80 we have aij S W S max amajj CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0210 Symmetric Positive De nite amp Cholesky Decomp 52 Cholesky Factorization Any SPD matrix A 6 RMquot can be decomposed to A GGT where G is lower triangular G has W unknowns To get G we have to solve W equations Review A LU L has W unknowns U has W unknowns totally nZequations If A is SPD and its Cholesky decomposition is A GOT then A3 b can be solved by solving 1 Gy b for y and 2 GT3 2 y for c When n 2 a11 Q12 911 911 921 9amp1 911921 Q12 Q22 921 922 922 921911 931 932 2 2 G12 2 G12 2 2 2 MM 911 a113921 911 T113922 5522 93921 an A CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0310 Symmetric Positive De nite amp Cholesky Decomp eg Show that when A is SPD gt 0 hint For any 8 g 1 a 12 gtOsinceAis SPD 1 a12 Q22 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0410 Symmetric Positive De nite amp Cholesky Decomp Equate z j entries forz 2 j we have 339 aij E gikgjk k1 3 1 When j i ajj gjjgjj I 992 ltgt 1 gjj Whenj lt z ajj j l 9ka k1 j l gikgjk k1 gij flop count i i 2j z n3 flops j1ij1 CS 8803 NMC Numerical Methods in Computational Science and Enaineerina Matrix Computations 0510 gjj 1 2 Symmetric Positive De nite amp Cholesky Decomp Algorithm forj 1 n compute gjj from Eq 1 forz39 j 1 n compute gij from Eq 2 end end CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0610 Symmetric Positive De nite amp Cholesky Decomp i A 0 where A e RMquot 0 e Rm and Tank0 nm 2 n then A is SPD Suppose 33 0 st cTAzc g 0 which means cTOTOsc 1012 3 0 So C I2 0 lt2 056 0 Contradiction because Tank0 72 Q null0 0 but we found a 0 in null0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinoi Matrix Computations 0710 Symmetric Positive De nite amp Cholesky Decomp i Theorem Cholesky Decomp runs to completion iff A is SPD In practice we use Cholesky decomp to check whether a matrix is SPD gT where oz is a rough proof Let A be SPD Write A as A a B 9 scalar After 1 step of Cholesky decomposition 0 a QT oz 9T 9 0 H g B 171 1 3 A B 3HsoHB amp 3 CS 8803 NMC Numerical Methods in Computational Science and Enoineerino Matrix Computations 0810 Symmetric Positive De nite amp Cholesky Decomp Claim H is SPD B is symmetric therefore H is symmetric Suppose H is not SPD ie Elzc 0 E Em 1 st cTHzc g 0 9 Consider y a then yTAy cTBzc 3239 33TH C 2 CT B c cTBsc g 0 thus yTAy g 0 A iS not SPD which is a contradiction Hint if we let 3 8 and compute yTAy and relate it to cTHsc can find 3239 T s 9a CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0910 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 13 October 4 2007 Least Squares Problem 74 Solved by Singular Value Decomposition 741 SVD Given any matrix A E Rm Ematrices U V E where U E RmX UTU 1m V e R X VTV 17123 6 Rm when m 2 n or 03971 when m g n and 01 2 02 2 2 an 2 0 are singular values such that A UEVT CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 018 Least Square Problem Full Rank f l Real case AQ ff QTA A UEVT UTAV 23 I Complex case AQ 1 QHQzlwhereQHz TQHA RE Ctan I A UEVT UTU I VHV I z diag01 0 with 71202ZZanZOandUEmemVEmenEERmxn UHAVE R 7 E Ome 0 i Q CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 028 Least Square Problem Full Rank 742 Symmetric Eigenvalue Decomposition SVD in Symmetric Cases For a given symmetric matrix B 6 RM there exists an orthogonal matrix Q ql qn st QTBQ A 2 diaqu An where Ai are eigenvalues and qi are eigenvectors QTBQAltSBQQAltS CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 038 Least Square Problem Full Rank 743 Properties ofSVD Suppose for matrix A E Rmxn n 2 n we have its SVD A UZVT ATA VETUTUZVT VZTZVT where 2T2 diagwi ai AAT UZVTVZTUT UEETUT where 2T2 diagwf 03 0 0 IfE diag01 0 diag01 aT0 0 Le 01 2022 Za gtm1 an 0thenrankA 7quot 31 0 V1 T A UZV U1 U2 0 0 2 where E31 d2ag01 aT With012022Zargt0 RangeA spanU1 NullA spanV2 RangeAT spanV1 NullAT spanU2 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 048 Least Square Problem Full Rank 744 Solving LS 111111 sz 5112 A e Rm 6 e Rm m 2 n Let the SVD of A be AU2VTU1 U2 818 V1 V2 ie rankA 7quot E31 2 diag01 azr Ax 5H2 IIUZVTx b2 IIEVTx UTIJ2 H21 iiiGill 0 0 z d lliz fi CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 058 2 Least Square Problem Full Rank whereVsz y andUsz C z d Since E31 6 RT nonsingular we can find the unique solution for Ely 00w lyzcwyz flc Letting Mac 2 le 6H2 the residual 7quotXLS d where mg is the LS solution 9 Z E31 10 0 IS called minimumnorm solution The solution is L3V where y 21 10 and 2 can be anything VVhenz0stV CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 068 Least Square Problem Full Rank 745 Example A e R6X4a4A 10 1603A 1014 1 05 10 14 A UZVT U 10 VT If we consider the tolerance e st 10 16 lt e and TankA 3 1 1 a 21 05 y 2 a 1014 1014 a If we consider the tolerance e st 10 14 lt e and TankA 2 2iii CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 078 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 25 December 4 2007 Linear Programming Simplex Method Initial Solution Artificial Variables Getting started when initial BFS is not known Introduce artificial variables and solve phase problem mincTa St Ax b a Z 0 A m X n m lt n rankA m Add m artificial variables 91 Qm consider Ax IQ b x g 2 0 We have an initial BFS to the new problem a 0 y b assume 5 2 0 with B I CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations b111 Linear Programming Simplex Method Want to force 3 0 Phase I problem mineTyz wheree StAxI bx ZO 1 1 If 2 0 then original problem has feasible solution 2 If 2 gt 0 the original problem has no feasible solution CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0211 Linear Programming Simplex Method Complexity of Simplex Algorithm Flopsiteration Ax b A E Rm m lt 91 B333 2 b LU with RP is 0m3 and 2 triangular system solve 0m2 Tj Cj 23 Cj GEE 1ng JB 0m2 Omn m ET 2 CB 0m2 Update LU 0m2 Total flopsiteration 0m3 number of iterations gtlt max 0m2 Omn m In the worst case the number of iterations is 0quot Average iterations based on experiments 0m310gn flops CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0311 Linear Programming Duality Linear Programming Duality Duality Definition Primal problem P mmin chAx b a 2 0 Dual problem Dmax bTwlATw g c Primal problem ltgt Dual problem they are related CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0411 Linear Programming Duality Example Primal max 321 2332 3323 st 331 23322333 5334 S 112gt331 23322333 5234335 11 4331 332 2333 2334 2 32gt 4331 332 23332334 336 3 2331 333 3334 2 1 Corresponding dual problem max 11101 3102 ws 1 4 2 1 2 1 0 2 101 2 2 1 3 102 S 5 2 3 0 103 1 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0511 Linear Programming Duality Weak Duality Lemma Main idea P 2 Suppose a is feasible for P and w is feasible for D then 0T3 2 bTw Proof From P Ax b bTw xTATw and ATw g c and a 2 0 SO bTw xTATw g xTC Corollary 1 Suppose we and we are primal and dual feasible and cho bTwo Then we solves P and we solves D Proof Let a be any primal feasible vector then by lemma 0T3 2 bTwo cho 80 320 gives min over all feasible 3 Let 10 be any dual feasible vector then bTw g cho bTwo So we gives max over all feasible w CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations b611 Linear Programming Duality Corollary 2 If P is unbounded then D is not feasible If D is unbounded then P has no feasible solution Proof as exercise Corresponding to every primal basis B 3 a dual vector to st the primal and dual function values are the same Let B be a primal basis and 33 be the basic cost vector Primal objective function z 2333 CEB lb Define a dual vector to by BT10 2 CB ltgt w BTCB then 0T3 GEE lb wa Suppose we consider only primal feasible vector bases so that 323 2 0 When is w BTCB dual feasible CS 8803 NMC Numerical Methods in Computational Science and Endineerind Matrix Computations b711 Linear Programming Duality Relation between Duality and Primality i Relation between optimal solutions Assume we have an optimal BFS for the primal problem with a basis B Then the optimal solution for dual problem is w BTCB BT10 313 aiTw 2 Ci 239 6 JB a1T C1 w 013 an All n inequalities constraints correspond to primal basis are satisfied as equalities Consider primal reduced costs mq wwBwwW Dual feasibility ltgt wTaj g cj for all j ltgt 93 gt 0 for all j ltgt Primal Optimality Thus dual feasibility and primal optimality are equivalent CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations b811 Linear Programming Duality i Relation between objective function value If the primal problem has an optimal solution then the dual problem has an optimal solution and the objective function values are the same Similarly dual gt primal CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0911 Linear Programming Duality OneNorm Minimization as Duality Problem Fz x g gt min 9H2 LS Fz g gt minFZ 9H1 or minFZ gllooi LP OneNorm Min Problem gt Duality Problem gt Primal Problem W 1le 9111 flT f1TZ 91 F 5 ERquf2Tisith rowofFFz g f prZ 9p Letting fZTz 92quot 62 P minpz 2min 52381 62 g fiTz gz g 62 52 2 02392 1 p i1 fiTz 62 g 91 f2Tz 62 g gz 239 1 p total 2p constraints 51 unknowns are z and 6 5p CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01011 L1 Norm Min as Linear Programming Duality 2141 Formulated in Duality problem Ip F Ip F I F LetATz I FER2pxpq2pgtp9 p 1 A 1 IPTERI 1X2PC 9 b 1 w6 F F g 0 z maX bTwATw g c which is a Dual problem min chAx bx 2 0 which is a Primal problem CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations b1111 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 11 September 27 2007 Least Squares Problem Full Rank 7 Least Squares Problem Full Rank 71 Least Squares Problem Givens A E Rm m 2 n and b E Rm want solution to Ax z b overdetermined system ie min lAac 6H2 5C Ax z 5 usually has no exact solution eg A E RSgtlt2 with rankM 2 RA RangeA Axlx E R2 lfb 2 1 2 where 1 E RA and 62 E RHA then 1 2 1ng and 52 b AQS LS Orthogonal Complement Of A RL A z E Rmsz 0 for all w E RA CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0110 Least Squares Problem Full Rank Theorem LS problem mmin le b2 always has a solution The solution is unique iff NullA 0 Le rankA n WhereAsznmZn Proof Let 1 be the projection of 5 onto RA let 2 be the projection of 5 onto Rim st 6 61 52 61 e RA b1 A213 6 RA for all 13 b1 143252 51 AxTbg 0 When acTy 0 lac y 132 Hy consider the orthogonal triangle Thus let p2x lAac 2 Mac b1 62 lAac 61 pc is minimum when Ax b2is minimum Minimum of Ax 61H2 is 0 since bl E RA CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0210 Least Squares Problem Full Rank Claim the LS Solution is unique iff NullA 0 Proof gt Assume the unique solution is 1 If NullA 7 0 we can find a nonzero 322 E NullA ie Am 2 0 hence Ar1 x2 bl x1 x2 is another solution which is a contradiction lt To prove NullA 0 gtsolution is unique Assume solution not unique then 3x1 75 322 st A3121 2 b1 and Am 2 1 where bl is the projection of 5 onto RA Ax1 x2 02191 322 7 0 E NullA which is a contradiction CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0310 Least Squares Problem Full Rank 72 Solved by QR Factorization 111111A19 b2 AQ 1 I where R 1sz 5112 IQTW 112 0 la QT W Solution for L8 is the solution for linear equation Rx a when rankR n CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0410 Least Square Problem Full Rank 73 Solved by Normal Equations Method Theorem If ATAc b 0 then x solves LS problem min le b2 Proof let 3 be any other point Then 1A9 6113 My Ax Ax 6113 My x A28 6 But Ay as e RA and Ag b e RAi so my 611 mo 113 1le 611321le 611 Note ATAac b 0 Cgt ATAx ATb normal equations ATAx 2 AT can be solved when ATA is nonsingular lt gtmnkA n When mmMA n ATA is SPD We can use Cholesky decomposition to solve ATAx ATb x ATA 1ATb is the unique solution of the LS problem CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0510 Least Square Problem Full Rank 1 1 2 S Example A 10 3 b 10 3 10 3 10 3 1 Assume 8 10 t 6 chopped arithmetic acLS 1 K2A 14 X 103 1 flATA 1 Tankx4 2 Tank fKATAD 1 1 10 6 1 Assume 10 t 7 l ATA f 1 1 10 6 E 2390001 where E is solution for flATAc flATb HK2ATA M14 x 103 llmLs 2 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0610 Least Square Problem Full Rank Accuracy of Solution of Normal Equations Assume no roundoff error occurs in forming ATA and ATE then Normal Equations solution 3 satisfies ATA EE 2 AT where E2 z u HAT1H2 and 13 39113 12 mug z MK2ATA u Kazan CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0710 Least Square Problem Full Rank Computation Cost of LS sol by Normal Equations A E Rmxn n Z n TankA 2 716 6 Rmgtlt1 Form C 2 ATA spd which takes mn2 flops Form d 2 AT which takes 2mm flops Compute Cholesky decomposition on ATA GOT which takes ns flops ATAx 2 AT Q CGTx ATb 1 Solve Gy 2 AT for y 2 Solve GT1 2 y for 22 Two steps take 2n2fIOpS Total it requires mm2 ns flops CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0810 Classical GramSchmidt CGS for Reduced QRD Given linear independent vectors a1 an E Rm find an orthonormal basis for spana1 an ie compute the reduced QRD forA a1 an LetQ1 q1 qn FromAleR T11 Tln a1 Tun T11 0 a1q1 qn I T11q1 0 T12 73922 a2 91 gm 0 T12Q1T22Q2 CS 8803 NMC 39 in f 39 Science and Enqineerinq Matrix Computations 0910 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 8 September 13 2007 QR Factorization 6 QR Factorization For solving LS problem we need orthogonalization to reduce matrices to canonical forms QR factorization decomposition and SVD 61 Overview For any matrixA E Rm 3 orthogonal matrixQ E Rmxm QTQ 1m and upper triangular matriXR 6 RM st A Q I 311411131 QRD is not unique R eg A Q 0 Q dzagi1 1 1 1 A 1 1 1 diagi1 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0114 QR Factorization Main QRD algorithms 1 Householder 2 Givens complexity z 2x comp complexity for householder But can selectively zero out some elements 3 GranSchmidt classical one and modified one which is better AQlfllQ1Q2llflQlR Q l is called full QRD and Q1R is called reduced QRD QTQ QQT I however QlTQl LQ1Q1T 1 A Q Q R eAT RT 0 1T 1 2 0 T RT 0 1TQ2RT 030soQ2isinthenullspaceof gt ATQ2 2 AT CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0214 QR Factorization 62 QRD by Householder Method 621 Householder Reflection Householder matrix is also called elementary reflector len 2va In 2 1 fv gwherev0 R UT Hng u 1 Properties 1 PT P 2 PTP I ie P is orthogonal 3 P2 I 4 Given a 0 E Rm we can find 22 so that gt1 T 0 P32 In 2v zcz ae1z 39u39u 0 CS 8803 NMC Numerical Methods in Computational Science and Endineerind Matrix Computations 0314 QR Factorization T T Ru 2 In 21391 c c 2va 0 1 gt v 83 0461 for some scalars a and 8 gt v c 0461 can scale 22 by scalar and have the same matrix P Pa 21WT a a 232Oc81320c81T32 vTv 32Oc81T32Oc81 232Oc81T32 232Oc81T320c 1 ltxaenTltxaengt 5 ltxae1Tltxae1 61 We want Pa 6 span61 so we want 232Oc81T32 1 Oc 1T93Oce1 0 lt2 2cozelTc cozelTcozel Q a2 cTsc lt2 04 l v as 1 11x15 e1 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0414 QR Factorization 1 1 30 39 1 30 Example 1 c 2 we have 11 2 1 0 2 3 3 0 3 4 4 0 4 P3 I 23 c c 215136 1 1 30 30 39 2 2 1m4916 2 0 3 1m24916 3 0 4 4 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0514 QR Factorization 3 9 6 Example 2 c g with v g P56 2 3 where P L 2g 1 1 0 Which sign to choose in v c 1 1312 61 Choose ifsc1 2 0 Choose ifsc1 g 0 1 1 V30 1 V30 2 2 2 c choose 0 2 instead of v to 3 3 3 4 4 4 avoid cancellation error Cancellation error occurs when two number of very close values are involved in the subtraction eg b 10 t 4 04 01234 x 102 0 01233 x 102 a 0 00001 x 102 gt 01000 x 10 1 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0614 QR Factorization 622 Householder QRD G11 33 33 6 G21 33 33 33 Use A e R4x4 031 33 33 6 G41 33 33 6 G11 4X4 021 1 Find a Householder matrix P1 6 R so that P1 2 G31 G41 3 c c c I 122 3239 3239 Then P114 2 P1 a1 a2 a3 a4 I 132 3239 3239 dig a a CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0714 000 QR Factorization I 022 2 Find a Householder matrix P2 6 R3X3 so that 152 032 2 0112 1 Define P2 A P2 3239 CL39 CL39 CL39 CL39 CL39 CL39 1 I P2P1A A CLI22 13 13 13 56 P2 032 c 1 G33 0112 33 33 CLZ3 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0814 5383838 QR Factorization II 3 Find a Householder matrix 153 e R2X2 so that 153 a Z G43 1 33 33 33 3 Define P3 1 so that P3P2P1A a a 33 p3 5 Letting QT P3P2P1 we have QTA R gt A QR CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0914 QR Factorization In general we need to find Householder matrices n times to find QRD of A E Rmxn form gt n PnP2P1A R P P2P1 is orthogonal since product of orthogonal matrices is orthogonal llflrl ll min lAzc I2 min IQTAzc QT6H2 min 2 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 01014 QR Factorization Algorithm 4 Householder Method for k 1 n determine a Householder matrix 1 of order m k 1 so that akk Tick A 0 Pk aim 1J4 amk 0 A diagIk115kA b diagIk115kb end CS 8803 NMC Numerical Methods in Computational Science and Endineerind Matrix Computations 01114 QR Factorization Complexity Householder Method requires 2n2m g flops If m n 2n2 n 72 ops 2va 2vaa 2vTa Hlnt I vTv a a vTv 1 a UTU v For matrix I 2314 I 2 a1 an U 3 k 1 u is calculated once 39UTai take 2m flops one saxpy 2m flops total 2m 2m X n 2 4mm flops k 214 diagIk1PkA b diagIk1Pkb gt A b dz39agIk115k A b where152 m 1X m l total 4m 1 x n flops k3f nz 2xnz 2k al4Un 2x 02 1 ops and con nue Total 2 4m k 1n k 2 flops 141 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01214 QR Factorization 63 QRD by Givens Method 631 Givens Rotation 06 Cos sml9 c 3 sm 6 cos 6 s 0 00 6 RM G6TG6 12 1 1 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01314 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 17 October 23 2007 Eigenvalue Problem Schur vector eigen vector when matrix is diagonalizable Definition a matrix A is normal iff AH A AAH Typical normal matrices include symmetric matrices orthogonal matrices and skewsymmetric matrices Corollary A E 0quot is normal iff El unitary Q st QHAQ diag1 An Proof c QHAQ D gt A QDQH gt AHA QDHDQH AAH QDDHQH gt AAH AHA gt A is normal gt Assume Schur Decomposition for A Le QHAQ T AHA AAH gt THT TTH gt T is normal Since any normal upper triangular matrix is diagonal T has to be diagonal Thus QHAQ T diagonal CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 0115 Jordan Decomposition If A E 0quot then El nonsingular X st X diagJ1 Jt where AZ 1 t J1 ECmixmi 2mizn 39 1 i1 A7 JZ is Jordan block has AZ as an eigenvalue with algebraic multiplicity mi 11 1 11 1 1 1 Example 2 2 2 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinoi Matrix Computations 0215 Eigenvalue Problem 2 1 a1 2 a1 2 a2 a2 2Q1C 2 2C 1 gtC 2 0 2042 2042 gt 041 is free a 2 1 0 J a 0 IS the only eigenvector for 2 22Hl2l 2 51 and 52 are two eigenvectors of J 2 A1 1 The only eigenvector for the Jordan block I I is a scalar multiple of 1 A1 1 0 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0315 Eigenvalue Problem Definition matrix A is defective if it has an eigen value of algebraic multiplicity k with fewer than k linearly independent eigen vector eg 2 i is defective 2 2 is not Corollary A E 0quot is nondefective iff 3 a nonsingular X E 0quot st X1AX diag1 An Proof A is nondefective 81 independent vectors x1 zcn E Oquotgtlt1 and A1quot39 An E 0311 i E77 1 n LetX 31 cn 60quot andDdiag1 An A7 ThenAc1 cnc1 33 An lt2AXXDlt2X4AXD CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0415 Eigenvalue Problem Gershorin Circle Theorem Let A 6 CWquot each eigen value of A lies in one of the circles Di AEOAaiiS Z laij i1n 313 The theorem in textbook is more general than the above one 4 1 eg A 2 2 there are two circles The first one has center 4 0 with radius 1 the second one has center 20 with radius 2 detI AA 4220 gt3li N ate Real Matrix 22gt eigenvalues are real Real and Symmetric gt eigenvalues are real CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0515 Eigenvalue Problem Pf Let A be an eigen value of A and c is the corresponding eigenvector 331 33 337 Suppose cz 2 5cj forallj 5121 n n A 0 Z aijxj gt Z aijscij i1 j1J i le quot aijwj quot Since Ml g 1forg 2 A aZZ 3 Z T 3 Z aij 31357 1 31357 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0615 Eigenvalue Problem Real Schur Decomposition If A 6 RMquot then 3 orthogonal Q 6 RMquot st R11 39 quot le QTAQ f 6 RMquot where R is 1 x 1 or 2 x 2 real Rmm matrix Note When R is 2 x 2 its eigen values are complex conjugates CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0715 Eigenvalue Problem Corollary If AT 2 A 6 RMquot then QTAQ is also symmetric R11 39 39 le A1 So Rmm An Proof QTAQT QTATQ QTAQ From Real Schur Decomposition R11 RT R gt R and also can show that all eigenvalues Rmm of a symmetric real matrix are real R11 A1 Rmm An CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0815 Eigenvalue Problem Theorem If AH A then all eigenvalues of A are real Proof Suppose A c is an eigen value eigen vector for A and c2 1 szAx xHAsczAscszA cHAscH 33HAHsc NH 2X as CHAHsc A we haveX A A E R CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 0915 Eigenvalue Problem Symmetric Eigenvalue Decomposition IfA 6 RM and AT 2 A HQ 6 Rnxnst QTAQ A diag1 An qi S are eigen vectors Upper Hessenberg form GOOSE 00838383 08838383 RSEEREE RSEEREE QHAQ triangular can not be done in a finite number of steps Q HAQ 2 Upper Hessenberg form can be done in a finite number of steps CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01015 Eigenvalue Problem all 33 33 33 33 121 33 33 33 33 Example A 131 c c c a 141 6 c c c 151 33 33 33 33 121 33 Can find a Householder matrix P1 st P1 Q31 2 0 141 0 151 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01115 Eigenval ue Problem Numerical Methods LetH11 P1 mmxmx mmxmx mmxmx mmxmx ThenH1AH1 a a a a a 0 a a a a mmxmx 0392981 mmxmx 0392981 aaaaa mmxmx mmxmx mmxmx 0 0392981 H1 0xmxa 0 0392981 0xmxa p1 Oaaaa 0xmxa aaaaa mmxmx 0392981 0392981 Oaaaa CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01215 Eigenvalue Problem Numerical Methods Similarly 5656565656 5656565656 565656 5656565656 5656565656 565656 056565656 gt056565656 gt05656 056565656 00565656 0056 056565656 00565656 000 80 5656565656 5656565656 H3H2H1AH1TH2TH 0 x x x x 00565656 0005656 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01315 83838883 83838883 Eigen Value Problem When A is symmetric ie A 2 AT 12 a a a a a a a a a a a 0 a a a a a a a a a a a a 12 H1 at a a a a Hg 0 a a a a 0 a a a a a a a 0 a a a a 0 a a a a a a a 0 a a a a 0 a it since H1 AHIT is also symmetric fi rst row has three zeros Hencewehave 0 0 0 0 0 H3H2H1AH1TH2T H3T 0 a 0 0 0 0 0 0 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 01415 88880 88880 CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations Haesun Park hparkcc gatech edu Division of Computational Science and Engineering College of Computing Georgia Institute of Technology Atlanta GA 30332 USA Lecture 4 August 30 2007 LU Factorization 36 GE with Partial Pivoting 1 10 1 A 0 b10t7 1 1 121 110 10 1010 MA 1 0 10 10 1 10 10 1 1 1010 1 1 1 0 10101 fl 1010 1 1010 Partial pivoting avoid small pivot elements ie avoids large multipliers CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 019 LU Factorization ng Ax 9 Let A 5 where 9 is z th row of A 95 61 b g wherebzER bn 91T 91 51 Ax a an 9528 bn Want x st 9 bl for all 239 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 029 LU Factorization 10 egA 10 1 1 CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 039 LU Factorization Every time we reorder rows and choose the biggest pivot elements If lang max a a321c if then mutipier g 1 Let q k 3 q 3 n be St a i maX a2 af lk If then 14q3 klu AWMLJ bumcl MVMLI and PIaka PWML 2 where P I initially Pq k is the permutation which swaps row q and row k CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 049 LU Factorization With pivoting at each step of Gauss Elimination we will end up with PA LU GE with pp gives Mn1Pn1M2P2M1P1A U M3P3M2P2M1P1A U ltgt M3P3M2 P3133 P2M1P1A U Q M3 P3M2P3 P3P2M1P1A U CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 059 LU Factorization 1 1 eg P3 swaps rows 3 and 4 then P3M2P3 P3 1 P3 23 1 1 1 1 1 P M 3 a 1 a 1 2 a 1 a 1 80 we have M3M5P3P2M1P1A U ltgt M3M5P3P2M1 132133133132 P114 2 U Q MgM P3P2M1P2P3 P3P2P1A U 1 P3P2M1P2P3 a M1 which leads to 5 5 1 MgM MinPgPlA U Let P P3P2P1 then PA MgM M l U MflMg lMg lU LU CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 069 LU Factorization Each P1 is an interchange permutation involving rowz and a row with indexz 239 So each M is also a Gauss Transformation To solve Ax b Cgt FAQ 2 Pb Cgt LUac Pb it equals to 1 Solve Ly Pb for y 2 Solve U3 2 y for x In practice never store P as a matrix n locations is enough to store P 1 1 eg gt HixootoI a AxeAmos CS 8803 NMC Numerical Methods in Computational Science and Enqineerinq Matrix Computations 079 LU Factorization 37 GE with Complete Pivoting In complete pivoting use the max in magnitude in the submatrix as the pivot element change row order PAac Pb change column order AER 1x 5 GE with complete pivoting will give PAH LU where P H are permutation matrices Mn IPn l 39 39 M2P2M1P1AH1H2 39 39 Hn l U Ax b Q PAx Pb Q PAHH lx Pb Q LUH lx Pb 1 Solve Ly Pb for y 2 Solve U2 2 y forz 3 Solve TI lx 2 Q a 2 Hz CS 8803 NMC Numerical Methods in Computational Science and Engineering Matrix Computations 089

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

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

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

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