Метод последовательных приближений с инерцией. Эксперименты
Описание метода последовательных приближений с «инерцией»
Этот метод может быть представлен итеративной формулой:
.
Где α — вектор коэффициентов инерции. Сумма элементов которого строго равна единице. Как видно из формулы — для получения следующего приближения используется сразу несколько предыдущих, причём для каждого предыдущего приближения определён свой вес.
Статистика
Для метода последовательных приближений с «инерцией» был проведён ряд экспериментов, результаты которых следуют далее. Тестовые примеры генерировались для экспериментов при помощи стандартных средств языка си (т. е. функции rand()). Если представить систему нелинейных алгебраических уравнений как:
.
Где Aij — элементы матрицы коэффициентов, которые выбирались случайно от 1 до 100 среди целых чисел;
Pij — элементы матрицы степеней, выбирались случайно от 1 до 4;
bj — элементы вектора правой части, выбирались случайно от 1 до 100 среди целых чисел.
Кроме того матрица A была диагонально доминирующая и все системы имели хотя бы одно решение. Всего на каждый набор параметров было сгенерировано 10000 экспериментов.
Во-первых было исследовано влияние вектора коэффициентов инерции на решаемость систем. Эмпирически было выявлено, что при убывающем векторе коэффициентов инерции решается на порядок большее количество систем.
Во-вторых были подобранны векторы коэффициентов инерции размером от 4 до 12 при помощи метода случайного поиска. После чего с этими векторами были проведены эксперименты для систем нелинейных алгебраических уравнений размерности от 3х3 до 15х15. В табл.1, где по столбцам отмечены различные вектора, а по строкам размеры систем можно увидеть процент решённых систем (из 10000).
Табл. 1
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
| 3х3 | 86% | 94% | 94% | 87% | 94% | 98% | 98% | 99% | 96% |
| 4х4 | 79% | 91% | 84% | 68% | 90% | 97% | 97% | 98% | 93% |
| 5х5 | 71% | 85% | 67% | 47% | 88% | 95% | 93% | 98% | 89% |
| 6х6 | 59% | 79% | 48% | 31% | 87% | 94% | 83% | 98% | 84% |
| 7х7 | 42% | 73% | 31% | 20% | 84% | 91% | 68% | 98% | 78% |
| 8х8 | 26% | 68% | 19% | 12% | 77% | 89% | 51% | 97% | 72% |
| 9х9 | 14% | 62% | 13% | 7% | 66% | 86% | 37% | 97% | 67% |
| 10х10 | 7% | 55% | 8% | 4% | 52% | 84% | 26% | 96% | 60% |
| 11х11 | 3% | 46% | 5% | 2% | 38% | 81% | 16% | 96% | 52% |
| 12х12 | 1% | 38% | 3% | 1% | 27% | 77% | 10% | 95% | 45% |
| 13х13 | 0% | 28% | 2% | 0% | 18% | 73% | 7% | 92% | 35% |
| 14х14 | 0% | 20% | 1% | 0% | 11% | 70% | 4% | 87% | 27% |
| 15х15 | 0% | 13% | 0% | 0% | 6% | 66% | 2% | 79% | 19% |
Выводы
Очевидно, что вектора размера 9 и 11 ведут себя лучше всего. Похоже, что вектора нечётного размера лучше чётного, хотя может быть это погрешность вычислений. Чем больше вектор, тем лучше решается, на данной выборке не видно ухудшения количества решённых матриц при увеличении размера вектора.