3. Алгоритмы приближения функций Если функция y = f(x) задана, то любому допустимому значению x сопоставляется некоторое значение y. Функция может быть. - презентация

1 3. Алгоритмы приближения функций Если функция y = f(x) задана, то любому допустимому значению x сопоставляется некоторое значение y. Функция может быть задана: –Аналитически; –Таблично; –Графически.

2 Пример. Пусть в результате измерений получены результаты, представленные таблицей, t | 0 | 10 | 20 | 30 T | 60 | 90 | 80 | 20 где T=f(t) функция, но эта функция не выражена формулой и известны лишь некоторые значения функции Т для отдельных значений аргумента t. Задача. Найти выражение Т через t посредством формулы, которая позволит вычислять Т для любого значения аргумента t. Данных недостаточно, чтобы при помощи формулы точно выразить функцию f(t), поэтому будем стремиться найти формулу, дающую приближённое выражение этой функции.

3 (t)=at 3 + bt 2 + ct + d(3.1) Коэффициенты a, b, c, d неизвестны и могут быть получены как решение системы уравнений : d=60, 1000a+100b+10c+d=90, 8000a+400b+20c+d=80, 27000a+900b+30c+d=20.

4 Решая эту систему, получим: и d=60. Таким образом, искомый многочлен имеет вид: (3.2) Функцию (3.2) можно считать приближённым аналитическим выражением функции T=f(t): (3.3)

5 Основная идея методов приближения функций Чаще всего удается получить небольшое число значений функции. Для расчетов с использованием этой функции желательно иметь достаточно простую аналитическую зависимость. В этом случае заданную таблично функцию f(x) заменяют приближенной аналитической зависимостью (x), близкой к f(x) в некотором смысле и удобной для вычислений. Различают два основных способа выбора приближения функций: –интерполяцию и –аппроксимацию.

6 Геометрическая интерпретация идеи приближения функции y=f(x) y n y 0 x 0 x 1 x 2 … x n x

7 Геометрическая интерпретация идеи приближения функции f(x) x 0 x 1 x 2 x n x y=f(x) y n y 0

8 Геометрическая интерпретация идеи приближения функции f(x) φ(x) x 0 x 1 x 2 x n x y y n y 0

9 3.1. Использование интерполяции для решения задачи приближения функции Постановка задачи. Пусть функция f(X) задана таблицей ее значений Y 0, Y 1,..., Y n в точках X 0, X 1,..., X n, называемых узлами интерполяции. Задача интерполяции состоит в выборе такой функции (X), которая в узлах X i принимала бы те же значения, что и f(X), т.е. (X i ) =Y i (i = 0, 1, 2, …, n). (3.4)

10 Обычно в качестве интерполирующих функций выбирают многочлены: (3.5) Степень интерполяционного многочлена равна n (на единицу меньше числа узлов).

11 Геометрическая интерпретация приближения функции с использованием аппроксимирующего многочлена y=f(x) y n y 0 x 0 x 1 x 2 … x n x

12 Геометрическая интерпретация приближения функции с использованием аппроксимирующего многочлена Х 0 Х 1 Х 2 Х n Х y y n y 0 f(Х) φ(Х)

13 Геометрическая интерпретация приближения функции с использованием аппроксимирующего многочлена f(Х) φ(Х) Х 0 Х 1 Х 2 Х n Х y y n y 0 Рm(Х)

14 Интерполяционная формула Ньютона Понятие разделенных разностей. Отношения (3.6) где i = 0, 1, 2, …, n –1 называются разделенными разностями первого порядка.

15 Отношения (3.7) называются разделенными разностями второго порядка. Разделенные разности m-го порядка имеют вид: (3.8)

16 Рассмотрим многочлен второй степени: P 2 (X)=f(X 0 )+A 10 (X 0,X 1 ) (X–X 0 )+A 20 (X 0,X 1,X 2 ) (X–X 0 ) (X–X 1 ). Докажем, что в узлах интерполяции вычисленное значение многочлена совпадает со значениями интерполируемой функции в тех же узлах. Результаты подстановки в многочлен значений узлов интерполяции : P 2 (X)=f(X 0 ); P 2 (X)=f(X 0 )+A 10 (X 0,X 1 ) (X–X 0 )= =f(X 0 )+[(f(X 0 )–f(X 1 ))/(X 1 –X 0 )] (X 1 –X 0 )=f(X 1 ); P 2 (X)=f(X 0 )+A 10 (X 0,X 1 ) (X 2 –X 0 )+ +A 20 (X 0,X 1, X 2 ) (X 2 –X 0 ) (X 2 –X 1 )= f(X 2 ).

17 Многочлен степени n P n (X)= f(X 0 )+A 10 (X 0,X 1 ) (X–X 0 )+A 20 (X 0,X 1,X 2 ) (X–X 0 ) (X–X 1 ) + … + A n0 (X 0,X 1,…,X n ) (X–X 0 ) (X–X 1 ) … (X–X n-1 ) (3.9) в точках X 0,X 1,…,X n принимает те же значения, что f(X). Это выражение называется интерполяционным многочленом Ньютона. Для равноотстоящих узлов разделенные разности вычисляются по формуле:,(3.10) где m = 1, 2,…, n–1, h=X m+1 -X m. Тогда, P n (X)=(...((A n0 (X–X n-1 )+A n-1,0 ) (X–X n-2 )+A n-2,0 )...) (X–X 0 )+A 0, где A 0 =Y 1.

18 Интерполяционный многочлен Лагранжа Интерполяционным многочленом Лагранжа называется многочлен вида: (3.11) Составление этого многочлена основано на одновременном введении в вычисления всех узлов интерполяции. Коэффициентами Лагранжа называются функции: (3.12) Причем (3.13)

19 Пример 3.1. Получить приближение функции f(x) для аргумента x=1,5 методом Лагранжа. xy

20 xy

21 3.1.3 Погрешность интерполяции При решении задачи приближения функции всегда можно записать равенство: f(X)=L n (X)+R n (X),(3.14) где R n (X) – остаточный член, то есть погрешность интерполяции. Получим выражение остаточного члена R n (X) в предположении, что f C n+1 [a,b] (принадлежит классу функций, определенных на [a,b] в (n+1)-ой точке), где [a,b] отрезок, содержащий узлы интерполяции X i и точку X.

22 Будем искать остаточный член R n (X) в следующем виде: R n (X)=W n (X) r n (X), (3.15) где W n (X)=(X–X 0 ) (X–X 1 )... (X X n ), (3.16) r n (X) – некоторая функция, значения которой в узлах интерполяции X i можно задавать какие угодно, т. к. R n (X i )=0 и W n (X i ) = 0, i =0, 1, 2, …, n.

23 Зафиксируем произвольное значение X [a,b] (X X i ) и рассмотрим функцию, зависящую от переменной t: (t) =[L n (t)+W n (t) r n (X)] – f(t). (3.17) (t)=0 при t=X i и t=X, т. е. в (n+2)–х точках отрезка [a,b], на котором изменяется t.

24 Теорема Ролля. Если функция f (X) непрерывна на отрезке [a, b] и дифференцируема внутри этого интервала и f(a)=f(b), то найдется точка c [a, b] такая, что f(c) = 0. Функция t обращается в ноль, по крайней мере, в (n+1)-й точке интервала (a,b), функция t равна нулю минимум в n точках этого интервала и так далее. Таким образом, найдется хотя бы одна точка (a,b), в которой t (n+1)( ) = 0.

25 Отсюда и из (3.17), учитывая, что L n (n+1) (X)( )=0, W n (n+1) ( )=(n+1)!, получим: (n+1)! r n (X)–f (n+1) ( )=0. Следовательно, r n (X)= f (n+1) ( )/(n+1)! и в соответствии с (3.14) и (3.15) R n (X)=W n (X) f (n+1) ( )/(n+1)!, (3.18) f(X)=L n (X)+[W n (X) f (n+1) ( )/(n+1)!], (3.19) где = (X) [a, b] – некоторая неизвестная точка.

26 Из равенства (3.18) вытекает оценка погрешности интерполяции в текущей точке x [a, b]: (3.20) и оценка максимальной погрешности интерполяции на всем отрезке [a, b]: (3.21) где

27 Если на отрезке [a,b] производная f (n+1) меняется слабо, то величина абсолютной погрешности |f(x)-L n (x)| определяется значением функции ω n (x). Типичный характер поведения функции ω n (x) ω x x 0 x 1 x 2 x 3 x 4 x 5 Y= ω 5 (x)

28 Пусть h i =x i+1 x i,, а h max =max (h i ) для 1 i n. Тогда, огрубив оценку (3.21), получим:. Таким образом, интерполяция многочленом степени n имеет (n+1)-й порядок точности относительно h max.

29 Пример 3.2. Необходимо оценить погрешность приближения f(x)= x в точке x=116 на отрезке [a, b], где a=100, b=144 с помощью интерполяционного многочлена Лагранжа L 2 (x), построенного с узлами X 0 =100, X 1 =121, X 2 =144.

30 Решение. Т. к. n=2, необходимо найти максимальное значения производной 3-го порядка. Производные заданной функции до третьего порядка включительно: Функция f (X) на отрезке [100, 133] принимает максимальное значение в точке Х=100:

31 На основании (3.15): В силу оценки (3.21):

32 Погрешность интерполяции на основе применения многочлена Ньютона В точке XX i погрешность интерполяции, проводимой на основе применения многочлена Ньютона, сопоставима со значением (n+1)-го члена в записи многочлена Ньютона: f(X)–P n (X)A(X 0,X 1 …,X n+1 )(X–X 0 )(X–X 1 )…(X–X n ). P n+1 (Х) – P n (Х)=A(X 0, X 1,…, X n+1 ) W n (Х).

33 Если функция f(X) достаточно гладкая и величина |X n+1 –X n | мала, то справедливо приближённое равенство: A(X 0, X 1,…, X n )A(X 0, X 1,…, X n+1 ) и тогда f(X) – P n (X) P n+1 (X) – P n (X). В этом случае значение абсолютной погрешности интерполяции Δ=|P n+1 (X)–P n (X)|. (3.22)