Реализация иерархии классов для решения системы линейных алгебраических уравнений
Курсовая работа
по дисциплине «Программирование для
ЭВМ»
Реализация иерархии классов для
решения системы линейных алгебраических уравнений
Оглавление
Введение
. Теоретические основы
.1 Определения, обозначения
.2 Метод Гаусса решения СЛУ
. Особенности программной реализации
.1 Иерархия классов
.2 Блок-схема алгоритма программы
.1 Основные классы
.2 Вспомогательные функции
Заключение
Список литературы
Введение
Курсовая работа состоит из трех разделов.
Ø В первом разделе содержатся теоретические сведения о методах
решения систем линейных уравнений.
Ø Второй раздел содержит программную реализацию используемых
методов - листинг программы, написанной на языке C++, с подробными
комментариями.
Ø Третий раздел включает особенности программной реализации
алгоритма, составленной средствами разработки Microsoft Visual Studio.NET.
В данной программе реализован метод решения системы линейных
алгебраических уравнений методом Гаусса с выборкой ведущего элемента. Помимо
решения СЛАУ в программе можно подсчитать, определитель матрицы и провести
сложение и умножение двух матриц.
Пользователю предоставляется выбор размерности искомых матриц и вариант
вывода результата, в файл или на экран. Матрицы для всех вычислений
генерируются случайным образом с помощью соответствующих функций. Программа
реализована в виде удобного меню. Данные вводимые пользователем проверяются на
корректность специальными функциями. Исходный код прилагается.
алгоритм уравнение программный матрица
1. Теоретические основы
.1 Определения, обозначения
Определение
1. Системой 
линейных уравнений с 
неизвестными
с действительными коэффициентами называется система
выражений вида
(1)
где
R. Элементы 
называются коэффициентами системы (1), 
- ее свободные члены. Если все 
, то система (1) называется однородной, иначе -
неоднородной.
Определение
2. Совокупность вещественных чисел 
называется
решением (1), если после подстановки их вместо 
соответственно
во все уравнения (1) получаются тождества.
Определение
3. Если система (1) имеет хотя бы одно решение, то она называется совместной,
если решений нет - несовместной.
Определение
4. Два решения 
и 
являются
различными, если нарушается одно из равенств 
, …, 
.
Определение
5. Если система (1) имеет единственное решение, то она называется определенной,
если у системы существует по крайней мере два различных решения, то система
называется неопределенной.
Решить
систему линейных уравнений - это значит выяснить, совместна она или нет, и в
случае совместности найти все ее решения.
Условие совместности СЛУ.
Теорема
2. (теорема Кронекерра-Капелли). Для того, чтобы система (1) была совместной,
необходимо и достаточно, чтобы ранг ее расширенной матрицы был равен рангу
основной матрицы, т.е. 
.
Доказательство.
Очевидно, что 
.
Для
доказательства перепишем систему (1) в виде:
(4)
где
выделены столбцы матрицы 
, являющиеся элементами R
.
Необходимость.
Если существует решение , то запись (4) означает, что столбец свободных членов
есть линейная комбинация столбцов матрицы 
. Значит,
добавление этого столбца не изменяет числа линейно независимых столбцов 
.
Достаточность.
Пусть . В этом случае базисный минор матрицы является базисным и для . Это и означает, что столбец свободных членов есть
линейная комбинация тех столбцов матрицы , в
которых расположен базисный минор, а значит, и всех столбцов матрицы (остальные можно взять с коэффициентом 0). Очевидно,
что коэффициенты этой линейной комбинации и являются решениями системы (1),
т.е. есть хотя бы одно решение.
.2
Метод Гаусса решения СЛУ
На
практике чаще всего используют метод Гаусса построения решений СЛУ. При этом
при исследовании и решении СЛУ производятся элементарные преобразования строк
расширенной матрицы 
: перестановка строк (это соответствует перестановке
уравнений системы), сложение строк (это соответствует сложению уравнений
системы), умножение строк на отличное от нуля число (это соответствует
умножению уравнения системы на отличное от нуля число). Очевидно, что при
указанных преобразованиях получается система, эквивалентная данной.
Следовательно, после элементарных преобразований строк расширенной матрицы получается расширенная матрица некоторой новой
системы, эквивалентной данной системе.
Замечание.
Перестановка в основной матрице двух столбцов соответствует в системе
перестановке неизвестных вместе со своими координатами. Умножение столбца на
число и сложение столбцов приводит к изменению коэффициентов только при одном
неизвестном и значит к системе, не эквивалентной рассматриваемой.
Рассмотрим
матрицу . Элементарными преобразованиями строк ее можно
привести к ступенчатой матрице 
: 
:
(
- некоторые вещественные числа). 
.
Выберем
в матрице 
ненулевой минор порядка 
, т.е. базисный минор. Как и в теореме 5, §6 (о
ступенчатой матрице), его можно выбрать на пересечении первых строк и столбцов, с которых начинаются ненулевые
элементы строк. Этот минор верхнетреугольный и равен произведению 
. Будем считать, что этот минор расположен в левом
верхнем углу матрицы (перестановкой столбцов матрицы и перенумерацией переменных этого всегда можно
добиться). Нулевые строки матрицы отбросим (этому соответствуют уравнения 
с любым решением).
.
Далее
все элементы базисного минора выше главной диагонали можно сделать равными нулю
(как в теореме 5, §6), а элементы главной диагонали - равными 1 (умножением
строки на 
):
Т.о.,
исходная система (1) приведена к эквивалентной системе
Отсюда
видно, что если 
, то система имеет единственное решение
, …, 
.
Если
, то переменные 
-
базисные, 
- свободные и придавая им произвольные значения 
, …, 
, получим
решение:
2. Особенности программной реализации
.1 Иерархия классов
Рисунок 2.1
.2 Блок-схема алгоритма программы
Пример работы программы
При запуске программы выходит следующее меню.
. Помощь (что же делает эта программа)
. Начало работы
. Выход
Если был выбран 2 пункта появиться еще одно меню, со следующим списком
доступных команд.
. Решение СЛАУ.
. Нахождение определителя матрицы.
. Поэлементное сложение двух матриц.
. Поэлементное вычитание одной матрицы из другой.
. Умножение матриц.
. Возврат к предыдущему меню.
.3 СЛАУ
Выбираем 1 пункт-решение СЛАУ. Сразу же необходимо ввести размер
квадратной матрицы, элементами которой являются коэффициенты при X.
После ввода размерности будущей матрицы появиться список.
. Печать СЛАУ и решения на экран.
. Печать СЛАУ и решения в файл.
. Вернуться назад.
Печать СЛАУ на экран
При выводе решения на экран или в файл можно выбрать как напечатать ответ
и невязку.
. В линию(как вектор строку)
. В столбец(как вектор столбец)
Печать СЛАУ в файл
После выбора пункта печать в файл. Вводятся имя файла для вывода СЛАУ,
решения и невязки. Потом, традиционно выбирается тип вывода решения и
невязки(строка или столбец).
Пример вывода в файл строку и в столбец.
Для корректного отображения данных в блокноте следует проделать следующие
действия.
Ввод размера матрицы
Выбор печати.
. Вывод матрицы и определителя на экран.
. В файл.
На экран и в файл
При выводе в файл на экран экран выводятся «done step1» и «done step2»
что является своеобразным индикатором успешного печати.
Алгебраические операции «+», «-» и «*»
Для сложения и вычитания процедуры ввода \ вывода идентичны и различаются
лишь результатом операции, поэтому рассмотрим лишь сложение и умножение матриц.
Стандартный выбор:
. Вывод на экран.
. Печать в файл.
Ввод имени фала вывода.
Пример вывода на экран и в файл.
Так
как можно перемножать только сопряженные матрицы, т.е. 
то помимо стандартной посимвольной проверки вводимых
данных осуществляется проверка сопряженности перемножаемых матриц.
Ввод
размерностей 1ой и 2ой матрицы.
Если
все введено верно то выбор - печать на экран или в файл.
В
файл.
Вывод
на экран и в файл.
3. Особенности программной реализации алгоритма
.1 Основные классы
my_matrix//базовый класс матрица произвольного размера
{: **a;//ячейки...массивi,//число строк
j;//число столбцов_matrix(){}//конструктор
~my_matrix(){}//деструкторmy_matrix_set(int ii,int jj){} //установка
размеров матрицы i на j
double get_(int i5,int j5) {} //возращает значение a[i5][j5] ячейкиmatrix_random(double
aa=1.,double bb=5.){}//рандомswap_line(int k1,int k2)
{}//меняет строки k1 и k2 искомой матрицы
//сложение строк. строка i умноженная на k прибавляется к строке i2
void line_sum_i_to_i2(int i_,int i2,double k){}
//умножение строки a[pos][] на число
void line_to_num(int pos,double k){}:my_matrix* operator +
(my_matrix aa,my_matrix bb);my_matrix* operator -(my_matrix aa,my_matrix bb);my_matrix*
operator *(my_matrix aa,my_matrix bb);my_matrix* operator *(my_matrix
aa,my_matrix *bb);
};
{
public:see_mat_console(my_matrix *b)//вывод матрицы на консольsee_mat_console(double
**a,int nn) //вывод матрицы
на консоль
////вывод СЛАУ(A|f) на консоль
//вывод корней(X) на консоль
//вывод в зависимости от параметра fl. ==1 то вывод СЛАУ ==2 печать
ответов на экран в строку ==3 печать ответов на экран в столбец
void look_all_(double **a,my_matrix *x,my_matrix *b,int fl)
//вывод матрицы на консоль==1 красивый вывод с a[][]
Kof==2 вывод без a[][]look_all_(my_matrix *m,int kof=1/*1 печать с
a[][],2 без */)look_all_(double
**a,int n2)
//вывод квадратной матрицы a[n2][n2] просмотр с a[][]
void look_all_(double **a1,int i_n2,int j_n3)
//вывод матрицы a[i_n2][j_n3] просмотр с a[][]
void look_all_file(char*fname,double **a,int
n2,char*mode_/*app или out */)
//печать квадратной матрицы в файл с именем fname. определена дозапись
или перезапись в зависимости от параметра mode_
void look_all_file(char*fname,double **a,int i_n2,int
j_n3,char*mode_/*app или out */,int kof=1/*1 печать с a[][]
2печать только
значений */)
//печать матрицы в файл с именем fname. определена дозапись или
перезапись в зависимости от параметра mode_
void look_pogr(double **a,int n3,char* mark/**/)
//печать матрицы «вектора» в зависимости от mark==lin печать в линию==ver
печать в столбец
void look_pogr_file(char*fname,double **a,int n3,char*
mark,char* type_record/*app out*/)//печать
погрешности в файл
};
square_matrix:public my_matrix,print//класс наследник
{:int size; //размерность
матрицы:square_matrix():my_matrix(){};//конструкторmy_matrix_set(int y)
//сведение матрицы к треугольному виду методом Гаусса с выборкой ведущего
элемента
//и подсчёт detdouble gauss_2()
//рассчет корней СЛАУ
//обратный проход gauss_(matrix*f)
void result_(my_matrix *b,my_matrix *x)
//обратный проход. Записывает ответы в матрицу Х...
bool good(my_matrix *b)
/*т.к. если система не была совместной то после прохода
методом гаусса получим a[n][n]==0 в то время как b[n] элемент в столбце свободных членов
равен ненулю,
т.е. a[n][n]*X==b[n] <=> 0*X=какоето число.
т.е. для совмемстности системы достаточно проверит не
является ли нулём a[n][n] при b[n] не равнным нулю*/
void put_mat_file(my_matrix *b,char* fname,char
*mode_,char*text/*,char*met*/)put_mat_ans_file(my_matrix *b,char* fname,char
*mode_,char*text,char*met)
};
3.2 Вспомогательные функции
chek_cin_int()//посимвольная проверка ввода
Выводит на экран сообщение с просьбой ввода размерности СЛАУ пока не
будет введено целое число. Осуществляет посимвольную проверку вводимых данных.
Возвращает введенное число.
int chek_cin_int(char *text)
//посимвольная проверка с выводом на экран содержимого массива *text
int chek_cin_int(char **text,int n)
//посимвольная проверка с выводом на экран содержимого массива **text
//где n число строк массива **textm1()// FAQ/Help о том что можно в этой
программе
char* m2()/*enter output file name */
Выводит на экран сообщение с просьбой о вводе имени файла вывода.
Возвращает имя файла.m3()//Ввод размерности СЛАУm4(char *fname/*имя
файла*/,char*tip/*печать ответов ver или lin*/,int n/*размер системы*/,int
my_mode/*1 если печать в файл,-1 на экран*/)//меню СЛАУ
Генерирует СЛАУ. Решает её и в зависимости от параметров выводит на экран
или в файл. В зависимости от параметра tip ответы и погрешность печатаются
вертикально или горизонтально.m5()//подменю СЛАУ
Выводится меню из 3 пунктов: печать СЛАУ с погрешностью вычислений в
файл, печать СЛАУ с погрешностью вычислений на экран и вернуться назад к
предыдущему меню.* m6()//Выводиться меню из 2ух пунктов: печать результатов
вертикально или горизонтально.slau_m()//Основное меню работы со СЛАУ.
В нем используются следующие функции m2() m3() m4() m5() m6().m8()//меню
для m7
//меню для подсчёта определителя матрицы с выбором: печать на экран или в
файл.m7()//Генерируется матрица и находится её определитель.A_plus_B()//Меню
сложение 2ух матриц.
Функции считывания размерности и имени файла вывода встроены.
Выводит матрицы A B C, где матрица С рез-тат операции
A+B.A_minus_B()//Меню вычитания 2ух матриц.
Функции считывания размерности и имени файла вывода встроены.
Выводит матрицы A B C, где матрица С рез-тат операции A-B.A_on_B()//Меню
умножения 2ух матриц.
Содержит функции считывания размерности каждой матрицы, имени файла
вывода.
Выводит матрицы A[n/k] B[k/m] C[n/m], где матрица С рез-тат операции A*B.
Содержит функцию проверки корректности вводимых размерностей матриц т.е. для
правильного ввода матрицы A и B должны быть сопряженными.menu_2()//меню
содержащее подпункты, при выборе которых срабатывают следующие функции
1) SLAU // slau_m()
) Det of matrix // m7()
) A+B=?// A_plus_B()
) A-B=?// A_minus_B()
) A*B=?// A_on_B()
6) back//вернуться на уровень вверх ()menu()//подпункты, при выборе
которых срабатывают следующие функции
1) help(FAQ)// m1();
) start program// menu_2();
3) exit// exit(0); завершение работы программы
Главная функция main()
void main()
{(time(NULL));
menu();
}
Заключение
В ходе работы были освоены основы объектно-ориентированного
программирования, методы программирования с использованием структур и классов.
Была написана программа на языке С++ среде разработки Microsoft Visual
Studio.NET, в которой реализована иерархия классов и перегрузка функций, работа
с динамической памятью.
По итогам работы была оформлена пояснительная записка в текстовом
редакторе MS Word согласно установленным требованиям к оформлению результатов
курсовой работы.
Список литературы
1. Голицына О.Л. Языки программирования: учеб. пособие.
Издательство: «ИНФРА-М, Форум», 2010.
. Программирование и алгоритмизация В.П. Аверкин, А.И.
Бобровский, В.В. Веснич и др.; Под ред. А.Д. Хомоненко. - СПб.: Корона принт,
2009. - 252 с.
. Архангельский А.Я. Программирование / А.Я. Архангельский. -
М.: Бином, 2012. - 1151 с.
. Павловская Т.А. Программирование на языке высокого уровня:
Учебник для вузов, Питер, 2012.