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

Рассмотрим систему, состоящую из n уравнений с n неизвестными.

a₁₁ x ₁ + a₁₂ x ₂ + a₁₃ x ₃ +... + a_1n x _n = b ₁

a₂₁ x ₁ + a ₂₂ x ₂ + a₂₃ x ₃ +... + a_2n x _n = b ₂ (4.1)

........................

a_n1 x ₁ + a_n2 x ₂ + a_n3 x ₃ +... + a_nn x _n = b _n

где x _i – неизвестные, подлежащие определению, a_ij – коэффициенты при неизвестных; b _i - числа, называемые свободными членами (правыми частями) системы уравнений.

Форма записи системы (4.1) - скалярная

Совокупность чисел x ₁ = λ₁, x ₂ = λ₂,..., x _n = λ _n, удовлетворяющих (4.1) называется решением СЛАУ.

Матричная форма записи системы (4.1) имеет вид

А = ; x = ; b = ; (4.2)

СЛАУ называется совместной, если она имеет хотя бы одно решение; в противном случае она называется несовместной.

СЛАУ называется определенной, если это решение - единственное.

Если СЛАУ не имеет ни одного решения, то такая система является неопределенной.

Задача теории систем линейных уравнений состоит в разработке методов, позволяющих узнать:

- совместна ли данная СЛАУ;

- если совместна, то установить число решений;

- указать способ отыскания этих решений.

Некоторые обозначения:

А^Т – матрица, транспонированная к матрице А, т.е. a _ij = a _ji.

А^-1 – матрица, обратная к матрице А, т.е. А^-1 · А = I,

где I - единичная матрица.

При решении СЛАУ возникают проблемы, связанные с вопросами:

1) разрешима ли данная СЛАУ;

2) каким методом ее решать;

3) какова чувствительность решения к ошибкам округления исходных данных.

Рассмотрим эти вопросы подробнее.

1) Теорема (из курса высшей алгебры)

Система n уравнений с n неизвестными, определитель которой отличен от 0, имеет решение, причем единственное.

(Это условие необходимое, но не достаточное.)

2) К выбору методов решения необходимо подходить рационально: например, метод Крамера требует около n²n! операций умножения и деления.

Т.е. для системы с 20 уравнениями и 20 неизвестными это число составляет 10²¹. Для современных ЭВМ, выполняющих миллионы операций в сек., для решения такой системы потребуется около 10¹⁵ сек. или 3∙10⁶ лет.

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