Пример 0

Пример 1. ( линейный оператор с характеристическим многочленом )

Рассмотрим линейный оператор с матрицей

,.

Покажем, что рациональное выражение

(2)

где а - первообразный корень степени 3 из 1 – L–инвариант этого оператора.

=

Определение 2. Пусть , - два набора переменных. Линейным циклом мы называем фрагмент императивной программы вида

X:= b;

While Q(X, b) do X:= A*X

Замечание. Операторы X:=b, X:=A*X интерпретируются как одновременные присвоения переменным левых частей значений правых частей. В дальнейшем условие Q(X, b) мы будем игнорировать, считая линейный цикл бесконечным, а его выполнение недетерминированным. Т.о. мы рассматриваем циклы вида

X:= b;

While True|False do X:= A*X

Предложение 1. Если - L-инвариант линейного оператора , многочлен - инвариант линейного цикла над полем . Такие инварианты циклов мы будем также называть L-инвариантами (линейных циклов).

Пример 2. (линейный цикл с оператором примера 1)

Линейный цикл, соответствующий оператору , имеет вид

(x, y, z):= (a, b, c);

While True|False do (x, y, z):= (y, z, 2*x)

L-инвариант этого цикла определен формулой (2):

(3)

Отметим, что L-инвариант цикла определен над полем . Однако ему соответствует набор L-инвариантов с коэффициентами из поля , которые можно построить, приведя (3) к каноническому виду – многочлену от , а затем – к многочлену от , используя соотношение и соотношения Виета. Продемонстрируем технику вычисления L-инвариантов над полем .

Введем обозначения

,

Многочлены определены над полем . Вычислим в виде многочленов от . Получим:

, ,

где

, ,

, , (4)

Дробь представима в виде многочлена от с коэффициентами из .

,

(5)

можно вычислить методом неопределенных коэффициентов, используя равенство (5). Осталось заметить, что - L-инварианты оператора . В самом деле,

Поскольку , имеем

Ввиду линейной независимости векторов над

, , ,

т.е , , - L-инварианты над .

Отметим, что если переменным придать числовые значения, L-инвариант преобразуется в инвариант цикла.

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

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

. (6)

Тогда

(7)

- L -инвариант линейного оператора .

Доказательство. Пусть . Тогда

Соотношение (6) мы будем называть мультипликативным соотношением (между корнями характеристического многочлена), определяющим L -инвариант (7).

Пример 3 (продолжение примера 2). Рассмотрим метод предложения 2 применительно к примеру 2. Вычислим собственные числа оператора

, . Т.о. характеристический многочлен имеет вид . Его корни - , (- первообразный корень степени 3 из 1).

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

, ранг которой равен 2. Фундаментальное решение этой системы – вектор . Поэтому собственными векторами оператора являются векторы

.

Легко установить, что . Поэтому оператор имеет L-инвариант (2).

Следствие 1. Если характеристический (минимальный) многочлен линейного оператора имеет свободный член, равный (т.е. ), линейный оператор обладает L -инвариантом.

Доказательство. Пусть – свободный член многочлена . Тогда . Поэтому либо , либо (- L-инвариант оператора . Отметим, что коэффициенты этого полинома принадлежат , поскольку они симметричны относительно перестановок корней .

Пример 4. Цикл поворота точки плоскости на угол .

(x,y):= (a,b);

While True do (x, y):= (4/5*x - 3/5*y, 3/5*x + 4/5*y)

Вычислим собственные значения и собственные векторы оператора :

. .

Дата добавления: 2014-01-20