A.3. Элементарные кручения и выметания

Многие преобразования при вычислениях, связанных с матрицами, можно рассматривать как последовательность операций, называемых кручениями. Полезно будет изучить операцию кручения детально и дать перечень некоторых ее применений. В дальнейшем всегда будем предполагать, что вначале мы имеем некоторую заданную матрицу В, которая постепенно видоизменяется с помощью последовательности кручений. Если только не оговаривалось противоположное, всегда, когда мы будем говорить о матрице В или о любых ее элементах, мы будем подразумевать текущие, а не исходные значения. Определение. Допустим, что элемент для некоторой пары индексов Тогда выполнение элементарного кручения Гаусса — Жордана, или просто кручения на элементе означает замену элементов матрицы В в соответствии следующей схемой.

1. Заменить элемент на для

2. Заменить элемент на для всех

3. Заменить элемент на для всех

4. Заменить элемент на

Элемент (до кручения) называют опорным (разрешающим, главным). Кручение на элементе т. е. с опорным элементом на главной диагонали, называют выметанием [20] по строке Кручения называются независимыми, если они отличаются как строками, так и столбцами, кручения независимы, если Легко проверяются следующие свойства:

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

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

3) из свойств 1 и 2 мы выводим, что последовательность кручений на элементах и эквивалентна единственному кручению с опорным элементом если элементы и независимы.

Следующие примеры применений послужат мотивировкой к определению кручения.

(а) Перестановка ролей переменных. Допустим, что матрица В размерами -мерный вектор х и -мерный вектор у удовлетворяют уравнению

Элементы векторов х и у можно рассматривать как соответственно независимые и зависимые переменные. Допустим, что мы хотим поменять ролями, скажем, т. е. мы хотим выразить переменные как функции отуу, Первая строка уравнения имеет вид

Если то это эквивалентно уравнению

Решая его относительно и подставляя результат в строку уравнения после приведения подобных членов мы находим:

Рассмотрим следующую таблицу, схематически представляющую уравнение

Тогда, после обмена местами на входах в таблицу, мы можем представить уравнения в следующем виде:

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

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

Соответствующая таблица имеет вид:

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

Предположим, что возможны перестановки по очереди: с Результат будет тот же самый, что и при перестановке вектора как целого с вектором Таким образом, в соответствии с равенствами выметание (если оно возможно) по строкам таблицы приводит к

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

(в) Обращение матрицы. Когда подматрица совпадает с полной матрицей В, то выметание по всем строкам преобразует матрицу поскольку уравнение переходит в уравнение Но если мы натолкнемся на нулевые диагональные элементы, то эти преобразования нельзя будет осуществить. Например, матрицу

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

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

2) среди всех элементов, для которых строки имеют заголовки у и а столбцы — найти элемент, скажем с наибольшей абсолютной величиной; если таких элементов уже не существует, то перейти к пункту 5. В противном случае:

3) если то матрица В вырождена, и процесс прерывается, В противном случае:

4) выполнить кручение на элементе и поменять местами заголовки Вернуться к пункту 2;

5) переставить строки так, чтобы их заголовки стояли в естественном порядке

6) переставить столбцы так, чтобы их заголовки стояли в естественном порядке: Наша таблица содержит теперь матрицу .

(г) Системы линейных уравнений. Мы хотим решить относительно систему уравнений

где матрица А имеет порядок Определим В как матрицу размерами и применим к В алгоритм предыдущего примера с тем лишь отличием, что в последнем столбце никакие опорные элементы недопустимы. Если матрица А невырождена, то в конечном счете получается матрица т. е. решение х находится в последнем столбце. Если интерес представляет только это решение х, то пункт 6 можно опустить. Точно так же в пункте 5 требуется упорядочить только элементы последнего столбца. Этот метод известен как метод исключений Гаусса — Жордана. Обычный метод исключений по Гауссу является более быстрым, но метод исключений Гаусса-Жордана оказывается более удобным и более экономичным по объему памяти, когда получение обратной матрицы тоже является желательным.

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

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

Тогда согласно табл. мы должны иметь:

Далее, если мы будем исключать непосредственно уравнений то обнаружим, что верны соотношения

которые ввиду можно записать в виде

Из этого мы выводим следующее:

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

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

Ранг матрицы и линейная независимость векторов. Пусть это множество -мерных векторов и пусть А — это матрица размерами для которой строкой служит вектор Мы хотим определить ранг матрицы А или, что то же самое, число линейно независимых векторов а. Представим матрицу А в табличном виде и начнем применять вышеописанный алгоритм раздела Число элементарных кручений, выполненных прежде чем процесс вынужденно остановится, равно рангу матрицы. Обращаясь к соотношениям мы видим, что условие можно переписать как Но точно так же Объединяя все вместе, мы находим:

Таким образом, матрицы содержат коэффициенты линейной зависимости между столбцами и строками матрицы А, соответственно. Строки матрицы образуют максимальное подмножество линейно-независимых векторов а. Столбцы матрицы

образуют максимальное подмножество линейно-независимых столбцов матрицы А. Когда ранг матрицы А равен числу строк, матрицы исчезают; когда ранг матрицы А равен числу столбцов, исчезают матрицы Если матрица А квадратная и невырожденная, то существуют только матрицы

Определитель. Чтобы вычислить определитель матрицы В, мы последуем процедуре (в); пункт 6 можно опустить. Если процесс не может быть завершен, то В противоположном случае

определитель равен произведению всех опорных элементов, умноженному на где есть число перестановок строк, требуемых в пункте 5.

(ж) Шаговая линейная регрессия. Мы хотим найти -мерный вектор 0, который минимизирует значение функции

Образуем матрицу размерами :

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

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

1) выбрать малое положительное число такое, чтобы изменение значения функции на величину рассматривалось как незначительное;

2) построить матрицу А. Пусть это пустое множество и пусть

3) среди элементов для которых найти тот, скажем для которого величина наибольшая. Выполнить выметание по строке и перевести элемент из множества в множество

4) возвращаться к пункту 3 до тех пор, пока не окажется, что никакая величина не превосходит число В этот момент модель представляется уравнением:

При шаговой регрессии с убывающим числом членов мы строим сначала матрицу

где Полагаем, что и что пустое множество. Вышеприведенный пункт 3 иереходит в пункт

3) среди элементов а для которых найти тот, скажем а, для которого величина наименьшая. Выполнить выметание по строке а и перевести элемент а из множества в множество