Погрешность интерполяции сплайнами и оптимальная сетка

[oliva]

Всем привет!
Вопрос к тем, кто изучал погрешность сплайн-интерполяции. Известно, что оценить ее сверху можно с использованием производных высших степеней интерполируемой функции. Используя эти сведения я попытался состряпать алгоритм формирования оптимальной сетки измерений. Но вскоре понял, что такой подход - тупик, поскольку производные (тем более высоких степеней) известны мне с погрешностью ~ +- 100% .
Решил попробовать моделировать процедуру интерполяции для типовой (средне-обычной) функции и подбирать сетку таким образом, чтоб погрешность не превысила допустимой. Тут своии проблемы, связанные с взаимным влиянием интервалов. Т.е. при изменении шага измерения на одном из интервалов, меняется погрешность на другом и наоборот.
В принципе, очень грубо, тут можно прикинуть в каких точках мерять, но слишком халтурно и "на глаз".
Если кто-нибудь занимался подобной деятельностью, посоветуйте, пожалуйста, более-менее обоснованный способ расчета оптимальной сетки измерений.
Заранее благодарен.

[worm2]

oliva писал(а):

Вопрос к тем, кто изучал погрешность сплайн-интерполяции. Известно, что оценить ее сверху можно с использованием производных высших степеней интерполируемой функции.

Что значит "высших степеней"? 3-я это высшая или как?
Для сплайн-интерполяции погрешность зависит от порядка сплайна, но не от количества точек. Например, для кубического сплайна на равномерной сетке:

$$|R_n(x)| \leqslant \frac{5}{2} h^3 \max\limits_{y \in [a, b]} |f^{(3)}(y)|$$

, где h --- шаг сетки.
Вас такая погрешность не устраивает?

Может быть, вы имеете в виду полиномиальную интерполяцию (единым многочленом на всём отрезке) ?.

Добавлено спустя 2 минуты 49 секунд:

Или у Вас нет вообще никаких оценок для максимума модуля третьей производной?

[oliva]

worm2 писал(а):

для кубического сплайна на равномерной сетке:

$$|R_n(x)| \leqslant \frac{5}{2} h^3 \max\limits_{y \in [a, b]} |f^{(3)}(y)|$$

, где h --- шаг сетки.

Вообще-то у меня другая формула для погрешности кубического сплайна. Но спорить не буду. Я так понял, что эта погрешность определяется свойствами (прерывностью, дифференциируемостью и т.п.) функции f.

worm2 писал(а):

Или у Вас нет вообще никаких оценок для максимума модуля третьей производной?

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

Добавлено спустя 3 минуты 28 секунд:

worm2 писал(а):

погрешность зависит от порядка сплайна, но не от количества точек. Например, для кубического сплайна на равномерной сетке:

$$|R_n(x)| \leqslant \frac{5}{2} h^3 \max\limits_{y \in [a, b]} |f^{(3)}(y)|$$

, где h --- шаг

Шаг и количество точек я рассматриваю как взаимоопределяющие факторы.

[olga_helga]

Стоп, я так понимаю что по сути это все дело сводится к нахождению новой таблицы значений, по которой будет построен более точный сплайн.Так?

Добавлено спустя 4 минуты 17 секунд:

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

\[ y_i \]

сведением какой либо зависимости м/у

\[ x_i \]

и

\[ y_i \]

к линейной

[oliva]

olga_helga писал(а):

Стоп, я так понимаю что по сути это все дело сводится к нахождению новой таблицы значений, по которой будет построен более точный сплайн.Так?

Речь идет об интерполяции данных, полученных в процессе градуировки датчиков (в данном случае температуры). Характеристика этих датчиков в рабочем диапазоне меняется от почти линейной до сильно нелинейной. Нужно составить оптимальную сетку измерений, которая гарантирует нужную точность интерполяции при минимальном количестве измерений.
Для этого я взял типовую характеристику и пытаюсь ее исследовать.

[olga_helga]

Вооо!!!!
Тык вот, для зглаживания экспериментальных данных используют апроксимацию.
Используя старую таблицу данных

\[ \left( {x_i ,y_i } \right) \]

, получают новую

\[ \left( {x_i ,\overline {y_i } } \right) \]

, где

\[ {\overline {y_i } } \]

-сглаженное значение.
Так вот коим образом получают новую таблицу.
1)если зависимость линейная, то

\[ \overline {y_i } = \frac{{y_{i - 1} + y_i + y_{i + 1} }} {3} \]

2)если зависимость степенная

\[ y = ae^{bx} \]

,

\[ \ln y = \ln a + b\ln x \]

,то вводя замену переменных

\[ \xi = \ln y,\eta = \ln x,a_0 = \ln a,a_1 = b \]

, получаем

\[ \xi = a_0 + a_1 \eta \]

,а

\[ \left( {\ln x_i ,\ln y_i } \right) \]

-новый узел таблицы
3)если зависимость

\[ y = \frac{a} {{b + x}} \]

, то замена

\[ \xi = yb,\eta = yx \]

,

\[ \xi = a - \eta \]

-линейная зависимость, а

\[ \left( {x_i \cdot y_i ,y_i } \right) \]

-новая таблица.
Ну вот что-то вроде етого.

[oliva]

olga_helga писал(а):

для зглаживания экспериментальных данных используют апроксимацию.

Да не нужно данные сглаживать Аппроксимацию со сглаживанием применяют когда данные получены с погрешностью и им не доверяют.
Я решаю задачу интерполяции и измеренным точкам доверяю больше чем каким-либо расчетным. Интерполяция - нахождение кривой, которая ПРОХОДИТ через экспериментальные точки.

[olga_helga]

Да я вкурсе че такое интерполяция!
Помоему есть такая оценка погрешности интерполяции

\[ \left| {f(x) - L_n (x)} \right| \leqslant \frac{{\mathop {\max }\limits_{x \in [a,b]} }} {{(n + 1)!}}\left| {\prod\limits_{i = 0}^n {(x - xi)} } \right| \]

, где

\[ {xi} \]

-узлы интерполяции.Есть оценка многочленом Чебышева.Т.е. строится многочлен степени

\[ n + 1 \]

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

\[ T_n (x) = \cos (arc\cos x) \]

,

\[ T_{n + 1} (x) = 2xT_n (x) - T_{n - 1} (x) \]

.

\[ \begin{gathered} T_0 (x) = 1, \hfill \\ T_1 (x) = x, \hfill \\ T_2 (x) = 2x^2 - 1, \hfill \\ T_3 (x) = 4x^3 - 3x, \hfill \\ T_4 (x) = 8x^4 - 8x^2 + 1, \hfill \\ T_5 (x) = 16x^5 - 20x^3 + 5x,... \hfill \\ \end{gathered} \]

[worm2]

Правильно ли я понял задачу:

По известной функции f(x) на отрезке [a, b] найти минимальное число точек интерполяции на этом отрезке и построить сплайн на них, который гарантировал бы заданную погрешность определения f(x).

Интересная задача. Можно попробовать решать тупым перебором на компьютере с каким-то шагом.

Добавлено спустя 2 минуты 37 секунд:

Я понимаю, что Ваша задача намного сложнее, но с этой упрощённой формулировки можно было бы начать.

[olga_helga]

Многочлен имеет n действительных корней,выражаемых формулой

\[ x_i = \cos \frac{{(2i + 1)\pi }} {{2n}},i = 0,1,...,n - 1 \]

Добавлено спустя 3 минуты 14 секунд:

В роде есть еще формулка для

\[ x_i^{} \in [a,b] \]

,что то типа что узлы интерполяции выбираются как

\[ x_i = \frac{1} {2}\left( {(b - a)\cos \frac{{(2i + 1)\pi }} {{2n + 2}} + b + a} \right),i = 0,1,...,n \]

.Воть.Помогло?

[Brukvalub]

olga_helga писал(а):

Помоему есть такая оценка погрешности интерполяции

\[ \left| {f(x) - L_n (x)} \right| \leqslant \frac{{\mathop {\max }\limits_{x \in [a,b]} }} {{(n + 1)!}}\left| {\prod\limits_{i = 0}^n {(x - xi)} } \right| \]

Это неверная оценка. Необходимо еще потребовать существование

\[f^{(n + 1)} (x)\]

и умножить правую часть на

\[\left| {f^{(n + 1)} (\xi )} \right|\]

[olga_helga]

Извиняюсь!Я ошибочку сделала!
В оригинале оценка для интерполирования n+1 раз непрерывно дифференцируемой ф-ции на отрезке [a,b] ф-ции f(x) многочленом Логранжа такая:

\[ \left| {f(x) - L_n (x)} \right| \leqslant \frac{{\mathop {\max \left| {f^{(n + 1)} (x)} \right|}\limits_{x \in [a,b]} }} {{(n + 1)!}}\left| {\prod\limits_{i = 0}^n {(x - x_i )} } \right| \]

.Вроде так.

[Brukvalub]

Теперь - так.

[olga_helga]

Попробуйте последней из написанных формул воспользоваться.

[oliva]

olga_helga писал(а):

Попробуйте последней из написанных формул воспользоваться.

Я ж начал с того, что не могу с достаточной точностью знать производную выше первой степени, а в Вашей формуле присутствует производная степени (n+1).

Что-же касается полиномов Чебышева - не все понял, но интересно. Сообщите пожалуйста источник, чтоб я вник.

Добавлено спустя 5 минут 24 секунды:

worm2 писал(а):

Можно попробовать решать тупым перебором на компьютере с каким-то шагом.

Над этим и "пыхтю"
Проблема в том, что интервал измерения переменный и влияет на соседние. Т.е. при попытке подобрать один интервал (если подходить строго) нужно пересчитывать остальные, что усложняет, запутывает и ставит под сомнение результативность алгоритма.