 |
Точные методы решения СЛАУ
|
|
|
|
Рассмотрим ряд точных методов решения СЛАУ [4,5].
Решение систем n-линейных уравнении с n-неизвестными по формулам Крамера.
Пусть дана система линейных уравнений, в которой число уравнений равно числу неизвестных:
Предположим, что определитель системы d не равен нулю. Если теперь заменить последовательно в определителе столбцы коэффициентов при неизвестных хj столбцом свободных членов bj, то получатся соответственно n определителей d1,...,dn.
Теорема Крамера. Система n линейных уравнений с n неизвестными, определитель которой отличен от нуля, всегда совместна и имеет единственное решение, вычисляемое по формулам:
x1=d1/d; x2=d2/d;....; xn-1=dn-1/d; xn=dn/d;
Решение произвольных систем линейных уравнений.
Пусть
произвольная система линейных уравнений, где число уравнений системы не равно числу n неизвестных. Предположим, что система (3) совместна и r 
min{m,n}, тогда в матрицах А и А найдутся r линейно независимых строк, а остальные m-r строк окажутся их линейными комбинациями. Перестановкой уравнений можно добиться того, что эти r линейно независимых строк займут первые r мест.
Отсюда следует, что любое из последних m - r уравнений системы (3) можно представить как сумму первых r уравнений (которые называются линейно независимыми или базисными), взятых с некоторыми коэффициентами. Тогда система эквивалентна следующей системе r уравнений с n неизвестными
Предположим, что минор r-го порядка, составленный из коэффициентов при первых r неизвестных, отличен от нуля Мr 
0, т. е. является базисным минором. В этом случае неизвестные, коэффициенты при которых составляют базисный минор, называются базисными неизвестными, а остальные n - r - свободными неизвестными.
|
|
|
В каждом из уравнений системы (4) перенесем в правую часть все члены со свободными неизвестными xr+1,..., xn. Тогда получим систему, которая содержит r уравнений с r базисными неизвестными. Так как определитель этой системы есть базисный минор Mr то система имеет единственное решение относительно базисных неизвестных, которое можно найти по формулам Крамера. Давая свободным неизвестным произвольные числовые значения, получим общее решение исходной системы.
Однородная система линейных уравнений.
Пусть дана однородная система линейных уравнений n неизвестными
Так как добавление столбца из нулей не изменяет ранга матрицы системы, то на основании теоремы Кронекера - Kaneлли эта система всегда совместна и имеет, по крайней мере, нулевое решение. Если определитель системы (5) отличен от нуля и число уравнений системы равно числу неизвестных, то по теореме Крамера нулевое решение является единственным.
В том случае, когда ранг матрицы системы (5) меньше числа неизвестных, т. е. r (А)< n, данная система кроме нулевого решения будет иметь и ненулевые решения. Для нахождения этих решений в системе (5) выделяем r линейно независимых уравнений, остальные отбрасываем. В выделенных уравнениях в левой части оставляем r базисных неизвестных, а остальные n - r свободных неизвестных переносим в правую часть. Тогда приходим к системе, решая которую по формулам Крамера, выразим r базисных неизвестных x1,..., хr через n - r свободных неизвестных.
Система (5) имеет бесчисленное множество решений. Среди этого множества есть решения, линейно независимые между собой.
Фундаментальной системой решений называются n - r линейно независимых решений однородной системы уравнений.
Метод главных элементов.
Пусть дана система n линейных уравнений с n неизвестными
расширенная матрица системы (6) 
. Выберем ненулевой наибольший по модулю и не принадлежащий столбцу свободных членов элемент apq матрицы , который называется главным элементом, и вычислим множители mi=-aiq/apq для всех строк с номерами i p (р - я строка, содержащая главный элемент, называется главной строкой).
|
|
|
Далее к каждой неглавной i-й строке прибавим главную строку, умноженную на соответствующий множитель mi; для этой строки.
В результате получим новую матрицу, все элементы q-го столбца которой, кроме apq, состоят из нулей.
Отбросив этот столбец и главную p-ю получим новую матрицу, число строк и столбцов которой на единицу меньше. Повторяем те же операции с получившейся матрицей, после чего получаем новую матрицу и т.д.
Таким образом, построим последовательность матриц, последняя из которых является двучленной матрицей-строкой (главной строкой). Для определения неизвестных xi объединяем в систему все главные строки, начиная с последней.
Изложенный метод решения системы линейных уравнений с n неизвестными называется методом главных элементов. Необходимое условие его применения состоит том, что определитель матрицы не равен нулю [6,7].
Схема Халецкого.
Пусть система линейных уравнений дана в матричном виде.
Ax=b (7)
Где А - квадратная матрица порядка n, а x,b - векторы столбцы.
Представим матрицу А в виде произведения нижней треугольной матрицы С и верхней треугольной матрицы В с единичной диагональю, т.е.
А=СВ,
Где
, 
Причем элементы сij и bij определяются по формулам:
,
Уравнение (7) можно записать в следующем виде:
CBx=b. (9)
Произведение Bx матрицы B на вектор-столбец x является вектором-столбцом, который обозначим через y:
Bx=y. (10)
Тогда уравнение (9) перепишем в виде:
Cy=b. (11)
Здесь элементы сij известны, так как матрица А системы (7) считается уже разложенной на произведение двух треугольных матриц С и В.
Перемножив матрицы в левой части равенства (11), получаем систему уравнений из которой получаем следующие формулы для определения неизвестных:
неизвестные yi удобно вычислять вместе с элементами bij.
После того как все yi определены по формулам (12), подставляем их в уравнение(10).
Так как коэффициенты bij определены (8), то значения неизвестных, начиная с последнего, вычисляем по следующим формулам:
К прямым методам, использующим свойство разреженности А, можно отнести: алгоритм минимальной степени, алгоритм минимального дефицита, древовидное блочное разбиение для асимметричного разложения, методы вложенных или параллельных сечений и др.
|
|
|
Метод Гаусса.
Пусть дана система
Ax = b
где А – матрица размерности m x m.
В предположении, что 
, первое уравнение системы
, 
делим на коэффициент 
, в результате получаем уравнение
Затем из каждого из остальных уравнений вычитается первое уравнение, умноженное на соответствующий коэффициент 
. В результате эти уравнения преобразуются к виду
первое неизвестное оказалось исключенным из всех уравнений, кроме первого. Далее в предположении, что 
, делим второе уравнение на коэффициент 
и исключаем неизвестное из всех уравнений, начиная со второго и т.д. В результате последовательного исключения неизвестных система уравнений преобразуется в систему уравнений с треугольной матрицей
Совокупность проведенных вычислений называется прямым ходом метода Гаусса.
Из 
-го уравнения системы (2) определяем 
, из (
)-го уравнения определяем 
и т.д. до 
. Совокупность таких вычислений называют обратным ходом метода Гаусса.
Реализация прямого метода Гаусса требует 
арифметических операций, а обратного - 
арифметических операций.
|
|
|
