 |
Прямые методы решения СЛАУ
|
|
|
|
Метод Крамера
При небольшой размерности системы m (m = 2,…,5) на практике часто используют формулы Крамера для решения СЛАУ:
(i = 1, 2, …, m). Эти формулы позволяют находить неизвестные в виде дробей, знаменателем которых является определитель матрицы системы, а числителем – определители матриц Ai, полученных из A заменой столбца коэффициентов при вычисляемом неизвестном столбцом свободных членов. Так А1 получается из матрицы А заменой первого столбца на столбец правых частей f.
Например, для системы двух линейных уравнений
Размерность системы (т.е., число m) является главным фактором, из–за которого формулы Крамера не могут быть использованы для численного решения СЛАУ большого порядка. При непосредственном раскрытии определителей решение системы с m неизвестными требует порядка m!*m арифметических операций. Таким образом, для решения системы, например, из m = 100 уравнений потребуется совершить 10158 вычислительных операций (процесс займёт примерно 1019 лет), что не под силу даже самым мощным современным ЭВМ
Метод обратной матрицы
Если det A ≠ 0, то существует обратная матрица 
. Тогда решение СЛАУ записывается в виде: 
. Следовательно, решение СЛАУ свелось к умножению известной обратной матрицы на вектор правых частей. Таким образом, задача решения СЛАУ и задача нахождения обратной матрицы связаны между собой, поэтому часто решение СЛАУ называют задачей обращения матрицы. Проблемы использования этого метода те же, что и при использовании метода Крамера: нахождение обратной матрицы – трудоемкая операция.
Метод Гаусса
Наиболее известным и популярным прямым методом решения СЛАУ является метод Гаусса. Этот метод заключается в последовательном исключении неизвестных. Пусть в системе уравнений
|
|
|
первый элемент 
. Назовем его ведущим элементом первой строки. Поделим все элементы этой строки на 
и исключим x1 из всех последующих строк, начиная со второй, путем вычитания первой (преобразованной), умноженной на коэффициент при 
в соответствующей строке. Получим
.
Если 
, то, продолжая аналогичное исключение, приходим к системе уравнений с верхней треугольной матрицей
.
Из нее в обратном порядке находим все значения xi:
.
Процесс приведения к системе с треугольной матрицей называется прямым ходом, а нахождения неизвестных – обратным. В случае если один из ведущих элементов равен нулю, изложенный алгоритм метода Гаусса неприменим. Кроме того, если какие–либо ведущие элементы малы, то это приводит к усилению ошибок округления и ухудшению точности счета. Поэтому обычно используется другой вариант метода Гаусса – схема Гаусса с выбором главного элемента. Путем перестановки строк, а также столбцов с соответствующей перенумерацией коэффициентов и неизвестных добиваются выполнения условия:
, j = i+1,i+ 2, …, m;
т.е. осуществляется выбор первого главного элемента. Переставляя уравнения так, чтобы в первом уравнении коэффициент a11 был максимальным по модулю. Разделив первую строку на главный элемент, как и прежде, исключают x1 из остальных уравнений. Затем для оставшихся столбцов и строк выбирают второй главный элемент и т.д.
Рассмотрим применение метода Гаусса с выбором главного элемента на примере следующей системы уравнений:
В первом уравнении коэффициент при =0, во втором = 1 и в третьем = -2, т.е. максимальный по модулю коэффициент в третьем уравнении. Поэтому переставим третье и первое уравнение:
Исключим из второго и третьего уравнений с помощью первого. Во втором уравнении исключать не надо. Для исключения из третьего уравнения умножим первое на 0.5 и сложим с третьим:
|
|
|
Рассмотрим второе и третье уравнения. Максимальный по модулю элемент при 
в третьем. Поэтому поместим его на место второго:
Исключим из третьего уравнения. Для этого умножим второе на -0.5 и сложим с третьим:
Обратный ход: 
.
Проверка: 0.5*8+0=4, -3+8-0=5, -2*(-3)+0=6.
Такая перестановка уравнений необходима для того, чтобы уменьшить влияние ошибок округления на конечный результат.
Часто возникает необходимость в решении СЛАУ, матрицы которые являются слабо заполненными, т.е. содержат много нулевых элементов. В то же время эти матрицы имеют определенную структуру. Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях. Для решения систем с ленточными матрицами коэффициентов вместо метода Гаусса можно использовать более эффективные методы. Например, метод прогонки, который мы рассмотрим позже при решении краевой задачи для обыкновенного дифференциального уравнения второго порядка.
|
|
|
