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

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

или в матричной форме АХ = В.

Без преувеличения можно сказать, что решение систем линейных уравнений относится к числу самых распространенных и очень важных задач математики. Для систем типа (3.9), имеющих небольшую размерность, созданы достаточно эффективные прямые методы решения, некоторые из которых изучаются в курсе высшей математики, например метод Гаусса. Однако при их реализации на ЭВМ, как и всегда, актуальны трудности, связанные с необходимостью округлений результатов многочисленных арифметических действий. При этом корректная оценка погрешности весьма проблематична. В связи с этим полезно уточнение полученных результатов, которое может быть осуществлено численным методом. Тогда роль исходного приближения играет результат решения системы, полученный регулярным методом.

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

Метод простой итерации. Если исключить из каждого уравнения системы (3.9) по одной переменной (для этого соответствующий коэффициент должен быть отличен от нуля), то система примет так называемый приведенный вид

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

где

Пусть известно некоторое начальное приближенное значение Х (0) искомого вектора неизвестного (проще всего положить Х (0) = = В). Подставив его в правую часть системы (3.11), можно получить новое приближение Х (1):

Теперь подставим в правую часть системы (3.11) приближение Х (1) и получим следующее приближение Х (2):

Подобный процесс может быть продолжен. В общем случае (г + 1)-е приближение вычисляется по формуле.

Это рекуррентное соотношение и лежит в основе простого итерационного метода. Решение уравнения (3.12) дает последовательность приближенных решений Х⁽⁰⁾, Х⁽¹), Х⁽²⁾,…, Х^(к). Покажем, что если существует конечный предел.

то он является решением уравнения (3.10), а следовательно, и уравнения (3.9).

Действительно, перейдя в формуле (3.12) к пределу, имеем.

Принимая во внимание равенство (3.13), получаем равенство (3.11), т. е. предельный вектор X является решением нашей системы уравнений.

Достаточные условия сходимости итерационного процесса (3.12) дает следующая теорема.

Теорема 3.1. Если в системе (3.11) выполнено условие

j = 1, …, п, или условие то процесс итерации

(3.12) сходится к единственному решению системы (3.10).

Пример 3.4.

С точность до 10^-2 найти решение системы.

Решение. Приведенная по отношению к заданной система имеет вид.

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

В качестве исходного приближения положим.

Подставив его в формулу (3.11), получим первое приближение.

Поскольку |ХП) — Х<�°)| < 0,01 не выполняется, то продолжим итерационный процесс. Последовательно получим.

Для X⁽⁴> погрешность не превысит величины 0,075, что отвечает требуемой точности. Для сравнения приведем точное решение заданной системы: = 1,х₂ = —1, х₃ = 1.