Быстрый поиск

Реферат: Аппроксимация

Министерство общего и профессионального образования Российской Федерации

Московский Государственный Строительный Университет

Кафедра информатики и прикладной математики

КУРСОВАЯ РАБОТА ПО ИНФОРМАТИКЕ

на темы:

1. Аппроксимация.

2. Разработка модуля исключения нуль-уравнений в комплексе “Решение задачи линейного программирования”.

Выполнил студент ЭОУС – I – 2: Моносов А. Л.

Преподаватель: доцент Марьямов А. Г.

Москва 1999.

Оглавление.

I. Математическая часть. Название…………………………………3.

1.1 Постановка задачи………………………………………………….3.

2.1 Изложение метода………………………………………………….4.

3.1 Блок-схема алгоритма. Описание исходных данных и результатов………………………………………………………………5.

4.1 Листинг программы, исходных данных и результатов……………6.

5.1 Список переменных основной программы………………………10.

6.1 Заголовки процедур и функций. Список их переменных……….10.

7.1 Ручной расчет……………………………………………………..11.

8.1 Обсуждение результатов с целью доказательства правильности алгоритма и программы………………………………………………..12.

9.1 Выводы…………………………………………………………….13.

II. Экономическая часть. Название………………………………..14.

1.2 Постановка задачи линейного программирования и задание на разработку модуля……………………………………………………...14.

2.2 Описание исходных данных и результатов решения задач линейного программирования………………………………………...18.

3.2 Описание модуля типов…………………………………………..19.

4.2 Укрупненная блок-схема задачи линейного программирования..20.

5.2 Параметры и заголовки процедур задачи линейного программирования……………………………………………………..21.

6.2 Блок-схема и параметры реализованной процедуры……………21.

7.2 Листинг модуля, исходных данных и результатов машинного расчета………………………………………………………………….23.

8.2 Ручной расчет задачи линейного программирования…………...24.

9.2 Выводы…………………………………………………………….26.

Список использованной литературы. ……………………………..27.

I. Математическая часть. Аппроксимация.

1.1 Постановка задачи.

Пусть величина y является функцией аргумента x. Это означает, что любому значению x из области определения поставлено в соответствии значение y. Вместе с тем на практике часто неизвестна явная связь между y и x, т.е. невозможно записать эту связь в виде y=f(x). В некоторых случаях даже при известной зависимости y=f(x) она настолько громоздка (например, содержит трудно вычисляемые выражения, сложные интегралы и т.п.), что ее использование в практических расчетах затруднительно.

Наиболее распространенным и практически важным случаем, когда вид связи между параметрами x и y неизвестен, является задание этой связи в виде некоторой таблицы {xi yi}. Это означает, что дискретному множеству значений аргумента {xi} поставлено в соответствие множество значений функции {yi} (i=0,1…n). Эти значения - либо результаты расчетов, либо экспериментальные данные. На практике нам могут понадобиться значение величины y и в других точках, отличных от узлов xi. Однако получить эти значения можно лишь путем очень сложных расчетов или провидением дорогостоящих экспериментов.

Таким образом, с точки зрения экономии времени и средств мы приходим к необходимости использования имеющихся табличных данных для приближенного вычисления искомого параметра y при любом значении (из некоторой области) определяющего параметра x, поскольку точная связь y=f(x) неизвестна.

Этой цели и служит задача о приближение (аппроксимации) функций: данную функцию f(x) требуется приближенно заменить (аппроксимировать) некоторой функцией g(x) так, чтобы отклонение (в некотором смысле) g(x) от f(x) в заданной области было минимальным. Функция g(x) при этом называется аппроксимирующей.

Для практики весьма важен случай аппроксимации функции многочленом:

g(x)=a0+a1x+a2x2+…+amxm (2.1)

При этом коэффициенты aj будут подбираться так, чтобы достичь наименьшего отклонения многочлена от данной функции.

Если приближение строиться на заданном множестве точек {xi}, то аппроксимация называется точечной. К ней относятся интерполирование, среднеквадратичное приближение и др. При построении приближения на непрерывном множестве точек (например, на отрезке [a,b] аппроксимация называется непрерывной или интегральной).

2.1 Изложение метода (Точечная аппроксимация).

Одним из основных типов точечной аппроксимации является интерполирование. Оно состоит в следующем: для данной функции y=f(x) строим многочлен (2.1), принимающий в заданных точках xi те же значения yi, что и функция f(x), т.е. g(xi)=yi, i=0,1,…n.

При этом предполагается, что среди значений xi нет одинаковых, т.е. xi¹xk при этом i¹k. Точки xi называются узлами интерполяции, а многочлен g(x) - интерполяционным многочленом.

Рис. 1

Таким образом, близость интерполяционного многочлена к заданной функции состоит в том, что их значения совпадают на заданной схеме точек (рис.1, сплошная линия).

Максимальная степень интерполяционного многочлена m=n; в этом случае говорят о глобальной интерполяции.

При большом количестве узлов интерполяции получается высокая степень многочлена (2.1) в случае глобальной интерполяции, т.е. когда нужно уметь один интерполяционный многочлен для всего интервала изменения аргумента. Кроме того, табличные данные могли быть получены путем измерений и содержать ошибки. Построение аппроксимируемого многочлена с условием обязательного прохождения его графика через эти экспериментальные точки означало бы тщательное повторение допущенных при измерениях ошибок. Выход из этого положения может быть найден выбором такого многочлена, график которого проходит близко от данных точек (рис.1, штриховая линия).

Одним из таких видов является среднеквадратичное приближение функции с помощью многочлена (2.1). При этом m £ n; случай m = n соответствует интерполяции. На практике стараются подобрать аппроксимирующий многочлен как можно меньшей степени (как правило, m=1, 2, 3).

Мерой отклонения многочлена g(x) от заданной функции f(x) на множестве точек (xi,yi) (i=0,1,…,n) при среднеквадратичном приближении является величина S, равная сумме квадратов разности между значениями многочлена и функции в данных точках:

S = å[g(xi)-yi]2

i=0

Для построения аппроксимирующего многочлена нужно подобрать коэффициенты a0, a1,…,am так, чтобы величина S была наименьшей. В этом состоит метод наименьших квадратов.

dS/da1=2å[ g(xi)-yi]2*1=0;

i=1

dS/da2=2å[ g(xi)-yi]2*xi=0;

i=1

…

dS/dam+1=2å[ g(xi)-yi]2*xim=0.

i=1

C A B

å xi

…

å xim

åyi

=

å xi

å xi2

…

å xim+1

åyixi

…

……

…

……

…

å xim

å xim+1

…

å xi2m

am+1

åyixim

3.1 Блок-схема алгоритма. Описание исходных данных и результатов.

i=1

i=n

Исходные данные, а именно:

m-число узлов аппроксимации.

n - степень аппроксимирующего многочлена.

X - вектор узлов аппроксимации.

Y - вектор значений аппроксимируемой функции.

Все эти значения мы заносим в файл jan.dat, который работает только на чтение и файловой переменной является f1.

Результаты:

Все результаты выводятся в файл jan.res, работающий на запись и имеющий файловую переменную f2.

Первоначально в этот файл выводятся исходные данные, которые берутся из файла jan.dat, но при этом уже с описанием, то есть не просто числа, а скоментарием, что они означают.

Затем выводятся результаты вычисления, проведенной машиной, при этом все результаты отформатированы:

Выводится матрица С системы линейных уравнений для аппроксимации вместе с вектором правых частей. Затем выводится решение этой системы уравнений, что является вектором коэффициентов аппроксимирующего многочлена по возрастанию степени. И в конце выводится вектор погрешности аппроксимации Z.

4.1 Листинг программы, исходных данных и результатов.

program approx;

uses crt,gausstpu;

const nm=20;

type vect1=array[1..nm] of real;

var c:matr;

a,b:vect;

x,y,z:vect1;

n,i,j,m:integer;

f1,f2:text;

procedure Create_BC(n,m:integer; var x,y:vect1; var c:matr; var b:vect);

var i,j:integer;

r:vect;

begin

for i:=1 to n do

r[i]:=1;

for j:=1 to m+1 do begin

c[1,j]:=0;

b[j]:=0;

for i:=1 to n do begin

c[1,j]:=c[1,j]+r[i];

b[j]:=b[j]+r[i]*y[i];

end;

for i:=1 to n do

r[i]:=r[i]*x[i];

end;

for i:=1 to m do begin

for j:=1 to m do

c[i+1,j]:=c[1,j+1];

c[i+1,m+1]:=0;

for j:=1 to n do

c[i+1,m+1]:=c[i+1,m+1]+r[j];

for j:=1 to n do

r[j]:=r[j]*x[j];

end;end;

begin

assign(f1,'jan.dat');reset(f1);

assign(f2,'jan.res');rewrite(f2);

readln(f1,n);writeln(f2,'Число узлов аппроксимации n=',n:3);

readln(f1,m);writeln(f2,'Степень многочлена m=',m:2);

writeln(f2,'Вектор узлов аппроксимации x[i]');

for i:=1 to n do begin

read(f1,x[i]);

write(f2,x[i]:4:2,' ');

end;

writeln(f2);

writeln(f2,'Вектор значений аппроксимируемой функции y[i]');

for i:=1 to n do begin

read(f1,y[i]);

write(f2,y[i]:4:2,' ');

end;

Create_BC(n,m,x,y,c,b);

writeln(f2);

writeln(f2,'Матрица системы линейных уравнений для аппроксимации и вектор правых частей);

for i:=1 to m+1 do begin

for j:=1 to m+1 do

write(f2,c[i,j]:8:1);writeln(f2,b[i]:8:1);end;

gauss(m+1,c,b,a);

for i:=1 to n do begin

z[i]:=0;

for j:=m+1 downto 1 do

z[i]:=z[i]*x[i]+a[j];

z[i]:=z[i]-y[i];end;

writeln(f2);

writeln(f2,'Вектор коэфициентов аппроксимирующего многочлена по возрастанию);

writeln(f2,'степени (m+1 элементов)');

for i:=1 to m+1 do

writeln(f2,'a[',i:1,']=',a[i]:6:2);

writeln(f2,'Вектор погрешности аппроксимации в узлах X);

for i:=1 to n do

writeln(f2,'z[',i:1,']=',z[i]:5:3);

close(f1);close(f2);

end.

Исходный файл jan.dat:

1 6 0 3 8 2 12 9 2 5

9 4 13 7 3 9 3 1 4 2

Файл результатов jan.res:

Число узлов аппроксимации n=10

Степень многочлена m=2

Вектор узлов аппроксимации x[i]

1.00 6.00 0.00 3.00 8.00 2.00 12.00 9.00 2.00 5.00

Вектор значений аппроксимируемой функции y[i]

9.00 4.00 13.00 7.00 3.00 9.00 3.00 1.00 4.00 2.00

Матрица системы линейных уравнений для аппроксимации и вектор правых частей

10.0 48.0 368.0 55.0

48.0 368.0 3354.0 159.0

368.0 3354.0 33428.0 1023.0

Вектор коэфициентов аппроксимирующего многочлена по возрастанию степени (m+1 элементов)

a[1]= 11.66

a[2]= -2.31

a[3]= 0.13

Вектор погрешности аппроксимации в узлах X

z[1]=0.479

z[2]=-1.381

z[3]=-1.343

z[4]=-1.070

z[5]=-1.247

z[6]=-1.430

z[7]=-0.244

z[8]=0.723

z[9]=3.570

z[10]=1.454

5.1 Список переменных основной программы.

В основной программе используются раздел констант и типов:

const nm=20;

type vect1=array[1..nm] of real;

Следующие переменные так же используются в программе, которые описываются в разделе var:

*Переменная*	*Тип переменной*	*Описание переменной*
С	matr	Матрица системы линейных уравнений для аппроксимации
А	vect	Вектор коэфициентов аппроксимирующего многочлена по возрастанию степени (m+1 элементов)
Х	vect1	Вектор узлов аппроксимации
B	vect	Вектор правых частей
Y	vect1	Вектор значений аппроксимирующей функции
Z	vect	Вектор погрешности аппроксимации в узлах Х
n	integer	Число узлов аппроксимации
m	integer	Степень многочлена
i	integer	Необходима для нумерации элементов массивов.
j	integer	Необходима для нумерации элементов массивов.
f1	text	Файловая переменная для файла исходных значений
f2	text	Файловая переменная резуртирующего файла