Остаточный член полиномиальной аппроксимации

[B@R5uk]

Помогите, пожалуйста, решить такую задачу.

Функция $f(x)$ определена на отрезке $[a,b]$ и бесконечно непрерывно дифференцируема на нём. На этом отрезке выбирается $N$ различных точек $x_n$, в них вычисляются значения функции, соответственно, $f_n$. Через эти точки методом наименьших квадратов проводится аппроксимирующий полином степени $M\leqslant N-1$:

$$\varphi(x)=\sum\limits_{k=1}^M a_k x^k$$

где коэффициенты a_k известным образом выражаются через числа $x_n$ и $f_n$.

Рассмотрим теперь остаточный член для такой аппроксимации:

$$R(x)=f(x)-\varphi(x)$$

Хотелось бы получить для него простую для анализа формулу аналогичную остаточному члену ряда Тейлора в форме Лагранжа или Коши. Как к такой задаче вообще подступиться? Посоветуйте, пожалуйста, книгу/статью где такая или аналогичная уже разобраны.

[_Ivana]

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

[B@R5uk]

Да, оно на самом деле так и есть. Поэтому одна из целей решения этой задачи -- оценить какое оптимальное $M$ при фиксированном $N$ стоит взять, чтобы величина

$$\Delta=\max\limits_{x\in[a,b]} |R(x)|$$

была минимальна. Так же интересно, как $\Delta$ зависит от разности $b-a$ в случае равномерной сетки $x_n=a+\frac{(b-a)(n-1)}_{N-1}$. Логично, что она будет уменьшаться вместе с разностью, но пропорционально какой степени?

-- 10.05.2014, 17:07 --

Может быть не стоит сразу хвататься за общий случай, а попробовать что-нибудь придумать для остаточного члена аппроксимации на равномерной сетке?

[_Ivana]

Можно не ограничивать себя полиномами, как и поступают в большинстве случаев. Ладно, вы хотите полиномы - тогда можно подобрать оптимальную сетку, на которой будет все хорошо. Но вы хотите равномерную... Я бы для начала чисто из любопытства прогнал бы этот пример Рунге - аппроксимация полиномами по МНК на равномерной сетке и посмотрел графики зависимости дельты от $M$ для разного количества узлов.

[B@R5uk]

_Ivana в сообщении #861379 писал(а):

Ладно, вы хотите полиномы - тогда можно подобрать оптимальную сетку, на которой будет все хорошо.

Да, я только что наткнулся на очень интересный текст про это дело. К сожалению, там обсуждается только "жёсткая" интерполяция, то есть через $N+1$ точку на отрезке $[-1,1]$ проводится полином $N$ степени, оценивается погрешность, а затем эти точки подбираются так, чтобы погрешность была минимальна. Поскольку множество полиномов, из которого выбирается оптимальный экземпляр, является всего лишь подмножеством всех возможных полиномов степени $N+1$, то совершенно не очевидно, что получаемый полином является оптимальным на всём множестве полиномов (то есть нельзя подобрать лучший экземпляр). В статье про это ничего не говориться, хотя логично предположить, что приведённое там построение даёт наилучший из всех возможных полиномов.

Но это всё сильно в сторону. Моя цель заключается не в том, чтобы построить оптимальную аппроксимацию на отрезке, а в том, чтобы изучить характер поведения функции, вычислив минимум значений функции на этом отрезке. Я хочу к этому делу приспособить аппроксимацию полиномом (поскольку это очень простая задача). Однако, как оценить остаточный член этой аппроксимации (сделанной методом наименьших квадратов) я не знаю.

_Ivana в сообщении #861379 писал(а):

Я бы для начала чисто из любопытства прогнал бы этот пример Рунге - аппроксимация полиномами по МНК на равномерной сетке и посмотрел графики зависимости дельты от $M$ для разного количества узлов.

Да, это действительно интересно, я тоже об этом думал, только не придумал какой взять образец функции для экспериментов.

[_Ivana]

B@R5uk в сообщении #861401 писал(а):

Но это всё сильно в сторону. Моя цель заключается не в том, чтобы построить оптимальную аппроксимацию на отрезке, а в том, чтобы изучить характер поведения функции, вычислив минимум значений функции на этом отрезке. Я хочу к этому делу приспособить аппроксимацию полиномом (поскольку это очень простая задача).

Мои кустарные мысли первого впечатления: возьмите какую-то равномерную сетку, рассчитайте значения вашей функции на ней, проинтерполируйте (рекомендую сплайны, их 100500 видов можно придумать и у них нет проблем типа примера Рунге) или проаппроксимируйте чем хотите - получили некую функцию первого приближения $f_1$. Теперь сделайте сетку в 2 раза чаще (рассчитайте вашу функцию в серединах исходных узлов) и повторите процедуру для новой сетки - получите $f_2$. Проанализируйте отклонение $f_1 - f_2$, причем, не только в узлах новой сетки, а на сетке существенно почаще. В той области аргумента, где отклонения невелики, можно брать или $f_1$ или $f_2$, они все равно близки, но лучше $f_2$. В области аргументов, где различия существенны - еще раз учащайте в 2 раза сетку, и т.д., пока $f_k - f_{k+1}$ не станут достаточно малы. В итоге вы получите неравномерную сетку, более густую в области бОльших изменений вашей исходной функции, и результирующую аппроксимационную (интерполяционную) кривую на всем интервале. Правда, есть шанс при удвоении сетки "пропустить всплески в дырки" и в дальнейшем решить, что их нет...

[B@R5uk]

Помогите, пожалуйста, понять истинность следующего утверждения.

На декартовой плоскости $Oxy$ имеется $N$ точек $(x_1,y_1), (x_2,y_2), ... , (x_{N-1},y_{N-1}), (x_N,y_N)$, причём величины $x_k$ пронумерованы в порядке возрастания, и ни одна пара не имеет одинаковых значений. Через эти точки методом наименьших квадратов проводится полином $p(x)$ степени $M$, причём $M\leqslant N-1$. Так же, через эти точки проводится непрерывная кривая, однозначно проектируемая на ось $Ox$.

Утверждение заключается в том, что количество точек пересечения этой кривой и полинома $p(x)$, попадающих на отрезок $[x_1, x_N]$, не меньше, чем $M+1$.

В случае, когда $M=N-1$ утверждение очевидно, так как полином будет полиномом Лагранжа, построенным на заданных точках, и будет через них проходить. Количество точек равно $N=M+1$. В случае, когда полином является константой, то есть $M=0$, утверждение тоже очевидно, потому что если эта константа больше максимального из $y_k$ или меньше минимального, то она не может удовлетворять требованиям МНК. Следовательно константа меньше максимального и больше минимально $y_k$ и по крайней мере одно пересечение есть. А вот для общего случая как быть?

-- 12.05.2014, 13:53 --

На всякий случай. МНК подразумевает, что величина

$$W=\sum\limits_{k=1}^N \left(y_k-p(x_k)\right)^2$$

минимальная при варьировании коэффициентов $\{a_m\}$ полинома

$$p(x)=\sum\limits_{m=0}^M a_m x^m$$

При этом требуется, чтобы $M\leqslant N-1$, иначе значения ${a_m}$ не определяются однозначно.

[B@R5uk]

МНК проводит полином не через эти точки, а строит его по этим точкам. Через точки он проходить не обязан, но такое возможно в определённых случаях.