대학원 이산수학 보고서(영문)
페이지 정보
작성일 23-01-26 19:13
본문
Download : Reccurrence_equation.pdf
[5] Cull P.; Flahive M.E, Robson, R.O., Difference equations: from rabbits to chaos, p.74, New York : Springer, c2005, ISBN:0387232338
References
순서
이산수학,영문이산수학,대학원이산수학,대학이산수학,discrete Mathematics,수학,수능이산수학,영문수학
There is a wide range of applications for linear recurrence equation where the field of computer
레포트 > 공학,기술계열
(1)
We show that the homogeneous solution is a linear combination of exponential functions and the particular solution is of the same form as the RHS of the equation with an increase in polynomial order if any part of the RHS can be expressed in terms of the homogeneous solution, so called resonance.
대학원 과정 이산수학 Discrete Mathmatics 리써치를베이스로 한 보고서입니다.
Recurrence equations are equations that, given initial conditions, recursively defines a sequence. The set of linear recursive equations is a subset of the set of recurrence equations and linear equations have many properties that enables more explicit theoretical analyses of the problem. A general linear recurrence equation can be written as [1, 3],
설명
algorithms is a large application area. Even if the problem is not linear the problem can sometimes be approximated as linear and it can therefore be solved using the methods developed for linear problems. In this report we focus on linear second order recurrence equations with constant coefficients hence K = 2 and dk,k = 0,1,2 are constants. This report aims to give a semi-rigorous introduction to the field of linear second order recurrence equations with constant coefficients where the solutions are derived and easy-to-use methods are presented.
[4] Epp, Susanna, Discrete Mathematics with Applications, 4th ed., p317-319, DePaul University, BROOKS/COLE CENGANGE Learning, 2011
1 Introduction
Using generating functions to solve such problems require a lot of computations and par- tial fractions expansions. Therefore a more hands on approach is presented and discussed where the forms of the homogeneous and particular solutions are assumed, based on the pre- viously derived solutions. The homogeneous solution is determined by solving a characteristic equation, and using the characteristic roots together with the assumed form of the solution the solution is given with two undetermined coefficients. The particular solution is found by substituting the assumed form of the particular solution into the equations and solving a linear system of equations. Finally the unknown coefficients are determined from the initial conditions.
[1] Tang M., Tang V.T. Using Generating Functions to Solve Linear Inhomogeneous Recurrence Equa- tions, Proceedings of the 6th WSEAS International Conference on Simulation, Modelling and Opti- mization, Lisbon, Portugal, September 22-24, 2006.
Having found the homogeneous and particular solutions to the problem the solution is given as a sum of the two , an = ahn + apn. This solution has two unknown parameters A, B, see (25), which are easily determined by the initial conditions a0,a1. The parameters A,B are given by (31).
Download : Reccurrence_equation.pdf( 31 )
∑N i=0
In this project, solutions to second order linear recurrence equations with constant coeffi- cients have been investigated. We have used generating functions to derive the general solution to the homogeneous equation and we show that in general the particular solution is complicated to find. By limiting the right hand side (RHS) in the equation to a polynomial-exponential family of functions we can however find the particular solution in a closed form.
[2] Parag H. Dave; Himanshu B. Dave, Design and Analysis of Algorithms, p.709, Pearson Education India, 2007, ISBN 978-81-775-8595-7
The solution is found for f(n) ∈ F but For other forms of f(n), other forms of apn have to be assumed which may be very complicated if f(n) is a complicated expression. Just note that cos n, sin n ∈ F since they can be expressed in terms of e±in.
[3] Kauers, M., Paule P., The Concrete Tetrahedron, Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates, p.66 Texts and Monographs in Symbolic Computation, 2011, ISBN: 978-3-7091-0445-3
대학원 이산수학 보고서(영문)
dk(n)an−k = f(n), n ≥ K,
다.
for arbitrary coefficients dk(n), initial conditions βi and a function f(n).
REFERENCES
In Section 2 we are first given a short overview to second order linear recurrence equations with constant coefficients where to the two main solution methods are introduced. Then in Section 2.1 we are given a brief introduction to the method of homogeneous and particular solutions. In Section 2.2 the method of generating functions is described where the solution to the homogeneous equation is derived in Section 2.2.1 and ditto for the particular solution is derived in Section 2.2.2 for a particular family of functions f(n) (polynomial-exponential functions). In Section 2.3 a hands-on solution method derived from the generating function results is introduced arriving at a final solution to the problem.
ai =βi,i=0,1,...,K−1
∑K
k=0
2.3.3 Solution to the full problem
대학원 과정 이산수학 Discrete Mathmatics 리써치를베이스로 한 레포트입니다.
