Метод кубических сплайнов

Походження терміна " сплайни" пов'язане з гнучкою креслярської лінійкою, якою користувалися для малювання гладких кривих, що проходять через задані точки.
Інтерполяція сплайнами - це швидкий, ефективний і стійкий спосіб інтерполяції функцій. Нарівні з раціональної інтерполяцією, сплайн-інтерполяція є однією з альтернатив поліноміальної інтерполяції [28].
В основі сплайн-інтерполяції лежить наступний принцип. Інтервал інтерполяції розбивається на невеликі відрізки, на кожному з яких функція задається поліномом третього ступеня. Коефіцієнти полінома підбираються таким чином, щоб виконувалися певні умови (які саме, залежить від способу інтерполяції). Загальні для всіх типів сплайнів третього порядку вимоги - безперервність функції і, зрозуміло, проходження через запропоновані їй точки. Додатковими вимогами можуть бути лінійність функції між вузлами, безперервність вищих похідних і т.д.
Основними достоїнствами сплайн-інтерполяції є її стійкість і мала трудомісткість. Системи лінійних рівнянь, які потрібно вирішувати для побудови сплайнів, дуже добре обумовлені, що дозволяє отримувати коефіцієнти поліномів з високою точністю. У результаті навіть про дуже великих N обчислювальна схема не втрачає стійкість. Побудова таблиці коефіцієнтів сплайна вимагає O (N) операцій, а обчислення значення сплайна в заданій точці - всього лише

Зазвичай для сплайна вибирають кубічний поліном

,

визначений на інтервалі з .

При цьому вся крива являє собою набір таких кубічних поліномів (рис 1.4), з певним чином підібраними коефіцієнтами - параметр сплайна [20, 38].

Малюнок 1.4 Схема методів сплайнов

Коефіцієнти на кожному інтервалі визначаються з умов сполучення у вузлах:

.

Крім того, на кордоні при і ставляться умови

. (1.12)

Будемо шукати кубічний поліном у вигляді

.

З умови маємо

(1.13)

Обчислимо похідні:

.

вимагатимемо їх безперервності при: :

. (1.14)

Загальне число невідомих коефіцієнтів, очевидно, так само, число рівнянь (1.13) і (1.14) дорівнює . Відсутні два рівняння отримуємо з умови (1.12) при

і :

.

Вираз з (1.14) , підставляючи цей вираз в (1.13) і виключаючи , отримаємо:

.

Підставивши тепер вирази для + в першу формулу (1.14), після нескладних перетворень одержуємо для визначення різницеве рівняння другого порядку:
. (1.15)

. (1.15)

З крайовими умовами:

(1.16)

Умова еквівалентно умові і рівняння. . Різницеве рівняння (1.15) з умовами (1.16) можна вирішити методом прогонки, представивши у вигляді системи лінійних алгебраїчних рівнянь виду , де вектор відповідає вектору , вектор F поелементно дорівнює правій частині рівняння (1.15), а матриця A має наступний вигляд:

,

де і

Метод прогонки, заснований на припущенні, що шукані невідомі пов'язані рекурентним співвідношенням:

.

Використовуючи це співвідношення, висловимо і через і підставимо в ie рівняння:

,

де - права частина i-го рівняння. Це співвідношення буде виконуватися незалежно від рішення, якщо вимагати:

;

.

Звідси випливає:

;

.

З першого рівняння отримаємо:

;

.

Після знаходження прогоночних коефіцієнтів і використовуючи рівняння (1), отримаємо рішення системи. При цьому,

.

Сплайнова інтерполяція хороша тим, що вимагає знання у вузлах тільки значень функції, але не її похідних [34, 36, 43].

5.3 Аналіз програмних аналогів

Програмний продукт спеціалізується для користування в підприємстві горно збагачувального комплексу. Користувачами програмного продукту будуть студенти денної та заочної форми навчання, а також викладачі. В зв’язку з тим, що з кожним роком істотне підвищення тарифів на послуги залізничного транспорту на одну тонну продукції, що робить перевезення не вигідним, то інформаційна система оптимізації планування процесів перевезення має важливе значення для соціально-економічного розвитку придніпровського регіону України.

Основна мета продукту – визначити прогнозный план перевезення вугілля, як для самого холдингу, так і для споживачів, а також надати данi про можливий прибуток наступного перiоду.

Як приклад аналогів мною було розглянуто:

Многочлен Лагранжа
Для вирішення запропонованого завдання зафіксуємо одну ординату , а решта будемо вважати рівними нулю (рис.1.1), тобто заданим значенням абсцис ставляться у відповідність значення ординат

Малюнок 1.1 Фіксація однієї ординати
З властивостей многочленів випливає, що многочлен, який звертається в нуль в різних точках, тобто що має різних коренів, повинен ділитися на кожну з різниць:

а отже, і на добуток цих різниць, тобто його ступінь не може бути нижче . У такому випадку многочлен повинен мати вигляд (1.1)

З умови визначимо значення const

,

таким чином знаходимо

В отриманому виразі ніякого особливого переваги не має, можна приписати цю особливу роль любому , тобто якщо абсцис поставити у відповідність значення , вказані в будь-який з наступних рядків:

,

то вираз для многочлена, що приймає при відповідних значеннях абсцис чисельні значення, виписані в одній з рядків, буде аналогічно розглянутому, тобто

(1.2)

Загальне рішення є суперпозицією (сумою) приватних рішень (1.2)

(1.3)

Це і є інтерполяційний многочлен Лагранжа. За розділами вихідних пар формула (1.3) дозволяє досить просто скласти «зовнішній вигляд» многочлена.
використовуючи позначення

, (1.4)

формулою Лагранжа можна надати більш стислий вигляд. продифференцируем

по

.

При маємо:

. (1.5)

Формула Лагранжа з урахуванням (1.4) і (1.5) прийме вигляд:

або (1.6)
Для залишкового члена многочлена Лагранжа справедливо вираз
, Якщо, , если , де ξ - внутрішня точка відрізка, який містить в собі точку і вузли . Звідси знаходимо [9, 11, 18, 25]:

, .

Метод найменших квадратів
Основним недоліком інтерполяційних многочленів є наявність у них великої кількості екстремумів і точок перегинів, що визначається підсумовуванням в них многочленів , n раз змінюють свій знак. Крім того, вихідні табличні значення функції задані неточно з різних причин, тому будувати многочлени вище 4-5-го ступеня, знаючи, що з теоретичних досліджень функція в інтервалі таблиці зовсім не така, не має особливого сенсу.
Якщо табличні значення функції можна інтерпретувати як теоретичне значення плюс похибка, то, задавши певний критерій близькості теоретичної кривої до заданого безлічі табличних точок, можна знайти потрібне число параметрів цієї кривої.
Найбільш популярним критерієм близькості є мінімум середнього квадрата відхилення:

де – точка експериментальних даних з таблиці,

- Значення шуканої залежності в точці .

Якщо шукану залежність бажано представити многочленом ступеня , то коефіцієнт в ньому представлятимуть невідомі параметри. Підставивши в суму квадратів відхилень шуканий многочлен, отримаємо функціонал, що залежить від цих параметрів:

Щоб функціонал був мінімальний, необхідно всі приватні похідні функціоналу за параметрами прирівняти нулю і систему дозволити щодо невідомих параметрів

. Ці дії призводять до наступної системи лінійних рівнянь

Тут – постійний коефіцієнт, що дорівнює сумі, равный сумме - тих ступенів усіх значень аргументів. Для їх ручного обчислення зручно до вихідної таблиці даних додати ще стовпців. – числові значення в правій частині системи лінійних алгебраїчних рівнянь, для підрахунку яких теж зручно до вихідної таблиці даних додати ще стовпців. Демонстрацію методу найменших квадратів проведемо для даних з кількістю точок в таблиці, рівним 4. Максимальна ступінь аппроксимирующего многочлена для такого набору дорівнює 3, так як має виконуватися співвідношення: . Для максимального ступеня аппроксимирующий і інтерполяційний многочлени рівні.
Нехай таблиця даних після додавання в неї додаткових колонок виглядає наступним чином:

У нижньому рядку розміщуємо підсумкові суми по кожній колонці.
Система рівнянь для полінома третього ступеня:

Вирішивши систему, знайдемо:

Ця ж таблиця без додавання чого-небудь дозволяє знайти коефіцієнти аппроксимирующего многочлена другого ступеня. Для цього достатньо в системі для полінома третього ступеня прибрати 4-е рівняння, а з решти рівнянь виключити доданки з невідомою . В результаті система рівнянь для полінома другого ступеня буде:

Вирішивши систему, знайдемо:

Аналогічно можна зменшувати число рівнянь для побудови апроксимуючих багаточленів першого і нульовий ступенів [13, 30, 32 33, 44].

Інтерполяціонная формула Ньютона

Використовуючи розділені різниці, інтерполяційний многочлен Лагранжа перетворимо до наступного вигляду

(1.7)

Його залишковий член

При інтерполяції функції в точці за допомогою формули Ньютона (1.7) обчислення доцільно проводити, дотримуючись алгоритму

(1.8)

Друга властивість розділених різниць можна використовувати для виявлення помилок в таблицях розділених різниць, які складені для многочленів або функцій, близьких до них. [6, 39]

Формула Ньютона для інтерполяції вперед

У інтерполяційної формулою (1.7) зробимо заміну змінної . Тоді вона прийме вигляд

(1.9)

Для залишкового члена цієї інтерполяційної формули можна використовувати уявлення [1, 17]:

.

Вказівка. Інтерполяціонная формула (1.9) застосовується для апроксимації функції в точці , близької до . (мал. 1.2)

Малюнок 1.2 Умови застосовності формули Ньютона для інтерполяції вперед

Формула Ньютона для інтерполяції назад

Якщо функцію потрібно апроксимувати в точці , близької до (мал. 1.3),

Малюнок 1.3 Умови застосовності формули Ньютона для інтерполяції назад

то використовують формулу Ньютона для інтерполяції назад:

(1.10)

Остаточний член в цьому випадку представимо у вигляді [1, 27]:

.

6. БІБЛІОГРАФІЧНИЙ СПИСОК

1. Амоносов А.А. Вычислительные методы для инженеров. / А.А.Амоносов. – М.: Высшая школа, 1994. – 436 c.

2. Акулич И.Л. Математическое программирование в примерах и задачах. / Акулич И.Л. – М.: Высшая школа, 1986. – 319 с.

3. Бахвалов Н.С., Численные методы / Бахвалов Н.С., Жидков Н.П., Кобельков Г.М.; [3-е изд.], доп. и перераб. – М.: БИНОМ. Лаборатория знаний, 2004. – 663 с.

4. Бахвалов Н.С. Численные методы в задачах и упражнениях. / БахваловН.С., Лапин А.В., Чижонков Е.В. – Учеб. пособие. – М.: Высшая школа, 2000. – 190с.

5. Березин И.С. Методы вычислений. Т.1. / Березин И.С., Жидков Н.П.– М.: Наука, 1966. – 324c.

6. Березин И.С. Методы вычислений. Т.2. / Березин И.С., Жидков Н.П.– М.: Наука, 1967. – 305c.

7. Вайк А. JavaScript в примерах. Пер. с англ. / Ален Вайк. – К.: Издательство «ДиаСофт», 2000. – 304с.

8. Вержбицкий В.М. Основы численных методов: Учебник для вузов. / Вержбицкий В.М – М.: Высшая школа, 2002. – 840с.

9. Вержбицкий В. М. Численные методы. Математический анализ и обыкновенные дифференциальные уравнения. / Вержбицкий В. М. – М.: Высш.шк., 2001. 383с.

10. Воеводин В.В. Численные методы алгебры. Теория и алгорифмы. – М.: Наука, 1966. – 248с.