Основы линейной алгебры
Собственные значения и собственные векторы
Основные определения
Ненулевой вектор называется собственным вектором квадратной матрицы , если выполняется равенство
где – некоторый скаляр, называемый собственным значением (или собственным числом) матрицы , соответствующим собственному вектору .
Если – некоторый собственный вектор, то вектор () также является собственным вектором.
Геометрический смысл собственного вектора: умножение собственного вектора на матрицу дает вектор , коллинеарный вектору . При этом его длина изменяется в раз.
Если рассматривать как матрицу некоторого линейного оператора, то собственный вектор этого оператора – любой ненулевой вектор , который оператором отображается в коллинеарный ему вектор , а соответствувющий скаляр называется собственным значением оператора.
Подставляя и в соотношение , получим однородную систему линейных уравнений относительно неизвестных :
Эта система имеет ненулевое решение, если ее определитель равен нулю:
Это уравнение называется характеристическим уравнением. Раскрывая определитель, получаем многочлен -й степени относительно :
Корни характеристического уравнения и являются собственными значениями матрицы. Для нахождения собственных векторов нужно каждое собственное значение подставить в однородную систему уравнений и решить ее. Эти системы будут иметь бесконечное множество решений, но для каждого достаточно найти только одно ненулевое решение.
Собственные векторы и собственные значения широко используются в различных приложениях линейной алгебры. Это связано с тем, что многие соотношения существенно упрощаются в системе координат, построенной в базисе из собственных векторов. А множество собственных значений линейного оператора характеризует важные свойства оператора без привязки к какой-либо системе координат.
Нахождение собственных значений и собственных векторов в Engee
В Engee собственные значения и собственные векторы матрицы вычисляются с помощью функции eigen, содержащейся в библиотеке LinearAlgebra. Эта функция имеет два выходных параметра: вектор собственных значений матрицы val и матрица vec, столбцы которой являются собственными векторами матрицы .
Пример. Найдем в Engee собственные значения и собственные векторы матрицы :
using LinearAlgebra;
A = [0 1; -2 -3];
val, vec = eigen(A);
println("eigenvalues =");
display(val);
println("eigenvectors =");
display(vec);
Таким образом, матрица имеет два собственных значения и и два соответствующих им собственных вектора и .
Сделаем проверку. Вычислим разности и и убедимся в том, что они равны нулевым векторам.
display(A * vec[:,1] - val[1] * vec[:,1]);
display(A * vec[:,2] - val[2] * vec[:,2]);
✏️Задание 1
Найдите в Engee собственные значения и собственные векторы матрицы .
Сделайте проверку.
Решение
using LinearAlgebra;
A = [1 -1 0; -1 2 -1; 0 -1 1];
val, vec = eigen(A);
println("eigenvalues =");
display(val);
println("eigenvectors =");
display(vec);
display(A * vec[:,1] - val[1] * vec[:,1]);
display(A * vec[:,2] - val[2] * vec[:,2]);
display(A * vec[:,3] - val[3] * vec[:,3]);
✏️Задание 2
Найдите в Engee собственные значения и собственные векторы диагональной матрицы .
Сделайте проверку.
Решение
using LinearAlgebra;
A = [1 0 0; 0 2 0; 0 0 3];
val, vec = eigen(A);
println("eigenvalues =");
display(val);
println("eigenvectors =");
display(vec);
display(A * vec[:,1] - val[1] * vec[:,1]);
display(A * vec[:,2] - val[2] * vec[:,2]);
display(A * vec[:,3] - val[3] * vec[:,3]);
Как мы видим, собственные значения диагональной матрицы совпадают с элементами, лежащими на ее главной диагонали. А собственные векторы образуют линейно независимую систему векторов.
Применение собственных значений и собственных векторов для вычисления рейтинга веб-страниц
Поисковые системы рассчитывают рейтинг веб-страниц в соответствии с популярностью каждой страницы.
Рассмотрим четыре веб-страницы A, B, C и D. Они содержат ссылки друг на друга. Например, страница A содержит ссылки на B и D.
Взаимосвязь между веб-страницами можно представить в виде графа. Стрелка между A и B означает, что страница A содержит ссылку на страницу B.
Этот граф можно представить в виде матрицы переходов :
Каждый элемент матрицы – это вероятность перехода пользователя со страницы на страницу . Сумма вероятностей в каждом столбце всегда равна единице. Вероятность 0 означает, что ссылка между страницами и отсутствует. Диагональные элементы, равные 0,1, означают, что существует вероятность 0,1 того, что пользователь останется на той же странице.
Пусть вектор-столбец с единицей в третьей строке означает пользователя, который начинает свою навигацию со страницы C.
Зададим в Engee матрицу и вектор . Умножив матрицу на вектор , получим вектор
A = [0.1 0 0 0.45; 0.45 0.1 0.9 0; 0 0 0.1 0.45; 0.45 0.9 0 0.1];
c = [0; 0; 1; 0];
cProb = A *c
Вектор
Если повторить эту операцию много раз (), то в результате получится доминирующий собственный вектор (соответствующим наибольшему по модулю собственному значению) матрицы .
Элементы этого вектора дают вероятность того, что пользователь окажется на определенной странице после навигации по страницам в течение бесконечного времени.
Найдем собственные значения и собственные векторы матрицы :
val, vec = eigen(A)
Два собственных значения комплексные; в данной задаче их можно игнорировать.
Два других собственных значения равны 1 и 0,1. Доминирующий собственный вектор (4-й столбец матрицы
Сохраним доминирующий собственный вектор в переменой
v1 = vec[:,4]
Чем больше значения элементов собственного вектора, тем более высокий рейтинг будет у этой страницы. Т.е. у пользователя больше всего шансов оказаться на странице D.
Напомним, что произведение собственного вектора на число также является собственным вектором. Если промасштабировать вектор
Разделив вектор
v1Prob = v1 / sum(v1)
Таким образом, пользователь, переходящий между 4 страницами, имеет вероятность приблизительно 18% оказаться на страницах A и C, 27% – на странице B и 36% – на странице D.
✏️Задание 3
Найдите в Engee вероятности оказаться на каждой из 4 страниц по прошествии бесконечного времени, если матрица переходов имеет вид: .
Подсказка
Сначала задайте матрицу переходов . Затем найдите ее собственные значения и собственные векторы с помощью выражения val, vec = eigen(A). Сохраните в переменной v1 доминирующий собственный вектор – тот столбец матрицы vec, который соответствует наибольшему по модулю собственному значению (т.е. наибольшему по модулю элементу вектора val). Затем разделите доминирующий вектор на сумму его элементов, в результате получится вектор искомых вероятностей.
Решение
A = [0.1 0 0 0; 0.5 0.5 0.5 0.5; 0 0 0.5 0.45; 0.4 0.5 0 0.05];
val, vec = eigen(A)
Как мы видим, наибольшее по модулю собственное значение равно единице (4-й элемент вектора val). Ему соответствует 4-й собственный вектор (доминирующий вектор). Сохраним его в переменной v1 и пронормируем, разделив на сумму его элементов:
v1 = vec[:,4];
v1Prob = v1 / sum(v1)
Таким образом, пользователь имеет вероятность 50% оказаться на странице B, приблизительно 24% – на странице C, 26% – на странице D и нулевую вероятность – на странице A.