New formulas for barycentric weights for Chebyshev third and fourth kind point distributions

[pasabanov]

Problem or Motivation

Currently, the alfi::misc::barycentric function supports special formulas for barycentric weights only for the following point distributions:

• Uniform
• Chebyshev (first kind)
• Circle projection (Chebyshev second kind)

The formulas for the "Chebyshev" and "Circle projection" distributions are very stable.

However, according to the article [1], there are at least two additional point distributions for which a special stable barycentric weight formulas exist: "Chebyshev third kind" and "Chebyshev fourth kind".

The corresponding formulas can be found in the referenced article.

There may also be other formulas applicable to the point distributions already implemented in the library, so further investigation is warranted.

Solution or Suggestion

Implement special formulas for barycentric weights for the "Chebyshev third kind" and "Chebyshev fourth kind" point distributions.

Tasks:

1. • Implement "Chebyshev third kind" point distribution. Added (circle|ellipse)_proj_no_(last|first) distribution types #48
2. • Implement "Chebyshev fourth kind" point distribution. Added (circle|ellipse)_proj_no_(last|first) distribution types #48
3. • Integrate the new formulas into alfi::misc::barycentric. Added (circle|ellipse)_proj_no_(last|first) distribution types #48
4. • Add description of the barycentric formula in https://github.com/ALFI-lib/alfi-lib.github.io. https://github.com/ALFI-lib/alfi-lib.github.io/pull/16
5. • Add test data for new distributions. Add test data for new Chebyshev-related point distributions test_data#5 Added chebyshev(_ellipse)?_(3|4) distributions data test_data#6
6. • Rename: chore(dist): Renamed Chebyshev-related distributions and updated tests #51
   • circle_proj to chebyshev_2
   • circle_proj_no_last to chebyshev_3
   • circle_proj_no_first to chebyshev_4
7. • Link tests to updated test data. chore(dist): Renamed Chebyshev-related distributions and updated tests #51

Further improvements:

• Evaluate and implement special formulas for barycentric weights for other point distributions.

Sources of literature:

1. Jean-Paul Berrut and Lloyd N. Trefethen, Barycentric Lagrange Interpolation (2004) – people.maths.ox.ac.uk/trefethen/barycentric.pdf
2. Families of polynomials related to Chebyshev polynomials – Wikipedia

[pasabanov]

It turns out that "Chebyshev points of the second kind", "Chebyshev points of the third kind", and "Chebyshev points of the fourth kind", as mentioned in the article Jean-Paul Berrut and Lloyd N. Trefethen, Barycentric Lagrange Interpolation (2004), have nothing to do with the Chebyshev polynomials of the second, third, and fourth kinds.

I have no idea why they are referred to this way in the article.

Here is the proper definition of these points from J.-P. Berrut, Baryzentrische Formeln zur trigonometrischen Interpolation I, Z. Angew. Math. Phys. (ZAMP), 35 (1984):

Coefficients that depend only on $m$ can be canceled out.

Here, "a)" corresponds to "Chebyshev points of the first kind", "c)" to "Chebyshev points of the second kind", while "b1)" and "b2)" correspond to "Chebyshev points of the third kind" and "Chebyshev points of the fourth kind".

It might be worth considering alternative names for these point distributions (e.g. "Circle projection" for "Chebyshev points of the second kind", which is already implemented).

[pasabanov]

I found that the extrema points of the Chebyshev polynomials are called "Chebyshev nodes of the second kind" in the Chebyshev nodes Wikipedia article.
However, I couldn't find any mention of "Chebyshev nodes of the third kind" or "Chebyshev nodes of the fourth kind".

I wrote a Python script to generate the images of the point distributions and their corresponding points on the circle.

Code (python)

import matplotlib.pyplot as plt
import numpy as np


def plot_circle_projection(xx):
	plt.figure()
	plt.xlim(-1.15, 1.15)
	plt.ylim(-0.1, 1.1)
	plt.gca().xaxis.set_major_locator(plt.MultipleLocator(0.2))
	plt.gca().set_aspect('equal')
	plt.tight_layout(pad=0.5)

	circle_x = np.linspace(-1, 1, 10000)
	circle_y = np.sqrt(1 - circle_x**2)
	plt.plot(circle_x, circle_y, 'grey')

	plt.axhline(y=0, color='grey')

	for x in xx:
		y = np.sqrt(1 - x*x)
		plt.annotate('', xy=(x, 0), xytext=(x, y), arrowprops=dict(arrowstyle='-|>', color='black', linewidth=2, mutation_scale=15))
		plt.plot(x, y, 'bo')
		plt.plot(x, 0, 'ro')

	plt.show()


def main():
	n = 6
	plot_circle_projection(np.cos(np.pi * ((2*np.linspace(0, n - 1, n) + 1) / (2*n))))
	plot_circle_projection(np.cos(np.pi * (np.linspace(0, n - 1, n) / (n - 1))))
	plot_circle_projection(np.cos(np.pi * ((2*np.linspace(0, n - 1, n) + 1) / (2*n - 1))))
	plot_circle_projection(np.cos(np.pi * (2*np.linspace(0, n - 1, n) / (2*n - 1))))


if __name__ == '__main__':
	main()

"Chebyshev nodes of the first kind" (aka "Chebyshev nodes")	"Chebyshev nodes of the second kind" (aka "Circle projection")
"Chebyshev nodes of the fourth kind"? (aka "Circle projection without last node")	"Chebyshev nodes of the third kind"? (aka "Circle projection without first node")

Note

The third ("Circle projection without last node") is "Chebyshev nodes of the fourth kind", and the fourth ("Circle projection without first node") is "Chebyshev nodes of the third kind"

[pasabanov]

An additional Python script that shows all four distributions on the same plot.

Code (python)

import matplotlib.pyplot as plt
from matplotlib.lines import Line2D
import numpy as np


def plot_circle_projection(*datasets):
	plt.figure()
	plt.xlim(-1.15, 1.15)
	plt.ylim(-0.1, 1.1)
	plt.gca().xaxis.set_major_locator(plt.MultipleLocator(0.2))
	plt.gca().set_aspect('equal')
	plt.tight_layout(pad=0.5)

	circle_x = np.linspace(-1, 1, 10000)
	circle_y = np.sqrt(1 - circle_x**2)
	plt.plot(circle_x, circle_y, 'grey')

	plt.axhline(y=0, color='grey')

	colors = ['red', 'blue', 'green', 'purple']
	legend_handles = []

	for i, (label, xx) in enumerate(datasets):
		legend_handles.append(Line2D([], [], marker='o', color='w', markerfacecolor=colors[i%len(colors)], markersize=8, label=label))
		for x in xx:
			y = np.sqrt(1 - x*x)
			plt.annotate('', xy=(x, 0), xytext=(x, y), arrowprops=dict(arrowstyle='-|>', color='black', linewidth=2, mutation_scale=15))
			plt.plot(x, y, marker='o', color=colors[i%len(colors)])
			plt.plot(x, 0, marker='o', color=colors[i%len(colors)])

	plt.legend(handles=legend_handles, loc='center')
	plt.show()


def main():
	n = 6
	plot_circle_projection(
		('Chebyshev', np.cos(np.pi * ((2*np.linspace(0, n - 1, n) + 1) / (2*n)))),
		('Circle projection', np.cos(np.pi * (np.linspace(0, n - 1, n) / (n - 1)))),
		('Circle proj without last', np.cos(np.pi * ((2*np.linspace(0, n - 1, n) + 1) / (2*n - 1)))),
		('Circle proj without first', np.cos(np.pi * (2*np.linspace(0, n - 1, n) / (2*n - 1))))
	)


if __name__ == '__main__':
	main()

[pasabanov]

I decided to call the distribution with the first point on the left end and the last point not on the right end Chebyshev nodes of the third kind, because these nodes are the roots of the polynomial, that can be derived from the Chebyshev polynomial of the third kind:

$P_{3}\left(n,x\right)=T\left(n,x\right)+T\left(n-1,x\right)$

$P_{3}\left(n,x\right)=\left(x+1\right)V\left(n-1,x\right)$

Similarly, the distribution with the first point not on the left end and the last point on the right end is called Chebyshev nodes of the fourth kind. The corresponding polynomial:

$P_{4}\left(n,x\right)=T\left(n,x\right)-T\left(n-1,x\right)$

$P_{4}\left(n,x\right)=\left(x-1\right)W\left(n-1,x\right)$

More formulas and information can be found on that Desmos graph: https://www.desmos.com/calculator/cllkue8ztz.

The barycentric formula, the formulas for the point distributions and the corresponding barycentric weights are described here: https://alfi-lib.github.io/en/docs/barycentric-formula.

[pasabanov]

I decided to perform renaming:

• circle_proj $\rightarrow$ chebyshev_2
• circle_proj_no_last $\rightarrow$ chebyshev_3
• circle_proj_no_first $\rightarrow$ chebyshev_4