### Create a StudySoup account

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

Already have a StudySoup account? Login here

# INTRONUMANALYS&COMPUT MATH541

SDSU

GPA 3.61

### View Full Document

## 26

## 0

## Popular in Course

## Popular in Mathematics (M)

This 42 page Class Notes was uploaded by Camryn Rogahn on Tuesday October 20, 2015. The Class Notes belongs to MATH541 at San Diego State University taught by P.Blomgren in Fall. Since its upload, it has received 26 views. For similar materials see /class/225269/math541-san-diego-state-university in Mathematics (M) at San Diego State University.

## Reviews for INTRONUMANALYS&COMPUT

### 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 Blomgren blomgren peter gmail com Department of Mathematics and Statistics ynamicai Systems Group San Diego State University San Diego CA 9218277720 terminussdsuecu Fall 2009 Peter Blom Hi 27 o Trigonometric Polynomial Approximation 0 Introduction 0 Fourier Series a The Discrete Fourier Transform 0 Introduction 0 Discrete Orthogonality of the Basis Functions 9 Trigonometric Least Squares Solution 0 Expressions 0 Examples Peter Blom olynomial Am Tngonon ric P Introduction Trigon Trigonometric Polynomials A Very Brief History PX 2 an cosnx i an Slnlnxl n0 quot0 17505 Jean Le Rond d39Alembert used finite sums of sin and cos to study vibrations of a string 17 Use adopted by Leonhard Euler leading mathematician at the time 17 Daniel Bernoulli advocates use of infinite as above sums of sin and cos 18 Jean Baptiste Joseph Fourier used these infinite series to study heat flow Developed theory 53g Peter Blomgren Polynomial Appox Fourier Series First Observations For each positive integer n the set of functions 07 CD1 7 2n1 where 5 l 0 E kx coskx7 k 17n nkx sinkx7 k1n71 is an Orthogonal set on the interval 7713977139 with respect to the weight function WX 1 Polynomial Appox Trigonomelric Polynomial Approximation T Trigono 5lt Orthogonality Orthogonality follows from the fact that integrals over 77r77r of coskx and sinkx are zero except cos0 and products can be rewritten as sums cos01 7 02 7 cos01 l 02 sin 01 sin 02 2 COS 01 COS 02 cos01 7 02 7 cos01 l 02 39 0 7 0 39 0 0 sin 01 COS 02 Let Tn be the set of all linear combinations of the functions 39 lgt07 CD1 ltlgt2n1 this is the set of trigonometric polynomials of degree n W Peter Blomgren Polynomial Appox Trigonomelric Polynomial Approximali T m 5lt Intiun on TrigonomE Emmi i For f E C77r7 7139 we seek the continuous least squares approximation by functions in Tn of the form n71 5X an cosnx Z ak coskx bk sinkx7 k1 where thanks to orthogonality ak fx coskx clx7 bk fx sinkx dxi twig Sam 1 The limit Fourier Series First we note that fx and coskx are even functions on 7713977139 and sinkx are odd functions on 77r77r Hence 1 7r 2 7r an 7 ixidx7 de7ri 7r 7W 7r 0 olynomial Ame Trigonomelric Polynomial Approximation V A T Trigono slt Fourie Example Approximating fx ixi on First we note that fx and coskx are even functions on 7713977139 and sinkx are odd functions on 77r77r Hence 1 7r 2 7r an 7 ixidx7 de7ri 7r 7W 7r 0 ak 7 ixicoskx dx xcoskx dx 7r W W 0 7 2 sinkx 7r 2 7r 7 ng 0 7EA 1smkx dx 2 0 2 k m cosk7r 7 cos0 m 71 71 i Peter Blomgren Polynomial Approx Trigonomelric Polynomial Approximation V A T S Fourle Trigono Example Approximating fx ixi on First we note that fx and coskx are even functions on 7713977139 and sinkx are odd functions on 77r77r Hence 1 7r 2 7r an ixidx7 de7ri 7r 7W 7r 0 ak 7 ixicoskx dx xcoskx dx 7r W W 0 7 2 sinkx 7r 2 7r 7 ng 0 7EA 1smkx dx 2 0 2 k sz cosk7r 7 cos0 m 71 71 i 1 7r bk ixi smkx dx 0 7T 7 7r even X odd odd Peter Blomgren Polynomial Approx olynomial Ame olynomial Ame olynomial Ame olynomial Ame olynomial Ame 39U39U Lio r Transferquot Introduction alum V V l 1 m The Discrete Fourier Transform Introduction The discrete Fourier transform aka the finite Fourier transform is a transform on samples of a function It and its cousins are the most widely used mathematical transforms applications include 0 Signal Processing 0 Image Processing 0 Audio Processing 0 Data compression 0 A tool for partial differential equations 0 etc olynomial Ame n Intwn A 1m Lio Transfon Introduction The Discrete Fourier Transform Suppose we have 2m data points 97 where w and 6fxj j012m71 m The discrete least squares fit of a trigonometric polynomial nx E Tn minimizes olynomial Ame m Discrete Ordlogonalily or the Basis Functions Orthogonality of the Basis Functions We know that the basis functions 0X E Clgtkx coskx7 k 17n Clgtnkx sinkx7 k 17n71 are orthogonal with respect to integration over the interval The Big Question Are they orthogonal in the discrete case Is the following true 2m71 Z WWWX1 rm 7 10 Peter Blomgren Polynomial Appox Lion Transform Solution u r K Discrete Ordlogonalily or the Basis Functions Orthogonality of the Basis Functions A Lemma If the integer r is not a multiple of2m then Moreover ifr is not a multiple of m then 2m71 mil 2 cosrxj2 Z SinUle2 m39 j0 10 olynomial Ame A11 rele Fourier Tran Discrete Ordlogonalily or the Basis Functions Proof of Lemma Recalling longforgotten or quite possible never seen facts from Complex Analysis Euler s Formula 5 cos6 isin6i Peter Blom olynomial Am ynomial Approx rele Fourier Tran i z Sq union ion Discrete Ordiogonalily or the Basis Functions genome Proof of Lemma Recalling longforgotten or quite possible never seen facts from Complex Analysis Euler s Formula 5 cos6 isin6i Thus 2m1 2m1 2m1 2m1 V Z cosrxj i Z sinrxj Z cosnj isinrxj Z 5 10 10 10 10 olynomial Am Peter Blom ynomial Am39n39ux39 39 V A I re eth39mquot Tmquot quot Discrete Ordiogonalily or the Bais Functions gonom gt3 q Proof of Lemma Recalling longforgotten or quite possible never seen facts from Complex Analysis Euler s Formula 5 cos6 isin6i Thus 2m71 2m71 2m71 2m71 E cosrxj i E sinrxj E cosnj isinrxj E 5 10 j0 j0 j0 Since sing eir77rj7rm sewagequot7 we get 2m71 2m71 2m71 V V 7 4m irj7r m E cosrxjl E sInrxj is E e i 10 10 1 5351 olynomial Am Peter Blom A an Lion Transform s S 39 n ohm Discrete Ordlogonalily or the Basis Functions Proof of Lemma Since eIUWm is a geometric series with first term 1 and ratio ei Wm 7 1 we get 2m 1 rm 7 17 einrm2m 7 17 eZinr Z 8 7 lieiMrm 7 lienrm39 J olynomial Aprro 39U39U Lion te our Transform S L 5 39 n v i Illmu Discrete Ordiogonality of the Bais Functions Proof of Lemma Since eIUWm is a geometric series with first term 1 and ratio ei Wm 7 1 we get 2m 1 rm 7 17 einrm2m 7 17 eZinr Z 8 7 lieiMrm 7 lienrm39 J This is zero since 1792 17cos2r7r7isin2r7r 1717I70 0 This shows the first part of the lemma olynomial Aprro i i Discrete Ordlogonalily or the Basis Functions Proof of Lemma If r is not a multiple of m then 2m71 2m71 2m71 1 l COS2D39 1 2 7 J 7 7 cosng 7 2 7 E 7 m 10 10 J0 Similarly use cos20 i sin2 9 1 2m71 Z sinrg2 m 10 This proves the second part of the lemma We are now ready to show that the basis functions are orthogonal 5351 i i Discrete Ordlogonalily or the Basis Functions Recall Sin 01 Sin 02 cos01 7 02 cos01 i 02 COS 01 COS 02 cos01 7 02 g cos01 i 02 sin 01 c0502 Sin01 7 02 Sinwl 02 Thus for any pair k 7 I 2m71 Z WWWX1 10 is a zero sum of sin or cos and when k I the sum is m m The Trigonomelr Finally The Trigonometric Least Squares Solution 1 Our standard framework for deriving the least squares solution set the partial derivatives with respect to all parameters equal to zero 2 The orthogonality of the basis functions We find the coefficients in the summation n71 nx 7 g i an cosnx i Z a coskx l bk sinkx k1 i2m71 1 2m71 m Peter Blomgren Polynomial Appox LI Th rm Trigonomelric Least Squares Solution 789111 Examples Example Discrete Least Squares Approximation Let fx X372X2X1X74 forx E 77r77r Letxj77r i j7r57 j019 ie Peter Blomgren 139 X1 6 0 314159 5402710 1 251327 3117511 2 188495 1585835 3 125663 658954 4 O62831 188199 5 o 025 6 062831 620978 7 125663 O28175 8 188495 100339 9 251327 508277 olynomial Appox Exam pies The Trigonomelr Example Discrete Least Squares Approximation We get the following coefficients ao 720837 31 1513227 32 790819 33 79803 b1 886617 b2 778193 b3 44910 i i i Peter Blomgren Polynomial Appox Exam pies Tue Trigonomelr Example Discrete Least Squares Approximation We get the following coefficients ao 720837 31 1513227 32 790819 33 79803 b1 886617 b2 778193 b3 44910 i i i Peter Blomgren Polynomial Appox Exam pies The Trigonomelr Example Discrete Least Squares Approximation We get the following coefficients ao 720837 31 1513227 32 790819 33 79803 b1 886617 b2 778193 b3 44910 i i i Peter Blomgren Polynomial Appox Example Discrete Least Squares Approximation We get the following coefficients ao 720837 31 1513227 32 790819 33 79803 b1 886617 b2 778193 b3 44910 l Polynomial Appox Exam pies The Trigonomelr Example Discrete Least Squares Approximation We get the following coefficients ao 720837 31 1513227 32 790819 33 79803 b1 886617 b2 778193 b3 44910 i i i Peter Blomgren Polynomial Appox Example Discrete Least Squares Approximation We get the following coefficients ao 720837 31 1513227 32 790819 33 79803 b1 886617 b2 778193 b3 44910 i i i Polynomial Appox i ion W Th T rm Ex am Trigonomelric Least Squares Solution P Example Discrete Least Squares Approximation Notes 1 The approximation get better as n a 00 2 Since all the nx are 27r periodic we will always have a problem when f77r 7 f7r Fix Periodic extension On the following two slides we see the performance for a 27r periodic f 3 It seems like we need 9m2 operations to compute 5 and b m sums with m additions and multiplications There is however a fast 0mlog2m algorithm that finds these coefficients We will talk about this Fast Fourier Transform next time 5351 Peter Blomgren Polynomial Appox LI Th rm Trigonomelric Least Squares Solution shut Examples Exampe2 Discrete Least Squares Approximation Let fx 2X2 i cos3x i sin2x X E 7713977139 Letxj77r i j7r57 j019 ie X1 6 314159 187392 251327 138932 188495 85029 125663 17615 O62831 O4705 0 10000 062831 14316 125663 29370 188495 73273 251327 119911 00NOUW4gtLAJMHOK Peter Blomgren olynomial Appox 3 l 73gt 4H4 Examples T Trigonomel Exampe2 Discrete Least Squares Approximation We get the following coefficients ao 782685 31 22853 32 702064 33 08729 7107 7217 i i i We get the following coefficients ao 782685 31 22853 32 702064 33 08729 1 07 2 17 b3 w w w L i I 7 Examples Tue Trigonomelr Exampe2 Discrete Least Squares Approximation We get the following coefficients ao 782685 31 22853 32 702064 33 08729 1 07 2 17 b3 i i i i i i Peter Blomgren 3 l 73gt 4H4 Examples T Trigonomel Exampe2 Discrete Least Squares Approximation We get the following coefficients ao 782685 31 22853 32 702064 33 08729 7107 7217 i i i We get the following coefficients ao 782685 31 22853 32 702064 33 08729 1 07 2 17 b3 0 w w w We get the following coefficients 107 217 73 w w w ao 782685 31 22853 32 702064 33 08729

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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