{VERSION 5 0 "IBM INTEL NT" "5.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0
1 0 0 0 0 1 }{CSTYLE "" -1 256 "" 0 10 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 257 "" 1 20 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1
258 "" 1 16 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0
0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 1 0 0 0 0
0 0 0 1 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 }
{CSTYLE "" -1 262 "" 1 16 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1
263 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 1 16 0
0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 1 16 0 0 0 0 0 0 1 0
0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 267 "" 1 16 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1
268 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 1 16 0 0
0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 0 1 0 0 0
0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 272 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1
273 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 0 0 0
0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 277 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1
278 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 1 0 0 0 0 0
0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 282 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal
" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1
1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1
-1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2
0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1
2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{PSTYLE "AC - Title
" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }
3 1 0 0 12 12 1 0 1 0 1 2 258 1 }{PSTYLE "AC - Author" -1 257 1
{CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 1 2 2 2 2 2 1 1 1 1 }3 1 0 0 8
8 1 0 1 0 2 2 259 1 }{PSTYLE "AC - Note" -1 258 1 {CSTYLE "" -1 -1 "Ti
mes" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }
{PSTYLE "AC - Normal Text" -1 259 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0
0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "AC - Se
ction Heading" -1 260 1 {CSTYLE "" -1 -1 "Times" 1 16 0 0 0 1 2 1 2 2
2 2 1 1 1 1 }1 1 0 0 12 0 1 0 1 0 2 2 260 1 }{PSTYLE "AC - Disclaimer
" -1 261 1 {CSTYLE "" -1 -1 "Times" 1 9 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }
1 1 0 0 12 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 262 1 {CSTYLE "" -1
-1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2
0 1 }{PSTYLE "AC - Author" -1 263 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0
0 1 1 2 2 2 2 2 1 1 1 1 }3 1 0 0 4 4 1 0 1 0 2 2 259 1 }}
{SECT 0 {PARA 256 "" 0 "" {TEXT -1 58 "The Effect of Choice of Points \+
on Polynomial Interpolation" }{TEXT 261 2 ". " }{TEXT 257 0 "" }}
{PARA 263 "" 0 "" {TEXT 256 7 "\251 2003 " }{TEXT -1 127 "Nathan Colli
er, Autar Kaw, Jai Paul , University of South Florida , kaw@eng.usf.ed
u , http://numericalmethods.eng.usf.edu/mws ." }}{PARA 259 "" 0 ""
{TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 129 "This worksheet demonst
rates the use of Maple to show how the choice of points affects the po
lynomial interpolation of a function." }}{SECT 0 {PARA 260 "" 0 ""
{TEXT 258 12 "Introduction" }{TEXT -1 0 "" }}{PARA 259 "" 0 "" {TEXT
259 105 "The following example illustrates the difference in interpola
tion curves due to the selection of points. " }{TEXT -1 116 "In 1901, \+
Carl Runge published his work on dangers of higher order interpolation
. He took a simple looking function, " }{OLE 1 4103 1 "[xm]Br=WfoRrB::
:wk;nyyI;G:;:j::>:B>N:F:nyyyyy]::yyyyyy:::::::::::::::::::::::::::::::
::::::::::::::::::::::::::::::::::::::::fyyyyya:nYf::G:jy;::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::Jcv
GYMt>^:fBWMtNHm=;:::::::n:;`:Z@[::Jrit\\@WkMj[Aj;J:M:
<:=ja^GE=;:::::::::N;?R:yyyyyyA:yayA:<::::::JDJ:j\\FHemj^HMmqnG;KaFFJu
fF>::::::;K;HYLkNG>::::::::NZ:nF>:nY>;V:;JykZ;NZBH@=Jyyy;d:yayQZHQ:>
:;`:Z@wZFZ>WdZfbk;>ZEZ?GHZhV`:^xsNp
kK:<::Wml^EalqnFcmuFF_mlj[vyyuyA:C:=B:;jysy?B:>:fyEJ@M:wi:F:MB:Hjy@:AB
:s:;j<>:Mb:>Z:f:NZ;F:\\:B:;xyyQVyyyyYJeZ:>u=j?^;UTRcETcTX[US<<:^:<
jP@:EZ:^\\jxM:<:[V:>Z:^Z**cTTUUSaEBWTSiEB_tU
?ja^G>D_=aMR>`:J:<:::::::>=?R:J;b=Z:j::<::::::wyyyA<::::::::::::jysy:>:<:::::::::::::::::::v
YxI:;Z::::::::Z;NZ<@??B\\]K;TrONZBP@?B\\eKCHBAr=V[KFZ<>klB:dJ;DrN>Z:>:
;FZ;F::[K<>:Uk:>;;JSdJ@IJyaj:jN`Q>JSJA
XJ;>:PM>ZDJEPj:jRPM>JSJUMj:JNPM>JSng;FaAF:F@JS>f<>mJSJ^@j:>:K
KH>:qQJxI<:[^:B:Cb:^D:jp@Pq:s<=:;JR^Z:jPN:C:[Y:=J>JS>v:[[:jPF:C:[Q;JSdJ@?nBF:>io>;N@;e:CY:=J:>IJSJ;=j:JmP
MHjw;<:[N:b:;b:;B>aTXDpql`q?B:[K<>:UK;^:>X=J>JSdJ@_x
?F:V_o>;N@;e:[u:=B:faoN;n>N;yqyyy:J:^=VY[j=J:^q:[KX?B:AZ:>::::WTJWTLB::::::::::::::::::::::::::::::
::::::::::::::::::::::::::::::::::::2:" }{TEXT -1 452 " on the interva
l [-1,1]. He took points equidistantly spaced in [-1,1] and interpola
ted the points with polynomials. He found that as he took more points
, the polynomials and the original curve differed considerably. Howeve
r, he also discovered that if he took data points close to the ends of
the interval [-1,1], the problem of large differences between interpo
lated and actual values was less pronounced. This simulation shows yo
u this phenomena." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "restart
;with(linalg):" }}}}{PARA 260 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3
"" 0 "" {TEXT 262 17 "Section I : Data." }}{EXCHG {PARA 0 "" 0 ""
{TEXT -1 168 "Let us first chose points which are equidistantly placed
in [-1,1], and interpolate it. We will chose 11 points, [-1, -0.8, -0
.6, -0.4, -0.2, 0, 0.2, 0.4, 0.6, 0.8, 1]." }}{PARA 0 "" 0 "" {TEXT
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "Runge's Function is given by:"
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "fRunge:=x->1/(1+25*x^2);
" }}}}{PARA 3 "" 0 "" {TEXT 263 18 "Plotting the data:" }}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "plot(fRunge,-1..1,-1..1,thickness=2
,title=\"Runge's function\");" }}}{PARA 3 "" 0 "" {TEXT -1 0 "" }}
{SECT 0 {PARA 3 "" 0 "" {TEXT -1 0 "" }{TEXT 264 70 "Section II: Polyn
omial Interpolation with equidistantly spaced points." }}{PARA 0 "" 0
"" {TEXT -1 226 "Let us now interpolate Runge's function using polynom
ial interpolation in [-1,1], choosing 11 equidistantly spaced data poi
nts, [-1, -0.8, -0.6, -0.4, -0.2, 0, 0.2, 0.4, 0.6, 0.8, 1]. This will
give us a 10th order polynomial." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 207 "eq_poly:=interp([-1, -0.8, \+
-0.6, -0.4, -0.2, 0, 0.2, 0.4, 0.6, 0.8, 1],[fRunge(-1),fRunge(-0.8),f
Runge(-0.6),fRunge(-0.4),fRunge(-0.2),fRunge(0),fRunge(0.2),fRunge(0.4
),fRunge(0.6),fRunge(0.8),fRunge(1)],t);" }}}{EXCHG {PARA 0 "" 0 ""
{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 56 "We will now plot this fu
nction against Runge's function." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 210 "eq_poly:=t->interp([-1, -0.
8, -0.6, -0.4, -0.2, 0, 0.2, 0.4, 0.6, 0.8, 1],[fRunge(-1),fRunge(-0.8
),fRunge(-0.6),fRunge(-0.4),fRunge(-0.2),fRunge(0),fRunge(0.2),fRunge(
0.4),fRunge(0.6),fRunge(0.8),fRunge(1)],t):" }}}{EXCHG {PARA 0 "> " 0
"" {MPLTEXT 1 0 235 "plot([fRunge,eq_poly],-1..1,-0.5..1,thickness=2,c
olor=[red,green],title=\"Plot of Runge's Function and Polynomial inter
polated with equidistantly spaced points\",legend=[\"Runge's function
\",\"Polynomial with equidistantly spaced points\"]);" }}}}{PARA 4 ""
0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 0 "" }{TEXT 265
52 "Section III: Polynomial with more points at the end." }{TEXT -1 0
"" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 443 "The idea of this function is
to place more points at the ends of the interval than in the middle. \+
To do this, first the half interval from -1 to 1 is divided to give 'n
' points in [-1,1] ( 'n' needs to be odd). Then the number of divisio
ns is (n-1), and the number of divisions are divided equally, that is \+
(n-1)/2, between [-1,0] and [0,1]. For points from -1 to 0, starting \+
with -1 as the first point, and assuming the next points are -1+ " }
{TEXT 271 1 "l" }{TEXT -1 6 ", -1+2" }{TEXT 275 3 "l, " }{TEXT -1 4 "-
1+4" }{TEXT 276 10 "l, ......." }{TEXT -1 2 ",0" }{TEXT 277 2 ", " }
{TEXT -1 51 "where the distance between -1 and the next point is" }
{TEXT 279 4 " l, " }{TEXT -1 100 "and the distance between consecutive
points from -1 to 0 gets doubled after each point, the value of" }
{TEXT 280 3 " l " }{TEXT -1 11 "is given by" }{TEXT 281 2 " l" }{TEXT
-1 18 "=1/[2^\{(n-1)/2\}-1]" }{TEXT 282 1 "." }{TEXT -1 83 " \nThe poi
nts from 0 to 1 are mirror images about the y-axis of points from -1 t
o 0." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n:=11:" }}{PARA 0 ">
" 0 "" {MPLTEXT 1 0 236 "Xb:=matrix(n,1,0):\nd:=0:\nfor i from 2 to (
(n-1)/2)+1 do\nd:=d+2^(i-2):\nend do:\nl:=1/d:\nXb[1,1]:=-1:\nfor i fr
om 2 to ((n-1)/2)+1 do\nXb[i,1]:=Xb[i-1,1]+2^(i-2)*l:\nend do:\nfor i \+
from (n-1)/2+2 to n do\nXb[i,1]:=Xb[i-1,1]+(2^(n-i))*l:\nend do:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "Yb:=matrix(n,1,0):\nfor i fr
om 1 to n do\nYb[i,1]:=fRunge(Xb[i,1]):\nend do:" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 165 "When x and y data and order is given, the followi
ng constructs the matrix whose inverse is needed to find coefficients \+
of the polynomial which approximates the data." }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 98 "A:=matrix(n,n,0):\nfor i from 1 to n do\nfor j
from 1 to n do\nA[i,j]:=Xb[i,1]^(j-1):\nend do:\nend do:" }}}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 86 "This generates the coefficients for the p
olynomial that approximates the x and y data." }}}{EXCHG {PARA 0 "> "
0 "" {MPLTEXT 1 0 27 "M:=evalm(inverse(A) &* Yb):" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 136 "When given the polynomial order and specific x, t
his procedure uses the above calculated coefficients to calculate the \+
approximated f(x)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "f2:=pr
oc(x)\nlocal i,c,d;\nc:=0:\nfor i from 1 to n do\nd:=M[i,1]*x^(i-1)+c:
\nc:=d:\nend do:\nd;\nend proc:" }{TEXT -1 0 "" }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 237 "plot([fRunge,f2],-1..1,-0.5..1,thickness=2,color=[RE
D,BLUE],title=\"Runge's function and interpolated polynomial with more
points near the ends of the interval [-1,1]\",legend=[\"Runge's funct
ion\",\"Polynomial with more points at the end\"]);" }}}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}}{PARA 3 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 0 "" }
{TEXT 266 0 "" }{TEXT 267 23 "Section IV: Comparison." }}{PARA 0 "" 0
"" {TEXT -1 207 "Below is a plot to compare the polynomial obtained by
interpolating using equidistantly placed data points and the polynomi
al obtained by interpolation using more data points near the end point
s of -1 and 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> "
0 "" {MPLTEXT 1 0 341 "plot([fRunge,eq_poly,f2],-1..1,-0.5..1,thicknes
s=2,color=[RED,GREEN,BLUE],title=\"Runge's function and Interpolated p
olynomials with equidistant data points and with more data points near
the ends of the interval [-1,1]\",legend=[\"Runge's function\",\"Poly
nomial with equidistantly spaced data points\",\"Polynomial with more \+
points at the end\"]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 343 "To better understand the difference betw
een the polynomial obtained by interpolating with equidistantly spaced
data points and the polynomial obtained by interpolating more data po
ints at the end of the interval, let us find the value of these functi
ons and the actual value from Runge's function for any x that is not s
pecified, say, x = 0.5:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 39 "Value of the original function at x=0.5"
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "fRunge(0.5);" }}}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 93 "Value of the polynomial interpolant at x=
0.5 with equidistant points chosen for interpolation" }}}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 13 "eq_poly(0.5);" }}}{EXCHG {PARA 0 "" 0 ""
{TEXT -1 93 "Value of the polynomial interpolant at x=0.5 with more po
ints chosen close to the end points." }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 8 "f2(0.5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "
" }}}}{PARA 4 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT
-1 0 "" }{TEXT 268 0 "" }{TEXT 269 23 "Section VI: Conclusion." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 449 "Maple he
lped us to apply our knowledge of numerical methods of interpolation t
o find a better interpolant for Runge's function by polynomial interpo
lation by choosing more data points at the end of the interval as oppo
sed to using equidistantly spaced data points. Although there is no \+
rule for choosing points for interpolation for a better approximation,
rules can be derived for particular functions (Davis, 1963; Kahaner, \+
Moler and Nash, 1989)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0
"" {TEXT -1 344 "Can you repeat the example by finding two polynomials
choosing 21 points. The points for the first polynomial are obtained
by using equidistantly spaced points and the points for the second po
lynomial are obtained using points concentrated towards the end in [-1
,1] domain. Compare the results for the two polynomials for a value o
f x = -0.7?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 4 "" 0 "" {TEXT
270 11 "References:" }}{PARA 0 "" 0 "" {TEXT -1 3 "[1]" }{TEXT 272 54
" Autar Kaw, Holistic Numerical Methods Institute, See " }}{PARA 0 ""
0 "" {TEXT 278 84 "http://numericalmethods.eng.usf.edu/mws/ind/05inp/m
ws_ind_inp_spe_choiceofpoints.pdf" }}{PARA 0 "" 0 "" {TEXT -1 14 "[2] \+
P. Davis, " }{TEXT 273 31 "Interpolation and Approximation" }{TEXT -1
28 ", Balisdell, New York, 1963." }}{PARA 0 "" 0 "" {TEXT -1 36 "[3] D
. Kahaner, C. Molder, S. Nash, " }{TEXT 274 30 "Numerical Methods and \+
Software" }{TEXT -1 32 ", Prentice Hall, New York, 1989." }}{PARA 261
"" 0 "" {TEXT -1 0 "" }{TEXT 260 11 "Disclaimer:" }{TEXT -1 248 " Whil
e every effort has been made to validate the solutions in this workshe
et, University of South Florida and the contributors are not responsib
le for any errors contained and are not liable for any damages resulti
ng from the use of this material." }}}{MARK "0 0" 0 }{VIEWOPTS 1 1 0
1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }
**