Учебник - Практические занятия по вычислительной математике - Аристова (1238839), страница 21
Текст из файла (страница 21)
Может ли применение методов исключения отрезков привести кневерному определению точки минимума x*, если f (x) не унимодальна?Ответ пояснить рисунком.V.6.10. Зависит ли точность определения точки минимума x*, которуюгарантируют методы дихотомии и золотого сечения в результате N вычислений f (x), от конкретной функции f (x)?V.6.11. Требуется найти точку минимума унимодальной функции на отрезке длины 1 с точностью ε = 0,02. Имеется возможность измерить неболее 10 значений f (x). Какой из прямых методов минимизации можноиспользовать для этого?V.6.12.
Указать класс функций, для точного определения точек минимума которых достаточно одной итерации метода парабол.V.6.13. В окрестности точки минимума x* график функции f (x) близок ксимметричному относительно вертикальной оси, проходящей через точку x*. А график функции g (x) заметно асимметричен. Для какой из этихфункций следует ожидать более высокой скорости сходимости методапарабол?V.7.
Практические задачиV.7.1. Используя методы дихотомии и сведения вариационной задачи кзадаче алгебраического уравнения, найти точку локального минимумафункции:а) f ( x) 2 x2 ln x,137V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИб) f (t ) t 3 / 3 t 2 ,в) f (t ) t 4 / 4 2t 2 ,2г) f (t ) tet /2 ,д) f (t ) 3t 4 8t 3 6t 2 ,е) f (t ) (t 5)et ,ж) f (t ) (t 2 3) / (t 2).V.7.2. Найти минимум функции y = x4 + e - x, x [0, 1] методом парабол.V.7.3. Найти минимум функции y = xx методом исключения отрезков.V.7.4. Для нахождения минимума функции f (x) сделать один шаг модифицированного метода Брендта от заданного начального приближения:а) f ( x) 10 x (2 ln x)2xx1 = 6.x2 = 7.x3 = 8.x4 = 9.f(x) 2.60185 0.20480 0.50488 3.50078.б) f ( x) 1 x e xxx1 = 0.5f(x)3.64872x2 = 0.753.45033x3 = 1.03.71828x4 = 1.254.29034в) f ( x) 1 x cos x 2xx1=1.0f(x)1.54030x2=1.50.03849x3=2.0–0.15364x4=2.51.39945x3=0.93.67853x4=1.34.10087г) f ( x) 1 x 4ln( x 1)xx1=0.1f(x)10.38124x2=0.53.62186д) f ( x) x sin xxx1=3.5f(x)1.52005x2=4.01.24320x3=4.51.14379x4=5.1.27715е) f ( x) ( x 1)2 arctg xxx1=0.f(x)1x2=0.50.71365x3=1.00.78540x4=1.51.23279138V.7.
Практические задачиОтвет.а) Парабола по точкам 1–2–4 имеет минимум в точке x5 = 7.38888,y5 = =4.19710–8, а по точкам 1–3–4 в точке x6 = 7.38752, y6 = 3.19310–6. Вследующем приближении остаются точки 2–6–5–3.б) Парабола по точкам 1–2–4 имеет минимум в точке x5 = 0.74530, апо точкам 1–3–4 в точке x6 = 0.72572. Сносов точек 5 и 6 нет,y5 = 3.448815, y6 = 3.44416.
В следующем приближении остаются точки1–6–5–2.в) Парабола по точкам 1–2–4 имеет минимум в точке x5 = 1.76613, апо точкам 1–3–4 в точке x6 = 2.06572. Сносов точек 5 и 6 нет,y5 = –0.43354, y6 = 0.05346. В следующем приближении остаются точки2–5–3–6.г) Парабола по точкам 1–2–4 имеет минимум в точке x5 = 0.87947, апо точкам 1–3–4 в точке x6 = 1.03285. Сносов точек 5 и 6 нет,y5 = 3.66101, y6 = 3.80595.
В следующем приближении остаются точки1–2–5–3.д) Парабола по точкам 1–2–4 имеет минимум в точке x5 = 4.36467, апо точкам 1–3–4 в точке x6 = 4.43883. Сносов точек 5 и 6 нет,y5 = 1.14903, y6 = 1.14404. В следующем приближении остаются точки5–6–3–4.е) Парабола по точкам 1–2–4 имеет минимум в точке x5 = =0.64340,а по точкам 1–3–4 в точке x6 = 0.64508. Сносов точек 5 и 6 нет,y5 = 0.69888, y6 = 0.69887. В следующем приближении остаются точки2–5–6–3.V.7.5. Методом покоординатного спуска найти точки локального минимума функцийа) f ( x, y) ( x2 y 11)2 ( x y 2 7)2 ,б) f ( x, y) ( x2 y 2 1)2 ( y x sin x)2 ,в) f ( x, y) x3 8 y3 6 xy 1,г) f ( x, y) ( x 3)2 ( y 2)2 ( x y 4)2 ,д) f ( x, y) 2 x3 xy 2 5x 2 y 2 .V.7.6.
Найти точку локального минимума функции:а) f ( x, y) 3x2 2 x y y 8x 8,б) f ( x, y) x3 8 y3 6 xy 1,139V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИв) f ( x, y) x2 y 2 xy x y 1,г) f ( x, y) 2 x3 xy 2 5x2 y 2 .V.8. Библиографический комментарийИзложение[3, 5, 19, 27].теоретическогоматериаласледуетпособиямМетодам оптимизации посвящена обширная литература, например, авторов, читавших курсы методов оптимизации в МФТИ в разные годы[28–30]. Модифицированный метод Брендта описан в [31, 32].140VI. ТАБЛИЧНОЕ ЗАДАНИЕИ ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙVI.1.
Задача интерполяцииЗадача интерполяции состоит в нахождении обобщенного многочленаnPn ( x) ck k ( x),(1.1)k 0где φk(x) – фиксированные функции, а значения коэффициентов определяются из условия равенства со значением приближаемой функции вузлах интерполяции:Pn ( xk ) f k ,k 0, 1,, n.(1.2)Набор точек xj на интервале [a, b], a ≤ x0 <x1<…< xn ≤ b, в которыхзаданы значения функции f (xj), называют сеткой.
Множество точек xjиногда также называют узлами сетки или узлами интерполяции.Сетка называется равномерной, еслиxj + 1 – xj = h = const, j = 0, 1, … , n – 1; a = x0, b = xn.Если φk(x) = xk, то соответствующая интерполяция называется алгебраической, если φk – тригонометрические функции, то говорят отригонометрической интерполяции.Если построенный обобщенный полином (1.1) используется длявосстановления функции на всем отрезке [a, b], то говорят о глобальнойинтерполяции. Если же для восстановления функции между каждымидвумя соседними узлами строится многочлен заданной невысокой степени, то говорят о кусочно-многочленной интерполяции.Если значения функции f (x) заданы в узлах xj на интервале [a, b],a ≤ x0 <x1<…< xn ≤ b, то говорят, что функция f(x) задана таблицей.141VI.
ТАБЛИЧНОЕ ЗАДАНИЕИ ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙVI.2. Алгебраическая интерполяцияТеорема 1. Пусть заданы n + 1 узел x0, x1, …, xn, среди которыхнет совпадающих, и значения функции в этих узлах f(x0), f(x1), …, f(xn).ТогдасуществуетодинитолькоодинмногочленPn(x) = Pn(x, f, x0, x1, …, xn) степени не выше n, принимающий в узлах xkзаданные значения f (xk).Интерполяционный многочлен можно записать (и соответственновычислить) различными способами представляя его в виде разложенияпо степеням x (в форме Лагранжа и в форме Ньютона) или в виде разложения по ортогональным многочленам.VI.2.1. Непосредственноевычислениеинтерполяционного полиномакоэффициентовПолином степени n можно записать в виде(2.1)где a0, …, an – неопределенные коэффициенты. Их можно определить изn + 1 условия:Pn ( x) a0 a1 x a2 x 2 ...
an x n ,a0 a1 x0 a2 x02 an x0n f ( x0 ),a0 a1 x1 a2 x12 an x1n f ( x1 ),................................................................a0 a1 xn a2 xn2 (2.2) an xnn f ( xn ).Определитель системы (2.2) есть детерминант Вандермонда, известный из курса линейной алгебры. Его значение в случае, когда выполняются условия теоремы 1, отлично от нуля, что доказывает существование и единственность полинома.
Эта линейная система во многихслучаях является плохо обусловленной. Последнее связано с тем, чтопоследовательные степени 1, x, x2, …, xn «почти линейно зависимы» наинтервале 0 < x < 1. Напомним, что обусловленность линейной системыAy = b определяется числом(2.3) || A || || A1 || .Это число определяет относительную погрешность решения системы взависимости от относительной погрешности правой части b:142VI.2.2.
Интерполяционный полином в форме Лагранжа. Интерполяционныймногочлен в форме Ньютона|| δy |||| y |||| δb |||| b ||(2.4).VI.2.2. Интерполяционный полином в форме Лагранжа. Интерполяционный многочлен в форме НьютонаВведем вспомогательные многочленыlk( x x0 ) ( x xk 1)( x xk 1) ( x xn ).k x0 ) ( xk xk 1)( xk xk 1) ( xk xn ) (x(2.5)Многочлен Pn(x), заданный равенствомPn ( x) Pn ( x, f , x0 , x1 , f ( x1 ) l1 ( x) , xn ) f ( x0 ) l0 ( x) (2.6) f ( xn ) ln ( x),есть интерполяционный многочлен в форме Лагранжа.Употребляются и другие виды записи интерполяционного многочлена. Часто используется запись в форме Ньютона.Рекурсивно определим разделенные разности.Разделенной разностью нулевого порядка f (xk) функции f (x) в точкеxk назовем значение функции в этой точкеf(xk) = f(xk).Разделенной разностью первого порядка f(xk, xt) функции f (x) дляпроизвольной пары точек xk, и xt определим через разделенные разностинулевого порядка:f ( x k , xt ) f ( xt ) f ( x k )xt x k.(2.7)Разделенную разность f (x0, x1, …,xn) порядка n определим через разделенную разность порядка n – 1, положивf ( x0 , x1 ,, xn ) f ( x1 ,, xn ) f ( x0 ,xn x0, xn 1 ).(2.8)Интерполяционный многочлен в форме Ньютона Pn(x, x0, x1, …, xn)может быть записан через разделенные разности следующим образом:Pn ( x, f , x0 , x1 ,, xn ) f ( x0 ) f ( x0 , x1 )( x x0 ) 143VI.
ТАБЛИЧНОЕ ЗАДАНИЕИ ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ f ( x0 , x1 , x2 )( x x0 )( x x1 ) f (x0 , x1 ,, xn )(x x0 )(x xn1 ) .(2.9)Если x0 < x1 < … <xn, то соответствующую интерполяцию называютинтерполяцией вперед; в случае x0 > x1 > … > xn интерполяцию называют интерполяцией назад.Теорема 2. Интерполяционный многочлен в форме Ньютона эквивалентен интерполяционному многочлену в форме Лагранжа.VI.2.3. Формула для погрешности алгебраической интерполяцииОценим погрешность Rs(x) = f(x) – Ps(x, f), xk < x <xk+1, возникающуюпри приближенной замене f (x) алгебраическим многочленом Ps(x, f). Воснове оценки лежит следующая общая теорема о формуле погрешности.Теорема 3. Пусть f (t) – функция, определенная на некотором отрезке α < t < β и имеющая производные до некоторого порядка s + 1включительно.Пусть t0, t1, …, ts – произвольный набор попарно различных точек изотрезка [α, β], f (t0), f (t1), …, f (ts) – значения функции f (t) в этих точках;Ps(t) – интерполяционный многочлен степени не выше s, построенный поэтим значениям.