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

 

Снова предположим, что корень отделён на отрезке $ [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$ будет выполнено с нужной точностью.

      

Основные обозначения и определения Функции и их графики

 

Пример 1.4 При сдаче пальто в гардероб каждому сданному пальто $ p$ соответствует ровно один выданный номерок $ n$. Таким образом, между множеством $ P$ сданных пальто и множеством выданных номерков $ N'$ ($ N'$-- это подмножество множества $ N$ всех номерков в гардеробе) устанавливается биекция $ f: p\mapsto n$ ($ p\in P$, $ n\in N'$).

Определение 1.4 Если $ f:A\to B$-- биекция, то отображение, сопоставляющее каждому $ y\in B$ тот элемент $ x\in A$, который переходит в этот самый $ y$ при отображении $ f$, называется обратным отображением (или обратной функцией) к отображению $ f$ и обозначается $ f^{-1}$. Таким образом, $ f^{-1}:B\to A$, и $ f^{-1}(y)=x$ тогда и только тогда, когда $ f(x)=y$ ($ x\in A$, $ y\in B$).

Пример 1.5 В условиях примера 1.4 отображение $ f:P\to N'$-- биекция. При выдаче пальто из гардероба по каждому из выданных номерков $ n\in N'$ находят соответствующее номерку пальто $ p\in P$. Соответствие $ g:N'\to P$, $ n\mapsto p$ ($ n\in N'$, $ p\in P$)-- это обратная функция к функции $ f:P\to N'$, $ p\mapsto n$, то есть $ g=f^{-1}$.

Классификация операционных систем Виртуальная память Реализация многозадачности
Системы безопасности Операционная система Linux Введение в компьютерные сети Принципы построения вычислительных систем Базовые технологии локальной сетиСредства анализа Процедуры и функции Pascal Язык запросов SQL Программирование на СИ Брандмауэры Протоколы TCP/IP Файловые системы Драйверы устройств