Решение алгебраических уравнений непрерывными дробями
Приводятся аналитические выражения, представляющие все корни произвольного алгебраического уравнения n-й степени через коэффициенты исходного уравнения. Эти формулы состоят из двух отношений бесконечных определителей Теплица, диагональными элементами которых являются коэффициенты алгебраического ура...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/58827 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение алгебраических уравнений непрерывными дробями / В.И. Шмойлов, В.Б. Коваленко // Штучний інтелект. — 2011. — № 1. — С. 260-270. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859602806753722368 |
|---|---|
| author | Шмойлов, В.И. Коваленко, В.Б. |
| author_facet | Шмойлов, В.И. Коваленко, В.Б. |
| citation_txt | Решение алгебраических уравнений непрерывными дробями / В.И. Шмойлов, В.Б. Коваленко // Штучний інтелект. — 2011. — № 1. — С. 260-270. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Приводятся аналитические выражения, представляющие все корни произвольного алгебраического уравнения n-й степени через коэффициенты исходного уравнения. Эти формулы состоят из двух отношений бесконечных определителей Теплица, диагональными элементами которых являются коэффициенты алгебраического уравнения. При вычислении отношений определителей Теплица используется модифицированный алгоритм Рутисхаузера. Для нахождения комплексных корней применяется метод суммирования непрерывных дробей.
Наводяться аналітичні вирази, які представляють всі корені довільного алгебраїчного рівняння n-го степеня через коефіцієнти початкового рівняння. Ці формули складаються з двох відношень нескінченних визначників Теплиця, діагональними елементами яких є коефіцієнти алгебраїчного рівняння. При обчислюванні відношень визначників Теплиця використовується модифікований алгоритм Рутісхаузера. Для визначення комплексних коренів застосовується метод додавання неперервних дробів.
There are given analytic expressions introducing all roots of arbitrary algebraic n-th equation using coefficients of initial equation. These formulas consist of two proportions of Toeplitz infinite determinants with algebraic equation coefficients as diagonal elements. To calculate Toeplitz determination ratio Rutishauser’s modified algorithm is used. For complex roots determination method of divergent continued fractions summability is used.
|
| first_indexed | 2025-11-28T00:46:24Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 1’2011 260
2Ш
УДК 517.524
В.И. Шмойлов, В.Б. Коваленко
Научно-исследовательский институт многопроцессорных вычислительных
систем им. акад. А.В. Каляева ЮФУ, г. Таганрог, Россия
Решение алгебраических уравнений
непрерывными дробями
Приводятся аналитические выражения, представляющие все корни произвольного алгебраического
уравнения n-й степени через коэффициенты исходного уравнения. Эти формулы состоят из двух отношений
бесконечных определителей Теплица, диагональными элементами которых являются коэффициенты
алгебраического уравнения. При вычислении отношений определителей Теплица используется
модифицированный алгоритм Рутисхаузера. Для нахождения комплексных корней применяется метод
суммирования непрерывных дробей.
Введение
Известный американский специалист Р. Хемминг в монографии «Численные ме-
тоды» [1] отмечал: «Задача нахождения корней многочленов возникает достаточно
часто для того, чтобы оправдать тщательное изучение и разработку специальных ме-
тодов ее решения. Различным известным методам нахождения действительных линейных
и квадратичных множителей можно посвятить целую книгу. Тот факт, что существует
так много методов, показывает, что не существует ни одного вполне удовлетворитель-
ного». В самом деле, известно более сотни алгоритмов и их модификаций, которые
применяются для нахождения нулей полиномов [2].
В [3] был описан r/φ-алгоритм, который оказался эффективным при определении
значений расходящихся непрерывных дробей и рядов [4], а также при решении беско-
нечных систем линейных алгебраических уравнений [5]. Цель работы – построение
алгоритма решения алгебраических уравнений n-й степени, базирующегося на спосо-
бе суммирования расходящихся непрерывных дробей.
Постановка задачи
Пусть имеется полином степени n:
nn
nn xxxxf
1
1
1 ...)( . (1)
Запишем следующую производящую функцию
.......1
...1
1 2
212
21
m
mn
n
xcxcxc
xxx
(2)
Коэффициенты i в (1) и (2) совпадают. Коэффициенты mc последовательнос-
ти (2) могут быть найдены из линейного рекуррентного уравнения
nmnmmm cccc ...2211 , 10 c , 11 c .
Решение алгебраических уравнений непрерывными дробями
«Штучний інтелект» 1’2011 261
2Ш
Для определения корней алгебраического уравнения
0... 1
1
1
nn
nn xxx (3)
Эйткен [6] предложил формулы:
m
m
m c
c
x 1
1 lim
, (4)
2
1
211
21
1
32
21
:lim x
x
xx
c
c
cc
cc
cc
cc
m
m
mm
mm
mm
mm
m
, (5)
3
21
321
21
1
32
21
432
321
21
543
432
321
:lim x
xx
xxx
cc
cc
cc
cc
ccc
ccc
ccc
ccc
ccc
ccc
mm
mm
mm
mm
mmm
mmm
mmm
mmm
mmm
mmm
m
, (6)
…
4212
121
21
321
32
121
221
21
11
121
132
21
...
......
...
...
...
......
...
...
:
...
......
...
...
...
......
...
...
lim
nmnmnm
nmmm
nmmm
nmnmnm
nmmm
nmmm
nmnmnm
nmmm
nmmm
nmnmnm
nmmm
nmmm
m
n
ccc
ccc
ccc
ccc
ccc
ccc
ccc
ccc
ccc
ccc
ccc
ccc
x . (7)
Здесь nxxxx ...321 .
Используя формулы Эйткена, можно непосредственно находить только действи-
тельные корни алгебраического уравнения (3). Способ нахождения старшего по моду-
лю действительного корня алгебраического уравнения (3), описываемый формулой (4),
как известно, принадлежит Д. Бернулли.
Применим предложенный в [3] r/φ-алгоритм суммирования расходящихся не-
прерывных дробей к определению комплексных корней алгебраического уравнения (3).
Решение алгебраических уравнений
при помощи r/φ-алгоритма
Запишем формулы Эйткена (4) – (7) в развернутом виде. В результате несложных
преобразований получим конструкции из отношений определителей матриц Теплица,
диагональными элементами которых являются коэффициенты исходного уравнения (3).
Шмойлов В.И., Коваленко В.Б.
«Искусственный интеллект» 1’2011 262
2Ш
Формулу (4) можно представить отношением определителей:
.
...
100
10
1
....
1000
100
10
1
:
...
10
1
....
100
10
1
1
21
1
21
321
1
21
321
1
21
321
4321
1
x
(8)
Последующие корни уравнения (3) запишутся следующим образом:
,
......
...10
...1
...
.......
...100
...10
...1
...
:
......
...1
...
...
.......
...10
...1
...
...
1
21
321
1
21
321
4321
21
321
432
21
321
4321
5432
2
x (9)
,
.......
...10
...1
...
...
........
...100
...10
...1
...
...
:
.......
...1
...
...
...
........
...10
...1
...
...
...
21
321
4321
5432
21
321
4321
54321
65432
321
4321
5432
6543
321
4221
54321
65432
76543
3
x
(10)
……………………………………………………………....
1 2 3 -1 1 2
-1 1 2 -2 -1 1
-2 -1 1 -3
-3 -2 -1
1 2
-1 1
-2 -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
i
i i i
i i i
i i i
x
-2 -1
-4 -3 -2 -1
-1 1
-2 -1
-3 -2 -1
- - ...
- - - - ...
. . . . ...
;
- - - ...
- - - ...
- - - ...
. . . ...
i i
i i i i
i i i
i i i
i i i
(11)
Решение алгебраических уравнений непрерывными дробями
«Штучний інтелект» 1’2011 263
2Ш
Отношения определителей (8) – (11), выражающие корни алгебраического урав-
нения (3) через его коэффициенты, будем называть функциями )(n
iX . Для функций )(n
iX
введём обозначение
)(n
iX = )....,,( 21 niX
Известно, что попытки найти решения алгебраических уравнений степеней вы-
ше четвёртой в радикалах стимулировалось тем обстоятельством, что для уравнений
2, 3 и 4 степени решения в радикалах были найдены. Метод аналогии при решении
уравнений в радикалах не сработал. И здесь уместно подчеркнуть, что для алгебраи-
ческих уравнений степени выше четвёртой функции )(n
iX записываются аналогично
их записи для алгебраических уравнений степени 2, 3 и 4. Например, для уравнения
пятой степени функции )5(
iX имеют вид:
,
.....
10000
1000
100
10
1
......
100000
10000
1000
100
10
1
:
.....
1000
100
10
1
......
10000
1000
100
10
1
0
,,,,
1
21
321
4321
1
21
321
4321
54321
1
21
321
4321
54321
1
21
321
4321
54321
54321
543211
X
(12)
,
.....
1000
100
10
1
......
10000
1000
100
10
1
0
:
.....
100
10
1
0
......
1000
100
10
1
0
00
,,,,
1
21
321
4321
54321
1
21
321
4321
54321
54321
21
321
4321
54321
5432
21
321
4321
54321
54321
5432
543212
X
(13)
Аналогично записываются функции )5(
3X , )5(
4X и )5(
5X .
Несложно по формулам (8) – (11) записать аналитические выражения для пред-
ставления корней алгебраических уравнений шестой, седьмой и, вообще, произволь-
ной степени n через коэффициенты исходного уравнения [7].
Очевидно, для комплексных корней уравнения (3), определяемых также форму-
лами (8) – (11), непосредственное их вычисление значений невозможно. В этом слу-
чае необходимо дополнительно использовать r/φ-алгоритм. Модуль и аргумент искомого
комплексного числа определяются здесь формулами:
p
p
m
n
im
p
i Xr
1
)(lim , (14)
Шмойлов В.И., Коваленко В.Б.
«Искусственный интеллект» 1’2011 264
2Ш
p
k p
p
i
lim , (15)
где )( n
imX – m-я подходящая дробь выражений (8) – (11), pk – число отрицательных под-
ходящих дробей из p подходящих дробей )(n
ip
X .
Например, подходящие дроби )(
2
n
m
X определяются следующим образом:
....,
1
10
1
:
1
,
1
:,
1
:
1
1
21
1
21
321
21
32
21
321
442
)(
23
1
1
21
2
21
32
)(
22
12)(
21
nnn XXX
В табл. 1 – 5 приведены результаты вычисления корней уравнения
012345 xxxxx (16)
при помощи функций )(n
iX .
Предел отношения определителей, входящих в формулу (17), совпадает, очевид-
но, со значением старшего по модулю корня уравнения (16):
.454859659482366,1
.....
11000
11100
11110
11111
11111
......
110000
111000
111100
111110
111111
011111
1
x (17)
Таблица 1 – Нахождение нулей полинома x5-x4-x3-x2-x-1=0
x1=1,965948236645… 1
Номер дроби,
i
Значения подходящих
дробей
Погрешность
модуля, r0–ri
15 1,965942454492 0,000005782153
16 1,965949820789 -0,000001584143
17 1,965948799757 -0,000000563111
18 1,965948280026 -0,000000043380
19 1,965948121250 0,000000115395
20 1,965948172439 0,000000064207
21 1,965948271478 -0,000000034833
22 1,965948244643 -0,000000007997
23 1,965948235028 0,000000001618
24 1,965948234248 0,000000002397
25 1,965948236206 0,000000000440
26 1,965948237310 -0,000000000665
27 1,965948236718 -0,000000000073
28 1,965948236581 0,000000000064
29 1,965948236608 0,000000000037
30 1,965948236649 -0,000000000003
Решение алгебраических уравнений непрерывными дробями
«Штучний інтелект» 1’2011 265
2Ш
Данные табл. 1 показывают высокую скорость сходимости непрерывной дроби
Хессенберга(17), которой представляется единственный вещественный корень урав-
нения (16).
При вычислении определителей (17) можно использовать рекуррентное соотно-
шение
54321 nnmnnn PPPPPP
с начальными условиями 10 P , 11 P , 22 P , 43 P , 84 P .
В табл. 2 и 3 приведены результаты вычислений первой пары комплексных кор-
ней уравнения (16), с использованием r/φ-алгоритма, описываемых формулами (14) и (15).
Таблица 2 – Нахождение нулей полинома x5-x4-x3-x2-x-1=0
x2=0,871047941737…ei1,344571014601…
Номер
дроби,
i
Значения
подходящих
дробей
Значение
модуля,
ri
Погрешность
модуля,
r0–ri
Значение
аргумента,
φi
Погрешность
аргумента,
φ0–φi
15 -5,340949820789 5,340949820789 -4,469901879051 3,141592653590 -1,797021638988
16 -0,272496418805 1,206395332874 -0,335347391137 3,141592653590 -1,797021638988
17 1,000718386641 1,133523144447 -0,262475202709 2,094395102393 -0,749824087791
18 0,600589118425 0,967090592961 -0,096042651224 1,570796326795 -0,226225312193
19 -0,633810653754 0,888721392189 -0,017673450452 1,884955592154 -0,540384577552
20 3,803725432936 1,132416586390 -0,261368644653 1,570796326795 -0,226225312193
21 -0,532683357579 1,016752405306 -0,145704463569 1,795195802051 -0,450624787450
22 0,704394902227 0,971158985921 -0,100111044183 1,570796326795 -0,226225312193
23 0,159361500265 0,794471738118 0,076576203619 1,396263401595 -0,051692386994
111 1,337912542695 0,881481533587 -0,010433591850 1,360277231451 -0,015706216850
112 -0,172523993990 0,866931967200 0,004115974537 1,378453919432 -0,033882904831
113 4,799388558207 0,882047751357 -0,010999809620 1,364530142468 -0,019959127867
114 0,232691795613 0,870372151545 0,000675790193 1,350884841044 -0,006313826442
Таблица 3 – Нахождение нулей полинома x5-x4-x3-x2-x-1=0
x3=0,871047941737…e-i1,344571014601…
Номер
дроби,
i
Значения
подходящих
дробей
Значение
модуля,
ri
Погрешность
модуля,
r0–ri
Значение
аргумента,
φi
Погрешность
аргумента,
φ0–φi
15 -0,380952380952 0,380952380952 0,490095560785 -3,141592653590 1,797021638988
16 -1,341666666667 0,714920352984 0,156127588753 -3,141592653590 1,797021638988
17 0,085636673368 0,352418233711 0,518629708027 -2,094395102393 0,749824087791
18 3,087217320025 0,606297221771 0,264750719966 -1,570796326795 0,226225312193
19 -2,159054235388 0,781629915587 0,089418026150 -1,884955592154 0,540384577552
20 0,619366691884 0,751898038419 0,119149903318 -1,570796326795 0,226225312193
21 -1,085115864528 0,792352707512 0,078695234225 -1,795195802051 0,450624787450
22 0,234690265487 0,680558734958 0,190489206779 -1,570796326795 0,226225312193
23 6,586290624847 0,875782371205 -0,004734429468 -1,396263401595 0,051692386994
111 0,563208963175 0,859347029743 0,011700911994 -1,360277231451 0,015706216850
112 -4,404014338375 0,873796326011 -0,002748384274 -1,378453919432 0,033882904831
113 0,158463117875 0,858856282764 0,012191658973 -1,364530142468 0,019959127867
114 3,267672163701 0,870409608931 0,000638332806 -1,350884841044 0,006313826442
Аналогично найдем вторую пару комплексных корней уравнения (16). В табл. 4, 5
приведены результаты вычислений второй пары комплексных корней уравнения (16).
Шмойлов В.И., Коваленко В.Б.
«Искусственный интеллект» 1’2011 266
2Ш
Таблица 4 – Нахождение нулей полинома X5-x4-x3-x2-x-1=0
x4=0,818788815767…e-i2,547185551422…
Номер
дроби,
i
Значения
подходящих
дробей
Значение
модуля,
ri
Погрешность
модуля,
r0–ri
Значение
аргумента,
φi
Погрешность
аргумента,
φ0–φi
15 -0,625000000000 0,625000000000 0,193788815767 -3,141592653590 0,594407102167
16 -1,252173913043 0,884651736929 -0,065862921162 -3,141592653590 0,594407102167
17 -2,308243727599 1,217892000014 -0,399103184246 -3,141592653590 0,594407102167
18 -0,039190897598 0,515825592710 0,302963223057 -3,141592653590 0,594407102167
19 5,947368421052 0,841138045930 -0,022349230163 -2,513274122872 -0,033911428551
20 -0,647727272727 0,805294553097 0,013494262670 -2,617993877991 0,070808326569
21 -1,026666666667 0,833724522949 -0,014935707181 -2,692793703077 0,145608151654
22 -1,758241758242 0,915228588979 -0,096439773211 -2,748893571891 0,201708020468
23 -0,136300093197 0,740690841881 0,078097973886 -2,792526803191 0,245341251768
111 -0,793851566699 0,823821565262 -0,005032749494 -2,558616697254 0,011431145831
112 -0,506765649740 0,819746988619 -0,000958172851 -2,564565431502 0,017379880079
113 -0,036008708749 0,794273382670 0,024515433097 -2,570393989301 0,023208437878
114 17,220715630403 0,819088485466 -0,000299669699 -2,544690049408 -0,002495502015
Таблица 5 – Нахождение нулей полинома x5-x4-x3-x2-x-1=0
x5=0,818788815767ei2,547185551422
Номер
дроби,
i
Значения
подходящих
дробей
Значение
модуля,
ri
Погрешность
модуля,
r0–ri
Значение
аргумента,
φi
Погрешность
аргумента,
φ0–φi
15 -0,400000000000 0,400000000000 0,418788815767 3,141592653590 -0,594407102167
16 -1,111111111111 0,666666666667 0,152122149101 3,141592653590 -0,594407102167
17 -2,571428571429 1,045515917149 -0,226727101382 3,141592653590 -0,594407102167
18 -7,000000000000 1,681792830507 -0,863004014740 3,141592653590 -0,594407102167
19 0,062500000000 0,870550563296 -0,051761747529 2,513274122872 0,033911428551
20 -0,333333333333 0,741836375590 0,076952440177 2,617993877991 -0,070808326569
21 -0,857142857143 0,757306542125 0,061482273643 2,692793703077 -0,145608151654
22 -1,750000000000 0,840896415254 -0,022107599486 2,748893571891 -0,201708020468
23 -3,555555555556 0,986998258526 -0,168209442758 2,792526803191 -0,245341251768
111 -0,850337500394 0,815103906755 0,003684909013 2,558616697254 -0,011431145831
112 -1,321059942912 0,819130068155 -0,000341252387 2,564565431502 -0,017379880079
113 -18,574035217831 0,845367070142 -0,026578254375 2,570393989301 -0,023208437878
114 0,038846972367 0,819725499605 -0,000936683837 2,544690049408 0,002495502015
На рис. 1 приведены графики распределения значений функции )5(
imX , которые
представляют корни алгебраического уравнения (16).
Из графика 1а) видно, что 1x – вещественный корень. Графики также показывают,
что имеются две пары комплексно-сопряжённых корней. Знак аргумента определяется
по динамике распределения подходящих. Из графиков рис. 1б) и 1в) можно заклю-
чить, что аргумент первой пары комплексных корней менее π/2. Из графиков рис. 1г)
и 1д) видно, что аргумент второй пары лежит в интервале π/2<φ<π, причём, φ ближе
к π, чем к π/2. Отчётливо просматривается регулярность графиков, представляющих
две пары комплексно-сопряжённых корней.
Вышеприведенные значения подходящих функций )(n
imX , задаваемые отноше-
ниями определителей Теплица n-го и (n-1)-го порядков, находились при помощи
стандартных программ для вычисления определителей общего вида. Такой подход
показывает возможность решения задачи «в принципе», но не позволяет установить
значения большого количества значений функции )(n
imX , или отсчетов, что ограничи-
вает точность при нахождении комплексных корней полиномов. Между тем, для
определения значения функции )(n
imX , записываемых отношениями определителей Теп-
Решение алгебраических уравнений непрерывными дробями
«Штучний інтелект» 1’2011 267
2Ш
лица, то есть определителей не общего, а весьма специального вида, может быть эф-
фективно использован после незначительной модификации, известный рекуррентный
алгоритм частных и разностей, или QD-алгоритм Рутисхаузера [8].
Рисунок 1 – Распределение значений функции )5(
imX ,
представляющих корни уравнения (16)
QD-алгоритм, определяемый формулами (18) и (19), удобно представлять следующей
схемой (рис. 2):
x1
(0) x 1
(1) x1
(2) x1
(3) x1
(4) x1
(5) x1
(6)
e1
(0) e1
(1) e1
(2) e1
(3) e1
(4) e1
(5)
x2
(0) x2
(1) x2
(2) x2
(3) x2
(4)
e2
(0) e2
(1) e2
(2) e2
(3)
x3
(0) x3
(1) x3
(2)
e3
(0) e3
(1)
x4
(0)
Рисунок 2 – Граф QD-алгоритма Рутисхаузера
в
Шмойлов В.И., Коваленко В.Б.
«Искусственный интеллект» 1’2011 268
2Ш
Так называемая упрощённая форма QD-алгоритма описывается формулами:
)()1()1(
1
)( m
n
m
n
m
n
m
n xxee
, (18)
)(
)1(
)1()(
1 m
n
m
nm
n
m
n
e
e
xx
. (19)
Полагаем, что 00 me . Элементы первой строки )(
1
mx составляют последовательные
подходящие дроби Хессенберга (8). Значение непрерывной дроби Хессенберга (8) удоб-
но вычислять при помощи нелинейной рекуррентной формулы
1
11
1
1
1
1
2
1
3
1
1
2
11
mnmnm
n
mmm
m
xxxxxx
x
.
В табл. 6 и 7 приведены результаты вычисления комплексных корней уравнения
0161cos1161cos1681cos14 234 xxxx (20)
с использованием алгоритма Рутисхаузера и r/φ-алгоритма. Уравнение (20) имеет кор-
ни: ,21 x ,22
iеx ,23
iex 24 x .
Таблица 6 – Нахождение нулей полинома 0161cos1161cos1681cos14 234 xxxx
x2=2ei
Номер
дроби,
i
Значение
подходящих
дробей
Значение
модуля,
ri
Погрешность
модуля,
r0–ri
Значение
аргумента,
φi
Погрешность
аргумента,
φ0–φi
32 3,843317264310 1,929075885880 0,070924114122 0,951997773815 0,048002226185
64 2,005784174240 1,959056634960 0,040943365045 0,966643893412 0,033356106588
128 -0,129973382076 1,936094593410 0,063905406585 0,998490688350 0,001509311650
256 1,376378788680 1,987249193310 0,012750806689 0,990151770198 0,009848229802
512 -6,402078713170 1,993746888830 0,006253111170 0,998205852895 0,001794147105
131072 1,248565967790 1,999973613170 0,000026386826 0,999980065310 0,000019934690
262144 -28,213818211700 1,999988822720 0,000011177283 0,999995864096 0,000004135904
524288 63,797892489700 1,999994624810 0,000005375191 0,999997771433 0,000002228567
1048576 9,590801968450 1,999997471920 0,000002528083 0,999998725105 0,000001274895
2097152 3,939400713830 1,999998804140 0,000001195860 0,999999201941 0,000000798059
Таблица 7 – Нахождение нулей полинома 0161cos1161cos1681cos14 234 xxxx
x3=2e-i
Номер
дроби,
i
Значение
подходящих
дробей
Значение
модуля,
ri
Погрешность
модуля,
r0–ri
Значение
аргумента,
φi
Погрешность
аргумента,
φ0–φi
32 0,993534847417 1,974703683030 0,025296316974 -0,951997773815 -0,048002226185
64 1,937971654080 1,990412258620 0,009587741380 -0,966643893412 -0,033356106588
128 -30,582211191500 2,039391626800 -0,039391626805 -0,998490688350 -0,001509311650
256 2,926554556880 1,999874774880 0,000125225118 -0,990151770198 -0,009848229802
512 -0,625436948679 1,999744289590 0,000255710409 -0,998205852895 -0,001794147105
131072 3,203718500850 2,000000857400 -0,000000857402 -0,999980065310 -0,000019934690
262144 -0,141774945268 1,999998412280 0,000001587717 -0,999995864096 -0,000004135904
524288 0,062697880567 1,999998992680 0,000001007319 -0,999997771433 -0,000002228567
1048576 0,417065781062 1,999999336820 0,000000663184 -0,999998725105 -0,000001274895
2097152 1,015382072280 1,999999600220 0,000000399776 -0,999999201941 -0,000000798059
На рис. 4 показано распределение значений функции )4(
imX , определяющих корни
уравнения (20).
Решение алгебраических уравнений непрерывными дробями
«Штучний інтелект» 1’2011 269
2Ш
x 1 = 2
0,0
1,0
2,0
3,0
0 10 20 30 40 50
x 2 = 2e i
-8
-3
2
7
0 10 20 30 40 50 60 70 80 90 100
x 3 = 2e -i
-8
-3
2
7
0 10 20 30 40 50 60 70 80 90 100
x 4=2
0,0
0,5
1,0
1,5
2,0
2,5
0 10 20 30 40 50
Рисунок 4 – Распределение значений функции )4(
imX , определяющих корни уравнения (20)
Заключение
Следует отметить простоту и регулярность QD -алгоритма: на вычисление каж-
дой вершины графа этого алгоритма требуется выполнение всего двух арифметических
операций. Также чрезвычайно прост для программирования и /r -алгоритм, который
используется при нахождении комплексных корней алгебраического уравнения. Все
это делает предложенный в статье алгоритм нахождения всех корней алгебраическо-
го уравнения степени n весьма привлекательным для широкого его использования.
Особо хотелось бы обратить внимание на то, что формула (11) есть аналитичес-
кое выражение, представляющее корни полинома n-й степени через его коэффициенты.
Используя формулу (11), можно установить различные критерии, связанные с корня-
ми полиномов общего вида. Численные методы, разумеется, не способны к решению
подобных задач. То обстоятельство, что в формулу (11) входят определители беско-
нечного порядка, не должно вызывать дополнительных вопросов, ибо нахождение того
же корня квадратного уравнения по известным формулам также связано с бесконеч-
ной вычислительной процедурой. Формулу (11), включающую отношения определи-
телей Теплица бесконечного порядка, можно рассматривать как мнемоническую за-
пись алгоритма нахождения корней произвольного алгебраического уравнения n-го
порядка, которая разворачивается в последовательность арифметических операций.
Точно также мнемоническими записями являются формулы для решения квадратных
уравнений, формулы Кардана и Феррари для решения алгебраических уравнений тре-
тьей и четвертой степеней. Формула (11) была названа функцией )(n
iX . Произвольное
алгебраическое уравнение степени 5n не разрешимо, как известно, в радикалах, но
Шмойлов В.И., Коваленко В.Б.
«Искусственный интеллект» 1’2011 270
2Ш
оно оказалось разрешимо в функциях )(n
iX , записываемых отношениями определите-
лей Теплица бесконечного порядка. Как уже отмечалось, при вычислении комплекс-
ных корней алгебраических уравнений по формуле (11) используется /r -алгоритм,
описываемый формулами (14) и (15).
Литература
1. Хемминг Р.В. Численные методы для научных работников и инженеров / Хемминг Р.В. – М. :
Наука, 1972. – 400 с.
2. Шмойлов В.И. Алгебраические уравнения. Бесконечные системы линейных алгебраических урав-
нений. Библиографический указатель / В.И. Шмойлов, Р.И. Тучапский. – Львов : Меркатор, 2003. –
83 c.
3. Aitken A. On Bernoulli’s numerical solution of algebraic equations / A. Aitken // Proc. Roy. Soc.,
Edinburgh, Ser. A, 46 (1925/26). – Р. 289-305.
4. Рутисхаузер Г. Алгоритм частных и разностей / Рутисхаузер Г. – М. : ИИЛ, 1960. – 93 с.
5. Шмойлов В.И. Решение алгебраических уравнений непрерывными дробями / Шмойлов В.И. – Львов :
Меркатор, 2003. – 599 с.
6. Шмойлов В.И. Непрерывные дроби : [в 3 т.] / Шмойлов В.И. – Львов : Меркатор, 2004. – Т. 1.
Периодические непрерывные дроби. – 645 с.
В.І. Шмойлов, В.Б. Коваленко
Розв’язування алгебраїчних рівнянь безперервними дробами
Наводяться аналітичні вирази, які представляють всі корені довільного алгебраїчного рівняння n-го степеня
через коефіцієнти початкового рівняння. Ці формули складаються з двох відношень нескінченних
визначників Теплиця, діагональними елементами яких є коефіцієнти алгебраїчного рівняння. При
обчислюванні відношень визначників Теплиця використовується модифікований алгоритм Рутісхаузера.
Для визначення комплексних коренів застосовується метод додавання неперервних дробів.
V.I. Shmoylov, V.B. Kovalenko
Solution of Algebraic Equations by Continued Fractions
There are given analytic expressions introducing all roots of arbitrary algebraic n-th equation using coefficients
of initial equation. These formulas consist of two proportions of Toeplitz infinite determinants with algebraic
equation coefficients as diagonal elements. To calculate Toeplitz determination ratio Rutishauser’s modified
algorithm is used. For complex roots determination method of divergent continued fractions summability is
used.
Статья поступила в редакцию 04.11.2010.
|
| id | nasplib_isofts_kiev_ua-123456789-58827 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-11-28T00:46:24Z |
| publishDate | 2011 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Шмойлов, В.И. Коваленко, В.Б. 2014-03-31T11:40:33Z 2014-03-31T11:40:33Z 2011 Решение алгебраических уравнений непрерывными дробями / В.И. Шмойлов, В.Б. Коваленко // Штучний інтелект. — 2011. — № 1. — С. 260-270. — Бібліогр.: 6 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58827 517.524 Приводятся аналитические выражения, представляющие все корни произвольного алгебраического уравнения n-й степени через коэффициенты исходного уравнения. Эти формулы состоят из двух отношений бесконечных определителей Теплица, диагональными элементами которых являются коэффициенты алгебраического уравнения. При вычислении отношений определителей Теплица используется модифицированный алгоритм Рутисхаузера. Для нахождения комплексных корней применяется метод суммирования непрерывных дробей. Наводяться аналітичні вирази, які представляють всі корені довільного алгебраїчного рівняння n-го степеня через коефіцієнти початкового рівняння. Ці формули складаються з двох відношень нескінченних визначників Теплиця, діагональними елементами яких є коефіцієнти алгебраїчного рівняння. При обчислюванні відношень визначників Теплиця використовується модифікований алгоритм Рутісхаузера. Для визначення комплексних коренів застосовується метод додавання неперервних дробів. There are given analytic expressions introducing all roots of arbitrary algebraic n-th equation using coefficients of initial equation. These formulas consist of two proportions of Toeplitz infinite determinants with algebraic equation coefficients as diagonal elements. To calculate Toeplitz determination ratio Rutishauser’s modified algorithm is used. For complex roots determination method of divergent continued fractions summability is used. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Моделирование объектов и процессов Решение алгебраических уравнений непрерывными дробями Розв’язування алгебраїчних рівнянь безперервними дробами Solution of Algebraic Equations by Continued Fractions Article published earlier |
| spellingShingle | Решение алгебраических уравнений непрерывными дробями Шмойлов, В.И. Коваленко, В.Б. Моделирование объектов и процессов |
| title | Решение алгебраических уравнений непрерывными дробями |
| title_alt | Розв’язування алгебраїчних рівнянь безперервними дробами Solution of Algebraic Equations by Continued Fractions |
| title_full | Решение алгебраических уравнений непрерывными дробями |
| title_fullStr | Решение алгебраических уравнений непрерывными дробями |
| title_full_unstemmed | Решение алгебраических уравнений непрерывными дробями |
| title_short | Решение алгебраических уравнений непрерывными дробями |
| title_sort | решение алгебраических уравнений непрерывными дробями |
| topic | Моделирование объектов и процессов |
| topic_facet | Моделирование объектов и процессов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58827 |
| work_keys_str_mv | AT šmoilovvi rešeniealgebraičeskihuravneniinepreryvnymidrobâmi AT kovalenkovb rešeniealgebraičeskihuravneniinepreryvnymidrobâmi AT šmoilovvi rozvâzuvannâalgebraíčnihrívnânʹbezperervnimidrobami AT kovalenkovb rozvâzuvannâalgebraíčnihrívnânʹbezperervnimidrobami AT šmoilovvi solutionofalgebraicequationsbycontinuedfractions AT kovalenkovb solutionofalgebraicequationsbycontinuedfractions |