Вычислительная математика 
 

  назад | оглавление | вперед

 

Глава 4. Решение систем линейных уравнений

1. Прямые и итерационные методы

Пусть имеется система линейных алгебраических уравнений с n неизвестными:

.               (1)

Если обозначить за матрицу А таблицу коэффициентов при неизвестных, за В – вектор-столбец правых частей, за Х - вектор-столбец неизвестных, то систему (1) можно записать в матричном виде:

,               (2)

где

.

Решение системы (2) всегда существует и единственно, если , т.е. матрица Aневырожденная.

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

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

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

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

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


2. Норма матрицы и вектора

Условия сходимости итерационных методов связаны с понятиями норм матрицы и собственными числами матрицы.

Пусть А – матрица размером m ´ n (матрица содержит m строк и n столбцов. Нормой матрицы называется неотрицательное число ||A||, обладающее следующими свойствами:

  1. ||A|| ³ 0, причем ||A|| = 0 тогда и только тогда, когда все элементы матрицы А равны нулю;
  2. ||a A|| = |a |× ||A||, где a - произвольное число;
  3. ||A + В|| ||A|| + ||В||;
  4. ||A × В|| ||A|| × ||В||;

Нормы матрицы можно вводить различными способами. Рассмотрим примеры трех легко вычисляемых норм:

  1. Первая норма (1-норма)
  2. .

  3. Вторая норма (Евклидова норма или 2-норма):
  4. .

  5. Бесконечная норма(¥ -норма) :
  6. .

Самостоятельно проверьте, что введенные нормы удовлетворяют всем свойствам из определения нормы.

Пример 1:Найти первую, вторую и бесконечную нормы для матрицы

,

,

.

Если рассматривать вектор X = (x1 , x1, ... xm) T как матрицу размера m ´ 1, то определенные выше нормы будут имеют следующий вид:

  1. Первая норма (1-норма)
  2. .

  3. Вторая норма (Евклидова норма или 2-норма):
  4. .

  5. Бесконечная норма(¥ -норма) :
  6. .

Пример 2:Найти первую, вторую и бесконечную нормы для вектора

,

,

.


3. Собственные значения матрицы

Собственными значениями квадратной матрицы А называются корни ее характеристического уравнения:

.              (3)

Совокупность всех собственных значений называется спектром матрицы А.

Пример Найти собственные значения матрицы:

Составим характеристическое уравнение (2):

Решая квадратное уравнение, находим . Спектр матрицы А состоит из чисел: 7, –2.


4. Метод простой итерации

Рассмотрим систему линейных уравнений (1) с невырожденной матрицей А.Предположим, что все диагональные элементы матрицы А не равны нулю. Поделим каждую строку системы (1) на соответствующий диагональный элемент матрицы Аaii. Получим систему

.              (4)

Систему (4) можно записать в матричном виде:

,               (5)

где

.

Представим матрицу в виде , где

, .

Тогда систему (5) можно записать в виде: . Тогда

              (6)

Рассмотрим итерационный процесс:

              (7)

или в виде

Теорема 1: Если итерационный процесс (7) сходится (т.е. существует вектор: ), то предельный вектор X* этого итерационного процесса будет решением системы (6) и, следовательно, исходной системы (1).

Доказательство:

Перейдем в (7) к пределу при к® ¥ получим:

Þ X* = BС X*.

Для того, чтобы запустить итерационный процесс необходимо задать значения первоначального приближения X(0)тогда все остальные значения X(к) вычисляются по формуле (7) . В качестве X(0) обычно берут .

Решение системы получается (5) получается в результате бесконечного процесса, и всякий вектор X(k) является приближенным решением.

Метод последовательных приближений, определяемых формулой (7), носит название метода простой итерации.

Сформулируем условия, при которых итерационный процесс (7) сходится.

Теорема 2 Для сходимости итерационного процесса метода простой итерации при произвольном начальном приближении X(0) необходимо и достаточно, чтобы все собственные значения матрицы С системы (6) были по модулю меньше единицы.

Теорема 3 (достаточное условие сходимости): Если в системе (6) ||C|| < 1 (любая норма 1,2,…, ¥), то процесс (7) сходится к единственному решению при любом начальном приближении X(0)

Условие ||C|| < 1 – равносильно тому, что для < матрицы A системы (1) выполняется условие диагонального преобладания по строкам, т.е. элемент, стоящий на диагонали, больше суммы модулей всех остальных элементов своей строки. Это является достаточным условием сходимости метода простой итерации.

Погрешность k-ой итерации можно оценить по формуле:

              (8)

Если , то формула (8) принимает вид: . Тогда, если , то и можно положить, что . Т.е. итерации можно прекратить, когда разность между двумя последовательными приближениями станет меньше заданной точности.

Оценка погрешности k-ой итерации, выраженная через разность начальных итераций задается формулой:

              (9)

В частности, если в качестве начального приближения взять X{0}= , то . Тогда . Следовательно,

.               (10)

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

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

.

Разделим первую строку на 5, вторую – на 4, третью – на 5. Преобразованная система:

, тогда , .

Найдем ¥-нормы матрицы С и вектора .

Т.к. , то по теореме 3 итерационный процесс сходится. Количество шагов метода, необходимых для достижения точности 0.001 найдем, используя формулу (10).

Þ Необходимо выполнить 41 шаг. Заметим, что эта оценка сильно завышена и на практике следует выполнить гораздо меньшее количество итераций.

Найдем X(1), выполнив один шаг по методу простой итерации при начальном приближении X(0) = .

Аналогично выполним еще два шага по методу простой итерации:

Оценим погрешность, с которой найдено значение X(3). Для этого найдем Þ

, Тогда по формуле (8) получаем:

. .


5. Метод Зейделя

Метод Зейделя представляет модификацию метода простой итерации. В этом методе при вычислении (k +1)-го приближения переменной xi учитываются уже вычисленные на этом шаге приближения неизвестных x1, x2,..., xi-1.

Пусть система (1) приведена к виду (6). Выберем начальное приближение X(0). X(k+1) будем вычислять по формулам:

              (11)

Метод Зейделя работает несколько быстрее метода простой итерации.

Если выполнено условие , то погрешность k-ой итерации метода Зейделя можно оценить по формуле:

              (12)

или

,               (13)

где

Можно так же использовать оценки метода простой итерации. Указанные для метода простой итерации достаточные условия сходимости обеспечивают и сходимость метода Зейделя.

Пример Выполнить три итерации по методу Зейделя для системы из предыдущего примера.

Выпишем формулы (11).

Так же как и в методе простой итерации возьмем за начальное приближение X(0) = .

Выполним еще два шага по методу Зейделя:

Оценим погрешность, с которой найдено значение X(3). Для этого найдем Þ

Тогда по формуле (12) получаем:

. .



назад | оглавление | вперёд