Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 8
Текст из файла (страница 8)
Постарайтесь избежать имеющихся здесь ловушек и сравните вашу подпрограмму со встроенной подпрограммой СТ!5!АКТ на следующем примере: 1 234 Х 10»г+ «2 345 Х 10»т. 2Л1. Вычислите сумму ряда 1 «р (х) ~~» „,+ а=! для х=О шаг О.! оп!.0 с ошибкой, не превышающей 0.5»10-а. Эвнг«ание! Эга задача требует как человеческого анализа, так н машинной вычислительной мощи, н одно без другого вряд ли приведет к успеху. Прежде всего не тратьте годовой бюджет ыашнннага времени, пытаясь просумынровать ряд «грубой силой».
(Сколько времени вам это стоило бы7) Ухи»ание! Используйте соотношение ! 1 1 л(4+1) л л+ ! йля доказательства того, чта !р(!)=-1. Затем представьте разность !р(х) — !р(1) рядом, который сходится быстрее исходного ряда, определяющего «р(х). Вам придется повторить этот трюк, прежде чем зы получите достаточно быстро сходнщийся ряд для вычисления ф(х).
Ссылка: Хемминг (1962), стр. 48 — 50. 2.12. Зта задача вычисления радов иллюстрирует невозможность использования современной вычислительной техники без предварительного анализа даже в простых случаях. Лля (х(<! хотим вычислить выражение » Ю '(") =Е )~ — '-Е, — ' а=! а=! с ошибкой, по модулю меньшей, чем е=ЗХ !О-г. а) Покажете, что каждый ряд сходится. б) Сколько примерно членов первого ряда потребуется, чтобы просумми.
ровать его с ошибкой, па модулю меньшей г7 в) Предполагая, что каждое слагаемое может быть вычислено за 500 микросекунд, оцените, сколько времени понадобится, чтобы в обоих рядах просуммировать то числа членов, которое определено в пункте б). г) С помощью алгебраических манипуляций перепишите выраженне для 3(х) так, чтобы его можно было вычислить быстрее.
З. ВЫЧИСЛЕНИЯ С ПЛЛВЛЮщей тОчКОЙ 42 е) Запрограммируйте ваш метод и вычислите 5 (х) для двух случаев: х=О. и х=0.999999999. Если удастся, заметьте время счета н сравните его со своей оценкой. 2.13. Во многих случаях аналитическое решение задачи приводит к необходимости вычисления ряда. Вычислите ряд л=! с ошибкой, меньшей единицы десятого десятичного значащего разряда. Указание: 1 пз пе л=! Предупреждение: не тратьте понапрасну машинное время, суммируя ряд, в скорости сходимости которого вы не уверены.
2,14. Задача для самасшоятелькоео исследо!алия Напишите фортран-подпрограмму для решения квадратного уравнения ах'+Ьх+с=О, где а, Ь, с — числа с плавающей точкой и с двойной точностью, Алгоритм дол- жен как можно ближе соответствовать идеалам, обсуждавшимся в 5 2.б. Замеюлие: Существуют две основные трудности: 1.
Нужно считаться с возможными переполнениями и машинными нулями. Это очень серьезно главным образом потому, чта ФОРТРАН не дает программе пользователя пинаких средств для того, чтобы обнаружить машинный нуль или переполнение и предпринять спасательные меры. Подпрограмма должна сама проверять, возможны лн они, и предусматривать предупредительные действия. 2.
Даже если переполнения и машинные нули невозможны, есть случаи, когда удовлетворительную точность нельзя получить без вычисления днскриминанта Ьз — 4ас с точностью, нревосходящей рабочую точность арифметики; действительно, если корень должен иметь Л' верных знаков, то все соответствующие знаки в Ьгд' — 4ас также должны быть верны. Это может привести вас к желанию вычислять Ъз — 4ж с учетверенной точностью. Для этого требуется несколько особое программирование.
В статье Леккера (!971) имеются на этот счет полезные программистские предложения, 3. ЛИНЕЙНЫЕ СИСТЕМЫ УРАВНЕНИЙ Одна из задач, наиболее часто встречающихся в научных вычислениях,— решение системы линейных уравнений; при этом обычно число уравнений равно числу неизвестных. Такую систему можно записать в виде Ах=Ь, где А — заданная квадратная матрица порядка п, Ь вЂ” заданный вектор-столбец с а компонентами и х — неизвестный вектор- столбец с и компонентами, Источники линейных уравнений включают аппроксимацию непрерывных дифференциальных или интегральных уравнений конечными, дискретными алгебраическими системами, локальная линеаризация систем нелинейных уравнений, построение полиномов или кривых какого-либо иного специального вида по заданной информации.
Некоторые нз этих приложений будут обсуждены в последующих главах. Лица, изучающие линейную алгебру, знакомятся с методами решения невырожденных систем линейных уравнений. Метод, который часто приводится в таких курсах,— это правило Крамера, согласно которому все компоненты решения представляются отношениями определителей с различными числителями и общим знаменателем. Если бы вы попробовали решить систему из 20 уравнений с помощью правила Крамера, то вам потребовалось бы вычислить 21 определитель порядка 20. Определитель матрицы А =-(а,~) обычно вводится как сумма членов вида -~-а, а, ... а,, где пропущенные индексы нужно заполнить произвольной перестановкой целых чисел 1, ..., и.
В данном случае в сумме имеется 201 членов и каждый требует 19 умножений. Следовательно, решение линейной системы предполагает 21 х 20! х 19 умножений плюс примерно такое же число сложений. На современной быстродействующей вычислительной машине можно выполнить около 100 000 умножений в секунду. Таким образом, только одни умножения потребуют приблизительно 44 3. ЛИНЕЙНЪ|Е СИСТЕМЫ УРАВНЕНИЙ 3х!0' лет при условии, что машина не сломается в процессе вычислений. Имеются гораздо лучшие способы вычисления определителей; однако при хорошем выборе метода линейную систему возможно решить примерно за то же время, которого требует вычисление одного определителя. Кроме того, правило Крамера зачастую ведет к чрезмерным ошибкам округлений. Лица, изучающие линейную алгебру, узнают также, что решение системы Ах=-Ь можно представить в виде х=А-'Ь, где А-' — матрица, обратная для А. Однако в огромном большинстве практических вычислительных задач вовсе не обязательно и даже нежелательно в действительности находить А-'.
В качестве крайнего, но поучительного примера рассмотрим систему, состоящую ровно из одного уравнения; например, 7х=2! . Наилучший способ решения этой задачи — делеииех 21 х = — =3. 7 Использование обратной матрицы привело бы к х=7 '21 = (. 142857) (21) = 2. 99997. Второй способ требует больше арифметики — деление и умножение вместо одного деления — и дает менее точный результат. Однако лишние действия — это главная причина, по которой мы рекомендуем избегать обращения.
Все сказанное справедливо и для систем с многими уравнениями. Зто же остается верным и в распространенной ситуации, когда имеется несколько систем уравнений с одной и той же матрицей А, но различными правыми частями Ь. Вследствие этого обратим главное внимание на прямое решение снстем уравнений, а не на вычисление обратной матрицы. Важно различать два типа матриц: 1. Хранимая матрица, т. е. матрица, все и' элементов которой хранятся в оперативной памяти машины.
Зто ограничивает порядок п примерно значением 100 для машин средней мощности и несколькими сотнями на больших машинах. 2. Разреженная матрица, т. е, матрица, большинство элементов которой — нули, а ненулевые элементы могут или храниться посредством какой-либо специальной структуры данных или регенерироваться по мере необходимости. (Ь4атрицы этого типа часто происходят из конечно-разностиых и конечно-элементных методов для дифференциальных уравнений с частными производными.) Порядок и зачастую достигает нескольких десятков тысяч, а иногда н того больше. ХЬ ЛИНЕЙНЫЕ СИСТЕМЫ С ХРАНИМЫМИ МАТРИЦАМИ 4$ Приведем пример разреженной матрицы, элементы которой легко могут быть восстановлены: 4 1 О 0 О 0 0 1 4 1 О О О О О 1 4 1 0 0 0 О О 1 4 1 0 О 0 О 0 1 4 1 О 0 0 0 0 1 4 1 О 0 О О О 1 4 Эти два типа матриц в известной степени пересекаются.
Хранимая матрица может иметь много нулевых элементов и, следовательно, быть в то же время разреженной; однако, если для нулевых элементов отводится место в оперативной памяти, то разреженность матрицы не важна. Очень большая неразреженная матрица может храниться во внешней памяти, на диске или ленте, и вследствие этого требовать более изощренных приемов обработки. Ленточная матрица — это матрица, все ненулевые элементы которой находятся вблизи главной диагонали; точнее, аы=О для всех 1, 1, таких, что |! — 1~)т, где тс~п. Шириной ленты называется число 2т+1, и ненулевые элементы размещаются на 2т+1 диагоналях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
