Solving linear recurrence relations - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Solving linear recurrence relations, слайд №1

Solving linear recurrence relations, слайд №2

Solving linear recurrence relations, слайд №3

Solving linear recurrence relations, слайд №4

Solving linear recurrence relations, слайд №5

Solving linear recurrence relations, слайд №6

Solving linear recurrence relations, слайд №7

Solving linear recurrence relations, слайд №8

Solving linear recurrence relations, слайд №9

Solving linear recurrence relations, слайд №10

Solving linear recurrence relations, слайд №11

Solving linear recurrence relations, слайд №12

Solving linear recurrence relations, слайд №13

Solving linear recurrence relations, слайд №14

Solving linear recurrence relations, слайд №15

Solving linear recurrence relations, слайд №16

Solving linear recurrence relations, слайд №17

Solving linear recurrence relations, слайд №18

Solving linear recurrence relations, слайд №19

Solving linear recurrence relations, слайд №20

Solving linear recurrence relations, слайд №21

Solving linear recurrence relations, слайд №22

Solving linear recurrence relations, слайд №23

Solving linear recurrence relations, слайд №24

Solving linear recurrence relations, слайд №25

Solving linear recurrence relations, слайд №26

Solving linear recurrence relations, слайд №27

Solving linear recurrence relations, слайд №28

Solving linear recurrence relations, слайд №29

Solving linear recurrence relations, слайд №30

Solving linear recurrence relations, слайд №31

Solving linear recurrence relations, слайд №32

Solving linear recurrence relations, слайд №33

Solving linear recurrence relations, слайд №34

Solving linear recurrence relations, слайд №35

Solving linear recurrence relations, слайд №36

Solving linear recurrence relations, слайд №37

Solving linear recurrence relations, слайд №38

Solving linear recurrence relations, слайд №39

Solving linear recurrence relations, слайд №40

Solving linear recurrence relations, слайд №41

Solving linear recurrence relations, слайд №42

Solving linear recurrence relations, слайд №43

Solving linear recurrence relations, слайд №44

Solving linear recurrence relations, слайд №45

Solving linear recurrence relations, слайд №46

Solving linear recurrence relations, слайд №47

Solving linear recurrence relations, слайд №48

Solving linear recurrence relations, слайд №49

Solving linear recurrence relations, слайд №50

Solving linear recurrence relations, слайд №51

Solving linear recurrence relations, слайд №52

Solving linear recurrence relations, слайд №53

Solving linear recurrence relations, слайд №54

Solving linear recurrence relations, слайд №55

Solving linear recurrence relations, слайд №56

Solving linear recurrence relations, слайд №57

Solving linear recurrence relations, слайд №58

Solving linear recurrence relations, слайд №59

Solving linear recurrence relations, слайд №60

Solving linear recurrence relations, слайд №61

Solving linear recurrence relations, слайд №62

Solving linear recurrence relations, слайд №63

Solving linear recurrence relations, слайд №64

Solving linear recurrence relations, слайд №65

Solving linear recurrence relations, слайд №66

Solving linear recurrence relations, слайд №67

Solving linear recurrence relations, слайд №68

Solving linear recurrence relations, слайд №69

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Solving linear recurrence relations. Доклад-сообщение содержит 69 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Solving linear recurrence relations Irina Prosvirnina Linear homogeneous recurrence relations with constant coefficients Solving linear homogeneous recurrence relations with constant coefficients Solving linear homogeneous recurrence relations with constant coefficients of degree two and of degree three Linear nonhomogeneous recurrence relations with constant coefficients Generating functions Using generating functions to solve recurrence relations

Слайд 2

Описание слайда:

Linear homogeneous recurrence relations with constant coefficients Definition 1 A linear homogeneous recurrence relation of degree with constant coefficients is a recurrence relation of the form where are real numbers, and .

Слайд 3

Описание слайда:

Linear homogeneous recurrence relations with constant coefficients A sequence satisfying the recurrence relation in the definition is uniquely determined by this recurrence relation and the initial conditions:

Слайд 4

Описание слайда:

Linear homogeneous recurrence relations with constant coefficients Example 1 The recurrence relation is a linear homogeneous recurrence relation of degree one.

Слайд 5

Описание слайда:

Linear homogeneous recurrence relations with constant coefficients Example 2 The recurrence relation is a linear homogeneous recurrence relation of degree two. The sequence of Fibonacci numbers satisfies this recurrence relation and also satisfies the initial conditions .

Слайд 6

Описание слайда:

Linear homogeneous recurrence relations with constant coefficients Example 3 The recurrence relation is a linear homogeneous recurrence relation of degree five.

Слайд 7

Описание слайда:

Linear homogeneous recurrence relations with constant coefficients Example 4 The recurrence relation is not linear.

Слайд 8

Описание слайда:

Linear homogeneous recurrence relations with constant coefficients Example 5 The recurrence relation is not homogeneous.

Слайд 9

Описание слайда:

Linear homogeneous recurrence relations with constant coefficients Example 6 The recurrence relation does not have constant coefficients.

Слайд 10

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients The basic approach for solving linear homogeneous recurrence relations is to look for solutions of the form where is a constant.

Слайд 11

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients Note that is a solution of the recurrence relation if and only if

Слайд 12

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients When both sides of this equation are divided by , we obtain the equation When the right-hand side is subtracted from the left we obtain the equation

Слайд 13

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients Consequently, the sequence with is a solution of linear homogeneous recurrence relations with constant coefficients is a solution if and only if is a solution of this last equation We call this the characteristic equation of the recurrence relation . The solutions of this equation are called the characteristic roots of the recurrence relation .

Слайд 14

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients As we will see, these characteristic roots can be used to give an explicit formula for all the solutions of the recurrence relation.

Слайд 15

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree two Theorem 1 Let and be real numbers. Suppose that has two distinct roots and . Then the sequence is a solution of the recurrence relation if and only if for , where and are constants.

Слайд 16

Описание слайда:

Proof of theorem 1 ? If and are roots of , and are constants then the sequence with is a solution of the recurrence relation . 

Слайд 17

Описание слайда:

Proof of theorem 1 ? If the sequence is a solution of , then for , for some constants and , where and are distinct roots of . Let is a solution of the recurrence relation and the initial conditions hold.

Слайд 18

Описание слайда:

Proof of theorem 1 ? If the sequence is a solution of , then for , for some constants and , where and are distinct roots of . It will be shown that there are constants and such that the sequence with satisfies these same initial conditions

Слайд 19

Описание слайда:

Proof of theorem 1 ? If the sequence is a solution of , then for , for some constants and , where and are distinct roots of . This requires that We can solve these two equations for and :

Слайд 20

Описание слайда:

Proof of theorem 1 ? If the sequence is a solution of , then for , for some constants and , where and are distinct roots of . Hence, with these values for the sequence with , satisfies the two initial conditions

Слайд 21

Описание слайда:

Proof of theorem 1 ? If the sequence is a solution of , then for , for some constants and , where and are distinct roots of . We know that and are both solutions of the recurrence relation and both satisfy the initial conditions when and . Because there is a unique solution of a linear homogeneous recurrence relation of degree two with two initial conditions, it follows that the two solutions are the same, that is, for .

Слайд 22

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree two Example 7 What is the solution of the recurrence relation with and ? Solution The characteristic equation of the recurrence relation is Its roots are and . By theorem 1, .

Слайд 23

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree two Example 7 What is the solution of the recurrence relation with and ? Solution 

Слайд 24

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree two Example 8 (Fibonacci numbers) What is the solution of the recurrence relation with and ? Solution The characteristic equation of the recurrence relation is Its roots are and . By theorem 1,

Слайд 25

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree two Example 8 (Fibonacci numbers) What is the solution of the recurrence relation with and ? Solution 

Слайд 26

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree two Theorem 2 Let and be real numbers with . Suppose that has only one root . A sequence is a solution of the recurrence relation if and only if for , where and are constants.

Слайд 27

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree two Example 9 What is the solution of the recurrence relation with and ? Solution The characteristic equation of the recurrence relation is Its root is . By theorem 2,

Слайд 28

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree two Example 9 What is the solution of the recurrence relation with and ? Solution 

Слайд 29

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree three Theorem 3 Let be real numbers. Suppose that the characteristic equation has distinct roots . A sequence is a solution of the recurrence relation if and only if for , where are constants.

Слайд 30

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree three Example 10 What is the solution of the recurrence relation with Solution The characteristic equation of the recurrence relation is Its roots are . By theorem 3,

Слайд 31

Описание слайда:

Solving linear homogeneous recurrence relations with constant coefficients of degree three Example 10 What is the solution of the recurrence relation with Solution .

Слайд 32

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Definition 2 A linear nonhomogeneous recurrence relation with constant coefficients is a recurrence relation of the form where are real numbers, is a function not identically zero depending only on . The recurrence relation is called the associated homogeneous recurrence relation. It plays an important role in the solution of the nonhomogeneous recurrence relation.

Слайд 33

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 11 The recurrence relation is a linear nonhomogeneous recurrence relation with constant coefficients. The associated linear homogeneous recurrence relation is .

Слайд 34

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 12 The recurrence relation is a linear nonhomogeneous recurrence relation with constant coefficients. The associated linear homogeneous recurrence relation is .

Слайд 35

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 13 The recurrence relation is a linear nonhomogeneous recurrence relation with constant coefficients. The associated linear homogeneous recurrence relation is .

Слайд 36

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 14 The recurrence relation is a linear nonhomogeneous recurrence relation with constant coefficients. The associated linear homogeneous recurrence relation is .

Слайд 37

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Theorem 4 If is a particular solution of the nonhomogeneous linear recurrence relation with constant coefficients , then every solution is of the form , where is a solution of the associated homogeneous recurrence relation

Слайд 38

Описание слайда:

Proof of theorem 4 Because is a particular solution of the nonhomogeneous recurrence relation , we know that

Слайд 39

Описание слайда:

Proof of theorem 4 Now suppose that is a second solution of the nonhomogeneous recurrence relation , so that .

Слайд 40

Описание слайда:

Proof of theorem 4 So, , . Subtracting the first of these two equations from the second shows that It follows that is a solution of the associated homogeneous linear recurrence relation,say, Consequently,

Слайд 41

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 15 Find all solutions of the recurrence relation Solution This is a linear nonhomogeneous recurrence relation. The solutions of its associated homogeneous recurrence relation are

Слайд 42

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 15 Find all solutions of the recurrence relation Solution We now find a particular solution. Suppose that where and are constants, such a solution.

Слайд 43

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 15 Find all solutions of the recurrence relation Solution

Слайд 44

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 16 Find all solutions of the recurrence relation Solution This is a linear nonhomogeneous recurrence relation. The solutions of its associated homogeneous recurrence relation are .

Слайд 45

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 16 Find all solutions of the recurrence relation Solution We now find a particular solution. Suppose that is a

Слайд 46

Описание слайда:

Linear nonhomogeneous recurrence relations with constant coefficients Example 16 Find all solutions of the recurrence relation Solution

Слайд 47

Описание слайда:

Generating functions Definition 3 The generating function for the sequence of real numbers is the infinite series

Слайд 48

Описание слайда:

Generating functions Example 17 The generating function for the sequence is

Слайд 49

Описание слайда:

Generating functions Example 18 The generating function for the sequence is

Слайд 50

Описание слайда:

Generating functions Example 19 The generating function for the sequence is

Слайд 51

Описание слайда:

Generating functions We can define generating functions for finite sequences of real numbers by extending a finite sequence into an infinite sequence by setting and so on. The generating function of this infinite sequence is a polynomial of degree because no terms of the form with occur, that is,

Слайд 52

Описание слайда:

Generating functions Example 20 The generating function of is We have when . Consequently, is the generating function of the sequence

Слайд 53

Описание слайда:

Generating functions Example 21 Let be a positive integer. The generating function for the sequence with is The binomial theorem shows that

Слайд 54

Описание слайда:

Generating functions Example 22 The function is the generating function of the sequence because for

Слайд 55

Описание слайда:

Generating functions Example 23 The function is the generating function of the sequence because for

Слайд 56

Описание слайда:

Using generating functions to solve recurrence relations Example 24 Solve the recurrence relation for and initial condition

Слайд 57

Описание слайда:

Solution of example 24 Let be the generating function for the sequence , that is, First note that

Слайд 58

Описание слайда:

Solution of example 24

Слайд 59

Описание слайда:

Solution of example 24

Слайд 60

Описание слайда:

Solution of example 24

Слайд 61

Описание слайда:

Using generating functions to solve recurrence relations Example 25 Solve the recurrence relation for and initial condition Suppose that a valid codeword is an -digit number in decimal notation containing an even number of 0s. Let denote the number of valid codewords of length . Proof that satisfies the recurrence relation and the initial condition Use generating functions to find an explicit formula for .

Слайд 62

Описание слайда:

Solution of example 25 To make our work with generating functions simpler, we extend this sequence by setting and use the recurrence relation, we have which is consistent with our original initial condition. (It also makes sense because there is one code word of length – the empty string.)