Подходящие многочлены к данным

Да, способ, которым это обычно делается, при помощи наименьших квадратов. Существуют другие способы определить, как хорошо аппроксимации полиномом, но теория является самой простой для наименьших квадратов. Общую теорию называют линейной регрессией.

Ваш лучший выбор состоит в том, чтобы, вероятно, запуститься с Числовые Рецепты .

, R свободен и сделает все, что Вы хотите и больше, но это имеет большую кривую обучения.

, Если у Вас есть доступ к Mathematica, можно использовать Пригодную функцию, чтобы сделать подбор методом наименьших квадратов. Я предполагаю, что Matlab и его Октава дубликата с открытым исходным кодом имеют подобную функцию.

Для (x, f (x)) случай:

import numpy

x = numpy.arange(10)
y = x**2

coeffs = numpy.polyfit(x, y, deg=2)
poly = numpy.poly1d(coeffs)
print poly
yp = numpy.polyval(poly, x)
print (yp-y)

Пустой в памяти, что многочлен более высокого градуса ВСЕГДА соответствует данным лучше. Многочлены более высокого градуса обычно приводят к очень невероятным функциям (см. Бритва Оккама ), хотя (сверхсоответствуя). Вы хотите найти баланс между простотой (степень многочлена) и соответствием (например, ошибка наименьшего квадрата). Количественно, существуют тесты для этого, информационный Критерий Akaike или байесовский информационный критерий . Эти тесты дают счет, какая модель должна быть предпочтена.

Lagrange многочлены (как @j w отправленный) дают Вам точное соответствие в точках, которые Вы определяете, но с многочленами градуса больше, чем говорят 5, или 6 можно столкнуться с числовой нестабильностью.

Наименьшие квадраты дает Вам "лучший пригодный" многочлен с ошибкой, определенной как сумма квадратов отдельных ошибок. (возьмите расстояние вдоль оси y между точками, которые Вы имеете и функция, которая заканчивается, придайте им квадратную форму и подведите итог их), функция MATLAB polyfit делает это, и с несколькими возвращаемыми аргументами, у Вас может быть он, автоматически заботятся о масштабировании/смещении проблем (например, если у Вас есть 100 точек все между x=312.1 и 312.3, и Вы хотите 6-й многочлен градуса, Вы собираетесь хотеть вычислить u = (x-312.2)/0.1, таким образом, u-значения распределяются между-1 и + =).

ПРИМЕЧАНИЕ , что результаты соответствий наименьших квадратов сильно под влиянием распределения значений оси X. Если x-значения будут равномерно распределены, то Вы получите большие ошибки в концах. Если у Вас будет случай, где Вы можете выбирать значения x, и Вы заботитесь о максимальном отклонении от Вашей известной функции и интерполяционного многочлена, то использование полиномы Чебышева дадут Вам что-то, что является близко к идеальному минимаксному многочлену (который очень трудно вычислить). Это обсуждено довольно долго в Числовых Рецептах.

Редактирование: Из того, что я собираюсь, это все работы хорошо для функций одной переменной. Для многомерных функций это, вероятно, будет намного более трудно, если градус будет больше, чем, скажем, 2. Я действительно находил ссылка на Google Books .

Если Вы хотите соответствовать (кси, f (xi)) к многочлену градуса n тогда, Вы настроили бы линейную проблему наименьших квадратов с данными (1, кси, кси, xi^2..., xi^n, f (xi)). Это возвратит ряд коэффициентов (c0, c1..., cn) так, чтобы многочлен оптимальной подгонки был *y = c0 + c1 * x + c2 * x^2 +... + cn * x^n.*

можно обобщить это два больше чем одна зависимая переменная включением полномочий y и комбинации x и y в проблеме.

Довольно легко вспугнуть быстрое использование соответствия матричные функции Excel, если Вы знаете, как представить проблему наименьших квадратов как проблему линейной алгебры. (Который зависит от того, как надежный Вы думаете, что Excel как решатель линейной алгебры.)

Помните, существует большая разница между приближение многочлен и нахождение точна один.

, Например, если я даю Вам 4 точки, Вы могли

1. , Приближаются, строка с методом как наименьшие квадраты
2. Приближаются, парабола с методом как наименьшие квадраты
3. Находят точный кубическая функция через эти четыре точки.

убедиться выбрать метод правильно для Вас!

лагранжев многочлен находится в некотором смысле "самый простой" интерполяционный многочлен, который соответствует данному набору точек данных.

Это иногда проблематично, потому что это может варьироваться дико между точками данных.

В колледже у нас была эта книга, которую я до сих пор нахожу чрезвычайно полезно: Конте, де Бур; элементарный численный анализ; Макроу Хилл. Соответствующий параграф - 6.2: Подбор данных.
Пример кода представлен на ФОРТРАНЕ, и листинги тоже не очень читабельны, но в то же время объяснения глубоки и ясны. в конечном итоге вы понимаете, что делаете, а не просто делаете это (как мой опыт работы с числовыми рецептами).
Обычно я начинаю с числовых рецептов, но для подобных вещей мне быстро приходится брать Конте-де Бура.

Может быть, лучше опубликовать какой-нибудь код ... он немного урезан, но самые важные части там есть. очевидно, он полагается на numpy!

def Tn(n, x):
  if n==0:
    return 1.0
  elif n==1:
    return float(x)
  else:
    return (2.0 * x * Tn(n - 1, x)) - Tn(n - 2, x)

class ChebyshevFit:

  def __init__(self):
    self.Tn = Memoize(Tn)

  def fit(self, data, degree=None):
    """fit the data by a 'minimal squares' linear combination of chebyshev polinomials.

    cfr: Conte, de Boor; elementary numerical analysis; Mc Grow Hill (6.2: Data Fitting)
    """

    if degree is None:
      degree = 5

    data = sorted(data)
    self.range = start, end = (min(data)[0], max(data)[0])
    self.halfwidth = (end - start) / 2.0
    vec_x = [(x - start - self.halfwidth)/self.halfwidth for (x, y) in data]
    vec_f = [y for (x, y) in data]

    mat_phi = [numpy.array([self.Tn(i, x) for x in vec_x]) for i in range(degree+1)]
    mat_A = numpy.inner(mat_phi, mat_phi)
    vec_b = numpy.inner(vec_f, mat_phi)

    self.coefficients = numpy.linalg.solve(mat_A, vec_b)
    self.degree = degree

  def evaluate(self, x):
    """use Clenshaw algorithm

    http://en.wikipedia.org/wiki/Clenshaw_algorithm
    """

    x = (x-self.range[0]-self.halfwidth) / self.halfwidth

    b_2 = float(self.coefficients[self.degree])
    b_1 = 2 * x * b_2 + float(self.coefficients[self.degree - 1])

    for i in range(2, self.degree):
      b_1, b_2 = 2.0 * x * b_1 + self.coefficients[self.degree - i] - b_2, b_1
    else:
      b_0 = x*b_1 + self.coefficients[0] - b_2

    return b_0