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

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

Ax = B

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

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

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

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

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

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

На первом шаге комбинацией 1-й строки и i-й строки (i=2..n) обнуляется 1-й столбец матрицы, начиная со второго элемента. Для этого 1-я строка A и 1-й элемент B делятся на a₁₁ и умножается на a_i1 для соответственно 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¹.