Лабораторный Практикум по Дискрмат2

Вариант 1.

а) б)

в)

Вариант 2.

а) б)

в)

Вариант 3.

а)

б)

в)

Вариант 4.

а)

б)

в)

Вариант 5.

а)

б)

в)

Вариант 6.

а)

б)

в)

Вариант 7.

а)

б)

в)

Вариант 8.

а) б) в)

Задания для самостоятельной работы

(a b)

a, a c| (a b)

c ;

|

(a

b)

(a

b) ;

| (a b )

((c

b)

(a c )) .

(a a)

b, a (b c) | a c ;

|

b

((b

a)

a ) ;

| (a b)

((a (c b ))

(a c)) .

a (a b), b c| a c ;

|

a

((a

b )

b) ;

| (a b)

((a (c b ))

(a c )) .

a, b c | (a b)

c ;

|

a

a ;

| (b

a)

((b c)

(a

c)) .

(a a)

a, b c | (a b)

c ;

|

a

(b

a) ;

|

(b

a)

(a

b) .

a (b c), (b c)

b | a c ;

|

(a

b)

(a

b ) ;

|

(b

a )

(a

b) .

(b c)

a, a b | (b c)

c ;

|

a

((a

b )

b) ;

| (b

a )

((b

c)

(a

c)) .

(a a)

a, a b | (b c)

c ;

|

(b

a )

(b

a) ;

| (b

a )

((b

c)

(a

c)) .

71

Вариант 9.

а) a b, b (b c) | a c ;

б) | (a b)

(a b) ;

в) | (a

(b

c))

((b

a )

(a

c)) .

Вариант 10.

а) a (a b), b (a c) | a c ;

б) | b ((b a )

a) ;

в) | (a (c

b ))

((b

a )

(a

c)) .

Вариант 11.

а) a (a a), b (b c) | (a b)

c ;

б) | a ((a b)

b) ;

в) | (b

a )

((c

b )

(a

c)) .

Вариант 12.

а) a, b (b c) | (a b) c ;

б) | a ((a

b)

b ) ;

в) | (c

b )

((b

a )

(a

c)) .

Вариант 13.

а) (a a)

(a b), b c | a c ;

б) | (a (b c))

((a b )

(a c)) ;

в) | (c

b )

((a

b)

(a c)) .

Вариант 14.

а) a (a b), b (b c) | a c ;

б) | (a b)

((a (b c ))

(a

c)) ;

в) | (c

b)

((a b )

(a c )) .

Вариант 15.

а) a b, b ((a a)

c) | a c ;

б) | (a (b c))

((b

(a c )) ;

в) | (a (c

b ))

((a b)

(a

c)) .

72

Вариант 16.

а) a ((a a) b), b c | a c ;

б) | (a (b

c ))

((a

(b c)) ;

в) | (a (c b ))

((a

b)

(a c )) .

Вариант 17.

а) a (a b),a (b c) | a c ;

б) | (a (b c ))

((a b)

(a

c)) ;

в) | (b c )

((b

a)

(a

c)) .

Вариант 18.

а) (a a)

(a b), a (b c) | a c ;

б) | a ((a

b )

b) ;

в) | a

((b

a)

b) .

Вариант 19.

а) a b, (a a)

(b c) | a c ;

б) | (a (b

c ))

((b (a c)) ;

в) | a

((b

a )

b) .

Вариант 20.

а) a (a ( a b)) | a b ;

б) | (a

(b c))

((a

b )

(a

c)) ;

в) | (b

c)

((b

a )

(a

c)) .

Вариант 21.

а) b, a (a (b c)) | a c ;

б) | (a

b )

(a b) ;

в) | (b

c)

((b a )

(a c )) .

Вариант 22.

а) a

(b

(a

c)),( b

(a

c))

b | a c ;

б) | (a b )

(a

b) ;

в) | (b

a )

((a

(b c))

(a

c)) .

73

Вариант 23.

а) a b, a (a (b c)) | a c ;

б)

| (a b)

((b

c )

(a c)) ;

в) | a ((b

a )

b ) .

Вариант 24.

а)

a

(a (b

c)),( a

(b c)) b | a c ;

б)

| (b

a )

((b

a)

b ) ;

в) | a ((b a )

b ) .

Вариант 25.

а) b c, a (a (a b)) | a c ;

б) | (b			a)	((b				a ) b ) ;
в) | (b			a)	(a b ) .

Лабораторная работа № 9

ОБЩИЕ И ЧАСТНЫЕ РЕШЕНИЯ РЕКУРРЕННЫХ СООТНОШЕНИЙ. РЕШЕНИЕ СИСТЕМ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ

Цель работы

Найти общее и частное решение рекуррентных соотношений. Найти общее и частное решение системы рекуррентных соотношений.

Краткая теория

Говорят, что последовательность {an} подчиняется линейному рекуррентному соотношению порядка k, если выполняется соотношение вида

an+k + p1an+k-1 + … + pkak = 0	(1)
где pi , i = 1, … , k некоторые константы. Многочлен
P(x) = xk + p1xk-1 + … + pk	(2)

называется характеристическим для рекуррентного соотношения (1). Возникает вопрос, можно ли решить рекуррентное соотношение (1),

то есть найти явное выражение для an, которое является решением

74

уравнения (1)? Последовательность	{an}	полностью определяется
заданием первых ее k членов a1, a2,	… , ak.	Если	является корнем

характеристического многочлена (2), то последовательность {cλk}, где с – произвольная константа, удовлетворяет соотношению (1). Если λ1, λ2, … , λs являются корнями характеристического многочлена (2), соответственно,

		s
кратности r1, r2, … ,	rs, где	ri	k , то общее решение рекуррентного
		i 1
соотношения (2) будет иметь следующий вид:
	s
an	(ci1	ci 2 (n	1) ... cir (n 1)r 1 ) in 1 ,
	i 1

где cij – произвольные константы, i = 1, … , s; j = 1, … , ri . Если k первых

членов последовательности {an} заданы, то коэффициенты cij для соответствующей последовательности находятся из системы k линейных

алгебраических уравнений относительно неизвестных cij .

Порядок выполнения работы

1.Найти общее и частное решение рекуррентных соотношений в случае отсутствия кратных корней.

2.Найти общее и частное решение рекуррентных соотношений для случая кратных корней.

3.Найти общее и частное решение системы рекуррентных соотношений.

Образец выполнения заданий

Найти общее решение рекуррентных соотношений а) и б); найти частное решение рекуррентных соотношений а) и б), если первые члены последовательности суть числа 0, 1, 2,…, k –1; найти общее и частное решение системы рекуррентных соотношений в):

а) an 2	4an 1	3an	0 ;
б) an 4	8an 3	18an 2	27an 0 ;

an 1	3an		bn
в) b	2a	n	b .
n 1			n

75

Решение. а) Последовательность {an} подчиняется линейному рекуррентному соотношению порядка 2. Характеристическим многочленом этого рекуррентного соотношения является многочлен P(x) = x2 – 4x + 3. Корнями многочлена P(x) являются числа 1 и 3. Следовательно, общим решением данного рекуррентного соотношения будет выражение:

a	c 1n 1	c	2	3n 1	c c	2	3n 1 .
	n 1				1

Найдем частное решение при условии, что последовательность начинается

членами 0 и 1. Для нахождения коэффициентов c1, c2 составим систему линейных уравнений:

a1		0	c1	c2		.
a	2	1	c	3c	2
			1

Решая эту систему относительно произвольных коэффициентов c1, c2

получим значения c1 = –1/2, c2 =1/2. Таким образом, частным решением будет

	an	1		1	3n 1 .
		2	2

б) Последовательность {an} подчиняется линейному рекуррентному соотношению порядка 4. Характеристическим многочленом этого

рекуррентного соотношения является многочлен P(x) = x4 – 8x3 + 18x2 – 27. Корнями многочлена P(x) являются числа 3, 3, 3 и –1. Следовательно, общим решением данного рекуррентного соотношения будет выражение:

a	n	[c c		2	(n 1) c (n 1)2 ] 3n 1	c	4	( 1)n 1 .
		1			3
Найдем частное решение при начальных условиях a1 = 1, a2 = 3, a3 =
27, a4 =		308.	Составляя систему из четырех			линейных уравнений,

соответствующих этим условиям, и решая эту систему, получим c1 = –1,

c2= 1/9, c3 = 8/9, c4 = 2. Подставляя полученные значения в общее решение, найдем следующее частное решение:

an [ 1 1/ 9 (n 1) 8 / 9 (n 1)2 ] 3n 1

2 ( 1)n 1 .

76

в)Найдем общее решение данной системы рекуррентных соотношений. Для этого, из первого равенства системы выразим bi через ai:

bn 3an an 1 или bn 1 3an 1 an 2

и подставим во второе равенство системы:

3an 1 an 2 2an (3an an 1 )

an an 1 .

В результате, получим следующее рекуррентное соотношение второго порядка:

an 2 2an 1 an 0.

Характеристическими корнями этого рекуррентного соотношения

являются числа 1 2 и 1 2 Тогда общее решение этого рекуррентного соотношения будет иметь следующий вид:

a	n	c (1	2)n 1		c	2	(1	2)n 1 .
		1

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

для an+1:

an 1

c1 (1

2)n

c2 (1

2)n .

Подставляя эти выражения в выражение для bn , получим:

bn

3an

an 1

3[c (1

2)n 1

c (1

2)n 1 ]

c (1

2)n

c (1

2)n .

1

2

1

2

Таким образом, общим решением заданной системы является

a

n

c (1

2)n 1

c

2

(1

2)n 1

1

b

c (2

2)(1

2)n 1

c

2

(2

2)(1

2)n 1 .

n

1

Найдем частное решение

системы. Пусть а1

= 1, b1

= –1,

тогда для

нахождения коэффициентов c1, c2 получим следующую систему линейных уравнений:

77

	a1	c1		c2 1			.
b	c (2		2)	c	(2	2)
1	1			2

Решая эту систему, получим значения констант c1, c2:

											c1				3								2		, c2			3						2				.
															2						2							2	2
	Следовательно, частным решением данной системы рекуррентных
соотношений будет:
								3								2												3				2					(1
			a		n													(1				2)n 1																	2)n 1
								2			2																	2	2
	3				2																							3			2													.
b									(2		2)(1											2)n 1														(2			2)(1				2)n 1
n	2		2																									2	2

Вопросы для самопроверки

1.Определите понятие рекуррентного соотношения и его порядок.

2.Что называется характеристическим многочленом рекуррентного соотношения?

3.Как влияет кратность корней характеристического уравнения на общее решение рекуррентного соотношения?

Литература: [2], часть 3, с. 60–67; [7], гл. 10, стр. 351–399.

Задания для самостоятельной работы

Вариант 1.
а) an 3	2an 2	an 1 2an	0 ;
б) an 4	10an 3	24an 2	25an 0 ;

an 1	an		bn
в) b	3a	n	2b .
n 1			n
Вариант 2.
а) an 3	3an 2		an 1 3an 0 ;

78

б) an 4 10an 3 36an 2 56an 1 32an 0 ;

	an 1 an					bn
в)	b		2a	n		2b .
	n 1					n
Вариант 3.
а) an 3		an 2			2an 1		2an 0 ;
б) an 4		6an 3			13an 2		12an 1 4an 0 ;
в)	an 1	an			bn	.
	b	a	n		b
	n 1				n

Вариант 4.

а) б)

в)

Вариант 5.

а) б)

в)

Вариант 6.

а) б)

в)

Вариант 7.

а) б)

в)

Вариант 8.

а) б)

an 3 an 4

an 1 bn 1

an 3 an 4

an 1 bn 1

an 3 an 4

an 1 bn 1

an 3 an 4

an 1 bn 1

an 3 an 4

3an 2

7an 3

2an an

an 2

2an 3

2an an

2an 2

2an 2

an an

an 2

8an 2

an an

2an 2

4an 3

4an 1 12an 0 ;

18an 2 20an 1 8an 0 ;

bn bn .

3an 1 3an 0 ;

2an 1 an 0 ;

bn bn .

3an 1	6an 0;
an	0 ;

bn bn .

2an 1 2an 0 ;

16an 0 ;

bn
b .
n
2an 1	4an	0 ;
6an 2	4an 1	an 0;

79

в)

Вариант 9.

а) б)

в)

Вариант 10. а) б)

в)

Вариант 11. а) б)

в)

Вариант 12. а) б)

в)

Вариант 13. а) б)

в)

Вариант 14. а) б)

an 1

an

bn

b

a

n

2b .

n 1

n

an 3

3an 2

2an 1

6an

0;

an 4

6an 2

8an 1

6an

0;

an 1

an

bn

b

a

n

2b .

n 1

n

an 3

2an 2

3an 1

6an

0;

an 4

2an 3

3an 2

4an 1

4an

0 ;

an 1

an

bn

.

b

a

n

2b

n 1

n

an 3

2an 2

3an 1

3an

0;

an 4

2an 3

3an 2

4an 1

4an

0 ;

an 1

2an bn

.

b

a

n

b

n 1

n

an 3

2an 2

an 1

2an

0 ;

an 4

an 3

3an 2

5an 1

2an

0;

an 1

2an

bn

b

2a

n

3b .

n 1

n

an 3

3an 2

an 1

3an

0 ;

an 4

4an 3

16an 1

16an

0 ;

an 1

2an

bn

b

2a

n

2b .

n 1

n

an 3

an 2

2an 1

2an

0 ;

an 4

9an 3

30an 2

44an 1

24an 0 ;

80