2.2. Интерполяционная формула Ньютона
Если точки x0, x1, ..., xn расположены на равных расстояниях (xk = x0 +
kh), многочлен Pn(x) можно записать так:
0x01 graphic
(здесь x0 + th = х, а Dk — разности k-го порядка: Dk yi = Dk — 1 yi +1 —
Dk — 1yi).
Это так называемая формула Ньютона для интерполирования вперёд; название
формулы указывает на то, что она содержит заданные значения у,
соответствующие узлам интерполяции, находящимся только вправо от x0. Эта
формула удобна при интерполировании функций для значений х, близких к x0.
При интерполировании функций для значений х, близких к наибольшему узлу
хn, употребляется сходная формула Ньютона для интерполирования назад. При
интерполировании функций для значений x, близких к xk, формулу Ньютона
целесообразно преобразовать, изменив начало отсчёта.
Формулу Ньютона можно записать и для неравноотстоящих узлов, прибегая для
этой цели к разделённым разностям. В отличие от формулы Лагранжа, где
каждый член зависит от всех узлов интерполяции, любой k-й член формулы
Ньютона зависит от первых (от начала отсчёта) узлов и добавление новых
узлов вызывает лишь добавление новых членов формулы (в этом преимущество
формулы Ньютона).
2.3. Тестовый пример
Для функции заданной в таблице построить первый интерполяционный член и
вычислить по нему приближенно значение в точке х=2.98
+-----------------------------------------------------------------------------------------------+
| X[i | ]2.95 | 2.97 | 2.99 | 3.01 | 3.03 | 3.05 | 3.07 | 3.09 | 3.11 | 3.13 |
|-----+---------+--------+--------+--------+--------+--------+--------+-------+--------+--------|
|]Y[i | 113.84 | 119.68 | 106.28 | 120.68 | 107.43 | 114.88 | 115.53 | 117.4 | 120.21 | 118.74 |
+-----------------------------------------------------------------------------------------------+
X=2.98
+--------------------------------------------------------------------------------------------------------------------------------------------+
|X[i |Y[i |Deltay[i |Delta^2y[i |Delta^3y[i |Delta^4y[i |Delta^5y[i |Delta^6y[i |Delta^7y[i |Delta^8y[i |Delta^9y[i |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|]2.95 |]113.84 | | | | | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |]5.82 | | | | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|2.97 |119.68 | |]-19.2 | | | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |-13.82 | |]46.98 | | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|2.99 |106.28 | |27.78 | |]-102.4 | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |14.4 | |-55.4 | |]206.19 | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|3.01 |120.68 | |-27.6 | |103.78 | |]-385.8 | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |-13.2 | |48.35 | |-179.6 | |]675.8 | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|3.03 |107.43 | |20.7 | |-75.85 | |291 | |]-1121 | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |7.45 | |-27.5 | |11.37 | |-446 | |]1170 |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|3.05 |114.88 | |-6.8 | |35.52 | |-155.1 | |648.3 | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |0.65 | |8.02 | |-43.79 | |202.1 | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|3.07 |115.53 | |1.22 | |-8.27 | |47 | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |1.87 | |-0.25 | |3.21 | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|3.09 |117.4 | |0.97 | |-5.05 | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |2.84 | |-5.31 | | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|3.11 |120.21 | |-4.34 | | | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
| | |-1.5 | | | | | | | | |
|-------+--------+-----------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------|
|3.13 |118.74 | | | | | | | | | |
+--------------------------------------------------------------------------------------------------------------------------------------------+
X[0]=2.97 , h=0.02
q=x-x[0]/h=2.98-2.97/0.02=0.01/0.02=0.5
y(x)=y[0]+qDeltay+q)q-1)/2!*Delta^2y[0]+q(q-1)(q-2)/3!*Delta^2y[0]+…+q(q-1)…(q…n+1)/n!*Delta^ny[0
]y(2.98)=119.66+0.5(-13.38)+0.5(0.5-1)/1*2*27.78+0.5(0.5-1)(0.5-2)/1*2*3*(-55.43)+0.5(0.05-1)(0.5-2)(0.5-3)/1*2*3*4*103.78+0.5(0.5-1)(0.5-2)(0.5-3)(0.5-4)/1*2*3*4*5*(-179.63)+
0.5(0.5-1)(0.5-2)(0.5-3)(0.5-4)(0.5-5)/1*2*3*4*5*6*291+0.5(0.5-1)(0.5-2)(0.5-3)(0.5-4)(0.5-5)(0.5-6)/1*2*3*4*5*6*7*(-446.16)+0.5(0.5-1)(0.5-2)(0.5-3)(0.5-4)(0.5-5)(0.5-6)(0.5-7)/1*2*3*4*5*6*7*8*648.32=75.422
2.4. Разработка алгоритма и программы вычисления функции в приложении 2.1
Заключение
Удалось разработать программу решения нелинейных и трансцендентных
уравнений методом секущих - хорд. Программа включает и учитывает многие
новые возможности в программировании и практике создания программ в среде
программирования С.
В процессе создания программы и последующего тестирования было устранено
большинство ошибок при трансляции, запуске и использовании программного
продукта, поэтому данная программа, реализующая алгоритм решения системы
линейных уравнений методом секущих - хорд, вполне может быть применена в
более крупных проектах по реализации нескольких математических методов
решения тех или иных задач. Интерфейс программы удобен и элементарно прост
в обращении даже для тех, кто в первый раз имеет дело с подобным типом
программ.
Список литературы
1. Архангельский Н.А. Вычислительные методы алгебры в приемах и задачах.
М.: МАИ, 1976.
2. Васильев Ф.П. Численные методы решения экстремальных задачь. М.:
Наука,1988.
3. Васильков Ф.В., Василькова Н.Н. Компьютерные технологии вычислений в
математическом моделировании: Учеб. Пособие. М.: Финансы и статистика,
1999.
4. Фильчаков П.Ф., Справочник по высшей математике. Киев: Наукова думка,
1974.
5. Фильчаков П.Ф., Численные методы. Киев: Наукова думка, 1976.
6. Большая математическая энциклопедия. М.: Олма-Пресс, 2004
7. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.:
Наука, 1970.
8. Тихонов А.Н., Вводные лекции по прикладной математике. М.: Наука,
1984.
9. Калиткин Н.Н., Численные методы. М.: Наука, 1987.
10. Корн Г., Корн Т. Справочник по математике. М.: Наука, 1984.
Приложение 1.1.
#include
#include
double f(double x)
{
return 5^x-3*x-5;
}
double findRootChord (double a,
double b,
double eps,
long max_step,
double (&f)(double))
{
double f_a = f(a);
double f_b = f(b);
double xn;
for(long k=0; k<0)
{
a = xn; f_a = f_xn;
}
else
{
b = xn; f_b = f_xn;
}
}
return xn;
}
void main()
{
clrscr();
cout.precision(6);
cout.setf(ios::fixed|ios::showpoint);
double x = findRootChord(-10,1,.0000001,10000,f);
cout<<\"x = \"<<<<\"f(x) = \"<<
#include
float FileFunction()
{ float h;
FILE *in;
in=fopen(\"spisok.txt\",\"r\");
for (;!feof(in);)
{
w_f=(struct files *)malloc(sizeof(struct files));
if(l_f==NULL) {l_f=w_f;}
else {r_f->radr=w_f;}
fscanf(in,\"%f\",&w_f->x);
fscanf(in,\"%f\",&w_f->y);
r_f=w_f;
}w_f=l_f;
fclose(in);
w_f=l_f->radr;
h=(w_f->x)-(l_f->x);
return h;
}
void TableMin()
{
float s,s1,p;
do
{
s=w_f->y;
w_f=w_f->radr;
s1=w_f->y;
p=s1-s;
w_msp=(struct msp *)malloc(sizeof(struct msp));
w_fll=(struct fll *)malloc(sizeof(struct fll));
if(l_msp==NULL){l_msp=w_msp;}
else{r_msp->radr1=w_msp;}
if(l_fll==NULL){l_fll=w_fll;}
else{r_fll->radr2=w_fll;}
w_fll->a=p;r_fll=w_fll;
w_msp->z=p;r_msp=w_msp;
}
while(w_f!=r_f);
w_msp=l_msp;
return;
}
void TableMax()
{
float p,s,s1,i,c;
for(i=1;i<=8;i++)
{c=w_msp->z;
l_msp=NULL;
do
{
s=c;
w_msp=w_msp->radr1;
c=w_msp->z;
s1=w_msp->z;
p=s1-s;
w_fll=(struct fll *)malloc(sizeof(struct fll));
r_fll->radr2=w_fll;
w_fll->a=p;r_fll=w_fll;
r_msp->radr1=w_msp;
if(l_msp==NULL){w_msp->z=p;l_msp=w_msp;}
else{w_msp->z=p;}
}while(w_msp!=r_msp);
r_msp=w_msp;
w_msp=l_msp;
}
return;
}
float UX(float x,float h)
{
float u,u1;
int i=1;
w_f=l_f;
while(w_f!=r_f){w_f=w_f->radr;i++;}
i=(i/2);
for(w_f=l_f;i>=1;i--){w_f=w_f->radr;}
u=(x-(w_f->x))/h;
w_u=(struct u *)malloc(sizeof(struct u));
l_u=w_u;
w_u->u=u;
r_u=w_u;
for(i=1;i<=3;i++)
{
u1=-(i*i-u*u)/((i*2)*((i*2)+1));
u1=u1*(w_u->u);
w_u=(struct u *)malloc(sizeof(struct u));
r_u->uadr=w_u;
w_u->u=u1;
r_u=w_u;
}
return u;
}
float VX(float u)
{
float v1,v,i;
v=1-u;
w_v=(struct v *)malloc(sizeof(struct v));
l_v=w_v;
r_v->vadr=w_v;
w_v->v=v;
r_v=w_v;
for(i=1;i<=4;i++)
{
v1=-(i*i-v*v)/((i*2)*((i*2)+1));
v1=v1*(w_v->v);
w_v=(struct v *)malloc(sizeof(struct v));
r_v->vadr=w_v;
w_v->v=v1;
r_v=w_v;
}
return 1;
}
float Summa()
{
int j,i=1;
float s,s1,p;
w_f=l_f;
w_fll=l_fll;
w_u=l_u;
w_v=l_v;
while(w_f!=r_f){w_f=w_f->radr;i++;}
i=(i/2);
for(w_f=l_f;i>=1;i--){w_f=w_f->radr;}
s=(w_f->y)*(w_v->v);
w_f=w_f->radr;
s1=(w_f->y)*(w_u->u);
w_f=l_f;
while(w_f!=r_f){w_f=w_f->radr;i++;}
i++;
j=i;
do
{
if(i==0){j--;}
i=j;
j=i-1;
i=j;
for(;i>=1;i--){w_fll=w_fll->radr2;}
i=j;
for(i=((i/2)-1);i>=1;i--){w_fll=w_fll->radr2;}
w_v=w_v->vadr;
s=s+(w_fll->a)*(w_v->v);
i=j;
for(i=((i/2));i>=1;i--){w_fll=w_fll->radr2;}
}while(w_fll!=r_fll);
w_fll=l_fll;
w_f=l_f;
while(w_f!=r_f){w_f=w_f->radr;i++;}
j=i;
w_u=l_u;
do
{
j=i;
for(;i>=1;i--){w_fll=w_fll->radr2;}
i=j-1;
for(i=((i/2)+1);i>=1;i--){w_fll=w_fll->radr2;}
w_u=w_u->uadr;
s1=s1+(w_fll->a)*(w_u->u);
i=j-1;
j=0;
i=i-1;
for(i=((i/2));i>=1;i--,j++){w_fll=w_fll->radr2;}
i=j*2;
}while(w_u!=r_u);
p=s1+s;
return p;
}
void main()
{
float p,u,h,x;
l_msp=NULL;l_fll=NULL;l_f=NULL;
w_u=NULL;r_u=NULL;l_u=NULL;
w_v=NULL;r_v=NULL;l_v=NULL;
h=FileFunction();
w_f=l_f;
TableMin();
TableMax();
printf(\"\\n BBEDuTE X=\");
scanf(\" %f\",&x);
u=UX(x,h);
VX(u);
p=Summa();
printf(\"\\nOTBET: %3.4f\",p);
getch();
}
0x08 graphic
0x01 graphic
3
+----+
|x* |
+----+
+-----+
|]x[s |
+-----+
+-------+
|]x[n2 |
+-------+
+-------+
|]x[n1 |
+-------+
+----+
|N |
+----+
+---+
|М |
+---+
+---+
|x |
+---+
+---+
|y |
+---+
+------+
|y = |
|f(x) |
+------+
+---+
|b |
+---+
+---+
|a |
+---+
10
-2
-1
2
1
y=5^x
y=3x-5
B
A
Конец
«OTBET: »
p
p=Summa();
VX(u);
u=UX(x,h);
x
BBEDuTE X=
TableMax();
TableMin();
w_f=l_f;
h=FileFunction();
l_msp=NULL;l_fll=NULL;l_f=NULL;
w_u=NULL;r_u=NULL;l_u=NULL;
w_v=NULL;r_v=NULL;l_v=NULL;
Начало
Начало
Конец
Вывод значения x на печать
Abs(b-x) меньше заданной точности
Расчет следующего значения X= x по формуле:
x=a-f(a)*(b-a)/(f(b)-f(a))
Процедура для расчета значения заданной функции Y = y при значении X = x
Расчёт значения Y = c при некотором значении X = a
Сохранение предыдущего значения x в переменной b
Выбор значения Х = x