BOUNDS ON THE SOLUTIONS OF DIFFERENCE EQUATIONS AND SPLINE INTERPOLATION AT KNOTS
Original Publication Date: 1976-Aug-11
Included in the Prior Art Database: 2007-Mar-30
Software Patent Institute
Friedland, Shmuel: AUTHOR [+3]
RC 6142 (#26471) 8/11/76 Mathematics 40 pages BOTTNDS ON THE SOLUTIONS OF DIFFERENCE EQUATIONS AND SPLINE INTERPOLATION AT KNOTS
RC 6142 (#26471) 8/11/76
Mathematics 40 pages
BOTTNDS ON THE SOLUTIONS OF DIFFERENCE EQUATIONS AND SPLINE
INTERPOLATION AT KNOTS
Shuel Miedland Institute of f at he ma tics Hebrew TJniversity Jerusalem, Israel
Charles A. Micchelli
IBM Thomas J. Watson ~esearch
Center Yorktown Heights, New York 10598
Typed by Manuscript Center
ABSTRACT: We prove several comparison theorems for difference equations and discuss their application to spline interpola- tion at knots.
Given a strictly increasing sequence
n (tilti+l) n '
where n = polynomials of degree <n-1. Sn(A) is the class of spline n
functions of degree n with knots on
Problem: Find conditions on A which imply that for any bounded sequence ... Y - ~ , yo, yl, ... there exists a unique bounded S E S.(b) n
(0.1) Ski) = yi1 id.
When a mesh A has this property, we w i l l say that problem (0.1) is solvable.
For n=l, problem (0.1) is solvable for any mesh. When n=2 the probltm is also elementary. W e w i l l not go into the simple details of its analys,,. For 1123, the problem becomes difficult. The case n=3 was recently investl-
gated by de Boor [I]. For arbitrary n and equally spaced partitions, A t i = ti+l -t = constant, the problem is studied in Schoenberg 171 and %r
A t i
a geometric mesh,
In this paper we w i l l study the general problem and assume fmm now
on that n 3 . Our hope was to prove a conjecture made in C41, howevex, aur
S (A) = (S:SeC (I), S] E IT ~ E Z
= ~0,41,f2,.. . I 3,
= constant, in [43 .
efforts were unsuccessful in this regard. A statement of this conjecture and our main results on problem (0.1) are discussed in Section 1.
The approach we use to study this interpolation problem replaces (0.1) n-1
by an [equivalent) first order difference equation on R with variable coefficients. This fact is our departure from (0.1) to the question of estimating the growth of solutions of a homogeneous difference equation
where each Ai is an nxn oscillation matrix and bounds on Ai are given. This information on (0.2) enables us to "solve" the inhomogeneous equation
Section 1. Spline interpolation
We begin by reviewing some facts .needed in the analysis of (0.1). TO this end, we define
in R by which we mean: given any bounded sequence (b :icZ in R (0.3) has a unique bounded solution. When this is the case we w i l l say (0.3) is solvable. Section 2 and Section 3 of the paper give various conditions
on A. which guarantee that (0.3) is solvable.
These polynomials have the following properties: for i = O,l, ...,
Hence any S E S (A) which satisfies (0.1) m y be expressed. on [tiIti+l]l