A nonuniform Sinc approximation
The paper proposes an interpolatory–type approximation method based on the use of Sinc basis and arbitrary irregular grid. We obtained admissibility conditions for the nodes of irregular grid and proved an apriori error estimate of the method which depends on the relative position of irregular grid...
Saved in:
| Date: | 2017 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут математики НАН України
2017
|
| Online Access: | https://trim.imath.kiev.ua/index.php/trim/article/view/56 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Transactions of Institute of Mathematics of NAS of Ukraine |
| Download file: |  |
Institution
Transactions of Institute of Mathematics of NAS of Ukraine| _version_ | 1872552581306253312 |
|---|---|
| author | Sytnik, D. O. Сытник, Д. А. Ситник, Д. О. |
| author_facet | Sytnik, D. O. Сытник, Д. А. Ситник, Д. О. |
| author_institution_txt_mv | [
{
"author": "Д. О. Ситник",
"institution": "Інститут математики НАН України"
}
] |
| author_sort | Sytnik, D. O. |
| baseUrl_str | https://trim.imath.kiev.ua/index.php/trim/oai |
| collection | OJS |
| datestamp_date | 2018-02-13T11:57:10Z |
| description | The paper proposes an interpolatory–type approximation method based on the use of Sinc basis and arbitrary irregular grid. We obtained admissibility conditions for the nodes of irregular grid and proved an apriori error estimate of the method which depends on the relative position of irregular grid and the nodes of uniform grid associated with classical Sinc–interpolant. We further study an error of the approximation provided by a given irregular grid lying in the neighobourhood of the classical uniform grid. |
| first_indexed | 2026-08-04T01:01:42Z |
| format | Article |
| fulltext |
Збiрник праць Iнституту математики НАН України 2016, т. 13, № 3, 230–242
УДК 517.983.27
Нерiвномiрна Sinc—апроксимацiя
Д.О. Ситник
Iнститут математики НАН України, Київ; sytnikd@gmail.com
The paper proposes an interpolatory–type approximation method based
on the use of Sinc basis and arbitrary irregular grid. We obtained ad-
missibility conditions for the nodes of irregular grid and proved an apriori
error estimate of the method which depends on the relative position of
irregular grid and the nodes of uniform grid associated with classical Sinc–
interpolant. We further study an error of the approximation provided by
a given irregular grid lying in the neighobourhood of the classical uniform
grid.
В работе предлагается аппроксимаций метод интерполяционного типа,
основанный на использовании Sinc базиса и произвольной неравномер-
ной сетки. Получены условия допустимости узлов, а также априорную
оценку погрешности метода, которая зависит от взаиморасположения
узлов неравномерной сетки и классической для Sinc методов равно-
мерной сетки. Исследован порядок аппроксимации при условии малого
отклонения заданной неравномерной сетки от классической.
1 Вступ
Задача наближення функцiї за її значеннями заданими на деякiй сi-
тцi вiдмiннiй вiд тiєї, що асоцiйована з iнтерполянтом часто виникає
у цифровiй обробцi сигналiв та у прикладних сферах, що пов’язанi з
обробкою та розпiзнаванням зображень.
Першi згадки стосуються проблеми вiдновлення функцiї з обме-
женим частотним спектром за її значеннями на нерiвномiрнiй сi-
тцi, використовуючи для цього нерiвномiрний аналог розкладу в ряд
Фур’є [10]. Бiльшiсть наступних робiт присвячених данiй тематицi
стосується точного вiдновлення функцiї 𝑓 ∈ 𝑉𝑗 ⊂ 𝕃𝑝 по її значеннях,
що заданi на деякiй нерiвномiрнiй сiтцi (див., наприклад, [2,7,14,17]
та бiблiографiю в цих джерелах).
c○ Ситник Д.О., 2016
Нерiвномiрна Sinc—апроксимацiя 231
Велика кiлькiсть бiльш сучасних робiт присвячена задачам нето-
чного (чисельного) вiдновлення функцiї [1, 8, 11, 12, 18, 21, 22]. Об’єд-
нуючою рисою згаданих робiт є те, що всi вони базуються на iдеологiї
сформульованiй у [10]. Ця iдеологiя полягає у побудовi та дослiджен-
нi нових апроксимацiйних операторiв пов’язаних iз заданою нерiв-
номiрною сiткою Λ′. Подальше чисельне вiдновлення 𝑓(𝑥) здiйсню-
ється використовуючи iтерацiйне рiвняння пов’язане з побудованим
iнтерполянтом. Альтернативна технiка вiдновлення невiдомих зна-
чень функцiї 𝑓 ∈ 𝐿2 за вiдомими значеннями деяких заданих лiнiй-
них функцiоналiв вiд цiєї функцiї була запропонована у роботi [17].
Подiбно до iнших робiт тут автор розглядає задачу точного вiдновле-
ння функцiї 𝑓 (умови точного вiдновлення для бiльш широкого класу
функцiй дослiджуються у [7]), використовуючи для цього пiдхiд подi-
бний до колокацiї. Загальна схема наближення функцiї iнтерполяцiй-
ними полiномами з використанням колокацiї її невiдомих значень на
асоцiйованiй з iнтерполянтом сiтцi по вiдомим значенням цiєї функцiї
на сiтцi, що вiдмiнна вiд асоцiйованої (класичної для iнтерполянта),
був запропонований в [25].
Дана робота присвячена реалiзацiї запропонованих в [25] iдей до
Sinc–iнтерполяцiї. Бiльш детальнi вiдомостi з теорiї Sinc–методiв та,
зокрема, теорiї Sinc–iнтерполяцiї представленi у пунктi 2. Основнi ре-
зультати роботи сформульованi у пунктi 3, де нами отримано умови
допустимостi нерiвномiрної сiтки, а також доведена апрiорна оцiн-
ка похибки побудованого нерiвномiрного Sinc–апроксиманту. Як на-
слiдок з цiєї оцiнки, ми отримуємо порядок апроксимацiї у випадку
невеликого вiдхилення заданої нерiвномiрної сiтки вiд класичної.
2 Sinc–апроксимацiя
Методи що обговорюються у данiй главi завдячують своєю назвою
Sinc–функцiї:
sinc (𝑥) =
sin𝜋𝑥
𝜋𝑥
яка вперше була використана у теорiї iнформацiї (див. наприклад до-
ведення Теореми Вiттакера–Котельнiкова–Шенона [6]). Ця функцiя
математично описує iдеальний низькочастотний фiльтр i тому ши-
роко застосовуються у цифровiй обробцi сигналiв. Для спрощення
подальшого викладу теорiї ми також введемо до розгляду наступне
232 Ситник Д.О.
позначення
𝑆{𝑘, }(𝑥) ≡ sinc
(︁𝑥
− 𝑘
)︁
, > 0, 𝑘 ∈ ℤ (1)
для функцiї, що є зсунутою та про-масштабованою версiєю sinc (𝑥).
Таке позначення є бiльш зручним для описання основаних на Sinc–
функцiї апроксимацiйних та квадратурних формул. Послiдовнiсть{︂
1√
𝑆(𝑘, )
}︂∞
𝑘=−∞
(2)
утворює повний ортонормований базис у просторi 𝐖(𝜋/) iнтегров-
них з квадратом функцiй 𝑓(𝑥) ∈ ℝ, таких, що ∀𝑧 ∈ ℂ функцiя 𝑓(𝑧)
аналiтична, причому |𝑓(𝑧)| ≤ 𝐶e𝜋|𝑧/|, з деякою додатною констан-
тою 𝐶 [19]. Вирiзняючою властивiстю Sinc–базису (1) з помiж iнших
неполiномiальних базисiв є те що проекцiя ∀𝑓 ∈ 𝐖(𝜋/) на 𝑘-й еле-
мент базису 𝑆{𝑘, }(𝑥) дорiвнює 𝑓(𝑘). Звiдки, позначивши
𝐶∞{𝑓, }(𝑥) =
∞∑︁
𝑘=−∞
𝑓(𝑘)𝑆{𝑘, }(𝑥),
матимемо
𝑓(𝑥) = 𝐶∞{𝑓, }(𝑥), 𝑥 ∈ ℝ.
Простiр 𝐖(𝜋/) є завузьким з точки зору застосувань оскiльки
вимагає аналiтичностi функцiї у всiй комплекснiй площинi. Вияви-
лось [19], що обмеження областi аналiтичностi функцiї до смуги 𝐷𝑑
𝐷𝑑 = {𝑧 = 𝑥+ 𝑖𝑦 𝑥 ∈ (−∞,∞), |𝑦| ≤ 𝑑} (3)
не призводить до втрати якiсних апроксимацiйних властивостей ба-
зису (2). Множина функцiй 𝑓(𝑧) аналiтичних у смузi 𝑧 ∈ 𝐷𝑑, для
деякого 𝑑 < 𝜋/2 i таких, що величина
𝑁1(𝑓,𝐷𝑑) ≡
∫︁
𝜕𝐷𝑑
|𝑓(𝑧)|𝑑𝑧 <∞,
утворює простiр, який називається простором Хардi 𝐻1(𝐷𝑑) з нор-
мою ‖𝑓‖ = 𝑁1(𝑓,𝐷𝑑) (аналогiчно можна визначити простiр 𝐻𝑥(𝐷𝑑)
для 𝑥 = 2, 3, . . . [19]). У цьому просторi розклад 𝑓(𝑥) по послiдовностi
Нерiвномiрна Sinc—апроксимацiя 233
функцiй 𝑆{𝑘, } (2) вже не є точним. Тим не менше, ∀𝑓 ∈ 𝐻1(𝐷𝑑)
справедлива наступна оцiнка точностi такого розкладу [20, с. 383]
sup
𝑥∈ℝ
|𝑓(𝑥)− 𝐶∞{𝑓, }(𝑥)| ≤ 𝑐e−𝜋𝑑/, (4)
константа 𝑐 > 0 не залежить вiд . Тобто, замiна функцiї 𝑓 ∈ 𝐻1(𝐷𝑑)
рядом який побудований з використанням значень 𝑓(𝑥) на дискре-
тнiй множинi точок призводить до виникнення експоненцiально ма-
лої похибки, при → 0. Похибку такого роду у лiтературi прийнято
називати похибкою дискретизацiї [23]. Згiдно пiдходу, запропонова-
ному в [9] для аналiзу точностi чисельних методiв з використанням
теорiї функцiй комплексної змiнної, похибка дискретизацiї є однiєю
з двох складових загальної похибки апроксимацiйного методу. Iнша
складова загальної похибки виникає при замiнi 𝐶∞{𝑓, }(𝑥) рядом
скiнченної довжини 𝐶𝑁{𝑓, }(𝑥) :
𝐶𝑁{𝑓, }(𝑥) =
𝑁∑︁
𝑘=−𝑁
𝑓(𝑘)𝑆{𝑘, }(𝑥), (5)
де 𝑁 > 0 – цiлий параметр, який визначає кiлькiсть точок Sinc–
апроксимацiйної формули рiвну 2𝑁 +1. Таку похибку називають по-
хибкою округлення (вiдкидання). Має мiсце наступна теорема [19, с.
137]:
Теорема 2.1. Якщо функцiя 𝑓 ∈ 𝐻1(𝐷𝑑) є такою, що ∀𝑥 ∈ ℝ вико-
нується умова
|𝑓(𝑥)| ≤ 𝐿e−𝛼|𝑥|, з деякими 𝛼,𝐿 > 0. (6)
Тодi, вибравши
=
√︂
𝜋𝑑
𝛼𝑁
(7)
для похибки Sinc–апроксимацiї функцiї 𝑓(𝑥) рядом 𝐶𝑁{𝑓, }(𝑥) спра-
ведлива оцiнка
sup
𝑥∈ℝ
|𝑓(𝑥)− 𝐶𝑁{𝑓, }(𝑥)| ≤ 𝑐ℰ𝑁 ,
ℰ𝑁 = 𝑁1/2e−
√
𝜋𝑑𝛼𝑁 ,
(8)
з константою 𝑐 залежною вiд 𝑓, 𝑑, 𝛼 та незалежною вiд 𝑁 .
234 Ситник Д.О.
При доведенi теореми, загальну похибку Sinc–апроксимацiї пред-
ставляють у виглядi суми двох згаданих складових. Умова (6) накла-
дена для того, щоб оцiнити залишок ряду |𝐶∞{𝑓, }(𝑥)−𝐶𝑁{𝑓, }(𝑥)| ≤
e−
√
𝜋𝑑𝛼𝑁 i таким чином узгодити похибку округлення з похибкою
дискретизацiї (4). Подiбнi мiркування можуть бути застосованими
до ситуацiї коли область аналiтичностi не змiнюється, а швидкiсть
спадання 𝑓(𝑥) на ℝ повiльнiша нiж експоненцiальна. Похибка окру-
глення, в такiй ситуацiї, домiнуватиме над похибкою дискретизацiї i
буде вносити основний вклад до загальної похибки методу.
У переважнiй бiльшостi застосувань параметри 𝑑, 𝛼 не доступнi
апрiорно, тому наступний вигляд похибки є бiльш зручним на пра-
ктицi
ℰ(𝑁) = 𝐶1
√
𝑁e−𝐶2
√
𝑁 . (9)
Цю формулу, насправдi застосовують для зворотньої задачi оцiнки
𝑁 , як функцiї вiд ℰ :
𝑁(ℰ) =
[︂
1
𝐶2
𝐖2
(︂
−𝐶2
𝐶1
ℰ
)︂
+ 1
]︂
, (10)
де 𝐖(𝑧) означає нижню гiлку функцiї Ламберта 𝙻𝚊𝚖𝚋𝚎𝚛𝚝𝚆(−1, 𝑧),
[16], а [·] – цiла частина вiд числа. Для цього спочатку за допомо-
гою (9) наближено знаходяться сталi 𝐶1, 𝐶2, а потiм за формулою
(10) обчислюється значення 𝑁 . Оцiнки на 𝐶1, 𝐶2 можна отримати
використовуючи апостерiорну схему, що базується на визначеннi не-
вiдомих сталих з системи рiвнянь складених на основi значення фун-
кцiї 𝑓(𝑥) та двох її наближень 𝐶𝑁{𝑓, }(𝑥) при 𝑁 = 𝑁0, 2𝑁0. Або
трьох наближень 𝑁 = 𝑁0, 2𝑁0, 4𝑁0, якщо точне значення функцiї не
доступно для жодного 𝑥. Строго кажучи, для формування системи
рiвнянь з невiдомими 𝐶1, 𝐶2 потрiбно чотири наближення до 𝑓(𝑥).
Три наближених значення дозволяють тiльки оцiнити константи 𝐶1
та 𝐶2 знизу. У бiльшостi випадкiв (для достатьно великих 𝑁0) така
оцiнка є досить точною.
Окрiм згаданих вище результатiв, що стосуються Sinc–апроксимацiї,
мiркування викладенi у пунктi 3 спираються на поняття колокацiї.
Наступний результат дозволяє оцiнити точнiсть наближення деякої
𝑓(𝑥) Sinc–апроксимантом за умови, що вiдомi тiльки наближеннi зна-
чення 𝑓(𝑥) у вiдповiдних точках апроксимацiї.
Теорема 2.2 (Stenger, [20, Теорема 3.3]). Нехай для функцiї 𝑓 ∈
𝐻1(𝐷𝑑) виконуються всi умови Теореми 2.1. Якщо для набору чисел
Нерiвномiрна Sinc—апроксимацiя 235
𝑐𝑘 ∈ ℂ, 𝑘 = −𝑁,𝑁 виконується умова(︃
𝑁∑︁
𝑘=−𝑁
|𝑓(𝑘)− 𝑐𝑘|2
)︃1/2
< 𝛿, (11)
з деяким додатнiм 𝛿 ∈ ℝ, то
sup
𝑥∈ℝ
⃒⃒⃒⃒
⃒𝑓(𝑥)− 1
𝑁∑︁
𝑘=−𝑁
𝑐𝑘𝑆{𝑘, }(𝑥)
⃒⃒⃒⃒
⃒ ≤ 𝑐ℰ𝑁 + 𝛿, (12)
з 𝑐, ℰ𝑁 визначеними в (8).
3 Sinc-апроксимацiя функцiї за її значеннями поза
iнтерполяцiйною сiткою
У цiй главi ми запропонуємо метод наближення функцiї 𝑓(𝑥) за її
значеннями на нерiвномiрнiй сiтцi та знайдемо оцiнку похибки отри-
маного наближення. Цей чисельний метод є адаптацiєю технiки роз-
робленої в [25] до використання Sinc–базису (2). Вiн полягає у ко-
локацiї 𝑓(𝑥) на заданiй нерiвномiрний сiтцi з використанням Sinc–
iнтерполянту (5). Процедура колокацiї, як вiдомо, приводить систе-
ми лiнiйних рiвнянь (колокацiйної системи) де невiдомими є значе-
ння iнтерполянта у вузлах асоцiйованої з ним сiтки {𝑘}𝑁𝑘=−𝑁 (див.
формулу (5)). Цi значення очевидно будуть вiдрiзнятися вiд послi-
довностi 𝑓(𝑘), 𝑘 = −𝑁,𝑁 потрiбної для побудови 𝐶𝑁{𝑓, }(𝑥). Не
зважаючи на це, виконання зазначених далi умов гарантує “близькi-
сть” обчислених, розв’язуючи колокацiйну систему рiвнянь, значень
до значень функцiї 𝑓(𝑘), а також те, що iнтерполянт, побудований
на основi обчислених значень, буде наближенням (апроксимантом)
до функцiї 𝑓(𝑥) ∀𝑥 ∈ ℝ (див. [25, Теорема 2.2]).
Символами Λ𝑆 та Λ позначимо сiтки:
Λ𝑆 = {𝑘}𝑁𝑘=−𝑁 , Λ = {𝑥𝑘}𝑁𝑘=−𝑁 , 𝑁 ∈ ℕ, (13)
де а 𝑥𝑘 ∈ 𝑅 — заданi вузли, а > 0 — фiксований крок залежний
вiд 𝑁 . Сiтку Λ називатимемо нерiвномiрною, припускаючи таким чи-
ном, що Λ не спiвпадає з Sinc-iнтерполяцiйною сiткою Λ𝑆 . Введемо до
розгляду лiнiйний оператор 𝐷 (Λ) : 𝑋𝑛 → 𝑋𝑛, який ставить у вiдпо-
вiднiсть впорядкованому набору елементiв 𝐳 = (𝑧−𝑁 , 𝑧−𝑁+1, . . . 𝑧𝑁 )
𝑇 ,
236 Ситник Д.О.
𝑧𝑖 ∈ ℂ, 𝑖 = −𝑁,𝑁 вiдповiдний набiр значень iнтерполянта
𝐶𝑁{𝐳, }(𝑥) = 1
𝑁∑︁
𝑘=−𝑁
𝑧𝑘𝑆{𝑘, }(𝑥),
на сiтцi Λ за правилом 𝐷 (Λ) 𝐳 = Φ𝐳,
Φ =
[︀
𝑆𝑘 (𝑥𝑛)
]︀𝑁
𝑛,𝑘=−𝑁 ≡
⎛⎜⎝𝑆−𝑁 (𝑥−𝑁 ) · · · 𝑆𝑁 (𝑥−𝑁 )
...
. . .
...
𝑆−𝑁 (𝑥𝑁 ) · · · 𝑆𝑁 (𝑥𝑁 )
⎞⎟⎠ ,
де 𝑆𝑘(𝑥) = 𝑆{𝑘, }(𝑥).
Зауважимо, що 𝐷 (Λ) 𝐟 , 𝐟 = (𝑓(−𝑁), . . . , 𝑓(𝑁))𝑇 це проекцiя iн-
терполяцiйного оператора 𝑓 → 𝐶𝑁{𝑓, } на сiтку Λ.
Лема 3.1. Припустимо, що, для фiксованих та 𝑁 , задано сiтку
Λ (13). Якщо
Δ ∩ {±𝑘}∞𝑘=𝑁 = ∅, (14)
то iснує обмежена обернена Φ−1 ≡
[︀
𝑑𝑛𝑘
]︀𝑁
𝑛,𝑘=−𝑁 ,
𝑑𝑛𝑘 =
𝜋(−1)𝑛
𝑁∏︀
𝑟=−𝑁
(𝑥𝑟 − 𝑛) (𝑥𝑘 − 𝑟)
(𝑥𝑘 − 𝑛) sin𝜋𝑥𝑘
𝑁∏︀
𝑟=−𝑁
𝑟 ̸=𝑛
(𝑛− 𝑟)
𝑁∏︀
𝑟=−𝑁
𝑟 ̸=𝑘
(𝑥𝑟 − 𝑥𝑘)
, (15)
яка визначає обернений оператор 𝐷−1 (Λ) 𝐟 = Φ−1𝐟 .
Доведення. Перепишемо матрицю Φ у виглядi
Φ =
𝜋
𝑃𝐴𝑅
де 𝑃 = diag
[︀
sin
(︀
𝜋 𝑥−𝑁
)︀
, . . . , sin
(︀
𝜋 𝑥𝑁
)︀]︀
, 𝑅 = diag
[︁{︀
(−1)𝑘
}︀𝑁
𝑘=−𝑁
]︁
,
𝐴 =
[︁
1
𝑥𝑛−𝑘
]︁𝑁
𝑛,𝑘=−𝑁
. В роботi [24, Лема 2.1] показано, що матриця
𝐴 має обернену 𝐴−1 = [𝑎𝑛𝑘]
𝑁
𝑛,𝑘=−𝑁 за умови 𝑥𝑛 ̸= 𝑘, 𝑘 = −𝑁,𝑁 ,
Нерiвномiрна Sinc—апроксимацiя 237
причому
𝑎𝑛𝑘 =
𝑁∏︀
𝑟=−𝑁
(𝑥𝑟 − 𝑛) (𝑥𝑘 − 𝑟)
(𝑥𝑘 − 𝑛)
𝑁∏︀
𝑟=−𝑁
𝑟 ̸=𝑛
(𝑛− 𝑟)
𝑁∏︀
𝑟=−𝑁
𝑟 ̸=𝑘
(𝑥𝑟 − 𝑥𝑘)
.
Враховуючи вигляд 𝑎𝑛𝑘, для елементiв Φ−1 = 𝜋
𝑅
−1𝐴−1𝑃−1 отриму-
ємо представлення (15).
Нехай 𝐛 = (𝑓(𝑥−𝑁 ), . . . , 𝑓(𝑥𝑁 ))
𝑇 ∈ ℂ2𝑁+1 вектор вiдомих значень
функцiї 𝑓(𝑥) на сiтцi Λ. Припустивши виконання умови (14), означи-
мо 𝐠 ∈ ℂ2𝑁+1, як вектор 𝐠 = (𝑔−𝑁 , . . . , 𝑔𝑁 )
𝑇 , що задовольняє рiвня-
ння
𝐷 (Λ)𝐠 = 𝐛. (16)
В якостi векторної норми ‖ · ‖2𝑁+1 простору ℂ2𝑁+1 використовувати-
мемо
‖𝐱‖2𝑁+1 = max
−𝑁≤𝑘≤𝑁
|𝑥𝑘|, ∀𝐱 ≡ (𝑥−𝑁 , . . . , 𝑥𝑁 )
𝑇 ∈ ℂ2𝑁+1.
Наступна лема характеризує похибку наближення невiдомих зна-
чень функцiї 𝑓(𝑥) на сiтцi Λ𝑆 елементами вектору 𝐠.
Лема 3.2. Нехай 𝑓 ∈ 𝐻1(𝐷𝑑) задовольняє умову (6).Якщо для за-
даної стiки Δ виконується умова (14), де визначена формулою
(7), то похибка наближення 𝐟 = (𝑓(−𝑁), . . . , 𝑓(𝑁))𝑇 вектором 𝐠,
обчисленим з (16), задовольняє нерiвнiсть
‖𝐟 − 𝐠‖2𝑁+1 ≤ 𝑐
⃦⃦
𝐷−1(Λ)
⃦⃦
ℰ𝑁 , (17)
де ‖·‖ — матрична норма узгоджена з ‖ · ‖2𝑁+1, а величини 𝑐, ℰ𝑁
визначенi у формулi (8).
Доведення. Символом 𝐯 позначимо вектор значень iнтерполяцiйного
полiнома 𝐶𝑁{𝑓, }(𝑥) на сiтцi Λ, тобто
𝐷(Λ)𝐟 = 𝐯.
Вiднявши почленно рiвнiсть (16) вiд попередньої рiвностi, отримаємо
𝐷(Λ) (𝐟 − 𝐠) = 𝐯 − 𝐛.
238 Ситник Д.О.
Умова (14) гарантує iснування 𝐷−1(Λ), тому
‖𝐟 − 𝐠‖2𝑁+1 =
⃦⃦
𝐷−1(Λ) (𝐯 − 𝐛)
⃦⃦
2𝑁+1
≤
⃦⃦
𝐷−1(Λ)
⃦⃦
‖𝐯 − 𝐛‖2𝑁+1 .
Норму ‖𝐯 − 𝐛‖2𝑁+1 з попередньої нерiвностi оцiнимо використову-
ючи формулу (8), теореми 2.1, справедливiсть якої забезпечується
обмеженнями накладеними на 𝑓(𝑥) в умовi леми. Маємо
‖𝐯 − 𝐛‖2𝑁+1 ≤ sup
𝑥∈ℝ
⃒⃒
𝑓(𝑥)− 𝐶𝑁 {𝑓, } (𝑥)
⃒⃒
≤ 𝑐ℰ𝑁 ,
що й доводить (17).
Зауваження 3.1. Явний вигляд
⃦⃦
𝐷−1(Λ)
⃦⃦
наступний
⃦⃦
𝐷−1(Λ)
⃦⃦
=
𝜋
max
−𝑁≤𝑛≤𝑁
𝑁∏︀
𝑟=−𝑁
|𝑥𝑟 − 𝑛|
2𝑁 |𝑛−𝑁 |! |𝑛+𝑁 |!
×
𝑁∑︁
𝑘=−𝑁
⃒⃒⃒⃒
𝑥𝑘 − 𝑘
sin𝜋𝑥𝑘 (𝑥𝑘 − 𝑛)
⃒⃒⃒⃒ 𝑁∏︁
𝑟=−𝑁
𝑟 ̸=𝑘
⃒⃒⃒⃒
𝑥𝑘 − 𝑟
𝑥𝑟 − 𝑥𝑘
⃒⃒⃒⃒
.
(18)
Матрицi виду 𝐷(Λ) в лiтературi носять назву узагальнених ма-
триць типу Кошi. Не зважаючи на те, що норма оберненої матрицi
𝐷−1(Λ) зростає коли сiтка Λ конденсується, це не обов’язково по-
гiршує стiйкiсть алгоритмiв обчислення цiєї матрицi. Справедливо
наступне
Зауваження 3.2. Для фiксованих 𝑓(𝑥) та Λ лiнiйна система (16)
може бути розв’язана з використанням обчислювально стiйких ал-
горитмiв [3,4], алгоритмiчна складнiсть яких — 7(2𝑁 + 1)2.
Сформулюємо основний результат роботи.
Теорема 3.1. Нехай 𝑓 ∈ 𝐻1(𝐷𝑑) задовольняє умову (6) з параме-
трами 𝛼, 𝐿, а для заданої стiки Δ виконується умова (14), де крок
визначений формулою (7). Тодi iснує апроксимант 𝐶 ′
𝑁 {𝑓, } (𝑥),
залежний виключно вiд значень 𝑓(𝑥) на Δ:
𝐶 ′
𝑁 {𝑓, } (𝑥) = 1
𝑁∑︁
𝑘=−𝑁
𝑔𝑘𝑆{𝑘, }(𝑥), (19)
Нерiвномiрна Sinc—апроксимацiя 239
де 𝑔𝑘 отриманi з (16) або за допомогою явного обчислення Φ−1 (15).
Похибка наближення функцiї 𝑓(𝑥) апроксимантом 𝐶 ′
𝑁 {𝑓, } (𝑥)
задовольняє нерiвнiсть
sup
𝑥∈ℝ
|𝑓(𝑥)− 𝐶 ′
𝑁 {𝑓, } (𝑥)| ≤ 𝑐
(︀
1 +
⃦⃦
𝐷−1(Λ)
⃦⃦)︀√
𝑁e−
√
𝜋𝑑𝛼𝑁 , (20)
причому стала 𝑐 не залежить вiд 𝑁 та Δ.
Доведення. Для доведення достатньо послiдовно застосувати Лему
3.2 та Теорему 2.2.
Наслiдок 3.1. Припустимо, що для функцiї 𝑓(𝑥) та сiтки Δ вико-
нуються умови Теореми 3.1. Якщо, для будь-яких 𝑘, 𝑝 ∈ {−𝑁, . . . , 𝑁}
∃𝜆 < 1, 𝛿 > 0 : |𝑥𝑘 − 𝑘| ≤ 𝜆, |𝑥𝑘 − 𝑥𝑝| ≥ 𝛿, (21)
то похибка наближення 𝑓(𝑥) апроксимантом 𝐶 ′
𝑁 {𝑓, } (𝑥) задоволь-
няє нерiвнiсть (20), причому
⃦⃦
𝐷−1(Λ)
⃦⃦
≤ 𝑐
(︂
𝛿
)︂2𝑁
(2𝑁 + 1)1+2𝜆
(1− 𝜆)2𝜆
, (22)
де стала 𝑐 не залежить вiд 𝑁 cv.
Доведення. Для оцiнки
⃦⃦
𝐷−1(Λ)
⃦⃦
розглянемо складовi явної форму-
ли (18) по–черзi.
𝑁∏︁
𝑟=−𝑁
𝑟 ̸=𝑘
⃒⃒⃒⃒
𝑥𝑘 − 𝑟
𝑥𝑟 − 𝑥𝑘
⃒⃒⃒⃒
=
𝑘−1∏︁
𝑟=−𝑁
⃒⃒⃒⃒
𝑥𝑘 − 𝑟
𝑥𝑟 − 𝑥𝑘
⃒⃒⃒⃒ 𝑁∏︁
𝑟=𝑘+1
⃒⃒⃒⃒
𝑥𝑘 − 𝑟
𝑥𝑟 − 𝑥𝑘
⃒⃒⃒⃒
≤
(︂
𝛿
)︂2𝑁 𝑘−1∏︁
𝑟=−𝑁
⃒⃒⃒⃒
𝑘 − 𝑟 + 𝜆
𝑘 − 𝑟
⃒⃒⃒⃒ 𝑁∏︁
𝑟=𝑘+1
⃒⃒⃒⃒
𝑟 − 𝑘 − 𝜆
𝑟 − 𝑘
⃒⃒⃒⃒
≤
(︂
𝛿
)︂2𝑁
Γ(𝑁 + 𝑘 + 𝜆+ 1)Γ(𝑁 − 𝑘 − 𝜆+ 1)
Γ(𝑁 − 𝑘 + 1)Γ(𝑁 − 𝑘 + 1)
,
Функцiя в правiй частинi останньої оцiнки — парна, тому, не втра-
чаючи загальностi далi припускатимемо 𝑘 ≥ 0. Застосувавши вiдомi
240 Ситник Д.О.
властивостi Гамма функцiї Γ(·), отримаємо
𝑁∏︁
𝑟=−𝑁
𝑟 ̸=𝑘
⃒⃒⃒⃒
𝑥𝑘 − 𝑟
𝑥𝑟 − 𝑥𝑘
⃒⃒⃒⃒
≤
(︂
𝛿
)︂2𝑁
(𝑁 + 𝑘 + 1)𝜆
(𝑁 − 𝑘 − 𝜆+ 1)𝜆
. (23)
Використаємо (23) для оцiнки iнших складових (18). Матимемо
𝑁∑︁
𝑘=−𝑁
⃒⃒⃒⃒
𝑥𝑘 − 𝑘
sin𝜋𝑥𝑘 (𝑥𝑘 − 𝑛)
⃒⃒⃒⃒ 𝑁∏︁
𝑟=−𝑁
𝑟 ̸=𝑘
⃒⃒⃒⃒
𝑥𝑘 − 𝑟
𝑥𝑟 − 𝑥𝑘
⃒⃒⃒⃒
≤𝑐2
(︂
𝛿
)︂2𝑁 𝑁∑︁
𝑘=−𝑁
𝛿
|sin𝜋𝑥𝑘 (𝑥𝑘 − 𝑛)|
(𝑁 + 𝑘 + 1)𝜆
(𝑁 − 𝑘 − 𝜆+ 1)𝜆
≤𝑐2𝑐3
𝜋
(︂
𝛿
)︂2𝑁
(2𝑁 + 𝜆)1+𝜆
𝜆(1− 𝜆)𝜆
.
Аналогiчно
𝑁∏︀
𝑟=−𝑁
|𝑥𝑟 − 𝑛|
2𝑁 |𝑛−𝑁 |! |𝑛+𝑁 |!
≤ 𝑐4
𝜆(2𝑁 + 1)𝜆
(1− 𝜆)𝜆
. (24)
Застосувавши (23) та (24) до (18) та позначивши 𝑐2𝑐3𝑐4 = 𝑐, отрима-
ємо (22).
Основною перевагою методу наближення функцiї апроксимантом
𝐶 ′{𝑓, } за значеннями цiєї функцiї на нерiвномiрнiй сiтцi є те, що, за-
стосування колокацiї дозволяє вiдносно прозоро отримати апрiорну
оцiнку похибки, а також виокремити клас сiток де ця оцiнка еквi-
валентна за порядком до класичної оцiнки похибки (8). Це вигiдно
вiдрiзняє запропонований в роботi метод вiд iнших [5,13,15]. В майбу-
тнiх роботах планується застосування розробленого методу до Sinc–
квадратур та iнших чисельних методiв, якi базуються на використан-
нi Sinc базису.
[1] Adcock B., Gataric M., Hansen A. On stable reconstructions
from nonuniform fourier measurements // SIAM Journal on
Imaging Sciences. — 2014. — Vol. 7, no. 3. — P. 1690–1723. —
http://dx.doi.org/10.1137/130943431.
http://dx.doi.org/10.1137/130943431
http://dx.doi.org/10.1137/130943431
http://dx.doi.org/10.1137/130943431
Нерiвномiрна Sinc—апроксимацiя 241
[2] Benedetto J. J. Irregular sampling and frames // Wavelets: A Tutorial
in Theory and Applications / Ed. by Charles K. Chui.— San Diego, CA,
USA : Academic Press Professional, Inc., 1992. — P. 445–507. — Access
mode: http://dl.acm.org/citation.cfm?id=160964.159455.
[3] Boros T., Kailath T., Olshevsky V. A fast parallel björck–pereyra-type
algorithm for solving cauchy linear equations // Linear Algebra and Its
Applications.— 1999.—Vol. 302.—P. 265–293.
[4] Boros T., Kailath T., Olshevsky V. Pivoting and backward stability of
fast algorithms for solving cauchy linear equations // Linear algebra and
its applications.— 2002.—Vol. 343.—P. 63–99.
[5] Boyd J. P. A fast algorithm for chebyshev, fourier, and sinc interpo-
lation onto an irregular grid // Journal of Computational Physics. —
1992. — Vol. 103, no. 2. — P. 243 – 257. — Access mode: http://www.
sciencedirect.com/science/article/pii/002199919290399J.
[6] Brigham E. The Fast Fourier Transform and Its Applications.—Prentice
Hall, 1988.—P. 463.
[7] Clark J., Palmer M., Lawrence P. A transformation method for the re-
construction of functions from nonuniformly spaced samples // Acoustics,
Speech and Signal Processing, IEEE Transactions on. — 1985. — Oct. —
Vol. 33, no. 5.—P. 1151–1165.
[8] Condat L. Reconstruction from non-uniform samples: A direct, variational
approach in shift-invariant spaces // Digital Signal Processing.— 2013.—
Vol. 23, no. 4.—P. 1277 – 1287.
[9] Davis P. Errors of numerical approximation for analytic functions // Jour-
nal of Rational Mechanics and Analysis. — 1953.—Vol. 2, no. 3.—P. 303–
313.
[10] Duffin R. J., Schaeffer A. C. A class of nonharmonic fourier series //
Transactions of the American Mathematical Society. — 1952. — Vol. 72,
no. 2.—P. 341–366.
[11] Feichtinger H. G., Gröchenig K. Theory and practice of irregular sam-
pling // Wavelets, Mathematics and Applications / Ed. by J. J. Benedetto,
M. W. Frazier.—CRC Press, 1994.—P. 305–363.
[12] Feichtinger H. G., Gröchenig K., Strohmer T. Efficient numerical meth-
ods in non-uniform sampling theory // Numer. Math. — 1995. — Feb.—
Vol. 69, no. 4.—P. 423–440.
[13] Greengard L., Lee J.-Y., Inati S. The fast sinc transform and image recon-
struction from nonuniform samples in k-space // Communications in Ap-
plied Mathematics and Computational Science.— 2007.—Vol. 1, no. 1.—
P. 121–131.
http://dl.acm.org/citation.cfm?id=160964.159455
http://dx.doi.org/10.1016/s0024-3795(99)00115-9
http://dx.doi.org/10.1016/s0024-3795(99)00115-9
http://dx.doi.org/10.1016/s0024-3795(01)00519-5
http://dx.doi.org/10.1016/s0024-3795(01)00519-5
http://dx.doi.org/http://dx.doi.org/10.1016/0021-9991(92)90399-J
http://www.sciencedirect.com/science/article/pii/002199919290399J
http://www.sciencedirect.com/science/article/pii/002199919290399J
http://dx.doi.org/10.1109/TASSP.1985.1164714
http://dx.doi.org/10.1109/TASSP.1985.1164714
http://dx.doi.org/http://dx.doi.org/10.1016/j.dsp.2013.01.015
http://dx.doi.org/10.1007/s002110050101
242 Ситник Д.О.
[14] Marks R. J. Advanced topics in Shannon sampling and interpolation the-
ory.— 1993.—Vol. 1.—P. 360.
[15] Maymon S., Oppenheim A. Sinc interpolation of nonuniform samples //
Signal Processing, IEEE Transactions on. — 2011. — Oct. — Vol. 59,
no. 10.—P. 4745–4758.
[16] On the LambertW function / R.M. Corless, G.H. Gonnet, D.E.G. Hare
et al. // Advances in Computational Mathematics. — 1996. — Vol. 5,
no. 1.—P. 329–359.
[17] Papoulis A. Generalized sampling expansion // Circuits and Systems,
IEEE Transactions on.— 1977.—Nov.—Vol. 24, no. 11.—P. 652–654.
[18] Scherzer O., Strohmer T. A multi-level algorithm for the solution of mo-
ment problems // Numerical Functional Analysis and Optimization. —
1998.—Vol. 19, no. 3-4.—P. 353–375.
[19] Stenger F. Numerical methods based on Sinc and analytic functions. —
Springer, New York, 1993.—P. 580.
[20] Stenger F. Summary of sinc numerical methods // J. Comput. Appl.
Math.— 2000.—Vol. 121.—P. 379–420.
[21] Strohmer T. A levinson–galerkin algorithm for regularized trigonomet-
ric approximation // SIAM Journal on Scientific Computing. — 2000. —
Vol. 22, no. 4.—P. 1160–1183.
[22] Strohmer T. Numerical analysis of the non-uniform sampling problem //
Journal of Computational and Applied Mathematics. — 2000. — Vol.
122, no. 1–2. — P. 297 – 316. — Numerical Analysis in the 20th Cen-
tury Vol. II: Interpolation and Extrapolation. Access mode: http:
//www.sciencedirect.com/science/article/pii/S0377042700003617.
[23] Trefethen L. N., Weideman J. The exponentially convergent trapezoidal
rule // SIAM Review.— 2014.—Vol. 56, no. 3.—P. 385–458.
[24] Trench W. F., Scheinok P. A. On the inversion of a Hilbert type matrix //
SIAM Review.— 1966.— jan.—Vol. 8, no. 1.—P. 57–61.
[25] Ситник Д. О. Метод iтеративної апроксимацiї функцiй з використан-
ням iнтерполянтiв у банахових просторах // Збiрник праць Iнституту
математики НАН України. — 2015. — Т. 12, № 5. — С. 140–159.
http://dx.doi.org/10.1109/TSP.2011.2160054
http://dx.doi.org/10.1007/BF02124750
http://dx.doi.org/10.1109/TCS.1977.1084284
http://dx.doi.org/10.1109/TCS.1977.1084284
http://dx.doi.org/10.1080/01630569808816833
http://dx.doi.org/10.1016/S0377-0427(00)00348-4
http://dx.doi.org/10.1016/S0377-0427(00)00348-4
http://dx.doi.org/10.1137/S1064827597329254
http://dx.doi.org/http://dx.doi.org/10.1016/S0377-0427(00)00361-7
http://www.sciencedirect.com/science/article/pii/S0377042700003617
http://www.sciencedirect.com/science/article/pii/S0377042700003617
http://dx.doi.org/10.1137/1008004
1. Луковський І.О., Гаврилюк І.О., Василик В.Б., Ситник Д.О.
2. Біленко В. І., Божонок К. В., Дзядик С. Ю., Стеля О. Б.
Інтегро–апроксимаційний алгоритм
Вступ
Постановка задачі
Алгоритм
Похибка алгоритму
Застосування a–методу для алгебраїчно–нелінійних рівнянь гіперболічного типу
Задача Дирихле для алгебраїчно–нелінійних рівнянь еліптичного типу на прямокутнику
Наближений розв'язок початкової задачі для алгебраїчно–нелінійних рівнянь параболічного типу на прямокутнику
Сплайн–алгоритм
Монотонна схема для рівняння конвекції–дифузії
Висновки
3. Василик В.Б., Макаров В.Л., Ситник Д.О.
Вступ
Регуляризація та явне зображення розв'язку
Вибір контуру інтегрування
Чисельний метод
4. Веселовська Г.М.
5. Грушковская В.В.
Введение
Построение модельной системы
Условия устойчивости
Оценка скорости убывания решений
Пример: оценка скорости затухания колебаний маятниковой системы с частичной диссипацией
Выводы
6. Дзюбенко Г.А.
Вступ
Допоміжні факти
Доведення Теореми ??
7. Діденко Ю.Ф., Денисенко В.І.
8. Елишевич М.А.
Постановка задачи
Полученный результат
Пример
9. Константинов А.В., Лимарченко О.С., Кинебас К.В., Паранькина О.Ю.
Введение
Объект исследования и математическая модель
Результаты вычислительных экспериментов
Выводы
10. Мазко О.Г., Кусій С.М.
Вступ
Допоміжні твердження
Лінійні системи з керованими і спостережуваними виходами
Статичний регулятор по вимірюваному виходу
Динамічний регулятор
Алгоритм побудови динамічного регулятора
Приклад. Гасіння коливань лінійного осцилятора.
Висновок
11. Працьовитий М. В., Маслова Ю. П.
Вступ
Функція Радемахера і ряди Уолша
Узагальнення функцій Радемахера
Узагальнення функцій Уолша
12. Працьовитий М.В., Чуйков А.С.
Вступ
Оператори лівостороннього та правостороннього зсуву елементів ланцюгового дробу
Інші функції, пов'язані з оператором T(x)
13. Новицький В.В., Зінчук М.О., Коломійчук О.П., Тетерятник О.В.
Вступ
Оптимальне керування лінійними неперервними майже консервативними системами
Оптимальне керування лінійними дискретними майже консервативними системами
14. Осауленко Р. Ю.
Вступ
Перетворення, які зберігають хвости Qs–зображення чисел
Група перетворень, які зберігають частоти цифр Qs–зображення числа
Приклад функції, яка зберігає частоти, але не зберігає хвости зображення Qs-ірраціональних чисел
15. Слинько В.І., Кравчук С.В.
Постановка задачі.
Основний результат.
Умови стійкості
16. Солодун А. В.
Постановка задачи
Численные результаты
17. Ситник Д.О.
Вступ
Sinc–апроксимація
Sinc-апроксимація функції за її значеннями поза інтерполяційною сіткою
18. Сосницький С.П.
Вступ
Про рівняння збуреного руху в околі стаціонарних лагранжевих трикутників
Теорема про орбітальну нестійкість лагранжевих стаціонарних рухів у задачі трьох тіл
Висновок
19. Сосницький С.П.
Вступ
Про достатні умови відсутності осцилюючих симетричних рухів
20. Чернецька Л.О.
21. Timokha A.N.
Statement
Asymptotic steady-state solutions of (??)–(??)
The reciprocating excitation type
The axisymmetric elliptic excitation type
The oblique elliptic excitation type
Conclusions
22. Shlepakov L.N.
Main relationships for a non-inflated system
Construction of enlarged systems
Defining the task mathematical programming
Case of multiple channels with same probability characteristics in the same system of channels.
23. Shidlich A.L.
Approximative characteristics
Main results
Order estimates for some functionals and their applications
Proof of Theorems ?? and ??.
24. Луковський І.О., Стороженко В.О.
25. Луковський І.О., Пустовойтов М.О.
|
| id | oai:trim.imath.kiev.ua:article-56 |
| institution | Transactions of Institute of Mathematics of NAS of Ukraine |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-08-04T01:01:42Z |
| publishDate | 2017 |
| publisher | Інститут математики НАН України |
| record_format | ojs |
| resource_txt_mv | trimimathkievua/1c/949a2df741779e2ff770e3e86bb62a1c.pdf |
| spelling | oai:trim.imath.kiev.ua:article-562018-02-13T11:57:10Z A nonuniform Sinc approximation Неравномерная Sinc—аппроксимация Нерiвномiрна Sinc—апроксимацiя Sytnik, D. O. Сытник, Д. А. Ситник, Д. О. The paper proposes an interpolatory–type approximation method based on the use of Sinc basis and arbitrary irregular grid. We obtained admissibility conditions for the nodes of irregular grid and proved an apriori error estimate of the method which depends on the relative position of irregular grid and the nodes of uniform grid associated with classical Sinc–interpolant. We further study an error of the approximation provided by a given irregular grid lying in the neighobourhood of the classical uniform grid. В работе предлагается аппроксимаций метод интерполяционного типа, основанный на использовании Sinc базиса и произвольной неравномерной сетки. Получены условия допустимости узлов, а также априорную оценку погрешности метода, которая зависит от взаиморасположения узлов неравномерной сетки и классической для Sinc методов равномерной сетки. Исследован порядок аппроксимации при условии малого отклонения заданной неравномерной сетки от классической. У роботі пропонується апроксимаційний метод інтерполяційного типу, заснований на використанні Sinc базису і довільної нерівномірної сітки. Отримано умови допустимості вузлів, а також апріорну оцінку похибки методу, яка залежить від взаємного розташування вузлів нерівномірної сітки і класичної для Sinc методів рівномірної сітки. Досліджено порядок апроксимації за умови малого відхилення заданої нерівномірної сітки від класичної. Інститут математики НАН України 2017-12-22 Article Article application/pdf https://trim.imath.kiev.ua/index.php/trim/article/view/56 Transactions of Institute of Mathematics, the NAS of Ukraine; Vol. 13 No. 3 (2016): Mathematical problems of mechanics and computational mathematics; 230-242 Сборник Трудов Института математики НАН Украины; Том 13 № 3 (2016): Математичні проблеми механіки та обчислювальної математики; 230-242 Збірник Праць Інституту математики НАН України; Том 13 № 3 (2016): Математичні проблеми механіки та обчислювальної математики; 230-242 3083-7529 1815-2910 uk https://trim.imath.kiev.ua/index.php/trim/article/view/56/51 Авторське право (c) 2016 Праці Інституту математики НАН України |
| spellingShingle | Sytnik, D. O. Сытник, Д. А. Ситник, Д. О. A nonuniform Sinc approximation |
| title | A nonuniform Sinc approximation |
| title_alt | Неравномерная Sinc—аппроксимация Нерiвномiрна Sinc—апроксимацiя |
| title_full | A nonuniform Sinc approximation |
| title_fullStr | A nonuniform Sinc approximation |
| title_full_unstemmed | A nonuniform Sinc approximation |
| title_short | A nonuniform Sinc approximation |
| title_sort | nonuniform sinc approximation |
| url | https://trim.imath.kiev.ua/index.php/trim/article/view/56 |
| work_keys_str_mv | AT sytnikdo anonuniformsincapproximation AT sytnikda anonuniformsincapproximation AT sitnikdo anonuniformsincapproximation AT sytnikdo neravnomernaâsincapproksimaciâ AT sytnikda neravnomernaâsincapproksimaciâ AT sitnikdo neravnomernaâsincapproksimaciâ AT sytnikdo nerivnomirnasincaproksimaciâ AT sytnikda nerivnomirnasincaproksimaciâ AT sitnikdo nerivnomirnasincaproksimaciâ AT sytnikdo nonuniformsincapproximation AT sytnikda nonuniformsincapproximation AT sitnikdo nonuniformsincapproximation |