Метод дихотомии: различия между версиями
Содержимое удалено Содержимое добавлено
Bosik GN (обсуждение | вклад) →Задача посложнее: вычислять значение f(b)*f(c) необязательно, достаточно проверить знак f(c) |
|||
Строка 90:
В предыдущий раз мы отгадывали задуманное число. Число было целым, и его можно было отгадать либо не отгадать — точнее, всегда отгадать, вопрос стоял лишь о числе попыток. Решим задачу посложнее, а именно, научимся находить приближённые (численные) значения корней уравнений, используя метод деления пополам.
Рассмотрим уравнение, корень которого представляет собой [[w:Трансцендентное число|трансцендентное число]]<ref>Напомним, что трансцендентным называется число, которое не может являться корнем никакого многочлена с целыми коэффициентами.</ref>
:<math>e^x (следствие — в результате деления рационального отрезка пополам, как и в любом другом рациональном отношении, мы никогда не «попадем» случайно в трансцендентный корень Начнём пошагово уточнять отрезок, на котором лежит корень, уменьшая его размер (область поиска) в два раза. Разделим данный нам отрезок пополам. В данном случае мы не связаны целыми числами, поэтому любой отрезок можно разделить ровно пополам<ref>Не следует, однако, задавать слишком малые значения <math>\varepsilon</math> — машинная точность не бесконечна, и всегда есть риск «зацикливания» программы. Вычисление корня с погрешностью <math>\varepsilon = 10^{-10}</math> часто бывает достаточно.</ref>.
Строка 96 ⟶ 98 :
Существует теорема, которая гласит, что если непрерывная функция <math>f(x)</math> на двух концах отрезка <math>[a;\, b]</math> имеет разные знаки, то она имеет корень (нулевое значение) на этом отрезке.
Обозначим концы исследуемого отрезка соответственно <math>a</math> и <math>b</math>. Для нашей функции будет верно:
:<math>f(a) < 0</math> :<math>f(b) > 0</math> На первом шаге вычислим <math>c = \frac{b - a}{2}</math>. Посмотрим на знак <math>f(c)</math>. Если <math>f(c) = 0</math> — редкая удача, мы нашли точное значение корня. В данном случае такая радужная перспектива нам не улыбается, потому как корень выражается трансцендентным числом. Если мы не попали в корень, то, согласно принципу дихотомии, нам необходимо подготовить новый отрезок для поиска, в два раза короче, чем на данной итерации. Это просто: <math>f(c)</math>
На каждой итерации мы твёрдо знаем, что на отрезке <math>[a;\, b]</math> есть искомый корень. Следовательно, число <math>\frac{a + b}{2}</math> даёт значение корня с погрешностью, не превосходящей <math>\frac{b - a}{2}</math>. Таким образом, если наша цель — найти корень с погрешностью, не превосходящей <math>\varepsilon</math>, условие <math>\frac{b - a}{2} < \varepsilon</math> является условием завершения итерационного процесса.
'''Пример программы на языке [[w:C++|Си++]]'''
<source lang="cpp">
Строка 122 ⟶ 127 :
while (b - a > epsilon){
c = (a + b) / 2;
if(
a = c;▼
else▼
b = c;
▲ else
▲ a = c;
}
cout << (a + b) / 2 << endl;
| |||