Методичка по курсовым и лабораторным работам (1085639), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Методом поразрядного поиска решим задачу, рассмотренную в примере 1.1: f(x) = x⁴ + e ^–x ® min, x Î [0, 1], e = 0.1.

Положим, что начальный шаг D = = 0.25.

Вычисляем последовательно f(x_i) в точках x_i с шагом D в направлении слева направо (от 0 к 1). Результаты вычислений представлены в таблице 1.2.

Таблица 1.2

xi	0.00	0.25	0.50	0.75
f(xi)	1.000	0.783	0.669	0.789

Вычисления в данном направлении прекращаются, потому что f(0.50) < f(0.75), причем êD ê> e. Продолжаем поиск в противоположном направлении, справа налево (от 0.75 к 0). Величину шага уменьшаем в 4 раза, положив D = –0.0625. Результаты вычислений представлены в таблице 1.3.

Таблица 1.3

xi	0.7500	0.6875	0.6250	0.5625	0.5000	0.4375
f(xi)	0.789	0.726	0.688	0.670	0.669	0.682

Так как f(0.5000) < f(0.4375) и êD ê= 0.0625 < e, вычисления прекращаются. Таким образом, x^* » 0.5 и f(x^*) » 0.669.

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

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

Пусть f(x) – непрерывная и унимодальная на отрезке [a, b] функция, принимающая во всех точках этого отрезка конечные значения. Пусть число пробных точек x₁, x₂, …, x_n конечно, и для определения каждой точки x_k можно использовать информацию о значениях функции во всех предыдущих точках x₁, x₂, …, x_{k – 1} . Положим a₀ = a, b₀ = b. Середина отрезка [a, b] = [a₀, b₀] находится в точке . Выберем две симметричные точки

x₁ = , x₂ = . (1.5)

Величина d, удовлетворяющая условию 0 < d < b – a , является параметром метода, как правило, d – малая величина.

Вычислим значения функции в выбранных точках: f(x₁) и f(x₂). Определим новый отрезок локализации [a₁, b₁] следующим образом:

если f(x₁) £ f(x₂), то a₁ = a₀, b₁ = x₂;

если f(x₁) > f(x₂), то a₁ = x₁, b₁ = b₀.

Далее процедура деления отрезка [a₁, b₁] повторяется.

Деление продолжают до тех пор, пока половина длины отрезка [a_n, b_n] не станет меньше заданной точности решения задачи e, e > d, т. е. пока не выполнится неравенство

< e.

Тогда за приближение x^* принимают середину отрезка [a_n, b_n], т.е. x^* » .

Алгоритм 1.2 (Алгоритм метода дихотомии).

Шаг 1. Ввести исходные данные: a, b, d, e.

Шаг 2. Определить x₁ и x₂ по формулам (1.5).

Шаг 3. Вычислить f(x₁) и f(x₂).

Шаг 4. Если f(x₁) £ f(x₂), то перейти к новому отрезку [a, b], положив b = x₂. Иначе перейти к новому отрезку [a, b], положив a = x₁.

Шаг 5. Если < e, то требуемая точность достигнута, перейти к шагу 6, иначе – к шагу 2 для продолжения итераций.

Шаг 6. Положить x^* » . Вычислить f ^* » f(x^*).

Число итераций метода дихотомии оценивается по формуле

n ³ log₂ .

Величину d выбирают из условия 0 < d < 2e. При этом нужно иметь в виду, что при слишком малом d из-за погрешности вычисления на ЭВМ сравнение f(x₁) и f(x₂) становится затруднительным.

Пример 1.3.

Методом деления отрезка пополам решим задачу, рассмотренную в примерах 1.1 и 1.2: f(x) = x⁴ + e ^–x ® min, x Î [0, 1], e = 0.1.

Положим d = 0.02. Результаты вычислений приведены в табл. 1.4.

Таблица 1.4

Номер итерации	a	b		x1	x2	f(x1)	f(x2)	Сравнение f(x1) и f(x2)
1 2 3 4	0 0.49 0.49 0.49	1 1.000 0.755 0.633	0.5 0.26 0.13 0.07	0.49 0.735 0.613	0.51 0.755 0.633	0.670 0.771 0.683	0.688 0.792 0.691	f(x1) > f(x2) f(x1) < f(x2) f(x1) < f(x2)

Вычисления прекращаются после 4-ой итерации, так как требуемая точность достигнута (0.07< 0.1). При этом

x^* » » 0.56, f ^* » f(0.56^*) » 0.67.

1.5. Метод Фибоначчи

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

Метод Фибоначчи основан на использовании чисел Фибоначчи, задаваемых рекуррентным соотношением

F_n = F_n-1 + F_n-2 (n ³ 2) (1.6)

с начальными значениями F₀ = 1, F₁ = 1.

Этот метод был предложен в 1953 г. Кифером.

Формула (1.6) вместе с начальными значениями определяет следующий ряд чисел Фибоначчи :

n	0 1 2 3 4 5 6 7 8 9 10 11 …
Fn	1 1 2 3 5 8 13 21 34 55 89 144 …

Метод Фибоначчи состоит из n шагов.

Положим вначале a₀ = a, b₀ = b.

На k-ом шаге, k =0, 1, … , n – 1, определим точки x и x из условия

x = a_k + (b_k – a_k), x = a_k + (b_k – a_k). (1.7)

Формулы (1.7) являются основными расчетными формулами метода Фибоначчи

После этого так же, как и в методе дихотомии, определяют новый, меньший отрезок локализации [a_k+1, b_k+1] по тому же правилу:

если f(x ) £ f(x ), то a_k+1 = a_k, b_k+1 = x ;

если f(x ) > f(x ), то a_k+1 = x , b_k+1 = b_k.

Важно, что одна из пробных точек x , x станет пробной точкой на новом отрезке локализации, т. е. совпадет с одной из точек x , x .

Поэтому на каждой итерации достаточно определить только одно значение f(x), так как другое уже найдено на предыдущей итерации.

В конце вычислений можно взять в качестве приближенного значения x^* = x .

После выполнения n итераций погрешность удовлетворяет следующему неравенству:

e_n = < . (1.8)

Следовательно, если задана требуемая точность e, число итераций n определяется из условия < e или

F_{n +1} > . (1.9)

Заметим, что из (1.9) следует, что число итераций, необходимое для удовлетворения заданной точности e , зависит только от длины отрезка b – a и точности e и не зависит от вида функции f(x).

Алгоритм 1.3 (Алгоритм метода Фибоначчи).

Шаг 1. Ввести исходные данные: a, b, e. Определить число итераций n из условия (1.9). Ввести числа Фибоначчи F₀, F₁, F₂, … , F_{n +1}.

Шаг 2. Положить k = 0 и определить x₁ и x₂ по формулам (1.7).

Шаг 3. Вычислить f(x₁) и f(x₂).

Шаг 4. Проверить критерий окончания вычислений: k = n . Если k < n, перейти к шагу 5, иначе – к шагу 6.

Шаг 5. Перейти к новому отрезку локализации и новым пробным точкам. Если f(x₁) £ f(x₂), то положить b = x₂, x₂ = x₁, f(x₂) = f(x₁), x₁= a + (b – a) и вычислить f(x₁). Иначе положить a = x₁, x₁ = x₂, f(x₁) = f(x₂), x₂ = a + (b – a) и вычислить f(x₂).

Положить k = k +1 и перейти к шагу 4.

Шаг 6. Положить x^* » x₁. Вычислить f ^* » f(x^*).

Пример 1.4.

Методом Фибоначчи решим задачу, рассмотренную ранее: f(x) = x⁴ + e ^–x ® min, x Î [0, 1], e = 0.1.

Условие (1.8) для нашей задачи имеет вид

F_{n +1} > = 5.

Первым среди чисел Фибоначчи, для которого выполняется это условие является число F₅ = 8, т.е. n +1 = 5, n = 4.

Результаты вычислений для четырех итераций приведены в табл. 1.5.

Таблица 1.5

Таким образом, x^* » 0.5 и f(x^*) » 0.669.

1.6. Метод золотого сечения

В основе этого метода лежит понятие "золотого сечения", введенного Леонардо да Винчи и используемого, в частности, при построении архитектурных сооружений античности и эпохи Возрождения.

Золотым сечением отрезка называется его разбиение на две неравные части, так, что отношение длины всего отрезка к длине его большей части равно отношению длины большей части к длине меньшей части (рис.1.3, слева)

= .

Характеристики

Список файлов книги