![]() |
![]() |
||||
![]() | |||||
![]() |
![]() АЛГОРИТМЫ Новости Рассылка новостей Форум AlgoPascal Редактор блок-схем Статьи О сайте Контакты |
![]() |
![]() Интерполяция по НьютонуПусть задано n+1 значение функции yi = y(xi ) в разных точках: x0 , x1 , ..., xn . Тогда интерполяционный многочлен степени n в форме Ньютона может быть построен по следующим формулам: где N0 (x) = 1,Ni (x) = (x-x0 )(x-x1 )...(x-xi-1 ) (i=1, ..., n), Ci = [x0 , x1 , ..., xi ], [xi ] = yi (i=0, .., n), [x0 , x1 , ..., xi ] = ([x1 , ..., xi ] - [x0 , ..., xi-1 ])/(xi - x0 ). Выражение [x0 , x1 , ..., xi ] называется разделенной разностью. Интервалы [xi , xi+1 ] могут быть неравными. Если точки x0 , .., xn заданы извне, то больше говорить не о чем. Если же у нас есть свобода выбора точек, в которых мы будем брать значение функции, то можно повысить точность интерполяции на определенном отрезке [a, b] за счет особого способа выбора точек. Если выбирать точки так, что они будут находиться в корнях полинома Чебышева n+1-ой степени, определенного на отрезке [a, b], то достигается минимальная возможная погрешность для данного числа точек на данном отрезке. Это расположение определяется следующими формулами: Такое расположение, помимо всего прочего, делает вычислительный процесс устойчивым при больших n. Обычно с ростом числа точек начинают накапливаться вычислительные погрешности, но при указанном расположении погрешности нейтрализуют друг друга. Если нашли ошибку в алгоритме - сообщите! Реализации алгоритма на различных языках:![]() ![]() ![]() Блоксхемы:![]() ![]() Реализация алгоритма на AlgoPascal:unit NewtonInterpolateUnit; interface NewtonInterpolate; implementation (* Интерполяция по Ньютону. function NewtonInterpolate(n:integer;x,y:array [0..n] of real;t:real):real; интерполирует функцию, принимающую в точках x[i] значение F[i]. Функция возвращает значение полинома в точке t. *) function NewtonInterpolate( const n : Integer; const x : array of Real; y : array of Real; t : Real):Real; var I : Integer; k : Integer; i1 : Integer; l : Real; s : Real; begin l:=y[0]; s:=1; for i:=n downto 1 do begin i1:=n-i; for k:=0 to i-1 do begin y[k]:=(y[k+1]-y[k])/(x[k+1+i1]-x[k]); end; s:=s*(t-x[i1]); l:=l+y[0]*s; end; Result:=l; end; end. |
![]() |
|
|
![]() |