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

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

[Введите текст]

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Челябинский государственный университет»

(ФГБОУ ВПО «ЧелГУ»)

Математический факультет

Кафедра Вычислительной математики

Контрольная работа по теме:

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

Челябинск

2014



ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1. ЗАДАЧА ИНТЕРПОЛИРОВАНИЯ АЛГЕБРАИЧЕСКИМИ МНОГОЧЛЕНАМИ

2. ИНТЕРПОЛЯЦИОННАЯ ФОРМУЛА ЛАГРАНЖА

3. ИНТЕРПОЛЯЦИОННАЯ ФОРМУЛА НЬЮТОНА

4. ПРИМЕНЕНИЕ ИНТЕРПОЛЯЦИОННЫХ ФОРМУЛ К ДАННОМУ ПРИМЕРУ

ЗАКЛЮЧЕНИЕ

ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ



ВВЕДЕНИЕ

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

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

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



1. ЗАДАЧА ИНТЕРПОЛИРОВАНИЯ АЛГЕБРАИЧЕСКИМИ МНОГОЧЛЕНАМИ

Пусть функциональная зависимость задана таблицей y0 = f(x0);…, y1= f(x1);…,yn = f(xn). Обычно задача интерполирования формулируется так: найти многочлен P(x) = Pn(x) степени не выше n, значения которого в точках xi (i = 0, 1 2,…, n)совпадают со значениями данной функции, то есть P(xi) = yi.

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

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

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

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



(1)

определитель которой (определитель Вандермонда) отличен от нуля, если среди точек xi (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-го порядка.

При выводе формулы Ньютона не накладывается ограничений на порядок узлов x0,x1,…,xn , поэтому множество интерполяционных формул можно получить из перенумерацией узлов. Также есть первая интерполяционная формула Ньютона (для интерполирования в начале таблицы, т.е. точка x близка к x0), по которой будет считаться данная формула:

Pn(x) = f0 + tД f0 + Д2f0 + … + Дn f0,

где 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.

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

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

Найдем:

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

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

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

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

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

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

x - x0 = 0,03

x - x1 = - 0,07

x - x2 = - 0,17

x - x3 = - 0,27

x - x4 = - 0,37

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

L5(1,03) = + + + + = 0,58212063 + 1,1341671975 - 0,7916740335 + 0,373898357 - 0,07648144875 = 1,22203070225

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

Дf0 = f1 - f0 = 0,16045

Дf1 = f2 - f1 = 0,17381

Дf2 = f3 - f2 = 0,18893

Дf3 = f4 - f3 = 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

P5(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

...