Вычисление определителей

4. Вычисление определителей

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

1) перестановка двух строк или столбцов определителя не изменяет его абсолютной величины, но меняет знак на противоположный;

2) умножение всех элементов одной строки или одного столбца на любое число равносильно умножению определителя на это число;

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

Пусть задан определитель

Выберем главный элемент a₁₁ ¹ 0. Если a₁₁ = 0, то выполним перестановку двух строк или столбцов этого определителя, чтобы получить a₁₁ ¹ 0.

Вынесем главный элемент a₁₁ из первой строки за знак определителя

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

Разложим полученный определитель по элементам первого столбца, что даст понижение его порядка определителя на единицу

Повторим указанную процедуру (n - 1) раз и окончательно получим

Если при вычислении определителя производилась перестановка строк или столбцов (для выбора главного элемента), то

где s – количество выполненных перестановок.

Таким образом, вычисление определителя detA некоторой матрицы A сводится к выполнению прямого хода метода Гаусса. Абсолютная величина этого определителя равна произведению главных элементов , k = , используемых на каждом шаге прямого хода. Знак определителя зависит от числа перестановок строк и столбцов, выполненных при выборе главных элементов.

Если такие перестановки не производились, то величина определителя также может быть вычислена как произведение диагональных элементов матрицы L, формируемой в процессе LU-разложения исходной матрицы А

5. Вычисление обратных матриц

Обратную матрицу А^-1 имеет любая квадратная матрица А, для которой detA ¹ 0. Пусть дана матрица А = [a_ij]_n´n. Для вычисления элементов обратной матрицы используется соотношение

A A^-1 = A^-1 A= E,

где E – единичная матрица.

Обозначим обратную матрицу A^-1 = X = [x_ij]_n´n. Тогда получим

A X= E.

Будем рассматривать столбцы матрицы X как векторы

  …

Аналогично выделим столбцы единичной матрицы E

  …;

Тогда система линейных уравнений вида

A =

позволяет определить элементы k-го столбца обратной матрицы X = A^-1. Всего потребуется решить n таких систем с одинаковой матрицей A, но разными правыми частями для k = . Это можно сделать с использованием LU-разложения матрицы коэффициентов A, либо непосредственно с помощью метода Гаусса.

6. Итерационные методы

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

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

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

Метод последовательных приближений Якоби. Пусть дана система линейных уравнений (1), для которой диагональные элементы

.

Тогда переменную x₁ можно выразить через первое уравнение,  - через второе уравнение и т. д.

 (10)

где  и

Система (10) называется системой линейных уравнений, приведенной к нормальному виду. Матричная форма записи такой системы представляется как

(11)

где

При решении системы (11) за нулевое приближение корней может быть принят столбец свободных членов, т.е. . Любое k-е приближение ( вычисляется по формуле

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

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

(12)

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

Итерационный метод Зейделя. Метод Зейделя представляет собой модификацию метода последовательных приближений. При определении значения переменной  на некоторой (k+1)-й итерации используются уже вычисленные (k+1)-е приближения неизвестных , , ..., , а также значения  полученные на предыдущей k-й итерации.

Пусть дана линейная система уравнений (10). Выбранные начальные приближения корней  подставляются в первое уравнение

Для определения  полученное значение  сразу же подставляется во второе уравнение системы

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

В общем случае получение значений неизвестных  по методу Зейделя на некоторой k-ой итерации производится по следующей формуле

При использовании обозначений исходной системы уравнений (1) итерационная формула обычно записывается как

Условие завершения итерационного процесса по методу Зейделя также формулируется в виде соотношения (12). При этом, как правило, процесс сходится к единственному решению быстрее, чем при использовании метода последовательных приближений Якоби.

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

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

Таким образом, для сходимости указанных итерационных процессов достаточно, чтобы значения элементов a_ij матрицы a при i ¹ j были небольшими по абсолютной величине. Можно показать, что для линейной системы вида (2) итерационные процессы последовательных приближений и Зейделя сходятся к точному решению X^*, если для всех уравнений системы модули диагональных коэффициентов удовлетворяют условиям

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

Линейную систему (2) можно заменить такой эквивалентной системой нормального вида (11), которая удовлетворяет условиям сходимости итерационных процессов. Для этого используются следующие элементарные преобразования:

1) перестановка двух строк или столбцов;

2) умножение всех элементов какой-либо строки на одно и то же число, отличное от нуля;

3) сложение элементов какой-либо строки с соответствующими элементами другой строки, умноженными на одно и то же число.

В качестве примера рассмотрим метод [1] приведения линейной системы к виду, удобному для итераций. Система уравнений AX = B умножается на матрицу D = A^-1 - D, где D = [d_ij] - матрица с малыми по модулю элементами. В результате получается эквивалентная система уравнений

(A^-1 - D) A X = D B

или в нормальном виде

X = b + a X,

где a = D A и b = D B. Если значения êd_ij ê достаточно малы, то очевидно, что полученная система вида (9) удовлетворяет условиям сходимости, поскольку умножение на матрицу D эквивалентно совокупности элементарных преобразований над уравнениями системы.

Заключение

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

Список литературы

1.  Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.

2.  Васильев, Ф.П. Численные методы решения экстремальных задач. [Текст] Ф.П. Васильев – М.: Наука, 2002. C. 415.

3.  Симанков, В.С. Основы функционального программирования [Текст] В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.

4.  Калиткин, Н.Н. Численные методы. [Электронный ресурс] Н.Н. Калиткин. – М.: Питер, 2001. С. 504.

5.  Кнут, Д.Э. Искусство программирования. Основные алгоритмы [Текст] Д.Э. Кнут. – М.: Вильямс, 2007. Т.1.– 712 с.