Полиномиальная интерполяция Гаусса, Ньютона, Стирлинга
Министерство образования Российской Федерации
Сибирский Государственный Технологический Университет
Факультет: Автоматизации и информационных технологий
Кафедра: Системотехники
Курсовая работа
Полиномиальная интерполяция Гаусса, Ньютона, Стирлинга
Руководитель: Ващенко Г.В.
Разработал: Русинов Д.В.
Содержание
Аннотация
Введение
. Постановка задачи
. Описание метода полиномиальной интерполяции
. Блок-схема программного обеспечения
. Исходные тексты основных процедур программы
. Результаты численных экспериментов
Заключение
Список используемых источников
Аннотация
В данной курсовой работе представлены алгоритмы и программное обеспечение, реализующее решение полиномиального интерполирования методами Ньютона, Гаусса и Стирлинга.
Введение
В данной курсовой работе были разработаны алгоритм и программа для решения задачи полиномиального интерполирования. В общем виде задача интерполирования формулируется следующим образом: для таблично заданной функции f требуется найти достаточно простую известную функцию p, удовлетворяющую соотношениям
p(xi)=yi (i=0,1,2, …, n)
1. Постановка задачи
Для таблично задаваемых функций требуется составить алгоритм и программное обеспечение для реализации конечноразностных интерполяционных формул Ньютона, Гаусса и Стирлинга.
2. Описание метода полиномиальной интерполяции
Пусть функция y=f(x) задана на сетке равноотстоящих узлов
xi=xo+ih,
где i=0, 1,…, n, и для неё построена таблица конечных разностей.
Будем строить интерполяционный многочлен Pn(x) в форме:
Pn(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+…+an(x-x0)(x-x1)…(x-xn-1)
3. Конструктивная схема программного обеспечения
1.Функция ввода:
Позволяет пользователю задавать размерность таблицы, выбирать крайние точки и задавать табличную функцию.
procedure TForm1.Button1Click(Sender: TObject);:=strtofloat(EditXo.text);:=(Strtofloat(EditXn.Text)-x0)/n;i:=0 to n do[i]:=strtofloat(setka.Cells[i+1,1]);:=PolyNuton1;:=PolyNuton2;i:=0 to n do[i-(n div 2)]:=y[i];:=x0+(n div 2)*h;:=PolyGauss1;:=PolyGauss2;:=PolyStirling;Polynoms do[1,0]:=PN1; Cells[1,1]:=PN2;[1,2]:=PG1; Cells[1,3]:=PG2;[1,4]:=PS;
DrawGraph;;
.Функция вычисления:
Function PolyNuton1:string;PolyNuton2:string; PolyGauss1:string;
функции вычисления полиномов в текстовом виде
Function PolyGauss2:string;PolyStirling:string;PolyN1(x:extended):extended;PolyN2(x:extended):extended;PolyG1(x:extended):extended;
Function PolyG2(x:extended):extended;PolyS(x:extended):extended;
Функция вывода:
procedure TForm1.Button1Click(Sender: TObject);:=strtofloat(EditXo.text);:=(Strtofloat(EditXn.Text)-x0)/n;i:=0 to n do[i]:=strtofloat(setka.Cells[i+1,1]);:=PolyNuton1;:=PolyNuton2;i:=0 to n do[i-(n div 2)]:=y[i];:=x0+(n div 2)*h;:=PolyGauss1;:=PolyGauss2;:=PolyStirling;Polynoms do[1,0]:=PN1; Cells[1,1]:=PN2;[1,2]:=PG1; Cells[1,3]:=PG2;[1,4]:=PS;;;; DrawGraph - процедура рисования графиков
4. Исходные тексты основных процедур программы
unit Unit1;
interface
uses, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, Grids, Math, StdCtrls, Spin,StrUtils, ExtCtrls;=array[-100..200] of extended;= class(TForm): TStringGrid;: TSpinEdit;: TLabel;: TLabel;: TEdit;: TLabel;: TEdit;: TButton;: TStringGrid;: TImage;: TCheckBox;: TCheckBox;: TCheckBox;: TCheckBox;: TCheckBox;Button1Click(Sender: TObject);FormCreate(Sender: TObject);EditXnExit(Sender: TObject);EditXoExit(Sender: TObject);SpinEditnKeyPress(Sender: TObject; var Key: Char);SpinEditnExit(Sender: TObject);PolynomsKeyPress(Sender: TObject; var Key: Char);CheckN1Click(Sender: TObject);
Function Fact(n:longint):longint; //ôàêòîðèàë
Function C(n,k:integer):extended; //Ñ èç n ïî kDelta(k:integer;y:Tarray;i:integer):extended; //Äåëüòà ê-îé ñòåï. YiZapX; //çàïîëíèòü ñòðîêó ñ x-ìè
Function PolyNuton1:string;PolyNuton2:string;PolyGauss1:string;PolyGauss2:string;PolyStirling:string;PolyN1(x:extended):extended;PolyN2(x:extended):extended;PolyG1(x:extended):extended;PolyG2(x:extended):extended;PolyS(x:extended):extended;DrawGraph;
{ Public declarations };: TForm1;:TArray;,i,j,k:integer;,x0,z,x,r:extended;,PN2,PG1,PG2,PS:string;
{$R *.dfm}TForm1.DrawGraph;,scy,miny,maxy:extended;:integer;:=strtofloat(EditXo.text);:=(Strtofloat(EditXn.Text)-x0)/n;i:=0 to n do[i]:=strtofloat(setka.Cells[i+1,1]);:=(image1.Width-30)/n;:=y[0];:=miny;i:=1 to n dominy>y[i] then miny:=y[i];maxy<y[i] then maxy:=y[i];;:=(Image1.Height-30)/(maxy-miny);.Canvas.FillRect(Rect(0,0,Width,Height));Image1.Canvas do.Color:=clLime;.Style:=psSolid;.Width:=1;i:=0 to n do(20+round(scx*i),Image1.Height-15);(20+round(scx*i),0);(15+round(scx*i),Image1.Height-15,floatToStr(x0+i*h));(15,Image1.Height-20-round(scy*(y[i]-miny)));(Image1.Width,Image1.Height-20-round(scy*(y[i]-miny)));(5,Image1.Height-27-round(scy*(y[i]-miny)),floatToStr(y[i]));;;Image1.Canvas do.Color:=clblack;.Width:=3;(20,Image1.Height-20-round(scy*(y[0]-miny)));i:=1 to n do(20+round(scx*i),Image1.Height-20-round(scy*(y[i]-miny)));.Width:=2;i:=21 to Image1.Width-10 doCheckN1.Checked then.Color:=clBlue;(i-1,Image1.Height-20-round(scy*(PolyN1(x0+(i-21)*h/scx)-miny)));(i,Image1.Height-20-round(scy*(PolyN1(x0+(i-20)*h/scx)-miny)));;CheckN2.Checked then.Color:=clGreen;(i-1,Image1.Height-20-round(scy*(PolyN2(x0+(i-21)*h/scx)-miny)));(i,Image1.Height-20-round(scy*(PolyN2(x0+(i-20)*h/scx)-miny)));;;i:=0 to n do[i-(n div 2)]:=y[i];:=x0+(n div 2)*h;i:=21 to Image1.Width-10 doCheckG1.Checked then.Color:=clRed;(i-1,Image1.Height-20-round(scy*(PolyG1(x0-(n div 2)*h+(i-21)*h/scx)-miny)));(i,Image1.Height-20-round(scy*(PolyG1(x0-(n div 2)*h+(i-20)*h/scx)-miny)));;CheckG2.Checked then.Color:=rgb(50,200,150);(i-1,Image1.Height-20-round(scy*(PolyG2(x0-(n div 2)*h+(i-21)*h/scx)-miny)));(i,Image1.Height-20-round(scy*(PolyG2(x0-(n div 2)*h+(i-20)*h/scx)-miny)));;CheckS.Checked then.Color:=clgray;(i-1,Image1.Height-20-round(scy*(PolyS(x0-(n div 2)*h+(i-21)*h/scx)-miny)));(i,Image1.Height-20-round(scy*(PolyS(x0-(n div 2)*h+(i-20)*h/scx)-miny)));;;;;TForm1.ZapX;:=strtofloat(EditXo.text);:=(Strtofloat(EditXn.Text)-x0)/n;i:=1 to n+1 do.Cells[i,0]:=floattostr(x0+pred(i)*h);;TForm1.Fact(n:integer):longint;i:integer;:=1;i:=1 to n do:=Result*i;;Tform1.C(n,k:integer):extended;:=fact(n)/(fact(k)*fact(n-k));;Tform1.Delta(k:integer;y:TArray;i:integer):extended;j:integer;:=0;j:=0 to k do:=result+intpower(-1,j)*C(k,j)*y[k+i-j];;TForm1.PolyNuton1:string;:=floattostr(y[0]);i:=1 to n do:=Delta(i,y,0)/(fact(i)*IntPower(h,i));z=0 then continue;(z>0) then Result:=Result+'+';z<>1 then Result:=Result+floattostr(z);j:=1 to i do:=x0+pred(j)*h;z=0Result:=Result+'x'if z>0 then Result:=Result+'(x-'+floattostr(z)+')'Result:=Result+'(x'+floattostr(z)+')';;;Tform1.PolyN1(x:extended):extended;:=(y[0]);i:=1 to n do:=Delta(i,y,0)/(fact(i)*IntPower(h,i));z=0 then continue;:=z;j:=1 to i do:=x0+pred(j)*h;:=r*(x-z);:=Result+r;;;TForm1.PolyNuton2:string;:=floattostr(y[n]);i:=1 to n do:=Delta(i,y,n-i)/(fact(i)*IntPower(h,i));z=0 then continue;(z>0) then Result:=Result+'+';z<>1 then Result:=Result+floattostr(z);j:=n downto n-pred(i) do:=x0+j*h;z=0Result:=Result+'x'if z>0 then Result:=Result+'(x-'+floattostr(z)+')'Result:=Result+'(x'+floattostr(z)+')';;;Tform1.PolyN2(x:extended):extended;:=(y[n]);i:=1 to n do:=Delta(i,y,n-i)/(fact(i)*IntPower(h,i));z=0 then continue;:=z;j:=n downto n-pred(i) do:=x0+j*h;:=r*(x-z);:=Result+r;;;TForm1.PolyGauss1:string;:=floattostr(y[0]);i:=1 to n do:=Delta(i,y,-(i div 2))/(fact(i)*IntPower(h,i));z=0 then continue;(z>0) then Result:=Result+'+';z<>1 then Result:=Result+floattostr(z);j:=-(i div 2)+1-i mod 2 to (i div 2) do:=x0+j*h;z=0Result:=Result+'x'if z>0 then Result:=Result+'(x-'+floattostr(z)+')'Result:=Result+'(x'+floattostr(z)+')';;;Tform1.PolyG1(x:extended):extended;:=(y[0]);i:=1 to n do:=Delta(i,y,-(i div 2))/(fact(i)*IntPower(h,i));z=0 then continue;:=z;j:=-(i div 2)+1-i mod 2 to (i div 2) do:=x0+j*h;:=r*(x-z);:=Result+r;;;TForm1.PolyGauss2:string;:=floattostr(y[0]);i:=1 to n do:=Delta(i,y,-(succ(i) div 2))/(fact(i)*IntPower(h,i));z=0 then continue;(z>0) then Result:=Result+'+';z<>1 then Result:=Result+floattostr(z);j:=-(i div 2) to (i div 2)-1+i mod 2 do:=x0+j*h;z=0Result:=Result+'x'if z>0 then Result:=Result+'(x-'+floattostr(z)+')'Result:=Result+'(x'+floattostr(z)+')';;;Tform1.PolyG2(x:extended):extended;:=(y[0]);i:=1 to n do:=Delta(i,y,-(succ(i) div 2))/(fact(i)*IntPower(h,i));z=0 then continue;:=z;j:=-(i div 2) to (i div 2)-1+i mod 2 do:=x0+j*h;:=r*(x-z);:=Result+r;;;TForm1.PolyStirling:string;:=floattostr(y[0]);i:=1 to n do:=(Delta(i,y,-(i div 2))+Delta(i,y,-(succ(i) div 2)))/(2*fact(i)*IntPower(h,i));not(odd(i)) then z:=z/2;z=0 then continue;(z>0) then Result:=Result+'+';z<>1 then Result:=Result+floattostr(z);j:=-(i div 2)+1-i mod 2 to (i div 2)-1+i mod 2 do:=x0+j*h;z=0Result:=Result+'x'if z>0 then Result:=Result+'(x-'+floattostr(z)+')'Result:=Result+'(x'+floattostr(z)+')';not(odd(i)) then:=-2*x0;z=0 then Result:=result+'2x'z<0Result:=Result+'(2x'+floattostr(z)+')'Result:=Result+'(2x+'+floattostr(z)+')';;;;Tform1.PolyS(x:extended):extended;:=(y[0]);i:=1 to n do:=(Delta(i,y,-(i div 2))+Delta(i,y,-(succ(i) div 2)))/(2*fact(i)*IntPower(h,i));not(odd(i)) then z:=z/2;z=0 then continue;:=z;j:=-(i div 2)+1-i mod 2 to (i div 2)-1+i mod 2 do:=x0+j*h;:=r*(x-z);not(odd(i)) then r:=r*(2*(x-x0));:=Result+r;;;TForm1.Button1Click(Sender: TObject);:=strtofloat(EditXo.text);:=(Strtofloat(EditXn.Text)-x0)/n;i:=0 to n do[i]:=strtofloat(setka.Cells[i+1,1]);:=PolyNuton1;:=PolyNuton2;i:=0 to n do[i-(n div 2)]:=y[i];:=x0+(n div 2)*h;:=PolyGauss1;:=PolyGauss2;:=PolyStirling;Polynoms do[1,0]:=PN1; Cells[1,1]:=PN2;[1,2]:=PG1; Cells[1,3]:=PG2;[1,4]:=PS;;;;TForm1.FormCreate(Sender: TObject);:=4;Polynoms do[1]:=1593;
Cells[0,0]:='I ïîëèíîì Íüþòîíà';[0,1]:='II ïîëèíîì Íüþòîíà';[0,2]:='I ïîëèíîì Ãàóññà';[0,3]:='II ïîëèíîì Ãàóññà';[0,4]:='ïîëèíîì Ñòèðëèíãà';
end;setka do[0,0]:=' x';[0,1]:=' y';;;TForm1.EditXnExit(Sender: TObject);StrTofloat(EditXn.Text)<StrTofloat(EditXo.Text) then.Undo;;;TForm1.EditXoExit(Sender: TObject);StrTofloat(EditXn.Text)<StrTofloat(EditXo.Text) then.Undo;;;TForm1.SpinEditnKeyPress(Sender: TObject; var Key: Char);not(key in ['0'..'9','-',#8,DecimalSeparator]) then key:=#0;;TForm1.SpinEditnExit(Sender: TObject);.ColCount:=SpinEditn.Value+1;:=SpinEditn.Value-1;;;TForm1.PolynomsKeyPress(Sender: TObject; var Key: Char);:=#0;TForm1.CheckN1Click(Sender: TObject);
begin;;.5. Результаты численных экспериментов.
Хорошо обусловленные матрицы(Ввод пользователем)
№Размерность матрицыВектор невязки(r)Норма матрицы ||r||-равномерное13r1=0,00001 r2=0 r3=0||r||=10124r1=0 r2=0,00002 r3=0,00003 r4=0,00003||r||=153310r1=0,00002 r2=0,00004 r3=0,00003 r4=0,00006 r5=0,00001 r6=0,00003 r7=0,00012 r8=0,00001 r9=0,00004 r10=0,00021||r||=362
Хорошо обусловленные матрицы(случайный выбор)
№Размерность матрицыВектор невязки(r)Норма матрицы ||r||-равномерноеДиапазон случайной величины13r1=0 r2=0 r3=0||r||=13От 1 до 524r1=0 r2=0 r3=0 r4=0||r||=36От 1 до10310r1=0,00014 r2=0,00004 r3=0,00013 r4=0,00009 r5=0,00032 r6=0,00001 r7=0,00012 r8=0,00021 r9=0,00002 r10=0,00022||r||=472От 1 до 100
Плохо обусловленные матрицы(Ввод пользователем)
Плохо обусловленные матрицы(заполнение по правилу 1/I+j)
№Размерность матрицыВектор невязки(r)Норма матрицы ||r||-равномерное13r1=0 r2=0 r3=0||r||=1,8324r1=0 r2=0 r3=0 r4=0||r||=2,08310r1=0 r2=0 r3=0 r4=0 r5=0 r6=0 r7=0 r8=0 r9=0 r10=0||r||=2,92
Заключение
программный полиномиальный интерполяция линейный
В данной работе был разработан алгоритм и программа для решения уравнения вида A*х=B методом оптимального исключения. Метод оптимального исключения дает возможность решения систем линейных уравнений размерностью на два порядка выше, чем в обычных методах (как например методы Гаусса, Жордана-Гаусса и т. д), за счет возможности подзагрузки в оперативную память порции уравнений во время решения системы.
Численные эксперименты, проведенные над линейными системами с хорошо и плохо обусловленными матрицами, различных размерностей, показали, что, не смотря на сложность вычислительной схемы (алгоритма) метод дает ряд преимуществ перед обычными методами (методы Гаусса, Жордана-Гаусса и т. д), а именно уменьшается погрешность (вектор невязки) и возрастает скорость вычисления.
Численные эксперименты проведены на процессоре Pentium 4 с одноразрядной точностью(real).
Список используемых источников
1.Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры.-М.: Физматгиз, 1963.- 734 с.
.Культин Н.Б. Основы программирования 0в Delphi 7. - СПб.: БХВ-Петербург, 2003. -608с.: ил.
.Бобровский И.С. Delphi 7. Учебный курс. - СПб.: Питер, 2003. - 736 с.: ил.