Решение систем линейных уравнений по методу Гаусса

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧЕРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. Р.Е.АЛЕКСЕЕВА ИНСТИТУТ РАДИОЭЛЕКТРОНИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ КУРСОВАЯ РАБОТА

«Решение систем линейных уравнений по методу Гаусса»

Выполнила студентка группы С11-РЭС Батюта М. Р Проверил доц. кафедры ИРС Сидоров С. Б Нижний Новгород 2012 г.

1.

Введение

В работе рассматривается решение задачи разработки прикладной программы решение линейных уравнений по методу Гаусса.

Одним из способов преодоления сложности данной задачи является использование технологии разработки программ «сверху-вниз». Этот подход позволяет путем декомпозиции исходной задачи свести ее к последовательному решению более простых задач. Его использование позволяет уменьшить затраты на отладку и повысить надёжность программы. Также существенным моментом технологии «сверху-вниз» является её акцент на повторное использование уже существующих модулей, а не разработку их «с нуля».

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

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

В заключении делаются выводы о полноте решения поставленной задачи, а так же приводится ряд соображений по возможным направлениям доработки программы.

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

алгебраический гаусс видеотека алгоритм

2. Постановка задачи Метод Гаусса при решении системы уравнений можно разделить на два этапа: прямой и обратный ход. Процесс последовательного исключения неизвестных называется прямым ходом метода Гаусса. После завершения прямого хода появляется возможность вычислить неизвестную переменную, находящуюся в последнем уравнении. С ее помощью из предпоследнего уравнения находим следующую неизвестную переменную и так далее. Процесс последовательного нахождения неизвестных переменных при движении от последнего уравнения к первому называется обратным ходом метода Гаусса.

Пусть дана система:

Метод Гаусса состоит в последовательном исключении неизвестных из этой системы. Последовательно умножая первое уравнение на и складывая с i-м уравнение, исключим из всех уравнений кроме первого. Получим систему Аналогичным образом из полученной системы исключим. Последовательно, исключая все неизвестные, получим систему треугольного вида Описанная процедура называется прямым ходом метода Гаусса. Заметим, что ее выполнение было возможно при условии, что все, не равны нулю.

Выполняя последовательные подстановки в последней системе, (начиная с последнего уравнения) можно получить все значения неизвестных.

3. Руководство пользователя Программа предназначена для работы с матрицами размерностью n*n.

Запуск программы осуществляется либо набором в командной строке имени программы Метод Гаусса. exe с последующим нажатием клавиши «Enter» либо другим способом, зависящем от конкретной операционной системы.

После запуска программы на экране появляется информационное сообщение о программе

Enter NUM of equations:

Программа является интерактивным консольным приложением. Весь диалог с пользователем осуществляется в текстовом режиме При вводе недопустимого значения ничего не происходит и программа ждёт ввода правильного значения.

Далее пользователю предлагается ввести коэффициенты при x системы линейных уравнений:

a[%d][%d] =

А так же свободные члены системы линейных уравнений:

b[%d] =

После на экран выводится получившаяся матрица, А и столбец свободных членов В:

See input

Matrix A:

Vector B:

Solving on Gauss method

После линейных преобразований строк на экран выводится преобразованная в ступенчатую матрицу, А и преобразованный столбец свободных членов В.

Forvard Gauss course

Matrix A:

Vector B:

Далее выполняется последовательное нахождение неизвестных х и вывод результата:

Back Gauss course

Results:

После пользователю предлагается ввести символ для продолжения использования программы. При нажатии другого символа программа завершает работу.

4. Руководство программиста

4.1. Структура программы Прикладная программа разработана с использованием принципов модульного программирования. Она является совокупностью взаимодействующих модулей. Модули объединяются в единую программу путем компоновки соответствующих объектных файлов. Структура программы:

1. Main. cpp-головной модуль

2. show_vector.cpp, show_vector.hслужит для вывода столбцом свободных членов. матрицы на экран

3. pryamoi_hod.cpp, pryamoi_hod.h-модуль служит для вывода получившейся матрицы путем линейных преобразований на экран

4. obratni_hod.cpp, obratni_hod.h-модуль служит для нахождения неизвестных и вывода результата на экран

5.

Заключение

В данной работе задача разработки прикладной программы формирования видеотеки была решена с использованием технологии «сверху-вниз». На основании проведенной отладки и испытаний с помощью контрольных примеров можно сделать вывод, что полученная прикладная программа решает поставленную задачу правильно и в полном объеме.

В результате выполнения курсового проекта были разработаны решение простейших задач линейной алгебры. Число этих функций сравнительно невелико, однако можно легко добавить в более сложные функции, построенные на базе уже имеющихся. Программа позволяет работать с матрицами и векторами, элементы которых могут быть любого типа, однако на практике чаще всего используется целый тип и тип чисел с плавающей запятой. Программа написана на языке С++, однако может быть легко переписана на любом из современных языков программирования, так как приведены довольно простые алгоритмы всех компонентных функций. Были максимально предусмотрены всевозможные ошибки, которые могут возникнуть при использовании функций. Особое внимание уделялось разумному выделению памяти подобъекты во время выполнения программы, поэтому все функции были тщательно отлажены. Данные функции могут быть эффективно применены на практике в задачах, требующих операций с матрицами и векторами, а также связанных с решением систем линейных алгебраических уравнений.

6. Список рекомендуемой литературы

1. Керниган, Брайан У., Ритчи, Деннис М. Язык программирования С, 2-е издание.: Пер. с анг.- М.: Вильямс, 2006.

2. С. А. Орлов. Технологии разработки программного обеспечения. Учебное пособие. 2-е изд. — СПб.: Питер, 2003. — 480 с.: ил.

3. Шилдт, Герберт. Полный справочник по С, 4-е издание.: Пер. с анг.- М.: Вильямс, 2005.

4. Борисенко В. В. Основы программирования — Интернет-университет информационных технологий — ИНТУИТ.ру, 328 стр. — 2005 г.

5. Костюкова Н. И., Калинина Н. А. Язык Си и особенности работы с ним — Интернет-университет информационных технологий — ИНТУИТ.ру, 208 стр. 2006 г.

6. Крутицкая Н. И., Тихонравов А. В., Шишкин А. А., Аналитическая геометрия и линейная алгебра с приложениями

7. Приложение

7.1. Основная программа

// main. cpp

// головной модуль приложения

#include //i/o

#include //getch

#include

#include «obratni_hod.h»

#include «pryamoi_hod.h»

#include «show_vector.h»

int main ()

{

int i, j, n;

double **a, *b, *x;

do

{

printf («Enter NUM of equations: «);

scanf («%d» ,&n);

//Выделяем память под матрицу, А и векторы В и Х

a = (double **)malloc (n*sizeof (double));

b = (double *)malloc (n*sizeof (double));

x = (double *)malloc (n*sizeof (double));

for (i = 0; i < n; i++)

{

a[i] = (double *)malloc (n*sizeof (double));

//Ввод a

for (j = 0; j < n; j++)

{

printf («a[%d][%d] = «, i + 1, j + 1);

scanf («%lf» ,&a[i][j]);

}

}

//Ввод b

for (i = 0; i < n; i++)

{

printf («b[%d] = «, i + 1);

scanf («%lf» ,&b[i]);

}

printf («tSee inputrn»);

printf («Matrix A: rn»);

for (i = 0; i < n; i++)

ShowVector (n, a[i]);

printf («Vector B: rn»);

ShowVector (n, b);

printf («tSolving on Gauss methodrn»);

PryamoiHod (n, a, b);

printf («Forvard Gauss coursern»);//Прямой ход

printf («Matrix A: rn»);

for (i = 0; i < n; i++)

ShowVector (n, a[i]);

printf («Vector B: rn»);

ShowVector (n, b);

ObratniHod (n, a, b, x);

printf («Back Gauss coursern»);//Обратный ход

printf («Matrix A: rn»);

for (i = 0; i < n; i++)

ShowVector (n, a[i]);

printf («Vector B: rn»);

ShowVector (n, b);

printf («Results :rn»);

ShowVector (n, x);

printf («Press Y for new inputrn»);

//Чистим память

free ((void *)a);

free ((void *)b);

free ((void *)x);

}

while (toupper (getch ()) == 'Y');

return 0;

}

7.2. Модуль «obratni_hod»

// obratni_hod.h

// интерфейс модуля «obratni_hod.h «

#ifndef obratni_vector_h

#define obratni_vector_h

#include

void ObratniHod (int n, double **a, double *b, double *x);

#endif

// obratni_hod.cpp

// реализация модуля «obratni_hod «

#include «obratni_hod.h»

void ObratniHod (int n, double **a, double *b, double *x)

{

double s = 0;

x[n — 1] = 1.0*b[n — 1]/a[n — 1][n — 1];

for (int i = n — 2, j; 0 <= i; i—)

{

s = 0;

for (j = i + 1; j < n; j++)

{

s = s+a[i][j]*x[j];

}

x[i] = 1.0*(b[i] - s)/a[i][i];

}

}

7.3. Модуль «pryamoi_hod»

// pryamoi_hod.h

// интерфейс модуля «pryamoi_hod.h»

#ifndef pryamoi_hod_h

#define pryamoi_hod_h

#include //i/o

void ShowVector (int n, double * vec);

#endif

// pryamoi_hod.cpp

// реализация модуля «pryamoi_hod»

#include «pryamoi_hod.h»

void PryamoiHod (int n, double **a, double *b)

{

double v;

for (int k = 0, i, j, im; k < n — 1; k++)

{

im = k;

for (i = k + 1; i < n; i++)

{

if (fabs (a[im][k]) < fabs (a[i][k]))

{

im = i;

}

}

if (im ≠ k)

{

for (j = 0; j < n; j++)

{

v = a[im][j];

a[im][j] = a[k][j];

a[k][j] = v;

}

v = b[im];

b[im] = b[k];

b[k] = v;

}

for (i = k + 1; i < n; i++)

{

v = 1.0*a[i][k]/a[k][k];

a[i][k] = 0;

b[i] = b[i] - v*b[k];

if (v ≠ 0)

for (j = k + 1; j < n; j++)

{

a[i][j] = a[i][j] - v*a[k][j];

}

}

}

}

7.4. Модуль «show_vector»

// show_vector.h

// интерфейс модуля «show_vector»

#ifndef show_vector_h

#define show_vector_h

#include

#include

void PryamoiHod (int n, double **a, double *b);

#endif

// show_vector.cpp

// реализация модуля «show_vector»

#include «show_vector.h»

void ShowVector (int n, double * vec)

{

for (int i = 0; i < n; i++)

printf («%.3f «, vec[i]);

printf («rn»);

}