Реализация секущего метода для поиска корня функции

Question

Я написал следующий код в качестве реализации метода secant. Это происходит на Java, но в основном можно перевести на аналогичные языки, такие как C++ (и C, если вы игнорируете исключения).

public interface Function 
{ 
    public double f(double x); 
}; 

public class Secant 
{ 
    public static double find(Function f, double a, double b, double epsilon) 
    { 
     double fa = f.f(a), fb = f.f(b); 

     if (fa == fb) throw new IllegalArgumentException(); 

     double c = b - ((fb * (b - a))/(fb - fa)); 

     if (Math.abs(c - b) > epsilon) return find(f, b, c, epsilon); 
     else return c; 
    } 
}; 

В этом коде (е) представляет собой класс реализации интерфейса Function, (а) предыдущее приближение корня, (б) представляет собой текущее приближение корня и (эпсилон) является , насколько я понимаю, максимальная разница между двумя последними приближениями для метода, который должен быть закончен. Если я верю в это, не проверял, будет ли | c-b | превышает (epsilon) трюк?

Это, кажется, работает хорошо для обычных функций, таких как х^2 + 2x + 1 но проблема возникает, когда я пытаюсь запустить найти с функцией возвращающей Math.log (х) - это корень находит NaN.

Есть ли что-то не в порядке с моим кодом или я просто неправильно понимаю фактическую математику? Я был бы признателен, если бы кто-то пролил свет на этот вопрос.

Answer 1

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

Когда секущая такова, что ее пересечение с ось x лежит в отрицательной половине, вы в конечном итоге вызываете find(f,b,c,epsilon) с отрицательным значением b и получаете NaN из-за попытки взять логарифм отрицательного числа.

Возможные средства:

1. сгенерирует исключение и сказать пользователю попробовать еще раз с различными начальными значениями.

2. Попытка восстановления: если f (b) не определено, замените b на (a + b)/2 (например, return find(f, a, (a+b)/2, epsilon)). Это может помочь алгоритму восстановить, хотя, с другой стороны, вы можете застрять в бесконечный цикл (рекурсии в вашем случае).

Answer 2

Существует проблема с описанным способом, может быть, не сходится. Самый простой способ, чтобы начать с 2 чисел а и Ь, для которых f(a) и f(b) имеют разные При условии, что f является непрерывным на [a;b] (при условии a < b), секущий алгоритм затем даст c с a < c < b. Фактически вы не храните последнее предположение, но лучше один

Затем итерация (или рекурсия с реализацией), с a, c если f(c) имеет такое же знак, как f(b), еще с c, b.

Возможная реализация:

public class Secant 
{ 
    static double find(Function f, double a, double b, double epsilon) 
    { 
     double temp; 
     if (b < a) { 
      temp = a; 
      a = b; 
      b = temp; 
     } 
     double fa = f.f(a), fb = f.f(b); 

     if (fa == fb) { 
      throw new IllegalArgumentException(); 
     } 

     double c = b - ((fb * (b - a))/(fb - fa)); 

     if (Math.abs(c - b) > epsilon) { 
      if (f.f(a) * f.f(b) < 0) { // different signs for f(a) and f(b) 
       if (f.f(a) * f.f(c) < 0) { 
        return find(f, a, c, epsilon); 
       } 
       else { 
        return find(f, c, b, epsilon); 
       } 
      } 
      else { // same signs for f(a) and f(b) 
       if (((f.f(a) < f.f(b)) && (f.f(c) < f.f(a))) || ((f.f(a) > f.f(b)) && (f.f(c) > f.f(a)))) { 
        // f(a) between f(b) and f(c) 
        return find(f, a, c, epsilon); 
       } 
       else { 
        return find(f, c, b, epsilon); 
       } 
      } 
     } 
     else { 
      return c; 
     } 
    } 
}; 

Для непрерывной функции, эта реализация гарантированно сходится, как только вы найдете 2 числа (в одном рекурсии уровне), для которых f(a) * f(b) < 0

Если вы не можете легко получить 2 номера, для которых f(a) * f(b) < 0, этот метод следует использовать только тогда, когда вы уже находитесь в низине корня и касательных в обеих точках, секущая и сама функция находятся достаточно близко. Фактически (за исключением того, что он не нуждается в каком-либо знании производной функции), его следует использовать только там, где может быть метод Эйлера. Таким образом, нормальный случай использования:

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