Метод быстрого обращения матрицы и решения систем линейных уравнений

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

У разностной системы (24.6), как и у дифференциальной (24.4), существует единственная неподвижная точка — это значение обратной матрицы Л-1. Найдем условия, которым удовлетворяет неподвижная точка отображения (24.6).[ …]

АЕк+1 А 1 < е. Обозначив Z = 11 < е, которое дает конструктивный способ оценки числа членов ряда к.[ …]

Все вышеизложенное можно обобщить в следующей теореме.[ …]

Остановимся на вопросе вычисления величины Н. Если из априорных соображений трудно оценить величину Л, то по поведению последовательности В, В2, В4,. . где В = НА А, можно судить о величине максимального собственного числа матрицы В. Действительно, если максимальное из собственных чисел матрицы В больше единицы, то последовательность В2 расходится, если меньше — сходится к нуль-матрице. Отсюда видно, что всегда можно выбрать значение Н таким образом, чтобы наибольшее собственное число матрицы В было меньше единицы, т. е. неравенство (24.8) будет выполнено. Однако не следует выбирать Н слишком малым ввиду того, что сходимость ряда (24.7) также зависит от величины Н.[ …]

Изложим теперь весь алгоритм вычислений.[ …]

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

Последняя треть XX века ознаменовалась открытием в 1968 г. [137] В. Штрассеном метода, позволяющего умножить две матрицы за число операций, меньшее 0(А 3).[ …]

Известно, что операция умножения двух матриц размерности N х х N требует ТУ3 умножений, если использовать стандартную формулу для произведения матриц.[ …]

Этот прием, рекурсивно продолженный на матрицы порядка N = = 2 , дает число умножений порядка 0(А 2,808).[ …]

Вернуться к оглавлению

Добавить в ЗАКЛАДКИ