Книга: Этюды для программистов

21. Превратное обратное, или Ошибки при работе с плавающей точкой

21.

Превратное обратное,

или Ошибки при работе с плавающей точкой

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

Прежде всего освежим в памяти основные положения. Матрица — это квадратный массив вещественных чисел, в котором по горизонтали и вертикали располагается по n ? 1 элементов. Произведение С матрицы А справа на матрицу В записывается в виде С = АВ и задается формулой

Здесь подразумевается, что А, В и С — матрицы размера n ? n. Умножение некоммутативно; можно найти такие матрицы А и В, что АВ ? ВА. Обратной матрицей к матрице А будет такая матрица А^?1, что

AА^?1 = А^?1A = I

где I — единичная матрица, определяемая формулами I_ii = 1 и I_ij = 0 для i ? j. Большинство матриц имеет обратные, но не все. К сожалению, простейший способ обнаружить такие вырожденные матрицы состоит в том, чтобы попытаться вычислить обратную матрицу и потерпеть неудачу.

Как вычислить обратную матрицу? Следующий алгоритм принадлежит Гауссу.

Во-первых, положите матрицу X равной матрице I. В процессе вычислений матрица А будет в конце концов преобразована в I, матрица X, которая изначально была единичной матрицей, станет обратной к матрице А.

Для каждого столбца А, начиная со столбца 1 слева и кончая столбцом n справа, выполните следующее: Обозначим столбец, который будет обрабатываться на каждом этапе, символом j.

Пусть

есть наибольший по абсолютной величине элемент в столбце j ниже строки j ? 1. Если М равно нулю, то А — вырожденная матрица и продолжать обращение не имеет смысла. В противном случае поменяйте местами в обеих матрицах А и X строку j и строку, в которой находится М. И наконец, разделите каждый элемент в строке j матриц А и X на новое значение A_jj.

Теперь для всех строк i, i ? j, выполните все вычитания:

A_ik = A_ik ? A_ijA_jk, j ? k ? n,

X_ik = X_ik ? A_ijX_jk, 1 ? k ? n.

Результатом всех этих поэлементных вычитаний будет вычитание из строки i строки j с коэффициентом A_jj в обеих матрицах А и X. После выполнения этого шага для всех j все элементы сверху и снизу от A_jj станут нулевыми, а сам элемент A_jj будет равен единице. В матрице А не нужно выполнять вычитания слева от столбца j, поскольку все элементы строки j слева от A_jj равны нулю.

Для любого алгебраиста будет одно удовольствие доказать, что этот алгоритм всегда работает правильно и после его остановки X = А?1, если матрица А невырожденна. Вы едва ли найдете алгоритм, более приспособленный для структурной реализации. Почему бы нам, исключительно ради забавы, не провести небольшую проверку? Матрица Гильберта Hn порядка n определяется формулой

Вычислите обратную к Hn матрицу для n = 1, 2, …, 20, 25, 30, 35, 40, 45, 50. Вы, несомненно, понимаете, что результат получится не вполне точным из-за небольших погрешностей машинной арифметики, но он должен быть очень близок к точной обратной матрице. Мерой погрешности служит левая остаточная матрица L = (Hn)^?1Hn ? I и правая остаточная матрица R = Hn(Hn)^?1 ? I; обе эти матрицы должны быть нулевыми, но, вероятно, не будут.

Конечно, если бы все элементы матриц L и R были порядка, скажем, 10^?20, то мы бы не имели забот. Для всех практических целей 10^?20 есть нуль, если элементы исходной матрицы равны в среднем 1/50 или больше. Существует, однако, точный способ оценки величины остаточных матриц L и R. Определим норму по строкам матрицы А как

Добавьте к своей программе, которая вычисляет обратную к матрице Гильберта, подпрограмму, печатающую таблицу |L|_r и |R|_r для каждой обратной матрицы. Проверьте вашу программу на отсутствие ошибок. Не сможете ли вы теперь объяснить, почему остаточные матрицы столь велики. Уверены ли вы в правильности программы?

Ваша программа правильна; причина неполадок — погрешность машинной арифметики. Матрицы Гильберта внешне выглядят вполне безобидно, однако они специально предназначены для демонстрации накопления ошибок в длинном ряду взаимосвязанных вычислений. Вы, быть может, считаете источником бед то, что ваш компьютер хранит недостаточное число цифр вещественных чисел. На многих ЭВМ имеется арифметика двойной точности. Предусмотрев в своем алгоритме двойную точность, вы сможете улучшить ситуацию, но заведомо не сможете полностью решить проблему. Весь этот этюд посвящен изучению влияния арифметики ограниченной точности на алгоритмы, которые являются абсолютно точными для «действительных» чисел (как их понимают математики). Прикладные математики и специалисты по численным методам в программистских лабораториях тратят большую часть времени на изменение теоретических алгоритмов, чтобы они могли работать на реальных ЭВМ[30].

Тема. Запрограммируйте алгоритм обращения матриц и проверьте его на матрицах Гильберта указанных выше порядков. Напечатайте таблицу или начертите график зависимости |L|_r и |R|_r от порядка n матрицы Hn. Если используемый вами язык допускает выбор точности чисел, то повторите вычисление обратных матриц с большей точностью, чтобы увидеть, улучшится ли в результате таблица или график ошибок. (Мудрый программист так составит программу, чтобы изменение точности достигалось путем замены небольшого числа деклараций.) Следите также за числом фактических перестановок строк при выборе ведущего элемента; оно будет показывать, насколько плохо алгоритм согласуется с теорией.

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

Инструментовка. Подойдет любой алгебраический язык. Фортран был создан для решения матричных задач. Сравните его с каким-нибудь более современным языком, запрограммировав этот этюд на обоих языках.

Длительность исполнения. Одному исполнителю на 1 неделю.

Развитие темы. Если в достаточной степени расширить задачу, то она послужит основой семестрового курса методов вычислений. Тем не менее вы можете получить дополнительную информацию о поведении ошибок, если вычислите |L| и |R| с использованием других норм, отличных от нормы по строкам, например нормы по столбцам:

Ниже определены нормы L₁, L₂ и L_?:

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