С.И.Хашин
Нахождение собственных векторов и собственных значений матрицы — важнейшая задача линейной алгебры, см., например здесь и здесь . Предлагаемые алгоритмы достаточно сложны. Причем, их не удастся значительно упростить, просто из-за сложности самой задачи. В случае симметричной матрицы задача упрощается, однако предлагаемые алгоритмы всё равно сложны.
Однако, если мы хотим найти не все собственные значения, а лишь одно из них — наименьшее, можно привести достаточно простой и эффективный алгоритм.
К удивлению, ни в одном из известных учебников по численым методам этот алгоритм не приводится, хотя все необоходимые идеи в них есть, нет только последнего шага. Если всё-же алгоритм где-то найдется, сообщите, пожалуйста.
В следующих модулях приведена функция на С++, позволяющую решать эту задачу:
eigen_min.h - заголовочный файл
eigen_min.cpp - реализация.
В модуле имеется, фактически, одна-единственная функция
double EigenMin(int N, double *a, double *evec); // evec - eigenvectors of positive symmetric matrix with minimal eigenvalue (returned)
На самом деле имеются еще несколько вспомогательных, совсем простых функций, реализующих некоторые элементарные операции с векторами из действительых чисел:
double vdbl_len2(int N, double *a); // |A|^2 void vdbl_normal(int N, double *a); // length(a):=1 double vdbl_scprod(int N, double *a, double *b); // (a,b) void vdbl_add(int N, double *a, double *b, double R); // a += R*b void vdbl_mult(int N, double *res, double *matr, double* v); // res = matr*v
R(v) = (v, Av)/(v,v)
Рассмотрим алгоритм нахождения для произвольного вектора v следующего вектора w, который будет иметь вид w=v+ t Av для некоторого t.
Пусть v — произвольный вектор. Введем обозначения:
Найдем минимум значений функции R на векторах вида v + t Av:
Замечание 1. f3 = (v, A3v) = (Av, A2v) , поэтому достаточно вычислить вектора Av и A2v, вектор A3v можно не вычислять.
Замечание 2. Если размерность пространства равна 2, то предлагаемый метод
даст точный ответ за один шаг.