Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
~ — 1 при нечетном числе к перестановок.
\
1 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
316
V..
Окончательно определитель матрицы А равен
ёеЫ=( — 1)*а1Л ?а$')2-ап,п1)-
Напомним формулу для обратной матрицы, представленной произведением двух матриц:
А = Ьи, А-^и-'Ь-1.
Матрицы Ь, и—треугольные, поэтому вычисление элементов Ь~х и и~1 не представляет труда (см. (8.2.7)). Если матрица А представлена в форме (8.2.11) с перестановками, то
А-1Р~1 = и-1Ь-19 А =
матрица Р~х есть матрица обратной перестановки, возвращающей строки на их прежние места. Можно заметить, что
Р^Х=Р\
где Р’—транспонированная к Р матрица.
В реальных вычислениях обратная матрица А ~1 находится решением п систем линейных уравнений методом исключения Гаусса:
Ах = е{, 1 </<л,
где е[— /-столбец единичной матрицы Е. Полученные векторы решений х19 х2, хп образуют п столбцов матрицы А~х, поскольку А А ~Х=Е.
8.2.3. Разложение на треугольные множители симметричной положительно определенной матрицы. Симметричные положительно определенные матрицы А очень часто связаны с изучением поведения механических систем в окрестности устойчивого положения равновесия. Матрица А трактуется тогда как матрица квадратичной формы в записи энергии IV:
п
1?=(Ах,х)— ? хьХ}, и=1
где х{ — обобщенные координаты.
Для положительно определенных матриц выполняются детер-минантные неравенства Сильвестра
а1,1 а1,2 >0, ..., а1,1 • •• а1,п >0,
а2Л а2,2 «*.,1 • •• я«,«
откуда в силу теоремы 8.4 сразу же следует существование ?С/-разложения.
Однако для рассматриваемого класса матриц, если не требовать, чтобы на диагонали Ь стояли единицы, справедливо следующее разложение:
А = Ы\ (8.2.12)
317
где Ь'—матрица, транспонированная к Ь. Действительно, определим элементы матрицы Г, сравнивая каждый элемент матрицы в левой и правой части (8.2.12). Имеем
а91,1 а 1, п
ап, 1 •••ап,п
'1,1. о
^1,п ••• '»,«
'1,1 ••• '1,(1
о
откуда получаем равенства для первого столбца
, ^1,1 =(а1л)1/2> ^,1=(а1л)1Ь,1’ Аналогично наводим соотношения
к=1
которые приводят к формулам
\ *=1
1/2
1-1
к} = уаи}~ Ъ ккЬлукь У+1
После того как выполнено разложение (8.2.12), решение системы линейных уравнений Ах = Ь получается решением двух систем с треугольными матрицами:
4 L,x=g.
В отличие от случая общих матриц изложенный метод разложения требует меньше памяти ЭВМ, так как хранится только треугольная часть матрицы А и не нужна перестановка строк.
8.2.4. Вычислительная погрешность метода Гаусса и выбор ведущего элемента исключения. Выше отмечалось, что метод исключения является точным методом. При этом предполагалось, что арифметические операции выполняются над точными числами. Если же метод исключения реализуется на ЭВМ, то появляется вычислительная погрешность, связанная с конечным числом разрядов ЭВМ для представления вещественных чисел, ошибками округления, реализацией на ЭВМ арифметических операций.
Вычислительная погрешность метода исключения может быть устранена в арифметике целых чисел. При этом если деление на элементы
«1.1, 4%..„а?"1' (8.2.13)
производится с остатком, то оно не выполняется, а запоминаются числитель и знаменатель. Компоненты вектора решения определяются в виде дробей. Метод Гаусса в арифметике целых чисел для общих матриц А требует определенного искусства масштабирования, чтобы избежать переполнения после арифметических операций.
318 \
Пусть метод исключения реализуется в арифметике вещественных чисел. Тогда естественно поставить вопрос об уменьшении вычислительной погрешности за счет модификации алгоритма исключения. Фактически идея такой модификации уже была использована выше. Вводились матрицы перестановок Р, чтобы избежать деления на нуль. Деление привело бы к бесконечно большой вычислительной погрешности.
Элементы (8.2.13), на которые производится деление в методе Гаусса, называются ведущими элементами исключения.
Уменьшение вычислительной погрешности производится путем перестановки строк и столбцов матрицы так, чтобы ведущий элемент на к-м шаге исключения был наибольшим по модулю из коэффициентов, участвующих в дальнейшем исключении:
\<*t,k1)\= max \<*t7l)l 1<к^п, (8.2.14)
k^i,j^n
где а$ = аи.
Выбор ведущих элементов по формуле (8.2.14) называют методом исключения с полным упорядочением.
Полное упорядочение требует большой дополнительной вычислительной работы, поэтому часто останавливаются на методе исключения с частичным упорядочением по строкам. Выбор ведущих элементов производится согласно формуле
I а?л1)\= max |а|\-1)|. (8.2.15)
k^i^n
Например, для системы уравнений
4*х + 5*2+12*3 = 1,
*1 — 3*2+ *з = 2,
10*!+ *2 — *з = 3
перед первым шагом исключения требуется согласно алгоритму с полным упорядочением поменять первый и третий столбцы системы уравнений:
12*з+ 4*i + 5*2 = 1,
*з+ *1“ 3*2 = 2,
— *3+10*!+ *2 = 3;
согласно алгоритму с частичным упорядочением поменять первую и третью строки системы уравнений:
10*!+ *2— *з = 3,
*1-3*2+ *з = 2,
4*1 + 5*2+12*3 = 1.
Затем выполняется 1-й шаг исключения.
Решая конкретную систему уравнений, трудно, вообще говоря, априори оценить по матрице А и вектору погрешность как
