В Библиотеку численного анализа включены три подпрограммы для вычисления нуля вещественной непрерывной на [ a, b ] функции f (x), такой, что f (a) f (b) < 0.
Подпрограмма ZF15R применяет метод бисекции (метод деления отрезка пополам) в комбинации с линейной интерполяцией. Бисекция осуществляется в тех случаях, когда использование линейной интерполяции не приводит к уменьшению в два раза наименьшего вычисленного значения функции или выводит за границы текущего суженного отрезка. Если при заданных при обращении к подпрограмме границах отрезка функция имеет одинаковые знаки, т.е. f (a) f (b) > 0, то делается попытка методом бисекции за заданное число итераций найти такой отрезок [ α, β ] ⊂ [ a, b ], что f (α) f (β) < 0. Нуль функции считается вычисленным с заданной точностью ε, если найдено такое x ∈ [ a, b ], что | f (x) | < ε. Подпрограмму ZF15R практически удобно применять лишь для грубого нахождения нулей заданной функции, поскольку при увеличении точности может значительно вырасти объем вычислительной работы. Поэтому в ZF15R применяется только этот критерий сходимости, удовлетворение которому, вообще говоря, не гарантирует достижения заданной точности.
В подпрограмме ZF11R реализован метод секущих (линейной интерполяции) в той своей модификации, когда текущее приближение нуля функции вычисляется на основе данных, полученных на двух предыдущих итерациях. Подпрограмма ZF10R использует комбинированный метод, основанный на методе бисекции, линейной интерполяции и обратной квадратичной интерполяции. Такой метод не так чувствителен к начальным приближениям и в предположении, что в окрестности искомого нуля функция f (x) является непрерывно дифференцируемой, имеет более чем линейную сходимость к простому нулю функции f (x).
В ZF11R и ZF10R применяются два критерия сходимости. Пусть xi - 1 и xi являются двумя последовательными приближениями к нулю функции f (x). Тогда xi принимается за искомый нуль, если выполнен один из двух критериев сходимости:
| f(xi) | ≤ ε или [ | xi - xi -1 | / max ( | xi | , | xi -1 | , 0.1 ) ] ≤ 10 - m
Здесь ε - заданная точность вычисления искомого нуля; m - заданное число значащих цифр в приближенном значении нуля.
При обращении к подпрограмме может быть задан либо только один из этих двух критериев, либо оба критерия одновременно.
Во всех трех подпрограммах вычисления нуля вещественной функции необходимо задавать максимальное число итераций, ориентировочно требуемых для обеспечения сходимости. Если сходимость достигнута, то пользователю выдается действительное число итераций, потребовавшихся для обеспечения сходимости в соответствии с заданными критериями. В противном случае пользователю выдается соответствующее диагностическое сообщение. Пользователю выдается диагностическое сообщение и в том случае, если функция не меняет знака на заданном интервале.
Для вычисления заданного числа n вещественных нулей вещественной функции y = f (x) при заданных начальных приближениях к нулям в Библиотеку численного анализа включены две подпрограммы. Реализованные в них алгоритмы предполагают, что у функции f (x) существует n различных вещественных нулей, при этом ни один изолированный нуль не может быть получен из двух различных начальных приближений.
В подпрограмме ZF13R используется метод квадратичной интерполяции (метод Мюллера) при начальных приближениях, о которых заранее неизвестно, являются ли они хорошими. В тех случаях, когда начальные значения достаточно близки к нулям, чтобы получить сходимость методом Ньютона, можно использовать подпрограмму ZF14R. В ZF14R для вычисления f ' (x) используются разделенные разности.
Для отделения кратных нулей применяется следующий алгоритм. После вычисления очередного i - го нуля производится проверка, не слишком ли он близок к уже вычисленным нулям:
| xi - xj | < ε1 , j = 1, 2, ..., i - 1
Если это условие выполнено для какого - нибудь j, вычисление i - го нуля возобновляется с начальным приближением xi + ε2.
Таким образом, ε1 и ε2 определяют критерий отделения кратных нулей.
Так же, как и в подпрограммах ZF10R и ZF11R (см. п. 2.1), используются два критерия сходимости, которые в данном случае имеют вид:
max | f ( xiK ) | ≤ ε
1 ≤ i ≤ n
или
{ max [ | xiK - xiK-1 | / max ( | xiK | , | xiK-1 | , 0.1 ) ] } ≤ 10 - m ,
1 ≤ i ≤ n
где
xK-1 = ( x1K-1, x2K-1, ..., xnK-1 ) , xK = ( x1K, x2K, ..., xnK )
- два последовательных приближения к искомым нулям. В тех случаях, когда за заданное максимальное число итераций необходимая точность при вычислении какого - либо нуля, не достигается, то соответствующая компонента решения полагается равной 3.4Е38 для версий подпрограмм с одинарной точностью или 1.7D308 для версий подпрограмм с удвоенной точностью. В подпрограмме ZF14R фиксируются случаи, когда при нахождении какого - либо нуля производная функции становится слишком малой; тогда соответствующая компонента решения полагается равной - 3.4Е38 (или - 1.7D308 в ZF14D).
Подпрограмма ZF12C предназначена для вычисления n нулей комплексной функции y = f (z) методом квадратичной интерполяции (методом Мюллера). Подпрограмме могут быть сообщены следующие данные, если они известны заранее:
- число известных нулей функции и их значения;
- число известных начальных приближений
к искомым нулям функции и их значения.
При вычислении как изолированных, так и кратных нулей применяются по выбору пользователя упомянутые выше два критерия сходимости.
После вычисления очередного нуля (например, с номером j - 1) с заданной точностью происходит его исключение, т.е. следующие нули уже ищутся для функции
f j (z) = f (z) / ( (z - z1) (z - z2) ... (z - zj -1) ) .
Подпрограмма выдает целый вектор ITER, j - компонента которого содержит число итераций, потребовавшихся для нахождения j - го нуля функции в соответствии с заданными критериями сходимости. Если при вычислении j - го нуля функции заданные критерии сходимости не выполняются, то ITER (J) полагается равным либо ITMAX + 1, либо ITMAX + L, где ITMAX - масимальное число итераций, ориентировочно требуемых для обеспечения сходимости, а L - целое, большее 1. В первом случае рекомендуется увеличить значение ITMAX. Если же ITER (J) = ITMAX + L, то это означает, что сходимость была достигнута за L итераций для функции, но не была достигнута для f (z). В этом случае можно попытаться задать более хорошие начальные приближения либо смягчить критерии сходимости.
Подпрограмма ZF12C показала высокие эксплуатационные качества и рекомендуется также для использования при нахождении нулей вещественных и комплексных полиномов, если возникают трудности при использовании более специальных подпрограмм из раздела Библиотеки "Алгебра полиномов".
Подпрограмма ZF30R предназначена для решения n вещественных совместных нелинейных уравнений f (x) = 0 с n неизвестными и использует модификацию метода Ньютона, имеющую по крайней мере квадратичную сходимость и требующую за один шаг итерации N2/2 + 3N/2 вычислений f (x) вместо N2 + N для классического метода Ньютона. Алгоритм не требует явного задания f ' (x) и для вычисления якобиана системы используются разделенные разности.
Подпрограмма применяет оба критерия сходимости, рассмотренные в п. 2.2., и выдает то число итераций, которое потребовалось для обеспечения сходимости. Предусмотрены диагностические сообщения в тех случаях, когда решение системы не может быть найдено в пределах заданного максимального числа итераций или когда якобиан системы имеет особенность. В этих случаях можно попробовать другое начальное приближение и (или) дополнительно исследовать систему с целью возможного исключения лишних уравнений или переменных, а также с целью возможного выражения одних переменных через другие.
Подпрограмма может быть использована для вычисления одного нуля вещественной функции.