Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 4

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

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

Если использовать округление до ближайшего числа, помещающегося в разрядной сетке, то отдельные ошибки будут частично нейтрализовывать друг друга, но среднее квадратичное отклонение будет расти с ростом числа операций, оставляя возможность большой ошибки в окончательном результате. Если же использовать усечение, т.е. отбрасывание хвостовых цифр, а не округление, то это приводит к смещению ошибок в одном направлении и вероятность большой погрешности в окончательном результате увеличивается*). Как пример этого явления рас«) Автор, видимо, предполагает, чтонспользуемые арифметические действия— сложение чисел одного знака и умножение.

— Примеч. ред 14 смотрим вычисление выражения 0,8132 0,6135 0,2103, значение которого, округленное до восьми десятичных знаков после запятой, равно 0,10491829. Усечение произведения первых двух чисел до четырех знаков дает 0,4988, с ошибкой 0,9820 10 4 . Умножение 0,4988 на 0,2103 дает после усечения 0,1048, с ошибкой 0,9764 1О ч.

Накопленная ошибка составля~т 0,1183 . 10 з. Помимо возможности накопления ошибок в результате выполнения большого числа операций, существует еше опасность катастрофической потери знаков. Предположим, что два числа а и о отличаются лишь в последнем знаке.

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

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

Примеры такого рода будут приведены позже. В настоящее время проведен детальный анализ влияния ошибок округления для ряда простых основных алгоритмов, например, для используемых при решении систем линейных уравнений; Некоторые из этих результатов будут описаны более подробно в гл. 3. Очень эффективным зарекомендовал себя так называемый обратный анализ ошибок. Исполъзуемый при этом подход основывается на доказательстве того, что влияние ошибок округления эквивалентно определенному возмущению исходных данных задачи. Когда такой анализ удается провести, можно утверждать„что погрешность решения, обусловленная ошибками округления, не превосходит погрешности, вызванной определенными ошибками в исходной модели.

Вопрос о влиянии ошибок округления на решение в этом случае сводится к изучению зависимости решения от возмущения параметров модели. Другое обстоятельство, где "конечность" ЭВМ приводит к погрешности численного решения, связано с необходимостью замены непрерывных задач дискретными. Вот, простой пример. Для вычисления интеграла от непрерывной функции нужно знать значение подынтегралъной функции на всем интервале интегрирования, т.е.

на бесконечном множестве точек. В то же время при вычислении этого интеграла на ЭВМ используются значения подынтегральной функции только в конечном числе очек. Следовательно, даже если последующие арифметические операции будут выполняться точно, без каких-либо ошибок округления, все равно будет сушествовать ошибка, обусловленная дискретной аппроксимацией интеграла Ошибки такого типа обычно называют ошибками дискретизации или ошибками усечения. Эти ошибки, за исключением тривиальных случаев, всегда возникают при численном решении дифференциальных уравнений и других непрерывных задач.

Имеется еще один более общий тип ошибок, который в каком-то смысле близок к ошибкам дискретизации. В основе многих численных методов лежит идея итерационного процесса. В ходе такого процесса строится последовательность приближений к решению в надежде, что этн приближения сойдутся к решению; во многих случаях может быть дано математическое доказательство сходимостн. Однако на ЭВМ можно реализовать только конечное число таких приближений, поэтому мы вынуждены останавливаться, не достигнув математической сходимости.

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

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

Другим важнейшим фактором, помимо точности, рассматриваемым прн разработке методов решения математических моделей на ЭВМ, является эффективность. Под этим мы понимаем количество усилий, как человеческих, так и ЭВМ, которое необходимо затратить для решения данной задачи. Для большинства задач, таких как решение систем линейных алгебраических уравнений, имеется целый ряд возможных методов решения, причем некоторые из них восходят к методам, предложенным десятки, а то и сотни лет назад.

Ясно, что мы хотели бы выбрать такой метод который минимизировал бы время счета, давая при этом приемлемую для нас точность приближенного решения. Это, однако, оказывается удивительно сложной задачей, требующей учета целого ряда обстоятельств. Хотя часто оказывается возможным оценить время работы алгоритма, подсчитав необходимое число арифметических операций, вопрос о том, как решить задачу с заданным уровнем погрешности за минимальное время счета или с минимальным объемом вычислений, все еще, за исключением нескольких случаев, остается открытым.

Даже если пренебречь ошибками округления, известно удивительно немного. В последние несколько лет эти вопросы привели к возникновению нового предмета: сложность вычислений. Однако, если даже такие теоретические результаты были бы известны, они бы дали только приближенную оценку фактического времени счета, которое зависит от ряда факторов, связанных с используемой вычислительной системой: от объема и быстродействия основной н внешней памяти, числа обращений к внешней памяти и характеристик операционной системы.

И эти факторы все время изменяются в результате создания новых вычислительных систем или нх новой архитектуры. Фактически разработка и анализ численных методов должны побуждать и направлять эти изменения. Мы на простом примере покажем, как может возникнуть очень неэффективный метод. Во многих элементарных учебниках по теории матриц или линейной алгебре излагается правило Крамера решения систем линейных алгебраических уравнений.

Это правило связано с вычислением отношений некоторых определителей. Определители же, в свою очередь, обычно вводятся как сумма всех возможных произведений элементов матрицы, по одному элементу из каждой строки и каждого столбца. Всего имеется и! таких произведений. Если мы теперь приступим к вычислению определителя, непосредственно следуя приведенному определению, то нам потребуется (и — 1)л! умножений н л! сложений. Если применить такой метод к очень маленьким матрицам, скажем 3 Х 3 или 4 Х 4, ничего плохого не произойдет. Предположим теперь, что мы применим этот метод к матрице размерности 20 Х 20, являющейся небольшой для задач современного научного программирования.

Если считать, что на выполнение каждой арифметической операции требуется 1 мс (10 6 с), то требуемое для вычислений время, если даже пренебречь всеми вспомогательными операциями программы, превысит миллион лет! В то же время метод исключения Гаусса, который будет рассмотрен в гл, 3, выполнит все арифметические операции, необходимые для решения линейной системы порядка 20 Х Х 20, менее чем за 0,005 с (по-прежнему считая, что одна операция выполняется за 1 мс). Хотя это н исключительный пример, но он очень наглядно иллюстрирует те неприятности, которые могут возникнуть, если при решении задач на ЭВМ наивно следовать математическим рецептам. Но даже если метод сам по себе является хорошим, чрезвычайно важно, чтобы реализующая его программа для ЗВМ была составлена как можно лучше, особенно в том случае, если ею будет пользоваться не только автор программы.

Приведем некоторые критерии качественного программирования. 1. Надежность — программа не содержит ошибок и можно быть уверенным, что она вычисляет именно то, ради чего она составлена. 2. Работослособносгь, которая тесно связана с надежностью, — программа может обнаруживать неверные данные, выявлять "вырожденность" или какие-то другие обстоятельства, прн которых от программы нельзя ожидать правильных результатов, а также фиксировать прочие ненормаль.

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

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