Козенко, Галанина Информатика_ч1

Министерство образования и науки российской федерации

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

ИНФОРМАТИКА

Методические указания к выполнению курсовой работы

ч.1

Санкт-Петербург 2014

Составители: канд. техн. наук С.Л. Козенко, канд. техн. наук В.А. Галанина Рецензент: канд. техн. наук И.Н. Лукъяненко

Приводятся методические указания к выполнению курсовой работы по дисциплинам «Информатика» и «Информатика и программирование» для студентов, обучающихся по следующими направлениям и специальностям: 16110165, 20010062, 20040062, 20100062, 21040062, 2217062, 23070062, 280762, 2800062.

Могут быть полезны для студентов других направлений и специальностей. Приведенные материалы соответствуют ФГОС и рабочим программам дисциплин соответствующих направлений и специальностей.

Дано описание основных принципов выполнения курсовой работы, приведены математическое описание поставленной задачи и соответствующие схемы алгоритмов.

Подготовлены к публикации кафедрой прикладной математики и рекомендованы к изданию редакционно– издательскимсоветомСанкт–Петербургскогогосударственного университета аэрокосмического приборостроения.

В авторской редакции Компьютерная верстка Ю.А.Гайнутдинова

Подписано к печати 14. Формат 60×84 1/16. Бумага офсетная. Усл. печ. л. . Уч.-изд. л.

Тираж 100 экз. Заказ №.

Редакционно-издательский центр ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

©Санкт-Петербургский государственный университет аэрокосмического

приборостроения (ГУАП), 2014

ПРЕДИСЛОВИЕ

Курсовая работа является завершающим этапом изучения дисциплин «Информатика» и «Информатика и программирование» и ее цель – закрепление навыков алгоритмизации и программирования, полученных студентами при изучении этих дисциплин.

Выполнение курсовой работы требует от студента:

а) практического освоения типовых вычислительных методов прикладной математики;

б) совершенствования навыков разработки алгоритмов и построения программ на языке высокого уровня;

в) использование принципов модульного программирования и совершенствование техники использования подпрограмм;

Практическое выполнение курсовой работы предполагает решение типовых инженерных задач обработки данных с использованием методов матричной алгебры, решение систем линейных алгебраических уравнений.

Тематика курсовой работы связана с решением задачи аппроксимации (приближенного представления) зависимости между величинами X и Y, полученной экспериментальным путем, с помощью известных функций или их комбинаций, подобранных надлежащим образом. Эта зависимость может быть задана значениями в отдельных точках (xi, yi), либо некоторой функцией y = f(x), заданной на интервале [a, b].

Врамках курсовой работы рассматривается первый случай задания зависимости между величинами X и Y, который имеет место

втакой практической области, как технические измерения.

Входе выполнения курсовой работы студенту необходимо рассчитать параметры аппроксимирующей функции в соответствии

скритерием метода наименьших квадратов (МНК), оценить качество полученной аппроксимации для контрольного (тестового)

3

задания, составить алгоритм и написать программу решения поставленной задачи и сравнить результаты по заданному тестовому примеру.

В методических указаниях приводятся описания математических методов и соответствующих алгоритмов для решения поставленной задачи. При этом учитывается, что практическая реализация схем алгоритмов будет осуществляться в среде программирования C. Приведенные в методических указаниях схемы алгоритмов выполнены в соответствии с требованиями ГОСТ [1].

Навыки, приобретенные в процессе выполнения курсовой работы, являются основой для использования вычислительных методов прикладной математики и техники программирования в процессе изучения последующих дисциплин, а также при выполнении курсовых и дипломных проектов.

4

1. Методические рекомендации по аппроксимации функции методом наименьших квадратов

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

Постановка задачи аппроксимации в общем виде выглядит следующим образом [2, 6].

Пусть проводится ряд измерений, цель которых – исследование зависимости некоторой физической величины Y от другой физической величины X.

Предполагается, что величины X и Y связаны функциональной зависимостью. Вид этой зависимости требуется определить исходя из результатов измерений, причем число этих измерений n невелико (табл. 1.1).

					Таблица 1.1
i	1	2	3	…	n
xi	x1	x2	x3	…	xn
yi	y1	y2	y3	…	yn

В табл. 1.1: i – номер измерения, xi – значение аргумента, yi – значение функции (i = 1, …, n). По данным таблицы можно построить график зависимости Y от X (рис. 1.1). На графике отдельные точки соответствуют значениям yi в точках xi (i = 1,..., n).

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

y

yn

(xi, yi)

ϕ(x)

yi

δi

y2

y1

x

xi

xn

x2

x1

Рис.1.1 Задание Y на дискретном множестве значений X

5

ловых параметров C1, C2, …, Cm. Требуется определить такие значения этих параметров (C1*, C2*, …, Cm*), чтобы кривая y = φ(x, C1*, C2*, …, Cm*)

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

Наиболее применимым на практике для решения таких задач является метод наименьших квадратов (МНК), при котором требование согласования кривой y = φ(x) и экспериментальных точек сводится к тому, чтобы сумма квадратов отклонений (δi) значений yi от значений аппроксимирующей функции в соответствующих точках ϕ(xi) (i = 1, …, n) обращалась в минимум (рис.1.1).

Запишем требование МНК аналитически

n	n
J=å(δi)2	= min (å (yi -φ (xi,C1,C2,...,Cm)2).	(1.1)
i=1	i=1

Выражение (1.1) определяет критерий выбора аппроксимирующей функции.

1.2. Методика выбора аппроксимирующей функции

Аппроксимирующую функцию φ(x)

j(x) = j (x, C1, C2, …, Cm),

(1.2)

выбирают из некоторого семейства функций, для которого задан вид функции, но неизвестны и подлежат определению ее параметры

С1, С2, …, Сm.

Определение аппроксимирующей функции φ(x) подразделяется на два основных этапа:

−подбор подходящего вида функции φ(х);

−нахождение параметров функции φ(х) в соответствии с кри-

терием МНК.

Подбор вида функции φ(х) представляет собой сложную задачу, решаемую методом проб и последовательных приближений. Исходные данные, представленные в графической форме, сопоставляются c семействами графиков ряда типовых функций, используемых обычно для аппроксимации. Более подробные сведения о функциях, которые могут

быть использованы в задачах аппроксимации, можно найти в [2]. После того как выбран вид аппроксимирующей функции φ(х)

и, следовательно, определена функциональная зависимость (1.2),

6

необходимо найти в соответствии с требованиями МНК значения параметров С1, С2, …, Сm.

Как уже указывалось, параметры должны быть определены таким образом, чтобы значение критерия (1.1) было наименьшим.

С учетом (1.2) критерий аппроксимации J, определяемый выражением (1.1) представляется функцией искомых параметров

J = J (С1, С2, …, Сm).

(1.3)

Последующие действия сводятся к отысканию минимума функции J, зависящей от переменных Сk. Определение значений Сk = Сk*, k = 1, 2, …, m, соответствующих этому минимуму J, и является целью решаемой задачи.

Возможны следующие два подхода к решению этой задачи:

−использование известных условий минимума функции нескольких переменных;

−непосредственное отыскание точки минимума функции ка- ким-либо из численных методов.

Для реализации первого из указанных подходов воспользуемся необходимыми условиями минимума функции нескольких переменных [2], в соответствии с которыми в точке минимума должны быть равны нулю частные производные этой функции по всем ее пе-

ременным:	¶J
		=0 (k=1,2,...,m).	(1.4)
	¶C
	k

Полученные m равенств следует рассматривать как систему уравнений относительно искомых значений С1, С2, …, Сm. При произвольном виде функциональной зависимости (1.2) уравнения (1.4) оказываются нелинейными относительно величин Сk, и их решение требует применения приближенных численных методов.

Используемые равенства (1.4) дают лишь необходимые, но не достаточные условия минимума функции (1.3). Поэтому требуется уточнить, обеспечивают ли найденные значения Сk* именно минимум функции J(С1, С2, …, Сm). Однако, поскольку величина J неотрицательна (как сумма квадратов) и нижняя ее граница равна 0, то, если существующее решение системы (1.4) единственно, оно отвечает именно минимуму J. Таким образом, (1.4) является как необходимым, так и достаточным условием минимума функции (1.3).

Уравнения (1.4), используемые в МНК, называются нормальными, поэтому описываемый способ решения задачи будем называть методом нормальных уравнений.

7

Структура этих уравнений получается более простой в том случае, когда аппроксимирующая функция j(x) выбирается линейной функцией искомых параметров Сk и выражение (1.2) имеет вид

m
ϕ(x)=åCk ϕ k(x),	(1.5)

k=1

где Сk – определяемые параметры; ϕ1(x), ϕ2(x), …, ϕm(x) – система ли- нейно-независимых функций, называемых в курсовой работе базисными функциями.

Замечание. Функции ϕ1(x), ϕ2(x), …, ϕm(x) называются линейнонезависимыми, если при любых x равенство

m

åCk ϕk(x)=0, k=1

справедливо только тогда, когда все Сk = 0.

Примеры функций, которые можно использовать в качестве базисных, приведены в табл. 1.2.

Таблица 1.2

Вид функции	Название функции
ϕk(х) (k = 1, …, m)
φ1(х) = x	Линейная
φ2(х) = x2	Параболическая
φ3(x) = 1/x	Обратно–пропорциональная
φ4(x) = loga x	Логарифмическая
φ5(x) = sin(x) и т.д.	Тригонометрические (и обратные к ним)
…

В этом случае, подставляя (1.5) в выражение (1.1) и выполняя дифференцирование в соответствии с (1.4), получим систему уравнений относительно искомых Сk.

Подставим выражение аппроксимирующей функции для m базисных функций

j(x) = С1 ϕ1(x) + С2 ϕ2(x) + … + Сm ϕm(x).

в формулу критерия аппроксимации (1.1).

8

Получим
n	é	ϕ1(xi) -C2	ù	2 .	(1.6)
J=åëyi -C1			ϕ2(xi) -...-Cm ϕm(xi)û

i=1

Применим операцию дифференцирования (1.4) к параметру С1:

n

2å[yi -C1ϕ1(xi) -C2ϕ2(xi) -...-Cmϕm(xi)](-ϕ1(xi)=0, i=1

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

n	n	n
C1åϕ1(xi) ϕ1(xi)+...+Cmåϕ1(xi)ϕm(xi) = åyi ϕ1(xi) .
i=1	i=1	i=1

Аналогичные уравнения можно получить, применяя описанные выше действия по отношению к переменным С2, …, Сm. Эти уравнения образуют систему нормальных уравнений:

a11 С1 + a12 С2 + … + a1m Сm = b1 a21 С1 + a22 С2 + … + a2m Сm = b2 ,

.....................................................

am1 С1 + am2 С2 + … + amm Сm = bm

(1.7)

где коэффициенты akl и величины bk (k, l = 1, 2, …, m) определяются выражениями

n	n
akl =åϕk(xi ) ϕl(xi ) ,	bk=åyi ϕk(xi ) .	(1.8)
i=1	i=1

Уравнения (1.7) представляют собой систему линейных алгебраических уравнений, основные методы решения которых описываются в разделах 2 и 3.

Систему m линейных уравнений вида (1.7) можно записать посредством матричных обозначений в следующем виде:

A × C = B, где

é

a

a

...

a

ù

é

C

ù

é

b

ù

ê

11

12

...

1m ú

ê

1

ú

ê

1

ú

ê

a

21

a

a

ú

ê

C

ú

,

ê

b

ú

(1.9)

A=ê

22

2m ú

, C=ê

2

ú

B=ê

2

ú .

ê

...

ú

ê

ú

ê

ú

ê ... ...

... ú

ê ...

ú

ê ...

ú

êa

a

...

a

ú

êC

ú

êb

ú

ê

m1

m2

mmú

ê

mú

ê

mú

ë

û

ë

û

ë

û

9

Квадратная матрица A называется матрицей системы, вектор

C – вектором-столбцом неизвестных системы, а вектор B – векто- ром-столбцом свободных членов.

В матричном представлении исходная система линейных уравнений примет вид:

é

a

a

...

a

ù

é

C

ù

é

b

ù

ê

11

12

...

1m ú

ê

1

ú

ê

1

ú

ê

a

21

a

a

ú

ê

C

ú

=

ê

b

ú

(1.10)

ê

22

2m ú

´ ê

2

ú

ê

2

ú.

ê

...

...

ú

ê

ú

ê

ú

ê ... ...

ú

ê ...

ú

ê ...

ú

êa

a

...

a

ú

êC

ú

êb

ú

ê

m1

m2

mmú

ê

mú

ê

mú

ë

û

ë

û

ë

û

Решение системы линейных уравнений сводится к отысканию значений элементов вектора-столбца С, называемых корнями системы. Для получения единственного решения системы, входящие в нее m уравнений должны быть линейно независимыми. Необходимым и достаточным условием этого является неравенство нулю определителя данной системы, то есть det A ≠ 0.

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

10