Аннотация:
Одним из наиболее распространенных способов решения векторного
линейного уравнения x=Ax+f является метод простых итераций, суть
которого в нахождении решения путем последовательных приближений
$x(n+1)=Ax(n)+f$.
Распространен также другой способ решения исходного уравнения - так
называемый метод Гаусса-Зейделя, который может быть представлен как
поочередное вычисление итераций либо по формуле $x(n+1)=Bx(n)+f$, либо
по формуле $x(n+1)=Cx(n)+f$, где $B$ и $C$ — специальным образом
сконструированные по A более простые матрицы “построчного пересчета”.
Возникает вопрос, что случится, если в методе Гаусса-Зейделя матрицы $B$
и $С$ начнут применяться не поочередно, а в произвольном порядке? Этот
вопрос далеко не искусственный и имеется множество примеров "реальных"
задач, приводящих к нему — распараллеливание вычислений, системы
управления с асинхронным обменом данными, поведение систем
коллективного поведения, проблема гладкости вейвлетов, теория
арбитражных операций валютного рынка и т.д.
Переход от итерационных процедур с одной матрицей к процедурам с
несколькими матрицами, применяемыми в произвольном порядке, мгновенно
делает практически бесполезной всю технику классической линейной
алгебры и переводит задачу из алгоритмически и вычислительно простой в
разряд “супертрудных”, основные методы решения которой в настоящее
время ассоциируются с так называемой теорией обобщенного или
совместного спектрального радиуса наборов матриц.
В докладе будут представлены начальные постановки и определения
соответствующей теории, будет дано объяснение алгебраической
неразрешимости и NP-сложности вычисления обобщенного спектрального
радиуса, будет сформулирована “неконструктивная” теорема о так
называемых “нормах Барабанова”, до сих пор вопреки своей
неконструктивности являющаяся одним из немногих работающих
инструментов данной теории.
|
