Сплайны: кусочно-полиномиальные функции и их применение.
Spline (mathematics)
Сплайны: математические функции, заданные полиномами. Применение в интерполяции, САПР и компьютерной графике для создания гладких кривых и аппроксимации.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Математическая функция, определяемая по частям полиномами, инструмент для черчения.
Mathematical function defined piecewise by polynomials
the drafting tool
В математике сплайн – это функция, определяемая по частям полиномами. При решении задач интерполяции сплайн-интерполяция часто предпочтительнее полиномиальной интерполяции, поскольку она дает сопоставимые результаты, даже при использовании полиномов низкой степени, избегая явления Рунге при высоких степенях. В областях компьютерных наук, таких как автоматизированное проектирование и компьютерная графика, термин "сплайн" чаще относится к кусочно-полиномиальной (параметрической) кривой. Сплайны популярны в этих областях благодаря простоте их построения, легкости и точности вычислений, а также способности аппроксимировать сложные формы посредством подгонки кривых и интерактивного проектирования. Термин "сплайн" происходит от гибких шаблонов, используемых судостроителями и чертежниками для рисования плавных линий.
In mathematics, a spline is a function defined piecewise by polynomials. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low degree polynomials, while avoiding Runge's phenomenon for higher degrees. In the computer science subfields of computer aided design and computer graphics, the term spline more frequently refers to a piecewise polynomial (parametric) curve. Splines are popular curves in these subfields because of the simplicity of their construction, their ease and accuracy of evaluation, and their capacity to approximate complex shapes through curve fitting and interactive curve design. The term spline comes from the flexible spline devices used by shipbuilders and draftsmen to draw smooth shapes.
Введение
Термин "spline" используется для обозначения широкого класса функций, применяемых в задачах интерполяции и/или сглаживания данных. Данные могут быть как одномерными, так и многомерными. Интерполяционные сплайны обычно определяются как минимизаторы подходящих показателей шероховатости (например, интегрального квадрата кривизны) при соблюдении условий интерполяции. Сглаживающие сплайны можно рассматривать как обобщение интерполяционных сплайнов, где функции определяются путем минимизации взвешенной комбинации средней квадратичной ошибки аппроксимации по наблюдаемым данным и показателя шероховатости. Для ряда значимых определений показателя шероховатости, сплайны оказываются конечномерными по своей природе, что является основной причиной их полезности в вычислениях и представлении. В остальной части этого раздела мы сосредоточимся исключительно на одномерных полиномиальных сплайнах и будем использовать термин "spline" в этом узком смысле.
The term "spline" is used to refer to a wide class of functions that are used in applications requiring data interpolation and/or smoothing. The data may be either one dimensional or multi dimensional. Spline functions for interpolation are normally determined as the minimizers of suitable measures of roughness (for example integral squared curvature) subject to the interpolation constraints. Smoothing splines may be viewed as generalizations of interpolation splines where the functions are determined to minimize a weighted combination of the average squared approximation error over observed data and the roughness measure. For a number of meaningful definitions of the roughness measure, the spline functions are found to be finite dimensional in nature, which is the primary reason for their utility in computations and representation. For the rest of this section, we focus entirely on one dimensional, polynomial splines and use the term "spline" in this restricted sense.
История
До появления компьютеров числовые вычисления производились вручную. Хотя использовались кусочно-определенные функции, такие как функция знака или функция ступенчатого роста, полиномы обычно предпочтительнее, поскольку с ними было легче работать. С появлением компьютеров сплайны приобрели важное значение. Они были впервые использованы в качестве замены полиномам при интерполяции, а затем как инструмент для построения гладких и гибких форм в компьютерной графике. Общепринято считать, что первое математическое упоминание о сплайнах содержится в статье Шенберга 1946 года, которая, вероятно, является первым местом, где слово "сплайн" используется в связи с гладким кусочно-полиномиальным приближением. Однако истоки этих идей лежат в авиационной и судостроительной промышленности. В предисловии к (Bartels et al., 1987) Робин Форрест описывает "лофтинг" – технику, использовавшуюся в британской авиационной промышленности во время Второй мировой войны для создания шаблонов для самолетов путем пропускания тонких деревянных планок (называемых "splines") через точки, размеченные на полу большого конструкторского цеха, технику, заимствованную из проектирования корпусов кораблей. На протяжении многих лет в судостроении практиковалось использование моделей для проектирования в малом масштабе. Успешный проект затем наносился на миллиметровую бумагу, а ключевые точки этого проекта переносились на миллиметровую бумагу большего формата в натуральную величину. Тонкие деревянные планки обеспечивали интерполяцию ключевых точек в плавные кривые. Эти планки фиксировались в дискретных точках (Форрест называл их "утками", Шенберг использовал "собаками" или "крысами"), а между этими точками принимали форму с минимальной энергией деформации. По словам Форреста, одним из возможных стимулов для создания математической модели этого процесса была потенциальная потеря критически важных компонентов конструкции целого самолета в случае попадания вражеской бомбы в конструкторский цех. Это привело к разработке "конического лофтинга", который использовал конические сечения для моделирования положения кривой между "утками". Конический лофтинг был заменен тем, что мы сейчас называем сплайнами, в начале 1960-х годов благодаря работам Дж. С. Фергюсона в Boeing и (несколько позже) М. А. Сабина в British Aircraft Corporation. Слово "spline" изначально было диалектным словом, используемым в Восточной Англии. Использование сплайнов для моделирования кузовов автомобилей, по-видимому, имеет несколько независимых истоков. Авторами работ считаются де Кастельжо в Citroën, Пьер Безье в Renault и Биркгофф, Гарабедян и де Бур в General Motors (см. Birkhoff and de Boor, 1965), все работы выполнялись в начале 1960-х или конце 1950-х годов. По крайней мере одна работа де Кастельжо была опубликована, но не получила широкой известности, в 1959 году. Работа де Бура в General Motors привела к публикации ряда статей в начале 1960-х годов, включая некоторые из основополагающих работ по B-сплайнам. Работа также велась в Pratt & Whitney Aircraft, где работали два автора (Ahlberg et al., 1967) – первой книги, посвященной сплайнам, – и Федор Тейльхаймер в David Taylor Model Basin. Подробное описание работы в General Motors можно найти в (Birkhoff, 1990) и (Young, 1997). Дэвис (1997) обобщает некоторые из этих материалов.
Before computers were used, numerical calculations were done by hand. Although piecewise defined functions like the sign function or step function were used, polynomials were generally preferred because they were easier to work with. Through the advent of computers, splines have gained importance. They were first used as a replacement for polynomials in interpolation, then as a tool to construct smooth and flexible shapes in computer graphics. It is commonly accepted that the first mathematical reference to splines is the 1946 paper by Schoenberg, which is probably the first place that the word "spline" is used in connection with smooth, piecewise polynomial approximation. However, the ideas have their roots in the aircraft and shipbuilding industries. In the foreword to (Bartels et al., 1987), Robin Forrest describes "lofting", a technique used in the British aircraft industry during World War II to construct templates for airplanes by passing thin wooden strips (called "splines") through points laid out on the floor of a large design loft, a technique borrowed from ship hull design. For years the practice of ship design had employed models to design in the small. The successful design was then plotted on graph paper and the key points of the plot were re plotted on larger graph paper to full size. The thin wooden strips provided an interpolation of the key points into smooth curves. The strips would be held in place at discrete points (called "ducks" by Forrest; Schoenberg used "dogs" or "rats") and between these points would assume shapes of minimum strain energy. According to Forrest, one possible impetus for a mathematical model for this process was the potential loss of the critical design components for an entire aircraft should the loft be hit by an enemy bomb. This gave rise to "conic lofting", which used conic sections to model the position of the curve between the ducks. Conic lofting was replaced by what we would call splines in the early 1960s based on work by J. C. Ferguson at Boeing and (somewhat later) by M. A. Sabin at British Aircraft Corporation. The word "spline" was originally an East Anglian dialect word. The use of splines for modeling automobile bodies seems to have several independent beginnings. Credit is claimed on behalf of de Casteljau at Citroën, Pierre Bézier at Renault, and Birkhoff, Garabedian, and de Boor at General Motors (see Birkhoff and de Boor, 1965), all for work occurring in the very early 1960s or late 1950s. At least one of de Casteljau's papers was published, but not widely, in 1959. De Boor's work at General Motors resulted in a number of papers being published in the early 1960s, including some of the fundamental work on B splines. Work was also being done at Pratt & Whitney Aircraft, where two of the authors of (Ahlberg et al., 1967) — the first book length treatment of splines — were employed, and the David Taylor Model Basin, by Feodor Theilheimer. The work at General Motors is detailed nicely in (Birkhoff, 1990) and (Young, 1997). Davis (1997) summarizes some of this material.