Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу
Algorithms for evaluating of approximants of continued fraction and its multidimensional generalization – a branched continued fraction of the general form are analyzed. The matrix algorithm is described for evaluating the value of the approximants of a branched continued C...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/295 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479666209587200 |
|---|---|
| author | Manziy, Oleksandra Hladun, Volodymyr Seredynskyi, Viktor |
| author_facet | Manziy, Oleksandra Hladun, Volodymyr Seredynskyi, Viktor |
| author_institution_txt_mv | [
{
"author": "Oleksandra Manziy",
"institution": "к. ф.-м. н., доцент , Національний університет «Львівська політехніка», вул. С.Бандери, 12, 79013, Львів"
},
{
"author": "Volodymyr Hladun",
"institution": "к. ф.-м. н., доцент, НУ «Львівська політехніка»"
},
{
"author": "Viktor Seredynskyi",
"institution": "магістр ОНП, НУ «Львівська політехніка»"
}
] |
| author_sort | Manziy, Oleksandra |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | Algorithms for evaluating of approximants of continued fraction and its multidimensional generalization – a branched continued fraction of the general form are analyzed. The matrix algorithm is described for evaluating the value of the approximants of a branched continued C-fraction with two branches. The formulas for determining the position of the nonzero elements of the sparse matrix for the representation of the numerators and denominators of the approximants of the branched continued C-fraction with two branches have been established. |
| first_indexed | 2026-06-09T01:09:54Z |
| format | Article |
| fulltext |
7
doi.org/10.15407/fmmit2023.37.007
Алгоритм континуант обчислення підхідних дробів
гіллястого ланцюгового дробу
Олександра Манзій1, Володимир Гладун2, Віктор Серединський3
1 к. ф.-м. н., доцент , Національний університет «Львівська політехніка», вул. С.Бандери, 12, 79013, Львів, e-
mail: oleksandra.s.manzii@lpnu.ua
2 к. ф.-м. н., доцент, НУ «Львівська політехніка», e-mail: volodymyr.r.hladun@lpnu.ua
3 магістр ОНП, НУ «Львівська політехніка», e-mail: viktor.seredynskyi.mnpmm.2021@lpnu.ua
У роботі проаналізовано алгоритми обчислення значення підхідних дробів неперервного
дробу та його багатовимірного узагальнення – гіллястого ланцюгового дробу загального
вигляду. Описано алгоритм континуант обчислення значення підхідних дробів гіллястого
ланцюгового С-дробу з двома гілками розгалуження. Встановлено формули для визначення
позиції ненульових елементів розрідженої матриці для зображення чисельників та
знаменників підхідних дробів гіллястого ланцюгового С-дробу з двома гілками
розгалуження.
Ключові слова: неперервний дріб, гілляcтий ланцюговий дріб, підхідний
дріб, алгоритм обчислення підхідного дробу, рекурентна формула,
матриця, визначник, LU-розклад.
Вступ. Неперервні дроби та їх багатовимірні узагальнення – гіллясті ланцюгові
дроби (ГЛД) знайшли своє широке застосування у багатьох областях [2, 4, 6, 8,
9]. В практичних задачах важливим є ефективність алгоритмів обчислення
значень підхідних дробів неперервних та гіллястих ланцюгових дробів. І якщо
список методів та алгоритмів обчислення підхідних дробів для неперервних
дробів є доволі об’ємним [1, 4, 5, 7, 8], то аналогічних методів обчислення
значень підхідних дробів для ГЛД є незначна кількість [2]. Це пов’язано в першу
чергу із тим, що не всі результати аналітичної теорії неперервних дробів можна
узагальнити для їх багатовимірного аналогу – ГЛД.
В статті запропоновано для обчислення значення підхідного дробу ГЛД
використовувати матричне зображення чисельника та знаменника підхідного
дробу, а також застосовувати методику LU-розкладності для обчислення
визначників відповідних матриць. Експериментальні обчислення підтвердили
висунуті гіпотези щодо ефективності запропонованого алгоритму.
1. Алгоритми обчислення підхідних дробів неперервного дробу.
Розглянемо основні алгоритми обчислення значення підхідного дробу
1
0
1
n
n
n
aa
f b
b b
неперервного дробу 1
0
1
n
n
aa
b
b b
УДК 517. 524
mailto:oleksandra.s.manzii@lpnu.ua
mailto:volodymyr.r.hladun@lpnu.ua
mailto:viktor.seredynskyi.mnpmm.2021@lpnu.ua
Олександра Манзій, Володимир Гладун, Віктор Серединський
Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу
8
Обернений рекурентний алгоритм (BR-алгоритм) [4, 6, 8] обчислення значення
nf використовує поняття залишків
n
kQ , які обчислюються «знизу – вверх» за
рекурентними формулами
1
1
n k
k k n
k
a
Q b
Q
, 1, 2, ,0k n n ,
n
n nQ b . Тоді
0
n
nf Q . При обчисленні залишків
n
kQ не виникає проблем з переповненням
розрядної сітки ЕОМ. Також BR-алгоритм стійкий до накопичення похибок, які
виникають в процесі обчислення підхідного дробу [7]. Вагомим недоліком цього
алгоритму є неможливість обчислення значення
1nf
на основі результатів
обчислення значення попереднього підхідного дробу
nf .
Згідно з прямим рекурентним алгоритмом (FR-алгоритм) [4, 6, 8] підхідний
дріб можна зобразити у вигляді
n n nf A B , де
nA ,
nB – відповідно чисельник
та знаменник n –го підхідного дробу, що обчислюються за рекурентними
формулами
1 2n n n n nA b A a A ,
1 2n n n n nB b A a A , 1,2,n , при
початкових умовах
0 0A b ,
1 1A ,
0 1B ,
1 0B . Вагомою перевагою BR-
алгоритму є ефективність обчислення послідовності підхідних дробів
неперервного дробу з метою досягнення заданої точності наближення. Однак
FR–алгоритму властиві проблеми, яких немає BR–алгоритм: послідовність nf
може збігатись, але при цьому послідовності nA та nB можуть одночасно
прямувати до нескінченості або до нуля, що може призвести до переповнення
розрядної сітки ЕОМ чи втрати порядку. Також при обчислені чисельників та
знаменників дробу при послідовному застосуванні тричленних рекурентних
співвідношень можливе накопичення похибок [5, 7].
Розглянемо також алгоритми обчислення підхідних дробів неперервного
дробу, які близькі до FR-алгоритму.
Матричний алгоритм обчислення підхідного дробу як і FR-алгоритм
використовує тричленні рекурентні співвідношення у матричному вигляді
1 1 2
1 1 2
1
0
n n n n n
n n n n n
A A A A a
B B B B b
.
Тоді
11 20
11 2
11 11
00 01 0
n n n
n n n
A b bb bb
B a aa a
.
Алгоритм континуант використовує співвідношення
0 1
n n nf , де
k
n ,
0,1k , – континуанти, які є визначниками тридіаональних матриць [2] і
дорівнюють многочленам, які залежать від коефіцієнтів дробу і зображають
чисельник та знаменник підхідного дробу:
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 7-11
9
0 1
1 2
0 2
1
0 0 0
1 0 0
0 1 0 0
0 0 0
0 0 0 1
n
n n
n
b a
b a
b
b a
b
,
1 2
2 3
1 3
1
0 0 0
1 0 0
0 1 0 0
0 0 0
0 0 0 1
n
n n
n
b a
b a
b
b a
b
.
2. Обчислення підхідного дробу ГЛД з двома гілками розгалуження.
Розглянемо загальний гіллястий ланцюговий С-дріб з двома гілками
розгалуження на кожному поверсі вигляду [2, 3]:
2
( ) 0 1
1
00 01 10 111
1 D : 1
1
1 1
1 1 1 1
k
i k
k
i
c c c
c c c c
, (1)
де мультиіндекс
1 2( ) ... ki k i i i , 0,1ji , 1,...,j k , а ( )i kc – коефіцієнти дробу.
Підхідним дробом ГЛД (1) називають скінчений ГЛД з n поверхами:
2
( )
1
1
1
1
k
n
i k
n
k
i
c
f D
. (2)
В процесі згортання при обчисленні підхідного дробу отримуємо
n n nf А B ,
де
nА – чисельник, а
nB – знаменник підхідного дробу (2).
Згідно з матричним зображенням чисельника та знаменника підхідних
дробів ГЛД (1) [2], значення підхідного дробу є відношенням визначників
відповідних матриць:
1m m
n A Bf
, (3)
де 2nm ,
k
C – визначник k-го порядку квадратної матриці C , ,C A B .
Враховуючи індексацію коефіцієнтів дробу ( )i kc , запишемо вигляд матриці A :
1
( ) 1 2
( )
1,
, 2 , 2
1,
0,
k k
i k
ij
i k
для i j
a для всіх i p j p
A a
симетричнодо a відносно головної діагоналі
у інших випадках
(4)
де
1 2( ) ... ki k i i i , 0,1ji , 1,...,j k , 1,...,k n ,
1p ,
2p – натуральні числа,
двійкове зображення яких дорівнює мультиіндексам ( 1)i k , ( )i k відповідно.
Олександра Манзій, Володимир Гладун, Віктор Серединський
Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу
10
Матрицю B отримуємо із матриці A шляхом викреслювання першого
рядка та першого стовпця. Таким чином
1m
B
дорівнює головному мінору
першого порядку матриці A m-го порядку.
Враховуючи вигляд коефіцієнтів ГЛД (1) очевидними є наступні
твердження:
1. Матриці A та B є невиродженими матрицями.
2. Усі діагональні елементи матриці A та B дорівнюють одиниці.
При обчисленні визначників
m
А і
1m
B
автори статті пропонують
застосувати принцип LU-розкладності матриць. Враховуючи наведені вище
твердження для матриць A та B буде існувати єдиний розклад на добуток двох
матриць LU, одна із яких L – нижня унітрикутна матриця, а інша U – верхня
трикутна, причому всі її діагональні елементи теж будуть рівні одиниці.
Нехай
m
АA L U і
1m
BB L U
. Неважко показати, що
( )
1
m
m m A
А А i
i
U d
, (5)
де
( )A
id – діагональні елементи матриці
m
АU .
1
1 1 ( )
1
m
m m B
B B i
i
U d
, (6)
де
( )B
id - діагональні елементи матриці
1m
BU
.
Згідно наведеного вище обґрунтування можна сформулювати основні
кроки алгоритму обчислення значення підхідного дробу ГЛД (1).
1. Згідно з (4) будуємо матрицю A .
2. Будуємо матрицю B , яка є під-матрицею матриці A , утвореною
викресленням першого рядка та стовпця матриці A .
3. Застосовуємо алгоритм Гауса для знаходження діагональних елементів
матриці
AU .
4. Застосовуємо алгоритм Гауса для знаходження діагональних елементів
матриці
BU .
5. Згідно (3), (5), (6)
1
( ) ( )
1 1
m m
A B
n i i
i i
f d d
.
При застосуванні перетворень методу Гауса до матриць A та B , побудованих
для обчислення значення підхідного дробу, що містить n поверхів ГЛД (1),
отримуємо таку властивість для діагональних елементів матриць
AU та
BU :
1( ) j jA
j A Ad
, 1,...,j m ,
1( ) t tB
t B Bd
, 1,..., 1t m , 2nm .
Причому
j
A і
t
B є багатовимірним аналогом континуант, які зображають
чисельник і знаменник фігурного підхідного дробу ГЛД (1) відповідно. Таким
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 7-11
11
чином діагональні елементи матриць
AU та
BU містять значення всіх фігурних
підхідних дробів ГЛД (1) до n – го порядку включно.
Висновки. Таким чином в роботі запропоновано алгоритм обчислення значень
підхідних дробів ГЛД з двома гілками розгалуження, який є двовимірним
аналогом алгоритму континуант обчислення підхідного дробу неперервного
дробу.
Література
[1] Blanch G. Numerical evaluation of continued fractions. SIAM Rev., 6, 383–421 (1964).
https://doi.org/10.1137/1006092.
[2] Bodnar D. I. Branched Continued Fractions. Naukova Dumka, Kyiv (1986). (In Russian)
[3] Bodnar D.І., Kuchmins’ka K.Y. Development of the Theory of Branched Continued Fractions in
1996–2016. J Math Sci 231 –P. 481–494 (2018). https://doi.org/10.1007/s10958-018-3828-7.
[4] Cuyt A., Brevik Petersen V., Verdonk B., Waadeland H., Jones W.B. Handbooks of Continued
Fractions for Special Functions. Berlin–Heidelberg–New York, Springer (2008).
https://doi.org/10.1007/978-1-4020-6949-9_6.
[5] Gautschi W. Computational aspects of three-term recurrence relations. SIAM Rev., 9, 24–82
(1967). https://doi.org/10.1137/100900.
[6] Jones W.B., Thron W.J. Continued Fractions: Analytic Theory and Applications (Encyclopedia of
Mathematics and its Applications, Series Number 11), Cambridge University Press; Reissue
edition (2009).
[7] Jones W.B., Thron W.J. Numerical stability in evaluating continued fractions. Math. Comp.,
28(127):795–810 (1974). https://doi.org/10.2307/2005701.
[8] Lorentzen L., Waadeland H. Continued Fractions, Vol. 1, Convergence Theory, Atlantis
Press/World Scientific, Paris, Amsterdam (2008). https://doi.org/10.2991/978-94-91216-37-4_5.
[9] Kuchmins’ka Kh. Yo. Two-dimensional continued fractions. IAPMM NASU (2010).(In Ukrainian)
Continuants algorithm for evaluation approximants of branched
continued fraction
Oleksandra Manziy, Volodymyr Hladun, Viktor Seredynskyi
Algorithms for evaluating of approximants of continued fraction and its multidimensional
generalization – a branched continued fraction of the general form are analyzed. The matrix
algorithm is described for evaluating the value of the approximants of a branched continued C-
fraction with two branches. The formulas for determining the position of the nonzero elements of
the sparse matrix for the representation of the numerators and denominators of the approximants
of the branched continued C-fraction with two branches have been established.
Отримано 15.03.23
https://doi.org/10.1137/1006092
https://doi.org/10.1007/s10958-018-3828-7
https://doi.org/10.1007/978-1-4020-6949-9_6
https://doi.org/10.1137/100900
https://doi.org/10.2307/2005701
https://doi.org/10.2991/978-94-91216-37-4_5
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-295 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:54Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/e7/5250b8753a1eeb92e0bb49858dbd76e7.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2952025-02-21T17:31:10Z Continuants algorithm for evaluation approximants of branched continued fraction Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу Manziy, Oleksandra Hladun, Volodymyr Seredynskyi, Viktor неперервний дріб, гілляcтий ланцюговий дріб, підхідний дріб, алгоритм обчислення підхідного дробу, рекурентна формула, матриця, визначник, LU-розклад Algorithms for evaluating of approximants of continued fraction and its multidimensional generalization – a branched continued fraction of the general form are analyzed. The matrix algorithm is described for evaluating the value of the approximants of a branched continued C-fraction with two branches. The formulas for determining the position of the nonzero elements of the sparse matrix for the representation of the numerators and denominators of the approximants of the branched continued C-fraction with two branches have been established. У роботі проаналізовано алгоритми обчислення значення підхідних дробів неперервного дробу та його багатовимірного узагальнення – гіллястого ланцюгового дробу загального вигляду. Описано алгоритм континуант обчислення значення підхідних дробів гіллястого ланцюгового С-дробу з двома гілками розгалуження. Встановлено формули для визначення позиції ненульових елементів розрідженої матриці для зображення чисельників та знаменників підхідних дробів гіллястого ланцюгового С-дробу з двома гілками розгалуження. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-26 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/295 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 7-11 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 7-11 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/295/263 Авторське право (c) 2023 Олександра Манзій, Володимир Гладун, Віктор Серединський (Автор) |
| spellingShingle | неперервний дріб гілляcтий ланцюговий дріб підхідний дріб алгоритм обчислення підхідного дробу рекурентна формула матриця визначник LU-розклад Manziy, Oleksandra Hladun, Volodymyr Seredynskyi, Viktor Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу |
| title | Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу |
| title_alt | Continuants algorithm for evaluation approximants of branched continued fraction |
| title_full | Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу |
| title_fullStr | Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу |
| title_full_unstemmed | Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу |
| title_short | Алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу |
| title_sort | алгоритм континуант обчислення підхідних дробів гіллястого ланцюгового дробу |
| topic | неперервний дріб гілляcтий ланцюговий дріб підхідний дріб алгоритм обчислення підхідного дробу рекурентна формула матриця визначник LU-розклад |
| topic_facet | неперервний дріб гілляcтий ланцюговий дріб підхідний дріб алгоритм обчислення підхідного дробу рекурентна формула матриця визначник LU-розклад |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/295 |
| work_keys_str_mv | AT manziyoleksandra continuantsalgorithmforevaluationapproximantsofbranchedcontinuedfraction AT hladunvolodymyr continuantsalgorithmforevaluationapproximantsofbranchedcontinuedfraction AT seredynskyiviktor continuantsalgorithmforevaluationapproximantsofbranchedcontinuedfraction AT manziyoleksandra algoritmkontinuantobčislennâpídhídnihdrobívgíllâstogolancûgovogodrobu AT hladunvolodymyr algoritmkontinuantobčislennâpídhídnihdrobívgíllâstogolancûgovogodrobu AT seredynskyiviktor algoritmkontinuantobčislennâpídhídnihdrobívgíllâstogolancûgovogodrobu |