Darbe.ru

Быт техника Дарби
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Постановка задачи. Пусть дана некоторая функция 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.

Для определённости пусть f(x)<0, f(b)>0. Разделим отрезок в отношении

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

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

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

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

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

Процесс вычисления заканчивается когда разность между 2-мя значениями корня <e или |f(xn+1)|<e. Графическая интерпретация показана на рис.

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

Блок-схема

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

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

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

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

│f(x)│< q < 1 (f(x) – производная функции F(x)) во всех точках

интервала изоляции [а;b] — это необходимое условие сходимости процесса.

Преобразование исходного уравнения к виду х=F(x) можно осуществить многими методами . Например , выделить х из исходного уравнения , а остальное перевести в правую часть .Вычисления заканчиваются когда

Читайте так же:
Можно ли заряжать чехол airpods без наушников

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

1) Заменяем уравнения f(x)=0 выражением x=φ(x)

2) Находим х1= φ(xо).

3) Проверяем |x1-xo|<=e, если выполняется условие , х1-корень, если нет ,продолжаем : х2= φ(x1)

Условие , при котором данный процесс сходится , определяется следующей теоремой: если интервал [a,b] является интервалом изоляции корня уравнения

x = φ(x­) , и во всех точках этого интервала производная φ’(x­) удовлетворяет условию :

то итерационный процесс сходиться.

В случае , если по условию | xn+1 — xn | <=e невозможно найти корень , то заданную точность вычислений необходимо найти из выражения , где q- наименьшее значение |φ’(x­)| на отрезке [a,b].

Таким образом начальное приближение выбирается из соображений |φ’(xо­)|<1.

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

· Скорость сходимости – большая.
· Необходимо преобразовывать уравнение f(x)=0 к виду x=φ(x), что не всегда возможно..

Блок-схема

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

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

Метод Ньютона используется для решения нелинейных уравнений. Метод основан на последовательном приближении к корню уравнения при заданных начальных условиях: начальное приближение и точность вычисления. В методе Ньютона осуществляется экстерполяция с помощью касательной к кривой в данной точке. В основе метода лежит разложение функции по формуле Тейлора. Члены, содержащие h во второй и более высоких степенях, отбрасываются. Для нахождения корня используется соотношение xn+1 = xn + h. Предполагается, что переход от xn к xn+1 приближает значение функции к нулю.

Геометрически метод Ньютона эквивалентен замене небольшой дуги y=f(x) касательной, проведенной в некоторой точке кривой.

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

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

Пусть задан некий отрезок [ a , b ], на котором находится один корень уравнения. Найдём середину отрезка и определим, в какой части отрезка – левой или правой – находится корень уравнения. Именно эта половина отрезка будет взята в качестве следующего приближения. Таким образом, будем уменьшать длину отрезка, пока она не станет меньше ε. В качестве корня берётся середина отрезка, и, таким образом, корень уравнения находится с точностью ε / 2. Рис. 2 иллюстрирует метод деления отрезка пополам.

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

Для того чтобы определить в какой части отрезка находится корень уравнения, надо сравнить знаки f ( a ) и f ( x ). Если знаки не совпадают, значит на отрезке [ a , x ] функция пересекает ось x , и корень уравнения находится на этом отрезке. В этом случае необходимо правую границу отрезка перенести в точку x (см. рис. 2-а). Если знаки совпадают, значит на отрезке [ a , x ] функция не пересекает ось x , и корень уравнения находится на отрезке [ x , b ]. В этом случае необходимо левую границу отрезка перенести в точку x (см. рис. 2-б).

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

Формальное описание метода деления отрезка пополам
while <длина отрезка больше точности> do begin <найти середину отрезка x> if <знаки f ( a ) и f ( x ) не совпадают> then <перенести правую границу в точку x > else <перенести левую границу в точку x > end;

Читайте так же:
Макрос цикла в excel

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

Приведём уравнение f(x) = 0 при помощи некоторых тождественных преобразований к виду x = φ(x). Такое преобразование можно произвести разными способами, и при этом будут получаться разные функции φ(x) в правой части уравнения. Уравнение f(x) = 0 эквивалентно уравнению x = λ(x)∙f(x) при любой функции λ(x) ≠ 0. Таким образом, можно взять φ(x) = λ(x)∙f(x) и при этом выбрать функцию λ(x) ≠ 0 так, чтобы функция φ(x) удовлетворяла тем свойствам, которые понадобятся нам для обеспечения нахождения корня уравнения. В простейшем случае в качестве λ(x) выбирается неравная 0 постоянная. Этот вариант удобен с точки зрения задания в программе функции λ(x) и, в то же время, позволяет подобрать такое значение постоянной, которое обеспечит быстрое и точное нахождение корня уравнения.

Для нахождения корня уравнения x = φ(x) выберем какое-либо начальное приближение x (расположенное, по возможности, близко к корню x * ). Далее будем вычислять последующие приближения x1, x2, …, xi, xi + 1, … по формуле xi + 1 = φ(xi).

Заметим следующее: тот факт, что x * – корень уравнения x = φ(x), означает, что x * есть абсцисса точки пересечения графика y = φ(x) с прямой y = x. Если при каком-либо xi вычислено значение xi + 1 = φ(xi) и взято в качестве нового аргумента функции, то это означает, что через точку графика (xi, φ(xi)) проводится горизонталь до прямой y = x, а оттуда опускается перпендикуляр на ось x. Там и будет находиться новый аргумент xi + 1.

Для метода простых итераций необходимо одно начальное приближение, в качестве которого можно взять середину отрезка [a, b]. Процесс вычисления прекращается, когда разность между двумя текущими приближениями становится меньше точности, т.е. когда выполняется условие |xi + 1xi| < ε, где ε – заданная точность вычисления. Рис. 2 иллюстрирует метод простых итераций.

Рис. 3. Метод простых итераций

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

Формальное описание метода простых итераций
repeat <сохраняем старое приближение> <вычисляем новое приближение> until <разность между двумя текущими приближениями меньше точности>; x 1 и x 2, в качестве которых берутся границы исходного отрезка [ a , b ]. Используя эти два приближения, находим третье приближение x 3 как точку пересечения прямой, проведенной между точками ( x 1, f ( x 1)) и ( x 2, f ( x 2)), с осью x по следующей формуле:
или

После этого самая старая точка x 1 отбрасывается, и в качестве следующих приближений берутся точки x 2 и x 3 по следующему правилу: x 1 = x 2, x 2 = x 3. После чего снова вычисляется следующее приближение по приведённой выше формуле. Процесс вычисления прекращается, когда разность между двумя текущими приближениями становится меньше точности, т.е. когда выполняется условие | x 1 – x 2| < ε. Рис. 3 иллюстрирует метод секущих.

Рис. 3. Метод секущих

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

Читайте так же:
Как в фотошопе написать текст под наклоном

Формальное описание метода секущих

repeat <вычислить очередное приближение на основе первых двух> <отбросить самое старое приближение> until <разность между двумя текущими приближениями меньше точности>; —>

3. Использование итерационных циклов в методах поиска корней уравнения

Мы видим, что в алгоритмах поиска корней уравнения так же, как и при нахождении суммы ряда, невозможно заранее определить, сколько итераций потребуется для нахождения корня. Это зависит от заданных начальных приближений, от точности и, конечно, от самой функции. Поэтому мы снова должны использовать циклы с неизвестным количеством повторов тела цикла. В описании метода деления отрезка пополам использовался цикл «пока», а в описании метода секущих – цикл «до». Однако это не является жёстким правилом, в любом методе можно использовать любой цикл. Главное, надо помнить, что цикл «пока» продолжается при истинности условия, а цикл «до» завершается при истинности условия. Поэтому при замене одного цикла на другой необходимо также поменять условие на противоположное.

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

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

Всем привет!
Дали такую задачу: методом деления отрезка пополам найти с точностью EPS=0,0001 корень уравнения cos(2/x)-2*sin(1/x)+1/x=0.

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

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

Цитата(Alexey91 @ 31.3.2009, 18:07 )
метод деления отрезка пополам,

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(Alexey91 @ 31.3.2009, 18:07 )
метод деления отрезка пополам

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(Alexey91 @ 31.3.2009, 17:07 )
Не понимаю в чем заключается метод деления отрезка пополам

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(mes @ 31.3.2009, 20:17 )
Не понимаю, какое отношение вопрос по алгоритмам имеет к разделу "общие вопросы по C++"?

Вы торопитесь. Дальше нужно будет реализовать данный алгоритм на С++, я полагаю. У автора реальные проблемы: с чего начать и он начал с понимания задачи, что правильно.

Alexey91, если сами писать не хотите — идите в центр помощи.

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(Anikmar @ 31.3.2009, 19:21 )
Вы торопитесь. smile Дальше нужно будет реализовать данный алгоритм на С++, я полагаю. У автора реальные проблемы: с чего начать и он начал с понимания задачи, что правильно. smile

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

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

Код
#include <stdio.h>
#include <math.h>
#include <conio.h>

Вот, только мне сказали, что надо еще рекурсию сделать, как это можно оформить?

Профиль
Группа: Участник
Сообщений: 274
Регистрация: 25.11.2006

Репутация: 13
Всего: 15

Цитата(Alexey91 @ 3.4.2009, 07:22 )
while(fabs(b-a > e) && f©!= 0)

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

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

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

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

Уравнение имеет вид: x 3 — 9x 2 + 20x – 11=0

Отрезок, на котором осуществляется поиск корня: [0; 1]

Блок-схема алгоритма поиска корня уравнения методом половинного деления (дихотомии)

Разработаем алгоритм программы поика решения уравнения на заданном отрезке в виде блок-схемы:

блок-схема алгоритма метод половинного деления

Текст программы решения задачи на С++

В среде программирования Borland C++ 7.0 вводим текст программы на Си ++:

#include <conio.h>
#include <math.h>
// функция для вычисления f(х)
float f(float z)
<
return pow(z,3)+6*pow(z,2)+6*z-7;//возвращаемое значение
>

x=(a+b)/2;// вычисление х после завершения цикла
printf(«x=%f F(x)=%f |a-b|=%f»,x,f(x),fabs(a-b)); // вывод результатов
getch();
>

Нажимаем клавиши CTRL+F9 для компиляции и запуска на выполнение программы. Получаем корень уравнения x≈0,834 :

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

Программа начинается с директив препроцессора, начинающихся с символа #, которые дают указание препроцессору подключить к программе заголовочные файлы с описанием тех или иных библиотечных функций. В данном случае подключается заголовочный файл stdio.h с описанием функций ввода-вывода, заголовочный файл math.h с описанием математических функций и заголовочный файл conio.h с описанием функции ожидания нажатия клавиши getch().

Программа состоит из двух функций: пользовательской функции f(x) и обязательной функции main(). Функция main() не возвращает никаких значений и поэтому она объявляется с ключевым словом void. В отличие от функции main(), функция f(x) возвращает вещественное значение и объявляется с ключевым словом float. Тела функций являются блоками и поэтому ограничены фигурными скобками.

В теле функции main() объявляются вещественные переменные a, b, e, х.
Далее используется оператор цикла while, в котором применяются условные операторы:
if (выражение) оператор 1; else оператор 2; которые позволяют проверить разные ли знаки у концов отрезка.
Использование вышеуказанной библиотечной функции printf() дает возможность вывести на стандартное устройство вывода (монитор) сообщение об отсутствии корней или сообщение с значением корня, значением функции в этой точке и модуль разности концов отрезка.
Тело функции main() зак¬рывается фигурной скобкой. На этом программа заканчивается.

Задания

Решите уравнение указанным в варианте методом. Функцию передать как параметр с помощью указателя.

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

Довольно часто на практике приходится решать уравнения вида:

F(x)=0( 2)

где функция F(x)определена и непрерывна на некотором конечном или бесконечном интервале

alpha < x < beta

Всякое значение overline<x data-lazy-src=

x=f(x)( 2)

Это уравнение получается выделением xиз уравнения F(x)и переносом того, что осталось, т.е. f(x), в левую часть уравнения. Иначе можно получить уравнение (2) следующим способом: левую и правую часть уравнения (1) умножить на произвольную константу lambdaи прибавить к левой и правой части x, т.е. получаем уравнение вида:

x=x+lambda F(x)( 3)

где f(x)=x+lambda F(x).

На заданном отрезке [a; b]выберем точку х_0– нулевое приближение – и найдем

x_1=f(x_0),

x_2=f(x_1),

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

x_n=f(x_<n-1 data-lazy-src=

|f

lim_<nrightarrowinfty data-lazy-src=

Выберем на отрезке [a; b]произвольную точку х_0– нулевое приближение. Затем найдем:

x_1=x_0-frac<F(x_0) data-lazy-src=

x_2=x_1-frac<F(x_1) data-lazy-src=

Таким образом, процесс нахождения корня уравнения сводится к вычислению чисел x_nпо формуле:

x_n=x_<n-1 data-lazy-src=

Этот процесс называется методом Ньютона.

Процесс вычисления продолжается до тех пор, пока не будет выполнено условие:

|x_n-x_<n-1 data-lazy-src=

Точку х_0необходимо выбирать так, чтобы выполнялось условие:

F(x_0)dot F

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

Пусть уравнение F(x_0)имеет один корень на отрезке [a, b]. Функция непрерывна на отрезке [a, b].

Метод половинного деления заключается в следующем:

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

x_0=(a+b)/2.

Если F(x_0)=0, то x_0является корнем уравнения. Если F(x_0)neq 0,то выбираем тот из отрезков, на концах которого функция имеет противоположные знаки. Полученный отрезок снова делим пополам и выполняем действия сначала и т.д.

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

|x_n-x_<n-1 data-lazy-src=

голоса
Рейтинг статьи
Ссылка на основную публикацию
Adblock
detector