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

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

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

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

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

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

на темы:

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. Постановка задачи.

Пусть величина 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, равная сумме квадратов разности между значениями многочлена и

функции в данных точках:

n

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

i=0

Для построения аппроксимирующего многочлена нужно подобрать коэффициенты

a0, a1,…,am так, чтобы величина S была наименьшей. В этом состоит метод

наименьших квадратов.

n

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

i=1

n

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

i=1

…

n

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

i=1

C

A B

|n |( xi |… |( xim | |a1 | |(yi |

|( xi |( xi2 |… |( | |a2 | |(yixi |

| | | |xim+1 | | | | |

|… |…… |… |…… | |… | |… |

|( xim|( |… |( xi2m| |am+1| |(yixim|

| |xim+1 | | | | | | |

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

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

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:

10

2

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 |Файловая переменная резуртирующего |

| | |файла |

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

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

операторе uses и процедуры:

Crt - стандартный модуль подключения экрана и клавиатуры для работы с

программой.

Gauss - процедура решения системы линейных уравнений методом Гаусса. Она

берется из модуля Gausstpu, где интерфейсная часть имеет вид:

Interface

Const nmax=20

Type

Поэтому при объявлении матрицы С ссылаться надо на matr, а векторов A и B

на vect.

Create_BC - процедура расчета матрицы С (С - матрица системы линейных

уравнений для аппроксимации). Заголовок этой процедуры выглядит так:

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

var i,j:integer;

r:vect;

А вот такие переменные используются только в этой процедуре, остальные

засылаются из основной программы:

|Переменная |Тип |Описание переменной |

| |переменной | |

|i |integer |Используются в циклах для перебора |

| | |численных значений |

|j |integer |Используются в циклах для перебора |

| | |численных значений |

|R |vect |Рабочий вектор |

7.1 Ручной счет.

Составляем матрицу системы уравнений по следующему принципу:

|n |(xi |(xi2|(yi |

|(xi |(xi2|(xi3|(xiyi|

|(xi2 |(xi3|(xi4|(xi2y|

| | | |i |

Для этого вычисляем необходимые значения:

n=10;

(xi=1+6+0+3+8+2+12+9+2+5=48;

(xi2=12+62+02+32+82+22+122+92+22+52=368;

(yi=9+4+13+7+3+9+3+1+4+2=55;

(xi3=13+63+03+33+83+23+123+93+23+53=3354;

(xiyi=1*9+6*4+0*13+3*7+8*3+2*9+12*3+9*1+2*4+5*2=159;

(xi3=14+64+04+34+84+24+124+94+24+54=33428;

(xi2yi=12*9+62*4+02*13+32*7+82*3+22*9+122*3+92*1+22*4+52*2=1023.

Получается следующая матрица:

|10 |48 |368 |55 |

|48 |368 |3354 |159 |

|368 |3354 |33428 |1023|

Которая эквивалентна такой системе уравнений:

10a1 + 48a2 + 368a3 = 55

48a1 + 368a2 + 3354a3 = 159

368a1 + 3354a2 + 33428a3 = 1023

Мы решаем эту систему уравнений методом Гаусса:

|10 |48 |368 |55 |

|0 |137,6 |1587,6 |-105 |

|0 |1587,6|19885,6 |-1001 |

|10 |48 |368 |55 |

|0 |137,6|1587,6 |-105 |

|0 |0 |1568,203488|210.4680233 |

Получаем упрощенную систему уравнений:

1568,203488a3 = 210,4680233

137,6a2 + 1587,6a3 = -105

10a1 + 48a2 + 368a3 = 55

Решая которую получаем следующие окончательные значения, которые

являются ответом:

a3=210,4680233/1568,203488=0,134209638

a2=(-105-1587,6 a3)/137,6=-2,311564115

a1=(55-48a2-368a3)/10=11,65659307

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

программы.

Полученные результаты показывают, что алгоритм и программа составлены

верно, так как значения полученные при ручном счете близки к машинным

вычислением.

9.1 Выводы.

Данная программа очень эффективна, так как машина выполняет все действия

гораздо быстрее, чем человек при ручном счете. Так же во время ручного

счета могут произоити ошибки, что приведет к повторному перещитыванию, а у

машины, при правильном алгоритме, таких сбоев не бывает (если только

"зависает"). Следовательно эта программа во многом облегчает жизнь

человеку.

II. Экономическая часть. Разработка модуля исключения нуль-уравнений в

комплексе “Решение задачи линейного программирования”.

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

модуля.

Рассмотрим задачу оптимального планирования производства [1]. Пусть

Страницы: 1, 2