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

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

Оглавление

Введение

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₀), по которой будет считаться данная формула:

_n(x) = f₀ + tΔ f₀ +  Δ²f₀ + … +  Δⁿ f₀, где t =

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

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

Нужно найти приближенное значение 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₀ = 0,03- x₁ = - 0,07 - 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 и подставим их в таблицу.

= = 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.

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

Unit1;

interface

uses, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, Grids, StdCtrls, XPMan, unit2, Buttons, TeEngine, Series,, TeeProcs, Chart;

type= class(TForm): TLabel;: TEdit;: TButton;: TStringGrid;: TXPManifest;: TButton;: TMemo;: TChart;: TLineSeries;: TBitBtn;: TLabel;: TRadioGroup;: TLabel;: TEdit;: TButton;: TEdit;: TMemo;: TLabeledEdit;: TLabel;: TEdit;: TEdit;FormCreate(Sender: TObject);Button1Click(Sender: TObject);Button2Click(Sender: TObject);Button3Click(Sender: TObject);

{ Private declarations }

{ Public declarations };

var: TForm1;:Methods;:bool;

{$R *.dfm}TForm1.FormCreate(Sender: TObject);:=Methods.Create;.ItemIndex:=0;.Cells[0,0]:='№ узла';.Cells[0,1]:='x[i]';.Cells[0,2]:='y[i]';.Cells[1,0]:=IntToStr(1);;

procedure TForm1.Button1Click(Sender: TObject);:integer;.N:=StrToInt(Edit1.Text);.ColCount:=Meth.N+1;i:=1 to Meth.N do.Cells[i,0]:=IntToStr(i);;

end;

procedure TForm1.Button2Click(Sender: TObject);: integer;.Clear;.Clear;.Clear;.Step:=StrToFloat(LabeledEdit1.Text);i:=1 to Meth.N do.x[i]:=StrToFloat(StringGrid1.Cells[i,1]);.y[i]:=StrToFloat(StringGrid1.Cells[i,2]);;i:=0 to Meth.N-1 do.x1[i]:=StrToFloat(StringGrid1.Cells[i+1,1]);.y1[i]:=StrToFloat(StringGrid1.Cells[i+1,2]);;RadioGroup1.ItemIndex = 0 then.Graf;RadioGroup1.ItemIndex = 1 then.Newton;;

procedure TForm1.Button3Click(Sender: TObject);RadioGroup1.ItemIndex = 0 then.Text:=FloatToStr(Meth.PointLag(StrToFloat(Edit2.Text))).Text:=FloatToStr(Meth.PointNew(StrToFloat(Edit2.Text)));

end;.

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

unit Unit2;

interface, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, Grids, StdCtrls,Math;= array [1..10] of real;= array [0..9] of real;= array [1..10] of array[1..10] of real;= class:integer;,y,a:Tvector;,x1:Tvector1;:TMatr;:real;: string;

// function Lagrange(q:real):real;Graf;PointLag(point:real):real;Razn();RealD(xk:real;x0:real):real;Factorial(Number:integer): integer;Newton();PointNew(point:real):real;;

implementationUnit1;

{function Methods.Lagrange(q:real):real;,j:integer;,s:real;:=0;i:=1 to n do:=1;j:=1 to N doj<>i then:=s*(q-x[j])/(x[i]-x[j]);:=L+y[i]*s;;.Memo1.Lines.Add('x= '+FloatToStr(q)+' y= '+FloatToStr(L));

//Form1.Series1.AddXY(q,l);:=l; }

procedure Methods.Graf();: array [1..10]of array [1..10]of real;: array[1..10] of real;: array[1..10] of real;,j,k:byte;, step, count:real;,My:real;i:=1 to N do[i]:=y[i];j:=1 to N do[j,i]:=Power(x[j],i-1);

end;

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

for k:=1 to n-1 doi:=k+1 to n do[i,k]:=-MassivA[i,k]/MassivA[k,k];j:=k+1 to n do[i,j]:=MassivA[i,j]+MassivA[i,k]*MassivA[k,j];;[i]:=MassivB[i]+MassivA[i,k]*MassivB[k];;[n]:=MassivB[n]/MassivA[n,n];

{Обратный ход - нахождение корней}k:=n-1 downto 1 do

begin:=MassivB[k];j:=k+1 to n do:=h-MassivX[j]*MassivA[k,j];[k]:=h/MassivA[k,k];;i:=1 to n do[i]:=MassivX[i];:='';

// построение многочленаi:=0 to N-1 do((i=N-1) or (i=0)) then(i=N-1) then(a[N-i]<0) then:=Polinom+FloatToStr(a[N-i]):=Polinom+ '+'+FloatToStr(a[N-i]);:=Polinom+FloatToStr(a[N-i])+'x^'+IntToStr(N-i-1);(a[N-i]<0) then:=Polinom+FloatToStr(a[N-i])+'x^'+IntToStr(N-i-1):=Polinom + '+'+FloatToStr(a[N-i])+'x^'+IntToStr(N-i-1);;;.Memo2.Lines.Add(Polinom);

// построение графика:=x[1];step<=x[N] do:=step;:=0;i:=1 to N do:=My+a[i]*Power(Mx,i-1);;.Series1.AddXY(Mx,My);:=step + 0.001;;

//уплотнение таблицы:=x[1];:= StrToFloat(Form1.LabeledEdit1.Text);step<=x[N] do:=step;:=0;i:=1 to N do:=My+a[i]*Power(Mx,i-1);;.Memo1.Lines.Add('x= '+Format('%.3f',[Mx])+' y= '+Format('%.4f',[My]));:=step + count;;;

function Methods.PointLag(point:real):real;:byte;i:=1 to N do:=result+a[i]*Power(point,i-1);;

// конечнее разностиMethods.Razn();, j: byte;j:=1 to N-1 do[j,1]:= y[j+1]-y[j];i:=2 to N doj:=1 to N-i+1 do[j,i]:= mas[j+1,i-1]-mas[j,i-1];;

// вывод DMethods.RealD(xk:real;x0:real):real;:=(xk-x0)/(x[2]-x[1]);;

function Methods.Factorial(Number:integer):integer;:integer;:=1;i:=1 to Number do:= Result*Number;;

procedure Methods.Newton();,j:integer;, Ndop, d:real;, xk, point:real;:= x[1];:= StrToFloat(Form1.Edit5.Text);:= StrToFloat(Form1.Edit4.Text);

// d:= RealD(xk,xn);;(point<=xk) do:=y[1];i:=1 to N-1 do:= RealD(point,xn);:=d*mas[1,i]/Factorial(i);(i>1) thenj:=1 to i-1 do:=Ndop*(d-j);;:=New+Ndop;;.Series1.AddXY(point,New);.Memo1.Lines.Add('x= '+Format('%.3f',[point])+' y= '+Format('%.4f',[New]));:=point+Step;;.Memo2.Lines.Add(Polinom);;

function Methods.PointNew(point:real):real;, Ndop, d:real;, j: byte;:=y[1];i:=1 to N-1 do:= RealD(point,x[1]);:=d*mas[1,i]/Factorial(i);(i>1) thenj:=1 to i-1 do:=Ndop*(d-j);;:=New+Ndop;;;

end.