Асимптотическая сложность оценки по столкновениям для решения линейных систем

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