‹-- Назад

Метод простого перебора

Пусть задана точность $ {\varepsilon}$, с которой мы хотим приближённо найти корень $ x^*$. Это означает, что мы должны предъявить в качестве результата вычислений известное число $ \wt x$, которое отличается от истинного значения корня $ x^*$ (которое нам неизвестно) не более чем на $ {\varepsilon}$: $ \vert\wt x-x^*\vert\leqslant {\varepsilon}$.

Пусть искомый корень $ x^*$ отделён на отрезке $ [a;b]$.

Самый простой (но и самый медленный) способ отыскать $ \wt x$ -- взять шаг $ h\leqslant 2{\varepsilon}$ и перебирать значения $ x$ с шагом $ h$ до тех пор, пока функция не сменит знак (по сравнению со знаком исходного числа $ f(a)$. Последовательно получаем: $ x_0=a; f(x_0)=f_0$; $ {x_1=x_0+h; f(x_1)=f_1}$; $ x_2=x_1+h;f(x_2)=f_2;\dots$. Вычисления продолжаются, пока $ f_0\cdot f_i>0$. Как только мы получим $ f_0\cdot f_i\leqslant 0$, нужно взять за приближённое значение корня середину между последними двумя точками: $ \wt x=\dfrac{x_i+x_{i-1}}{2}$. Поскольку по теореме о корне непрерывной функции $ x^*\in(x_{i-1};x_i]$, а длина этого сегмента $ x_i-x_{i-1}=h\leqslant 2{\varepsilon}$, то $ \vert\wt x-x^*\vert=\vert\frac{1}{2}(x_i-x_{i-1})-x^*\vert\leqslant {\varepsilon}$, то есть корень найден с нужной точностью.

Рис.9.1.Перебор значений функции, до тех пор пока она не сменит знак


Недостатком метода, конечно, является необходимость большого количества вычислений функции $ f(x)$. Считая шаг $ h={\varepsilon}$ малым и предполагая, что в среднем корень будет обнаруживаться где-то вблизи середины отрезка, мы можем предположить, что среднее количество вычислений функции, которое нам понадобится до нахождения $ \wt x$, составит

$\displaystyle N=\left\lceil\dfrac{b-a}{4{\varepsilon}}\right\rceil+1.$

В случае, если это вычисление занимает слишком много времени, метод становится совершенно непригодным. Однако, при увеличивающемся быстродействии вычислительной техники, когда нам становится не так уж важно, сколько именно времени займёт вычисление $ f(x)$ в очередной точке (всё равно немного!), привлекательность метода повышается: уж очень он прост и, кроме того, совершенно нетребователен к гладкости функции, достаточно лишь, чтобы она была непрерывной.

        Пример 9.4   Рассмотрим уравнение $ x^3+2x^2+3x+5=0$, корень которого был нами отделён на отрезке $ [-2;-1]$. Пусть корень $ x^*$ требуется определить с точностью $ {\varepsilon}=0.005$. Возьмём шаг $ h$ равным $ 2{\varepsilon}$, то есть $ h=0.01$. Тогда, вычисляя последовательно значения функции в точках $ -1,-0.99,-0.98,\dots$, получаем:

\begin{multline*}
f(-2)=-1;f(-1.99)=-0.030399;f(-1.98)=-0.861592;
\dots;\\
f(-1.85)=-0.036625;f(-1.84)=0.021696.
\end{multline*}

При переходе от $ x=-1.85$ к $ x=-1.84$ функция сменила знак. Следовательно, корень приближённо равен $ \wt x=-1.845$ с точностью $ {\varepsilon}=0.005$. При этом нам понадобилось вычислить значение функции $ f(x)$ 17 раз. Можно сказать, повезло: ведь оценка количества вычислений даёт $ N=51$.