VIII Международная студенческая научная конференция Студенческий научный форум — 2016
РЕШЕНИЕ СЛАУ НА ЯЗЫКЕ C#
Решение системы линейных алгебраических уравнений (СЛАУ) имеет большое значение, поскольку к нему сводится решение широкого круга сложных практических задач. Особая необходимость в решении СЛАУ возникает при использовании широкого класса моделей и подходов, применяемых при автоматизированном проектировании аппаратуры с учетом электромагнитной совместимости. Так как решение СЛАУ «вручную» представляет собой трудоёмкую задачу, а использование средств математического моделирования (MathCAD, MathLab) требует наличие у пользователя некоторых специальных знаний, представляется актуальной задача создания алгоритма решения СЛАУ и программы, построенной на данном алгоритме.
Под СЛАУ подразумевают систему, содержащую m уравнений и n неизвестных (x1,x2,…,xn).
Параметры aij называют коэффициентами, а bi– свободными членами СЛАУ. Иногда, чтобы подчеркнуть количество уравнений и неизвестных, говорят так «m×n система линейных уравнений», – тем самым указывая, что СЛАУ содержит m уравнений и n неизвестных.
Если все свободные члены равны 0, то СЛАУ называют однородной. Если среди свободных членов есть хотя бы один, отличный от нуля, СЛАУ называют неоднородной.
Решением СЛАУ называют всякую упорядоченную совокупность чисел (α1,α2,…,αn), если элементы этой совокупности, подставленные в заданном порядке вместо неизвестных x1,x2,…,xn, обращают каждое уравнение СЛАУ в тождество.
Если СЛАУ имеет хотя бы одно решение, ее называют совместной, если же решений нет – несовместной. Если совместная СЛАУ имеет ровно одно решение, её именуют определённой, если бесконечное множество решений – неопределённой.
В данной работе, была создана программа на языке C# для решения СЛАУ методом Гаусса.
Словесно, алгоритм работы программы можно представить в следующем виде:
Формируем массив, в который записывается расширенная матрица из коэффициентов и свободных членов;
Делим каждый элемент первой строки на коэффициент в первом столбце;
Вычитаем из всех строк, начиная со второй, первую строку, умноженную на коэффициент в первом столбце;
Переходим к следующей строке и выполняем пункты 2 и 3, увеличивая номер столбца, из которого мы берем первый элемент;
Выполняем пункт 4 до тех пор, пока не кончатся строки;
Последний столбец получившейся матрицы представляет собой столбец корней СЛАУ, притом номер корня равен номеру строки, в котором он находится в преобразованной матрице.
Программный код на языке C#, реализующая решение указанный алгоритм:
Программная реализация метода Гаусса
Вычислительная схема метода Гаусса состоит из двух этапов. Первый этап заключается в приведении системы к трапециевидной. Этот этап называется прямым ходом. Второй этап — определение неизвестных — называется обратным ходом.
Прямой ход метода Гаусса состоит в последовательном исключении коэффициентов при неизвестных начиная с первого столбца.
Прямой ход реализуется по следующим формулам (индекс k в круглых скобках означает номер цикла — номер столбца).
Умножение k-й строки на число
. (1)
Вычитание k-й строки из j-й строки
. (2)
. (3)
Обратный ход — вычисление неизвестных — реализуется по следующим формулам, начиная с последнего уравнения системы
. (4)
Код C++
using namespace std;
double **a = new double *[n];
for (i = 0; i new double [n];
double **a1 = new double *[n];
for (i = 0; i new double [n];
double *b = new double [n];
double *x = new double [n];
cout «Vvedite koefficienty i svobodnye chleny » for (i = 1; i for (j = 1; j «a[ » «,» «]= » ;
for (k = 1; k // прямой ход
for (j = k + 1; j // формула (1)
for (i = k; i // формула (2)
b[j] = b[j] — d * b[k]; // формула (3)
for (k = n; k >= 1; k—) // обратный ход
for (j = k + 1; j // формула (4)
d = d + s; // формула (4)
x[k] = (b[k] — d) / a[k][k]; // формула (4)
cout «Korni sistemy: » for ( i = 1; i «x[» «]=» » » return 0;
Метод Гаусса на Java
Статья посвящена реализации алгоритма Гаусса для решения системы линейных алгебраических уравнений на языке Java.
Теоретические сведения
Рассмотрим математическую теорию. Система линейных уравнений может иметь одно решение, бесконечно много решений или же быть несовместной (не иметь решений). Не все методы решения СЛАУ могут справится с вторым случаем, когда система имеет бесконечно много решений. Например, метод Крамера и матричный метод не применимы, но метод Гаусса вполне можно использовать.
Алгоритм можно условно разделить на два этапа:
- Прямой ход
- Обратный ход
В первом этапе образуются нули ниже или выше главной диагонали, за счет использования элементарных преобразований матрицы. На втором этапе находят неизвестные начиная с конца. Подробную теорию можно посмотреть по ссылке: метод Гаусса, поэтому с теорией пожалуй все. Перейдем к реализации.
Реализация
Начнем с постановки задачи:
- нам нужно создать программу, реализующую систему линейных уравнений в виде некоторой структуры данных, используя приемы обобщенного программирования. Система должна содержать коэффициенты производного типа от класса Number (т.е. Float, Integer, Double и т.д.)
- Запрограммировать алгоритм, который получив на вход структуру данных системы образует нули ниже главной диагонали
Начнем с написания интерфейса, который должно реализовывать каждое уравнение:
Здесь все должно быть ясно, N некоторый наследник Number‘а, T — некоторый тип, реализующий данный интерфейс (рекурсивные дженерики). Метод addEquation(T item) позволяет прибавить каждый элемент уравнения item к каждому своему элементу. Остальные методы работают аналогично.
Теперь рассмотрим класс системы уравнений. Как видно в листинге ниже, он дженеризирован так же, как и интерфейс Gauss и содержит методы для удобного доступа к приватному списку содержащих в себе уравнений.
Теперь можно приступать к реализации «частного случая» структуры уравнения. Создадим класс MyEquation, реализующий наш интерфейс. Пусть наследником Number‘а будет сверхточный класс Float (на практике лучше брать Double). Обратите внимание, что в методе addEquation(MyEquation item) используется объект класса ListIterator, позволяющий изменять элементы перебираемого списка.
Теперь имеем полноценную структуру данных, реализующую систему уравнений. Составим алгоритм который будет принимать некоторый объект, реализующий интерфейс Gauss, затем вызывая нужные методы приведет матрицу к нужному виду.
Алгоритм простой, найти нужный коэффициент, домножить на него i-ю строку (i=0..n-1), и прибавить ее к j-й строке (j=i..n). Заметьте, алгоритм не знает как именно реализуются методы findCoefficient, mul и addEquation, это придает коду бОльшую гибкость, т.к. при потребности изменить способы манипуляции уравнениями (строками), будут изменены только реализации трех вышеупомянутых методов, а главный алгоритм останется нетронутым.
Почти все. Осталось запустить это все в методе main:
Запустим это чудо, что бы проверить корректность работы…
Это все. Исходники можно скачать на github’е.
Вывод
Метод Гаусса не очень поддается обобщенному программированию (как видите обратный ход выполнен отдельно), однако вышла своеобразная реализация которая, надеюсь, поможет кому то лучше разобраться в искусстве использования интерфейсов и дженериков.