### Create a StudySoup account

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

Already have a StudySoup account? Login here

# NUMERICALMATRIXANALYSIS MATH543

SDSU

GPA 3.64

### View Full Document

## 23

## 0

## Popular in Course

## Popular in Mathematics (M)

This 31 page Class Notes was uploaded by Miss Gladys Lubowitz on Tuesday October 20, 2015. The Class Notes belongs to MATH543 at San Diego State University taught by P.Blomgren in Fall. Since its upload, it has received 23 views. For similar materials see /class/225266/math543-san-diego-state-university in Mathematics (M) at San Diego State University.

## Popular in Mathematics (M)

## Reviews for NUMERICALMATRIXANALYSIS

### 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/20/15

Peter Blom N Peter Blomgren blomgren peter gmail com Department of Mathematics a Dyn umnms m 39 39qu mula s 39 r Value Dmmp ltVD Forquot Def Outline 9 Introduction Matrix Norms Recap 9 Inequalities 0 General Matrix Norms a The Singular Value Decomposition 0 Many Names One Powerful Tool39 0 Examples for 2 X 2 Matrices 0 More Details and Examples Revisited a The SVD Formal Definition 0 Spheres and Hyperiellipses 0 Homew Peter Blom Matrix Norm Last Time Orthogonal Vectors Matrices and Norms The Adjoint Hermitian Conjugate of a Matrix A The Inner Product of Two Vectors lt52 9 SEW Orthogonal lt52 9 0 and Orthonormal 1 Vectors Orthogonal and Orthonormal Sets Linear Independence Basis for Cm Unitary Matrices QQ I Vector Norms llp p norms weighted p norms lnduced Matrix Norms Peter Blomgren Matrix Norms die SVD Introduction Matrix Norms Tl Singular Value D n The SVEI Fo Inequalities Holder and Cauchy Bunyakovsky Schwarz Last time we noted that the 1 norm and oo norm of a matrix simplify to the maximal column and row sum respectively ie for AECan llAll1 gagnllill llAlloo 12W ll5ill1 iISm For other p norms 1g p g 00 the matrix norms do not reduce to simple expressions like the ones above 5351 Introduction Matrix Norms E r The Singular Value D io Inequalities Tll SVEI Forn D t l v Inequalities Helder and Cauchy Bunyakovsky Schwarz However we can usually find useful bounds on vector and matrix norms using the H lder inequality 1 1 F9 2 y 771 l l H M llq p q In the special case p q 2 the inequality is known as the Cauchy Schwarz or Cauchy Bunyakovsky Schwarz inequality lin S llillz llyllz Ma 39x Norm die SVD Introdi clio Th Singular Vaine The SVEI For Example 2 norm of a Rank 1 Matrix A i l Rank 1 matrices formed by an outer product 10 show up in many numerical schemes U1 U1 Ll17 2 HQ W u2v uv v1 v2 vn v7 um um umv Now for any i E C we get HAin HWin H iiz Vii S H iiz iiVHz Hiiiz Hence Ali 2 HAH2 sup W 3 M2 M2 iectm 2 Matrix Norms die SVD Peter Blomgren Example 2 norm of a Rank 1 Matrix A 19 Since 9 E C the inequality A llAllz sup ll llz quoteCni6 llxll2 S ll llzlli llz is actually an equality Let i V llAVllz ll VWllz ll llz l77l ll llz Milli Peter Blomgrel Matrix Norms die SVD Intro Th Singular Va The ltVD Bounds on the Norms of Matrix Products llABll Let A E C 39 B E Cm and i E C and let ldenote compatible p norms then llABill S llAll llBill S llAll llBll llil Therefore we have llABll S llAll llBll7 where in general llABll 7 m Peter Blomgrel Matrix Norms die SVD lnLrodi clio Th Singular Value Tl F I9 SVEI or rix Norms General Non Induced Matrix Norms Matrix norms induced by vector norms are quite common but as long as the following norm conditions are satisfied 1 2 07 and 0 only if A O 2 HA Bil S llAll NW 3 llaAll lal MN for A 6 CW is a valid matrix norm The most commonly used non induced matrix norm is the Frobenius norm sometimes referred to as the Hilbert Schmidt norm 12 rn n llAllF ZZlaulz i1j1 Peter Blomgren Matrix Norms die SVD Introduction Matrix Norms mlllar Vain u m w ltVD Fo39 General Matrix Norms The Frobenius Norm We can view the Frobenius Norm in terms of column or row sums 12 12 n rn 2 2 5ng ZHWE 11 i1 12 In HAHF or in terms of the trace sum of diagonal entries HAHF traceAA traceAA Introduction Matrix Norms The Singular Value D The SVEI F0 391 General Matrix Norms Invariance under Unitary Multiplication Both the 2 norm and the Frobenius norm are invariant under multiplication by unitary matrices ie For any A 6 cm and unitary Q E mem we have llQAllz llAllz llQAllF llAllF an indication of the importance and usefulness of unitary matrices Introduction Matrix Norms Th Singular Value Decomp n The svn Forle Def mun aim2 Ml l lgf Uu m f 39 Both the 2 norm and the Frobenius norm are invariant under multiplication by unitary matrices ie Tl xaom l For any A 6 cm and unitary Q E mem we have llQAllz llAll27 llQAllF llAllF an indication of the importance and usefulness of unitary matrices animation to basic llirn This ends mu Intro Th Singular Va The ltVEI Matrix Norms Linear Algebra References Linear Algebra and Its Applications Gilbert Strang Brooks Cole 4th edition 2005 ISBN 0030105676 Introduction to Linear Algebra Gilbert Strang Wellesley Cambridge Press 4th edition 2009 lSBN 0980232716 Linear Algebra Done Right Sheldon Axler Springer Verlag 2nd edition July 18 1997 lSBN 0387982582 Peter Blomgrel Matrix Norms die SVD Many Names One Powerful Tool odu M ar Value Decompo The svn Forle Defi ion The Singular Value Decomposition The SVD mathematics is known by many names 0 the Proper Orthogonal Decomposition POD 0 the Karhunen Loeve KL Decomposition signal analysis 0 Principal Component Analysis PCA statistics 0 Empirical Orthogonal Functions etc The SVD is absolutely a high point of linear algebraquot Prof Gilbert Strang MIT Peter Blomgren Matrix Norms die SVD Ininducfun Mam Nun The Singular Value Dunn an me 5er r nle Mm on scholar google com new specialized service for searching schole arly literature Including peererevlewed papers theses books preprmts abstracts and techHe cal reports from all broad areas of research HUD quotmoment Hi ya Smgulzv Value Decumvusmun szhunen L znumtzl CavvelztmnAn ny c 5 Emma Ovthugunzl FunmuniFunctmm vaa Onmwnzl Demmvusmun able The many names faces and close relamves of the SmgularValue Der composmon The Singular Value Decomposition In our first look at the SVD we will not consider how to compute the SVD but will focus on the meaning of the SVD especially its geometric interpretation The motivating geometric fact The image of the unit sphere under any m X n matrix A is a hyper ellipse The hyper ellipse in Rm is the surface we get when stretching the unit sphere by some factors 01 02 am in some orthogonal directions 11 g m We take 1 to be unit vectors ie ll illg 1 thus the vectors ai i are the principal semi axes of the hyper ellipse m Peter Blomgren Matrix Norms die SVD One Powerful Tool uc Ma The Sin lar Value Decompo zl D The SVEI Form The Singular Value Decomposition For A E Rm if rankA r then exactly r of the lengths a will be non zero In particular if m 2 n at most n of them will be non zero Before we take this discussion further let39s look at some examples of the SVD of some 2 x 2 matrices Keep in mind that computing the SVD of a matrix A answers the question what are the principal semi axes of the hyper ellipse generated when A operates on the unit spherequot In some sense this constitutes to most complete information you can extract from a matrix Inn oduc Ma Norms m The Simmlar Value Decompos on Examples for T SVDFol39mgtlDef on gt V Examplel SVD of a 2 2 Matrix 20 102010 SVD01010101 f H1 2 diag71fg 01 02 T For HOW et s sweep the matmx Vquot under the carpet and note that the SVD has dehtmed the dwectwohs of stretchmg 11412 and the amount ofstretchmg 0102 21 Peter Blom Matrix Norm In In Ma The Singular Value Decomp The svn Forle Def Example2 SVD of a 2 2 Matrix SVD 16 70 65 7 70 9553 0 2955 18011 0 70 9553 70 2955 70 65 70 3 0 2955 0 9553 0 0 5011 0 2955 70 9553 Here the principal semi axes of the ellipse are 709553 02955 0391u1 18011 739ng 05011 09553 02955 l m In In Ma The Singular Value Decomp The svn Forle Def Example3 SVD of a 2 2 Matrix SVD 1 4 70 62 7 70 2501 0 9682 2 0556 0 70 6885 0 7253 71 1 717 0 9682 0 2501 0 14896 70 7253 70 6885 Here the principal semi axes of the ellipse are 70 250 09682 09682 0161 20556 l l 02501 5350 1 l mag 14896 l uc Ma The Sin lar Value Decompo zl D The SVEI Form More Dela and Examples Revisited The Singular Value Decomposition More Let S 1 be the unit sphere in R ie Sn l i E R 1 Let A E Rm m 2 n be of full rank ie rankA n and let ASrquot1 denote the image of the unit sphere our hyper ellipse The n singular values of A are the lengths of the n principal semi axes of AS 1 some lengths may be zero written as 01 02 70 By convention they are ordered in descending order so that 01202220ngt0 The n left singular vectors of A are the unit vectors 11 g n oriented in the directions of the principal semi axes of ASn l 5351 7 Zn3H du VD Forle Def The Singular Value Decomposition Note that the vector 01 is the ith largest principal semi axis of ASn l The n right singular vectors of A are the unit vectors 91 92 an 6 S 1 that are pre images of the principal semi axes of ASn l ie AV O39J39UJ39 With that knowledge we can re visit the three examples More Details and Examples Revisited Revisited Our 3 Examples In Forle Def More Delai and Examples Revisited The Reduced SVD What we have described so far is known as the reduced or thin SVD if we collect the relations between the right and left singular vectors AvJz7juj7 117n in full blown matrix notation we get mm M ar Value Decompo A The svu For vial D 39 More Details and Examples Revisited The Reduced SVD In looking at the reduced SVD in this form AV U we note that A 6 CW ifArankA n V 6 CM unitary U 6 CW unitary and X 6 RM diagonal real If we multiply by V from the right and use the fact that VV I we get the reduced SVD in its standard form A UEW AIAJE 55 I Matrix Norms die SVD Peter Blomgren In most applications the SVD is used as we have described Le the reduced SVD is used However the SVD can be extended as follows The columns of U are n orthonormal vectors in Cm m 2 n If m lt n then they do not form a basis for Cm By adding an additional n 7 m orthonormal columns to we get a new unitary matrix U 6 CM Further we form the matrix X by adding n 7 m rows of zeros at the bottom of X Peter Blomgren Matrix Norms die SVD A E A U A Ufw We can now drop the simplifying assumption that rankA n If A is rank deficient ie rankA r lt n the full SVD is still appropriate however we only get r left singular vectors 1 from the geometry of the hyper ellipse In order to construct U we add n 7 r additional arbitrary orthonormal columns In addition V will need n 7 r additional arbitrary orthonormal columns The matrix X will have r positive diagonal entries With the remaining n 7 r equal to zero m Peter Blomgren Matrix Norms die SVD lnu oduciion Ma 39 Th Singular Vaim The SVD Forma De nition smug Mama Wam i Let m and n be arbitrary integers Given A 6 CW a i T m of A is a factorization A UX V where U E mem is unitary V 6 CM is unitary X E Rm is diagonal The diagonal entries of X are non negative and ordered in decreasing order ie 01 2 02 2 0p 2 0 where p minm7 n Note We do not require m 2 n rankA r minm7 n Peter Blomgren si x g D pa The svn Formal Defiv Spheres and Hyper ellipses ClearlyQ ifA has a SVD ie A UXV then A must map the unit sphere into a hyperellipse 0 V preserves the sphere since multiplication by a unitary matrix preserves the 2norm Multiplication by V is a rotation possibly a reflection o Multiplication by X stretches the sphere into a hyperellipse aligned with the basis 0 Multiplication by the unitary U preserves a 2norms and angles between vectors hence the shape of the hyperellipse is preserved albeit rotated and reflected If we can show that every matrix A has a SVD then it follows that the image of the unit sphere under any linear map is a hyperellipse something we stated body on slide 16 I A It tquotQ ceary re you as ye m Spheres and Hyperrellipses Next Time More on the SVD We save the proof that indeed every matrix A has a SVD for next lecture We also discuss the connection between the SVD and the more familiar eigenvalue decomposition Further we make connections between the SVD and the rank range and null space of A etc It takes some time to digest the SVD We will return to the computation of the SVD later when we have developed a toolbox of numerical algorithms Peter Blomgren Matrix Norms die SVD du ar Va e The SVD For Homework 2 Due at 1234pm Friday February 12 2010 Figure out how to get your favorite piece of mathematical software eg Matlab to compute the SVD Use your software to solve tb 4 1 and tb 43 pp30 31 Hint To get started in matlab try help svd and help plot Peter Blomgren Matrix Norms me svn 7 an3H

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