Linear difference equation

from Wikipedia, the free encyclopedia

Linear difference equations (also linear recursion equations , rarely C recursions or linear recurrence from English linear recurrence relation) are relationships of a particularly simple form between the members of a sequence .

example

A well-known example of a sequence that satisfies a linear difference equation is the Fibonacci sequence . With the linear difference equation

and the initial values and the result is the result

0, 1, 1, 2, 3, 5, 8, 13, ...

Each term in the sequence (apart from the two initial values) is the sum of the two previous ones.

In general, each is called an equation of form

a (homogeneous) linear difference equation of the 2nd order (with constant coefficients). The coefficients and define the difference equation. A sequence that satisfies the equation for all is called the solution of the difference equation. These solutions are clearly defined by the two initial values.

So the Fibonacci sequence is a solution to the difference equation defined by . The result is due to the initial values and determined uniquely.

General theory

A -th order linear difference equation over a body is of form

whereby . The linear difference equation is defined by the coefficients and the function . A sequence of numbers that satisfies the equation for all is called the solution of the difference equation. This infinite sequence is uniquely determined by its  initial values . If for all , then the equation is called homogeneous , otherwise it is called inhomogeneous. The sequence of numbers for all satisfies all homogeneous equations and is therefore called a trivial solution.

Without loss of generality it can be assumed. This gives an alternative representation that clarifies the calculation rule for from the previous values ​​more clearly:

whereby .

Calculation rules

  • If and are solutions of the homogeneous linear difference equation , then there is also a solution for any .
  • If and are solutions of the inhomogeneous linear difference equation , then a solution of the corresponding homogeneous linear difference equation is with for all .
  • If a solution of the inhomogeneous linear difference equation and a solution of the associated homogeneous linear difference equation is with for all , then there is also a solution of the inhomogeneous linear difference equation for any .

Solution theory of homogeneous linear difference equations of the 2nd order with constant coefficients

The first idea for the solution is to observe that such sequences usually grow exponentially . This suggests the first approach with a non-zero lambda. When used, that results

after division by so

This quadratic equation is called the characteristic equation of recursion . Sequences of the form with one that is a ( real or complex ) solution of the characteristic equation thus satisfy the desired recursion equation.

The second idea is that of superposition : Are and consequences that satisfy the recurrence equation, so this also applies to the result with

for any (real or complex) numbers . One can also express it this way: The set of all sequences that satisfy the recursion equation forms a vector space .

If the initial values ​​are now given and the characteristic equation has two different solutions , the coefficients can be determined from the following linear system of equations :

Then applies to everyone .

In the example of the Fibonacci sequence are

the so-called Binet formula results

Special case: The characteristic equation has a double solution

If the characteristic equation has only one solution, i.e. a double zero  , the general solution has the form

For example, (that is ) satisfies the recursion equation

Solving linear difference equations with constant coefficients

A linear difference equation with constant coefficients is of the form

where all are constant.

Solution of the homogeneous equation

With the approach a nontrivial solution of the homogeneous equation is determined. be o. B. d. A. same . This leads to the characteristic equation . The different zeros of the equation then result in linearly independent solution sequences and thus solutions of the homogeneous equation.

If the zeros are not different, the solution sequence belonging to a multiple zero occurs with a factor in the solution that is a polynomial with a degree smaller than the multiplicity of the zero.

Example:

Homogeneous difference equation
Approach:
Characteristic equation with
Solving the equation as a linear combination of special solutions. The constants and can be determined from two initial values ​​of , and .

Particulate solution

The determination takes place here analogously to differential equations.

Disturbance function b (n) Approach particular solution
constant constant
polynomial Polynomial of the same degree

If the approach should already be a solution of the corresponding homogeneous difference equation, it has to be multiplied by until it yields a solution of the inhomogeneous equation.

example

A sequence is given with . We are looking for the explicit formula. We first look for the general solution for the homogeneous recursion equation.

Inhomogeneous recursion equation
Homogeneous recursion equation, approach:
Shorten , solutions expire
Characteristic equation, solutions: and
General solution of the homogeneous recursion equation

Now we are looking for a special solution to the inhomogeneous recursion equation, the particular solution.

Inhomogeneous recursion equation, approach:
Solution by comparison of coefficients:
Particulate solution

According to the above calculation rules we get all solutions of the inhomogeneous recursion equation. Now and must be determined in such a way that and applies.

:
:

So this is the formula we were looking for.

See also

literature

  • L. Berg: Linear systems of equations with a band structure. Carl Hanser, Munich / Vienna 1986.
  • Ian Jaques: Mathematics for Economics and Business. Fifth Edition, Prentice Hall, 2006 (Chapter 9.1 Difference Equations ).

Web links