Решение систем линейных алгебраических уравнений (СЛАУ)

Дана система линейных алгебраических уравнений

Ax = B

Необходимо найти из этого уравнения вектор х.

Методы решения СЛАУ делятся на прямые и итерационные.

Прямые методы дают точное решение за конечное число арифметических операций. Недостатком прямых методов является то, что на ЭВМ вычисления делаются с погрешностью, а это может привести к тому, что полученное решение будет неверным. При хорошо обусловленной матрице А прямые методы необходимо использовать при размерности матрицы А n <= 200.

Итерационные методы основаны на построении сходящейся к точному решению рекуррентной последовательности. В отличие от прямых методов итерационные дают решение с заданной погрешностью за неизвестное заранее число действий.

Метод исключения Гаусса

Метод исключения Гаусса является прямым методом, суть которого основана к сведению исходной СЛАУ к СЛАУ с верхней треугольной матрицей.

На первом шаге комбинацией 1-й строки и i -й строки (i =2.. n) обнуляется 1-й столбец матрицы, начиная со второго элемента. Для этого 1-я строка A и 1-й элемент B делятся на a ₁₁ и умножается на a_{i 1} для соответственно i -й строки. Далее из получившейся 1-й строки вычитается i -я:

…………………………………

На втором шаге аналогичными преобразованиями обнуляется второй столбец матрицы А начиная с 3-го элемента. Аналогичные действия проводятся для всех столбцов до (n – 1)-го. В результате этих преобразований получается система с верхней треугольной матрицей:

Эта система решается с конца:

x_n = d_n / c_nn

Подставная x_n в предпоследнее уравнение легко найти x_{n –1} и т. д. до получения x ₁.

Метод Зейделя

Метод является итерационным. В качестве начального приближения задается вектор решения x ₀.

В основе метода Зейделя лежит последовательное вычисление x ₁, x ₂ и т. д. из соответственно 1-го, 2-го и т. д. уравнений системы.

Первый шаг итерации начинается тем, что из первого уравнения вычисляется x ₁¹:

Далее определяется погрешность E=|x₁¹ – x₁⁰| и полагается x ₁⁰ = x ₁¹.

Из второго уравнения аналогичным образом вычисляется x ₂¹:

По x ₂¹ и x ₂⁰ определяется очередное значение погрешности E=max(E,| x ₂¹- x ₂⁰|) и полагается x ₂⁰ = x ₂¹. Процесс вычисления x_j ¹ по аналогии с x ₂¹ продолжается до вычисления x_N ¹. Первый шаг итерации заканчивается проверкой Е на допустимую погрешность. Ели Е больше допустимой погрешности, то выполняется очередной шаг итерации начиная с вычисления x ₁¹. Если Е окажется меньше допустимой погрешности, то итерационный процесс завершается с решением в векторе x ⁰.

Метод простой итерации

Сутьметода основана на сведении исходного уравнения

Аx = В

к виду

x = x + u (Ax – B),

где u — произвольная константа, подбираемая индивидуально для каждого уравнения из условия наилучшей сходимости итерационного процесса.

В качестве начального приближения в методе задается вектор x ⁰. Затем вычисляется новое приближение вектора x

x ¹ = x ⁰ + u (Ax ⁰ – B)

и погрешность E= . Если Е окажется меньше погрешности, то решение в x ¹. В противном случае полагается x ⁰ = x ¹ и итерационный процесс продолжается с вычисления очередного x ¹.