Способ деление отрезка пополам

Метод деления отрезка пополам.

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

Рассмотрим метод деления отрезка пополам более подробно.

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

При отыскании корня методом половинного деления сначала вычисляются значения функции в точках a и b — соответственно f(a) и f(b), имеющие противоположные знаки. Далее по формуле x_ср=(a+b)/2 вычисляется координата центра отрезка [a, b] и находится значение функции в этой точке f(x_ср). Оно сравнивается со значениями функции на концах отрезка. Если функция меняет знак на отрезке [a, x_ср], то весь отрезок [a, b] усекается до его левой части, то есть x_ср становится правой границей отрезка (b). Аналогично, если функция меняет знак на отрезке [x_ср, b], отрезок [a, b] усекается до правой части. Эти операции повторяются до тех пор, пока разница между соседними значениями x не станет меньше или равной выбранной точности .

	· Простота; · Быстрое достижение результата.
	· Необходимо заранее знать отрезок, на котором функция меняет знак, что не совсем удобно. · Линейная сходимость.

Блок-схема

алгоритма поиска корня уравнения f(x)=0

Методом деления отрезка пополам

Метод хорд.

Является более быстрым способом нахождения корня уравнения f(x)=0 лежащего на отрезке [a;b], таком, что f(a)*f(b) 0. Разделим отрезок в отношении

Это даёт приближённое значение корня x₁=a+h₁ ,

Применяя этот приём, к тому из отрезков [a;x₁] или [x₁;b] на концах которого функция имеет противоположные знаки. Получим второе приближение корня x₂.

Геометрически, метод хорд эквивалентен замене кривой y=f(x) хордой проходящей через т. а и т. B.

Полагая, что х=х₁ и у=0, получим х₁=а — f(a)*(b-a)/(f(b)-f(a)), x₁ – первое приближение.

Для сходимости процессов корень должен быть отделён вторая производная должна сохранять знак на отрезке [a;b].

Процесс вычисления заканчивается когда разность между 2-мя значениями корня

Блок-схема

алгоритма поиска корня уравнения f(x)=0

нет

да

методом хорд

Метод простой итерации.

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

при заданных начальных условиях : начальное приближение и точность вычисления. При использовании метода простой итерации , важным является выбор функции х = F(x) , при этом должно выполняться условие :

│f(x)│ 0 , то разделим первое уравнение на а11 и умножим

на а21 . Вычтем из второго уравнения преобразованное первое. Получим :

Сейчас легко находим v:

Аналогично для матриц большего порядка.

Метод итерации.

При большом числе неизвестных используют приближённо-численные методы.

|a11 a12 … a1n| |B1| |x1|

A=| a21 a22 … a2n| B= |B2 x=|x2|

|an1 an2 … ann| |Bn| |xn|

Предположим, что аii<>0. Разрешим первое уравнение относительно х1, второе относительно х2 и т.д.

Далее решаем методом последовательных приближений. За начальное приближение выбираем столбец свободных членов:

Алгоритм нахождения корней:

Вычисление заканчивается тогда, когда разность между 2-мя ближними итерациями значений корня будет 2 + a₃t 3 + a₄t 4 + … + a_nt n

по схеме Горнера представляется в виде

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

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем.

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала.

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.).

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот.

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:

Источник

Способ деление отрезка пополам

Pers.narod.ru. Обучение. Лекции по численным методам. Приближённое решение нелинейных алгебраических уравнений

1. Приближенное решение нелинейных алгебраических уравнений

Дано нелинейное алгебраическое уравнение

Нелинейность уравнения означает, что график функции не есть прямая линия, т.е. в f(x) входит x в некоторой степени или под знаком функции.

Решить уравнение – это найти такое x* ∈ R: f(x*)=0. Значение x* называют корнем уравнения. Нелинейное уравнение может иметь несколько корней. Геометрическая интерпретация корней уравнения представлена на рис. 1. Корнями уравнения (1) являются точки x₁*, x₂*, x₃*, в которых функция f(x) пересекает ось x.

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

В приближенных методах процесс нахождения решения, вообще говоря, бесконечен. Решение получается в виде бесконечной последовательности <x_n>, такой, что . По определению предела, для любого (сколь угодно малого) ε, найдется такое N, что при n>N, |x_n – x*| / (x) не меняет знак на отрезке [a, b], т.е. f(x) – монотонная функция, в этом случае отрезок [a,b] будет интервалом изоляции.

Читайте также:  Звуки речи способы их образования логопедическое занятие 1 класс

Если корней несколько, то для каждого нужно найти интервал изоляции.

Существуют различные способы исследования функции: аналитический, табличный, графический.

Аналитический способ состоит в нахождении экстремумов функции f(x), исследование ее поведения при и нахождение участков возрастания и убывания функции.

Графический способ – это построение графика функции f(x) и определение числа корней по количеству пересечений графика с осью x.

Табличный способ – это построение таблицы, состоящей из столбца аргумента x и столбца значений функции f(x). О наличии корней свидетельствуют перемены знака функции. Чтобы не произошла потеря корней, шаг изменения аргумента должен быть достаточно мелким, а интервал изменения достаточно широким.

Решить уравнение x 3 ‑ 6x 2 +3x+11=0, т.е. f(x)= x 3 ‑ 6x 2 +3x+11.

Найдем производную f / (x)=3x 2 -12x+3.

Найдем нули производной f / (x)=3x 2 -12x+3=0; D=144-4*3*3=108;

X₁== 0.268;

X₂== 3.732;

Так как f / ()>0, то f / (x)>0 при , f / (x) / (x)>0 при . Кроме того, f()= 0. Следовательно, на интервале возрастает от до f(x₁)= 3x₁ 2 -12x₁+3=11.39; на интервале — убывает до f(x₂)= 3x₂ 2 -12x₂+3=-9.39 и на интервале возрастает до , т.е. уравнение имеет три корня.

Найдем интервалы изоляции для каждого из корней.

Рассмотрим для первого корня отрезок [-2, -1]:

f(-2)= -27 0, f / (x)>0 при т.е. этот отрезок является интервалом изоляции корня.

Рассмотрим для второго корня отрезок [1, 3]:

f(1)= 9>0, f(3)= -7 / (x) 0, f / (x)>0 при т.е. этот отрезок является интервалом изоляции корня.

Источник

Метод деления отрезка пополам (метод бисекции)

Один из простейших методов нахождения корней нелинейных уравнений состоит в следующем. Допустим, что нам удалось найти отрезок [а, b], на котором расположено искомое значение корня (далее мы предполагаем, что х = с – единственный корень на отрезке [а, b], а если корней на [а, b] несколько, то в результате применения метода деления отрезка пополам и метода хорд (см. разд. 1.1.3) будет найдено приближенное значение одного из корней) х = с, т.е. .

В качестве начального приближения корня с0 принимаем середину этого отрезка: с0=(а+b)/2. Далее исследуем значения функции F(x) на концах отрезков [а, с0] и [с0, b], т.е. в точках а, с0, b. Тот из отрезков, на концах которого F(x) принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка [a1,b1]. Вторую половину отрезка [а, b], на которой знак F(x) не меняется, отбрасываем. В качестве первого приближения корня принимаем середину нового отрезка c1 = (a1+b1)/2 и т.д. Таким образом, k-е приближение вычисляем как

Читайте также:  Интеллект карты как способ визуализации

(1.2)

После каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, а после kитераций он сокращается в 2kраз:

(1.3)

Пусть приближенное решение требуется найти с точностью до некоторого заданного малого числа ε > 0:

(1.4)

Взяв в качестве приближенного решения k-еприближение корня: , запишем (1.4) с учетом обозначения — сk в виде:

(1.5)

Из (1.2) следует, что (1.5) выполнено, если

(1.6)

Таким образом, итерационный процесс нужно продолжать до тех пор, пока не будет выполнено условие (1.6).

Метод деления отрезка пополам проиллюстрирован на рис. 1.1. Пусть для определенности F(a) 0. В качестве начального приближения корня примем с0 = (а + b)/2. Поскольку в рассматриваемом случае F(c0) 0 и F(b) > 0. Таким образом, с[с0, c1],а2=с0, b2 = с1. Аналогично находим другие приближения: с2=(с0+c1)/2и т.д. до выполнения условия (1.6).

Рис. 1.1. Метод деления отрезка пополам

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

Однако метод деления отрезка пополам довольно медленный. Вычислим число итераций N, требуемое для достижения точности ε. Для этого выясним, пользуясь (1.3), для каких kвыполнено условие (1.6), и возьмем в качестве N наименьшее из таких k. Окончательно получим

(1.7)

где Е(х) – целая часть числа х. Обычно для метода деления отрезка пополам N больше, чем для некоторых других методов, что не является препятствием к применению этого метода, если каждое вычисление значения функции F(x) несложно.

Итерационный процесс можно завершать и тогда, когда значение функции F(x) после k-й итерации станет меньшим по модулю ε, т.е.

(1.8)

Такое условие окончания итераций аналогично условию (2.24). Действительно, для уравнения (1.1) величина F(ck)есть невязка(см. разд. 2.2.2),полученная на k—йитерации.

На рис. 1.2 представлен алгоритм итерационного процесса нахождения корня уравнения (1.1) методом деления отрезка пополам. Здесь сужение отрезка осуществляется заменой границ а или bна текущее значение корня с. При этом значение F(a) вычисляют лишь один раз, поскольку нам нужен только знак функции F(x) на левой границе, а он в процессе итераций не меняется.

Рис. 1.2. Алгоритм метода деления отрезка пополам

Источник