АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Элементы теории

Читайте также:
  1. D – элементы
  2. I. МЕХАНИКА И ЭЛЕМЕНТЫ СПЕЦИАЛЬНОЙ ТЕОРИИ ОТНОСИТЕЛЬНОСТИ
  3. III. Несущие элементы покрытия.
  4. S-элементы I и II групп периодической системы Д.И.Менделеева.
  5. V. ЭЛЕМЕНТЫ ФИЗИКИ АТОМА
  6. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  7. А. Понятие и элементы договора возмездного оказания услуг
  8. А. Понятие и элементы комиссии
  9. А. Понятие и элементы простого товарищества
  10. Административный менеджмент в классической теории организации и управления
  11. Аксиома выражения в теории вероятностей.
  12. Аксиома выражения в теории множеств.

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

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

Отделение можно осуществить, как графически, так и табулированием. Все методы уточнения точек экстремумов можно рассматривать относительно уточнения минимума на заданном отрезке. Алгоритм основан на следующем следствии из теоремы Больцано-Коши:

пусть непрерывная функция f (x) Î С ([ a, b ]), тогда, если sign (f (a)) ≠ sign (f (b)), то $ C Î [ a, b ]: f (C) = 0.

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

Точность вычислений задаётся одним из двух способов:

1. λ f ( x ) по оси y, что ближе к условию f (x) = 0 из описания алгоритма; или

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

Процедуру следует продолжать до достижения заданной точности λ.

Задача заключается в нахождении корней нелинейного уравнения

f (x) = 0 (8.1)

 

Для начала итераций необходимо знать отрезок [ x ( L ), x ( R )] значений x, на концах которого функция принимает значения противоположных знаков.

Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения f (x ( L )) и f (x ( R )) путём сравнения результата с нулём:

 

f (x ( L )) · f (x ( R )) < 0. (8.2)

 

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

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

 

sign (f (x (L))) ≠ sign f (x (R)), (8.3)

 

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

Из непрерывности функции f (x) и условия (8.3) следует, что на отрезке [ x ( L ), x ( R )] существует хотя бы один корень уравнения (в случае не монотонной функции f (x) функция имеет несколько корней и метод приводит к нахождению одного из них).

Найдём значение х в середине отрезка:

 

x ( M ) = (x ( L ) + x ( R ))/2. (8.4)

 

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

 

x ( D ) = x ( R ) - x ( L ), (8.5)

 

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

 

x ( D ) = x ( D ) /2 (8.6)

 

и новую середину по формуле:

 

x ( M ) = (x ( L ) + x ( D )). (8.7)

 

Вычислим значение функции f (x ( M )) в середине отрезка x ( M ):

Если f (x ( M )) = 0 или, в действительных вычислениях, ǀ f (x ( M ))ǀ ≤ λ f (x), где λ f (x)— заданная точность по оси y, то корень найден.

Иначе f (x ( M )) ≠ 0 или, в действительных вычислениях, ǀ f (x ( M ))ǀ > λ f (x), то разобьём отрезок [ x ( L ), x ( R )] на два равных отрезка: [ x ( L ), x ( M )] и [ x ( M ), x ( R )].

Теперь найдём новый отрезок, на котором функция меняет знак.

Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке, f (x ( L )) · f (x ( M )) ˂ 0 или sign f (x ( L )) ≠ sign f (x ( M )), то, соответственно, корень находится внутри левого отрезка [ x ( L ), x ( M )]. Тогда возьмём левый отрезок присвоением x ( R ) = x ( M ), и повторим описанную процедуру до достижения требуемой точности λ f (x)по оси y.

Если значения функции на концах отрезка имеют противоположные знаки на правом отрезке, f (x ( M )) · f (x ( R )) ˂ 0 или sign f (x ( M )) ≠ sign f (x ( R )), то, соответственно, корень находится внутри правого отрезка [ x ( M ), x ( R )]. Тогда возьмём правый отрезок присвоением x ( L ) = x ( M ), и повторим описанную процедуру до достижения требуемой точности λ f (x) по оси y.

Итерации деления пополам осуществляется N раз, поэтому длина конечного отрезка в 2 N раз меньше длины исходного отрезка.

Существует похожий метод, но с критерием остановки вычислений λ (х) по оси х. В этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси х: (x ( R ) - x ( L )) > λ (х). В этом методе отрезок на оси x может достичь заданной величины λ (х), а значения функций f (x) (особенно крутых) на оси y могут очень далеко отстоять от нуля, при пологих же функциях f (x) этот метод приводит к большому числу лишних вычислений.

В дискретных функциях x ( L ), x ( M ) и x ( R ) - это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия остановка вычислений, разность (x ( R ) - x ( L )) не может быть меньше λ (х) = 1.

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

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

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

Основные шаги поисковой процедуры нахождения точки минимума в интервале (a, b):

1. Принимаем х m=(a + b)/2, L = b - a. Вычислить f (x m).

2. x 1 = a + L /4; x 2 = b - L /4. Вычислить f (x 1) и f (x 2).

3. Сравнить f (x 1) и f (x m). Если f (x 1) £ f (x m), исключить интервал (x m, b), положив b = x m. Средней точкой нового интервала поиска становится точка х 1. x m = x 1. Перейти к п.5. Если f (x 1) ³ f (x m), перейти к п.4.

4. Сравнить f (x 2) и f (x m). Если f (x 2) £ f (x m), исключить интервал (a, x m), положив x m = a. x 2 становится точкой x m. Средней точкой нового интервала становится точка x 2. Перейти к п.5. Если f (x 2) ³ f (x m), исключить интервалы (a, x 1) и (х 2, b), положив а = х 1, b = x 2. x m остается средней точкой нового интервала. Перейти к п.5.

5. Вычислить L = b - a. Если величина ½ L ½£ λ (λ – некоторое заданное значение точности), закончить поиск. В противном случае вернуться к п. 2.

Достоинства метода: простота и быстрое достижение результата.

Недостатки метода: необходимо заранее знать отрезок, на котором функция меняет знак. Это не совсем удобно.


Выполнение работы в среде MS EXCEL

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

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

Таблица расчетных данных должна содержать согласно алгоритму расчета графы расчета величин a, b, L, x m, x 1, x 2, f (x m), f (x 1), f (x 2). Для первой итерации формулы для расчета этих величин очевидны. На следующих итерациях трудность представляет только определение границ a и b, формулы для расчета остальных величин одни и те же для всех итераций. Во второй итерации необходимо внести такие формулы для расчета границ a и b, которые при копировании на все остальные итерации давали бы правильные значения границ в зависимости от значений функции в точках x m, x 1, x 2. Для этого также необходимо использовать логические функции. Расчет следует вести до тех пор, пока L не станет меньше λ.

 


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

 

Пример выполнения представлен в табл. 8.2.


Таблица 8.2

f (x) = (100- x)2 λ = 0,1

Итерация a b L x m х (1) x (2) f (х (1)) f (x (m)) f (x (2))
  65,000 185,000 120,000 125,000 95,000 155,000 25,000 625,000 3025,000
  65,000 125,000 60,000 95,000 80,000 110,000 400,000 25,000 100,000
  80,000 110,000 30,000 95,000 87,500 102,500 156,250 25,000 6,250
  95,000 110,000 15,000 102,500 98,750 106,250 1,563 6,250 39,063
  95,000 102,500 7,500 98,750 96,875 100,625 9,766 1,563 0,391
  98,750 102,500 3,750 100,625 99,688 101,563 0,098 0,391 2,441
  98,750 100,625 1,875 99,688 99,219 100,156 0,610 0,098 0,024
  99,688 100,625 0,938 100,156 99,922 100,391 0,006 0,024 0,153
  99,688 100,156 0,469 99,922 99,805 100,039 0,038 0,006 0,002
  99,922 100,156 0,234 100,039 99,980 100,098 0,000 0,002 0,010
  99,922 100,039 0,117 99,980 99,951 100,010 0,002 0,000 0,000
  99,980 100,039 L<l            

Примеры программ, реализующих поиск корня уравнения

f (x) = 0 методом деления отрезка пополам (Basic, Pascal)

Basic

 

DECLARE FUNCTION F! (X!) REM ИСХОДНОЕ УРАВНЕНИЕ В ВИДЕ F(X)=0

CLS

INPUT "Введите границы интервала "; A, B

IF (F(A) * F(B)) > 0 THEN

SOUND 500, 5

PRINT "Ошибка! Функция не меняет знак на этом интервале!"

END

ELSE

INPUT "Задайте точность вычислений "; E

PRINT

PRINT " X F(X) A F(A) B F(B)"

PRINT "------------------------------------------------"

DO WHILE (ABS(B - A) >= 2 * E)

X = (B + A) / 2

IF F(X) * F(A) > 0 THEN A = X ELSE B = X

PRINT USING "####.###"; X; F(X); A; F(A); B; F(B)

LOOP

END IF

PRINT

PRINT "Корень уравнения ";

PRINT USING "####.###"; (B + A) / 2

END

 

FUNCTION F (X)

F = SIN(X) + COS(X) REM ИСХОДНОЕ УРАВНЕНИЕ В ВИДЕ F(X)=0

END FUNCTION

 


Pascal

 

Program Half;

 

Uses Crt;

 

Var

a,b,e,x: real;

 

Function f(x:real):real;

Begin

f:= sin(x)+cos(x);

End;

 

Begin

 

Clrscr;

Write('Введите границы интервала: ');

Readln(a,b);

 

if (f(a)*f(b)) > 0 then

Begin

Sound(220);

Delay(200);

NoSound;

Writeln('Ошибка! Функция не меняет знак на этом интервале!');

Writeln('Нажмите любую клавишу');

Readkey;

Halt;

End

else

Begin

Write('Задайте точность вычислений: ');

Readln(e);

Writeln;

Writeln(' X F(X) A F(A) B F(B)');

Writeln('------------------------------------------------');

While (Abs(b-a)>=2*e) do

Begin

x:=(b+a)/2;

if f(x)*f(a)>0 then a:=x else b:=x;

Writeln(x:8:3,f(x):8:3,a:8:3,f(a):8:3,b:8:3,f(b):8:3);

End;

End;

 

Writeln;

Writeln('Корень уравнения ',(B + A) / 2:4:2);

Writeln('Нажмите любую клавишу');

Readkey;

 

End.

Контрольные вопросы

 

1. В каких точках интервала сравниваются значения функции при использовании метода деления интервала пополам?

2. Что представляет собой минимум функции?

3. Для чего используется заданная точность (l)?.

4. Для чего уменьшают интервал поиска?

5. Какие методы исключения интервалов существуют в оптимизации?

6. Какую часть интервала исключают на каждом шаге поиска в методе деления интервала пополам?

7. Что позволяет исключить метод деления интервала пополам?

8. Какие основные шаги поисковой процедуры нахождения точки минимума в заданном интервале?

9. Что служит исходными данными для нахождения минимума функции методом деления интервала пополам?

10. Какие величины должна содержать таблица расчетных данных согласно алгоритму расчета для нахождения минимума функции методом деления интервала пополам?

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

12. Что можно использовать при нахождении заданных границ при решении задачи в среде MS EXCEL?

13. До каких значений L ведутрасчеты для нахождения минимума функции методом деления интервала пополам?


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.022 сек.)