отделение корней

[papirus]

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

[Imperator]

http://www.uchites.ru/files/nummethod_b ... ter2-1.pdf

[papirus]

а как первую производную высчитать?

[papirus]

вот нашел алгоритм http://algolist.manual.ru/maths/findroot/brac_find.php
тут находит тока один корень, а как найти все корни? подскажите плз

[Circiter]

2papirus

Цитата:

дано уравнение надо найти отрезки в которых, будет находиться корень

Обычно делают так. Находят один корень $f(x^*)=0$ любым способом, хоть простыми итерациями, хоть по Ньютону, хоть секущими, не важно. Теперь конструируют новую $f(x)=f(x)/(x-x^*)$ удаляя у неё тем самым найденный корень. Этот процесс продолжают пока не будут найдены (отделены) все корни.

Может быть имеет смысл просканировать область определения функции скользящим окном и таким образом найти отрезки на концах которых функция меняет знак (т.е. отрезки, содержащие корни). Но я не уверен в этом методе.

Цитата:

На практике то понятно

И какие методы вам известны? Попробуйте реализовать, а вам тут помогут в случае чего. :)

[papirus]

вот сделал, тока она не работает((
почему это оффтопик?:) обычно же спойлер

(Оффтоп)

#include <iostream>
using namespace std;
double f(double x);
int main() {
    double x0 = 1;
    int d = 1, di = 2, dmax = 50;
    double f0 = f(x0);
    double a, b;
    a = x0 - d;
    b = x0 + d;
    double fa = f(a), fb = f(b);
    int loca[2], locb[2];
    while (d*=di < dmax) {
        int i=0;
        if (f0 > 0) {
            if (fa*f0 < 0) {
                loca [i] = a;
                locb [i] = x0;
                ++i;
            }
            if (f0*fb < 0) {
                loca [i] = x0;
                locb [i] = b;
                ++i;
                }
            if (fa < fb) {
                b = x0;
                x0 = a;
                fb = f0;
                f0 = fa;
                a -= d;
                fa = f(a);
            }
            else if (fb < fa) {
                a = x0;
                x0 = b;
                fa = f0;
                f0 = fb;
                b += d;
            }
            else {
                a -= d;
                b += d;
                fa = f(a);
                fb = f(b);
                }
        } else if (f0 < 0) {
            if (fa > 0) {
                loca [i] = a;
                locb [i] = x0;
                ++i;
            };
            if (fb > 0) {
                loca [i] = x0;
                locb [i] = b;
                ++i;
            }
            if (fa > fb) {
                b = x0;
                x0 = a;
                fb = f0;
                f0 = fa;
                a -= d;
                fa = f(a);
            }
            else if (fb > fa) {
                a = x0;
                x0 = b;
                fa = f0;
                f0 = fb;
                b += d;
            }
            else {
                a -= d;
                b += d;
                fa = f(a);
                fb = f(b);
                }

        }


}
        cout << loca[0] << " " << locb[0];
}
double f(double x)
{
    return (x*x*x-0.2*x*x+0.5*x-1);
}

[Circiter]

2papirus
Объясните словами, как работает ваша программа?

(Оффтоп)

Цитата:

почему это оффтопик?:) обычно же спойлер

Не, это оффтопик. :) Не используйте этот тег для оформления исходников. Вместо этого, попробуйте тег syntax.

[papirus]

алгоритм я отсюда взял: http://algolist.manual.ru/maths/findroot/brac_find.php
там в принципе очень подробно расписано

[Circiter]

Но ведь по указанному вами адресу лежит работающий код. Что вы с ним сделали непонятно. Перепутаны приоритеты операторов и добавлена лапша из if'ов.

В любом случае, этот алгоритм, как я понимаю, локализует только один корень.

[Circiter]

По-прежнему предлагаю тупо просканировать достаточно большой отрезок скользящим окошком. Пример:

Используется синтаксис C++

#include <vector>
#include <utility>

...

typedef std::vector<std::pair<float, float> > cBrackets;

template <class T>
cBrackets Bracketing
    (
        T Function,
        float Left,
        float DomainSize,
        float WindowSize
    )
{
    cBrackets Brackets;
    float x=Left, f1=Function(x), f2;

    // Move the sliding window across specified domain.
    while((x+=WindowSize)<=Left+DomainSize)
    {
        f2=Function(x);

        if(f1*f2<=0) // Current window contain at least one root.
            Brackets.push_back(std::make_pair(x-WindowSize, x));

        f1=f2;
    }

    return Brackets;
}

...

float f(float x) {return ...;}

...

cBrackets Brackets=Bracketing(f, -5, 10, 0.2);
 

Найденные отрезки можно допилить, например дихотомией.