|
|
| Строка 1: |
Строка 1: |
| - | == Введение ==
| |
| | | | |
| - | '''Метод дихотомии''' - достаточно широко используемый метод поиска, известный также как '''метод бисекции''' или '''метод половинного деления'''.
| |
| - | #Во-первых, это один из простых способов поиска корней функции одного аргумента.
| |
| - | #Во-вторых, метод дихотомии применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на минимум, максимум или конкретное число).
| |
| - |
| |
| - | == Метод дихотомии как метод поиска корней функции ==
| |
| - | === Изложение метода ===
| |
| - | Перед применением метода дихотомии для поиска корней функции необходимо отделить корни одним из известных способов, например, графическим методом. Отделение корней необходимо в случае, если неизвестно на каком отрезке нужно искать корень.
| |
| - |
| |
| - | Будем считать, что корень <tex>t</tex> функции <tex>f(x)=0</tex> отделён на отрезке <tex>[a,b]</tex>. Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления (дихотомии). Другими словами, требуется найти приближённое значение корня с заданной точностью <tex>\eps</tex>.
| |
| - |
| |
| - | Пусть функция <tex>f</tex> непрерывна на отрезке <tex>[a,b]</tex>,
| |
| - | ::<tex>f(a)\cdot f(b)<0, \; \eps=0,01</tex> и <tex>t\in[a,b]</tex> - единственный корень уравнения <tex>f(x)=0, \; a\le t\le b</tex>.
| |
| - |
| |
| - | (Мы не рассматриваем случай, когда корней на отрезке <tex>[a,b]</tex> несколько, то есть более одного. В качестве <tex>\eps</tex> можно взять и другое достаточно малое положительное число, например, <tex>0,001</tex>.)
| |
| - |
| |
| - | Поделим отрезок <tex>[a,b]</tex> пополам. Получим точку <tex>c= \frac {a+b}{2}, \; a<c<b</tex> и два отрезка <tex>[a,c], \; [c,b]</tex>.
| |
| - | *Если <tex>f(c)=0</tex>, то корень <tex>t</tex> найден (<tex>t=c</tex>).
| |
| - | *Если нет, то из двух полученных отрезков <tex>[a,c]</tex> и <tex>[c,b]</tex> надо выбрать один <tex>[a_1;b_1]</tex> такой, что <tex>f(a_1)\cdot f(b_1)<0</tex>, то есть
| |
| - | **<tex>[a_1;b_1] = [a,c]</tex>, если <tex>f(a)\cdot f(c)<0</tex> или
| |
| - | **<tex>[a_1;b_1] = [c,b]</tex>, если <tex>f(c)\cdot f(b)<0</tex>.
| |
| - | :Новый отрезок <tex>[a_1;b_1]</tex> делим пополам. Получаем середину этого отрезка <tex>c_1=\frac {a_1+b_1}{2}</tex> и так далее.
| |
| - |
| |
| - | Для того, чтобы найти приближённое значение корня с точностью до <tex> \eps >0</tex>, необходимо остановить процесс половинного деления на таком шаге <tex>n</tex>, на котором <tex>|b_n-c_n|<\eps</tex> и вычислить <tex>x=\frac {a_n+b_n}{2}</tex>. Тогда можно взять <tex>t\approx x</tex>.
| |
| - |
| |
| - | === Реализация метода на С++ и числовой пример ===
| |
| - | Решим уравнение <tex>4-e^x-2x^2=0</tex> методом дихотомии. Графическим методом находим отрезок <tex>[0; \,1]</tex>, которому принадлежит искомый корень. Так как <tex>f(0)\cdot f(1)<0</tex>, то принимаем <tex>a=0, \; b=1</tex>.
| |
| - |
| |
| - | Ниже приведен пример программы на [[C++|Си++]], которая решает поставленную задачу.
| |
| - |
| |
| - | '''Программа 1. Корень уравнения'''
| |
| - |
| |
| - | <source lang="cpp">#include <iostream>
| |
| - | #include <cmath>
| |
| - | using namespace std;
| |
| - | const double epsilon = 1e-2;
| |
| - |
| |
| - | double f(double x)
| |
| - | {
| |
| - | return 4- exp(x) - 2*x^2;
| |
| - | }
| |
| - |
| |
| - | int main()
| |
| - | {
| |
| - | double a, b, c;
| |
| - | a = 0;
| |
| - | b = 2;
| |
| - | while (b - a > epsilon){
| |
| - | c = (a + b) / 2;
| |
| - | if(f(b) * f(c) < 0)
| |
| - | a = c;
| |
| - | else
| |
| - | b = c;
| |
| - | }
| |
| - | cout << (a + b) / 2 << endl;
| |
| - | return 0;
| |
| - | }</source>
| |
| - |
| |
| - | Искомый корень <tex>x \approx 0.88281</tex>. Вычисления проводились с точностью <tex>0.01</tex>.
| |
| - |
| |
| - | Промежуточные вычисления представлены в таблице ниже.
| |
| - | <center>
| |
| - | {| class="standard"
| |
| - | !n
| |
| - | !a<sub>n</sub>
| |
| - | !b<sub>n</sub>
| |
| - | !c<sub>n</sub>
| |
| - | !|b<sub>n</sub>-c<sub>n</sub>
| |
| - | |-
| |
| - | !1
| |
| - | |0
| |
| - | |1
| |
| - | |0.5
| |
| - | |0.5
| |
| - | |-
| |
| - | !2
| |
| - | |0.5
| |
| - | |1
| |
| - | |0.75
| |
| - | |0.25
| |
| - | |-
| |
| - | !3
| |
| - | |0.75
| |
| - | |1
| |
| - | |0.875
| |
| - | |0.125
| |
| - | |-
| |
| - | !4
| |
| - | |0.875
| |
| - | |1
| |
| - | |0.9375
| |
| - | |0.0625
| |
| - | |-
| |
| - | !5
| |
| - | |0.875
| |
| - | |0.9375
| |
| - | |0.90625
| |
| - | |0.03125
| |
| - | |-
| |
| - | !6
| |
| - | |0.875
| |
| - | |0.90625
| |
| - | |0.890625
| |
| - | |0.015625
| |
| - | |-
| |
| - | !7
| |
| - | |0.875
| |
| - | |0.890625
| |
| - | |0.8828125
| |
| - | |0.0078125
| |
| - | |}
| |
| - | </center>
| |
| - |
| |
| - | == Метод дихотомии как метод оптимизации ==
| |
| - | [[Изображение:09 01.gif|frame|Рис. 1. Поиск экстремума функции <tex>F(x)</tex> методом дихотомии]]
| |
| - | [[Изображение:09 02.gif|frame|Рис. 2. Схема алгоритма метода дихотомии]]
| |
| - |
| |
| - | '''''Однопараметрическая оптимизация''''' (поиск экстремумов функций одной переменной) является самостоятельной и часто встречаемой задачей. Кроме того, к ней сводится гораздо более сложная задача - поиск экстремума функции многих переменных.
| |
| - |
| |
| - | Рассмотрим метод дихотомии как простейший однопараметрический метод безусловной оптимизации. Данный метод является ''методом прямого поиска''. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.
| |
| - |
| |
| - | Дана функция <tex>F(x)</tex>. Необходимо найти <tex>\overline{x}</tex>, доставляющий минимум (или максимум) функции <tex>F(x)</tex> на интервале <tex>[a,b]</tex> с заданной точностью <tex>\varepsilon</tex>, т.е. найти
| |
| - | ::<tex>\overline{x} = \arg \min F(x), \; \overline{x} \in [a,b]</tex>.
| |
| - |
| |
| - | Запишем словесный алгоритм метода.
| |
| - |
| |
| - | #На каждом шаге процесса поиска делим отрезок <tex>[a,b]</tex> пополам, <tex>x=\frac {a+b}{2}</tex> - координата середины отрезка <tex>[a,b]</tex>.
| |
| - | #Вычисляем значение функции <tex>F(x)</tex> в окрестности <tex>\pm \varepsilon</tex> вычисленной точки <tex>x</tex>, т.е. <br
| |
| - | \> <tex>F_1=F(x-\varepsilon),\; F_2=F(x+\varepsilon)</tex>.
| |
| - | #Сравниваем <tex>F_1</tex> и <tex>F_2</tex> и отбрасываем одну из половинок отрезка <tex>[a,b]</tex> (рис. 1).
| |
| - | #*При поиске минимума:
| |
| - | #**Если <tex>F_1<F_2</tex>, то отбрасываем отрезок <tex>[x,b]</tex>, тогда <tex>b=x</tex>. (рис. 1.а)
| |
| - | #**Иначе отбрасываем отрезок <tex>[a,x]</tex>, тогда <tex>a=x</tex>. (рис. 1.б)
| |
| - | #*При поиске максимума:
| |
| - | #**Если <tex>F_1<F_2</tex>, то отбрасываем отрезок <tex>[a,x]</tex>, тогда <tex>a=x</tex>.
| |
| - | #**Иначе отбрасываем отрезок <tex>[x,b]</tex>, тогда <tex>b=x</tex>.
| |
| - | #Деление отрезка <tex>[a,b]</tex> продолжается, пока его длина не станет меньше заданной точности <tex>\varepsilon</tex>, т.е. <tex>|b-a| \le \varepsilon</tex>.
| |
| - |
| |
| - |
| |
| - | Схема алгоритма метода дихотомии представлена на рис 2.
| |
| - |
| |
| - | На рис 2:
| |
| - | ::<tex>c</tex>- константа,
| |
| - | ::<tex>c =\begin{cases} \quad 1 , \quad (min \; F(x)), \\-1, \quad (max \; F(x)). \end{cases}</tex>
| |
| - |
| |
| - | При выводе <tex>x</tex> – координата точки, в которой функция <tex>F(x)</tex> имеет минимум (или максимум), <tex>F_M</tex> – значение функции <tex>F(x)</tex> в этой точке.
| |
| - |
| |
| - | == Список литературы ==
| |
| - | * ''А.А.Самарский, А.В.Гулин.'' Численные методы. Москва «Наука», 1989.
| |
| - | * http://www.mgopu.ru/PVU/2.1/nummethods/Chapter1.htm
| |
| - | * http://www.intuit.ru/department/calculate/calcmathbase/1/4.html
| |
| - |
| |
| - | == См. также ==
| |
| - | * [[Практикум ММП ВМК, 4й курс, осень 2008]]
| |
| - |
| |
| - | [[Категория:Учебные задачи]]
| |
