интерполяционный полином Ньютона n-й степени, нужно написать в Delphi Опции

[Mystical]

Здравствуйте все!
Вобщем сразу к делу. Есть такая задачка:
Функция задана таблично (n +1 значение). Разработайте программу, строящую интерполяционный полином Ньютона n-й степени.
Вроде что-то нарыл в нете, но не то. Помогите плиз кто может.

[klik1602]

я не понимаю((( что у меня должно получиться на выходе??
и ещё...вы можете закомментить вот эти функции??

function Prod(t: double; k: integer): double;  // t(t-1)...(t-k)
begin
  if k=0 then Prod:=t else Prod:=t*Prod(t-1,k-1)
end;


function FinDif(k,i: integer): double;   // finite difference
begin
  if k=0 then FinDif:=y[i] else FinDif:=FinDif(k-1,i+1)-FinDif(k-1,i)
end;


function NewtonPol(x: double): double;
var
  k: integer;
  p,t,f: double;
begin
  p:=y[0];
  t:=(x-x0)/h;
  f:=1;
  for k:=1 to n do begin
    f:=f*k;
    p:=p+Prod(t,k-1)*FinDif(k,0)/f
  end;
  NewtonPol:=p
end;

[Lapp]

я не понимаю((( что у меня должно получиться на выходе??

Как что? значение интерполяционного полинома. Если вызвать NewtonPol с параметром x, то вернется значение полинома в точке x. Я не вполне уверен, представляют ли какой-то интерес его коэффициенты, поскольку они стоят перед степенями конечных разностей порядков до n. Так что я беру назад свои слова выше и предлагаю считать конечным продуктом саму программу )).

и ещё...вы можете закомментить вот эти функции??

_Закомментить_ - не рекомендую, работать не будет. А _прокомментить_ - можно.. ))

Собственно, я особо не разбираюсь в интерполировании. Просто делал тупо по формулам, а формулы взял в Википедии.

function Prod(t: double; k: integer): double;  // t(t-1)...(t-k)
begin
  if k=0 then Prod:=t else Prod:=t*Prod(t-1,k-1)
end;

Тут просто произведение - то есть то, что написано в оригинальном комменте. Чтоб в этом убедиться, заметь, что она просто умножает сама себя k раз, а при вызове мы каждый раз уменьшаем ее на 1.

function FinDif(k,i: integer): double;   // finite difference
begin
  if k=0 then FinDif:=y[i] else FinDif:=FinDif(k-1,i+1)-FinDif(k-1,i)
end;

Тут просто по определению конечных разностей, см. вики

Далее все один в один (если я не ошибся, конечно - я все ждал, что dark_san проверит, но она исчезла) по формулам. Я использовал прямую интерполяционную формулу Ньютона вот отсюда. Функция Prod (англ. product - произведение) вычисляет числитель дроби, знаменатель (фаеториал) считается по ходу дела (переменная f), а функция FinDif (англ. Finite Difference) считает конечные разности. Сумма находится в цикле. Вот и все, вроде..

function NewtonPol(x: double): double;
var
  k: integer;
  p,t,f: double;
begin
  p:=y[0];
  t:=(x-x0)/h;
  f:=1;
  for k:=1 to n do begin
    f:=f*k;
    p:=p+Prod(t,k-1)*FinDif(k,0)/f
  end;
  NewtonPol:=p
end;

Добавлено через 1 мин.

в этом алгоритме n-ая конечная разность ищется за O(2^n), что просто отвратительно.

А что ж ты замолчал?.. Расскажи даме, как делать быстрее )).