Решение уравнения y=F(x) методом Ньютона (касательных)

/ Просмотров: 349

Метод Ньютона позволяет решить уравнение y=f(x), зная начальное приближение и производную f’(x). Метод состоит в построении итерационной последовательности xn+1=xn-f(xn)/f’(xn). Определим условия сходимости метода.

Функция f(x) должна быть определена и дважды дифференцируема на отрезке [a, b], причём f(a)f(b)<0, а производные f’(x), f’’(x) сохраняют знак на отрезке [a, b]. Это означает, что функция должна иметь на отрезке [a, b] только один корень и монотонно убывать или возрастать. В противном случае алгоритм не работает. Изобразим алгоритм решения уравнения графически. В качестве примера возьмём уравнение x3-3x-2e-x=0. Построим график. Выберем в качестве начального приближения точку 1,2.

/uploads/_pages/24/newton.png

Перейдём к алгоритмизации. В этой лабораторной работе структура программы была несколько изменена, предыдущая реализация признана неэффективной. Теперь нет интерфейса, содержащего функцию F(x), вместо него теперь делегат.

public delegate double Equation(double x);

Также создано несколько исключений, сигнализирующих о неверной работе алгоритма.

public class DivergentException : Exception

Это исключение свидетельствует о расхождении алгоритма по неизвестной причине.

public class InvalidValueException : Exception

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

public class TooManyIterationsException : Exception

Это исключение свидетельствует о том, что совершено слишком много итераций. Обычно для метода Ньютона достаточно не более 10 итераций. Класс, решающий эту задачу, будет выглядеть следующим образом.

/// <summary>
/// Осуществляет решение уравнения методом касательных Ньютона
/// </summary>
public class Newton
{
    /// <summary>
    /// Начальное приближение
    /// </summary>
    public double X0;
    /// <summary>
    /// Точность
    /// </summary>
    public double Epsilon;
    /// <summary>
    /// Максимальное количество итераций. При превышении возникает TooManyIterationsException
    /// </summary>
    public double MaxIterations = 100;

    /// <summary>
    /// Выполняет вычисления по методу Ньютона
    /// </summary>
    /// <param name="eq">Уравнение, которое необходимо решить</param>
    /// <param name="derivative">Первая производная</param>
    /// <returns></returns>
    /// <exception cref="TooManyIterationsException"></exception>
    /// <exception cref="InvalidValueException"></exception>
    public double Resolve(Equation eq, Equation derivative)
    {
        double del0 = double.PositiveInfinity;
        double xs = X0;     //текущее приближение
        int i = 1;          //Счетчик итераций
        double y;           
        double xn;
        double del;
        while (true)
        {
            y = derivative(xs);     //Вычиление производной
            xn = xs - eq(xs) / y;   //Вычисление следующего приближения
            if ((double.IsNaN(y)) || 
                (double.IsInfinity(y)) ||
                (double.IsNaN(xn)) ||
                (double.IsInfinity(xn))) throw new InvalidValueException();
            del = Math.Abs(xn - xs);    //Вычисление разности текущего и следующего приближений
            if (del < Epsilon) return xn;
                if (i >= MaxIterations) throw new TooManyIterationsException();
                i++;
                xs = xn;
                del0 = del;
        }
    }
}

Теперь воспользуемся этим алгоритмом и решим несколько уравнений. Для проверки правильности работы алгоритма воспользуемся модульным тестированием.

10x-ex=0

ln2x-1/x=0

x3-3x-2e-x=0

    [TestMethod]
    public void TestNewton()
    {
        Newton n = new Newton();
        n.MaxIterations = 10;
        n.X0 = 0;
        n.Epsilon = EPSILON;
        Assert.AreEqual(n.Resolve(x => {return 10 * x - Math.Exp(x);}, x => {return 10 - Math.Exp(x);}), 0.111833, EPSILON);
        n.X0 = 0.1;
        Assert.AreEqual(n.Resolve(x => { return Math.Pow(Math.Log(x), 2) - 1 / x; }, x => { return 2 * Math.Log(x) / x + 1 / x / x; }), 2.020747, EPSILON);
        Assert.AreEqual(n.Resolve(x => { return Math.Pow(x, 3) - 3 * x - 2 * Math.Exp(-x); }, x => { return 3 * x * x - 3 - 2 * (-Math.Exp(-x)); }), 1.785461, EPSILON);
    }
Оставьте комментарий!

Комментарий будет опубликован после проверки

Вы можете войти под своим логином или зарегистрироваться на сайте.

(обязательно)