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

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

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

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

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

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

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

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

Конт, де Боор (Conte S. D., de Boor С). Elementary Numerical Analysis, 2nd ed. McGraw-Hill, New York, NY, 1972.

Стьюарт (Stewart G. W.). Introduction to Matrix Computations. Academic Press, New York, NY, 1973.

Конт и де Боор написали превосходный учебник по основам методов вычислений, используемый во многих учебных заведениях. Он содержит куда больше информации по методам вычислений, чем могло бы понадобиться любому нормальному человеку. Если вы все же хотите узнать еще больше о задаче с матрицами, обратитесь к книге Стьюарта. Там описаны теория и практика линейной алгебры.

* Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. Пер. с англ. — М.: Мир, 1976, упр. 1.2.3.45.

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

Математику часто считают сухой наукой, однако и математику творили люди. Одной из самых печальных была судьба Уильямса Шенкса, жившего в девятнадцатом веке и посвятившего себя вычислению числа ? с высокой точностью. Закончив многолетний труд, Шенкс в 1837 г. опубликовал значение ? до 707- го десятичного знака, впоследствии исправив некоторые знаки. Может быть, надо счесть за благо, что Шенкс умер в 1882 г., поскольку в 1946 г. было показано, что его вычисления ошибочны начиная с 528-го десятичного знака. Фактически Шенкс не продвинулся дальше своих предшественников.

Полученное Шенксом значение было проверено, вероятно, с помощью механических устройств, а компьютер был впервые использован для вычисления ? только в 1949 г.; это была машина ENIAC. Даже тогда проект был монументальным. Джорж У. Рейтуиснер писал: «Поскольку получить машину в рабочее время было практически невозможно, мы воспользовались разрешением выполнить эту работу за 4 выходных дня в период летних отпусков, когда ENIAC стоял без дела». Собственно вычисления (не программирование!) заняли 70 часов: было получено несколько больше 2 000 цифр. Все это время приходилось постоянно обслуживать компьютер, поскольку из-за ограниченности его возможностей требовались постоянная перфорация и ввод промежуточных результатов. Те первые программисты так же далеки от нынешних, как Шенкс далек от них.

Как бы мы стали вычислять ?? Во-первых, необходимо выражение, которое можно вычислять. Ряд

?/4 = 1 ? 1/3 + 1/5 ? 1/7 + 1/9 ? …

довольно прост для понимания, но он ужасно медленно сходится. Гораздо лучше ряд для арктангенса

arctg x = x ? х3/3 + х5/5 ? х7/7 + …, |x| ? 1

Объединим его с формулой сложения для тангенса

tg (a + b) = (tg a + tg b)/(1 ? tg a · tg b)

и выберем а и b так, чтобы tg (a + b) = 1 = tg ?/4. (Учитывая, что tg (arctg x) = х для ??/2 < х < ?/2, можно взять, например, а = arctg (1/2), b = arctg (1/3).)

Тогда

arctg (tg (a + b)) = a + b = arctg 1 = ?/4,

и теперь можно использовать приведенный выше ряд для нахождения a и b. На практике чаще всего используются следующие суммы:

?/4 = 4 arctg (1/5) ? arctg (1/239),

?/4 = 8 arctg (1/10) ? 4 arctg (1/515) ? arctg (1/239),

?/4 = 3 arctg (1/4) + arctg (1/20) + arctg (1/1985).

Теперь мы собираемся просуммировать эти ряды на ЭВМ. Как известно, все, что нужно для суммирования, — это простой итерационный цикл, но тут возникает одна проблема. Точность вычислений на ЭВМ ограничена, а весь смысл этого упражнения в том, чтобы найти много-много цифр числа ?, значительно превзойдя обычную точность. Первое, что приходит в голову, — промоделировать ручные методы выполнения арифметических действий. Будем представлять числа очень большими целочисленными массивами (по одной десятичной цифре в каждом элементе), тогда ясно, как составить программы сложения, вычитания и умножения. Запрограммировать ручной метод деления несколько сложнее, но все же возможно. Неприемлемым, однако, оказывается время выполнения алгоритмов. Хотя на это редко обращают внимание, но при ручных методах для умножения или деления n-значных чисел требуется время, пропорциональное n?. Если речь идет об операциях над числами из тысяч цифр, то такие расходы будут нам не по карману. К счастью, имеются лучшие алгоритмы.