Материал: Методичка

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

Приведем некоторые факты из истории вычисления числа . Великий древнегреческий ученый Архимед дошел до вычисления периметров правильных 96-угольников и получил следующую двухстороннюю оценку : . К первой половине XV века в знаменитой обсерватории под Самаркандом придворный астроном Ал-Каши вычислил с 17 знаками после запятой. К концу XIX века английский математик В.Шенкс вычислил 707 знаков , затратив на это более 15 лет. В настоящее время с помощью ЭВМ число вычислено с точностью, измеряемой сотнями тысяч знаков.

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

Рис. 1.2. Этапы решения математических задач с применением ЭВМ.

Рассмотрим содержание представленных на рис. 1.2 этапов решения и исследования математических задач с использованием ЭВМ.

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

Составление математической модели объекта исследования. На данном этапе обычно строится континуальная математическая модель, сформулированная в терминах дифференциальных, трансцендентных или алгебраических уравнений для функций непрерывного аргумента. Такая модель является наиболее экономичным способом описания исследуемого объекта или явления.

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

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

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

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

Вычислительные эксперименты заключаются в том, что с использованием разработанной программы на основании наборов исходных данных производится необходимое количество расчетов на ЭВМ.

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

Содержание рассмотренных выше этапов «решения задачи» с помощью ЭВМ позволяет сделать следующие выводы:

1. ЭВМ задач не решает, она производит заранее определенную последовательность вычислений по заданному алгоритму.

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

Сформулируем наиболее важные проблемы вычислительной математики:

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

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

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

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

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

1.2. Общая постановка и понятие устойчивости задач вычисления

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

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

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

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

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

1.3. Структура погрешности решения задач вычисления

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

• погрешность математической модели;

• погрешность исходных данных задачи;

• погрешность метода решения задачи;

• погрешность реализации вычислений, включая погрешность округления.

Результирующая погрешность определяется величиной всех перечисленных выше погрешностей.

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

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

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

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

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

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

Пример 1.1. Определим дальность полета снаряда, выпущенного под углом к горизонту со скоростью , при следующих предположениях:

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

• ускорение свободного падения постоянно;

• кривизной земли можно пренебречь и считать ее плоской;

• действием воздуха на движущийся снаряд можно пренебречь.

Как известно из курса физики, при таких предположениях (выбранной схеме идеализации процесса) задача имеет достаточно простое решение:

,

причем снаряд движется по параболической траектории.

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

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