Алгоритм

Рисунок 3, а, б.

В первом случае конец а неподвижен и последовательные приближения: x ₀ = b;

(5)

образуют ограниченную монотонно убывающую последовательность, причем

Во втором случае неподвижен конец b, а последовательные приближения: x ₀ = а;

(6)

образуют ограниченную монотонно возрастающую последовательность, причем

Обобщая эти результаты, заключаем:

1. неподвижен тот конец, для которого знак функции f (х) совпадает со знаком ее второй производной f'' (х);

2. последовательные приближения x_n лежат по ту сторону корня x, где функция f (х) имеет знак, противоположный знаку ее второй производной f'' (х).

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

| x_i - x_{i -} 1|< e,

где e - заданная предельная абсолютная погрешность.

27. Метод Ньютона решения уравнений – метод приближенного нахождения корня х ₀уравнения f (x) = 0.

Суть метода можно сформулировать так.

Берется какое-либо число а ₁ как можно ближе к искомому корню х ₀ и принимается за первое приближение корня (см. рис.). Затем через точку А ₁ с координатами (а ₁; f (a ₁)) проводится касательная к графику функции у = f (x) до пересечения с осью абсцисс в точке (а ₂; 0). Эта точка пересечения дает нам второе приближение корня х ₀. Повторяя этот процесс, получаем все более и более точные значения а ₀; а ₁; а ₂; … корня х ₀.

С помощью уравнения касательной можно вывести рекуррентную формулу, выражающую очередное, i -е приближение а _i через предыдущее:
.

28. Метод итераций. Одним из наиболее важных способов численного решения уравнений является метод итерации. Сущность этого метода заключается в следующем. Пусть дано уравнение

где f(x) – непрерывная функция, и требуется определить его вещественные корни. Заменим уравнение (1) равносильным уравнением

Выберем каким-либо способом грубо приближенное значение корня x₀ и подставим его в правую часть уравнения (2). Тогда получим некоторое число

Подставляя теперь в правую часть равенства (3) вместо x₀ число x₁ получим новое число x₂=j (x₁). Повторяя этот процесс, будем иметь последовательность чисел

Если эта последовательность – сходящаяся, т.е. существует предел , то, переходя к пределу в равенстве (4) и предполагая функцию j (x) непрерывной, найдем:

или

x =j (x). (5)

Таким образом, предел x является корнем уравнения (2) и может быть вычислен по формуле (4) с любой степенью точности.

Доказано, что достаточными условиями сходимости итерационного процесса является выполнение условия | j (x)< 1 для xÎ [ a,, b ].

При этом процесс сходится к единственному корню x.

На рис. 1 приведен пример сходящегося итерационного процесса x_n+1=j (x_n) при 0 < j ’(x)< 1 и на рис.2 – расходящегося при j ’(x)< 1.

29.

Суть – поиск направления убывания целевой функции, движение в данном направлении в случае удачного поиска с постепенно возрастающим шагом. Сначала определяем начальную координату M0 функции F(M), минимальное значение шага h0, направление поиска. Затем определяем функцию в т. M0. Далее совершаем шаг и находим значение данной функции в данной точке. В случае если функция меньше значения, которое было на предыдущем шаге, следует произвести следующий шаг в том же направлении, предварительно увеличив его в 2 раза. При ее значении, которое больше предыдущего, потребуется поменять направление поиска, а затем начать двигаться в выбранном направлении с шагом h0. Представленный алгоритм можно модифицировать

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

Алгоритм

1. Шаг 1. Задаются начальные границы отрезка и число итераций , рассчитывают начальные точки деления: и значения в них целевой функции: .

2. Шаг 2. .

· Если , то .

· Иначе .

3. Шаг 3.

· Если , то и останов.

· Иначе возврат к шагу 2.

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

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

, где — пропорция золотого сечения.

Таким образом:

То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.