Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Алгоритм






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

 

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

(5)

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

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

(6)

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

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

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

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

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

| xi - xi - 1|< e,

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

 

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

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

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

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

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

  f(x)=0. (1)

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

  x=j (x). (2)

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

  x1=j (x0). (3)

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

  xn=j (xn-1) (n=1, 2,...). (4)

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

или

x =j (x). (5)

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

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

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

На рис. 1 приведен пример сходящегося итерационного процесса xn+1=j (xn) при 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. Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:

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

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

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

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


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.01 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал