18. Методы решения систем линейных алгебраических уравнений.

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

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

,

где  – квадратная матрица размерности n×n,

  – вектор неизвестных величин размерности n,

  – вектор известных величин размерности n.

В развернутом (табличном) виде СЛАУ может быть переписана в виде:

a11x1+ a12x2 + a13x3 + × × × + a1nxn = b1, a21x1+ a22x2 + a23x3 + × × × + a2nxn = b2, × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × an1x1+ an2x2 + an3x3 + × × × + annxn = bn.

Метод Гаусса или метод последовательных исключений состоит в том, что из первого уравнения выражают x₁, и получают (n–1) уравнение относительно (n–1) неизвестного: x₂ ¸ x_n. Затем этот процесс повторяют, пока не останется одно уравнение относительно одного x_n неизвестного. Из этого уравнения находится неизвестное x_n, его значение подставляется в выражение для х_n-1, полученное на предыдущем шаге, затем в выражение для х_n-2, далее процесс повторяется пока не будут найдены все значения компонентов вектора .

При реализации этого алгоритма может возникнуть ситуация, когда коэффициент, на который следует поделить выражение равен 0. Например, система начинается с уравнения

0·x1+ a12x2 + a13x3 + × × × + a1nxn = b1

В таком случае следует переставить либо строки системы, либо ее столбцы, провести соответствующее перенумерование и продолжить решение.

При решении системы следует использовать метод ведущего элемента. Этот метод заключается в том, что на каждом деление производится на коэффициент модуль которого максимален. Такой элемент называется ведущим. Это необходимо для уменьшения ошибки вычислений. Затем изменением порядка следования строк и столбцов добиваются такого их расположения, чтобы ведущий элемент оказался первым в первой строке.

Метод LU–матриц заключается в том, что сначала матрицупредставляют в виде произведения

где

нижняя треугольная матрица (все элементы матрицы под главной диагональю равны 0), а

верхняя треугольная матрица (все элементы матрицы над главной диагональю равны 0), а диагональные элементы равны 1.

Исходная система уравнений записывается в виде:

,

затем вводится новый неизвестный вектор:

,

и решается система уравнений

.

Ее решение легко находится последовательным спуском, так как система имеет вид

l11x1 = b1, l21x1+ l22x2 = b2, × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × ln1x1+ ln2x2 + ln3x3 + × × × + lnnxn = bn.

После вычисления вектора  решается система

,

Ее решение легко находится последовательным подъемом, так как система имеет вид

x1+ u12x2 + u13x3 + × × × + u1nxn = z1, x2 + u23x3 + × × × + u2nxn = z2, × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × × ×  xn = zn.