Решение квадратного уравнения методом половинного деления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) Если d>0, то теперь точкой a станет c: a=c; Если d ?, то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;

Видео:Метод половинного деления решение нелинейного уравненияСкачать

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

Метод половинного деления

Считаем, что отделение корней уравнения f ( x) = 0 проведено и на отрезке [ a, b] расположен один корень, который необходимо уточнить с погрешностью ε. В качестве начального приближения корня принимаем середину этого отрезка: c0 = (a + b) / 2 (рис. 4):

Решение квадратного уравнения методом половинного деления

Рис. 4. Метод половинного деления.

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

Решение квадратного уравнения методом половинного деления

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

Решение квадратного уравнения методом половинного деления

Прекратить итерационный процесс следует, когда будет достигнута заданная точность, т.е. при выполнении условия |x0 – ck|

Дата добавления: 2017-09-19 ; просмотров: 3744 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Видео:Метод половинного деления. ДихотомияСкачать

Метод половинного деления. Дихотомия

1 Численный метод решения нелинейных уравнений

Видео:Решение нелинейного уравнения методом половинного деления (программа)Скачать

Решение нелинейного уравнения методом половинного деления (программа)

1.1 Область локализации корней

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

Например , для уравнения Решение квадратного уравнения методом половинного деления выполним преобразование и приведем его к виду f(x)= 0 т.е. Решение квадратного уравнения методом половинного деления . График этой функции представлен на рисунке 1. Очевидно, что данное уравнение имеет два действительных корня – один на отрезке [-1, 0] , а второй – [1, 2].

Решение квадратного уравнения методом половинного деления

Рисунок 1. График функции Решение квадратного уравнения методом половинного деления

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

Некоторые виды уравнений допускают аналитическое решение. Например, степенные алгебраические уравнения степени n Решение квадратного уравнения методом половинного деления при n ≤ 4. Однако, в общем виде, аналитическое решение, как правило, отсутствует. В этом случае, применяются численные методы. Все численные методы решения уравнений представляют собой итерационные алгоритмы последовательного приближения к корню уравнения. То есть, выбирается начальное приближение к корню x 0 и затем с помощью итерационной формулы генерируется последовательность x 1, x 2, …, xk сходящаяся к корню уравнения Решение квадратного уравнения методом половинного деления .

Видео:Метод половинного деления - ВизуализацияСкачать

Метод половинного деления - Визуализация

1.2 Критерии сходимости при решении уравнений

Ø Абсолютная погрешность — абсолютное изменение приближения на соседних шагах итерации Решение квадратного уравнения методом половинного деления

Ø Относительная погрешность — относительное изменение приближения на соседних шагах итерации Решение квадратного уравнения методом половинного деления

Ø Близость к нулю вычисленного значения левой части уравнения (иногда это значение называют невязкой уравнения, так как для корня невязка равна нулю) Решение квадратного уравнения методом половинного деления

Видео:12й класс; Информатика; "Численные методы. Метод половинного деления"Скачать

12й класс; Информатика; "Численные методы. Метод половинного деления"

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

Метод половинного деления основан на последовательном делении отрезка локализации корня пополам.

Для этого выбирается начальное приближение к отрезку [ a , b ], такое, что f ( a ) × f ( b ) Решение квадратного уравнения методом половинного деления — середине отрезка [ a , b ]. Если он противоположен знаку функции в точке a, то корень локализован на отрезке [ a , c ], если же нет – то на отрезке [ c , b ]. Схема метода дихотомии приведен на рис у нке 2.

Решение квадратного уравнения методом половинного деления

Рисунок 2. Последовательное деление отрезка пополам и приближение к корню Решение квадратного уравнения методом половинного деления

Алгоритм метода дихотомии можно записать так:

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

2. выбрать a, b и вычислить Решение квадратного уравнения методом половинного деления

3. если f(a) × f( с ) то a=a; b = c иначе a = c; b=b

4. если критерий сходимости не выполнен, то перейти к п. 2

Видео:Метод половинного деленияСкачать

Метод половинного деления

Пример решения уравнения методом дихотомии

Найти решение заданного уравнения методом дихотомии с точностью до 10 -5 .

Пример создания расчетной схемы на основе метода дихотомии на примере уравнения: Решение квадратного уравнения методом половинного деленияна отрезке [1, 2]

Данный метод заключается в проверке на каждой итерации условия:

если f ( a ) × f (с) Решение квадратного уравнения методом половинного деления и выбор соответствующего отрезка для следующей итерации.

Решение квадратного уравнения методом половинного деления

Решение квадратного уравнения методом половинного деления

Рисунок 3. Последовательность итераций метода дихотомии при поиске корня уравнения Решение квадратного уравнения методом половинного деленияна отрезке [1, 2]

a ) схема расчета (зависимые ячейки); b) режим отображения формул;

Для нашего примера итерационная последовательность для нахождения решения принимает вид:

Решение квадратного уравнения методом половинного деления

Точность до пятой значащей цифры достигается за 20 итераций.

Скорость сходимости этого метода является линейной.

При выполнении начального условия он сходится к решению всегда.

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

Видео:14 Метод половинного деления Ручной счет Численные методы решения нелинейного уравненияСкачать

14 Метод половинного деления Ручной счет Численные методы решения нелинейного уравнения

2 Решение уравнений , используя “Подбор параметра ”

Используя возможности Excel можно находить корни нелинейного уравнения вида f(x)=0 в допустимой области определения переменной. Последовательность операций нахождения корней следующая:

1. Производится табулирование функции в диапазоне вероятного существования корней;

2. По таблице фиксируются ближайшие приближения к значениям корней;

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

При подборе параметра Excel использует итерационный (циклический) процесс. Количество итераций и точность устанавливаются в меню Сервис/Параметры/вкладка Вычисления. Если Excel выполняет сложную задачу подбора параметра, можно нажать кнопку Пауза в окне диалога Результат подбора параметра и прервать вычисление, а затем нажать кнопку Шаг, чтобы выполнить очередную итерацию и просмотреть результат. При решении задачи в пошаговом режиме появляется кнопка П родолжить — для возврата в обычный режим подбора параметра.

Видео:Урок 10. C++ Метод половинного деленияСкачать

Урок 10.  C++ Метод половинного деления

2.1 Пример решения уравнения, используя “Подбор параметра”

Например , найдем все корни уравнения 2x 3 -15sin(x)+0,5x-5=0 на отрезке [-3 ; 3].

Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3; 3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня.

Решение квадратного уравнения методом половинного деления

Решение квадратного уравнения методом половинного деления

Рисунок 4. Поиск приближенных значений корней уравнения

Выполните команду меню Сервис/Параметры, во вкладке Вычисления установите относительную погрешность вычислений E=0,00001, а число итераций N=1000, установите флажок Итерации.

Выполните команду меню Сервис/Подбор параметра. В диалоговом окне (рисунок 9) заполните следующие поля:

þ Установить в ячейке : в поле указывается адрес ячейки, в которой записана формула правой части функции;

þ Значение : в поле указывается значение, которое должен получить полином в результате вычислений, т.е. правая часть уравнения (в нашем случае 0);

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

Решение квадратного уравнения методом половинного деления

Рисунок 5. Диалоговое окно Подбор параметра для поиска первого корня

После щелчка на ОК получим значение первого корня -1,65793685 .

Выполняя последовательно операции аналогичные предыдущим, вычислим значения остальных корней: -0,35913476 и 2,05170101 .

Видео:8 Метод половинного деления Calc Excel Численные методы решения нелинейного уравненияСкачать

8 Метод половинного деления Calc Excel Численные методы решения нелинейного уравнения

3 Решение уравнений и систем уравнений, используя надстройку “Поиск решения”

Для решения уравнений можно также использовать команду Поиск решения, доступ к которой реализуется через пункт меню Сервис/Поиск решения.

Последовательность операций нахождения корней следующая:

1. Найти приближенное значение корня уравнения

2. Открыть диалог Поиск решения и установить следующие параметры (рисунок 10):

þ в поле У становить целевую ячейку ввести адрес ячейки, содержащей формулу (левую часть уравнения);

þ установить переключатель в положение ‘ значению’ и ввести значение 0 (правая часть уравнения);

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

þ в поле Ограничения с помощью кнопки Д обавить ввести все ограничения, которым должен отвечать результат поиска (область поиска корня уравнения);

þ для запуска процесса поиска решения нажать кнопку В ыполнить.

þ Для сохранения полученного решения необходимо использовать переключатель С охранить найденное решение в открывшемся окне диалога Результаты поиска решения.

Решение квадратного уравнения методом половинного деления

Рисунок 6. Диалоговое окно Поиск решения

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

Рассмотрим некоторые Опции, управляющие работой Поиска решения, задаваемые в окне Параметры (окно появляется, если нажать на кнопку Параметры окна Поиск решения):

þ Максимальное время — ограничивает время, отведенное на процесс поиска решения (по умолчанию задано 100 секунд, что достаточно для задач, имеющих около 10 ограничений, если задача большой размерности, то время необходимо увеличить).

þ Относительная погрешность — задает точность, с которой определяется соответствие ячейки целевому значению или приближение к указанным ограничениям (десятичная дробь от 0 до 1).

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

þ Показывать результаты итераций — этот флажок позволяет включить пошаговый процесс поиска, показывая на экране результаты каждой итерации.

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

Решение квадратного уравнения методом половинного деления

Рисунок 7. Вкладка Параметры окна Поиск решения

Видео:Решение уравнений (метод дихотомии) на C#Скачать

Решение уравнений (метод дихотомии) на C#

3.1 Пример решения уравнения, используя надстройку “Поиск решения”

Например , найдем все корни уравнения 2x 3 -15sin(x)+0,5x-5=0 на отрезке [-3 ; 3]. Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3;3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня. На рисунке 12 представлен пример заполнения окна Поиск решения для нахождения первого корня на отрезке [-2; -1].

Решение квадратного уравнения методом половинного деления

Рисунок 8. Пример решения уравнения при помощи надстройки Поиск решения

Видео:7 Метод половинного деления Mathcad Численные методы решения нелинейного уравненияСкачать

7 Метод половинного деления Mathcad Численные методы решения нелинейного уравнения

Задание 1. Решение уравнений численным методом

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

Видео:Отделение корней уравнений аналитическим методом. Уточнение корней методом половинного деленияСкачать

Отделение корней уравнений аналитическим методом. Уточнение корней методом половинного деления

Задания 2. Решение уравнений встроенными средствами “Подбор параметра” и “Поиск решения”

На листе 2 (название листа: Подбор Поиск) для заданного уравнения вида f(x)=0 (Таблица 1. Индивидуальные задания) на заданном интервале и с некоторым шагом (шаг выбрать самостоятельно) построить таблицу значений функции f(x) и определить количество корней уравнения и выделить интервалы, на которых находятся корни. Построить график функции. Уточнить на заданных интервалах с точностью до 10 -6 корни уравнения с помощью встроенных средств: Подбор параметра, Поиск решения

📹 Видео

6 Метод половинного деления C++ Численные методы решения нелинейного уравненияСкачать

6 Метод половинного деления C++ Численные методы решения нелинейного уравнения

Численные методы решения нелинейного уравнени Теория Шаговый Метод половинного деления Метод НьютонаСкачать

Численные методы решения нелинейного уравнени Теория Шаговый Метод половинного деления Метод Ньютона

Численное решение уравнений, урок 2/5. Метод деления отрезка пополамСкачать

Численное решение уравнений, урок 2/5. Метод деления отрезка пополам

Формула корней квадратного уравнения. Алгебра, 8 классСкачать

Формула корней квадратного уравнения. Алгебра, 8 класс

5 способов решения квадратного уравнения ➜ Как решать квадратные уравнения?Скачать

5 способов решения квадратного уравнения ➜ Как решать квадратные уравнения?

Метод переброски в квадратных уравнениях. ЕГЭ и ОГЭ 2022 по математикеСкачать

Метод переброски в квадратных уравнениях. ЕГЭ и ОГЭ 2022 по математике

Быстрый способ решения квадратного уравненияСкачать

Быстрый способ решения квадратного уравнения

Решение квадратных уравнений. Дискриминант. 8 класс.Скачать

Решение квадратных уравнений. Дискриминант. 8 класс.
Поделиться или сохранить к себе: