Re: Многочлены

From

Mikhail Kalenkov ()

To

Valentin Davydov

Date

2002-12-24T20:33:55Z

Area

RU.ALGORITHMS

From: "Mikhail Kalenkov" <kalenkov@rinet.ru>

Hello Valentin Davydov

> Задана табличная функция, довольно гладкая, в равноотстоящих узлах
> (узлов порядка тысячи). Хочется аппроксимировать её многочленом
> достаточно высокой степени, скажем, 15-20. Я пока сделал вот как:
> построил многочлены Лежандра прямо по формулам P(0,x)=1, P(1,x)=x,
> P(n+1,x)=((2*n+1)*x*P(n,x)-n*P(n-1,x))/(n+1), вычислил их значения
> в каждом узле (приведя последние к промежутку [-1,1], разумеется),
> затем методом прямоугольников проектирую заданные точки на эти
> многочлены и получаю таким образом коэффициенты.
А почему именно многочлены Лежандра, а не скажем многчлены Чебышева?
> Для повышения точности я, перед тем, как работать с очередным
многочленом,
> вычитаю из исходных данных все предыдущие с соответствующими (найденными
> на предыдущих шагах) коэффициентами. Однако после нескольких итераций
такие
> вычтенные данные явно содержат остатки низших степеней, причём в довольно
> странном количестве (порядка процента - для ошибок округления явно много,
> а для пропущенной в формуле двойки явно мало). Проверил ортогональность
> используемых многочленов (тем же способом прямоугольников) и увидел тот
> же самый процент в двух местах: во-первых, в отличие нормы многочлена от
> единицы, а во-вторых, в нормах произведений разных многочленов одной
> чётности.

> Насколько я понимаю, причина - в используемом мною способе
интегрирования.
> Вопрос, собственно, следующий: есть ли более простой способ "исправить"
> многочлены (или алгоритм интегрирования), чем тупая процедура
> ортонормирования?
Я не всё понял из твоего объяснения, но как мне показалось ты пытаешься
разложить свою функцию в ряд по полиномам Лежандра
f(x)=sum a_n P_n(x)
Причём при нахождении коэффициентов a_n тебе приходится вычислять интегралы
вида
\int f(x)P_n(x)dx
по формулам прямоугольников, которая не блещет точностью. Я прав? Если да,
то у меня есть, как мне кажется, хорошая идея. Есть у меня книжка, где
описаны ортогональные многочленны дискретного переменного. Это такие
полиномы, для которых соотношение ортонормированности на отрезке [0,N-1]
записывается в виде

\sum_{i=0}^{N-1} p(i) t_n(i) t_m(i) =\delta_{n,m} (дельта символ Кронекера)
p(i) -- весовая функция. В случае p(i)=1 эти многочлены называются
многочленами Чебышева, хотя и являются аналогами многочленов Лежандра
непрерывного переменного. Существуют явные и рекуррентные формулы для
ортогональных многочленов дискретного переменного. Преимущество таких
многочленов состоит в том, что соотношение ортогональности будет выполнятся
ТОЧНО. Я никогда раньше не использовал раньше многочлены дискретного
переменного, но мне кажется, что в этой задаче они довольно естественны.
Как тебе такая идея?

        Михаил Каленков.

PS А почему бы тебе не использовать метод наименьших квадратов? Обращение
матрицы с размерностью 15-20 не столь уж и ресурсоёмко. Причём на твоём
месте я бы использовал многочлены Чебышева (легче смотреть за погрешностью
приближения, да и вычислять их проще).


--- ifmail v.2.15dev5
 * Origin: Cronyx Plus ISP (2:5020/400)