Метод гаусса для линейных уравнений на c (3 видео)

Программная реализация метода Гаусса

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

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

Прямой ход реализуется по следующим формулам (индекс k в круглых скобках означает номер цикла — номер столбца).

Умножение k-й строки на число

. (1)

Вычитание k-й строки из j-й строки

. (2)

. (3)

Обратный ход — вычисление неизвестных — реализуется по следующим формулам, начиная с последнего уравнения системы

. (4)

Код C++

using namespace std;

cout «Poryadok: » > n;

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;

Содержание

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

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

BestProg

Видео:Метод Гаусса за 7 минут. Система линейных уравненийСкачать

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

Условие задачи

Задана система линейных алгебраических уравнений:

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

Выполнение

При сохранении проекта имя модуля главной формы приложения оставляем по умолчанию « Unit1.cpp «.

Рис. 1. Форма приложения с созданными файлами

2. Разработка главной формы приложения

2.1. Название приложения

Задать название приложения. Для этого свойство Caption главной формы устанавливаем в значение «Метод Гаусса».

2.2. Установка свойств формы

Выделить форму. В Object Inspector установить значение следующих свойств:
– свойство Border Style = bsDialog ;
– свойство Position = poScreenCenter ;
– в свойстве Font выбрать параметры шрифта: шрифт Tahoma , размер шрифта 12 (рис. 2).

Рис. 2. Установка параметров шрифта главной формы приложения

В результате, форма приложения примет вид как показано на рисунке 3.

Рис. 3. Главная форма приложения

2.3. Компонент типа TGroupBox

Размещаем на форме компонент (элемент управления) типа TGroupBox из палитры компонент « Tool Palette «.

Рис. 4. Компонент типа TGroupBox

В результате, система создаст объект-переменную с именем GroupBox1 .

Изменяем размеры компонента GroupBox1 на всю ширину окна главной формы.

Свойство Caption компонента GroupBox1 устанавливаем в значение « Условие задачи «. Форма приложения будет иметь вид, как показано на рисунке 5.

Рис. 5. Форма приложения после размещения компонента TGroupBox

2.4. Компонент типа TLabel .

Размещаем компонент типа TLabel в области компонента TGroupBox . Автоматически создается объект-переменная с именем Label1 (рис. 6).

Устанавливаем свойство WordWrap компонента Label1 в значение « true » (рис. 6).

С помощью мышки изменяем ширину вывода текста компонента Label1 (рис. 6).

Рис. 6. Компонент Label1 , свойство WordWrap

Свойство Caption компонента Label1 устанавливаем в значение:

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

В результате, форма приложения примет вид, как показано на рисунке 7.

Рис. 7. Форма приложения после размещения компонента Label1

2.5. Компоненты типа TButton .

Размещаем на форме компоненты типа TButton . В результате образуются два объекта-переменные с именами Button1 и Button2 .

Для лучшей наглядности изменяем размеры компонент так как показано на рисунке 8.

Рис. 8. Форма приложения с размещенными компонентами Button1 и Button2

Устанавливаем такие свойства компонент Button1 и Button2:
– в компоненте Button1 свойство Caption = «Выход» ;
– в компоненте Button2 свойство Caption = «Расчет >>» .

В результате форма приложения примет вид, как показано на рисунке 9.

Рис. 9. Главная форма приложения после размещения всех компонент

3. Программирование события клика на кнопке «Выход».

Вызовем событие OnClick компонента Button1 (кнопка « Выход «) (рис. 10). Событие размещается на вкладыше Events в Object Inspector .

Процесс программирования события OnClick подробно описан здесь.

Рис. 10. Вызов события OnClick компонента Button1

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

Метод Close() закрывает окно главной формы приложения и осуществляет все необходимые операции по освобождению памяти, ресурсов и т.д.

Листинг метода обработки события следующий:

4. Разработка формы ввода числа уравнений n.

4.1. Размещение компонент на форме и их настройка.

Процесс создания новой формы подробно описан здесь.

Для создания новой формы вызовем команду

В результате, будет создана новая форма, как показано на рисунке 11. Сохраняем форму под именем « Unit2.cpp «.

Создаются файлы, которые соответствуют форме:
– файл « Unit2.h «, содержащий описания глобальных переменных и подключения других модулей;
– файл « Unit2.cpp «, содержащий реализацию методов формы;
– файл « Unit2.dfm «, содержащий описание изображения формы на экране (размеры окна, координаты формы относительно окна экрана, значение цветов и прочее).

Новосозданной форме отвечает объект с именем Form2 . С помощью этого имени можно приступаться к свойствам и методам формы Form2 .

Рис. 11. Новосозданная форма Form2

Осуществим настройку формы Form2 .

Сначала настроим свойства формы:
– свойство Caption = «Задайте число уравнений» ;
– свойство BorderStyle = bsDialog ;
– свойство Position = poScreenCenter ;
– в свойстве Font нужно выбрать следдующие параметры шрифта: шрифт Tahoma, размер шрифта 12.

Размещаем на форме такие компоненты:
– компонент типа TGroupBox которому будет отвечать объект GroupBox1;
– компонент типа TLabel, размещается внутри области компонента GroupBox1 . Компоненту типа TLabel отвечает объект-переменная Label1 ;
– компонент типа TEdit , размещается внутри области компонента GroupBox1 . Этому компоненту отвечает объект (переменная) Edit1 ;
– два компонента типа TButton , которым отвечают объекты с именами Button1 и Button2 .

Осуществим настройку свойств компонент:
– в компоненте GroupBox1 значение свойства Caption = «» (пустая строка);
– в компоненте Label1 значение свойства Caption = «n = « ;
– в компоненте Edit1 значение свойства Text = «» ;
– в компоненте Button1 значение свойства Caption = « ;
– в компоненте Button2 значение свойства Caption = «Далее >>» .

После размещения компонент и корректирования размеров формы, форма Form2 имеет вид как показано на рисунке 12.

Рис. 12. Форма Form2 после размещения и настройки всех компонент

4.2. Программирование обработчиков событий формы Form2 .

В форме Form2 программируем два обработчика событий:
– обработчик события OnClick клика на кнопке « «;
– обработчик события OnClick клика на кнопке « Далее >> «.

Листинг обработчика события клика на кнопке Button1 (« «):

Листинг обработчика события клика на кнопке Button2 (« Продолжить >> «):

Глобальная переменная ModalResult отвечает за состояние формы. Если глобальная переменная ModalResult=0 , то это означает что форма открытая как модальное окно. Как только значение ModalResult станет ненулевым, то форма Form2 закроется с кодом возврата, помещенным в ModalResult .

Таким образом, если пользователь сделает клик на кнопке Button1 , то форма Form2 закроется с кодом возврата mrNo. Если пользователь сделает клик на кнопке Button2, то форма Form2 закроется с кодом возврата mrOk .

5. Построение формы ввода коэффициентов в уравнениях.

5.1. Размещение компонент на форме и их настройка.

Создание формы происходит стандартным путем и описано в п. 4.

Сохраняем форму под именем предлагаемым по умолчанию « Unit3.cpp «.

После создания формы получим объект с именем Form3 . С помощью этого объекта можно будет использовать методы и свойства формы Form3 .

Данной форме отвечают файлы с именами « Unit3.h «, « Unit3.cpp » и « Unit3.dfm «.

Сначала осуществим настройку свойств формы Form3 так, как описано в п. 4:
– свойство Caption = «Ввод коэффициентов уравнений «;
– свойство BorderStyle = bsDialog ;
– свойство Position = poScreenCenter ;
– в свойстве Font нужно выбрать параметры шрифта: шрифт Tahoma , размер шрифта 12 .

Для построения формы ввода коэффициентов уравнений используем такие компоненты:
– два компонента типа TLabel . Автоматически будут созданы объекты с такими именами: label1 и label2 ;
– компонент типа TStringGrid (рис. 13) для ввода коэффициентов, которые размещаются в левой части системы уравнений.

Компонент TStringGrid размещается во вкладке Additional панели инструментов « Tool Palette «. Создается объект с именем StringGrid1 ;
– компонент типа TStringGrid (рис. 13) для введения коэффициентов, которые размещаются в правой части системы уравнений. Создается объект с именем StringGrid2 ;
– два компонента типа TButton (кнопки « » и « Продолжить >> «). Создаются два объекта с именами Button1 и Button2 .

Рис. 13. Компонент TStringGrid на палитре компонент

После размещения компонент и корректировки их размеров, форма Form3 будет иметь приблизительно следующий вид (рис. 14).

Рис. 14. Форма Form3

Формируем свойства компонент формы Form3:
– в компоненте Label1 свойство Caption = « Коэффициенты в левой части уравнения «;
– в компоненте Label2 свойство Caption = «Правая часть» ;
– в компоненте Button1 свойство Caption = « ;
– в компоненте Button2 свойство Caption = «Далее >>» .

Формируем свойства компонентов типа TStringGrid :
– в компоненте StringGrid1 свойство FixedCols = 0 (число фиксированных колонок);
– в компоненте StringGrid1 свойство FixedRows = 0 (число фиксированных строк);
– в компоненте StringGrid2 свойство FixedCols = 0 ;
– в компоненте StringGrid2 свойство FixedRows = 0 ;
– в компоненте StringGrid1 выбираем вкладку Options и устанавливаем опцию goEditing в значение « true «;
– в компоненте StringGrid2 во вкладке Options опция goEditing = « true «.

Рис. 15. Установление опции goEditing во вкладке Options компонента StringGrid1

После выполненных действий, форма Form3 будет иметь вид как показано на рисунке 16.

Рис. 16. Форма Form3 после окончательного формирования

5.2. Программирование обработчиков событий формы Form3 .

Программируем обработчики событий OnClick клика на кнопках Button1 и Button2 формы Form3 .

Листинг обработчиков событий приведен ниже.

6. Создание формы вывода результата.

Последней в приложении создается форма, которая будет выводить результат вычислений. Процесс создания и сохранения формы подробно описан здесь. При сохранении формы оставляем имя по умолчанию « Unit4.cpp «.

В результате получаем объект с именем Form4 .

Новосозданная форма Form4 описывается в файле « Unit4.dfm «. Также форме отвечают файлы « Unit4.h » и « Unit4.cpp «.

6.1. Построение формы Form4 .

Сначала настраиваем свойства формы Form4 :
– свойство Caption = «Результат» ;
– свойство BorderStyle = bsDialog ;
– свойство Position = poScreenCenter ;
– в свойстве Font нужно выбрать следующие параметры шрифта: шрифт Tahoma , размер шрифта 12 .

Также корректируем размеры формы.

Следующим шагом идет размещение на форме компонент.

Размещаем на форме следующие компоненты (рис. 17):
– один компонент типа TLabel ;
– два компонента типа TStringGrid ;
– один компонент типа TButton .

Корректируем размеры и позиции компонент для удобного отображения.

После размещения компонент будут созданы объекты с такими именами: Label1 , StringGrid1 , StringGrid2 , Button1 . В компоненте StringGrid1 выводятся номера переменных величин x в уравнении. В компоненте StringGrid2 выводятся значения решения системы уравнений.

Настраиваем компоненты формы следующим образом:
– в компоненте Label1 свойство Caption = «Решение системы» ;
– в компоненте Button1 свойство Caption = «OK» ;
– в компоненте StringGrid1 свойства FixedCols = 0 и FixedRows = 0 ;
– в компоненте StringGrid2 свойства FixedCols = 0 и FixedRows = 0 .

После размещения и настройки компонент, форма Form4 будет иметь вид, как показано на рисунке 17.

Рис. 17. Форма Form4 после окончательного формирования

6.2. Программирование события клика на кнопке « ОК » формы Form4 .

Листинг обработчика события клика на кнопке « ОК » следующий:

7. Написание программного кода расчета.

7.1. Подключение модулей «Unit2.h», «Unit3.h», «Unit4.h» к модулю «Unit1.h».

Для того, чтобы из главной формы приложения Form1 вызвать второстепенные формы, нужно осуществить их подключения в модуле « Unit1.h «.

Подключение модулей форм Form2 , Form3 , Form4 к форме Form1 осуществляется стандартным для языка C/C++ способом.

Сначала нужно перейти в модуль « Unit1.h «.

Затем после строк

Видео:Математика без Ху!ни. Метод Гаусса.Скачать

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

Дана система линейных алгебраических уравнений (СЛАУ) с неизвестными. Требуется решить эту систему: определить, сколько решений она имеет (ни одного, одно или бесконечно много), а если она имеет хотя бы одно решение, то найти любое из них.

Формально задача ставится следующим образом: решить систему:

где коэффициенты и известны, а переменные — искомые неизвестные.

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

где — матрица , составленная из коэффициентов , и — векторы-столбцы высоты .

Стоит отметить, что СЛАУ может быть не над полем действительных чисел, а над полем по модулю какого-либо числа , т.е.:

— алгоритм Гаусса работает и для таких систем тоже (но этот случай будет рассмотрен ниже в отдельном разделе).

Видео:Система линейных уравнений. Общее решение. Метод ГауссаСкачать

Алгоритм Гаусса

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

Базовая схема

Кратко говоря, алгоритм заключается в последовательном исключении переменных из каждого уравнения до тех пор, пока в каждом уравнении не останется только по одной переменной. Если , то можно говорить, что алгоритм Гаусса-Жордана стремится привести матрицу системы к единичной матрице — ведь после того как матрица стала единичной, решение системы очевидно — решение единственно и задаётся получившимися коэффициентами .

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

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

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

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

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

Поиск опорного элемента (pivoting)

Разумеется, описанная выше схема неполна. Она работает только в том случае, если на каждом -ом шаге элемент отличен от нуля — иначе мы просто не сможем добиться обнуления остальных коэффициентов в текущем столбце путём прибавления к ним -ой строки.

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

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

К счастью, для корректности метода достаточно одних только обменов строк (т.н. «partial pivoting», в отличие от «full pivoting», когда обмениваются и строки, и столбцы). Но какую же именно строку следует выбирать для обмена? И правда ли, что поиск опорного элемента надо делать только тогда, когда текущий элемент нулевой?

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

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

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

Без этой эвристики, даже если система такова, что на каждой -ой фазе — алгоритм Гаусса-Жордана отработает, но в итоге накапливающаяся погрешность может оказаться настолько огромной, что даже для матриц размера около погрешность будет превосходить сам ответ.

Вырожденные случаи

Итак, если останавливаться на алгоритме Гаусса-Жордана с partial pivoting, то, утверждается, если и система невырождена (т.е. имеет ненулевой определитель, что означает, что она имеет единственное решение), то описанный выше алгоритм полностью отработает и придёт к единичной матрице (доказательство этого, т.е. того, что ненулевой опорный элемент всегда будет находиться, здесь не приводится).

Рассмотрим теперь общий случай — когда и не обязательно равны. Предположим, что опорный элемент на -ом шаге не нашёлся. Это означает, что в -ом столбце все строки, начиная с текущей, содержат нули. Утверждается, что в этом случае эта -ая переменная не может быть определена, и является независимой переменной (может принимать произвольное значение). Чтобы алгоритм Гаусса-Жордана продолжил свою работу для всех последующих переменных, в такой ситуации надо просто пропустить текущий -ый столбец, не увеличивая при этом номер текущей строки (можно сказать, что мы виртуально удаляем -ый столбец матрицы).

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

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

Впрочем, проще это проверить явной подстановкой найденного решения: всем независимыми переменным присвоить нулевые значения, зависимым переменным присвоить найденные значения, и подставить это решение в текущую СЛАУ.

Видео:12. Метод Гаусса решения систем линейных уравнений. Часть 1.Скачать

Реализация

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

На вход функции передаётся сама матрица системы . Последний столбец матрицы — это в наших старых обозначениях столбец свободных коэффициентов (так сделано для удобства программирования — т.к. в самом алгоритме все операции со свободными коэффициентами повторяют операции с матрицей ).

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

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

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

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

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

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

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

Асимптотика

Оценим асимптотику полученного алгоритма. Алгоритм состоит из фаз, на каждой из которых происходит:

поиск и перестановка опорного элемента — за время при использовании эвристики «partial pivoting» (поиск максимума в столбце)
если опорный элемент в текущем столбце был найден — то прибавление текущего уравнения ко всем остальным уравнениям — за время

Очевидно, первый пункт имеет меньшую асимптотику, чем второй. Заметим также, что второй пункт выполняется не более раз — столько, сколько может быть зависимых переменных в СЛАУ.

Таким образом, итоговая асимптотика алгоритма принимает вид .

При эта оценка превращается в .

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

Более точная оценка числа действий

Для простоты выкладок будем считать, что .

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

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

Видео:Общее, частное, базисное решение системы линейных уравнений Метод ГауссаСкачать

Дополнения

Ускорение алгоритма: разделение его на прямой и обратный ход

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

В целом, в отличие от описанного выше алгоритма, можно приводить матрицу не к диагональному виду, а к треугольному виду — когда все элементы строго ниже главной диагонали равны нулю.

Система с треугольной матрицей решается тривиально — сначала из последнего уравнения сразу находится значение последней переменной, затем найденное значение подставляется в предпоследнее уравнение и находится значение предпоследней переменной, и так далее. Этот процесс и называется обратным ходом алгоритма Гаусса.

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

Разница в том, что прямой ход работает быстрее алгоритма Гаусса-Жордана — поскольку в среднем он делает в два раза меньше прибавлений одного уравнения к другому. Обратный ход работает за , что в любом случае асимптотически быстрее прямого хода.

Таким образом, если , то данный алгоритм будет делать уже операций — что в два раза меньше алгоритма Гаусса-Жордана.

Решение СЛАУ по модулю

Для решения СЛАУ по модулю можно применять описанный выше алгоритм, он сохраняет свою корректность.

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

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

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

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

Если модуль произвольный (не обязательно простой), то всё становится несколько сложнее. Понятно, что пользуясь Китайской теоремой об остатках, мы сводим задачу с произвольным модулем только к модулям вида «степень простого». [ дальнейший текст был скрыт, т.к. это непроверенная информация — возможно, неправильный способ решения ]

Наконец, рассмотрим вопрос числа решений СЛАУ по модулю. Ответ на него достаточно прост: число решений равно , где — модуль, — число независимых переменных.

Немного о различных способах выбора опорного элемента

Как уже говорилось выше, однозначного ответа на этот вопрос нет.

Эвристика «partial pivoting», которая заключалась в поиске максимального элемента в текущем столбце, работает на практике весьма неплохо. Также оказывается, что она даёт практически тот же результат, что и «full pivoting» — когда опорный элемент ищется среди элементов целой подматрицы — начиная с текущей строки и с текущего столбца.

Но интересно отметить, что обе эти эвристики с поиском максимального элемента, фактически, очень зависят от того, насколько были промасштабированы исходные уравнения. Например, если одно из уравнений системы умножить на миллион, то это уравнение почти наверняка будет выбрано в качестве ведущего на первом же шаге. Это кажется достаточно странным, поэтому логичен переход к немного более сложной эвристике — так называемому «implicit pivoting».

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

Улучшение найденного ответа

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

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

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

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