Метод Гаусса для решения СЛАУ

Необходимо разработать программу для решения систем линейных алгебраических уравнений (СЛАУ).
Порядок СЛАУ должен быть произвольным и задаваться пользователем с клавиатуры.
Элементы матрицы коэффициентов СЛАУ и столбца свободных членов должны также запрашиваться у пользователя.
...

Введение………………………………………………………………………….4
1. Постановка задачи…………………………………………………………….5
1.1. Анализ существующих решений поставленной задачи…………………6
1.1.1. Метод Гаусса……………………………………………………………7
1.1.2. LU–метод………………………………………………………………..9
1.1.3. Метод квадратного корня……………………………………………...11
1.1.4. Метод вращений решения линейных систем…………………………13
1.2. Обоснования выбора метода решения задачи...………………………...16
1.3. Математическая модель…………………………………………………..18
2. Разработка алгоритма решения………....................………………………...21
3. Разработка задачи…………………..………………………………………...24
3.1. Описание программы..…………………………………………………....24
3.2. „Руководство програмиста”........................................................................26
3.3. „Руководство оператора”............................................................................28
Вывод……………………………………………………………………………29
Список литературы……………………………………………………………..30
Приложение А: Текст программы......................................................................31

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

Присутствие в названии дисциплины термина «программирование» объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово «programming» означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (из учение оптимальной экономической программы). Термин «линейное программирование» был предложен Дж. Данцигом в 1949 г. для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях. Поэтому наименование «Математическое программирование» связано с тем, что целью решения задач является выбор оптимальной программы действий.

Теперь перейдем к вопросу как же добиться того, чтобы система стала треугольной.
Из линейной алгебры известно что если к некоторой строке системы уравнений прибавить любую линейную комбинацию любых других строк этой системы, то решение системы не изменится. Под линейной комбинацией строк понимается сумма строк, каждая из которых умножается на некоторое число (в принципе, любое).
Нужно, чтобы во второй строке получилось уравнение, в которой отсутствует член при x1. Прибавим к этой строке первую строку, умноженную на некоторое число M.
(a11x1 + a12x2 + a13x3 + ... a1NxN = b1)*M + a21x1 + a22x2 + a23x3 + ... a2NxN = b2
Получим
(a11*М + a21) x1 + ... = b1*M + b2
Для того, чтобы член при x1 равнялся нулю, нужно, чтобы M = - a21 / a11. Проделав эту операцию, получившееся уравнение запишемвместо второго и приступим к третьему уравнению. К нему мы прибавим первое уравнение, умноженное на M = - a31 / a11 и тоже получим ноль вместо члена при x1. Такую операцию нужно проделать над всеми остальными уравнениями. В результате получим систему такого вида:
a11x1 +
a12x2 +
a13x3 +
...
a1NxN = b1
a22x2 +
a23x3 +
...
a2NxN = b2
a32x2 +
a33x3 +
...
a3NxN = b3
...
aN2x2 +
aN3x3 +
...
aNNxN = bN
После этого будем избавляться от членов при x2 в третьем, четвертом, N-ом уравнении. Для этого нужно к уравнению с j-м номером прибавить 2-ое уравнение, умноженное на M = - aj2 / a22. Проделав эту операцию над всеми остальными уравнениями, получим систему где нет членов с x2 в уравнениях с номером больше 2.
И так далее... Проделав это для третьего члена, четвертого... до тех пор, пока не кончатся уравнения, получим в итоге систему треугольного вида.
Алгоритм описан в псевдокоде (команды в виде текста на русском языке).
Поскольку весь метод уже описан, коротко опишу, как эта программа
получает уравнения на вход, что выдает в результате решения.
3. Разработка задачи
3.1. Описание программы
Программа предназначена для решения систем линейных уровнений. Представлена в программе Borland C++. Имеет объем 170 строк. Текс программы можно описать таким образом:
Решение СЛАУ методом Гаусса.
Распределение данных - горизонтальными полосами.
Каждая ветвь задает размеры своих полос матрицы MA и вектора правой части.
Описываем массивы для полос исходной матрицы - MA и вектор V для приема данных. Для простоты, вектор правой части уравнений присоединяем дополнительным столбцом к матрице коэффициентов. В этом дополнительном столбце и получим результат.
Инициализация библиотеки
Каждая ветвь узнает размер системы
и свой номер (ранг)
Выделяем память под массивы для описания вершин и ребер в топологии полный граф
Заполняем массивы для описания вершин и ребер для топологии полный граф и задаем топологию "полный граф".
Каждая ветвь генерирует свою полосу матрицы A и свой отрезок вектора правой части, который присоединяется дополнительным столбцом к A. Нулевая ветвь генерирует нулевую полосу, первая ветвь - первую полосу и т.д. (По диагонали исходной матрицы - числа = 2, остальные числа = 1).
Каждая ветвь засекает начало вычислений и производит вычисления
Прямой ход
  Цикл p - цикл по компьютерам. Все ветви, начиная с нулевой, последовательно приводят к диагональному виду свои строки. Ветвь, приводящая свои строки к диагональному виду, назовем активной, строка, с которой производятся вычисления, так же назовем активной.
Цикл k - цикл по строкам. (Все веиви "крутят" этот цикл).
Активная ветвь с номером MyP == p приводит свои строки к диагональному виду.
  Активная строка k передается ветвям, с номером большим чем MyP Работа принимающих ветвей с номерами MyP > p
Обратный ход
 Циклы по p и k аноалогичны, как и при прямом ходе.
Работа активной ветви
Работа ветвей с номерами MyP < p
Все ветви засекают время и печатают
Все ветви печатают, для контроля, свои первые четыре значения корня
Все ветви завершают выполнение
Конец программы
3.2. Рекомендации программиста
Программа была написана с целью облегчения решения систем линейных уровнений. Программа написана в программе Borland C++.
Чтобы воспользоваться этой программой, нужно запустить
скомпилированный исполняемый файл. В первую очередь программа
спросит, откуда ей брать коэффициенты для уравнений. Создайте в любом
текстовом редакторе (но только не в Word-е а, например в notepad-е) файл,
где напишите коэффициенты уравнений построчно через пробел,
приблизительно так:
a11
a12
a13
…
a1N
b1
a21
a22
a23
…
a2N
b2
a31
a32
a33
…
a3N
b3
aN1
aN2
aN3
…
aNN
bN
Например:
2
-3
1
5
-1
-1
2
1
2
-1
3
Этот файл необходимо создать в той директории, где лежит программа,
иначе она его не найдет. В результате работы программы, она выдаст
результат, нечто вроде:
X0 = 3.000000
X1 = 1.000000
X2 = 2.000000
Это и есть решение системы уравнений, т.е. набор неизвестных Х.
Коротко опишем, для чего служит такое большое количество подпрограмм в данной программе:
void count_num_lines() – подсчитывает количество уравнений в системе
void allocmatrix() – выделяет память для массивов для хранения коэффициентов уравнений, свободных членов и решения
void readmatrix() – прочитывает из файла коэффициенты и свободные члены в массивы
void printmatrix() – распечатывает систему уравнений
void diagonal() – делает так, чтобы на главной диагонали не было нулей, чтобы не пришлось однажды делить на ноль в процессе приведения матрицы к треугольному виду
void testsolve() – подставляет решение в систему и распечатывает рядом то, что получается в левой части уравнения и для сравнения печатает рядом свободные члены, те, что в правой части уравнения; получившиеся два столбца должны совпадать, если уравнения решены правильно
void printresult() – распечатывает получившийся столбец решений
void freematrix() – освобождает память, которая была выделена ранее
void cls() – стирает экран в начале работы программы
void main() – основная функция из которой последовательно вызываются все вышеперечисленные функции, и проходит процесс приведения системы уравнений к треугольному виду и обратная прогонка.
3.3. Рекомендации оператора
Программа предназначена для облегчения решения систем линейных уровненний. Решение СЛАУ происходит не отнимает много времени, от пользователя требуется лишь ввести свои исходные данные. Программа предназначена для общего пользования.
Чтобы воспользоваться этой программой, нужно запустить
скомпилированный исполняемый файл. В первую очередь программа
спросит, откуда ей брать коэффициенты для уравнений. Создайте в любом
текстовом редакторе (но только не в Word-е а, например в notepad-е) файл,
где напишите коэффициенты уравнений построчно через пробел,
приблизительно так:
a11
A12
a13
…
a1N
b1
a21
A22
a23
…
a2N
b2
a31
A32
a33
…
a3N
b3
aN1
aN2
aN3
…
aNN
bN