Cтраница 3
Существует большое число стратегий упорядочивания, которые отличаются критериями выбора главных элементов в выражениях (4.280) - (4.283) и, как следствие, различным временем упорядочивания. Поскольку конечной целью упорядочивания является решение системы (4.301), то при выборе главных элементов, кроме уменьшения ННЭ и ИНЭ, учитывают некоторые дополнительные требования. Так, в системе уравнений (4.301) возможно появление малых по величине ненулевых элементов ( НЭ), которые нельзя выбирать в качестве главных, и поэтому при упорядочивании необходимо проводить численные оценки. Кроме того, для повышения скорости упорядочивания и решения необходимо по возможности полнее учитывать особенности системы и на каждом шаге упорядочивания ограничиваться выбором главных элементов не по всему полю исследуемой системы, а среди некоторого множества строк - выбором столбцов, которые удовлетворяют критерию минимизации числа ННЭ и приемлемы с точки зрения вычислительной точности и устойчивости процесса решения. [31]
Чтобы повысить точность вычислений, целесообразно сначала найти в первой строке наибольший по абсолютной величине элемент и начать делать нули в том столбце, в котором он находится. После получения нулей в этом столбце находим, что во второй - строке полуленного определителя наибольший по абсолютной величине элемент находится и во всех строках, расположенных ниже второй строки. Повторяем то же самое для остальных строк. Все остальные вычисления производятся, как в предыдущем методе. Таким образом, выбор очередного столбца зависит от того, где находится наибольший по абсолютной величине элемент в соответствующей строке. Это видоизменение метода исключения называется методом главных элементов. [32]
Поскольку ведущая строка добавляется перед преобразованием, и сразу после преобразования вычеркивается, можно прямо представить переход от таблицы к таблице, как элементарное преобразование по столбцам, в котором ведущий столбец, умножаемый на целые числа, складывается с каждым столбцом, при этом целые множители получаются из текущей целочисленной ведущей строки. Элементарное преобразование по столбцам не может изменить ранга таблицы. Из ( 11) ясно, что столбцы в первой таблице линейно независимы и поэтому столбцы всех последующих таблиц должны быть также линейно независимыми. Соответственно Tfc tj для любой пары столбцов aft и а7 - в любой таблице, поскольку равенство означало бы пропорциональность, а значит, линейную зависимость столбцов aft и &. Отсюда можно сделать вывод о том, что правило выбора ведущего столбца дает всегда однозначный результат. [33]
Чтобы повысить точность вычислений, целесообразно сначала найти в первой строке наибольший по абсолютной величине элемент и начать делать нули в том столбце, в котором он находится. После получения нулей в этом столбце находим во второй строке полученного определителя наибольший по абсолютной величине элемент и делаем нули в столбце, в котором этот элемент находится и во всех строках, расположенных ниже второй строки. Повторяем то же самое для остальных строк. Все остальные вычисления производятся как в предыдущем методе. Таким образом, выбор очередного столбца зависит от того, где находится наибольший по абсолютной величине элемент в соответствующей строке. Это видоизменение метода исключения называется методом главных элементов. [34]
При преобразовании ядра, как только столбец преобразован, его ненулевые элементы, принадлежащие к недопустимым строкам, могут быть удалены во внешнюю память вплоть до осуществления нижних треугольных операций. Несмотря на это, список матричных элементов в допустимых строках и столбцах может оказаться первоначально слишком большим для того, чтобы быть хранимым в МОЗУ или может стать позднее слишком большим в силу создания новых ненулевых элементов. На любой стадии операции на ядре, если список матричных элементов превышает возможности оперативной памяти, столбцы, выбираемые для того, чтобы храниться во вне, это столбцы, которые имеют наибольшие оценки. Эти столбцы не вызываются назад вплоть до того момента, когда появляется пространство для них в магнитной памяти. Таким образом, по крайней мере на нескольких операциях они не играют никакой роли в выборе ведущих элементов. Это может привести к плохому выбору ведущего столбца. Таким образом, процедура часто приводит к плохим результатам, когда большая часть столбцов должна остаться во внешней памяти. [35]
Для выбора конкретной ячейки из всех доступных необходим какой-то вполне определенный способ выбора. Один из таких способов заключается в использовании дешифратора. Для 16-разрядной памяти можно использовать дешифратор Ьиз-16 с четырьмя входными, или адресными, линиями и 16 выходными линиями, каждая из которых соединена с ячейкой памяти. Нужную ячейку можно выбрать, поместив ее адрес на входы дешифратора. Метод линейной выборки реально применим только при небольшом количестве ячеек. При использовании этого способа для памяти объемом 1 Кбит ( 1 К 1024210) необходимо иметь дешифратор с 1024 выходными линиями. Использовать дешифраторы такого размера просто нерационально. Поэтому обычно ячейки в памяти располагаются в виде матрицы и используются два дешифратора - один для выбора столбца, или Y-линии, а другой для выбора строки, или Х - линии. В этом случае для 16-разрядной памяти можно использовать два дешифратора 1-из - 4 так, что два младших бита адреса поступают на дешифратор Х - линий, а два старших бита адреса - на дешифратор Y-линий. [36]