Численные методы решения нелинейных уравнений

Алгоритмизация / Численные методы решения нелинейных уравнений

 

Пусть имеется уравнение вида

f(x)= 0

где f(x) — заданная алгебраическая или трансцендентная функция.

Решить уравнение — значит найти все его корни, то есть те значения x, которые обращают уравнение в тождество.
Если уравнение достаточно сложно, то задача точного определения корней является в некоторых случаях нерешаемой. Поэтому ставится задача найти такое приближенное значение корня xПP, которое отличается от точного значения корня x* на величину, по модулю не превышающую указанной точности (малой положительной величины) ε, то есть

│x* – xпр │< ε

Величину ε также называют допустимой ошибкой, которую можно задать по своему усмотрению.

Этапы приближенного решения нелинейных уравнений

Приближенное решение уравнения состоит из двух этапов:

  • Отделение корней, то есть нахождение интервалов из области определения функции f(x), в каждом из которых содержится только один корень уравнения f(x)=0.
  • Уточнение корней до заданной точности.

Отделение корней

Отделение корней можно проводить графически и аналитически.
Для того чтобы графически отделить корни уравнения, необходимо построить график функции f(x). Абсциссы точек его пересечения с осью Ox являются действительными корнями уравнения.

Для примера рассмотрим задачу решения уравнения
Уравнение
где угол x задан в градусах. Указанное уравнение можно переписать в виде
f(x)=0
Для графического отсечения корней достаточно построить график функции
График функции
Из рисунка видно, что корень уравнения лежит в промежутке x∈(6;8).

Аналитическое отделение корней

Аналитическое отделение корней основано на следующих теоремах.
Теорема 1. Если непрерывная функция f(x) принимает на концах отрезка [a; b] значения разных знаков, т.е.
f(a)f(b)<0
то на этом отрезке содержится по крайней мере один корень уравнения.
Теорема 2. Если непрерывная на отрезке [a; b] функция f(x) принимает на концах отрезка значения разных знаков, а производная f'(x) сохраняет знак внутри указанного отрезка, то внутри отрезка существует единственный корень уравнения f(x) = 0.

Уточнение корней

Для уточнения корней может использоваться один из следующих методов:

Метод последовательных приближений (метод итераций)

Метод итерации — численный метод решения математических задач, используемый для приближённого решения алгебраических уравнений и систем. Суть метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным). Метод позволяет получить решение с заданной точностью в виде предела последовательности итераций. Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения решения.
Функциональное уравнение может быть записано в виде
x=f(x)
Функцию f(x) называют сжимающим отображением.

Последовательность чисел x0, x1 ,…, xn называется итерационной, если для любого номера n>0 элемент xn выражается через элемент xn-1 по рекуррентной формуле
xn=f(xn-1)
а в качестве x0 взято любое число из области задания функции f(x).

Реализация на C++ для рассмотренного выше примера
Уравнение
Уравнение может быть записано в форме
x=1/sinx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define _USE_MATH_DEFINES
#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++
Для заданного уравнения
метод Ньютона
производная будет иметь вид f'(x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define _USE_MATH_DEFINES
#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(a)f(b)
то последующие приближения находят по формуле
Метод хорд
Методом хорд называют также метод, при котором один из концов отрезка закреплен, т.е. вычисление приближения корня уравнения f(x) = 0 производят по формулам:
Метод секущих
Геометрическая интерпретация метода хорд:
Метод хорд
Реализация на C++
В отличие от двух рассмотренных выше методов, метод хорд предполагает наличие двух начальных приближений, представляющих собой концы отрезка, внутри которого располагается искомый корень.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define _USE_MATH_DEFINES
#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++

1
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
#define _USE_MATH_DEFINES
#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

  • Пользователь
    Здравствуйте, скажите пожалуйста, естьу у вас решения метода Зенделя? Очень нужно)

  • А можете помочь написать код для метода итераций. Система линейного уравнения с точностью до 0.001, предварительно оценив количество необходимых для этого шагов. x=0.05x-0.06x-0.12x+0.14x-2.17 x=0.04x-0.12x+0.08x+0.11x+1.4 x=0.34x+0.08x-0.06x+0.14x-2.1 x=0.11x+0.12x-0.03x-0.8 Очень нужно, пожалуйста.

  • Здравствуйте, спасибо за отличную статью, очень помогла разобраться в теме. Можете объяснить, почему в методе Ньютона в условии продолжения цикла происходит сравнение допустимой ошибки eps со значением функции по модулю fabs(f), а не с разностью | Xn+1 - Xn | ?

    • Елена Вставская
      Наша задача - найти такое значение x, при котором функция будет принимать нулевое значение.

  • Блог программиста
    В теореме 1 функции мало быть непрерывной, ей нужно быть монотонной, иначе теорема не сработает. Чтобы аналитически выполнять "отделение корней" - ИМХО надо вычислить вторую производную, т.к. она равна нулю в точках перегиба, т.е. точках где монотонность функции изменяется. Ну а иначе - не понятно каким образом мне подбирать границы интервала. Я думаю, что вычисление функции, для которой ищете корни надо было вынести в отдельную функцию. Очень странное ограничение у вас на количество итераций, зачем оно?

    • В теореме 1 сказано о наличии корня на указанном интервале, а не о его единственности. Чтобы говорить о единственности корня необходимо убедиться в монотонности функции на рассматриваемом интервале. Для этого необходимо определить экстремумы функции (взять первую производную функции и приравнять ее к нулю). Экстремумы ограничивают интервалы монотонности функции. Да, можно вынести вычисление в отдельную функцию (как сделано в примере по дихотомии). Ограничение на количество итераций играет роль "предохранительного клапана" и предотвращает "зависание" алгоритма.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *