ПРИЛОЖЕНИЕ II. РЕШЕНИЕ БОЛЬШИХ ЗАДАЧ ЛИНЕЙНОЙ АЛГЕБРЫ

Говоря о решении задач линейной алгебры на ЭВМ, мы всюду молчаливо предполагали, что входные данные и результаты промежуточных вычислений расположены в оперативной памяти (ОП). Однако в силу ряда причин одновременное хранение всей информации в ОП часто бывает невозможно или нецелесообразно. Такое положение может возникать при решении задач линейной алгебры как на малых вычислительных машинах, так и на больших машинах с многопрограммным управлением.

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

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

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

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

Важной характеристикой вычислительной схемы метода является общее время, затрачиваемое на обмен информацией. Сокращение этого времени имеет большое значение для ЭВМ как с однопрограммным, так и с многопрограммным управлением. Ясно, что чем полнее

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

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

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

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

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

Как уже отмечалось, первая схема наиболее эффективна при Поэтому возьмем во второй схеме Простые вычисления показывают, что теперь общее время обмена для второй схемы будет таким:

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

Очевидно, что для решения любой системы уравнений клеточным методом с использованием ВП потребуется больше времени, чем для решения той же системы обычным методом с записью всей матрицы

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

Здесь время, затрачиваемое на выполнение арифметических операций в клеточном методе, — время, затрачиваемое на обмен информацией между ОП и ВП, - время, затрачиваемое на выполнение арифметических операций в обычном методе.

Исследование коэффициента потерь обнаруживает удивительный факт. Для средних машин типа БЭСМ-4 он близок к 2 уже при Следовательно, используя ВП для хранения матрицы и всего лишь 300 ячеек ОП для организации обйрна, можно на таких ЭВМ весьма успешно решать большие задачи. При этом мы затратим только в 2 раза больше времени по сравнению с тем случаем, если бы смогли записать в ОП всю матрицу.

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

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

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

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

Эффективные по скорости и использованию памяти ЭВМ численные методы решения систем с клеточно-теплицевыми матрицами появились сравнительно недавно.

Пусть ваданы квадратные матрицы порядка Рассмотрим клеточно-теплицевы матрицы

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

Ясно, что при эти столбцы совпадают и содержат лишь одну клетку Предположим, что известны и Будем искать и в трком виде:

где -некоторые матрицы порядка Так как являются клеточными столбцами матрицы то

Здесь -единичная матрица порядка Обозначив

получаем из последних соотношений, что

и далее находим

Таким образом, для матриц можно последовательно определить первые и последние клеточные столбцы, не вычисляя элементы остальных столбцов.

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

и рассмотрим усеченные системы

где

Все векторы, выписанные здесь в квадратных скобках, имеют один и тот же порядок Пусть

Подставив это выражение в уравнение

и учитывая, что вектор и удовлетворяет уравнению

заключаем, что вектор поправки с элементами является решением системы где

Вектор есть линейная комбинация последних столбцов матрицы координаты вектора являются коэффициентами данной линейной комбинации. Следовательно, для рекуррентного вычисления векторов достаточно рекуррентно вычислять последний клеточный столбец матриц Заметим, что вектор совпадает с а вектор

Этот метод решения систем с клеточно-теплицевыми матрицами весьма эффективен по сравнению с другими прямыми методами. Для его реализации при больших необходимо выполнить лишь порядка арифметических операций, занимая при этом слов памяти ЭВМ. Если клетки матрицы связаны между собой соотношениями для некоторых симметричных матриц перестановок то объем вычислений и необходимую память можно уменьшить примерно в два раза.

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

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

Введем в рассмотрение классы соответственно клеточно-диагональных, клеточно-циркулянтных и клеточно-теплицевых матриц клеточного порядка Под будем понимать класс любых других клеточных матриц такого же порядка. Теперь рассмотрим системы, матрицы которых задаются последовательностью где в каждой позиции вместо стоит одна из букв Это означает, что разбиение первого уровня определяется символом второго — символом последнего — символом

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

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

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

Значительное число теоретических и прикладных задач привадит к решению больших алгебраических систем с разреженными матрицами. Эти матрицы имеют много нулевых элементов. Если ненулевые элементы расположены согласно рис. 27.3, то для решения таких систем исключительно эффективным оказывается применение метода Гаусса. При этом эффективность метода будет тем выше, чем меньше на рис. 27.3 площадь заштрихованной части и число нулевых элементов в ней.

Последнее замечание лежит в основе многих способов предварительного преобразования разреженной матрицы. Как правило, эти преобразования состоят лишь в перестановке строк и столбцов и направлены либо на сокращение общего времени счета задачи, либо на уменьшение объема необходимой памяти ЭВМ. Эффект от таких преобразований может быть очень большим. Рассмотрим, например, матрицы вида

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

Если ненулевые элементы разреженной матрицы расположены без какого-нибудь явного порядка, то найти соответствующие матрицы перестановок очень трудно. Для решения этой задачи нередко приходится привлекать различные методы комбинаторики, теории графов, целочисленного программирования и т. п. Однако затраты на предварительное преобразование разреженных матриц вполне окупаются, если сами матрицы имеют большие размеры и системы с ними решаются многократно. Такие ситуации возникают при оперативном управлении энергетическими сетями, транспортными потоками, технологическими процессами. Конечно, аналогичные преобразования можно выполнять и с клеточными разреженными матрицами.

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

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

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

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

ЛИТЕРАТУРА

(см. скан)