Рівномірне кусково-поліноміальне наближення

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

Full description

Saved in:

Bibliographic Details
Date:	2006
Main Author:	Вакал, Л.П.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2006
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/6460
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Рівномірне кусково-поліноміальне наближення / Л.П. Вакал // Комп’ютерні засоби, мережі та системи. — 2006. — № 5. — С. 54-60. — Бібліогр.: 8 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-6460
record_format	dspace
spelling	Вакал, Л.П. 2010-03-04T10:57:16Z 2010-03-04T10:57:16Z 2006 Рівномірне кусково-поліноміальне наближення / Л.П. Вакал // Комп’ютерні засоби, мережі та системи. — 2006. — № 5. — С. 54-60. — Бібліогр.: 8 назв. — укр. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/6460 519.651.2 Запропоновані метод і відповідний алгоритм побудови рівномірного кусково-поліноміального наближення неперервної функції. Виконані обчислення підтвердили, що вузли розбиття та величина наближення, знайдені за цим алгоритмом, практично збігаються з оптимальними вузлами і мінімаксмінімаксною похибкою наближення. Наведені деякі результати тестування алгоритму. A method and a corresponding algorithm for solving of the uniform piecewise polynomial approximation problem are described. The algorithm is applied to compute best piecewise polynomial approximation with free knots for continuous functions. Received results confirm that knots and approximation error obtained by the algorithm agree with optimal knots and minmaxminmax error. Some algorithm testing results are given. uk Інститут кібернетики ім. В.М. Глушкова НАН України Рівномірне кусково-поліноміальне наближення Uniform piecewise polynomial approximation Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Рівномірне кусково-поліноміальне наближення
spellingShingle	Рівномірне кусково-поліноміальне наближення Вакал, Л.П.
title_short	Рівномірне кусково-поліноміальне наближення
title_full	Рівномірне кусково-поліноміальне наближення
title_fullStr	Рівномірне кусково-поліноміальне наближення
title_full_unstemmed	Рівномірне кусково-поліноміальне наближення
title_sort	рівномірне кусково-поліноміальне наближення
author	Вакал, Л.П.
author_facet	Вакал, Л.П.
publishDate	2006
language	Ukrainian
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Uniform piecewise polynomial approximation
description	Запропоновані метод і відповідний алгоритм побудови рівномірного кусково-поліноміального наближення неперервної функції. Виконані обчислення підтвердили, що вузли розбиття та величина наближення, знайдені за цим алгоритмом, практично збігаються з оптимальними вузлами і мінімаксмінімаксною похибкою наближення. Наведені деякі результати тестування алгоритму. A method and a corresponding algorithm for solving of the uniform piecewise polynomial approximation problem are described. The algorithm is applied to compute best piecewise polynomial approximation with free knots for continuous functions. Received results confirm that knots and approximation error obtained by the algorithm agree with optimal knots and minmaxminmax error. Some algorithm testing results are given.
issn	1817-9908
url	https://nasplib.isofts.kiev.ua/handle/123456789/6460
citation_txt	Рівномірне кусково-поліноміальне наближення / Л.П. Вакал // Комп’ютерні засоби, мережі та системи. — 2006. — № 5. — С. 54-60. — Бібліогр.: 8 назв. — укр.
work_keys_str_mv	AT vakallp rívnomírnekuskovopolínomíalʹnenabližennâ AT vakallp uniformpiecewisepolynomialapproximation
first_indexed	2025-11-25T23:50:49Z
last_indexed	2025-11-25T23:50:49Z
_version_	1850586561270251520
fulltext	Комп’ютерні засоби, мережі та системи. 2006, № 5 54 L.Vakal UNIFORM PIECEWISE POLYNOMIAL APPROXIMATION A method and a corresponding algo- rithm for solving of the uniform piecewise polynomial approximation problem are described. The algo- rithm is applied to compute best piecewise polynomial approximation with free knots for continuous func- tions. Received results confirm that knots and approximation error ob- tained by the algorithm agree with optimal knots and minmaxminmax error. Some algorithm testing results are given. Запропоновані метод і відповід- ний алгоритм побудови рівно- мірного кусково-поліноміального наближення неперервної функції. Виконані обчислення підтвердили, що вузли розбиття та величина наближення, знайдені за цим ал- горитмом, практично збігають- ся з оптимальними вузлами і мі- німаксмінімаксною похибкою на- ближення. Наведені деякі резуль- тати тестування алгоритму.  Л.П. Вакал, 2006 УДК 519.651.2 Л.П. ВАКАЛ РІВНОМІРНЕ КУСКОВО-ПОЛІНОМІАЛЬНЕ НАБЛИЖЕННЯ Вступ. Під кусковим наближенням (апрок- симацією) розуміють сегментну апроксима- цію, що базується на розбитті початкового проміжку наближення функції f(x) на ряд пі- дінтервалів і наближенні f(x) на кожному з цих підінтервалів деяким аналітичним вира- зом (поліномом, раціональним дробом та ін.). Кускова апроксимація найбільш зручно ре- алізується на ЕОМ, якщо на усіх підінтерва- лах функція наближається аналітичним вира- зом одного виду. Найчастіше як апроксиму- ючі вирази використовують алгебричні полі- номи. Такі кусково-поліноміальні наближен- ня успішно застосовуються на практиці при розв’язанні багатьох задач обчислювальної математики і техніки. До них належать гео- метричне моделювання плоских і просторо- вих об’єктів з кусково-гладкими границями, апроксимація розподілу струмів у вібраторах антенних решіток та ін. Слід зазначити, що за деяких умов кускові наближення можна розглядати як наближен- ня розривними сплайнами відповідного типу. Наприклад, для випадку кускового набли- ження алгебричними поліномами степеня n аналогом можуть бути розривні поліномі- альні сплайни степеня n і дефекту n+1. У цій статті пропонується метод побудови рівномірних кусково-поліноміальних набли- жень неперервних функцій і ефективний ал- горитм його реалізації. Постановка задачі. Нехай f(x) – функція, неперервна на відрізку [, ]; r – натуральне число; Р   0 1 n n nP x a a x a x      клас алгебричних поліномів степеня  n. РІВНОМІРНЕ КУСКОВО-ПОЛІНОМІАЛЬНЕ НАБЛИЖЕННЯ Комп’ютерні засоби, мережі та системи. 2006, № 5 55 Позначимо T сукупність розбиттів  0 1α βrt t       проміжку [, ] на r сегментів  -1,i it t  1,i r . Точки 0 1, , , rt t t називаються вузлами розбиття. Крім того, позначимо    i nP x і i відповідно поліном і величину найкращого рівномірного (чебишовського) наближення функції f(x) на i-му сегменті:  -1,i i iL t t                 -1 -1, , min max max n i i i i i n n P x t t x t t f x P x f x P x       . (1) В основі побудови чебишовських наближень є роботи видатного українсь- кого вченого Є.Я. Ремеза [1]. Кусково-поліноміальне наближення, кожна ланка якого є поліномом    i nP x найкращого рівномірного наближення функції f(x) на i-му сегменті з відповідною величиною найкращого наближення i , називається рівномірним (чебишовським) кусково-поліноміальним наближенням. Якщо при цьому викону- ється нерівність   i ri1 max~ , (2) то таке наближення називається рівномірним кусково-поліноміальним набли- женням із заданою похибкою . Чебишовське кусково-поліноміальне наближення n-го степеня, як зазнача- лося, можна розглядати як розривний рівномірний поліноміальний сплайн Sn(x) степеня n у вигляді         1 1 r i n n i i i S x P x x t t x        , (3) де   0, 0 1, 0 x x x      – функція Хевісайда. Розбиття  * * * * 0 1α βrt t t       називається оптимальним розбит- тям проміжку [, ], а його вузли  оптимальними вузлами, якщо  * minL      1 1 max ,i i i r L t t   . (4) Враховуючи співвідношення (1), формула (4) матиме вигляд  * min T L     1 max i r        -1 , min max - n i i n P R x t t f x P x   . (5) Отже, величину  L  можна назвати мінімаксмінімаксною похибкою кус- ково-поліноміального наближення функції f(x) на проміжку [, ]. Було доведено [3], що для довільної неперервної на невід’ємному відрізку [, ] функції f(x) оптимальне розбиття існує, хоча може бути і не єдиним. Уста- новлено також, що достатньою умовою оптимальності розбиття є рівність вели- Л.П. ВАКАЛ Комп’ютерні засоби, мережі та системи. 2006, № 5 56 чин найкращих наближень:  1,i iL t t =  1,i iL t t  для 1, 1i r   . (6) Слід додати, що при справедливості рівностей (6), рівномірне кускове на- ближення поліномами непарного степеня функції  f x , для якої    1 α,βnf x C  і    1 0 n f x   для  α,βx , (7) буде неперервним, тобто у цьому випадку сплайн виду (3) буде неперервною функцією [2, с. 20]. Вимога виконання умови (6) була покладена в основу цілого ряду методів та алгоритмів знаходження оптимальних вузлів і побудови відповідних кусково- поліноміальних наближень [47]. Наприклад в алгоритмі [5] співвідношення (6) розглядаються як система (r1)-го трансцендентного рівняння для визначення (r1)-го вузла 1 1, , rt t  ( 0 αt  , βrt  ). Для розв’язання системи застосовується метод Ньютона, необхідна кількість ітерацій якого залежить від вибору почат- кового наближення. Крім того, на функцію f(x) додатково накладаються обме- ження (7). У противагу алгоритмам, які використовують при знаходженні оптимальних вузлів методи типу Ньютона для розв’язання нелінійної системи рівнянь, алго- ритми [6, 7] збігаються для довільно вибраних початкових вузлів, у тому числі рівновіддалених, і зводяться до паралельної побудови послідовності дійсних чи- сел  τ jL , що збігається до величини  τL , і послідовності вузлів τ j , яка збігається до оптимального розбиття  . Ці алгоритми доволі громіздкі, хоча вони, за твердженням авторів, збігаються досить швидко. Далі описується розроблений автором метод побудови чебишовського кус- ково-поліноміального наближення неперервної функції, вузли розбиття і вели- чина сегментного наближення ~ якого практично збігаються з оптимальними вузлами і мінімаксною похибкою наближення  τL відповідно. Метод побудови рівномірного кусково-поліноміального наближення неперервних функцій. Цей метод є двоетапним і суть його полягає в наступно- му. На першому етапі визначається мінімальна кількість сегментів r, на які не- обхідно розбити відрізок [, ] для отримання рівномірного кусково-полі- номіального наближення функції f(x) із заданою похибкою . На другому етапі знаходим сегментне наближення функції f(x) з мінімально можливою величиною наближення ~ за фіксованої кількості сегментів r, але з вільним розташу- ванням вузлів. Розглянемо кожний з цих етапів методу детальніше. Перший етап. Процес знаходження мінімального числа сегментів r почина- ється з одного сегмента, тобто r =1, 0 αt  і 1 βt  . Далі на відрізку  0 1,t t для функції f(x) знаходимо поліном  1 ( )nP x і величину 1 =  0 1,L t t найкращо- РІВНОМІРНЕ КУСКОВО-ПОЛІНОМІАЛЬНЕ НАБЛИЖЕННЯ Комп’ютерні засоби, мережі та системи. 2006, № 5 57 го рівномірного наближення. Якщо 1 , то це означає, що бажана точність апроксимації поліномом заданого степеня n на сегменті  0 1,t t не може бути до- сягнута. Тоді відрізок наближення необхідно відповідно зменшити з коефіцієн- том k, який визначається за нижченаведеним способом, причому вузол 0t зали- шається на місці, а зміщується тільки вузол 1t . Формулу для визначення коефіцієнта зменшення k отримуємо з оцінки по- хибки сегментного наближення [1, с. 104]. Якщо для функції f(x) виконуються умови (7) і відношення        1 1 max / min n n f x f x   є досить обмеженим для x[, ], то заміна відрізка [, ] деяким сегментом довжиною (  )/k для того ж самого значення степеня n поліному найкращого рівномірного наближення призведе до зменшення відповідної величини найкращого наближення  приб- лизно в 1nk  разів, тобто 1ρ ε nk  . Звідси для обчислення коефіцієнта k отри- муємо формулу 1 ρ ε nk  . (8) Уперше нове значення it вузла it обчислюємо за формулою it   -1 -1 β- 1, 1i i t t i r k    , (9) де  – початкове значення вузла it . У загального випадку, коли зменшення від- різку здійснюється декілька разів, формула має вигляд it   -1 -1 - 1, 1i i i t t t i r k    , (9/) де it  попереднє значення вузла it . Зменшення проміжку  0 , βt згідно з формулами (8), (9) і (9/) здійснюємо до тих пір, поки не отримаємо апроксимуючий поліном з величиною чебишовсько- го наближення 1 . Останнє положення точки it приймаємо за остаточне значення 1t першого вузла розбиття відрізку [, ] на сегменти, тобто кількість сегментів r збільшується на 1 (r = 2). Вищеописану процедуру повторюємо для сегмента  1, βt . Якщо при де- якому r на відрізку  1, βrt  величина чебишовського наближення r , то це значення r буде шуканим мінімальним числом сегментів. На цьому перший етап методу закінчується. На другому етапі знаходимо рівномірне кускове наближення на r сегментах відрізку [, ] для функції f(x) поліномами з мінімально можливою величиною Л.П. ВАКАЛ Комп’ютерні засоби, мережі та системи. 2006, № 5 58 сегментного наближення ~  , де відповідно до позначень формули (2) ~ 1 maxρ .i i r  Для цього застосовуємо таку ітераційну процедуру: на кожній j-й ітерації задаємо ε j менше попереднього ( 1ε εj j ), будуємо кусково-полі- номіальне наближення, для якого величина наближення сегментної апроксимації ρ j  ε j . Якщо на деякій ( j k )-й ітерації, де k = 1, 2,..., при побудові кусково- поліноміального наближення з заданою похибкою ε j k для виконання умови ρ εj k j k  буде недостатнім кількості сегментів r, яка визначена на першому етапі, то на цьому ітераційний процес завершується. Тоді шуканим рівномірним кусково-поліноміальним наближенням на r сегментах для функції f(x) буде на- ближення, отримане на попередній (j+k1)-й ітерації, величина наближення 1ρ j k   якого буде мінімальною. Для визначення вузлів розбиття на кожній ітерації другого етапу методу ви- користовувалась та ж сама процедура, що й на першому етапі, а значення ε j для j-ї ітерації обчислювалось за формулою ε j  -1λρ j  , (10) де   коефіцієнт  15.0  , який визначається емпірично і залежить від вимог до точності (опис його вибору наводиться нижче в алгоритмі). Алгоритм побудови рівномірного кусково-поліноміального наближення неперервних функцій. Вхідні дані для алгоритму, який реалізує вищеописаний метод: n – степінь полінома-апроксиманта на кожному сегменті; ,   відповідно лівий і правий кінці усього проміжку наближення;   значення, яке не повин-но перевищувати похибка сегментного наближення; m – кількість то- чок сегмен-та, на яких виконується наближення. Обчислювальна схема алгоритму має такий вигляд: 1. Покладаємо stage = 1. Значення stage дорівнює 1, якщо не знайдено сег- ментного наближення з величиною ~  , і дорівнює 2, якщо таке наближення отримано. 2. Покладаємо значення першого вузла 1 αt  , номер сегмента i = 1, значен- ня лівого і правого кінців поточного сегмента eleft α і eright β відповідно. 3. Знаходимо значення кроку h наближення і точки  1 2, , , mx x x i-го сег- мента, на яких буде виконуватись наближення, відповідно за формулами eright eleft 1 h m    ,  eleft 1jx j h     1,j m . 4. На множині точок  1 2, , , mx x x знаходимо поліном     1 1 1 n i j n ij j P x a x     РІВНОМІРНЕ КУСКОВО-ПОЛІНОМІАЛЬНЕ НАБЛИЖЕННЯ Комп’ютерні засоби, мережі та системи. 2006, № 5 59 і його величину найкращого рівномірного наближення ρi за алгоритмом, описа- ним в [8] (див. також [1, 5]). Індекс i означає номер сегмента. 5. Якщо ρ εi  , то переходимо до п. 7, інакше – до п. 6. 6. Обчислюємо коефіцієнт k зменшення інтервалу за більш зручною для програмної реалізації, ніж (8), формулою ln ρ ln ε exp 1 ik n        . Нове значення правого кінця eright поточного сегмента знаходимо за фор- мулою eright-eleft eright eleft k   і повертаємося до п. 3. 7. Покладаємо i = i +1, erightit  . 8. Якщо eright β , тобто ми досягли кінця проміжку  , , то переходимо до п. 10, у протилежному випадку – до п. 9. 9. Покладаємо eleft = eright , eright β і повертаємося до п. 3. 10. Визначаємо величину наближення ~ кусково-поліноміальної апрокси- мації на усьому проміжку  , за формулою 1 ρ maxρ j j i   . 11. Якщо stage = 1, то переходимо до п. 12, інакше – до п. 13. 12. Покладаємо число сегментів r = i, кількість ітерацій k = 1,  ~ last , stage = 2 і переходимо до п. 14. 13. Якщо i = r, то переходимо до п. 14, у протилежному випадку – до п. 15. 14. Формуємо матрицю значень коефіцієнтів plj  1, 1, 1, 1l r j n    шляхом присвоєння plj lja . Вузли поточного розбиття сегмента lt заносимо в масив значень T : l lT t  1,l r . Покладаємо ρ ρlast   , k = k +1,  ~99.0 (або  ~999.0 ) і переходимо до п. 2. 15. Алгоритм закінчує роботу і на друк виводяться: кількість сегментів r1; вузли розбиття lT  1,l r ; матриця коефіцієнтів plj  1, 1, 1, 1l r j n    апрок- симуючих поліномів на усіх сегментах; величина сегментного наближення ρlast . Для перевірки ефективності запропонованого алгоритму виконані розрахун- ки для функцій, оптимальні вузли величина і кускове-поліноміального набли- ження яких відомі з літератури як результати аналогічних обчислень за алгорит- мами інших авторів. Для порівняння нижче у таблиці наводяться результати наближення функції  f x x на відрізку [0, 1] поліномами 3-го степеня, отримані за алгоритмом, описаним у цій статті, та за алгоритмом [6]. Легко пересвідчитись, що наведені у таблиці результати практично збігаються. Л.П. ВАКАЛ Комп’ютерні засоби, мережі та системи. 2006, № 5 60 Висновки. Перевірка на багатьох тестових прикладах показала ефектив- ність запропонованого алгоритму побудови кускового наближення поліномами n-го степеня для апроксимації довільної неперервної функцій, яка задовольняє умови (7) і значення величини (n+1)-ї похідної якої є досить обмеженим. Для такої функцій знайдені вузли розбиття та величина кусково-поліноміального наближення практично збігаються відповідно з оптимальними вузлами і міні- максмінімаксною похибкою наближення. ТАБЛИЦЯ. Наближення функції  f x x на [0, 1] поліномами 3-го степеня Число сегме- нтів Результати наближення за алгоритмом [6] Результати наближення за алгоритмом, описаним у статті Вузли розбиття Величина сегментно- го набли- ження ~ Величини наближень ρi на кож- ному сегменті Вузли розбиття Величина сегментно- го набли- ження ~ Величини наближень ρi на кож- ному сегменті 2 0.0 0.0430 1.0 0.00953 0.00953 0.0 0.0425 1.0 0.00947 0.00947 0.00935 0.00943 3 0 0.00458 0.1142 1.0 0.00334 0.00311 0.0 0.00503 0.1149 1.0 0.00326 0.00326 0.00334 0.00312 0.00325 0.00322 4 0.0 0.000921 0.0216 0.1878 1.0 0.00140 0.00139 0.0 0.00093 0.0218 0.1871 1.0 0.00141 0.00140 0.00138 0.00139 0.00139 0.00137 0.00140 0.00141 1. Ремез Е.Я. Основы численных методов чебышевского приближения. – Киев.: Наук. дум- ка, 1969. – 623 с. 2. Попов Б.А. Равномерное приближение сплайнами.  Киев.: Наук. думка, 1989. – 272 с. 3. Lawson C.L. Characteristic properties of the segmented rational minmax approximation problem // Numer. Math. – 1964. – 6, N 4. – P. 293301. 4. Вершик А.М., Малоземов В.Н., Певный А.Б. Наилучшая кусочно-полиномиальная аппро- ксимация // Сиб. мат. ж. – 1975. – XVI, № 5. – С. 925938. 5. Вопросы теории и элементы программного обеспечения минимаксных задач. – Л.: Из-во Ленинигр. ун-та, 1977. – 192 с. 6. Nürnberger G., Sommer M., Strauss H. An algorithm for segment approximation // Numer. Math. – 1986. – 48, N 4. – P. 463477. 7. Meinardus G., Nürnberger G., Sommer M., Strauss H. Algorithm for piecewise polynomials and splines with free knots // Math. of Computation – 1989. – 53, N 187. – P. 235247. 8. Олександренко В.Л., Порханова А.О. Побудова чебишовського поліноміального набли- ження функції однієї змінної за методом підвищуючої дії // Автоматика. – 1967.  № 4. – С. 8794. Отримано 20.02.2006

Рівномірне кусково-поліноміальне наближення

Institution

Similar Items