Текст программы вычисления многочлена Ньютона

 

// method_N.cpp : main project file.

 

#include "stdafx.h"

#include<iostream>

#include<conio.h>

#include<cmath>

#include<iomanip>

#define max 20

 

using namespace System;

using namespace std;

void newton (double arg[][max],double x,int n, double e) /*объявление функции "ньютон", входные данные:двумерный массив значений "Х" и "Y", значение "Х", введенное с клавиатуры, количество узлов интерполяции, заданная погрешность*/

      

{

  double s,dX,q,h; //локальные переменные

  int k, flag;

  k=0;

  flag=0;

  h=arg[2][1]-arg[1][1];

  for(int i=0;i<n;i++)

  {

if(x==arg[i][1]) /*проверка равенства введенного значения аргумента "х" со значением из массива табличных аргументов "х[]" если равенство выполняется, в переменную flag записывается номер элемента массива табличных значений, равного введенному с клавиатуры "х"*/

                flag=i;

 

        dX=x-arg[i][1];

         

  if((dX<h)&&(dX>0)) //нахождение ближайшего узла интерполяции

        k=i;

  }

      

  if (flag==0) //если совпадений, введенного с клавиатуры значения, "х" с массивом табличных значений нет, вычисляются конечные разности

  {

      

        for(int j=3;j<=n+2;j++)

               for(int i=k;i<=n-j+2;i++)

                      arg[i][j]=arg[i+1][j-1]-arg[i][j-1]; /* вычисление конечных разностей. Конечные разности записываются в двумерный массив

                                                                                           начиная с третьего столбца*/

 

        q=(x-arg[k][1])/h;

        arg[0][0]=arg[1][0]=arg[max][max]=0;

            

        for(int m=1;m<=n-k;m++)

        {

               arg[0][0]=arg[k][2]; //инициализация первого слагаемого (y0) полинома

               for(int j=3;j<=m+2;j++) //вычисление слагаемых полинома

               {

               s=arg[k][j]; //переменной s присваивается значение dY порядка j

                          

               for(int i=1;i<=j-2;i++)

                             s=s*((q-i+1)/i);

                      arg[0][0]=arg[0][0]+s; //вычисление значения функции в заданной точке          

}

 

 

               arg[1][0]=s; //в элементе первой строки нулевого столбца записывается приблизительная погрешность интерполирования

               arg[max][max]=m; //в элемент последнего столбца нижней строки сохраняется порядок полинома

 

               if (fabs(s)<e) //если заданная точность интерполирования достигнута процесс вычисления завершается

                      break;

                          

        }

  }

  else

  {

        s=arg[flag][2];

  }

}                     //конец функции "ньютон"

 

int main()     //начало основной программы

 

{

   

  double arg[max][max],x,e;

float h;

int n;

cout<<"Enter quantity of figures N=";

cin>>n;           //ввод количества узлов интерполяции

cout<<endl;

cout<<"Enter value of argument X=";

cin>>x;           //ввод значения "х"

cout<<endl;

cout<<"Enter an interpolation error E=";

cin>>e;           //ввод заданной погрешности интерполяции

cout<<endl;

cout<<"Enter distance between knots h=";

cin>>h;           //ввод расстояния между узлами

cout<<endl;

 

  for (int i=0;i<=n;i++)

  {

        arg[i][1]=i*h; //заполнение массива табличных значений аргумента функции "x", аргументы функции заполняют первый столбец двумерного массива

        cout<<"Enter values of function Y"<<i<<"= ";

        cin>>arg[i][2]; //заполнение массива табличных значений функции "y", значения функции заполняют второй столбец двумерного массива

        cout<<"\n";

  }

 

  newton(arg,x,n,e);

  cout<<setw(5)<<"X(i)"<<setw(15)<<"Y(i)"<<endl;

      

  for(int i=0;i<=n;i++)

        cout<<setw(5)<<arg[i][1]<<setw(16)<<arg[i][2]<<"\n"; //вывод на экран табличных значений аргументов и функции

 

  cout<<endl;

  cout<<"X="<<x<<" P("<<arg[max][max]<<")="<<arg[0][0]<<" E="<<arg[1][0]<<endl; // вывод результатов вычислений на экран

      

  getch();

  return 0;

}

 

2.2.2 Интерполяция «назад».

Если искомая точка находится в конце таблицы заданных значений, к примеру, a = x=0.865, то для того, чтобы использовать большее число узлов применяется интерполяция «назад», в которой используется вторая интерполяционная формула Ньютона (11).

Ближайший справа к точке a = x=0.865 узел справа х=0.9, поэтому полагаем х_n=0.9. Используя интерполяционную формулу (11) и таблицу 2 составим полином Ньютона взяв два узла интерполяции. Для оценки погрешности используем формулу (13).

Для вычисления y(0.865) примем х _n=0.9, у _n=1.577351, тогда

 

q= = -0.35

 

P(0.865)=y_n+q Δy_n-1+  Δ²y_n-2 =

= 1.577351+(-0.35)* 0,050235+ -0,00429)=1.5605739

 

 

R(0.865)  6.9*10^-5=4.3*10^-6

Выводы:

1. В формулах Ньютона в случае добавления узла все найденные члены сохраняются и появляется новое слагаемое, представляющее собой ни что иное, как поправку к уже вычисленному значению.

 

2. При интерполяции на малых участках слагаемые в формулах (10) и (11) будут расположены в порядке их малости, что облегчает использование формул Ньютона в вычислениях и позволяет судить о точности интерполяции.

 

3. Степень интерполирующего полинома существенно зависит от шага таблицы (чем меньше шаг, тем график функции более приближен к линейному, что позволяет использовать линейную интерполяцию)

 

4. Ограниченность применения формул Ньютона связанна с их пригодностью лишь для равноотстоящих узлов.