ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ УРАВНЕНИЙ С ОДНОЙ НЕИЗВЕСТНОЙ И ИХ РЕАЛИЗАЦИЯ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ С++

Численные методы в широком понимании – совокупность дискретной модели, которая реализуется на компьютере и позволяет получить решение в виде конкретизированных числовых значений. Требования численного решения задач привели к тому, что появилось множество методов их решений.

Пусть имеется уравнение вида f(x)=0, где f(x) непрерывна на <a, b>, где <a, b> отрезок либо вся числовая ось.

Решить уравнение означает найти все его корни либо доказать, что их нет.

Процесс нахождения корней состоит из 2-х этапов:

- отделение корней (разбить всю область определения на отрезки, в каждом из которых содержится один корень);

- уточнение корней до заданной степени точности.

Отделение корней включает в себя два метода: графический и аналитический.

Рассмотрим первый, графический метод отделения корней.

Если уравнение задается в виде f(x)=0, то строится график функции y=f(x) и визуально выбираются отрезки, содержащие точки пересечения графика и оси абсцисс. Эти отрезки содержат по одному из корней уравнения.

Рассмотрим второй, аналитический метод отделения корней.

Теорема. Если первая производная функции f сохраняет знак на отрезке [a, b] и на концах отрезка функция f имеет разные знаки, то на отрезке [a, b] функция f имеет, и притом единственный корень.

Процедура отделения корней состоит из трёх этапов:

Первое – найти производную функции f, определить стационарные точки из уравнения.

Второе – составить таблицу знаков .

Третье – найти интервалы [a, b], где  и .

Второй этап процесса нахождения корней – уточнение корней до заданной степени точности.

Уточнить корень это значит довести его значение до заданной степени точности.

Пусть дано уравнение f(x)=0, на отрезке [a, b] отделен корень, функция f монотонна на отрезке [a, b], f(a)f(b) <0, задана точность . Уточнить корень с точностью .

Решение. Если , то в качестве корня . В случае, если , то применяются различные методы уточнения корней.

Перечислим методы уточнения корней:

- метод половинного деления;

- метод простой итерации;

- метод хорд;

- метод Ньютона (метод касательных).

Первым рассмотрим метод половинного деления.

Пусть корень уравнения f(x)=0 отделен на отрезке [a; b], . Возьмем точку  и рассмотрим значение функции  в точке x=с.

Если f(c) = 0, то x=с точный корень.

Если , то

Если , то

Процедура продолжается до тех пор, пока не станет выполнятся равенство . Корень  приближенно равен . Таким образом, получен результат с точностью до . На рисунках 1 и 2 представлен метод половинного деления.

Рисунок 1. Метод половинного деления

Рисунок 2. Метод половинного деления

Реализация метода на языке программирования С++ представлена на рисунке 3.

Рисунок 3. Реализация метода половинного деления на языке программирования С++

Вторым рассмотрим метод простой итерации.

Идея метода простой итерации состоит в том, чтобы уравнение                   привести к эквивалентному уравнению,  так, чтобы отображение             было сжимающим. Если это удаётся, то последовательность итераций  сходится. Такое преобразование можно делать разными способами. В частности, сохраняет корни уравнение вида  если  на исследуемом отрезке.

В качестве функции  берут некоторую постоянную , знак которой совпадает со знаком производной  в некоторой окрестности корня. Формула итераций оказывается предельно простой: . На рисунке 4 представлен метод простой итерации.

Рисунок 4. Метод простой итерации

Достаточное условие сходимости:

откуда получаем, что сходимость гарантируется, когда, во-первых, ,

а во-вторых, когда  при всех х на всём рассматриваемом отрезке, окружающем корень.

Это второе неравенство заведомо выполнено, если  где

Реализация метода на языке программирования С++ представлена на рисунке 5.

Рисунок 5. Реализация метода простой итерации на языке программирования С++

Третий метод– метод хорд.

Для реализации данного метода нужно построить исходную функцию y=F(x) и найти значения функции на концах отрезка F(a) и F(b). Затем провести хорду М₁M₂ c концами в точках М₁(a, F(a)) и M₂(b, F(b)). Абсцисса точки пересечения хорды М₁M₂ с осью OX это и есть приближенный корень x₁. Далее найти точку M₃(X₁, F(x₁)), построить следующую хорду и найти второй приближенный корень x₂. И так далее. В зависимости от поведения функции возможны два случая,  которые отображены на рисунках 6 и 7.

Рисунок 6. Метод хорд, случай 1

 А – неподвижная точка,

Рисунок 7. Метод хорд, случай 2

 B – неподвижная точка,

Реализация метода на языке программирования С++ представлена на рисунке 8.

Рисунок 8. Реализация метода Хорд на языке программирования С++

Заключительным методом рассмотрим метод Ньютона.

Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации.

Чтобы численно решить с помощью метода простой итерации уравнение , приведем его к следующей форме: , в которой  является сжимающим отображением.

Для получения наилучшей сходимости данного метода в точке очередного приближения  необходимо выполнение следующего условия . Решением данного уравнения является функция вида , тогда .

Предполагая, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:

Тогда сжимающая функция  примет вид:

При выполнении некоторых условий функция  осуществляет сжимающее отображение в окрестности корня, тогда алгоритм поиска численного решения уравнения сводится к итерационной процедуре вычисления: . На рисунке 9 представлен метод Ньютона.

Рисунок 9. Метод Ньютона

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

В отличии от метода Хорд, в данном методе основная идея состоит в том, что на каждом шаге вместо хорды проводится касательная к исследуемой функции  и ищется точка пересечения касательной с осью OX. Так же будет достаточно найти лишь некоторое начальное приближение корня , определять отрезок [a, b], содержащий решение уравнения, не обязательно.

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

Реализация метода на языке программирования С++ представлена на рисунке 10.

Рисунок 10. Реализация метода Ньютона на языке программирования С++

Список литературы:

1. Демидович Б.П., Марон И.А. Основы вычислительной математики. – М.: Наука, 1970.- 664 с.
2. Страуструп Б. Программирование: принципы и практика в C++: Пер. с англ. – М: Вильямс, 2016. – 1328 с.
3. Бахвалов Н. С., Н. П. Жидков, Г. М. Кобельков. Численные методы — 6-е изд. — М.: БИНОМ. Лаборатория знаний, 2008. — 636 с.