Алгоритм метода половинного деления. Методы дихотомии

Метод половинного деления (метод также известен как метод Больцано или метод дихотомии ) один из методов решения нелинейных уравнений и основан на последовательном сужении интервала, содержащего единственный корень уравнения . Итерационный процесс выполняется до того момента, пока не будет достигнута заданная точность .

Пусть дано уравнение и определен отрезок такой, что данный отрезок содержит один единственный корень уравнения . Тогда по концам заданного отрезка функция имеет значения, противоположные по знаку: . Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов - умножение значений функции на концах отрезка и определение знака произведения путём сравнения результата умножения с нулём:

Отрезок называется начальным интервалом неопределенности, потому что известно, что корень ему принадлежит, но его местоположение с требуемой точностью не определено.

Процедура уточнения положения корня заключается в построении последовательности вложенных друг в друга отрезков, каждый из которых содержит корень уравнения. Для этого находится середина текущего интервала неопределенности , , и в качестве следующего интервала неопределенности из двух возможных выбирается тот, на концах которого функция имеет разные знаки.

Процесс завершается, когда длина текущего интервала неопределенности становится меньше заданной величины , задающей точность нахождения корня. В качестве приближенного значения корня берется середина последнего интервала неопределенности.

Метод имеет линейную, но безусловную сходимость, и его погрешность за каждую итерацию уменьшается в два раза:

Из данного соотношения можно оценить число итераций k для достижения заданной точности :

Из полученной формулы можно сделать вывод, что для достижения точности от длины первоначального промежутка необходимо выполнить примерно десять итераций.

К достоинствам метода также следует отнести то, что он позволяет найти простой корень уравнения любых непрерывных функций при любых значениях таких, что .

Недостатки метода - он не обобщается на системы нелинейных уравнений и не может использоваться для нахождения корней четной кратности.

Алгоритм нахождения корня нелинейного уравнения по методу половинного деления.

1. Найти начальный интервал неопределенности одним из методов отделения корней. Задать погрешность расчета (малое положительное число ) и начальный шаг итерации () .

2. Найти середину текущего интервала неопределенности:

3. Необходимо найти значение функции в точках , и . Далее необходимо проверить два условия:

Если выполняется условие , то искомый корень находится внутри левого отрезка положить, ;

Если выполняется условие , то искомый корень находится внутри правого отрезка принять , .

В результате находится новый интервал неопределенности, на котором находится искомых корень уравнения:

4. Проверяем новый отрезок на предмет заданной точности, в случае:

Если длина нового отрезка меньше заданной точности , то итерационный процесс заканчивается. Приближенное значение корня определяется по формуле:

Если длина нового отрезка не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.

Решение алгебраического уравнения. Для численного решения алгебраических уравнений существует множество способов. Среди самых известных можно назвать метод Ньютона, метод Хорд, и «всепобеждающий» метод Половинного Деления. Сразу оговоримся, что любой метод является приближенным, и по сути дела лишь уточняющим значение корня. Однако уточняющим до любой точности, заданной Нами.

Метод половинного деления или дихотомии (дихотомия - сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f(x)=0 состоит в делении пополам отрезка , где находится корень. Затем анализируется изменение знака функции на половинных отрезках, и одна из границ отрезка переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала становится меньше заданной погрешности нахождения корня?, либо функция попадает в полосу шума?1 - значение функции сравнимо с погрешностью расчетов.

Сначала поставим задачу. Дана монотонная, непрерывная функция f(x), которая содержит корень на отрезке , где b>a. Определить корень с точностью?, если известно, что f(a)*f(b)<0

Дано уравнение вида:

Необходимо найти удовлетворяющие ему значения x.

Итак, приступим к решению. Первым делом, определимся, что значит f(x)=0. Посмотрите на рис.1. На нем изображен график некоей функции. В некоторых точках этот график пересекает ось абсцисс. Координаты x этих точек нам и нужно найти. Если вид уравнения простой или стандартный, например, квадратное уравнение или линейное, то применять численный метод здесь совершенно ни к чему. Но если уравнение у нас такое:

F(x)=x3-14x2+x+ex; (2)

То ни в каком учебнике вы не найдете метода аналитического решения этого кошмара. Здесь и приходит на помощь непобедимый численный метод. Метод половинного деления. Из самого названия метода можно предположить, что нам понадобится что-то делить пополам.

Ученикам метод половинного деления можно преподнести в виде решения задачи.

Задача

Идет осада неприятельской крепости. На некотором расстоянии от нее установили новую пушку. Под каким углом к горизонту надо стрелять из этой пушки, чтобы попасть в заданный участок крепостной стены.

Над моделью этой задачи физики изрядно поработали. Оно и понятно: ведь многие научные задачи, как и эта, возникали прежде всего в военном деле. И решение этих задач почти всегда считалось приоритетным.

Какие же факторы принять за существенные в этой задаче? Поскольку речь идет о средневековье, то скорость снаряда и дальность полета невелики. Значит можно считать несущественным, что Земля круглая (помните обсуждение в параграфе 27), и пренебречь сопротивлением воздуха. Остается единственный фактор - сила земного притяжения.

Математик тут бы сказал, что надо решить уравнение. Мы тоже будем решать, только приближенно и очень похоже на то, как делают настоящие артиллеристы. Они же поступают следующим образом: производят несколько выстрелов, беря цель «в вилку», т.е. одно попадание выше цели, а другое ниже. Затем делят пополам угол между этими выстрелами, и при стрельбе под таким углом снаряд ложится к цели намного ближе. Но если все же не попали, то новую «вилку» снова делят пополам и т.д.

Мы заранее можем указать «вилку» для угла: 0 и?/4 (мы надеемся, что вы помните какой угол имеет радианную меру?/4 и чему приближенно равно?). А дальше будем делить пополам эту «вилку» и смотреть, куда попадает снаряд, пока не добьемся нужного результата.

Как же долго нам придется вести «пристрелку», чтобы получить угол?, с нужной точностью? Чтобы ответить на этот вопрос, отвлечемся от нашей задачи и сформулируем на чисто математическом языке, что и как мы находили.

Нам даны некоторая функция f(x) и отрезок , причем на концах этого отрезка эта функция принимает значения противоположных знаков. Если функция непрерывна, т.е. ее график - непрерывная линия, то ясно, что график функции пересекает ось абцисс в некоторой точке с отрезка , как показано на рисунке 1. Иными словами, f(c)=0, т.е. с - корень уравнения f(x)=0.

Как же предлагается находить этот корень? А вот так. Делим отрезок пополам, т.е. берем середину отрезка а+b/2. В этой точке вычисляем значение функции f(x) (рис. 2). Если это значение 0, то корень найден; если нет, то оно имеет тот же знак, что и значение на одном из концов отрезка . Тогда этот конец заменям точкой а+b/2. Новый отрезок тоже содержит корень уравнения f(x)=0, поскольку на его концах функция f(x) снова имеет разные знаки. Однако этот отрезок в 2 раза короче предыдущего. И самое главное - с ним можно поступить точно так же. со следующим отрезком еще раз проделать то же самое и т.д. поскольку длина отрезка каждый раз уменьшается вдвое, мы можем получить отрезок сколь угодно малой длины, внутри которого содержится корень уравнения f(x)=0. Например, если исходный отрезок был , т.е. имел длину 1, то через десять шагов мы получим отрезок длиной. Это означает, что концы отрезка дают нам приближенное значение корня с точностью, равной длине отрезка: левый конец отрезка - приближенное значение корня с недостатком, правый конец - приближенное значение корня с избытком.

Фактически мы сейчас сформулировали метод приближенного решения уравнения f(x)=0. Его можно было бы назвать методом артиллерийской пристрелки. Но математики называют его методом половинного деления.

Алгоритм

1) Найдем середину отрезка : c=(a+b)/2;

2) Вычислим значения функции в точках a и c и найдем произведение полученных значений: d=f(c)?f(a);

3) Если d>0, то теперь точкой a станет c: a=c; Если d<0, то точкой b станет c: b=c;

4) Вычислим разность a и b, сравним ее с точностью?: если |a-b|> ?, то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;

Его ещё называют методом дихотомии. Этот метод решения уравнений отличается от выше рассмотренных методов тем, что для него не требуется выполнения условия, что первая и вторая производная сохраняют знак на интервале . Метод половинного деления сходится для любых непрерывных функций f(x) в том числе не дифференцируемых.

Разделим отрезок пополам точкой. Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке (Рис. 3.8), либо на отрезке (Рис. 3.9)

Выбирая в каждом случае тот отрезок, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения.

Пример 4. Уравнение 5x - 6x -3 = 0 имеет единственный корень на отрезке . Решить это уравнение методом половинного деления.

Решение : Программа на языке Паскаль может быть такой:

function f(x: real): real;

f:=exp(x*ln(5))-6*x-3;

a, b, e, c, x: real;

while abs(b-a)>e do

if f(a)*f(c)<0 then

writeln ("x=",x:3:3," f(x)=",f(x):4:4);

Результат выполнения программы:

e=0.001 x=1.562 f(x)=-0.0047

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

1.Определить новое приближение корня х в середине отрезка [а,b]: х=(а+b)/2.

2.Найти значения функции в точках а и х : F(a) и F(x) .

3.Проверить условие F(a)*F(x) < 0 . Если условие выполнено, то корень расположен на отрезке [а,х] b переместить в точку х (b=х) . Если условие не выполнено, то корень расположен на отрезке [х,b] . В этом случае необходимо точку а переместить в точку х (а=х) .

4.Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до того времени, пока не будет выполнено условие /F(x)/ < e (заданная точность).

21.Метод простой итерации для поиска корней. Геометрическая интерпретация .

Исходное уравнение f(x)=0 эквивалентными преобразованиями приводится к виду с выделением неизвестного в левой части, то есть x=φ(x),где φ(x) – некоторая функция, связанная с исходной функцией f(x). Такая форма записи уравнения позволяет, задаваясь начальным приближением x 0, получить следующее, первое приближение x 1 =φ(x 0), далее получают второе приближение x 2 =φ(x 1) и так далее x n +1 =φ(x n)…. Последовательность {x n }= x 0, x 1, x 2, …, x n ,… называется последовательностью итераций или приближений с начальным значением x 0. Если функция φ(x) на непрерывна и существует предел ξ = lim x n при n→∞, то, переходя к пределу в равенстве x n +1 =φ(x n), найдем, что при n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n), то есть ξ=φ(ξ).Следовательно, если последовательность приближений сходится, то она сходится к корню уравнения (2), а значит и уравнения (1). В силу сходимости итерационного процесса этот корень можно вычислить при достаточно большом n с любой заданной точностью. Однако необходимо определить при каких условиях последовательность {x n }будет сходящейся. Получим связь между погрешностями двух соседних приближений - ε n и ε n +1: x n =ξ+ε n , x n +1 =ξ+ε n +1. Подставим эти представления в x n +1 =φ(x n) и разложим функцию в ряд Тейлора в окрестности корня:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n φ’(ξ)+(ε n 2 /2!)φ’’(η), где η Î [ξ; ξ+ε n ] Ì .Поскольку ξ - корень, то ξ=φ(ξ) , то получаем: ε n +1 =ε n φ’(ξ)+(φ’’(η)/2)ε n 2 .Так как ε<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n |ε n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.

Теорема о сходимости метода простых итераций. Пусть ξ - корень уравнения x=φ(x), функция φ(x) определена и дифференцируема на отрезке , причем для x Î все значения функции φ (x) Î . Тогда, если существует такое положительное число q<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ’(х)>-1, то соседние приближения лежат по разную сторону от корня – такую сходимость называют двусторонней (или спиралевидной) – рис.2. Поскольку в этом случае корень заключен в интервале, концами которого являются соседние приближения – ξÎ(x n ,x n +1), то выполнение условия |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.

Чтобы можно было сравнивать итерационные методы по скорости сходимости, вводят следующие понятия:

Определение 1: Сходимость последовательности {x n } к ξ называется линейной (соответственно, итерационный процесс - линейно сходящимся ), если существует такая постоянная CÎ(0,1) и такой номер n 0 , что выполняются неравенства |ξ-x n +1 |≤C|ξ-x n | для n≥n 0.

Для введенных ранее погрешностей это означает |ε n+1 |≤C|ε n |. В методе простой итерации в роли постоянной C выступает значение q, то есть метод сходится линейно.

Определение 2: Последовательность приближений {x n } сходится к ξ по меньшей мере с р -ым порядком (соответственно, итерационный процесс имеет по меньшей мере p -ый порядок), если найдутся такие константы C>0, p ≥1 и n 0 , что для всех n≥n 0 выполняются условия |ξ-x n +1 |≤C|ξ-x n | р (или в других обозначениях |ε n+1 |≤C|ε n | p).

Иванов Иван

При прохождении темы численные методы учащиеся уже умеют работать с электронными таблицами и составлять программы на языке паскаль. Работа комбинированного характера.Расчитана на 40 минут. Цель работы повторить и закрепить навыки паботы с программами EXCEL, ABCPascal. Материал содержит 2 файла. Один содержит теоретический материал, так как он и предлагается ученику. Во 2-м файле пример работы ученика Иванова Ивана.

Скачать:

Предварительный просмотр:

Решение уравнений

Аналитическое решение некоторых уравнений, содержащих, например тригонометрические функции может быть получено лишь для единичных частных случаев. Так, например, нет способа решить аналитически даже такое простое уравнение, как cos x=x

Численные методы позволяют найти приближенное значение корня с любой заданной точностью.

Приближённое нахождение обычно состоит из двух этапов:

1) отделение корней, т.е. установление возможно точных промежутков , в которых содержится только один корень уравнения;

2) уточнение приближённых корней, т.е. доведение их до заданной степени точности.

Мы будем рассматривать решения уравнений вида f(x)=0. Функция f(x) определена и непрерывна на отрезке [а.Ь]. Значение х 0 называется корнем уравнения если f(х 0 )=0

Для отделения корней будем исходить из следующих положений:

Если f(a)* f(b] \a, b\ существует, по крайней мере, один корень
Если функция y = f(x) непрерывна на отрезке , и f(a)*f(b) и f "(x) на интервале (a, b) сохраняет знак, то внутри отрезка [а, b] существует единственный корень уравнения

Приближённое отделение корней можно провести и графически. Для этого уравнение (1) заменяют равносильным ему уравнением р(х) = ф(х), где функции р(х) и ф(х] более простые, чем функция f(x). Тогда, построив графики функций у = р(х) и у = ф(х), искомые корни получим, как абсциссы точек пересечения этих графиков

Метод дихотомии

Для уточнения корня разделим отрезок [а, b] пополам и вычислим значение функции f(х) в точке x sr =(a+b)/2. Выбираем ту из половин или , на концах которых функция f(x) имеет противоположные знаки.. Продолжаем процесс деления отрезка пополам и проводим то же рассмотрение до тех пор, пока. длина станет меньше заданной точности . В последнем случае за приближённое значение корня можно принять любую точку отрезка (как правило, берут его середину). Алгоритм высокоэффективен, так как на каждом витке (итерации) интервал поиска сокращается вдвое; следовательно, 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 ищем самостоятельно)

sin(x/2)+1=x^2 (х=1,26)

x-cosx=0 (х=0,739)

x^2+4sinx=0 (х=-1,933)

x=(x+1) 3 (х=-2,325)

Метод дихотомии имеет свое название от древнегреческого слова, что в переводе означает деление надвое. Именно поэтому данные метод имеет еще второе название: метод половинного деления. Его мы используем довольно часто. Допустим, играя в игру "Угадай число", где один игрок загадывает число от 1 до 100, а другой пытается его отгадать, руководствуясь подсказками "больше" или "меньше". Логично предположить, что первым числом будет названо 50, а вторым в случае если оно меньше - 25, если больше - 75. Таким образом, на каждом этапе (иттерации) неопределенность неизвестного уменьшается в 2 раза. Т.е. даже самый невезучий в мире человек отгадает загаданное число в данном диапазоне за 7 предположений вместо 100 случайных утверждений.

Метод половинного деления в решении уравнения

Правильное решение уравнения методом половинного деления возможно лишь в том случае, если известно, что на заданном интервале имеется корень и он является единственным. Это совсем не означает что метод дихотомии может использоваться только для решения линейных уравнений. Для нахождения корней уравнений более высокого порядка методом половинного деления необходимо сначала отделить корни по отрезкам. Процесс отделения корней осуществляется путем отыскания первой и второй производной от функции и приравнивании их нулю f"(x)=0 и f""(x)=0. Далее определяются знаки f(x) в критических и граничных точках. Интервал, где функция меняет знак |a,b|, где f(a)*f(b)< 0.

Алгоритм метода дихотомии

Алгоритм метода дихотомии очень прост. Рассмотрим отрезок |a,b| в пределах которого имеется один корень x 1

На первой этапе вычисляется x 0 =(a+b)/2

Далее определеяется значение функции в этой точке: если f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.

Вычисления прекращаются, когда разность b-a меньше требуемой погрешности.

В качестве примера использования метода половинного деления найдем корень на интервале уравнения x 3 -3*x+1=0 с точностью в 10 -3

Как видно из таблицы корнем является 0,347. Колличество иттераций равно 10. Условие завершения: a-b=0,0009< 10 -3

Метод половинного деления или метод дихотомии является наиболее простым для решения уравнения в численных методах.

Скачать:

Решение уравнения методом дихотомии - Решение уравнения методом половинного деления в Паскале.