Examples

an+1

= an¡1

55; : : : :

+ an:

0 12 1	0	1, поступить согласно протоколу дешифрования.
0	0	A
@ ¡

1¡1 1

Например, если получена последовательность 19; 45; 26; 13; 36; 41 òî

в результате дешифровки получится вектор 19; 7; 0; 13; 10; 18; было зашифровано THANKS.

Упражнения

1. Используйте шифр Цезаря для передачи сообщения THERE IS A SPY ON THE LINE.

2. Расшифруйте сообщение Цезаря об исходе сражения: SFZQLQV.

6Структура линейного преобразования и формула для чисел Фибоначчи.

Числовая последовательность fan; n 2 Ng называется возвратной или рекуррентной если каждый е¼ последующий член an+1 вычисляется по некоторому правилу исходя из уже вычисленных членов a1; : : : ; an:

В XIII веке Фибоначчи поставил следующую проблему о воспроизводстве кроликов. "Предположим, что новорожденные кролики в тече- ние первого месяца своей жизни не размножаются. А далее каждая пара кроликов каждый месяц производит одну пару кроликов. Следует определить количество пар кроликов в любом месяце в предположении, что они не погибают вообще." Здесь нужно определить формулу по которой можно вычислять число этих пар.

Эта проблема определяет последовательность чисел

0; 1; 1; 2; 3; 5; 8; 13; 21; 34;

Она подчиняется рекуррентной формуле Рождается

столько пар кроликов, сколько их было в позапрошлом месяце плюс количество пар кроликов, родившихся перед этим месяцем. Эта числовая

19

последовательность называется последовательностью Фибоначчи.

Рассмотрим двумерное числовое пространство пар чисел. Полагаем
X1 =	µ 0	¶: Будем представлять текущие значения вектором Xn =
µ an¡1	1
	¶: Последующие значения вычисляются произведением матриц
an	= µ		¶ =	µ			¶ ¢ µ an¡1	¶ = AXn; здесь A = µ			¶:
Xn+1		an			1	0			1	0
		an+1			1	1	an		1	1
Заключаем Xn+1				= An ¢ X1: Т.о., чтобы решить проблему следует
вывести формулу для степени матрицы An:

Матрица A симметрическая, используем структуру симметрических линейных преобразований. Найд¼тся ортогональная матрица Q из векторов ортонормированного базиса собственных векторов матрицы A и диагональная матрица D из собственных чисел матрицы A для которых имеет место представление A = QDQ¡1: Тогда в силу ассоциативности

произведения матриц и свойства ортогональной матрицы при любом натуральном n выполняется равенство:

An = QDQ¡1QDQ¡1 : : : QDQ¡1 = QDnQ¡1:

Это позволит вывести формулу. Заметим, что достаточно определить разложение в котором матрица Q всего лишь невырожденная матрица

составленная из собственных векторов (не обязательно нормированных). Определим искомое разложение.

													1+p					;	¸2 = 1¡p							; это корни
Собственные числа матрицы A: ¸1 =																5									5
полинома ¸		¡ ¸ ¡ 1. Заключаем D =											Ã		2		0			1¡2p5			!	: Собственные
																							2
		2													1+p				5	0
																	2
векторы (		2		; 1) è (		¡2		; 1) образуют матрицу Q =															µ	1			1			¶:
	1+p		5	1		p	5																		1+p		5	1¡p	5
																								2			2
Получаем формулу
				An = Q Ã ( 20						)	(1¡2p5)n							!Q¡1:
								1+p	5		n		0

20

f(x0; y0) является

Отсюда

ÃÃ

!

¡ Ã

1

¡2

! !

an = p5

2

:

1

1 + p5

n

p5

n

p

Число Á = 1+2 5 ¼ 1; 61803398 : : : называется золотой пропорцией.

Упражнения

1. В террариуме живут зеленые и	2. В одном изолированном водоеме
красные хамелеоны. Каждый день	загородили часть берега сетью. В
одна треть хамелеонов меняет	загородку выпустили косяк рыб.
свой цвет на противоположный, а	Оказалось, что в течение одного
остальные земноводные окраски	дня одна треть всех огороженных
не меняют. Через сколько дней в	рыб выплывает за огороженную
террариуме будет равное число	часть берега, а половина всех рыб
животных разного цвета если	вне загородки вплывает в нее.
вначале разница между теми и	Сколько было выпущено особей
другими составляла 162	если только через пять дней в
животных?	загородке и вне ее оказалось
	равное количество морских
	животных?

7Квадратичные формы и экстремумы вещественных функций нескольких переменных.

Рассмотрим функцию двух переменных z = f(x; y) и точку из е¼ об-

ласти определения (x0; y0). Функция в этой точке имеет локальный экстремум если в некоторой окрестности точки значение

наибольшим или наименьшим значением.

Будем предполагать, что функция определена и является трижды гладко дифференцируемой в окрестности точки (x0; y0): В этой окрест-

ности функция представляется формулой Тейлора:

21

@2f

+@x2

f(x; y) = f(x0; y0) +		@f		(x0; y0)(x ¡ x0) +	@f	(x0; y0)(y ¡ y0)+
		@x			@y
(x0; y0)(x¡x0)2+2	@2f						@2f	(x0; y0)(y¡y0)2+: : : :
			(x0; y0)(x¡x0)(y¡y0)+
	@x@y						@y2

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

Необходимым условием экстремума в точке (x0; y0) является усло-

вие стационарности этой точки, т.е. должны выполняться условия

8

>< @f@x (x0; y0) = 0

>: @f@y (x0; y0) = 0:

Стационарные точки функции также называют е¼ критическими точ- ками.

Это условие следует из необходимого условия экстремума функций одной переменной (по переменной x и по переменной y). А достаточное

условие состоит в знакоопредел¼нности квадратичной формы

F (¢X; ¢Y ) =	@2f	(x0; y0)¢X2	+ 2	@2f	(x0; y0)¢X¢Y +	@2f	(x0; y0)¢Y 2:
	@x2			@x@y		@y2

Матрица этой формы называется гессианом функции в точке, она
симметрическая:	0							1 =
		@@x2f2 (x0; y0)		@2f			(x0; y0)
H(x0; y0) =				@x@y					A	B	:
	B	@x@y@2 (x0; y0)		@@y2f2 (x0; y0)				C	µ B	C	¶
	@							A
Достаточное условие получается для случая невырожденного гес-

сиана функции в точке (x0; y0); т.е. при условии detH(x0; y0) = AC¡B2 =6 0: В этом случае либо AC ¡ B2 > 0; ëèáî AC ¡ B2 < 0: Рассмотрим оба

эти варианта по порядку.

22

f(x; y). À åñëè

Из критерия положительной определ¼нности формы (положительности главных миноров матрицы формы H(x0; y0) критерия Сильвестра)

заключаем, что при условии A > 0; detH = AC ¡ B2 > 0 форма поло-

жительно определена и в точке (x0; y0) имеет место локальный минимум функции A < 0; AC ¡ B2 > 0; то форма отрицательно

определ¼нная, имеем локальный максимум. В случае же AC ¡ B2 < 0

форма неопредел¼нная, точка является седловой точкой. По одному направлению это точка максимума, а по другому минимума, функция f(x; y) в точке (x0; y0) не достигает экстремальных значений.

Для примера определим точки экстремума функции

z = f(x; y) = 13x3 + xy2 ¡ 4xy + 1:

Для этого достаточно вначале определить все критические точки, а
затем с помощью теории квадратичных форм выяснить их характер.
Имеем	fx = x2 + y2 ¡ 4y = 0
	½ fy = 2xy ¡ 4x = 2x(y ¡ 2) = 0:

Решение этой системы определяет четыре критические точки функции: A(0; 0); B(0; 4); C(2; 2); D(¡2; 2): Чтобы определить их характер

вычисляем вторые производные fxx = 2x;			fxy	= 2y ¡ 4; fyy = 2x è
образуем гессиан функции:	µ 2y0 ¡0	4 2x¡0	¶	:
H =
	2x	2y0	4

По критерию Сильвестра заключаем, что точки A è B являются седловыми, в них detH < 0; форма неопредел¼нная. В точке C достигается

локальный минимум, форма положительно определ¼нная. А в точке Dлокальный максимум, форма отрицательно определена.

23

Упражнения

1. Определить характер точки	2. Будет ли (1;0;0) точкой
начала координат для функции	локального минимума, локального
f(x; y) = 3x2 ¡ xy + y2:	максимума или седловой точкой
	для функции
	f(x; y; z) = x3 + xyz + y2 ¡ 3x ?

3. Проверьте, что у дважды гладко дифференцируемой функции двух переменных f(x; y) стационарная точка (x0; y0) является седловой тогда

и только тогда, когда detH(x0; y0) < 0: Верно ли это для функции тр¼х переменных?

8Линейная независимость дифференцируемых функций и определитель Вронского.

Рассмотрим семейство функций f1; : : : ; fn: Как и для множества век-

торов оно называется линейно зависимой системой если найд¼тся нетривиальная линейная комбинация c1f1(x) + : : : + cnfn(x) (c вещественными

коэффициентами в которой есть ненулевые коэффициенты ci =6 0) которая представляет нулевую функцию c1f1(x) + : : : + cnfn(x) = 0:

Будем предполагать, что все эти функции дифференцируемы n ¡ 1

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

нулевую функцию: c1f1(m)(x) + : : : + cnfn(m)(x) = 0: В частности, линейно зависимыми являются столбцы функций, векторные функции

0 f1

@: : :

f1(n¡1)

1 0 fn

1

A; : : : ; @ : : : A:

fn(n¡1)

24

Определителем Вронского или вронскианом этого семейства называ-
ют новую функцию, выраженную определителем от производных:
	° f10				: : : fn0	°
		f1	¡		: : : fn	°
	° f1				: : : fn ¡
W (x) =	°					°	:
	°	: : :			: : : : : :	°
	°					°
	°					°
	°	(n		1)	(n 1)	°
	°					°
	°					°

По свойству определителя для линейно зависимого семейства функций при любом x имеем W (x) = 0: В частности, если хотя бы для одного

x выполняется неравенство W (x) 6= 0; то система функций будет линейно независимой.

Например, система функций f1; sin(x); cos(x)g линейно независима поскольку

	°	0		sin(x)	cos(x)	°
	°	1	sin(x)		cos(x)	°
	°		¡		¡ sin(x)	°	= cos(2x); W (0) = 1 6= 0:
W (x) =	°	0	cos(x)			°
	°					°
	°					°

Линейное дифференциальное уравнение уравнение, связывающее производные неизвестной функции y(x):

a0(x)y(n) + a1(x)y(n¡1) + : : : + an(x)y = f(x):

Предполагается, что некоторый коэффициент такого уравнения ненулевой, отбросим старшие нулевые слагаемые и будем предполагать что уже

a0 =6 0:

Если в дифференциальном уравнении правая часть нулевая,f(x) = 0,

то его называют однородным дифференциальным уравнением.

Мы ограничимся дифференциальными уравнениями с постоянными коэффициентами, будем считать, что a0; : : : ; an вещественные числа.Такие

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

Определим дифференциальный оператор формулой

L(y) = a0y(n) + a1y(n¡1) + : : : + any:

25

По свойству производной суммы этот оператор является линейным оператором в классе функций дифференцируемых n ðàç Cn; L : Cn !

Cn: Решение дифференциального уравнения состоит в определении всех функции y 2 Cn для которых L(y) = f(x):

Вначале определим ядро дифференциального оператора L, оно образует множество решений однородного дифференциального уравнения

ker L = fy 2 Cnj L(y) = a0y(n) + a1y(n¡1) + : : : + any = 0:g

По свойству линейного оператора это линейное подпространство в пространстве функций Cn.

Заметим, что из существования решений дифференциальных уравнений следует, что df(L) = n. Базис ядра, т.е. фундаментальная система

решений однородного дифференциального уравнения строится по корням характеристического полинома дифференциального уравнения

многочлена Â(¸) = a0¸n + : : : + an¡1¸ + an:

Для каждого вещественного корня ¸ кратности r в базис включаются функции xme¸x; m = 0; : : : ; r: А для каждой пары сопряж¼нных комплексных корней ¸ = a § bi кратности r пары функций xm sin(bx)eax è xm cos(bx)eax; m = 0; : : : ; r: Линейная независимость этого набора функций проверяется с помощью определителя Вронского.

Например, уравнение y(3) + y0 = 0 в качестве базиса пространства решений имеет функции f1; sin(x); cos(x)g: Общее решение представ-

ляется в виде C1 + C2 sin(x) + C3 cos(x):

Согласно структуре решения уравнения линейного оператора L(y) = f общее решение получается в виде суммы некоторого частного решения этого уравнения и общего решения однородного уравнения L(y) = 0 :

yO:H: = y0 + yO:O::

Например, общим решением уравнения y(3) + y0 = x будет x22 + C1 +

C2 sin(x) + C3 cos(x):

26

в общем случае предполага-

Упражнения

1. Будет ли независимой система

функций 1; sin2 x; cos2 x ?

2. Проверить независимость систем функций ex; e2x; e3x:

Фундаментальной системой решений какого однородного дифференциального линейного уравнения она будет?

9 Системы линейных дифференциальных уравнений.

Системой линейных дифференциальных уравнений называют систе-
му уравнений
>	y10	= a11y1 + a12y2 + : : : + a1nyn
			: : :
>
<			+ a22y2 + : : : + a2nyn
8 y20 = a21y1
>
:
> yn0 = an1y1			+ an2y2 + : : : + annyn;

которые связывают производные векторной функции Y = (y1; : : : ; yn)T ñ е¼ значениями. Коэффициенты системы aij

ются функциями параметра t.

Можно определить матрицу коэффициентов такой системы A = (aij); i; j = 1; : : : ; n и представить е¼ в матричной форме

Y 0 = AY:

Решением системы называется такая дифференцируемая векторная функция Y = Y (t) от параметра t, которая все уравнения системы пре-

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

27

Рассмотрим семейство решений Y1(t); : : : ; Yn(t) линейного дифферен-

циального уравнения. Вронскианом этого семейства решений называется функция W (t) выраженная определителем

°

°° y11 ° y W (t) = ° 12

°° : : :

° y1n

y21 y22

: : :

y2n

°

: : : yn1 °°

: : : yn2 °°:

: : : : : : °°

: : : ynn °

В силу свойств определителя: если хотя бы для одного значения t выполняется W (t) =6 0; то семейство решений линейно независимо. Оказывается, что тогда W (t) 6= 0 при всех значениях t. Это следует из такого

свойства производной вронскиана.
Напомним, что следом матрицы A называют сумму е¼ диагональных
элементов	n
	trA = Xaij:

i=1

Оказывается, что W 0(t) = tr(A)W (t): Это выводится из свойств функции

следа и определителя. Это уравнение с разделяющимися переменными, определяем общее решение. Оно имеет вид: W (t) = Cetr(A)t:

Из существования решений систем линейных дифференциальных уравнений следует, что множество решений линейное пространство размерности n. А вронскиан позволяет выделять базисы пространства решений.

В качестве примера рассмотрим экологическую проблему об охотниках и жертвах. Обозначим x(t) è y(t) количества существ в некото-

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

½ x0(t) = ax(t) ¡ bx(t)y(t) y0(t) = ¡cy(t) + dx(t)y(t)

28