VIII Международная студенческая научная конференция Студенческий научный форум - 2016

Моделирование реальных процессов в различных областях деятельности зачастую приводит к системам линейных уравнений (СЛУ). Для их решения существует несколько способов: метод Гаусса, метод Крамера, матричный метод. Каждый способ предусматривает неоднократное выполнение одних и тех же операций с различным числом данных. В этой связи их несложно представить в виде алгоритмов и перевести на язык программирования. Время решения компьютерной программы тесно связано с числом переменных, их типом, количеством арифметических операций, выполнением соответствия различных условий и т.п. Этот вопрос принимает актуальное значение при решении СЛУ в режиме реального времени, особенно, если исходные данные динамически изменяются.

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

Метод Гаусса

Система из nлинейных уравнений с n неизвестными имеет вид:

(1)

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

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

а к третьему уравнению ‑ первое, умноженное на коэффициент

С остальными уравнениями поступаем аналогично.

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

В результате первой итерации мы получим СЛУ, в которой первое уравнение включает все неизвестные, а остальные – исключают :

(1*)

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

(2)

количество арифметических операций.

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

(3)

Общее количество арифметических операций для приведения СЛУ общего вида (1) к виду (3) будет выражаться суммой числового ряда элементов, рассчитанных по формуле (2), от двух до n:

Существует два способа для нахождения неизвестных: метод подстановки и обратный ход по методу Гаусса. По второму способу СЛУ (3) приводится к виду:

(5)

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

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

Полученное значение подставляем в -е уравнение, находим значение , и так далее. С точки зрения количества операций, в этом случае мы имеем ряд арифметической прогрессии: 1, 3, 5, 7, …, сумма которой равна . Окончательно:

‑ для обратного хода:

‑ для последовательной подстановки:

Сравнительный анализ количества арифметических операций представлен в таблице 1.

Таблица 1

Количество уравнений	3	4	5	6	7	8	9	10
Кол-во операций на обратном ходе	84	192	360	600	924	1344	1872	2520
Кол-во операций для последовательной подстановки	37	80	145	236	357	512	705	940

Таким образом, для последующего анализа эффективности алгоритмов выбираем вариант последовательной подстановки.

Метод Крамера

Общий вид СЛУ (1) можно представить в матричном виде:

, где: (8)

‑ основная матрица системы, элементами которой являются коэффициенты при неизвестных переменных;

‑ матрица-столбец свободных членов;

– матрица-столбец неизвестных переменных.

Решение СЛУ (1) методом Крамера определяется по формуле:

– определитель основной матрицы системы;

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

Таким образом, для решения СЛУ методом Крамера необходимо найти определитель n-го порядка и еще произвести n делений. В качестве ограничения примем, что определитель основной матрицы не равен нулю, в противном случае СЛУ решений не имеет.

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

В свою очередь, для нахождения значения используется формула , где – минор, т.е. определитель матрицы -го порядка, полученной путём вычёркивания первой строки и j-го столбца из исходной матрицы. Соответствующие миноры также находятся по методу разложения по элементам ряда. В результате мы получим следующую формулу:

‑ инверсия в перестановке порядка n, т.е. число пар индексов p и q, для которых p-ый элемент перестановки больше q-го;

– номера перестановок из n.

Соответственно, формула (10) будет содержать слагаемых. Каждое слагаемое представляет собой произведение элементов матрицы, причем в каждом произведении содержится элемент из каждой строки и из каждого столбца матрицы А. С ростом n количество операций сильно возрастает. Для примера приведем таблицу факториалов от четырех до десяти (таблица 2):

Таблица 2

	4	5	6	7	8	9	10
n!	24	120	720	5040	40320	362880	3628800

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

В отличие от рассмотренного выше (формула 2), количество арифметических операций будет определяться исходя из n, а не умножений и делений на каждой итерации, т.к. отсутствует столбец свободных членов. В этом случае количество действий при получении треугольной матрицы определится формулой:

Общее количество арифметических операций при решении СЛУ методом Крамера будет выражаться в следующем виде:

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

Матричный метод решения СЛУ

Исходя из выражения (8) решение СЛУ можно получить в матричном виде следующим образом:

. (13)

Обратная матрица находится по формуле:

detA ‑ определитель (или детерминант) матрицы;

‑ алгебраические дополнения элементов .

Соответственно, для нахождения обратной матрицы необходимо найти один определитель n-го порядка, определителей -го порядка и произвести делений. В этом случае будем иметь большое количество операций, которое резко возрастает с ростом n. Поэтому воспользуемся альтернативным методом ‑ методом Жордана-Гаусса.

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

(15)

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

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

По аналогии с предыдущими методами, количество арифметических операции для получения нижней треугольной матрицы слева будет сумма ряда:

Прибавление единицы соответствует делению последнего уравнения на коэффициент .

С правой единичной матрицей для прямого хода количество операций будет гораздо меньше. Значения компенсирующих множителей уже получено. Все элементы, с которыми производится сложение, равны нулю. Следовательно, количество арифметических действий с правой матрицей будет равно количеству элементов, стоящих ниже главной диагонали. Это есть сумма арифметической прогрессии от 1 до , которая определиться формулой:

Теперь необходимо перейти к обратному ходу. Учитывая, что левая матрица превратилась в нижнюю треугольную, то для преобразования ее в единичную можно проводить действия только по столбцам. Эти же коэффициенты будут учитываться при преобразовании правой матрицы с помощью метода Гаусса. Таким образом, для перевода левой матрицы в единичную для n-го столбца умножаем элемент на коэффициент и складываем уравнения. Получили две операции. Для левой матрицы происходит умножение каждого элемента n-ой строки и почленное сложение уравнений.

Подытоживая, можно сказать, что для приведения левой матрицы к виду единичной потребуется добавить к выражению (16) удвоенное умножение количества элементов, стоящих выше главной диагонали. Это будет удвоенная сумма арифметической прогрессии натуральных чисел от 1 до :

Для правой матрицы количество операций соответствует

Общее количество арифметических операций при нахождении обратной матрицы будет определятся суммой выражений (18) и (19).

Далее необходимо выполнить умножение (13), что равносильно проведению операций. В результате количество действий при решении СЛУ методом обратной матрицы определится формулой:

Сравнительный анализ эффективности алгоритмов решения СЛУ, рассчитанных по формулам (7), (12) и (20) представлен в таблице 3.

На представленной таблице показаны результаты расчётов количества арифметических операций при реализации рассмотренных методов решения СЛУ.

Отсюда видно, что наиболее оптимальным методом решения СЛУ является метод Гаусса, т.к. он имеет наименьшее количество арифметических действий. Так же метод Гаусса применяется в качестве математической основы для других методов решения.

Таблица 3.

Количество уравнений	Метод Гаусса	Метод Крамера	Матричный метод	Выигрыш 2 от 3	Выигрыш 2 от 4	Выигрыш 4 от 3
1	2	3	4	5	6	7
3	37	99	62	2,68	1,68	1,60
4	80	279	127	3,49	1,59	2,20
5	145	629	221	4,34	1,52	2,85
6	236	1231	348	5,22	1,47	3,54
7	357	2183	512	6,11	1,43	4,26
8	512	3599	717	7,03	1,40	5,02
9	705	5609	967	7,96	1,37	5,80
10	940	8359	1266	8,89	1,35	6,60

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

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

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

Список литературы:

1. Письменный Д.Т. Конспект лекций по высшей математике. 1 часть. – 2-е изд., испр. – М.: Айрис-пресс, 2003.

2. http://www.cleverstudents.ru

Код для цитирования: Скопировать