4. Решение уравнений. Метод перебора. Метод деления отрезка пополам

Метод перебора является простейшим прямым методом. Опишем его суть на примере поиска минимума на заданном отрезке значений функции \(F(x)\). Отрезок [\(a\); \(b\)], на котором предполагается искомое значение, разбивается на \(n\) равных отрезков точками деления:

 

 

Вычисляем значения $F(x_i)$ и путём сравнения находим точку $x_m$, такую, что $F(x_m)=\mathit{min}(F(x_i))$ для всех \(i = 0...n\).

Погрешность в этом случае не превосходит величины $\mathrm{ϵ}=\frac{b-a}{n}$.

Метод перебора применяется редко для решения реальных задач, так как требует большого объёма вычислений.

 

Метод деления отрезка пополам — итерационный метод. Он опирается на свойство непрерывных функций, заключающееся в том, что если функция на концах выбранного отрезка принимает разные по знаку значения, то внутри этого отрезка находится хотя бы один корень.
Нахождение таких отрезков — задача отделения корней.
Отделить корень — значит указать такой отрезок [$a_1;b_1$], на котором содержится ровно один корень уравнения \(F(x) = 0\).

Найти отрезок [$a_1;b_1$] можно, построив, например, график функции или составив таблицу значений функции от разных значений аргументов. Выполнить это можно вручную, в электронных таблицах или в специализированных пакетах Mathcad, MathLAB.

 

Пример \(5\)

Отдели корень уравнения $y=x^3+2\cdot x+2$ на участке [\(-2\); \(2\)] при шаге \(h = 1\).

 

Составим таблицу значений функции на отрезке [\(-2\); \(2\)] при шаге \(h = 1\).

 

 

Из анализа таблицы видно, что на концах отрезка [\(-1\); \(0\)] функция принимает разные по знаку значения. Это и есть искомый отрезок.

 

Пусть из предварительного анализа известно, что корень уравнения \(F(x) = 0\) находится на отрезке [$x_{\mathit{left}};x_{\mathit{right}}$]. Разделим этот отрезок точкой $x_{\mathit{middle}}$ пополам и вычислим значения $F(x_{\mathit{left}} )$ и $F(x_{\mathit{middle}})$, а также их произведение. Рассмотрим варианты, которые могут получиться.

 

 

Далее действия повторяются до тех пор, пока не выполнится неравенство $x_{\mathit{right}}-x_{\mathit{left}}<2\mathrm{ϵ}$, где $\mathrm{ϵ}$ — принятая погрешность.

 

Пример \(6\)

 

Найди решение уравнения $y=x^3-8\cdot x+1$ на участке [\(-5\); \(0\)].

 

Составим программу на языке Pascal, реализуя метод деления отрезка пополам. Проверим полученный результат в электронных таблицах, используя встроенный инструмент «Сервис-Решатель» (LibreOffice Calc).

 

 

Проверка в электронных таблицах:

 

 

Пример \(7\)

Найди решение уравнения $y=x^3-8\cdot x+1$ на участке [\(-5\); \(0\)].

  

 

Составим программу на языке Pascal, реализуя метод перебора. Проверим полученный результат в электронных таблицах, используя встроенный инструмент «Поиск решения».

 

  

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

 

При выборе для решения приближённых методов следует учитывать их недостатки:
• не дают точных решений;
• решение — всегда число, а зависимость получить нельзя;
• объём вычислений может быть очень большим;
• не всегда удаётся получить оценку погрешности.

 

И применять, учитывая достоинства:
• при невозможности или затруднительном получении аналитического решения дают быстрый результат;
• некоторые из численных методов в применении к определённым задачам дают более точное решение, чем аналитические.