числаки. Название билета и его решение
 Скачать 3.03 Mb.
|
|
метод сопровождающей матрицы (companion matrix). Можно доказать, что матрица 1 2 0 1 1 0 0 0 0 1 0 0 0 0 1 0 n n n n n n a a a a a a a a − − − − − − = A , называемая сопровождающей матрицей для полинома 0 ( ) n i i i P x a x = = , имеет собственные значения равные корням полинома. Напомним, что собственными значениями матрицы называются такие числа , для которых выполняется равенство = Ax x или ( ) det( ) 0 P x = − = A I . Существуют весьма эффективные методы поиска собственных значений, о некоторых из них мы будем говорить далее. Таким образом, задачу поиска корней полинома можно свести к задаче поиска собственных значений сопровождающей матрицы. 2 Решение алгебраических и трансцендентных уравнений. Постановка задачи. Понятие о скорости сходимости численных методов. Теоремы о сходимости метода Ньютона и секущих (без доказательства). Теорема о сходимости метода простых итераций с доказательством 3 Интерполяция функций. Постановка задачи. Интерполяционный полином в форме Лагранжа: вывод формулы, поведение ошибки интерполяции. Интерполяция по чебышевским узлам. Теорема Фабера (без доказательства) и пример Рунге. Теорема о сходимости по чебышевским узлам (без доказательства). Постановка задачи приближения функций. Необходимо вычислить значение функции y=f(x). Для элементарных, а также для основных специальных функций разработаны быстрые и надежные алгоритмы, реализованные в виде стандартных программ математического обеспечения ЭВМ. Однако в расчетах нередко используются и другие функции, непосредственное вычисление которых затруднено по каким-либо причинам. Укажем на типичные ситуации. 1. Функция задана таблицей своих значений: n i x f y i i ,... 1 , 0 ), ( = = , а вычисление производится в точках x ,не совпадающих с табличными. 2. Непосредственное вычисление значения y=f(x) связано с проведением сложных расчетов и приводит к значительным затратам машинного времени. Возникающие проблемы удается решить следующим образом. Функцию f(x) приближенно заменяют функцией g(x) , вычисляемые значения которой и принимают за приближенные значения функции f. Такая замена оправдана лишь в случае, когда значения g(x) вычисляются быстро и надежно, а погрешность приближения f(x) -g(x) достаточно мала. При постановке задачи необходимо: 1. Какая информация о функции f может использоваться как входные данные для вычисления приближения g.(Таблица значений функции, таблица значений ее производных.) 2. Дополнительная априорная информация о приближаемой функции( f «достаточно гладкая», периодическая, монотонная, четная) 3. Знание свойств функции f позволяет осознанно выбрать класс G аппроксимирующих функций. 4. Необходим критерий выбора в классе G конкретной аппроксимирующей функции g, являющейся в смысле этого критерия наилучшим приближением к функции f. Постановка задачи интерполяции. Типичной задачей приближения функций является задача интерполяции. Функция ) (x f задана своими значениями в точках N i b a x i ..., , 1 , 0 , , = : ( ) ( ) i i x f x , Требуется найти функцию ) ..., , , ; ( ) ( 1 0 N x x x x g x g = , удовлетворяющую условиям ) ( ) ..., , , , ( 1 0 i N i x f x x x x g = , N i ..., , 1 , 0 = Другими словами, ставится задача о построении функции g, график которой проходит через заданные точки ( ) ( ) i i x f x , Точки N i b a x i ..., , 1 , 0 , , = называют узлами интерполяции, а функцию ) ..., , , , ( 1 0 N x x x x g — интерполирующей функцией, в частности, если интерполирующая функция — многочлен, то говорят об интерполяционных многочленах. В дальнейших расчетах для b a x , полагают ) ( ) ( x g x f . Величина ) ( ) ( max ] , [ x g x f b a − называется погрешностью интерполяции. Экстраполяция. В случае, когда интерполяция используется для вычисления значения функции f в точке x не принадлежащей отрезку наблюдения b a x , , говорят, что осуществляется экстраполяция. Этот метод часто используют при прогнозировании характера протекания тех или иных процессов. Задача интерполяции обобщенными многочленами. Классическое решение задачи интерполяции — построение обобщенного многочлена ( ) = = N i i i N x x 0 ) ( , где ) (x i — заданные базисные функции, а i — параметры модели, коэффициенты обобщенного многочлена. Назовем обобщенный многочлен интерполяционным, если он удовлетворяет условию n i y x i i N ,..., 1 , 0 , ) ( = = , или, что то же самое, системе линейных алгебраических уравнений 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 1 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) N N N N n n N n N n x a x a x a y x a x a x a y x a x a x a y + + + = + + + = + + + = относительно коэффициентов N a a a ,..., , 1 0 Опр. Система функций N ,..., , 1 0 линейно зависима в точках n x x x ,..., , 1 0 , если один из векторов j системы N ,..., , 1 0 может быть представлен в виде линейной комбинации остальных векторов системы: = = N j k k k k j , 0 , где N j x x x T n j j j j ,..., 1 , 0 , )) ( ),..., ( ), ( ( 1 0 = = В противном случае систему функций N ,..., , 1 0 будем называть линейно независимой в точках n x x x ,..., , 1 0 Замечание. Система функций n x x x ,..., , , 1 2 линейно независима в точках n x x x ,..., , 1 0 Интерполяционный многочлен Лагранжа. Рассмотрим задачу интерполяции алгебраическим многочленом ( ) = = n i i i n x x P 0 ) ( , где i i x x = ) ( Если выполняется условие n i y x P i i n ,..., 1 , 0 , ) ( = = , то многочлен степени n называется интерполяционным многочленом. Это равенство можно записать в виде системы уравнений 2 0 1 0 2 0 0 0 2 0 1 1 2 1 0 1 2 0 1 2 n n n n n n n n n n a a x a x a x y a a x a x a x y a a x a x a x y + + + + = + + + + = + + + + = относительно коэффициентов многочлена. Эта система однозначно разрешима. Приведем одну из форм записи интерполяционного многочлена - интерполяционный многочлен Лагранжа. Интерполяционный многочлен Лагранжа имеет вид: = = n i ni i n x x f x L 0 ) ( ) ( ) ( , = − − = n i k k k i k ni x x x x x 0 ) ( , или, что то же самое, ( )( ) ( )( ) ( ) ( )( ) ( )( ) ( ) 0 1 1 1 0 0 1 1 1 ( ) ( ) N i i N N i i i i i i i i i N x x x x x x x x x x L x f x x x x x x x x x x x − + = − + − − − − − = − − − − − Интерполяционный многочлен Лагранжа — многочлен N-й степени, для которого справедливо ) ( ) ( i N i x L x f = , N i ..., , 1 , 0 = В инженерной практике наиболее часто используется интерполяция многочленами первой, второй и третьей степени( линейная, квадратичная и кубическая интерполяции). Приведем соответствующие формулы: ( ) ( ) ( ) ( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) 1 2 0 2 1 0 2 2 1 0 1 2 0 1 2 0 1 0 2 1 0 2 0 1 0 1 1 0 1 0 1 ) ( ) ( ) ( ) ( ) ( ) ( ) ( x x x x x x x x x f x x x x x x x x x f x x x x x x x x x f x L x x x x x f x x x x x f x L − − − − + − − − − + − − − − = − − + − − = Погрешность интерполяции. Теорема.1 Пусть функция f дифференцируема n+1 на отрезке b a, , содержащем узлы интерполяции n x x x ,..., , 1 0 . Тогда для погрешности интерполяции в точке b a x , справедливо равенство ) ( ) )( ( ) ( , ) ( )! 1 ( ) ( ) ( 1 0 1 1 1 n n n n n x x x x x x x где x n M x P x f − − − = + − + + + , а ) ( max ) 1 ( ] , [ 1 x f M n b a n + + = Пусть теперь n x x x 1 0 и 1 − − = i i i x x h шаг таблицы, а i n i h h = 1 max max . Несколько огрубляя оценку можно получить следующее неравенство: 1 max 1 ] , [ ) 1 ( 4 ) ( ) ( max 0 + + + − n n n x x h n M x P x f n Интерполяция многочленом степени n имеет (n+1)-й порядок точности относительно max h Минимизация оценки погрешности интерполяции. Многочлены Чебышева. Трудности построения «хороших» интерполяционных многочленов иногда удается преодолеть, переходя к специальным многочленам или выбором специальной системы узлов интерполяции. Предположим, что значения функции ) (x f можно вычислить в любой точке отрезка b a, , однако по некоторым причинам целесообразно в дальнейшем вычислять ее приближенно, используя интерполяционный многочлен ) (x P n . При этом естественно стремится к такому выбору узлов интерполяции и интерполяционного многочлена, чтобы погрешность интерполяции ( ) ) ( ) ( max , x P x f P n b a x n − = была минимальной. Такая задача называется задачей о наилучшем равномерном приближении. Доказано, что для широкого класса функций существует и единственен многочлен наилучшего равномерного приближения. П.Л.Чебышев вычислил точное значение погрешности многочлена наилучшего равномерного приближения для степенной функции: ( ) 1 1 1 1 0 1 , 1 1 , 2 1 max min ) ( − − − − − = + + + − = n n n n x n k o C n x C x C C x f E k Многочлены, на которых достигается минимум погрешности интерполяции ( ) ) ( ) ( max , x P x f P n b a x n − = , в честь П.Л.Чебышева названы многочленами Чебышева. При n=0 и n=1 они определяются явными формулами x x T x T = = ) ( , 1 ) ( 1 0 , а при 2 n рекуррентной формулой ) ( ) ( 2 ) ( 2 1 x T x xT x T n n n − − − = Запишем явные формулы для многочленов Чебышева ), (x T n при n=2,3,4,5. x x x x T x xT x T x x x T x xT x T x x x T x xT x T x x T x xT x T 5 20 16 ) ( ) ( 2 ) ( 1 8 8 ) ( ) ( 2 ) ( 3 4 ) ( ) ( 2 ) ( 1 2 ) ( ) ( 2 ) ( 3 5 3 4 5 2 4 2 3 4 3 1 2 3 2 0 1 2 + − = − = + − = − = − = − = − = − = Аналогично можно записать явные формулы для 6 n Свойства многочленов Чебышева. 1. При четном n многочлен ) (x T n содержит только четные степени x и является четной функцией, а при нечетном n многочлен ) (x T n содержит только нечетные степени x и является нечетной функцией. 2. При 1 n старший коэффициент многочлена ) (x T n равен 2 n-1 3. Для ] 1 , 1 [− x многочлен Чебышева n-й определяется равенством ( ) ) arccos( cos ) ( x n x T n = : ( ) 1 0 cos ) arccos( 0 cos ) ( 0 = = = x x T — алгебраический многочлен нулевой степени, ( ) ( ) x x x x T = = = ) arccos( cos ) arccos( 1 cos ) ( 1 — алгебраический многочлен 1-й степени, ( ) ( ) 1 2 1 ) arccos( cos 2 ) arccos( 2 cos ) ( 2 2 2 − = − = = x x x x T — многочлен 2-й степени, и т.д. 4. При 1 n многочлен ) (x T n имеет ровно n действительных корней, расположенных на отрезке ] 1 , 1 [− и вычисляемых по формуле + = n k x k 2 ) 1 2 ( cos , 1 ..., , 2 , 1 , 0 − = n k Т.к. ( ) ) arccos( cos ) ( x n x T n = , то корни многочлена ) (x T n на отрезке ] 1 , 1 [− совпадают с корнями уравнения ( ) 0 ) arccos( cos = x n . Эквивалентное преобразование этого уравнения дает ,... 2 , 1 , 0 , 2 arccos = + = k k x n .Т.к. x arccos 0 , то имеется ровно n корней. 5. При 0 n справедливо равенство 1 ) ( max ] 1 , 1 [ = − x T n . Если 1 n , то этот максимум достигается ровно в 1 + n точках. При этом m m n x T ) 1 ( ) ( − = , т.е. максимумы и минимумы многочлена Чебышева чередуются. Доказано, что минимум погрешности интерполяции ( ) ) ( ) ( max 1 , 1 x P x f P n x n − = − на отрезке 1 , 1 − достигается в нулях многочлена Чебышева ( ) ) arccos( ) 1 ( cos ) ( 1 x n x T n + = + , т.е. в точках + + = 2 2 1 2 cos n k x k , n k ..., , 2 , 1 , 0 = . При этом ( ) ( ) ! 1 2 ) ( ) ( max 1 1 , 1 + = − = + − n M x P x f P n n n x n и любой другой выбор узлов дает большую погрешность. Для сравнения: если для приближения функции использовать многочлен Тейлора n-й степени = = n k k k n x k f x P 0 ) ( ! ) 0 ( ) ( , то оценка границы погрешности в n 2 раз больше. Пусть теперь отрезок интерполяции произволен b a, . Стандартной заменой t a b b a x 2 2 − + + = , 1 , 1 − t отрезок b a, преобразуется в отрезок 1 , 1 − . Решение поставленной задачи дает выбор узлов 2 1 , 0,1,... 2 2 2 2 k a b b a k x сos k n n + − + = + = + , которому отвечает значение верхней границы погрешности интерполяции, равное ( ) ( ) 1 1 2 ! 1 2 + + − + = n n n n a b n M P Согласно теореме Вейерштрасса каждая непрерывная на отрезке функция может быть как угодно точно приближена многочленом. |