Интерполирование алгебраическими многочленами

Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Задача интерполирования алгебраическими многочленами

2. Интерполяционная формула Лагранжа

3. Интерполяционная формула Ньютона

4. Применение интерполяционных формул к данному примеру

Заключение

Использованная литература

Приложение

алгебраический интерполяционный лагранж программа

Введение

Интерполированием является одним из способов приближения функций и применяется в тех случаях, когда функция задается таблицей своих значений в некоторых точках.

Задачей интерполирования состоит в том, чтобы по значениям функции f(x) в нескольких точках отрезка восстановить ее значения в остальных точках данного отрезка. Разумеется, такая постановка задачи допускает сколь угодно много решений.

Задача интерполирования возникает, например, в том случае, когда известны результаты измерений y_k = f(x_k) некоторой физической величины f(x) в точках x_k, k = 0, 1,…, n и требуется определить ее значение в других точках. Интерполирование используется также при необходимости сгущения таблиц, когда вычисление значений f(x) по точным формулам трудоемко.

1. Задача интерполирования алгебраическими многочленами

Пусть функциональная зависимость задана таблицей y_{0 =} f(x₀);…, y₁= f(x₁);…,y_{n =} f(x_n). Обычно задача интерполирования формулируется так: найти многочлен P(x) = P_n(x) степени не выше n, значения которого в точках x_i (i = 0, 1 2,…, n)совпадают со значениями данной функции, то есть P(x_i) = y_i.

Геометрически это означает, что нужно найти алгебраическую кривую вида

проходящую через заданную систему точек М_i(x_i,y_i) (рис. 1). Многочлен Р(х) называется интерполяционным многочленом. Точки x_i (i = 0, 1, 2,…, n) называются узлами интерполяции

Рис. 1. Интерполирование алгебраическим многочленом

Для любой непрерывной функции f(x) сформулированная задача имеет единственное решение. Действительно, для отыскания коэффициентов а₀, а₁, а₂ ,…, а_n получаем систему линейных уравнений

(1)

определитель которой (определитель Вандермонда) отличен от нуля, если среди точек x_i (i = 0, 1, 2,…, n) нет совпадающих.

Решение системы (1) можно записать различным образом. Однако наиболее употребительна запись интерполяционного многочлена в форме Лагранжа и в форме Ньютона.

2. Интерполяционная формула Лагранжа

Пусть и заданы точки , (узлы интерполирования), в которых известны значения функции . Задача интерполирования состоит в том, чтобы построить многочлен:

степени n, значения которого в заданных точках , совпадают со значениями функции в этих точках. Такой полином существует и единственен.

Интерполяционный многочлен степени не выше n по системе алгебраических многочленов 1, х, х?,…,x? можно задать по формуле Лагранжа:

,где ,

.

Обозначая

получим "барицентрический" вид многочлена Лагранжа:

3. Интерполяционная формула Ньютона

Интерполяционная формула Ньютона является разностным аналогом формулы Тейлора и имеет вид:

где , i,j=0,1,…,n,

i ? j - разделенные разности первого порядка,

, i,j,k=0,1,…,n,

I ? j ? k - разделенные разности второго порядка,

разделенные разности k-го порядка.

При выводе формулы Ньютона не накладывается ограничений на порядок узлов x₀,x₁,…,x_n , поэтому множество интерполяционных формул можно получить из перенумерацией узлов.

Также есть первая интерполяционная формула Ньютона (для интерполирования в начале таблицы, т.е. точка x близка к x₀), по которой будет считаться данная формула:

P_n(x) = f₀ + tД f₀ + Д²f₀ + … + Дⁿ f₀, где t =

n	fn	Дfn	Д2fn	Д3fn	Д4fn
0	f0	Дf0	Д2f0	Д3f0	Д4f0
1	f1	Дf1	Д2f1	Д3f1	…
2	f2	Дf2	Д2f2	…	…
3	f3	Дf3	…	…	…
4	f4	…	…	…	…

4. Применение интерполяционных формул к данному примеру

Дана таблица значений функции y = Sh(x):

x	Sh(x)
1,0 1,1 1,2 1,3 1,4	1,17520 1,33565 1,50946 1,69838 1,90430

Нужно найти приближенное значение Sh(x) по интерполяционной формуле Лагранжа и Ньютона для значения аргумента 0,03.

Исходя из данной формулы Лагранжа найдем значение.

,

в нашем случае L₅(1,03).

Найдем:

щ(1,03) = (1,03-1)*(1,03-2)*(1,03-3)*(1,03-4) = 0,0000356643

(щ'(x₀) = (1-1,1)*(1-1,2)*(1-1,3)*(1-1,4) = 0,0024

(щ'(x₁) = (1,1-1)*(1,1-1,2)*(1,1-1,3)*(1,1-1,4) = -0,0006

(щ'(x₂) = (1,2-1)*(1,2-1,1)*(1,2-1,3)*(1,2-1,4) = 0,0004

(щ'(x₃) = (1,3-1)*(1,3-1,1)*(1,3-1,2)*(1,3-1,4) = -0,0006

(щ'(x₄) = (1,4-1)*(1,4-1,1)*(1,4-1,2)*(1,4-1,3) = 0,0024

x - x₀ = 0,03

x - x₁ = - 0,07

x - x₂ = - 0,17

x - x₃ = - 0,27

x - x₄ = - 0,37

После того, как нашли щ(x) и щ' (x_k), найдем L₅(1,03).

L₅(1,03) = + +

+ + + =

= 0,58212063 + 1,1341671975 - 0,7916740335 + 0,373898357 - 0,07648144875 = 1,22203070225.

Найдем значение в точке 1,03 по интерполяционной формуле Ньютона.

Дf₀ = f₁ - f₀ = 0,16045

Дf₁ = f₂ - f₁ = 0,17381

Дf₂ = f₃ - f₂ = 0,18893

Дf₃ = f₄ - f₃ = 0,20592

Аналогично находим остальные значения Дf и подставим их в таблицу.

n	fn	Дfn	Д2fn	Д3fn	Д4fn
0	1,1752	0,16045	0,01336	0,00175	0,00014
1	1,33565	0,17381	0,01511	0,00189	…
2	1,50946	0,18892	0,017	…	…
3	1,69838	0,20592	…	…	…
4	1,9043	…	…	…	…

t = = 0,3

P₅(1,03) = 1,1752 + 0,3*0,16045 + *0,01336 + *

*0,00175 + *0,00014 = 1,1752 + 0,048135 - 0,0014028 + 0,000104125 - 0,00000562275 = 1,22203070225.

Теперь посчитаем значение в точке 1,03 по формуле гиперболического синуса:

Sh(x) = => Sh(1,03) = = 1,22202943707.

Заключение

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

Мною было рассчитано значение в точке по интерполяционным формулам Лагранжа и Ньютона и была создана демонстративная программа на Delphi 7, которая наглядно показывает достоверность решения методов.

Использованная литература

1) Монастырский П.И. Сборник задач по методам вычислений 1-е издание.

2) Монастырский П.И. Сборник задач по методам вычислений 2-е издание.

3) Тынкевич М. А.. Глава 7.6.1. Интерполяционный многочлен Лагранжа. Численные методы анализа.

Приложение

Используя все выше перечисленные интерполяционные формулы Лагранжа и Ньютона, внесем их в программу Delphi 7 через язык программирования Паскаль.

Результат по интерполяционной формуле Лагранжа:

Результат по интерполяционной формуле Ньютона:

Вывод: все значения в программе Delphi 7 совпадают со значениями из пункта 5.

Код программы Паскаль по интерполяционной формуле Ньютона:

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, StdCtrls, XPMan, unit2, Buttons, TeEngine, Series,

ExtCtrls, TeeProcs, Chart;

type

TForm1 = class(TForm)

Label1: TLabel;

Edit1: TEdit;

Button1: TButton;

StringGrid1: TStringGrid;

XPManifest1: TXPManifest;

Button2: TButton;

Memo1: TMemo;

Chart1: TChart;

Series1: TLineSeries;

BitBtn1: TBitBtn;

Label2: TLabel;

RadioGroup1: TRadioGroup;

Label3: TLabel;

Edit2: TEdit;

Button3: TButton;

Edit3: TEdit;

Memo2: TMemo;

LabeledEdit1: TLabeledEdit;

Label4: TLabel;

Edit4: TEdit;

Edit5: TEdit;

procedure FormCreate(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Meth:Methods;

flag:bool;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

begin

Meth:=Methods.Create;

RadioGroup1.ItemIndex:=0;

StringGrid1.Cells[0,0]:='№ узла';

StringGrid1.Cells[0,1]:='x[i]';

StringGrid1.Cells[0,2]:='y[i]';

StringGrid1.Cells[1,0]:=IntToStr(1);

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i:integer;

begin

Meth.N:=StrToInt(Edit1.Text);

StringGrid1.ColCount:=Meth.N+1;

for i:=1 to Meth.N do

begin

StringGrid1.Cells[i,0]:=IntToStr(i);

end;

end;

procedure TForm1.Button2Click(Sender: TObject);

var

i: integer;

begin

Memo1.Clear;

Memo2.Clear;

Series1.Clear;

Meth.Step:=StrToFloat(LabeledEdit1.Text);

for i:=1 to Meth.N do

begin

Meth.x[i]:=StrToFloat(StringGrid1.Cells[i,1]);

Meth.y[i]:=StrToFloat(StringGrid1.Cells[i,2]);

end;

for i:=0 to Meth.N-1 do

begin

Meth.x1[i]:=StrToFloat(StringGrid1.Cells[i+1,1]);

Meth.y1[i]:=StrToFloat(StringGrid1.Cells[i+1,2]);

end;

if RadioGroup1.ItemIndex = 0 then

Meth.Graf;

if RadioGroup1.ItemIndex = 1 then

Meth.Newton;

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

if RadioGroup1.ItemIndex = 0 then

Edit3.Text:=FloatToStr(Meth.PointLag(StrToFloat(Edit2.Text)))

else

Edit3.Text:=FloatToStr(Meth.PointNew(StrToFloat(Edit2.Text)));

end;

end.

Код программы Паскаль по интерполяционной формуле Лагранжа:

unit Unit2;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, StdCtrls,Math;

type

Tvector = array [1..10] of real;

Tvector1 = array [0..9] of real;

TMatr = array [1..10] of array[1..10] of real;

Methods = class

N:integer;

x,y,a:Tvector;

y1,x1:Tvector1;

mas:TMatr;

Step:real;

Polinom: string;

// function Lagrange(q:real):real;

procedure Graf;

function PointLag(point:real):real;

procedure Razn();

function RealD(xk:real;x0:real):real;

function Factorial(Number:integer): integer;

procedure Newton();

function PointNew(point:real):real;

end;

implementation

uses Unit1;

{function Methods.Lagrange(q:real):real;

var

i,j:integer;

L,s:real;

begin

L:=0;

for i:=1 to n do

begin

s:=1;

for j:=1 to N do

if j<>i then

s:=s*(q-x[j])/(x[i]-x[j]);

L:=L+y[i]*s;

end;

Form1.Memo1.Lines.Add('x= '+FloatToStr(q)+' y= '+FloatToStr(L));

//Form1.Series1.AddXY(q,l);

Lagrange:=l

end; }

procedure Methods.Graf();

Var

MassivA: array [1..10]of array [1..10]of real;

MassivB: array[1..10] of real;

MassivX: array[1..10] of real;

i,j,k:byte;

h, step, count:real;

Mx,My:real;

begin

for i:=1 to N do

begin

MassivB[i]:=y[i];

for j:=1 to N do

MassivA[j,i]:=Power(x[j],i-1);

end;

{Прямой ход - исключение переменных}

for k:=1 to n-1 do

for i:=k+1 to n do

begin

MassivA[i,k]:=-MassivA[i,k]/MassivA[k,k];

for j:=k+1 to n do

begin

MassivA[i,j]:=MassivA[i,j]+MassivA[i,k]*MassivA[k,j];

end;

MassivB[i]:=MassivB[i]+MassivA[i,k]*MassivB[k];

end;

MassivX[n]:=MassivB[n]/MassivA[n,n];

{Обратный ход - нахождение корней}

for k:=n-1 downto 1 do

begin

h:=MassivB[k];

for j:=k+1 to n do

h:=h-MassivX[j]*MassivA[k,j];

MassivX[k]:=h/MassivA[k,k];

end;

for i:=1 to n do

a[i]:=MassivX[i];

Polinom:='';

// построение многочлена

for i:=0 to N-1 do

begin

if ((i=N-1) or (i=0)) then

begin

if (i=N-1) then

begin

if(a[N-i]<0) then

Polinom:=Polinom+FloatToStr(a[N-i])

else

Polinom:=Polinom+ '+'+FloatToStr(a[N-i]);

end

else

Polinom:=Polinom+FloatToStr(a[N-i])+'x^'+IntToStr(N-i-1);

end

else

begin

if(a[N-i]<0) then

Polinom:=Polinom+FloatToStr(a[N-i])+'x^'+IntToStr(N-i-1)

else

Polinom:=Polinom + '+'+FloatToStr(a[N-i])+'x^'+IntToStr(N-i-1);

end;

end;

Form1.Memo2.Lines.Add(Polinom);

// построение графика

step:=x[1];

while step<=x[N] do

begin

Mx:=step;

My:=0;

for i:=1 to N do

begin

My:=My+a[i]*Power(Mx,i-1);

end;

Form1.Series1.AddXY(Mx,My);

step:=step + 0.001;

end;

//уплотнение таблицы

step:=x[1];

count:= StrToFloat(Form1.LabeledEdit1.Text);

while step<=x[N] do

begin

Mx:=step;

My:=0;

for i:=1 to N do

begin

My:=My+a[i]*Power(Mx,i-1);

end;

Form1.Memo1.Lines.Add('x= '+Format('%.3f',[Mx])+' y= '+Format('%.4f',[My]));

step:=step + count;

end;

end;

function Methods.PointLag(point:real):real;

var

i:byte;

begin

for i:=1 to N do

result:=result+a[i]*Power(point,i-1);

end;

// конечнее разности

procedure Methods.Razn();

var

i, j: byte;

begin

for j:=1 to N-1 do

mas[j,1]:= y[j+1]-y[j];

for i:=2 to N do

for j:=1 to N-i+1 do

mas[j,i]:= mas[j+1,i-1]-mas[j,i-1];

end;

// вывод D

function Methods.RealD(xk:real;x0:real):real;

begin

result:=(xk-x0)/(x[2]-x[1]);

end;

function Methods.Factorial(Number:integer):integer;

var

i:integer;

begin

result:=1;

for i:=1 to Number do

Result:= Result*Number;

end;

procedure Methods.Newton();

var

i,j:integer;

New, Ndop, d:real;

xn, xk, point:real;

begin

xn:= x[1];

xk:= StrToFloat(Form1.Edit5.Text);

point:= StrToFloat(Form1.Edit4.Text);

// d:= RealD(xk,xn);

Razn;

while (point<=xk) do

begin

New:=y[1];

for i:=1 to N-1 do

begin

d:= RealD(point,xn);

Ndop:=d*mas[1,i]/Factorial(i);

if (i>1) then

begin

for j:=1 to i-1 do

Ndop:=Ndop*(d-j);

end;

New:=New+Ndop;

end;

Form1.Series1.AddXY(point,New);

Form1.Memo1.Lines.Add('x= '+Format('%.3f',[point])+' y= '+Format('%.4f',[New]));

point:=point+Step;

end;

Form1.Memo2.Lines.Add(Polinom);

end;

function Methods.PointNew(point:real):real;

var

New, Ndop, d:real;

i, j: byte;

begin

New:=y[1];

for i:=1 to N-1 do

begin

d:= RealD(point,x[1]);

Ndop:=d*mas[1,i]/Factorial(i);

if (i>1) then

begin

for j:=1 to i-1 do

Ndop:=Ndop*(d-j);

end;

result:=New+Ndop;

end;

end;

end.

Размещено на Allbest.ru