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

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

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

Выбор главного элемента. Рассмотрим теперь невырожденную матрицу А, не накладывая никаких ограничений на ее главные миноры. Уже условие ан эь О может быть невыполненным. В этом случае для превращения первого столбца матрицы А в столбец единичной матрицы недостаточно ограниченного набора элементарных операций, примененных в описанной выше схеме единственного деления. Однако если к этим операциям добавить перестановки строк (или столбцов), то условие отличия от нуля главных миноров в теореме 1 может быть снято. В самом деле, имеет место П р е д л о ж е н н е 5, Бевырожденную матрщ!у А порядка и перестановкой только строк (или только столбцов) можно перевести в матрицу, главные миноры которой отличны от нуля. В первых п — 1 столбцах матрицы А обязательно есть минор, отличный от нуля, так как иначе столбцы были бы линейно зависимы и де! А был бы равен нулю.

Переставим строки так, чтобы этот минор оказался главным минором порядка и — !. Пусть А' — матрица, полученная в результате проделанной перестановки. Очевидно, что в А' мы можем переставлять строки с номерами 1, ..., п — 1, не обращая в нуль ее главный минор порядка п — !. Воспользуемся этим, для того чтобы переставить на главную диагональ отличный от нуля минор порядка п — 2, расположенный где-то в первых п — 1 строках н в первых и — 2 столбцах.

Такой минор обязательно существует, так как иначе главный минор порядка п — 1 в матрице А' равнялся бы нулю. Действуя дальше подобным образом по отношению к минорам убывающих порядков, мы докажем утверждение для перестановок строк. Для перестановок столбцов доказательство аналогично. Перестановка строк в матрице равносильна умножению этой матрицы слева на матрицу Р, получаемую из единичной матрицы Е той же перестановкой строк.

Точно так же перестановка столбцов равносильна умножению справа на матрицу Д, получаемую из Е этой перестановкой столбцов. Такие матрицы, как Р и !е называются матрицами перестановок. Матрица, обратная к матрице перестановки, является матрицей обратной перестановки, возвращающей строки на их прежние места. Поскольку матрица перестановки ортогональна, для нее Р ' = Рт З 3 ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ Записывая указанные в предложении 5 перестановки как умножение на матрицу, в силу полученных ранее результатов об Г.У- разложении мы приходим к следующей теореме. Т е о р е м а 2.

Для произвольной невырожденной матрицы А существуют следующие разложения: А=РГ.и, А = РМОУ, А = М'0'1~Я, в которых Р и Я вЂ” матрицы перестановок, У, У', у и 1' — верхние треугольньы матрицы с единицами на главной диагонали, Л, Г.', М и М' — нижние треугольные матрицы, причем М и М' имеют единицы на диагонали, а 0 и 0' — диагональные матрицы. Для применений этого результата нужно указать алгоритм, позволяющий построить матрицы перестановок, или, что то же самое, указать перестановку строк или столбцов, делающую главные миноры отличными от нуля. Вместо такого алгоритма, как правило, применяется схема единственного деления в измененном виде. Эта измененная схема приводит к последовательности преобразующих матриц, в которой чередуются треугольные матрицы и матрицы перестановок.

Изменения вносятся следующие. Если окажется, что в начале первого шага элемент а„равен нулю, мы переставим строки так, чтобы в левый верхний угол попал ненулевой элемент. Хоть один такой элемент обязательно найдется в первом столбце, так как де1 А ~и О. Выбранный нами для этой цели ненулевой элемент мы назовем главным (или ведущим) элементом первого шага. Точно так же, если на втором шагу аД = О, то второй столбец матрицы А си содержит ненулевой элемент ниже диагонали (иначе первые два столбца были бы линейно зависимыми).

Переставляя строки, мы можем поместить этот элемент на место а!',Ц Он будет называться главным элементом второго шага. Аналогнчно определяется главный элемент и для любого шага. Здесь описан выбор главного элемента по столбцу. Если пере. становки строк заменить перестановками столбцов, то на й-м шагу главный элемент будет выбираться среди элементов Ьй строки матрицы А "-". Выбор главного элемента по всей матрице означает возможность переставить на место а'," — и любой элемент а)" — и при 1 = й, у ) й. Заметим, что выбор главного элемента по строке приводит ко второму разложению в теореме 2.

Теоретически в качестве главного элемента может быть взят любой ненулевой элемент. Однако с практической точки зрения дело обстоит не так просто. Как мы видели в Э 1, даже результат проверки, равен ли элемент нулю, может зависеть от представления чисел в машине. Выбор главного элемента оказывает существенное влияние на ошибки округления. Поэтому, даже если мы установили, что, например, в исходной матрице ам не равно нулю, это ГЛ и! ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ еще не означает, что его разумно выбрать в качестве ведущего элемента. Для примера рассмотрим систему 10-лх+ у 1 х+у=2 и допустим, что арифметические операции производятся с округлением результата до трех значащих цифр в системе с плавающей запятой.

Вычисленное без округления решение системы есть х= (! — 1О ') '= 1+ 10-'+!О-'+..., у = 2 — х =! — 1О-" — 10-' —... Пчипяв 1О ' за главный элемент, л.ы должны будем преобразовать расширенную мшрицу системы следующим образом: !о-4 !!!! ! ! !Ел! !ол! В !он !он !! о(о)~ Заметим, что число 2 после прибавления к нему !О' и округления исчезло, и если бы в исходной системе там стояло 3, а не 2, результат был бы тем же.

Найденное решение есть х == О, у =!. Это далеко от истинного решения. Если же, переставив строки, мы выберем в качестве главного элемента 1, то преобразование расширенной матрицы будет таким: ~~!о- ! )!!! !~о 1!!' ,„~о !!!,~' Это даст вычисленное решение х = 1, у = 1, совпадающее с округленным истинным решением, т. е. настолько точное, насколько это вообще возможно. В первом варианте решения мы видели, что потеря точности связана с тем, что приходится складывать числа, порядки которых отличаются больше чем на длину мантиссы.

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

Обычная рекомендация состоит в том, чтобы в качестве главного выбирать наибольший по модулю элемент преобразуемой части матрицы или, что проще, ио несколько хуже, наибольший по модулю элемент очередной строки или столбца. В следующем пункте мы вернемся к этому вопросу, а сейчас заметим только, что, умножив в разобранном выше примере первое уравнение на 1О', мы получим систему 10х+ 10'у = 10', х+ у=2. й!аксимальный элемент первого столбца равен 10, но, выбрав главным его, мы получим то же неудовлетворительное решение.

$3 ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СНСТЕМ В некоторых случаях увеличение точности решения — не единственное соображение, которое нужно принимать во внимание, выбирая главный элемент. Если метод Гаусса применяется к разреженной матрице (см. стр. 120), то с каждой элементарной операцией заполненность матрицы ненулевыми элементами, вообще говоря, будет возрастать.

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

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

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

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

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