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

### View Full Document

## 42

## 0

## Popular in Course

## Popular in Mathematics (M)

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

## Popular in Mathematics (M)

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

Numerical Analysis and Computing Lecture Notes 13 Approximation Theory Rational Function Approximation Peter Blomgren blomgren peter gmail com Department of Mathematics and Statistics ynamical Systems roup San Diego CA 9218277720 httpterminussdsuedu Fall 2009 m Rational Function Approximation 7 121 Outline a Approximation Theory 0 Pros and Cons of Polynomial Approximation 0 New Bagof Tricks Rational Approximation O Pad Approximation Example 1 a Pad Approximation 0 Example 2 0 Finding the Optimal Pad Approximation Rational Function Approximation 7 221 Polynomial Approximation Pros and Cons n i D of In nrr 1 We can approximate any continuous function on a closed inter val to within arbitrary tolerance Weierstrass approximation theorem 2 Easily evaluated at arbitrary values eg Homer39s method 3 Derivatives and integrals are easily determined p i D of In nrr 1 Polynomials tend to be oscillatory which causes errors This is sometimes but not always fixable Eg if we are free to select the node points we can minimize the interpolation error Chebyshev polynomials or optimize for integration Gaussian Quadrature m Rational Function Approximation 7 321 Moving Beyond Polynomials Rational Approximation We are going to use rational functions rx of the form n ZPiX39 i0 rn 1 2 qixi j1 and say that the degree of such a function is N n l m rx 7 PM W Since this is a richer class of functions than polynomials rational functions with qx E 1 are polynomials we expect that rational approximation of degree N gives results that are at least as good as polynomial approximation of degree N Rational Function Approximation 7 421 Pad Approximation Extension of Taylor expansion to rational functions selecting the p39s and qi39s so that rkxo fkxo Vk 01 N Now use the Taylor expansion fx N 20 aX 7 X0i for simplicity X0 0 23ami 203wi 7 203m fx 7 rx Next we choose pJp17 i i i 7p and q17q27iii7qm so that the numerator has no terms of degree g N Rational Function Approximation 7 521 Pad Approximation The Mechanics For simplicity we sometimes define the indexing out of bounds coefficients Pn1Pn2 PNO qm1qm2 qN07 so we can express the coefficients of Xk in 00 m n ZaiXiZinIizpixi07 k01N i0 i0 i0 k Zaiqkii Pk k 017N i0 Rational Function Approximation 7 521 Pad Approximation Abstract Example 1 of 2 Find the Pad approximation of fx of degree 5 where fx N 30 i 31X i a5x5 is the Taylor expansion of fx about the point X0 0 The corresponding equations are X0 i 30 7 p0 0 X1 a0 71 a1 7 p1 0 X2 30 31 32 7 p2 0 X3 30 a1q2 a2q1 a3 7 p3 0 X4 30q4 31q332q233q1 34 7 p4 0 X5 aoq5a1q4a2q3a3q2a4q1a5 P5 0 Note p0 30 This reduces the number of unknowns and equations by one m Rational Function Approximation 7 721 Pad Approximation Abstract Example 2 of 2 We get a linear system for p17 p2 pN and q17q27qN a0 71 P1 31 a1 30 72 P2 32 32 a1 a0 73 P3 33 33 32 a1 a0 74 P4 34 a4 33 32 a1 30 75 P5 35 fwewantn3m2 1 71 a1 31 30 0 1 72 32 32 31 O O 71 p1 33 iii 3 3 Siiiii iii Pad Approximation Concrete Example e 1 of 3 7 k The Taylor series expansion for e about X0 O is 220 Xk 1 71 1 7 hence 30731732733734735 7 liiliai i i m 1 O 71 ql 71 71 1 O 71 qg 12 12 71 O O 71 p1 7 716 7 716 12 0 O 0 p2 124 i 124 716 0 O Oi ipgi i 71120 i which gives Q1iQ2iP17P27P3 25 i2o 735 320 7160 3 3 2 1 3 r i 17 EX i EX 7 EX 330 2 1 39 1 EX i Exz 5351 Rational Function Approximation 7 921 Pad Approximation Concrete Example e 2 of 3 All the possible Pad approximations of degree 5 are Note r50 r50X r41X r32 X r23 X r14X r05 is the Taylor polynomial of degree 5 1 2 1 L 4 L 5 1 Xl 2X 6X3 24x 120x 4 3 1 3 1 4 17 x xzi x erx 1x 3 17 xx27x 1gx x2 17X20X2 S li 1gx x2wx3 17g S l li 1gxmxzgx3mgt 1x x2x3 x4170x5 Rational Function Approximation 7 1021 Pad Approximation Concrete Example e 3 of 3 The Absolute Error i i i i 0 1 i i i i R 50 H R 41 4 i R 32 0 01 r H R 23 E R 14 I R 05 0001 00001 g 7 1e05 Rational Function Approximation 7 1121 Pad Approximation Matlab Code The algorithm in the book looks frightening lfwe think in term of the matrix problem defined earlier it is easier to figure out what is going on 7 The Taylor Coefficients 30731732733734735 a 1 71 12 716 124 7112OJ N lengtha A zerosN 1N 1 quoto m is the degree of qx and n the degree of px m 3 n 1m quoto Set up the columns which multiply ql through qm for i1m AiN 1i a1N i end quoto Set up the columns that multiply p1 through pn e en A1nm1n quoto Set up the righthandside a2N c1m quota Select qg through qm 30 Cm1mn 7 Select p0 through pn Rational Function Approximation 7 1221 Optimal Pad Approximation l l One Point l Optimal Points l l Polynomials l Taylor l Chebyshev l l Pad l 7 l l Rational Functions From the example e we can see that Pad approximations suffer from the same problem as Taylor polynomials they are very accurate near one point but away from that point the approximation degrades Chebyshev placement of interpolating points for polynomials gave us an optimal uniform error bound over the interval Can we do something similar for rational approximations Rational Function Approximation 7 1321 Chebyshev Basis for the Pad Approximation We use the same idea instead of expanding in terms of the basis functions Xk we will use the Chebyshev polynomials Tkx as our basis e 7 220 Pk TkX 7 Elle qk TkX where N n m and qo 1 rnmx We also need to expand fx in a series of Chebyshev polynomials fx Z akaX k0 so that x 7 MAX 2200 3k TkX Elle qkaX ZLo PkaX Elle qk TAX 5350 Rational Function Approximation 7 1421 The Resulting Equations Again the coefficients p07 p17 pn and q17q27qm are chosen so that the numerator has zero coefficients for Tkx k01N e ZakaXquTkXZPkTiAX Z VkaX k0 k0 k0 kN1 We will need the following relationship TiXTjX Twle Tiiajilxll Also we must compute maybe numerically 1 1 fx 2 1 fx 7kx 7 gt 304 1de and ak 1 W dx7 k 1 Rational Function Approximation 7 1521 Example Revisiting e X with Chebyshev Pad Approximation 15 The 8Ll order Chebyshev expansion ALL PRAISEMAPLE for e is P Tx 1266065878 T0x 7 1130318208 T1x 02714953396 T2x 7004433684985 T3x 0005474240442 74x 700005429263119 T5x 000004497732296 T5x 70000003198436462 T7x 00000001992124807 Tgx and using the same strategy building a matrix and right hand side utilizing the coefficients in this expansion we can solve for the Chebyshev Pad polynomials of degree n l 2m 8 Next slide shows the matrix set up for the r3Cp2X approximation Note Due to the folding TX7X TijX f Tli7jl we need n 2m Chebyshev expansion coefficients Burden Faires do not mention this but it is obvious from algo rithm 82 Example2 p 519 is broken it needs m Rational Function Approximation 7 1521 Example Revisiting e x with Chebyshev Pad Approximation 25 T000 3 1 i 31511 32612 7 2p0 230 T100 3 1 i 230 32q1 21 asq2 7 2p1 231 T200 3 i 31 33q1 220 a4q2 7 2p2 232 T300 3 i 32 34q1 21 asq2 7 2p3 233 T400 3 i 33 asq1 22 25q2 7 O 234 T500 3 i 34 aaq1 23 ayq2 7 O 235 J 5351 Rational Function Approximation 7 1721 Example Revisiting e x with Chebyshev Pad Approximation 35 R ltxgt 7 1 155054 Tom 7 0 8549674 T1gtlt 0 1561297 T2x 7 0 01713502 T3x 0 001066492 mx T0x 0 1964246628 T1gtlt R230 7 1 050531166 Tgx 7 0 6016362122 T1x 0 07417897149 T2x 7 0 004109558353 T3x Tom 0 3870509565 T1x 0 02365167312 T2x R3310 7 0 9541897238 Tom 7 0 3737556255 T1gtlt 0 02331049609 T2x Tom 0 5682932066 T1x 0 06911746318 T2x 0 003726440404 T3x Rf tx 7 0 8671327116 Tgx 7 01731320271T1x T0gtlt 0 73743710 T1gtlt 0 13373746 T2x 0 014470654 T3gtlt 0 00086486509 T4x Rational Function Approximation 7 1821 Example Revisiting e x with Chebyshev Pad Approximation 45 Rational Function Approximation 7 1921 Example Revisiting e x with Chebyshev Pad Approximation 55 Rational Function Approximation 7 2021 The Bad News It39s Not Optimal The Chebyshev basis does not give an optimal in the min max sense rational approximation However the result can be used as a starting point for the second Remez algorithm It is an iterative scheme which converges to the best approximation A discussion of how and why and why not you may want to use the second Remez39 algorithm can be found in Numerical Recipes in C The Art of Scientific Computing Section 513 You can read it for free on the web just Google for itl M The old 2nd Edition is Free the new 3rd edition is for sale Rational Function Approximation 7 2121

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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