NISP

NISP Commit Details

Date:2015-03-31 21:26:29 (3 years 6 months ago)
Author:Michael Baudin
Commit:334
Parents: 333
Message:Added Chebyshev figure for T11.
Changes:
A/doc/polychaos/figures/cheby11.pdf
A/doc/polychaos/scripts/chebyshev.sce
M/doc/polychaos/5-particularorthopoly.tex
M/doc/polychaos/4-gaussintegral.tex
M/doc/polychaos/1-orthopoly.tex

File differences

doc/polychaos/figures/cheby11.pdf
doc/polychaos/5-particularorthopoly.tex
206206
207207
208208
209
209
210210
211211
212212
......
228228
229229
230230
231
231
232
232233
233234
234235
235
236
236237
237238
238239
......
261262
262263
263264
264
265
265266
266267
267268
268269
269270
270271
271
272
272273
273274
274275
......
284285
285286
286287
287
288
288289
289290
290
291
291
292
293
294
292295
293296
294297
295298
296
299
297300
298301
299302
......
452455
453456
454457
455
458
456459
457460
458461
......
477480
478481
479482
480
483
484
481485
482486
483487
......
510514
511515
512516
513
517
514518
515519
516520
......
520524
521525
522526
523
524
525
527
528
529
530
526531
527532
528533
529534
530
531
535
536
537
532538
533539
534540
......
537543
538544
539545
540
541
546
547
542548
543549
544550
545551
546552
547
553
548554
549555
550556
......
555561
556562
557563
558
564
559565
560566
561567
......
730736
731737
732738
733
739
734740
735741
736742
......
759765
760766
761767
762
768
763769
764770
765771
......
773779
774780
775781
776
782
777783
778784
779785
......
781787
782788
783789
784
790
785791
786792
787793
......
820826
821827
822828
823
829
824830
825831
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
832
833
834
843835
844
836
837
845838
846
839
847840
848
849
850
851
852
853
854
841
855842
856843
857844
......
10761063
10771064
10781065
1079
1066
1067
10801068
10811069
10821070
10831071
10841072
1085
1086
10871073
10881074
10891075
......
11141100
11151101
11161102
1117
1118
1119
1120
1103
1104
1105
1106
1107
1108
11211109
11221110
11231111
11241112
11251113
1114
1115
11261116
11271117
11281118
1129
1119
1120
1121
11301122
11311123
11321124
......
11401132
11411133
11421134
1135
11431136
11441137
11451138
......
11481141
11491142
11501143
1151
11521144
11531145
11541146
......
12101202
12111203
12121204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
12131241
12141242
12151243
......
12901318
12911319
12921320
1293
1321
12941322
12951323
12961324
\end{proposition}
The previous proposition will not be proved here.
The previous proposition will not be proved in this document.
\begin{proposition}
\label{prop-orthoher}
\begin{proof}
Rodrigues' formula for Hermite polynomials imply :
\begin{eqnarray}
\int_{-\infty}^\infty He_n(x) He_m(x) w(x) dx
(He_n,He_m)
&=& \int_{-\infty}^\infty He_n(x) He_m(x) w(x) dx \nonumber \\
&=& (-1)^{n}
\int_{-\infty}^\infty e^{\frac{x^2}{2}} \frac{d^n}{dx^n} \left(e^{-\frac{x^2}{2}}\right) He_m(x) e^{-\frac{x^2}{2}} dx \nonumber \\
&=& (-1)^{n}
\int_{-\infty}^\infty \frac{d^n}{dx^n} \left(e^{-\frac{x^2}{2}}\right) He_m(x) dx
\int_{-\infty}^\infty \frac{d^n}{dx^n} \left(e^{-\frac{x^2}{2}}\right) He_m(x) dx.
\label{eqn-orthoherm1}
\end{eqnarray}
\int_{-\infty}^\infty \frac{d^n}{dx^n} \left(e^{-\frac{x^2}{2}}\right) He_m(x) dx
&=&- \int_{-\infty}^\infty \frac{d^{n-1}}{dx^{n-1}} \left(e^{-\frac{x^2}{2}}\right) \frac{d}{dx} He_m(x) dx
\end{eqnarray*}
Integrating $n-1$ more times by part, we get :
Integrating by part $n-1$ more times, we get :
\begin{eqnarray*}
\int_{-\infty}^\infty \frac{d^n}{dx^n} \left(e^{-\frac{x^2}{2}}\right) He_m(x) dx
&=&(-1)^n \int_{-\infty}^\infty e^{-\frac{x^2}{2}} \frac{d^n}{dx^n} He_m(x) dx
\end{eqnarray*}
We plug the previous equation into \ref{eqn-orthoherm1} and get :
\begin{eqnarray}
\int_{-\infty}^\infty He_n(x) He_m(x) w(x) dx
(He_n,He_m)
&=& (-1)^{n} (-1)^n \int_{-\infty}^\infty e^{-\frac{x^2}{2}} \frac{d^n}{dx^n} He_m(x) dx \nonumber \\
&=& \int_{-\infty}^\infty e^{-\frac{x^2}{2}} \frac{d^n}{dx^n} He_m(x) dx
\label{eqn-orthoherm2}
Secondly, assume that $n=m$.
The equation \ref{eqn-orthoherm2} implies :
\begin{eqnarray*}
\int_{-\infty}^\infty He_n(x) He_m(x) w(x) dx
(He_n,He_n)
&=& \int_{-\infty}^\infty e^{-\frac{x^2}{2}} \frac{d^n}{dx^n} He_n(x) dx.
\end{eqnarray*}
The equation \ref{eqn-hermiterec} makes clear that $He_n$ is a monic degree $n$ polynomial.
In other words, its leading term is $x^n$.
The equation \ref{eqn-hermiterec} implies that $He_n$ is a monic degree
$n$ polynomial since the monomial with highest exponent
is $xHe_n(x)$.
In other words, the leading term of $He_n$ is $x^n$.
The $n$-th derivative of this monomial is $n!$ and the $n$-th derivative of lower degree
monomials is zero.
Hence,
\begin{eqnarray*}
\int_{-\infty}^\infty He_n(x) He_m(x) w(x) dx
(He_n,He_n)
&=& n! \int_{-\infty}^\infty e^{-\frac{x^2}{2}} dx \\
&=& n! \sqrt{2\pi},
\end{eqnarray*}
for $x\in[-1,1]$.
\end{proposition}
The previous proposition will not be proved here.
The previous proposition will not be proved in this document.
\begin{proposition}
Rodrigues' formula \ref{eqn-rodrileg} implies :
\begin{eqnarray*}
\int_{-1}^1 P_n(x) P_m(x) dx
(P_n,P_m)
&=&\int_{-1}^1 P_n(x) P_m(x) w(x) dx \\
&=& \frac{1}{2^{n+m} n! m!} \int_{-1}^1 \frac{d^n}{dx^n} ((x^2-1)^n) \frac{d^m}{dx^m} ((x^2-1)^m) dx.
\end{eqnarray*}
Integration by part implies :
\end{eqnarray*}
We continue to integrate by part $n-1$ more times, and get :
\begin{eqnarray}
\int_{-1}^1 P_n(x)P_m(x)
(P_n,P_m)
=\frac{(-1)^n}{2^{n+m} n! m!} \int_{-1}^1 (x^2-1)^n \frac{d^{m+n}}{dx^{m+n}} ((x^2-1)^m) dx,
\label{eqn-ortholeg2}
\end{eqnarray}
Now, suppose that $m<n$ (in the case where $m>n$, then we just switch $m$ and
$n$).
This implies $2m<m+n$.
But the leading monomial of $(x^2-1)^m$ is $x^{2m}$, which shows that
the derivative in the right hand side of the previous integral is zero,
and concludes the first part of the proof.
But the leading monomial of $(x^2-1)^m$ is $x^{2m}$, which
implies that the derivative in the right hand side of the
previous integral is zero, and concludes the first part of the
proof.
We now prove the equation \ref{eqn-ortholeg} when $m= n$.
The equation \ref{eqn-ortholeg2} implies :
\begin{eqnarray}
\int_{-1}^1 P_n(x)^2 dx
=\frac{(-1)^n}{2^{2n} (n!)^2} \int_{-1}^1 (x^2-1)^n \frac{d^{2n}}{dx^{2n}} ((x^2-1)^n) dx,
(P_n,P_n)
&=&\int_{-1}^1 P_n(x)^2 w(x) dx \nonumber \\
&=&\frac{(-1)^n}{2^{2n} (n!)^2} \int_{-1}^1 (x^2-1)^n \frac{d^{2n}}{dx^{2n}} ((x^2-1)^n) dx,
\label{eqn-ortholeg3}
\end{eqnarray}
except for the leading term $x^{2n}$.
This implies :
\begin{eqnarray*}
\frac{d^{2n}}{dx^{2n}} ((x^2-1)^n) dx
&=& \frac{d^{2n}}{dx^{2n}} x^{2n} dx \\
\frac{d^{2n}}{dx^{2n}} ((x^2-1)^n)
&=& \frac{d^{2n}}{dx^{2n}} x^{2n} \\
&=& (2n)!.
\end{eqnarray*}
We plug the previous equation into \ref{eqn-ortholeg3}, which implies
\begin{eqnarray}
\int_{-1}^1 P_n(x)^2 dx
(P_n,P_n)
=(-1)^n \frac{(2n)!}{2^{2n} (n!)^2} \int_{-1}^1 (x^2-1)^n dx.
\label{eqn-ortholeg4}
\end{eqnarray}
\end{eqnarray*}
We plug the previous equation into \ref{eqn-ortholeg4} and get :
\begin{eqnarray*}
\int_{-1}^1 P_n(x)^2 dx
(P_n,P_n)
&=&(-1)^n \frac{(2n)!}{2^{2n} (n!)^2} (-1)^n \frac{(n!)^2 2^{2n+1}}{(2n+1)!} \\
&=&\frac{2}{2n+1},
\end{eqnarray*}
for $x\geq 0$.
\end{proposition}
The previous proposition will not be proved here.
The previous proposition will not be proved in this document.
\begin{proposition}
\label{prop-ortholagu}
Indeed, we can use the Rodrigues formula \ref{eqn-rodrilagu} then integrate by part.
This leads to :
\begin{eqnarray}
(L_n(x), L_m(x) )
(L_n, L_m )
&=& \int_{0}^\infty \frac{e^x}{n!} \frac{d^n}{dx^n} \left(x^ne^{-x} \right) L_m(x) e^{-x} dx \nonumber \\
&=& \frac{1}{n!} \int_{0}^\infty \frac{d^n}{dx^n} \left(x^ne^{-x} \right) L_m(x) dx \nonumber \\
&=& \frac{1}{n!} \left[ \frac{d^{n-1}}{dx^{n-1}} \left(x^ne^{-x} \right) L_m(x) \right]_{0}^\infty \nonumber \\
\end{eqnarray*}
The previous equation implies that the first derivative of
$x^n e^{-x}$ has $x^{n-1} e^{-x}$ as factor.
Using this recursively, we find that
By induction on $n$, this implies that
$$
\frac{d^{n-1}}{dx^{n-1}} \left(x^ne^{-x} \right)
$$
Hence the first expression in the equation \ref{eqn-ortholagu2} is zero.
This implies :
\begin{eqnarray*}
(L_n(x), L_m(x) )
(L_n, L_m )
&=& - \frac{1}{n!} \int_{0}^\infty \frac{d^{n-1}}{dx^{n-1}} \left(x^ne^{-x} \right) \frac{d}{dx} L_m(x) dx.
\end{eqnarray*}
Using the same method $n-1$ more times leads to the equation \ref{eqn-ortholagu1}.
\frac{d^n}{dx^n} L_n(x) = (-1)^n \frac{n!}{n!} = (-1)^n.
$$
We plug the previous equation into \ref{eqn-ortholagu3} and get :
\begin{eqnarray}
\begin{eqnarray*}
(L_n, L_n )
&=& \frac{(-1)^{2n}}{n!} \int_{0}^\infty x^n e^{-x} dx \nonumber \\
&=& \frac{1}{n!} \int_{0}^\infty x^n e^{-x} dx. \label{eqn-ortholagu4}
\end{eqnarray}
Let
$$
I_n = \int_{0}^\infty x^n e^{-x} dx,
$$
for $n=0,1,...$.
Obviously,
$$
I_0= \int_{0}^\infty e^{-x} dx = 1.
$$
Integrating by part, we get :
\begin{eqnarray*}
I_{n+1}
&=& \int_{0}^\infty x^{n+1} e^{-x} dx \\
&=& - \left[x^{n+1} e^{-x} \right] + (n+1) \int_{0}^\infty x^n e^{-x} dx \\
&=& (n+1)I_n.
&=& \frac{1}{n!} \int_{0}^\infty x^n e^{-x} dx. \\
&=& \frac{n!}{n!} \\
&=& 1,
\end{eqnarray*}
By induction on $n$, we get :
where we have used the proposition \ref{prop-laguint}, page \pageref{prop-laguint},
which proves that
$$
I_n = \int_{0}^\infty x^n e^{-x} dx = n!.
\int_{0}^\infty x^n e^{-x} dx = n!,
$$
We plug the previous equation into \ref{eqn-ortholagu4} and get :
\begin{eqnarray*}
(L_n, L_n )
&=& \frac{n!}{n!} \\
&=&1,
\end{eqnarray*}
which concludes the second part of the proof.
for $n\geq 0$.
\end{proof}
Laguerre polynomials are solutions of the following differential equation :
\begin{eqnarray*}
(T_n,T_m)
&=& \frac{1}{2} \int_0^\pi \left( \cos((n+m)\theta) + 1 \right) d\theta \\
&=& \frac{1}{2} \left[ \frac{\cos((n+m)\theta)}{n+m} + \theta \right]_0^\pi \\
&=& \frac{1}{2} \int_0^\pi \left( \cos(2n\theta) + 1 \right) d\theta \\
&=& \frac{1}{2} \left[ \frac{\sin(2n\theta)}{2n} + \theta \right]_0^\pi \\
&=& \frac{1}{2},
\end{eqnarray*}
which concludes the proof.
\end{proof}
\begin{proposition}
(\emph{Roots of Chebyshev polynomials})
The Chebyshev polynomial of degree $n$ has $n$
There is one small issue with the equation \ref{eqn-chebyroot}.
When $k=1,...,n$, the roots $x_1,...,x_n$ are from the end of the
interval $[-1,1]$ to the beginning.
This might be surprising for users, which may expect that the
roots are in increasing order.
It can be proved that the roots of the Chebyshev polynomial
of degree $n$ are :
This might be surprising, because we may expect that the
roots are in increasing order.
This issue is solved by the following proposition.
\begin{proposition}
The roots of the Chebyshev polynomial of degree $n$ are :
\begin{eqnarray}
\label{eq-chebynodes}
x_k = -\cos\left(\frac{2k-1}{2n}\pi\right),
\end{eqnarray}
for $k=1,...,n$.
\end{proposition}
The roots defined by the equation \ref{eq-chebynodes}
are computed in increasing order when $k=1,...,n$ and are
the same as the roots defined by the equation \ref{eqn-chebyroot}.
Indeed, notice that :
\begin{proof}
Notice that :
$$
\cos(\theta)=-\cos(\pi-\theta),
$$
&=& \cos\left(\frac{2j-1}{2n}\pi\right),
\end{eqnarray*}
with $j=n-i+1$.
\end{proof}
The corresponding weights in the quadrature rule are
\begin{eqnarray}
\end{eqnarray}
for $k=1,...,n$.
\begin{proposition}
(\emph{Extrema of Chebyshev polynomials})
The extrema of the Chebyshev polynomial of degree $n$ are :
\left(\frac{1}{\sqrt{1-x^2}} y'\right)' = -\frac{n^2}{\sqrt{1-x^2}}y.
\end{eqnarray*}
The figure \ref{fig-cheby11} presents the polynomial $T_{11}$.
It is produced by the following script, which uses the
\scifun{cheby\-shev\_eval} function in order to evaluate $T_{11}$
on the interval $[-1,1]$.
Then we use the \scifun{cheby\-shev\_quadrature} function in order
to computes the roots \scifun{r} and the weights \scifun{w} of the
Gauss-Chebyshev quadrature.
\lstset{language=scilabscript}
\begin{lstlisting}
n=11;
x=linspace(-1,1,100);
y=chebyshev_eval(x,n);
plot(x,y)
[r,w]=chebyshev_quadrature(n);
plot(r,zeros(r),"rx")
xlabel("x")
ylabel("P(x)")
title(msprintf("Chebyshev polynomial - Degree %d",n))
\end{lstlisting}
We can see that the roots of the Chebyshev polynomial have
a higher density at the ends of the interval $[-1,1]$.
Moreover, we check that the polynomial $T_{11}$ oscillates,
although its absolute value is always lower than 1,
as predicted by the equation \ref{eqn-chebyext2}.
\begin{figure}
\begin{center}
\includegraphics[width=0.7\textwidth]{figures/cheby11.pdf}
\end{center}
\caption{
Degree 11 Chebyshev polynomial.
}
\label{fig-cheby11}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Accuracy of evaluation of the polynomial}
The figure \ref{fig-LaguerreD} plots the number of common digits,
when $n$ ranges from 1 to 100 and $x$ ranges from 1 to 21.
\begin{figure}[htbp]
\begin{figure}
\begin{center}
\includegraphics[width=0.5\textwidth]{figures/laguerredigits.pdf}
\end{center}
doc/polychaos/scripts/chebyshev.sce
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Copyright (C) 2015 - Michael Baudin
//
// This file must be used under the terms of the
// GNU Lesser General Public License license :
// http://www.gnu.org/copyleft/lesser.html
n=11;
x=linspace(-1,1,100);
y=chebyshev_eval(x,n);
plot(x,y)
[r,w]=chebyshev_quadrature(n);
plot(r,zeros(r),"rx")
xlabel("x")
ylabel("P(x)")
title(msprintf("Chebyshev polynomial - Degree %d",n))
doc/polychaos/4-gaussintegral.tex
250250
251251
252252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
\end{eqnarray*}
which shows that the recurrence is true for $n$ and concludes the proof.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A Laguerre integral}
\label{sec-laguint}
The goal of this section is to prove the following proposition.
\begin{proposition}
\label{prop-laguint}
We have
$$
\int_{0}^\infty x^n e^{-x} dx = n!,
$$
for $n\geq 0$.
\end{proposition}
\begin{proof}
Let
$$
I_n = \int_{0}^\infty x^n e^{-x} dx,
$$
for $n=0,1,...$.
Obviously,
$$
I_0= \int_{0}^\infty e^{-x} dx = 1.
$$
Integrating by part, we get :
\begin{eqnarray*}
I_{n+1}
&=& \int_{0}^\infty x^{n+1} e^{-x} dx \\
&=& - \left[x^{n+1} e^{-x} \right] + (n+1) \int_{0}^\infty x^n e^{-x} dx \\
&=& (n+1)I_n.
\end{eqnarray*}
By induction on $n$, we get :
$$
I_n = n!.
$$
\end{proof}
doc/polychaos/1-orthopoly.tex
965965
966966
967967
968
968
969
969970
970
971
971972
972973
973974
......
12321233
12331234
12341235
1235
1236
12361237
1238
12371239
12381240
12391241
......
12911293
12921294
12931295
1294
1296
12951297
12961298
12971299
1298
1300
12991301
1300
1301
1302
1303
1304
1305
1306
1307
13081302
13091303
13101304
13111305
1312
1313
1306
1307
1308
1309
1310
1311
13141312
13151313
13161314
\label{prop-threetermgen}
Assume $\{p_k\}_{k=-1,0,1,...,n}$ is a family of orthogonal
polynomials, with
$$
\begin{eqnarray}
\label{eq-threetermgen0}
p_{-1}=0, \qquad p_0=\frac{1}{\gamma_0},
$$
\end{eqnarray}
Therefore,
\begin{eqnarray}
p_{k+1}(x)=\frac{\gamma_k}{\gamma_{k+1}} (x-\alpha_k)p_k(x)
& \ddots & \ddots & \ddots & \\
& & \sqrt{\beta_{n-1}} & \alpha_{n-1} & \sqrt{\beta_{n}}\\
0 & & & \sqrt{\beta_{n}} & \alpha_n
\end{pmatrix}
\end{pmatrix},
$$
for $n\geq 0$.
\end{definition}
Notice that the previous matrix is symmetric.
\end{pmatrix} \\
&=&
\begin{pmatrix}
x p_0 \\
x p_0 - \sqrt{\beta_{0}} p_{-1} \\
x p_1 \\
\vdots \\
x p_{n-1} \\
x p_{n}
x p_{n} - \sqrt{\beta_{n+1}} p_{n+1}
\end{pmatrix}
-
\begin{pmatrix}
0 \\
0 \\
\vdots \\
0 \\
\sqrt{\beta_{n+1}} p_{n+1}
\end{pmatrix}
,
\end{eqnarray*}
where we have used the equation \ref{eq-eigenjacobi3} in
the last equality.
If $x$ is a root of $p_{n+1}$, then $p_{n+1}(x)=0$,
and the previous equation implies the equation \ref{eq-eigenjacobi1}.
First, the equation \ref{eq-threetermgen0} implies that
the first row is equal to $x p_0$.
Second, if $x$ is a root of $p_{n+1}$, then $p_{n+1}(x)=0$
which implies that the last row is equal to $x p_{n}$.
This is why the previous equation implies the equation \ref{eq-eigenjacobi1},
which concludes the proof.
\end{proof}
\begin{proposition}

Archive Download the corresponding diff file

Revision: 334