Пусть имеется уравнение вида
{\displaystyle{f(x)=0}}
где {\displaystyle{f(x)}} — заданная алгебраическая или трансцендентная функция.
Решить уравнение — значит, найти все его корни, то есть те значения {\displaystyle{x}}, которые обращают уравнение в тождество.
Если уравнение достаточно сложно, то задача точного определения корней является в некоторых случаях нерешаемой. Поэтому ставится задача найти такое приближенное значение корня {\displaystyle{x_{ПР}}}, которое отличается от точного значения корня {\displaystyle{x^*}} на величину, по модулю не превышающую указанной точности (малой положительной величины) {\displaystyle{ \varepsilon}}, то есть
{\displaystyle{|x^* \ — \ x_{ПР}| \lt \varepsilon}}
Величину {\displaystyle{ \varepsilon}} также называют допустимой ошибкой, которую можно задать по своему усмотрению.
Этапы приближенного решения нелинейных уравнений
Приближенное решение уравнения состоит из двух этапов:
- Отделение корней, то есть нахождение интервалов из области определения функции {\displaystyle{f(x)}}, в каждом из которых содержится только один корень уравнения {\displaystyle{f(x)=0}}.
- Уточнение корней до заданной точности.
Отделение корней можно проводить графически и аналитически.
Графическое отделение корней
Для того чтобы графически отделить корни уравнения, необходимо построить график функции {\displaystyle{f(x)}}. Абсциссы точек его пересечения с осью Ox являются действительными корнями уравнения.
Для примера рассмотрим задачу решения уравнения
{\displaystyle{sin(x)= \frac {1} {x}}},
где угол {\displaystyle{x}} задан в градусах.
Указанное уравнение можно переписать в виде
{\displaystyle{sin \left( \frac {\pi} {180} \cdot x \right) — \frac {1} {x} = 0}}
Для графического отсечения корней достаточно построить график функции
Из рисунка видно, что корень уравнения лежит в промежутке {\displaystyle{x \in (6; 8)}}
Аналитическое отделение корней
Аналитическое отделение корней основано на следующих теоремах.
Теорема 1. Если непрерывная функция {\displaystyle{f(x)}} принимает на концах отрезка {\displaystyle{[a; b]}} значения разных знаков, т.е.
{\displaystyle{f(a) \cdot f(b) \lt 0}}
то на этом отрезке содержится по крайней мере один корень уравнения.
Теорема 2. Если непрерывная на отрезке {\displaystyle{[a; b]}} функция {\displaystyle{f(x)}} принимает на концах отрезка значения разных знаков, а производная {\displaystyle{f'(x)}} сохраняет знак внутри указанного отрезка, то внутри отрезка существует единственный корень уравнения {\displaystyle{f(x)=0}}.
Уточнение корней
Для уточнения корней может использоваться один из следующих методов:
- Метод последовательных приближений (метод итераций)
- Метод Ньютона (метод касательных)
- Метод секущих (метод хорд)
- Метод половинного деления (метод дихотомии)
Во всех реализациях используется переменная iter, которая ограничивает количество итераций для предотвращения зависания алгоритма (если начальные приближения не были найдены корректно).
Метод последовательных приближений (метод итераций)
Метод итерации — численный метод решения математических задач, используемый для приближенного решения алгебраических уравнений и систем. Суть метода заключается в нахождении по приближенному значению величины следующего приближения (являющегося более точным). Метод позволяет получить решение с заданной точностью в виде предела последовательности итераций. Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения решения.
Функциональное уравнение может быть записано в виде
{\displaystyle{x=f(x)}}
Функцию {\displaystyle{f(x)}} называют сжимающим отображением.
Последовательность чисел {\displaystyle{x_0, x_z, …, x_n}} называется итерационной, если для любого номера {\displaystyle{n \gt 0}} элемент {\displaystyle{x_n}} выражается через элемент {\displaystyle{x_{n-1}}} по рекуррентной формуле
{\displaystyle{x_n=f(x_{n-1})}}
а в качестве {\displaystyle{x_{0}}} взято любое число из области задания функции {\displaystyle{f(x)}}.
Реализация на C++ для рассмотренного выше примера
{\displaystyle{sin \left( \frac {\pi}{180} \cdot x \right)= \frac {1} {x}}}
Уравнение может быть записано в форме
{\displaystyle{x = \frac {1} {sin \left( \displaystyle{ \frac {\pi} {180} \cdot x }\right)}}}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cmath>
using namespace std;
double find(double x, double eps)
{
double rez; int iter = 0;
cout << "x0= " << x << " ";
do
{
rez = x;
x = 1 / (sin(M_PI * x / 180));
iter++;
} while (fabs(rez - x) > eps && iter < 20000);
cout << iter << " iterations" << endl;
return x;
}
int main()
{
cout << find(7, 0.00001);
cin.get();
return 0;
}
Результат выполнения
Метод Ньютона (метод касательных)
Если известно начальное приближение {\displaystyle{x_0}} корня уравнения {\displaystyle{f(x)=0}} , то последовательные приближения находят по формуле
{\displaystyle{x_i = x_{i-1} — \displaystyle{ \frac {f(x_{i-1})} {f'(x_{i-1})}}}}
Графическая интерпретация метода касательных имеет вид
Реализация на C++
Для заданного уравнения
{\displaystyle{f(x)=sin \left( \frac {\pi} {180} \cdot x \right) — \frac {1} {x} = 0}}
производная будет иметь вид
{\displaystyle{f'(x)= \frac {\pi}{180} \cdot cos \left( \frac {\pi} {180} \cdot x \right) + \frac {1} {x^2}}}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cmath>
using namespace std;
double find(double x, double eps)
{
double f, df; int iter = 0;
cout << "x0= " << x << " ";
do
{
f = sin(M_PI * x / 180) - 1 / x;
df = M_PI / 180 * cos(M_PI * x / 180) + 1 / (x * x);
x = x - f / df;
iter++;
} while (fabs(f) > eps && iter < 20000);
cout << iter << " iterations" << endl;
return x;
}
int main()
{
cout << find(1, 0.00001);
cin.get(); return 0;
}
Результат выполнения
Метод секущих (метод хорд)
Если {\displaystyle{x_0, x_1}} — приближенные значения корня уравнения {\displaystyle{f(x)=0}} и выполняется условие {\displaystyle{f(x_0) \cdot f(x_1) \lt 0}}, то последующие приближения находят по формуле
{\displaystyle{x_i = x_{i-1} — \displaystyle{\frac {f(x_{i-1})}{f(x_{i-1}) — f(x_{i-2})}} \cdot (x_{i-1} — x_{i-2})}}
Методом хорд называют также метод, при котором один из концов отрезка закреплен, т.е. вычисление приближения корня уравнения {\displaystyle{f(x_0) = 0}} производят по формулам:
{\displaystyle{x_i = x_{i-1} — \displaystyle{\frac {f(x_{i-1})}{f(x_{i-1}) — f(x_0)}} \cdot (x_{i-1} — x_0)}}
Геометрическая интерпретация метода хорд:
Реализация на C++
В отличие от двух рассмотренных выше методов, метод хорд предполагает наличие двух начальных приближений, представляющих собой концы отрезка, внутри которого располагается один искомый корень.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cmath>
using namespace std;
double find(double x0, double x1, double eps)
{
double rez = x1, f0, f;
int iter = 0;
cout << "x0= " << x0 << " x1= " << x1 << " ";
do
{
f = sin(M_PI * rez / 180) - 1 / rez;
f0 = sin(M_PI * x0 / 180) - 1 / x0;
rez = rez - f / (f - f0) * (rez - x0);
iter++;
} while (fabs(f) > eps && iter < 20000);
cout << iter << " iterations" << endl;
return rez;
}
int main()
{
cout << find(1.0, 10.0, 0.000001);
cin.get(); return 0;
}
Результат выполнения
Метод половинного деления (метод дихотомии)
Если {\displaystyle{x_0, x_1}} — приближенные значения корня уравнения {\displaystyle{f(x)=0}} и выполняется условие {\displaystyle{f(x_0) \cdot f(x_1) \lt 0}}, то последующие приближения находятся по формуле
{\displaystyle{x_i= \frac {x_{i-1} + x_{i-2}}{2}}}
и вычисляется {\displaystyle{f(x_i)}}. Если {\displaystyle{f(x_i)=0}}, то корень найден. В противном случае из отрезков выбирается тот, на концах которого {\displaystyle{f(x)}} принимает значения разных знаков, и проделывается аналогичная операция. Процесс продолжается до получения требуемой точности.
Геометрическая интерпретация метода дихотомии
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cmath>
using namespace std;
double func(double x)
{
return (sin(M_PI * x / 180) - 1.0 / x);
}
double find(double x0, double x1, double eps)
{
double left = x0, right = x1, x, fl, fr, f;
int iter = 0;
cout << "x0= " << x0 << " x1= " << x1 << " ";
do
{
x = (left + right) / 2;
f = func(x);
if (func(left) < 0) // если функция возрастающая
{
if (f > 0) right = x;
else left = x;
}
else // если функция убывающая
{
if (f < 0) right = x;
else left = x;
}
iter++;
} while (fabs(f) > eps && iter < 20000);
cout << iter << " iterations" << endl;
return x;
}
int main()
{
cout << find(1.0, 10.0, 0.000001);
cin.get();
return 0;
}
Результат выполнения
