Метод половинного деления Приближённое нахождение корней уравнений

 

Снова предположим, что корень отделён на отрезке $ [a;b]$ и знаки $ f(a)$ и $ f(b)$ различны (функция $ f(x)$ меняет знак при переходе через корень $ x^*$).

Положим $ a_0=a$ и $ b_0=b$ и вычислим значения функции в левом конце отрезка, $ f(a_0)$, и в его середине $ c_0=\dfrac{a_0+b_0}{2}$: $ f(c_0)$. Сравним знаки чисел $ f(a_0)$ и $ f(c_0)$. Если эти знаки различны, то корень $ x^*$ лежит в интервале $ (a_0;c_0)$; если же одинаковы, то тогда различны знаки $ f(c_0)$ и $ f(b_0)$, и корень лежит в интервале $ (c_0;b_0)$. (Возможен ещё случай $ f(c_0)=0$; тогда корень $ x^*=c_0$ уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке $ [a_0;c_0]$ либо $ [c_0;b_0]$, длина которого ровно в два раза меньше длины исходного отрезка $ [a_0;b_0]=[a;b]$. Обозначим этот отрезок половинной длины через $ [a_1;b_1]$ (то есть положим $ a_1=a_0;b_1=c_0$ в случае, когда $ f(a_0)$ и $ f(c_0)$ разных знаков, и $ a_1=c_0;b_1=b_0$ в случае, когда $ f(a_0)$ и $ f(c_0)$ одного знака).

Далее повторим процесс для отрезка $ [a_1;b_1]$: снова отыщем его середину $ c_1$, найдём значение функции $ f(c_1)$ и сравним знак этого числа со знаком $ f(a_1)$; если знаки разные, то корень отделён на $ [a_2;b_2]=[a_1;c_1]$, если одинаковые, то на $ [a_2;b_2]=[c_1;b_1]$ (или же оказывается, что $ f(c_1)=0$; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.

Рис.9.2.Последовательное деление отрезка пополам и приближение к корню $ x^*$

Поступая тем же образом и далее, получаем, что после $ k$ делений длина отрезка, на котором лежит корень, сокращается в $ 2^k$ раз и становится равной $ {\delta}_k=\dfrac{b-a}{2^k}$ (если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с $ c_i$ при некотором $ i$). Пусть $ {\varepsilon}$ -- заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство $ 2{\delta}_k\leqslant {\varepsilon}$. Очевидно, что если при этом положить

$\displaystyle \wt x=c_k=\dfrac{a_k+b_k}{2},$

то расстояние от корня $ x^*$, лежащего где-то в интервале $ (a_k;b_k)$, до середины этого интервала $ \wt x$ будет не больше $ {\varepsilon}$, то есть приближённое равенство $ x^*\approx\wt x$ будет выполнено с нужной точностью.

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

Выпуклость функции