Вызов Кода — Гигантские Вавилонские Матрицы

Введение

У вавилонян был хитрый метод поиска квадратных корней. Чтобы найти квадратный корень числа

 
 
 
 M 
 
 
 

Если предположение меньше, чем sqrt(N), N/guess должно быть больше, чем sqrt(N), поэтому усреднение этих двух членов должно приблизить вас к истинному ответу. Оказывается, этот метод довольно быстро сходится к правильному ответу:

Расширение

Существует ли эквивалентный алгоритм для матриц? Отбросив всю математическую строгость, если мы хотим найти «квадратный корень» из квадратной матрицы guess , we may again start with a M , затем уточните его, неоднократно оценивая строку кода:

где inverse() — обратная функция матрицы, а * — умножение матрицы. Вместо 1 нашей первоначальной догадкой является единичная матрица соответствующего размера.

Однако сходимость больше не гарантируется — алгоритм расходится для большинства (но не всех) входных данных. Если M производит сходящийся ряд, это Вавилонская матрица. Более того, сходящееся значение на самом деле представляет собой действительный квадратный корень матрицы (т. Е. guess = (guess + N/guess) / 2 ).

Пример

Вот пример использования матрицы 2x2, показывающий сходимость ряда:

Всего за несколько итераций ряд сходится с точностью до 1e-9. Через некоторое время она становится неустойчивой из-за суммирования ошибок округления, но демонстрируется первоначальная устойчивость, чего вполне достаточно.

Задача

Ваша задача — найти квадратную матрицу. N , populated by the integers 1 through 9, which, when given an initial guess of an identity matrix of the proper size, converges successfully. Matrices should be submitted as comma-delimited text (or attached text files, if they are too large), with either brackets or newlines separating subsequent rows.

Правила

Несмотря на то, что матрица M и начальное предположение используют целые числа (в основном для удобства отображения), вся арифметика должна выполняться с использованием плавающей запятой двойной точности. Целочисленные операторы (например, 3/2, приравнивающие к 1) запрещены.

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

Алгоритм считается сходящимся, если итерация не приводит к изменению, превышающему 1e-9, в любой отдельной ячейке.

Вы можете использовать внешние математические библиотеки для инверсии матриц (нет необходимости изобретать велосипед).

Условие победы

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

#вызов кода #математика #последовательность

Изготавливаем такую ​​матрицу любой размерности

 
 
 
 
 n = 10;
M = RandomInteger[{1, 9}, {n, n}];
guess = IdentityMatrix[n] // N;
result = NestList[(# + Inverse[#].M)/2 &, guess, 32];
ListPlot[Transpose[Flatten /@ result], Joined -> True]
M // MatrixForm
 
 
 
 
 

Пример:

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

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

Я построил данную матрицу так, чтобы она имела положительные собственные значения следующим образом. Во-первых, начните с матрицы всех единиц, которая имеет ранг 1 и, следовательно, имеет одно собственное значение (n), а все остальные равны 0. Затем добавьте единицу, которая сдвигает собственные значения на 1 вверх, чтобы получить (n + 1 ,1,1,...,1). Итерация приводит к тому, что собственные значения сходятся к (sqrt(n+1),1,1,...,1). Обратите внимание, что единицы не меняются на каждой итерации.

Вот вавилонская матрица 10x10 в качестве первой цели:

который сходится к

и был найден с помощью этого кода Mathematica: