Oct 16, 2013

Zeros of the Legendre Polynomials

Legendre functions (Legendre polynomials) are the solutions of the following linear Ordinary Differential Equation (ODE), \[
\frac{\mathrm{d}}{d x}\left[ (1-x^2) \frac{\mathrm{d}}{\mathrm{d}x} P_n(x) \right] + n(n+1)P_n(x) = 0

The Legendre function $P_n(x)$ is a degree $n$ polynomial. It has $n$ distinct roots within (-1,1), $x_{n,k}, k=1,2,\cdots n$, $x_{n,1} < x_{n,2} < \cdots < x_{n,n}$. There is no analytical solution for high order Legendre polynomials. It is useful to know the analytical bounds of the roots.

According to Bruns, Markoff, Stieltjes and Szego [1], the roots satisfy the following inequality, \[
\cos\frac{(n-k+1)\pi}{n+1} < x_{n,k} < \cos\frac{(n-k+\frac{3}{4})\pi}{n+\frac{1}{2}}
 \] for $k = 1, \cdots \left[\frac{n}{2}\right]$. For the other half, recall $x_{n,n-k+1} = -x_{n,k}$.

It may also be useful to give a pair of global bounds, \[
\cos\frac{(n-k+\frac{1}{2})\pi}{n+\frac{1}{2}} < x_{n,k} < \cos\frac{(n-k+1)\pi}{n+\frac{1}{2}}
\] for $k=1,2,\cdots n$, although this is a coarse one.

The roots of the Legendre polynomials also admit asymptotic expansion due to Francesco Tricomi [2]. Let $\theta_{n,k} = \frac{n-k+3/4}{n+1/2}\pi$. Then the $k$-th root (in ascent order) is \[
x_{n,k} = \left\{1 - \frac{1}{8n^2} + \frac{1}{8n^3} - \frac{1}{384n^4}\left( 39 - \frac{28}{\sin^2\theta_{n,k}} \right) + \mathcal{O}(n^{-5})\right\} \cos\theta_{n,k}, \] which can be improve by Newton's algorithm $x_{\nu+1} = x_{\nu} - \frac{1-x_\nu^2}{n} \frac{P_n(x_\nu)}{P_{n-1}(x_\nu) -x_\nu P_n(x_\nu)}$.

Another approximation due to Gatteschi and Pittaluga [3] is \[
x_{n,k} = \cos\left\{ \theta_{n,k} + \frac{1}{16(n+1/2)^2}(\cot\frac{1}{2}\theta_{n,k} - \tan\frac{1}{2}\theta_{n,k}) \right\} + \mathcal{O}(n^{-4}).

Let $x_{n,k}$ be the $k$-th root of $P_n(x)$, $\xi_{n,k}$ be its approximations.

The $x_{n,k} \simeq \cos\theta_{n,k}$ is a pretty good estimator of the location $k$ of Gaussian nodes from $x_{n,k}$.

Last but not least, the zeros are the nodes of the Gaussian quadrature. \[
 \int_{-1}^{+1} \mathrm{d}x f(x) \simeq \sum_{k=1}^n w_{n,k} f(x_{n,k})
\] where $w_{n,k} = \frac{2}{(1-x_{n,k}^2) \left[ P'_n(x_{n,k}) \right]^2}$ are called the Gaussian weights. Gaussian quadrature can be illustrated by the bellow figure ($n = 16$).


[1] Gabriel Szego, Inequalities for the Zeros of Legendre Polynomials and Related Functions, Transactions of the American Mathematical Society, Vol. 39, No. 1 (1936)

[2] F. G. Tricomi, Sugli zeri dei polinomi sferici ed ultrasferici, Ann. Mat. Pura Appl., 31 (1950), pp. 93–97; F.G. Lether and P.R. Wenston, Minimax approximations to the zeros of $P_n(x)$ and Gauss-Legendre quadrature, Journal of Computational and Applied Mathematics Volume 59, Issue 2, 19 May 1995, Pages 245–252

[3] L. Gatteschi and G. Pittaluga, An asymptotic expansion for the zeros of Jacobi polynomials, in Mathematical Analysis. Teubner-Texte Math., 79 (1985), pp. 70–86

Source codes:

John Burkardt (GNU LGPL): http://people.sc.fsu.edu/~jburkardt/cpp_src/quadrule/quadrule.html

pomax.github.io: http://pomax.github.io/bezierinfo/legendre-gauss.html

rosettacode: http://rosettacode.org/wiki/Numerical_integration/Gauss-Legendre_Quadrature


GaussianQuadratureWeights[n, a, b, prec]

Oct 9, 2013

Smoothing a polygon

Ref. [1] has an interesting observation. For any closed polygon, if one takes the midpoint repeatedly, the polygon will be eventually smoothed out. The authors observed that the curves will become an elliptic.

The mapping is in fact independent in x and y directions. Therefore, after large enough iteration, the x and y coordinate will be "in phase", i.e. belong to the same eigensubspace.

randline[n_Integer, a_: - 1, b_: 1] := RandomReal[{a, b}, {n, 2}]

mpt[pts_, n_: 3] := 
 Table[Sum[pts[[Mod[i + j - 1, Length@pts, 1]]], {j, 1, n}]/n, {i, 1, 

nl[npts_, nitr_, n_: 2, a_: - 1, b_: 1] := 
  NestList[mpt[#, n] &, randline[npts, a, b], nitr];

randplot[npt_, nit_, nst_: 10, na_: 2, pt_: False, init_: False, a_: - 1,
   b_: 1] :=
 Module[{n, i0 = Min[Max[1, nst], nit + 1]},
  n = nl[npt, nit, na, a, b];
     Flatten[Table[{Hue[(i - i0)/(nit + 1 - i0)], 
        Line[closeline[n[[i]]]], PointSize[Medium], 
        Point[n[[i]]]}, {i, nst, nit + 1}], 1]],
     Flatten[Table[{Hue[(i - nst)/(nit + 1 - i0)], 
        Line[closeline[n[[i]]]]}, {i, nst, nit + 1}], 1]]
    ], If[init,
    Graphics[{Opacity[0.6], Line[closeline[n[[1]]]]}],

I here also present the spectrum


Oct 6, 2013

The Pythagorean theorem in "Zhou Bi Suan Jing" (周髀算经)

The celebrated Phythagorean theorem gives the relation between the sides of a right triangle: \[
a^2 + b^2 = c^2
\] where $a,b,c$ are the lengths of the sides with $c$ the one opposite to the right angle.

In China, the theorem is known as "Gou Gu Theorem" (勾股定理) or "Gou Gu Xian Theorem" (勾股弦定理). It first appears in the oldest Chinese mathematical book that survives today, the "Zhou Bi Suan Jing" (周髀算经). "Zhou" refers to the ancient dynasty Zhou (周); "Bi" means arm and according to the book, it refers to the gnomon of the sundial. The book is dedicated to astronomical observation and calculation. "Suan Jing" or "classic of arithmetic" were appended in later time to honor the achievement of the book in mathematics.

In Chapter I.1, In a dialog between "the Duke of Zhou" (周公) and "Gao of Shang" (商高), Gao said,
"故折矩, 以為句廣三, 股修四,徑隅五."
"So for the half of the rectangle,  if Gou is three, Gu is four, then Xian is Five."

Gou (勾/句) , Gu (股), Xian (弦) are the Chinese names of the three sides of a triangle. These texts essentially give a Pythagorean triplet (3, 4, 5), a triple of numbers that satisfies the Pythagorean equation $a^2 + b^2 = c^2$. Further explanation appears in Chaper I.2 in a dialog between "Rong Fang" (荣方) and "Chen Zi"  (陈子). Chen Zi in explaining a problem concerning of the measurement of the position of the sun, said,
"若求邪至日者, 以日下為句, 日高為股, 句股各自乘, 并而開方除之, 得邪至日."
"Suppose the distance to the sun is wanted. Let the distance to the projection of the sun on the ground be Gou, the distance of the sun to the ground be Gu. Square them respectively, add together and take the square root. Then the distance to the sun is obtained." 

Now the Pythagorean theorem is given.

The author of Zhou Bi is unknown, nor the year was it written. But according to the texts, it is a collection of the astronomical and mathematical methods of the Shang and Zhou dynasty ( 1100 - 1000 BC). The Duke of Zhou is the brother of the creator of Zhou dynasty, which had been a state in the Shang dynasty. Gao of Shang was apparently a figure in the Shang dynasty, as suggested by his name. If this is true, the Pythagorean theorem was proposed as early as 1000BC, contrast of Pythagoras who lived between 570 BC - 495 BC. Other people argue that Zhou Bi was compiled by more than one author and settled around 200 BC.