Content-Type: multipart/related; start=<op.mhtml.1318397626447.fb8c852a552c2f2d@172.16.0.2>; boundary=----------f1bZp9W8pUFZraiXrfmzZZ
Content-Location: http://alglib.sources.ru/interpolation/spline3.php
Subject: =?utf-8?Q?=D0=98=D0=BD=D1=82=D0=B5=D1=80=D0=BF=D0=BE=D0=BB=D1=8F=D1=86=D0=B8=D1=8F=20=D1=81=D0=BF=D0=BB=D0=B0=D0=B9=D0=BD=D0=B0=D0=BC=D0=B8=20-=20=D0=91=D0=B8=D0=B1=D0=BB=D0=B8=D0=BE=D1=82=D0=B5=D0=BA=D0=B0=20=D0=B0=D0=BB=D0=B3=D0=BE=D1=80=D0=B8=D1=82=D0=BC=D0=BE=D0=B2?=
MIME-Version: 1.0

------------f1bZp9W8pUFZraiXrfmzZZ
Content-Disposition: inline; filename=spline3.htm
Content-Type: text/html; name=spline3.htm
Content-ID: <op.mhtml.1318397626447.fb8c852a552c2f2d@172.16.0.2>
Content-Location: http://alglib.sources.ru/interpolation/spline3.php
Content-Transfer-Encoding: 8bit

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html>
<head>
<title>Интерполяция сплайнами - Библиотека алгоритмов</title>


<style type="text/css">
h2                      { font-family: Tahoma,sans-serif; font-size : 14pt; }
h3                      { font-family: Arial,sans-serif; font-size : 12pt;}
input                   { font-family: Courier New,monospace; font-size : 9pt; }
ul,ol                   { text-align:justify; }

a.topmenu               { font-family: Tahoma,sans-serif; font-weight:bold; font-size:9pt; text-decoration: none; color:#2020B0; margin:0px; padding: 0px;}
a.topmenu:hover         { text-decoration: underline; color:#2020FF;}
.ctopmenu               { font-family: Tahoma,sans-serif; font-weight:bold; font-size:11pt; text-decoration: none; color:#000000; margin:0px; padding: 0px;}

.manlink                { color:#000066; font-weight: bold; cursor: pointer; text-decoration: underline; }
a.nav                   { color:#000066; }
a.nav:visited           { color:#000066; }
a.download              { color:#000066; }
a.download:visited      { color:#000066; }
a.btnnav                { color:#000066; background-color: #F8F8FF; padding: 0.2em; text-decoration: none; }
a.btnnav:visited        { color:#000066; background-color: #F8F8FF; padding: 0.2em; text-decoration: none; }
div.navbar p            { font-family: Serif; font-size:10pt; margin-top:10px; margin-bottom:10px; }
div.navbar a            { color:#000066; }
div.navbar a:visited    { color:#000066; }

.pagecontent            { width: 900px; margin-left: auto; margin-right: auto; font-family: Arial; font-size: 10pt; text-align: justify; margin-top: 1em; margin-bottom: 1em; }
div.navbar table        { font-family: Arial; font-size: 10pt;  }

h2.graybar              { background-color:#E8E8E8; margin-top:10px; margin-bottom:10px; margin-left:0px; margin-right:0px; padding:6px; }
.comment                { width: 700px; margin-left: auto; margin-right: auto; font-family: Arial; font-size: 8pt; font-decoration: italic; text-align: justify; margin-top: 1em; margin-bottom: 1em; }

p.example               { padding: 4px; margin-left: 30px; margin-right: 30px; margin-top: 5px;; margin-bottom: 0; font-size: 80%; }
pre.example             { padding: 4px; margin-left: 30px; margin-right: 30px; margin-top: 0; margin-bottom: 5px; border-width: 2px 2px 2px 30px; border-style: solid; border-color: #F0F0F0; font-size: 95%; }


div.desc_h p            { margin-top: 3.0ex; margin-left:     0; margin-bottom: 0; padding: 0; }
div.desc_t p            { margin-top: 1.0ex; margin-left:  40px; margin-bottom: 0; }
div.desc_e p            { margin-top: 1.0ex; margin-bottom:   0; font-size: 85%; font-weight: bold; color: black; }
div.desc_e a            { color:#000066; text-decoration: none; }
div.desc_e a:visited    { color:#000066; text-decoration: none; }

div.dlpanel h3          { margin-top:0; margin-bottom:0; }
div.dlpanel p           { font-family: Serif; font-size:10pt; margin-left:18pt; margin-top:0pt; margin-bottom:0pt; margin-right:0pt; }
div.blspanel p          { font-family: Serif; font-size:10pt; margin:0pt; }


.attention              { color:#aa0000; font-weight:bold; }



a.ref                   { text-decoration: none; }
a.ref:hover             { text-decoration: underline; }

a.artlist               {color:#111177; text-decoration: none;}
a.artlist:visited       {color:#111177; text-decoration: none;}
a.artlist:hover         {color:#111177; text-decoration: underline;}

a.specialatt            {color:#aa0000; font-size : 10pt; font-weight:bold; }
a.specialatt:visited    {color:#aa0000; font-size : 10pt; font-weight:bold; }

.halfsmalltext { font-size : 11pt; }
.smalltext { font-size : 10pt; }
.compact { margin-top:0; margin-bottom:0; }
a.special {color:#FF0066; font-size : 20pt;}
a.special:visited {color:#FF0066; font-size : 20pt;}
</style>
<script type="text/javascript" src="/scripts.js"></script>
</head>

<body bgcolor=white text="#333333" link="#000099" vlink="#222255" alink="#552255" bottommargin=0 topmargin=0 marginwidth=0 marginheight=0 rightmargin=0 leftmargin=0>

<table cellpadding=0 cellspacing=0 border=0 width=100%>
<tr height=119><td background="/img/nettopback2.png"><img src="/img/site-logo-v3-oss.png" width=720 height=119 border=0 alt=""></td></tr>
<tr height=1><td bgcolor=#0056A0></td></tr>
<tr><td bgcolor=#F5F5F5><div style='margin-top: 0.5em; margin-bottom: 0.5em; margin-left: 3em; margin-right: 3em;'><a class=topmenu href='/'>Главная</a>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=topmenu href='http://www.alglib.net/download.php'>Скачать</a>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=topmenu href='http://www.alglib.net/commercial.php'>Коммерческая поддержка</a>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=topmenu href='http://www.alglib.net/faq.php'>FAQ</a>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=topmenu href='http://forum.alglib.net/'>Forum</a>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=topmenu href='http://www.alglib.net/aboutus.php'>О нас</a>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=topmenu href='http://www.alglib.net/'>Английская версия</a></div></td></tr>
<tr><td bgcolor=#0056A0 height=1></td></tr>
</table>

<div class="pagecontent">
<div class=navbar>
<p>
<a href="/#book">ALGLIB User Guide</a> - <a href="/interpolation/">Интерполяция, аппроксимация и численное дифференцирование</a> - Интерполяция сплайнами
</p></div>
<h2 class=graybar>Интерполяция сплайнами</h2>

<p align=justify>
Интерполяция сплайнами третьего порядка - это быстрый, эффективный и устойчивый способ интерполяции функций.
Наравне с <a href="rational.php">рациональной интерполяцией</a>,
сплайн-интерполяция является одной из альтернатив <a href="polynomial.php">полиномиальной интерполяции</a>.
</p>

<p align=justify>
В основе сплайн-интерполяции лежит следующий принцип.
Интервал интерполяции разбивается на небольшие отрезки, на каждом из которых функция задается полиномом третьей степени.
Коэффициенты полинома подбираются таким образом, чтобы выполнялись определенные условия (какие именно, зависит от способа интерполяции).
Общие для всех типов сплайнов третьего порядка требования - непрерывность функции и, разумеется, прохождение через предписанные ей точки.
Дополнительными требованиями могут быть линейность функции между узлами, непрерывность высших производных и т.д.
</p>

<p align=justify>
Основными достоинствами сплайн-интерполяции являются её устойчивость и малая трудоемкость.
Системы линейных уравнений, которые требуется решать для построения сплайнов, очень хорошо обусловлены, что позволяет получать коэффициенты полиномов с высокой точностью.
В результате даже про очень больших <i style='font-family: Verdana;'>N</i> вычислительная схема не теряет устойчивость.
Построение таблицы коэффициентов сплайна требует <i style='font-family: Verdana;'>O(N)</i> операций, а вычисление значения сплайна в заданной точке - всего лишь <i style='font-family: Verdana;'>O(log(N))</i>.
</p>







<table class=pagecontent border=0 cellspacing=0 cellpadding=10 style='border-style: solid; border-width: 1px; border-color: silver; background-color: #F8F8F8;'><tr><td>
<h3 style='margin-bottom: 0;'>Содержание</h3>
<p align=left style='margin-top: 0.2em; margin-bottom: 0em;'>
&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header0'>1 Типы сплайнов</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header1'>Линейный сплайн</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header2'>Сплайн Эрмита</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header3'>Сплайн Катмулла-Рома</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header4'>Кубический сплайн</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header5'>Сплайн Акимы</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header6'>2 Сплайны в ALGLIB</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header7'>Основные операции</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header8'>Дифференцирование на сетке, переход от сетки к сетке</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header9'>Примеры</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header10'>3 Аппроксимация кубическими сплайнами</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header11'>4 Численные результаты</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header12'>Интерполяция различными видами сплайнов</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header13'>5 Manual entries</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;<a class=nav href='#header14'>6 Ссылки по теме</a><br>
</p></td></tr></table>




<a name='header0'></a><h3 style='border-style: solid; border-width: 0px 0px 1px 0px; border-color: #A0A0A0; margin-top: 2em;'><i>Типы сплайнов</i></h3>





<a name='header1'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Линейный сплайн</i></h3>

<p align=justify>
Линейный сплайн - это сплайн, составленный из полиномов первой степени, т.е. из отрезков прямых линий.
Точность интерполяции линейными сплайнами невысока, также следует отметить, что они не обеспечивают непрерывности даже первых производных.
Однако в некоторых случаях кусочно-линейная аппроксимация функции может оказаться предпочтительнее, чем аппроксимация более высокого порядка.
Например, линейный сплайн сохраняет монотонность переданного в него набора точек.
</p>








<a name='header2'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Сплайн Эрмита</i></h3>

<p align=justify>
Сплайн Эрмита - это сплайн третьего порядка, производная которого принимает в узлах сплайна заданные значения.
В каждом узле сплайна Эрмита задано не только значение функции, но и значение её первой производной.
Сплайн Эрмита имеет непрерывную первую производную, но вторая производная у него разрывна.
Точность интерполяции значительно лучше, чем у линейного сплайна. 
</p>








<a name='header3'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Сплайн Катмулла-Рома</i></h3>

<p align=justify>
Сплайн Катмулла-Рома - это сплайн Эрмита, производные которого определяются по формуле:
</p>
<p><img src="i/catmullrom.gif" width=126 height=48 align=absmiddle hspace=5></p>
<p align=justify>
Как и сплайн Эрмита, сплайн Катмулла-Рома имеет непрерывную первую производную и разрывную вторую.
Сплайн Катмулла-Рома локален - значения сплайна зависят только от значений функции в четырех соседних точках (двух слева, двух справа). Можно использовать два типа граничных условий:
</p>
<ul><li>Сплайн, завершающийся параболой. В этом случае граничный отрезок сплайна представляется полиномом второй степени вместо третьей (для внутренних отрезков по-прежнему используются полиномы третьей степени). В ряде случаев это обеспечивает большую точность, чем естественные граничные условия.</li>
<li>Периодические граничные условие (этот вид граничных условий используется при моделировании периодических функций).</li>
</ul>








<a name='header4'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Кубический сплайн</i></h3>

<p align=justify>
Все сплайны, рассмотренные на этой странице, являются кубическими сплайнами - в том смысле, что они являются кусочно-кубическими функциями.
Однако, когда говорят "кубический сплайн", то обычно имеют в виду конкретный вид кубического сплайна, который получается,
если потребовать непрерывности первой и второй производных.
Кубический сплайн задается значениями функции в узлах и значениями производных на границе отрезка интерполяции (либо первых, либо вторых производных).
</p>
<ul><li>Если известно точное значение первой производной на обеих границах, то такой сплайн называют фундаментальным. Погрешность интерполяции таким сплайном равна <i style='font-family: Verdana;'>O(h<sup><small>&nbsp;4</small></sup>)</i>.</li>
<li>Если значение первой (или второй) производной на границе неизвестно, то можно задать т.н. естественные граничные условия <i style='font-family: Verdana;'>S''(A)=0</i>, <i style='font-family: Verdana;'>S''(B)=0</i>, и получить естественный сплайн. Погрешность интерполяции естественным сплайном составляет <i style='font-family: Verdana;'>O(h<sup><small>&nbsp;2</small></sup>)</i>. Максимум погрешности наблюдается в окрестностях граничных узлов, во внутренних узлах точность интерполяции значительно выше.</li>
<li>Ещё одним видом граничного условия, которое можно использовать, если неизвестны граничные производные функции, является условие типа "сплайн, завершающийся параболой". В этом случае граничный отрезок сплайна представляется полиномом второй степени вместо третьей (для внутренних отрезков по-прежнему используются полиномы третьей степени). В ряде случаев это обеспечивает большую точность, чем естественные граничные условия.</li>
<li>Можно указать периодические граничные условие (этот вид граничных условий используется при моделировании периодических функций).</li>
</ul>
<p align=justify>
Наконец, можно сочетать различные типы граничных условий на разных границах (кроме периодических условий, которые должны быть указаны сразу на двух границах).
Обычно так имеет смысл делать, если у нас есть только часть информации о поведении функции на границе
(например, производная на левой границе - и никакой информации о производной на правой границе).
</p>








<a name='header5'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Сплайн Акимы</i></h3>
 
<p align=justify>
Сплайн Акимы - это особый вид сплайна, устойчивый к выбросам.
Недостатком кубических сплайнов является то, что они склонны осциллировать в окрестностях точки, существенно отличающейся от своих соседей.
На графике приведен набор точек, содержащий один выброс. Зеленым цветом обозначен кубический сплайн с естественными граничными условиями.
На отрезках интерполяции, граничащих с выбросом, сплайн заметно отклоняется от интерполируемой функции - сказывается влияние выброса.
Красным цветом обозначен сплайн Акимы. Можно видеть, что, в отличие от кубического сплайна,
сплайн Акимы в меньшей мере подвержен влиянию выбросов - на отрезках, граничащих с выбросом, практически отсутствуют признаки осцилляции.
</p>
<p align=justify>
Важным свойством сплайна Акимы является его локальность - значения функции на отрезке <i style='font-family: Verdana;'>[x<sub><small>i&nbsp;</small></sub>, x<sub><small>i+1&nbsp;</small></sub>]</i> зависят только от
<i style='font-family: Verdana;'>f<sub><small>i-2&nbsp;</small></sub></i>, <i style='font-family: Verdana;'>f<sub><small>i-1&nbsp;</small></sub></i>, <i style='font-family: Verdana;'>f<sub><small>i&nbsp;</small></sub></i>, <i style='font-family: Verdana;'>f<sub><small>i+1&nbsp;</small></sub></i>, <i style='font-family: Verdana;'>f<sub><small>i+2&nbsp;</small></sub></i>, <i style='font-family: Verdana;'>f<sub><small>i+3&nbsp;</small></sub></i>.
Вторым свойством, которое следует принимать во внимание, является нелинейность интерполяции сплайнами Акимы -
результат интерполяции суммы двух функций не равен сумме интерполяционных схем, построенных на основе отдельных функций.
Для построения сплайна Акимы требуется не менее 5 точек. Во внутренней области (т.е. между <i style='font-family: Verdana;'>x<sub><small>2&nbsp;</small></sub></i> и <i style='font-family: Verdana;'>x<sub><small>N-3&nbsp;</small></sub></i> при нумерации точек от 0 до N-1)
погрешность интерполяции имеет порядок <i style='font-family: Verdana;'>O(h<sup><small>&nbsp;2</small></sup>)</i>.
</p>
<p><img src="i/akimaspline.gif" width=323 height=220 align=absmiddle hspace=5></p>








<a name='header6'></a><h3 style='border-style: solid; border-width: 0px 0px 1px 0px; border-color: #A0A0A0; margin-top: 2em;'><i>Сплайны в ALGLIB</i></h3>

<a name='header7'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Основные операции</i></h3>

<p align=justify>
Работа с кубическими сплайнами в ALGLIB осуществляется в два этапа:
</p>
<ul><li>
Построение сплайна при помощи одной из подпрограмм (выбор конкретной подпрограммы зависит от типа сплайна и решаемой задачи - интерполяции или аппроксимации).
Результатом работы является структура <span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?struct_spline1dinterpolant",350,250); return false;'>spline1dinterpolant</span>, хранящая построенную модель. 
</li>
<li>
Работа с полученным сплайном (интерполяция, копирование/сериализация модели и т.д.). 
</li></ul>
<p align=justify>
Для построения сплайна можно использовать следующие подпрограммы: 
</p>
<ul><li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dbuildlinear",350,250); return false;'>spline1dbuildlinear</span> для построения линейного сплайна 
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dbuildcubic",350,250); return false;'>spline1dbuildcubic</span> для построения кубического сплайна 
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dbuildhermite",350,250); return false;'>spline1dbuildhermite</span> для построения сплайна Эрмита 
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dbuildakima",350,250); return false;'>spline1dbuildakima</span> для построения сплайна Акимы 
</li></ul>
<p align=justify>
После того, как сплайн построен, вы можете использовать следующие подпрограммы:
</p>
<ul><li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dcalc",350,250); return false;'>spline1dcalc</span> - для вычисления значения сплайна в заданной точке
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1ddiff",350,250); return false;'>spline1ddiff</span> - для вычисления значения сплайна и его производных в заданной точке
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dintegrate",350,250); return false;'>spline1dintegrate</span> - для интегрирования сплайна
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dlintransx",350,250); return false;'>spline1dlintransx</span> - для линейной замены аргумента <i style='font-family: Verdana;'>x=a&middot;t+b</i>
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dlintransy",350,250); return false;'>spline1dlintransy</span> - для линейного преобразования сплайна <i style='font-family: Verdana;'>S<sub><small>2&nbsp;</small></sub>(x)=a&middot;S(x)+b</i>
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dunpack",350,250); return false;'>spline1dunpack</span> - для получения доступа к таблице коэффициентов
</li></ul>
<a name='header8'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Дифференцирование на сетке, переход от сетки к сетке</i></h3>

<p align=justify>
Одной из часто встречающихся задач является использование кубических сплайнов для перехода от одной сетки к другой.
Мы имеем сетку <i style='font-family: Verdana;'>x</i>, значения <i style='font-family: Verdana;'>y</i> (на сетке <i style='font-family: Verdana;'>x</i>), а также новую сетку <i style='font-family: Verdana;'>x<sub><small>2&nbsp;</small></sub></i>.
Нам надо получить значения кубического сплайна, построенного на основе старой сетки, в узлах новой сетки <i style='font-family: Verdana;'>x<sub><small>2&nbsp;</small></sub></i>.
Дополнительно могут требоваться значения производных.
</p>
<p align=justify>
Разумеется, можно просто построить кубический сплайн при помощи функциии <span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dbuildcubic",350,250); return false;'>spline1dbuildcubic</span>,
после чего использовать функцию <span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1ddiff",350,250); return false;'>spline1ddiff</span>, вызвав её для каждого из узлов новой сетки (см. пример ниже).
Приведенный ниже код имеет трудоемкость <i style='font-family: Verdana;'>O(n<sub><small>2&nbsp;</small></sub>&middot;log(n<sub><small>1&nbsp;</small></sub>))</i>. 
</p>
<p class=example>C++ example</p><pre class=example>

... <i>initialization of x, y, x2</i> ...

alglib::spline1dbuildcubic(x, y, spline);
for(i=0; i&lt;n2; i++)
    y2[i] = alglib::spline1dcalc(spline, x2[i]);
    
... <i>now y2 contains new values</i> ...

</pre>
<p align=justify>
Однако есть более удобное и быстрое решение - использовать специальные функции для операций на сетках:
</p>
<ul><li><span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dconvcubic",350,250); return false;'>spline1dconvcubic</span>, которая вычисляет значения кубического сплайна на новой сетке</li>
<li><span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dconvdiffcubic",350,250); return false;'>spline1dconvdiffcubic</span>, которая вычисляет значения кубического сплайна и его первой производной на новой сетке</li>
<li><span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dconvdiff2cubic",350,250); return false;'>spline1dconvdiff2cubic</span>, которая вычисляет значения кубического сплайна, а также первой и второй производных на новой сетке</li>
<li><span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dgriddiffcubic",350,250); return false;'>spline1dgriddiffcubic</span>, которая дифференцирует сплайн на старой сетке</li>
<li><span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?sub_spline1dgriddiff2cubic",350,250); return false;'>spline1dgriddiff2cubic</span>, которая дифференцирует сплайн на старой сетке, вычисляя первые и вторые производные</li>
</ul>
<p align=justify>
Результат работы этих функций эквивалентен результату, полученному при помощи приведенного выше кода, но принцип работы другой - 
используется специализированное представление кубического сплайна, оптимизированное для единственной операции - перехода от одной сетки к другой.
Это позволяет значительно повысить быстродействие на предварительно отсортированных сетках - до <i style='font-family: Verdana;'>O(max(n<sub><small>2&nbsp;</small></sub>,n<sub><small>1&nbsp;</small></sub>))</i>.
</p>
<p style="text-align: justify; margin-left: 100px;  margin-right: 60px; font-size: 85%; ">
<b>Замечание #1</b><br>

В случае, если сетки не отсортированы, трудоемкость увеличивается до <i style='font-family: Verdana;'>O(n<sub><small>2&nbsp;</small></sub>&middot;log(n<sub><small>2&nbsp;</small></sub>)+n<sub><small>1&nbsp;</small></sub>&middot;log(n<sub><small>1&nbsp;</small></sub>))</i> в связи с проведением предварительной сортировки.
Однако и это часто оказывается быстрее, чем первый вариант.

</p>
<p align=justify>
С использованием этих функций мы можем написать более компактный код:
</p>
<p class=example>C++ example</p><pre class=example>

... <i>initialization of x, y, x2</i> ...

alglib::spline1dconvcubic(x, y, x2, y2);
    
... <i>now y2 contains new values</i> ...

</pre>
<a name='header9'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Примеры</i></h3>

<p align=justify>
ALGLIB Reference Manual содержит следующие примеры использования кубических сплайнов:
</p>
<ul><li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?example_spline1d_d_linear",350,250); return false;'>spline1d_d_linear</span> - демонстрирует использование линейного сплайна
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?example_spline1d_d_cubic",350,250); return false;'>spline1d_d_cubic</span> - демонстрирует использование кубического сплайна с различными типами граничных условий
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?example_spline1d_d_griddiff",350,250); return false;'>spline1d_d_griddiff</span> - демонстрирует дифференцирование сплайна на сетке
</li>
<li>
<span class=manlink onclick='popup_window_near_event("/include/scripts/man_entry.php?example_spline1d_d_convdiff",350,250); return false;'>spline1d_d_convdiff</span> - демонстрирует переход от одной сетки к другой
</li></ul>












<a name='header10'></a><h3 style='border-style: solid; border-width: 0px 0px 1px 0px; border-color: #A0A0A0; margin-top: 2em;'><i>Аппроксимация кубическими сплайнами</i></h3>

<p align=justify>
Пакет ALGLIB также может использоваться для аппроксимации сплайнами.
Более подробно этот вопрос рассмотрен в <a href="leastsquares.php#splinefit">главе ALGLIB User Guide</a>, посвященной аппроксимации.
</p>









<a name='header11'></a><h3 style='border-style: solid; border-width: 0px 0px 1px 0px; border-color: #A0A0A0; margin-top: 2em;'><i>Численные результаты</i></h3>
 




<p align=justify>
В этой секции мы продемонстрируем результаты применения численных сплайнов к различным задачам.
Условия задач подобраны таким образом, чтобы продемонстрировать поведение сплайнов в наиболее типичных условиях.
Мы рассматриваем следующие задачи:
</p>
<ul><li>интерполяцию гладкой функции с демонстрацией точности, достигаемой за счет применения различных типов сплайнов.</li>
</ul>







<a name='header12'></a><h3 style='font-size: 100%; margin-top: 2.0em;'><i>Интерполяция различными видами сплайнов</i></h3>
 




<p align=justify>
Рассмотрим следующую проблему: интерполяцию функции <i style='font-family: Verdana;'>f(x)=sin(x)</i> на интервале <i style='font-family: Verdana;'>[-&pi;/2,+&pi;/2]</i>. Мы используем равномерную сетку с <i style='font-family: Verdana;'>N</i> узлами и четыре различных типа сплайнов:
</p>
<ul><li>сплайн Катмулла-Рома</li>
<li>кубический сплайн с естественными граничными условиями</li>
<li>кубический сплайн, завершающийся параболой</li>
<li>кубический сплайн с точными граничными условиями (известно точное значение производной в граничных точках)</li>
</ul>
<p align=justify>
Исследуем зависимость погрешности от числа узлов, варьируя <i style='font-family: Verdana;'>N</i> в диапазоне 10...100. В результате мы получим следующий график:
</p>



<p><img src="i/spline_sinx.gif" width=517 height=320 align=absmiddle hspace=5></p>


<p align=justify>
Мы можем видеть, что в данном случае лучшим выбором является кубический сплайн с точными граничными условиями.
Если значение производной в узловых точках неизвестно, то лучшим вариантом будет сплайн, завершающийся параболой.
Два прочих варианта - сплайн Катмулла-Рома и кубический сплайн с естественными граничными условиями - дают значительно большую ошибку.
</p>
<p align=justify>
Этот вывод верен и для большинства других задач. Если вы знаете производную на границе, лучше использовать её. Если нет - используйте сплайн, завершающийся параболой.
</p>
<p style="text-align: justify; margin-left: 100px;  margin-right: 60px; font-size: 85%; ">
<b>Замечание #2</b><br>

На графике не показан результат, полученный с помощью сплайна Эрмита.
Обычно он очень близок по качеству к кубическому сплайну с точными граничными условиями, но требует больше информации.
В частности, в рассмотренном выше случае графики для этих двух сплайнов полностью совпали бы.

</p>



<a name='header14'></a><h3 style='border-style: solid; border-width: 0px 0px 1px 0px; border-color: #A0A0A0; margin-top: 2em;'><i>Ссылки по теме</i></h3>
<ol><li><a href="http://en.wikipedia.org/wiki/Spline_interpolation">'Spline_interpolation', Wikipedia</a></li>
</ol><a name='manual'></a><a name='header13'></a><h3 style='border-style: solid; border-width: 0px 0px 1px 0px; border-color: #A0A0A0; margin-top: 2em;'><i>Manual entries</i></h3>

<table cellspacing=3 cellpadding=0 class=pagecontent>
<tr><td bgcolor=E8E8E8><B>C++</B></td><td width=10>&nbsp;</td><td><a class=nav href='/translator/man/manual.cpp.html#unit_spline1d'><code>spline1d</code> subpackage</a>&nbsp;&nbsp;&nbsp;</td></tr>
<tr><td bgcolor=E8E8E8><B>C#</B></td><td width=10>&nbsp;</td><td><a class=nav href='/translator/man/manual.csharp.html#unit_spline1d'><code>spline1d</code> subpackage</a>&nbsp;&nbsp;&nbsp;</td></tr>
</table><p align=left style='font-size: 9pt;'><i>This article is intended for <a href='/#guide_license'>personal use only</a>.</i></p><h2 class=graybar>Скачать ALGLIB</h2>
<div class=dlpanel>

<h3>C#</h3>
<p>Исходный код на C#</p>
<p><a class=download href="/download.php">Downloads page</a></p>
<p>&nbsp;</p><h3>C++</h3>
<p>Исходный код на C++</p>
<p><a class=download href="/download.php">Downloads page</a></p>
<p>&nbsp;</p><h3>C++, арифметика высокой точности</h3>
<p>Исходный код на C++, использующий библиотеки MPFR/GMP.</p>
<p>Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.</p>

<p><a class=download href="/download.php">Downloads page</a></p>
<p>&nbsp;</p><h3>FreePascal</h3>
<p>
Исходный код на Free Pascal.<br>

</p>
<p><a class=download href="/download.php">Downloads page</a></p>
<p>&nbsp;</p><h3>Delphi</h3>
<p>
Исходный код на Delphi.<br>

</p>
<p><a class=download href="/download.php">Downloads page</a></p>
<p>&nbsp;</p><h3>VB.NET</h3><p>Исходный код на VB.NET.</p>
<p><a class=download href="/download.php">Downloads page</a></p>
<p>&nbsp;</p><h3>VBA</h3><p>Исходный код на VBA.</p>
<p><a class=download href="/download.php">Downloads page</a></p>
<p>&nbsp;</p><h3>Python</h3><p>Исходный код на Python (CPython и IronPython).</p>
<p><a class=download href="/download.php">Downloads page</a></p>
<p>&nbsp;</p></div>
</div>

<table cellpadding=0 cellspacing=0 border=0 width=100%'>
<tr>
<td bgcolor=#0056A0 height=1>
</td>
</tr>
<tr>
<td bgcolor=#E2E2E2 height=30>
&nbsp;
</td>
</tr>
<tr>
<td bgcolor=#0056A0 height=1>
</td>
</tr>
<tr>
<td nowrap align=right>
<p style='margin: 2em; font-size: 80%;'>
ALGLIB&reg; - numerical analysis library, 1999-2011.<br>
ALGLIB is <a href="/trademark.php">registered trademark</a> of the ALGLIB Project.
</p>
</td>
</tr>
</table>

</body>
</html>


------------f1bZp9W8pUFZraiXrfmzZZ
Content-Disposition: inline; filename=scripts.js
Content-Type: application/x-javascript; name=scripts.js
Content-Location: http://alglib.sources.ru/scripts.js
Content-Transfer-Encoding: Base64

ZnVuY3Rpb24gcG9wdXBfd2luZG93X25lYXJfZXZlbnQodXJsLHcsaCkNCnsNCiAg
ICAvLyBwb3B1cHMgd2luZG93IG5lYXIgbGFzdCBldmVudCAob3IgYXQgdGhlIGNl
bnRlciwgaWYgT3BlcmEgaXMgdXNlZCkNCiAgICB2YXIgbmV3d2luZG93Ow0KICAg
IGlmKCAodHlwZW9mIGV2ZW50ICE9ICJ1bmRlZmluZWQiKSAmJiAobmF2aWdhdG9y
LnVzZXJBZ2VudC5pbmRleE9mKCJPcGVyYSIpPT0tMSkgKQ0KICAgIHsNCiAgICAg
ICAgd2xlZnQgPSBldmVudC5zY3JlZW5YLTUwOw0KICAgICAgICB3dG9wID0gZXZl
bnQuc2NyZWVuWS01MDsNCiAgICB9DQogICAgZWxzZQ0KICAgIHsNCiAgICAgICAg
d2xlZnQgPSBNYXRoLnJvdW5kKDAuMypzY3JlZW4ud2lkdGgpOw0KICAgICAgICB3
dG9wID0gTWF0aC5yb3VuZCgwLjMqc2NyZWVuLmhlaWdodCk7DQogICAgfQ0KICAg
IHBvcyA9ICd3aWR0aD0nICsgdyArICcsaGVpZ2h0PScgKyBoICsgJyxsZWZ0PScg
KyB3bGVmdCArICcsdG9wPScgKyB3dG9wOw0KICAgIG5ld3dpbmRvdyA9IHdpbmRv
dy5vcGVuKHVybCwgJycsIHBvcysnLHJlc2l6YWJsZT0xLHNjcm9sbGJhcnM9MCx0
b29sYmFyPTAsbWVudWJhcj0wLGxvY2F0aW9uPTAsc3RhdHVzPTAnKTsNCiAgICBp
Ziggd2luZG93LmZvY3VzICkNCiAgICAgICAgbmV3d2luZG93LmZvY3VzKCk7DQog
ICAgcmV0dXJuIGZhbHNlOw0KfQ0K

------------f1bZp9W8pUFZraiXrfmzZZ
Content-Disposition: inline; filename=nettopback2.png
Content-Type: image/png; name=nettopback2.png
Content-Location: http://alglib.sources.ru/img/nettopback2.png
Content-Transfer-Encoding: Base64

iVBORw0KGgoAAAANSUhEUgAAAAoAAACWCAIAAABo9I7SAAAABGdBTUEAALGOfPtR
kwAAACBjSFJNAAB6JQAAgIMAAPn/AACA6QAAdTAAAOpgAAA6mAAAF2+SX8VGAAAA
CXBIWXMAAAsSAAALEgHS3X78AAAAGHRFWHRTb2Z0d2FyZQBQYWludC5ORVQgdjMu
Mzap5+IlAAAAVklEQVRYR+2WMQ4AIAwC8ZP+zx/2B9XRgbC4mSPd2C5AOqpKQccO
ErYjABabi0csmitdRwnbEQCLzQVYwHIRIA7EgTg0NaAG1IAa+FeadWAdWId/12ED
LSsvNRzGRXMAAAAASUVORK5CYII=

------------f1bZp9W8pUFZraiXrfmzZZ
Content-Disposition: inline; filename=site-logo-v3-oss.png
Content-Type: image/png; name=site-logo-v3-oss.png
Content-Location: http://alglib.sources.ru/img/site-logo-v3-oss.png
Content-Transfer-Encoding: Base64

[encoded data, 20736 characters]
rkJggg==

------------f1bZp9W8pUFZraiXrfmzZZ
Content-Disposition: inline; filename=catmullrom.gif
Content-Type: image/gif; name=catmullrom.gif
Content-Location: http://alglib.sources.ru/interpolation/i/catmullrom.gif
Content-Transfer-Encoding: Base64

R0lGODlhfgAwAPcAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAACH5BAEAAP8ALAAAAAB+ADAAAAj/AP8JHEiwoMGDCBMqXMiw
ocOHECNKnEixosWLGDNq3Mixo8ePIEOKHEmypMmTKFOqXMmypcuXMCcCADBw5keb
AnHGvEkzJ0idPXfe9ClxplGjB3sGFepRqUinTIcGXVqTakSaS63+0xn1IdeEWr2G
NTi2K8KsWWtapPpVbUOkW+MWLEuQrleydd3KTHr2bVWscyHaVQgY79ajcgUnDnwU
6sK0iwcHpth2cWLJdcOOHQwZsuKOXJVWpqwV7mPCZG2OxmwW4+azZa02Nt16bV++
qGuH9JwXN1iZs4MLH068uPHbRCcz1ss8Z3DdRYH6dhsb+tDDr6s6P6zc+kq7bL27
aqTLW/z3383NMx2tvr379wyRsl+rmjV87k/t37cs+Lnh/Z89BaBi+hE4oF+XJVWg
XOVtdx9O8/H3lmjxHZhZbxKShpyFkaVn23QWiiYfR1ghluGDyi0IIoYhdhahWAqq
yOGMNNZo440aBQQAOw==

------------f1bZp9W8pUFZraiXrfmzZZ
Content-Disposition: inline; filename=akimaspline.gif
Content-Type: image/gif; name=akimaspline.gif
Content-Location: http://alglib.sources.ru/interpolation/i/akimaspline.gif
Content-Transfer-Encoding: Base64

[encoded data, 4928 characters]
bNmWbvmWcBmXFhEQADs=

------------f1bZp9W8pUFZraiXrfmzZZ
Content-Disposition: inline; filename=spline_sinx.gif
Content-Type: image/gif; name=spline_sinx.gif
Content-Location: http://alglib.sources.ru/interpolation/i/spline_sinx.gif
Content-Transfer-Encoding: Base64

[encoded data, 16448 characters]
zTXbfDPOMAcEADs=

------------f1bZp9W8pUFZraiXrfmzZZ--
