Курсовая работа: Поиск решений системы линейных уравнений методом Гаусса

Цель задачи - зная a_ij и b_i найти x_i .

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

a11 x1 +	a12 x2 +	a13 x3 +	...	a1N xN = b1
a22 x2 +	a23 x3 +	...	a2N xN = b2
a33 x3 +	...	a3N xN = b3
...
...	aNN xN = bN

Особенность этой системы - в строках с номером i все коэффициенты a_ij при j<i равны нулю.

Если мы смогли привести нашу систему уравнений к такому треугольному виду, то решить уравнения уже просто. Из последнего уравнения находим x_N = b_N / a_NN . Дальше подставляем его в предпоследнее уравнение и находим из него x_N-1 . Подставляем оба найденных решения в следующее с конца уравнение и находим x_N-2 . И так далее, пока не найдем x₁ , на чем решение заканчивается. Такая процедура называется обратной прогонкой.

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

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

Нужно, чтобы во второй строке получилось уравнение, в которой отсутствует член при x₁ . Прибавим к этой строке первую строку, умноженную на некоторое число M.

(a₁₁ x₁ + a₁₂ x₂ + a₁₃ x₃ + ... a_1N x_N = b₁ )*M +

a₂₁ x₁ + a₂₂ x₂ + a₂₃ x₃ + ... a_2N x_N = b₂

Получим

(a₁₁ *М + a₂₁ ) x₁ + ... = b₁ *M + b₂

Для того, чтобы член при x₁ равнялся нулю, нужно, чтобы M = - a₂₁ / a₁₁ . Проделав эту операцию, получившееся уравнение запишем вместо второго и приступим к третьему уравнению. К нему мы прибавим первое уравнение, умноженное на M = - a₃₁ / a₁₁ и тоже получим ноль вместо члена при x₁ . Такую операцию нужно проделать над всеми остальными уравнениями. В результате получим систему такого вида:

a11 x1 +	a12 x2 +	a13 x3 +	...	a1N xN = b1
a22 x2 +	a23 x3 +	...	a2N xN = b2
a32 x2 +	a33 x3 +	...	a3N xN = b3
...
aN2 x2 +	aN3 x3 +	...	aNN xN = bN

После этого будем избавляться от членов при x₂ в третьем, четвертом, N-ом уравнении. Для этого нужно к уравнению с j-м номером прибавить 2-ое уравнение, умноженное на M = - a_j2 / a₂₂ . Проделав эту операцию над всеми остальными уравнениями, получим систему где нет членов с x₂ в уравнениях с номером больше 2.

И так далее... Проделав это для третьего члена, четвертого... до тех пор, пока не кончатся уравнения, получим в итоге систему треугольного вида.

Алгоритм описан в псевдокоде (команды в виде текста на русском языке).

ПРОЦЕСС 0: (главный процесс)

1.Разослать всем процессам количество текущих строк.

(Или не всем процессам, если процессов больше чем строк).

2.ЦИКЛ ПО СТРОКАМ (выбор текущей строки)

1.Разослать всем процессам текущую строку.

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

2.Разослать всем процессам строки для обработки (посылаем строку, затем строки в матрице). Разделить между процессами строки ниже текущей. Разделяем так в цикле по строкам раздаём по одной каждому процессу, пока не кончатся строки, по процессам 1..N идём циклически.

3.Разослать всем процессам количества строк, посланных им для обработки.

4.Принять от процессов 1..N обработанные строки, занести их в матрицу. (Принимаем строку и номер строки в матрице)

5.Выбрать следующую текущую строку - новый шаг цикла.

КОНЕЦ ЦИКЛА

3.Вычислить решение системы по диагональной матрице.

4.Выдать результат работы.

5.Завершить работу.