Remkomplekty.ru

IT Новости из мира ПК
17 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Метод дихотомии паскаль

Метод дихотомии паскаль

‘ width=’8′ height=’8’ /> Внимание! Действует предмодерация

Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.

Группа: Пользователи
Сообщений: 7

Репутация:

Уникальный

Группа: Пользователи
Сообщений: 64
Пол: Мужской

Репутация: 2

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

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

var
x:real;
a:array [1..2, 1..255] of real;
b:boolean;
i,n:byte;
y1,y2,dr,md,maxx,maxy,maxx2,maxy2:integer;

procedure search(a,b:real; var x:real);
const e=0.0001; < e - Точность >
begin
repeat
x:=(a+b)/2;
if f(a)*f(x)>0 then a:=x else b:=x;
until abs(f(x)) 0 then b:=true;

repeat
if b=true then begin
if f(x) 0;

if b=false then begin
if f(x)>0 then begin
n:=n+1;
a[2,n]:=x;

repeat
x:=x-0.1;
until f(x) d2;

if n=0 then writeln(‘Корней нет . ‘)
else begin
writeln(‘В уравнении F(x) на отрезке [‘,d1,’,’,d2,’] найдено ‘,
n,’ корн(-ей/-я/-ь)’);
for i:=1 to n do begin
search(a[1,i],a[2,i],x);
writeln(‘X’,i,’ = ‘,x:5:3);
end;
end;

writeln(‘Нажмите клавишу «Enter» для построения’);
readln;
dr:=9;
md:=2;
initgraph(dr,md,’c:bpbgi’);
setcolor(12);

maxx:=getmaxx;
maxy:=getmaxy;
maxx2:=maxx div 2;
maxy2:=maxy div 2;

<ось OY>
line(maxx2,0,maxx2,maxy);
line((maxx2)-4,10,maxx2,0);
line((maxx2)+4,10,maxx2,0);
line((maxx2)+10,5,maxx2+14,9);
line((maxx2)+14,9,maxx2+18,5);
line((maxx2)+14,9,maxx2+14,14);
<ось OX>
line(0,maxy2,maxx,maxy2);
line(maxx-10,maxy2-4,maxx,maxy2);
line(maxx-10,maxy2+4,maxx,maxy2);
line(maxx-15,maxy2-12,maxx-7,maxy2-20);
line(maxx-15,maxy2-20,maxx-7,maxy2-12);

<График уравнения>
x:=d1;
setcolor(15);
repeat
y1:=maxy2-round(f(x-1));
y2:=maxy2-round(f(x));
if (y1>0) and (y1 0) and (y2 d2;
readln;
closegraph;
end.

Эскизы прикрепленных изображений

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

Материал из MachineLearning.

Содержание

Введение

Существует довольно очевидная теорема: «Если непрерывная функция на концах некоторого интервала имеет значения разных знаков, то внутри этого интервала у нее есть корень (как минимум, один, но м.б. и несколько)». На базе этой теоремы построено численное нахождение приближенного значения корня функции. Обобщенно этот метод называется дихотомией, т.е. делением отрезка на две части. Обобщенный алгоритм выглядит так:

  1. Задать начальный интервал ;
  2. Убедиться, что на концах функция имеет разный знак;
  3. Повторять
    • выбрать внутри интервала точку ;
    • сравнить знак функции в точке со знаком функции в одном из концов;
      • если совпадает, то переместить этот конец интервала в точку ,
      • иначе переместить в точку другой конец интервала;

пока не будет достигнута нужная точность.

Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд.

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

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

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

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

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

Метод половинного деления как метод поиска корней функции

Изложение метода

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

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

Пусть функция непрерывна на отрезке ,

и — единственный корень уравнения .

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

Поделим отрезок пополам. Получим точку и два отрезка .

  • Если , то корень найден ( ).
  • Если нет, то из двух полученных отрезков и надо выбрать один такой, что , то есть
    • , если или
    • , если .

Новый отрезок делим пополам. Получаем середину этого отрезка и так далее.

Для того, чтобы найти приближённое значение корня с точностью до 0″ alt= » eps >0″ />, необходимо остановить процесс половинного деления на таком шаге , на котором

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

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

Дана функция . Необходимо найти , доставляющий минимум (или максимум) функции на интервале с заданной точностью , т.е. найти

Запишем словесный алгоритм метода.

  1. На каждом шаге процесса поиска делим отрезок пополам, — координата середины отрезка .
  2. Вычисляем значение функции в окрестности вычисленной точки , т.е.
    .
  3. Сравниваем и и отбрасываем одну из половинок отрезка (рис. 1).
    • При поиске минимума:
      • Если , то отбрасываем отрезок , тогда . (рис. 1.а)
      • Иначе отбрасываем отрезок , тогда . (рис. 1.б)
    • При поиске максимума:
      • Если , то отбрасываем отрезок , тогда .
      • Иначе отбрасываем отрезок , тогда .
  4. Деление отрезка продолжается, пока его длина не станет меньше заданной точности , т.е. .
Читать еще:  Произведение элементов массива паскаль

Схема алгоритма метода представлена на рис 2.

При выводе – координата точки, в которой функция имеет минимум (или максимум), – значение функции в этой точке.

Метод хорд

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

Изложение метода

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

При этом в процессе поиска семейство хорд может строиться:

  1. при фиксированном левом конце хорд, т.е. , тогда начальная точка (рис. 3а);
  2. при фиксированном правом конце хорд, т.е. , тогда начальная точка (рис. 3б);

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

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

Метод обеспечивает быструю сходимость, если 0″ alt= «f(z)cdot f»(z) > 0″ />, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.

Схема алгоритма уточнения корня методом хорд представлена на рис. 4.

Комбинация метода хорд и метода половинного деления

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

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

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

Поэтому лучше использовать в качестве точки деления что-то среднее: если метод половинного деления предлагает использовать , а метод хорд — , то возьмем . Коэффициент .

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

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

Метод дихотомии паскаль

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

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

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

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

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

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

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

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

// главная функция
void main()
<
float a=-3.0, b=2.0, e=0.001, x;// объявление переменных
while (fabs(a-b)>=e) // цикл
<
// проверка на разные знаки по концам отрезка
if((f(a)>0&&f((a+b)/2) 0))
b=(a+b)/2;
else
if ((f((a+b)/2)>0&&f(b) 0))
a=(a+b)/2;
else
<
printf(«! Net kornej !»);
return;
getch();
>
>

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() зак¬рывается фигурной скобкой. На этом программа заканчивается.

X Международная студенческая научная конференция Студенческий научный форум — 2018

ОТДЕЛЕНИЯ КОРНЕЙ. УТОЧНЕНИЕ КОРНЕЙ МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ (МЕТОД ДИХОТОМИИ)

Предположим теперь, что найден отрезок [a, b] такой, что

функцияF(x) непрерывна на отрезке [a, b] вместе с производной первого порядка;

значения F(x) на концах отрезка имеют разные знаки (F(a)F(b) . lgx = 1. (3)

Решение. Уравнение (3) перепишем в виде равенства lg x=.

Отсюда ясно, что корни уравнения (3) могут быть найдены как абсциссы точек пересечения логарифмической кривой y = lg x и гиперболы y = . Построив эти кривые (см. рис. 1), приближенно найдем единственный корень уравнения (3) или определим его содержащий отрезок [2, 3].

Рис. 1 – Графическое отделение корней (пример 1)

Убедимся, что отрезок [2, 3] содержит один и только один корень уравнения (3).

Перепишем уравнение в виде F(x) = 0, где .

Тогда F(2) = 2 . lg(2) – 1 = 2 . 0.30103 – 1 = 0.60206 – 1 = – 0.39794 0, т.е. на концах отрезка функция F(x) принимает значения разных знаков.

Найдем первую производную функции:

Следовательно, первая производная сохраняют свой знак на отрезке, а на концах отрезка функция F(x) принимает значения разных знаков, значит отрезок [2, 3] – отрезок изоляции искомого корня ξ.

Другим, не менее распространенным методом отделения корней является метод производных. Этот метод основан на том, что между любыми двумя нулями функции содержится, по крайней мере, один нуль ее производной. Отсюда следует, что нули функции естественно искать на интервалах, порождаемых нулями производной. Метод заключается в том, что ищут и приравнивают к нулю производную функции F'(х), а затем на отрезках определяют знак функции F(х), где хi корни уравнения F'(х)= 0. Таким образом, всю числовую ось разбивают на интервалы. Отметим, что описанный метод называют еще методом экстремумов функции.

Пример 2. Отделить методом производных корни уравнения:

Решение. Найдем производную F'(х) и приравняем ее нулю.

Составим приблизительную схему знаков функции F(х):

Следовательно, уравнение (4) имеет три действительных корня, лежащих в интервалах (– ∞, –2), (–2, 0) и (0, + ∞). Возьмем для пробы три дополнительные точки х = – 3, х = – 1, х = 1 и составим следующую схему знаков F(x):

Если исследуемая функция есть полином n-й степени, то используют метод удаления корней: определяют один корень, и функцию F(х) представляют в виде F(х)= g1(х) . (хх1), где x1 первый найденный корень, а g1(х)– полином степени (n – 1).Затем проверяют, является ли х1корнем полинома g1(x). Если корень имеет кратность, большую единицы, то записывают многочлен в виде F(х)= g2(х) . (хх1) 2 . После конечного числа шагов получают представление F(х)= (хх1) k gk(х) и переходят к определению следующего корня при помощи gk(х). В результате получают представление

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

На практике предполагаемые корни уточняют различными специальными вычислительными методами. Одним из них является метод дихотомии (бисекции, половинного деления), относящийся к итерационным. Он состоит в построении последовательности вложенных отрезков, на концах которых F(х) имеет разные знаки. Каждый последующий отрезок получают делением пополам предыдущего. Этот процесс построения последовательности вложенных отрезков позволяет найти нуль функции (F(х) = 0)с любой заданной точностью.

Опишем подробно один шаг итерации. Пусть на k-м шаге найден отрезок [аk , bk], на концах которого F(х) имеет разные знаки. Заметим, что обязательно [аk, bk] [а, b]. Разделим теперь отрезок [аk, bk]пополам и вычислим F(с), где с середина [аk , bk], т.е. . Здесь возможны два случая: первый, когда F(с) = 0, тогда мы говорим, что искомый корень найден и ξ = с; второй, когда F(с)  0, тогда сравниваем знак F(с) с F(аk) и F(bk) и из двух половин [аk, с] и [с,bk] выбираем ту, на концах которой функция меняет свой знак. Таким образом, bk = с, если F(с) . F(аk) . F(bk) . , тогда координата середины последнего найденного отрезка и есть значение корня требуемой точности.

Читать еще:  Оператор выбора паскаль примеры

Метод дихотомии – простой и надежный метод поиска простого корня уравнения F(х) = 0. Он сходится для любых непрерывных функций F(х), в том числе и недифференцируемых.

проблема определения отрезка, на котором функция меняет свой знак (как правило, это отдельная вычислительная задача, наиболее сложная и трудоемкая часть решения);

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

не применим к корням четной кратности;

для корней нечетной, но высокой кратности метод неустойчив, дает большие ошибки;

медленно сходится. Для достижения ε необходимо выполнить итераций, т.е. для получения 3 верных цифр (ε = 0.0005) надо выполнить около 10 итераций, если первоначальный отрезок имеет единичную длину.

Программа, по которой можно уточнить корни методом дихотомии, построена по алгоритму, приведенному ниже (см. рис. 2).

Рис. 2 Блок-схема метода дихотомии

Пример 3. Отделить корни уравнения x 2 5 . sin x = 0 и уточнить их с точностью ε = 0.00005 методом дихотомии.

Решение. Первый этап – графическое отделение корней. Графическим методом (см. рис. 3) находится отрезок, на котором расположен один из корней данного уравнения [1.8; 2.2]; (второй корень тривиальный, х = 0 находится легко).

Рис. 3 Графическое отделение корней (пример 3)

Второй этап – уточнение отделенного корня методом дихотомии до заданной точности ε. Для того чтобы уточнить корень, изолированный на отрезке [1.8; 2.2], с указанной точностью используем процедуру bisect.

Формальные параметры процедуры BISECT. Входные:A, B (тип real) – определяют длину отрезка; EPS (тип real) – определяет заданную точность вычислений; IT (тип integer) – определяет наибольшее разрешенное количество итераций (для избежания зацикливания процесса в случае неправильного определения отрезка изоляции). Выходные:X (тип real) – в нем содержится искомый корень сравнения; K (тип integer) – в него заносится количество выполненных итераций; FLAG (тип integer) – определяет способ выхода из процедуры, если FLAG=1, то заданная точность вычислений EPSне достигнута за разрешенное количество итераций IT.

Перед началом работы программы определяют func(Х) – процедуру-функцию, по которой вычисляют значения F(х). Тип функции должен быть вещественным.

Паскаль-программа и результаты расчета в среде Pascal ABC приведены на рисунках 4 и 5.

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

Рис. 5 Результаты уточнения корня методом дихотомии в среде PascalABC

Вариант алгоритма метода дихотомии может быть реализован в среде математического пакета Mathcad (см. рис. 6). Достоинством пакета является возможность графического отделения корней и оценка значений первой и второй производных на интервале изоляции.

Рис. 6 Результаты решения в среде пакета Mathcad

Постановка и решение задачи

Формулировка задачи

Нахождение корня уравнения методом дихотомии и методом хорд (на примере уравнения ) с точностью .

Решение задачи методом дихотомии

Решить дифференциальное уравнение вида с точностью =0.01.

График функции (рис.4) принимает следующий вид на отрезке [-7;2]:

Рисунок 4. График функции f(x)=x*2x-1

Из него видно,что функция меняет знак на промежутке [0;1].

Разделим этот отрезок на две части и проверим знак функции на концах каждой из них:

f(0)= -1 и f(0,5)=-0,29289; f(0,5)=-0,29289 и f(1)=1.

Отсюда видно, что функция меняет знак на отрезке [0,5;1].

Следовательно, следующим отрезком, который мы станем делить, будет именно он.

Аналогично: f(0,5)= -0,29289 и f(0,75)= 0,261345; f(0,75)= 0,26134 и f(1)= 1.

Корень уравнения принадлежит отрезку [0,5;0,75].

Продолжив итерацию, получим:

f(0,5)= -0,29289 и f(0,625)= -0,03612; f(0,625)= -0,03612 и f(0,75)= 0,26134.

f(0,625)= -0,03612 и f(0,6875)= 0,107212; f(0,6875)= 0,107212 и f(0,75)= 0,26134.

f(0,625)= -0,03612 и f(0,6563)= 0,034352; f(0,6563)= 0,034352 и f(0,6875)= 0,107212.

f(0,625)= -0,03612 и f(0,6407)= -0,00109; f(0,6407)= -0,00109 и f(0,6563)=0,034352.

f(0,6407)= -0,00109 и f(0,6485)= 0,016548; f(0,6485)= 0,016548 и f(0,6563)=0,034352.

Длина отрезка [0,6407;0,6485] меньше 2. Значит, корнем уравнения можно считать значение его середины, т.е. 0,6446, т.к. оно удовлетворяет заданной погрешности.

Решение задачи методом хорд

Решить дифференциальное уравнение вида с точностью =0.01.

График функции (рис.5) принимает следующий вид на отрезке [-7;2] (с хордой, проходящей через начало координат и пересекающей график в точке (2;7)):

Рисунок 5. График функции f(x)=x*2х-1

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

Подставив соответствующие значения в эту формулу, получим Х1:

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

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

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

Программная реализация

Блок-схемы

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

Тексты программ

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

a — начало отрезка,

b — конец отрезка,

e — погрешность вычислений,

x — искомое значение корня,

c — середина отрезка,

d — половина последнего найденного отрезка,

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×