числаки. Название билета и его решение
 Скачать 3.03 Mb.
|
|
Теорема.2 (Вейерштрасса) Пусть функция ) (x f непрерывна на отрезке b a, . Тогда для любого 0 ) (x P n степени ) ( n n = такой, что − ) ( ) ( max ] , [ x P x f n b a Естественно предположить, что увеличивая количество узлов интерполяции, т.е. увеличивая степень интерполяционного многочлена, можно приблизить функцию как угодно точно. Однако ряд примеров показывает, что даже при большом числе узлов интерполяционный многочлен Лагранжа не гарантирует хорошее приближение функции. С.Н.Бернштейн доказал, что последовательность многочленов Лагранжа, построенная для непрерывной функции x x f = ) ( по равноотстоящим узлам (равномерная сетка) на отрезке 1 , 1 − , не сходится при возрастании числа узлов к ) (x f ) (x L x n − не стремится к нулю при → n Замечательный пример построен Карлом Рунге. Рунге рассмотрел бесконечно дифференцируемую функцию 2 25 1 1 ) ( x x R + = (ее называют функцией Рунге). Последовательность интерполяционных полиномов Лагранжа, построенная по равноотстоящим узлам, не сходится к функции Рунге по равномерной норме. Более того, для обоих примеров установлено, что = − − → ) ( ) ( max lim 1 , 1 x L x f N x N , а для функции Рунге показано, что 58 ) ( ) ( max 20 1 , 1 − − x L x R x Однако проблема сходимости для этой функции исчезает, если в качестве узлов интерполяции брать корни многочлена Чебышева ) ( 1 x T n+ Погрешность интерполяции функции Рунге многочленом Лагранжа, построенным по чебышевским узлам, стремится к нулю с ростом степени интерполяционного многочлена. Теорема 3.(Фабера) Какова бы ни была стратегия выбора узлов интерполяции, найдется непрерывная на отрезке b a, функция f , для которой = − → ) ( ) ( max lim , x P x f N b a x N Теорема Фабера отрицает наличие единой стратегии выбора узлов интерполяции для непрерывных функций. Теорема 4. Пусть в качестве узлов интерполяции на отрезке b a, выбираются чебышевские узлы. Тогда для любой непрерывно дифференцируемой на отрезке b a, функции f метод интерполяции сходится. Пусть на отрезке [ a , b ] заданы значения функции y = f(x) в точках ax 0 <x 1 <x 2 <…<x n b: f(x 0 ) = y 0 , f(x 1 ) = y 1 , f(x 2 ) = y 2 , … , f(x n ) = y n def: Интерполяция — нахождение многочлена не выше n-ой степени: P n (x) = a 0 x n + a 1 x n-1 + a 2 x n-2 + … + a n-1 x + a n (1) который в точках x 0 , x 1 , x 2 ,…, x n принимает те же значения, что и данная функция, т.е. выполняются равенства: P n (x i ) = f(x i ) = y i , i = 0, 1, 2, …,n. (2) Другими словами, интерполяция – нахождение многочлена вида (1), который на отрезке [ a , b ] являлся бы приближением для функции y = f(x). Многочлен (1) называется интерполяционным многочленом , точки x 0 , x 1 , x 2 , …, x n . – узлами интерполяции Интерполяция дает возможность находить приближенные значения функции f(x) в точках x, лежащих между узлами интерполяции, когда функция задана только в точках x 0 , x 1 , …, x n . А т.ж. когда функция задана формулой на всем отрезке [ a , b ], но вычисление ее значений по этой формуле очень трудоемко. 4 Интерполяция функций. Постановка задачи. Интерполяционный полином в форме Ньютона (вывод формулы) 5 Интерполяция с кратными узлами. Постановка задачи. Интерполяционный полином Эрмита (вывод формулы) 2.1.7.1 Интерполяционный многочлен с кратными узлами Иногда в узлах x i (i = 0, 1, ..., m) бывают заданы не только значения y i = f (x i ) функции f, но и значения ее производных y i ' = f ’ (x i ), y i " = f (x i ), ..., ( ) y i k i −1 = ( ) f k i −1 (x i ) до некоторого порядка k i – 1. В этом случае узел x i называют кратным, а число k i , равное количеству заданных значений, – кратностью узла. Пусть n = k 0 + k 1 + k m – 1. Можно доказать, что существует единственный многочлен P n (x) степени n, удовлетворяющий условиям P n (x i ) = y i , P n ' (x i ) = y i ' , ..., ( ) P n k i −1 (x i ) = ( ) y i k i −1 для всех i = 0, 1, ..., m. Этот многочлен называют интерполяционным многочленом с кратными узлами. Отметим два важных случая. 1 Пусть на концах отрезка [x 0 , x 1 ] заданы значения y 0 , y 1 , y 0 ' , y i ' . Тогда m = 1, k 0 = 2, k 1 = 2, n = 3 и интерполяционный многочлен P 3 (x), удовлетворяющий условиям P 3 (x 0 ) = y 0 , P 3 ' (x 0 ) = y 0 ' , P 3 (x 1 ) = y 1 , P 3 ' (x 1 ) = y i ' , может быть представлен в следующем виде: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 3 0 1 2 0 3 0 1 2 0 2 1 0 2 1 3 1 0 2 1 2 2 2 x y x x x x h h y x x x x h y x x x x h h y x x x x h = − − + + − − + + − − + + − − ' ' , (1.37) где h = x 1 – x 0 . Многочлен (1.37) принято называть кубическим интерполяционным многочленом Эрмита. 2 Пусть в точке x 0 заданы значения y 0 , y 0 ' , ( ) y 0 n . Тогда многочлен P n (x), удовлетворяющий условиям P n (x 0 ) = y 0 , P ' n (x 0 ) = y 0 ' , ..., ( ) P n n (x 0 ) = ( ) y 0 n представляется в следующем виде: ( ) n k k n k x y x x k ( ) ! ( ) = − = 0 0 0 . (1.38) Многочлен P n (x) представляет собой отрезок ряда Тейлора. Таким образом, формула Тейлора дает решение задачи интерполяции с одним узлом кратности n + 1. 2.1.7.2 Погрешность интерполяции с кратными узлами Пусть функция f дифференцируема n + 1 раз на отрезке [a, b], содержащем узлы интерполяции x i (i = 0, 1, ..., m). Тогда для погрешности интерполяции с кратными узлами в точке x [a, b] справедливы равенство (1.27) и неравенств (1.28), в которых n+1 (x) = (x − x 0 ) k 0 (x − x 1 ) k 1 (x − x m ) k m , а − некоторая точка, принадлежащая интервалу (a, b). Для формулы Тейлора (m = 0, k 0 = n + 1) известна формула остаточного члена в форме Лагранжа. Для кубического многочлена Эрмита (m = 1, k 0 = 2, k 1 = 2) оценка погрешности имеет вид: max f (x) – P 3 (x) 4 4 384 h . (1.39) [x 0 , x 1 ] Здесь учтено, что максимум функции 4 (x) = (x – x 0 ) 2 (x – x 1 ) 2 на отрезке [x 0 , x 1 ] достигается в точке x = (x 0 + x 1 )2 и равен h 4 16. 6 Кусочная интерполяция при помощи сплайнов. Постановка задачи. Кусочнопостоянная и кусочно-линейная интерполяция. Дефект сплайна. Кусочно-квадратичная интерполяция дефекта 2. Квадратичный сплайн дефекта 1 и граничные условия (без решения системы с трехдиагональной матрицей) Кусочная интерполяция Далеко не всегда приходится иметь дело с очень гладкими функциями. В связи с этим часто применяется кусочная интерполяция - для приближения функции в точке x строится полином невысокой степени по данным в табличных точках, ближайшим к т. x Пример. Необходимо вычислить ) (x f для 1 ; + i i x x x Кусочно-линейная интерполяция Для вычисления ) (x f используется линейное приближение ( ) i x x h i f i f i f x f − − + + 1 ) ( , где i i x x h − = +1 Очевидно, что при подстановке i x x = или 1 + = i x x получается тождество. Кусочно-квадратичная интерполяция. Привлекается еще одна табличная точка ( 1 − i x или 2 + i x ), и строится полином второй степени: ( )( ) 1 2 1 1 1 2 2 ) ( ) ( + − + + − − + − + − − + i i i i i i i i i x x x x h f f f x x h f f f x f Очевидно, что при подстановке i x x = , или 1 + = i x x , или 1 − = i x x , получается тождество. Кусочно-кубическая интерполяция. ( )( ) ( )( )( ) 1 1 3 1 1 2 1 2 1 1 1 6 3 3 2 2 ) ( ) ( + − − + + + − + + − − − − + − + − − + − + − − + i i i i i i i i i i i i i i i i x x x x x x h f f f f x x x x h f f f x x h f f f x f Нетрудно убедиться, что при 1 − i f , i f , 1 + i f , 2 + i f в последних двух формулах стоят биномиальные коэффициенты. Более высокие степени ИП для КИ, как правило, не используют. Узлы интерполяции при кусочной интерполяции берутся вблизи интересующего нас узла i x Возможные обобщения приближения функций с помощью интерполяции. По аналогии с ИП ( ) n n n x a x a a x P + + + = 1 0 можно искать приближение таблично заданной функции в виде обобщенного ИП: ( ) ( ) ( ) ( ) x a x a x a x P n n n φ φ φ 1 1 0 0 + + + = по системе линейно независимых функций ( ) n k x k ,..., 1 , 0 : φ = Исходя из условий интерполяции (совпадения значения полинома с табличными значениями функции), для неопределенных коэффициентов i a получим систему линейных уравнений: ( ) ( ) ( ) i i n n i i f x a x a x a = + + + φ φ φ 1 1 0 0 , n i ,..., 1 , 0 = Для существования и единственности решения необходимо, чтобы детерминант удовлетворял условию ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 0 φ φ φ φ φ φ φ φ φ 1 0 1 1 1 1 0 0 0 1 0 0 = n n n n n n x x x x x x x x x Например, периодическую функцию может оказаться удобно приближать в виде полинома по системе функций ( ) ( ) ( ) n m m k kx kx x k = + = = ) 1 2 ( ; ,..., 2 , 1 , cos , sin , 1 - это тригонометрическая интерполяция. Часто используется, если функция разложима в ряд Фурье. Если в табличных точках заданы не только значения функции, но и ее производные, то для приближения функции используются полиномы Эрмита. Для построения используется следующие условия: • В табличных точках полином принимает заданные значения; • Производные от полинома также принимают заданные значения. В таких случаях полиномы Эрмита обеспечивают лучшее приближение сравнительно с обычной интерполяцией 7 Кусочная интерполяция при помощи сплайнов. Постановка задачи. Кубический сплайн дефекта 1 и граничные условия (без решения системы с трехдиагональной матрицей). Теорема о скорости сходимости кубического сплайна дефекта 1 в применении к гладким функциям (без доказательства) Кубический сплайн дефекта 1 Это сплайны, которые произошли от гибкой линейки чертёжника при этом в узлах непрерывна должна быть 1-ая и 2-ая производная. ( ) x M y EJ = уравнение изогнутой оси балки, когда заданы изгибные моменты в каждой точке. По аналогии 2-ые производные будем называть моментами. ( ) ( ) x S x S 3 1 , 3 = Пусть в n попарно различных точках отрезка [a,b] a x n =b y 1 =f(x 1 )…. Y n =f(x n ) ( ) x S 3 непрерывен на [a,b] вместе с 1-ой и 2-ой производной, совпадает с кубическим полиномом на каждом из отрезков и удовлетворяет условиям ( ) i i y x S = 3 i=1..n Поскольку 2ая производная по условию в каждом узле непрерывна, то введя обозначения ( ) i i x S M 3 = i=1,2…n и предположив, что ( ) i x S 3 меняется линейно на интервале 1 , + i i x x можно записать ( ) i i i i i i h x x M h x x M x S − + − = + + 1 1 3 (1) i i i x x h − = +1 Проинтегрируем дважды (1). Интегрирование будем выполнять со скобкой. Тогда после 1-го интегрирования получим ( ) i i i i i i i i i i i i h M M h y y h x x M h x x M x S − − − + − + − − = + + + + 6 2 ) ( 2 ) ( 1 1 2 1 2 1 3 (2) А после второго интегрирования получим ( ) i i i i i i i i i i i i i i i i h x x h M y h x x h M y h x x M h x x M x S − − + − − + − + − = + + + + + ) 6 ( ) 6 ( 6 ) ( 6 ) ( 2 1 1 1 2 3 1 3 1 3 (3) Это выражение мы получили для отрезка 1 , + i i x x , аналогичное выражение мы можем получить для предыдущего отрезка ( ) 1 1 1 1 1 2 1 1 2 1 3 6 2 ) ( 2 ) ( − − − − − − − − − − − + − + − − = i i i i i i i i i i i i h M M h y y h x x M h x x M x S (4) Используя условие непрерывности 1-ой производной для узла x i Для этого приравняем (2) при x=x i к выражению (4) при x=x i . В результате получим 1 1 1 1 1 1 1 6 3 6 − − + + − − − − − − = + + + i i i i i i i i i i i i i h y y h y y h M h h M h M (5) i h i h i h i b + − = 1 (6) i c i M i b i M i M i a = + + + − 1 2 1 (7) i=2,3…n-1 Т.е. мы получили n-2 линейных алгебраических уравнения относительно M i Для замыкания этой системы нужно задать 2 дополнительных уравнения. Эти уравнения можно получить используя условие на концах интервала [a,b] (краевые условия) 1.Периодический сплайн T=b-a. При этом предполагается, что интерполируемая функция периодическая с T=b-a и поэтому сам сплайн тоже должен быть периодическим с таким же периодом. Запишем условия периодичности: ( ) ( ) b S a S 3 3 = ( ) ( ) b S a S 3 3 = ( ) ( ) b S a S 3 3 = Тогда можно потребовать, чтобы уравнение (7) было справедливо и для i=n, а условие периодичности примет вид 1 Y Y n = 1 M M n = 2 1 h h = 2 1 Y Y n = + 2 1 M M n = + Тогда уравнение (7) примет вид = + + + − = = + i c i M i b i M i M i a M M M M n n 1 2 1 2 1 1 (8) 2.Непериодический сплайн с заданными наклонами в т a и b ( ) 1 3 Y a S = заданное число ( ) n Y b S = 3 заданное число Запишем уравнение (2) при i=1 ( ) 1 1 1 2 1 2 1 ` 6 2 C Y Y Y h M M = − − = + Если записать уравнение (3) при i=n n n n n n n n n C h Y Y Y h M M = − − = + − − − − 1 1 1 1 6 2 Тогда замыкающая система примет вид = + + = + + + − = + n c n M n M i c i M i b i M i M i a c M M 2 1 1 2 1 1 2 1 2 (9) Решив системы 8 и 9 можно найти неизвестные M 1 …..M n и можем построить сплайн в соответствии с формулой (3) i b i a − = 1 i h i h i h i y i y i h i y i y i c + − − − − − − + = 1 1 1 1 6 В некоторых случаях более удобно записывать сплайн в виде набора коэффициентов кубических полиномов вида ( ) ( ) ( ) ( ) 3 3 2 2 1 3 i x x i d i x x i d i x x i d i y x S − + − + − + = , где 2 2 i M i d = i h i M i M i d − + = 1 3 ( ) 1 2 6 1 1 + + − − + = i M i M i h i h i y i y i d i=1,2..n-1 8 Кусочная интерполяция при помощи сплайнов. Постановка задачи. Кусочные полиномы Эрмита 9 Приближение данных. Постановка задачи. Используемые для приближения модели (линейные и нелинейные, примеры). Критерий приближения — наименьшие квадраты. Вывод соответствующей СЛАУ на примере приближения полиномом второй степени. Условие невырожденности матрицы данной СЛАУ |