Skip to main content

Optimal Interpolation Nodes

Project description

Optimal Interpolation Nodes

Computes a set of points with an optimal Lebesgue constant. Having an exact analytical solution for these points is an unresolved problem in mathematics. The code here approximates the values numerically. Numerical approximations have been available for many years, but to my knowledge, there are no other open source Python libraries with this functionality.

Usage

Installation

pip install optinterp

Example

import optinterp

nds = optinterp.nodes(10)

This functions similarly to numpy's chebpts1 but produces points with a slightly improved Lebesgue constant:

import numpy as np

nds = np.polynomial.chebyshev.chebpts1(10)
nds = nds / nds[-1]

Algorithm Description

This solution expoits the following properties:

  • Optimal interpolation points can take values -1 and 1 for their minimum and maximum.
  • To mimimize the global maximum of the Lebesgue function, all local maxima should be equal.
  • Moving two adjacent nodes closer together reduces the local maximum of the Lebesgue function at the expense of increasing the other local maxima.

Start with two initial guesses for optimal points. The extended Chebyshev nodes and a set of slightly perturbed Chebyshev nodes. Then for each set of nodes define:

dx_i = x_{i+1} - x_i
dL_i = L_i - L_{avg}

Where L_i is the local maximum of the Lebesgue function between x_{i+1} and x_i. Now assuming each dL_i is a function of dx_i, use the Secant method to find roots:

dx_{i, n+1} = dx_{i, n} - dL_{i, n} * (dx_{i, n} - dx_{i, n-1}) / (dL_{i, n} - dL_{i, n - 1})

For the next iteration, calculate each node x_i from these roots of dx_i and scale the values to be from -1 to 1.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

optinterp-0.1.0.tar.gz (6.0 kB view details)

Uploaded Source

Built Distribution

optinterp-0.1.0-py3-none-any.whl (6.2 kB view details)

Uploaded Python 3

File details

Details for the file optinterp-0.1.0.tar.gz.

File metadata

  • Download URL: optinterp-0.1.0.tar.gz
  • Upload date:
  • Size: 6.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.1 importlib_metadata/3.10.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.59.0 CPython/3.7.10

File hashes

Hashes for optinterp-0.1.0.tar.gz
Algorithm Hash digest
SHA256 13c43deb26ce260d1dd07783d02febedfad098b5f9046598c04cfb55c2c845f4
MD5 7e4d97bcf4df0f6d21a1ce2494d67e08
BLAKE2b-256 275e399ecfd8752d4a978b4fb0576ef8033ef4530ed9b97d8eecd809563ceb26

See more details on using hashes here.

File details

Details for the file optinterp-0.1.0-py3-none-any.whl.

File metadata

  • Download URL: optinterp-0.1.0-py3-none-any.whl
  • Upload date:
  • Size: 6.2 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.1 importlib_metadata/3.10.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.59.0 CPython/3.7.10

File hashes

Hashes for optinterp-0.1.0-py3-none-any.whl
Algorithm Hash digest
SHA256 b82d7cd8b136ec6c6a92f7768b9c91b509dd332a7e8f50140c4281f8ccea436a
MD5 d0584a5e06a025f2ed30f1e88584680e
BLAKE2b-256 2bd4cdd8dccdba6b915f296f041542c04f2cbc59ea76b20f6fc76da4ae9b27d0

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page