Генерация систем уравнений

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

Первые эксперименты

Системы представлены матрицей коэффициентов — A, вектором f, и матрицей степеней P, т.е:

для каждого уравнения из системы.

Коэффициенты матрицы A подбирались тремя способами:

1. Произвольно с помощью функции random(), от 1 до 20 включительно;

2. Недиагональные элементы подбирались произвольно как и в первом случае, а затем диагональ подгонялась так, чтобы выполнялось условие: после чего строки делились на диагональные элементы;

3. Недиагональные элементы подбирались произвольно как и в первом случае, а затем диагональ подгонялась так, чтобы выполнялось условие: .

На проверку каждого способа было сгенерировано по 500 систем уравнений каждого вида. Элементы матрицы степеней всегда генерировалась произвольно с помощью функции random(), от 1 до 4 включительно. Вектор f так же генерировался произвольно с помощью функции random(), от 1 до 20 включительно.

Таким способом решались матрицы размером 3х3, 4х4 и 5х5. Код был написан на php, сразу отмечу, что для прототипирования php хорош, а для вычислений нет — считалось очень медленно. Поэтому были проведены некоторые изменения к экспериментах.

Изменения в экспериментах

Из-за недостаточной скорости программа была переписана на c. После этого результаты существенно не изменились. Но существенно увеличилась скорость работы и теперь на каждый эксперимент генерировалсь 10000 систем.

Затем изменилась генерация вектора f: Сначала генерировался случайный вспомогательный вектор t, как ранее f (с помощью функции random(), от 1 до 100 включительно). После чего вектор t подставлялся в исходную систему вместо вектора x и высчитывалась правая часть системы, которая и становилась вектором f. Таким образом у каждой системы гарантированно имелось решение. Но теперь системы вовсе не решались для разных векторов коэффициентов по длине (Ранее стартовый вектор брался как единичный вектор).

Для того чтобы хоть как-то восстановить результаты стартовый вектор начал генерироваться с помощью функции random(), от 1 до 100 включительно. Из-за чего результаты улучшились, для вектора коэффициентов размером 4 и больше (до 5-7% решенных систем).

Из-за вероятности корреляции стартового вектора и вектора t, стартовый вектор вновь стал получаться статично, но теперь каждый элемент был равен 60. Это значение было подобранно опытным путём. При таком стартовом векторе успешно решаются 14-18% систем. Если брать вектор меньше, к примеру 20 для всех элементов, то было решено 1-5% систем. 100 так же не лучшее значение — решалось 8-12%. И при увеличении значения процент решённых систем уменьшался (150 стартовые значения и 6-7% решённых систем). Значение 60 возможно не самое оптимальное.

Затем было замечено, что решения всё же есть, но не точные. Различие у элементов t и вектора решения sol были в 4-7 разряде после запятой. Из-за этого решение считалось не точным и не засчитывалось. И таких неточных решений было 55-65%.

Значение ε было уменьшено до 10^-15 и все неточные решения перешли в точные. Таким образом неточных решений стало меньше 5%. А процент решённых систем стал 70-80%.

Для того, чтобы совсем исключить процент неточных решений были введены принудительные итерации, т. е. теперь поиск решения прекращался не тогда, когда различия между элементами вектора решения были меньше чем ε, а когда проходило количество принудительных итераций. На данный момент количество таких итераций — 1000. А количество не точно решённых систем не превышает 1%.

Последним шагом было применение метода случайного поиска для подбора более оптимальных коэффициентов.

Дополнительные сведения:

1. Для вектора коэффициентов размерности 3 решения тоже получаются, но они расходятся на 0,5 примерно, хотя я пробовал и до 5000 принудительных итераций;

2. Для вектора коэффициентов размерности меньше трёх правильных или хотя бы неточных решений совсем нет.

3. Далее при условии, что коэффициенты генерируются по формуле: Где i — номер коэффициента от n до 1, n — размер вектора коэффициентов. По формуле получается, что последнее приближённое решение умножается на максимальный элемент, т. е. вектор коэффициентов убывает. Так как число 60, которым инициализируется стартовый вектор st зависимо от диапазона генерации, то для некоторых опытов стартовый вектор инициализировался диагональными элементами матрицы.

Проверка на циклическое повторение получаемых приближений

Из-за неточных преобразований при вводе вектора коэффициентов сумма компонент этого вектора не равнялась единице. Сейчас это исправлено и сумма элементов вектора равна 0.(9), т. е. единице фактически, учитывая то, что длина мантиссы 512 бит или 154-155 десятичных цифр (Была использована библиотека GMP).

Затем был сделан пересчёт, в результате которого почти не было решённых систем, но было большое количество неверно решённых. Для анализа были выбраны 10 систем размера 3х3 и вектор размера 11.

У всех было выявлено циклическое повторение приближений, т.е. приближения после некоторого количества итераций начинали повторяться с некоторым периодом. Причём у 8 систем период был равен двум, т.е. на каждой чётной итерации значение приближения стремилось к одному числу, на каждой нечётной к другому. Так же было замечено, что настоящее решение обычно (но не всегда), лежит между этими двумя числами. Например чередуются 120 и 87, значение компоненты вектора настоящего решения равно 96 или 33-54 и ответ 36.