шпорки (851429), страница 2

22. Аппроксимация функций по МНК. Постановка задачи. Вывод нормальной системы метода. Выбор степени аппроксимирующего многочлена.

В случае, если: 1. f(x) задана табл. 2. f(x) – вычисл. сложно. Задача: приблизить ф-ию f(x) ф-ией F(x), т. е. f(x)  F(x).  - средеквадр. отклон. должно быть миним.  = ((1/(n + 1))_i=0ⁿ(y_i – F(x_i))²)  min. Приближаем многочленом Р_n(x) = a₀ + a₁x + a₂x² + … + a_mx^m = 0.  = ((1/(n + 1))_i=0ⁿ(a₀ + a₁x_i + a₂x_i² + … + a_mx_i^m - y_i)²)  min. _i=0ⁿ(a₀ + a₁x_i + a₂x_i² + … + a_mx_i^m - y_i)²  min по a₀, a₁, a₂, …, a_m, т. е. g/a₀ = 2_i=0ⁿ(a₀ + a₁x_i + a₂x_i² + … + a_mx_i^m - y_i)*1) = 0; … g/a_m = 2_i=0ⁿ(a₀ + a₁x_i + a₂x_i² + … + a_mx_i^m - y_i)*x_i^m) = 0; Получаем нормальную систему ур-ий МНК: (_i=0ⁿx_i⁰)a₀ + (_i=0ⁿx_i¹)a₁ + … + (_i=0ⁿx_i^m)a_m = _i=0ⁿy_i; … ; (_i=0ⁿx_i^m)a₀ + (_i=0ⁿx_i^m+1)a₁ + … + (_i=0ⁿx_i^2m)a_m = _i=0ⁿy_ix_i^m. Система симметрична и плохообусловлена. при m > 5 погрешность – катастрофическая. Из нее нах. a₀, a₁, a₂, …, a_m. Степень аппр. мн. m выбир. такой, когда ф-ия (m) имеет первый локальный минимум

23. Постановка задачи интерполяции. Т. о существовании и единственности интерполяционного многочлена.

Дана n + 1 точка, построить интерп. мн. степени n, так, чтобы P_n(x_i) = y_i. Т. интерполяц. многочлен  и единственен. Д. 1. Существование. Рассм. м-н Логранжа: L_n(x) = _i=0ⁿy_i((x – x₀)(x-x₁)…(x-x_i-1)(x-x_i+1)…(x-x_n)/(x_i-x₀)(x_i-x₁)…(x_i-x_i-1)(x_i-x_i+1)…(x_i-x_n)). L_n(x) -  мн-ов n-ой степени, сам он тоже n-ой степени. L_n(x_k) = y_k, k = 0, 1, …, n. 2. Единственность. Рассм. P_n¹, P_n² – 2 интерп. мн-на n – ой ст. P_n(x) = P_n¹ - P_n². P_n(x_k) = 0; k = 0, …, n

24. Многочлен Лагранжа. Оценка погрешности интерполяции.

см. чуть повыше

Погрешность интерп.: R_n(x)=y(x)–P_n(x). T. y(x)cⁿ⁺¹[x₀,x_n]. R_n(x)(M_n+1/(n+1))!_n+1(x), где: M_n+1=max_{[x0, xn]}y^{(n + 1)}(x); _n+1(x) = (x – x₀)(x - x₁)…(x – x_n). без. док. max_n+1(x) невелико внутри [x₀, x_n], а вне быстро растет.

25. Многочлен Ньютона с конечными разностями. Оценка погрешности.

. Применяется, когда сетка равномерна. Составим диаг. таблицу конеч. разностей: строка заголов.: x_i; y_i; y_i; ²y_i;… Возьмем интерп. мн. в след. виде: _n(x) = a₀ + a₁(x – x₀) + a₂(x – x₀)(x – x₁) + … + a_n(x – x₀)(x – x₁)…(x – x_n). Условие: _n(x_i) = y_i. (x_k – x_k-1) = h. Рассмотри _n(x₀) = a₀ = y₀; _n(x₁) = … и выведи ф-лу: a_k = ^ky₀/(k!h_k). Интерп. м-н Н. при интерп. вперед от точки x₀: _n(x) = y₀ + (y₀/1!h)(x – x₀) + … + (ⁿy₀/n!hⁿ)(x – x₀)(x – x₁)…(x – x_n). Интер. МН при инт. назад от точки x_n: _n(x) = y_n + (y_n-1/1!h)(x – x₀) + … + (ⁿy₀/n!hⁿ)(x – x₀)(x – x₁)…(x – x_n). Оценка погреш.: как для Логранжа R_n(x)  (M_n+1/(n+1)!)hⁿ⁺¹. Преимущ.: при добавл. новых узлов надо только добавить новое слагаемое, можно строить от  точки табл.

26. Глобальная и кусочно-полиномиальная интерполяция.

Глоб. – с исп. всех точек. Кусочнополин. – с использованиием части точек, мн-ми невыс. степ. Погрешность: max[x₀, x_n]f(x) – P_m(x) (M_m+1)/4(n + 1))/h_max^m+1, где m – степень интерп. мн-на, а M_m+1 = max_{[a, b]}f ^(m+1)(x).  from book. Из тетрадки: R⁽ⁿ⁾_инт  (M_n+1/(n+1)!)hⁿ⁺¹.

27. Интерполяция с кратными узлами.

Мы знаем в хi не только значения f(x_i), но и f '(x_i), … f^(k-1)(x_i). (x_i – узел кратности k), причем для всех точек (i = 0, …, m). Пусть k₁ – кратность 1-ого узла, …, k_m – кратность m-ого узла. n = k₀ + … + k_m.  единственный многочлен ст. n, такой, что P_n(x_i) = y_i; P'(x_i) = y'(x), … до (k – 1) для всех i = 0, …, m. 1. Задан один узел кратности k. P_n(x) = _i=0^k-1y₀⁽ⁱ⁾(x – x₀)ⁱ/(i!). 2. Заданы несколько точек кратности 2, т. е. мы знаем y(x_i) и y'(x_i). По каждым двум соседним точкам в этом случае строят мн-н Эрмита: P₃(x) = y_i-1((x – x_i)²(2(x – x_i-1) + h_i)/h_i³) + y_i((x – x_i-1)²(2(x_i – x) + h_i)/h_i³) + y'_i-1((x – x_i-1)(x – x_i)²/h_i²) + y'_i((x – x_i-1)²(x – x_i)/h_i²). (локальный сплайн). Погрешность max_{[x0, x1]}f(x) – P₃(x)  (M₄/384)h⁴, M₄ = max_{[x0, x1]}f⁽⁴⁾(x). h = (x₁ – x₀).

28. Понятие сплайна. Интерполяционный сплайн степени m. Различные виды граничных условий.

(Гибкая линейка). Условия: 1. Ф-ия S_m(x) и ее произв. до S^(p)_m(x) вкл. непрер. на [x₀, x_n]. 2. Значение S_m(x) на [x_i-1,x_i] представл. собой полином степени m. 3. S_m(x_i) = y(x_i). S_m(x) – интерп. сплайн. Деффект спл. есть m–p. Рассмотрим кубический сплайн: S₃(x) = P_3,i(x) = y_i-1((x – x_i)²(2(x – x_i-1) + h_i)/h_i³) + y_i((x – x_i-1)²(2(x_i – x) + h_i)/h_i³) + s_i-1((x – x_i-1)(x – x_i)²/h_i²) + s'_i((x – x_i-1)²(x – x_i)/h_i²). Граничные условия: 1. если известны y'(x₀), y'(x_n), то полагают, что s₀ = y'(x₀); s_n=y'(x_n), где s_i – наклон сплайна, s_i = S'_m(x_i). 2. известны y''(x₀), y''(x_n)  - 4s₀/h₁ – 2s₁/h₁ + 6(y₁ – y₀)/h₁² = y''(x₀); 2s_n-1/hⁿ + 4s_n/hⁿ – 6(y_n – y_n-1)/h_n² = y''(x_n). 3. естественный сплайн: y'(x₀) = y'(x_n) = 0. 4. отсутствие узла. выбор наклонов s_i производят так, чтобы P_3,1(x)=P_3,2(x); P_3,n-1(x)=P_3,n(x). для этого потребуем совпад. соотв. 3-их произв.: P'''_3,1(x₁) = P'''_3,2(x₁); P'''_3,n-1(x_n-1) = P'''_3,n(x_n-1). 2h₁^-3(y₀ – y₁) + h₁^-2(s₀ – s₁) = 2h₂^-3(y₁ – y₂) + h₂^-2(s₁ + s₂), 2h_n-1^-3(y_n-2 – y_n-1) + h_n-1^-2(s_n-2 + s_n-1) = 2h_n^-3(y_n-1 – y_n) + h_n^-2(s_n-1 + s_n).

29. Построение линейного и кубического сплайнов. Оценка погрешности приближения функции кубическим сплайном.

Лин. сплайн: y_i+((y_i+1–y_i)/(x_i+1–x_i))(x–x_i), x  [x_i, x_i+1]. Дефект =1. Куб. сплайн.: S₃(x)=P_3,i(x)=y_i-1((x–x_i)²(2(x–x_i-1)+h_i)/h_i³)+y_i((x–x_i-1)²(2(x_i–x)+ h_i)/h_i³) + s_i-1((x – x_i-1)(x - x_i)²/h_i²) + s'_i((x – x_i-1)²(x – x_i)/h_i²). Необходимо, чтобы P''_3,i(x_i) = P''_3,i+1(x_i), i = 1, 2, …, n – 1. P''_3,i(x_i) = 2s_i-1/h_i + 4s_i/h_i – 6(y_i – y_i-1)/h_i²; P''_3,i+1(x_i) = - 4s_i/h_i+1 – 2s_i+1/h_i+1 + 6(y_i+1 – y_i)/h_i+1². Эти рав-ва приводят к системе ур-ий отн. s_i: h_i^-1s_i-1+2(h_i^-1+h_i+1^-1)s_i+h_i+1^-1s_i+1 = 3[h_i^-2(y_i – y_i-1) + h_i+1^-2(y_i+1 – y_i)]. Дополняя условиями s₀ = y'(x₀); s_n = y'(x_n) получаем фундаментальный кубич. сплайн. Погрешность кубич. сплайна: y(x) – S₃(x)  cM₄h_max⁴, M₄ = max_{[x0, xn]}y⁽⁴⁾(x).

31. Унимодальные ф-ии.

Ф-ия f(x) наз. унимодальной, если x₁  x₂, то f(x₁)  f(x₂) при x₁, x₂  x_, а если x₁  x₂, то f(x₁)  f(x₂) при x₁, x₂  x^. (аналогично, ф-ия унимодальна, если для всех х  [a, b] f''(x)  0, то ф-ия унимод. на [a, b]. Поиск min: 1. нахождение отрезков унимодальности f(x). 2. Нах. т. мин. с заданной точностью. Необх. условие: y(x)  c²[a, b]; y'(x^) = 0; y''(x^)  0. Утв.: Если f(x) – унимод. на [a, b] и если    и выполнены условия f()  f(), тогда х^  [a, ], если f()  f(), тогда х^  [, b]. Утв.2. Если f(x) – унимод. на [a, b], то также унимодальна на любом [, ]  [a, b].

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 (0)) £ 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 – число итераций.

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

Числа Фибоначи: F_n = F_n-1 + F_n-2, (n ³ 2). (1, 2, 3, 5, 8, 13, …). a^(k) = (F_N-k-1/F_N-k+1)(b^(k) – a^(k)); b^(k) = a^(k) + (F_N-k/F_N-k+1)(b^(k) – a^(k)). 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^(N-1)½ £ D/F_N+1, 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.