Browse Prior Art Database

BOUNDS ON THE SOLUTIONS OF DIFFERENCE EQUATIONS AND SPLINE INTERPOLATION AT KNOTS

IP.com Disclosure Number: IPCOM000148727D
Original Publication Date: 1976-Aug-11
Included in the Prior Art Database: 2007-Mar-30
Document File: 40 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Friedland, Shmuel: AUTHOR [+3]

Abstract

RC 6142 (#26471) 8/11/76 Mathematics 40 pages BOTTNDS ON THE SOLUTIONS OF DIFFERENCE EQUATIONS AND SPLINE INTERPOLATION AT KNOTS

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 40

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.

[This page contains 1 picture or other non-text object]

Page 2 of 40

Introduction
Given a strictly increasing sequence

we define

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

such that
(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
i

A t i

a geometric mesh,

-

*ti-l

    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

n-1

S (A) = (S:SeC (I), S] E IT ~ E Z

= ~0,41,f2,.. . I 3,

= constant, in [43 .

[This page contains 1 picture or other non-text object]

Page 3 of 40

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

00

Section 1. Spline interpolation

    We begin by reviewing some facts .needed in the analysis of (0.1). TO this end, we define

                                              i n-1
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.

1

[This page contains 1 picture or other non-text object]

Page 4 of 40

These polynomials have the following properties: for i = O,l, ...,

n-I.,

Hence any S E S (A) which satisfies (0.1) m y be expressed. on [tiIti+l]l
as

n

~t.=t~+~-t..
since...