Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 12487
Последний выпуск: 4.04.2014

Вопросы и ответы - Форум

Нужна помощь в нахождении точности

0спам
25K
05 марта 2007 года
Nik.rus
6 / / 05.03.2007
Здравствуйте, помогите пожалуйста доделать программу в Builder C++ в консольном приложении, сколько я не мучался у меня ничего не получается [Помогите]
Найти корни уравнения: a * x3 + b∙x2 + c∙x + d = 0 с точностью до 0.01
Вместо компонентов a, b, c и d записать заданные значения полинома, где а=1, b=2, с= -6, d= -3, Корни найти методом половинного деления.
:confused: :confused: :confused:
15K
05 марта 2007 года
Sara
79 / / 04.01.2007
А эта программа должна находить корни любого кубического уравнения? Или только для конкретных значений а=1, b=2, с=-6, d=-3?
85
05 марта 2007 года
MrXaK
721 / / 31.12.2002
ну во первых сначала делим всё на a и оставляем уравнения вида x^3 + ax^2 + bx + c (a b c ессно другие уже), корни от этого не меняются
на самом деле для кубического уравнения можно найти корни и без метода половинного деления, как - написано здесь
но если уж так понадобился метод половинного деления, то сначала надо найти какие-то отрезки, на которых многочлен обращается в ноль... для этого можно пройтись с каким-то большим eps и посмотреть какого знака произведение f(x-eps)*f(x+eps) в какой-то точке х.. (или как-то по другому найти отрезки... единственно что на отрезке должен быть один корень)
а потом пока (F(xi) <> 0) и |xk-xn| > eps повторять:
xi := xn+(xk-xn)/2;
если (F(xn)*F(xi) < 0), то xk := xi;
если (F(xi)*F(xk) < 0), то xn := xi.
где xk и xn концы отрезка

собственно вся основная проблема состоит в нахождении границ отрезка
для этого помогут теоремы, изучаемые в институте на первом курсе, а именно
Если функция f(x) непрерывна на отрезке [a;b], причём значения её в концах отрезка f(a) и (f)b - это числа разных знаков, то на отрезке [a;b] лежит по крайней мере один корень уравнения.
Если функция f(x) строго монотонна на отрезке [a;b], то есть возрастает или убывает на [a;b], то на этом отрезке уравнение f(x) = 0 не может иметь более одного корня.
собсна монотонность исследуется по производной (которую найти для кубического трёхчлена очень легко), а дальше просто находишь отрезок, на границе которого функция имеет другой знак, а дальше уже метод половинного деления
85
05 марта 2007 года
MrXaK
721 / / 31.12.2002
вот прога... но поскольку с математикой в средней школе у меня было не очень, то если я неправ, поправьте последний else в mainе
Код:
#include <stdio.h>
#include <iostream.h>
#include <math.h>

#define EPS 1e-4

float a, b, c;
float x1v, x2v; // мин и максимум трёхчлена (локальные)
float D; //дискриминант у производной
float x1, x2, x3; // корни

bool abs(float); // модуль
short int sgn(float); // знак
float F( float ); // функция - трёхчлен
float Fpr( float ); // производная
float dih(float, float, float); // метод половинного деления на интервале
bool otr1( void ); // считает минимум и максимум функции F

short int sgn( float val )
{  
    (val > 0) ? (1) : ((val == 0) ? (0) : (-1));
}

bool otr1( void )
{
    D = a*a - 3*b;
    if( D < 0 )
    {
    return false;
    }
    else if( D == 0 )
    {  
    x1v = x2v = -1*a/3;
    }
    else
    {
    x1v = (-1*a + sqrt(D)) / 3;
    x2v = (-1*a - sqrt(D)) / 3;
    }
    return true;
}

bool abs(float val)
{
    (val > 0) ? (val) : (-1*val);
}

float F( float x )
{
    return x*x*x + a*x*x + b*x + c;
}
float Fpr( float x )
{
    return 3*x*x + 2*a*x + b;
}

float dih(float xn, float xk, float eps)
{
    if( F(xn)*F(xk) > 0 )
    {
        cout<<"Err";
        return 0;
    }
    float xi, fl;
    if( F(xn) == 0 )
        return xn;
    if( F(xk) == 0 )
        return xk;
    while( (F(xi) != 0) && (abs(xk-xn) > eps) )
    {
    xi = xn + (xk - xn)/2;
    if( F(xn)*F(xi) < 0 )
        xk = xi;
        if( F(xi)*F(xk) < 0 )
            xn = xi;
    }
    return xi;
}

int main( void )
{
    cin>>a;
    cin>>b;
    cin>>c;
    float x;
    if( otr1() == false)
    {
        // это означает что наша функция возрастает на области определения и имеет один корень
        // передаём в функцию dih в качестве границ очень большое и очень маленькое число
        // неоптимально, можно продолжить исследование и сузить поиск
        // но будет работать))
        x1 = dih((-1)*(unsigned)(-1.0), (unsigned)(-1.0), EPS );
        cout<<"корень 1: "<<x1;
        return 0;
    }
    // посчитаем значение функции на точке, большей точки максимума (локального) == знаку на +бесконечности
    bool znakbeskpl; // true - плюс, false - минус
    if( sgn(F(x1v+1)) == 1 )
        znakbeskpl = true;
    else
        znakbeskpl = false;
/*    bool znakbeskmin;
    if( sgn(F(x2v-1)) == 1 )
        znakbeskmin = true;
    else
        znakbeskmin = false;*/
    // дальше найдём значения функций в точках экстремума
    short int znakx1v, znakx2v;
    znakx1v = sgn(F(x1v));
    znakx2v = sgn(F(x2v));
    if( znakx1v == 0 )
    {
    // один корень есть, равен максимуму, второй будет лежать правее
    // если знак на +беск > 0 и левее если знак -беск < 0
    x1 = x1v;
    cout<<"корень 1: "<<x1;
    if( znakbeskpl == true )
            x2 = dih(x2v, (unsigned)(-1.0), EPS);
        else
            x2 = dih((-1)*(unsigned)(-1.0), x2v, EPS);
        cout<<endl<<"корень 2: "<<x2;
    }
    else if( znakx2v == 0 )
    {
    // аналогично если корень совпал с локальным минимумом
    x1 = x2v;
    cout<<"корень 1: "<<x1;
    if( znakbeskpl == true )
            x2 = dih((unsigned)(-1.0), x1v, EPS);
        else
            x2 = dih(x1v, (-1)*(unsigned)(-1.0), EPS);
        cout<<endl<<"корень 2: "<<x2;
    }
    else if( ((znakx1v == 1) && (znakx2v == -1)) || ((znakx2v == 1) && (znakx1v == -1)) )
    {
    // локальные максимумы и минимумы имеют разные знаки... очевидно что корни есть между ними и снаружи
    x1 = dih(x1v, x2v, EPS);
    if( znakbeskpl == true )
    {
            x2 = dih(x2v, (unsigned)(-1.0), EPS);
            x3 = dih((-1)*(unsigned)(-1.0), x1v, EPS);

    }  
    else
    {
            x2 = dih(x1v, (unsigned)(-1.0), EPS);
            x3 = dih((-1)*(unsigned)(-1.0), x2v, EPS);
    }
    cout<<"корень 2: "<<x2;
    cout<<endl<<"корень 3: "<<x3;
    }
    else
    {
    // то есть локальные максимум и минимум имеют одинаковый знак
    // тогда корень один, по идее этот вариант аналогичен
    // тому, что D < 0
    }

    return 0;
}


если не работает, то меня не убивайте) ибо писал чам)
в гугле вроде есть готовая функция) но она на паскале, портируешь сам если надо будет
420
05 марта 2007 года
nilbog
507 / / 19.12.2006
Цитата: Mr.Hacker
ну во первых сначала делим всё на a и оставляем уравнения вида x^3 + ax^2 + bx + c (a b c ессно другие уже), корни от этого не меняются


а если a=0
это конечно вырожденный не представляющий интереса случай но нужно про него помнить
вот могу предложить процедуру(правда только на паскале - но это неважно) которая находит корень на [a,b] с точностью eps
принимает функцию как параметр

Код:
type FT=function(x:real):real;
procedure root(z:FT; a,b,eps:real; var  x:real);
var c:real;
begin
   repeat
     c:=(a+b)/2;
     if z(a)*z(c)<0 then b:=c else
     if z(c)*z(b)<0 then a:=c
   until (b-a)<eps;
   x:=(a+b)/2
end;

ну а нахождение a b уже предложили вариант
работая только с такими многочленами вообще не возникает проблем найти производную в общем виде
исследуйте ее - находите число корней и нужные a b

/*add*/ меня опередили с полной программой на нужном языке :)
85
05 марта 2007 года
MrXaK
721 / / 31.12.2002
кстати блин неправильно я малёк написал) D у производной определяет форму, так что в последнем else не то же самое, там надо дописать, если на +беск плюс, то если мин/макс >0 то корень слева от макс, если <0 то справа от мин, и наоборот на +беск минус))) впадлу редактировать
15K
06 марта 2007 года
Sara
79 / / 04.01.2007
Цитата:
собственно вся основная проблема состоит в нахождении границ отрезка


Вот здесь кое-что написано о границах корней многочлена: http://www.pm298.ru/mnog5.shtml

Т.е. для многочлена ax3 + bx2 + cx + d получится формула

 
Код:
|x| <= 1 + max{|b|,|c|,|d|}/|a|
25K
08 марта 2007 года
Nik.rus
6 / / 05.03.2007
Цитата: Sara
А эта программа должна находить корни любого кубического уравнения? Или только для конкретных значений а=1, b=2, с=-6, d=-3?


Только для конкретных значений))) а=1, b=2, с=-6, d=-3

25K
08 марта 2007 года
Nik.rus
6 / / 05.03.2007
Цитата: Sara
А эта программа должна находить корни любого кубического уравнения? Или только для конкретных значений а=1, b=2, с=-6, d=-3?


Здравствуйте))
Ну желательно чтобы программа находила значения только для конкретных значений а=1, b=2, с=-6, d=-3
Ну наверно сложно будет сделать программу для произвольных значений заданных пользователем))

420
08 марта 2007 года
nilbog
507 / / 19.12.2006
Цитата: Nik.rus

Ну наверно сложно будет сделать программу для произвольных значений заданных пользователем))


да нет - особой сложности нет
дифференцирование многочлена линейная операция
ну а для конкретных a b c d задача сводиться к очень простой
не нужно искать отрезки с уединенными корнями - их можно посчитать вручную

72
08 марта 2007 года
kosfiz
1.6K / / 18.09.2005
[quote=Nik.rus]Здравствуйте, помогите пожалуйста доделать программу в Builder C++ в консольном приложении, сколько я не мучался у меня ничего не получается [Помогите]
Найти корни уравнения: a * x3 + b&#8729;x2 + c&#8729;x + d = 0 с точностью до 0.01
Вместо компонентов a, b, c и d записать заданные значения полинома, где а=1, b=2, с= -6, d= -3, Корни найти методом половинного деления.[/quote]
вообще еще в задачах подобного рода пишется на каком отрезке надо искать корни. я взял, к примеру, отрезок [-10;10]. решение будет следующее:
Код:
#include <iostream.h>
#include <stdlib.h>
#pragma hdrstop
#pragma argsused

double poldel(double x1, double x2, double eps)
{
    double a,b,c,f1,f2;
    a=x1;
    b=x2;
    do{
        c=(a+b)/2;
        f1=a*a*a+2*a*a-6*a-3;
        f2=b*b*b+2*b*b-6*b-3;
        if (f1*f2<=0){
            b=c;
        }else{
            a=c;
        }
    }while((b-a)>=2*eps);
    return (a+b)/2;
}

#define a -10
#define b 10
#define h 0.00001
#define eps 0.01

int main(int argc, char* argv[])
{
        double y2,y1,x1,x2;
    x1=a;
    x2=a+h;
    while(x2<b){
        y1=x1*x1*x1+2*x1*x1-6*x1-3;
        y2=x2*x2*x2+2*x2*x2-6*x2-3;
        if (y1*y2<=0){
            cout<<x1<<" "<<x2<<endl;
            cout<<"poldel= "<<poldel(x1,x2,eps)<<endl;
        };
        x1=x2;
        x2+=h;
    }
        system("pause");
    return 0;
}

вообщем находим отрезки локализации и для каждого отрезка находим корень. вроде все достаточно точно работает. взял конкретно для твоего случая.
[quote=nilbog]да нет - особой сложности нет[/quote]
согласен. например приведенный мной код вполне можно переделать для произвольных значений a, b, c, d.
15K
08 марта 2007 года
Sara
79 / / 04.01.2007
Цитата: Nik.rus
Здравствуйте))
Ну желательно чтобы программа находила значения только для конкретных значений а=1, b=2, с=-6, d=-3
Ну наверно сложно будет сделать программу для произвольных значений заданных пользователем))


Да почему сложно? Для студента математического факультета эта задача, так сказать, средней сложности. Главное - не забыть про кратные корни (имейте в виду, что если корень имеет кратность 2, то значения функции справа и слева от этого корня будут иметь одинаковый знак).

А для конкретных значений а=1, b=2, с=-6, d=-3 задача решается и вовсе просто.
В данном случае действительный корень только один, и находится он на отрезке [1,2].
Вот код, который я написала в C++ Builder (проверено, работает).

Код:
int sign( double x )
{
  if(x >= 0) return 1;
  else return -1;
}
//-------------------------------------------------------
double f( double x )
{
  return x*x*x* + x*x*2 - x*6 - 3;
}
//-------------------------------------------------------
bool find_root( double x1, double x2, double eps, double* x )
{
  double v1, v2, v12, x12;
  while( fabs(x1-x2) > eps )
  {
    v1 = f(x1);
    v2 = f(x2);
    if( sign(v1) == sign(v2) ) return false;
    else
    {
      x12 = (x1+x2)/2;
      v12 = f(x12);
      if( sign(v12) == sign(v1) ) x1 = x12;
      else x2 = x12;
    }
  }
  *x = x12;
  return true;
}
//-------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
  double x1 = Edit1->Text.ToDouble();
  double x2 = Edit2->Text.ToDouble();
  double eps = Edit3->Text.ToDouble();
  double x = 0;
  if( find_root(x1, x2, eps, &x) == true )
  {
    Edit4->Text = FloatToStr(x);
    Edit5->Text = FloatToStr(f(x));
  }
  else
  {
    Edit4->Text = "Error";
  }
}
72
08 марта 2007 года
kosfiz
1.6K / / 18.09.2005
вздумалось попробвать данный код(ничего не менял) и получил ответ x=1,41... сразу видно, что выражение x^3+2*x^2-6*x-3 при таком x никак не будет равно 0 даже приблизительно.
и еще мне вот интересно, а почему ищем только один корень? ну допустим действительный только один(остальные комплексные вроде - не проверял), но мы же можем получить приближенный действительный корень(корни)(естественно корень будет на малом отрезке, на котором функция меняет знак), при котором функция будет приблизительно равна 0(т.е. будет приблизительно выполнять равенство F(x)=0), что учитывая, что метод половинного деления относится к приближенным вполне нас устраивает.
85
08 марта 2007 года
MrXaK
721 / / 31.12.2002
а я вам на первой странице что написал? для любых чисел всё находит, только подправить немного и учесть границы корней)
72
08 марта 2007 года
kosfiz
1.6K / / 18.09.2005
[quote=Mr.Hacker]а я вам на первой странице что написал? для любых чисел всё находит, только подправить немного и учесть границы корней)[/quote]
так я у Sara интересуюсь почему она находит только действительный корень(мой-то код все обрабатывает).
420
08 марта 2007 года
nilbog
507 / / 19.12.2006
вообще говоря этот метод должен находить уединенный действительный корень на отрезке
72
08 марта 2007 года
kosfiz
1.6K / / 18.09.2005
[quote=nilbog]вообще говоря этот метод должен находить уединенный действительный корень на отрезке[/quote]
ну да. так называемый отрезок локализации о нем уже писалось.
15K
08 марта 2007 года
Sara
79 / / 04.01.2007
Цитата: kosfiz
вздумалось попробвать данный код(ничего не менял) и получил ответ x=1,41... сразу видно, что выражение x^3+2*x^2-6*x-3 при таком x никак не будет равно 0 даже приблизительно.


Прежде чем такое писать, хоть бы на калькуляторе проверили, что ли :(
Я же не зря вставила в свою программу вот эту строку

 
Код:
Edit5->Text = FloatToStr(f(x));

Это сделано специально для проверки правильности решения.
Корень равен 1,41921801120043 с точностью 1E-8, значение функции в этой точке равно 1,38429245810992E-7.

Цитата: kosfiz

и еще мне вот интересно, а почему ищем только один корень? ну допустим действительный только один(остальные комплексные вроде - не проверял), но мы же можем получить приближенный действительный корень(корни)(естественно корень будет на малом отрезке, на котором функция меняет знак), при котором функция будет приблизительно равна 0(т.е. будет приблизительно выполнять равенство F(x)=0), что учитывая, что метод половинного деления относится к приближенным вполне нас устраивает.


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

72
08 марта 2007 года
kosfiz
1.6K / / 18.09.2005
2Sara
1.[quote=Sara]Прежде чем такое писать, хоть бы на калькуляторе проверили, что ли
Я же не зря вставила в свою программу вот эту строку
 
Код:
Edit5->Text = FloatToStr(f(x));

Это сделано специально для проверки правильности решения.
Корень равен 1,41921801120043 с точностью 1E-8, значение функции в этой точке равно 1,38429245810992E-7[/quote]
вообщем пишу еще раз получилось у меня 1.41, если посчитаем с помощью калькулятора, т.е. 1.41^3+2*1.41^2-6*1.41-3=-4.6 приблизительно. но смотри свой код, а точнее строку:
 
Код:
double f( double x )
{
  return x*x*x* + x*x*2 - x*6 - 3;
}

я за тобой код проверять не стал(а зря) и скопировал к себе. вот здесь и получилось неразбериха, если я уберу последний *, то получится ответ x=1.9296, что дает приблизительно равенство 0 значения функции при данном х.
2. [quote=Sara]Насколько мне известно, метод половинного деления позволяет найти только действительные корни. Если вы придумаете какую-либо модификацию этого метода для комплексных чисел, буду очень признательна.[/quote]
да действительно находит только действительные корни. я говорю о том, что можно найти действительный корень, который бы был близок к тому, чтобы быть корнем, т.е. F(x)=0. в данном случае почему бы не взять -3.4775 и -0.4475 значение функции близко 0 в них + на малых отрезках 0.000001, в которые они входят функция меняет знак. так что на мой взгляд они могут быть признаны корнями пусть и приближенно.

P.S. неужели ты думаешь я хотел тебя обидеть или покритиковать? но если обидел или задел - прости, честное слово не хотел.
420
09 марта 2007 года
nilbog
507 / / 19.12.2006
Цитата: kosfiz

да действительно находит только действительные корни. я говорю о том, что можно найти действительный корень, который бы был близок к тому, чтобы быть корнем, т.е. F(x)=0. в данном случае почему бы не взять -3.4775 и -0.4475 значение функции близко 0 в них + на малых отрезках 0.000001, в которые они входят функция меняет знак. так что на мой взгляд они могут быть признаны корнями пусть и приближенно.


погрешность можно легко оценить
(b-a)/2^n n - n'ый шаг
легко видеть что в пределе у нас получиться точное значение
ну а при реализации у нас неминуемо получится приближенно
хотя бы если взять представление вещ чисел

15K
09 марта 2007 года
Sara
79 / / 04.01.2007
Цитата: kosfiz
2Sara
1.
вообщем пишу еще раз получилось у меня 1.41, если посчитаем с помощью калькулятора, т.е. 1.41^3+2*1.41^2-6*1.41-3=4.6 приблизительно. но смотри свой код, а точнее строку:
 
Код:
double f( double x )
{
  return x*x*x* + x*x*2 - x*6 - 3;
}

я за тобой код проверять не стал(а зря) и скопировал к себе. вот здесь и получилось неразбериха, если я уберу последний *, то получится ответ x=1.9296, что дает приблизительно равенство 0 значения функции при данном х.


Да, действительно, опечатка вышла :)
Теперь исправила. Получился корень 1,9254229.

Кстати, корни -3,47735 и -0,44807 моя программа тоже находит, если задать отрезки [-4,-3] и [-1,0]. Почему сначала я подумала, что только один действительный корень? Возможно, вы будете смеяться, но я... неправильно посчитала дискриминант :)

72
09 марта 2007 года
kosfiz
1.6K / / 18.09.2005
вот, собственно, переделал свой код для проивольных значений a, b, c, d:
Код:
#include <iostream.h>
#include <stdlib.h>
#pragma hdrstop
#pragma argsused

double func(double x, double* coeff)
{
        return coeff[0]*x*x*x+coeff[1]*x*x+coeff[2]*x+coeff[3];
}

double poldel(double x1, double x2, double eps, double* coeff) //ищем корень методом половинного деления на указанном с помощью x1 и x2 отрезке локализации
{
    double a,b,c,f1,f2;
    a=x1;
    b=x2;
    do{
        c=(a+b)/2;
        f1=func(a, coeff);
        f2=func(b, coeff);
        if (f1*f2<=0){
            b=c;
        }else{
            a=c;
        }
    }while((b-a)>=2*eps);
    return (a+b)/2;
}

int main(int argc, char* argv[])
{
        double coeff[4];
        double y2,y1,x1,x2;
        int i;
        double a, b, h, eps;
        cin>>a; //левая граница отрезка на котором надо искать корни
        cin>>b; //правая граница отрезка
        cin>>h; //шаг необходим для определения отрезков локализации
        cin>>eps; //точность
        for (i=0;i<4;i++)cin>>coeff; //последовательно вводим a, b, c, d
        x1=a;    //дальнейший код - поиск отрезков локализации
    x2=a+h;
    while(x2<b){
        y1=func(x1, coeff);
        y2=func(x2, coeff);
        if (y1*y2<=0){
                        //если отрезок локализации найден, то ищем на данном отрезке корень методом половинного деления
                        cout<<"x= "<<poldel(x1, x2, eps, coeff)<<endl; //выводим корень
                        out<<"F(x)="<<func(poldel(x1,x2,eps,coeff),coeff)<<endl; //выводим значение функции в корне
        };
        x1=x2;
        x2+=h;
    }
        system("pause");
    return 0;
}

код можно сократить на пару строк, но я этого намеренно делать не стал.

7:35 по Москве. можно впринципе все это сделать и для полинома степени n, т.е. x^n+x^(n-1)+...+x^1+x^0 и с произвольными коэффициентами при x.
420
09 марта 2007 года
nilbog
507 / / 19.12.2006
kosfiz ужасно непродуктивный способ шажками искать отрезки
да и не красивый
если уж хотите для произвольных коэфицентов то будьте добры исследуйте производную в общем виде, определите число корней и тд и тп
благо произв всего 2 степени а такие ур-я решать мы можем "точно" ;)
15K
09 марта 2007 года
Sara
79 / / 04.01.2007
2 kosfiz:

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

2. Если значения функции на концах отрезка имеют разные знаки, то из этого следует, что на данном отрезке имеется нечетное число корней (с учетом кратности), но вовсе не обязательно один.

В общем, как ни крути, а без дифференцирования тут не обойтись :)

P.S.
Кстати, я у многих видела вот такой способ проверки:
 
Код:
if( f1*f2 <= 0 )

Как я понимаю, это пишется вместо условия
 
Код:
if( (f1 <= 0 && f2 >= 0) || (f1 >= 0 && f2 <= 0) )

Конечно, первая запись выглядит короче, но для программиста это довольно странный способ "оптимизации" кода. Во-первых, операция умножения (особенно для чисел с плавающей запятой) выполняется дольше, чем операции сравнения. Во-вторых, когда f1 и f2 достаточно малые числа (но не нули), их произведение может оказаться почти нулевым, и программа примет его за 0. Так что второй способ ИМХО все же более оптимален.
Впрочем, это уже мелочи :)
72
09 марта 2007 года
kosfiz
1.6K / / 18.09.2005
[quote=nilbog]kosfiz ужасно непродуктивный способ шажками искать отрезки
да и не красивый
если уж хотите для произвольных коэфицентов то будьте добры исследуйте производную в общем виде, определите число корней и тд и тп
благо произв всего 2 степени а такие ур-я решать мы можем "точно"[/quote]
некрасивый и непродуктивный так пусть: я и не претендую на красоту и продуктивность. код работает, а пользоваться им или нет это уже дело каждого.
[quote=Sara]1. Я уже говорила о случае кратных корней. Напоминаю: если корень имеет кратность 2 (или вообще любое четное число), то функция в этой точке не пересекает ось, а лишь касается ее, т.е. смены знака не происходит. Этот корень тоже можно найти методом половинного деления, но применять его надо не к самой функции, а к ее производной.[/quote]
знаю. просто хочу отметить, что данный метод, т.е. метод половинного деления(дихотомия), неприменим к корням четной кратности, т.е. само то, что в задании присутствует фраза:"метод половинного деления", говорит о том, что дается поблажка на нахождение корней четной кратности. кстати у этого метода есть проблемы и с нечетными корнями высокой кратности.
[quote=Sara]2. Если значения функции на концах отрезка имеют разные знаки, то из этого следует, что на данном отрезке имеется нечетное число корней (с учетом кратности), но вовсе не обязательно один.[/quote]
и с этим я не спорю(это все знают - прописные истины, можно сказать), но если взять малый отрезок(шаг), то большая вероятность того, что корень на нем будет один(хотя, конечно, и работать все будет гораздо дольше).

в заключении: может метод предложенный мной и кривоват и некрасив, но по-крайней мере единственное, что требуется - это ввести все параметры(без каких-либо аналитических манипуляций). если вы хотите получать все точно и все учитывать, тогда зачем вообще численные методы? приближенность корней и т.д., какие-то еще потери - все это учитывается при выборе метода, так что пункты 1 и 2 лично я считаю несущественными. и еще раз повторюсь пользоваться кодом или нет дело каждого. хотите напишите свой код, но мой тоже имеет право на существование.

P.S. кстати помоему все здесь сравнивали длину отрезка с eps, т.е.
 
Код:
while( fabs(x1-x2) > eps )

или
 
Код:
until (b-a)<eps;
.
разве деление не должно продолжаться пока отрезок не будет меньше 2*eps? т.е. и там и там должно быть 2*eps.
15K
09 марта 2007 года
Sara
79 / / 04.01.2007
Цитата: kosfiz
разве деление не должно продолжаться пока отрезок не будет меньше 2*eps? т.е. и там и там должно быть 2*eps.


Хм... Сейчас разберемся :)
Когда говорят "найти решение с точностью eps", обычно подразумевают вот такое неравенство (я уверена, что почти всем это известно, но на всякий случай напишу)

 
Код:
|x-x*| <= eps

где x - точное решение, x* - приближенное (или наоборот).

Теперь давайте посмотрим, что будет, если в моей функции заменить eps на 2*eps.
Выход из цикла произойдет, когда fabs(x1-x2) <= 2*eps. После этого произойдет присваивание *x = x12. Чему будет равен x12 к этому моменту? Очевидно, он будет совпадать с одим из значений x1 или x2. Т.е. в качестве решения берется один из концов отрезка, а длина отрезка <=2*eps. Рассмотрим худший случай, когда длина отрезка составляет 2*eps, точное решение находится вблизи точки x2, а в качестве приближенного мы взяли x1. В этом случае модуль разности |x-x*| будет равен 2*eps, т.е. нужная точность не будет обеспечена.

Вот если, кроме этого, еще заменить строку
 
Код:
*x = x12;

на строку
 
Код:
*x = (x1+x2)/2;

тогда все будет OK. Но мой первоначальный вариант тоже позволяет найти решение с точность eps. Правда, в новом варианте итераций будет на 1 меньше... Но это, на мой взгляд, как раз несущественно.

А вот насчет кратных корней - извините, но ни о каких "поблажках" речь не шла. Если бы Вы сказали это одному из наших преподов, зачет бы Вам не поставили :)
Чем кратные корни хуже других? Тем более, найти их методом половинного деления можно, только для этого надо вычислить производную. Кстати, а в чем проблема с нахождением нечетных корней высокой кратности?

Цитата: kosfiz

если взять малый отрезок(шаг), то большая вероятность того, что корень на нем будет один(хотя, конечно, и работать все будет гораздо дольше).


Что значит "большая вероятность"? Может быть, Вы знаете, как посчитать эту вероятность? Или хотя бы приближенно оценить ее? ;) Если уж заговорили о вероятности, извольте обосновать свои суждения.

Цитата: kosfiz

если вы хотите получать все точно и все учитывать, тогда зачем вообще
численные методы?


Да, численные методы не могут дать нам точное решение. У каждого метода есть определенная погрешность. Но эту погрешность можно оценить! Т.е. если я задаю погрешность eps, то я могу утверждать, что найденное решение будет отличаться от точного не более чем на eps. Вот для этого и нужны численные методы.

А если погрешность метода нельзя оценить, то этот метод действительно бесполезен.

85
09 марта 2007 года
MrXaK
721 / / 31.12.2002
если есть кратный корень кратности 2, то есть ещё один действительный корень... корень кратности два будет равен или локальному минимуму, или локальному максимуму и без половинного деления... оставшийся корень успешно находится методом половинного деления, где функция меняет знак...
з.ы. да и вообще для кубического уравнения можно прекрасно найти все корни без всех методов половинного деления... вот для высоких степений кратности уже проблема...
25K
09 марта 2007 года
Nik.rus
6 / / 05.03.2007
Здравствуйте можете внести поправочку в тексте программы Найти корни уравнения: a * x^3+ b*x^2+ c*x + d = 0 с точностью до 0.01
Вместо компонентов a, b, c и d записать заданные значения полинома, где а=1, b=2, с= -6, d= -3, Корни найти методом половинного деления.
сама формула в первый раз была не точной
15K
09 марта 2007 года
Sara
79 / / 04.01.2007
Цитата: Mr.Hacker
если есть кратный корень кратности 2, то есть ещё один действительный корень... корень кратности два будет равен или локальному минимуму, или локальному максимуму и без половинного деления... оставшийся корень успешно находится методом половинного деления, где функция меняет знак...
з.ы. да и вообще для кубического уравнения можно прекрасно найти все корни без всех методов половинного деления... вот для высоких степений кратности уже проблема...


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

25K
09 марта 2007 года
Nik.rus
6 / / 05.03.2007
Цитата: kosfiz
вот, собственно, переделал свой код для проивольных значений a, b, c, d:
Код:
#include <iostream.h>
#include <stdlib.h>
#pragma hdrstop
#pragma argsused

double func(double x, double* coeff)
{
        return coeff[0]*x*x*x+coeff[1]*x*x+coeff[2]*x+coeff[3];
}

double poldel(double x1, double x2, double eps, double* coeff) //ищем корень методом половинного деления на указанном с помощью x1 и x2 отрезке локализации
{
    double a,b,c,f1,f2;
    a=x1;
    b=x2;
    do{
        c=(a+b)/2;
        f1=func(a, coeff);
        f2=func(b, coeff);
        if (f1*f2<=0){
            b=c;
        }else{
            a=c;
        }
    }while((b-a)>=2*eps);
    return (a+b)/2;
}

int main(int argc, char* argv[])
{
        double coeff[4];
        double y2,y1,x1,x2;
        int i;
        double a, b, h, eps;
        cin>>a; //левая граница отрезка на котором надо искать корни
        cin>>b; //правая граница отрезка
        cin>>h; //шаг необходим для определения отрезков локализации
        cin>>eps; //точность
        for (i=0;i<4;i++)cin>>coeff; //последовательно вводим a, b, c, d
        x1=a;    //дальнейший код - поиск отрезков локализации
    x2=a+h;
    while(x2<b){
        y1=func(x1, coeff);
        y2=func(x2, coeff);
        if (y1*y2<=0){
                        //если отрезок локализации найден, то ищем на данном отрезке корень методом половинного деления
                        cout<<"x= "<<poldel(x1, x2, eps, coeff)<<endl; //выводим корень
                        out<<"F(x)="<<func(poldel(x1,x2,eps,coeff),coeff)<<endl; //выводим значение функции в корне
        };
        x1=x2;
        x2+=h;
    }
        system("pause");
    return 0;
}

код можно сократить на пару строк, но я этого намеренно делать не стал.

7:35 по Москве. можно впринципе все это сделать и для полинома степени n, т.е. x^n+x^(n-1)+...+x^1+x^0 и с произвольными коэффициентами при x.



Здравствуйте именно такая формула используется в первом случае? Найти корни уравнения: a * x^3+ b*x^2+ c*x + d = 0 с точностью до 0.01 :confused:

420
09 марта 2007 года
nilbog
507 / / 19.12.2006
Цитата: kosfiz
некрасивый и непродуктивный так пусть: я и не претендую на красоту и продуктивность. код работает, а пользоваться им или нет это уже дело каждого.


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

кстати тогда уж почему бы нам корень не искать шажками :D

15K
09 марта 2007 года
Sara
79 / / 04.01.2007
Цитата: Nik.rus
Здравствуйте можете внести поправочку в тексте программы Найти корни уравнения: a * x^3+ b*x^2+ c*x + d = 0 с точностью до 0.01
Вместо компонентов a, b, c и d записать заданные значения полинома, где а=1, b=2, с= -6, d= -3, Корни найти методом половинного деления.
сама формула в первый раз была не точной


Все, я уже не выдерживаю, начинаю ругаться :mad:
Nik.rus, какой же ты программист, если ты даже задачу правильно сформулировать не можешь?

Цитата: Nik.rus

Вместо компонентов a, b, c и d...


Ты хоть понимаешь, что компоненты и коэффициенты - это, вообще говоря, разные вещи? :D
Ну, ладно бы один раз - можно было бы подумать, что опечатка, но когда человек второй раз такой "перл" выдает...

Цитата: Nik.rus

записать заданные значения полинома...


Так что же все-таки задано? Значения полинома или его коэффициенты?

Цитата: Nik.rus

сама формула в первый раз была не точной


Какая формула? О чем вообще речь?

72
09 марта 2007 года
kosfiz
1.6K / / 18.09.2005
[quote=nilbog]я имел ввиду под словом некрасивый немножко другое[/quote]
да я понял что ты имел ввиду просто выразился неправильно. о всех ограничениях и недостатках предложенного мной способа знаю.

1.[quote=Sara]Хм... Сейчас разберемся
Когда говорят "найти решение с точностью eps", обычно подразумевают вот такое неравенство (я уверена, что почти всем это известно, но на всякий случай напишу)
 
Код:
|x-x*| <= eps

где x - точное решение, x* - приближенное (или наоборот).[/quote]
я процитирую
[quote=]Если требуется найти корень с точностью eps, то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2*eps. Тогда середина отрезка даст значение корня с требуемой точностью.[/quote]

2.[quote=Sara]Чем кратные корни хуже других? Тем более, найти их методом половинного деления можно, только для этого надо вычислить производную.[/quote]
опять цитирую
[quote=]Метод неприменим к корням четной кратности.[/quote]

3.[quote=Sara]Кстати, а в чем проблема с нахождением нечетных корней высокой кратности?[/quote]
а я разве писал про проблему нахождения? смотрим
[quote=kosfiz]кстати у этого метода есть проблемы и с нечетными корнями высокой кратности.[/quote]
я не конкретизировал. просто метод половинного деления для таких корней менее точен и хуже устойчив к ошибкам.

4.[quote=Sara]Что значит "большая вероятность"? Может быть, Вы знаете, как посчитать эту вероятность? Или хотя бы приближенно оценить ее? Если уж заговорили о вероятности, извольте обосновать свои суждения.[/quote]
отвечу вопросом. представим, что у нас есть отрезок длиной 10(-6). много ли будет функций, имеющих корни(минимум три) на этом отрезке?(прямую, совпадающую с осью X, брать во внимание не будем)

5.[quote=Sara]Да, численные методы не могут дать нам точное решение. <skip>. Вот для этого и нужны численные методы.[/quote]
я знаю для чего они нужны).

Цитировал я этого человека.

вообщем повторюсь: я все недостатки своего метода прекрасно знаю.

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

2 All
вам не кажется, что автор темы сам не знает чего хочет?
мы тут пытаемся ему помочь, друг с другом спорим, стараемся, а он.... вообщем слов нету.
85
09 марта 2007 года
MrXaK
721 / / 31.12.2002
автор лол) по-моему он гулял весь семестр, а ща вспомнил, что сессию надо закрыть))

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

точность уже другая беда... для любого eps можно подобрать функцию, которая на отрезке <eps будет иметь >1 корня... но 1e-4 для большинства инженерных задач хватает... студентам тем более) для самых точных расчётов всё равно хватает точности, которой обеспечивает нас тип double...
25K
14 марта 2007 года
Nik.rus
6 / / 05.03.2007
Спасибо большое всем кто мне помогал))) Ваша помощь мне пригодилась)) Эту тему можно закрыть ))) Спасибо ))

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог