8508

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

Пусть имеется множество векторов { 1, … , } и некоторый вектор . Тогда вектор – ближайший к вектору , если

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

Важную роль в алгебре векторов играет знаменитое неравенство Коши:

| T | ≤ ‖ ‖‖ ‖

для любых векторов и . Доказывается оно следующим образом. Если хотя бы один из векторов нулевой, то неравенство верно. Если оба вектора ненулевые, обозначим ‖ ‖ = , ‖ ‖ = и сделаем преобразования

0 ≥ ‖ − ‖2 = 2‖ ‖2−2( )T( )+ 2‖ ‖2 = 2(‖ ‖2‖ ‖2−‖ ‖‖ ‖( T )).

Разделив обе части на ‖ ‖‖ ||, получим T ≤ ‖ ‖‖ ‖. Применяя это неравенство к векторам − и , получим − T ≤ ‖ ‖‖ ‖. Оба полученных неравенства доказывают справедливость неравенства Коши. Заметим, что неравенство Коши превращается в равенство, если только ‖ −‖ = 0, т.е. = . Это значит, что неравенство Коши переходит в равенство только в случае, когда один из векторов равен произведению скаляра на другой вектор или, другими словами, когда сомножители коллинеарны.

Угол между двумя ненулевыми векторами и определяется как

= arccos

T

‖ ‖‖ ‖

или, что то же, как единственное число между 0 и , для которого

T = ‖ ‖‖ ‖ cos .

11

В случае двумерных или трехмерных векторов это понятие совпадает с привычным определением угла. Например, угол между векторами

1, … ,

зависим, по крайней мере один из векторов является линейной комбинацией остальных: если ≠ 0, то

= (− 1/ ) 1 + +(− −1/ ) −1 +(− +1/ ) +1 + +(− / ) .

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

Набор векторов { 1, … , } с ≥ 1 называется линейно независимым, если

1 1 + + = 0

только при всех нулевых 1, … , . Например, векторы

линейно независимы, так как из 1 1 + 2 2 + 3 3 = 0 следует, что

Решая эту линейную систему, находим единственное решение = 0,= 1, 2, 3. Единственный вектор линейно независим, если он ненулевой. Стандартные единичные векторы 1, … , линейно независимы,

12

так как

= 1 1 + +

для некоторых других , = 1, … , . Вычитая одно уравнение из другого, получим

0 = (1 − 1) 1 + + ( − ) ,

откуда в силу линейной независимости векторов 1, … , следует, что= , = 1, … , . В дальнейшем будет показано, как находить коэффициенты разложения данного вектора в линейную комбинацию заданного набора векторов.

Если -векторы 1, … , линейно независимы, то ≤ . Этот факт, доказательство которого мы опустим, можно выразить также следующим образом: любой набор из + 1 и более -мерных векторов является линейно зависимым. Например, любые три двумерных или четыре трехмерных вектора линейно зависимы. Набор из линейно независимых -мерных векторов называется базисом. Если -мерные векторы 1, … , образуют базис, то любой -мерный вектор может быть единственным образом представлен как линейная комбинация базисных векторов. Действительно, рассмотрим набор {1, … , , }. Эти векторы линейно зависимы, следовательно существуют ненулевые коэффициенты 1, … , +1 такие, что

1 1 + + + +1 = 0.

13

Если +1 = 0, то

1 1 + + = 0,

откуда следует 1 = = = 0, что противоречит предположению. Поэтому +1 ≠ 0 и тогда

= (−1/+1) 1 + + (− /+1) .

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

Набор векторов 1, … , называется взаимно ортогональным, если= 0 для всех ≠ , и ортонормированные, если плюс к этому ‖ ‖ = 1 для всех . Стандартные -мерные векторы 1, … , – ортонормированы. Ортонормированные векторы являются линейно независимыми. Действительно, пусть

1 1 + + = 0.

Скалярно умножая это равенство последовательно на векторы , = 1, … , , получим

0 = T(1 1 + + ) = ,

что доказывает утверждение. Если некоторый вектор есть линейная комбинация ортонормированных векторов

= 1 1 + + ,

то умножая скалярно обе части этого равенства на вектор , получим= T . Таким образом, для любого вектора имеем

= (1T) 1 + + (T) .

14

1.1.2. Алгоритм Грама-Шмидта

Вэтом разделе будет описан классический алгоритм Грама-Шмидта,

спомощью которого можно определить является ли данное множество-мерных векторов 1, … , линейно независимым, а также решать линейные уравнения и другие полезные в приложениях задачи. Если эти векторы линейно независимы, то алгоритм выдает набор ортонорми-

рованных векторов 1, … , , обладающих следующими свойствами: для каждого вектор является линейной комбинацией векторов 1, … , , а вектор – линейной комбинацией векторов 1, … , . Если векторы1, … , −1 линейно независимы, но векторы 1, … , линейно зависимы, то алгоритм обнаруживает это и останавливается. Таким образом,

алгоритм находит первый вектор , который является линейной комбинацией предыдущих векторов 1, … , −1.

Для заданных векторов 1, … , при каждом = 1, … , алгоритм состоит из трех шагов:

2.проверка линейной зависимости: если = 0, то стоп;

3.нормализация: = /‖ ‖.

Проанализируем алгоритм. Пусть 1, … , линейно независимы. Докажем по индукции, что 1) для любого ≤ имеем ≠ 0, 2) векторы1, … , ортонормированы, 3) – линейная комбинация 1, … , и 4)–линейная комбинация 1, … , . Действительно, на первом шаге при

= 1 имеем 1 = 1, поэтому 1 = ‖ 1‖ 1 и 1 = (1/‖ 1‖) 1. Предполо-

жим, что −1 ≠ 0 для некоторого < . Если = 0, то из первого шага алгоритма следует, что является линейной комбинацией 1, … , −1,

где −1 по предположению индукции является линейной комбинацией 1, … , −1. Отсюда следует, что является линейной комбинацией

1, … , −1, т.е. векторы 1, … , линейно зависимы, что противоречит линейной независимости 1, … , . Следовательно, ≠ 0.

Теперь покажем, что 1, … , ортогональны (то, что они нормированы, непосредственно следует из третьего шага алгоритма). Вычисляя при = 1, … , − 1 скалярные произведения, получим

T = T − ( T ) T 1 − − ( T ) T −1 = T − T = 0,

1 −1

15

так как T = 0 для ≠ и T = 1. С учетом того, что = (1/‖ ‖) ,

получим T = 0 для = 1, … , − 1.

Из первого шага алгоритма следует, что – линейная комбинация1, … , , а именно

индукции каждый из 1, … , −1 – линейная комбинация 1, … , −1, то, а значит и , является линейной комбинацией 1, … , , что завер-

шает доказательство.

Из этих свойств следует, что если алгоритм доходит до конца, то векторы 1, … , линейно независимы. Действительно, пусть

= 1 = 0.

Теперь допустим, что алгоритм остановился на -м шаге, где < , т.е. = 0. Тогда

т.е. есть линейная комбинация векторов 1, … , −1, каждый из которых в свою очередь является линейной комбинацией векторов 1, … , −1. Следовательно, есть линейная комбинация 1, … , −1, т.е. векторы1, … , , а значит и векторы 1, … , , линейно зависимы. Таким образом, алгоритм Грама-Шмидта дает прямой ответ на вопрос, является ли данное множество векторов линейно зависимым или нет.

Далее, допустим, что имеется набор линейно независимых векторов1, … , и требуется определить, является ли заданный вектор их линейной комбинацией. Для этого применим алгоритм к набору из + 1 вектора 1, … , , . Если окажется, что эти векторы линейно зависи-

16

мы, то ответ утвердительный, если же эти векторы линейно независимы, то ответ отрицательный. Ясно, что алгоритм не может остановиться на первых шагах, а если +1 = 0, то есть линейная комбинация

1, … , .

1.1.3. Матрицы

Матрицей называется таблица, заключенная между двумя скобками и состоящая из строк и столбцов

Элемент матрицы находится в -ой строке и -ом столбце. Черно-белую фотографию, разбитую на × пикселей, можно за-

писать как ( × )-матрицу, элемент которой отражает интенсивность соответствующего пикселя. Среднее количество осадков, выпавших в регионах за определенные периодов времени, представимы матрицей размером × , строки которой соответствуют различным регионам. Матрицей × можно представить цены различных продавцов за различных товаров. Матрицу × можно использовать для информации об объектах произвольной природы, имеющих две характеристики, одна из которых принимает значений, а другая – . Например, абитуриенты, поступившие в университет в различные годы, приезжают из различных регионов. Элемент такой матрицы показывает количество абитуриентов из -го региона, принятых в -м году.

Две матрицы равны, если они имеют одинаковые размеры и соответствующие их элементы равны. Если = , то матрица называется квадратной. Квадратные матрицы с нулевыми элементами вне диагонали называются диагональными. Множество ( × )-матриц с действительными элементами обозначается R×. -мерный вектор можно рассматривать как ( × 1)-матрицу, а матрицу, состоящую из одной строки, т.е. (1 × )-матрицу, называют вектор-строкой. Полезно рассматривать так называемые блочные матрицы, элементы которых сами

17

являются матрицами согласованных размеров. Например, матрица

В частности, ( × )-матрица может быть записана как строка из ее столбцов или как столбец из ее строк:

Матрицы часто используют для того, чтобы представить набор векторов одной размерности: если 1, … , – -мерные векторы, которые отражают признаки каких-то объектов, то их можно собрать в одну ( × )-матрицу

= ( 1 2 ) .

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

= ( 1 ) ,

где 1, … , – набор -мерных единичных векторов.

Если есть ( × )-матрица с элементами , то транспонированной к ней называется ( × )-матрица с элементами = , которая обозначается как = T. Другими словами, строчки и столбцы матрицы переходят в столбцы и строчки матрицы T. Нетрудно проверить, что транспонирование блочной матрицы осуществляется следующим образом:

18

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

( + )T = T + T.

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

Норма ( × )-матрицы обозначается ‖ ‖ и является квадратным корнем из суммы квадратов всех ее элементов, т.е.

Это определение согласуется с определением нормы вектора, когда = 1. Норма матрицы является количественной характеристикой ее величины. Матричная норма удовлетворяет всем свойствам норм, а имен-

но: ‖ ‖ ≥ 0 и ‖ ‖ = 0 только если = 0; ‖ ‖ = | |‖ ‖; ‖ + ‖ ≤ ‖ ‖ + ‖ ‖. Матричная норма позволяет определить расстояние между двумя матрицами как ‖ − ‖. Если это величина маленькая, то можно считать, что эти матрицы не сильно различаются между собой. Нетруд-

но видеть, что ‖ T‖ = ‖ ‖ и что квадрат нормы матрицы равен сумме

квадратов норм ее столбцов, т.е. ‖ ‖2 = ∑ ‖ ‖2.

=1

Если – ( × )-матрица и – -мерный вектор, то произведением этой матрицы на этот вектор будет -мерный вектор = с элементами

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

19

т.е. = T , где T – -я строка матрицы . Если – -й столбец матрицы , тогда вектор = может быть записан, как следует из (1.2), в

виде

= 1 1 + 2 2 + + ,

т.е. в виде линейной комбинации столбцов матрицы c коэффициентами, являющимися соответствующими компонентами вектора . Умножение матрицы на единичный вектор позволяет получить соответствующий столбец этой матрицы, т.е. = . Произведение T представляет собой вектор-столбец, элементы которого есть соответствующие элементы -й строки матрицы . Операция произведения матрицы на вектор обладает следующими свойствами:

Уравнение = , где – ( × )-матрица, можно интерпретировать как отображение -мерного вектора , который называется входом, в -мерный вектор , называемый выходом системы, определяемой матрицей .

Если матрица указывает цены товаров у продавцов, а -мерный вектор показывает количества этих товаров (корзина товаров), то вектор -мерный вектор = содержит цены корзины товаров у разных продавцов.

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

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

Используя операцию умножения матрицы на вектор, можно компактно выразить линейную зависимость или независимость заданных векторов. Для этого составим матрицу , столбцами которой являются эти векторы. Тогда эти векторы линейно зависимы, если = 0 для некоторого ненулевого вектора ≠ 0, и линейно независимы, если = 0

20