Материал из ProgSchool

Метод Гаусса

Лекции

• Решение СЛАУ методом Гаусса
• Ликбез по матрицам:
  • Простейшие операции над матрицами. Связь между ними.
  • Поиск обратной матрицы методом Гаусса
• Определитель матрицы

Задачи

Решение системы линейных алгебраических уравнений методом Гаусса (7 + 3*k)

• Работающий алгоритм на хороших случаях - 2 балла.
• Разбор случаев несовместных систем и систем с бесконечным числом решений - ещё 2 балла.
• Выбор главного элемента по столбцу - 1 балл.
• Красиво оформленный код, к которому у меня не будет замечаний - ещё 2 балла (разумеется, программа, которая ничего не умеет делать, не сможет получить 2 балла по этому пункту).
• Есть страница с тестами. Нужно придумать неправильное решение, которое проходит все эти тесты, а также предъявить пример, на котором бы решение работало неверно. Решение должно быть нетривиальным, т.е. это не должно быть просто узнавание предъявленных случаев и вывод заготовленного ответа. За каждое неверное решение, выявляющее неполноту существующих тестов, и дополнение в виде тестов, закрывающих эту прореху, можно получить по 3 балла.

Материалы по теме:

• http://www.uchites.ru/files/nummethod_book_chapter1-1.pdf
• http://referats.5-ka.ru/49/28103/1.html
• Study/Cycles/Gauss/Tests
• http://acmp.ru/index.asp?main=task&id_task=198

Примеры:

3
1 0 2 5
0 0 2 5
0 -1 2 10

0 -5 2.5

Также можно тестировать свои решения тут: Acmp-198

Вычисление определителя квадратной матрицы методом Гаусса (2)

В дополнение к решению СЛАУ можно получить 2 балла. Важно: обратите внимание на слово "квадратной". Значит, из файла считывается квадратная матрица.

Общий код алгоритма Гаусса для решения СЛАУ и вычисления определителя (2)

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

Я бы попробовал сделать так:

• алгоритм обрабатывает матрицу MxN, приводя её к диагональному виду, пока не упрётся куда-нибудь (в нули или в одну из сторон); на выход выдаёт полученную матрицу. Это общая часть программы.
• полученную матрицу каждая часть по-своему обрабатывает.
  • Модуль решения СЛАУ интересуется столбцом сводных членов и диагональю, получая ответ x_i = a[i][n+1]/a[i][i].
  • Модуль вычисления определителя перемножает диагональные элементы и получает ответ.

Вычисление обратной матрицы методом Гаусса (2)

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

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