Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ интерполяционный полином Ньютона n-й степени

Автор: Mystical 31.05.2009 7:23

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


Автор: Ozzя 31.05.2009 12:31

http://algolist.manual.ru/maths/approx.php

Автор: Mystical 31.05.2009 19:27

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

Автор: volvo 31.05.2009 20:04

Цитата
думаю я не из тех кто зная математическую часть смржет без труда сделать программную часть
А я думаю - ты из тех, кто пальцем не пошевелит, а будет сидеть и ждать, пока не придет добрый дядя и не выложит здесь решение полностью, от начала до конца, проверенное, отлаженное, только приходи, Mystical, копируй, и сдавай... Попробуй меня разубедить в этом (а разубедить меня можно только показав свои наработки по теме, пусть неправильные, пусть корявые, но свои. Чтоб тебе помогать, надо видеть, как ты сам ХОЧЕШЬ что-то сделать, и прилагаешь к этому усилия. Иначе - без твоих попыток - это никому не надо...)

Автор: klik1602 15.06.2011 23:17

оуу)) а меня точно такая же задача, Функция задана таблично (n +1 значение). Разработайте программу, строящую интерполяционный полином Ньютона n-й степени. видимо в одном месте с человеком учимся, но я хотела бы разобраться в ней, не совсем понятны условия
1. Функция задана таблично (n +1 значение) - функцию мы задаём самостоятельно любую?? к примеру f(x) = n+1, то в таблице у нас будет 2 строки = x и f(x) в которое соответственно по данному примеру будут записаны x=1 f(x)=2, x=2 f(x)=3, x=3 f(x)=4 ...x=n f(x)=n+1, x=n+1 f(x)=n+2
2. далее мы задаём я так понимаю степень интерполяционного полинома
3. а вот далее не понимаю что делать((

и построить - это значит функцию рисовать??

Автор: klik1602 16.06.2011 3:28

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

Автор: Lapp 16.06.2011 3:54

Цитата(klik1602 @ 15.06.2011 20:17) *
и построить - это значит функцию рисовать??

Нет, это значит привести набор коэффициентов полинома.

Автор: Lapp 16.06.2011 5:12

Поиск по семплу
+полин* +Ньют*
дает, в частности, вот такую тему: http://forum.pascal.net.ru/index.php?showtopic=25679

Автор: klik1602 16.06.2011 5:36

уух)) а вы ,ребята, с юмором)) меня препод думаю есть не станет, если я чуть попозже принесу ему лабу) а пока что-то на сонную голову вникнуть не могу, с утра посмотрю что к чему

паасссиб)) что не прошли мимо)

Автор: klik1602 19.06.2011 2:57

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

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;

Автор: klik1602 20.06.2011 19:44

хммм, полиномы это точно не моё..

Автор: TarasBer 20.06.2011 19:59

Объяснить, что делают эти функции? Это называется рекурсия.

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

Автор: klik1602 20.06.2011 21:55

как это называется я-то знаю) но что они делают в этом примере я не понимаю)

Автор: Lapp 21.06.2011 9:38

Цитата(klik1602 @ 18.06.2011 23:57) *
я не понимаю((( что у меня должно получиться на выходе??
Как что? значение интерполяционного полинома. Если вызвать 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;
Тут просто по определению конечных разностей, см. http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B5_%D1%80%D0%B0%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8

Далее все один в один (если я не ошибся, конечно - я все ждал, что dark_san проверит, но она исчезла) по формулам. Я использовал прямую интерполяционную формулу Ньютона вот http://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0. Функция 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 мин.
Цитата(TarasBer @ 20.06.2011 16:59) *
в этом алгоритме n-ая конечная разность ищется за O(2^n), что просто отвратительно.
А что ж ты замолчал?.. Расскажи даме, как делать быстрее )).

Автор: TarasBer 21.06.2011 13:19

> Расскажи даме, как делать быстрее )).

Надо сначала высчитать все конечные разности 1-го порядка, потом, используя их, вычислить конечные разности 2-го порядка, потом, используя их, третьего и так далее до эн.

Автор: klik1602 23.06.2011 1:38

ага..кажется что-то начинаю понимать.. yes2.gif