Baixe o app para aproveitar ainda mais
Prévia do material em texto
Function Approximation Pafnuty Chebyshev, 1821-1894 Numerical Methods © Wen-Chieh Lin 2 Administration Assignment 3 is out; due on April 23 midnight Chapter 3 Excises 30 (a)(b)(c)(d), 33, 48, 49, 69 (20% each) Extra credit (10%): App 8 Mid-term exam: Apr 30 Numerical Methods © Wen-Chieh Lin 3 Function Approximation How does a computer approximate cos(x), exp(x), and other non-polynomial functions? Efficient and accurate approximation is desired Chebyshev polynomials Orthogonal polynomials Converge faster than a Taylor series Rational functions Ratio of two polynomials Fourier series Series of sine and cosine terms Can approximate periodic or discontinuous functions Numerical Methods © Wen-Chieh Lin 4 Truncation Error in Taylor Series Recall that Taylor series If approximating a function using first n terms Error grows rapidly as x-value departs from x = a! 2)( !2 )(" ))((')()( ax af axafafxf 1 )1()( )( )!1( )( )( ! )( )( n n n n ax n f ax n af af 1 )1( )( )!1( )( n n ax n f Error Numerical Methods © Wen-Chieh Lin 5 Chebyshev Polynomials Recursive definition xxTxTxTxxTxT nnn )(,1)(),()(2)( 1011 12)( 22 xxT xxxT 34)( 33 188)( 244 xxxT Numerical Methods © Wen-Chieh Lin 6 Chebyshev Polynomials (cont.) Equivalent form Proof ))acos(cos()( xnxTn )cos(x xxTxTxTxxTxT nnn )(,1)(),()(2)( 1011 coscos2)1cos()1cos( nnn )(2)()( 11 xxTxTxT nnn Numerical Methods © Wen-Chieh Lin 7 Chebyshev Series 12)( 22 xxT xxxT 34)( 33 188)( 244 xxxT 1)(0 xT xxT )(1 )( 2 1 02 2 TTx )3( 4 1 13 3 TTx )34( 8 1 024 4 TTTx 1Tx 01 T Numerical Methods © Wen-Chieh Lin 8 Chebyshev Series is More Economical On the interval [-1, 1], approximating a function with a series of Chebyshev polynomials is better than with a Tayor series as it has a smaller maximum error On an interval [a, b], we have to transform the function to translate the x-value into [-1, 1] 12~ ab ax x)~()( xfxf Numerical Methods © Wen-Chieh Lin 9 )34( 8 1 024 4 TTTx Example: Economizing a Power Series Maclaurin series is Taylor series expansion of a function about 0 Maclaurin series of ex Approximated by a Chebyshev series 7201202462 1 65432 xxxxx xex )34( 8 1 24 1 )3( 4 1 6 1 )( 2 1 2 1 024130210 TTTTTTTTTe x )( 2 1 02 2 TTx )3( 4 1 13 3 TTx )1510( 23040 1 )510( 16 1 120 1 2031 TTTT Numerical Methods © Wen-Chieh Lin 10 Example (cont.) Maclaurin series of ex truncated after 3rd degree Chebyshev series of ex truncated after 3rd degree 62 1 32 xx x 3210 0443.02715.01302.12661.1 TTTTex 32 1772.05430.09973.09946.0 xxx 7201202462 1 65432 xxxxx xex Numerical Methods © Wen-Chieh Lin 11 Example (cont.) Error of Maclaurin series grows rapidly when x-value departs from zero Error of Maclaurin series Error of Chebyshev series x Numerical Methods © Wen-Chieh Lin 12 Orthogonaliy of Chebyshev Polynomials Two polynomials p(x), q(x) are orthogonal on an interval [a, b] if their inner product Set of polynomials is orthogonal if each polynomial is orthogonal to each other Chebyshev Polynomials are orthogonal on interval [-1, 1] with 0)(,0)()()(, xwdxxwxqxpqp ba 211)( xxw Numerical Methods © Wen-Chieh Lin 13 Verify Orthogonaliy of Chebyshev Polynomials Example: p(x) = T0(x), q(x) = T3(x) Matlab code int('(4*x^3-x)/sqrt(1-x^2)', -1 ,1) 0 1 1 )34(1)(),( 2 1 1 3 dxxxxxqxp Numerical Methods © Wen-Chieh Lin 14 Least Squares Approximation using Orthogonal Polynomials System of normal equations for a high-degree polynomial fit is ill-conditioned Fitting data with orthogonal polynomials such as Chebyshev polynomials can reduce the condition number to about 5 )()()()( 1100 xTaxTaxTaxf nn mnmnmm n n y y y a a a xTxTxT xTxTxT xTxTxT 2 1 1 0 10 22120 11110 )()()( )()()( )()()( Numerical Methods © Wen-Chieh Lin 15 Rational Function Approximation Approximating a function with a Chebyshev series has smaller maximum error than with a Taylor series We can further improve the maximum error using rational function approximation Padé approximation: n≥m m m n n N xbxbxb xaxaxaa xRxf 2 21 2 210 1 )()( 1 mnN Numerical Methods © Wen-Chieh Lin 16 Padé Approximation Represent a function in a Taylor series expanded at x = 0 Coefficients are determined by setting and equating coefficients )()( xRxf N m m n nN N xbxbxb xaxaxaa xcxcxcc 2 21 2 2102 210 1 )( ! )0()( i f c i i 00 ca 1011 ccba nnmnmn ccbcba 11 011 mNmNN cbcbc 0111 mnmnn cbcbc Numerical Methods © Wen-Chieh Lin 17 Example: Padé Approximation Find arctan(x)≈R10(x) Maclaurin series of arctan(x) through x10 is f(x) = R10(x) 9753 9 1 7 1 5 1 3 1 )arctan( xxxxxx 5 5 4 4 3 3 2 21 5 5 4 4 3 3 2 2109753 19 1 7 1 5 1 3 1 xbxbxbxbxb xaxaxaxaxaa xxxxx Numerical Methods © Wen-Chieh Lin 18 Example: Padé Approximation (cont.) Equating coefficients x0 through x5 5 5 4 4 3 3 2 21 5 5 4 4 3 3 2 2109753 19 1 7 1 5 1 3 1 xbxbxbxbxb xaxaxaxaxaa xxxxx 00 a 11a 12 ba 23 1 3 ba 313 1 4 bba 423 1 5 1 5 bba 0331151 bb 043125171 bb 0531351171 bbb 045127191 bb x6 through x10 0551371191 bbb Numerical Methods © Wen-Chieh Lin 19 Padé Approximation vs. Maclaurin Series Padé Approximation Maclaurin series 9753 9 1 7 1 5 1 3 1 )arctan( xxxxxx 42 53 21 5 9 10 1 945 64 9 7 )arctan( xx xxx x Numerical Methods © Wen-Chieh Lin 20 Padé Approximation vs. Maclaurin Series 9753 9 1 7 1 5 1 3 1 )arctan( xxxxxx 42 53 21 5 9 10 1 945 64 9 7 )arctan( xx xxx x Maclaurin series Pade approximation True value Pade approximation Numerical Methods © Wen-Chieh Lin 21 Chebyshev-Padé Rational Function We can get a rational function approximation from a Chebyshev series expansion of a function as well Example: We first form Then expand the numerator and set the coefficients of each degree of the T’s to zero 3210 0443.02715.01302.12661.1 TTTTex 11 22110 3210 1 0443.02715.01302.12661.1 Tb TaTaa TTTT Numerical Methods © Wen-Chieh Lin 22 ])cos()[cos( 2 1 )cos()cos( mnmnmn 11 22110 3210 1 0443.02715.01302.12661.1 Tb TaTaa TTTT Recall that Apply the last equation to The numerator becomes )cos()( nxTn )]()([ 2 1 )()( xTxTxTxT mnmnmn )( 2 2661.1 0443.02715.01302.12661.1 11 1 3210 TT b TTTT )( 2 0443.0 )( 2 2715.0 )( 2 1302.1 24 1 13 1 02 1 TT b TT b TT b 22110 TaTaa Numerical Methods © Wen-Chieh Lin 23 Equating the Coefficients of Each Degree of T’s in Numerator )( 2 2661.1 0443.02715.01302.12661.1 11 1 3210 TT b TTTT )( 2 0443.0 )( 2 2715.0 )( 2 1302.1 24 1 13 1 02 1 TT b TT b TT b 22110 TaTaa 2 1302.1 2661.1 10 b a 2 2715.0 2661.11302.1 111 b ba 2 0443.0 2 1302.1 2715.0 112 bb a 2 2715.0 0443.00 1 b x xx T TT ex 3263.01 1598.06727.00018.1 3263.01 0799.06727.00817.1 2 1 21 Numerical Methods © Wen-Chieh Lin 24 Chebyshev vs. Chebyshev-Padé Rational Numerical Methods © Wen-Chieh Lin 25 Error Plot Pade-Chebyshev rational function Chebyshev serires Numerical Methods © Wen-Chieh Lin 26 Fourier Series Representing a function as a trigonometric series f(x) need be integrable so that the coefficients can be computed 1 0 )sin()cos( 2 )( n nn nxBnxA A xf Numerical Methods © Wen-Chieh Lin 27 Properties of Orthogonality 0)sin( dxnx 0,2 0,0 )cos( n n dxnx 0)cos()sin( dxmxnx mn mn dxmxnx , ,0 )sin()sin( mn mn dxmxnx , ,0 )cos()cos( Numerical Methods © Wen-Chieh Lin 28 ....2,1,)()cos( 1 mdxxfmxAm 1 0 )cos()cos()cos( 2 )()cos( n n dxmxnxAdxmx A dxxfmx Computing Fourier Coefficients using Orthogonality 1 0 )sin()cos( 2 )( n nn nxBnxA A xf 11 0 )sin()cos( 2 )( n n n n dxnxBdxnxAdx A dxxf 000 A 1 )cos()sin( n n dxmxnxB 00 mA Numerical Methods © Wen-Chieh Lin 29 Computing Fourier Coefficients using Orthogonality (cont.) 1 0 )sin()cos( 2 )( n nn nxBnxA A xf 1 0 )sin()cos()sin( 2 )()sin( n n dxmxnxAdxmx A dxxfmx 1 )sin()sin( n n dxmxnxB 00 mB ....2,1,)sin()( 1 mdxmxxfBm Numerical Methods © Wen-Chieh Lin 30 Fourier Series for Periods other than 2π Let the period of f(x) be P Consider that f(x) is periodic in [-P/2, P/2] Change of variable 2 2 ....2,1,) 2 cos()( 2 P Pm mdx P xm xf P A 2P x y 2 2 ....2,1,) 2 sin()( 2 P Pm mdx P xm xf P B ....2,1,)()cos( 1 mdxxfmxAm ....2,1,)sin()( 1 mdxmxxfBm Numerical Methods © Wen-Chieh Lin 31 Fourier Series for Periods other than 2π 1 0 ) 2 sin() 2 cos( 2 )( n nn P xn B P xn A A xf 2 2 ....2,1,) 2 cos()( 2 P Pn ndx P xn xf P A 2 2 ....2,1,) 2 sin()( 2 P Pn ndx P xn xf P B Numerical Methods © Wen-Chieh Lin 32 Example: f(x) = x, x in [-π,π] 0 )sin()sin(1 )cos( 1 dx m mx m mx xxdxmx ....2,1,)()cos( 1 mdxxfmxAm ....2,1,)sin()( 1 mdxmxxfBm dxm mx m mx xxdxmx )cos()cos(1 )sin( 1 mm m m 1)1(2)cos(2 1 1 )sin( )1(2 m m mx m x Numerical Methods © Wen-Chieh Lin 33 Fourier Series for Nonperiodic Functions Chop the interval of interest [0, L] L Numerical Methods © Wen-Chieh Lin 34 Fourier Series for Nonperiodic Functions Solution 1: make an even function by reflecting the segment about y-axis, f(x)=f(-x) L Numerical Methods © Wen-Chieh Lin 35 Fourier Series for Nonperiodic Functions Solution 2: make an odd function by reflecting the segment about the origin, f(x) = -f(x) L Numerical Methods © Wen-Chieh Lin 36 Properties of Even and Odd Functions Product of two even functions is an even function Product of two odd functions is an even function Product of an even function and an odd function is an odd function LL L dxxfdxxfxf 0 )(2)(evenis)(if L L dxxfxf 0)(oddis)(if Numerical Methods © Wen-Chieh Lin 37 Fourier Series for Even Functions 2 2 ....2,1,) 2 cos()( 2 P Pm mdx P xm xf P A L L dx L xm xf L ) 2 2 cos()( 2 2 L dxL xm xf L 0 )cos()(2 1 2 2 ....2,1,) 2 sin()( 2 P Pm mdx P xm xf P B 0 odd function even function Numerical Methods © Wen-Chieh Lin 38 Fourier Series for Odd Functions 2 2 ....2,1,) 2 cos()( 2 P Pm mdx P xm xf P A L L dx L xm xf L ) 2 2 sin()( 2 2 L dxL xm xf L 0 )sin()(2 1 2 2 ....2,1,) 2 sin()( 2 P Pm mdx P xm xf P B 0 odd function even function Numerical Methods © Wen-Chieh Lin 39 Example: Fourier Series of Nonperiodic Functions—even extension 21,1 10,0 )( x x xf Lm dxL xm xf L A 0 )cos()( 2 odd, )1( 2 even,0 2)1( m m m m 20 )2cos()(2 2 dx xm xf 1)( 2 2 2 00 dxxfA 1 2-1-2 x y 1 1 0 ) 2 sin() 2 cos( 2 )( n nn P xn B P xn A A xf Numerical Methods © Wen-Chieh Lin 40 Example: Fourier Series of Nonperiodic Functions—odd extension 21,1 10,0 )( x x xf Lm dxL xm xf L B 0 )sin()( 2 ) 2 cos()cos( 2 m m m 2 0 ) 2 sin()( 2 2 dx xm xf 1 2-1-2 x y 1 -1 ) 2 sin( ) 2 cos()cos(2 1 xn n n n n 1 0 ) 2 sin() 2 cos( 2 )( n nn P xn B P xn A A xf
Compartilhar