Чисельні коефіцієнти 3 страница. 12. Охлопков HLM. Численные методы решения обыкновенных дифференциальных уравнений: Учебное пособие

10. Охлопков HLM., Иванов ФМ. Лабораторные работы по методам вычислений. Часть 1: Методическое пособие.- Якутск: Издательство ЯГУ. 1992.45 с.

11. Охлопков Н.М.. Иванов Ф.В. Лабораторные работы по методам вычислении. Часть 2: Методическое пособие. - Якутск: Издательство ЯГУ 1992.42 с.

12. Охлопков HLM. Численные методы решения обыкновенных дифференциальных уравнений: Учебное пособие. Якутск: Изд - во ЯГУ. 1993. 102 с.

Урок №___ 31 ____

(згідно робочої навчальної програми)

Тема: ___ Кубічні сплайни _______

Питання: 1. Як визначаються коефіцієнти?

2. Умови неперервності сплайнів?

Інтерполяція
Локальна	Глобальна
Лінійна	Параболічна	Кубічна парабола	поліном степені (N -1)	кубічний сплайн
Рисунок 31.1.

Кубічний сплайн - це функція, яка:

- Проходить через всі задані точки,;

- На кожному відрізку між сусідніми точками є кубічної параболою;

- Неперервна разом зі своїми першої та другої похідними в усіх точках.

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

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

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

Інтерполяція	апроксимація	Інтерполяція или апроксимація	Зглажування
Рисунок 31.2.

Якщо маємо безперервну або дискретну функцію, то зазвичай використовують 5 видів перетворень функцій:

- Безперервна в дискретну (дискретизація),

- Дискретна в безперервну (інтерполяція),

- Дискретна в безперервну (апроксимація),

- Безперервна в безперервну (інтерполяція),

- Дискретна в дискретну (згладжування).

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

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

Кубічні сплайни для інтерполяції запропонував використовувати Шенберг в 1949 р. Слово " сплайн" походить від назви довгих тонких металевих рейок, які з давніх часів німецькі креслярі кріпили гвоздиками на кульмані замість лекал для проведення складних кривих.

Кубічний сплайн - це функція, яка:

- Проходить через всі задані точок,;

- На кожному відрізку між сусідніми точками є кубічним поліномом;

- Неперервна разом зі своїми першої та другої похідними у всіх точках.

Зауважимо, що, завдяки третьому умові, кубічна парабола через дві точки проводиться однозначно.

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

,

(1)

Причому між заданими точками маємо відрізок, так що в цій формулі .

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

, , ,

(2)

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

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

Постановка завдання: дані точки,. Визначити всі коефіцієнти сплайна.

Розглянемо два будь сусідніх відрізка і з номерами і. Точка для них є загальною рис. 31.3.

Рисунок 31.3. Кубический сплайн.

Кубічний сплайн правого відрізка має вигляд (31.3), а для лівого, тобто при

(3)

.

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

Такі трійки рівнянь можна записати для всіх внутрішніх вузлів , , що дає рівнянь.

(4)

(тут це номери ділянок).

Ще одне рівняння отримуємо, записуючи для останнього вузла перше з умов

(5)

В результаті отримуємо рівннь. Ці рівняння містять невідомих, т.я. для кожного відрізка між вузлами маємо 3 невідомих. Очевидно, що для однозначного визначення коефіцієнтів потрібні ще два рівняння.

Ці додаткові два рівняння можуть бути довільними, але зазвичай вважають, що функція поблизу її решт є лінійною

і ,

(6)

звідки , =0

У результаті введення двох додаткових умов виходить система рівнянь з невідомими коефіцієнтами , , . Ці рівняння можна перетворити, висловивши коефіцієнти і через . введемо формально . Тоді маємо з останнього і першого рівнянь (4) і рівняння (5):

, , .

(7)

Підставляючи ці вирази на друге рівняння (4), отримаємо СЛАУ для коефіцієнтів :

(8)

, при , .

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

Часто систему рівнянь (8) записують для других похідних у вузлах, позначаючи їх . Тоді вона приймає вигляд (Бахвалов, Чисельні методи, М., 2002):

(9)

, причьому і формально введемо .

Питання для контролю вивченого матеріалу:

1. Як визначаються коефіцієнти?

2. Умови неперервності сплайнів?

Література

1. Амосов АА., Дубжзскнн ЮА, Копченова HLB. Вычислительные методы для инженеров: Учебное пособие.-М.: Высшая школа. 1994. 544с.

2. Азаров АН.. Баснк В А.. Мелешко ИН. и др. Сборник задач по методам вычислении Пол ред. ПИ. Монастырского, -Минск: Издательство БГУ, 1983.

3. Богнаев Ю.П Вычислительная математика и программирование: Учебное пособие для студентов втузов. - М: Высшая школа. 1990. 544с.

4. Дубровская Н.С.. Численные методы: Учебник для техникумов. - М.: Высшая школа, 1976. 363c.

5. Дежидович Б П.. Марон И.А Основы вычислительной математики. - М: Издательство ФМЛ, I960. 659с,

6. Демидов Б Л.. Марон И. А. Шувалова Численные методы анализа.: Издательство ФМЛ, 1963. 400с.

7. Охлопков HLM-. Численные методы и вычислительные алгоритмы. Часть 2: Учебное пособие. — Якутск: Издательство ЯГУ. 1994.108с»

8. Охлопков HLM-. Численные методы и вычислительные алгоритмы. Часть.: Учебное пособие. - Якутск: Издательство ЯГУ. 1994.10Sc.

9. Охлопков HLM-. Бадаева ОН.. Вычислительные алгоритмы решения некоторых задач математики: Методическое пособие. -Якутск: Издательство ЯГУ, 1995. 42 с.

10. Охлопков HLM., Иванов ФМ. Лабораторные работы по методам вычислений. Часть 1: Методическое пособие.- Якутск: Издательство ЯГУ. 1992.45 с.

11. Охлопков Н.М.. Иванов Ф.В. Лабораторные работы по методам вычислении. Часть 2: Методическое пособие. - Якутск: Издательство ЯГУ 1992.42 с.

12. Охлопков HLM. Численные методы решения обыкновенных дифференциальных уравнений: Учебное пособие. Якутск: Изд - во ЯГУ. 1993. 102 с.

Урок №___ 32 ____

(згідно робочої навчальної програми)

Тема: ___ Інтерполяційні сплайни _______

Питання: 1. Причини падіння точності інтерполяції між вузлами?

2. Сплайн-інтерполяція

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

При великому числі вузлів інтерполяції розглянуті поліноми Ньютона і Лагранжа мають високу ступінь і сильно «коливаються», особливо на кінцях розглянутого інтервалу. Це призводить до падіння точності інтерполяції між вузлами переважно при обчисленні похідних. Виходом з цієї ситуації можуть бути частково інтерполяція та сплайн-інтерполяція (інтерполяція сплайнами).

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

Сплайн-інтерполяція. Інтерполюються функції на кожній ділянці між сусідніми вузлами i-1 і i представляють у вигляді полінома невеликому ступені k (k-сплайном). При k = 1 інтерпольована функція буде представляти ламану лінію, що сполучає вузли. Найбільше застосування знайшов випадок k = 3 (кубічні сплайни).

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

Такий поліном для i-го вузла (i = 1.. n) можна записати у вигляді

Si (x) = ai + bi (x - xi-1) + ci (x - xi-1) 2 + di (x - xi-1) 3. (1)

Для обчислення коефіцієнтів поліномів на всіх n ділянках необхідно мати 4n рівнянь. 2n з них отримаємо з умов проходження Si (x) через вузлові точки yi-1 і yi:

Si (xi-1) = ai = yi-1;

Si (xi) = ai + bi hi + ci hi2 + di hi3 = yi; (2)

де hi = xi - xi-1, i = 1.. n.

Додаткові рівняння отримуємо, накладаючи обмеження на похідні Si (x) у вузлах інтерполяції. Якщо вважати, що у вузлах інтерполяції повинні бути безперервними перша і друга виробниц-ні, одержимо додатково 2n - 2 рівнянь:

S'i (x) = bi + 2ci (x - xi-1) + 3di (x - xi-1) 2;

S''i (x) = 2ci + 6di (x - xi-1);

S'i (xi) = S'i +1 (xi);

S''i (xi) = S''i +1 (xi).

Звідси bi +1 = bi + 2ci hi + 3di hi2;

ci +1 = ci +3 di hi. (5.14)

Відсутні співвідношення отримаємо з умов закріплення кінців сплайна. Наприклад, при вільному закріпленні решт можна припустити, що кривизна згаданої вище пружною лінійки на кінцях дорівнює нулю, що відповідає нульовим других похідних: S''(xi-1) = 0; S''(xi) = 0.

Звідси

ci = 0;

2ci + 6di hi = 0. (3)

Отримані співвідношення (2) - (3) представляють систему ли-лінійних алгебраїчних рівнянь для визначення шуканих коефіцієнтів полінома

Питання для контролю вивченого матеріалу:

1. Причини падіння точності інтерполяції між вузлами?

2. Сплайн-інтерполяція

Література

1. Амосов АА., Дубжзскнн ЮА, Копченова HLB. Вычислительные методы для инженеров: Учебное пособие.-М.: Высшая школа. 1994. 544с.

2. Азаров АН.. Баснк В А.. Мелешко ИН. и др. Сборник задач по методам вычислении Пол ред. ПИ. Монастырского, -Минск: Издательство БГУ, 1983.

3. Богнаев Ю.П Вычислительная математика и программирование: Учебное пособие для студентов втузов. - М: Высшая школа. 1990. 544с.

4. Дубровская Н.С.. Численные методы: Учебник для техникумов. - М.: Высшая школа, 1976. 363c.

5. Дежидович Б П.. Марон И.А Основы вычислительной математики. - М: Издательство ФМЛ, I960. 659с,

6. Демидов Б Л.. Марон И. А. Шувалова Численные методы анализа.: Издательство ФМЛ, 1963. 400с.

7. Охлопков HLM-. Численные методы и вычислительные алгоритмы. Часть 2: Учебное пособие. — Якутск: Издательство ЯГУ. 1994.108с»

8. Охлопков HLM-. Численные методы и вычислительные алгоритмы. Часть.: Учебное пособие. - Якутск: Издательство ЯГУ. 1994.10Sc.

9. Охлопков HLM-. Бадаева ОН.. Вычислительные алгоритмы решения некоторых задач математики: Методическое пособие. -Якутск: Издательство ЯГУ, 1995. 42 с.

10. Охлопков HLM., Иванов ФМ. Лабораторные работы по методам вычислений. Часть 1: Методическое пособие.- Якутск: Издательство ЯГУ. 1992.45 с.

11. Охлопков Н.М.. Иванов Ф.В. Лабораторные работы по методам вычислении. Часть 2: Методическое пособие. - Якутск: Издательство ЯГУ 1992.42 с.

12. Охлопков HLM. Численные методы решения обыкновенных дифференциальных уравнений: Учебное пособие. Якутск: Изд - во ЯГУ. 1993. 102 с.

Урок №___ 34 ____

(згідно робочої навчальної програми)

Тема: ___ Кінцеві різниці _______

Питання: 1. Інтерполіція

2. Оцінка кінцевого члену інтерполяційного поліному Лагранжа

3. Роздільні і кінцеві різниці

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

Найпростіша задача, яка приводить до наближення функцій, залючається в наступному. В дискретні моменти х₁, х₂,..., х_п знаходиться значення функції у=f (x); необхідно встановити її значення при інших х.

Інколи відомо, що наближаючу функцію необхідно шукати у вигляді

Якщо параметри а₁, а₂,..., а_п визначаються з умови співпадання f (x) і наближаючої функції g (x) в точках х₁, х₂,..., х_п; g (x_і) = f (x_і), , то такий спосіб наближення називається інтерполяцією.

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

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

ІНТЕРПОЛЯЦІЯ

Інтерполяційний многочлена Лагранжа

Серед способів інтерполяції найбільш поширеним є випадок лінійної інтерполяції ,

де - фіксовані функції.

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

(1)

В випадку , маємо

(2)

і . (3)

(визначник Вандермонда), отже, система має лише один розв’язок.

Інтерполяційний многочлен (2), записаний у вигляді

(4)

називається інтерполяційним поліномом Лагранжа.

Введемо позначення: . Очевидно

; .

Тому (4) можна записати у вигляді:

. (5)

Оцінка кінцевого члену інтерполяційного поліному Лагранжа

Припустимо

.

Виберемо К з умови х* - точка, в якій оцінюється похибка. Тоді

.

При такому виборі К перетворюється в нуль в (п+ 1) точці х ₁, х ₂ ,..., х_п, х*. На основі теореми Ролля її похідна перетворюється в нуль, в крайньому випадку, в п точках, …, перетворюється в нуль, в крайньому випадку, в одній точці : ; . Так як , то з умови виходить і

, – (6)

кінцевий член інтерполяційної формули Лагранжа (4).

Визначальна схема Ейткена. Схема Ейткена дозволяє звести визначення коефіцієнтів а_і, , полінома (2) з врахуванням (4) до визначення функціональних визначників другого порядку.

Введемо позначення:

, ; (7)

, ; (8)

і т.д.

. (9)

Тоді, визначивши функціональний визначник Р _{1, 2,..., п} (х), отримаємо (4) у вигляді (2), тобто знайдемо значення коефіцієнтів а ₁, а ₂,..., а_п.

Особливо велику економію дає описана схема при визначенні значень полінома Лагранжа в фіксованих точках .

Для визначення визначників (7) маємо

, (10)

; ; .

Коефіцієнти , визначаємо за формулами:

; ;

;

; (11)

; .

Замінивши , , можна за формулами виду (11) визначити коефіцієнти полінома загального виду (9):

; (12)

,

; ; .

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

Роздільні і кінцеві різниці. Узагальненням поняття довільної є поняття роздільної різниці. Рішення різниці першого порядку визначаються рівністю

;