Математическая энциклопедия - окаймления метод

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

к решению задачи с матрицей , рассматриваемой как результат окаймления

Вычислительная схема О. м. для обращения матриц такова. Пусть невырожденная матрица. Для обращения матрицы используется представление

где ,

Тогда

Последовательное обращение матриц A1, А 2, . . ., А п по этой схеме дает матрицу А ^-1.

Описанная схема О. м. пригодна лишь для матриц с отличными от нуля главными минорами. В общем случае следует принять схему О. м. с выбором главного элемента. В этой схеме в качестве окаймляющих строки и столбца берутся те, для к-рых будет максимальным по модулю. Тогда вычисленная матрица будет отличаться от А ^-1 лишь перестановкой строк и столбцов [1].

По быстродействию О. м. не уступает самым быстродействующим из прямых методов обращения матрицы.

О. м. позволяет аффективно обращать треугольные матрицы. Если правая треугольная матрица, то в (1)

Объем вычислений в этом случае уменьшается в 6 раз. Особенно эффективен О. м. при обращении эрмитовых положительно определенных матриц. Для этих матриц не нужно применять схему выбора главного элемента. Кроме того, они могут быть заданы лишь половиной своих элементов. Вычислительная схема в этом случае упрощается:

Вычислительная схема О. м. для решения системы состоит в следующем. Пусть , k=1,2. . . ., п; b^(n,n+1)=-b. Если невырожденная матрица и решение системы

, то решение системы находится из представления

и из (2) следующим образом:

Таким образом, по решениям и систем с одной и той же матрицей и разными правыми частями легко получить решение системы с окаймленной матрицей . Решение исходной системы: x^(n,n+1). Оно может быть получено рекуррентным применением соотношения (4). Это сводится к последовательному вычислению совокупности векторов , k=1,2,. . ., п, р>k, то есть

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

О. м. позволяет решать системы повышенного порядка за счет эффективного использования памяти ЭВМ. Это обусловлено тем, что для вычисления векторов , p>k, требуется запоминание только векторов , p>(k-1), и коэффициентов k-го уравнения системы, т. е. массива чисел длины f(k).= k(n-k+1).(n+1). Поэтому для решения системы n-го порядка достаточно иметь рабочее поле длины (n+1) (n+5)/4 (n/2)². При этом элементы матрицы и правой части можно вводить в намять ЭВМ не сразу, а последовательно по строкам.

О. м. целесообразно использовать при решении системы, для к-poй уже ранее решена усеченная система. Тогда соотношение (4) сразу дает искомое решение.

Описанная схема О. м. может быть использована для вычисления определителя. Из представления (1) следует, что

Рекуррентное применение этого соотношения дает А.

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

Лит.:[1] Воеводин В. В., Численные методы алгебры, М., 1966; [2] Фаддеев Д. К., Ф а д д е е в а В. Н., Вычислительные методы линейной алгебры, 2 изд., М.-Л., 1963.

Г. Д. Ким.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985