РОЗДІЛ 2
МЕТОДИ ОБЧИСЛЕНЬ ПОЛІНОМІАЛЬНИХ ЧЕБИШОВСЬКИХ СПЛАЙНІВ, ОРІЄНТОВАНІ НА РЕАЛІЗАЦІЮ ЗАСОБАМИ ООС
Розроблено прості обчислювальні алгоритми для знаходження параметрів рівномірних чебишовських сплайнів для наближення табличних і неперервних функцій. Це дало змогу розробити алгоритми і програмні засоби для швидкого обчислення функцій, використовуючи засоби паралельного програмування на однорідних обчислювальних структурах.
2.1. Наближення функцій поліноміальними сплайнами з заданою кількістю ланок
Розроблено алгоритм рівномірного наближення чебишовськими сплайнами табличних функцій з заданою кількістю ланок і мінімальною похибкою [44]. Для побудови алгоритму використовується алгоритм наближення рівномірними поліноміальними сплайнами з заданою похибкою , описаний в роботах [74,76]. Ці алгоритми можуть також використовуватися для наближення неперервних функцій, якщо використати значення функції в досить густій сітці. При тому різниця , ( - максимальна похибка на - ій ланці) може бути зроблена як завгодно малою.
2.1.1. Алгоритм обчислень
Для побудови алгоритму сформульовано і доведено наступні теореми [47].
Теорема 2.1. Якщо при , при і - поліном -го степеня найкращого чебишовського наближення на , де , то максимальне значення похибки цього наближення
є неперервною не спадною функцією від .
Доведення: Припустимо, що не є не спадною функцією. Тоді знайдуться такі числа і , що . Оскільки
і , то
З даної нерівності випливає, що поліном має на проміжку меншу похибку, ніж . Але це неможливо, так як найкраще поліноміальне наближення на проміжку . Одержане протиріччя показує, що - не спадна функція.
Якщо функція не є неперервною на проміжку то знайдеться точка і такі два числа і , що для будь-якого справедлива нерівність
. (2.1)
При встановленні неперервності функції розглянемо три випадки.
1. Точка не є точкою чебишовського альтернансу для функції на проміжку , тобто
(2.2)
З (2.2) і неперервності функцій і випливає, що знайдеться достатньо мале число , для якого
Відповідно, найкращі поліноміальні наближення співпадають на проміжках , і , що суперечить припущенню (2.1). Звідси неперервна в точці .
2. Точка є точкою чебишовського альтернансу для функції на проміжку , тобто
(2.3)
Виберемо таке достатньо мале , щоб на підінтервалі не було жодної точки чебишовського альтернансу функції , яка наближається поліномом на проміжку .
Тоді
. (2.4)
З виразів (2.3) і (2.4) випливає, що на проміжку і , що суперечить припущенню (2.1). Таким чином, неперервна в точці
3. Має місце рівність (2.4) і на інтервалі є точка альтернансу для функції на проміжку . Якщо таких точок декілька, то позначимо через найменшу з них Припустимо, що . Якщо це не так, то відповідно зменшимо .
З неперервності функцій , і випливає, що можна вибрати таке мале число , щоб для довільних додатних чисел , і , , де , були справедливі нерівності
, і .
Нехай для точки мають місце останні нерівності. Тоді
Так як функція не спадна, то одержана нерівність суперечить нерівності (2.1). Відповідно, функція неперервна.
Теорема 2.2. Нехай на множині точок побудований поліноміальний РЧС виду (14), який наближає функцію з заданою похибкою . Якщо максимальна похибка досягається на останній ланці, тобто , то на множині точок не існує сплайна з ланками, який наближає з похибкою меншою ніж .
Доведення: Припустимо від протилежного, що сплайн (1.4) існує. Тоді на останній -ій ланці сплайна похибка повинна бути менша ніж Але це можливо лише в випадку, якщо ліва межа цієї ланки пересунута хоч би на одну точку вправо. Якщо при цьому залишити без змін межі всіх інших ланок сплайна, то . Для того щоб , необхідно пересунути хоч би на одну точку вправо ліву межу -ї ланки сплайна. Аналогічно, для того щоб , , ,, необхідно пересунути ліву межу кожної з відповідних ланок сплайна хоч би на одну точку вправо. В цьому випадку для першої ланки сплайна одержуємо . Теорема доведена.
Розроблено алгоритм наближення, з допомогою якого при заданій кількості ланок сплайна досягається мінімальна похибка. Алгоритм використовується для наближення функцій, заданих в виді таблиць [44].
Виходячи з приведеної теореми алгоритм для сплайнів всіх видів з заданою кількістю ланок будується однотипно: спочатку знаходиться похибка , при якій кількість ланок сплайна рівна заданій, максимальна похибка, яка досягається на -ій ланці сплайна, зменшується за рахунок збільшення похибки на останній ланці сплайна. Обчислення припиняються, якщо незначне зменшення похибки веде до збільшення кількості ланок або якщо максимальна похибка досягається на останній ланці сплайна. В останньому випадку рівномірний сплайн з ланками і меншою похибкою не може бути побудований (теорема 2.2.).
При описі алгоритму обчислень для побудови рівномірного сплайна з заданою кількістю ланок введено наступні позначення:
* - задана кількість ланок сплайна;
* - початкове значення похибки, для якої будується сплайн;
* - кількість ланок сплайна, одержана при наближенні з похибкою ;
* - максимальна похибка на і-й ланці сплайна;
* - максимальна похибка, фактично одержана на одній з ланок сплайна ;
* - номер ланки сплайна на якому досягається максимальна похибка ;
* - максимальна зважена похибка, при якій ;
* - похибка, при якій ;
* - похибка, при якій ;
* - похибка, при якій ;
* - допустима відносна похибка в визначенні максимального значення , для якого, ;
* - параметр, який приймає певні значення при відповідних значеннях похибок і кількості ланок сплайна, а саме: ;
*
* і необхідна кількість ланок в процесі рахунку вже досягалася;
* - різниця між рівними величинами, яка одержується в результаті похибок заокруглення.
2.1.