Список постов с меткой "линейная интерполяция"

Полтора дня разбирался в работе B-сплайна и как это применяется на практике. Хочу поделиться с вами результатами моих изысканий.

Немного теории

Допустим, у вас есть некий массив точек размером . Что вам потребуется для работы B-сплайна:

• определить количество интерполируемых точек (от этого зависит скорость работы, гладкость получившейся кривой и размер формулы для вычисления, количество точек равно )
• избавится от рекурсии формулы для вычисления

Общая формула для расчета коэффициентов:

   

Формула рекурсивная и заканчивается на равном единице:

*** QuickLaTeX cannot compile formula:
\begin{equation*}
  N_{i,1}(x)=\left{\begin{array}{cr}1&\text{if }t_i\leq x\textless t_{i+1}\0&\mathrm{otherwise}\quad\end{array}\right.\end{equation*}

*** Error message:
Missing delimiter (. inserted).
leading text:   N_{i,1}(x)=\left{

Пояснения к формуле:

• если делитель получается равным или близким по значению к нулю, значит вся дробь равна нулю
• параметр — это индекс текущей точки
• — значение от до с нужным вам шагом (например, равно 7, и нам нужно создать 3 точки для интерполяции, значит берем равным 7.0, 7.5, 8.0)
• — неубывающий массив индексов

Вычисление элементов массива :

*** QuickLaTeX cannot compile formula:
\begin{equation<em>}
  t=\left{\begin{array}{ll}0,&\mathrm{if}\ i<k\i-k+1,&\mathrm{if}\ k\leq{i}\leq{n}\n-k+2,&\mathrm{if}\ i>n\end{array}\right.
\end{equation</em>}

*** Error message:
Environment equation<em> undefined.
leading text: \begin{equation<em>}

Практика

Мне нужно было интерполировать по четырем точкам, поэтому я заранее на бумажке вычислил формулу без рекурсии:

*** QuickLaTeX cannot compile formula:
\begin{equation<em>}
  N_{i,3}(x)=\left{\begin{array}{ll}0,&\mathrm{if}\ x\textless t_{i}\\frac{x-t_i}{t_{i+2}-t_i}</em>\frac{x-ti}{t_{i+1}-ti},&\mathrm{if}\ t_i\leq x\textless t_{i+1}\\frac{x-ti}{t_{i+2}-ti}<em>\frac{t_{i+2}-x}{t_{i+2}-t_{i+1}}+\frac{t_{i+3}-x}{t_{i+3}-t_{i+1}}</em>\frac{x-ti}{t_{i+2}-t_{i+1}},&\mathrm{if}\ t_{i+1}\leq x\textless t_{i+2}\\frac{t_{i+3}-x}{t_{i+3}-t_{i+1}}<em>\frac{t_{i+3}-x}{t_{i+3}-t_{i+2}},&\mathrm{if}\ t_{i+2}\leq x\textless t_{i+3}\0,&\mathrm{if}\ x\geq t_{i+3}\end{array}\right.
\end{equation</em>}

*** Error message:
Environment equation<em> undefined.
leading text: \begin{equation<em>}

Про бумажку я, конечно, соврал, мне было удобнее сделать функцию на питоне вот такого вида:

def div(a, b):
    try:
        return a / float(b)
    except ZeroDivisionError:
        return 0

def N(i, k, x, t):
    if 1 == k:
        if t[i] <= x < t[i + 1]:
            return 1.0
        return 0.0
    a = div(x - t[i], t[i + k - 1] - t[i]) * N(i, k - 1, x, t)
    b = div(t[i + k] - x, x[i + k] - x[i + 1]) * N(i + 1, k - 1, x, t)
    return a + b

После этого добавил условие и все возможные возвращаемые значения в зависимости от , затем условие , значения которого зависят от . Может вам будет удобнее все это сделать на бумажке.

Наконец можно приступать к интерполяции. Формула такая:

*** QuickLaTeX cannot compile formula:
\begin{equation<em>}
  \sum\limits_{i}^{i+k}=\vec{p_{i}}N_{i,k}(x)
\end{equation</em>}

*** Error message:
Environment equation<em> undefined.
leading text: \begin{equation<em>}

Если индекс точки меньше нуля, берем нулевую точку, если индекс точки больше размера массива, то берем последнюю точку в массиве.

Небольшой пример

У нас есть некий массив точек, нам надо интерполировать с пятой по шестую точки с шагом 0.25, при этом равно 3 (значит для интерполяции нужно взять четыре точки).

*** QuickLaTeX cannot compile formula:

\begin{equation<em>}
  p_0=p_5</em>N_{0,3}(0.0)+p_6<em>N_{1,3}(0.0)+p_7</em>N_{2,3}(0.0)+p_8<em>N_{3,3}(0.0)
\end{equation</em>}

*** Error message:
Environment equation<em> undefined.
leading text: \begin{equation<em>}

*** QuickLaTeX cannot compile formula:

\begin{equation<em>}
  p_1=p_5</em>N_{0,3}(0.25)+p_6<em>N_{1,3}(0.25)+p_7</em>N_{2,3}(0.25)+p_8<em>N_{3,3}(0.25)
\end{equation</em>}

*** Error message:
Environment equation<em> undefined.
leading text: \begin{equation<em>}

*** QuickLaTeX cannot compile formula:

\begin{equation<em>}
  p_2=p_5</em>N_{0,3}(0.5)+p_6<em>N_{1,3}(0.5)+p_7</em>N_{2,3}(0.5)+p_8<em>N_{3,3}(0.5)
\end{equation</em>}

*** Error message:
Environment equation<em> undefined.
leading text: \begin{equation<em>}

*** QuickLaTeX cannot compile formula:

\begin{equation<em>}
  p_3=p_5</em>N_{0,3}(1.0)+p_6<em>N_{1,3}(1.0)+p_7</em>N_{2,3}(1.0)+p_8<em>N_{3,3}(1.0)
\end{equation</em>}

*** Error message:
Environment equation<em> undefined.
leading text: \begin{equation<em>}

Итого четыре новых точки вместо двух.

Спасибо за внимание, надеюсь нигде не ошибся. На несложные вопросы по теме могу ответить в комментариях.