Справочная информация

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

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

,

где

,

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

Точные методы. К ним относятся известные из классического курса линейной алгебры правило Крамера и метод, основанный на использовании обратной матрицы в виде x = A ^–1 b, а также метод Гауссаи его разновидности. Все они не имеют ограничений на свойства матрицы системы.

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

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

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

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

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

или

,

где

.

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

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

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

Полученная система с верхней треугольной матрицей может быть легко разрешена относительно неизвестных. Последнее уравнение системы определяет значение x_n, что позволяет определить x_{n –1} из предпоследнего уравнения как

.

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

Метод Гаусса может быть использован и для вычисления обратной матрицы A ^–1 системы линейных алгебраических уравнений. Этот алгоритм основан на свойстве матриц: AA ^–1 = E, где E – единичная матрица. Поэтому для вычисления столбцов обратной матрицы достаточно решить методом Гаусса серию задач вида , где b _i – столбцы единичной матрицы E, а x _i будут столбцами обратной матрицы.

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

, .

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

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

или или

,

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

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

,

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

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

или или ,

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

.

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

Дата добавления: 2015-07-08