Беклемишев - Дополнительные главы линейной алгебры (947281), страница 26

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 26)

Возмущение коэффициентов системы линейных уравнений может ие просто немного исказить ее решение, а иметь более серьезные последствия. Система линейных уравнений х-(- 0,99у = 1,01, л+ 1,01у = 0,99 ыз гл нв вввдвнив в числвнныв мвтоды имеет единственное решение, но за счет изменения ее коэффициентов и свободных членов на 1 % можно получить как противоречивую систему, так и систему, имеющую бесконечно много решений.

В приведенном примере детерминант матрицы системы мал по сравнению с ее коэффициентами. Нетрудно, однако, привести пример матрицы, детерминант которой не может рассматриваться как малое число, но обращается в куль при малом возмущении элементов матрицы. Рассмотрим, например, диагональную матрицу, скажем, двенадцатого порядка, у которой все элементы на диагонали равны десяти, кроме последнего, равного 10 ". Детерминант такой матрицы равен 10, но может быть обращен в нуль изменением одного элемента на 10 'ч. Причина этого заключается в следукяцем. Будем рассматривать элементы матрицы как независимые переменные.

Детерминант— линейная функция от каждой нз этих переменных, причем коэффициент прн переменной ао равен дополнительному минору этого элемента, умноженному на ( — 1)'"'. Отдельные миноры порядка п — 1 могут оказаться велики по сравнению с детерминантом. В этом случае малое изменение одного элемента может повлечь обращение детерминанта в нуль. Подробнее этот вопрос будет рассмотрен в й 2. Сейчас нам следует подчеркнуть принципиальную важность этого явления. Если числа не могут быть заданы точно, то стирается четкая грань между вырожденными и невырожденными матрицами. Появляется класс почти вырожденных матриц, границы которого зависят от принятой в данном конкретном исследовании меры точности.

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

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

ПоСкольку эта функция непрерывна, множество невырожденных матриц открыто (см. Кудрявцев Пб), т, 1, стр. 329). Это означает, что у невырожденной матрицы А, существует окрестность!! А— — А, !1 (е, также состоящая из невырожденных матриц. Однако мы не можем рассматривать произвольно малые окрестности— радиус окрестности не может быть меньше, чем некоторое число е„ бпределяемое точностью вычислений или величиной возможного возмущения матрицы. Почти вырожденные матрицы — это такие, у которых в окрестности радиуса з, найдется вырожденная матрица. Этн соображения имеют достаточно общий характер и приводят К тому, что вдоль границы любого открытого множества а» появляется «полоса неопределенности» ширины з„составленная нз з,-окрестностей граничных точек множества аК.

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

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

Правда, объем внешних запоминающих устройств йастолько велик, что не накладывает чувствительных ограничений, 1)о использование этих устройств связано с другими трудностями, Ь первую очередь со сравнительно ббльшимн затратами времени. Читателю, не имевшему дела с программированием, проще всего представлять себе дело так. Вы решаете систему линейных уравнений на классной доске.

Она расчерчена на клетки, и в каж- Ъ ой клетке можно записать одно число. После того как доска исписа, дальше писать можно, только стерев что-нибудь. Есть еще н тетрадь, но она хранится так, что доставать ее долго, и, кроме 120 ГЛ. НЬ ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ того, списывать с доски в тетрадь или обратно нужно обязательно целое число страниц. Ясно„что решить при таких условиях систему, матрица которой не уменьшается на доске или занимает ее почти целиком, можно, только проявив известную изобретательность и затратив дополнительное время.

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

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

б) Разреяеенные матрицы. Так называются матрицы, у которых большая часть элементов равна нулю, причем не предполагается, что ненулевые элементы расположены по какому-либо известному закону. Мы можем запоминать только ненулевые элементы разреженной матрицы, но придется затрачивать дополнительное время и память на то, чтобы указать, в какой строке и каком столбце лежит данный ненулевой элемент. Например, простейшая схема состоит в том, чтобы вместе с элементом матрицы запомнить номера его строки и столбца. Если сделать это опять-таки самым простым, но не самым экономным способом, и отвести на хранение номеров по одной ячейке, то общее число потребующихся ячеек окажется втрое больше числа ненулевых элементов. Если при этом матрица заполнена на 1/5, то еще не ясно, стоит ли полученная экономия дополнительных затрат времени н усложнения программы.

Практически матрицу больших размеров имеет смысл считать разреженной, если число ненулевых элементов имеет тот же порядок, что и число строк в матрице. Разреженные матрицы встречаются во многих вопросах прикладной математики. Описание способов их хранения и переработки можно найти в книге Тьюарсона 132). $ Ь ВВЕДЕНИЕ в) Промежуточное положение между двумя описанными выше классами матриц занимают матрицы, которые можно назвать матрицами специальных видов. Они имеют нули на заранее известных местах или часть их элементов вычисляется по остальным элементам, которые должны храниться. Вспомним, например, матрицы диагональные, симметричные или треугольные.

Из матриц специального вида, не встречавшихся нам до сих пор, стоит сказать о ленточных матрицах. Матрица А называется ленточной, если ее элементы таковы, что ац = О при ~ 1 — 1 ~ ) й, где й — некоторое фиксированное число. Это значит, что отличными от нуля могут быть только те элементы матрицы, которые лежат внутри «ленты» ширины 2й+ 1, идущей вдоль главной диагонали, Ленточные матрицы часто встречаются в разных приложениях. Происходит это по следующей причине.

Характеристики

Список файлов книги