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

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

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

f(x)= 0

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

x* xпр │< eps

Величину eps также называют допустимой ошибкой, которую можно задать по своему усмотрению.
Этапы приближенного решения нелинейных уравнений
Приближенное решение уравнения состоит из двух этапов:

  • Отделение корней, то есть нахождение интервалов из области определения функции 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).
Реализация для рассмотренного выше примера
УравнениеУравнение может быть записано в форме
x=1/sinx

#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, то последовательные приближения находят по формуле
метод Ньютона
Графическая интерпретация метода касательных имеет вид Метод касательных
Реализация
Для заданного уравнения метод Ньютона
производная будет иметь вид f'(x)

#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 производят по формулам:
Метод секущих
Геометрическая интерпретация метода хорд:
Метод хорд
Реализация В отличие от двух рассмотренных выше методов, метод хорд предполагает наличие двух начальных приближений, представляющих собой концы отрезка, внутри которого располагается искомый корень.

#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) принимает значения разных знаков, и проделывается аналогичная операция. Процесс продолжается до получения требуемой точности.

Геометрическая интерпретация метода дихотомии

Метод дихотомии

Реализация

#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;
}

Результат выполнения
Метод дихотомии

Для численного поиска решения также можно использовать генетические алгоритмы.
Назад

Комментариев к записи: 2

  • Блог программиста

    В теореме 1 функции мало быть непрерывной, ей нужно быть монотонной, иначе теорема не сработает.

    Чтобы аналитически выполнять «отделение корней» — ИМХО надо вычислить вторую производную, т.к. она равна нулю в точках перегиба, т.е. точках где монотонность функции изменяется. Ну а иначе — не понятно каким образом мне подбирать границы интервала.

    Я думаю, что вычисление функции, для которой ищете корни надо было вынести в отдельную функцию. Очень странное ограничение у вас на количество итераций, зачем оно?


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


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

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