Scribd
Upload
3 views6 pages

4 NumericalMethods EvaluationFunction

The document discusses various numerical methods for evaluating functions, including polynomials, rational functions, continued fractions, and Chebyshev approximations. It outlines recursive methods for polynomial evaluation and provides algorithms for rational functions and continued fractions, emphasizing their applications in scientific computations. Additionally, it explains the Chebyshev polynomial approximation and the process of converting coefficients into polynomial forms for better evaluations.

Uploaded by

khoanart05
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views6 pages

4 NumericalMethods EvaluationFunction

The document discusses various numerical methods for evaluating functions, including polynomials, rational functions, continued fractions, and Chebyshev approximations. It outlines recursive methods for polynomial evaluation and provides algorithms for rational functions and continued fractions, emphasizing their applications in scientific computations. Additionally, it explains the Chebyshev polynomial approximation and the process of converting coefficients into polynomial forms for better evaluations.

Uploaded by

khoanart05
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Evaluation of Function

Numerical Methods for IT


Polynomials
Given a polynomial = + + + ⋯+
and ∈ ℝ.
Evaluation ( ) ?

We have
= + + + ⋯+ +
= + + + ⋯+ +
= + ∗ ( ), where
= + + ⋯+ + , = , = 0, … , − 2

Let = [0 … ] is a 1-dimensional array that represents the computer representation of the


polynomial ( ). Given a value . To evaluate , we can represent the recursive form as
follows:
0, =0
, =
[0] + ∗ ( , ), ≥ 1
.
Rational functions
To evaluate a rational function like:
#$ % () (* % ⋯ ($ % $
" =& %
= +) +* % ⋯ +' % '
.
'

Given ,, to evaluate "(,), we can use the polynomial evaluation routine to:
(1) -. ← (0, ,)
(2) 12. ← 3( , ,)
(3) Return -./12.
Evaluation of Continued Fractions
Continued fractions are often powerful ways of evaluating functions that occur in scientific
applications.
A continued fraction looks like:
6* 6 6 6
5 = + 89 ≡ + * 9 < ….
7* 8 7* 79 7<
:9 ; <
:< ;⋯
% %9 %9 %9
For example, the continued fraction representation of tangent function is: tan = A B C
…
Let 5 denote the result of 5( ) with coefficients through and . Then
D
5 = FE, Steed’s method.
E
where G , H are given by the following recurrence: . Set 5 = . M5 = 0, NOP 5 = Q.
G ≡ 1 ;H ≡ 0 . Set R = 5 , S = 0.
G ≡ ;H ≡ 1 . For K = 1,2, …:
GJ = J GJ + J GJ ; HJ = J HJ + J HJ ; . Set SJ = J + J SJ
K = 1,2, … , . . If SJ = 0, NOP SJ = Q
. Set RJ = J + J /RJ .
. If RJ = 0, NOP RJ = Q.
. Set SJ = 1/SJ , Δ = RJ SJ , 5J = 5J ΔJ .
. If ΔJ − 1 < Q , PℎO O P.
Chebyshev Approximation
The Chebyshev polynomial of degree is denoted W = cos( [\2N ).

It can be combined with trigonometric identities to yield explicit expression for W ( ):


W = 1 ;W = ;W = 2 − 1 ; WA = 4 A − 3 ; W_ = 8 _ − 8 + 1…
W =2 W −W , ∀ ≥ 1 (*).
Suppose b is so large. We consider the truncated approximation:
* *
i e 9 iJ e 9
5 ≈ Σef
g
\e We − \ (**) where \J = h
Σ h
ef 5 cos h
cos h
.

Now that we have the Chebyshev coefficients, how to evaluate the approximation?
We can use the above recurrence relation (*) to generate values for We from W = 1, W = ,
while also accumulating the sum of (**).
It is better to use Clenshaw’s recurrence formula:
1g ≡ 1g ≡ 0
1J = 2 1J − 1J + \J , K = . − 1, . − 2, … , 1
5 ≡1 = 1 −1 + \ .
Polynomial Approximation from Cheb. Coeff.
Convert the \ ’s into actual polynomial coefficients in the original variable and have an
e
approximation of the following form:
5 ≈ Σef
g
ke e
, ≤ ≤ .
Given a coefficients c[0..n-1], this routine returns Given a coefficients c[0..n-1], this routine returns
d[0..n-1]: Σef 1e j e = Σef \e We j − \ /2. g[0..n-1]: Σef 1e j e = Σef ke e − \ /2. The
Int k,j; interval -1<y<1 is mapped to the interval a<x<b.
Doub sv; Int k,j,n=[Link]();
VecDoub d(m), dd(m); Doub cnst=2.0/(b-a), fac=cnst;
For (j=0;j<m;j++): d[0]=c[m-1]; VecDoub d(m), dd(m);
For (j=m-2;j>0;j--): For (j=0;j<n;j++):
for (k=m-2;k>0;k--): d[j] *= fac
sv=d[k]; fac *= cnst
d[k]=2.0*d[k-1]-dd[k]; cnst = 0.5*(a+b)
dd[k]=sv; For (j=0; j< n-2; j++):
sv=d[0]; for (k=n-2; k>=j; k--):
d[0]=-dd[0]+c[j] d[k] -= cnst*d[k+1]
dd[0]=sv
For (j=m-2;j>0;j--): d[j]=d[j-1]-dd[j];
d[0]=-dd[0]+0.5*c[0];
Return d

You might also like