3. Пошук наближених коренів системи нелінійних рівнянь

Частина задач контрольної роботи стосується знаходження точок перетину графіків двох функцій однієї змінної та , причому принаймні одна з цих функцій є нелінійною. Для знаходження точного розв’язку, тобто, всіх точок , що належать одночасно графікам двох заданих функцій, слід розв’язати рівняння . Однак, лише для вузького класу нелінійних функцій можна знайти аналітичний розв’язок. Інакше розв’язки шукають чисельно.

Взагалі кажучи, існує ряд спеціально розроблених чисельних методів для розв’язання нелінійних рівнянь і їхніх систем, і цим методам присвячена окрема дисципліна. Однак, навіть не будучи знайомими з цими методами, можемо використати наступний інтуїтивно зрозумілий підхід. Спочатку визначають хоча б приблизні числові діапазони, в яких можуть знаходитися корені рівняння (цей процес іменують ізоляцією коренів). Кожен зі знайдених числових діапазонів розбивають на N рівновіддалених точок (вузлів). У вузлах рахують значення функцій та . Те значення , для якого модуль різниці двох функцій буде найменшим, імовірно, є ближчим до істинного значення шуканого кореня рівняння . Для точного значення шуканого кореня дорівнює нулю, для наближеного – значення прямує до нуля. Точність знайденого кореня тим вища, чим більшою є кількість вузлів. Цей підхід проілюстрований на рис. 2.

Рис. 2 Ілюстрація підходу до пошуку наближених точок перетину графіків двох функцій

Розглянемо для прикладу задачу знаходження точок перетину кола та параболи . Нагадаємо, що коло зручніше представити у параметричних координатах:

;

,

де – кут, що перебігає множину значень від 0 до 360º.

Для пошуку діапазонів, в яких знаходяться абсциси цих точок, можна використати наступний підхід. Перебрати у циклі значення кута з певним вибраним кроком. Знайти ті пари точок та , для яких значення функції змінює знак (з “+” на “–” або ж з “–” на “+”). Внаслідок неперервності функцій та їхня різниця теж є неперервною величиною. А це означає, що функція на проміжку перетинає 0, тобто корінь рівняння існує в цьому проміжку. Ілюстрацією до сказаного є рис. 3.

Рис. 3 Приклад підходу до ізоляції коренів

Реалізуємо найпростіший варіант функції для знаходження точок перетину кола та параболи.

#include <iostream>

#include "conio.h"

#include <math.h>

/* заголовок функції для знаходження заданого кореня */

double findIntersection(int, int, double, int);

using namespace std;

int main()

{

const int N = 360; /* змінна N визначає розмір масиву, тому оголошена з кваліфікатором const; 360 означає, що будемо розглядати 360 різних значень кута α, перебігаючи значення від 0 до 359 з кроком 1º. Взагалі кажучи, перебігати можливі значення α можна з більшим кроком, тоді визначені діапазони з ізольованими коренями будуть ширші */

const double PI = 3.14159265;

int cR, step = 1; /* cR – радіус кола (початок його у центрі координат), step – крок змінної циклу, встановлений в 1º */

cout<<"Circle's radius?"<<endl;

cin>>cR;

/* У масиви cXs і cYs будемо записувати абсциси та ординати точок кола для значень кута α від 0 до 359º з кроком 1, а у массив fYs[N] – ординати параболи для відповідних елементів масиву cXs */

double cXs[N], cYs[N], fYs[N];

for(int i = 0;i < N; i+=step){

/* Не забуваємо виражати градуси у радіанах! */

cXs[i] = cR*cos(i*PI/180);

cYs[i] = cR*sin(i*PI/180);

fYs[i] = (cXs[i])*(cXs[i]);

}

/* масив intersections створюємо для того, щоб зберігати у ньому значення тих кутів у градусах, в околі яких перетинають коло та парабола; у цьому масиві зарезервовано 8 елементів, хоча коло та парабола в дійсності можуть перетинаються менше, ніж у 2 точках */

int K = 0; int intersections[10];

for(int i = 0; i < N-1; i++){

/* порівнюємо пари сусідніх відповідних елементів масивів cYs і fYs з метою виявлення тих значень кута α, для яких різниця сYs – fYs змінює знак, і запам’ятовуємо ці значення кута в масив intersections */

if((cYs[i]<=fYs[i])&&(cYs[i+1]>=fYs[i+1]))

{ intersections[K] = i; K++;}

if((cYs[i]>=fYs[i])&&(cYs[i+1]<=fYs[i+1]))

{intersections[K] = i; K++;}

}

/* У змінні startI та endI будемо записувати кути у градусах, що є початком і кінцем відповідно кожного діапазону з ізольованими коренями; для уникнення можливості непопадання кореня в діапазон його межі встановлюємо “з запасом”: якщо кут у градусах є більший за 0, то за нижню межу приймаємо попереднє розглянуте значення кута; верхню межу встановлюємо аналогічно */

int startI, endI;

for(int i = 0; i < K; i++){

(intersections[i] > 0)?(startI = intersections[i]-1):(startI = intersections[i]);

(intersections[i] < (N - 1))?(endI = intersections[i] + 1):(endI = intersections[i]);

/* для знаходження кореня викликаємо функцію findIntersection, якій передаємо межі діапазону, значення константи PI та радыус кола */

cout<<"bestAngle: "<<"\t";

double bestAngle = findIntersection(startI,endI,PI,cR);

/* виводимо на екран значення кута α, при якому є перетин кола з параболою, та координати х, y відповідної точки */

cout<<bestAngle<<" rad= "<<bestAngle*(180/PI)<<" grad"<<endl;

cout<<"best value of X: "<<cR*cos(bestAngle)<<endl;

cout<<"sin: "<<cR*sin(bestAngle)<<"\t"<<"x^2: "<<(cR*cos(bestAngle))*(cR*cos(bestAngle));

cout<<endl;

}

_getch();

}

double findIntersection(int startI, int endI, double PI, int cR){

int points = 1000; // кількість вузлів

/* у змінну bestResidual будемо записувати так звану “нев’язку” – модуль різниці між значенням y = Rsinα та y = x² ; очевидно, що найменшому значенню bestResidual відповідає значення кута, при якому значення х найбільш наближене до істинного кореня рівняння y = Rsinα та y = x² */

double cX, cY, fY, bestResidual = 100, bestAngle = -1, step = (PI/180)*(endI - startI)/points;

for(double angle = startI*PI/180; angle < endI*PI/180; angle+=step) {

cX = cR*cos(angle);

cY = cR*sin(angle);

fY = cX*cX;

if(fabs(cY - fY) < bestResidual)

{

bestResidual = fabs(cY - fY);

bestAngle = angle;

}

}

return bestAngle;

}

Зауваження до наведеного коду.

1. У даному конкретному випадку точок перетину двох кривих може бути не більше 2³ = 8. Однак, в залежності від функцій, кількість точок перетину їхніх графіків і, відповідно, довжина вектора intersections може бути різною. Тому масив intersections, взагалі кажучи, бажано будувати не статичним, а динамічним.

2. В ряді запропонованих у контрольній роботі задач передбачають, що центр кола не співпадає з початком координат. Наведений код не працюватиме коректно у цьому випадку.

3. У наведеному коді числовий діапазон, де знаходиться шуканий корінь, один раз розбивається на стільки точок, скільки вказано у змінній points. Це не найкращий підхід, оскільки, як ми знаємо, корінь в цьому діапазоні лише один, а тому інформативною є перевірка лише найближчих двох до нього точок, тоді як перевірка (points – 2) точок нічого не дає. Краще наближатися до шуканого значення поступово, кожного разу звужуючи діапазон пошуку. Для цього доцільно організувати рекурсію.

Приклад виконання при радіусі 3 показано на рис. 4.

Рис. 4 Приклад виконання коду

Зазначені зауваження слід урахувати при розробленні програмних кодів для вирішення аналогічних завдань.