Журнал вычислительной математики и математической физики, 2019, T. 59, № 6, стр. 920-936

1. ВВЕДЕНИЕ

В настоящее время существует много итерационных методов для решения нелинейных уравнений и систем уравнений (см. [1]–[6]). В частности, необходимы методы, не содержащие производные, когда невозможно или затруднительно найти производную функции. Самый простой из них – хорошо известный метод секущих и метод Стефенсона с низким порядком сходимости. В настоящее время весьма важно получить новые оптимальные методы с восьмой степенью сходимости, потому что их индекс эффективности равен ${{8}^{{1/4}}} \approx 1.682$. Такие методы имеют приложения в экспериментальной математике, в теории чисел, в физике высоких энергий, в нелинейном процессе моделирования, в конечном элементе моделирования CAD, в 3D графике, в статистике, безопасности, в криптографии (см. [7]–[9]). В последнее десятилетие были разработаны различные двух- и трехточечные методы, не содержащие производные, с хорошими свойствами сходимости (например, см. [1]–[24], [25]–[33]). Построение итерационных методов высокого порядка сходимости стало возможным благодаря быстрому развитию компьютера, успехам компьютерной арифметики и символьных вычислений. В данной работе предлагаются некоторые семейства итерационных методов, не содержащих производные, основанных на методе производящих функций, предложенном в [5] и оптимальном выборе параметров итераций [6]. Предлагается новый и прямой подход к доказательству порядка сходимости методов без использования символьных вычислений.

Структура работы следующая. В разд. 2 рассмотрены двухточечные итерационные методы, не содержащие производные, и получены необходимые и достаточные условия для того, чтобы они были четвертого порядка сходимости. Предложены также выборы производящих функций для итерационного параметра $\tau $. В частности, получены оптимальные конечно-разностные варианты известных методов Кунга–Трауба, Кинга и Махешвари. В разд. 3 рассмотрены трехточечные итерационные методы, не содержащие производные, и получены также необходимые и достаточные условия для того, чтобы они были восьмого порядка сходимости. Предложен широкий класс оптимальных трехточечных итераций, который содержит в себе много известных методов как частные случаи. Доказана локальная сходимость методов, не используя символьных вычислений. В разд. 4 представлены результаты численных экспериментов, которые подтверждают теоретический вывод о порядке сходимости и сделаны сравнения с другими известными методами.

2. ДВУХТОЧЕЧНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ, НЕ СОДЕРЖАЩИЕ ПРОИЗВОДНЫЕ

Рассмотрим следующие двухточечные итерации, не содержащие производные

где $\gamma $ – свободный ненулевой параметр, и ${{\bar {\tau }}_{k}}$ – параметр, который необходимо определить должным образом. Здесь функция $\phi (x) \equiv \phi (x,\gamma )$ зависит не только от $x$, но и от параметра $\gamma $, и по определению производной имеем Для определения порядка сходимости итераций (2.1a), (2.1b) обозначим Пусть $f(x) \in {{C}^{3}}(I)$, где $I$ – интервал, содержащий корень $x{\kern 1pt} {\text{*}}$ уравнения $f(x) = 0$. Тогда разложения Тейлора функций $f({{y}_{k}})$ и $f({{x}_{k}} + \gamma f({{x}_{k}}))$ дают Подставляя (2.6) в (2.4), получаем или Принимая во внимание (2.8) в (2.5), имеем Как в [6], используем обозначение Из (2.9), (2.10) следует, что ${{\theta }_{k}} = O(f({{x}_{k}}))$. Используя (2.5) в (2.10), получим Исключение $\tfrac{{f{\kern 1pt} ''({{x}_{k}})f({{x}_{k}})}}{{f{\kern 1pt} '({{x}_{k}})}}$ из (2.7) и (2.11) дает Из (2.12) видно, что ${{w}_{k}}$ зависит от ${{\theta }_{k}}$. В силу (2.8) можно искать ${{w}_{k}}$ в виде Подставляя (2.13) в (2.12), имеем Из (2.14) следует, что Подставляя (2.15) в (2.13), имеем С другой стороны, разложение Тейлора функции $f({{x}_{{k + 1}}})$ дает В силу (2.1a) имеем Исключение члена $\tfrac{{f{\kern 1pt} ''({{x}_{k}})f({{x}_{k}})}}{{f{\kern 1pt} '({{x}_{k}})\phi ({{x}_{k}})}}$ из (12) и (19) дает Подставляя ${{w}_{k}}$, из (2.16) в (2.19) и используя известное разложение получаем Используя (2.21) в (2.17), имеем

Теперь можно доказать следующее:

Теорема 1. Пусть $f(x) \in {{C}^{3}}(I)$ и начальное приближение ${{x}_{0}}$ достаточно близко к простому нулю $x{\kern 1pt} * \in I$ функции $f(x)$. Тогда итерационный метод (2.1) имеет четвертый порядок сходимости тогда и только тогда, когда параметр ${{\bar {\tau }}_{k}}$ в (2.1) удовлетворяет условию

Доказательство. Предположим, что ${{\bar {\tau }}_{k}}$ в (2.1) удовлетворяет условию (2.23). Тогда

и $f({{y}_{k}}) = O({{f}^{2}}({{x}_{k}}))$ из-за (2.8). Следовательно, в силу (2.22), имеем т.е. порядок сходимости (2.1) равен $4$ при условии (2.23). Обратно, пусть метод (2.1) имеет четвертый порядок сходимости, то есть, (2.24) верно. Тогда из (2.24) и (2.22) следует, что $f({{y}_{k}}) = O({{f}^{2}}({{x}_{k}}))$ и $1 - (1 - {{\hat {d}}_{k}}{{\theta }_{k}}){{\bar {\tau }}_{k}} = O({{f}^{2}}({{x}_{k}}))$, т.е. ${{\bar {\tau }}_{k}}$ удовлетворяет условию (2.23).

Итерационный метод (2.4) использует на каждом шаге итерации значения $f({{x}_{k}}),f({{y}_{k}})$ и $\phi ({{x}_{k}})$, поэтому он оптимален в смысле гипотезы Кунг–Трауба. Второй шаг в (2.1) можно переписать как

где Если $\phi ({{x}_{k}},\gamma ) = f{\kern 1pt} '({{x}_{k}}),\;\gamma \to 0$, то ${{w}_{k}} = 1$ и формулы (2.23) и (2.26) принимают вид соответственно. Итак, итерация (2.1) имеет вид и является оптимальной двухточечной итерацией четвертого порядка [6]. Как и в [5], метод производящих функций применим также для построения новых итераций (2.1). Конечно, имеются различные варианты производящих функций ${{\bar {\tau }}_{k}} = H({{\theta }_{k}})$, удовлетворяющих условиям Здесь рассматривается одна простая форма Теперь рассмотрим некоторые интересные случаи $H$.

1. Пусть $c = 1$, $d = \beta - 2$, $b = \omega = 0$ в (2.29). Тогда получим

Итерация (2.1) с выбором ${{\bar {\tau }}_{k}} = H({{\theta }_{k}})$ имеет вид Когда $\gamma \to 0$, итерация (2.30) дает хорошо известный метод Кинга. Назовем итерацию (2.30) конечно-разностным (КР) вариантом метода Кинга.

2. Пусть $c = b = 1$, $d = - 2$ и $\omega = 0$ в (2.29). Тогда получим

Итерация (2.1) с таким выбором ${{\bar {\tau }}_{k}} = H({{\theta }_{k}})$ имеет вид При $\gamma \to 0$ итерация (2.31) дает хорошо известный метод четвертого порядка метода Кунга–Трауба. По этой причине назовем итерацию (2.31) КР-вариантом метода Кунга–Трауба.

3. Пусть $c = 1$, $\omega = d = - 1$ и $b = 0$ в (2.29). Тогда получим

Итерация (2.1) с таким выбором ${{\bar {\tau }}_{k}} = H({{\theta }_{k}})$ имеет вид Когда $\gamma \to 0$, итерация (2.32) дает метод Махешвари. По этой причине назовем итерацию (2.32) КР-вариантом метода Махешвари.

Следует отметить, что авторами статьи [30] была сделана попытка распространить методы Кунга и Трауба на варианты, не содержащие производные. Но полученный в [30] метод отличается от наших расширений (2.30) и (2.31).

Таким образом, используя метод производящих функций, получаем широкий класс оптимальных двухточечных методов без производных (2.1) с ${{\bar {\tau }}_{k}} = H({{\theta }_{k}})$, заданным формулой (2.29). Этот класс включает пять параметров $(\gamma ,c,d,b,\omega )$. Коэффициенты в (2.29) могут зависеть от номера итераций $k$. Следует отметить, что многие двухточечные методы, не содержащие производные, были построены в [1], [2], [7], [14]–[18]. Наш класс итераций (2.1) с параметром ${{\bar {\tau }}_{k}}$, заданный по формуле (2.29), содержит некоторые хорошо известные итерации как частные случаи. В табл. 1 перечислены некоторые из них. Только ${{\bar {\tau }}_{k}}$ в методе Рен и др. [16], [34] не принадлежит классу $H({{\theta }_{k}})$, заданному по формуле (2.29). Таким образом, можно считать, что наше семейство (2.1) с параметром, заданным по формуле (2.29), является существенным обобщением методов, предложенных в работах [2], [7], [9], [11]–[18], [20]–[23], [26], [27].

Двухточечная итерация (2.1) содержит один свободный ненулевой параметр $\gamma $. Хорошо известно, что ускорение скорости сходимости достигается за счет подходящего варьирования свободного параметра на каждом шаге итерации $\gamma = {{\gamma }_{k}}$. Этот подход полезен при построении итераций высокого порядка с памятью, (см. [9], [22], [23], [25]). Теперь попытаемся найти оптимальный выбор свободного параметра с точки зрения точности. Рассмотрим разложение Тейлора функции $f({{\eta }_{k}}) = f({{x}_{k}} + \gamma f({{x}_{k}}))$ в окрестности ${{x}_{k}}$

Отсюда ясно, что можно выбрать $\gamma $ переменным способом, таким как Тогда соотношение (2.33) принимает вид где Следовательно, значение ${{\eta }_{k}}$, заданное по формуле (2.36), можно рассматривать как новое приближение лучше, чем ${{x}_{k}}$, в силу (2.35). С учетом (2.34) и (2.35) формулы (2.5) и (2.7) принимают вид соответственно. Подставляя (2.38) в (2.37) и используя (2.35), получаем Пусть параметр ${{\bar {\tau }}_{k}}$ выбран по формуле Затем, используя (2.39) и (2.40) в (2.22), получим Это означает, что выбор переменного параметра (2.34) существенно ускоряет двухточечный метод (2.1). Порядок сходимости увеличивается от $4$ до $6.$ В этом случае итерация (2.1) фактически является трехточечной, т.е. Если заменим ${{\gamma }_{k}} = - \tfrac{1}{{f{\kern 1pt} '({{x}_{k}})}} \approx - \tfrac{1}{{N_{3}^{'}({{x}_{k}})}}$, то получим двухточечные итерации с памятью (${{x}_{0}}$, ${{\gamma }_{0}}$ заданы). Тогда ${{\eta }_{0}} = {{x}_{0}} + {{\gamma }_{0}}f({{x}_{0}})$ и Здесь через ${{N}_{3}}(t) = {{N}_{3}}(t,{{x}_{k}},{{x}_{{k - 1}}},{{y}_{{k - 1}}},{{\eta }_{{k - 1}}})$ обозначен интерполяционный многочлен Ньютона третьей степени, заданный через узловые точки ${{x}_{k}}$, ${{x}_{{k - 1}}}$, ${{y}_{{k - 1}}}$, ${{\eta }_{{k - 1}}}$ [9], [23]. Очевидно, что $R$-порядок методов (2.43) равен, по крайне мере, шести.

Следует упомянуть, что иногда использовались несимметричные итерации, не содержащие производные, требующие дополнительных вычислений. Например, в [33] были предложены оптимальные итерационные семейства методов типа Кинга

где $f[{{x}_{k}},{{\eta }_{k}}]$ – первая разделенная разность. Второй подшаг в (2.44) можно переписать как где т.е. в этом случае ${{\bar {\tau }}_{n}}$, определяется более сложной формулой, чем в (2.30). Более того, при $\gamma \to 0$, имеем в то время как в (2.30). Второй пример КР-варианта оптимального семейства Хансена–Патрика, предложенный в [32], можно записать в виде где Устраняя несимметричность в (2.47), рассмотрим следующие итерации: где, как и раньше, ${{\bar {\tau }}_{k}}$, определяется по формуле (2.48). Легко доказывается

Теорема 2. Пусть $f(x) \in {{C}^{3}}(I)$ и имеет простой нуль $x{\kern 1pt} * \in I.$ Если начальное приближение ${{x}_{0}}$ достаточно близко к $x{\kern 1pt} * \in I$, то итерационный метод (2.49) имеет оптимальную сходимость четвертого порядка, когда

Доказательство. Предположим, что $H(0) = a,\quad H{\kern 1pt} '(0) = b.$ Тогда из (2.48) получаем

Сравнение последнего с достаточным условием сходимости (2.23), дает Следовательно, по теореме 1 итерация (2.49) имеет четвертый порядок сходимости при условии (2.50).

3. ТРЕХТОЧЕЧНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ, НЕ СОДЕРЖАЩИЕ ПРОИЗВОДНЫЕ

Рассмотрим трехточечные методы, не содержащие производные,

которые получаются из трехточечных методов в [6] заменой $f{\kern 1pt} '({{x}_{k}})$ на $\phi ({{x}_{k}})$. Отметим, что первые два шага в (3.1) определяют оптимальные двухточечные методы четвертого порядка, когда ${{\bar {\tau }}_{k}}$ задается формулой (2.23). Наша цель – найти ${{\alpha }_{k}}$, так чтобы порядок сходимости итераций (3.1) равнялся восьми. С этой целью используем разложение Тейлора $f({{x}_{{k + 1}}})$: Из последнего соотношения ясно, что при условии Теперь аппроксимируем $f{\kern 1pt} '({{z}_{k}})$ в (3.4), используя имеющиеся данные $f({{x}_{k}})$, $f({{y}_{k}})$, $f({{z}_{k}})$ и $\phi ({{x}_{k}})$, такие что Используя разложение Тейлора функции $f(x)$ в точке ${{z}_{k}}$, получим следующую систему: где Система (3.6) имеет единственное решение Подставляя (3.8) в (3.5), получаем где Согласно (3.2) и (3.7), имеем Используя (3.10)–(3.12) в (3.8), получаем Подставляя (3.9) в (3.4) и пренебрегая малым членом $O({{f}^{4}}({{x}_{k}}))$, находим где ${{a}_{k}}{{w}_{k}}$ и ${{b}_{k}}{{\gamma }_{k}}$ определяются формулой (3.13). Выражения в круглых скобках в (3.14) можно переписать в терминах вторых разделенных разностей как: Подставляя (3.13), (3.15) и (3.16) в (3.14), получаем другое представление для ${{\alpha }_{k}}$: где ${{F}_{k}} = ({{\tau }_{k}}({{\tau }_{k}} + \gamma {{\phi }_{k}})f[{{y}_{k}},{{z}_{k}},{{x}_{k}}] + ((1 - {{\tau }_{k}})(2{{\tau }_{k}} + \gamma {{\phi }_{k}}) + {{({{\tau }_{k}} + \gamma {{\phi }_{k}})}^{2}})f[{{z}_{k}},{{x}_{k}},{{\xi }_{k}}])$.

Теперь найдем асимптотику для ${{\alpha }_{k}}$, заданную формулой (3.14). С этой целью используем следующие формулы

Аналогичным образом, формулу (3.13) можно также переписать в терминах ${{\bar {\tau }}_{k}}$, как (3.18) и (3.19). Принимая во внимание это и (3.18) и (3.19), можно переписать (3.14) как где Согласно (2.23), можем написать ${{\bar {\tau }}_{k}}$ как где ${{\tilde {\beta }}_{k}}$ и ${{\tilde {\gamma }}_{k}}$ – некоторые константы. Тогда, по теореме 1, имеем Используя (3.23) и (3.24) в (3.22), получаем где Аналогично, имеем Тогда Подставляя последнее выражение в (3.21) и используя известное разложение (2.20), получаем или Когда $\gamma \to 0$, формула (3.30) сводится к виду который является асимптотикой ${{\alpha }_{k}}$ в трехточечных итерационных методах [6].

Теорема 3. Пусть выполнены все предположения Теоремы 1. Тогда трехточечные итерационные методы (3.1) имеют 8-й порядок сходимости тогда и только тогда, когда итерационные параметры ${{\bar {\tau }}_{k}}$ и ${{\alpha }_{k}}$ задаются формулами (3.23) и (3.30) соответственно.

Доказательство. Пусть ${{\bar {\tau }}_{k}}$ и ${{\alpha }_{k}}$ задаются формулами (3.23) и (3.30) соответственно. Тогда, по теореме 1, первые два шага в (3.1) определяют оптимальный метод четвертого порядка, т.е. $f({{z}_{k}}) = O({{f}^{4}}({{x}_{k}}))$. А значение ${{\alpha }_{k}}$, заданное формулой (3.30), удовлетворяет условию (3.4). Следовательно, справедливо соотношение (3.3). Обратно, предположим, что порядок сходимости итерации (3.1) равен 8. Тогда из (3.1) и (3.3) следует, что $f({{z}_{k}}) = O({{f}^{4}}({{x}_{k}}))$ и формула (3.4). Поэтому, по теореме 1, формула (3.23) верна с некоторыми константами $\tilde {\gamma }$ и $\tilde {\beta }$. Используя аппроксимацию (3.9) в (3.4), получаем (3.14) с точностью $O({{f}^{4}}({{x}_{k}}))$. Так как (3.23) верно, то из (3.14) приходим к асимптотике (3.30).

Предположим в (3.1)

Тогда получаем семейство оптимальных трехточечных итераций, не содержащих производные, так как ${{\bar {\tau }}_{k}}$ и ${{\alpha }_{k}}$, заданные формулами (2.23) и (3.33), удовлетворяют условиям (3.23) и (3.30) с константами соответственно. Таким образом, метод производящих функций [5] позволяет построить семейство оптимальных трехточечных итераций.

Теперь рассмотрим следующие трехточечные итерации:

Здесь функция ${{\psi }_{4}}$ берется из любого оптимального метода четвертого порядка, не содержащего производные, и $f[{{z}_{k}},{{y}_{k}},{{x}_{k}},{{\eta }_{k}}]$ – третья разделенная разность. Из теоремы 2 следует

Теорема 4. Пусть выполнены все предположения теоремы 1. Тогда порядок сходимости итерации (3.34) равен 8.

Доказательство. Так как ${{\psi }_{4}}$ – итерация четвертого порядка, то ${{z}_{k}}$ можно переписать как

По теореме 1 имеем ${{\bar {\tau }}_{k}} = 1 + {{\hat {d}}_{k}}{{\theta }_{k}} + O({{f}^{2}}({{x}_{k}}))$. Это означает, что верно разложение Тейлора ${{\bar {\tau }}_{k}}$ (3.23). Если сравнить (3.1) с (3.34), то можно записать Легко показать, что параметр ${{\alpha }_{k}}$, заданный формулой (3.35), удовлетворяет условию (3.30). Тогда согласно теореме 3, порядок сходимости (3.34) равен 8.

Замечание 1. Порядок сходимости трехточечных итераций, предложенных в [12], [22]–[24], сразу следует из теоремы 4. Теорема 4 является расширением теорем, приведенных в [12], [22]–[24].

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

Легко проверить, что параметры ${{\bar {\tau }}_{k}}$ и ${{\alpha }_{k}}$ в этих методах имеют одинаковую асимптотику (3.23) и (3.30) с собственными константами $\tilde {\gamma }$ и $\tilde {\beta }$. Таким образом, сходимость всех существующих оптимальных трехточечных методов, не содержащих производные, может быть доказана с использованием достаточных критериев сходимости (3.23) и (3.30) без использования символьных вычислений. Более того, применение этих достаточных условий сходимости позволяет в некоторых случаях построить новые оптимальные итерации [29]. Из табл. 1 видно, что параметр ${{\bar {\tau }}_{k}}$, входящий во всех перечисленных здесь оптимальных трехточечных методах, получается с помощью производящих функций $H({{\theta }_{k}})$, заданных формулой (3.32), за исключением метода, предложенного в [16]. Из (3.32) и (3.34) видно, что функция ${{\psi }_{4}}$ может содержать в себе некоторые свободные параметры. Это означает, что итерации (3.34) представляют широкий класс оптимальных трехточечных методов, не содержащих производные. Этот класс включает в себя многие из хорошо известных методов как частные случаи, см. [4]–[6], [9], [12]. Как и в предыдущем раз., можно варьировать $\gamma $ на каждом шаге итераций, используя информацию, полученную в предыдущем и настоящем шагах. Это позволяет увеличить порядок сходимости без использования дополнительных вычислений. А именно, получить трехточечные итерации с памятью (${{x}_{0}}$, ${{\gamma }_{0}}$ заданы). Тогда ${{\eta }_{0}} = {{x}_{0}} + {{\gamma }_{0}}f({{x}_{0}})$ и

Здесь ${{N}_{4}}(t) = {{N}_{4}}(t,{{x}_{k}},{{z}_{{k - 1}}},{{y}_{{k - 1}}},{{\eta }_{{k - 1}}},{{x}_{{k - 1}}})$ – интерполяционный многочлен Ньютона четвертой степени, построенный на узловых точках ${{x}_{k}}$, ${{z}_{{k - 1}}}$, ${{y}_{{k - 1}}}$, ${{\eta }_{{k - 1}}}$, ${{x}_{{k - 1}}}$. Как в [9], легко доказать, что $R$ – порядок сходимости метода (3.36), по крайне мере, равен 12.

4. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ

В этом разделе приведены результаты численных экспериментов для сравнения эффективности методов. Численные расчеты, представленные здесь, были выполнены в системе Maple. Чтобы получить очень высокую точность, избежать потери значимых цифр, вычисления проводились с 300 значащими десятичными цифрами. Численные эксперименты сделаны для гладкой и негладкой функций (см. табл. 2) и при $\gamma = - 0.01$. Для проверки сходимости итераций расчетный порядок сходимости (РПС) вычислялся с помощью формулы

где ${{x}_{k}}$, ${{x}_{{k - 1}}}$, ${{x}_{{k - 2}}}$ – три последовательных приближения. Итерации завершаются при условии ${\text{|}}{{x}_{k}} - x{\kern 1pt} *{\text{|}} < {{10}^{{ - 30}}}$.

В табл. 2 приведены примеры, взятые из [9]. Третий пример с негладкой функцией (см. [7], [14], [32]) часто используется для проверки работоспособности итераций, не содержащих производных. В табл. 3–6 приведены числа итераций $(k)$, абсолютные погрешности ${\text{|}}{{x}_{k}} - x{\kern 1pt} *{\text{|}}$ и РПС для выборных методов при $\gamma = - 0.01$. Численные результаты подтверждают теоретический вывод о порядке сходимости. Из табл. 6 видно, что методы высокого порядка сходимости устойчиво работают не только для достаточно гладкой функции, но и также для негладкой функций. Отметим, что первая производная нелинейной функции ${{f}_{3}}(x)$ терпит разрыв в точке $x* = 0$, поэтому в этом случае РПС = 2 для всех предлагаемых методов (см. первую часть табл. 5, также [7]). Предлагаемые методы (3.34) могут быть успешно применены в расчетах, требующих высокую точность.

5. ВЫВОДЫ

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