Предисловие

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

Пособие условно разбито на 10 глав, в которых рассматриваются общие вопросы вычислительной математики (Введение), численные методы решения систем линейных и нелинейных уравнений, а также скалярных уравнений (главы I–III), задачи аппроксимации, интерполяции и равномерного приближения функций (главы IV–V), приближенное дифференцирование и интегрирование функций (главы VI–VII), численное решение дифференциальных уравнений (глава IX), а также разложение периодических функций в ряд Фурье (глава X). Каждая глава сопровождается контрольными вопросами и задачами для самостоятельного решения.

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

I. Введение

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

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

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

2. Погрешность метода. Это погрешность, связанная со способом решения поставленной математической задачи и появляющаяся в результате подмены исходной математической модели другой или конечной последовательностью других, например, линейных моделей. При создании численных методов закладывается возможность отслеживания таких погрешностей и доведения их до сколь угодно малого уровня. Отсюда естественно отношение к погрешности метода как к устранимой (или условной).

3. Погрешность округлений (погрешность действий). Этот тип погрешностей обусловлен необходимостью выполнять арифметические операции над числами, усеченными до количества разрядов, зависящего от применяемой вычислительной техники (если, разумеется, не используются специальные программные средства, реализующие, например, арифметику рациональных чисел).

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

Рассмотрим некоторые возможные подходы к учету погрешностей действий.

Пусть и — два «близких» числа; условимся считать – точным, – приближенным.

Величина называется абсолютной погрешностью приближенного числа , a его относительной погрешностью. Числа и такие, что и , называются оценками или границами абсолютной и относительной погрешностей соответственно (к и часто применяют также термин «предельные погрешности»). Так как обычно истинные погрешности не известны, то там где не может возникнуть недоразумений, будем иногда называть и просто абсолютной и относительной погрешностями.

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

(1.1)

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

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

,

т.е. такая же, как и у исходных данных. В то же время по формуле (1.1) имеем

.

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

Прямое применение вероятностно-статистических оценок погрешностей также является достаточно сложным делом и вряд ли может быть рекомендовано при рядовых массовых вычислениях. Однако именно такие оценки подкрепляют практические правила работы с приближенными числами, составляющие основу так называемого технического метода. Этот подход связывают с именем известного русского кораблестроителя, математика и механика академика А. Н. Крылова. Согласно принципу А. Н. Крылова, приближенное число должно записываться так, чтобы в нем все значащие цифры, кроме последней, были верными и лишь последняя была бы сомнительна, и притом в среднем не более чем на одну единицу. Напомним, что значащими цифрами числа в его позиционной записи называются все его цифры, начиная с первой ненулевой слева. Значащую цифру приближенного числа называют верной, если абсолютная погрешность числа не превосходит единицы разряда, в котором стоит эта цифра (или половины единицы; в этом случае иногда применяется термин верная в узком смысле).

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

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

2. при умножении и делении в результате следует сохранять столько значащих цифр, сколько их имеет приближенное данное с наименьшим числом значащих цифр;

3. результаты промежуточных вычислений должны иметь один–два запасных знака (которые затем должны быть отброшены).

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

В силу неизбежного появления погрешностей в исходных данных задачи (в процессе создания математической модели изучаемого объекта иди явления), а также погрешностей округления при ее решении, следует иметь представление о том, насколько чувствительными могут оказаться сами задачи и методы их решения к таким, погрешностям. Рассмотрим несколько примеров проявления чрезмерной чувствительности.

Пример 1.1. Пусть требуется найти вещественное решение уравнения

,

где – очень малое положительное число, а натуральное достаточно велико. Тогда естественно заменить нулем и положить . Так как точное решение данного уравнения есть , то абсолютная погрешность при таком подходе составит величину . Много это или мало – судить об этом можно, придавая и численные значения. Например, взяв , , получим абсолютную погрешность значения корня , равную 0,1. Относительная погрешность при этом может оказаться сколь угодно большой, если взять сколь угодно малым.

Пример 1.2. (пример Уилкинсона). Многочлен

имеет 20 хорошо отделимых действительных корней

.

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

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

Пример 1.3. Линейная система

имеет единственное решение , . Допустив абсолютную погрешность в 0,01 в правой части одного уравнения, получим возмущенную систему

с единственным решением , . Последнее никак не назовешь близким к решению исходной системы.

Пример 1.4. Для вычисления определенных интегралов вида

,

где , с помощью метода интегрирования «по частям» легко вывести рекуррентную формулу

. (1.2)

Существует сводная таблица результатов подсчета при по формуле (1.2), полученных в 60-х годах на разных вычислительных машинах в Чехословакии, Восточной Германии, России. Эта таблица наглядно демонстрирует рост разброса значений интеграла при увеличении значения . He приводя здесь полностью этих результатов, отметим лишь, что при спектр вычисленных значений интеграла лежит в границах от –148 до 5356. Несмотря на то, что на некоторых ЭВМ вычисления велись с мантиссами, имеющими более десяти десятичных разрядов, ни один результат не имел ни одной верной цифры! Причина подобного явления – в численной неустойчивости схемы (1.2). Безупречная в теоретическом плане, т.е. с точки зрения аналитической математики, она совершенно непригодна с позиций вычислительной математики, поскольку неизбежная погрешность стартового значения при подсчете увеличивается в раз, т.е. катастрофически нарастает.

Если примеры 1–3 указывали прямо на существование неустойчивых задач, то в четвертом примере видно яркое проявление неустойчивого метода вычислений. Последним, как правило, есть альтернативы. Например, для вычисления рассматриваемого там интеграла при конкретном значении можно применять квадратурные формулы, т.е. формулы, специально приспособленные для приближенного вычисления определенных интегралов. А можно воспользоваться и равенством (1.2), только переписать его в виде

. (1.3)

Учитывая, что и , для подсчета при некотором фиксированном (и для меньших этого индексов) можно задаться значением и вести счет по формуле (1.3) при . Так как начальная погрешность на каждом шаге теперь уменьшается в раз, то такой алгоритм будет численно устойчивым. Значение при этом может быть определено теоретически или экспериментально.