Метод половинного деления в excel
Данный метод описывает алгоритм нахождение корней (нулей) функции. Чтобы найти минимум целевой функции методом дихотомии используйте этот калькулятор.
Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b)1. Если |f(c)| < ε, то c – корень. Здесь ε - заданная точность.
2. Если f(c)f(a)3. Если f(c)f(b)Продолжая процесс половинного деления в выбранных подынтервалов, можно дойти до сколь угодно малого отрезка, содержащего корень ξ.
Так как за каждую итерацию интервал, где расположен корень уменьшается в два раза, то через n итераций интервал будет равен:
при этом an≤ξ≤bn, , .
В качестве корня ξ. возьмем =½(bn+an). Тогда погрешность определения корня будет равна (bn – an)/2. Если выполняется условие (bn–an)/2n+an).
см. более подробный алгоритм метода бисекции.
Теорема 2. Итерационный процесс половинного деления сходится к искомому корню ξ с любой наперед заданной точностью ε.
Доказательство: Рассмотрим последовательность чисел ξi являющихся приближением корня на i -ом шаге.
ξi=½(bi+ai), i=0,1.
где a0=a; b0=b; ai;bi - границы подынтервалов, в которых f(ai)f(bi)|ξ1- ξ0|, |ξ2- ξ1|, …, |ξn- ξn-1|.
Имеем |ξ1-ξ0|=½(b1+a1-b0-a0). Так как всегда имеем либо b1=b0, a1=½(b0+a0), либо a1=a0, b1=½(a0+b0), поэтому , если, b1=b0
либо , если a1=a0.
Повторяя аналогичные рассуждения и учитывая, что всегда выполняется соотношение либо bi=bi-1, ai=½(bi-1+ai-1), либо bi=½(bi-1+ai-1), ai=ai-1. Получим
;
;
, где a0=a, b0=b.
Отсюда видно, что какое бы малое число ε>0 мы ни задали, всегда можно найти такое n , что ч.т.д.
Графически метод дихотомии выглядит следующим образом
Сходимость метода дихотомии линейная с коэффициентом α=0,5. Покажем это.
Если в качестве xn брать an, то из формулы (6) мы можем записать , . Отсюда следует .
Отметим, что за 10 итераций (n=10) интервал уменьшается в 2 10 = 1024 ≈ 10 3 раз. За 20 итераций (n=2) уменьшается в 2 20 ≈ 10 6 раз.
Находим производную функции: y ' = 10x-4. Найдем нули функции методом дихотомии: y'=0.
Поскольку F(0)*F(10) Пример №2 . Методом дихотомического поиска найдите максимумы функций, пологая, что Δ=0,05.
f(x) = x*cos(x), 0 ≤x≤ π
Пример №3 . Методом бисекции найти решение нелинейного уравнения на отрезке [a,b] с точностью ε = 10 -2 . Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью ε = 10 -4 . Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности число итераций.
sqrt(t)+x 2 = 10, a = 2.6, b = 3
Найдем корни уравнения:
Используем для этого Метод половинного деления (метод дихотомии)..
Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b) 1 /2(a+b) и вычисляем f(c). Проверяем следующие условия:
1. Если |f(c)| 1 /2 n (b-a)
В качестве корня ξ. возьмем 1 /2(an+bn). Тогда погрешность определения корня будет равна (bn – an)/2. Если выполняется условие:
(bn – an)/2 1 /2(an+bn).
Решение.
Поскольку F(2.6)*F(3) 0, то a=2.8
Итерация 2.
Находим середину отрезка: c = (2.8 + 3)/2 = 2.9
F(x) = 0.113
F(c) = -0.487
Поскольку F(c)•F(x) 0, то a=2.825
Остальные расчеты сведем в таблицу.
N | c | a | b | f(c) | f(x) |
1 | 2.6 | 3 | 2.8 | -1.6275 | -0.4867 |
2 | 2.8 | 3 | 2.9 | -0.4867 | 0.1129 |
3 | 2.8 | 2.9 | 2.85 | 0.1129 | -0.1893 |
4 | 2.8 | 2.85 | 2.825 | -0.1893 | -0.3386 |
5 | 2.825 | 2.85 | 2.8375 | -0.3386 | -0.2641 |
6 | 2.8375 | 2.85 | 2.8438 | -0.2641 | -0.2267 |
Решение было получено и оформлено с помощью сервиса Метод Ньютона онлайн
Пример №2 . Локализовать корень нелинейного уравнения f(x) = 0 и найти его методом бисекции с точностью ε1 = 0,01. Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью ε2 = 0,0001. Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности ε2 число итераций.
При прохождении темы численные методы учащиеся уже умеют работать с электронными таблицами и составлять программы на языке паскаль. Работа комбинированного характера.Расчитана на 40 минут. Цель работы повторить и закрепить навыки паботы с программами EXCEL, ABCPascal. Материал содержит 2 файла. Один содержит теоретический материал, так как он и предлагается ученику . Во 2-м файле пример работы ученика Иванова Ивана.
Вложение | Размер |
---|---|
материал для ученика | 57.5 КБ |
работа ученика | 27 КБ |
Предварительный просмотр:
Аналитическое решение некоторых уравнений, содержащих, например тригонометрические функции может быть получено лишь для единичных частных случаев. Так, например, нет способа решить аналитически даже такое простое уравнение, как cos x=x
Численные методы позволяют найти приближенное значение корня с любой заданной точностью.
Приближённое нахождение обычно состоит из двух этапов:
1) отделение корней, т.е. установление возможно точных промежутков [a,b], в которых содержится только один корень уравнения;
2) уточнение приближённых корней, т.е. доведение их до заданной степени точности.
Мы будем рассматривать решения уравнений вида f(x)=0. Функция f(x) определена и непрерывна на отрезке [а.Ь]. Значение х 0 называется корнем уравнения если f(х 0 )=0
Для отделения корней будем исходить из следующих положений:
- Если f(a)* f(b] \a, b\ существует, по крайней мере, один корень
- Если функция y = f(x) непрерывна на отрезке [a, b], и f(a)*f(b) и f '(x) на интервале (a, b) сохраняет знак, то внутри отрезка [а, b] существует единственный корень уравнения
Приближённое отделение корней можно провести и графически. Для этого уравнение (1) заменяют равносильным ему уравнением р(х) = ф(х), где функции р(х) и ф(х] более простые, чем функция f(x). Тогда, построив графики функций у = р(х) и у = ф(х), искомые корни получим, как абсциссы точек пересечения этих графиков
Для уточнения корня разделим отрезок [а, b] пополам и вычислим значение функции f(х) в точке x sr =(a+b)/2. Выбираем ту из половин [a, x sr ] или [x sr ,b], на концах которых функция f(x) имеет противоположные знаки.. Продолжаем процесс деления отрезка пополам и проводим то же рассмотрение до тех пор, пока. длина [a,b] станет меньше заданной точности . В последнем случае за приближённое значение корня можно принять любую точку отрезка [a,b] (как правило, берут его середину). Алгоритм высокоэффективен, так как на каждом витке (итерации) интервал поиска сокращается вдвое; следовательно, 10 итераций сократят его в тысячу раз. Сложности могут возникнуть с отделением корня у сложных функций.
Для приближенного определения отрезка на котором находится корень можно воспользоваться табличным процессором, построив график функции
ПРИМЕР : Определим графически корень уравнения . Пусть f1(х) = х , a и построим графики этих функций. (График). Корень находится на интервале от 1 до 2. Здесь же уточним значение корня с точностью 0,001(на доске шапка таблицы)
Алгоритм для программной реализации
- а:=левая граница b:= правая граница
- m:= (a+b)/2 середина
- определяем f(a) и f(m)
- если f(a)*f(m)
- если (a-b)/2>e повторяем , начиная с пункта2
Точки графика функции на концах интервала соединяются хордой. Точка пересечения хорды и оси Ох (х*) и используется в качестве пробной. Далее рассуждаем так же, как и в предыдущем методе: если f(x a ) и f(х*) одного знака на интервале , нижняя граница переносится в точку х*; в противном случае – переносим верхнюю границу. Далее проводим новую хорду и т.д.
Осталось только уточнить, как найти х*. По сути, задача сводится к следующей: через 2 точки с неизвестными координатами (х 1 , у 1 ) и (х 2 , у 2 ) проведена прямая; найти точку пересечения этой прямой и оси Ох.
Запишем уравнение прямой по двум точках:
В точке пересечения этой прямой и оси Ох у=0, а х=х*, то есть
, откуда
процесс вычисления приближённых значений продолжается до тех пор, пока для двух последовательных приближений корня х„ и х п _1 не будет выполняться условие abs(xn-x n-1 ) е - заданная точность
Сходимость метода гораздо выше предыдущего
Алгоритм различается только в пункте вычисления серединной точки- пересечения хорды с осью абсцисс и условия останова (разность между двумя соседними точками пересечения)
Уравнения для самостоятельного решения: (отрезок в excel ищем самостоятельно)
Решение уравнения в Microsoft Excel x^3-8x-3=0 разными методами: графическим методом, методом половинного деления , хорд, касательных, простой итерации.
Вложение | Размер |
---|---|
Решение уравнений в Microsoft Excel | 1.01 МБ |
Предварительный просмотр:
Подписи к слайдам:
Решение уравнений в Microsoft Excel Выполнила Соколова М.А.
Вариант № 13 индивидуального расчетного задания Найдите приближенное значение уравнения с точностью 0,001 Представьте графически поставленную задачу;
Состав задания: Ознакомиться с теоретической частью задания; Провести расчет для своего варианта индивидуального задания в Microsoft Excel Оформить презентацию в Ms Power Point , включающую: § постановку задачи; § алгоритм расчета; § таблицу с расчетом из Ms Excel , график исходной функции; результат расчета и его анализ.
Постановка задачи: Пусть дано уравнение f(x) = 0, (a, b) - интервал, на котором f(x) имеет единственный корень. Нужно приближенно вычислить этот корень с заданной точностью. Примечание: Заметим, что если f(x) имеет k корней, то нужно выделить соответственно k интервалов.
Общая постановка задачи. Найти действительные корни уравнения f ( x ) =0 , где f ( x ) –алгебраическая или трансцендентная функция. Точные методы решения уравнений подходят только к узкому классу уравнений ( квадратные, биквадратные, некоторые тригонометрические, показательные, логарифмические) Задача численного нахождения корней уравнения состоит из двух этапов: 1.Отделение(локализация) корня; 2.Приближенное вычисление корня до заданной точности (уточнение корней)
6 Уточнение корня . Если искомый корень уравнения f(x)=0 , отделен, т.е. определен отрезок [ a , b ], на котором существует только один действительный корень уравнения, то далее необходимо найти приближенное значение коня с заданной точностью. Такая задача называется уточнения корня. Уточнения корня можно производить различными методами: 1)Метод половинного деления(бисекции); 2)Метод итераций; 3)Метод хорд(секущих); 4)Метод касательных(Ньютона); 5)Комбинированные методы.
индивидуальное расчетное задание Дано: Найти: Отделить корень заданного уравнения, пользуясь графическим методом, и вычислите один корень с точностью 0,001 при помощи программы Microsoft Excel
Графический метод: Для отделения корней уравнения естественно применять графический метод. График функции у = f ( х ) с учетом свойств функции дает много информации для определения числа корней уравнения f ( х ) = 0. До настоящего времени графический метод предлагалось применять для нахождения грубого значения корня или интервала, содержащего корень, затем применять итерационные методы, т. е. методы последовательных приближений для уточнения значения корня. С появлением математических пакетов и электронных таблиц стало возможным вычислять таблицы значений функции с любым шагом и строить графики с высокой точностью. Это позволяет уточнять очередной знак в приближенном значении корня при помощи следующего алгоритма: 1) если функция f ( x ) на концах отрезка [ а , b ] значения разных принимает значения разных знаков то делим отрезок на 10 равных частей и находим ту часть, которая содержит корень (таким способом мы можем уменьшить длину отрезка, содержащего корень, в 10 раз); 2) повторим действия предыдущего пункта для полученного отрезка. Этот процесс можно продолжать до тех пор, пока длина отрезка не станет меньше заданной погрешности.
Метод половинного деления: Постановка задачи: Пусть дано уравнение f(x) = 0, (a, b) - интервал, на котором f(x) имеет единственный корень. Нужно приближенно вычислить этот корень с заданной точностью. Примечание: Заметим, что если f(x) имеет k корней, то нужно выделить соответственно k интервалов. Метод половинного деления или дихотомии ): Метод основан на той идее, что корень лежит либо на середине интервала (a, b) , либо справа от середины, либо - слева, что следует из существования единственного корня на интервале (a, b) . Алгоритм для программной реализации: а:=левая граница b:= правая граница m:= ( a+b )/2 середина определяем f(a) и f(m) если f(a)*f(m) e повторяем , начиная с пункта2 m- искомый корень.
Расчет уравнения по методу половинного деления:
Метод простой итерации: Смысл метода простой итерации состоит в том, что мы представляем уравнение f(x) в виде и по формуле будем строить итерации, которые сходятся к искомому корню с интересующей степенью точности, но тут есть проблемы: возможно f(x) очень сложно представить в таком виде, да и не факт, что любая будет строить сходящиеся итерации, поэтому алгорим сводится к тому, чтобы оптимально найт и . Подготовка: Ищем числа m и M такие, что на (a, b) ; Представляем , где ; Алгоритм: 1. Выбираем х 0 из (a, b) ; 2.Вычисляем ; 3.Проверяем условие , где q=(M-m)/( M+m ) ; 4.Если оно ложно, то переходим к пункту 7; 5. х 0 =х 1 ; 6.Переходим к пункту 2 ; 7. х 1 –искомый корень.
Расчет уравнения по методу простой итерации:
Метод хорд Метод хорд заключается в замене кривой у = f ( x ) отрезком прямой, проходящей через точки ( а , f ( a )) и ( b , f ( b )) . Абсцисса точки пересечения прямой с осью ОХ принимается за очередное приближение. Чтобы получить расчетную формулу метода хорд, запишем уравнение прямой, проходящей через точки ( a , f ( a )) и ( b , f ( b )) и, приравнивая у к нулю, найдем х : Алгоритм метода хорд : 1) П усть k = 0; 2) В ычислим следующий номер итерации: k = k + 1. Найдем очередное k -e приближение по формуле: x k = a - f ( a )( b - a )/( f ( b ) - f ( a )). Вычислим f ( x k ); 3) Е сли f ( x k )= 0 (корень найден), то переходим к п. 5. Если f ( x k ) × f ( b )>0, то b = x k , иначе a = x k ; 4) Е сли |x k – x k -1 | > ε , то переходим к п. 2; 5) В ыводим значение корня x k ; 6) К онец.
Расчет уравнения по методу хорд:
Метод касательных В точке пересечения касательной с осью Оx переменная у = 0. Приравнивая у к нулю, выразим х и получим формулу метода касательных: Теорема. Пусть на отрезке [а, b]выполняются условия: 1) функция f(x)и ее производные f '(х)и f ''(x)непрерывны; 2) производные f '(x)и f ''(x)отличны от нуля и сохраняют определенные постоянные знаки; 3) f(a)× f(b) 0, то итерационная последовательность сходится монотонно
Расчет уравнения по методу касательных:
Вывод о проделанной работе: Вывод: Решение уравнения в Microsoft Excel Было выполнено: графическим методом, методом половинного деления , хорд, касательных, простой итерации. Графический метод самый неточный, чем остальные методы. метод половинного деления быстрее графического метода, а метод простой итерации намного точнее предыдущих. Метод хорд более точный, чем все остальных методы. Метод касательный относительно быстрее и точнее всех методов.
По теме: методические разработки, презентации и конспекты
УЧЕБНОЕ ПОСОБИЕ по разделу «Электронные таблицы» Microsoft Excel
Учебное пособие является практическим руководством по электронным таблицам для студентов колледжа, в котором описаны основные приёмы и правила работы в Excel.Оно содержит систематизированную информаци.
Самостоятельная работа по Microsoft Excel (5 вариантов)
В каждом варианте пять заданий.Задание 1. Оформить рабочий лист по образцу и вычислить значение выражения в соответствующей ячейке. Проверяется умение набора формул в строку.Задание 2. Определить каки.
Методический материал для внеаудиторной работы студентов:"Интерфейс и объекты электронных таблиц Microsoft Excel".
Методический материал содержит теоретический материал, необходимый для выполнения практических работ: основные понятия и термины электронных таблиц, способы автоматизации ввода данных, ввода и копиров.
Курс занятий «Электронные таблицы Microsoft Excel. Теория и практика».
Цикл занятий для повышения компьютерной грамотности педагогов школы.
Методическая разработка занятия по предмету Элементы высшей математики по теме: "Определение обыкновенных дифференциальных уравнений. Общее и частное решение. Уравнения с разделенными переменными".
Определение обыкновенных дифференциальных уравнений. Общее и частное решение. Уравнения с разделенными переменными.Тип занятия: комбинированный, с элементами игры.Формы занятия: индивидуальная, группо.
Microsoft Excel - основы работы в программе
В презентации описаны основы работы в программе MS Excel 2007-2010:правила работы с ячейками и текстом, элементы их форматирования,работа с числами, создание простых формул,применение функций,сортиров.
Использование надстроек в Excel. Решение уравнений. 11 класс
В файле «Решение_урав.xls» (в книге Excel) находятся различные задание по работе с надстройкой Поиск решения и небольшой теоретический материал.
где f(x) - алгебраическая или трансцендентная функция.
Решить такое уравнение – значит установить, имеет ли оно корни, сколько корней, и найти значения корней (с указанной точностью).
- Отделение корней алгебраических и трансцендентных уравнений
Решение указанной задачи начинается с отделения корней, т.е. с установления:
- количества корней;
- наиболее «тесных» промежутков, каждый из которых содержит только один корень.
Чтобы выяснить имеет ли уравнение корень:
1) Строят график функции y=f(x) для уравнения вида f(x)=0. Значения действительных корней уравнения являются абсциссами точек пересечения графиков функций y=f(x) с осью Ох.
y=f(x) кривая трижды пересекает ось абсцисс, следовательно уравнение f(x)=0 имеет три простых корня
если кривая касается оси абсцисс, то уравнение имеет двукратный корень
если кривая имеет точку перегиба, следовательно уравнение имеет трехкратных действительных корень.
2) представляют уравнение в виде f(x)=g(x) и стоят графики функции y=f(x) и y=g(x). Значения действительных корней уравнения являются абсциссами точек пересечения графиков функций у=f(х) и y=g(x). По графику определяются два числа а и b, между которыми заключен корень.
кривые y=f(x) и y=g(x) пересекаются в двух точках, абсциссы которых х 1 и х 2 являются корнями уравнения f(x)=g(x)
При решении задачи об отделении корней бывают полезными следующие очевидные положения:
- Если непрерывная на отрезке [ a;b ] функция f(x) принимает на его концах значения разных знаков (т.е. f(a) . f(b) ), то уравнение (2.1) имеет на этом отрезке, по меньшей мере, один корень.
- Если функция f(x) к тому же еще и монотонна, то корень на отрезке [ a;b ] единственный.
Пример: Для графического отделения корней уравнения преобразуем его к равносильному уравнению и отдельно построим графики функций .
Из рисунка видно, что графики пересекаются в одной точке, то есть уравнение имеет единственный корень х= Е и этот корень находится на отрезке [1;1,5].
Вычислим для проверки значения функции на концах отрезка [1;1,5]: f(1)=0.909298; f(1,5)= -0,264344, на концах отрезка значения функции имеют разные знаки, тогда корень на отрезке [1;1,5] действительно имеется.
Для уточнения корней можно пользоваться различными методами. Рассмотрим некоторые из них.
Пусть уравнение (2.1) имеет на отрезке [ a;b ] единственный корень, причем функция f(x) на этом отрезке непрерывна.
1) Разделим отрезок [ a;b ] пополам точкой с=(a+b)/2 .
2) Если f(c)=0, то корень найден.
3) Если f(c)≠ 0(что практически наиболее вероятно), то нужно выбрать отрезок, на котором расположен корень. Возможны два случая: f(x) меняет знак либо на отрезке [ a;с ] (рис 2.1), либо на отрезке [ с;b ] (рис 2.2).
Рис 2.1. – функция f(x) меняет знак Рис 2.2. – функция f(x)
на отрезке [a;c] меняет знак на отрезке [c;b]
Выбирая отрезок, на котором функция меняет знак, мы выбираем отрезок, содержащий корень.
4) Этот отрезок снова делим пополам и повторяем шаги 1)-3)
Тогда, либо через конечное число делений отрезка пополам найдём точное значение корня, либо построим бесконечную последовательность вложенных отрезков:
[a; b] [a1; b1] . [an; bn], длины которых стремятся к нулю.
Как только |b n –a n |/2 E , где Е - заданная точность, то в качестве
приближённого значения корня можно взять середину этого отрезка: х=(a n +b n )/2.
Метод половинного деления требует утомительных ручных вычислений, однако он легко реализуется с помощью программы на компьютере.
- Пример решения уравнений методом половинного деления
Пример: Найти корень уравнения на отрезке [1,3;1,5] с точностью до
Решение: Уравнение имеет единственный корень на отрезке [1,3;1,5].
- Уточним корень уравнения: Найдем середину отрезка [1,3;1,5]: .
Определим, на каком из полученных отрезков [1,3;1,4] и [1,4;1,5] функция меняет свой знак.
Значит, корень уравнения находится на отрезке [1,3;1,4].
Проверим, достигается ли заданная точность решения 10 -4 :
, точность не достигнута.
- Продолжаем процесс разделим отрезок [1,3;1,4] пополам точкой .
Определим, на каком из полученных отрезков [1,3;1,35] и [1,35;1,4] функция меняет свой знак.
Значит, корень уравнения находится на отрезке [1,35;1,4].
Проверим, достигается ли заданная точность решения 10 -4 :
, точность не достигнута.
- Снова разделим отрезок [1,35;1,4] пополам точкой .
Определим, на каком из полученных отрезков [1,35;1,375] и [1,375;1,4] функция меняет свой знак.
Значит, корень уравнения находится на отрезке [1,375;1,4].
Проверим, достигается ли заданная точность решения 10 -4 :
, точность не достигнута.
- Продолжая делить отрезок пополам и проверять знаки функции на новых промежутках, до тех пор, пока не будет достигнута нужная точность решения ( сделайте самостоятельно ), получим:
Решение уравнения с точностью 10 -4 : х=1,3994.
Алгоритм метода половинного деления
1) Найдем середину отрезка [a; b]: c=(a+b)/2;
2) Вычислим значения функции в точках a и c и найдем произведение полученных значений: d=f(c)*f(a);
3) Если d>0, то теперь точкой a станет c: a=c; Если d ε или
|a-b|/2> ε , то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;
Рассмотрим последовательный поиск точки xф ∈ [0;1], в которой унимодальная на отрезке [0,1] функция f(x) достигает наименьшего значения f0=f(x0).
Метод прямого поиска, основанный на делении пополам отрезка, на котором находится точка x0, называют методом дихотомии.
Рис.1
Алгоритм метода дихотомии
Пусть известно, что на k -м шаге последовательного поиска xф ∈ [ak;bk] ⊂ [0;1] (на первом шаге при k=1 имеем a1=0 и b1=1). На отрезке [ak, bk] длиной lk выберем две точки xk1=(ak+bk)/2-δ и xk2=(ak+bk)/2+δ (рис. 1), где δ>0 — некоторое достаточно малое число. Вычислим значения f(xk1) и f(xk2) функции f(x) в этих точках и выполним процедуру исключения отрезка.
Если f(xk1) < f(xk2), то в силу унимодальности функции f(x) имеем xф ∈ [ak;xk2], а отрезок [xk2,bk] исключаем из дальнейшего рассмотрения.
Наоборот, если f(xk1) ≥f(xk2), то xф ∈ [xk1;bk], а отрезок [ak,xk1] не рассматриваем. В результате получим новый отрезок [ak+l;bk+l] ⊂ [ak;bk].
Если длина lk+1 нового отрезка больше заданной наибольшей допустимой длины ε0интервала неопределенности, то алгоритм метода дихотомии переходит к (k+1) -му шагу, повторяя все описанные для k -го шага действия. Если же lk≤ε0, то вычисления прекращают и полагают x0=(ak+1+bk+1)/2.
Так как lk+1=lk/2+δ или lk+1-2δ =(lk-2δ)/2, то
.
Из этого равенства выводим следующую формулу длины lk отрезка [ak,bk], получаемого на k-м шаге метода дихотомии:
. (1)
Из (1) следует, что lk+1→2δ при k→∞, но при этом lk+1>2δ. Поэтому выполнение неравенства lk+10, означающее достижение заданной точности нахождения точки xф, возможно лишь при условии выбора 2δ0. Кроме того, нужно учитывать неизбежную погрешность, возникающую при вычислении приближенных значений функции f(x) . Это приводит к дополнительной погрешности ∆0 при нахождении точки x0 (см. 2). Поэтому выбор значения δ ограничен и снизу, т.е.
∆0< 2δ0. (2)
Если эти неравенства нарушаются, то знак разности может не совпадать со знаком разности f(xk1)-f(xk2), что приводит к ошибочному выполнению процедуры исключения отрезка.
Итак, метод дихотомии — это последовательное построение на каждом k-м шаге поиска точек xk1=(ak+bk)/2-δ и xk2=(ak+bk)/2+δ, симметричных относительно середины отрезка [ak,bk] длины lk. После выполнения k-го шага будет выделен отрезок [ak+1,bk+1] длины lk+1 и вычислено N=2k значений функции. Используя формулу (1) для длины отрезка (интервала неопределенности) и полагая l1=1, получаем
. (3)
Отметим, что после исключения отрезка на k -м шаге описанного алгоритма точки xk1 и xk2 принадлежат новому отрезку [ak+1,bk+1], причем одна из них является внутренней для этого отрезка. Но вычисленное в этой точке значение функции f(x) в методе дихотомии не используют для исключения отрезка на следующем шаге, а проводят вычисления в двух новых точках. Существуют методы последовательного поиска, в которых на каждом k -м шаге начиная с k=2 вычисляют лишь одно новое значение функции в точке, принадлежащей отрезку [ak+1,bk+1]. Это значение вместе с уже вычисленным на предыдущем шаге значением функции во внутренней точке отрезка [ak,bk] используют при выполнении процедуры исключения отрезка на следующем шаге последовательного поиска.
Пример . Пользуясь методом дихотомии (методом одномерного поиска), минимизировать следующую функцию с точностью до одного знака после запятой: f(x)=3x 4 +(x-1) 2
Читайте также: