|
|
| (5 промежуточных версий не показаны.) |
| Строка 1: |
Строка 1: |
| - | == Введение ==
| + | #REDIRECT [[Методы дихотомии]] |
| - | | + | |
| - | '''Метод дихотомии''' - достаточно широко используемый метод поиска, известный также как '''метод бисекции''' или '''метод половинного деления'''.
| + | |
| - | #Во-первых, это один из простых способов поиска корней функции одного аргумента. | + | |
| - | #Во-вторых, метод дихотомии применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на минимум, максимум или конкретное число).
| + | |
| - | | + | |
| - | == Метод дихотомии как метод поиска корней функции ==
| + | |
| - | === Изложение метода ===
| + | |
| - | Перед применением метода дихотомии для поиска корней функции необходимо отделить корни одним из известных способов, например, графическим методом. Отделение корней необходимо в случае, если неизвестно на каком отрезке нужно искать корень. Будем считать, что корень <tex>t</tex> функции <tex>f(x)=0</tex> отделён на отрезке <tex>[a,b]</tex>. Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления (дихотомии). Другими словами, требуется найти приближённое значение корня с заданной точностью <tex>\eps</tex>.
| + | |
| - | | + | |
| - | Пусть функция <tex>f</tex> непрерывна на отрезке <tex>[a,b], \; 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>4-e^x-2x^2=0</tex> на отрезке <tex>[0;\, 2]</tex> с точностью <tex>0.01</tex> методом дихотомии. Искомый корень <tex>x \approx 0.88281</tex>.
| + | |
| - | | + | |
| - | Промежуточные вычисления представлены в таблице ниже.
| + | |
| - | | + | |
| - | n a_n b_n c_n |b_n-c_n|
| + | |
| - | 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
| + | |
| - | | + | |
| - | == Метод дихотомии как метод оптимизации ==
| + | |
| - | '''''Однопараметрическая оптимизация''''' (поиск экстремумов функций одной переменной) является самостоятельной и часто встречаемой задачей. Кроме того, к ней сводится гораздо более сложная задача - поиск экстремума функции многих переменных.
| + | |
| - | | + | |
| - | Рассмотрим метод дихотомии как простейший однопараметрический метод безусловной оптимизации. Данный метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.
| + | |
| - | | + | |
| - | Дана функция <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>, т.е. <tex>F_1=F(x-\varepsilon),\; F_2=F(x+\varepsilon)</tex>.
| + | |
| - | #Сравниваем <tex>F_1</tex> и <tex>F_2</tex> и отбрасываем одну из половинок отрезка <tex>[a,b]</tex> (рис. 9.1).
| + | |
| - | #*При поиске минимума:\\Если <tex>F_1<F_2</tex>, то отбрасываем отрезок <tex>[x,b]</tex>, тогда <tex>b=x</tex>. (рис. 9.1.а)\\Иначе отбрасываем отрезок <tex>[a,x]</tex>, тогда <tex>a=x</tex>. (рис. 9.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>.
| + | |
| - | | + | |
| - | | + | |
| - | | + | |
| - | Рис. 9.1. Поиск экстремума функции <tex>F(x)</tex> методом дихотомии
| + | |
| - | | + | |
| - | Схема алгоритма метода дихотомии представлена на рис 9.2.
| + | |
| - | | + | |
| - | На рис 9.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> в этой точке.
| + | |
| - | | + | |
| - | | + | |
| - | | + | |
| - | Рис. 9.2. Схема алгоритма метода дихотомии
| + | |
| - | | + | |
| - | | + | |
| - | Метод хорд
| + | |
| - | | + | |
| - | '''Метод хорд''' (способ пропорциональных частей) — численный метод уточнения корня трансцендентного уравнения.
| + | |
| - | Метод основан на замене функции <tex>f(x)</tex> на каждом шаге поиска хордой, пересечение которой с осью <tex>Х</tex> дает приближение корня.
| + | |
| - | | + | |
| - | При этом в процессе поиска семейство хорд может строиться:
| + | |
| - | | + | |
| - | а) при фиксированном левом конце хорд, т.е. <tex>z=a</tex>, тогда начальная точка <tex>x_0=b</tex> (рис. 4.10а);
| + | |
| - | | + | |
| - | б) при фиксированном правом конце хорд, т.е. <tex>z=b</tex>, тогда начальная точка <tex>x_0=a</tex> (рис. 4.10б);
| + | |
| - | | + | |
| - | | + | |
| - | | + | |
| - | Рис. 4.10.
| + | |
| - | | + | |
| - | В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:
| + | |
| - | | + | |
| - | для случая а):
| + | |
| - | | + | |
| - | <tex>x_{n+1}=x_n - \frac{f(x_n)}{f(x_n)-f(a)} (x_n - a);</tex> (4.11)
| + | |
| - | | + | |
| - | для случая б):
| + | |
| - | <tex>x_{n+1}=x_n - \frac{f(x_n)}{f(x_n)-f(b)} (x_n - b);</tex> (4.12)
| + | |
| - | | + | |
| - | Процесс поиска продолжается до тех пор, пока не выполнится условие
| + | |
| - | <tex>|x_{n+1}–x_n| \le \varepsilon </tex> или <tex>| h| \le \varepsilon </tex>. (4.13)
| + | |
| - | | + | |
| - | Метод обеспечивает быструю сходимость, если <tex>f(z)\cdot f''(z) > 0</tex>, т.е. хорды фиксируются в том конце интервала <tex>[a,b]</tex>, где знаки функции <tex>f(z)</tex> и ее кривизны <tex>f"(z)</tex> совпадают.
| + | |
| - | | + | |
| - | Схема алгоритма уточнения корня методом хорд представлена на рис. 4.11.
| + | |
| - | | + | |
| - | | + | |
| - | | + | |
| - | Схема алгоритма уточнения корня методом хорд
| + | |
| - | | + | |
| - | Рис. 4.11. Схема алгоритма уточнения корня методом хорд
| + | |
| - | | + | |
| - | | + | |
| - | | + | |
| - | Этот метод позволяет исключать в точности половину интервала на каждой итерации.
| + | |
| - | Приведем описание поисковой процедуры, ориентированной на нахождение точки минимума функции <tex>f(x)</tex> в интервале <tex>(a,b)</tex>.
| + | |
| - | | + | |
| - | 1. Шаг1. Положить <tex>x_m=(a+b)/2</tex> и <tex>L=b-a</tex>.
| + | |
| - | Вычислить значение <tex>f(x_m)</tex>.
| + | |
| - | 2. Шаг2. Положить <tex>x_1=a+L/4</tex> и <tex>x_2=b-L/4</tex>.
| + | |
| - | Можно заметить,что точки <tex>x_1,\; x_m,\; x_2</tex> делят интервал <tex>(a,b)</tex> на четыре равные части.
| + | |
| - | Вычислить значения <tex>f(x_1)</tex> и <tex>f(x_2)</tex>.
| + | |
| - | 3. Шаг3. Сравнить <tex>f(x_1)</tex> и <tex>f(x_2)</tex>.
| + | |
| - | * если <tex>f(x_1)\le f(x_m)</tex>, исключить интервал <tex>(x_m,b)<tex>, положив <tex>b=x_m</tex>.
| + | |
| - | Средней точкой нового интервала поиска становится точка <tex>x_1</tex>.
| + | |
| - | Следовательно, необходимо положить <tex>x_m=x_1</tex>. Перейти к шагу 5.
| + | |
| - | * если <tex>f(x_1)\me f(x_m)</tex>, то перейти к шагу 4.
| + | |
| - | 4. Шаг4. Сравнить <tex>f(x_2)</tex> и <tex>f(x_m)</tex>.
| + | |
| - | * если <tex>f(x_2)&le f(x_m)</tex>, исключить интервал <tex>(a,x_m)</tex>, положив <tex>a=x_m</tex>.
| + | |
| - | Т.к. средней точкой нового интервала становится точка <tex>x_2</tex>, положить <tex>x_m=x_2</tex>.
| + | |
| - | Перейти к шагу 5.
| + | |
| - | * если <tex>f(x_2)>=(x_m)</tex>, исключить интервалы <tex>(a,x_1)</tex> и <tex>(x_2,b)</tex>.
| + | |
| - | Положить <tex>a=x_1</tex> и <tex>b=x_2</tex>. (Заметим, что <tex>x_m</tex> продолжает оставаться средней точкой нового интервала)
| + | |
| - | Перейти к шагу 5.
| + | |
| - | 5. Шаг5. Вычислить <tex>L=b-a</tex>.
| + | |
| - | Если величина <tex>|L|</tex> мала, закончить поиск, в противном случае вернуться к шагу 2.
| + | |
| - | | + | |
| - | == Список литературы ==
| + | |
| - | * ''А.А.Самарский, А.В.Гулин.'' Численные методы. Москва «Наука», 1989.
| + | |
| - | * http://www.mgopu.ru/PVU/2.1/nummethods/Chapter1.htm
| + | |
| - | * http://www.intuit.ru/department/calculate/calcmathbase/1/4.html
| + | |
| - | | + | |
| - | == См. также ==
| + | |
| - | * [[Практикум ММП ВМК, 4й курс, осень 2008]]
| + | |
| - | | + | |
| - | [[Категория:Учебные задачи]]
| + | |
