4.2. ПОРЯДОК ИНТЕРПОЛЯЦИОННЫХ ИТЕРАЦИОННЫХ ФУНКЦИЙ

4.2.1. Порядок итерационных функций, порождаемых обратной интерполяцией.

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

В равенстве (4.6) положим Тогда

где Введем обозначение . Соотношение (4.7) можно переписать, используя или В самом деле, где лежит в интервале между Поэтому

где Очевидно, откуда следует, что

Если погрешности отличны от нуля и производная не обращается в нуль в пределах интервала,

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

для всех или, что то же самое, для всех Пусть Тогда Покажем теперь, что если

то при всех В самом деле, поскольку то С учетом (4.10) получаем

Продолжим доказательство по индукции. Пусть при Тогда

и индукция завершена. Поскольку то для всех номеров

Рассуждая аналогичным образом, можно показать, что Поступим проще: заметим, что

отсюда с учетом леммы 3.1 следует

Лемма 4.1. Пусть производная непрерывна, производная не обращается в нуль на интервале и

Тогда из условия следует, что

4.2.2. Случай стандартной информации.

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

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

Предположим, что условия леммы 4.1 выполняются при Тода для всех где

Таким образом, выполнены все условия теоремы 3.3, из которой следует, что

(через обозначен единственный положительный корень уравнения при этом Кроме того, где Следовательно,

Заметим, что с учетом соотношений утверждения (4.13) и (4.14) эквивалентны.

Результаты, относящиеся к сходимости и порядку порождаемых обратной интерполяцией ИФ, объединяет

Теорема 4.1. Пусть на интервале производная непрерывна, а произведение не обращается в нуль. Пусть, кроме того, а последующие элементы последовательности определяются по правилу

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

Тогда для всех и

где единственный положительный корень уравнения

Утверждение (4.15) эквивалентно следующему:

В заключение этого пункта сделаем несколько замечаний.

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

При функция относится к классу одноточечных ИФ, а при к классу одноточечных ИФ с памятью. Целый порядок имеют только одноточечные ИФ «без памяти», т. е. при

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

Значения для различных можно получить из табл. 3.1, полагая

4.2.3. Порядок итерационных функций, порождаемых прямой интерполяцией.

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

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

Эту процедуру повторим затем применительно к набору

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

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

Лемма 4.2. Пусть производная непрерывна, производная не обращается в нуль на интервале для всех х из а

Пусть, кроме того, расположены в интервале по одну сторону от а. Тогда многочлен имеет в интервале вещественный корень

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

где расположено в интервале, заданном точками Тогда

где Применяя теорему о среднем, получаем

где расположено между Отсюда видно, что как только

Неравенства завершают доказательство леммы.

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

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

Тогда многочлен имеет вещественный корень удовлетворяющий неравенствам

Доказательство. В зависимости от знаков доказательство сводится к независимому рассмотрению четырех случаев. Продемонстрируем идею доказательства на примере двух из них.

Случай 1: Достаточно доказать, что Запишем представление (4.3) в виде

Очевидно,

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

Случай 2: Достаточно доказать, что Ввиду

В рассматриваемом случае поэтому неравенство эквивалентно неравенству — Последнее неравенство в свою очередь эквивалентно любому из двух неравенств:

Пусть выполнены условия предыдущей леммы. Тогда при имеем

а при

Предположим, что выполнено (4.22). Тогда последовательность монотонно убывает и ограничена снизу. Следовательно, она имеет предел и

Обозначим этот предел через и положим в Тогда с учетом получаем

где При из (4.24) следует, что Так как по предположению то поэтому Аналогичный вывод справедлив и в случае (4.23). Подытожим проведенные рассуждения.

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

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

Этот результат хорошо известен для ИФ Ньютона (при ). В этом случае условия теоремы 4.2 носят название условий Фурье (Fourier [4.2-1]). Теорема 4.2 существенно обобщает этот результат Фурье. Заметим, что условия Фурье, будучи геометрически очевидными в случае метода Ньютона, в общем случае отнюдь не являются очевидными.

Отметим, что условия теоремы 4.2 не накладывают, за исключением условия никаких других ограничений на размер интервала, в котором гарантируется монотонная

сходимость. Нетрудно видеть, что при все точки автоматически располагаются по одну сторону от а. Если же ни одно из условий (4.25) и (4.26) не выполняется, то на размер интервала, в котором гарантируется сходимость, приходится накладывать ограничения. Так, на примере леммы 4.2 мы уже видели, что для наличия у многочлена вещественного нуля в интервале необходимо накладывать ограничение на длину интервала.

При доказательстве сходимости в общем случае вновь исходим из формулы

откуда

Предположим, что выполняются условия леммы 4.2. Тогда найдется вещественное такое, что Справедливо соотношение где расположено между а и Поэтому

Допустим, что производная не обращается в нуль в промежутке между а и В таком случае

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

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

где Теперь из леммы 3.1 следует, что если то

Отметим, что в данном случае зависит от поэтому здесь неприменим прием, использованный при доказательстве леммы 4.1.

В силу того что имеем где Таким образом, выполняются все условия теоремы 3.3. Поэтому

где единственный положительный корень уравнения

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

Теорема 4.3. Пусть производная непрерывна на интервале произведение не обращается в нуль на этом интервале, для всех причем

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

Предположим, что для всех х из промежутка между а и причем где

Тогда для всех и

где единственный положительный корень уравнения

Замечание. Точка удовлетворяющая условиям теоремы, может быть не единственной; для однозначности требуются дополнительные условия.

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

Отметим поразительное совпадение формы соотношений (4.30) и (4.15). В обоих случаях единственными использованными параметрами являются

При функция относится к классу одноточечных ИФ, а при к классу одноточечных ИФ с памятью.