Buscar

chap4_1

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 40 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 40 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 40 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

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
11a
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


Outros materiais