ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   06 May 2003  15:23:58
 To : Max Medvedev
 Subject : ГЛАВHЫЙ ЭЛЕМЕHТ ПО СТРОКЕ
 -------------------------------------------------------------------------------- 
 

 Mon May 05 2003 23:08, Max Medvedev wrote to All:
 
  MM>  Есть задачка - посчитать опpеделитель матpицы с ВЫБОРОМ САБЖА.
  MM>  Что есть сабж?
 
 Один из простых, и в то же время практичных способов вычисления определителя -
 приведение матрицы к единичной (еще практичнее - к треугольной, примерно вдвое
 меньше операций) посредством
 а. Деления строки матрицы на число, равное одному из элементов (таким образом,
 на его месте получается единица)
 б. Вычитания строки, умноженной на соответствующее число изо всех прочих строк
 (получая в том столбце, где на шаге "а" мы получили единицу, сплошные нули -
 понятно, число для каждой строки будет разное).
 После приведения к единичной (Клад! Мы нашли клад!) произведение элементов,
 фигурировавших в шаге "а" будет равно определителю.
 Hо попробуем сделать то же для матрицы, скажем,
 0 1
 1 0
 Оказывается, можно ограничиться приведением к матрице перестановок (в каждой
 строке и столбце по одной единице, остальные нули - приведенный пример как раз
 матрица перестановок). Тогда полезно для шага "а" выбирать наибольший элемент,
 это сокращает вычислительную погрешность. Hо выбор изо всех элементов
 непрактичен - сильно усложняя алгоритм, он не дает существенного выигрыша в
 точности. Поэтому выбирают этот (ведущий, главный, pivot) элемент обычно по
 строке. Hачинают с первой, находят в ней максимум по абсолютной величине,
 делят на него, полученную строку вычитаем, домножая на надлежащее, изо всех
 прочих, чтобы в этом столбце были одни нули, затем производят то же для всех
 прочих строк (имея в виду, какие столбцы мы уже обработали!) Произведение
 ведущих элементов и будет определитель.
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    ГЛАВHЫЙ ЭЛЕМЕHТ ПО СТРОКЕ   Max Medvedev   05 May 2003 23:08:20   ГЛАВHЫЙ ЭЛЕМЕHТ ПО СТРОКЕ   Evgenij Masherov   06 May 2003 15:23:58