Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції
Предложен метод построения разрывного интерполяционного линейного сплайна для приближения функции с возможными разрывами первого рода, область определения которых разбита на прямоугольные треугольники. Построенные разрывные сплайны включают в себя, как частный случай, классические непрерывные сплайн...
Gespeichert in:
| Datum: | 2012 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2012
|
| Schriftenreihe: | Управляющие системы и машины |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/83091 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції / О.М. Литвин, Ю.І. Першина // Управляющие системы и машины. — 2012. — № 5. — С. 27-35. — Бібліогр.: 8 назв. — укр., рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-83091 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-830912015-06-15T03:02:06Z Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції Литвин, О.М. Першина, Ю.І. Новые методы в информатике Предложен метод построения разрывного интерполяционного линейного сплайна для приближения функции с возможными разрывами первого рода, область определения которых разбита на прямоугольные треугольники. Построенные разрывные сплайны включают в себя, как частный случай, классические непрерывные сплайны первой степени на триангулированной сетке узлов. The method of construction of the explosive interpolational linear spline for the approach of a function with possible ruptures of the first sort which range of definition is broken into rectangular triangles is suggested. The constructed explosive splines include, as a special case, the classical continuous splines of the first degree on triangulation to a grid of knots. Запропоновано метод побудови розривного інтерполяційного лінійного сплайну для наближення функції з можливими розривами першого роду, область визначення яких розбито на прямокутні трикутники. Побудовані розривні сплайни включають в себе, як частинний випадок, класичні неперервні сплайни першого степеня на триангульованій сітці вузлів. 2012 Article Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції / О.М. Литвин, Ю.І. Першина // Управляющие системы и машины. — 2012. — № 5. — С. 27-35. — Бібліогр.: 8 назв. — укр., рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/83091 519.6 uk Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Новые методы в информатике Новые методы в информатике |
| spellingShingle |
Новые методы в информатике Новые методы в информатике Литвин, О.М. Першина, Ю.І. Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції Управляющие системы и машины |
| description |
Предложен метод построения разрывного интерполяционного линейного сплайна для приближения функции с возможными разрывами первого рода, область определения которых разбита на прямоугольные треугольники. Построенные разрывные сплайны включают в себя, как частный случай, классические непрерывные сплайны первой степени на триангулированной сетке узлов. |
| format |
Article |
| author |
Литвин, О.М. Першина, Ю.І. |
| author_facet |
Литвин, О.М. Першина, Ю.І. |
| author_sort |
Литвин, О.М. |
| title |
Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції |
| title_short |
Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції |
| title_full |
Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції |
| title_fullStr |
Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції |
| title_full_unstemmed |
Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції |
| title_sort |
побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2012 |
| topic_facet |
Новые методы в информатике |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/83091 |
| citation_txt |
Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій, що мають розриви на лініях триангуляції / О.М. Литвин, Ю.І. Першина // Управляющие системы и машины. — 2012. — № 5. — С. 27-35. — Бібліогр.: 8 назв. — укр., рос. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT litvinom pobudovarozrivnihlíníjnihínterpolâcíjnihsplajnívdlânabližennâfunkcíjŝomaûtʹrozrivinalíníâhtriangulâcíí AT peršinaûí pobudovarozrivnihlíníjnihínterpolâcíjnihsplajnívdlânabližennâfunkcíjŝomaûtʹrozrivinalíníâhtriangulâcíí |
| first_indexed |
2025-07-06T09:49:30Z |
| last_indexed |
2025-07-06T09:49:30Z |
| _version_ |
1836890583112613888 |
| fulltext |
УСиМ, 2012, № 5 27
УДК 519.6
О.М. Литвин, Ю.І. Першина
Побудова розривних лінійних інтерполяційних сплайнів для наближення функцій,
що мають розриви на лініях триангуляції
Предложен метод построения разрывного интерполяционного линейного сплайна для приближения функции с возможными разры-
вами первого рода, область определения которых разбита на прямоугольные треугольники. Построенные разрывные сплайны вклю-
чают в себя, как частный случай, классические непрерывные сплайны первой степени на триангулированной сетке узлов.
The method of construction of the explosive interpolational linear spline for the approach of a function with possible ruptures of the
first sort which range of definition is broken into rectangular triangles is suggested. The constructed explosive splines include, as a spe-
cial case, the classical continuous splines of the first degree on triangulation to a grid of knots.
Запропоновано метод побудови розривного інтерполяційного лінійного сплайну для наближення функції з можливими розри-
вами першого роду, область визначення яких розбито на прямокутні трикутники. Побудовані розривні сплайни включають в
себе, як частинний випадок, класичні неперервні сплайни першого степеня на триангульованій сітці вузлів.
Вступ. Задача наближення розривних функцій
є однією з найскладніших в обчислювальній
математиці. Спеціалістам в цій галузі відомі
оператори наближення неперервних та дифе-
ренційовних функцій за допомогою поліномів
та сплайнів [1, 3]. Відомі також праці з набли-
ження неперервних функцій однієї змінної ку-
сково-сталими функціями [4, 5], в яких непе-
рервні та диференційовані функції наближують-
ся сплайнами степеня нуль. Щодо наближення
розривних функцій, то авторам невідомі загальні
методи сплайн-апроксимації розривних функ-
цій за допомогою розривних сплайнів. Але роз-
в’язання такої задачі є актуальною, оскільки се-
ред багатовимірних об’єктів, які потрібно до-
сліджувати, значно більшу їх кількість описано
розривними функціями.
В роботах [6, 7] авторами розроблено метод
наближення розривних функцій однієї змінної
розривними сплайнами, що використовує ме-
тод мінімакса. Роботу [8] присвячено розробці
загального методу наближення розривної фун-
кції двох змінних за допомогою розривних ін-
терлінаційних сплайнів двох змінних, коли роз-
риви першого роду наближуваної функції та
розриви першого роду наближувальних сплай-
нів розміщено на лініях, паралельних осям ко-
ординат.
В даній статті запропоновано метод побудо-
ви розривних сплайн-інтерполянтів для набли-
ження розривних функцій двох змінних, об-
ласть визначення яких розбивається на прямо-
кутні трикутники.
Постановка задачі
Нехай задано розривну функцію двох змін-
них f (x, y) в області D. Вважатимемо, що об-
ласть D розбивається прямими x0 = 0 < x1 < x2 <
… < xm = 1, y0 = 0 < y1 < y2 < < yn = 1 на прямо-
кутні елементи, а кожний прямокутник розби-
вається діагоналлю на два прямокутні трикут-
ники, які не вкладаються один в один, а сторони
трикутників не перетинаються. Функція f (x, y)
має розриви першого роду на границях між ци-
ми прямокутними трикутниками (не обов’язково
між всіма). Метою роботи є побудова та дослі-
дження операторів розривної кусково-поліно-
міальної інтерполяції таких, що в кожному три-
кутнику є операторами поліноміальної інтерпо-
ляції функції f (x, y).
Метод побудови наближувального розрив-
ного сплайн-інтерполянта
Якщо (xi, yj) – вузол, в якому знаходиться
прямий кут прямокутного трикутника, то може
зустрітися чотири типи трикутників (рис. 1):
1 1(1)
1
1
( )( )
, ;i j j
ij i i j j
i i
x x y y
x x x y y y
x x
1 1(2)
1
1
( )( )
, ;i j j
ij i i j j
i i
x x y y
x x x y y y
x x
1(3)
1 1
1
( )( )
, ;i j j
ij i i j j
i i
x x y y
x x x y y y
x x
1 1(4)
1
1
( )( )
, i j j
ij i i j j
i i
x x y y
x x x y y y
x x
.
28 УСиМ, 2012, № 5
x
ix 1ix
1jy
jy
1ix
1jy
(1)
ij (2)
ij
(3)
ij (4)
ij
Рис. 1. Зображення можливих трикутних елементів з прямим
кутом у вузлі (xi, yj)
Вважатимемо, що на кожній із сторін заданих
трикутників функція f (x, y) може мати (а може
і не мати) розриви першого роду, причому в
вершинах трикутника функція набуває значень
(1)
1 ,
(2) (2)
1 ,
(1) (1)
2 , 1 1
(2) (2)
2 , 1 1
(1) (1)
3 1, 1
(2) (2)
3 1, 1
( 0, 0),
( 0, 0),
( 0, 0),
( 0, 0),
( 0, 0),
( 0, 0),
i j i j
i j i j
i j i j
i j i j
i j i j
i j i j
C C f x y
C C f x y
C C f x y
C C f x y
C C f x y
C C f x y
(3) (3)
1 ,
(4) (4)
1 ,
(3) (3)
2 1, 1
(4) (4)
2 1, 1
(3) (3)
3 , 1 1
(4) (4)
3 , 1 1
( 0, 0),
( 0, 0),
( 0, 0),
( 0, 0),
( 0, 0),
( 0, 0).
i j i j
i j i j
i j i j
i j i j
i j i j
i j i j
C C f x y
C C f x y
C C f x y
C C f x y
C C f x y
C C f x y
Визначення. Розривним інтерполяційним
лінійним поліноміальним сплайном в області
( ) ( {1, 2,3, 4})k
ij D k називатимемо наступ-
ну функцію:
( )
( ) ( )
1 ( ) ( )
1
3 ( , )
( , ) ( , )
3
k
ijk k
ij k k
ij
x y
S x y s x y C
A
( )
( )
2 ( ) ( )
2
( )
( ) ( )
3 ( ) ( )
3
2 ( , )
2
1 ( , )
,( , ) ,
1
k
ijk
k k
ij
k
ijk k
ijk k
ij
x y
C
A
x y
C x y
A
(1)
( ) ( )1 ( , ) , 2 ( , )k k
ij i ij jx y x x x y y y ,
1 1
1
1 1
1
( )
1
1
1
1 1
1
( )( )
,
1
( )( )
,
23 ( , ) ( )( )
,
3
( )( )
,
4
i j j
j
i i
i j j
j
i i
k
ij
i j j
j
i i
i j j
j
i i
x x y y
y y
x x
k
x x y y
y y
x x
kx y x x y y
y y
x x
k
x x y y
y y
x x
k
,
( )
1 ( , )k
i jA x y ,
1
1( )
2
1
1
( 0, 0), 1
( 0, 0), 2
( 0, 0), 3
( 0, 0), 4
i j
i jk
i j
i j
x y k
x y k
A
x y k
x y k
,
1
1( )
3
1
1
( 0, 0), 1
( 0, 0), 2
( 0, 0), 3
( 0, 0), 4
i j
i jk
i j
i j
x y k
x y k
A
x y k
x y k
.
Теорема 1. Функція ( )( , ) ( , ), ( , )k
ijS x y s x y x y
( ) ( 1, 2, 3, 4)k
ij D k задовольняє наступні
властивості:
(1) (1)
1
(1) (1)
1 2
(1) (1)
1 3
( 0, 0) ,
( 0, 0) ,
( 0, 0) ,
ij i j
ij i j
ij i j
s x y C
s x y C
s x y C
(2) (2)
1
(2) (2)
1 2
(2) (2)
1 3
( 0, 0) ,
( 0, 0) ,
( 0, 0) ,
ij i j
ij i j
ij i j
s x y C
s x y C
s x y C
(3) (3)
1( 0, 0) ,ij i js x y C
(3) (3)
1 2
(3) (3)
1 3
( 0, 0) ,
( 0, 0) ,
ij i j
ij i j
s x y C
s x y C
(4) (4)
1( 0, 0) ,ij i js x y C
(4) (4)
1 2
(4) (4)
1 3
( 0, 0) ,
( 0, 0) .
ij i j
ij i j
s x y C
s x y C
УСиМ, 2012, № 5 29
Доведення виконується безпосередньою під-
становкою відповідних значень аргументів у
визначений розривний сплайн (1).
Теорема 2. Нехай функція f (x, y) наближу-
ється оператором S (x, y) =
( )( , ),k
ijs x y (x, y) ( )k
ij
D (k = 1,2,3,4) та ( , ) ,xf x y M ( , )yf x y N .
Тоді для оцінки похибки наближення в кож-
ному трикутному елементі розбиття справед-
лива нерівність:
( , ) ( , )
2
x yM N
f x y S x y
,
1 1,x i i y j jx x y y .
Теорему 2 доведено.
Теорема 3. Якщо ( ) ( ) , 1, 4,k kC f A k
1,3 , то в кожному трикутнику ( ) ,k
ij 1, ,i m
1,j n оператор (1) точно відновлює всі ліній-
ні функції.
Доведення витікає з того, що на трьох точ-
ках можна розмістити тільки одну площину.
Зауваження. Якщо значення функції у вузлах
трикутної сітки невідомі, то для знаходження
невідомих коефіцієнтів ( ) , 1, 2,3,k
pC p k = 1, 2, 3,
4 в даній статті запропоновано використовува-
ти метод найменших квадратів, згідно з яким
всі невідомі відшукуються з умови
( ) ( )
2( ) ( )( ) ( , ) ( , , ) min .
k k
ij ij
k k
ij C
D
J C f x y s x y C dxdy
Тоді отримуємо апроксимаційний розривний
лінійний сплайн.
Приклад 1. Нехай задані вузли трикутної
сітки x1 = 0, x2 = 0,5, x3 = 1, y1 = 0, y2 = 0,5,
y3 = 1 та функцію f (x, y) визначено в області
T = T1 T2 T3 T4, показаній на рис. 2.
х
у
12
3 4
1
1
0,5
0,5
Рис. 2. Область визначення наближуваної функції f (x, y)
T1 = {x – 0,5 >0, y – 0,5 >0, 1,5 – x – y > 0},
T2 = {–(x – 0,5) >0, y – 0,5 >0, 0,5 + x – y > 0},
T3 = {–(x – 0,5) >0, –(y – 0,5) >0, –0,5 + x +y > 0},
T4 = {x – 0,5 >0, –(y – 0,5) >0, 0,5 – x +y > 0},
Задамо функцію f (x, y) з розривами першого
роду у вузлах заданої трикутної сітки (рис. 3).
f1 SS1 f2 SS2
f3 SS3 f4 SS4
Рис. 3. Графічний вигляд наближуваної функції f(x, y) в кож-
ному з визначених трикутників
1
2
3
4
, ( , )
, ( , )
( , )
, ( , )
, ( , )
x y x y
x y x y
f x y
y x x y
x y x y
.
Функція f (x, y) має розриви першого роду у
вузлах заданої трикутної сітки та в них має та-
кі значення:
(0,5; 0,5) 1,f (0,5; 0,5) 0,f
(0,5; 0,5) 0, (0,5; 0,5) 1,f f
(1; 0,5) 1,5,f (1; 0,5) 1,5,f
(0,5; 1) 1,5,f (0,5; 1) 0,5f
(0; 0,5) 0,5,f (0; 0,5) 0,5,f
(0,5; 0) 0,5,f (0,5; 0) 0,5f .
Розривний сплайн-інтерполянт побудуємо у
вигляді
1 1
2 2
3 3
4 4
( , , ), ( , )
( , , ), ( , )
( , )
( , , ), ( , )
( , , ), ( , )
S f x y C x y
S f x y C x y
S x y
S f x y C x y
S f x y C x y
, (2)
30 УСиМ, 2012, № 5
де
(1)
1 1
(1) (1)
2 3
( , , ) 2 (1,5 )
2 ( 0,5) 2 ( 0,5),
S x y C C x y
C y C x
(2)
2 1
(2) (2)
2 3
( , ) 2 (0,5 )
2 ( 0,5) 2 ( 0,5),
S f x y C x y
C y C x
(3)
3 1
(3) (3)
2 .
( , ) 2 ( 0,5)
2 ( 0,5) 2 ( 0,5),
S f x y C x y
C y C x
(4)
4 1
(4) (4)
2 3
( , , ) 2 (0,5 – )
2 ( 0,5) 2 ( 0,5),
S f x y C C x y
C y C x
де C – матриця невідомих коефіцієнтів
(1) (1) (1)
1 2 3
(2) (2) (2)
1 2 3
(3) (3) (3)
1 2 3
(4) (4) (4)
1 2 3
C C C
C C C
C
C C C
C C C
.
Далі за методом найменших квадратів роз-
глянемо вираз
1
2
2
( ) ( ( , ) ( , , ))
( ( , ) 1( , , ))
D
F C f x y S x y C dxdy
f x y S x y C dxdy
2 3
4
2
2 2
( ( , ) 2( , , )) ( ( , )
3( , , )) ( ( , ) 4( , , )) .
f x y S x y C dxdy f x y
S x y C dxdy f x y S x y C dxdy
Треба знайти такі елементи матриці C , щоб
вираз F(C) набував мінімального значення, тоб-
то треба розв’язати мінімізаційну задачу
2( ) ( ( , ) ( , , )) min
D
F C f x y S x y C dxdy .
Цю задачу розв’язано в системі комп’ютер-
ної математики MathCad та отримано наступну
матрицю коефіцієнтів
1 1,5 1,5
0 0,5 0,5
0 0,5 0,5
0 1 1
C
.
Після підстановки значень невідомих кое-
фіцієнтів у вираз (2), отримаємо наближувану
функцію f (x, y). Тобто побудований розривний
інтерполяційний сплайн збігається з апрокси-
маційним та точно відновлює задану розривну
функцію, що і підтверджує викладену теорію.
Приклад 2. Нехай на області, визначеній у
прикладі 1 задано функцію f (x, y) з розривами
першого роду у вузлах заданої сітки:
2 2
1
2 2
2
2 2
3
2 2
4
, ( , )
, ( , )
( , )
, ( , )
, ( , )
x y x y
x y x y
f x y
x y x y
x y x y
.
В кожному розглянутому трикутному еле-
менті побудуємо інтерлінаційний сплайн S(x,y,C)
у вигляді, поданому в прикладі 1; як коефіцієн-
ти матриці C візьмемо значення функції (ліво-
сторонні та правосторонні) у вузлах сітки. От-
римаємо наступний інтерполяційний сплайн:
1
2
3
4
1,5 1,5 –1,0 ( , )
0,5 1,5 0,5, ( , )
( , )
0,5 0,5 , ( , )
1,5 0,5 0,5, ( , )
x y x y
x y x y
S x y
x y x y
x y x y
.
Максимальне відхилення наближуваної фу-
нкції f (x, y) від побудованого інтерполяційного
сплайну S(x,y) має вигляд
max ( , ) ( , ) 0,12f x y S x y .
Тепер побудуємо апроксимаційний сплайн у
вигляді формули (1). Коефіцієнти матриці C зна-
ходимо, застосовуючи метод найменших квад-
ратів, тобто розв’язуємо мінімізаційну задачу
2( ) ( ( , ) ( , , )) min
D
F C f x y S x y C dxdy .
Отримано наступні результати (рис. 4).
Далі визначимо максимальне відхилення на-
ближуваної функції f (x, y) від побудованого ап-
роксимаційного сплайну S (x, y):
max ( , ) ( , ) 0,088f x y S x y .
Приклад 3. Нехай функцію f (x, y) визначено
в області T = T1 T2 T3 T4 T5 T6, по-
казаній на рис. 5.
T1 = {x, y > 0, 1 – x – y > 0},
T2 = {x < 0, y < 1, x + y > 0},
T3 = {x < 0, y > 0, – x – y > 0},
T4 = {x < 0, y < 0, 1 + x + y > 0},
T5 = {x > 0, y > –1, – x – y > 0},
T6 = {x > 0, y < 0, x + y > 0},
УСиМ, 2012, № 5 31
f1 SS1 f3 SS3
f2 SS2 f4 SS4
Рис. 4. Графічний вигляд наближуваої функції f(x, y) (світлий
колір) та наближувального сплайну S(x, y) (темний ко-
лір) в кожному з визначених трикутників у прикладі 2
Задамо функцію f (x, y) з розривами першого
роду у вузлах заданої сітки
2 2
1
2 2
2
2 2
3
2 2
4
2 2
5
2 2
6
1, ( , )
2, ( , )
3, ( , )
( , )
4, ( , )
5, ( , )
6, ( , )
x y x y
x y x y
y x x y
f x y
x y x y
x y x y
x y x y
1
2
3
4
5
6
Рис. 5. Область визначення наближуваної функції f(x, y)
В кожному трикутнику побудуємо сплайн ви-
гляду (1) та представимо функцію і сплайн на
рис. 6.
Далі визначимо максимальне відхилення на-
ближуваної функції f (x, y) від побудованого
сплайну S (x, y):
max ( , ) ( , ) 0, 29f x y S x y .
Висновки. Отже, реалізовано запропонова-
ний метод побудови розривного інтерполяцій-
ного лінійного сплайну для наближення функ-
ції з можливими розривами першого роду, об-
ласть визначення яких розбито на прямокутні
трикутники. Побудовані розривні сплайни вклю-
чають в себе, як окремий випадок, класичні
неперервні сплайни першого степеня на триан-
гульованій сітці вузлів.
f2 SS2 f1 SS1
f3 SS3 f4 SS4
f5 SS5 f6 SS6
Рис. 6. Графічний вигляд наближуваної функції f(x, y) (світлий
колір) та наближувалього сплайну S(x, y) (темний ко-
лір) в кожному з визначених трикутників у прикладі 3
Методи наближення розривних функцій, об-
ласть визначення яких розбивається на трику-
тні елементи з криволінійною границею, є пред-
метом подальших розробок.
1. Корнейчук Н.П. Сплайны в теории приближения. –
М.: Наука, 1984. – 352 с.
2. Стечкин С.Б., Субботин Ю.Н. Сплайны в вычис-
лительной математике. – Там же, 1976. – 215 с.
3. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. Ме-
тоды сплайн-функций. – Там же. – 375 с.
4. De Vore R.A. A method of grid optimization for finite
element methods // Computer method in appl. Me-
chanics and engineering. – 1983. – 41. – P. 29–45.
32 УСиМ, 2012, № 5
5. Литвин О.М. Інтерлінація функцій та деякі її за-
стосування. – Харків: Основа, 2002. – 544 с.
6. Литвин О.М., Першина Ю.І. Наближення розрив-
ної функції однієї змінної, використовуючи метод
мінімакса // Обчислювальні методи і системи пере-
творення інформації: Пр. наук.-техн. конф. (7–8 жовт.
2010 р.). – Львів, 2010. – С. 52–55.
7. Литвин О.М., Першина Ю.І. Наближення розрив-
ної функції за допомогою розривних сплайнів // Ма-
тематичне та комп’ютерне моделювання. Серія: Фі-
зико-математичні науки: Зб. наук. пр. – Кам’янець-
Подільський: Нац. ун-т ім. Івана Огієнка, 2010. – 3. –
С. 122–131.
8. Литвин О.М., Першина Ю.І. Наближення розривних
функцій двох змінних розривними сплайнами (пря-
мокутні елементи) // «Теорія прийняття рішень»: Пр.
V міжнар. шк.-сем., 27 вер. – 1 жовт. 2010 р., Уж-
город. – 2010 – С. 141–142.
Поступила 26.02.2012
Тел. для справок: +380 57 771-0545, +380 50 222-6979
(Харьков)
E-mail: academ@kharkov.ua, yulia_pershina@mail.ru
© О.Н. Литвин, Ю.И. Першина, 2012
О.Н. Литвин, Ю.И. Першина
Построение разрывных линейных интерполяционных сплайнов для приближения функций,
имеющих разрывы на линиях триангуляции
Введение. Задача приближения разрывных функций –
одна из самых сложных задач вычислительной матема-
тики. Специалистам в этой области известны операторы
приближения непрерывных и дифференцируемых функ-
ций с помощью полиномов и сплайнов [1, 3]. Известны
также работы по приближению непрерывных функций
одной переменной кусочно-постоянными функциями [4,
5], в которых непрерывные и дифференцируемые функ-
ции приближаются сплайнами степени ноль. Что касает-
ся приближения разрывных функций, то авторам неиз-
вестны общие методы сплайн-аппроксимации разрывных
функций с помощью разрывных сплайнов. Но решение
такой задачи актуально, поскольку среди многомерных
объектов, которые нужно исследовать, значительно боль-
шее их количество описано разрывными функциями.
В работах [6, 7] авторами разработан метод прибли-
жения разрывных функций одной переменной разрыв-
ными сплайнами, использующий метод минимакса. Ра-
бота [8] посвящена разработке общего метода прибли-
жения разрывной функции двух переменных с помощью
разрывных интерлинационных сплайнов двух перемен-
ных, когда разрывы первого рода приближаемой функ-
ции и разрывы первого рода приближающих сплайнов
расположены на линиях, параллельных осям координат.
В данной статье предложен метод построения раз-
рывных сплайн-интерполянтов для приближения разрыв-
ных функций двух переменных, область определения
которых разбивается на прямоугольные треугольники.
Постановка задачи
Пусть задана разрывная функция двух переменных
f (x, y) в области D. Будем считать, что область D разби-
вается прямыми x0 = 0 < x1 < x2 < < xm = 1, y0 = 0 < y1 < y2 <
< yn = 1 на прямоугольные элементы, а каждый пря-
моугольник разбивается диагональю на два прямо-
угольных треугольника, которые не вкладываются один
в другой, а стороны треугольников не пересекаются.
Функция f (x, y) имеет разрывы первого рода на грани-
цах между прямоугольными треугольниками (не обяза-
тельно всеми). Цель работы – построение и исследова-
ние операторов разрывной кусочно-полиномиальной
интерполяции таких, которые в каждом треугольнике
есть операторами полиномиальной инетрполяции функ-
ции f (x, y).
Метод построения разрывного приближающего
сплайн-инерполянта
Если (xi, yj) – узел, в котором находится прямой угол
прямоугольного треугольника, то могут встретиться че-
тыре типа треугольников (рис. 1):
x
ix 1ix
1jy
jy
1ix
1jy
(1)
ij (2)
ij
(3)
ij (4)
ij
Рис. 1. Изображение возможных треугольных элементов с
прямым углом в узле (xi, yj)
1 1(1)
1
1
( )( )
, i j j
ij i i j j
i i
x x y y
x x x y y y
x x
;
1 1(2)
1
1
( )( )
, i j j
ij i i j j
i i
x x y y
x x x y y y
x x
;
1(3)
1 1
1
( )( )
, i j j
ij i i j j
i i
x x y y
x x x y y y
x x
;
1 1(4)
1
1
( )( )
, i j j
ij i i j j
i i
x x y y
x x x y y y
x x
.
Примем, что на каждой из сторон заданных тре-
угольников функция f (x, y) может иметь (а может и не
иметь) разрывы первого рода, причем в вершинах тре-
угольника функция имеет значения
УСиМ, 2012, № 5 33
(1)
1 ,
(1) (1)
2 , 1 1
(1) (1)
3 1, 1
( 0, 0),
( 0, 0),
( 0, 0),
i j i j
i j i j
i j i j
C C f x y
C C f x y
C C f x y
(2) (2)
1 ,
(2) (2)
2 , 1 1
(2) (2)
3 1, 1
( 0, 0),
( 0, 0),
( 0, 0),
i j i j
i j i j
i j i j
C C f x y
C C f x y
C C f x y
(3) (3)
1 ,
(3) (3)
2 1, 1
(3) (3)
3 , 1 1
( 0, 0),
( 0, 0),
( 0, 0),
i j i j
i j i j
i j i j
C C f x y
C C f x y
C C f x y
(4) (4)
1 ,
(4) (4)
2 1, 1
(4) (4)
3 , 1 1
( 0, 0),
( 0, 0),
( 0, 0).
i j i j
i j i j
i j i j
C C f x y
C C f x y
C C f x y
Определение. Будем называть разрывным интерпо-
ляционным линейным полиномиальным сплайном в об-
ласти ( ) ( {1, 2,3, 4})k
ij D k следующую функцию:
( )
( ) ( )
1 ( ) ( )
1
( ) ( )
( ) ( ) ( )
2 3( ) ( ) ( ) ( )
2 3
3 ( , )
( , ) ( , )
3
2 ( , ) 1 ( , )
, ( , ) ,
2 1
k
ijk k
ij k k
ij
k k
ij ijk k k
ijk k k k
ij ij
x y
S x y s x y C
A
x y x y
C C x y
A A
(1)
( ) ( )1 ( , ) , 2 ( , )k k
ij i ij jx y x x x y y y ,
1 1
1
1 1
1( )
1
1
1
1 1
1
( )( )
, 1
( )( )
, 2
3 ( , ) ,
( )( )
, 3
( )( )
, 4
i j j
j
i i
i j j
j
i ik
ij
i j j
j
i i
i j j
j
i i
x x y y
y y k
x x
x x y y
y y k
x x
x y
x x y y
y y k
x x
x x y y
y y k
x x
( )
1 ( , ),k
i jA x y
1
1( )
2
1
1
( 0, 0), 1
( 0, 0), 2
( 0, 0), 3
( 0, 0), 4
i j
i jk
i j
i j
x y k
x y k
A
x y k
x y k
,
1
1( )
3
1
1
( 0, 0), 1
( 0, 0), 2
( 0, 0), 3
( 0, 0), 4
i j
i jk
i j
i j
x y k
x y k
A
x y k
x y k
.
Теорема 1. Функция ( ) ( )( , ) ( , ), ( , )k k
ij ijS x y s x y x y
( 1, 2,3, 4)D k удовлетворяет следующим свойствам:
(1) (1)
1
(1) (1)
1 2
(1) (1)
1 3
( 0, 0) ,
( 0, 0) ,
( 0, 0) ,
ij i j
ij i j
ij i j
s x y C
s x y C
s x y C
(2) (2)
1
(2) (2)
1 2
(2) (2)
1 3
( 0, 0) ,
( 0, 0) ,
( 0, 0) ,
ij i j
ij i j
ij i j
s x y C
s x y C
s x y C
(3) (3)
1
(3) (3)
1 2
(3) (3)
1 3
( 0, 0) ,
( 0, 0) ,
( 0, 0) ,
ij i j
ij i j
ij i j
s x y C
s x y C
s x y C
(4) (4)
1
(4) (4)
1 2
(4) (4)
1 3
( 0, 0) ,
( 0, 0) ,
( 0, 0) .
ij i j
ij i j
ij i j
s x y C
s x y C
s x y C
Доказательство проводится непосредственной под-
становкой значений аргументов в определенный раз-
рывный сплайн (1).
Теорема 2. Пусть функция f (x, y) приближается опера-
тором ( )( , ) ( , ),k
ijS x y s x y ( )( , ) ( 1, 2,3, 4)k
ijx y D k и
( , ) , ( , )x yf x y M f x y N , тогда для оценки погреш-
ности приближения в каждом треугольном элементе раз-
биения справедливо неравенство:
( , ) ( , )
2
x yM N
f x y S x y
,
1 1,x i i y j jx x y y .
Теорема 2 доказана.
Теорема 3. Если ( ) ( ) , 1, 4, 1,3k kC f A k , то в
каждом прямоугольном треугольнике ( ) ,k
ij 1, ,i m 1,j n
оператор (1) точно восстанавливает все линейные функции.
Доказательство вытекает из того, что на трех точках
можно разместить только одну плоскость.
Замечание. Если значения функции в узлах треуголь-
ной сетки неизвестны, то для нахождения неизвестных ко-
эффициентов ( ) , 1, 2,3, 1, 2,3, 4k
pC p k в данном случае
предлагается использовать метод наименьших квадратов,
согласно которому все неизвестные находятся из условия
( ) ( )
2( ) ( )( ) ( , ) ( , , ) min
k k
ij ij
k k
ij C
D
J C f x y s x y C dxdy
.
Тогда получаем аппроксимационный разрывный ли-
нейный сплайн.
Пример 1. Пусть заданы узлы треугольной сетки:
x1 = 0, x2 = 0,5, x3 = 1, y1 = 0, y2 = 0,5, y3 = 1 и функция
f (x, y) определена в области T = T1 T2 T3 T4, пред-
ставленной на рис. 2.
х
у
12
3 4
1
1
0,5
0,5
Рис. 2. Область определения приближаемой функции f (x, y)
T1 = {x – 0,5 >0, y – 0,5 >0, 1,5 – x – y > 0},
T2 = {–(x – 0,5) >0, y – 0,5 >0, 0,5 + x – y > 0},
T3 = {–(x – 0,5) >0, –(y – 0,5) >0, –0,5 + x +y > 0},
34 УСиМ, 2012, № 5
T4 = {x – 0,5 >0, –(y – 0,5) >0, 0,5 – x +y > 0},
Зададим функцию f (x, y) с разрывами первого рода в
узлах заданной треугольной сетки (рис. 3).
1
2
3
4
, ( , )
, ( , )
( , )
, ( , )
, ( , )
x y x y
x y x y
f x y
y x x y
x y x y
.
Функция f (x, y) имеет разрывы первого рода в узлах
заданной треугольной сетки и в них имеет такие значения:
f + +(0,5; 0,5) = 1, f – +(0,5; 0,5) = 0,
f – –(0,5; 0,5) = 0, f + –(0,5; 0,5) = –1,
f – +(1; 0,5) = 1,5, f – –(1; 0,5) = –1,5,
f + –(0,5; 1) = 1,5, f – –(0,5; 1) = –0,5,
f + +(0; 0,5) = –0,5, f + –(0; 0,5) = 0,5,
f – +(0,5; 0) = –0,5, f + +(0,5; 0) = –0,5.
Разрывный сплайн-интерполянт построим в виде
1 1
2 2
3 3
4 4
( , , ), ( , )
( , , ), ( , )
( , )
( , , ), ( , )
( , , ), ( , )
S f x y C x y
S f x y C x y
S x y
S f x y C x y
S f x y C x y
, (2)
где
(1) (1) (1)
1 1 2 3( , , ) 2 (1,5 ) 2 ( 0,5) 2 ( 0,5)S x y C C x y C y C x
(2) (2) (2)
2 1 2 3( , ) 2 (0,5 ) 2 ( 0,5) 2 ( 0,5)S f x y C x y C y C x
(3) (3) (3)
3 1 2 .( , ) 2 ( 0,5) 2 ( 0,5) 2 ( 0,5)S f x y C x y C y C x
(4) (4) (4)
4 1 2 3( , , ) 2 (0,5 ) 2 ( 0,5) 2 ( 0,5)S f x y C C x y C y C x ,
где C – матрица неизвестных коэффициентов
(1) (1) (1)
1 2 3
(2) (2) (2)
1 2 3
(3) (3) (3)
1 2 3
(4) (4) (4)
1 2 3
C C C
C C C
C
C C C
C C C
.
Далее методом наименьших квадратов рассмотрим вы-
ражение
1
2
2
( ) ( ( , ) ( , , ))
( ( , ) 1( , , ))
D
F C f x y S x y C dxdy
f x y S x y C dxdy
2
3
4
2
2
2
( ( , ) 2( , , ))
( ( , ) 3( , , ))
( ( , ) 4( , , )) .
f x y S x y C dxdy
f x y S x y C dxdy
f x y S x y C dxdy
Требуется найти такие элементы матрицы C, чтобы
выражение F(C) достигало минимального значения, т.е.
решить минимизационную задачу
2( ) ( ( , ) ( , , )) min
D
F C f x y S x y C dxdy .
f1 SS1 f2 SS2
f3 SS3 f4 SS4
Рис. 3. Графический вид приближаемой функции f (x, y) в каж-
дом из выше определенных треугольников
Эта задача решена в системе компьютерной матема-
тики MathCad и была получена следующая матрица ко-
эффициентов
1 1,5 1,5
0 0,5 0,5
0 0,5 0,5
0 1 1
C
.
После подстановки значений неизвестных коэффи-
циентов в выражение (2), получаем приближаемую функ-
цию f (x, y), т.е. построенный разрывный интерполяци-
онный сплайн совпадает с аппроксимационным и точно
восстанавливает заданную разрывную функцию, что и
подтверждает изложенную теорию.
Пример 2. Пусть на области, определенной в приме-
ре 1, задана функция f (x, y) с разрывами первого рода в
узлах заданной сетки
2 2
1
2 2
2
2 2
3
2 2
4
, ( , )
, ( , )
( , )
, ( , )
, ( , )
x y x y
x y x y
f x y
x y x y
x y x y
.
В каждом рассмотренном треугольном элементе по-
строим интерполяционный сплайн S (x, y, C) в виде, пред-
ставленном в примере 2; в качестве коэффициентов мат-
рицы C берем значения функции (левосторонние и пра-
восторонние) в узлах сетки. Получим следующий ин-
терполяционный сплайн:
1
2
3
4
1,5 1,5 1,0 ( , )
0,5 1,5 0,5, ( , )
( , )
0,5 0,5 , ( , )
–1,5 0,5 0,5, ( , )
x y x y
x y x y
S x y
x y x y
x y x y
.
Максимальное отклонение приближаемой функции
f (x, y) от построенного интерполяционного сплайна S (x, y)
maxf(x, y) – S(x, y) 0,12.
УСиМ, 2012, № 5 35
Теперь построим аппроксимационный сплайн в виде
формулы (1). Коэффициенты матрицы C находим, при-
меняя метод наименьших квадратов, т.е. решаем мини-
мизационную задачу
2( ) ( ( , ) ( , , )) min
D
F C f x y S x y C dxdy .
Получены следующие результаты (рис. 4):
f1 SS1 f3 SS3
f2 SS2 f4 SS4
Рис. 4. Графический вид приближаемой функции f (x, y) (светлый
цвет) и приближающего сплайна S (x, y) (темный цвет) в
каждом из определенных треугольников в примере 2
Далее определим максимальное отклонение прибли-
жаемой функции f (x, y) от построенного приближающе-
го сплайна S (x, y)
max ( , ) ( , ) 0, 088f x y S x y .
Пример 3. Пусть функция f (x, y) определена в облас-
ти 1 2 3 4 5 6 (рис. 5).
T1 = {x, y > 0, 1 – x – y > 0}, T4 = {x < 0, y < 0, 1 + x + y > 0},
T2 = {x < 0, y < 1, x + y > 0}, T5 = {x > 0, y > –1, – x – y > 0},
T3 = {x < 0, y > 0, – x – y > 0}, T6 = {x > 0, y < 0, x + y > 0}.
Зададим функцию f (x, y) с разрывами первого рода в
узлах заданной сетки
2 2
1
2 2
2
2 2
3
2 2
4
2 2
5
2 2
6
1, ( , )
2, ( , )
3, ( , )
( , )
4, ( , )
5, ( , )
6, ( , )
x y x y
x y x y
y x x y
f x y
x y x y
x y x y
x y x y
.
В каждом треугольнике строим сплайн вида (1) и
предсталяем функцию и сплайн на рис. 6.
Далее определим максимальное отклонение приближа-
емой функции f (x, y) от построенного сплайна S (x, y):
max ( , ) ( , ) 0, 29f x y S x y .
1
2
3
4
5
6
Рис. 5. Область определения приближаемой функции f (x, y)
f1 SS1 f2 SS2
f3 SS3 f4 SS4
f5 SS5 f6 SS6
Рис. 6. Графический вид приближаемой функции f (x, y) (светлый
цвет) и приближающего сплайна S (x, y) (темный цвет) в
каждом из определенных треугольников в примере 3
Заключение. Итак, реализован предложенный метод
построения разрывного интерполяционного линейного
сплайна для приближения функции с возможными раз-
рывами первого рода, область определения которых раз-
бита на прямоугольные треугольники. Построенные раз-
рывные сплайны включают в себя, как частный случай,
классические непрерывные сплайны первой степени на
триангулированной сетке узлов.
Методы приближения разрывных функций, область
определения которых разбивается на треугольные эле-
менты с криволинейной границей станут предметом
дальнейших разработок.
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|