Пусть имеется уравнение вида
f(x)= 0
где f(x) — заданная алгебраическая или трансцендентная функция.
Решить уравнение — значит найти все его корни, то есть те значения x, которые обращают уравнение в тождество.
Если уравнение достаточно сложно, то задача точного определения корней является в некоторых случаях нерешаемой. Поэтому ставится задача найти такое приближенное значение корня xПP, которое отличается от точного значения корня x* на величину, по модулю не превышающую указанной точности (малой положительной величины) ε, то есть
│x* – xпр │< ε
Величину ε также называют допустимой ошибкой, которую можно задать по своему усмотрению.
Этапы приближенного решения нелинейных уравнений
Приближенное решение уравнения состоит из двух этапов:
- Отделение корней, то есть нахождение интервалов из области определения функции f(x), в каждом из которых содержится только один корень уравнения f(x)=0.
- Уточнение корней до заданной точности.
Отделение корней
Отделение корней можно проводить графически и аналитически.
Для того чтобы графически отделить корни уравнения, необходимо построить график функции f(x). Абсциссы точек его пересечения с осью Ox являются действительными корнями уравнения.
Для примера рассмотрим задачу решения уравнения
где угол x задан в градусах. Указанное уравнение можно переписать в виде
Для графического отсечения корней достаточно построить график функции
Из рисунка видно, что корень уравнения лежит в промежутке x∈(6;8).
Аналитическое отделение корней
Аналитическое отделение корней основано на следующих теоремах.
Теорема 1. Если непрерывная функция f(x) принимает на концах отрезка [a; b] значения разных знаков, т.е.
то на этом отрезке содержится по крайней мере один корень уравнения.
Теорема 2. Если непрерывная на отрезке [a; b] функция f(x) принимает на концах отрезка значения разных знаков, а производная f'(x) сохраняет знак внутри указанного отрезка, то внутри отрезка существует единственный корень уравнения f(x) = 0.
Уточнение корней
Для уточнения корней может использоваться один из следующих методов:
- Метод последовательных приближений (метод итераций)
- Метод Ньютона (метод касательных)
- Метод секущих (метод хорд)
- Метод половинного деления (метод дихотомии)
Метод последовательных приближений (метод итераций)
Метод итерации — численный метод решения математических задач, используемый для приближённого решения алгебраических уравнений и систем. Суть метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным). Метод позволяет получить решение с заданной точностью в виде предела последовательности итераций. Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения решения.
Функциональное уравнение может быть записано в виде
Функцию f(x) называют сжимающим отображением.
Последовательность чисел x0, x1 ,…, xn называется итерационной, если для любого номера n>0 элемент xn выражается через элемент xn-1 по рекуррентной формуле
а в качестве x0 взято любое число из области задания функции f(x).
Реализация на C++ для рассмотренного выше примера
Уравнение может быть записано в форме
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
}
Результат выполнения
Метод Ньютона (метод касательных)
Если известно начальное приближение x0 корня уравнения f(x)=0, то последовательные приближения находят по формуле
Графическая интерпретация метода касательных имеет вид
Реализация на C++
Для заданного уравнения
производная будет иметь вид 
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
}
Метод секущих (метод хорд)
Если x0, x1 - приближенные значения корня уравнения f(x) = 0 и выполняется условие
то последующие приближения находят по формуле
Методом хорд называют также метод, при котором один из концов отрезка закреплен, т.е. вычисление приближения корня уравнения f(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
#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;
}
Метод половинного деления (метод дихотомии)
Если x0, x1 - приближенные значения корня уравнения f(x) = 0 и выполняется условие
то последующие приближения находятся по формуле
и вычисляется f(xi). Если f(xi)=0, то корень найден. В противном случае из отрезков выбирается тот, на концах которого f(x) принимает значения разных знаков, и проделывается аналогичная операция. Процесс продолжается до получения требуемой точности.
Геометрическая интерпретация метода дихотомии
Реализация на C++
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
#include <iostream>
#include <cmath>
using namespace std;
double func(double x)
{
return (sin(M_PI*x / 180) - 1 / 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 (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;
}
Результат выполнения
Для численного поиска решения также можно использовать генетические алгоритмы.
Назад: Алгоритмизация
Комментариев к записи: 8