1.2. ОСНОВНЫЕ ПОНЯТИЯ И ОБОЗНАЧЕНИЯ

1.2.1. Некоторые понятия и обозначения.

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

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

Мы ограничимся рассмотрением случая, когда вещественная однозначная функция вещественного аргумента, производные которой вплоть до некоторого порядка непрерывны в окрестности вещественного нуля а. Условие вещественности нуля не играет принципиальной роли. Всюду, за исключением гл. 11, f является скалярной функцией скалярного аргумента; в гл. 11 функция вектор-функция векторного аргумента.

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

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

Нуль а имеет кратность если

причем функция ограничена в окрестности точки а и Мы будем всегда предполагать, что целое положительное число. Случай, когда не является натуральным, рассматривается в книге Ostrowski [1.2-2, Chap. 5]. Если

то называется простым нулем; если же то называется кратным нулем.

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

Данный алгоритм бисекции является примером одноточечной итерационной функции с памятью (строгие определения приводятся ниже). Поскольку алгоритм не использует данных, характеризующих структуру (например, значения ее производных), скорость его сходимости невелика. В то же время гарантируется сходимость метода. Для ускорения сходимости привлекаются различные свойства (см., например, Gross, Johnson [1.2-3], Hooke, Jeeves [1.2-4], Lehmer [1.2-5]). В статье приводится оптимальная стратегия поиска максимума унимодальной функции.

Использование дополнительной информации об позволяет добиться существенного ускорения сходимости по сравнению с алгоритмом бисекции. Естественной и легко вычисляемой информацией являются значения самой функции и значения ее производных. В дальнейшем наряду с термином «информация» будем использовать термины «данные» и «испытание» (sample).

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

Определенную таким образом функцию будем называть итерационной функцией. В дальнейшем вместо термина

«итерационная функция» как в единственном, так и во множественном числе будет использоваться аббревиатура ИФ, Положим

Мы будем также писать вместо и вместо

Поскольку в точке используется информация о значениях функции и ее производных, правомерна и такая запись:

Однако мы не будем заниматься ИФ столь общего вида; классы изучаемых в дальнейшем ИФ определены в п. 1.2.2.

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

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

а вторая —

Первую мы будем в дальнейшем называть ИФ Ньютона. ИФ метода секущих тесно связана с методом regula falsi. При определении последнего предполагается сохранение двух аппроксимаций, «объемлющих» корень, в то время как ИФ метода секущих использует две последние аппроксимации.

Во многих случаях мы будем иметь дело не с самой функцией а с ее нормированным аналогом

Если то и не определено. При (случай кратного нуля) положим В дальнейшем изложении и играет исключительно важную роль. Одна из причин этого состоит в том, что в случае кратного нуля

Что касается простых нулей, то для них

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

Для удобства дальнейшего изложения введем дополнительные обозначения:

Таким образом, погрешность аппроксимации. Положим

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

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

где причем для всех Тогда

поскольку Аналогично поскольку

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

Так, обозначает внутренность единичного интервала.