Метод прямого сканирования

Задача заключается в локализации экстремума функции одной переменной, заданной на интервале [a, b] с точностью до Δ. При решении этой задачи весь интервал разбивается на участки величиной Δ. В узлах разбиения вычисляются значения функции Q и из них выбирается экстремальное. Этот метод требует больших затрат времени (зависящего от значения Δ), но главное его преимущество – это определение глобального экстремума.

Рисунок 2. Локализация экстремума методом сканирования:
геометрическая интерпретация

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

Естественным и наиболее распространенным на практике методом поиска экстремума функции одной переменной является метод последовательного деления отрезка пополам. Этот метод был известен еще в древней Греции как метод дихотомии.

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке [a, b] с точностью Δ. Отрезок [a, b] делится пополам и вычисляются значения функции Q (x1) = F1 и Q (x2) = F2 в точках .

На основе анализа значений F1 и F2 вдвое уменьшается интервал неопределенности и процесс повторяется пока b – a > Δ.

Рисунок 3 Метод половинного деления:

геометрическая интерпретация

Метод «золотого сечения»

Гораздо эффективнее, с точки зрения уменьшения затрат на вычисления, метод "золотого сечения": интервал неопределенности делится не пополам, как в методе дихотомии, а в определенном иррациональном соотношении:

Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x1 (см. рис. 2.3, б) по формуле

Точка x2 определяется как точка, симметричная точке x1 на отрезке (a – b). На основе анализа значений F1 = Q (x1) и F2 = Q (x2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий унимодальности Q (u).

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

Рисунок 4. Метод «золотого сечения»:
а – золотое сечение; б – геометрическое представление

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

Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением:

F₀ = F₁ = 1; F_k = F_k–1 + F_k–2 ; k = 2, 3, …

При большом "k" отношение соседних чисел Фибоначчи близко к отношению "золотого сечения". Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от Δ, число вычислений значений функции Q (u).

По заданному Δ определяется количество вычислений n и соответствующее ему число Фибоначчи F_n , исходя из соотношения:

Метод Гаусса–Зейделя

Одним из самых распространенных итерационных методов, отличающийся простотой и легкостью программирования, является метод Гаусса–Зейделя.

Проиллюстрируем сначала этот метод па примере решения системы

(3.9.1)

Предположим, что диагональные элементы а11, а22, а33отличны от нуля (в противном случае можно переставить уравнения). Выразим неизвестные х1, х2и х3 соответственно из первого, второго и третьего уравнений системы (3.9.1):

(3.9.2)

(3.9.3)

(3.9.4)

Зададим некоторые начальные (нулевые) приближения значений неизвестных: Подставляя эти значения в правую часть выражения (3.9.2), получаем новое (первое) приближение для х1:

Используя это значение для x1 и приближение для х3, находим из (3.9.3) первое приближение для х2:

И наконец, используя вычисленные значения находим с помощью выражения (3.9.4) первое приближение для х3:

На этом заканчивается первая итерация решения системы (3.9.2) - (3.9.4). Теперь с помощью значений х1(1), х2(1)их3(1)можно таким же способом провести вторую итерацию, в результате которой будут найдены вторые приближения к решению: х1 = х1 (2), х2 = х2(2)и х3 = х3(2)и т.д.

Приближение с номером kможно вычислить, зная приближение с номером k– 1, как

Итерационный процесс продолжается до тех пор, пока значения х1(k), х2(k)и х3(k)не станут близкими с заданной погрешностью к значениям х1(k-1), х2(k-1)и х3(k-1).