Методы решения систем линейных уравнений (стр. 1 из 3)

Методы решения систем линейных уравнений

1. Решение системы линейных уравнений методом Гаусса

Задачи аппроксимации функции, а также множество других задач прикладной математики м вычислительной физики сводятся к задачам о решении систем линейных уравнений. Самым универсальным методом решения системы линейных уравнений является метод последовательного исключения неизвестных, называемый методом Гаусса.

Для иллюстрации смысла метода Гаусса рассмотрим систему линейных уравнений:

(1)

Эту систему запишем в матричном виде:

(2)

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

На первом шаге прямого хода умножим первое уравнение на

и вычтем из второго, тогда исключится переменная из второго уравнения. Затем, умножим первое уравнение на и вычтем из третьего, тогда система (2) преобразуется в систему вида:

(3)

На втором шаге прямого хода из третьего уравнения исключаем

, т.е. из третьего уравнения вычитаем второе, умноженное, на , что приводит систему (3) к треугольному виду (4)

(4)

Систему (4) переписываем в привычном виде:

(5)

Теперь, из системы (5) можем находить решение в обратном порядке, т.е. сначала находим из третьего уравнения

, далее, подставляя во второе уравнение, находим . Подставляя и в первое уравнение системы (5), находим . Нахождение решения из системы (5) называют обратным ходом.

Теперь, на основе рассмотренного примера, составим общий алгоритм метода Гаусса для системы:

(6)

Метод Гаусса состоит из двух этапов:

а) прямой ход – когда матрица системы (6) приводится к треугольному виду;

б) обратный ход – когда последовательно вычисляются неизвестные в обратном порядке, т.е. в последовательности:

.

а) Прямой ход: для приведения системы (6) к треугольному виду, уравнения с ненулевыми коэффициентами при переменной

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

(7)

Далее, применяем туже самую процедуру, для уравнений системы (7), начиная со второго уравнения, т.е. первое уравнение исключается из «игры». Теперь стараемся обнулить коэффициенты при переменной

, начиная с третьего уравнения и т.д., пока не приведём систему к треугольному виду. Если , то система всегда приводима (теоретически) к треугольному виду. Общий алгоритм прямого хода можно представить в виде:

(8)

б) Обратный ход: Вычисляем неизвестные по формулам:

(9)

Замечание: для вычисления определителя системы можно использовать треугольную форму полученной матрицы, тогда определитель этой матрицы равен произведению диагональных элементов, т.е.

(10)

2. Метод Гаусса с выбором главного элемента

Метод Гаусса настолько универсален, что для некоторых систем получаются практически «плохие» результаты, поэтому разрабатываются различные хитрые выходы из ситуации. В случае, когда некоторые коэффициенты матрицы системы близки между собой, как известно относительные погрешности сильно возрастают при вычитании, поэтому классический метод Гаусса даёт большие погрешности. Чтобы обойти эту трудность, стараются в прямом ходе Гаусса выбрать то уравнение, у которого коэффициент при

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

Обратный ход происходит так же, как и в классическом методе Гаусса.

3. Оценка погрешности при решении системы линейных уравнений

Для того, чтобы оценить погрешности вычислений решения системы линейных уравнений, нам нужно ввести понятия соответствующих норм матриц.

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

:

(11)

(Евклидова норма) (12)

(Чебышевская норма) (13)

Для всякой нормы векторов можно ввести соответствующую норму матриц:

(14)

которая согласована с нормой векторов в том смысле, что

(15)

Можно показать, что для трёх приведённых выше случаев нормы матрицы

задаются формулами:

(16)

(17)

(18)

Здесь

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

Для вещественных симметричных матриц

- где - собственные числа матрицы .

Абсолютная погрешность решения системы:

(19)

где

- матрица системы, - матрица правых частей, оценивается нормой: