АЛГОРИТМЫ

Новости

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

Форум

AlgoPascal

Редактор блок-схем

Статьи

О сайте

Контакты



Содержание - Интерполяция - Интерполяция по Ньютону

Интерполяция по Ньютону

Пусть задано n+1 значение функции y = y(x) в разных точках: x, x, ..., x. Тогда интерполяционный многочлен степени n в форме Ньютона может быть построен по следующим формулам:

где

N(x) = 1,
N(x) = (x-x)(x-x)...(x-xi-1 ) (i=1, ..., n),
C = [x, x, ..., x],
[x] = y (i=0, .., n),
[x, x, ..., x] = ([x, ..., x] - [x, ..., xi-1 ])/(x - x).

Выражение [x, x, ..., x] называется разделенной разностью. Интервалы [x, xi+1 ] могут быть неравными.

Если точки x, .., x заданы извне, то больше говорить не о чем. Если же у нас есть свобода выбора точек, в которых мы будем брать значение функции, то можно повысить точность интерполяции на определенном отрезке [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