Вычислительная математика
|
назад | оглавление | вперед |
Глава 4. Решение систем линейных уравнений
1. Прямые и итерационные методы
Пусть имеется система линейных алгебраических уравнений с n неизвестными:
.               (1)
Если обозначить за матрицу А таблицу коэффициентов при неизвестных, за В – вектор-столбец правых частей, за Х - вектор-столбец неизвестных, то систему (1) можно записать в матричном виде:
,               (2)
где
.
Решение системы (2) всегда существует и единственно, если , т.е. матрица A – невырожденная.
Все методы решения систем линейных уравнений можно разбить на две группы:
Прямые методы используют формулы для вычисления неизвестных. Они дают решение системы за конечное число арифметических операций. Эти методы сравнительно просты и наиболее универсальны, т.е. пригодны для решения широкого класса линейных систем. Наиболее известным из прямых методов решения систем линейных уравнений является метод Гаусса.
Вместе с тем прямые методы имеют и ряд недостатков. При решении таких задач на компьютере они требуют хранения в оперативной памяти сразу всей матрицы, поэтому при больших значениях n расходуется много места в памяти. Так же прямые методы не учитывают структуру матрицы – при большом числе нулевых элементов эти элементы все равно хранятся в памяти и над ними выполняются арифметические операции. Существенным недостатком прямых методов является накапливание погрешности в процессе решения, поскольку все вычисления на компьютере производятся с ограниченным числом знаков, определяемых разрядностью компьютера, и вычисления на любом этапе используют результаты предыдущих операций. Особенно это опасно для больших систем (n > 200) и для систем с близким к нулю определителем (плохо обусловленных систем).
Итерационные методы – это методы последовательных приближений решения. В них необходимо задать начальное приближение решения. После этого с помощью некоторого алгоритма проводится один цикл вычислений, называемый итерацией. В результате итерации находят новое приближение решения. Итерации проводятся до получения решения с заданной точностью. Алгоритмы решения линейных систем с использованием итерационных методов более сложные по сравнению с прямыми методами. При этом объем вычислений заранее определить сложно.
Тем не менее, в ряде случаев итерационные методы предпочтительнее прямых. Они требуют хранения в памяти не всей матрицы системы. Погрешность в процессе вычислений не накапливается, т.к. точность вычислений в каждой итерации определяется лишь результатами предыдущей итерации и практически не зависит от ранее выполненных вычислений.
Условия сходимости итерационных методов связаны с понятиями норм матрицы и собственными числами матрицы.
Пусть А – матрица размером m ´ n (матрица содержит m строк и n столбцов. Нормой матрицы называется неотрицательное число ||A||, обладающее следующими свойствами:
Нормы матрицы можно вводить различными способами. Рассмотрим примеры трех легко вычисляемых норм:
.
.
.
Самостоятельно проверьте, что введенные нормы удовлетворяют всем свойствам из определения нормы.
Пример 1:Найти первую, вторую и бесконечную
нормы для матрицы
,
,
.
Если рассматривать вектор X = (x1 , x1, ... xm) T как матрицу размера m ´ 1, то определенные выше нормы будут имеют следующий вид:
.
.
.
Пример 2:Найти первую, вторую и бесконечную
нормы для вектора
,
,
.
3. Собственные значения матрицы
Собственными значениями квадратной матрицы А называются корни ее характеристического уравнения:
.              (3)
Совокупность всех собственных значений называется спектром матрицы А.
Пример Найти собственные значения матрицы:
Составим характеристическое уравнение (2):
Решая квадратное уравнение, находим . Спектр матрицы А состоит из чисел: 7, –2.
Рассмотрим систему линейных уравнений (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) получаем:
.
.
Метод Зейделя представляет модификацию метода простой итерации. В этом методе при вычислении (k +1)-го приближения переменной xi учитываются уже вычисленные на этом шаге приближения неизвестных x1, x2,..., xi-1.
Пусть система (1) приведена к виду (6). Выберем начальное приближение X(0). X(k+1) будем вычислять по формулам:
              (11)
Метод Зейделя работает несколько быстрее метода простой итерации.
Если выполнено условие
, то погрешность
k-ой итерации метода Зейделя можно оценить по формуле:
              (12)
или
,               (13)
где
Можно так же использовать оценки метода простой итерации. Указанные для метода простой итерации достаточные условия сходимости обеспечивают и сходимость метода Зейделя.
Пример Выполнить три итерации по методу Зейделя для системы из предыдущего примера.
Выпишем формулы (11).
Так же как и в методе простой итерации возьмем за начальное
приближение X(0) =
.
Выполним еще два шага по методу Зейделя:
Оценим погрешность, с которой найдено значение
X(3). Для этого найдем
Þ
Тогда по формуле (12) получаем:
.
.