КУРСОВАЯ РАБОТА
по теме: «Вычислительная техника ипрограммирование»
Киев
Введение
Если задана функция y(x),то это означает, что любому допустимому значению х сопоставлено значение у. Нонередко оказывается, что нахождение этого значения очень трудоёмко. Например,у(х) может быть определено как решение сложной задачи, в которой х играет рольпараметра или у(х) измеряется в дорогостоящем эксперименте. При этом можновычислить небольшую таблицу значений функции, но прямое нахождение функции прибольшом числе значений аргумента будет практически невозможно. Функция у(х)может участвовать в каких-либо физико-технических или чисто математическихрасчётах, где её приходится многократно вычислять. В этом случае выгоднозаменить функцию у(х) приближённой формулой, то есть подобрать некоторуюфункцию j(х), которая близка в некотором смысле к у(х) и просто вычисляется.Затем при всех значениях аргумента полагают у(х)«j(х).
Что касается критериясогласия, то классическим критерием согласия является „точное совпадение вузловых точках“. Этот критерий имеет преимущество простоты теории ивыполнения вычислений, но также неудобство из-за игнорирования шума(погрешности, возникающей при измерении или вычислении значений в узловыхточках). Другой относительно хороший критерий — это „наименьшие квадраты“.Он означает, что сумма квадратов отклонений в узловых точках должна бытьнаименьшей возможной или, другими словами, минимизирована. Этот критерийиспользует ошибочную информацию, чтобы получить некоторое сглаживание шума.Третий критерий связывается с именем Чебышева. Основная идея его состоит в том,чтобы уменьшить максимальное отклонение до минимума. Очевидно, возможны идругие критерии.
Цель задачи о приближении(интерполяции): данную функцию у(х) требуется приблизительно заменить некоторойфункцией j(х), свойства которой нам известны так, чтобы отклонение в заданнойобласти было наименьшим. интерполяционные формулы применяются, прежде всего,при замене графически заданной функции аналитической, а также для интерполяциив таблицах.
Один из подходов к задачеинтерполяции — метод Лагранжа. Основная идея этого метода состоит в том, чтобыпрежде всего найти многочлен, который принимает значение 1 в одной узловойточке и 0 во всех других. Легко видеть, что функция (1) является требуемыммногочленом степени n; он равен 1, если X=Xj и 0, когда X=Xi, i¹j.
/> (1)
Многочлен Lj(x)×Yj принимает значения Yi в i-й узловой точке и равен 0 вовсех других узлах. Из этого следует, что (2) есть многочлен степени n,проходящий через n+1 точку (Xi, Yi).
/> (2)
Другой подход — методНьютона (метод разделённых разностей). Этот метод позволяет получитьаппроксимирующие значения функции без построения в явном виде аппроксимирующегополинома. В результате получаем формулу для полинома Pn, аппроксимирующую функциюf(x):
P(x)=P(x0)+(x-x0)P(x0,x1)+(x-x0)(x-x1)P(x0,x1,x2)+…+
(x-x0)(x-x1)…(x-xn)P(x0,x1,…,xn);
/> разделённая разность 1-го порядка;
/> разделённая разность 2-го порядка и т.д.
Значения Pn(x) в узлахсовпадают со значениями f(x)
Фактически формулыЛагранжа и Ньютона порождают один и тот же полином, разница только в алгоритмеего построения.
Постановка задачи:
1. Построитьинтерполяционный полином Ньютона по значениям функции в узлах: />.
2. Математическаяпостановка задачи:
Формула выглядиттак:
/>
Разделённаяразность:
/>.
1.Алгоритм программы Polinom
/>
Рис.1 Схема алгоритма подпрограммы Swap
/>
Рис.2 Схема алгоритма подпрограммы Null
/>
Рис.3 Схема алгоритма подпрограммы Rise
/>
Рис.4 Схема алгоритма подпрограммы Calculat
/>
Рис.5 Схема алгоритмаподпрограммы Vvod
/>
Рис.6 Схема алгоритмапрограммы Print_Polinom
/>
Рис.7 Схема алгоритмаподпрограммы Div_Res
/>
Рис.8 Схема алгоритма программы Nuton
/>
Рис.9 Схема алгоритмаподпрограммы Recover
/>
Рис.10 Блок-схемапрограммы Polinom
2. Листинг программы Polinom
Реализуем алгоритм наязыке высокого уровня Turbo Pascal, используяподпрограммы.
PROGRAM POLINOM; {Программа построения интерполяционного полиномаНьютона}
Uses Crt;
ConstMax_Num_Usel=20; {Количество узлов}
Type
Matrix_Line =Array[1..Max_Num_Usel] Of Real;
Var Max:Byte;
X,F:Matrix_Line;
PROCEDURESwap(Var First,Second:real); {Обмена двухREAL переменных}
Var Temp:Real;
Begin
Temp:=First;
First:=Second;
Second:=Temp;
End; {Swap}
FUNCTIONRise(Root:Real;Power:Integer):Real; {Возведение в степень}
Var Temp:Real;
i:Integer;
Begin
Temp:=1;
For i:=1 ToPower Do
Temp:=Temp*Root;
Rise:=Temp;
End; {Rise}
PROCEDURENull(Last:Byte;Var M:Matrix_Line); {Обнуление матриц}
Var i:Byte;
Begin
For i:=1 ToLast Do
M[i]:=0;
End; {Null}
PROCEDURECalculat(Num:Integer;Cx:Matrix_Line); {вычисление значений полинома}
Var x,y:Real;
i:Integer;
Finish:Boolean;
c:Char;
Begin
Writeln('***********************************************');
Writeln;
Writeln('Вычисление значенийинтерполяционного полинома:');
Writeln('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~');
Writeln('Введите значение x:');
Repeat
y:=0;
Readln(x);
For i:=NumDownTo 1 Do
y:=y+Cx[i]*Rise(x,i-1);
Writeln('Значение полинома в точке Xo=',x:7:4,' равно Yo=',y:7:4);
Write('Нажмите `ESC` для выхода или любую клавишу для продолжения');
c:=Readkey;
If c=#27 ThenFinish:=True Else Finish:=False;
GoToXY(1,WhereY-2);
DelLine;DelLine;DelLine;
Until Finish;
End;{Calculat}
PROCEDUREVvod(Var Mat_x,Mat_f:Matrix_Line;Var Number:Byte);
Var c:Char;
i,j:Integer;
Enter:Boolean;
Begin
ClrScr;
Writeln('Построение интерполяционногополинома Ньютона по значениям функции в узлах');
Writeln('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~);
Writeln;
Writeln('Введите кол-во узлов интерполяции(0
Repeat
Readln(Number);
Until(Number
ClrScr;
Writeln('Значения узлов не должнысопадать');
Writeln('Введите значения узлов и значенияфункций в них:');
For i:=1 ToNumber Do
Begin
Repeat
{Ввод узлов}
Enter:=True;{Правильность ввода}
GoToXY(5,i+3);
Write('X(',i-1,')=');
Readln(Mat_x[i]);
For j:=i-1DownTo 1 Do
If (Mat_x[j]=Mat_x[i]) Then {Проверка на одинаковые узлы}
Begin
Writeln('Значения узлов ',i,' и ',j,' введены неверно!!!');
Write('Нажмите `Y` для повторения ввода или любую клавишу для выхода');
c:=Readkey;
If (c='Y') Or(c='y') Then Enter:=False Else Halt;
GoToXY(5,i+3);
DelLine;DelLine;DelLine;
End;
Until Enter;
{Ввод значений функции вузлах}
GoToXY(35,i+3);
Write('Y(',Mat_x[i]:5:2,')=');
Readln(Mat_f[i]);
End;
{Сортировка узлов повозрастанию}
For i:=1 To Number Do
For j:=i ToNumber Do
If (Mat_x[j]
Begin
Swap(Mat_x[j],Mat_x[i]);
Swap(Mat_f[j],Mat_f[i]);
End;
End;{Vvod}
{Распечатка полинома}
PROCEDUREPrint_Polinom(N:Integer;Cx:Matrix_Line);
Var i:Integer;
c:Char;
Begin
Writeln;
Writeln('Полином Ньютона:');
Write('P',N-1,'(x)=');
For i:=N DownTo 1 Do
If Round(Cx[i]*1000)0 Then{Если в числе не более 3х нулей послезапятой,}
Begin {тогда выводим его на экран}
If(Cx[i]
Write(ABS(Cx[i]):5:3);
If (i>2)Then Write('·x^',i-1) Else
If (i>1)Then Write('·x')
End;
Writeln;
Writeln;
Writeln('Нажмите `ESC` для выхода или любую клавишу для вычисления значенияполинома');
c:=Readkey;
GoToXY(1,WhereY-1);
DelLine;DelLine;
Ifc#27 Then Calculat(N,Cx);
End;{Print_Polinom}
PROCEDURERecover(Current,Number:byte; Var Result,Mat_X:Matrix_Line);
{Восстановлениекоэффициентов полинома по его корням}
VarProcess,i,j,k:Integer;
Begin
{Заносим первый линейныймножитель вида (X — Cn) в Result}
k:=2; {Количество коэффициентов в Result = 2}
If Current1 Then {Еслиисключаем не Х1, то Result[1] = X1}
Begin
Result[1]:=-Mat_X[1];
Process:=2 {Начнем обработку со второгомножителя}
End
Else Begin {Иначе Result[1] = X2}
Result[1]:=-Mat_X[2];
Process:=3 {Начнем обработку с третьегомножителя}
End;
Result[2]:=1; {В любом случае Result[2] = 1, т.к. все множители вида (X — Cn) }
For i:=ProcessTo Number Do
IfiCurrent Then
Begin
For j:=kDownTo 1 Do {Домнoжаем полученный полином на X}
Result[j+1]:=Result[j];
Result[1]:=0; {Поэтому C0 = 0}
For j:=1 To k Do {Домнoжаемполученный полином на Cn = -X[n]}
Result[j]:=Result[j]-Mat_X[i]*Result[j+1];
Inc(k); {Размерность полинома увеличилась}
End;
End; {Recover}
PROCEDURENuton(Number:Byte;Var Mat_x,Mat_f:Matrix_Line);
{Интерполяционная формула Ньютона }
Vari,j:integer;
Temp,Result:Matrix_Line;
C:real;
{Функция вычисленияразделенной разности по начальному и конечному узлам}
FunctionDiv_Res(Beg_Usel,Fin_Usel:Byte;Var Xn,Fn:Matrix_Line):real;
Begin
Beg_Usel:=Beg_Usel+1;
IfBeg_Usel=Fin_Usel Then
Div_Res:=(Fn[Fin_Usel]-Fn[Beg_Usel-1])/(Xn[Fin_Usel]-Xn[Beg_Usel-1])
ElseDiv_Res:=(Div_Res(Beg_Usel,Fin_Usel,Xn,Fn)-Div_Res(Beg_Usel-1,Fin_Usel-1,Xn,Fn))/(Xn[Fin_Usel]-Xn[Beg_Usel-1]);
End; {Div_Res}
Begin {Nuton}
Null(Number,Result);
Null(Number,Temp);
For i:=2 ToNumber Do
Begin
Recover(Number+1,i-1,Temp,Mat_x);
c:=Div_Res(1,i,Mat_x,Mat_f); {Значение разделенной разности 1 и i-го узлов}
For j:=1 To iDo
Result[j]:=c*Temp[j]+Result[j];
End;
Result[1]:=Result[1]+Mat_f[1];
Print_Polinom(Number,Result)
End;{Nuton}
Begin{Main}
Null(Max_Num_Usel,X);
Null(Max_Num_Usel,F); {Начальное обнуление матриц}
Vvod(X,F,Max);
Nuton(Max,X,F);
End.{Main}
3. Пример работы программы
Чтобы проверить правильноли у нас строится полином Ньютона, разложим какую-нибудь известную функцию.Например, y=sin(x) наинтервале Х от 0.1 до 0.9. Полином будем строить по 5 точкам (шаг 0.2). Данныев программу вводим согласно таблице 1.
Таблица 1. Исходныезначения для программы.x y(x) 0.1 0.0998 0.3 0.2955 0.5 0.4794 0.7 0.6442 0.9 0.7833
На инженерномкалькуляторе вычисляем Sin(0.4)=0.3894
Результаты работыпрограммы:
Построениеинтерполяционного полинома Ньютона по значениям функции в узлах
Введите кол-во узловинтерполяции (0
Значения узлов не должнысопадать
Введите значения узлов изначения функций в них:
X(0)=0.1 Y(0.10)=0.0998
X(1)=0.3 Y(0.30)=0.2955
X(2)=0.5 Y(0.50)=0.4794
X(3)=0.7 Y(0.70)=0.6442
X(4)=0.9 Y(0.90)=0.7833
Полином Ньютона:
P4(x)= + 0.018·x^4 — 0.181·x^3 + 0.005·x^2 + 0.99
/>
Рисунок 11. Результатработы программы Polinom
Вычисление значенийинтерполяционного полинома:
Введите значение x:
0.4
Значение полинома в точкеXo= 0.4000 равно Yo= 0.3894
/>
Рисунок 12. Результатвычисления значения полинома
Заключение
Появление и непрерывноесовершенствование ЭВМ привело к революционному преобразованию науки вообще иматематики в особенности. Изменилась технология научных исследований,увеличились возможности теоретического изучения, прогноза сложных процессов,проектирования инженерных конструкций. Но более сложные расчёты требуют и болееглубокого знакомства с численными методами. Численные методы носят в основномприближённый характер, позволяя, тем не менее, получить окончательный числовойрезультат с приемлемой для практических целей точностью.
Выполняя курсовую работу,я познакомилась с понятием интерполяция, укрепила свои знания впрограммировании на языке Turbo Pascal и при оформлении курсовой работыполучила практические навыки при работе в пакетах Microsoft Word и MicrosoftVisio.