recurrent methods. General and particular solutions of recurrence relations Calculate the determinants of the order n by the method of recurrence relations

With a large amount of observation data X finite methods for solving the likelihood equation lead to significant computational difficulties associated with the need to remember a large number of initial data and intermediate results of calculations. In this regard, recurrent methods are of particular interest, in which the maximum likelihood estimate is calculated in steps with gradually increasing accuracy, each step is associated with obtaining new observational data, and the recurrent procedure is constructed in such a way as to store in memory as little data as possible from the previous ones. steps. An additional and very significant advantage from a practical point of view of recursive methods is the readiness to issue a result at any intermediate step.

This makes it expedient to use recurrent methods even in cases where it is possible to obtain an exact solution of the maximum likelihood equation by a finite method, and makes them even more valuable when it is impossible to find an exact analytical expression for estimating the maximum likelihood.

Let the set of observation data be a sequence for the description of which we introduce the vector . (As always, each of its components, in turn, can be a vector, a segment of a random process, etc.). Let be the likelihood function, and

its logarithm. The latter can always be represented as

The log-likelihood of the observational data set without the last value, and

The logarithm of the conditional probability density of the value for given values ​​of and .

Representation (7.5.16) for the logarithm of the likelihood function is the basis for obtaining a recurrent procedure for calculating the maximum likelihood estimate. Let's consider the regular case. In this case, the maximum likelihood estimate can be found as a solution to the equation

which differs from (7.1.6) only by introducing the index p y logarithm of the likelihood function.

Let's designate the solution of this equation through thus emphasizing that this estimate was obtained from the totality of observational data . Similarly, let us denote by the solution of the equation the maximum likelihood estimate obtained from the dataset .

Equation (7.5.19) can be rewritten taking into account (7.5.16) in the following form:

Let us expand the left side of (7.5.20) into a Taylor series in the vicinity of the point . Wherein

(7.5.22)

The gradient vector of the function at the point ; term vanishes due to the fact that , is the solution of the likelihood equation for the previous (P - 1)th step:

The symmetric matrix of the second derivatives of the logarithm of the likelihood function at the point , taken with the opposite sign, the unwritten terms of the expansion have a quadratic and higher order of smallness with respect to the difference . Neglecting these latter, we obtain the following approximate solution of the maximum likelihood equation:

where is the inverse matrix.

This solution is presented in the form of a recurrence relation that determines the next value of the estimate through the estimate at the previous step and the correction , dependent on available observational data directly and through previous evaluation. The correction is formed as the product of the gradient of the logarithm of the conditional probability density of the newly obtained value X n at the point equal to the previous estimate, onto the weight matrix . The latter is determined by expression (7.5.23) and also depends on the estimate at the previous step, and its dependence on new observational data is entirely determined by the form of the logarithm of the conditional probability density .

The form of relation (7.5.24) is very similar to (7.5.8), which implements an iterative way of calculating the maximum likelihood estimate by Newton's method. However, in fact, they differ significantly from each other. In (7.5.8), the correction to the previous value of the estimate is determined by the magnitude of the gradient of the logarithm of the entire likelihood function, which always depends on all available observational data , which requires remembering the entire population. In accordance with (7.5.24), the correction to is determined by the magnitude of the gradient , which, due to the properties of the conditional probability density, actually depends only on those values ​​() that are in a strong statistical relationship with X n. This difference is a consequence of the special choice of the previous approximation as the maximum likelihood estimate found from the set of observational data reduced by one value , and is especially pronounced for independent values ​​of (). In this last case

due to which it depends only on and X n , and the gradient is only from the previous value of the estimate and the newly obtained P- Surveillance data step. Therefore, for independent values, to form a vector, it is not necessary to store any other information from the previous step, except for the value of the estimate .

Similarly, in the case of a Markov sequence of observational data, that is, when

the vector depends only on , current and one previous value . In this case, for the calculation, it is required to remember from the previous step, in addition to the value , only the value , but not the entire set of observation data, as in the iterative procedure. In general, the calculation may require storing a larger number of previous values ​​(), however, due to the need to take into account only those values ​​\u200b\u200bthat are statistically dependent on , this number is almost always less than the total volume of the observation data set. So, if a vector describes a time sequence, then the number of memorized members of this sequence is determined by the time of its correlation, and their relative share decreases inversely proportionally n, as in the case of independent values ​​.

Let us now consider the structure of the weight matrix , included in the recurrent relation (7.5.24). According to the definition (7.5.23), due to the presence of the term, it generally depends on all values ​​even for independent values ​​of , which deprives the recurrence relation (7.5.24) of the advantages associated with a possible reduction in the amount of data stored from the previous step. There are several ways to approximate the matrix , which remedy this shortcoming.

The first of them is based on a more consistent use of the basic assumption of a small difference between two successive values ​​of the estimate and , which is the basis for obtaining the recurrence relation (7.5.24). This allows us to obtain a similar recurrence relation for the weight matrix . Indeed, using the smallness from (7.5.23), we have

By introducing the notation

from (7.5.24) and (7.5.25) we obtain a system of recurrent relations for the vector and the weight matrix

This system, together with the initial values, completely determines the value of the estimate at any step, requiring at each of them to calculate only the gradient and the matrix of second derivatives of the logarithm of the conditional probability density for the current observed value . The initial values ​​are chosen taking into account the available a priori data on the possible values ​​and the range of change of the parameters , and in the absence of these data, they are taken to be zero (,).

For independent values, the system of recurrence relations (7.5.27) obviously describes a multidimensional (dimensions ) Markov random process, the component of which converges to the true value of the parameter , and the component converges to the Fisher information matrix (7.3.8), where is the true value of the estimated parameter , and increases indefinitely as P. System (7.5.27) has similar convergence properties under more general conditions if the sequence is ergodic.

The second of the mentioned methods is based on replacing the matrix of second derivatives of the logarithm of the likelihood function with its mathematical expectation - the Fisher information matrix, which, taking into account (7.5.16), can be written as:

where similarly to (7.5.26)

Replacing the matrix in (7.5.24) with the matrix , we obtain the recurrent relation

for the approximate calculation of the maximum likelihood estimates proposed by Sakrison (in the original for independent identically distributed , when and . This recurrence relation is simpler than the system (7.5.27), since the optimal weight matrix is ​​replaced by its mathematical expectation, and available observational data are not required to find it, except for those that are concentrated in the value of the estimate At the same time, it is obvious that such a replacement means the need to fulfill an additional requirement compared to (7.5.27) that the matrix of second derivatives be close to its mathematical expectation.

If the probability density distribution and the matrix change from step to step, finding each step directly may require too many calculations. At the same time, due to an additional decrease in the accuracy of the results, which is determined by the inequality zero of small differences , one can proceed to recurrent calculation of the approximate value of the matrix . Returning to the previous notation for this approximate value, we obtain another system of recurrence relations

Mathematical expectation of the matrix (Fisher information matrix for one observation), taken at the point . This system differs from (7.5.27) in that the second of the recurrence relations (7.5.31) does not directly involve observational data.

Any of the systems of recurrence relations considered above is perfectly exact if the function depends quadratically on , and additionally the matrix of second derivatives does not depend on . In fact, this corresponds to the case of independent normally distributed (not necessarily equally) values ​​with an unknown mathematical expectation , which is the estimated parameter.

The system of recurrence relations (7.5.24) gives the exact solution of the maximum likelihood equation under much broader conditions with the only requirement that the function depends quadratically on . In this case, the dependence on is arbitrary, which corresponds to a wide class of population probability distributions with both independent and dependent values.

Along with the considered general methods, there are a number of methods for choosing a matrix of weight coefficients in the recurrence relation (7.5.24), adapted to certain specific restrictions. The simplest of these is the choice in the form of a diagonal matrix, so that , ( I is the identity matrix), where is a decreasing sequence of numerical coefficients, chosen regardless of the properties of the likelihood function in the same way as in the Robins-Monroe stochastic approximation procedure, which will be discussed in the following chapters.

It should be noted that any iterative or recurrent procedures for finding maximum likelihood estimates are generally approximate. Therefore, generally speaking, for the estimates obtained as a result of applying these procedures, consistency, asymptotic efficiency, and asymptotic normality must be proved anew. For iterative procedures, the necessary properties of estimates are guaranteed by the fact that, in principle, such procedures, with an appropriate number of iterations, give a solution to the likelihood equation with any predetermined accuracy. For recurrent procedures like (7.5.27), (7.5.30), (7.5.31) and others, there are special proofs. At the same time, in addition to the requirement of regularity, some additional requirements are imposed:

On the behavior of the function (7.2.2) for different values ​​of ||, in order to achieve, using the recurrent procedure, the global maximum of this function at the point corresponding to the true value of the parameter;

By an order of growth of the second moments of the derivatives of the logarithm of the likelihood function for large modulo values ​​of . These requirements are a consequence of more general conditions for the convergence to a point of all or part of the components of a Markov random process, to which one or another recurrent procedure leads.

In conclusion, we also note that in the case when there is an exact solution of the maximum likelihood equation, it can almost always be represented in a recursive form. We give two simple heterogeneous examples. Thus, an elementary estimate of the unknown mathematical expectation of a normal random variable in the aggregate n its sample values ​​in the form of an arithmetic mean

is the maximum likelihood estimate and can be represented in the recursive form:

which is the simplest special case (7.5.30) for

Another example is the irregular maximum likelihood estimate for the parameter - the width of the rectangular distribution - from (7.4.2), which can also be determined by the recurrence relation

with initial condition . This recurrence relation is of a different type: its right-hand side cannot be represented as the sum of the previous estimate and a small correction, which is a consequence of the irregularity of this example; however, it has all the advantages of the recursive approach: it requires only one number to be remembered from the previous step - the estimate - and it drastically reduces the enumeration to one comparison instead of comparing all values.

The given examples illustrate the advantages of recursive methods even in the case when the maximum likelihood equation admits an exact solution, because the simplicity of the analytical representation of the result is not identical to the computational simplicity of obtaining it.

7.5.3. Transition to continuous time. Differential Equations for Maximum Likelihood Estimates

Let us now consider a special case where the available observational data X are not described by a set of sample points , but represent a segment of the implementation of some process , depending on the parameters , given on the interval , moreover, the length of this interval can increase during observation (time t is variable).

For a statistical description of the observational data, in this case, the likelihood ratio functional is introduced, which is the limit at , max of the ratio of the probability density of the set of values ​​at an arbitrarily given value to a similar probability density at some fixed value , and in some cases, when it admits the representation , where is a random process , independent of , to the probability density of the set of values ​​provided that . The use of the likelihood ratio functional makes it possible to eliminate the formal difficulties in determining the probability density that arise in the transition to continuous time.

The logarithm of the likelihood ratio functional can be represented as

where is some process functional on the interval . In some cases, the functional degenerates into a function that depends only on the value of . So if

where is a known function of time and parameters , and is a delta-correlated random process ("white" noise) with spectral density N o , then, choosing as the denominator the likelihood ratio of the probability distribution X at , we will have

Let - the maximum likelihood estimate of the parameter , built on the implementation of the process on the interval , that is, the solution of the maximum likelihood equation

Differentiating the left side of this equation with respect to time, we obtain

Introducing the notation

and solving equation (7.5.42) with respect to , we obtain the differential equation for the maximum likelihood estimate

The matrix , in turn, according to (7.5.37) is determined by the differential equation

Just as in the discrete case, the matrix in (7.5.45), (7.5.47) can be replaced by its mathematical expectation - the Fisher information matrix with the value , and the differential equation (7.5.46) for the weight matrix - by the equation

where, similarly to the discrete case

Mathematical expectation of the matrix of second derivatives.

The set of differential equations (7.5.45), (7.5.46) or (7.5.45), (7.5.48), together with the initial conditions, regarding the choice of which everything said for the discrete case remains valid, completely determines the maximum likelihood estimate for any point in time. This set can be simulated by means of appropriate, generally speaking, non-linear analog devices or, with suitable time sampling, solved by a computer. In conclusion, we note one of the modifications of these equations, which makes it possible to avoid the need to invert the matrix .

Introducing the notation

, where I

and differentiating with respect to time the relation , where I is the identity matrix, we obtain with the help of (7.5.46) a differential equation that directly determines the matrix :

(and similarly when replaced by ), which together with equation (7.5.45)

determines the score , without requiring matrix inversion. In this case, there is a transition from the simplest linear differential equation (7.5.46) to a non-linear with respect to differential equation (7.5.51) of the Riccati type.

Combinatorial calculations on finite sets

Introduction to combinatorics

The subject of the theory of combinatorial algorithms, often called combinatorial computations, is computations on discrete mathematical structures. In this theory, much attention is paid to the algorithmic approach to solving problems of discrete mathematics, optimization of enumeration of options, and reduction in the number of considered solutions.

The field of combinatorial algorithms includes tasks that require counting (estimating) the number of elements in a finite set or listing these elements in a special order (Appendix B). In this case, the procedure for selecting elements with return and its variants are widely used.

There are two types of counting problems. In the simple case, a specific set is given and it is required determine the exact number of elements in him. In the general case, there is a family of sets defined by some parameter, and the cardinality of the set is defined as a function of the parameter. At the same time, it is often a sufficient estimate of the order of the function and sometimes you only need assessment of its growth rate. For example, if the power of the set under consideration grows exponentially in some parameter, then this may be enough to abandon the proposed approach to studying the problem without going into various details. For this more general type of problem, the procedures of asymptotic expansions, recurrence relations, and generating functions are applied.

Asymptotics

An asymptote is a special line (most often a straight line), which is the limit for the curve under consideration.

Asymptotics is the art of estimating and comparing the growth rates of functions. They say that at X®¥ function "behaves like X", or "increases at the same rate as X", and at X®0 "behaves like 1/ x". They say that "log x at x®0 and any e>0 behaves like x e , and what n®¥ grows no faster than n log n". Such imprecise but intuitively clear statements are useful in comparing functions in the same way as the relations<, £ и = при сравнивании чисел.

Let us define three main asymptotic relations.

Definition 1. Function f(x) is equivalent to g(x) at X® x0, if and only if =1.

In this case, the function is said to be f(x) is asymptotically equal to the function g(x) or what f(x) grows at the same rate as g(x).

Definition 2. f(x)=o( g(x)) at x® x0, if and only if =0.

They say that at x® x 0 f(x) grows more slowly than g(x), or what f(x) "there is o-small" from g(x).

Definition 3 . f(x)=O( g(x)) at x® x0, if and only if there exists a constant C such that sup =C.

In this case, they say that f(x) grows no faster than g(x), or whatever x® x 0 f(x) "there is a big O" from g(x).

Ratio f(x)=g(x)+o(h(x)) at x®¥ means that f(x)-g(x)=o(h(x)). Similarly f(x)=g(x)+ABOUT(h(x)) means that f(x)-g(x)=O(h(x)).

The expressions O( ) and o( ) can also be used in inequalities. For example, inequality x+o(x)£2 x at x®0 means that for any function f(x) such that f(x)=o(x), at x®¥ x+f(x)£2 x for all sufficiently large values X.

Let us present some useful asymptotic equalities.

The polynomial is asymptotically equal to its highest term:

at x®¥; (4.1)

at x®¥; (4.2)

at x®¥ and a k¹0. (4.3)

The sums of powers of integers satisfy the relation:

at n®¥. (4.4)

Hence, in particular, we have n®¥

In a more general case, when n®¥ and for any integer k³0

; (4.6)

. (4.7)

Recurrent relations

Let us illustrate the concept of recurrence relations with the classical problem posed and studied by Fibonacci around 1200.

Fibonacci put his problem in the form of a story about the rate of growth of a population of rabbits under the following assumptions. It all starts with one pair of rabbits. Each pair of rabbits becomes fertile (fertile) after a month, after which each pair gives birth to a new pair of rabbits every month. Rabbits never die and their reproduction never stops. Let be F n- the number of pairs of rabbits in the population after n months and let this population consist of N n litter pairs and O n“old” pairs, i.e. F n = N n + O n. Thus, in the next month the following events will occur:

Old population in ( n+1)-th moment will increase by the number of births at the time n, i.e. O n+1 = O n + N n= F n;

Every old at a point in time n the pair produces at time ( n+1) a couple of offspring, i.e. Nn+1= C n.

The following month, this pattern is repeated:

O n+2 = O n+1+ Nn+1= Fn+1,

Nn+2=O n+1;

combining these equalities, we get the Fibonacci recurrence relation:

O n+2 + Nn+2=Fn+1 + O n+1,

Fn+2 = Fn+1 + F n. (4.8)

The choice of initial conditions for the Fibonacci sequence is not important; the essential properties of this sequence are determined by the recurrent relation (4.8). Usually believed F0=0, F1=1 (sometimes F0=F1=1).

The recurrence relation (4.8) is a special case of homogeneous linear recurrence relations with constant coefficients:

x n = a 1 x n-1 + a 2 x n-2 +…a k x n-k , (4.9)

where coefficients a i do not depend on n And x 1, x2, …, x k are considered given.

There is a general method for solving (i.e. finding x n as a function n) linear recurrent relations with constant coefficients. Let us consider this method using relation (4.8) as an example. We find a solution in the form

F n=crn (4.10)

with permanent from And r. Substituting this expression into (4.8), we obtain

cr + 2 = crn+ 1 + crn,

crn(rn-r-1)=0. (4.11)

It means that F n=crn is a solution if either from=0, or r= 0 (and hence F n =0 for all n), and also (and this is a more interesting case) if r 2 - r -1=0, and the constant from arbitrary. Then from (4.11) it follows

r= or r = . (4.12)

The number "1.618" is known as the "golden" ratio, since since ancient times it has been believed that a triangle (rectangle) with sides of 1 has the most eye-pleasing proportions.

The sum of two solutions to a homogeneous linear recurrence is obviously also a solution, and one can actually show that the general solution of the Fibonacci sequence is

F n= , (4.13)

where are the constants from And from' are determined by the initial conditions. Putting F 0 =0 and F 1 =1, we obtain the following system of linear equations:

, (4.14)

whose solution gives

c = -c" = . (4.15)

Linear recurrent relations with constant coefficients. Basic definitions and examples of recurrence relations Often the solution of one combinatorial problem can be reduced to the solution of similar problems of smaller dimension with the help of some relation called recurrence from the Latin word recurrere - to return. Thus, the solution of a complex problem can be obtained by successively finding a solution to easier problems and then recalculating according to recurrence relations to find a solution to a difficult problem. The recurrence relation of...

Share work on social networks

If this work does not suit you, there is a list of similar works at the bottom of the page. You can also use the search button

Aranov Viktor Pavlovich Discrete Math. Section 2. Elements of combinatorics.

Lecture 5

Lectures 5. METHOD OF RECURRENT RELATIONS

Lecture plan:

1. Basic definitions and examples of recurrent relations.
2. Linear recurrent relations with constant coefficients. Formula

Binet.

1. Basic definitions and examples of recurrence relations

Often, the solution of one combinatorial problem can be reduced to the solution of similar problems of lower dimension using some relation called the river R rent (from the Latin word recurrere - return). Thus, a solution to a complex problem can be obtained by sequentially finding a solution to easier problems, and further, n e calculating by recurrence relations, find a solution to a difficult problem.

The recurrence relation of the -th orderbetween elements of a sequence of numbers is called a formula of the form

(1)

Private decisionrecurrence relation is any successor b relation that turns relation (1) into an identity. Relation (1) im e there are infinitely many particular solutions, since the first elements are sequential about sti can be set arbitrarily. For example, the sequence is p e recurrent relation about solutions, since the identity holds.

The solution of the -th order recurrence relation is called common, if it is for a depends on arbitrary constants, and by choosing these constants we can well but get any solution of this relation. For example, for the ratios e niya

(2)

the general solution would be

. (3)

Indeed, it is easy to check that sequence (3) turns relation (2) into an identity. Therefore, it is only necessary to show that any solution of relation (2) can well but represent in the form (3). But any solution to this relation is uniquely determined. T with values ​​and. Therefore, we must prove that for any numbers and there are m but which values ​​and what

Since this system has a solution for any values ​​of and, then solution (3) is indeed a general solution of relation (2).

Example 1 . Fibonacci numbers.In 1202, the famous Italian mathematician Le about nardo of Pisa, who is better known by his nickname Fibonacci ( Fib o nacci - abbreviated filius Bonacci , i.e. the son of Bonacci), a book was written “ Liber abacci "(" Book and ha about the abacus"). This book has come down to us in its second version, which dates back to 1228. Let's consider one of the many problems given in this book.

A pair of rabbits brings once a month an offspring of two rabbits (female and male), etc. And than newborn rabbits, two months after birth, already bear offspring. How many rabbits will appear e res year, if at the beginning of the year there was one pair of rabbits?

From the condition of the problem it follows that in a month there will be two pairs of rabbits. Two months later I only the first pair of rabbits will give offspring, and you will get 3 pairs. A in another month, both the original pair of rabbits and the pair of rabbits that appeared two months ago will give offspring. Therefore, there will be 5 pairs of rabbits in total, etc.

Denote by the number of pairs of rabbits after months from the beginning of r about Yes. Then in months there will be these couples and so many more newborn couples. about faces, how many there were at the end of the th month, that is, more pairs. Thus, there is r e current ratio

. (4)

Since, then we sequentially find: etc. These numbers make up the sequence

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,

called near Fibonacci, and its members - Fibonacci numbers. They have a number of wonderful properties. Fibonacci numbers are related to the following combinator but a thorny task.

Find the number of binary words of length in which no two 1s go along d row.

Let's call these words correct and denote their number by . Let us divide the set of these regular words into two classes: words ending in zero and words ending in one. Let us denote the number of words in these classes and T responsible. According to the rule of addition

(5)

Obviously, for a word ending in zero, the first characters form a regular word of length, or in other words, there is a bijection between the set of regular length words ending in zero and the set of regular length words, that is.

If a valid length word ends in one, then the previous character of that word must be zero, and the first characters must form a valid length word. As in the previous case, we again have a bijection between the set of regular words of length ending in one and the set of regular words of length. Consequently. . From formula (5) we obtain the recursive relation About

. (6)

To use the recurrence relation, it is necessary for this calculation from change of all previous values. For example, if we need to know the number of rules b words of 10 characters, then it can be found by sequentially filling in the following table b face:

Table 1

The first two values ​​are found directly (-words 0 and 1; - words 000, 010, 101), and the rest - by formula (6).

Example 2 The problem of placing brackets in an expression with a non-associative bin operation. Let “” denote some binary operation. Consider in s expression in which a symbol denotes some binary non-association but active operation. How many different ways of arranging brackets are there in this s raz e nii?

An example of a non-associative operation is the vector product. Another example is the usual addition and multiplication performed on a computer. In with And that the representation of each number in computer memory is limited by a certain n number of digits, when performing each operation, an error occurs and m The expected result of these errors depends on the arrangement of brackets. Let - machine zero . It means that. Then while.

Let us denote the number of possible ways of arranging brackets by. Then

We call the operation conditionally a product. For an arbitrary, we divide all the ways of arranging brackets into classes, including in the -th class the ways in which but chala, the product of the first and last operands is calculated with some distance but new parentheses, and then their product is calculated:

(7)

where.

By definition, the number of ways to arrange brackets to calculate the first operands is equal, the last - . According to the product rule, the number of arrangements about side for expression (4) is equal. According to the rule of addition

, (8)

For example, .

1. Linear recurrence relations with constant coefficients

Let the function in relation (1) be a line th noah

, (9)

where are some numbers. Such ratios are called linear ratios solutions of the -th order with constant coefficients.

Let us first examine the second-order relations in detail, and then proceed to o b current occasion. At , from formula (9) we obtain

, . (10)

The solution of these relations is based on the following easily proven statements e niyakh.

Lemma 1. Let be a solution of relation (10), and be any number. Then the sequence is also solved And eat this ratio.

Lemma 2. Let and be solutions of the about solutions (10). Then the sequence is also I is a solution to this relation.

These two simple lemmas lead to the following important conclusion. scoop P the existence of all possible sequences with the operations of rest R dinatic addition and multiplication by a scalar forms a vector space. scoop P number of sequences that are solutions of relation (10) represents with about fight a subspace of that space. The enclosing space of all possible about sequences is infinite-dimensional, but the subspace of solutions of a linear recurrent T relation has a finite dimension equal to the order of the equation e niya.

Lemma 3. The dimension of the solution space of the recurrent relation (10) is equal to two.

From Lemma 3 it follows that to determine all solutions of Eq. (12) it is necessary to find two linearly independent solutions. Any other solution will be b is a linear combination of these basic solutions.

Consider the first order recurrence relation

, (11)

where is a constant.

If, then from (11) we have

, (12)

that is, the solution to a first-order recursive equation is a geometric progression.

We will look for the solution of the second-order recurrence relation also in the form (12). Then, substituting (12) into (9), we obtain

. (13)

For =0 we have a zero solution, which is of no interest. Considering, we divide the last ratio by:

(14)

Thus, the geometric progression (12) is a solution to the recurrence relation (10) if the denominator of the progression is the root of the quadratic equation e niya (14). This equation is calledcharacteristic equationfor recurrent coo t wearing (9).

The construction of basic solutions depends on the roots and the characteristic equation (14).

1. (). In this case, we have two solutions and, which l and unknown sims. To verify this, we show that from the formula

(15)

by an appropriate choice of constants, any solution of relation (10) can be obtained. Consider an arbitrary solution. We choose constants and so that for and:

(16)

Linear system determinant (16)

therefore, the system has a unique solution, which means that formula (15) is a general р e relation (10).

1. . In the case of multiple roots, the characteristic equation (13) has the form or. Then, and for relation (10) p about we obtain an equation that gives two basic solutions and. The general solution is represented as

. (17)

In the case of the th order relation (9), statements similar to those considered for the 2nd order equations take place.

1. The set of all solutions of equation (9) is a subspace in pr about the space of all sequences.
2. The dimension of this space is equal, that is, each solution is uniquely determined by its first values.
3. To determine the basis of the subspace of solutions, a characteristic e equation

. (18)

Polynomial

(19)

called characteristic polynomialrecursive relation (9).

1. If the characteristic equation has different roots, then the general solution of the recurrent relation (9) has the form

. (20)

For given initial values ​​of the solution, the constants n but walk out of the system

1. If is the root of the characteristic multiplicity equation, then relation (9) has the following solutions

Let the characteristic equation (18) have roots: ,…, multiplicities with about responsibly, ..., moreover. Then the characteristic set about the term and the general solution of relation (9) are represented as

Example 3 . Binet formula . Let us set the task of obtaining a formula in explicit form for h And sat Fibonacci. To do this, we find a solution to the recurrence relation (4) under the condition that. We compose the characteristic equation, find its roots and obtain a general solution. Constants and definitions e lim from the initial conditions: . Then either

, (21)

where is the golden section. Formula (21) is called Binet's formula . Wherein. From Binet's formula it follows that.

Other related works that may interest you.vshm>
3792.		Rationality of ratios in the asset of the enterprise	113.83KB
	The balance sheet is the main form of financial statements. It characterizes the property and financial condition of the organization at the reporting date. The balance sheet reflects the balances of all accounting accounts at the reporting date. These indicators are given in the balance sheet in a certain grouping.
8407.		constant method	17.82KB
	An object method is said to have the property of immutability (constancy) if, after its execution, the state of the object does not change. If you do not control the property of immutability, then its provision will depend entirely on the skill of the programmer. If the immutable method produces extraneous effects during execution, then the result may be the most unexpected, and it is very difficult to debug and maintain such code.
13457.		Phase plane method	892.42KB
	The phase plane method was first applied to the study of nonlinear systems by the French scientist Henri Poincaré. The main advantage of this method is the accuracy and visibility of the analysis of the motions of a nonlinear system. The method is qualitative
2243.		POSSIBLE DIRECTIONS METHOD	113.98KB
	The idea of ​​the method of possible MRI directions is that at each successive point there is a direction of descent such that moving a point along this direction for a certain distance does not violate the constraints of the problem. A direction determined by a vector is called a possible direction at a point if a sufficiently small movement from in the direction does not take the point outside the allowable area m. Obviously, if is an internal point of the set, then any direction at this point is possible. Possible...
12947.		HARMONIC LINEARIZATION METHOD	338.05KB
	Turning directly to the consideration of the harmonic linearization method, we will assume that the nonlinear system under study is reduced to the form shown in. A non-linear element can have any characteristic as long as it is integrable without discontinuities of the second kind. The transformation of this variable for an example by a non-linear element with a dead zone is shown in fig.
2248.		Graphical method for solving LLP	219.13KB
	Points lying inside and on the border of this area are valid planes. Namely, all points of the segment AB are the optimal plans of the problem on which the maximum value of the linear form is achieved. Sequential plan improvement method The method is based on an ordered enumeration of the corner points of the set of problem plans in the direction of increasing or decreasing the linear form and contains three essential points. First, the method for calculating the baseline is specified.
7113.		Harmonic linearization method	536.48KB
	Harmonic linearization method Since this method is approximate, the results obtained will be close to the truth only if certain assumptions are met: A non-linear system should contain only one non-linearity; The linear part of the system should be a low-pass filter that attenuates the higher harmonics that occur in the limit cycle; The method is applicable only to autonomous systems. We study the free motion of the system, that is, the motion under non-zero initial conditions in the absence of external influences....
10649.		Index method of analysis	121.13KB
	individual indexes. General aggregate indexes. Average converted indexes. Indices of variable and constant composition indices of structural shifts.
12914.		Least square method	308.27KB
	Let from theoretical considerations we know that. Therefore, we can say that our task is to draw a straight line in the best possible way. We will assume that the entire error lies in. We will select the desired coefficients from the considerations so that the random addition is the smallest.
9514.		Accounting method	1002.23KB
	Accounting rahunki that їх pobudova. Vіn sladєtsya z a number of elementіv golovnі z yakikh: documentation; inventory; rahunki; sub-record; assessment; calculation; balance; soundness. Rahunki accounting recognized for the appearance of the presence of assets and liabilities. Accounting rahunki that їх pobudova.

RECURRENT RELATIONS

RECURRENT RELATIONS

(from lat. recur-rens, genus case recurrentis - returning) - f-s of the same type, which connect a certain sequence following each other (this can be a sequence of numbers, f-tions, etc. ). Depending on the nature of the objects connected with R. with., these relations can be algebraic, functional, differential, integral, etc.

Naib. well-known class of R. s. are recurrent functions for special functions. Yes, for cylindrical functions Z m (x)P. from. look like

They allow by function Z m0 (x) find functions Z m (x)at T= T 0 b 1, T 0 b 2 etc. or, for example, according to the values ​​of functions at some point X 0 . 0 find (in numerical calculations) the value of any of the functions

At the same point (here m 0 - any real number).

Dr. an important class of R. s. give numerous methods of successive approximations (cf. iteration method); here are the methods perturbations of the theory.

In quantum mechanics, there is one more type of R. s., connecting vectors in the Hilbert space of states. For example, stationary harmonies, oscillators are parameterized by non-negative integers. The corresponding vectors, denoted by , where n- whole, with different n can be obtained from each other by the action of the creation operators a + and destruction but:

These relationships can be resolved by expressing any vector in terms of (the lowest energy state, h = 0):

A generalization of this construction is the representation second quantization in quantum statistics. mechanics and quantum field theory (see Fock space).

A typical example of R. s. in the statistical mechanics - equations for partial distribution functions that form the Bogolyubov chain (see. Bogolyubov equations); knowledge of such f-tions allows you to find all thermodynamic. system characteristics.

In quantum field theory dynamic. contained, for example, in Green's functions. For their calculation, various approximations, most often - perturbation theory calculations. An alternative approach is based on integro-differential Dyson equations, which are R. s.: the equation for the two-point Green's function contains a four-point one, etc. Like the Bogolyubov equation, this system can be solved only by "breaking" the chain (the place of the "break" is usually chosen from physical considerations and determines the resulting ).

Another type of R. s. in quantum field theory - The horde of identities in theories calibration fields. These identities also represent a chain of integro-differential relations connecting Green's functions with dec. the number of external lines, p are a consequence of the gauge invariance of the theory. They play a decisive role in checking the calibration symmetry during the procedure renormalization.

Finally, itself is also a recurrent procedure: at each step (in each subsequent loop) counterterms, obtained from the calculation of diagrams with fewer loops (for more details, see R operation).A. M. Malokostov.

Physical encyclopedia. In 5 volumes. - M.: Soviet Encyclopedia. Editor-in-Chief A. M. Prokhorov. 1988 .

See what "RECURRENT RELATIONS" is in other dictionaries:

recurrent relations- - [L.G. Sumenko. English Russian Dictionary of Information Technologies. M .: GP TsNIIS, 2003.] Topics information technology in general EN recurrence relations ... Technical Translator's Handbook

- (Weber functions) the general name for special functions that are solutions of differential equations obtained by applying the method of separation of variables for equations of mathematical physics, such as the Laplace equation, the equation ... ... Wikipedia

Or the Josephus rhyme is a well-known mathematical problem with historical overtones. The task is based on the legend that the detachment of Josephus Flavius, who defended the city of Yodfat, did not want to surrender to the superior forces of the Romans who blocked the cave. ... ... Wikipedia

Pafnuty Lvovich Chebyshev In mathematics, an infinite sequence of real polynomials is called a sequence of orthogonal polynomials ... Wikipedia

This article is proposed for deletion. An explanation of the reasons and a corresponding discussion can be found on the Wikipedia page: To be deleted / November 22, 2012. While the discussion process ... Wikipedia

The Padovan sequence is an integer sequence P(n) with initial values ​​and a linear recurrence relation The first values ​​of P(n) are 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28 , 37, 49, 65, 86, 114, 151, 200, 265 ... Wikipedia

Hermite polynomials of a certain form are a sequence of polynomials in one real variable. Hermite polynomials arise in probability theory, in combinatorics, and physics. These polynomials are named after Charles Hermite. Contents 1 ... ... Wikipedia

- (Bessel functions) solutions Zv(z) of the Bessel equation where the parameter (index) v is an arbitrary real or complex number. In applications, one often encounters an equation that depends on four parameters: the solutions to which are expressed in terms of C... Physical Encyclopedia

Method for solving a system of linear algebraic. equations A x= b with a Hermitian non-singular matrix A. Among direct methods, it is the most effective when implemented on a computer. The computational scheme of the method is generally based on the Hermitian factorization ... ... Mathematical Encyclopedia

Modified Bessel functions are Bessel functions of a purely imaginary argument. If we replace with in the Bessel differential equation, it will take the form This equation is called the modified Bessel equation ... Wikipedia

The recurrence relation has order k , if it allows expressing f(n+k) in terms of f(n), f(n+1), …, f(n+k-1).

Example.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 is a second order recurrence relation.

f(n+3)=6f(n)f(n+2)+f(n+1) is a recurrent relation of the third order.

If a k-th order recurrence relation is given, then infinitely many sequences can satisfy it, since the first k elements of the sequence can be set arbitrarily - there are no relations between them. But if the first k terms are given, then all other elements are uniquely determined.

Using the recurrence relation and the initial terms, one can write out the terms of the sequence one by one, and sooner or later we will get any of its members. However, if you need to know only one specific member of the sequence, then it is not rational to calculate all the previous ones. In this case, it is more convenient to have a formula for calculating the nth term.

The solution of the recurrence relation any sequence for which the given relation holds identically is called.

Example. The sequence 2, 4, 8, …, 2 n is the solution for the relation f(n+2)=3∙f(n+1) – 2∙f(n).

Proof. The common term of the sequence is f(n)=2 n . So f(n+2)= 2 n+2, f(n+1)= 2n+1 . For any n, the identity 2 n+2 =3∙2 n+1 – 2∙2 n holds. Therefore, when substituting the sequence 2 n into the formula f(n+2)=3f(n+1) – 2f(n), the relation is fulfilled identically. Hence, 2 n is the solution of the indicated relation.

Solution of the recurrence relation kth order is called general, if it depends on k arbitrary constants α 1 , α 2 , … α k and by selecting these constants, any solution of this relation can be obtained.

Example. The recurrence relation is given: f(n+2)=5f(n+1)-6f(n). Let us prove that its general solution has the form: f(n)= α 2 n + β3 n .

1. First we prove that the sequence f(n)=α 2 n + β3 n is a solution to the recurrence relation. Substitute this sequence into the recurrence relation.

f(n)= α 2 n + β 3 n , so f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 , then

5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f( n+2).

The recurrence relation holds, therefore, α 2 n + β 3 n is the solution of this recurrence relation.

2. Let us prove that any solution of the relation f(n+2)=5f(n+1)–6f(n) can be written as f(n)= α 2 n + β 3 n . But any solution of the second-order recurrence relation is uniquely determined by the values ​​of the first two terms of the sequence. Therefore, it suffices to show that for any a=f(1) and b=f(2) there are α and β such that 2 α +3 β =a and 4 α +9 β =b. It is easy to see that the system of equations has a solution for any values ​​of a and b.

Thus, f(n)= α 2 n + β 3 n is the general solution of the recurrent relation f(n+2)=5f(n+1)–6f(n).

Linear recurrence relations with constant coefficients

There are no general rules for solving recurrence relations, but there is a frequently occurring class of recurrence relations for which an algorithm for solving them is known. These are linear recurrent relations with constant coefficients, i.e. type ratios:

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

Let us find the solution of the general linear recurrence relation with constant coefficients of the first order.

A linear recurrence relation with constant coefficients of the first order has the form: f(n+1)=c f(n).

Let f(1)=a, then f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, similar to f(4)=c 3 ∙a and so on, note that f(n)=cn -1 ∙f(1).

Let us prove that the sequence c n -1 ∙f(1) is the solution of the first order recurrence relation. f(n)=c n -1 ∙f(1), so f(n+1)=c n f(1). Substituting this expression into the relation, we obtain the identity c n f(1)=с∙ c n -1 ∙f(1).

Let's now consider in more detail linear recurrence relations with constant coefficients of the second order , that is, relations of the form

f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).

Note that all considerations hold true for higher-order relations as well.

Solution Properties:

1) If the sequence x n is a solution (*), then the sequence a∙x n is also a solution.

Proof.

x n is a solution to (*), hence x n +2 =C 1 x n +1 +C 2 x n . We multiply both sides of the equality by a. We get a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n . This means that ax n is the solution (*).

2) If the sequences x n and y n are solutions (*), then the sequence x n +y n is also a solution.

Proof.

x n and y n are solutions, so the following identities hold:

x n +2 \u003d C 1 x n +1 + C 2 x n.

y n +2 =C 1 y n +1 +C 2 y n .

Let's add the two equalities term by term:

xn +2 +yn +2 =С 1 ∙xn +1 +С 2 ∙xn + С 1 ∙yn +1 +С 2 ∙yn = С 1 ∙(xn +1 + yn +1)+С 2 ∙(xn +yn). This means that x n +y n is the solution to (*).

3) If r 1 is a solution to the quadratic equation r 2 =С 1 r+С 2, then the sequence (r 1) n is the solution to the relation (*).

r 1 is the solution of the quadratic equation r 2 =C 1 r+C 2 , so (r 1) 2 =C 1 r 1 +C 2 . Let's multiply both sides of the equality by (r 1) n . Get

r 1 2 r 1 n \u003d (C 1 r 1 + C 2) r n.

r 1 n +2 \u003d C 1 r 1 n +1 + C 2 r 1 n.

This means that the sequence (r 1) n is the solution to (*).

From these properties it follows solution way linear recurrence relations with constant coefficients of the second order:

1. Compose the characteristic (quadratic) equation r 2 =C 1 r+C 2 . Let's find its roots r 1, r 2. If the roots are different, then the general solution is f(n)= ar 1 n +βr 2 n .

2. Find the coefficients a and β. Let f(0)=a, f(1)=b. System of equations

has a solution for any a and b. These solutions are

A task . Let's find a formula for the common term of the Fibonacci sequence.

Solution . The characteristic equation has the form x 2 \u003d x + 1 or x 2 -x-1 \u003d 0, its roots are numbers, which means that the general solution has the form f (n) \u003d . As it is easy to see, from the initial conditions f(0)=0, f(1)=1 it follows that a=-b=1/Ö5, and, consequently, the general solution of the Fibonacci sequence has the form:

.

Surprisingly, this expression takes integer values ​​for all natural values ​​of n.