3.3. Вычисление определителей
Решение системы (3.4) существует только в том случаем, если определитель матрицы A отличен от нуля, поэтому решение любой системы линейных уравнений следует предварять вычислением ее определителя.
Для вычисления определителя используют известное свойство треугольных матриц: определитель треугольной матрицы равен произведению ее диагональных элементов.
Пусть задана квадратная матрица X n-го порядка:
.
(3.6)
Представим матрицу X в виде:
,
(3.7)
где
,
.
(3.8)
Известно, что определитель матрицы равен произведению определителей:
,
(3.9)
но
,
поэтому
.
(3.10)
Формулы
для вычисления элементов матриц
и
получаются перемножением матриц
,
и приравниванием к соответствующим
элементам матрицы X:
;
,
при
(3.11)
;
,
при
.
(3.12)
В пакете MathCAD вычислительный алгоритм, задаваемый формулами (3.11), (3.12), оказывается возможным реализовать в виде одной функции, представленной на рис. 3.4.
|
Рис. 3.4. Функция, возвращающая значение определителя матрицы, вычисленного в соответствии с (3.11), (3.12). Аргумент функции: А имя квадратной матрицы |
Для проверки правильности работы данной функции полезно сравнить результат, возвращенный данной функцией и результат, возвращаемый функцией встроенной в пакет MathCAD:
3.4. Решение систем линейных уравнений методом простой итерации
Запишем исходную систему (3.4) в следующем виде:
(3.13)
или сокращенно
(3.14)
где
.
Правая часть (3.14) определяет отображение F
,
(3.15)
преобразующее
точку
n-мерного
векторного
пространства в точку
того же пространства. Используя систему
(3.4) и выбрав начальную точку
,
можно построить итерационную
последовательность точек n-мерного
пространства
(аналогично методу простой итерации
для скалярного уравнения
):
(3.16)
Оказывается, что при определенных условиях последовательность (3.16) сходится и ее предел является решением системы (3.13). Предваряя обсуждение данных условий, напомним необходимые сведения из математического анализа.
Определение
3.4. Функцию
,
определяющую расстояние между точками
x
и y
множества X,
называют метрикой, если выполнены
следующие условия:
1) 0,
2) = 0 тогда и только тогда, когда x = y,
3)
=
,
4)
.
Определение 3.5. Множество с введенной в нем метрикой становится метрическим пространством.
Определение
3.6.
Последовательность точек метрического
пространства называется фундаментальной,
если для любого
существует такое число
,
что для всех m,n > N
выполняется неравенство
.
Определение 3.7. Пространство называется полным, если в нем любая фундаментальная последовательность сходится.
Пусть F отображение, действующее в метрическом пространстве Е с метрикой , x и y точки пространства Е, а Fx, Fy образы этих точек.
Определение 3.8. Отображение F пространства E в себя называется сжимающим отображением, если существует такое число , 0<<1, что для любых двух точек x, y E выполняется неравенство
.
(3.17)
Определение 3.9. Точка x называется неподвижной точкой отображения F, если Fx=x.
Аналогично одномерному случаю можно доказать теорему о достаточном условии сходимости итерационного процесса в n-мерном пространстве. (Доказательство теоремы приводится практически во всех учебниках, посвященных численным методам (например, [1]))
Теорема.
3.1. Если
F
сжимающее отображение, определенное в
полном метрическом пространстве, то
существует единственная неподвижная
точка x, такая, что x=Fx. При этом итерационная
последовательность, построенная для
отображения F
с любым начальным членом
,
сходится к x.
В ходе доказательства данной теоремы показывается, что
.
(3.18)
Из (3.18), приняв k-ое приближение за нулевое, получаем полезное для приложений неравенство:
.
(3.19)
Рассмотрим условия, при которых отображение (3.15) будет сжимающим. Как следует из определения (3.17), решение данного вопроса зависит от способа метризации данного пространства. Обычно при решении систем линейных уравнений используют одну из следующих метрик:
,
(3.20)
,
(3.21)
.
(3.22)
Для того чтобы отображение F, заданное в метрическом пространстве уравнениями (3.15), было сжимающим, достаточно выполнения одного из следующих условий:
1)
в пространстве с метрикой
:
,
(3.23)
2)
в пространстве с метрикой
:
,
(3.24)
3)
в пространстве с метрикой
:
.
(3.25)
Для установления момента прекращения итераций при достижении заданной точности может быть использована, например, формула, следующая из (3.19):
.
(3.26)
Алгоритм решения системы методом итераций реализуется следующей последовательностью действий:
1) Привести систему (3.4) к виду с преобладающими диагональными коэффициентами.
2) Разделить каждое уравнение на соответствующий диагональный коэффициент.
3) Проверить выполнение условий (3.23)(3.25).
4) Выбрать метрику, для которой выполняется условие сходимости итерационного процесса.
5) Реализовать итерационный процесс (обычно за начальное приближение берется столбец свободных членов)
Пример 3.1. Преобразование системы к виду пригодному для итерационного процесса
Возьмем первым уравнением второе, третьим первое, а вторым сумму первого и третьего уравнений:
Разделим каждое уравнение на диагональный коэффициент и выразим из каждого уравнения диагональное неизвестное
На этом приведение уравнения к виду, пригодному для использования итерационного процесса, завершается.
После приведения системы к виду, пригодному для использования итерационного процесса, для дальнейших вычислений целесообразно использовать пакет MathCAD. Созданный нами документ для решения системы линейных уравнений методом Гаусса состоит из следующих блоков.
1. Задание функций, возвращающих значение расстояния между точками в соответствующем метрическом пространстве (рис. 3.5)
Рис. 3.5. Функции, возвращающие расстояние между точками в соответствующем метрическом пространстве
2. Задание функции, возвращающей значение коэффициентов (рис. 3.6)
3. Задание матрицы системы, приведенной к виду, пригодному для метода простой итерации
|
Рис. 3.6. Функция, возвращающая значения коэффициентов для каждого из трех метрических пространств. Аргументы функции: A имя матрицы системы, i (i =1,2,3) имя соответствующей метрики |
|
Рис. 3.7. Функция, реализующая вычисления в соответствии с итерационным алгоритмом. Аргументы функции: A имя матрицы системы, b имя вектор-столбца свободных членов, имя метрики, соответствующее значение коэффициента, точность решения |
4. Вычисление значений коэффициентов для каждого метрического пространства
5. Задание функции, реализующей вычисления в соответствии с итерационным алгоритмом (рис. 3.7)
6. Нахождение решения системы линейных уравнений
