This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
1. Then the iterates converge to the unique fixed point of G(x] — G(x, x). Proof.
Setting yk = \\%k+i ~ xk\\i
we
obtain
yk+i < By Theorem 1.6.6, we then get yk < uk, where u^ is the solution of auk + fluk-i, which is Uk — CQZ^ + c\z%, where z\ and 22 axe the roots of z2 — az — j3 — 0. Because of the assumption on a and ,3, the two roots z\ and z<2 are less than 1 in modulus, which means that the zero solution of the comparison equation is exponentially stable. Using similar arguments as in the previous theorems, we can conclude that the sequence x^ is a Cauchy sequence. Since
+ \\G(x*,xk.l}-G(xk,xk-l < @\\x* -xk_i\\ +a||x* the convergence of xk shows that xk+i —* G(x*}. The uniqueness of x* now follows very easily, and the proof is complete. D
6.3.2
Effect of perturbations
The effect of perturbations on the iterative methods are of two different kinds. If the perturbations are small and tend to zero as n tends to oo, then the theorems on total stability will ensure that the fixed points continue to have asymptotic stability. In numerical analysis, however, perturbations may remain bounded for all n (roundoff errors, for example). In this case, a more convenient concept is practical stability. If an iterative procedure is practically stable, the sequence of iterates will not tend to the solution x* but to a ball B(x*,5] surrounding x* . Inside 5, the solution may oscillate,
Copyright © 2002 Marcel Dekker, Inc.
180
CHAPTER 6. APPLICATIONS
TO NUMERICAL
ANALYSIS
but what is important is that it never leaves B. Of course it would be nice to have B as small as possible. Let us consider for example the iterative method •-^n+1 — J\'E"n);
"^no
^'O-
^D.oZJ
WTe assume that for x, y e DQ C IRS,
\\f(x)-f(y}\\
(6.33)
with a < I . Suppose that the errors in the computations perturb (6.32) by a bounded perturbation Rn, that is xri+} - f ( x n ) + Rn,
xno = x0,
(6.34)
with xn,xn G DQ for all n. Then Theorem 4.11.2 can be applied. The conclusion is that the difference of the two solutions \\xn — xn\\ will not exceed R/(l — a), wThere R = supRn. The condition that all the balls B (xn. j™;) must be contained in DQ may be very restrictive. In fact if a is close to one, it follows that these balls are very large and the method is considered a bad one.
6.4
Miller's, Olver's, and Clenshaw's Algorithms
The situation that we shall analyze in this section and in the next is in a certain sense the opposite of that treated in the previous ones. In fact, there the limit point was important (and indeed in the theory of iterative processes the "solution1' is the limit point), where the intermediate values zn are considered an unavoidable noise. Here the limit point will riot be important (generally it will not exist) and the important part (the solution) will be a finite subset of the sequence itself. These problems are very typical in that part of numerical analysis which concerns the study of special functions, orthogonal polynomials, quadrature formulas, and numerical methods for ordinary differential equations. Consider the homogeneous scalar linear equation (see (2.12)) of order k Lyn = 0.
(6.35)
It has k linearly independent solutions /i(n), f2(^)1 • • • •> f k ( n ) - Suppose that the solution yn — 0 (n > 0) is unstable, and 11111^7-7=0^
i
= 2,3, . . . , f c .
(6.36)
When this happens, the solution f i ( n ) is said to be minimal. The problem is how to find f\ or a multiple of it. Even if we know the exact initial
Copyright © 2002 Marcel Dekker, Inc.
6.4.
MILLER'S, OLVER'S, AND CLENSHAW'S ALGORITHMS
181
condition that generates the minimal solution, small errors in the calculations will, as usual, lead us to solve a perturbed equation Lyn = e n , whose solution (see (2.18)) will contain all the fi(n). This will destroy the process (see for example [69, 180]) because the fi(n) (i > 2) grow faster than \f\(n}\. The same problem appears, of course, in the nonhomogeneous case, where it is riot excluded a priori that there exists a bounded solution even if all the fi(ri) are bounded. One is often interested in following this solution. Consider, for example, the following first-order equation yn+i -(n + l}yn = -1,
y0 - e.
(6.37)
The solution of the homogeneous part is yn = en\, while the complete solution is
which is bounded for n —> oo. If one tries to follow this solution, a small error in the initial data e (always existing because it has infinite digits), will be amplified by the factor n\. A simple method is to find the way to look for the solution of the problem backwards (for n —> oo). because in this case the origin becomes asymptotically stable for the homogeneous equation and the errors will be damped. This idea indeed works, as we will show in a simple case, which is the original problem to which it was applied (see [69] for references). Consider Lyn = anyn+i + bnyn 4- c n 2/ n -i, (6.38) where a n ,c n 7^ 0 for all n, and the nonhomogeneous problem Lyn = 9n-
(6.39)
Suppose that two linearly independent solutions 0n and 4>n of the homogeneous equation are such that 0n is minimal, that is lim — = 0.
n-oo^ n
(6.40)
Of course all solutions that are multiple of 4>n are minimal and vice versa. That means that only one appropriate initial condition is needed to determine the minimal solution we are interested in. The general solution of the nonhomogeneous problem is then yn — Cl4>n + C2$n + 2/n,
(6-41)
where yn is a particular solution that will be supposed minimal too; that is, lim ^ = 0
n-oo -
Copyright © 2002 Marcel Dekker, Inc.
(6.42)
182
CHAPTER 6. APPLICATIONS
TO NUMERICAL
ANALYSIS
and £o = 0. We are interested in the solution
yn = ~n + yn.
(6.43)
9o
A class of methods are based on the following result. Theorem 6.4.1 Consider the boundary value problem
where N is a positive integer, and suppose that conditions (6.40) and (6.42) are verified. Then the problem (6-44) has a solution and moreover for fixed n, y(n -> yn as N -> oo. Proof. Since yn is a particular solution of the nonhomogeneous equation, any other solution of the same equation will be (6.45) The boundary conditions give for c\ , . 4>N
It follows that C} n
and c2
and c2 Co
the values
__ —
tend to zero as N —> oo and the claim follows.
Note that the condition yN — 0 can be replaced by y^- = k where k is any fixed value (for example an approximation of 7/yv, if available). In the homogeneous case yn can be obtained starting from yN = 0, yjv-i
=
1>
anc
^ then using the difference equation backwards
iin-i — ~~r~yn+i ~ ~yn i obtaining a value y^
different from y^. Multiplying the sequence by the one
scale factor 1/0/2/0 ' o^t^118 yn • This is Miller's algorithm. A disadvantage of this algorithm is that one does not know a priori which value of TV must be used. A modified version of it which works in the nonhomogeneous case is also obtained by considering that the boundary value problem (6.41) is equivalent to the system of equations Ay(N] = b,
Copyright © 2002 Marcel Dekker, Inc.
(6.46)
6.4.
MILLER'S, OLVER'S, AND CLENSHAW'S ALGORITHMS
183
where 0
\
A= CN-I
a/v-2 6/v-i J
and y(N)
y
, (N) (N) —_ \y\ • • • UN-I) ' ]T
Some clever methods to solve this system can be used to avoid the growth of the errors (see [33, 34]. By solving the system in an appropriate way, it is also possible to determine the best value of ./V (Olver's algorithm). Similar in motivation to the previous algorithm and indeed related to it is the following, known as Clenshaw's algorithm. Here the problem is to evaluate the sum N v—«.
bnUr
where bn is a given sequence and un is supposed to satisfy a linear difference equation Lun = 0. The algorithm uses the result stated in Theorem 2.2.6, that is, one considers the transposed equation (j = 1,2, . . . ,
= 0
L yn, obtaining /v
jf
fc-i
]T bnun = Yl yj ^Pi(j - k)uj-i-
n=0
j^O
i=0
Suppose, for example, we want to compute f^ = Y^n=o bnTn(z), where Tn(z) are Chebyshev polynomials satisfying the equation Tn+\ — 2zTn + T n _i — 0. The transpose equation is yn - 2zyn+i + yn+2 = bn,
n = N, N - 1 , . . . , 0
2//V+1 = 2//V+2 = 0, which can be solved recursively obtaining y\ and y^. From the quoted result it then follows /N ~ yo + y\\T\(z} — 2zTo(z)} — yo — zy\. It is interesting to note that the sum can be obtained without the knowledge of the polynomials Tn(z) except for TQ(Z) and T\(z} and also the reduction of the operations involved.
Copyright © 2002 Marcel Dekker, Inc.
184
6.5
CHAPTER 6. APPLICATIONS
TO NUMERICAL
ANALYSIS
Boundary Value Problems
The topic discussed in this section arises typically in that part of numerical analysis that concerns the approximation of solutions of ODEs and PDEs. We shall consider, for simplicity, the autonomous case. The more general case is not, in principle, more complicated. Let us consider yn+i - 25yn + yn-i = gn,
yo = a,
yN = /?,
(6.47)
with 5 > 1, TV » 1. This problem can be solved in many different ways. It can be rewritten as a system of N — 1 equations similar to (6.46), and then solved by a suitable factorization of the coefficient matrix. This procedure has already been discussed in Chapter 5. Here we prefer to remain in the difference equation framework. We only outline that the LU'factorization would lead to the same kind of equations derived below. The characteristic polynomial of (6.47) has two positive roots, one less than one and the other greater than one. This means that the origin is not asymptotically stable for the homogeneous part and this, as usual, creates difficulties because the errors may be amplified. One way to avoid this is to transform the linear second-order equation (6.47) into nonlinear first-order equation (see Problem 6.12). xn+i = ^—, zo — xn
(6.48)
*»' = w^-
(6 49)
and
-
Furthermore, one verifies that 2/n+i = xnyn + zn.
(6.50)
The solution is obtained by computing recursively the sequences {xn}, {zn} utilizing (6.48) and (6.49) with x\ = 0 and z\ — a up to n — N — 1 and then computing {yn} using (6.50) from n — N to n = 1 with y^ — (3. The advantage is that (6.48) has a limit point asymptotically stable and the sequence xn converges rnonotonically to this point, while the sequences (6.49) and (6.50) remain bounded. Theorem 6.5.1 If XQ = 0,5 > 1, the sequence {xn} converges rnonotonically to the first root p of the characteristic polynomial of (6-47) and, moreover, 0 < xn < p.
Copyright © 2002 Marcel Dekker, Inc.
6.6.
MONOTONE ITERATIVE METHODS
185
Proof. The critical points of (6.48) are the roots of the equation xn — 26x + 1 = 0, which is the characteristic polynomial of (6.47). Let p be the root less than one. Changing the variable hn = p(p - xn), equation (6.48) becomes 2
One shows at once (for example using the Liapunov function Vn = h^ that the half line h > 0 is contained in the asymptotic stability region of the origin, and moreover 0 < hn < p2, from which it follows that -p < xn ~ P < 0.
O
(6.52)
The method just described is known under many names, for example Sweep method (see [41]), recessive method, discrete Riccati method, and so on. It is also related to Bellman's method of invariant imbedding.
6.6
Monotone Iterative Methods
In this section, we shall develop a general theory for a broad class of monotone iterations. This class of iterations includes Newton's method as well as a family of methods, which are called Newton-Gauss-Seidel processes that are obtained by using the Gauss-Seidel iteration on the linear systems of Newton's method. As before, we are interested in finding the solutions of 0 = f(u),
(6.53)
where / e C[IR n ;IR n ]. Let us first split the system (6.53) as 0 = /»(ui,M w ,[4J,
(6-54)
where, for each z, 1 < i < n, pi + qi = n — 1 and u — (w^, [u]pi, [u]qi). Let v, w G IRn be such that v < w. Then v, w are said to be coupled quasi lower and upper solutions of (6.53) if 0 < fi(vi,[v]pi,[w]qi), 0 > fi(wi,[w]pi,[v]Qi). Coupled quasi-extremal solutions of (6.53) can be easily defined. Vectorial inequalities mean the same inequalities between the components of the vectors. We arc now in a position to prove the following result.
Copyright © 2002 Marcel Dekker, Inc.
186
CHAPTER 6. APPLICATIONS TO NUMERICAL
ANALYSIS
Theorem 6.6.1 Assume that f G C[IR n ,IR n ] and possesses a mixed quasimonotone property. That is, for each z, fi(ui, [w] pi , Hg,;) is nondecreasing in [u]p., and nonincreasing in [u]qi. Suppose further v,w are coupled quasi lower and upper solutions of (6.53) and
whenever v < u < u < w and Mi > 0. Then there exist monotone sequences {un},{wn} such that vn —* p, wn —» r as n —> oo and p.r are coupled minimal and maximal solutions of (6.53) such that v
For any 771,772 G [v.w] = [u G IRn : v < u < w}, consider the
Ui = M^fifai,
[r)i]jri, \rn\qi) + mi,
i = 1, 2, . . . , n.
Clearly u can be uniquely defined, given 771,772 G [v,w]. Therefore, we can define a mapping A such that .A [771, 772] — u. It is easy to show that A satisfies the properties: (i) 0 < A[v,w],
0 > A[w.v}]
(ii) A is mixed monotone on [TJ,U']. Then the sequences {vn}. {wn} with VQ — v. WQ — w can be defined as follows
w = Furthermore, it is clear that {vn}, {wn} are monotone sequences such that v < Vn < wn < w and consequently limT^-^oo vn = p, limn^oo wn = r exist and satisfy the relations
By induction, it is also easy to show that if ( u i , U 2 ) is a coupled quasi solution of (6.53) such that v < u\,u^ < w and consequently (p, r) are coupled quasi solutions, the conclusion of the theorem follows and the proof is complete. D If / does not possess the mixed quasi monotone property, we need a different set of assumptions to generate monotone sequences that converge to extremal solutions. This is the content of the following results. Theorem 6.6.2 Assume that (i) there exist v, w G IRn with v < w such that 0 < f(v).. 0 > f ( w ) :
Copyright © 2002 Marcel Dekker, Inc.
6.6. MONOTONE ITERATIVE METHODS
187
(ii) there is a n x n matrix M such that f(y)-f(x)>-M(y)(y-x), whenever v < x < y < w. Then the sequence {wn}, given by wn + Bnf(wn),
(6.55)
where Bn is any nonnegative subinverse of M(wn), is well defined, and {wn} is monotone nonincreasing such that limn_+00 wn — r. If there exists a nonsingular matrix B > 0 such that lim inf n_>oo Bn > B, then r is a maximal solution of (6.53). Proof. Set v — VQ and w — WQ. From BO > 0 and /(WQ) < 0 it follows that w\ < WQ. Using the fact that BQ is a subinverse of M(WQ), we find for any u e [v,w], u + B0f(u)
= wi - (WQ-U)- B0[f(w0) - f(u)] < wi - [I - BOM(WQ)}(WQ -u}<wi.
Hence, in particular. VQ < VQ + 5o/(vo) < w\- Similarly, we obtain f ( w i ) < f ( w Q ) + M(w0 - wi) = [I- M(wQ}B0}f(w0)
< 0.
Proceeding similarly we see by induction that wn-i>wn>vo,
f(wn) > 0,n = 1,2,
----
(6.56)
Consequently, as a monotone nonincreasing sequence that is bounded below, {w} has a limit r > VQ. If u is any solution of (6.53) such that u 6 [v, w}, then u = u + BQ/(U) < wi, then by induction u < wn for all n. Hence u < r. Finally, the continuity of / and the fact Iiminf n 5 n > B, where B > 0 is nonsingular, (6.56) yields 0 = limmi[wn+i - wn] = ]immi(Bnf(wn)) n—»oo
=
n—KX>
-(lim inf B n ) f ( r ] > -Bf(r) > 0,
which implies /(r) = 0 completing the proof. D By following the argument of Theorem 6.6.2, one can prove the next corollary. Corollary 6.6.1 Let the assumptions of Theorem 6.6.2 hold. Suppose that M(y] is monotone nonincreasing in y. Then the sequence {vn} with VQ = v, given by vn+i = vn + Bnf(vn), is well-defined, m.onotone nondecreasing such that limr^oo vn = p, and is the minimal solution of (6.53).
Copyright © 2002 Marcel Dekker, Inc.
188
CHAPTER 6. APPLICATIONS TO NUMERICAL
ANALYSIS
The case of most interest is when p — r because then the sequences {vn},{wn} constitute lower and upper bounds for the unique solution of (6.53). The following uniqueness result is of interest.
Theorem 6.6.3 Suppose that f(y)-f(x)0. Then if (6.53) has either maximal or minimal solution in \v,w\, then there are no other solutions in
Proof. Suppose r G \v, w\ is the maximal solution of (6.53) and u e [v.r] is any other solution of (6.53). Then 0=
f(r)-f(u)
Since N(u)~l > 0, it follows that r > u and hence r = u. A similar proof holds if the minimal solution exists. The proof is complete. D
6.7
Monotone Approximations
Consider the problem of finding the solutions of
Ax = /(z),
(6.57)
where A is an n x n matrix and / € C[IRn, IRTO], which arises as finite difference approximation to nonlinear differential equations. If A is nonsingulai, writing F(x) — f ( x ) — Ax = 0, one can study existence of multiple solutions by employing the method of upper and lower solutions and the monotone iterative technique described in Section 6.6. In this section we extend such existence results to equation (6.57) when A is singular. For convenience let us split the system (6.57) and write it in the form (>hOi = / i ( u » , M P i , M 9 i ) ,
(6.58)
where for each z, 1 < i < n, u — (uj.. [u]pi, [u]qi} with pi + ql = n— 1 and (Au)i represents the ith component of the vector Au. As before, a function / 6 C[]R'S, IR'S] is said to be mixed quasi-monotone if, for each z, /,• is monotone nondecreasing relative to u Pi components and monotone nonincreasing with respect to [u]qi components. Let v,w G IRS be such that v < w. Then v,w are said to be coupled quasi lower and upper solutions of (6.57) if
Coupled quasi-extremal solutions and solutions can be denned with equality holding. We are now in a position to prove the following result.
Copyright © 2002 Marcel Dekker, Inc.
6.7. MONOTONE APPROXIMATIONS
189
Theorem 6.7.1 Assume that (i) / G C[IRS,IRS] and f is mixed quasi-monotone; (ii) v.w are coupled quasi lower and upper solutions of (6.57); (iii) fi(v.i, [u]pi, [u]qi) - f i f a , [u] pi , [u]qi) > -Mi(ui - Uj) whenever v 0, for each i; (iv) A is an n x n singular matrix such that A + M = C is nonsingular where M is a diagonal matrix with Mi > 0 and C"1 > 0. Then there exist monotone sequences {vn}, {wn} such that vn ^> p,wn -* r as n —> oc and p:r are coupled quasi- extremal solutions of (6.57) such that if u is any solution of (6.57), then v] since the matrix C is nonsingular. Furthermore, we have Av < F(v,w),Aw > F(w.v], and F is mixed monotone. Consequently we can define a mapping T such that T[?/, \ J L - U and easily show, using the fact that C~l > 0, that (a) v < T[v,w],w > T[w,v]] (b) T is mixed monotone on [v.w]. Then the sequences {vn},{u}n} with VQ = V,WQ = w can be defined as follows: = T[vnj wn], wn+i = T[wnj vn]. Furthermore, it is evident from the properties (a) and (b) that {vn}, {wn} are monotone such that
^o < ^i < • • • < vn < wn < . . . < w\ < WQ. Consequently, lim vn = p, lim wn = r
n—>oo
n—>oo
exist and satisfy the relations (6.60) By induction, it is also easy to prove that if (111,1*2) is a coupled quasisolution of (6.57) such that v < 111,112 < w, then vn < u\,u<2 < wn for all n and hence (p, r] are coupled quasi-extremal solutions of (6.57). Since
Copyright © 2002 Marcel Dekker, Inc.
190
CHAPTER 6. APPLICATIONS
TO NUMERICAL
ANALYSIS
any solution u of (6.57) is a coupled quasi-solution, the conclusion of the theorem follows and the proof is complete. D The case of most interest is when p — r, because then the sequences {vn},{wn} constitute lower and upper bounds for the unique solution of (6.57). The following uniqueness result is thus of interest. Corollary 6.7.1 If in addition to the hypotheses of Theorem 6. 7.1, we assume for each i, that f i ( X i , [x] pi , [y]qi) - f i ( y i , [y] p ., [*]J < [B(x - y}}^
(6.61)
where B is an nxn matrix such that (A — B] is nonsingular and (A — B)~l > 0. Then u = p = r is the unique solution of (6.57) such that v < u < w. Proof.
Since p < r. it is enough to prove that p > r. We have by (6.61)
\A(r ~ p}]r < /t(r?, [r] p?; , \p]qi) - ft(Pi, [p] pl , [r]9J < (B(r - p}^ Consequently, (A-B)(r- p) < 0. which implies r < p. D If qi = 0 for each i, then Theorem 6.7.1 shows that r, p are maximal and minimal solutions of (6.57) and Corollary 6.7.1 gives the unique solution. If / does not possess the mixed quasi-monotone property, we need a different set of assumptions to generate monotone sequences that converge to a solution. This is the content of the next result. Theorem 6.7.2 Assume that (iv) of Theorem, 6.7.1 holds. Further, suppose that v. w 6 IRn such that v < w, Av< f(v)-B(w-v), -B(x
Aw> f ( w ) + B(w-v),
~y}< f(x] - f(y) < B(x - y]
(6.62) (6.63)
whenever v < y < x < w, B being an n x n matrix of nonnegative elements. Then there exist monotone sequences {vn}, {wn} that converge to a solution u of (6.57) such that
provided that (A — B) is a nonsingular matrix. Proof.
We define (6.64)
Copyright © 2002 Marcel Dekker, Inc.
6.7. MONOTONE APPROXIMATIONS
191
It is easy to see that F(y, z) is mixed monotone and -B(z ~z}< F(y, z) - F(y, z} < B(y - y}
(6.65)
whenever z, z,y,y £ [v, w] and z < z, y < y. In particular, we have F(y,z)-F(z,y)
= B(y-z).
(6.66)
From (6.64) we obtain -B(w-v)
Similarly Aw > F(w,v). Finally, it follows from (6.64) that F(x,x) = f ( x ) . Consider now for any 77, /i 6 v,w],
the linear system given by Cu = G(rj,n) where C — A -f M, M being the diagonal matrix with Mi > 0 and for each i, G,(r),Li) = Fi(Ti,fj.) + Mi7ii. Proceeding as in proof of Theorem 6.7.1, we arrive at Ap = F(p, r),
Ar = F(r, p ) .
Using (6.65), we see that A(r -p} = F(r, p] - F(p, r) = B(r - p) and this implies u = r — p is a solution of (6.57). The proof is complete. D
Corollary 6.7.2 If in addition to the hypotheses of Theorem 6.7.2 we also have f(x)-f(y)
then u is the unique solution of (6.57).
Copyright © 2002 Marcel Dekker, Inc.
192
CHAPTER 6. APPLICATIONS Proof.
TO NUMERICAL
ANALYSIS
If u is another solution of (6.57), we get A(u - u] = f ( u ) - /(u) < C(u)(u - u),
which yields u — u. Similarly, u < u and hence u is the unique solution of (6.57). D Equations of the form (6.57) arise as finite difference approximations to nonlinear partial differential equations as well as problems at resonance where the matrix is usually a singular, irreducible M-matrix. For such matrices the following result is known. Theorem 6.7.3 Let A be an n x n singular irreducible, M-matrix. Then (i) A has rank (n — I}; (ii)
there exists a vector u > 0 such that Au = 0;
(iii) Av > 0 implies Av = 0; (iv) for any nonnegative diagonal matrix D, (A + D] is an M-matrix and (A + D}~1 is a nonsingular M-matrix, if da > 0 for some i.l < i < n. As a consequence of Theorem 6.7.3, if we suppose that A in (6.57) is n x n singular irreducible, M-matrix, then (A + M) is a nonsingular A/matrix. Therefore assumption (iv) of Theorem 6.7.1 holds since a nonsingular M-matrix has the property that its inverse exists and is greater than or equal to zero. Furthermore, in some applications to partial differential equations, the function / in (6.57) is of a special type, namely /(«) = (/i (HI), 72(^2)5 • • • ) fn(un))- In this special case lower and upper solutions such that assumption (ii) of Theorem 6.7.1 holds whenever we have limsup f i ( u i ) S i g ( u i ) < 0 for each i.
I-U/HOO
In fact, by Theorem 6.7.3, there exists a £ > 0 such that KerA — Span(£), and hence we can choose a A > 0 so large that /(AC) < 0 and /(-A£) > 0. Letting v = —\£,w = A£ we see that v < w.Av < f ( v ) and Aw > f ( w ) . Assumption (iii) is simply a one-sided Lipschitz condition, and in assumption (6.61) B is a diagonal matrix.
6.8
Problems
6.1 Show that p(G'(x*)) = 0 where G(x] = x - (F1 ( x ) ) ~ l F ( x ) and a:* is a simple root of F ( x ) — 0.
Copyright © 2002 Marcel Dekker, Inc.
6.8. PROBLEMS
193
6.2 Show that, under the hypotheses of Theorem 6.3.4, one has HF'(x)- 1 (F(y) - F(x) - F'(x}(y - x)) || < |||x - y\\2. 6.3 Show that if in the Newton-Kantorovitch theorem one supposes llF'(x)"" 1 1 bounded for all x 6 H n , then ||xn — x*|| < c||x n _i — x*||2. 6.4 Show that in the hypothesis of Theorem 6.3.5, the error satisfies the inequalities (6.30) and (6.31). 6.5 Suppose that xn e IR s ,n > 0 and ||Axn|| < £*""_ ||Axn-i||, where £ n , is a positive converging sequence with to = 0 and limn^oo tn = t*. Show that xn converges to a limit x*. 6.6 As in the previous exercise suppose that ||Axn|| < A*n (||Axn-i||)7 71, — 1
with ^J
< 1. ZQ-1Z2
6.7 Show that the solution of zn+\ = l_2z n is given by zn = 1 — (1 — 2;io) 1//2 coth(A;2 n ), with k appropriately chosen. 6.8 Find the constant k in the previous problem and deduce that for Newton's method one has:
where
6.9 Obtain the result of Theorem 6.3.3 by considering the first integral vvith 20 = \- (Hint: in this case the first-order equation becomes zn+\ = 6.10 Consider the iterative method xk+i = fJ.[XG(xk) + (1 -
X)G(xk,xk-i)]
where A, /u e [0, 1] and G, G are defined as in Theorem 6.3.6. Show that // and A can be chosen such that the convergence becomes faster. 6.11 Solve equation (6.47) directly and show the growth of the errors. 6.12 Obtain the relations (6.48), (6.49), and (6.50). 6.13 Show that the sweep method is equivalent to the Gaussian elimination of the problem Ay — g when the problem 6.47 is stated in vector form (see (6.46)).
Copyright © 2002 Marcel Dekker, Inc.
194
6.9
CHAPTER 6. APPLICATIONS TO NUMERICAL
ANALYSIS
Notes
The discussions of Sections 6.1 to 6.3 have been introduced only to show examples of application of difference equations to numerical analysis. More details can be found in the excellent books by Ortega and Rheinboldt [140] and Ostrowsky [142]. Theorem 6.3.3 is a simplified version of the original one, see [137, 140], while the estimates given before 6.3.5(b) are new. For other estimates of the error bounds for the Newton's method and Newtonlike methods, see also Meil [124, 125], Yamamoto [184], and Potra [154]. For the effect of errors in the iterative methods, see Urabe [176], A very large source of material on the problem discussed in Section 6.4 can be found in Gautschi's review paper [69]. Theorem 6.4.1 has been taken from Olver [136]. A detailed analysis, in a more general setting, of the Miller's algorithm is given in Zahar [185]. For an extension to three terms matrix equations, see Ahlbrandt and Patula [11]. Applications to numerical methods for ODE's can be found in Cash's book [33], while a large exposition of applications as well as theoretical results are in Wimp's book [180] (see also Mattheji [120]). The sweep method can be found in the Godunov and Ryabenki's book [76], where it is also presented for differential equations. An improvement of the Olver's algorithm can be found in Van der Cruyssen [55]. An application of the "sweep" method to the problem of Section 6.4 can be found in Trigiante and Sivasundaram [175]. The contents of Section 6.6 are adapted from Ladde and Vatsala [66] and Ortega and Rheinboldt[139, 140]. The material of Section 6.7 is taken from [106], but see also [98, 101, 66].
Copyright © 2002 Marcel Dekker, Inc.
Chapter 7
Numerical Methods for Differential Equations
7.0
Introduction
Numerical methods for differential equations are one of the very rich fields of application of the theory of difference equations where the concepts of stability play a prominent role. Because of the successful use of computers to solve difficult problems arising in applications such as multiscale problems, the connection between the two areas has become increasingly important. Furthermore, in a fundamental work Dahlquist emphasized the importance of stability theory in the study of numerical methods of differential equations. In this chapter we shall consider some of the most relevant applications. In Section 7.1 we discuss linear multistep methods again and show that the problem can be reduced to the study of total or practical stability when the roundoff errors are taken into account. In Section 7.2 we deal with the case of a finite interval where we shall find a different form of Theorem 2.8.3. Section 7.3 considers the situation when the interval is infinite restricting in the linear case. The nonlinear case when the nonlinearity is of monotone type is investigated in Section 7.4, while in Section 7.5 we show how one can utilize nonlinear variation of constants formulae for evaluating global error. Sections 7.6 and 7.7 are devoted to the extension of previous results to partial differential equations via the method of lines, which leads to the consideration of the spectrum of a family of matrices in order to obtain the right stability conditions. The problems given in Section 7.8 complete the picture. 195 Copyright © 2002 Marcel Dekker, Inc.
196
7.1
CHAPTER
7. NUMERICAL
METHODS
Linear Multistep Methods
We have already seen that a linear multistep method (LMM), which approximates the solution of the differential equation
y' = f(t,y)>
y(*o) = i/o,
(7.1)
is defined by p(E)zn-h
= 0,
(7.2)
where p(E) and cr(E) are defined in Section 2.8. For convenience we shall suppose that / is defined on [0, T] x H and it is continuously differentiable. The general case can be treated similarly except for some notational difficulties. The values of the solution y(t) on the knots tj = to + jh satisfy the difference equation p ( E ) y ( t n ) - ha(E)f(tn, y ( t n } } = rn
(7.3)
where rn is the local truncation error. The global error
en = y(tn) - zn
(7.4)
then satisfies the difference equation p(E)en - ha(E] ( f ( t n , zn + en] - f(tn, zn)) = rn.
(7.5)
In practice, equation (7.2) is solved on the computer and instead of (7.2) one really solves the perturbed equation p(E}zn - ha(E)f(tn, zn) = e n ,
(7.6)
where en represent the roundoff errors. The equation for the global error then becomes p(E}en - ha(E] ( f ( t n , zn + en] - /(t n , *„)) = wn,
(7.7)
wn = rn - en-
(7.8)
where It is worth noting the different nature of the two kinds of errors. If the method is consistent, rn depends on some power of h, greater than one, while en is independent on such a parameter (it depends on the machine's precision). For simplicity, we assume that en is bounded. The equation (7.7) can be considered as the perturbation of the equation p(E)en - ha(E] ( f ( t n , zn + en] - f ( t n , zn}} = 0, which has the trivial solution en = 0.
Copyright © 2002 Marcel Dekker, Inc.
(7.9)
7.1. LINEAR MULTISTEP METHODS
197
The problem is then a problem of total stability or of practical stability if the roundoff errors en are taken into account. One needs to study equation (7.9) and verify whether the zero solution is uniformly asymptotically stable and then apply, for example, a theorem similar to 4.11.1 in order to get total stability. This has been done indirectly in the linear case. Recently some efforts have been devoted to certain nonlinear cases. The techniques used to approach the problem are essentially of two types. One approach uses the Z-transform (with arguments similar to those used in the proof of Theorem 2.8.3 (see for example [132]) while the other transforms the difference equation of order A: to a first-order system in R n . We shall follow the latter approach. Let us put f(tn, zn + en) - f(tnj Zn) - cnen.
(7.10)
Equation (7.7) can be written (we take ak = 1) as fc-i en+k - hfikcn+ken+k + ^(oij - h(3jCn+j}en+j
- wn.
j=0
or if we suppose that 1 — h/3kcn+k ^ 0 for all values of indices, as
en+k
_ -
- >
-
——
w
-en+j
— h/3kcn+k
k-l _ v~^ j n+j - 2_^ j=0 j=0 fc-1 k-l . , », V" ^(")
1 — h(3kcn+k
k-l
E
E
w
a e
i
aj
j
n
1
_
j=0
"^
where , n _
1 - h(3kCn+k
By introducing the fc-dimensional vectors
En
—
Copyright © 2002 Marcel Dekker, Inc.
e
ri K>
^
198
CHAPTER 7. NUMERICAL
METHODS
and the matrices /
0
0
\
0
(7.12)
1 -ttfc-1 I
v/ o
0
\
(7.13) (n)
\ \
equation (7.7) reduces to the form pi
/ A
•t-^n+l — I71
hBn}En + W.
(7.14)
The problem is now to study total stability for the zero solution of this equation, which depends crucially on the nonlinearity of / contained in the matrix Bn. Historically this problem has been studied under some simplifying hypothesis such as infinite precision arithmetic, single-scale problems, multiscale problems around an asymptotic stable critical point, etc. Each of the above assumptions leads us to important simplification of equation (7.14). For example the infinite precision hypothesis leads to assume that \\Wn\\ —> 0 as h —> 0. Moreover, when h is kept fixed, single-scale problems have N — T/h not very large and the opposite is true in the case of multiscale (stiff) problems. Since the latter circumstance is very similar to the case where T is infinite, for sake of simplicity wre shall group the above assumption under the following categories: finite interval, infinite interval with / linear, and infinite interval with / of monotone type.
7.2
Finite Interval
If the interval of integration (to, to + T) is bounded and the precision is infinite, we take h = ^ and n = 0 . 1 , . . . ,7V. This implies that h becomes smaller arid smaller as N increases and the quantity hBnEn. like the term W n , can be considered as small perturbation of the equation En+l = AEr
(7.15)
The eigenvalues of the matrix A are roots of the characteristic polynomial p(z) and the requirement of the stability of the null solution of (7.15) is equivalent to the notion of 0-stability. We cannot assume asymptotic stability of the zero solution and apply Theorem 4.11.1 because one of the
Copyright © 2002 Marcel Dekker, Inc.
7.2. FINITE
INTERVAL
199
conditions of consistency imposes p(l] = 0, which means that at least one of the eigenvalues of A is on the boundary of the unit disk in the complex plane. The analysis of the stability of the zero solution of (7.14) needs to be done directly. This is not difficult if we use (4.38). In fact n-l n
(7.16)
En = A E0 3=0
Taking the norms, we get
\\En\\ < 3=0
Now suppose that the zero solution of (7.15) is stable (that is demanding that the method is 0-stable). This means that the spectral radius of A is one and moreover the eigenvalues on the boundary of the unit circle are simple. It follows then that the powers of A are bounded. Let us take for simplicity that || A7' || < I . j = 1 , 2 , . . . , TV (see also Theorem A.6.2). The inequality (7.16) becomes
\\EN\\ < Poll + £ j=o
h\\BJ\\\\EJ\\).
By Corollary 1.6.2 we obtain <
\\E0\\
<
\\E0\\e
,|| exp h
\\BT\
(7.18) 3=0
where L — maxi< T
(7.19)
Then (7.18) becomes \\EN\\ <\\E0\\eLT+eehL~li Usually the initial points are chosen such that lim U-Ebll = 0.
N—>oo
Copyright © 2002 Marcel Dekker, Inc.
(7.21)
200
CHAPTER 7. NUMERICAL
METHODS
Hence, taking the limit as h —» 0, we have lim \\EN\\ < v(eLT - 1) lim € *L T ^ . /i-o " "~ /i-+o e^ - 1 from which it is clear that if e 7^ 0 (i.e. when the roundoff errors are considered), the right-hand side is unbounded. It is possible to derive for H-EWII a lower bound with a similar behavior. This means that the zero solution is not practically stable. If the roundoff errors are not considered, and if the method is consistent (sec Definition 2.8.1) then e = 0 and r(h) — O(hp+l),p > I and therefore lim||£ n ||=0.
/i—>0
(7.22)
This implies that the null solution is totally stable. It is possible to give a more refined analysis of (7.16) by considering in the limit only the components of the matrix A (see Appendix A), corresponding to the eigenvalues on the unit circle, that have nonzero limit for n —•> oo (see Problem 7.1). This analysis allows us to weaken the conditions that we impose on the local error. If, as usually happens in the modern program packages designed to solve the problem, one allows the stepsize to vary at each step, the difference equation for the global error is no longer autonomous even for autonomous differential equations. Gear and Tu [72], for example, obtain the difference equation En+l = S(n}En + Wn,
(7.23)
where the matrix S(n) takes into account many other factors that define the method. It is shown that S(n) = S(n) + hnS(n).
(7.24)
Suppose that these two conditions hold: (1) (2)
where $(n, no) is the fundamental matrix of the homogeneous equation derived from (7.23), namely En+i = S(n}En. The first condition (see Theorem 4.2.1) is equivalent to asking that the zero solution of En+l = S(n}En
(7.25)
is uniformly stable. The second condition is related to the bouridness of the Lipschitz constant of f ( t . y ) .
Copyright © 2002 Marcel Dekker, Inc.
7.3. INFINITE
INTERVAL
201
From (4.38) we have N-l
EN =
and hence it follows that \\EN\\ < k0\\E0\\ + k0
- l l + \\Wj\\).
By Corollary 1.6.2 we obtain N-I \\EN\\
< fco||£o
N-I / N-I + k0 ^ ||Wa||exp I k0ki ^ s=n 0
y
j=s+l
<
from which follows that if ||£^o|| and ZlsLno II ^5 II tend to zero as h —>• 0, the method is converent.
7.3
Infinite Interval
In practice one uses methods with h bounded away from zero. This means that it is no longer true that h —> 0 as n tends to infinity. The term hBnEn cannot be considered as a perturbation, especially when the norm \\Bn\\ is very large (in stiff equations). For such problems it is necessary to consider the quantity hBnEn as a principal component of equation (7.14). Because h is taken either fixed or bounded away from zero, there are problems (stiff or multiscale) where n may assume very large values. When the term hBnEn is taken into account, the equation is no longer linear because the elements of the matrix Bn depend on the solution. The problem becomes a difficult one. It has been studied extensively in the linear case f(y] = Xy when Re\ < 0. In this case, the matrix Bn becomes independent on n, namely
(7 26)
-
where bT =
(7.27)
and the equation (7.14) reduces to En+i = (A + hB)En
Copyright © 2002 Marcel Dekker, Inc.
(7.28)
202
CHAPTER 7. NUMERICAL
METHODS
whose solution is, taking no — 0, n-l
En = CnE0 + ]T Cn-j+lWj.
(7.29)
3=0
The behavior of En will be dictated by the eigenvalues of the matrix C, which are the roots of the polynomial iv(z,q) defined in Section 2.8. The set D of values of q = hX for which the zero solution of the unperturbed equation En+l = CEn (7.30) is asymptotically stable is said to be the absolute-stability region of the method. As in the previous case, since the roundoff errors EJ are only bounded, it is more desirable, according to Theorem 4.11.1, to require the asymptotic stability of En = 0 in (7.30). This implies that q must be strictly inside the absolute-stability region. A very large effort has been made to study the absolute stability for different a.t and /3j, that is, for different classes of methods. Special importance is given to methods for which the absolute stability region is unbounded and contains the complex left-half plane (/i-stable methods) because in this case no restrictions are to be imposed on the parameter h in order to restrict hX to be inside that region. We will not go into the details of this work. We are only interested in the techniques used relative to difference equations. In recent years, the case of nonautonomous linear equations has also been discussed. This is very important because in the modern software packages to solve differential equations, one allows the step-size to vary at each step. In this case, the difference equation is no longer autonomous and the considerations based on the eigenvalues of the matrices C(n) are no longer enough to ensure the asymptotic stability (compare the counterexample given in Section 4.4). One needs to impose some conditions on the norms of matrices ||C'(n) in order to get information on the fundamental matrix <$(n,no) of the equation En+i = C(n}En.
(7.31)
Once this has been achieved, we can use the formula (4.41) and obtain n-l
En = $(n, no)E0 +
$(n,j + \)Wj-
( 7 - 32 )
Suppose that the zero solution of (7.31) is uniformly asymptotically stable, then by Theorem 4.2.2, there exist a, 77 > 0 and 77 < 1 such that
Copyright © 2002 Marcel Dekker, Inc.
7.4. NONLINEAR CASE
203
It then follows that ll^nll < ^n-nol|£o|| +a ]T rjn->-l\\W3l j=no
from which one derives at once the stability of En = 0 for the perturbed equation. So far we have treated the case of a single equation. The case of autonomous systems y' = Ay, y(tQ) = yo, (7.34) can be treated similarly. In fact, suppose that the matrix A can be reduced to the diagonal form by means of a similarity transformation A — T~1KT where A — diag(\i,\2, . . . ,\k)- Then the system (7.34) reduces to uncoupled scalar equations and the condition becomes that each h\i must be inside the absolute stability region.
7.4
Nonlinear Case
The study in the nonlinear case of equation (7.14) is difficult and has been made only for nonlinearities of a special kind, namely, monotone. The techniques used require essentially to bound norms of the matrix A -f hBn. We shall be content to present only the case of the implicit Euler method and the one-leg methods, since they are good examples of the use of the equations employed here. Let / : [0, oo] x IRS —> IRS and suppose that for w, v e R, (u - v } T ( f ( t , u) - f ( t , v}) < fi\\u - v\\2,
(7.35)
with fj, < 0. The difference equation (7.14) becomes in this case en+i - en - h (f(tn+i,zn+i + e n+ i) - f(tn+i,zn+\)) = wn.
(7.36)
By multiplying both sides by e^+l we have \\en+i II 2
< <
||en||||en+1|| + Mien-fill 2 + ||en+i|||K||,
(7-37)
where the Cauchy-Schwarz inequality \aTb\< \\a\\\\b\\ has been used. From (7.37) one gets
Copyright © 2002 Marcel Dekker, Inc.
(7.38)
204
CHAPTER 7. NUMERICAL METHODS
By using Corollary 1.6.1, we then obtain n-n 0
n
-!
/
1
\n-j-l
(7 40)
'
Since the quantity 77 = ^^ is less than one by hypothesis, the uniform stability of the solution en — 0 follows. The previous arguments can be generalized to the class of methods defined by p(E)yn - hf(a(E}tn, a(E}yn) = 0.
(7.41)
This class of methods was proposed by Dahlquist who named one-leg methods. There is a connection between the solutions of the difference equation (7.2) and the solutions of (7.41) (see Problems 7.6, 7.7). For the sake of simplicity, we shall suppose / : [0,T] x IR —>• 1R. In this case the quantities in (7.41) are scalars. The error equation for (7.41) is p(E)en - h ( f ( a ( E ) t n , a(E}yn + cr(E}en] - f(a(E)tn, a(E}yn}} = wn. (7.42) Multiplying by <j(E)en one obtains cr(E)en • p(E}en < h/j,\a(E}en\2 + wn • cr(E)en. Let us switch now to the vectorial notation and suppose that there exists a symmetric positive definite matrix G such that the Liapunov function
Vn = En GEn satisfies the inequality Vn+l -Vn< 2a(E)en • p(E)en.
(7.43)
It then follows that Vn+i-Vn
< 1a(E)en • p(E)en en\ + 2\a(E}en\\wn\.
By considering that (here || • | 2 is used)
i=0
we have: by setting (Eto A2 Vn+l - Vn < &(\\En+l\\ + ||^n||)kn +
Copyright © 2002 Marcel Dekker, Inc.
2
^(\\En+l\\ + \\En\\)2 .
(7.44)
7.5.
OTHER TECHNIQUES
205
Since \\En\\ < HC'^IIHG 1 / 2 ^!! - \\G-l/2\\Vn/2 the relation becomes
Vn+1 -Vn< We let (5||G- 12 || = a. Consequently
from which follows the estimate T/V2 /
a
\'
n—no
/ a
*\~^ I
n
2\
~J~l
~*~ ^^f~ |
i-/*Y j=o \ i - f c V / i
7 LLCL
L. id
l - i
7 Lid"
I
which gives a bound for ([EViHcThe existence of the matrix G can be established if the method is Bistable. See Dahlquist [48].
7.5
Other Techniques
The formula (4.52) can be used to evaluate the global error. In fact if x(n, no, XQ) is the solution of the unperturbed problem corresponding to (7.2) and 7/(n,no,xo) ig the solution of the perturbed problem corresponding to (7.3), then the difference En = y(n, no, XQ) — x(n, no, XQ) derived from (4.52) gives the global error. We have already used this result in the linear case (see (7.16)). In applications one uses a similar formula obtained by using the method of variation of parameters of the original differential equation.
Theorem 7.5.1 Let (1) y(t] be the solution of (7.1); (2) 7/0 — 20; zii • • • , zn be approximations of y(i] at the points £Q, £1,. • • , tnj (3) p ( t ) be a sufficiently smooth function that interpolates the points zi so that p(t7j) = Zi i = 0 , 1 , . . . , n. Then En = y(tn) — zn satisfies the relation En = - I" $(*n, s,P(s)}\p'(s} - f ( s , p ( s ) ) ] d s , Jto
Copyright © 2002 Marcel Dekker, Inc.
(7.45)
CHAPTER 7. NUMERICAL METHODS
206
Proof. Let s G { t o , t n } and y(to,s,p(s}} be the solution of (7.1) with initial value (s,p(s)). It is known in the theory of differential equations that dy(tn,s,p(s)) ds and
dy(tn,s,p(s)) dp Consider the integral /
= -En.
y(tn,s,p(s))ds = y(tn,tn,p(tn))
This integral also is equal to ,
dp
'to
which completes the proof. D The formula (7.45) can be used to obtain methods with higher order, to find the order of known methods, and to study new methods. See [150, 179].
7.6
The Method of Lines
Consider the following problems du(x.t) di u(0,1}
d2u(x,t)
du(x,t) dt
du(x.i]
(7.46)
dx2 -0,
u(x,Q) = g(x]
and
u(0,t)
dx = 0,
(7.47)
' u(x,0) = g(x},x > 0.
Let us discretize the interval (0,1) by taking Xi = ih. i — 0 . 1 , . . . , N + 1 and consider the vectors U(t} = (u(xi,t),..., U(XN, t))T, G = ( g ( x \ } . . . . , g(xN))J where u(x^t) are approximations of the solution along the lines x = x,. We approximate the operators -j^ and ^ by central differences and backward differences respectively. By introducing the matrices / -2 1 AN =
Copyright © 2002 Marcel Dekker, Inc.
0
1 0 ... -21 0
...
0 \ 0 (7.48)
207
7.6. THE METHOD OF LINES and / 1 -1
1
(7.49) -1 1 / NxN
the two problems can be approximated by
= G,
(7.50)
and
(7.51) We have approximated the two problems of partial differential equations with two problems of ordinary differential equations. If we discretize the time, using, for example, the explicit Euler method and try the results on absolute stability, we get two different results, namely, one correct result for problem (7.46) and one incorrect result for problem (7.47). In fact, the eigenvalues of AN and BN are k = 1 , 2 , . . . , TV,
Xk = -2 + 2cosTV + 1' // fc = 1,
k = 1,2, . . . , 7 V ,
(7.52) (7.53)
and the region of absolute stability for the explicit Euler method is D = {z£C:\z + l\
(7.54)
In order to have stability of the method we must have (7.55) for the first case and (7.56)
for the second case. From (7.55) and (7.52) it follows that the condition of stability for the first problem is 2'
and for the second one is
Copyright © 2002 Marcel Dekker, Inc.
At
< 2.
(7.57)
(7.58)
208
CHAPTER 7. NUMERICAL METHODS
It happens that (7.57) agrees with the Courant Friedrichs and Lewy condition, while (7.58) does not agree with the correct condition, which is ~ < 1(7-59) ' Ax The reason for the discrepancy lies in the fact that the ordinary differential equations (7.50) and (7.51) depend on JV, which tends to infinity when Ax tends to zero. This implies that when we study the error equation, for Ax and At tending to zero, the dimension of the space IR^ and therefore of the matrices AN and BN increases. We shall see in the next section how to obtain the right conditions.
7.7
Spectrum of a Family of Matrices
Consider a family of matrices {Cn}n£N+, where Cn are n x n real matrices. Definition 7.7.1 The spectrum of a family of matrices {Cn} is the set of complex numbers A such that for any e > 0, there exists n E N^ and x E C n , x ^ 0 such that
\\Cnx - Xx\\ < e\\x\\.
(7.60)
The spectrum of [Cn] will be denoted by 5({Cn}), or S when no confusion will arise. It is obvious that the set S of all eigenvalues of all matrices of the family is contained in S. The elements of the set 5 \ S are called quasi-eigenvalues. We now list some properties of S, without proof. PI S is a closed set. P2 If the matrices are normal, then S = S where E is the closure of S. P3 If P is a compact set of the complex plane and if P Pi S — 0, then sup \(Iz-Cnrl\\ < oo.
(7.61)
P4 Let S be compact and 5 C Q where il is an open, simply connected set of C. Moreover let / be an analytic function in O. Then
S({f(Cn)}) = f ( S ( { C n } ) )
(7.62)
q = sup|A|.
(7.63)
P5 Let A65
If q < 1, one has for every n, m E N^ imi < where k is independent on m and n.
Copyright © 2002 Marcel Dekker, Inc.
fc,
(7.64)
7.7. SPECTRUM OF A FAMILY OF MATRICES
209
Let us now find the spectrum of the family {Cn}: a
7
(7.65) -. 7 (3 a /
where a, /3,7 are real and we shall suppose for simplicity that |/3/7J < 1. Let be Q = S\ S. The elements of Q are the quasi-eigenvalues. Theorem 7.7.1 The set of complex numbers A, such that the zero solution of the difference equation -yxi+i + (a - \}xi +
0
(7.66)
is asymptotically stable, is contained in S({Cn}). Proof.
The characteristic polynomial of (7.66) is 7r2 + (a - A)r + /3 = 0
(7.67)
and to get asymptotic stability it must be a Schur polynomial (see Theorem 2.7.1). Suppose it is. Then taking as vector x the vector made up with the first n components of the solution of problem (7.66), one has Cnx - \x — (0, . . . , 0,
It follows that \\Cnx - \x\\ =
where r\ and r^ are the roots of (7.67) which, for simplicity, are supposed to be simple and ci,C2 are deduced from the initial conditions. That is 1 1 C2 = n -r 2 I — r\ We then get \\CnX -
n+l
In -
r' 1
—
where we have considered that ||x|| > 1. The quantity multiplying ||x can be made arbitrary small if \r\ and r^ arc less than 1 . Similar considerations can be made if \r\\ — \r^\. One can show that if \r\ or \r^\ are greater than 1, the corresponding A is no part of the spectrum and A ^ E (see Problem 7.9). n The next theorem explicitly furnishes the boundary of S.
Copyright © 2002 Marcel Dekker, Inc.
210
CHAPTER 7. NUMERICAL METHODS
Theorem 7.7.2 The boundary of S is given by x = Q• + (0 + 7) cos 0,
y
= (7 - /3) sin 0
(7.68)
where X = x + iy, and 0 < $ < 27r. Proof. The proof reduces to finding for which values of A the polynomial (7.67) is a Schur polynomial. This can be done easily by using Theorem B.I.I of Appendix B, obtaining the conditions (7.68). d The set S has then the ellipses with center (a, 0) and semiaxes (j3 + 7) and (7 — j3) as boundary. By considering that the eigenvalues AJ,, °f the matrices Cn, are given by X^} = a + 2(3 7 ) 1 / 2 cos ^. itfollowsthat AJ; n) 6 S. Particular cases are: (a) a = —2,3 = 7 = 1; in this case the family {Cn} coincides with the family {An} defined by (7.48). The spectrum S({An}) is then the segment -2 4-2 cos 0, O<#
y = - sin 0.
(7.70)
Once the spectrum of the family has been obtained, the correct stability conditions can be derived. In the case where the ordinary differential equations are discrctized by using the Euler method, for example, instead of (7.55) and (7.56). one imposes At
~" ' }}CD
(7.71)
^S({Bn}) c D
(7.72)
for the first problem and
for the second problem. In fact we have: Theorem 7.7.3 Suppose that the problems (7.50) and (7.51) are solved with the explicit Euler method. If (7.71) and (7.'72) hold, then the resulting difference equations are stable for all values of n. Proof. Let Us. s = 0. 1 . . . . be an approximation of U(ts}. The Euler method will produce the difference equations
Us+i = U, +
Copyright © 2002 Marcel Dekker, Inc.
AnUs =(l+ - A
n
U
7.8. PROBLEMS
211
and
respectively. When (7.71) and (7.72) hold, by P4, it follows that the spectrum of the families of matrices {/ + ^z^-n} and < / — ^.Bn\ are contained in the unit circle. This implies, by P5, that all the powers of the matrices of the families are uniformly bounded, and this implies the stability. D One should consider, however, that the condition of consistency for the space discretization implies a + /? -f 7 = 0 and the origin is a point of the boundary of both S and 3D. This implies that (7.71) and (7.72) cannot be strictly satisfied. For some class of matrices, for example normal matrices, this does not create any problem. Note that condition (7.71) is not more restrictive than the one obtained by using only the eigenvalues because in this case, the matrices are normal and the spectrum is only the closure of the set of all the eigenvalues. Condition (7.72) is more restrictive because the spectrum is a disk in the complex plane, while the set of eigenvalues is made up of only one point. More generally, a region of absolute stability D defined by the discretization of the variable t and a region 5, which is a function of the spectrum of a family of matrices defined by the discretization of the space variables, will be associated with each method. For the stability the second region must be contained in the first. This approach is also useful because it permits the choice of appropriate discretization of the time as a consequence of the discretization of the space variables.
7.8
Problems
7.1 Suppose that the matrix A has the eigenvalues 1 = \\ > \2 > • • - > XkUsing the decomposition (A. 13) of the matrix, give a bound for \\En\\ in (7.16). 7.2 Show that for the Euler method yn+\ = yn + hfn the region of absolute stability is the circle with center at —1 and radius 1. 7.3 Show that the region of absolute stability of the trapezoidal method zn+i = zn + |(/n + fn+i) is the left-hand plane. 7.4 Find the one-leg correspondent of the trapezoidal method. It is known as the implicit midpoint method. 7.5 Show that the region of absolute stability of the midpoint method zn+2 = zn + 2hfn+i is the segment [—i, i] of the imaginary axis.
Copyright © 2002 Marcel Dekker, Inc.
212
CHAPTER 7. NUMERICAL METHODS
7.6 Suppose that yn satisfies the one-leg equation p(E)yn - hf(a(E}yn} = 0. Show that yn — a(E}yn, satisfies the equation p(E)yn — ha(E)f(yn) = 0. (Hint: the operators p(E) and cr(E) commute.) 7.7 Suppose that {yn} satisfies the equation p(E)yn — ha(E}f(yn) — 0 and P ( z ) and Q(z] are polynomials satisfying P ( z } a ( z ) — Q(z}p(z) = 1. Show that yn = P(E)yn — hQ(E)f(yn) satisfies the one-leg equation p(E}yn —
7.8 Suppose that c.n < -p, (fj, > 0) for all n.3n / 0 in (7.10) and the roots of cr(z) are inside the limit disk. Show that the error en tends to zero. 7.9 Show that in Theorem 7.7.1 if one of the roots of (7.66) has modulus greater than 1, then A does not lie in Q. 7.10 Show that for the matrix (7.65) we have \\Cnx - \x\\ = f3pn-lUn(q) , where p = (/3/7) 1 / 2 and q = (A — a ) / 2 ( l d j } 1 ^ 2 and Un(q) is the Chebyshev polynomial of second species. (Hint: use the results of Section 2.4.) 7.11 Show that the midpoint method cannot be used for \trie time discretization of 7.50. 7.12 Consider the second-order hyperbolic equation Utt - Uxx = 0, U(x, 0) - f ( x ) , (7(0. i) = U(TT, t) = 0 and discretize the space variable obtaining a system of first-order equations,
1 dt
= -1^D2N'W,
Aa
™(0) = '0,
where w = (U.V)T , ;/' = (^-0) T . C7, V, $ G IR^, discrete points in (O.Tr), and 0 A
N
N is the number of
Ax 2 / n 0
7.13 Show that D\^ is normal and find its spectrum. Using this result, show that the midpoint method can be used in this case.
7.9
Notes
The problem of numerical methods for differential equations has been extensively studied in the last 40 years. For important works in this field see Henrici [88, 89] and Dahlquist [45]. The most important reference books on the subject arc by Lambert [107], Butcher [30]. and Hairer ct al. [83].
Copyright © 2002 Marcel Dekker, Inc.
7.9. NOTES
213
The recent book by Brugnano and Trigiante [26] is more oriented toward difference equations. For example, it contains a wide treatment of the notion of spectrum of a family of matrices. The study of nonlinear case was also initiated systematically by Dahlquist [52, 46, 47, 48, 49, 50]. Important contributions have also been made by Odeh and Liniger [134], Nevanlinna and Liniger [131], and Nevanlinna and Odeh [132]. For the class of RungeKutta methods, not treated in this book, see Butcher [29] and Burrage and Butcher [27], [28]. For applications of the theory of difference equations to methods for boundary value problems see Mattheij [119]. Material on the spectrum of family of matrices can be found in Bakhvalov [17], Godunov and Ryabencki [76], and Di Lena and Trigiante [109]. A general treatment in Hilbert space setting of the spectrum of infinite Toeplitz matrices can be found in Hartman and Wintner [87], as well as in the Toeplitz original papers [171]. A related question (the pseudo-spectrum) has been principally studied by Reddy and Trefethen [156] and F. Chaitin-Chatelin et al. [37]. Applications of the enlarged spectrum of symmetric tridiagonal matrices (Jacobi matrices) are found in the theory of orthogonal polynomials (see for example Mate and and Nevai [116] and the references therein).
Copyright © 2002 Marcel Dekker, Inc.
Chapter 8
Models of Real World Phenomena 8.0
Introduction
In this chapter we offer several examples of real world models to illustrate the theory developed, to show how versatile difference equations are and to demonstrate how often the results of discrete models can explain the observed phenomena better when compared to continuous models. Furthermore, the contents of this chapter are also intended to help the practitioners who can look first at the examples and then proceed to read the necessary theory of difference equations. Section 8.1 deals with linear models of population dynamics, sketches the development, and discusses the appearance of population waves. We devote Section 8.2 to the study of nonlinear models of population dynamics including bifurcation and chaotic behavior. In Section 8.3, we consider models arising in the distillation of a binary ideal mixture of two liquids, while in Section 8.4 we discuss models from theory of economics. Models from queueing theory and traffic flow are investigated in Section 8.5. In Section 8.6 we collect some interesting examples dealing with various models.
8.1
Linear Models for Population Dynamics
The dynamics of populations have been extensively studied since Malthus. The object of study is the evolution in time of a group of individuals who follow the simplest and essential life events: they are born, mature, reproduce and die. The group can be of bacteria, animals, or humans. For simplicity, in all the models one usually only considers the female part of the population. Both continuous and discrete models have been proposed. More than the law of mechanics it does nor always seem justified to use in this field continuous models. In fact the usual assumption that the variation 215 Copyright © 2002 Marcel Dekker, Inc.
216
CHAPTER 8. MODELS OF REAL WORLD PHENOMENA
per unit time of the number of individuals is small compared to the total number is no longer valid as in mechanics. Often the results of continuous and discrete models are qualitatively similar, but sometimes, especially in nonlinear models, they are not and the continuous models are unable to explain observed phenomena (see Section 8.2). Let yn be the number of females of a population at time tn. The simplest model, called after Malt 1ms, the Malthusian model is the following 2/n+i = aVn-
yno = yoi
a > 0,
(8.1)
which simply states that the number of newborn individuals, as well as the number of individuals that are deceased in the time interval At n , is proportional to the number of individuals at time tn. The parameter a is called the intrinsic growth rate and is simply the difference between the birth and death rates. The solution of (8.1) is yn = an~n°yo and has been found to be very effective to fit exponential data for populations that are not large. One of the weaknesses of the model is that for n —> oo, yn —> oc, which is impossible due to limitation of the resources. The foregoing simple model does not take into account the age structure of the population, which is important because all the essential life events depend on the age of individuals. A more refined model is the following (often called Leslie model). Let us divide the lifetime L into M parts and then population in groups (or classes) yi(n], y<2 ( n ) , . . . , yi\i(n) such that the group yi(n) is made of individuals whose age a,- satisfies
Considering the unit time equal to the time spanned by a class, one has that yi+i(n 4- 1) is made up of all the individuals in the class i at time n except of those who are deceased (or removed in some way). That is, yi+i(n+l) =/3iyi(n),
i = 1. 2. . . . , M - 1,
where /?7 > 0 is the survival rate of the ith age and M
which states the newborns at time n + 1 as sum of the contribution of the different groups each of which is considered to have an homogeneous behavior in the reproduction. Having the human population in mind, one would expect a, to be zero in the extreme groups and the maximum in some group in the middle. In nature, however, there is a wide range of
Copyright © 2002 Marcel Dekker, Inc.
8.1. LINEAR MODELS FOR POPULATION
DYNAMICS
217
possibilities; for example on = 0 for all groups except one, giving rise to different kinds of behavior. By introducing the vector y(n) — ( y i ( n ) , . . . , ?/A/(n)) T and the matrix
0
x
0
(8.2)
...
o J MxM
0
the model can be written as y(n + 1) = Ay(n),
y(n0) =
(8.3)
where yo is supposed to be known. The solution is y(n) = Anyo (we take no = 0 for simplicity). The behavior of the solution will then follow from the spectral properties of the matrix A. Consider first the case on > 0 and j3i > 0 for all indices. In this case it is easy to verify that AM > 0 (see Sec. A.7). By the Perron-Frobenius theorem (see Theorem A.7.2), it follows that A has a positive simple eigenvalue AI associated with a positive eigenvector u\. The remaining eigenvalues are inside the circle B^ in the complex plane. By using the expression (A.26) for the powers of A and considering that in the present case m\ — 1, one has
An = \\
\n—i+l
_u + k=2i=l
from which it follows that the double sum in brackets tends to zero as n —* oo. Considering that Z\\ is the projection to the eigenspace corresponding to A], one has Any$ « cX^ui where c is a constant. The population tends to grow as A^ and is close to u\. that means that the distribution between the age groups tends to remain fixed. In fact. (8.4)
where u^ is the i — th entry of the vector u\. The vector u\ is called the stable age vector and AI the natural growth rate. Of course the overall population will grow for AI > 1 and will extinguish for \\ < 1. Special cases of interest are those where some c^ can be zero. To make the study simpler, it is useful to change variables. Letting l^ = 1, lk = nto1 A (k = 2 , . . . , M), a, = Ii0ti (i = l,2,...,M),D = diag^h,..., / A / ),
Copyright © 2002 Marcel Dekker, Inc.
218
CHAPTER 8. MODELS OF REAL WORLD
x(n) = D l y ( n ] and B = D
B=
l
PHENOMENA
AD, one verifies that
0*1
Cif2
1 0
0
V 0
\
0
1
which is a companion matrix (see Section 3.4). The model is now x(n+ 1) = Bx(n),
(8.5)
and the characteristic equation of B is then (see (3.20)): \ A/
A
„ \ A/-1
— CL\A
„
\ A/-2
— a2-A
\
n
. . . — &M — 1-^ ~ &M — U-
(a (;\
V*'W
The following theorem from Cauchy is very useful in this case. Theorem 8.1.1 If a, (i = 1.2....M) are nonnegative and the indices of the positive a, have the greatest common divisor 1, then there is a unique simple positive root A I , of the greatest modulus. For a proof, see Ostrowski [141]. Since the eigenvector u\ of B is u\ = (A^" 1 , A f 7 , . . . , 1)T, it follows that til is a positive vector and all the previous results are still valid. When the hypothesis on the indices of Theorem 8.1.1 are not satisfied, then some eigenvalues may have the same modulus of AI giving rise to the interesting phenomenon of population waves. In this case in fact there are oscillating solutions to the model. To see this in a simpler way, let us consider the scalar equation for the population of the first group. This can be seen from (8.5). The first equation of the system gives A/
and from the following equations, choosing the appropriate index n, we obtain xl(n] — x\(n — i + 1). By substitutions one has xi(n + 1) =
which is a scalar difference equation of order M. The characteristic polynomial coincides with (8.6). The solution of (8.8) in terms of the roots of (8.6) is given by (2.37) with A, instead of Z{. If there are two distinct roots with the same modulus, sa AI = el°, \2 = e~ld, one has + other terms.
Copyright © 2002 Marcel Dekker, Inc.
8.2. THE LOGISTIC EQUATION
219
It is possible to find two new constants a and i/j such that c\ — ae1^, 02 = ae~1^, and then x\(n) — 2pnacos(n6 + i/') + other terms, from which follows that x\(n) is an oscillating function. In the general case more than one period can coexist. In the extreme case a^ — 0, i = 1, 2 , . . . , M — 1, OM 7^ 0 a number proportional to M of periods can coexist and for large M a phenomena similar to chaos (see next section) may appear. The population waves have been observed in insect populations.
8.2
The Logistic Equation
The discrete nonlinear model, which we are going to present for the dynamics of populations and which takes into account the limitation of resources, has been used successfully in many areas such as meteorology, fluid dynamics, biology, and so on. Its interest consists of the fact that, in spite of its simplicity, it presents a very rich behavior of the solutions that permits to explain and predict a lot of experimental phenomena. Let N(n) be the number of individuals at time n and suppose that N(n + 1) is a function of 7V(n), that is, N(n+l) = F(N(n)). (8.9) This hypothesis is acceptable if two generations do not overlap. For small N, (8.9) must recover the Malthusian model, that is, F ( N ( n ) ) — aN(n] + nonlinear terms. The nonlinear terms must take into account the fact that, when the resources are bounded, there must be a competition among the individuals which is proportional to the number of encounters among them. The number of encounters is proportional to N2(n). The model becomes N(n + 1) = aN(n) - WV 2 (n),
(8.10)
with a and 6 positive. The parameter a represents the growth rate, and b is a parameter depending on the environment (resources). The quantity a/b is said to be the carrying capacity of the environment. For a > 1, this equation has a positive critical point N = ^^ which, as shown below, is asymptotically stable when a is in a suitable interval. This means that limn_^oo N(n) — N and N is a limit size of the population. N depends on both a and b. A more realistic model would assume both such parameters to vary with time. In fact b can diminish because the population learns to better use the existing resources or to discover new ones; a can grow because the population learns how to live longer or how to accelerate the birth ratio. Anyway, taking
Copyright © 2002 Marcel Dekker, Inc.
220
CHAPTER 8. MODELS OF REAL WORLD PHENOMENA
into account the corresponding variation of TV (which happens with a longer time scale), one sees the evolution of the population can be described as a sequence of equilibrium points with increasing values of TV. Almost all the previous results are similar to those obtained in the continuous case. A further analysis of the discrete logistic equation shows solutions that are unexpected if one thinks the discrete equation merely as an approximation of the continuous one. To see this, let us change the variable and simplify the equation. Let yn — ^TV(n). The model becomes yn+i = ayn(l - yn] = f ( y n } -
(8.11)
The new variable yn represents the population size expressed in unit of carrying capacity a/6. The equation (8.11) has two equilibrium points, the origin and y ~ (a — l)/a. which has physical meaning only for a > 1. For a < 1, by using the theorems of stability by first approximation (see Section 4.7), one sees at once that the origin is asymptotically stable. For a > 1, the second critical point becomes positive and the origin becomes unstable. The stability of y can be studied locally by the linearization methods again using one of the theorems of Section 4.7. In fact 2/n+i - y - f'(y)(yn -y)-\
—(yn - y}2 = ( 2 - a)(yn - y) - a(yn - y ) 2 .
If the coefficient of the linear term is less than one in absolute value, then y is asymptotically stable. As a consequence, one has that for 1 < a < 3 the point y is asymptotically stable. For a = 2, the solution can be found explicitly (see (1.15)). For a > 3, a new phenomenon appears. There exists a couple of points x\ and a:2 such that x2 = f ( x i ) and xi - /(x 2 ).
(8.12)
The couple x\ and X2 is called a cycle of period two. From (8.12) it follows that L), (8-13) that is, x\ and x-2 are fixed points of the difference equation
)-
(8.14)
One can determine the fixed points by using the Equation (8.13). which is a fourth degree equation (it contains as roots the origin arid y ) . The following theorem permits us to simplify the problem. Let f [ x . y] be the usual divided difference, that is. f,[rx , y \ ! = /(*) - /(y)
Copyright © 2002 Marcel Dekker, Inc.
8.3. DISTILLATION OF A BINARY LIQUID
221
Theorem 8.2.1 The solutions of period two for the difference equation — f(yn] exist iff there exist values of x such that /[x, f(x}} = — 1. Proof.
By definition
If /( 2 )(x) = x then (8.15) is equal to -1. On the other hand, if (8.15) is equal to — 1, then it follows at once that x = f^(x). D Applying the previous results one obtains in the present case /[x, f ( x } \ = a(l — x — ax + ax2} = — 1. This equation has real roots for a > 3. It can be shown, for example, considering the linear part of /( 2 )(x), that the cycle is asymptotically stable for values of a in a certain range, while y becomes unstable. One says in this case that the solution y bifurcates in the cycle of order two. As a result, it follows that if y is greater than | then the system tends to oscillate between two values. We cannot go into details on what happens for a > 3 (see [122] for details), but we shall qualitatively sketch the picture. For higher values of a, a cycle of order four appears and then a cycle of order eight and so on. All the cycles of even period 2 r . r > 0 will appear. All this happens as a goes from 3 to 3.57, where the last point is an accumulation point of cycles of 2r periods. What is the solution like to the left of this point? For a near 3.57 one can find a very large number of points that are parts of some even period solutions. In this region even if two similar populations evolve starting from two very close initial points, their history will be completely different. After a long time every subiriterval of (0, 1) will contain a point of the trajectory and if one maps the density of the number of occurrences of yn, in subintervals of (0, 1) the pictures are very similar to sample functions of stochastic processes. This behavior has been called chaos. After the value 3.57 of a, the solution of period three appears. There is a result by Li and Yorkc [112] that states if there is a cycle of period three, then there are solutions of any integer periods and. for the same reasons discussed above, the term chaos is appropriate in this case as well. When a = 4, again the solution can be done in closed form (see Example 3). Almost all of the previous results can be extended to more general functions / leading to the conclusion that the qualitative results are widely independent from the particular function chosen to describe the discrete model.
8.3
Distillation of a Binary Liquid
The distillation of a binary ideal mixture of two liquids is often realized by a set of AT-platcs (column of plates) at the top of which there is a condenser
Copyright © 2002 Marcel Dekker, Inc.
222
CHAPTER 8. MODELS OF REAL WORLD PHENOMENA
and at the bottom there is a heater. At the base of the column there is a feeder of new liquid to still. A stream of vapor, whose composition becomes richer from the more volatile component, proceeds from one plate to the next one until it reaches the condenser from which part of the liquid is removed and part returned to the last plate. On each plate, which is at different temperature, the vapor phase will be in equilibrium with a liquid phase. Because of this, a liquid stream will proceed from the top to the bottom. We suppose that the liquids are ideal (Raoult's law applies) as well as the vapors (DaltoiVs law applies). Let yl (i — 1. 2) be the mole fraction of the z-th component in the vapor phase and :r? the mole fraction of the same component in the liquid phase. Of course y\ + y2 — 1 and x\ + x^ — 1 (the sum of the mole fraction in each phase is 1 by definition). Under this hypothesis, the quantity called relative volatility,
- y^'^ 2/2 Xi '
can be considered constant in a moderate range of the temperature (see [173]). If a > 1. one says that the first component is more volatile. For simplicity, we shall consider as reference only the more volatile component. Setting y\ — y and x\ — x. one has
(i-s) -
, 8(8.16) irM
which will be considered valid every time the two phases are in equilibrium. Let us see what happens on the n-th plate. Here the two components are in equilibrium in the two phases. Let xn be the mole fraction of the more volatile component in the liquid phase, y^ the mole fraction in vapor phase of the same component, and yn the mole fraction of the same component leaving the plate n. If we assume that the plate efficiency is 100 percent, then y* = yn. Moreover, part of the liquid will fall down with rnole rate d and the vapor will go up with mole rate V. Let D be the mole rate of the product, which is withdrawn from the condenser. Consider now the system starting from the nih plate (above the point where new liquid enters into the apparatus) and the condenser. We can write the balance equation Vyn-i = dxn + DxD,
(8.17)
where XD is the mole fraction of the liquid withdrawn from the condenser. To this equation one must add the definition of relative volatility that will hold for the equilibrium of the two phases at each plate (8.18)
Copyright © 2002 Marcel Dekker, Inc.
8.3. DISTILLATION
OF A BINARY LIQUID
223
From the last relation we obtain n
(8-19)
, ++ ,(a- l)x ,n 1
and, after substitution in (8.17) we get xn DxD(a - 1) - Va DxD xnxn-i + -- -f -—.-IT- xn-i + -T( -TT = 0, a —1
d(oi — 1)
d(a — 1)
from which, by letting _
1 ~, Q-l'
CL —
^ _ DxD(a- 1) - Va ~ ~ , d(a-l) '
0 —
_ C—
DxD d(a-l)
one obtains xnxn-i + axn + bxn^i + c = 0.
(8.21)
This is a difference equation of Riccati type (see Example 11). Let us consider the boundary conditions. The initial condition depends on how the apparatus is fed from the bottom, and we will leave this undetermined. The other boundary condition will depend on the condition that we impose on the composition of the fluid on some plate. The final condition (which can be deduced from Fig. 16 of [110]) requires that y^ = XD, XN+I = XD- It is consistent with the condition V = d + D, necessary for other physical considerations. The Riccati equation can be transformed to a linear one by setting ^--a
(8.22)
to obtain zn+l + (6 - a)zn + (c - ab}zn^ = 0.
(8.23)
If AI and A2 are two solutions of the polynomial associated with the previous equation, one has (if AI ^ A2)
and therefore
By letting XN+\ — XD we get D
~
One obtains an equation whose unknowns are ^ (the Riccati equation is of first order and its general solution must contain only an arbitrary constant) and N (the number of plates needed to complete the process).
Copyright © 2002 Marcel Dekker, Inc.
(8.20)
224
CHAPTER 8. MODELS OF REAL WORLD PHENOMENA
Let us set, for simplicity, K — c\/c<2. After some simple algebraic manipulations. one obtains .--
=
(
}
i<*£ The value of /C is determined from the condition of the feed plate (which can be assumed as the zero-th plate).
8.4
Models from Economics
A model called the cobweb model concerns the interaction of supply and demand for a single good. It assumes that the demand is a linear function of the price at the same time, while the supply depends linearly on the price at the previous period of time. The last assumption is based on the fact that the production is not instantaneous, but requires a fixed period of time. Let the above period of time be unitary. We shall then have
do
(8.27)
where d n , sn are respectively the demand and supply functions and a, 6, d$. SQ are positive constants. This model is based on the following assumptions: (1) The producer hopes that the price will be the same in the next period and produces according to this. (2) The market determines at each time the price such that dn = sn.
(8.28)
From (8.27) and (8.28) one obtains Pn-l
+d^.
(8.29)
The equilibrium price pe is obtained by setting pn = pn-\ = pe, which gives
and the solution of (8.29) is given by Pn=--)"po+l --a which is deduced from (1.14).
Copyright © 2002 Marcel Dekker, Inc.
Pe,
(8-30)
8.4. MODELS FROM ECONOMICS
225
If b/a < 1, it follows that the equilibrium price pe is asymptotically stable, that is limn-^oopn = pe. Since —a/6 is negative, we see that pn will oscillate approaching pe. For b/a > 1 the equilibrium price is unstable, and the process will never reach this value (unless p$ = pe). As a more realistic model, take sn as a linear function of a predicted price at time n. This means that the producer tries to predict the new price using information on the past evolution of the price. For example, he can assume as the new price pn = pn-\ + p(pn-\ — Pn-i] obtaining Sn = b(pn-i + p(pn-l ~ Pn-l}} + «0,
while the first equation remains unchanged. By equating the demand and supply, one obtains -apn + d0 = bpn-i + bppn-i - bppn-2 + «0
from which />„ + -(! + p)pn-l - -pPn-2 + ^—^- = 0.
a The equilibrium price is again Pe
a
a
(8.31)
^° ~ so
a —o
The homogeneous equation is pn + -(l + p}pn-i - -ppn-2 = 0 a a and the characteristic polynomial reduces to z2 + -(I + p)z-^- =0. a a
(8.32)
(8.33)
Let z\ and z^ be the roots of this equation. The general solution of the homogeneous equation is Pn =
while the general solution of (8.31) is Pn = CiZ? + C2z2 + Pe,
(8.34)
where c\ arid c^ are determined by using the initial conditions. From (8.34) it follows that if both \z\\ and [22! are less than one. one has lim n _^oop n = pe. If at least one of the two roots has modulus greater than one, then \imn-Kx, pn — oo (for generic initial conditions). The problem is now reduced
Copyright © 2002 Marcel Dekker, Inc.
226
CHAPTER 8. MODELS OF REAL WORLD PHENOMENA
to derive the conditions on the coefficients of the equation in order to have \zi\ and Z2 both less than one. A necessary condition is
bp The other condition is
a 1 + P < T -P0
A positive value of p means that the producer expects the price will continue to have the same tendency, while a negative value means that the producer expects to have an inversion in the tendency. To an equation similar to (8.31), one arrives in the Samuelson's model of national income. Here the economy of a nation is modeled by considering four discrete functions: the national income yn, the consumer expenditures Cn, used to purchase goods, the investments In and the government expenditure Gn. The definition of yn is (8.35)
Gn-
The other relations among the four variables arc based on the following assumptions, which are self-explanatory even from the economics point of view 0 < a < I,
ayn,
p(Cn-Cn_i),
p>0.
The parameter a is usually called marginal propensity to consume and p is the acceleration coefficient or "the relation"'. For simplicity we assume Gn = G constant. By substituting in (8.35) we get yn - f*(l + p)yn~i + apyn-2 ~ G = 0, which is similar to (8.31). The constant solution (or equilibrium point) is now G
i
Copyright © 2002 Marcel Dekker, Inc.
8.5. MODELS OF TRAFFIC IN CHANNELS
227
If this point is asymptotically stable, then lin^^oo yn = ye, which means that with this hypothesis the national income, under the effect of the government expenditure G, will tend toward the income ye, which is greater than G. The factor j^ is said to be a multiplier. To see when this happens, just repeat what is said for the previous model remembering that in this case p cannot be negative.
8.5
Models of Traffic in Channels
The models presented here concern the traffic in channels (for example telephone lines) and are from information and queueing theory. In the first simple model, the number of messages of given duration is derived. In the other two models the probability of requests for services (for example telephone calls) is derived as well as the probability of loss of the request in a system of limited channels. Consider a channel and suppose that two elementary informations Si and 82 of duration t\ and £2 respectively (for example the point and line in the Morse alphabet) can be combined in order to obtain a message. Let t be a time interval greater than both t\ and £2- One is interested in the number of messages Nt of length t. These messages can be divided in two classes: those ending with Si and those ending with 82- The number of messages in the first class is Nt-ti while the number of messages in the second class is Nt-ti- Then we have Nt = Nt.tl + Nt.tz.
(8.36)
Suppose, for simplicity, that t\ = 1 and £2 — 2. The previous formula becomes Nt = Nt-i + Nt-2.
(8-37)
The initial conditions are N\ = I and 7V2 — 2. The equation (8.37) is the same as that which defines the Fibonacci sequence (see (2.45)). The solution is
where p\ = 1 ^ ' P2 — *~2 • Because \p2\ < 1. for large t one has Nt — c\p\. Shannon defines the capacity of a channel as c = rhm —2-— = Iog9 pi . t—»oc
Copyright © 2002 Marcel Dekker, Inc.
£
228
CHAPTER 8. MODELS OF REAL WORLD PHENOMENA
Difference equations arise very often in queuing theory. We shall give two examples. Consider a queue of individuals (or telephone calls in a channel). Let Pn(t] be the probability of n items arrived at time t and we have /L??Lo Pn(t) ~ 1-
Let AAt be the probability that a single arrival during the small time interval At and suppose that the probability of more than one arrival in the same interval is negligible (Poisson process). Let fj,At be the probability of completing the service in the interval At. We shall assume that the service is a Poisson process, that is, the probability of no arrivals in At is 1 — AAt and the probability of the service not completed in At (no departures) is 1 — /j,At. The following model is due to Erlang and describes the situation where at the beginning there are no items in the single channel queue and the service is made on a first come, first served basis,
P n (t P0(t + At) =
P0(t)(l-
The meaning of the equations is the following: the probability that at time t + At there are n items in line is equal to the sum of three terms: (1) The probability of already having n items at time t multiplied by the probability of no arrivals during At and the probability of no departure in the same interval; (2) the probability of having n — 1 items at time t multiplied by the probability of a new arrival in At; (3) the probability of having n + I items at time t multiplied by the probability of a departure in At. Taking the limit as At —-> 0 one has
dt
-XP0(t)+lJ,Pi(t).
It is important to know how the system behaves for large t. That is, to know if the limit Pn = Hindoo Pn(t] exists. The probability Pn. will describe the steady state of the problem. In order to get this information one observes that in the steady state the derivatives will be zero.
Copyright © 2002 Marcel Dekker, Inc.
8.5. MODELS OF TRAFFIC IN CHANNELS
229
It follows that the Pn will satisfy the difference equations M P n +i
- (A + v)Pn + AP n _i -XPo + ^Pi
= 0, = 0.
(8.38) (8.39)
To this one must add the condition X^n^=o-^n — 1> which simply states that it is certain that in the system we must have either no items, or more items. Let p = -. The solution of (8.38) is given in terms of the roots of the polynomial equation Z 2 - ( l + p ) 2 + p = 0,
which are z\ = 1, 22 = p. If p ^ 1, we get
Considering that from (8.39) one has P\ = pPo, it follows that c\ = 0. The integral condition can be satisfied if p < 1, obtaining
r
n=0
which gives c% = 1 — p and then Pn = (1 — p)pn, which is called geometric distribution. Important statistical parameters are: (1) the expected number in the system
n=0
n=0
p
n=0
(2) the variance r\Jp _ \ " "2p
n=0
r-2
— 1^) *n — / 'i - » n — -^ 5 n=0
one shows that E^o n2Pn = L + 2L2 and F = L + L 2 ; (3) the expected number in the line
n=0
In the following generalization the case of ./V identical channels is considered. The hypothesis on the distribution of arrivals and departures (Poisson distribution) is maintained. Moreover, we shall assume that both the state with zero items EQ and the state with N items EN arc reflecting, that is,
Copyright © 2002 Marcel Dekker, Inc.
230
CHAPTER 8. MODELS OF REAL WORLD PHENOMENA
from these states transactions are possible only in one direction. From the state EQ a possible transaction will be to the state E\, and from the state EN a possible transaction will be to the state E^_l. The resulting model is eft
= -(A + n^Pn(f) + AP n _i(t) + (n + l) M P n+1 (t). 1 < n < N - 1,
dt
The steady state solution satisfies the difference equations (n + l)Pn+i ~ ( p + n)Pn + pPn_! = 0. - pPo,
Pi
where, as before p — -. Let us look for solutions of the form Pn — znpr from which one has ZQ — PO, zi = P(h ^v = ^isT1- The equation is then p n [(-^ 4- (n + l)zn+l)p - (-2 Tl -i + nz n )] - 0. Let On = — zn + (n + l}zn+\. The equation becomes f)0n ~ On.! = 0.
whose solution is n
x>—"/a
"n — P
"()•
For n — N—l, we must have ^v-i — —ZN-\ +Nzj\ It follows then OQ — 0. The equation for zn is then ^2 n + (n + l)zn+1 = 0, which has the solution zn = —.ZQ — —PQ. n\ n\
Going back to Pn we have Pn — ^pnP(). Imposing the condition 1, one finds P(j = I/ X^jLo ^T- The solution is then
Copyright © 2002 Marcel Dekker, Inc.
8.6. PROBLEMS
231
which is called Erlang's loss distribution. For n — N, one obtains the probability that all the channels are busy, which also gives the probability that a call is lost. As N —» oo one obtains the Poisson distribution on
Pn -~~ —i ce~p
1
n\
The previous model also describes the parking lot problem. For this problem, N is the number of places or slots in the parking lot. The reflecting condition at the end just describes the policy that the parking lot closes when it is full. The probability that a car cannot be parked is P/V. If the management follows the policy of allowing a queue waiting for a free place, then the model is modified as follows: Pi
(n + l)Pn+\ -(p + n}Pn + pPn-i NPN+l -(p + n}Pn + pPn,i
= pPo,
= 0, = 0,
n < TV, n > N.
The solution is
= —PQ,
n < TV,
as before, and
Using the relation ]C^Lo Pn — 1 one obtains PQ.
8.6
Problems
8.1 In the case a7; > 0, derive the existence of eigenvalue of greatest absolute value from Theorem 8.1.1 instead of the Perron-Frobenius theorem. 8.2 Write the generating function for the solution of (8.8) and derive the behavior of the solution (Renewal Theorem). 8.3 Show that for a < I the origin is asymptotically stable for T/Q £ (0,1) for the discrete logistic equation. (Hint: use the Lyapunov function Vn =
vl) 8.4 Discuss the stability of y for the logistic equation using Vn — (yn — y)2. 8.5 Determine the solution of (8.5) for M = 4 and a\ = 0,2 = 03 = 0, 04 = 16. 8.6 Discuss the modified cobweb model with p — — 1.
Copyright © 2002 Marcel Dekker, Inc.
232
CHAPTER 8. MODELS OF REAL WORLD PHENOMENA
8.7 Derive the national income model assuming that In — p(yn-\ ~ 2/71-2)8.8 Suppose that the input for the traffic in N channels has Poisson distribution and depends on the numbers of free channels, that is. pi is not constant. Derive the model and find the solution.
8.T
Notes
Age-dependent population models have many names associated with them such as Lotka, McKendrick, Bernardelli, and Leslie. An extensive treatment of the subject may be found in Hoppensteadt [93]and Svirezhev and Logofet [169]. In [169] we also have several references to the subject. Theorem 8.1.1, which is a generalization of a Cauchy theorem, may be found in Ostrowski [141], but see also Pollard [151]. The discrete logistic equation has been discussed by many authors, for example, Lorenz [113], May [122, 121], Hoppensteadt [93]. and Hoppensteadt and Hyman [94]. The result of Li and Yorke [112] on the existence of periodic solutions is contained in a more general result due to Sharkovsky (see [163], [165], [94], [167] and [1] for more recent proofs and results). When a difference equation is derived from an approximation of a continuous differential equation, the question arises to what extent the behaviors of the respective solutions are similar. This problem has been outlined and treated by Yamaguti et al. [182, 183, 181] and Potts [155]. The distillation model has been adapted from [80], see also [2]. The discrete models in economics may be found in Gandolfo [67], Goldberg [77], and Luenberger [114]. Queueing theory is a large source of difference equations (see for example Jagermann [96] and Saaty [158]) where one may find very interesting traffic models more general than those presented in Section 8.4. For the parking lot problem, as well as other models concerning traffic flow, see Haight [82].
Copyright © 2002 Marcel Dekker, Inc.
Chapter 9
Historically Important Equations 9.0
Introduction
It is well-known that in mathematics many unsolved problems or problems solved after centuries of efforts have a very easy formulation. This is also true in the present field. All the examples provided below are very easily formulated, but, in most cases, their solutions have been obtained after many years of effort. In fact they have been studied for almost two centuries and still continue to attract the interest of many mathematicians. As we shall see, most of them share the difficulty that the set of critical points is not a discrete set. but the entire line y = x. To each initial point there corresponds a critical point on such line. The second example, derived from the Weierstrass method for proving the fundamental theorem of Algebra, has also a similar problem, although of a different nature. In Section 9.4, few examples relating difference equations to prime numbers are presented, along with the celebrated Euler theorem.
9.1
Combinations of Means
It is well-known that, given for example two positive values x and y, one can define countless types of averaging values, such as A G H
^rr^ (xy}* - ( x ~^y } r ,
Arithmetic mean; Geometric mean; Harmonic mean; r ^ 0 Power mean.
Both A and H are P-means corresponding to the values r = 1 and r = —I respectively. What happens if any couple of such operations is 233 Copyright © 2002 Marcel Dekker, Inc.
234
CHAPTER 9. HISTORICALLY IMPORTANT
EQUATIONS
iterated? In all cases they give rise to a system of two difference equations of the form
Xn+l
=
/(^n,2/n)
2/n+l
=
g(Xn,yn)
I9-1)
with the common feature that all the points of the line y — x = 0 are solutions of the system defining the critical points, given by (9.2)
Many common properties of the system (9.1) can be derived from the properties of the means. We list some of them here. For simplicity we denote a generic mean by M(x.y). PI If x > Q.y > 0, then m.m(x.y) < M(x,y] < max(x.?/); the equality occurs only when x = y< P2 two different means Mi(x,y] and M^x.y) give two different values when x ^ y: P3 M(x,y) is an homogeneous function of degree one, i.e. M(\x,\y) = XM(x.y). Such properties permit us to prove two important results about the location of the limit points. The first one, almost trivial, says that the motion is entirely in the first quadrant. The second is the following theorem. Theorem 9.1.1 If the sequences xn andyn converge, then their limit points need to coincide. Proof.
In fact, if lim yn =
n—>oc
then such limit points must satisfy (9.2). If x ^ y. P2 would be violated for both functions f ( x . y ) and g(x.y}. D Unlike the cases considered in the previous chapters, where the set of critical points was a discrete set, here the limit points depend on the initial values (XQ. yo}. The study of this type of iterative process can be traced back to Gauss and even earlier. In the following subsections we shall present a few of them not in their historical sequence, but starting from the easiest case.
Copyright © 2002 Marcel Dekker, Inc.
9.2. ARITHMETIC-GEOMETRIC
9.1.1
(BORCHARD)
235
Arithmetic-harmonic mean
In this first case the arithmetic and the harmonic means are combined and iterated giving
(9.4)
with XQ ^ 7/0 both positive. By multiplying both equations, we obtain at once that xn+iyn+i = xnyn, i.e. that xy is constant along the motion, or equivalently the motion stays on the hyperbola xy = XQJ/O (and, as mentioned above, in the first quadrant). Moreover, one has _
x
n+l ~ TJn+l — 7^ ; r> 2(x n + J/n)
i.e. for n > 1 we have xn > yn. Apart perhaps for the first point, the motion stays on the hyperbola below the bisectrix of the first quadrant. The direction of the motion can be also easil deduced. In fact we have X
_ —
2
which, as indicated above, is negative. The direction on the hyperbola is towards the bisectrix, and then the two sequences converge. By Theorem 9.1.1, they converge to the point (Y/XO^/O? ^/XQyo}• Since such convergence is quadratic (see Problem 9.1 ), the system (9.1) can be used to numerically find the square roots of any positive number.
9.2
Arithmetic-Geometric (Borchard)
Here the couple of arithmetic and geometric means is considered, although not simultaneously. First we perform the arithmetic mean and then the geometric mean. The technique of using the updated variable in the following equations of a system, well-known in numerical analysis as the Gauss-Seidel process, usually leads to an improvement in the rate of convergence, while leaving unchanged the limit point. Here, since the limit point is sensitive to the initial point, such a process changes such points as well. The system is now described by
n+l
_ —
x
x
yn+l
=
(Xn+lVn}*-
It is not difficult to check that
Copyright © 2002 Marcel Dekker, Inc.
n i 7/
(9-6)
236
CHAPTER 9. HISTORICALLY IMPORTANT
EQUATIONS
- Vn+l = o 2 ( Z n + yn)2 + (2yn)2
from which it follows that the sign of xn — yn is constant. The motion will then always be below or above the bisectrix of the first quadrant, according to the position of the initial point (xo>2/o)- Suppose that xn < 2/o> it will always be xn < yn. We can then define X7
cosa = — getting
cosan+i = -2 —^ (Xn +, \2^
We then have a
_ &n
n+l — — ,
i.e. a n — 2~ n ao- From this result one easily derives that ihm • — ^n — 11.
n^co yn
It also possible to obtain explicitly both xn and yn as functions of n. For this we need to prove the following identity:
n
J
cos2-Ja 0 =
^
n . °n . 2 n s m 2 n ao
, N 9.7)
The proof is almost immediate by considering that sin2-J'+1Q!o cos 2 Jar) — ———-—:— and substituting in (9.7). We are now in the position to obtain the result. Since x n +i = yn cos" a n +i, we have
from which we get
n Conccrnine: xn. we have
Copyright © 2002 Marcel Dekker, Inc.
, cos2 Ja0 = yo
sina 0
9.2. ARITHMETIC-GEOMETRIC
xn = yy ncos2
(BORCHARD)
an u =
1
237
sin a0
-VQ. 2ntan2-na0y
It is now an easy matter to show that smc r v *0 (yg-xg) 1 / 2 hm xn - hm yn = - y0 = —--^—-.
n->oo
n-+oo
Q;O
(9.8)
Iii the case XQ > yo the limit is x o) 1//2 —— hm xn = hm yn = - y0 (2/0 =~-*oc n-+oc QJQu arccosh^
(9.9)
(see Problem 9.2).
9.2.1
Arithmetic-geometric mean II
Contrary to the system considered in the previous section, the present system does not use the updated value in the second equation. The resulting limit is completely different and cannot be expressed by means of elementary functions, but it is expressible in terms of integrals. The system is
yn+i
=
•Era i" yn
/,-,-, n \
(x n y n )2.
(9.11)
Since 2-n+l ~ Un+\
==
/
"2
*? \ 2
7^ (2-n ~ J/n j i
it follows that xn > y n , n > 0 independently of the sign of XQ — yo- Moreover, one has
and
i
I
-
yn+i -yn = y2(xn -yn) > 0, i.e. for n > 0, the sequences xn and yn arc decreasing and increasing, respectively. Apart from the initial point (XQ, yo], the successive points (x n , yn] will be contained in the triangle having vertices at the points (XI,T/I), ( x i , x i ) and (3/1,2/1). The convergence of the process is then evident. In the case %Q > 2/0) the limit point is (see [162]) lim xn — lim xn —
n—>oo
n—>oo
2
As result, the successive iterates can be used to approximate the above integral.
Copyright © 2002 Marcel Dekker, Inc.
238
9.3
CHAPTER 9. HISTORICALLY IMPORTANT
EQUATIONS
The Weierstrass Method
In this section we give an overview of another historically important system of difference equations. It was proposed by Weierstrass, he used it to prove the fundamental theorem of algebra. It has been rediscovered several times and used as an algorithm to simultaneously approximate all the roots of a complex polynomial. The starting point is the Vieta's relations among the roots z\, 2 2 , . . . , zs and the coefficients ps,ps-\,. ..po of a polynomial, i.e.
z\ + Z2 + . . . + zs
—
=
0
Ps
. .. + zs-izs +-^=—
— 0
f_iy'PQ ps
_ o
Ps
Let be z — ( 2 1 , 2 2 , . . . , 2S)T and F(z) the vector whose entries are the left sides of the above equations, which is then written as F(z)=0.
(9.12)
It turns out that the entries of any solution of (9.12) are roots of the polynomial ,s
p(, \ — \^ .,r' n J JJ-j JL
J ^ JLr J —
.
(a i "*} ^ a. L O j
?:=0
The Jacobian J(z] of (9.12) is a Vandermonde-like matrix whose determinant is not equal to zero iff 2; ^ Zj, for i =^ j. When this happens, the Newton method applied to (9.12) leads to -J~i(zk}F(zk}.
(9.14)
When the above sequence converges, it provides the roots of the polynomial. Of course a necessary condition for the convergence is that in each step Zi ^ Zj. which leads, to be conservative, to the assumption that the roots are simple. It has been conjectured that in the latter case the method converges for almost all initial points. The proof has been provided only in the case s — 2. We shall report this case for brevity and also because it provides an example of dynamics similar to those presented in the previous sections. Let f(x] = x~ — ax+b. whose roots are supposed real and z — (x, y)T. For simplicity, we shall also suppose that the roots are positive (a > 0. b > 0). Equation (9.14) reduces to
Copyright © 2002 Marcel Dekker, Inc.
9.4. DIFFERENCE EQUATIONS AND PRIME NUMBERS
xn+i \
( xn \
1
xn
-1
239
xn + yn - a
i.e. Xn+1
n
n
(9.15)
xn-yn
As expected, the vector (xn,yn)T needs to stay away from the bisectrix x — y = 0. It is easy to check that xn + yn — a, i.e. after the first iteration, the motion will stay on the line x + y — a — 0. This result is also valid for the general case, where the motion stays on the hyperplane
i=0
n Ps
Going back to the bidimentional case, it is easy to check directly, or by using the fact that the successive iterations stay on the straight line (see Problem 9.4), that f ( x n ] = f ( y n ) . This permits us to show that ,
0~
i.e. the motion stays always on the same side with respect to the hyperbola xy — b = 0 on which stays the solution (x* , y*). Suppose now that xn > yn, by subtracting the two entries in (9.15) we get (xn - y )2 - (f(x ] + f(y }}
b-x y
n n O n n Xn+i - yn+i = -—n:= 2-—-— > 0, Xn yn) X y n
n
i.e. all the successive iterates remain below both the bisectrix and the hyperbola xy — 6 = 0. The latter property implies that xn is greater than the largest root and then f ( x n ] > 0. As a consequence, for n > 0, xn is decreasing and yn is increasing such that xn — yn > 0. The convergence then easily follows.
9.4
Difference Equations and Prime Numbers
In Section 1.3 a difference equation was presented whose solution yn assumes prime values for all n. There are also many examples of difference equations whose solutions relatively prime values for all n. Here are two of them. Example 20 Let us consider the discrete problem 2/n+i -yn(yn - 2) - 2 = 0,
2/0 = 3.
The following facts can be deduced almost immediately:
Copyright © 2002 Marcel Dekker, Inc.
240
CHAPTER 9. HISTORICALLY IMPORTANT
EQUATIONS
1. At n-th step yn is the product of all the previous values plus 2. In fact
yn+i -2 = yn(yn - 2) = ynyn-\(yn-\ - 2) = . . . = ynyn-\ • • • 2/12/02. All the successive values are odd numbers; 3. All the successive values are relatively prime. In fact, if yn and yj had a common factor, such a factor would be divisible by 2 and thus be even. 4. The explicit form of the solution is
yn - 22" + 1, i.e. the set of Fermat numbers. The proof simply follows by setting yn = zn + 1. which reduces the above equation to zn+\ — z% (see Problem 1.28). Similar considerations apply to the following example. Example 21 yn+i - yn(yn - 1) - 1 = 0,
2/0 = 2.
Both example are consequences of Euler theorem, which in complete form states: Theorem 9.4.1 I f p o , p \ , . . . .pn is any set of relatively prim,e numbers, then P = POPl . . . p n + l
is a new number which is relatively prime to the previous one and of course different. Proof. When p is divided by each pt. it gives 1 as remainder, and then it is relatively prime to all of them. The following consequence is well-known. Corollary 9.4.1 // the above set contains all the primes less or equal to pn, then a new prime p is found and consequently the number of primes is infinite.
Copyright © 2002 Marcel Dekker, Inc.
9.5. PROBLEMS
9.5
241
Problems
9.1 Prove that the convergence of (9.1) is quadratic. 9.2 Prove the relation (9.9). 9.3 Show that the algorithm •Z-n+l —
n
2/n+l —
— -4Xn
J/
is equivalent to + — ],
^ = Vxoyo
already considered in (1.27). 9.4 Show that f ( x n ) = f(yn] in (9.15). 9.5 Show that for a — 0, the Weierstrass method becomes the method described in (1.27) 9.6 Show that the equation in Example (21) is a consequence of Theorem 9.4.1.
9.6
Notes
The few difference systems presented in Section 9.1 are part of a large family based on the use of couples of means and studied in the last two centuries. Such studies indeed can be traced back to Gauss and even earlier, and they continue to attract the attention of many mathematicians. The interested reader may consult Tricomi [173], Carlson [32], Schoenberg [162], Gatteschi [68], and Wimp [180]. There is a historical overview along with interesting generalizations in Carlson. The Weierstrass method has attracted the attention of many people because of its interesting theoretical properties (see Smale [164]) and also in connection to the search of polynomial roots (see for example Kerner [100], Durand [59], Ehrlich [60], and Aberth [3]). A similar method, although more general since it can also be used for searching roots of analytical functions, has been proposed by Pasquini and Trigiante [148]. In the latter paper they present the extension to the case of multiple roots, and a proof of the convergence in the case when all roots are real is also provided. The Euclid theorem, as well as the material of Section 9.4, can be found in Sylvester [170].
Copyright © 2002 Marcel Dekker, Inc.
Appendix A
Function of Matrices A.I
Introduction
Let A be a fh x m matrix with real or complex elements, and let us consider expressions such as
p(A) = 5>^,
(A.I)
2=0
where k G N+ and pi E C. Such expressions are said to be matrix polynomials. To each of them we associate the polynomials
i=0
sharing the same coefficients. There are, however, some differences of algebraic nature among polynomials defined in the complex field and those defined on a commutative ring (the set of powers of a matrix). For example, it can happen that An — AAn~l — 0 but neither A or An~l is the null matrix. More generally, it can happen that p(A) — Y[i=i(A — Z{I] with Zi G C is the null matrix and A / Zil, which cannot happen for complex polynomials. The Cayley theorem, in fact, states that if z\, 22, • • • , zs are the eigenvalues of A with multiplicity ra?, letting P(A)
= f[(A-ZiI)**
(A.2)
z=l
one has p(A) = 0. The polynomial p(z) is called the characteristic polynomial associated to the matrix A. Let ip(z] be the monic polynomial of minimal degree such that ij>(A) = 0, and let m be its degree. 243 Copyright © 2002 Marcel Dekker, Inc.
(A.3)
244
APPENDIX A. FUNCTION OF MATRICES
Theorem A. 1.1 Every root of the minimal polynomial is also a root of the characteristic polynomial and vice versa. Proof. such that
Dividing p ( z ) by 0(z) we find two polynomials q(z) and r ( z ) p ( z ) = q(z)^(z) + r ( z )
(A.4)
where the degree of r(z] is less than m. For the corresponding matrix polynomials we have 0 = p(A] = g(A)'0(A) + r(A). Since ?/>(A) = 0 and it is minimal, it follows that r(A) is identically zero. Thus (A.4) becomes p(z] = q(z)'il'(z) proving that the roots of ijj(z) are necessarily roots of p ( z ) . Now suppose that A G C is a root of p(z] and therefore also an eigenvalue of A. For every j G N+, it follows that AJx — XJx. where x is the corresponding eigenvector. Then we have fd>(A}x — i/'(A)x from which it follows il'(X) = 0, proving that A is also a root of y ( z } . n Let h(z] be any other polynomial of degree greater than m. We can write h ( z ) = q(z)u'(z) + r ( z ) where the degree of r ( z ) is less than m. Consequently
h(A) = r(A).
(A.5)
The last result shows that a polynomial of degree greater than m and a polynomial of degree less than m may represent the same matrix. Let h ( z ) and y ( z ) be two polynomials such that h(A) — g(A). Then the polynomial d(z) = h(z) - g(z] (A.6) annihilates A; that is, d(A] = 0. It follows that it is possible to find q(z) such that d(z) — q(z}'il}(z). Let 777,1,77^ • • • , ^.s, be the multiplicities of the roots of 0(2). Then we have V(*i) = v'&) = ... =^(mi^(zl] = 0,i - 1, 2 , . . . , s, from which d ' ( z i ) = d ' ( z i ) = ... = d^mi~l\Zi) = Q,i = l , 2 , . . . , s . This result shows that
(A.7)
for i — 1.2..... s. Two polynomials satisfying the above condition are said to assume the same values on the spectrum of A. Now. suppose that the two polynomials assume the same values on the spectrum of A. It follows that d(z] has all the Zi as roots of respective multiplicity ?n,? and will be divided exactly by ty(z): that is. d(z] = q(z)'il>(z). Then d ( A ) = g(A) — h(A] — 0 and the two polynomials represent the same matrix. The foregoing arguments prove the following result.
Copyright © 2002 Marcel Dekker, Inc.
A.I. INTRODUCTION
245
Theorem A. 1.2 Let g(z] and h(z) be two polynomials on C. Then g(A) — h(A) iff they assume the same values on the spectrum of A. Definition A. 1.1 Let f ( z ) be a complex valued function defined on the spectrum of A, and let g(z) be the polynomial assuming the same values on the spectrum of A. The matrix function f ( A ) is defined by
The problem of defining f(A) is then solved once we find the polynomial g(z) such that g(l](zk}'= }(i\zk] for k = 1, 2, . . . , s, i = 0, 1, . . . ,mk-i. The later is solved by constructing the interpolating polynomial (LagrangeHermite polynomial) s
mk
1
^)^)'
(A-8)
where $ki(z] are polynomials of degree m — 1 such that ki
' •"
/', k = 1 , 2 , . . . ,s, ' i, r = 1 , 2 , . . . ,mjfe.
"J "
For example, for m7- = 1, z — 1, 2, . . . . n,
It can be proved that the functions 4>ki(z) are linearly independent. The matrix polynomial is then s
mk (l l) z
~ ( ^kr(A}.
(A.9)
The matrices 4>ki(A) are called component matrices of A. They are independent of the function f ( z ) . As usual in this field we shall put
ki(A) = Zki.
(A.10)
Such matrices, being polynomials of A, commute with A. With this notation (A. 10) becomes s mk 1 f ( A ) = g(A) = V Z—/ V Z—, /^- )(z fc )^-.
(A-ll)
The set of matrices Zki are linearly independent. In fact if there exist constants cki not all zero such that -0,
Copyright © 2002 Marcel Dekker, Inc.
246
APPENDIX A. FUNCTION OF MATRICES
the associated polynomial s
mk
would annihilate A and be of degree less then the degree of the minimal polynomial.
A. 2
Properties of Component Matrices
Let us look for some properties of the component matrices Zkl. Taking f ( z ) — 1, we get from (A. 11)
Also, taking /(z) = z. we see that s
A = ]T (zkZkl + Zk2),
(A.13)
from which s
s
k=l
3=1
k=lj=l Starting directly from f ( z ) = z1, one has Zkl + 2zkZk2
fc=i Comparing the two results, it follows that
Zk\Zj\
=
Proceeding in a similar way, it can be proved in general that ZkpZir ZkpZkl ZkpZk2
Copyright © 2002 Marcel Dekker, Inc.
= 0 = Zkp — pZk,p+i
k ^ i, p>l. p > 2.
(A. 14)
A.2. PROPERTIES
OF COMPONENT MATRICES
247
From the last relation it easily follows that
1
j
It is worth noting that from the second relation of (A. 14) we get Z2ki = Z fcl ,
(A. 16)
showing that the matrices Zki are projections. Multiplying the expression s
s
A — zT — VVz — z-\Z
-\- V^ Z
k=l
k=l
by Zn, and considering (A. 14), one gets, s
s Zk
(A — ZiI)Zn = 2—<( fc=l
z
~ i}ZklZn + / ^ Zfc2^il = ^z2fc=l
(A-17)
Because of (A. 15) and (A.17), we obtain Zkp =
(p- l)\Z^2
=
(p- 1}\^A ~ Zkl^
Zkl
'
(A- 18)
From this result, it follows that (A. 11) can be also written as 5
=
mk
f(i-l)(
\
E E V*r - nL ) -. (A ~ t*1?-1^-
fc=li=l
( A - 19 )
Let us now consider the function f ( z ) = -^^ where A 7^ zk. The function f(A) = (A — A/)"1 is expressed by
(A - A/)- 1 = - £ E(* - 1)!(A - z*)-1^
(A.20)
fc=l i=l
from which, considering (A. 15), we get
(A - A / ) -1
fc-i + (A - zk)-3Z2k2 + . . . + (A Because of (A — XI) — — Y^k=i[(^ ~ zk)Zki - ^2], we then obtain
k=l
Copyright © 2002 Marcel Dekker, Inc.
APPENDIX A. FUNCTION OF MATRICES
248 (A
-2 ^ 2
ZkiZk2 - (A
J
k1
k=l
from which results
= o,
(A.21)
showing that the matrices Z^2 are nilpotent. This result allows us to extend the internal sum in formula (A. 19) up to ra/c, the multiplicity that the fc-th eigenvalue assumes in the characteristic polynomial. In fact, since m^ < m^, Z™2k+J — 0 for j = 0 . 1 , . . . , m^ — m^, and hence (A. 19) can be written as (A.22) Definition A.2.1 An eigenvalue z^ is called simple if rrik = 1. Definition A.2.2 An eigenvalue z\. is called semisimple if nik — 1 (Zk2 — 0). A semisimple eigenvalue is not simple (or degenerate) if nik — 1 and In both cases the terms containing (A — Z k I ) p ~ l Z k i with p > 2 are not present in the expression of
A.3
Particular Matrices
We discuss in this section matrices which frequently appear in the applications considered in this book. Example 22 An important class of matrices are the so-called companion matrices (or Frobenius matrices), defined by
1
° 0
1
0
0
1
...
A=
0
\
0 0
\
...
0
1
—an-i
For this class of matrices m7; = mi (for all values of i): that is, the characteristic polynomial and the minimal polynomial coincide. In fact, let EI be the z'-th unit vector in IRn. It is easily checked that E^A° — E\,
Copyright © 2002 Marcel Dekker, Inc.
A.3. PARTICULAR MATRICES
249
EI A = EI and, in general, E\A1 = E^+i, for i — 0 , 1 , . . . , n — 1. If there were a polynomial ^>(A) = Y^=Q aiAl of degree m less than n such that tl'(A) = 0, it would imply
Such a result is not possible because the unit vectors are linearly independent. As a consequence, companion matrices do not degenerate semisimple eigenvalues. Example 23 Let f ( z ) = ezi and A be an n x n matrix. Then s
cAt — \//
rhk
^ x/ ^
^ (
J
,i-\
A ~ Zjc±rV"! 7 • ~(^ ;^_ r ]\\ ~ _r/ o~fc£/' e \ i\ ) ^/rl V ft/ ft-l
/l-rx.^O/ A OQ\
V
/
If the eigenvalues are all simple, the previous relation becomes _
.
(A.24)
k=\
If Zj is a semisimple eigenvalue, (A.22) becomes s
mk
,i-\
l Zkt i l Z]t k &At _ y^ y^ Z^- Z^ (« _ -\\\ c (A ^ — zit} ' ~ Z^ fcl+ e Z -J^l '
\(A• 25) i
Theorem A.3.1 // Rezi < 0 for i = 1, 2 , . . . , s, J/ien
lim e^ = 0.
t^oo
Proof.
From (A.23) it follows easily.
D
Theorem A.3.2 If for i = 1 , 2 , . . . . s, Rezi < 0 and those for which 0 are semisimple eigenvalues, then eAi remains bounded as t —» oo. Proof.
It follows easily from (A.24).
D
Example 24 Let f ( z ] = zn and
(A-26) fc=l 4=0
Copyright © 2002 Marcel Dekker, Inc.
APPENDIX
250
A. FUNCTION OF MATRICES
If the eigenvalues Zj of A are all simple, then (A. 26) becomes (A.27) k=\
If Zj is semisimple, (A. 25) reduces to
/_^ />=0> EE
(A.28)
k=l
Theorem A.3.3 // \zr < 1 for i = 1, 2 , . . . , s, then lim An = 0.
n—>oc
Proof.
The proof easily follows from (A.26).
D
Theorem A.3.4 If for i = 1, 2 , . . . , s, (z^l < 1 and t/ie eigenvalues for which Zi\ = 1 are semisimple, then An remains bounded as n -^ oo. Proof.
The proof is easy to see from (A.28).
D
It may happen, however, that for a multiplicity of a higher order and consequently higher dimension of the matrix, the terms in (A.28) may become large. For example, let us take the matrix / A J3 0 A
0 j3
...
0 \ 0
A
0H 0 / 0 1 0 0 0 1
(A.29)
0 A/ 0 \ 0
H =
[A.30) 1 0 )
s
and H = 0. Then (A.28) becomes (A.31) Multiplying by E = (1,1.. . . , 1)T and taking n ~ s — 1, we have \n-lQllilE. ?'=!
Copyright © 2002 Marcel Dekker, Inc.
(A.32)
A.4. SEQUENCE OF MATRICES
251
The first entrv of this vector is = (A + /3)n,
(A.33)
i=0 W
from which it is seen that \\AnE\\ > |A + /3|n.
(A.34)
This implies that the component of AnE will grow even if |A| < 1, but |A + f3\ > 1. Eventually they will tend to zero for n > s — 1 because from (A.31) the exponents of A become larger and larger while those of (3 remain bounded by s — 1. But in the cases (as in the matrix arising in the discretization of P.D.E.), where 5 grows itself, the previous example shows that the eigenvalues are not enough to describe the behavior of An. This will lead to the introduction of the concept of spectrum of a family of matrices (see Section 7.7).
A.4
Sequence of Matrices
Often functions of matrices are defined using the Taylor series of the respective complex valued functions f ( z ) . We will show now that such definitions are compatible with the definitions given above. Let us consider a sequence of complex valued functions /i(z), / 2 ( z ) , . . . defined on the spectrum of A. Definition A.4.1 The sequence /i, /2, • • • converges to a function / on the spectrum of A if, for k — 1, 2 , . . . , s, lim fi(zk]
=
T f ' f \ hm JjAzki % \ r^ /
=
I—»00
f(zk}, -C> / J \
\ i (Zk) l\ /
The following theorem is almost evident (see Lancaster). Theorem A. 4.1 A sequence of matrices f i ( A ) converges if the sequence fi(z] converges on the spectrum of A. Corollary A. 4.1 Let A be an s x s complex matrix having all the eigenvalues inside the complex unit disk. Then
i=0
Copyright © 2002 Marcel Dekker, Inc.
252
APPENDIX A. FUNCTION OF MATRICES
Proof. Consider the sequence fi(z) = H}=o z^ f°r ^ — 0- This sequence (and the sequences obtained by differentiation) converges if \z\ < 1 to (1 — z}~1. It follows that the limit of f i ( A ) exists and the limit is (/ — A)" 1 . D Corollary A. 4. 2 Let A be an s x s complex matrix. Then
Proof.
Consider for i > 0 the sequence fi(z) = 5Z}=o ^r- This sequence
converges for all z e C. Likewise for /,- (z), follows that //(A) converges to eA. D
A. 5
Jordan Canonical Form
From (A. 13), it results that s
A = ]T>fcZfcl + Z fc2 ), fc=i
(A.35)
and from (A. 12) it follows that the space IRm can be decomposed into s subspaces M\ , . . . , Ms , defined by Mj^ZjiIR™,
j = l,2,...,s.
(A.36)
Similarly, from (A. 14) it follows that for i ^ j Mi n MJ = 0.
(A. 37)
Let inl — dim A/7. Then Y^l=\ ™li — ™- and it is seen that ffi% is the multiplicity of z% as root of the characteristic polynomial. We want to appropriately choose a base for the subspace MJ. Lemma A. 5.1 Let x ( j ) G Mj,ZJ2x(^ / 0 for 0 < i < p and Z^x^ = 0. Then the vectors Z'- 2 z' , i = 0. 1, . . . . p — I are linearly independent. Proof.
From
P-I ^c,Z]2x^^O,
(A.38)
7= 0
multiplying successively by Z^ •, ^j2^-. • • • , it follows that c?; = 0. D We shall call the set of vectors Zj2x^^ for i — 1. 2, . . . .p — I the chain starting at x^ . Such vectors are also called generalized eigenvectors associated with x^ .
Copyright © 2002 Marcel Dekker, Inc.
A.5.
JORDAN CANONICAL FORM
253
Lemma A.5.2 Let x^ G M,-,ZJ2x^ ^ 0 for 0 < i < p and Zj2z(j) = 0. Suppose that there exists y^ £ Mj linearly independent from the previous defined set of vectors {Zj2z^^}. Then the vectors {Z^2y^} are linearly independent from the previous set. Proof.
Similar to the previous proof.
D
Going back to our problem we shall distinguish the following cases: (1) If rrii = 1 = mi, for i = 1 , 2 . . . . , n, it follows from (A.35), x7; G M 7 , that Ax, = zlxl.
(A.39)
Defining the matrix X = ( x i , . . . , x n ), we obtain
0
•••
0 \
0
AX = X
(A.40)
0
\ Considering that the matrix X is nonsingular, we define the diagonal matrix B similar to A by
(2) ra? = l,m ? < ra?;. In this case we can choose m 7 linearly independent vectors in M^, such that (it is Z12 = 0): AXJ = ZiXj,
j = 1, 2, . . . , rrii
and the matrix A can be transformed in diagonal form, as in the previous case. (3) At least an rrij is different from 1, rrij = frij and ZJ2 ^ 0 for t < ni-j — 1. Consider the choice of vectors xj
= Z^XQ . i = 0. 1. . . . , rrij — 1, where
XQ is a vector in Mj. From Lemma A. 5.1, these vectors are linearly independent and can be chosen as a base for Mj. From (A. 35) we have
Defining the matrix X = (XQ , . .. , x'rr? _ j . . . . . x0 have from the above relations:
Copyright © 2002 Marcel Dekker, Inc.
x
m s -i )>
we
APPENDIX A. FUNCTION OF MATRICES
254
AX = X
V Since X is rionsingular. a matrix J similar to A can be defined as J = X~1AX = diag(Ji,J2,...,Js). The structure of B is block diagonal; each block has the form 0 1
\
'-.
(A.42)
(4) At least an rrij is different from f arid ZJ2
0 for 0 < t < rrij. Choos-
ing x{ we define the set of vectors x- — for 0 , 1 . . . . , t < t. These t vectors are linearly independent (see Lemma A.5.1). but they are not enough to form a base of Mj. Choose another vector xp independent of the previous ones and define x^ = Zj2X z and so on until a set of rrij linearly independent vectors has been found. Then we proceed as in the previous case.
The matrix J is block diagonal as in the previous case, but the block corresponding to the subspaces Mj can be decomposed in different subblocks with each one corresponding to one chain of vectors. Each subblock is of the type (A.42). The matrix J is said to be the Jordan canonical form of the matrix A. Each chain associated to Mj contains an eigenvector associated to Zj (the last vector of the chain). The number of eigenvectors associated to Zj is the geometric multiplicity of the chain. The dimension of Mj is the algebraic multiplicity of zr
A.6
Norms of Matrices and Related Topics
The definitions of norms for vectors and matrices can be found on almost every book on matrix theory or numerical analysis. We recall that the most used norms in a finite dimensional space IRS are:
Copyright © 2002 Marcel Dekker, Inc.
A. 6. NORMS OF MATRICES AND RELATED TOPICS
255
(1) Ni = E?=iM, (2) IM|2 = (E?=it;?) 1/2 , (3) \\v\\oo = maxi
(2')
(3') H^Hoo = maxi<j< s where A is any s x s complex matrix, AH is the transpose conjugate of A, and p(A) is the spectral radius of A. Given a non-singular matrix T, one can define other norms starting from the previous ones, namely, \\V\\T = \\Tv\\ and the related consistent matrix norms ||^4||T — HT^-ATII. If T is a unitary matrix and the norm chosen is || • ||2, it follows that \\A\\ = \\A\\T(A.44) For all the previously defined norms the consistency relations P*II<MIIINI
(A.45)
and
(A.46) hold, where A,B,x are arbitrary. Theorem A. 6.1 For every consistent matrix norm one has p(A] < \\A\\.
(A.47)
Proof. Let A be an eigenvalue of A and v the associated eigenvector. Then we have
from which (A.45) follows.
Copyright © 2002 Marcel Dekker, Inc.
D
256
APPENDIX A. FUNCTION OF MATRICES
Corollary A. 6.1 If \\A\\ < 1, then the series f>'
(A.48)
i=0
converges to (I — A)" 1 , and
Proof. From Theorem A. 6.1 it follows that p(A) < 1. and the results follow from Theorem A. 4.1 (see also Exercise A.I). D Another simple consequence is the following (known as the Banach lemma). Corollary A. 6. 2 Let A, B be s x s complex matrices such that HA" 1 )] < a. | A — B < 8, with a/3 < 1. Then B~} exists and
Proof. Let be C = A"1 (A - B}. By hypothesis \\C\\ < a/3 < 1. Then (/ - C)-1 exists and |(7 - C)~l < 1/(1 - a/3). But B~} = (I - C)~lA~l, and then \B~l < a/(l - a/3). D Theorem A. 6. 2 Given a matrix A and e > 0, there exists a norm \\ • \\ such that \\A\\ < p(A) + e. Proof. Consider the matrix A' — ~A and let X be the matrix that transforms A' into the Jordan form (see section A. 5). Then -X~1AX = Jf = -D + H. c ( where D is a diagonal matrix having on the diagonal the eigenvalues of A and H is defined by (A.30)'. For any one of the norms (I'), (2'), (3'), ||#|| = 1, and p| < p ( A ) . It follows that \X~1AX\\ = \\A\ x < \ D\\ +e\H\\ < p(A) + e. which completes the proof. D
A. 7
Nonnegative Matrices
In many applications one has to consider special classes of matrices. We define some of the necessary notions below. Definition A. 7.1 An s x s matrix A is said to be (1) positive (A > 0) if avj- > 0 for all indices. (2) nonnegative (A > 0) if a/j > 0 for all indices.
Copyright © 2002 Marcel Dekker, Inc.
A.7. NONNEGATIVE MATRICES
257
A similar definition holds for vectors x e Rs considered as matrices s x 1. Definition A.7.2 An s x s nonnegative matrix A is said to be reducible if there exists a permutation matrix P such that
PApT
=(c D
where B is an r x r matrix (r < s) and D an (s — r) x (s — r) matrix. Since PT = P~l, it follows that the eigenvalues of B form a subset of the eigenvalues of A. Definition A.7.3 A nonnegative matrix A which is not reducible is said to be irreducible. Of course if A > 0 it is irreducible. Theorem A.7.1 If A is reducible, then all its powers are reducible. Proof.
It is enough to consider that
PA*PT = PAPTPAP = ( B"
° )
u2
V °
and proceed by induction.
)
D
Definition A.7.4 An irreducible matrix is said to be primitive if there exists an m > 0 such that Am > 0. Definition A.7.5 An irreducible matrix A is said to be cyclic if it is not primitive. It is possible to show that the cyclic matrices can be transformed by means of a permutation matrix P to the form
•-•
0 T
PAP =
Gr\
i
0
0
0
G2
!
0
••• Gr-i
0
(A.50)
J
In case when A is irreducible we have the following result (due to PerronFrobenius). Theorem A.7.2 // A > 0 (or A > 0 and primitive) then there exist AQ positive and XQ > 0 such that
Copyright © 2002 Marcel Dekker, Inc.
258
APPENDIX A. FUNCTION OF MATRICES
(a) AXQ =
(b) if X 7^ XQ is an eigenvalue of A then \X\ < XQ, (c) AQ is simple. If A > 0 but is not primitive, then (a) is still valid but \X\ < XQ in (b}. Theorem A. 7. 3 Let A > 0 be irreducible with XQ its spectral radius. Then the matrix (XI — A)~l exists and is positive if \X\ > AQ. Proof. Suppose |A| > AQ. The matrix A* = X~1A has eigenvalues inside the unit circle. Hence it follows (see Corollary A. 4.1) that (/ — A*)~l is given by oo
(/-A*)" 1 -^ A*1 T= 0
from which we get 00
(XI - A)" 1 = A- ] (7 - A*)- 1 - A'1 ^(A^ i=0
The second part of the proof is left as an exercise.
Copyright © 2002 Marcel Dekker, Inc.
D
Appendix B
The Schur Criteria B.I
The Schur Criteria
We have seen in Chapters 2 and 3 that the asymptotic stability problem for autonomous linear difference equations is reduced to the problem of establishing when a polynomial has all the roots inside the unit disk in the complex plane. This problem can be solved by using the Routh method (see for example [160] and [19]). In this Appendix we shall present the Schur criteria, the one most commonly used for such a problem. Let
be a polynomial of degree k. The coefficients pi can be complex numbers. Let
(pi are the conjugates of pi) be the reciprocal complex polynomial q(z] = zkp(z-1}. Let S be the set of all the Schur polynomials (see Definition 2.7.4). Consider the polynomial of degree k — 1:
p(V(z)
= vwW ~z P°Q(Z)
It is easy to see that p^l\z] = Y!i=i(pkPi - PoPk-i)zl~l. Theorem B.I.I p(z) e S iff (a) |po| < \Pk\ and (b) pW(z) eS. 259
Copyright © 2002 Marcel Dekker, Inc.
APPENDIX B. THE SCHUR CRITERIA
260
Proof.
Suppose p ( z ) G S and let z\, 22, • • • , Zk be its roots. Then \Pk\
and condition (a) is verified. On the unit circle \z\ = I one has k
D >;=o
- \p(z}\.
Since condition (a) is verified, we get \Pkp(z)
> \Pop(z)\ = \Pop(z}\ = \PQQ(Z)\ = | -p0q(z)\.
Applying Rouche's theorem (see [90]) it follows that the polynomial Pkp(z) and pkp(z) — Poq(z) — zp^(z) have the same number of roots in \z\ < 1, which means that p^(z) 6 S. Suppose now that p ( z ) e 5 and |po| < \Pk\- It follows that on l , \ p k p ( z ) \ > | — poq(z)\ and again by Rouche's theorem the polynomial Pkp(z) has n roots inside the unit disk: that is, p(z) E S. D The previous theorem permits us to define an algorithm to check recursively if a polynomial is a Schur polynomial. The algorithm is very easily implemented on a computer. The next theorem, which is similar to the previous one, gives the possibility of finding the number of roots inside the unit disk. Consider the polynomial of degree k — 1 fc-i
Tp(z) =
pkq(z) =
The polynomial Tp(z] is called the Schur transform of p ( z } . The transformation can be iterated by defining Tsp = T(Ts~lp), for s — 2, 3, . . . , k. Let 7., = Theorem B.I. 2 Let 7S ^ 0, s = l.2....,k. and let si,S2...-.sm be an increasing sequence of indices for which 7>s < 0. Then the number of roots inside the unit disk is given by h(p] — '^Jjl-i(-^~l(k + 1 — Sj). Proof. See Henrici [90]. D Analogous results can be given for Von-Neumann's polynomials. Let A/" be such a set. Theorem B.I. 3 A polynomial p(z] is a Von- Neumann polynomial iff either (!) bo | < bfc| and (2)
Copyright © 2002 Marcel Dekker, Inc.
B.I. THE SCHUR CRITERIA
or (!') p(l\z) = Q and
(2') j/(z) G S. Proof.
See [127].
Copyright © 2002 Marcel Dekker, Inc.
D
261
Appendix C
The Chebyshev Polynomials C.I
Definitions
The solutions of the second-order linear difference equation yn+2 - 2zyn+i + yn = 0
(C.I)
where z G C, corresponding to the initial conditions
yo = 1,
3/1 = z,,
(C.2)
y_! = 0 ,
yo = 1,
(C.3)
and are polynomials as functions of z and are called Chebyshev polynomials of the first and second kind, respectively. They are denoted by Tn(z) and Un(z}.
We list the first five of them below: To(z) Ti(z) T2(z) T3(z) T4(z}
= l U-i(z) = 0 =z U0(z) = l = 2z2-l Ui(z} = 1z = 4z3 - 3z U2(z) =4z2 -I 2 4 = 8z -8z + l U3(z) = Sz3 - 42.
Since the Casorati determinant
Tl(z]
Uo(z)
is equal to 1, the general solution of (C.I) can be written as yn(z) - ciTn(z) + c2Un-i(z).
263 Copyright © 2002 Marcel Dekker, Inc.
(C.4)
264
APPENDIX C. THE CHEBYSHEV
POLYNOMIALS
Let w\ and w^ be the roots of the characteristic polynomial associated with (C.I), that is, w2 -2zw + l = Q. (C.5) It is easy to express Tn(z) and Un(z] in terms of w™ and w^. In fact, considering that w-2 = w^ , one obtains Tn(z)
=
^coshnlog^ + _ 1)1/2
-l)),
(C.6)
2
(C.7) ^
^
For z 6 [— 1, 1], by setting z = cos 9, it follows that w\ — eld and ^nl 2 ) — cosh n log el = coshnz'^ = cosnO. sin(n + 1)0
£w) = —S1I10 —^— , which arc the classical Chebyshev polynomials.
C.2
Properties of Tn(z) and Un(z)
One can easily prove that the roots of Tn(z) and Un+i(z) are 2fc = cos?^ti-,
n
2
fc = 0,l ..... n - 1 ,
(C.8)
and /T7T"
2fc = cos — , fc = l , 2 ..... n - 1 , (C.9) n respectively. Other properties of T n (z) and Un(z] are the following, which can be easil verified.
(1) w?=Tn(z) + (T*(z) (2) T n (2) = T-n(z), (symmetry) (3) Tjn(z] = Tj(Tn(z)},
(semigroup property)
(4) C/ 7 - n _ 1 ( z ) = £7 J -_ 1 (r n (^)), (5) U-n = -Un-2(z), (6) Tn-!(z) - ^r n (z) - (1 - z 2 )I/ n _i(e), (7)
Un^(z)-zUn(z}^-Tn+l(z},
Copyright © 2002 Marcel Dekker, Inc.
C.2.
PROPERTIES OF TN(Z) AND UN(Z)
(8) Un+j(z) + Un-j(z) =
265
2Tj(z)Un(z).
From the last property one can derive many others. For example, (9) Un+j-!(z) + Un-j-^z) = 2TJ(z)Un-l(z), (10) Un+j(z) + Un-j-2(z)
(11) 2Tn(z)Un(z)
= 2TJ + l(z)Un-l(z),
= U2n(z] + I ,
(12) 2Tn+l(z)Un-i(z)
= U2n(z)-l,
(13) 2Tn(z) = Un(z)-Un-2(z). Among the properties of Chebyshev polynomials the following has a fundamental importance in approximation theory. (14) Let Pn be the set of all n degree polynomials having the leading coefficient 1. Then for any p(z) € Pn, max \2l~nTn(z)\ < max
\p(z}\.
The proof of this property is not difficult and can be found in several books on numerical analysis. (15) Tn(z) and U n ( z ) , as functions of z, satisfy the differential equations 7^(z) = nC/ n _i(2:),
(C.10)
U'n(z) = -(z2 - l ) ~ l [ z U n ( z ) -(n (1 - z2)T^(z) - zT'n(z] + n2Tn(z) = 0,
(C.ll)
(1 - z }U'^(z) - 3zU^(z] + n(n + 2}Un(z) = 0.
(C.12)
2
The first two are consequences of the definitions (C.6) and (C.7), and the other can be derived from them. Finally, Tn(z) and Un(z) satisfy the orthogonal properties: (
}
(17)
2 [l Tn(z)Tm(z)
a2
I 26nm for Snm for
- [l (I - Z2)l/2Un(z)Um(z)dz 7T J-l
= 6nm,
(is) A; ^ 0, /c / m, fc = 0. k = n,
where Zj = cos ^ . j — 1 , . . . , n — 1 .
Copyright © 2002 Marcel Dekker, Inc.
n = 0, n>0,
Appendix D
Solutions to the Problems D.I
Chapter 1
1.1 From (1.4) 3/5 = E4yi = Y^j-o (j)^yi and from the scheme A° A1 A 2 A 3 A 4 2/i -2 2/2 -2 0 2/3 0 2 2 1 / 4 4 4 2 0 0 we get 2/5 = 10.
1.3 The first result of problem 1.2 can also be written
(
pia/2
_ f,-ia/2\
^
n
c
2
— 2zsin-e^ ox+6+a/2) /
2
By taking the real and imaginary parts one gets the result. 1.6 Using the Stirling transform one has j3 = j^+Sj^-t-j^ and A"1^3 = l(2) .^^ -,'(4) „ . . . . £1 , ,-(3) , ^ + 2 """J ^ "44 from which one obtains:
j=o
1.4 Let 7/05 2/1, • • • De a sequence. We have
Let ^ = (*+*). Consider then that (see 1.20) A n y 0 = ( TO ^ n ) and
267
Copyright © 2002 Marcel Dekker, Inc.
268
APPENDIX D. SOLUTIONS TO THE PROBLEMS
1.7 From the result of problem 1.3 we have A-I
sin(ax + 6) 2 sin a/2
Setting a = q. b = —q/2 and x = n, we have: A -1 s'm(qn — q/2) A cos an = ; 2 sm o/2 and
cos, =
=
1.10 From x("+*-«) = XW(X - n )(^-") and ;r( x ) - r(rr + 1), (x -
1.13 Using the Stirling transformation, p(x) can be written in the form P(X) — ICi^o a i^^^- Applying A , A 2 . . . . . A f c and putting x — 0 one gets au?, gets — ., 1.14 One has: q-n
/
\
q—n-l
= E
n
1
~ ~ ^—> /
1
. o // ,w,
—1\
J. \
o— n-1
q—n—l
-,
~
V----L
v—>
— —
,
. .. A I/ /U7
— 1
-*-
~
-.
1
n- I
By setting j — I = / in the second term, it is easily seen that the two sums cancel.
Copyright © 2002 Marcel Dekker, Inc.
269
D.I. CHAPTER 1 1.15 One has: -n-]
5(g,/,n)
—n
=
q-n-l
+ E
' -1
1.26 Letting yn — zn l the equation becomes zn+\ = zn + 1. 1.27 Letting zn = ^4 1//2 cothy n one has yn+\ — 2yn. 1.28 (B) From \ogyn+i = loga+p\ogyn, by posing zn = \ogyn one obtains — pzn + log a, and then
1.29 By substituting yn = ^f^ the equation becomes zn+\ = which one obtains yn = ^[1 — (1 — 2yo)2"']-
1.30 1.32 It is not restrictive to consider the case i > j. One has
ltf =
3
J
S 'r
s/ \ s
j
= E
5=0
Copyright © 2002 Marcel Dekker, Inc.
/.A /A
I — S I \S
-P + P \ I , I — S
I
\S
, from
270
APPENDIX D. SOLUTIONS TO THE PROBLEMS Then take n = i 4- j. p = m = j.
1.35 From Ps = P(I + K}\ we get R(K) = e~sK(I + K)s. 1.37 From the result of problem 1.36 one has /
un <6exp
\ / , n _i n _i n=i Hl/2M V --i— +6 V exp ,W2M V -
It is known that ££=1 k~l/2 < 2nl/2 ~ L un
Tnen one has
< $ ( exp(/i 1 / 2 M(2n 1 / 2 - 1)) + ]T exp(/i 1 / 2 M(2(n - s - I) 1 / 2 - 1)) V s =0
1.38 Let Vn = c + ~E^n+1ksVs. One has yn < Vn and Vn = Vn+l + kn+iVn+i, then is Vn = flUn+il 1 + fcs)^ < ^ ex P(EUn+i fcs) and for ^ -^ oo, yn < KO 1.39 For a < 1 one obtains y 2 +1 < y2 + bn(yn + y n +i) and them yn+i < Un + bn, form which yn < yo + H?=o ^'- ^or a > -^ one ^as Vn+i ~ a?/n ^ M2/n + yn+i) and then 1/2
^7
n
,
yn+i - a ' yn < bn^-^ [/z -•- < 6 n ,
a yn + yn+i
form which one obtains
D.2
Chapter 2
2.11 The roots of the characteristic polynomial are z\ — a + b\/~d and 2-2 = zf 1 . Then j/n = a.z™ + (3z^n. xn — 7zf + <5zf n . In order to have integer solutions it will be a = j3, 7 — —5. The initial condition leads to a = 1/2 and 5= I/ (26). 2.13 By the Cayley theorem we have p(A) — 0 where p(z) is the characteristic polynomial of A. It follows then that, for all n.
Copyright © 2002 Marcel Dekker, Inc.
D.2. CHAPTER 2
271
Consequently, each entry of the matrix a^v satisfyies
i=0
2.15 Let Cj+i = Si+i -5i+i,rj = ai+i -a^+i,^ = l C ( s ; + flj+i). One has = €i 4- ri — <5f, from which n-l
From this, one deduces that one must keep Y^$i\ as small as possible, and this can be achieved adding first the smaller a* in absolute value. If \a,i\ < a, then \Si\ < ia. Finally one has N-l
kwl < kN + 10~*a Y^ i < kn + lO^a showing that the error grows like TV2. 2.20 From (2.70) we have oo
-r^oo
J2)
n+2
where ^Q(2) = q\(2) — 0 and q^ — l/n. The roots of the denominator are 1 and 2. In the unit circle it can be written 1
2
2
2
3
~2
x-l
°°
2+
with 7i bounded and limn=o Y^o 1i — °° (why?)- Then one has
i=0 2) where Cj = En=2 9n7*-nThen yn = = cn_2 = = Ej=o j+i7n-j-2 <
2.21 Taking / = 0, the error equation becomes p(E)en = /?(!), whose solution is the sum of the general solution of the homogeneous equation and a particular solution. The general solution is given by (2.43), from which it follows that p(z) must be a Von-Neumann polynomial.
Copyright © 2002 Marcel Dekker, Inc.
272
APPENDIX D. SOLUTIONS TO THE PROBLEMS
2.22 Taking / = 0 as in the previous problem and e$ = e\ — . . . = ek-\ = 0, we have (see 2.60) en = p(I)/p(I), and this cannot be zero for n oo(nh < T) unless p ( l ) = 0. Similarly for / = I : p(E)en = 2.24 Use Theorems B.I.I and B.I. 2 of Appendix B. For case (a) one finds D = -i,i.
D.3
Chapter 3
3.3 The roots of the characteristic polynomial are z\ = a + b\/[d) and 22 = z if 1 . Then xn — az™ + (3z^n. yn = 72™ + 5z^n . In order to have integer solutions it will be a = j3, 7 = —5. The initial conditions lead t o a = 1/2. 6= 3.9 Exchanging with care the sum in the expression X^=o Pi(n} Z^j=n0 -^(n+ k — i , j ) g j , one has Y^j=n9i ^i,=QPiH(n + k~~i,j}+gn — gn. (Remember that some values of H are zero.) 3.13 \zs\ ^ 1.
3.14 It depends on the roots of 22 + p\z + p2. It will be H(n + l)+piH(n)+p2H(n-l) H(I)+PlH(0)+p2H(-I}
= 0 = 1.
forn ^ 0
According to the values of the roots, several cases are possible. For example: (a) |2! < 1 , N > 1 ~ \ (zi+Pi (b) \zi\ < I,\z2\ < l,H(n) = (21 - z2)-l(z? - z%) for n > 0 and H(ri) = 0 for n < 0. O. -L <3
XJ (V 77-
J7 IJ —
• Tr sin
1 :' 1/rj / • n •^' t - -— ^-—'7=U
• Ir. sin
^/'J -JJ •
3.16 Let y^ the nih element of the ith column of the inverse matrix C^1. By multiplying CAT and its inverse one shows that the columns of C^ are solutions of the boundary value problems:
= 5\
Copyright © 2002 Marcel Dekker, Inc.
D.3.
CHAPTERS
273
for i = 1, 2, . . . , N. Let z\ and z% be the roots of 7 4- az + fiz2 = 0. The solutions are: for
+
n
z _ 2 where #(n) = 2 z _ z 1 . One sees that for \z\zi\ < 1 and j ^ j > 1, oo. the elements remain bounded for N
3.17 Suppose that A(n) is a companion matrix that is of the form (3.20). AT(n) is not of the same form, and then the components of xn given by (3.46) are not successive values of the solution of a scalar equation. Now consider the matrix \
-Pk(n) 0
V(n} =
V
0
One easily verifies that x^ =
+ 1), where
and tn is the last component of xn. From this new vector one has Xn+iV(n + \)A(n)V-l(n) = xZ+1tl(n). The matrix fi(n) = K(n + V~ 1 (n) is given by 1 0 0 0
0 \
1
Pkn
+1)0
oy
which is the companion form for the adjoint equation defined in Section 2.2. 3.18 In order to have periodic solutions it must be CN = 7, where 7 is the identity matrix. It follows that the off-diagonal entries of CN must vanish. This is impossible for \z\ > 1, since Chebishev polynomials never vanish for such values of \z\ (see Appendix C). For z < 1, UN-I(Z) vanishes for zk = cos(^), k = 1, 2 , . . . , fc — 1. Moreover, we - There will be periodic have Uiv(zk) = ( — l)k and ~UN-2(zk] — (~ solutions in almost every point. 3.19 Since the fundamental matrix is a power of the matrix C, imposing that Cn+J = CnCi , the result is obtained by equating the entries of the both sides matrices.
Copyright © 2002 Marcel Dekker, Inc.
274
APPENDIX D. SOLUTIONS TO THE PROBLEMS
3.20 Let / and r be the two quantities. Divide the decagon in 10 isosceles triangles having all the the vertices at the center. Obviously the vertex angle of each triangle is equal to > = Tr/5, while the other angles are both equal to 20. One has then r
. . = 2cos(d>) = p.
sn sin
3.27 From the definition, one has TV
i=0 and
N
x ]T L,$(n, i, j + l)T(j + 1. m) = I + AG(j, j). z=0
3.28 One has N
N
i=0
N i=0 N s=0 TV
TV
3.29
5= 0
n/v-1
^ G(n, s)bs] + 6n = ^4yn + bn. s=0
Copyright © 2002 Marcel Dekker, Inc.
DA.
CHAPTER 4
275
For what concerns the boundary conditions one has: TV
N nN-l
AT
bs = w.
3=0
D.4
Chapter 4
4.3 The system is symmetric with respect to the origin: gi(—x,—y] = —gi(x,y) for i — 1,2. This allows us to consider only the upper half plane. According to the signs of g\ and #2, let us consider the following sets: A = {{x,y)\y>2x} 9\(x,y] > 0 , 0 2 ( z , 2 / ) > 0 B - { ( x , 7 / ) | 7 / < 2 x a n d x 2 ( 7 / - x ) + 2 / 5 > 0} g i ( x , y ] >0,g2(x,y) < 0 C = {(x,y)\x2(y-x)+y5 < 0} 5i(^,y) < Q,9i(x,y} < 0 It is clear that for ( x k , y k ) ^ ^4,Axfc > 0, Ay/j > 0, that is both the sequences Xk,yk are not decreasing. If they remain in A, they will y never cross the line y = 2x and the ratio 9yin2\('xiy \) has to be greater than 2 for all k. This means that x^/ _~^ 5 > 2, which is impossible because the y in the denominator has degree larger than the y in the numerator. The sequences must cross the line y = 1x and enter in B. In a similar way it can be shown that they cannot remain in B. They will enter in C, where both Ao;/- and Ay/t are negative and the sequences are decreasing. Now if y^ > 0 it follows that . -
2/fc +
_ yk(r2k + r6k+y2k- 2xkyk) -
_
and similarly for x^. This shows that the sequences must remain in C and must converge to a point where both Ax^ and Ayk are zero, which is the origin.
Copyright © 2002 Marcel Dekker, Inc.
276
APPENDIX D. SOLUTIONS TO THE PROBLEMS Starting from (—5, 6) for small positive 8, it is easy to check that in the following iterations the points (xfc,yfc) have increasing distance from the origin until they reach the regions B or C, showing that the origin is unstable.
4.5 The solution is ((n no o)\
log n
( ° + 2) 0
^ ' ^ = Io^T^ n
The series X^n0 \y( -> ^o, 2/o)| does not converge, showing that the origin is not l\— stable. 4.9 In this case D is the set of all positive numbers. If yo G D, then y$ G D for all n. Consider V(y) = y/(l + y0 and AT/
AV
The set E1 is (0, 1} and W(x) —> 0 for x —> oo. Then, according to the theorem, yn is either unbounded or tends to E. In fact the solution ( — 2)" is yn = T/Q , and it tends to zero if yo < 1 and n even and it is unbounded for n odd. If yo — I then yn~\ for all n. 4.11 Let y = 3 — 4z. The equation becomes 2 n+ i = 4z n (l — z n ), which coincides with the logistic equation considered in Chapter 8. 4.12 The eigenvalues of A are AI = | with multiplicity s — 1 and A2 = (1 — -s)/2. They can be obtained easily by considering that A is a circulant matrix and the eigenvalues are the values assumed by the polynomial p(z] — —\(z 4- z2 -f . . . + zs~l) on the si/l roots of the unity. There is global asymptotic stability for s — 2, only stability for s = 3 and instability for s > 3. 4.13 In order to have Vn+\ > 0, it must be Vn - uj(Vn) > 0. If u and v are such that u > n. u — u(u) > 0, i'~ w(v) > 0, and u — v > o;(u)— u;( / y) one has u — uj(u) > v — a;(v). The solution satisfies un = UQ — X^?=o a; ( w j)Since uj is increasing and it must remain positive, it follows that Uj —* 0. 4.14 Let x £ Q(yo), and let there exists a sequence n,; —> oo such that y(nl.n0.yo) -> .r. But y(n i + i,n 0 ,yo) = /(y(^?., ^o, 2/o)) and lim
n n ,
=
;r
^
showing that /(x) G ^(T/O) and that fi(yo) is invariant. Now let y^ be a sequence in Q(yo) converging to y. We shall prove that y G Q (yo). For each index /c, there is a sequence mf —» oo such that y(rn^n().yo} —> y fc . Suppose for simplicity that dist(^, y('m^, HQ. J/Q))
Copyright © 2002 Marcel Dekker, Inc.
D.5. CHAPTER 5
277
< A;"1 and raf > k for i > k. Consider the sequence m^ = ra£. Then dist(y,y(m fc ,no,yo)) < dist(y,yfc) + fc"1 which implies dist(y,y(mjb,no,yo)) -* 0 and then y G
D.5
Chapter 5
5.2 By multiplying equation (5.3) by pn-i we obtain (xpn,pn-l)
= —• &n
Change n in n — 1 in the same equation and multiply by pn(x). We have Q-n-l
5.3 Define Dh — diag(/ig , hi , . . . , /i^_j). The vector Dh-1p(x] is now normalized. The new matrix is then T = 5.6 From (<jj + r^) 2 < 1, we have 0 < (ai — TJ) < 1 — 4<7;T^ 5.8 Divide the two equation (5.29) and (5.30) and obtain
D.6
Chapter 6
6.2 From the mean value theorem one has F(x) - F(y) - F'(x}(y - x) = f\F'(x + s(y - x)) - F'(x)}ds(y - x); Jo \\F(x) - F(y) - F'(x}(y - x}\\ < 7 /' 8ds\\y - x\\2. Jo
6.4 Let QQ = !/?7- One has \\xn+i - xn\\ < and k+m— 1 \\Xk+m-Xk\\
Copyright © 2002 Marcel Dekker, Inc.
<
^ j=k
APPENDIX D. SOLUTIONS TO THE PROBLEMS
278
\xk -xk-i\
TL. i k-\\
x
_9
—2
6.5 Consider the equation un — ^~in un-\- One has -%£- — ^ * , that is ^- is constant and must maintain its initial value u\ft\. Then un — Ai n (wi/£i). It follows then that Ax n < un. Moreover "A^" is decreasing. That is, for m > n, " A ^ m '' < '' A ^ n '' and n - xn"II — < Z-/1' ^ Hz
3=0 p-1
Atn+j rllAXnl
from which it follows that t* — t
lim | x n + p - x
tn
Being ||Azn|| < un one has
6.6 In this case the comparison equation is AU Un =
Copyright © 2002 Marcel Dekker, Inc.
D.7. CHAPTER 1
279
. vy-i whose solution is un = At n (j 1 J . A s before one has II** - *»ll < (** - *n)
6.7 Let yn — I — zn. The equation becomes yn+i — \ (yn + the result of problem 1.27.
1 2
*° j . Apply
6.8 From the given solution one has ZQ — 1 — (1 — 2zo)1/'2 coth k from which k = logfl" 1 / 2 and then zn Z
l — -
1
1+
* 22"nI 1 —/jOn B
~
-,
1
2 2;..W Oj ZZ
from which
6.12 The equation (6.48) is the homogeneous equation related to (6.47) when one takes _ 2/n-i x — n
yn
Imposing that (6.50) satisfies the nonhomogeneous equation one gets (6.49). In fact one has yn+i — 25yn + xnyn + zn = gn from which _
D.7
z
Un+l
n ~ 9n _
Chapter 7
7.1 Consider the term £j=d An~*~lWj and the decomposition (A. 13). It follows that A = Zn + Y^k=2(^kZki + Zk2] = S+Si where d is the number of distinct eigenvalues of A. Using the properties of the component matrices Z^j it is seen that 5J = 5 for all j and limj--^ 5^ = 0. Moreover A? - # 4- S{. The sum E"=o An-i~lWj becomes
^E^ + E^r'-x-3=0
}=0
The quantity SWj is called the essential local error. If the errors are such that SWj = 0, one can proceed as usual. 7.5 Applying the theorem B.I. 3 one has p^(z) = —4Req and p'(z) — 2(z — q). It follows that p(z) € N iff Reg = 0 and || < 1.
Copyright © 2002 Marcel Dekker, Inc.
APPENDIX D. SOLUTIONS TO THE PROBLEMS
280
7.8 Rewrite the equation (7.14) such that the linear autonomous matrix A is the companion matrix of &(z), obtaining En+i = (A + Bn}En + Wn, where Bn — $kbT with b is now the vector with components. - cn+j}
, _ 3
2 - h(3kcn+k
Find a bound for bj independent on n and consider that by hypothesis \\A\\ < 1. 7.9 Consider the nonhomogeneous equation C^xN — \XN = 6^N\ where \\XN\\ = 1 for all N and ||<5^|| = e 2 . Component-wise one considers the equation fix^-\ + (a — ^)%n + jx^+l = 6^ whose solutions are chosen such that the initial condition (a — X)x^ +7^^ = 0 is satisfied. In the hypothesis made, the solution will diverge and (7.60) will not be satisfied. 7.12 The matrix AN is the matrix representing the centered second-order discretization, that is
o \
/ -2 1 1 - 2 0
0 0
1
V 0
0
Ax AM
-2 ) NxN
I '
which is symmetric. The spectrum of (Ax2)"1!)2^ is S — {—2 -f 2cos 0,0 < 9 < TT}. The spectrum of D^N is then 51//2 which is an interval of the imaginary axis. The midpoint rule can be used because its region of absolute stability lies on the imaginary axis and it can be chosen appropriately in order that the region contain
D.8
Chapter 8
8.2 From 2.70 one has X ( z ) =
M
— > . ,d.; t—ir — \ '•
The problem reduces to the
study of the roots of the denominator. They are the reciprocal of the characteristic roots and they are outside the circle 5(0, Xl ). The series X(z] = ~Y^=QX\(n}zn is then convergent in this circle. To see if z\ = A^ is less or equal to 1, one considers that 1 — Y^i—i aiz% is monotone decreasing on the real line from 1 to — oo and the z\ will be
Copyright © 2002 Marcel Dekker, Inc.
D.9. CHAPTER 9
281
less or greater than 1 according to the sign of 1 — ]T en. If this quantity is positive, then z\ > 1, otherwise z\ < 1. In the first case one has 1
V x (n} = n=0
^ *
and XI(H) —> 0. In the second case xi(n) —> oo. If 1 — ]T0i = 0, then by Theorem 2.6.2 the solution XI(H) is unbounded. 8.6 By definition f [ x j ( x ) ] = / ( x ) - / ( 3 : ) . If /( 2 )(x) = x then the fraction assumes the value — 1, and vice versa. 8.8 The model is Pi = PoPo (n + l)Pn+i - (Pn + n}Pn + pn-lPn-l = 0
NPN-pN-iPN-i=0 To obtain the solution, observe that
That is nPn — /9 n _iP n _i = K, where K is a constant. From the first equation one sees that K = 0. One obtains
n
and then from
D.9
= Pi — ^
one
obtains
Chapter 9
9.1 Let x* be the common limit. One has
i xn+i - x* = xn+i - (xnyn)2 = (x% - yn and i
Xn
i
/ 2 X * = Xn2 \Xn
i
\ yn2 )i
From which it follows that xn+\ — x* — x~l(xn — x*) 2 . 9.3 Just take yn = A/xn.
Copyright © 2002 Marcel Dekker, Inc.
282
APPENDIX D. SOLUTIONS TO THE PROBLEMS
9.4 One easily derives that
yn+i - yn
f(yn]
and such a ratio has to be equal to —1 since both points are on the line x + y — a = 0. 9.6 Let yo be prime, the yo and yo + lare relatively prime. So is yo(yo + 1)4-1 and so on. Since yo — 2 and yo + 1 — 3 are prime, then Corollary 9.4.1 applies and the same will be true for the successive values.
Copyright © 2002 Marcel Dekker, Inc.
Bibliography [1] C. A. ARNEODO, P. FERRERO AND TRESSER, Sharkovskii order for appearance of superstable cycles: An elementary proof, Comm. Pure and Appl. Math., XXXVII (1984), pp. 13-17. [2] E. A. WEISSBERGER, Technique of Organic Chemistry, Distillation, vol. Vol. IV, Interscience, New York, 1951. [3] O. ABERTH, Iteration methods for finding all zeros of a polynomial simultaneously, Math. Comp., 27 (1973), pp. 339-344. [4] L. ACETO AND D. TRIGIANTE, The matrices of Pascal and other greats, Amer. Math. Monthly, 108 (2001), pp. 232-245. [5] R. AGARWAL AND J. POPENDA, On periodic solutions of first order linear difference equations, Math. Comput. Modeling, 22 (1995), pp. 11-19. [6] R. P. AGARWAL, On multipoint boundary value problems for discrete equations, Jour, of Math. Analysis and Appl., 96 (1983), pp. 520-534. [7]
, Initial value methods for discrete boundary value problems, Jour. of Math. Analysis and Appl., 100 (1984), pp. 513-529.
[8]
, Difference equations and inequalities: theory, methods, and applications., Marcel Dekker, New York, 2 ed., 2000.
[9] R. P. AGARWAL AND E. THANDAPANI, On some new discrete inequalities, Appl. Math, and Computation, 7 (1980), pp. 205,224. [10] ——, Some inequalities of Gronwall type, Arialele Stjietifice Univ. lasi., XXVII (1981), pp. 139-144. [11] C. AHLBRANDT AND W. T. PATULA, Recessive solutions of block tridiagonal nonhomogeneous systems, J. of Diff. Eq., 1 (1995), pp. 1— 98. [12] C. AHLBRANDT AND A. C. PETERSON, Discrete Hamiltonian Systems, Kluwer. Boston, 1996. 283
Copyright © 2002 Marcel Dekker, Inc.
284
BIBLIOGRAPHY
[13] P. AMODIO, Optimized cyclic reduction for the solution of tridiagonal systems on parallel computers, Comp. Math. Appl., 26 (1993), pp. 4553. [14] P. AMODIO AND F. MAZZIA, Backward error analysis of cyclic reduction for the solution of tridiagonal systems, Math. Comput., 62 (1994), pp. 601-617. [15] F. ASHBY, T. MANTUEFFEL. AND P. SAYLOR, A taxonomy for conjugate gradient methods, SIAM J. Numer. Anal., 27 (1990), pp. 1452-
1568. [16] F. V. ATKINSON, Discrete and continuous boundary value problems, Academic Press, 1964. [17] N. S. BAKHVALOV, Numerical Methods, MIR, Moscow, 1977. [18] B. BARNA, Uber die diverenzpunbe des Newtonches verfahrens zur bestinemmung von wurzelu algebraischen, Publications Mathematical Debrecen. (1956), pp. 384-397. [19] S. BARNETT AND D. D. SILIJAK, Routh algorithm, a centennial survey, SIAM Review, 19 (1977), pp. 472-489. [20] A. BERMAND AND R. PLEMMONS, Nonnegative matrices in the Mathematical Sciences, Academic Press, New York, 1979. [21] L. BRAND, Differential York. 1966.
and Difference
Equations, John Wiley, New
[22] L. BRUGNANO, Numerical implementation of a new algorithm for polynomial with multiple roots, J. of Diff. Eq. and Appl., 1 (1995), pp. 187207. [23] L. BRUGNANO AND D. TRIGIANTE, Tndiagonal matrices: Invertibility and conditioning, Lin. Alg. Appl.. 166 (1992), pp. 131-150. [24]
, Toeplitz Matrices and Difference Equations in Numerical Analysis. In Proc. of First Int. Conf. on Difference Eq. Tampa, Gordon and Breach. 1994. pp. 79-94.
[25]
, Polynomial roots: The ultimate answer?, Lin. Alg. Appl., 225 (1995), pp. 207-219.
[26] L. BRUGNANO AND D. TRIGIANTE, Solving Differential Problems by Multistep Initial and Boundary Value Methods, vol. 6 of Stability and Control: Theory Methods and Applications. Gordon and Breach, Amsterdam. 1998.
Copyright © 2002 Marcel Dekker, Inc.
BIBLIOGRAPHY
285
[27] K. BuRRAGE AND J. BUTCHER, Nonlinear stability for a general class of differential equation methods, BIT, 20 (1980), pp. 185-203. [28] K. BURRAGE AND J. C. BUTCHER, Stability criteria a implicit Runge-Kutta methods, SIAM J. Numer. Anal., 15 (1979), pp. 46-57. [29] J. BUTCHER, A stability property for implicit Runge-Kutta methods, BIT, 15 (1975), pp. 358-361. [30] J. BUTCHER, The Numerical Analysis of Ordinary Differential tions, J. Wiley, Chichester, 1987.
Equa-
[31] B. BuZBEE, G. GOLUB, AND C. W. NiELSON, On direct methods for solving Poisson's equations, SIAM J. Numer. Anal., 7 (1970), pp. 627656. [32] B. CARLSON, Algorithms involving arithmetic and geometric means, Amer. Math. Monthly, (1971), pp. 496-505. [33] J. R. CASH, Stable Recursions, Academic Press, London, 1979. [34]
, A note on the solution of linear recurrence relations, Num. Math., 34 (1980), pp. 371-386.
[35] F. CASORATI, // calcolo delle differenze finite accresciuto di nuovi teoremi..., Mem. Acad. Lincei Ser. Ill, 5 (1880), pp. 195-208. [36]
-, II calcolo delle differenze finite accresciuto di nuovi teoremi..., Annali di Matematica, 10 (1889), pp. 10-45.
[37] F. CHAITIN-CHATELIN. V. TOUMAZOU, AND E. TRAVIESAS, Accuracy assessment for eigencomputations: Variety of backward errors and pseudospectra, Linear Algebra Appl., 309 (2000), pp. 73—83. [38] S. S. CHENG AND L. Y. HSIEH, Inverse of matrices arising from difference equations, Utilitas Mathematica. 38 (1990), pp. 65-77. [39] T. CHIHARA, An Introduction to Orthogonal Polynomials, Gordon and Breach, London, 1978. [40] C. W. CLENSHAW, A note on the summation of Chebyshev series, MTAC, 9 (1955), pp. 118-120. [41] L. COLLATZ, Functional Analysis and Numerical Mathematics, Academic Press, 1966. [42] K. COOKE AND L. LADEIRA, Applying Carvalho's method to find periodic solutions of difference equations, J. of Diff. Eq. and Appl., 2 (1996). pp. 105-115.
Copyright © 2002 Marcel Dekker, Inc.
286 [43] C. CORDUNEANU, Principles of Differential Chelsea, New York, 1977.
BIBLIOGRAPHY and Integral Equations,
[44] C. CORDUNEANU, Almost periodic discrete processes, Libertas Math, 2 (1982), pp. 159-169. [45] G. DAHLQUIST, A special stability problem for linear multistep methods, BIT, 3 (1963), pp. 27-43. [46] —— , Error analysis for a class a methods for stiff nonlinear initial value problems. Num. Anal., Dundee, Springer Lect. Notes in Math., 506 (1975). pp. 60-74. [47] - . On stability and error analysis for stiff nonlinear problems, Part 1. Report Trita-NA-7508, 1975. [48] - , G- stability is equivalent to A- stability, BIT, 18 (1978). pp. 384401. [49] - , On the local and lobal errors of one-leg methods, Report, TRITANA-8110, 1981. [50] - , Some comments on stability and error analysis far stiff nonlinear differential Systems, preprint, NAD A Stockholm, 1983. [51] G. DAHLQUIST AND A. BJORK, Numerical Methods. Prentice-Hall, 1974. [52] G. DAHLQUIST. L. W.. AND O. NEVANLINNA, Stability of two step methods for variable integration steps, SIAM J. Numer. Anal., 20 (1983), pp. 1071-1085. [53] F. DANNAN, S. ELAYDI. AND P. Liu, Periodic solutions of equations, J. of Diff. Eq. and Appl, 6 (2000), pp. 203-232.
difference
[54] P. DAVIS AND P. RABINOWITZ, Method of Numerical Integration., Computer Science and Applied Mathematics. Academic Press, New York. 1984. [55] P. V. DER CRUYSSEN, A reformulation of Olver's algorithm for the numerical solution of second order difference equations. Num. Math., 32 (1979), pp. 159-166. [56] P. DIAMOND, Finite stability domains for difference Austral. Soc.. 22A (1976). pp. 177-181.
equations. Jour.
[57] - , Discrete Liapunov function with 5~v > 0, Jour. Austral. Soc., 20B (1978), pp. 280-284.
Copyright © 2002 Marcel Dekker, Inc.
BIBLIOGRAPHY
287
[58] R. D. DRIVER, Note on a paper of Halanay on stability of finite difference equations. Arch. Rat. Mech., 18 (1965), pp. 241-243. [59] E. DURAND, Solution Numerique des Equations Algebriques, vol. I, Masson, Paris, 1968. [60] L. EHRLICH, A modified Newton method for polynomial, Comm. ACM, 10 (1967), pp. 107-109. [61] S. ELAYDI, Asymptotics for linear difference equations, J. of Difference Equations, 5 (1999), pp. 563-588. [62]
, An Introduction to Difference Equations, 2ed., Springer-Verlag, New York, 1999.
[63] H. ELMAN, A stability analysis of incomplete LU factorization, Math. Comp., 47 (1986), pp. 191-217. [64] G. FARIN, Curve and Surfaces for Aided Geometric Design, Academic Press, Boston, 1990. [65] T. FORT, Finite Differences and Diffrence Equations in the Real Domain, Oxford Univ. Press, Oxford, 1948. [66] V. L. G. S. LADDE AND A. S. VATS ALA, Monotone Iterative Techniques for Nonlinear Differential Equations, Pitman Publishers Co., 1985. [67] G. GANDOLFO, Mathematical Methods and Models in Economics Dynamics, North-Holland. Amsterdam. 1971. [68] L. GATTESCHI, New results on some two dimentional iterative algorithms, Acad. Naz. dei Lincei, 147 (1998), pp. 137-159. [69] W. GAUTSCHI, Computational aspects of three terms recurrence relations, SIAM Rev., 9 (1967), pp. 24-82. [70] W. GAUTSCHI, Numerical Analysis, Birkhauscr, Basel, 1997. [71] G. W. GEAR, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice-Hall, Englewood Cliffs, 1971. [72] G. W. GEAR AND K. W. Tu, The effect of variable mesh size on the stability of multistep methods, SIAM J. Numer. Anal., 1 (1974), pp. 1025-1043. [73] G. GEIST, Reduction of a general matrix to tridiagonal form, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 362-373.
Copyright © 2002 Marcel Dekker, Inc.
288
BIBLIOGRAPHY
[74] A. P. GELFOND, Calcul des Difference
Finies, Dunod, Paris, 1963.
[75]
Hindusten Publishing Corp.,
, Calculus of finite Differences, Delhi, 1971.
[76] S. K. GODUNOV AND V. S. RYABENKI, Theory of Difference North-Holland, 1964.
Schemes,
[77] S. GOLDBERG, Introduction to Difference Equations, John Wiley, New York, 1958. [78] G. GOLUB AND C. VAN LOAN, Matrix Iterative Analysis, John Hopkins University Press, Baltimore, 1983. [79] S. P. GORDON. Stability and summability of solutions of equations, Math. Syst. Theory, 5 (1971), pp. 56-75.
difference
[80] T. K. S. H. S. MICKLEY AND C. E. REED, Applied Mathcrnaitcs in Chemical Engineering, McGraw-Hill, N. Y., 1967. [81] W. HAHN, Stability of Motion, Springer, Berlin, 1967. [82] F. A. HAIGHT, Mathematidal Theories of Traffic Press, New York, 1963.
Flow, Academic
[83] E. HAIRER. S. NORSETT, AND G. WANNER, Solving Ordinary Differential Equations, vol. I, Springer-Verlag, Berlin, 1993. [84] A. H ALAN AY, Quelque questions de la, thorie de la stabilit pour les systmes aux differences finies, Arch. Rat. Mech., 12 (1963), pp. 150154. [85]
, Solution periodiques et presque-periodiques des systems d'equationes aux difference finies, Arch. Rat. Mech., 12 (1963), pp. 134-149.
[86] A. HALANAY AND D. WEXLER, Teoria Calitative a Sisternlor cu Impulsun, Bucharest, 1968. [87] P. HARTMAN AND A. WINTNER, On the spectre of Toeplitz matrices, Am. J. of Math., 72 (1950), pp. 359-366. [88] P. HENRICI. Discrete Variable Methods for Ordinary Equations, John Wiley, New York, 1962.
Differential
[89]
, Error Propagation for Difference York, 1963.
[90]
, Applied and Computational Complex Analysis, vol. Vol. 1, John Wilcv. New York, 1974.
Copyright © 2002 Marcel Dekker, Inc.
Methods, John Wiley, New
BIBLIOGRAPHY
289
[91] M. HESTENES AND E. STIEFEL, Methods of conjugate gradients for solving linear systems, J. of Ris. of the Nat. Bur. of Standards, 49 (1952), pp. 409-436. [92] F. B. HILDEBRAND, Methods of Applied Mathematics, Prentice-Hall, 1952. [93] F. C. HOPPENSTEADT, Mathematical Methods a Population Biology, Courant Inst. of Math. Science, 1976. [94] F. C. HOPPENSTEADT AND J. M. HYMAN, Periodic solutions of a logistic difference equation, SIAM JAM, 32 (1977), pp. 73-81. [95] J. HURT, Some stability theorems for ordinary difference SIAM J. Numer. Anal., 4 (1967), pp. 582-596.
equations,
[96] D. JAGERMANN, Difference Equations with Applications to Queues, vol. 233 of Pure and Applied Mathematics, Marcel Dekker, New York, 2000. [97] C. JORDAN, Calculus of Finite Difference,
Chelsea, New York, 1950.
[98] R. KANNAN AND M. B. RAY, Monotone iterative methods for nonlinear equations involving a non-invertible linear part, Num. Math., 45 (1984), pp. 219-225. [99] W. G. KELLEY AND A. C. PETERSON, Difference Equations, an Introduction with Applications, Academic Press, San Diego, 2001. [100] I. KERNER, Ein gesamtschrittverfahren zur berechnung der nullstellen von polynomen, Numer. Math., 8 (1966), pp. 290-294. [101] M. KHAVANIN AND V. LAKSHMIKANTHAM, The method of mixed monotony and first order differential systems, Nonlinear Analysis, 10 (1986), pp. 873-877. [102] V. Kocic AND G. LADAS, Global behavior of nonlinear difference equations of higher order with applications, Mathematics and its Applications, Kluwer Academic Publishers, Dordrecht, 1993. [103] W. KRATZ, Banded matrices and difference Appl. To appear.
equations, Linear Algebra
[104] V. LAKSHMIKANTHAM AND S. LEELA, Differential and Integral Inequalities, vol. I, II, Academic Press, New York, 1969. [105] V. LAKSHMIKANTHAM AND D. TRIGIANTE, Theory of difference equations, Numerical Methods and Applications, vol. 181 of Mathematics in Science and Engeneering, Academic Press, New York, 1988.
Copyright © 2002 Marcel Dekker, Inc.
290
BIBLIOGRAPHY
[106] V. LAKSHMIKANTHAM AND A. S. VATSALA, Method of mixed monotony for non linear equations with a singular linear part, Appl. Math, and Computations, 23 (1987), pp. 235-241. [107] J. A. LAMBERT, Computational Methods in Ordinary Equations. John Wiley, 1973.
Differential
[108] J. P. LASALLE, The stability of dynamical systems, Regional Conference Series in Applied Mathematics, SIAM, 1979. [109] G. D. LENA AND D. TRIGIANTE, On the stability and convergence of lines method. Rend, di Mat., 3 (1982), pp. 113-126. [110]
, Stability and spectral properties of incomplete Japan J. Appl. Math., 7 (1990), pp. 145-153.
factorization,
[Ill] J. W. LEWIS, Inversion of tridiagonal matrices, Num. Math., 38 (1982), pp. 333-345. [112] T. Y. Li AND J. YORKE, Period three implies chaos, Amer. Math. Monthly, 82 (1975), pp. 985-992. [113] E. N. LORENZ, The problem of deducing the climate from, the governing equations, TELLUS, 16 (1964), pp. 1-11. [114] D. G. LuENBERGER, Introduction to Dynamic Systems, John Wiley, New York. 1979. [115] Y. L. LUKE, The Special Functions and Their vol. Vol. 1. Academic Press, 1969.
Approximations,
[116] A. MATE AND P. NEVAI, Sublinear perturbations of the differential equation y' = 0 and the analogous difference equation, J. Diff. Eq., 53 (1984), p. 234 257. [117]
, A generalization of Poincare theorem for recurrence equation, J. Approx. Theory, 63 (1990), pp. 92-97.
[118] R. MATTHEIJ AND M. SMOOKE, Estimates of the inverses of tridiagonal matrices arising in boundary value problems, Lin. Alg. Appl., 73 (1986), pp. 33-57. [119] R. M. MATTHEIJ, Accurate estimates for the fundamental solutions of discrete boundary value problems, J. Math. Anal, and Appl., 101 (1984). pp. 444-464. [120]
, Stability of block LU-decompositions of the 'matrices arising from BVP, SIAM J. Alg. Dis. Math., 5 (1984), pp. 314-331.
Copyright © 2002 Marcel Dekker, Inc.
BIBLIOGRAPHY
291
[121] R. M. MAY, Biological populations with nonoverlapping generations. Stable points, stable cycles and chaos, Science, 186 (1974). [122]
, Simple mathematical models with very complicated dynamics, Nature, 261 (1976), pp. 459-467.
[123] F. MAZZIA AND D. TRIGIANTE, Numerical methods for second order singular perturbation problems, Comp. Math. Appl., 23 (1992), pp. 8189. [124] G. J. MEIL, Majorizing sequences and error bounds for iterative methods, Math, of Computations, 34 (1960), pp. 185-202. [125]
, An updated version of the Kantorovich theorem for Newton's method, Computing, 27 (1981), pp. 237-244.
[126] W. MELVIN, Stability properties of functional differential J. Math. Anal. Appl., 48 (1974), pp. 749-763.
equations,
[127] J. J. H. MILLER, On the location of zeros of certain classes of polynomial with applications to numerical analisis, J. Inst. Math. Appl., 8 (1971), pp. 397-406. [128] K. S. MILLER, An Introduction to the Calculus of Finite Differences and Difference Equations, Hold and Company, New York, 1960. [129]
, Linear Difference
Equations, Benjamin, New York, 1968.
[130] L. M. MILNE-THOMSON, The Calculus a Finite Differences, McMillan and Co., London, 1933. [131] O. NEVANLINNA AND W. LINIGER, Contratctive methods for stiff differential equations, BIT, 19 (1979), pp. 53—72. [132] O. NEVANLINNA AND F. ODEH, Multiplier techniques for linear multistep methods, Num. Funct. Anal, and Optimiz., 3 (4) (1981), pp. 377423. [133] R. O' SHEA. The extention of Zubov method to sampled data control systems described by difference equations, IEEE, Trans Auto. Conf., 9 (1964), pp. 62-69. [134] F. ODEH AND W. LINIGER, Non linear fixed h stability of linear multistep formulas, J. Math. Anal. Appl., 61 (1977), pp. 691-712. [135] O. OLIVEIRA FILHO AND L. CARVALHO, On Periodic solutions of x(t) = ax(t — 1) + bx(t — 2), In Proc. of First Int. Conf. on Difference Eq. To,mpa, Gordon and Breach, 1994, pp. 79-94.
Copyright © 2002 Marcel Dekker, Inc.
292
BIBLIOGRAPHY
[136] F. W. OLVER, Numerical solutions of second order linear difference equations, Jour, of Research, NBS, 71B (1967), pp. 111-129. [137] J. M. ORTEGA, The Newton-Kantorovich theorem,, Amer. Math. Monthly, 75 (1968), pp. 658-660. [138]
, Stability of difference equations and convergence of iterative processes, SIAM J. Numer. Anal, 10 (1973), pp. 268-282.
[139] J. M. ORTEGA AND W. C. RHEINBOLDT, Monotone iterations for nonlinear equations with application to Gauss-Seidel methods, SIAM J. Numer. Anal, 4 (1967), pp. 171-190. [140]
, Iterative Solution of Nonlinear Equations in Several Variables. Academic Press. New York, 1970.
[141] A. OSTROWSKI, Les points detraction el de repulsion pour ^iteration dans resace a n dimension, C. R. Acad. Sciences. Paris, 244 (1957), pp. 288-289. [142]
. Solution of Equations and Systems of Equations, Academic Press, New York. 1960.
[143] B. G. PACHPATTE, Finite difference inequalities and an extension a Lyapunov method, Michigan Math. J., 18 (1971). pp. 385-391. [144]
, On some discrete inequalities of Bellman-Bihari type, Indian J. Pure and Applied Math., 6 (1975), pp. 1479-1487.
[145]
, On some fundamental inequalities and its applications in the theory of difference equations, Ganita, 27 (1976), pp. 1-11.
[146] P. PANG AND R. AGARWAL, On the periodicity of difference equations of a general type, J. of Diff. Eq. and AppL 2 (1996), pp. 271-287. [147] B. PARLETT, Reduction to tridiagonal form and minimal realizaiions, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 567-593. [148] L. PASQUINI AND D. TRIGIANTE, A globally convergent method for simultaneously finding polynomial roots, Math, of Computation, 44 (1985), pp. 135-150. [149] W. PATULA, Growth, oscillations and comparison theorems for second order difference equations, SIAM J. Math. An., 10 (1979), pp. 12721279. [150] G. PIAZZA AND D. TRIGIANTE, Propagazione degli errori nella integrazione numerica di equazioni differenziali ordinane, vol. 120, Pubbl. IAC III, Roma, 1977.
Copyright © 2002 Marcel Dekker, Inc.
BIBLIOGRAPHY
293
[151] J. H. POLLARD, Mathematical Methods for the Growth of Human Populations, Cambridge University Press. 1973. [152] J. POPENDA, Finite difference pp. 79-87. [153]
inequalities, Fasciculi Math., 13 (1981),
, On the boundness of the solutions of difference ciculi Math., 14 (1985), pp. 101-108.
equations, Fas-
[154] F. A. POTRA, Sharp error bounds for a class of Newton-like methods, Libertas Matematica, 5 (1985). pp. 71-84. [155] R. B. POTTS, Nonlinear difference 6 (1982), pp. 659-665.
equations, Nonlinear Anal. TMA,
[156] S. REDDY AND L. TREFETHEN, Stability of the method of lines, Nurrier. Math., 62 (1992), pp. 235-267. [157] J. RiORDAN, Combinatorial Identities, John Wiley, New York, 1968. [158] T. L. SAATY, Elements of Queuing Theory, with Applications, Dover, New York, 1961. [159] A. SAMARSKI AND E. NILOAIEV, Methodes de Resolution des Equation des Mailles, MIR, Moscow, 1981. [160] C. W. SCHELIN, Counting zeros of real polynomials within the unit disk, SIAM J. Numer. Anal., 5 (1983), pp. 1023-1031. [161] I. J. SCHOENBERG, Monosplines and Quadrature Formulae, In T.N.E. Grcville, Theory and Applications of Spines Functions, Academic Press, New York, 1969. [162]
, Mathematical Time Exposures, Math. Ass. of America, 1982.
[163] A. N. SHARKOVSKII, Coexistence of cycles of continuous map of line into itself, Ukrainian Math. J., 16 (1964), pp. 61-71. [164] S. SMALE, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc., 4 (1981), pp. 1-36. [165] P. STEPHAN, A theorem of Sharkovskii on the existence of periodic orbits of continuous endomorphisms of the real line, Comm. Math. Phys., 54 (1977), pp. 237-248. [166] G. W. STEWART. Afternotes goes to graduate school, SIAM, Philadelphia, 1998. [167] P. D. STRAFFIN, Periodic points of continuous functions, Math. Mag., 51 (1978), pp. 99-105.
Copyright © 2002 Marcel Dekker, Inc.
294
BIBLIOGRAPHY
[168] S. SUGIYAMA, Difference inequalities and their applications to stability problems, Lectures Notes in Math., Springer, 243 (1971), pp. 1-15. [169] Y. M. SVIREZHEV AND D. O. LOGOFET, Stability of Biological Community, MIR, Moscow, 1983. [170] J. SYLVESTER, On certain inequalities relating to prime numbers. Nature, XXXVIII (1888), pp. 259-262. [171] O. TOEPLITZ, Zur theorie der quadratischen und bilinearen formen von unendlichvielen veranderlichen. i. te.il: Theorie der l-formen., Mathematische Annalen, 70 (1911), pp. 351-376. [172] W. TRENCH, Asimptotic behavior of solutions of Poincare recurrence systems, Comp. Math. Appl, 28 (1994), pp. 317-314. [173] F. TRICOMI, Sugh algoritmi iterativi dell'analisi numerica, Accad. Naz. dei Lincei, (1975), pp. 105-117. [174] D. TRIGIANTE. On a system, of difference equations arising in the cyclic reduction., J. of Diff. Eq. and Appl., 3 (1998), pp. 369-384. [175] D. TRIGIANTE AND S. SIVASUNDARAM, A new algorithm for unstable three term recurrence relations, Appl. Math, and Comp, 22 (1987), pp. 277-289. [176] M. URABE, Nonlinear Autonomous Oscillations. Academic Press, New York, 1976. [177] R. A. USMANI, Applied Linear Algebra, Marcel Dekker, New York, 1988. [178]
, On the explicit inverse and conditioning of a tridiagonal matrix, Int. J. Comp. Math., 4 (1992), pp. 201-213.
[179] G. WARMER AND H. REITBERGER, On the perturbation formulas of Grobner and Alekseev. Bui. lust. Pol. lasi, XIX (1973), pp. 15-25. [180] J. WlMP, Computation with Recurrence Relations, Pitman, 1984. [181] M. YAMAGUTI AND H. MATANO, Euler's finite difference chaos, Proc. Japan Acad, 55A (1979), pp. 78-80.
scheme and
[182] M. YAMAGUTI AND S. USHIKI, Discretization and chaos, C.R. Acad. Sc. Paris, 290 (1980), pp. 637-640. [183]
, Chaos in numerical analysis of ordinary differential Physica, 3D (1981), pp. 618-626.
Copyright © 2002 Marcel Dekker, Inc.
equations.
BIBLIOGRAPHY
295
[184] T. YAMAMOTO, Error bound for Newton's iterated, derived, from the Kantorovich theorem, Num. Math., 48 (1986), pp. 91-98. [185] R. V. M. ZAHAR, Mathematical analysis of Miller's algorithm, Num. Math., 27 (1977), pp. 427-447.
Copyright © 2002 Marcel Dekker, Inc.