АЛГОРИТМЫ

Новости

Рассылка новостей

Форум

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. Обычно с ростом числа точек начинают накапливаться вычислительные погрешности, но при указанном расположении погрешности нейтрализуют друг друга.

Если нашли ошибку в алгоритме - сообщите!


Реализации алгоритма на различных языках:

Реализация алгоритма на C++
Реализация алгоритма на Delphi
Реализация алгоритма на Visual Basic 6

Блоксхемы:

Посмотреть блок-схему алгоритма
Скачать блок-схему алгоритма

Реализация алгоритма на 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.

 


Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU