Интерполяция с использованием динамического программирования

У меня проблемы с выполнением домашнего задания.

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

  1. Пусть P[i,j] будет полиномиальной интерполяцией точек (xi, yi),..., (xj, yj). Найдите 3 простых многочлена q(x), r(x), s(x) степени 0 или 1, таких что:

    P[i,j+1]={q(x)P[i,j](x)-r(x)P[i+1,j+1](x)}/s(x)

  2. Имея точки (x1,y1),....(xn,yn), опишите эффективный алгоритм динамического программирования, основанный на рекуррентном соотношении, которое вы нашли в разделе 1 для вычисления коэффициентов a0,...an-1 полиномиальная интерполяция.

Что ж, я знаю, как решить проблему полиномиальной интерполяции с помощью многочлена Ньютона, который очень похож на приведенный выше. рекуррентное соотношение, но я не понимаю, как оно помогает мне найти q(x), r(x), s(x) степени 0 или 1, и если у меня есть правильное q(x), r(x), s(x) - как мне решить эту проблему с помощью динамического программирования?

Любая помощь будет высоко ценится.


interpolation algorithm polynomials dynamic-programming
person user3114639    schedule 16.06.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward 

q(x) = (x at {j+1}) - x
r(x) = (x at i) - x
s(x) = (x at {j+1}) - (x at i)

x at i или x at j означают их место в упорядоченном списке входных точек.

Некоторые пояснения:

Сначала нам нужно понять, что означает P[i,j](x).

Поместите все ваши исходные (x,y) пары на главную диагональ матрицы n x n. Теперь вы можете извлечь P[0,0](x) как значение y точки в вашей матрице в (0,0). P[0,1] — это линейная интерполяция точек вашей матрицы в точках (0,0) и (1,1). Это будет прямолинейная функция.

((x at 0 - x)(y at 1) - (x at 1 - x)(y at 0)) 
---------------------------------------------
              (x at 1 - x at 0)

P[0,2] — это линейная интерполяция двух предыдущих линейных интерполяций, что означает, что ваши ys теперь будут линейными функциями, которые вы вычислили на предыдущем шаге. Это также динамический алгоритм, который строит полный полином.

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

person Yaelet    schedule 04.06.2016
comment
Ссылки на рекомендуемую лекцию в ответе не работают. Вот обновленные, которые работают: clear.rice.edu/comp360/lectures /old/Lagra.pdf clear.rice.edu/ comp360/lectures/old/LagrangeText.pdf - person Sharonas Ykm; 08.06.2017