РОЗДІЛ 17. ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ АЛГЕБРАЇЧНИХ РІВНЯНЬ

17.1. Метод половинного ділення (дихотомія)

Якщо корінь відокремлений, то для знаходження кореня рівняння ділимо відрізок [а, b] навпіл: c = (а + b)/2. Обов'язково один з відрізків [а, c] або [c, b] задовольняє умовам теореми і містить корінь рівняння, але має довжину в два рази менше, ніж початковий. В результаті застосовуємо цей прийом до нового відрізку, і отримуємо послідовність вкладених відрізків, довжина яких прямує до 0, а кінці цих відрізків прямують до кореня заданого рівняння.

Наведемо фрагмент програми реалізації методу половинного ділення.

#include <iostream>

#include <cmath>

using namespace std;

#include <conio.h>

double func(double x)

{

return x*x + 5*x + 6;

}

// Розв’язання рівняння методом половинного ділення

// (знаходження тільки одного кореня)

void main()

{

double a,b,c,fa,fb,fc,eps;

a = -1000;

b = -2.5;

eps = 0.00000001;

fa = func(a);

fb = func(b);

if(fa*fb>0)

{

cout<<"Невірні значення a та b";

getch();

exit(0);

}

c = (a+b)/2;

fc = func(c);

while(fabs(a-b)>eps&&fabs(fc)>eps)

{

if(fc*fa<=0)

{

fb = fc;

b = c;

}

else

{

fa = fc;

a = c;

}

c = (a+b)/2;

fc = func(c);

}

cout<<"Корінь рівняння "<<c;

getch();

}

Таким чином даний метод на заданому відрізку має log₂(b-a) ітерацій, де a та b, відповідно, початок та кінець відрізку на якому знаходиться єдиний корінь рівняння. Слід зауважити, що у даному прикладі знайдено один корінь квадратного рівняння x² + 5x + 6 = 0, що знаходиться на проміжку [-1000; -2,5].

Результат виконання програми:

Корінь рівняння -3

17.2. Метод Ньютона (метод дотичних)

Нехай корінь рівняння f(x)= 0 відокремлений на відрізку [а, b], причому перша і друга похідна визначені, безперервні і зберігають певний знак на цьому відрізку. Тоді ітераційний процес Ньютона:

x_n+1 = x_n – f(x_n) /f'(x_n)

сходиться для будь-якого початкового наближення x₀, що належить відрізку [а, b]. Причому повинна виконуватися нерівність:

f(x₀)*f''(x₀)>0.

Оскільки f(a)*f(b)<0, то у якості x₀ зручно вибрати точку а або b залежно від того більше або менше нуля друга похідна функції f на відрізку [а, b]. Аналіз показує, що за будь-яких умов один з кінців відрізків можна взяти за початкове наближення процесу.

Наведемо фрагмент програми реалізації методу Ньютона (рівняння x² + 5x + 6 = 0, проміжок пошуку кореня [-1000; -2,5]).

#include <iostream>

#include <cmath>

using namespace std;

#include <conio.h>

double func(double x)

{

return x*x + 5*x + 6;

}

double difer1(double x,double h)

{

return (func(x+h)-func(x-h))/(2*h);

}

double difer2(double x,double h)

{

return (func(x+h)-2*func(x)+func(x-h))/(h*h);

}

// Розв’язання рівняння методом Ньютона

// (методом дотичних)

// (знаходження тільки одного кореня)

void main()

{

double a,b,fa,fa2,fb,h,eps;

double x,y,x1,y1;

long l,i,n;

n = 1000;

a = -1000;

b = -2.5;

eps = 0.00000001;

h = 0.00001;

fa = func(a);

fb = func(b);

if(fa*fb>0)

{

cout<<"Невірні значення a та b";

getch();

exit(0);

}

fa2 = difer2(a,h);

//Вибір нерухомого кінця відрізку

if(fa*fa2>0)

{

x = a;

l = 1;

}

else

{

x = b;

l = -1;

}

for(i=1;i<n;i++)

{

y = func(x);

y1 = difer1(x,h);

if(fabs(y1)<eps&&fabs(y)>eps)

{

cout<<"\nПерша похідна функції повинна бути знакопостійна!";

break;

}

x1 = x - y/y1;

if((l==1&&x>x1)||(l==-1&&x<x1))

{

cout<<"\nПорушені умови збіжності методу Ньютона!";

cout<<"\nКорінь рівняння не знайдено!";

break;

}

if(fabs(x-x1)<eps)

{

cout<<"\nКорінь рівняння "<<x1;

break;

}

else x = x1;

}//end for

if(i==n)cout<<"\nКорінь рівняння не знайдено!";

getch();

}

Результат виконання програми:

Корінь рівняння -3

Методи, розглянуті вище, призначені для пошуку лише одного кореня рівняння. Якщо їх декілька, необхідно знаходити такі проміжки пошуку, де буде знаходитись один корінь. Для пошуку всіх дійсних коренів рівняння використовується метод Рибакова.