Calculators, Power Series and Chebyshev Polynomials: Unterschied zwischen den Versionen

Aus DMUW-Wiki
Wechseln zu: Navigation, Suche
(→‎Approximation by Chebyshev Polynomials)
Zeile 192: Zeile 192:
  
 
<math>
 
<math>
−
x=T_1(x), \
+
x=T_1(x), \quad
 
</math>
 
</math>
  
Zeile 206: Zeile 206:
  
 
<math>
 
<math>
−
S_5(x){{Kurzinfo-1|Idee}}=x-\frac{x^3}{6}+\frac{x^5}{120} =T_1(x)-\frac16\cdot\frac14(3T_1(x)+T_3(x))+\frac1{120}\cdot\frac1{16}(10T_1(x)+5T_3(x)+T_5(x)) =\frac{169}{192}T_1(x)-\frac5{128}T_3(x)+\frac1{1920}T_5(x).
+
S_5(x)=x-\frac{x^3}{6}+\frac{x^5}{120} =T_1(x)-\frac16\cdot\frac14(3T_1(x)+T_3(x))+\frac1{120}\cdot\frac1{16}(10T_1(x)+5T_3(x)+T_5(x)) =\frac{169}{192}T_1(x)-\frac5{128}T_3(x)+\frac1{1920}T_5(x).
 
</math>
 
</math>
  
Zeile 217: Zeile 217:
 
</math>
 
</math>
  
−
and the cubic function we end with is the function we called <math>F</math>.
+
and the cubic function we end with is the function we called <math>F\,</math>.
  
 
We have thus shown, partly through a graphical justification, that
 
We have thus shown, partly through a graphical justification, that
−
values of the cubic function <math>F</math>, where
+
values of the cubic function <math>F\,</math>, where
  
 
<math>
 
<math>
Zeile 226: Zeile 226:
 
</math>
 
</math>
  
−
are closer to values of <math>\sin\,x</math>, for <math>|x|\le2</math>, than are values of
+
are closer to values of <math>\sin\,x</math>, for <math>|x|\le2</math>, than are values of the cubic function <math>x-\frac16x^3</math>, which is obtained from the power
−
the cubic function <math>x-\frac16x^3/<math>, which is obtained from the power
+
series representation of <math>\sin\,x</math>.
−
series representation of <math>\sin x<math>.
+
  
 
==Conclusion==
 
==Conclusion==

Version vom 24. April 2010, 03:32 Uhr

Of all the familiar functions, such as trigonometric, exponential and logarithmic functions, surely the simplest to evaluate are polynomial functions. The purpose of this article is to introduce the concept of a power series, which can be thought of in the first place as a polynomial function of infinite degree. In particular, we will deduce a series for \sin\,x and will see how to improve on the the most straightforward way of approximating its values. This simplest way uses the polynomials obtained by truncating the power series. The improvement will involve Chebyshev polynomials, which are used in many ways for a similar purpose and in many other applications, as well. When a calculator gives values of trigonometric or exponential or logarithmic functions it is doing so by evaluating polynomial functions that are sufficiently good approximations. (For trigonometric functions, the Cordic algorithm is in fact often the preferred method of evaluation---the subject of another article here, perhaps.)

In the spirit of Felix Klein, there will be some reliance on a graphical approach.

Inhaltsverzeichnis

Manipulations with geometric series

The geometric series 1+x+x^2+x^3+\cdots is the simplest power series. The sum of the series exists when |x|<1\,. In fact,

1+x+x^2+x^3+\cdots=\frac 1{1-x}, \quad \mathrm{when}\ |x|<1. \qquad\qquad (1)

The general form of a power series is

a_0+a_1x+a_2x^2+a_3x^3+\cdots,

so the geometric series above is a power series in which all the coefficients a_0,\,a_1,\,a_2,\,\ldots are equal to 1. In this case, since the series converges to 1/(1-x)\, when |x|<1\,, we say that the function f\,, where

f(x)=\frac1{1-x}, \quad |x|<1,

has the series expansion 1+x+x^2+x^3+\cdots, or that f\, is represented by this series. We are interested initially to show some other functions that can be represented by power series.

Many such functions may be obtained directly from the result in (1). For example, by replacing x\, by -x^2\,, we immediately have a series representation for the function 1/(1+x^2)\,:

1-x^2+x^4-x^6+\cdots=\frac 1{1+x^2}, \quad \mathrm{when}\ |x|<1. \qquad\qquad (2)

We can differentiate both sides of (1) to give a series representation of the function 1/(1-x)^2\,:

1+2x+3x^2+4x^3+\cdots=\frac 1{(1-x)^2}, \quad \mathrm{when}\ |x|<1.

We can also integrate both sides of (1). Multiply through by -1 (for convenience), then write t\, for x\, and integrate with respect to t\, from 0 to x\,, where |x|<1\,:

-\int_0^x (1+t+t^2+t^3+\cdots)\,dt=-\int_0^x\frac {dt}{1-t},

so

-x-\frac{x^2}2-\frac{x^3}3-\frac{x^4}4-\cdots=\log\,(1-x), \quad \mathrm{when}\ |x|<1.

So this gives a series representation of the function \log\,(1-x) for |x|<1\,. In the same way, from (2),

x-\frac{x^3}3+\frac{x^5}5-\frac{x^7}7+\cdots=\tan^{-1}x, \quad \mathrm{when}\ |x|<1.

Much of what we have done here (and will do later) requires justification, but we can leave that to the textbooks.

The power series for the sine function

We will show next how to find a power series representation for \sin\,x. In general terms, we can write

\sin x=a_0+a_1x+a_2x^2+a_3x^3+\cdots. \qquad\qquad (3)

Put x=0\,, and immediately we have a_0=0\,. Differentiate both sides of (3):

\cos x=a_1+2a_2x+3a_3x^2+4a_4x^3+\cdots.

Again put x=0\,, giving a_1=1\,. Keep differentiating and putting x=0\,:

-\sin\,x = 2a_2+3\cdot2a_3x+4\cdot3a_4x^2+5\cdot4a_5x^3+\cdots, \qquad\mathrm{so}\ a_2=0,

-\cos\,x = 3\cdot2a_3+4\cdot3\cdot2a_4x+5\cdot4\cdot3a_5x^2+6\cdot5\cdot4a_6x^3+\cdots, \qquad\mathrm{so}\ a_3=\frac{-1}{3\cdot2}=\frac{-1}{3!},

\sin\,x = 4\cdot3\cdot2a_4+5\cdot4\cdot3\cdot2a_5x+6\cdot5\cdot4\cdot3a_6x^2+\cdots, \qquad\mathrm{so}\ a_4=0,

\cos\,x = 5\cdot4\cdot3\cdot2a_5+6\cdot5\cdot4\cdot3\cdot2a_6x+7\cdot6\cdot5\cdot4\cdot3a_7x^2+\cdots, \qquad\mathrm{so}\ a_5=\frac1{5\cdot4\cdot3\cdot2}=\frac1{5!}.

In this way, we can find a formula for all the coefficients a_0,\,a_1,\,a_2,\,\ldots, namely,

a_{2n}=0, \qquad\qquad a_{2n+1}=\frac{(-1)^n}{(2n+1)!},

for n=0,\,1,\,2,\,\ldots. (The coefficients of even index and those of odd index are specified separately.) Thus

\sin\,x=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots.

This is the power series representation that we were after. From the way we developed it, it is reasonable that the series will represent \sin\,x for values of x\, at and near 0 (say for |x|<1\,, as for all the earlier examples), so it is surprising to know that it can be shown that the series represents \sin\,x for all values of x\,. Then partial sums of the series, obtained by stopping after some finite number of terms, should give polynomial functions that can be used to find approximate values of the sine function, such as you find in tables of trigonometric functions or as output on a calculator.

Approximation by Chebyshev Polynomials

For example, write

S_3(x)=x-\frac{x^3}{3!} \quad \mathrm{and} \quad S_5(x)=x-\frac{x^3}{3!}+\frac{x^5}{5!}.

The cubic polynomial S_3(x)\, and the quintic polynomial S_5(x)\, are plotted below, along with \sin\,x, all for -2\le x\le 2. It can be seen that these are both very good approximations for -1\le x\le1, say, but not so good near x=\pm2. The quintic S_5\, is much better than the cubic S_3\, in these outer regions, as might be expected, but can we do better than S_3\, with some other cubic polynomial function?

When x=1\,, for example, the error in using the cubic is \sin1-(1-\frac16)\approx0.0081. We will construct a cubic polynomial function F\, whose values differ from those of \sin\,x by less than 0.001 for |x|\le1. The curve y=F(x)\, has been included in the graph below for |x|\le2, and it is clear from the graph that this curve is closer to that of y=\sin\,x than y=S_3(x)\, is, even near x=\pm2.

INSERT FIGURE HERE, WHEN WE WORK OUT HOW TO DO IT

We will use Chebyshev polynomials to construct F\,. These are used extensively in approximation problems, as we are doing here. They are the functions T_k\, given by

T_k(x)=\cos\,k\theta, \quad\mathrm{where}\ x=\cos\,\theta,

for integer k\ge0 (or you can write T_k(x)=\cos\,(k\cos^{-1}\,x)). By properties of the cosine, they all have domain [-1,1]\, and their range is also in [-1,1]\,. Putting k=0\, and k=1\, gives

T_0(x)=1, \qquad T_1(x)=x,

but it is not immediately apparent that the T_k\, are indeed polynomials for k\ge2. To see that this is the case, recall that

\cos\,(k+1)\theta=\cos\,(k\theta+\theta)=\cos\,k\theta\,\cos\,\theta-\sin\,k\theta\,\sin\,\theta,

\cos\,(k-1)\theta=\cos\,(k\theta-\theta)=\cos\,k\theta\,\cos\,\theta+\sin\,k\theta\,\sin\,\theta,

from which, after adding these,

\cos\,(k+1)\theta=2\cos\,\theta\,\cos\,k\theta-\cos\,(k-1)\theta.

Therefore,

T_{k+1}(x)=2xT_k(x)-T_{k-1}(x), \quad k\ge1.

Now put k=1,\,2,\,3,\,\ldots and obtain

T_2(x) = 2x^2-1, \quad

T_3(x) = 4x^3-3x, \qquad\qquad\qquad\quad\ (4)

T_4(x) = 8x^4-8x^2+1, \quad

T_5(x) = 16x^5-20x^3+5x, \qquad\qquad (5)

and so on, clearly obtaining a polynomial each time. As polynomials, we no longer need to think of their domains as restricted to [-1,1]\,.

Returning to our problem of approximating \sin\,x for |x|\le1 with error less than 0.001, we notice first that the quintic S_5\, has that property. In fact,

\left|\sin1-S_5(1)\right|=\left|\sin1-\left(1-\frac16+\frac1{120}\right)\right| <0.0002,

and the theory of alternating infinite series shows that |\sin\,x-S_5(x)|<0.0002 throughout our interval, as certainly seems reasonable from the figure. We next express S_5(x)\, in terms of Chebyshev polynomials. Using (4) and (5), we have

x=T_1(x), \quad

x^3=\frac14(T_3(x)+3x)=\frac14(T_3(x)+3T_1(x)),

x^5=\frac1{16}(T_5(x)+20x^3-5x)=\frac1{16}(T_5(x)+5T_3(x)+10T_1(x)),

so

S_5(x)=x-\frac{x^3}{6}+\frac{x^5}{120} =T_1(x)-\frac16\cdot\frac14(3T_1(x)+T_3(x))+\frac1{120}\cdot\frac1{16}(10T_1(x)+5T_3(x)+T_5(x)) =\frac{169}{192}T_1(x)-\frac5{128}T_3(x)+\frac1{1920}T_5(x).

Since |T_5(x)|\le1 when |x|\le1, omitting the term \frac1{1920}T_5(x) will admit a further error of at most \frac1{1920}<0.0006 which, using (6), gives a total error less than 0.0008, still within our bound of 0.001. Now,

\frac{169}{192}T_1(x)-\frac5{128}T_3(x) =\frac{169}{192}x-\frac5{128}(4x^3-3x)=\frac{383}{384}x-\frac5{32}x^3,

and the cubic function we end with is the function we called F\,.

We have thus shown, partly through a graphical justification, that values of the cubic function F\,, where

F(x)=\frac{383}{384}x-\frac5{32}x^3,

are closer to values of \sin\,x, for |x|\le2, than are values of the cubic function x-\frac16x^3, which is obtained from the power series representation of \sin\,x.

Conclusion

The effectiveness of Chebyshev polynomials for our purpose here arises from properties of the cosine function: for all integers k\ge0\, and for |x|\le1\,, we have, first, |T_k(x)|\le 1, and, second, the local maxima and minima of T_k(x)\, all equal 1 or -1. Pafnuty Lvovich Chebyshev, whose surname is often given alternatively as Tchebycheff, was Russian; he introduced these polynomials in a paper in 1854. The procedure outlined above is known as economization of power series.

Incomplete --- I have no idea how to include my graph, constructed with PStricks

Von „http://dmuw.zum.de/index.php?title=Calculators,_Power_Series_and_Chebyshev_Polynomials&oldid=18427“