Экзаменационные шпоргалки

32. Решение задачи одномерной минимизации методом деления отрезка пополам. Алгоритм и оценка погрешности.

Утв.: Если f(x) – унимод. на [a, b] и если a < b и выполнены условия f(a) < f(b), тогда х^½ Î [a, b], если f(a) > f(b), тогда х^½ Î [a, b]. Утв.2. Если f(x) – унимод. на [a, b], то также унимодальна на любом [a, b] Ì [a, b]. На каждом шаге метода вычисл. 2 значения: a^(k) = (a^(k) + b^(k))/2 - d. b^(k) = (a^(k) + b^(k))/2 + d. d - параметр метода, причем 0 <d< (b – a)/2. Условие выбора новых границ: Если f(a⁽⁰⁾) £ f(b⁽⁰⁾), то [a⁽¹⁾, b⁽¹⁾] = [a⁽⁰⁾, b⁽⁰⁾]; а если f(a⁽⁰⁾) > f(b⁽⁰⁾), то [a⁽¹⁾, b⁽¹⁾] = [a⁽⁰⁾, b⁽⁰⁾]. D⁽ⁿ⁾ = b⁽ⁿ⁾ – a⁽ⁿ⁾ = (D - 2d)/2ⁿ + 2d. lim_n®¥D⁽ⁿ⁾ = 2d. ® d < e/2.

33. Решение задачи одномерной минимизации методом золотого сечения. Алгоритм и оценка погрешности.

ЗС отрезка наз деление на 2 наравные части, так, что D/D₁ = D₁/D₂. D - длина всего отрезка. a^(k) = а^(k) + (2/(3 + Ö5))(b^(k) – a^(k)); b^(k) = a^(k) + (2/(1 + Ö5))(b^(k) – a^(k)). Точка a осущ. золотое сечение не только отр. [a, b] но и отрезка [a, b]. a^(k) или b^(k) совпадают с предыд. знач. a^(k-1) или b^(k-1). Поэт. в отличие от деления на 2, необх. вычисл. только одно недостающ. знач. ф-ии. Далее выбирают так: если f(a^(k)) £ f(b^(k)), то [a^(k+1), b^(k+1)] = [a^(k), b^(k)], если же f(a^(k)) > f(b^(k)), то [a^(k+1), b^(k+1)] = [a^(k), b^(k)]. Погрешн.: ½x^½-x⁽ⁿ⁾½£(2/(1 + Ö5))ⁿ⁺¹D, D = b–a. n – число итераций.

35. МН поиска минимума для задачи одномерной минимизации. Трудности применения.

Условие: f(x) Î c²[a, b]. Если х^½ - точка мин., то f '(x) = 0, f ''(x) ­. Хочем: x⁽ⁿ⁾ » x^½.Возьмем за р – направление спуска. f(x⁽ⁿ⁾ + p) = f(x⁽ⁿ⁾) + (f '(x⁽ⁿ⁾)/1!)p + (f''(x⁽ⁿ⁾)/2!)p² + … f(x⁽ⁿ⁾ + p) » q(p) = f(x⁽ⁿ⁾) + (f '(x⁽ⁿ⁾)/1!)p + (f ''(x⁽ⁿ⁾)/2!)p². q(p) – парабола. q(p) – мин. по р. ® dq/dp = f '(x⁽ⁿ⁾) + f ''(x⁽ⁿ⁾)p = 0. Условие экстр.: p = - f '(x⁽ⁿ⁾)/f ''(x⁽ⁿ⁾) ® x⁽ⁿ⁺¹⁾ = x⁽ⁿ⁾ + p = x⁽ⁿ⁾ - f '(x⁽ⁿ⁾)/f ''(x⁽ⁿ⁾) ® x⁽ⁿ⁺¹⁾ = x⁽ⁿ⁾ - f '(x⁽ⁿ⁾)/f ''(x⁽ⁿ⁾) ¬ расчетная ф-ла. Метод облад. локальной сходимостью. Вблизи x^½ сход. квадратично. Критерий окончания: ½x⁽ⁿ⁾ - x^(n-1)½ < e.