1.4. Устойчивость и сложность алгоритма (по памяти, по времени)

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

Например, математической моделью малых колебаний маятника может оказаться следующая задача:

,

y(0) = 0, (1.14)

где y(t) – отклонение маятника в момент времени t.

При изучении гармонических колебаний с помощью этой математической модели, т. е. задачи Коши (1.14), некоторую пользу может принести знание физической сущности моделируемого физического объекта. В данной задаче, например, можно предвидеть, что решение носит колебательный (периодический) характер. Однако математическая модель (1.14) после ее построения становится самостоятельным объектом, для изучения которого можно применять любые математические средства, в том числе и те, которые не имеют никакого отношения к физическому происхождению задачи. Это сильно расширяет возможности исследователя. Так, например, значение решения задачи (1.14) в заданной момент времениt = z, т. е. представление числа в виде десятичной дроби с заданным числом знаков, можно осуществить с помощью ряда

воспользовавшись его частичной суммой.

Между тем представление функции в виде степенного ряда, использованное нами, не имеет никакого физического смысла.

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

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

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

1. Алгоритм может быть точнее алгоритма , т. е.

.

Например, будем вычислять по формуле вида

(1.15)

Примем за алгоритм, отвечающий n =1, а за алгоритм, отвечающий n =2. Очевидно, что

.

2. Алгоритмы обладают одинаковой точностью, но вычисление требует много больше арифметических действий, чем вычисление.

Пусть, например, требуется найти

при х = 0,99. За примем алгоритм, осуществляющий вычисления прямо по заданной формуле, возводя0,99 поочередно в степени 1, 2, …, 1023 и складывая. В качестве примем алгоритм, осуществляющий вычисление по формуле

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

А именно, вычисляя последовательно придется проделать 1022 умножения. В то же время при вычислении требуется всего10 умножений:

.

3. Алгоритмы обладают одинаковой точностью, но вычислительно устойчив, анеустойчив.

Например, для вычисления с заданной точностьювоспользуемся суммой

(1.16)

где выбирается так, чтобы выполнялось неравенство

,

Приняв вычисления этой суммы за алгоритм . Если, то

.

При n = 5, и

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

Пусть ; например,х = 100. Тогда для достижения требуемой точности число n должно удовлетворять неравенству:

из которого для n заведомо выполнено неравенство n > 48. Но при вычислении суммы (16) первые ее члены будут очень большими. Малая относительная погрешность при их вычислении дает большую абсолютную погрешность, и алгоритм вычислительно неустойчив.

Укажем устойчивый алгоритм . Записываем заданноех в виде , (, l целое). Тогда

,

Этот алгоритм по устойчивости совпадает с алгоритмом для.

4. Алгоритм может быть сходящимся или расходящимся.

Пусть требуется вычислить . Воспользуемся рядом

(1.17)

и положим

Получим метод вычисления , зависящий от номера n как от параметра.

Если , то , т. е. погрешность алгоритма с ростом n стремится к нулю. Но если x > 1, то , так как ряд (1.17) имеет радиус сходимостиr =1. В этом случае алгоритм непригоден для вычислений.

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

Лекция № 3

2. ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ

Численные методы решения задач линейной алгебры в значительной степени объединяет система понятий и идентичность подходов к решению задач.

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

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

Для системы нелинейных уравнений приведено обобщение методов простой итерации, метода итераций Зейделя и метода Ньютона в приложении к одному нелинейному уравнению.