ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


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

Визначення інтерполяції

Розглянемо систему незбіжних точок з деякої області D . Нехай значення функції відомі тільки в цих точках:

,

Завдання інтерполяції полягає у пошуку такої функції F із заданого класу функцій, що:

,

  • точки називають вузлами інтерполяції, а їх сукупність - інтерполяційної сіткою.
  • пари називають точками даних або базовими точками.
  • різниця між "сусідніми" значеннями - кроком інтерполяційної сітки. Він може бути як змінним так і постійним.
  • функцію F(x) - функцією що інтерполює або інтерполянтом.

 

Способи інтерполяції

На практиці найчастіше застосовують інтерполяцію многочленами. Це пов'язано насамперед з тим, що многочлени легко обчислювати, легко аналітично знаходити їх похідні і безліч многочленів щільні в просторі неперервних функцій ( теорема Вейєрштрасса).

 

Види інтерполяції:

§ Лінійна інтерполяція

§ Метод скінченних різниць

§ Интерполяционная формула Ньютона

§ Поліном Лагранжа (інтерполяційний поліном)

§ Сплайн-функція

· В-сплайн

§ Задача оберненого інтерполювання

Лінійна інтерполяція

Лінійна інтерполяція — це інтерполяція функції f алгебраїчним двочленом P1(x) = kx + c у точках x0 та x1, які належать відрізку [a, b].

 

Геометрична інтерпретація

З геометричної точки зору це означає заміну функції прямою,яка проходить через точки та .

Рівняння такої прямої має вигляд:

звідси для маємо:

Це і є формула лінійної інтерполяції, при чому

де — похибка формули, яка обчислюється за формулою:

Для неї є справедливою наступна оцінка:


 

Рис.1. Лінійна інтерполяція функції (сині прямі)

 

Крім лінійної інтерполяції існують також поняття: білінійної та бікубічної інтерполяцій.

Білінійна інтерполяція - в обчислювальній математиці розширення лінійної інтерполяції для функцій двох змінних. Ключова ідея полягає в тому, щоб провести звичайну лінійну інтерполяцію спочатку в одному напрямку, а потім в іншому.

Бікубічна інтерполяція– це розширення кубічної інтерполяції на випадок функції двох змінних, значення якої задані на двовимірній регулярній сітці. Поверхня, отримана в результаті бікубічної інтерполяції є гладкою функцією, на відміну від поверхонь, отриманих в результаті білінійної інтерполяції чи інтерполяціі методом найближчого сусіда. Дана інтерполяція теж часто використовується в обробці зображень, даючи більш якісне зображення в порівнянні з білінійною інтерполяцією. У випадку використання бікубічної інтерполяції значення функції в шуканої точці обчислюється через її значення в 16-ти сусідніх точках.

Метод скінченних різниць

Методи скінченних різниць, методи сіток — чисельні методи розв'язку інтегро-диференціальних рівнянь алгебри, диференціального, інтегрального числення, основані на заміні диференціальних операторів різницевими операторами,інтегралів — сумами, а функцій неперервного аргументу — функціями дискретного аргументу. Така заміна приводить до системи, взагалі кажучи, нелінійних алгебраїчних рівнянь, які зрештою зводяться до лінійної системи деяким ітераційним методом. Якщо початкова задача має вигляд

,

де — циліндрова область інтеграції — межа області , — її основа, — шукана вектор-функція і — задані вектор-функції, — просторовий векторний аргумент, і — оператори (не обов'язково обмежені), то найпростіша схема інтеграції початкового рівняння має вигляд:

,

Тут — сіткова функція, що є розв'язком різницевого рівняння, — різницеві оператори, залежні від параметрів , сітки, , — сіткова область, що апроксимує деяким чином область , — її границя і — сіткові функції, що апроксимують функції і відповідно. Окремим випадком схеми (2) є схема з вагами, коли , — ваговий коефіцієнт.

Схема (2) називається двошаровою, оскільки вона зв'язує між собою значення і різницевого розв'язку на двох тимчасових шарах ; можливі також і багатошарові схеми. Якщо оператор , де — одиничний оператор, оборотний, то схема (2) може бути представлена у вигляді, що розв'язується де оператор називаєстья оператором кроку різницевої схеми і враховує крайові умови, а — функція, залежна від і . Кажуть, що оператор , залежний від параметра , апроксимує (приблизно) оператор , якщо при . Тут — деяке еталонне сімейство функцій, на якому перевіряється апроксимація (напр., сімейство достатньо гладких функцій).

Схема (2) називаєтсья коректною, або стійкою, якщо , де означає норму оператора в деякому банаховому просторі. (див. простір абстрактний у функциональному аналізі), яке може залежати від .

Схема (2) апроксимує рівняння (1), якщо і . Для лінійних систем рівнянь встановлені теореми збіжності, що стверджують, що збіжність різницевого рішення до розв'язку початкового рівняння виходить з апроксимації і коректності (стійкості) різницевої схеми.

Якщо властивості апроксимації, стійкості і збіжності мають місце лише при деякому співвідношенні між параметрами сітки , , де , то їх називаютьумовними. Якщо ж ці властивості справедливі при будь-якому співвідношенні між і , то їх називають абсолютними.

Схема (2) називається явною, якщо , і неявною, якщо .

Схеми, що абсолютно збіжні, існують лише в класі неявних схем. Як правило, при відповідному виборі параметрів схеми (наприклад вагових коефіцієнтів) неявні схеми є абсолютно стійкими, вони допускають скільки завгодно великий крок . Але перетворення оператора ускладнює алгоритм. У разі одновимірних задач неявні схеми реалізують методом факторизації; вони є достатньо економічними. Для багатовимірних задач неявні економічні схеми одержують за допомогою дробових кроків методу, який зводить багатовимірні задачі до послідовності одномірних або простіших задач.

Для розв'язання стаціонарних задач застосовують метод стаціонування (встановлення), в якому стаціонарний розв'язок розглядається як межа нестаціонарного розв'язку із стаціонарним (або що встановлюються) краєвими умовами. Відповідно до цього стаціонарну задачу вирішують ітераційним методом, аналогічним різницевому методу інтеграції (2). На відміну від нестаціонарного випадку, оператор для ітераційного процесу повинен бути сильно стійкий, тобто повинен задовольняти умові , . При розв'язку нелінійних задач, особливо в механіці суцільного середовища, застосовують комбінації схем інтеграції з ітераційними методами (т.з. ітерації по нелінійності).

 

Рис.2. Методи скінченних різниць базуються на дискретизації функції на сітці

 

Визначення

Лагранж запропонував спосіб обчислення таких многочленів:

де базисні поліноми визначаються за формулою:

Очевидно, що мають такі властивості:

§ Це поліноми степеня

§

§ при

Звідси випливає, що , як лінійна комбінація , може мати степінь не більший від , та .

Застосування

Поліноми Лагранжа використовуються для інтерполяції, а також для чисельного інтегрування.

Нехай для функції відомі значення у деяких точках. Тоді ця функція може інтерполюватися як

Зокрема,

Значення інтегралів від не залежать від , тож їх можна обчислювати заздалегідь, знаючи послідовність .

Сплайн-функція

Сплайн (англ. spline — планка, рейка) — функція, область визначення якої розбита на куски, на кожному з кусків функція є деяким поліномом (многочленом).

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

Максимальний степінь поліномів в сплайні називається степенем сплайна. Різниця між степенем сплайна і його гладкістю називається дефектом сплайна.

Означення та історія

Сплайн (spiline) називали гнучку металеву лінійку — універсальне лекало, що використовували креслярі для того, щоб гладко з'єднати окремі точки на кресленні. Тобто для графічного виконання інтерполяції. Більше того, крива, що описує деформацію гнучкої лінійки зафіксованої в окремих точках є сплайном. Отже, ми маємо фізичну модель сплайн-функції (або навпаки сплайн-функція є математичною моделлю гнучкої лінійки). Інтуїтивний підхід до використання кусочних функцій в задачах апроксимації зустрічався в математиці протягом тривалого часу. Але, як зазначає Корнейчук Н. П., вторгнення сплайнів в теорію наближення відбулося через задачі інтерполяції, завдяки їхнім хорошим обчислювальним та апроксимативним властивостям.

Початок розвитку теорії інтерполяції сплайнами та й сам термін сплайн відраховують з 1946 року зі статті Ізо Шонберга (Isaac Jacob Schoenberg). Особливо інтенсивний її розвиток відбувся в 50-70 роки, традиційною прикладною сферою використання інтерполяційних сплайнів стали в цей час системи автоматизованого проектування. Однак потенційні можливості сплайнів значно ширші ніж просто опис деяких кривих. В реальному світі велика кількість фізичних процесів за самою своєю природою є сплайнами. В механіці це деформація гнучкої пластини чи стержня, зафіксованих в окремих точках; траєкторія руху тіла, якщо сила, що діє на нього змінюється ступінчато (траєкторія штучного космічного об'єкта з активними та інерційними відрізками руху, траєкторія руху літака при ступінчатій зміні тяги двигунів та зміні профілю крила і т. д.). В термодинаміці це теплообмін в стержні складеному з фрагментів з різною теплопередачою. В хімії — дифузія через шари різних речовин. В електриці — поширення електромагнітних полів через різнорідні середовища. Тобто сплайн не надумана математична абстракція, а в багатьох випадках він є розв'язанням диференційних рівнянь, які описують цілком реальні фізичні процеси.

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

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

Для визначення інтерполяційного сплайна з неперервною першою похідною достатньо розрахувати значення першої похідної у вузлах. Спосіб визначення похідних у вузлах сплайна визначає широку різноманітність інтерполяційних сплайнів. Часто похідні визначаються не як константи, а як деякі залежності від інтерпольованої функції та сітки інтерполяції.

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

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

Найпростішою умовою побудови фрагмента локального сплайна є умова рівності полінома на кінцях відрізків відповідним значенням інтерпольованої функції.

Для найпростішого сплайна — ламаної цієї умови цілком досить. Два коефіцієнта прямої однозначно визначаються з двох рівнянь. Такий сплайн є локальним. Для поліномів вищих степенів ми повинні додати додаткові умови таким чином, щоб загальне число рівнянь дорівнювало числу коефіцієнтів полінома. Так для сплайна 3-й степені такою умовою є рівність 1-ї похідної на кінцях відрізка деякому значенню, що визначається для сусідніх відрізків однаковим чином (у формулах (2) через значення похідної функції яку наближують).

Система з 4-х рівнянь

дозволяє однозначно визначити 4 коефіцієнти полінома. Для полінома 5-ї степені ми повинні додатково накласти умову рівності 2-ї похідної на кінцях відрізка і т. д. Наведене вище показує, чому сплайн будують переважно з поліномів непарних степенів (з парною кількістю коефіцієнтів).

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

Існують локальні методи побудови сплайнів Бесселя та Акіми, B — сплайни [] . В основному коли йде мова про сплайни то мають на увазі сплайни побудовані з алгебраїчних поліномів. Саме таких до них відноситься приведене вище визначення. Саме ці сплайни є найбільше вивченими. Проте сплайн може складатися з фрагментів функцій будь-якого класу. В [] розглянуто побудову таких сплайнів, та досліджуються їхні властивості. Автор не дає загального визначення побудованих сплайнів. Очевидно, що для довільних класів функцій з яких складається сплайн наведене на початку статті визначення не зовсім годиться. Якщо, наприклад, сплайн складається з відрізків експоненти то поняття дефекту сплайна втрачає зміст. Хоча кількість неперервних похідних залишиться важливою характеристикою. Побудова сплайна, фрагментами якого є розривні функції (раціональні функції, функції Паде) дещо виходить за рамки сплайнової ідеї, оскільки однією з основних переваг сплайнів є їхня гладкість. Якщо довільно розширювати такі конструкції, то стираються відмінності сплайнів від кускових функцій. Іншою перевагою сплайнів є ефективність обчислень. Надмірне ускладнення фрагментів суттєво знижує переваги сплайнів перед класичними функціями.

Для сплайнів є характерними такі ознаки: сплайн складається з фрагментів — функцій одного класу, які різняться лише своїми параметрами; на сусідні фрагменти в точках стикування накладаються певні умови, що зводяться до неперервності значень та деяких перших похідних. Сплайни — напрямок прикладної математики, що інтенсивно розвивається.

Форма представлення. Функції, що задають фрагменти сплайна, як правило, залежать від множини параметрів, завдяки яким вони змінюють свою форму. Значення параметрів на кожному із фрагментів індивідуальні. Ці параметри можуть задавати конкретний сплайн. Для поліноміальних сплайнів це поліноміальні коефіцієнти. Отже, сплайн можна представити множиною параметрів функцій на кожному з фрагментів. Назвемо це представлення пофрагментним. Таке представлення є наглядним, часто має явний фізичний зміст. Але число параметрів є надмірним. Так, для кубічного сплайна необхідно мати 4*(r-1) параметри (r — число вузлів сплайна). Значно компактнішим є представлення сплайна у вигляді полінома, через базисні сплайн-функції у вигляді:

,

де — базисні сплайн-функції (як правило локальні), — числові коефіцієнти, що задають вагу базисних функцій при формуванні сплайна. Число параметрів, що задають сплайн рівне числу вузлів сплайна. Між параметрами функції на фрагменті та коефіцієнтами полінома-сплайна існує залежність, що дозволяє за одними коефіцієнтами знаходити інші, хоча формули можуть мати досить складний вигляд.

B-сплайн

B-сплайн (базисний сплайн) — сплайн-функція, що має мінімальний носій для заданого степеня, гладкості та області визначення.

Фундаментальна теорема стверджує, що довільна сплайн-функція заданого степеня, гладкості і області визначення може бути представлена як лінійна комбінація B-сплайнів того ж степеня і гладкості на тій же області визначення.

Термін B-сплайн запровадив Ісак Яков Шонберг в 1947 році.

Визначення

B-сплайн степеня n з заданими вузлами:

та (m−n) контрольними точками

Це параметрична крива задана на що складена з базисних B-сплайнів степеня n

Базисні B-сплайни визначаються рекурсивними формулами:

при

При одинаковій відстані між сусідніми вузлами B-сплайни називаються однорідними, в протилежному випадку — неоднорідними.

 

Однорідні B-сплайни

Для однорідних B-сплайнів, базисні B-сплайни одинакового степеня є зміщеними екземплярами однієї функції. Нерекурсивним визначенням базисних B-сплайнів є

де

Приклади

Константні B-сплайни

Це найпростіші сплайни. Вони не є навіть неперервними.

Лінійні B-spline

Лінійні B-сплайни є неперервними, але не диференційовними.

Однорідні кубічні B-сплайни

Кубічний сплайн

Деяка функція f(x) задана на відрізку ,що розбитий на частини

Кубічним сплайном дефекту 1 називається функція , яка:

· на кожному відрізку є многочленом степеня не вище третього;

· має неперервну першу та другу похідні на всьому відрізку ;

· в точках виконується рівність , тобто. сплайн інтерполює функцію f в точках .

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

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

Теорема: Для будь-якої функції і будь-якого розбиття відрізка існує лише один сплайн S(x), ,що задовольняє перечисленим вище умовам.

Ця теорема є наслідком більш загальної теореми Шойнберга-Уітні про умови існування інтерполяційного сплайна.

Побудова

Позначимо:

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

тоді

Умови неперервності всіх похідних до 2-го порядку включно записуютьсятак:




а умови інтерполяції в виді

Звідси отримуємо формули для обчислення коефіцієнтів сплайна:

,

Якщо врахувати, що , то обрахунок можна провести завдяки методу прогонки для трьохдіагональної матриці.

Визначення інтерполяції

Розглянемо систему незбіжних точок з деякої області D . Нехай значення функції відомі тільки в цих точках:

,

Завдання інтерполяції полягає у пошуку такої функції F із заданого класу функцій, що:

,

  • точки називають вузлами інтерполяції, а їх сукупність - інтерполяційної сіткою.
  • пари називають точками даних або базовими точками.
  • різниця між "сусідніми" значеннями - кроком інтерполяційної сітки. Він може бути як змінним так і постійним.
  • функцію F(x) - функцією що інтерполює або інтерполянтом.

 

Способи інтерполяції

На практиці найчастіше застосовують інтерполяцію многочленами. Це пов'язано насамперед з тим, що многочлени легко обчислювати, легко аналітично знаходити їх похідні і безліч многочленів щільні в просторі неперервних функцій ( теорема Вейєрштрасса).

 

Види інтерполяції:

§ Лінійна інтерполяція

§ Метод скінченних різниць

§ Интерполяционная формула Ньютона

§ Поліном Лагранжа (інтерполяційний поліном)

§ Сплайн-функція

· В-сплайн

§ Задача оберненого інтерполювання

Лінійна інтерполяція

Лінійна інтерполяція — це інтерполяція функції f алгебраїчним двочленом P1(x) = kx + c у точках x0 та x1, які належать відрізку [a, b].

 

Геометрична інтерпретація

З геометричної точки зору це означає заміну функції прямою,яка проходить через точки та .

Рівняння такої прямої має вигляд:

звідси для маємо:

Це і є формула лінійної інтерполяції, при чому

де — похибка формули, яка обчислюється за формулою:

Для неї є справедливою наступна оцінка:


 

Рис.1. Лінійна інтерполяція функції (сині прямі)

 

Крім лінійної інтерполяції існують також поняття: білінійної та бікубічної інтерполяцій.

Білінійна інтерполяція - в обчислювальній математиці розширення лінійної інтерполяції для функцій двох змінних. Ключова ідея полягає в тому, щоб провести звичайну лінійну інтерполяцію спочатку в одному напрямку, а потім в іншому.

Бікубічна інтерполяція– це розширення кубічної інтерполяції на випадок функції двох змінних, значення якої задані на двовимірній регулярній сітці. Поверхня, отримана в результаті бікубічної інтерполяції є гладкою функцією, на відміну від поверхонь, отриманих в результаті білінійної інтерполяції чи інтерполяціі методом найближчого сусіда. Дана інтерполяція теж часто використовується в обробці зображень, даючи більш якісне зображення в порівнянні з білінійною інтерполяцією. У випадку використання бікубічної інтерполяції значення функції в шуканої точці обчислюється через її значення в 16-ти сусідніх точках.

Метод скінченних різниць

Методи скінченних різниць, методи сіток — чисельні методи розв'язку інтегро-диференціальних рівнянь алгебри, диференціального, інтегрального числення, основані на заміні диференціальних операторів різницевими операторами,інтегралів — сумами, а функцій неперервного аргументу — функціями дискретного аргументу. Така заміна приводить до системи, взагалі кажучи, нелінійних алгебраїчних рівнянь, які зрештою зводяться до лінійної системи деяким ітераційним методом. Якщо початкова задача має вигляд

,

де — циліндрова область інтеграції — межа області , — її основа, — шукана вектор-функція і — задані вектор-функції, — просторовий векторний аргумент, і — оператори (не обов'язково обмежені), то найпростіша схема інтеграції початкового рівняння має вигляд:

,

Тут — сіткова функція, що є розв'язком різницевого рівняння, — різницеві оператори, залежні від параметрів , сітки, , — сіткова область, що апроксимує деяким чином область , — її границя і — сіткові функції, що апроксимують функції і відповідно. Окремим випадком схеми (2) є схема з вагами, коли , — ваговий коефіцієнт.

Схема (2) називається двошаровою, оскільки вона зв'язує між собою значення і різницевого розв'язку на двох тимчасових шарах ; можливі також і багатошарові схеми. Якщо оператор , де — одиничний оператор, оборотний, то схема (2) може бути представлена у вигляді, що розв'язується де оператор називаєстья оператором кроку різницевої схеми і враховує крайові умови, а — функція, залежна від і . Кажуть, що оператор , залежний від параметра , апроксимує (приблизно) оператор , якщо при . Тут — деяке еталонне сімейство функцій, на якому перевіряється апроксимація (напр., сімейство достатньо гладких функцій).

Схема (2) називаєтсья коректною, або стійкою, якщо , де означає норму оператора в деякому банаховому просторі. (див. простір абстрактний у функциональному аналізі), яке може залежати від .

Схема (2) апроксимує рівняння (1), якщо і . Для лінійних систем рівнянь встановлені теореми збіжності, що стверджують, що збіжність різницевого рішення до розв'язку початкового рівняння виходить з апроксимації і коректності (стійкості) різницевої схеми.

Якщо властивості апроксимації, стійкості і збіжності мають місце ли

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти