Все задачи

Дихотомия (численные методы)

15 Apr 2014

На практикуме по численным методам студент реализовал решение нелинейных уравнений методом деления отрезка пополам.

# Ищет нули функции методом деления отрезка пополам.
#
# Параметры: 
#  * ссылка на функцию, чей ноль ищем;
#  * концы отрезка, на котором ищем ноль (знак функции на концах отрезка должен быть разным, это проверяется);
#  * epsilon (точность по x) -- деление отрезка продолжается до тех пор, 
#    пока длина отрезка не станет меньше этого значения. 
#    Необязательный параметр, по умолчанию 1e-2.
#
# Пример:
# sub f2 {return $_[0]**2 - 10;}
# my $x = dichotomy(\&f2, 0, 100, 1e-4);
sub dichotomy
{
    my ($f, $x1, $x2, $epsilon) = @_;

    my ($y1, $y2) = ($f->($x1), $f->($x2));
    if ($y1 == 0 ) {
        return $x1;
    } elsif ( $y2 == 0 ){
        return $y1;
    } elsif ( $y1 > 0 && $y2 < 0 ){
        ($x1, $x2) = ($x2, $x1);
    } elsif ( $y1 < 0 && $y2 > 0 ){
        # ok
    } else {
        die "incorrect interval: f($x1) = $y1, f($x2) = $y2\n";
    }
    $epsilon ||= 0,01;

    while ( abs($x1 - $x2) >= $epsilon ){
        my $xnew = ($x1+$x2)/2;
        if ( $f->($xnew) > 0  ){
            $x2 = $xnew;
        } else {
            $x1 = $xnew;
        }
    }

    return ($x1+$x2)/2;
}

Поиск корней работал, и неплохо. Но не всегда. Иногда ужасно тормозил. С чего бы?

Подсказка

Показать

Точнее сказать – не просто тормозил, а зависал совсем поиск корней иногда.

Подсказка-2

Показать

по умолчанию 1e-2

Подсказка-3

Показать

    $epsilon ||= 0,01;

Разоблачение

Показать

Проблема с умолчальным значением точности:

    $epsilon ||= 0,01;

Вместо десятичной точки написана запятая, и присваивание превращается в такое:

    ($epsilon ||= 0),01;

И дальнейшие итерации продолжались, пока было выполнено условие

abs($x1 - $x2) >= 0

То есть… Ну, все и так понятно. Следите за пунктуацией ;)

Из наших читателей лучшее объяснение прислал Роман Луговкин. Здорово!