Статья посвящена реализации алгоритма Гаусса для решения системы линейных алгебраических уравнений на языке Java.
- Теоретические сведения
- Реализация
- Вывод
- Решение системы линейных уравнений методом Гаусса
- Метод Гаусса решения системы линейных уравнений
- Алгоритм Гаусса
- Базовая схема
- Поиск опорного элемента (pivoting)
- Вырожденные случаи
- Реализация
- Асимптотика
- Более точная оценка числа действий
- Дополнения
- Ускорение алгоритма: разделение его на прямой и обратный ход
- Решение СЛАУ по модулю
- Немного о различных способах выбора опорного элемента
- Улучшение найденного ответа
- 🌟 Видео
Видео:Java - урок 5.4 (Практика - решаем квадратное уравнение)Скачать

Теоретические сведения
Рассмотрим математическую теорию. Система линейных уравнений может иметь одно решение, бесконечно много решений или же быть несовместной (не иметь решений). Не все методы решения СЛАУ могут справится с вторым случаем, когда система имеет бесконечно много решений. Например, метод Крамера и матричный метод не применимы, но метод Гаусса вполне можно использовать.
Алгоритм можно условно разделить на два этапа:
- Прямой ход
- Обратный ход
В первом этапе образуются нули ниже или выше главной диагонали, за счет использования элементарных преобразований матрицы. На втором этапе находят неизвестные начиная с конца. Подробную теорию можно посмотреть по ссылке: метод Гаусса, поэтому с теорией пожалуй все. Перейдем к реализации.
Видео:6 способов в одном видеоСкачать

Реализация
Начнем с постановки задачи:
- нам нужно создать программу, реализующую систему линейных уравнений в виде некоторой структуры данных, используя приемы обобщенного программирования. Система должна содержать коэффициенты производного типа от класса 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’е.
Видео:Решение системы линейных уравнений с двумя переменными способом подстановки. 6 класс.Скачать

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

Решение системы линейных уравнений методом Гаусса
Дата добавления: 2014-05-02 ; просмотров: 4539 ; Нарушение авторских прав
Простейшие численные методы
Рассмотрим численные методы решения систем линейных алгебраических уравнений

где А – матрица m 
Методы численного решения системы линейных алгебраических уравнений делятся на две группы: прямые методы (Гаусса, Крамера) и итерационные методы. Итерационные методы состоят в том, что решение x системы находится как предел при n 


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

где А – матрица m 
Запишем систему (1) в развернутом виде

Метод Гаусса решения системы (2) состоит в последовательном исключении неизвестных x1, x2,…, xm из этой системы. Предположим, что a110. Поделив первое уравнение на a11 получим


Рассмотрим теперь оставшиеся уравнения системы (2):

Умножим (3) на ai1 и вычтем полученное уравнение из i-го уравнения системы (4), i=2,…,m. В результате получим следующую систему уравнений:
, , , , | (5) |

Матрица системы (5) имеет вид

Матрицы такой структуры принято обозначать так:

Где крестиками обозначены ненулевые элементы. В системе (5) неизвестное x1 содержится только в первом уравнении, поэтому в дальнейшем достаточно иметь дело с укороченной системой уравнений



Тем самым мы осуществили первый шаг метода Гаусса. Если 

При этом первое уравнение системы (5) остается без изменения.
Исключая таким же образом неизвестные x3,x4,…,xm, придем окончательно к системе уравнений вида
, , , , , Матрица этой системы | (8) |

Содержит нули всюду ниже главной диагонали. Матрицы такого вида называются верхними треугольными матрицами.
Получение системы (8) составляет прямой ход метода Гаусса. Обратный ход заключается в нахождении неизвестных x1,x2,…,xm из системы (8). Поскольку матрица имеет треугольный вид, можно последовательно, начиная с xm, найти все неизвестные. Общие формулы обратного хода имеют вид

При реализации в программе прямого хода метода Гаусса нет необходимости действовать с переменными x1,x2,…,xm. Достаточно указать алгоритм, согласно которому исходная матрица А преобразуется к треугольному виду (9), и указать соответствующие преобразования правых частей системы. Получим эти общие формулы. Пусть реализованы первые k-1 шагов, т.е. уже исключены переменные x1,x2,…,xk-1. Тогда имеем систему
, , , , , , , | (11) |
Рассмотрим k-е уравнение этой системы

И предположим, что 




Далее, умножим уравнение (12) на 
, , ![]() |

Таким образом, в прямом ходе метода Гаусса коэффициенты уравнений преобразуются по следующему правилу:



Вычисление правых частей системы (8) осуществляются по формулам


Коэффициенты cij и правые части yi, i=1,2. m, j=i+1,i+2,…, m, хранятся в памяти и используются при осуществлении обратного хода по формулам (10).
Основным ограничением этого является предположение о том, что все элементы 

В листинге представлен метод Gauss(), который получает матрицу А и столбец свободных членов В, и реализует прямой и обратных ход метода Гаусса.
Листинг 15.1. Метод Гаусса
public static void Gauss(float[,] A, float[] B,
Видео:Решение системы линейных уравнений графическим методом. 7 класс.Скачать

Метод Гаусса решения системы линейных уравнений
Дана система 

Формально задача ставится следующим образом: решить систему:
где коэффициенты 


Удобно матричное представление этой задачи:
где 





Стоит отметить, что СЛАУ может быть не над полем действительных чисел, а над полем по модулю какого-либо числа 
— алгоритм Гаусса работает и для таких систем тоже (но этот случай будет рассмотрен ниже в отдельном разделе).
Видео:Уроки Java с нуля / #5 – Данные от пользователя. Математические действияСкачать

Алгоритм Гаусса
Строго говоря, описываемый ниже метод правильно называть методом «Гаусса-Жордана» (Gauss-Jordan elimination), поскольку он является вариацией метода Гаусса, описанной геодезистом Вильгельмом Жорданом в 1887 г. (стоит отметить, что Вильгельм Жордан не является автором ни теоремы Жордана о кривых, ни жордановой алгебры — всё это три разных учёных-однофамильца; кроме того, по всей видимости, более правильной является транскрипция «Йордан», но написание «Жордан» уже закрепилось в русской литературе). Также интересно заметить, что одновременно с Жорданом (а по некоторым данным даже раньше него) этот алгоритм придумал Класен (B.-I. Clasen).
Базовая схема
Кратко говоря, алгоритм заключается в последовательном исключении переменных из каждого уравнения до тех пор, пока в каждом уравнении не останется только по одной переменной. Если 


При этом алгоритм основывается на двух простых эквивалентных преобразованиях системы: во-первых, можно обменивать два уравнения, а во-вторых, любое уравнение можно заменить линейной комбинацией этой строки (с ненулевым коэффициентом) и других строк (с произвольными коэффициентами).
На первом шаге алгоритм Гаусса-Жордана делит первую строку на коэффициент 






В итоге, по окончании первого шага первый столбец матрицы 
Аналогично производится второй шаг алгоритма, только теперь рассматривается второй столбец и вторая строка: сначала вторая строка делится на 

И так далее, пока мы не обработаем все строки или все столбцы матрицы 


Поиск опорного элемента (pivoting)
Разумеется, описанная выше схема неполна. Она работает только в том случае, если на каждом 


Чтобы сделать алгоритм работающим в таких случаях, как раз и существует процесс выбора опорного элемента (на английском языке это называется одним словом «pivoting»). Он заключается в том, что производится перестановка строк и/или столбцов матрицы, чтобы в нужном элементе 
Заметим, что перестановка строк значительно проще реализуется на компьютере, чем перестановка столбцов: ведь при обмене местами двух каких-то столбцов надо запомнить, что эти две переменных обменялись местами, чтобы затем, при восстановлении ответа, правильно восстановить, какой ответ к какой переменной относится. При перестановке строк никаких таких дополнительных действий производить не надо.
К счастью, для корректности метода достаточно одних только обменов строк (т.н. «partial pivoting», в отличие от «full pivoting», когда обмениваются и строки, и столбцы). Но какую же именно строку следует выбирать для обмена? И правда ли, что поиск опорного элемента надо делать только тогда, когда текущий элемент 
Общего ответа на этот вопрос не существует. Есть разнообразные эвристики, однако самой эффективной из них (по соотношению простоты и отдачи) является такая эвристика: в качестве опорного элемента следует брать наибольший по модулю элемент, причём производить поиск опорного элемента и обмен с ним надо всегда, а не только когда это необходимо (т.е. не только тогда, когда 
Иными словами, перед выполнением 




Во-первых, эта эвристика позволит решить СЛАУ, даже если по ходу решения будет случаться так, что элемент 
Без этой эвристики, даже если система такова, что на каждой 


Вырожденные случаи
Итак, если останавливаться на алгоритме Гаусса-Жордана с partial pivoting, то, утверждается, если 

Рассмотрим теперь общий случай — когда 






Итак, некоторые переменные в процессе работы алгоритма могут оказываться независимыми. Понятно, что когда количество 


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

Реализация
Приведём здесь реализацию алгоритма Гаусса-Жордана с эвристикой partial pivoting (выбором опорного элемента как максимума по столбцу).
На вход функции 





Функция возвращает число решений системы (




В функции поддерживаются два указателя — на текущий столбец 

Также заводится вектор 
Реализация использует технику partial pivoting, производя поиск строки с максимальным по модулю элементом, и переставляя затем эту строку в позицию 

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

Видео:Математика это не ИсламСкачать

Асимптотика
Оценим асимптотику полученного алгоритма. Алгоритм состоит из 
- поиск и перестановка опорного элемента — за время
при использовании эвристики «partial pivoting» (поиск максимума в столбце)
- если опорный элемент в текущем столбце был найден — то прибавление текущего уравнения ко всем остальным уравнениям — за время
Очевидно, первый пункт имеет меньшую асимптотику, чем второй. Заметим также, что второй пункт выполняется не более 
Таким образом, итоговая асимптотика алгоритма принимает вид 
При 

Заметим, что когда СЛАУ рассматривается не в поле действительных чисел, а в поле по модулю два, то систему можно решать гораздо быстрее — об этом см. ниже в разделе «Решение СЛАУ по модулю».
Более точная оценка числа действий
Для простоты выкладок будем считать, что 
Как мы уже знаем, время работы всего алгоритма фактически определяется временем, затрачиваемым на исключение текущего уравнения из остальных.
Это может происходить на каждом из 


Видео:Метод Ньютона (метод касательных) Пример РешенияСкачать

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

Решение СЛАУ по модулю
Для решения СЛАУ по модулю можно применять описанный выше алгоритм, он сохраняет свою корректность.
Разумеется, теперь становится ненужным использовать какие-то хитрые техники выбора опорного элемента — достаточно найти любой ненулевой элемент в текущем столбце.
Если модуль простой, то никаких сложностей вообще не возникает — происходящие по ходу работы алгоритма Гаусса деления не создают особых проблем.
Особенно замечателен модуль, равный двум: для него все операции с матрицей можно производить очень эффективно. Например, отнимание одной строки от другой по модулю два — это на самом деле их симметрическая разность («xor»). Таким образом, весь алгоритм можно значительно ускорить, сжав всю матрицу в битовые маски и оперируя только ими. Приведём здесь новую реализацию основной части алгоритма Гаусса-Жордана, используя стандартный контейнер C++ «bitset»:
Как можно заметить, реализация стала даже немного короче, при том, что она значительно быстрее старой реализации — а именно, быстрее в 
Если модуль произвольный (не обязательно простой), то всё становится несколько сложнее. Понятно, что пользуясь Китайской теоремой об остатках, мы сводим задачу с произвольным модулем только к модулям вида «степень простого». [ дальнейший текст был скрыт, т.к. это непроверенная информация — возможно, неправильный способ решения ]
Наконец, рассмотрим вопрос числа решений СЛАУ по модулю. Ответ на него достаточно прост: число решений равно 


Немного о различных способах выбора опорного элемента
Как уже говорилось выше, однозначного ответа на этот вопрос нет.
Эвристика «partial pivoting», которая заключалась в поиске максимального элемента в текущем столбце, работает на практике весьма неплохо. Также оказывается, что она даёт практически тот же результат, что и «full pivoting» — когда опорный элемент ищется среди элементов целой подматрицы — начиная с текущей строки и с текущего столбца.
Но интересно отметить, что обе эти эвристики с поиском максимального элемента, фактически, очень зависят от того, насколько были промасштабированы исходные уравнения. Например, если одно из уравнений системы умножить на миллион, то это уравнение почти наверняка будет выбрано в качестве ведущего на первом же шаге. Это кажется достаточно странным, поэтому логичен переход к немного более сложной эвристике — так называемому «implicit pivoting».
Эвристика implicit pivoting заключается в том, что элементы различных строк сравниваются так, как если бы обе строки были пронормированы таким образом, что максимальный по модулю элемент в них был бы равен единице. Для реализации этой техники надо просто поддерживать текущий максимум в каждой строке (либо поддерживать каждую строку так, чтобы максимум в ней был равен единице по модулю, но это может привести к увеличению накапливаемой погрешности).
Улучшение найденного ответа
Поскольку, несмотря на различные эвристики, алгоритм Гаусса-Жордана всё равно может приводить к большим погрешностям на специальных матрицах даже размеров порядка 

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

Решение системы уравнений методом ГауссаСкачать

Java для начинающих. Урок 16: Тип возвращаемого значения метода.Скачать

Уроки Java для начинающих | #6 - Математические операцииСкачать

Матричный метод решения систем уравненийСкачать

Метод Зейделя Пример РешенияСкачать

Java для начинающих. Урок 8. Логический тип данных BooleanСкачать

Метод Крамера за 3 минуты. Решение системы линейных уравнений - bezbotvyСкачать

Решение систем линейных уравнений с помощью матрицСкачать

12. Решение систем линейных уравнений методом ГауссаСкачать




,
,
,
, Матрица этой системы
,
,
,
,






при использовании эвристики «partial pivoting» (поиск максимума в столбце)