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

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

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

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

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

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

е, их элементы связаны соотношениями аи — — 10г'+"(ау, 1, !=1, ..., и, а свободные члены обеих систем удовлетворяют условиям Ь'; =10е~Ь; 1=1 ... и. Тогда имеет место следующее П р ед л о же н и е 6. Пусть обе системы решаются по схеме единственного деления, причем для обеих систем на каждом шагу берутся в качестве главных элементы, занимаюи4ие в матрицах одинаковые позиции.

Тогда вычисленные решения обеих систем связаны равенством х,'=10 чгхм /=1, „., и, а мантиссы х) и х, совпадают, если при решении одной из систем не появится машинный нуль или не возникнет перепо|нения. (Говорят, что решение второй системы получается демасштабированием из решения первой.) Д о к а з а т е л ь с т в о. Заметим вначале, что мантиссы соответствующих элементов рассматриваемых систем совпадают, а округление затрагивает мантиссу, а не порядок, который может поалцять лишь на возникновение переполнения или появление машинного нуля. Проверим, что применение к обеим матрицам одной и той же элементарной операции схемы единственного деления даст такие же системы, отличающиеся масштабированием.

Для простоты записи будем считать, что речь идет о первом шаге прямого хода схемы единственного деления. Пусть в качестве главного выбран элемент из й-й строки и 1-го столбца. В матрице А из 1-й строки вычитается й-я, умноженная иа $ Д ПРЯМЫЕ МЕТОДЫ РЕПГВИИЯ СИСТЕМ д«/ааь Тогда 1-й элемент полученной строки равен аа а )' = ап — — ' а,~. ам В матрице А' аналогичное преобразование дает Ао'+'с а;')" =а„!0сч+'г — " аец10'а+'! =10'+'гаЯ'. ,аа+«~ аы Для элементов й-й строки преобразованной матрицы А' имеем а ..

Ра+аг а~'= —, м аадо — а +а = 10 заец. аи а„ВОР" ~ а~ В частности, ама=аД'=1 при 1'=1. В столбце свободных членов Ь' из 1-го элемента вычитается й-й, умноженный на аа/аы. ш'+'~ Кроме того, й-й элемент столбца свободных членов должен быть разделен на а,',: Ьаа= ~'1О =а" 10 ак а„,1О'а+ "~ Таким образом, в результате преобразования получились две системы, связанные между собой так же, как н исходные системы, и масштабирующие множители ие изменились, за исключением множителя ведущей й-й строки, заменившегося на 10 а~ благодаря делению на ааь После окончания прямого и обратного хода мы получаем системы с единичными матрицами (считая, что перестановки выполнены).

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

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

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

Перед решением системы линейных уравнений ее матрицу можно масштабировать так, чтобы она стала равновесной. Недостаток такого подхода состоит в том, что при этом можно получить много равновесных матриц, сильно отличающихся обусловленностью. 5. Вычисления с двойной точностью и компактная схема. На ряде ЭВМ имеется техническая возможность, нашедшая отражение в принятых на них языках программирования (Фортран 111, ПЛ/1) проделывать любые вычисления с удвоенным числом разрядов. Конечно, это сильно повышает точность результата, но мы не будем останавливаться на обсуждении этой возможности, так как мы нигде не фиксировали число знача1цих цифр 1, и его удвоение не вносит в наши рассуждения ничего нового. Однако анализ ошибок округления показывает, что не все вычисления, проделываемые по какому-нибудь алгоритму, одинаково влияют на точность результата. Часто точность всего вычислительного процесса может быть существенно повышена за счет увеличения точности только некоторой его части.

Для широкого класса вычислительных средств имеется возможность сравнительно просто и без существенных дополнительных затрат времени получать с повышенной точностью выражения вида ~; а4», т. е. произведения строк на столбцы.

Это называется вычислением скалярного произведения в режиме накопления. Подробнее речь идет о следующем. Пусть мы должны перемножить два числа в системе с плавающей запятой. Для этого следует сложить их порядки и перемножить мантиссы. Если мантиссы являются 1-разрядными десятичными дробями, то их точное произведение имеет 21 разрядов. Произведение мантисс больше чем 0,01, но может оказаться меньше чем О,1.

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

Вычисленная таким образом сумма произведений отличается от истинной на величину, немногим превосходящую единичную ошибку округления, если только при сложении не произойдет существенной потери значащих цифр из-за большой разности порядков слагаемых. Доказательство этого факта можно найти в книге Форсайта и Малера 137]. Вычисление суммы произведений входит, практическим, во все алгоритмы решения задач линейной алгебры, и возможность вычислять такие суммы с меньшими ошибками округления весьма существенна. Обратим, например, внимание на то, что по формуле (2) система линейных уравнений с треугольной матрицей может быть решена при помощи вычисления суммы произведений. Таким образом, если используется режим накопления, решение такой системы содержит ошибки округления, сравнимые с ошибкой округления при одном умножении. Возможность вычислять сумму произведений в режиме накопления вызвала создание ряда алгоритмов, которые позволяют лучше использовать эту возможность.

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

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