samsergey 26 мая в 07:58

О новом методе решения алгебраических уравнений и обобщении чисел Каталана

Средний

13 мин

4.2K

Обзор

Материалы на математические темы нечасто врываются в бурные новостные потоки. Как правило, туда попадает либо какая-либо сомнительная «сенсация» из области школьной математики (вроде нового доказательства теоремы Пифагора), либо что-то абсолютно непонятное большинству читателей из гильбертовских «задач тысячелетия» или программы Ленглендса. Что-либо нетривиальное, но вместе с тем, доступное пониманию непрофессиональному математику, редко оказывается в публичных новостях.

Пару недель назад я рад был увидеть исключение: броские заголовки объявляли, что найден универсальный способ решения алгебраических уравнений произвольной степени, неизвестный ранее, и если верить журналистам, нарушающий «запреты» Абеля и Галуа на существование решения в конечной форме для уравнений выше четвёртой степени. Человеку, знакомому с теорией Галуа и теоремой Абеля, понятно, что либо речь идёт о рождении принципиально нового подхода, либо мы имеем дело с передëргиванием и созданием сенсации из какого‑то частного случая.

Интриги добавляло то, что одним из фигурантов новостей выступил небезызвестный Норман Вайлдбергер: видеоблогер, блестящий историк математики, убеждëнный борец с иррациональными числами и концепцией бесконечности, автор своеобразной рациональной тригонометрии и оригинального подхода к теории чисел. К тому же, все новости упоминают, что в основе метода лежат комбинаторика и числа Каталана, давно и хорошо известные в разных областях математики. Вайлдбергер не похож на неземных Александра Гротендика, Григория Перельмана или Теренса Тао, он скорее относится к ряду таких звёзд, как Джон Конвей, Дональд Кнут или Стивен Вольфрам, которые не только могут применять глубокое математическое мышление к относительно простым прикладным задачам, но и не боятся увлекаться радикальными идеями и принципиально новыми подходами к давно изученным задачам, даже рискуя репутацией.

В общем, новость явно не пустая и интригующая: не понятно, как именно революционер, отвергающий иррациональные числа, одолел невозможность конечного выражения в радикалах решения алгебраических уравнений высоких степеней.

Сразу следует заметить, что построить рациональное приближение к некратным корням уравнения произвольной степени не только можно, но и очень просто, если воспользоваться итерационным методом Ньютона. Действительно, для полиномиального уравнения с рациональными коэффициентами , на каждом шаге итерации

$x \mapsto x - \frac{f(x)}{f'(x)},$

начинающейся с рационального , будут получаться рациональные числа. Итерации Ньютона обладают суперсходимостью и очень быстро дают приближённое решение уравнения, так что для создания какой-никакой сенсации нужно предложить что-то не менее простое, не менее рациональное, но при этом, новое и в чём-то превосходящее метод Ньютона.

Мне без труда удалось найти в открытом доступе статью Вайлдбергера и его коллеги Дина Рубайна “A Hyper‑Catalan Series Solution to Polynomial Equations, and the Geode” и разобраться в ней. Оказалось, что речь, действительно, идëт о рациональных приближениях, а не о конечной форме решения уравнений, и что в некотором смысле предложенный способ, действительно, проще метода Ньютона, но проще не в плане понимания или вычислительной сложности, а в форме представления решения. Если метод Ньютона даëт сложную цепную дробь, то метод Вайлдбергера-Рубайна представляет решение в виде формального степенного ряда, то есть в выражения, в котором все скобки раскрыты и все степени разложены. При этом коэффициенты ряда имеют конечную явно выраженную форму, что делает возможным дальнейший точный алгебраический анализ решения.

Теория, связывающая комбинаторные числа Каталана и алгебраические уравнения оказалась вовсе не нова: исторический обзор, данный в статье Вайлдбергера содержит четыре десятка ссылок. Отдельные фрагменты этой теории появлялись в работах Леонарда Эйлера, Кристиана Гольдбаха, Жака Бине, Эжена Каталана, Артура Кэйли и многих других не нуждающихся в представлении математиков. Более того, один из основных результатов теории был изложен в качестве упражнения в книге «Concrete mathematics» упомянутого выше Дональда Кнута. А ближе всего к описываемому методу решения алгебраических уравнений подошли Джозеф Мотт во второй половине XIX в и Гюнтер Леттль в 1990-е годы. В чëм же состоит новизна метода и откуда взялся повод для сенсации? С этим я и предлагаю разобраться.

Я начну свой обзор с примеров использования метода Вайлдбергера-Рубайна для решения некоторых алгебраических уравнений, а потом покажу какая красивая связь существует между числами Каталана, их обобщениями и рациональными приближениями решений произвольных алгебраических уравнений в виде формальных рядов.

Описание метода и примеры использования

Числа Каталана

Числами Каталана называют последовательность натуральных чисел (A000108), которые отражают количество объектов, имеющих рекурсивную природу. Ими описывается количество правильных скобочных выражений и бинарных деревьев указанной глубины вложенности, число разбиений выпуклого многоугольника на треугольники и количество монотонных путей на регулярной квадратной решётке и многие другие комбинаторные объекты. Во втором томе книги «Перечислительная комбинаторика» Ричарда Стэнли приводится 66 различных интерпретаций чисел Каталана. Иллюстрацию к некоторым примерам можно увидеть тут.

Числа Каталана обозначаются и индексируются с нуля. Вот первые десять из них: Существует явное выражение в конечной форме для произвольного члена ряда:

$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! \, n!}$

и рекуррентное соотношение,

$C_0 = 1, \quad C_n = \frac{2(2n - 1)}{n + 1} C_{n-1}$

удобное для практической работы, поскольку не требует вычисления больших промежуточных факториалов или биномиальных коэффициентов. Стоит упомянуть ещё одно рекуррентное соотношение, отражающее основной комбинаторный смысл чисел Каталана: каждое следующее число является суммой попарных произведений всех предыдущих:

$C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} \quad \text{для} \quad n \geq 0.$

Например:

$\begin{eqnarray*} C_1 &=& C_0 C_0 = 1 \cdot 1 = 1, \\ C_2 &=& C_0 C_1 + C_1 C_0 = 1 \cdot 1 + 1 \cdot 1 = 2, \\ C_3 &=& C_0 C_2 + C_1 C_1 + C_2 C_0 = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5, \\ C_4 &=& C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 = 1 \cdot 5 + 1 \cdot 2 + 2 \cdot 1 + 5 \cdot 1 = 14 \end{eqnarray*}$

Последовательность Каталана растёт достаточно быстро, используя формулу Стирлинга для аппроксимации факториалов, можно получить асимптотику:

$C_n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}.$

Числа Каталана и решение квадратного уравнения

Известно, что если квадратное уравнение особого вида:

$(1)\qquad tx^2-x+1=0$

имеет некратный вещественный корень, то он выражается в виде бесконечной суммы:

$(2)\qquad x = \sum\limits_{n \ge 0} C_n t^n = S.$

Это утверждение мы докажем позже. Ряд имеет абсолютную сходимость для , что соответствует асимптотике для чисел Каталана, а для положительных — условию положительности дискриминанта уравнения . В пределах сходимости ряда оказываются корни в интервале $(2\sqrt2-2,2)\approx (0.843,2)$ .

Алгебраическое уравнение, в котором свободный член равен а коэффициент при линейном , называется уравнением в геометрической форме.

Пример 1

Простое решаемое уравнение

Уравнение имеет два корня: $x_{1,2}= (9 \pm 3\sqrt{5})/2$ . Частичные суммы ряда дают последовательность, которая сходится к меньшему корню.

$\begin{eqnarray*} S_0 &=& 1, \\ S_1 = \frac{10}{9} &\approx& 1.1111, \\ S_2 = \frac{92}{81} &\approx& 1.1358, \\ S_3 = \frac{833}{729} &\approx& 1.1427, \\ S_4 = \frac{7511}{6561} &\approx& 1.1446\\ S_\infty = x_1 = \frac{9 - 3\sqrt{5}}{2} &\approx& 1.145898 \end{eqnarray*}$

Второй корень можно получить из теоремы Виетта.

Пример 2

Простое не решаемое уравнение

При уравнение принимает вид и имеет корни $\phi$ и $-1/\phi,$ где $\phi = (\sqrt5-1)/2 \approx 0.618034$ — золотое сечение. Приближение решения уравнения рядом даёт красивое соотношение:

$\sum_{n \ge 0} (-1)^nC_n = C_0-C_1+C_2-C_3+...= \phi,$

которое могло бы стать ещё одним интересным свойством золотого сечения, если бы этот ряд сходился. Однако достаточно вычислить несколько первых частичных сумм ряда, чтобы убедиться в том, что золотое сечение так посчитать не получится.

Решение произвольного квадратного уравнения

Квадратное уравнение с произвольными коэффициентами с помощью замены $x \to -y{c_0}/{c_1}$ можно привести к геометрической форме:

$\frac{c_0c_2}{c_1^2} y^2 - y + 1 = 0,$

в которой $t = {c_0c_2}/{c_1^2}.$ Это значит, что решение квадратного уравнения общего вида можно получить в виде суммы следующего ряда:

$(3)\qquad x = -\frac{c_0}{c_1} \sum\limits_{n \ge 0}{ C_n \left(\frac{c_0c_2}{c_1^2}\right)^n}.$

Пример 3

Использование смещения неизвестной для решения уравнения

Давайте воспользуемся этим обобщением для того, чтобы подобраться к золотому сечению. Рассмотрим смещение неизвестной $x \to x+1/2,$ которое превратит уравнение золотого сечения x^2+x-1=0 в другое уравнение: x^2+2x-1/4 = 0 . Для него ряд (3) сходится, поскольку $t = {c_0c_2}/{c_1^2} = -1/8$ , и даёт в пределе значение x = 0.118034, которое после смещения на 1/2 приводит нас к искомому корню 0.618034 .

Этот нехитрый приём, — смещение неизвестной, позволяющее попасть в область сходимости ряда, будет важен при поиске решений уравнений высоких степеней.

Переход к более высоким степеням

Обобщение чисел Каталана

Для решения алгебраических уравнений произвольной степени метод Вайлдбергера-Рубайна использует обобщение чисел Каталана, которое с точки зрения комбинаторики выглядит достаточно естественным. Если числами можно посчитать разбиения выпуклого -угольника на заданное число треугольников, то обобщёнными числами $C_{[m_2,m_3,...,m_k]}$ выражают количество разбиений выпуклого многоугольника на треугольников, выпуклых четырёхугольников и так далее. Число обозначает количество выпуклых многоугольников с вершинами. Эти числа образуют уже не ряд, а более сложное структурированное множество: мультипоследовательность, индексированную мультииндексом $\mathbf{m} = [m_2,m_3,..., m_k]$ . Авторы называют их «super‑Catalan numbers», но на русском языке буквальный перевод звучит коряво, поэтому я буду называть их обобщёнными числами Каталана. В явном виде они вычисляются так:

$C_{[m_2,m_3,...,m_k]}=\frac{(2m_2 + 3m_3 + \cdots + km_k)!}{(1 + m_2 + 2m_3 + \cdots + (k-1) m_k)! \, m_2! \, m_3! \cdots m_k! }.$

Например, количество разбиений семиугольника на 2 треугольника и один пятиугольник обозначается с помощью мультииндекса (два треугольника, ни одного четырёхугольника и один пятиугольник). Рисунок показывает все возможные такие разбиения, которых оказывается .

Разбиения семиугольника на два треугольника и один пятиугольник

Основным результатом обсуждаемой статьи является доказательство утверждения о том, что решение уравнения произвольной степени в геометрической форме

$(4)\qquad t_k x ^k + ... + t_2 x ^2 - x + 1 = 0$

выражается в виде формального ряда:

$(5)\qquad x = \sum\limits_{m_2,m_3,..m_k \ge 0} C_{[m_2,m_3,..., m_k]} t_2^{m_2}t_3^{m_3}... t_k^{m_k}$

Уравнение с произвольными коэффициентами

$(6)\qquad c_k x^k + \cdots + c_2 x^2 + c_1 x + c_0 = 0$

сводится к геометрической форме:

$\frac{c_0^{k-1}c_k }{(-c_1)^k} x^k + \cdots - \frac{c_0^2c_3}{c_1^3} x^3 + \frac{c_0c_2}{c_1^2}c_2 x^2 - x + 1 = 0$

и имеет формальное решение

$(7)\qquad x=\sum\limits_{m_2,m_3,...,m_k \ge 0}C_{[m_2,m3,..,m_k]}\frac{c_0^{1+m_2+2m_3+...+(k-1)m_k}}{(-c_1)^{1+2m_2+3m_3+...+k m_k}}c_2^{m_2}c_3^{m_3}\cdots c_k^{m_k}.$

Вопрос сходимости этого ряда авторы не рассматривают, оставляя его практическим, то есть, полагаясь на опыт конкретного вычисления. Также как при использовании метода Ньютона мы полагаемся на удачный выбор начального приближения, так и здесь, конкретные коэффициенты определяют будут ли существовать суммы или . Для двух коэффициентов некоторых уравнений третьего и пятого порядков я построил области сходимости указанных рядов, которые оказываются достаточно нетривиальными:

Решения кубических уравнений

Рассмотрим кубическое уравнение в геометрической форме:

$(8)\qquad t_3 x ^3 + t_2 x ^2 - x + 1 = 0.$

Оно имеет по крайней мере один вещественный корень, который при условии сходимости ряда может быть выражен следующим образом:

$(9)\qquad x = \sum\limits_{m_2,m_3 \ge 0} C_{[m_2,m_3]} t_2^{m_2}t_3^{m_3}$

Числа $C_{[m_2,m_3]}$ образуют бесконечную таблицу

$\begin{array}{c|rrrrrrс} m_2 \backslash m_3 & 0 & 1 & 2 & 3 & 4 & 5 & \cdots\\ \hline 0 & 1 & 1 & 3 & 12 & 55 & 273 & \\ 1 & 1 & 5 & 28 & 165 & 1001 & 6188 &\\ 2 & 2 & 21 & 180 & 1430 & 10920 & 81396 &\\ 3 & 5 & 84 & 990 & 10010 & 92820 & 813960 &\\ 4 & 14 & 330 & 5005 & 61880 & 678300 & 6864396 &\\ 5 & 42 & 1287 & 24024 & 352716 & 4476780 & 51482970 &\\ \vdots & & & & & & &\ddots \end{array}$

В качестве частичных сумм для выражения можно рассматривать суммы, включающие антидиагональные элементы таблицы, которые соответствуют однородным многочленам для и :

$\begin{eqnarray*}S_0 &=& 1\\ S_1 &=& S_0 + t_2 + t_2\\S_2 &=& S_1 + 2t_2^2+5t_2t_3+3t_3^2\\S_3 &=& S_2+5 t_2^3 + 21 t_2^2t_3 + 28 t_2t_3^2+12 t_3^3\\&\vdots&\\S_k &=& S_{k-1}+\sum\limits_{m_2+m_3=k}C_{[m_2,m_3]}t_2^{m_2}t_3^{m_3}\end{eqnarray*}$

Приближённое решение уравнения с произвольными коэффициентами c_3 x ^3 + c_2 x ^2 +c_1 x + c_0 = 0 может быть выражено частичной суммой:

$x\approx -\frac{c_0}{c_1}S_k\left(\frac{c_0 c_2}{c_1^2},\frac{c_0^2 c_3}{c_1^3}\right) = K_k[c_0,c_1,c_2,c_3]$

а точное решение выражается формальной суммой $K_\infty[c_0,c_1,c_2,c_3]$ .

Пример 4

Итерационное смещение неизвестной

Рассмотрим классическое уравнение , которое в 1685 году Джон Валлис использовал для демонстрации предложенного им метода Ньютона. Ограничимся вычислением частичной суммы третьего порядка . К сожалению, для этих коэффициентов ряд не сходится, поэтому необходимо смещение аргумента. Искомый корень близок к , назовём это начальным приближением и попробуем решить уравнение . Третья частичная сумма равна что соответствует первому приближению к корню:

Если подставить его в уравнение, то получим . Существенно уточнить это решение можно если найти решение уравнения . Вычисление третьей частичной суммы для этого уравнения даст второе приближение:

Проверка показывает, что $f(x_2) = 3\cdot 10^{-15}$ .

Такой итерационный способ позволяет достаточно быстро получать точные значения, ограничиваясь небольшим количеством членов ряда . Если начать такие же итерационные вычисления с то получим такие приближения

$\begin{array}{ll}x_0 &= -1+i, &|f(x_0)|=1\\ x_1 &= -1.0474 - 1.136i, &|f(x_1)| = 2\cdot 10^{-3}\\ x_1 &= -1.0472757407711633 - 1.135939889088928i & |f(x_2)|| = 10^{-15}\end{array}$

Подведём итог

Метод Вайлдбергера-Рубайна небезынтересен и может быть использован в аналитических исследованиях корней полиномов высоких степеней. К его достоинствам можно отнести относительную простоту и универсальность, а также то, что решение уравнений представляется в форме степенного ряда, удобной для анализа корней. В обсуждаемой статье есть целый раздел, посвящённый открытым вопросам и новым направлениям исследований, что точно является определённым прорывом в теории полиномиальных уравнений.

Однако метод имеет ряд ограничений, делающих его применение в вычислительных методах затруднительным. Вычисление обобщенных чисел Каталана по общей формуле требует использования целых чисел с неограниченной разрядностью (существование универсальных рекуррентных способов пока неочевидно). Есть и ограничения на решаемое уравнение, в частности, для уравнений степени выше второй область сходимости имеет сложное строение, кроме того, метод требует наличия ненулевого линейного члена в уравнении. Эти ограничения можно обходить смещением неизвестной и итерационным уточнением корня, однако традиционный метод Ньютона решает эти же проблемы существенно проще. Но повторю, обсуждаемый метод не численный, а аналитический, и не предлагается в качестве альтернативы методу Ньютона.

Почему это работает?

Я не буду полностью повторять доказательство метода, а обозначу лишь его путь, достаточно интересный и на удивление не сложный. Прежде чем рассматривать общий случай, вновь для начала обратим наше внимание на квадратное уравнение и выясним что связывает числа Каталана с корнями уравнения .

Вернёмся к подсчёту разбиений выпуклого многоугольника на заданное число треугольников и рассмотрим абстрактную алгебру над множеством многоугольников, в которой аддитивной операцией будет объединение множеств, а мультипликативной — операция соединения двух многоугольников, которую мы будем рассматривать как бинарную функцию $\overline{\nabla}(\cdot,\cdot)$ . Элементами алгебры являются выпуклые многоугольники с одной выделенной стороной, которую авторы назвали «крышей» (roof). Роль единицы в этой алгебре играет тривиальный «двухугольник» или отрезок, обозначаемый символом , его «крышей» является он сам.

Красным цветом выделены "крыши" многоугольников.

Рисунок показывает, как производится соединение различных многоугольников между собой: на базе единичного элемента, который станет «крышей» нового элемента, строится треугольник, в котором две стороны достраиваются «крышами» соединяемых элементов. Форма многоугольников нас не волнует, поэтому мы можем считать два многоугольника равными, если они равны, как графы. Операция соединения дистрибутивна относительно операции объединения множеств.

Поскольку любой многоугольник является либо единичным, либо является соединением двух других многоугольниеов, то всë множество многоугольников можно формально описать таким образом:

$(10)\qquad T = \{|\}\cup\nabla(T,T).$

Опытный программист без труда увидит в этом определении абстрактныт алгебраический тип, описывающий бинарные деревья или правильные непустые скобочные выражения (язык Дика):

data T = Unit | Join T T

В тоже время, читатель, знакомый с алгебраической теорией типов увидит в этом выражении уравнение , порождающее множество возможных элементов абстрактного типа:

$\begin{align*} T &= 1 + [1×1] + [1×(1×1)+(1×1)×1] + \dots\\ &= 1 + T+ 2T^2+5T^3+14T^4+...\end{align*}$

Где обозначает подмножество , в котором все элементы содержат ровно множителей. Дистрибутивность операции соединения относительно объединения множеств приводит к комбинаторному рекуррентному соотношению, которое определяет числа Каталана. Поэтому-то мы и можем утверждать, что ряд Каталана порождается решением уравнения , то есть, квадратного уравнения в геометрической форме.

Для получения более общего выражения можно построить гомоморфизм $\psi$ из алгебры многоугольников в алгебру мономов , в которых показатель соответствует числу треугольников, разбивающих многоугольник. При этом $\psi(|) = t^0 = 1$ (ни одного треугольника), $\psi(r \cup s) = \psi(r) + \psi(s)$ и $\psi(\overline{\nabla}(r,s)) = t\cdot\psi(r)\cdot \psi(s)$ . В последнем выражении умножение на отражает добавление нового треугольника, а перемножение $\psi(r)\cdot \psi(s),$ опять же, следует из дистрибутивности операции соединения относительно объединения множеств.

Гомоморфизм $\psi$ позволяет распространить себя на всё множество , отображая его на множество многочленов по , которое мы обозначим $\mathbf{T}$ . При этом формальному уравнению соответствует формальное уравнение для множества многочленов:

$\mathbf{T} = 1 + t\mathbf{T}^2.$

Это множество разбивается на классы с одинаковыми степенями , соответствующие разбиениям многоугольников на треугольников:

$\mathbf{T} = 1 + t + 2t^2+5t^3+14t^4 + … = \sum\limits_{n>0} C_n t^n.$

Для перехода к уравнениям произвольной степени, следует расширить алгебру многоугольников обобщенной операцией объединения $\overline{\nabla}_k(\cdot,\cdot,\dots,\cdot)$ произвольной арности . При этом $\overline{\nabla}_2 = \overline{\nabla}$ . Принцип действия этой операции естественным образом обобщает бинарное соединение $\overline{\nabla}$ и показан на рисунке:

Пример соединения четырёх многоугольников.

С помощью этого обобщения строится множество многоугольников , разбиваемых на указанное число многоугольников меньшего порядка.

$S = \{|\} + \overline{\nabla_2}(S,S) + \overline{\nabla_3}(S,S,S) + \dots$

На языке типов такое множество можно описать так:

data S = Unit | Join₂ S S  | Join₃ S S S | …

Он изоморфен типу, определяющему т. н. розовое дерево:

data R = Empty | Node [R]

Действительно, можно убедиться, что обобщённые числа Каталана $C_{[m_2,m_3,… ]}$ подсчитывают количество розовых деревьев с узлами 2-го порядка, узлами 3-го порядка и т.д.

Все деревьев с двумя узлами 2-го порядка и одним узлом 4-го. — Все $C_{[2,0,1]} = 28$ деревьев с двумя узлами 2-го порядка и одним узлом 4-го.

Все $C_{[2,0,1]} = 28$ деревьев с двумя узлами 2-го порядка и одним узлом 4-го.

Если числа Каталана отражали количество правильных скобочных выражений указанной вложенности, то их обобщение подсчитывает количество S-выражений (или выражений языкпа Лисп с одинаковыми символами) с известным количеством функци различной валентности. Приведённый выше пример соответствует возможным S-выражениям, составленным из двух унарных функций и одной тернарной.

Наконец, можно построить гомоморфизм из алгебры над в алгебру мономов $t_2^{m_2} t_3^{m_3}…$ и с его помощью определить алгебру формальных рядов $\mathbf{S}$ :

$(11) \qquad \mathbf{S} = 1 + t_2 \mathbf{S}^2 + t_3 \mathbf{S}^3 + t_4 \mathbf{S}^4 + \dots$

разбивая множество $\mathbf{S}$ на классы на соответствующие разбиениям многоугольников на треугольников, четырёхугольников и т.д., которые отображаются гомоморфизмом в мономы $t_2^{m_2} t_3^{m_3}…$ Это разбиение и порождает формальный ряд, лежащий в основе метода:

$(12) \qquad S = \sum\limits_{m_2,m_3,… >0}C_{[m_2,m_3,… ]}t_2^{m_2} t_3^{m_3}…$

За деталями доказательства я отправляю терпеливого и дотошного читателя к оригинальной статье. Добавлю только, что авторы дополняют доказательство, рассматривая формальный ряд как инверсию ряда , используя метод Лагранжа.

Кроме основного результата Валдбергер и Рубайн обнаружили любопытную факторизацию ряда , которая выявляет некую более глубокую структуру внутри множества обобщённых чисел Каталана. В частности, из суммы всех неединичных слагаемых в правой части равенства можно вынести общий множитель:

$\mathbf{S} = 1 + (t_2+t_3+...)\sum\limits_{m_2,m_3,… > 0}G_{[m_2,m_3,… ]}t_2^{m_2} t_3^{m_3}…$

получив новую числовую мультипоследовательность $G_{[m_2,m_3,… ]}$ , названную авторами «жеодой» (без объяснений почему). Будучи результатом факторизации мультипоследовательности $C_{[m_2,m_3,… ]}$ , она в известном смысле проще или фундаментальнее её. Однако получение явного общего вида $G_{[m_2,m_3,… ]}$ , и изучение её алгебраических свойств пока остаёся полем для будущих исследований.

Примеры кода

Для того, чтобы поэкспериментировать с методом Вайлдбергера-Рубайна я написал несколько простых функций на языке Julia. Приведу здесь эти функции и примеры их использования.

""" Вычисляет обобщенное число Каталана для мультииндекса mix """
function C(mix)
    # факториал, возвращающий число с неограниченной разрядностью
    fct(x :: Int) :: BigInt = factorial(BigInt(x))
    
    # мультииндекс с исключёнными нулевыми элементами 
    ms = [(k,m) for (k,m) in enumerate(mix) if m != 0]
    
    # тривиальный случай
    if length(ms) == 0 
        return 1
    end
    
    E = fct(sum((k+1)*m for (k,m) in ms))
    V = fct(1+sum(k*m for (k,m) in ms))
    M = prod(fct(m) for m in mix)
    return Int(E/(V*M))
end

>>> [C([m2,m3]) for m2 in 0:5, m3 in 0:5]

6×6 Matrix{Int64}:
  1     1      3      12       55       273
  1     5     28     165     1001      6188
  2    21    180    1430    10920     81396
  5    84    990   10010    92820    813960
 14   330   5005   61880   678300   6864396
 42  1287  24024  352716  4476780  51482970

""" 
Для списка ts = [t₂, t₃, ...] коэффициентов уравнения, 
заданного в геометрической форме:

   0 = 1 - x + t₂x² + t₃x³ + ...

возвращает список из n первых частичных сумм ряда Вайлдбергера-Рубина
"""
function S(ts :: Vector{Int}, n :: Int)
    
    function layers(n,k)
        return n == 0 ? [] : 
               n == 1 ? [k] : 
               [ [i;l] for i in k:-1:0 for l in layers(n-1,k-i)]
    end
    
    l = length(ms)
    
    function partial(k)
        return sum( C(ix)*prod(m^i for (m,i) in zip(ms,ix) if m != 0) 
                   for ix in layers(l,k))
    end
    
    return cumsum(partial.(0:n))
end

# Приближения к корню уравнения 1 - x + 0.3x² - 0.2x³ = 0
>>> S([0.3,-0.2],10)

11-element Vector{Float64}:
 1.0
 1.1
 1.1
 1.0970000000000002
 1.0968000000000002
 1.09698
 1.0970100000000003
 1.0969976999999997
 1.0969939199999998
 1.096994718000001
 1.0969951620000107

""" Возвращает предел конечной последовательности, если она сходится. """
function limit(s)
    if length(s) < 3 
        return NaN
    elseif abs(s[end]-s[end-1]) < abs(s[end-1]-s[end-2])
        return last(s)
    else
        return NaN
    end
end

"""
Для списка cs = [c₀,c₁,c₂,c₃, ...] коэффициентов уравнения, 
заданного в геометрической форме:

   0 = c₀ + c₁x + c₂x² + c₃x³ + ...

возвращает предел первых n частичных сумм ряда Вайлдбергера-Рубина
если он сходится.
"""
function Wildberger_Rubinе(cs, n)
    c0=cs[1]
    c1=cs[2]
    s = -c0/c1*S([c0^k*c/(-c1)^(k+1) for (k,c) in enumerate(cs[3:end])],n)
    return limit(s)
end

# Приближённое решение уравнения -1 + 10x + 6x² - x³ = 0 
>>> Wildberger_Rubinе([-1,10,6,-1], 10)

0.09470366708440983

""" 
Для полинома P(x), заданного списком коэффициентов, и смещения a
возвращает списрк коэффициентов смещённого полинома P(x+a)
"""
function polynomial_shift(coeffs, a)
    n = length(coeffs) - 1  # Степень полинома
    shifted_coeffs = zeros(n+1)
    
    for k in 0:n  # Индекс нового коэффициента при x^k
        for m in k:n  # Суммируем вклады от старших степеней
            binom = binomial(m, k)
            shifted_coeffs[k+1] += coeffs[m+1] * binom * a^(m - k)
        end
    end
    
    return shifted_coeffs
end

# Итерационное решение уравнения -5 - 2x + x³ = 0 
cs = [-5,-2,0,1]
x0 = 2.0
x1 = Wildberger_Rubinе(polynomial_shift(cs,x0), 3) + x0
x2 = Wildberger_Rubinе(polynomial_shift(cs,x1), 3) + x1

>>> [x0,x1,x2]
3-element Vector{ComplexF64}:
 2.0
 2.0945345708
 2.094551481542327

# Итерационное решение уравнения -5 - 2x + x³ = 0 в комплексных числах
cs = Complex.([-5,-2,0,1])
x0 = -1 - im
x1 = Wildberger_Rubinе(polynomial_shift(cs,x0), 3) + x0
x2 = Wildberger_Rubinе(polynomial_shift(cs,x1), 3) + x1

>>> [x0,x1,x2]
3-element Vector{ComplexF64}:
                -1.0 - 1.0im
      -1.04735103535 - 1.1356950116125im
 -1.0472757407711633 - 1.135939889088928im

Хабы:

Математика