билет 3

Билет намбер 3:

1. Линейный оператор и его матрица. Собственные числа и собственные векторы линейного оператора. Понятие диагонализируемости линейного оператора. Существование базиса из собственных векторов линейного оператора как основной необходимый и достаточный признак его диагонализируемости. Характеристический многочлен линейного оператора и его свойства.

Ответ на билет намбер 3:

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

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

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

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

Если пространства  и  совпадают, то говорят, что оператор действует в пространстве . В дальнейшем ограничимся рассмотрением линейных операторов, действующих в линейном пространстве .

Линейный оператор и его матрица.

Рассмотрим линейный оператор , действующий в конечномерном линейном пространстве  и пусть  базис в . Обозначим через образы базисных векторов .

Матрица

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

Доказано, что каждому линейному оператору, действующему в n-мерном линейном пространстве, отвечает единственная квадратная матрица порядка n; и обратно каждая  квадратная матрица порядка n задает единственный линейный оператор, действующий в этом пространстве. При этом соотношения

с одной стороны, связывают координаты образа  с координатами прообраза , с другой стороны,  описывают действие оператора, заданного матрицей .

Собственные значения и собственные векторы линейного оператора

Пусть  линейный оператор, действующий в линейном пространстве.

Число  называется собственным значением, а ненулевой вектор соответствующим собственным вектором линейного оператора , если они связаны между собой соотношением  .

Пусть  матрица оператора в некотором базисе.

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

Уравнение  называется характеристическим уравнением оператора, а многочлен  характеристическим многочленом оператора.

Для собственных значений и собственных векторов линейного оператора справедливы следующие утверждения:

характеристический многочлен оператора, действующего в n-мерном линейном пространстве является многочленом  n-й степени относительно ;

линейный оператор, действующий в n-мерном линейном пространстве имеет не более различных собственных значений;

собственные векторы, отвечающие различным собственным значениям, линейно независимы;

если линейный оператор, действующий в  n-мерном линейном пространстве , имеет  различных собственных значений, то собственные векторы оператора образуют базис в пространстве ; этот базис называют собственным базисомоператора;

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

Диаганализаруемость линейного оператора и т.д. и т.п.

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

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

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

ТЕОРЕМА (необходимое и достаточное условие диагональности матрицы оператора) .

Матрица A оператора φ в базисе e1,e2,…,en имеет диагональный вид все базисные векторы ei являются собственными векторами этого оператора.

Для доказательства теоремы нам понадобится лемма.

Лемма 2.7.3. Собственные подпространства Vλ1, . . . , Vλk, соответствующие попарно различным собственным значениям λ1, . . . , λk оператора A, образуют прямую сумму Vλ1 ⊕ . . . ⊕ Vλk

Доказательство. Проведём индукцию по k. При k = 1 утверждение очевидно. По определению прямой суммы мы должны проверить, что соотношение

(2.3) v1 + . . . + vk = 0,

где vi ∈ Vλi

, влечёт v1 = . . . = vk = 0. Применив к (2.3) оператор A, получим

λ1v1 + . . . + λkvk = 0

Умножим (2.3) на λk и вычтем из предыдущего соотношения:

(λ1 − λk)v1 + . . . + (λk−1 − λk)vk−1 = 0.

По предположению индукции получаем (λ1 − λk)v1 = . . . = (λk−1 − λk)vk−1 = 0. Так

как по условию λ1 − λk ̸= 0, . . . , λk−1 − λk ̸= 0, получаем v1 = . . . = vk−1 = 0. Тогда

из (2.3) следует, что и vk = 0.

Характеристический многочлен линейного оператора и его свойства

Для данной матрицы , где Е — единичная матрица, является многочленом от , который называется характеристическим многочленом матрицы A

Свойства:

Для матрицы , характеристический многочлен имеет степень .

Все корни характеристического многочлена матрицы являются её собственными значениями.

Теорема Гамильтона — Кэли: если  — характеристический многочлен матрицы , то .

Характеристические многочлены подобных матриц совпадают: .

Если A и B — две -матрицы, то . В частности, отсюда вытекает, что tr(AB)=tr(BA) и det(AB)=det(BA).

В более общем виде, если A — -матрица, а B — -матрица, причем mn, так что AB и BA — квадратные матрицы размеров m и n соответственно, то

.

2. Виды списочных структур. Методы работы со списками.

Если для каждой динамической переменной описывать и хранить ее «личный» указатель, то никакой выгоды на этапе выполнения программы получить не удастся: часть памяти, как и прежде, будет выделяться статически, а ее общий объем даже увеличится — ведь каждый указатель требует для себя четыре байта.

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

Списки применяются, например, в таких ситуациях:

программист заранее ничего не знает о том, какой именно объем памяти может потребоваться его программе;

некоторые (особенно «тяжелые») переменные нужны поочередно, и после того как первые «отработали свое», их можно смело стирать из памяти, не дожидаясь конца работы программы, — освобождать место для других «тяжелых» переменных;

в процессе обработки данных нужно провести большую работу по перестройке всей структуры «на ходу»; и т.д.

Итак, каждый элемент создаваемого списка должен содержать:

полезную информацию, которая может иметь любой формат: integer, real, array, record и т.п.;

специально выделенное поле (и, может быть, не одно), которое хранит адрес другого элемента этой же структуры.

Приведем примеры различных списочных структур:

a) Односвязный (линейный) список: структура, каждый элемент которой «знает» адрес только следующего за ним элемента (см. рис. 10.1 (a)). Очень удобно представлять таким списком стек и очередь (см. лекцию 9).

b) Двусвязный линейный список: структура, каждый элемент которой «помнит» адрес не только следующего, но и предыдущего элемента списка (см. рис. 10.1 (b)). Этот список удобен для работы с деками (см. лекцию 9)

c) Бинарное дерево (см. лекцию 11) может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков (см. рис. 10.1 (c)). Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трехсвязным.

d) Для представления ориентированного графа (см. лекцию 11) можно использовать иерархические списки - комбинацию из двух различных линейных списков (см. рис. 10.1 (d): вершины задаются структурой, содержащей три поля, а дуги — два; справа показан орграф, представленный приведенной списочной структурой ).

методы работы со списками:

Обращение к элементам списка

Если есть указатель, указывающий на некоторый элемент списка, то содержимое полей этого элемента и даже следующих за ним можно получить так (см. рис. 10.2):

p

адрес текущего элемента списка;

p^

- запись из нескольких полей, хранящаяся по адресу p ;

p^.znachenie

- значение первого поля этой записи;

p^.next_element

- значение второго поля этой записи, являющееся адресом следующего элемента списка;

p^.next_element^.znachenie

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

Создание списков

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

Просмотр элементов списка

Удаление элементов списка

Для того чтобы при удалении элемента из середины списка не терялась целостность всей структуры, необходимо при поиске удаляемого элемента «остановиться» за один шаг до него: в тот момент, когда следующий за текущим элемент должен быть удален

Перестройка списков

Разницу между структурой статической (массив) и структурой динамической (список) очень доступно проиллюстрировал Никлаус Вирт в своей книге «Алгоритмы и структуры данных». Мы позволим себе позаимствовать оттуда, хотя и не дословно, красивый пример.

Представим обычную очередь у прилавка в магазине. Первый покупатель — это тот, кто в данную минуту стоит непосредственно возле прилавка; следующий за ним — второй, за вторым — третий и т.д. Покупатели занумерованы строго в порядке следования, и вновь пришедшие встают в хвост. В принципе, взглянув на очередь, всегда можно сказать, кто за кем стоит. А что происходит, если один из покупателей желает покинуть очередь? Хвост тут же сдвигается: каждый человек делает шаг вперед, чтобы очередь не утратила целостности. Если же, наоборот, некто желает встроиться в середину очереди (невзирая на крики «А вас тут не стояло!»), то задним приходится пятиться, чтобы освободить ему место. Точно так же ведут себя элементы линейного массива.