Справочная информация. Численные методы решения систем линейных алгебраических уравнений

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

записываемых в матричной форме в виде

,

где

,

делятся на точные и итерационные. Они используются для систем, у которых количество неизвестных равно количеству уравнений и матрица A – не вырождена (её определитель не равен нулю). Точными методами условно называют методы, которые дают решение задачи посредством конечного числа арифметических операций. Итерационные методы позволяют получить решение системы как предел бесконечной последовательности его приближений.

Метод Гаусса (K.F.Gauβ, 1849)

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

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

Один из простейших способов исключения состоит в следующем. Первое уравнение системы

которое на этом шаге считается ведущим, нормируется – делится на значение диагонального элемента a ₁₁

или

,

где

.

Если в исходной системе a ₁₁ = 0, то в качестве первого уравнения следует взять любое другое с ненулевым первым коэффициентом, поменяв их местами. Полученное уравнение умножается на первый коэффициент второго уравнения a ₂₁ и вычитается из него. В результате во втором уравнении пропадает слагаемое a ₂₁ x ₁, содержащее первое неизвестное x ₁. Такие же операции проводятся со всеми последующими уравнениями. В результате система уравнений принимает вид

Далее процесс повторяется. За ведущее берется второе уравнение и исключается неизвестное x ₂ из всех уравнений, начиная с третьего

Таким образом, за n шагов система уравнений последовательно сводится к треугольному виду, при этом для последнего уравнения операцию нормирования можно не выполнять

Полученная система с верхней треугольной матрицей легко разрешима относительно неизвестных. Последнее уравнение системы даёт значение x_n

,

что позволяет определить x_{n –1} из предпоследнего уравнения как

.

Далее, подстановкой найденных неизвестных в вышестоящие уравнения, удается определить все компоненты решения x_{n –2},..., x ₂, x ₁.

Метод Гаусса даёт точное решение, если все исходные данные точны и все вычисления производятся точно. На практике, при выполнении вычислений, неизбежно проводятся округления. Ошибка округлений вносит погрешность в решение метода Гаусса. Таким образом, при операциях с округленными десятичными числами метод Гаусса даёт не точное решение x _т системы линейных алгебраических уравнений, а некоторое приближённое решение , где

, .

Степень отличия приближённого решения от точного определяется длиной разрядной сетки ЭВМ: чем больше разрядов в ней учитывается, тем это отличие меньше.

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

или или

,

где двойные модульные скобки обозначают норму вектора.

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

,

а затем посредством повторного решения системы уравнений

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

или или ,

так и его относительная погрешность

.

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