Упражнение #1.

Классический способ приближенного вычисления числа p, вероятно, известен вам из школьного курса геометрии, но на всякий случай напоминаем его. "Точное" значение p есть результат деления длины произвольной окружности на ее диаметр. Если в окружность фиксированного радиуса последовательно вписывать правильные многоугольники, начав, скажем, с квадрата, и удваивая на каждом шаге процесса число сторон, то очередное приближение для длины окружности получается как длина периметра соответствующего многоугольника. При этом с каждой очередной итерацией периметр все меньше отличается от окружности. Разница между искомой величиной и очередным приближением называется абсолютной невязкой. Стало быть, абсолютная невязка для приближенного значения числа p уменьшается с очередной итерацией. Разумеется, без знания точного значения нет возможности проверять, достаточно ли мала абсолютная невязка, чтобы удовлетворить заданной точности вычислений. Поэтому, взамен, проверяется невязка относительная, которая представляет собой разность, без знака, между двумя последовательными приближениями. Соответственно, процесс можно остановить по достижении относительной невязкой заданной точности. Например, для достижения в таком процессе часто используемого в вычислениях значения p = 3.14 следует дождаться, пока невязка станет меньше 0.01. Нельзя не отметить, что указанный способ получения большого количества разрядов в представлении числа p нельзя отнести к достаточно быстрым, и существуют гораздо более эффективные вычислительные механизмы. Тем более, представляет интерес вопрос, сколько в действительности требуется итераций для достижения некоторой, фиксированной точности. Таким образом, задача состоит в написании программы, которая по заданному радиусу окружности, требуемой точности вычисления искомого значения и начальному количеству сторон вписанного многоугольника устанавливала, сколько шагов потребуется для достижения цели.

Упражнение #2.

Похожий, по сути, механизм применяют для вычисления значения определенного интеграла. Постановка задачи: вычислить площадь под графиком непрерывной неотрицательной функции на заданном конечном интервале. В самой простой интерпретации механизм реализуется как метод левых прямоугольников. Идея состоит в том, что в качестве начального, нулевого, приближения для искомой площади назначается площадь прямоугольника, построенного на основании, равном длине интервала области определения функции, и на боковой стороне, равной ординате в левом конце этой области. На следующем шаге область определения разбивается ровно пополам, и в качестве очередного приближения принимается сумма двух прямоугольников, построенных из соответствующих полуинтервалов и левых ординат. Далее - вновь каждый из интервалов разбивается пополам и, соответственно, количество прямоугольников удваивается. Вычислительный процесс останавливается, когда разница между двумя последовательными приближениями становится меньше требуемой точности. Полагаем, читатель без особого труда сформулирует, что собой представляет метод правых прямоугольников, или метод средних прямоугольников. Стоит иметь в виду, что методы прямоугольников могут "плохо себя вести", например, когда функция быстро растет или имеет несколько локальных экстремумов. На практике, для ускорения сходимости итераций, применяют более совершенные механизмы, такие как метод трапеций, формулу Симпсона и другие, но эти темы - из сферы интересов вычислительной математики, а отнюдь не дискретной. Ваша задача состоит, естественно, в написании программы. Предлагается вычислить методом левых прямоугольников определенный интеграл для функции y=ax2+b на интервале [0,c], причем точность и параметры a, b и c>0 являются входными данными. В качестве ответа выдается количество необходимых итераций.

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