Метод половинного деления (метод дихотомии)

⇐ ПредыдущаяСтр 45 из 47Следующая ⇒

Метод половинного деления применяется не только при поиске минимума функции одной переменной, но и при решении уравнения вида f(x)=0. В послекднем случае строеится последовательность вложенных отрезков, содержащих корень. При этом на каждом шаге очередной отрезок делится пополам и в качестве следующего отрезка берется та половина, на которой значения функции в концах имеют разные знаки. Процесс продолжают до тех пор, пока длина очередного отрезка не станет меньше, чем величина 2ε. Тогда его середина и будет приближенным значением корня с точностью ε. Однако при поиске минимсмума суть метода половиного деления несколько иная. В этом случае метод половинного длеления иногда называют методом дихотомии. Данный метод применим, вообще говоря, только для унимодальных функций, имеющих единственный строгий минимум на рассматриваемом отрезке. Если применить этот метод для неунимодальной функции, можно получить, вообще говоря, один из локальных минимумов. Для удобства введем обозначение отрезка [a,b] через [a⁽⁰⁾,b⁽⁰⁾]. Поиск минимума начинают с выбора на отрезке [a⁽⁰⁾,b⁽⁰⁾] двух симметрично расположенных точек: α=[a⁽⁰⁾+b⁽⁰⁾]/2−δ и β=[a⁽⁰⁾+b⁽⁰⁾]/2+δ. Здесь δ − параметр метода, 0<δ<(b−a)/2. Далее вычисляют значения заданной функции f(x) в этих точках f(α⁽⁰⁾) и f(β⁽⁰⁾)и сравнивают их по величине. Такое сопоставление позволяет сократить отрезок локализации:


Если f(α⁽⁰⁾)≤f(β⁽⁰⁾), то x*∈[a,β]	Если f(α⁽⁰⁾)≥f(β⁽⁰⁾), то x*∈[α,b]

В результате удается сократить отрезок локализации следующим образом
Если f(α⁽⁰⁾)≤f(β⁰), то x*∈[a⁽¹⁾,b⁽¹⁾]=[a⁽⁰⁾,β⁽⁰⁾]
Если f(α⁽⁰⁾)≥f(β⁽⁰⁾), то x*∈[a⁽¹⁾,b⁽¹⁾]=[α⁽⁰⁾,b⁽⁰⁾]
Если описанную процедуру принять за одну итерацию метода и продолжить аналогичные операции для образования последовательности сокращающихся отрезков локализации, то получим итерационный метод. Опишем его (k+1) итерацию в предположении, то отрезок [a⁽¹⁾,b⁽¹⁾] уже найден.

Алгоритм метода половинного деления

Вычисляют α^(k)=[a^(k)+b^(k)]/2−δ и β^(k)=[a^(k)+b^(k)]/2+δ
Находят f(α^(k)) и f(β^(k))
Определяют новый отрезок локализации по следующему правилу:
Если f(α^(k))≤f(β^k), то [a^(k+1),b^(k+1)]=[a^(k),β^(k)] и x^(k+1)=α^(k)
Если f(α^(k))≥f(β^(k)), то [a^(k+1),b^(k+1)]=[α^(k),b^(k)] и x^(k+1)=β^(k)

Определение нового отрезка локализации решения в методе половинного деления может быть проиллюстрировано следующим образом:

Как видно из рисунка, длина нового отрезка |b^(k+1)−a^(k+1)|=|b^(k)−a^(k)|/2+δ. Отсюда следует, что при δ<<|b^(k)−a^(k)| длина вновь полученного отрезка почти вдвое меньше длины предыдущего отрезка. Отсюда - название метода.
С помощью метода математической индукции легко показать, что
|b^(k)−a^(k)|=(b−a−2δ)/2^k+2δ.
Отсюда следует, что при k→∞
|b^(k)−a^(k)|→2δ
Поэтому обеспечить заданную точность вычислений ε можно только если выбрать параметр метода δ<ε/2. Тогда критерием окончания вычислительного процесса будет
|b^(k)−a^(k)|<ε
В то же время, следует иметь в виду, что величину параметра δ нельзя задавать слишком малой, поскольку значения функции вычисляются с определенной вычислительной погрешностью.

Метод золотого сечения

Золотым сечением отрезка называется такое разбиение отрезка на две неравные части, при котором отношение длины сего отрезка к длине его большей части равно отношению длины его большей части к длине меньшей части отрезка. Термин "золотое сечение" ввел Леонардо да Винчи. Принципы золотого сечения широко использовались при композиционном построении многих произведений мирового искусства (в особенности, архитектурных сооружений античности и эпохи Возрождения). Золотое сечение отрезка [a,b] осуществляется каждой из двух симметрично расположенных относительно отрезка точек При этом нетрудно убедиться в том, что Замечательно то, что точка α осуществляет золотое сечение не только отрезка [a,b], но и отрезка [a,β]. Точно также точка β осуществляет золотое сечение не только отрезка [a,b], но и отрезка [α,b]. Очередная (k+1)-я итерация метода золотого сечения проводится аналогично (k+1)-й итерации метода половинного деления. Отличие заключается в выборе точек α^k, β^k, которые вычисляются по формулам: Алгоритм метода золотого сечения

Вычисляют α^k, β^k
Находят f(α^k) и f(β^k)
Определяют новый отрезок локализации по следующему правилу: Если f(α^k)≤f(β^k), то [a^(k+1),b^(k+1)]=[a^(k),β^(k)] и x^(k+1)=α^(k) Если f(α^(k))≥f(β^(k)), то [a^(k+1),b^(k+1)]=[α^(k),b^(k)] и x^(k+1)=β^(k)

Метод бисекции

Пусть f(x) - унимодальная непрерывно дифференцируемая на отрезке [a,b]=[a⁽⁰⁾,b⁽⁰⁾] функция и на отрезке [a,b] точка x* является единственной стационарной точкой. Тогда для нахождения этой точки можно воспользоваться необходимым условием f'(x*)=0. Пусть отрезок локализации [a^(k),b^(k)] известен и найдено значение x^(k)=(a^(k)+b^(k))/2. Алгоритм метода бисекции

Вычисляют значение f'(x^(k))
Если f'(x^(k))<0, то [a^(k+1),b^(k+1)]=[x^(k),b^(k)], в противном случае [a^(k+1),b^(k+1)]=[a^(k),x^(k)],
Вычисляют x^(k)=(a^(k+1)+b^(k+1))/2

Сходимость метода бисекции: |x^(k)-x*|≤(b−a)/2^k+1

Метод Ньютона