Приближение функций.

Лекция 4. Стр. 1 Лекция 4 Приближение функций Приближение функций: интерполяция, равномерная интерполяция, многочлены Чебышева. Интерполяция сплайнами, метод наименьших квадратов. Интерполяция многочленами Постановка задачи приближения функций. Необходимо вычислить значение функции y=f(x). Для элементарных, а также для основных специальных функций разработаны быстрые и надежные алгоритмы, реализованные в виде стандартных программ математического обеспечения ЭВМ. Однако в расчетах нередко используются и другие функции, непосредственное вычисление которых затруднено по каким-либо причинам. Укажем на типичные ситуации. 1. Функция задана таблицей своих значений: yi  f ( xi ), i  0,1,...n , а вычисление производится в точках 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. Постановка задачи интерполяции. Типичной задачей приближения функций является задача интерполяции. Функция f (x) задана своими значениями в точках xi  a, b, i  0,1, ..., N : xi , f xi  . Требуется найти функцию g ( x)  g ( x; x0 , x1 , ..., x N ) , удовлетворяющую условиям g ( xi , x0 , x1 , ..., x N )  f ( xi ) , i  0,1, ..., N . Другими словами, ставится задача о построении функции g, график которой проходит через заданные точки xi , f xi  Точки xi  a, b, i  0,1, ..., N называют узлами интерполяции, а функцию g ( x, x0 , x1 , ..., x N ) — интерполирующей функцией, в частности, если интерполирующая функция — многочлен, то говорят об интерполяционных многочленах. В дальнейших расчетах для x  a, bполагают f ( x)  g ( x) . Величина max f ( x)  g ( x) [ a ,b ] называется погрешностью интерполяции. Экстраполяция. В случае, когда интерполяция используется для вычисления значения функции f в точке x не принадлежащей отрезку наблюдения x  a, b, говорят, что осуществляется экстраполяция. Этот метод часто используют при прогнозировании характера протекания тех или иных процессов. Лекция 4. Стр. 2 Задача интерполяции обобщенными многочленами. Классическое решение задачи интерполяции — построение обобщенного многочлена  N ( x)  N   x  , где  (x) — i 0 i i i заданные базисные функции, а  i — параметры модели, коэффициенты обобщенного многочлена. Назовем обобщенный многочлен интерполяционным, если он удовлетворяет условию  N ( xi )  yi , i  0,1,..., n , или, что то же самое, системе линейных алгебраических уравнений  0 ( x0 )a0  1 ( x0 )a1  ...   N ( x0 )a N  y 0  0 ( x1 )a0  1 ( x1 )a1  ...   N ( x1 )a N  y1 ...................................................................  0 ( x n )a0  1 ( xn )a1  ...   N ( x0 )a N  y n относительно коэффициентов a0 , a1 ,..., a N . Опр. Система функций  0 , 1 ,...,  N линейно зависима в точках x0 , x1 ,..., xn , если один из векторов  j системы  0 , 1 ,...,  N может быть представлен в виде линейной комбинации N   остальных векторов системы:  j  k 0, k  j k k T , где  j  ( j ( x0 ),  j ( x1 ),...,  j ( x n )) , j  0,1,..., N В противном случае систему функций  0 , 1 ,...,  N будем называть линейно независимой в точках x0 , x1 ,..., xn . Замечание. Система функций 1, x, x 2 ,..., x n линейно независима в точках x0 , x1 ,..., xn . Интерполяционный многочлен Лагранжа. Рассмотрим задачу интерполяции алгебраическим многочленом Pn ( x)  n    x  , где  ( x)  x . i i 0 i i i Если выполняется условие Pn ( xi )  yi , i  0,1,..., n , то многочлен степени n называется интерполяционным многочленом. Это равенство можно записать в виде системы уравнений a0  a1 x0  a2 x0  ...  an x0  y0 2 n a0  a1 x1  a2 x1  ...  an x1  y1 2 n ..................................................... относительно коэффициентов многочлена. a0  a1 xn  a2 xn  ...  an xn  yn 2 n Эта система однозначно разрешима. Приведем одну из форм записи интерполяционного многочлена - интерполяционный многочлен Лагранжа. Интерполяционный многочлен Лагранжа имеет вид: n n i 0 k 0 k i Ln ( x)   f ( xi ) ni ( x) ,  ni ( x)   N L N ( x )   f ( xi ) i 0 x  xk , или, что то же самое, xi  x k x  x0 x  x2 ...x  xi1 x  xi1 ...x  x N  . xi  x0 xi  x2 ...xi  xi1 xi  xi1 ...xi  x N  Интерполяционный многочлен Лагранжа — многочлен N-й степени, для которого справедливо f ( xi )  LN ( xi ) , i  0,1, ..., N . В инженерной практике наиболее часто используется интерполяция многочленами первой, второй и третьей степени( линейная, квадратичная и кубическая интерполяции). Приведем соответствующие формулы: Лекция 4. Стр. 3 x  x0  x  x1   f ( x1 ) x0  x1  x1  x0  x  x0 x  x2  x  x1 x  x2  f ( x0 )  f ( x1 )  x0  x1 x0  x2  x1  x0 x1  x2  L1 ( x)  f ( x0 ) L2 ( x )  f ( x2 ) x  x0 x  x1  x2  x0 x2  x1  Погрешность интерполяции. Теорема.1 Пусть функция f дифференцируема n+1 на отрезке a, b , содержащем узлы интерполяции x0 , x1 ,..., xn . Тогда для погрешности интерполяции в точке x  a, b справедливо равенство f ( x)  Pn ( x)  M n 1  n 1 ( x) , где n 1 ( x)  ( x  x0 )( x  x1 )  ...  ( x  x n ) , а (n  1)! M n1  max f ( n1) ( x) . [ a ,b ] Пусть теперь x0  x1  ...  xn и hi  xi  xi 1 шаг таблицы, а hmax  max hi . Несколько 1i  n огрубляя оценку можно получить следующее неравенство: max f ( x)  Pn ( x)  [ x0 , x n ] M n 1 n 1 hmax . 4(n  1) Интерполяция многочленом степени n имеет (n+1)-й порядок точности относительно hmax . Минимизация оценки погрешности интерполяции. Многочлены Чебышева. Трудности построения «хороших» интерполяционных многочленов иногда удается преодолеть, переходя к специальным многочленам или выбором специальной системы узлов интерполяции. Предположим, что значения функции f (x) можно вычислить в любой точке отрезка a, b , однако по некоторым причинам целесообразно в дальнейшем вычислять ее приближенно, используя интерполяционный многочлен Pn (x) . При этом естественно стремится к такому выбору узлов интерполяции и интерполяционного многочлена, чтобы погрешность интерполяции Pn   max f ( x)  Pn ( x) была минимальной. Такая задача xa ,b  называется задачей о наилучшем равномерном приближении. Доказано, что для широкого класса функций существует и единственен многочлен наилучшего равномерного приближения. П.Л.Чебышев вычислил точное значение погрешности многочлена наилучшего равномерного приближения для степенной функции: En ( f )  min   max x n  C 0  C1 x  ...  C n 1 x n 1  C k ,o  k  n 1 x1,1 1 2 n 1 . Многочлены, на которых достигается минимум погрешности интерполяции Pn   max f ( x)  Pn ( x) , в честь П.Л.Чебышева названы многочленами Чебышева. xa ,b  При n=0 и n=1 они определяются явными формулами T0 ( x)  1, T1 ( x)  x , а при n  2 рекуррентной формулой Tn ( x)  2 xTn1 ( x)  Tn2 ( x) . Запишем явные формулы для многочленов Чебышева Tn (x), при n=2,3,4,5. T2 ( x)  2 xT1 ( x)  T0 ( x)  2 x 2  1 T3 ( x)  2 xT2 ( x)  T1 ( x)  4 x 3  3 x T4 ( x)  2 xT3 ( x)  T2 ( x)  8 x 4  8 x 2  1 T5 ( x)  2 xT4 ( x)  T3 ( x)  16 x 5  20 x 3  5 x Аналогично можно записать явные формулы для n  6 . Лекция 4. Стр. 4 Свойства многочленов Чебышева. 1. При четном n многочлен Tn (x) содержит только четные степени x и является четной функцией, а при нечетном n многочлен Tn (x) содержит только нечетные степени x и является нечетной функцией. 2. При n  1 старший коэффициент многочлена Tn (x) равен 2n-1. 3. Для x  [1,1] многочлен Чебышева n-й определяется равенством Tn ( x)  cosn arccos(x) : T0 ( x)  cos0  arccos( x)  cos 0  1 — алгебраический многочлен нулевой степени, T1 ( x)  cos1 arccos(x)  cosarccos(x)  x — алгебраический многочлен 1-й степени, T2 ( x)  cos2 arccos( x)  2 cos 2 arccos( x)  1  2 x 2  1 — многочлен 2-й степени, и т.д. 4. При n  1 многочлен Tn (x) имеет ровно n действительных корней, расположенных на отрезке [1,1] и вычисляемых по формуле  (2k  1)  x k  cos  , k  0, 1, 2, ..., n  1 . 2n   Т.к. Tn ( x)  cosn arccos(x) , то корни многочлена Tn (x) на отрезке [1,1] совпадают с корнями уравнения cosn arccos(x)  0 . Эквивалентное преобразование этого уравнения дает n arccos x   2  k , k  0,1,2,... .Т.к. 0  arccos x   , то имеется ровно n корней. 5. При n  0 справедливо равенство max Tn ( x)  1 . Если n  1 , то этот [ 1,1] максимум достигается ровно в n  1 точках. При этом Tn ( x m )  (1) m , т.е. максимумы и минимумы многочлена Чебышева чередуются. Доказано, что минимум погрешности интерполяции Pn   max f ( x)  Pn ( x) на x1,1 отрезке  1, 1 достигается в нулях многочлена Чебышева Tn1 ( x)  cos(n  1) arccos( x)  , т.е. в M  2k  1    , k  0, 1, 2, ..., n . При этом Pn   max f ( x)  Pn ( x)  n n 1 и x1,1 2 n  1!  2n  2  точках x k  cos любой другой выбор узлов дает большую погрешность. Для сравнения: если для приближения функции использовать многочлен Тейлора n-й f ( k ) (0) k x , то оценка границы погрешности в 2 n раз больше.  k ! k 0 Пусть теперь отрезок интерполяции произволен a, b . Стандартной заменой ab ba x  t , t   1, 1 отрезок a, b преобразуется в отрезок  1, 1 . Решение 2 2 степени Pn ( x)  n поставленной задачи дает выбор узлов x ab ba  2k  1   сos  , k  0,1,...n , которому отвечает значение верхней 2 2  2n  2  границы погрешности интерполяции, равное M ba Pn   n n 1   2 n  1!  2  n 1 Лекция 4. Стр. 5 Согласно теореме Вейерштрасса каждая непрерывная на отрезке функция может быть как угодно точно приближена многочленом. Теорема.2 (Вейерштрасса) Пусть функция f (x) непрерывна на отрезке a, b . Тогда для любого   0 Pn (x) степени n  n( ) такой, что max f ( x)  Pn ( x)   . [ a ,b ] Естественно предположить, что увеличивая количество узлов интерполяции, т.е. увеличивая степень интерполяционного многочлена, можно приблизить функцию как угодно точно. Однако ряд примеров показывает, что даже при большом числе узлов интерполяционный многочлен Лагранжа не гарантирует хорошее приближение функции. С.Н.Бернштейн доказал, что последовательность многочленов Лагранжа, построенная для непрерывной функции f ( x)  x по равноотстоящим узлам (равномерная сетка) на отрезке  1, 1 , не сходится при возрастании числа узлов к f (x) . x  Ln (x) не стремится к нулю при n   . Замечательный пример построен Карлом Рунге. Рунге рассмотрел бесконечно дифференцируемую функцию R ( x )  1 (ее называют функцией Рунге). 1  25 x 2 Последовательность интерполяционных полиномов Лагранжа, построенная по равноотстоящим узлам, не сходится к функции Рунге по равномерной норме. Более того, для обоих примеров установлено, что lim max f ( x)  LN ( x)   , а для функции Рунге показано, что N  x1,1 max R( x)  L20 ( x)  58 . x1,1 Однако проблема сходимости для этой функции исчезает, если в качестве узлов интерполяции брать корни многочлена Чебышева Tn1 ( x) . Погрешность интерполяции функции Рунге многочленом Лагранжа, построенным по чебышевским узлам, стремится к нулю с ростом степени интерполяционного многочлена. Теорема 3.(Фабера) Какова бы ни была стратегия выбора узлов интерполяции, найдется непрерывная на отрезке a, b функция f , для которой lim max f ( x)  PN ( x)   . N  xa ,b  Теорема Фабера отрицает наличие единой стратегии выбора узлов интерполяции для непрерывных функций. Теорема 4. Пусть в качестве узлов интерполяции на отрезке a, b выбираются чебышевские узлы. Тогда для любой непрерывно дифференцируемой на отрезке a, b функции f метод интерполяции сходится. Лекция 4. Стр. 6 Интерполяция сплайнами Интерполяция сплайнами, метод наименьших квадратов. На практике часто возникает задача интерполяции с наперед заданными узлами интерполяции и, следовательно, улучшить свойства интерполяции построением многочлена наилучшего равномерного приближения невозможно. Тогда, вместо построения глобального интерполяционного полинома на всем промежутке, используют интерполяцию "кусочными многочленами". Простейший пример такой интерполяции известен всем. Обычно, изображая на графике экспериментальные точки xi , f xi , xi  a, b, i  0,1, ..., N , их, не задумываясь, соединяют отрезками прямых. Это ни что иное как кусочная интерполяция многочленами первой степени. В общем случае отрезок a, b точками a  x0  x1  ...  x N  b разбивают на части и на каждом отрезке xi , xi 1  строят некоторый интерполяционный многочлен. Такой многочлен-многозвенник дает интерполяцию на всем отрезке и называют сплайном. Свойства сплайна будут зависеть от степени многочлена на каждом отрезке (обычно они одинаковы для всех отрезков) и от условий на концах отрезков. Гладкие сплайны обладают многими замечательными свойствами, которые обеспечили им широкое применение в прикладных вычислениях. Например, кубический сплайн функции Рунге на сетке с шестью узлами дает настолько малую погрешность, что она не видна на графике. Опр. Пусть отрезок a, b разбит точками a  x0  x1  ...  x N  b на N частичных отрезков xi , xi 1  . Сплайном степени m называется функция S m (x) , обладающая следующими свойствами: 1. функция S m (x) непрерывна на отрезке a, b вместе со всеми своими (1) производными S m ( x), S m ( 2) ( x),..., S m ( p) ( x) до некоторого порядка р. 2. на каждом частичном отрезке xi , xi 1  функция S m (x) совпадает некоторым алгебраическим многочленом степени m. Разность m-p между степенью сплайна и наивысшим порядком непрерывной отрезке a, b производной называется дефектом сплайна. Наиболее широкое применение получили кубические сплайны— дважды непрерывно дифференцируемые сплайны, с дефектом равным 1, построенные с использованием кусочной интерполяции многочленами третьей степени. Такие сплайны на каждом из частичных отрезков xi , xi 1  совпадают с кубическим многочленом: S 3 ( x)  P3,i ( x)  ai  bi ( x  xi 1 )  ci ( x  xi 1 ) 2  d i ( x  xi 1 ) 3 Пусть некоторая дважды непрерывно дифференцируемая функция f (x) задана на отрезке a, b своими значениями в узлах сетки xi , f xi , xi  a, b, i  0,1, ..., N . Интерполяционным кубическим сплайном S (x ) , с дефектом равным 1, называется сплайн, удовлетворяющий условиям: 1. S xi   f xi  , для i  0,1, 2, ..., N . Количество условий N  1 S ' xi   f ' xi  -наклон сплайна в точке xi , i  1, 2, ..., N  1 . Количество условий N  1 3. S ' ' xi   f ' ' xi  , i  1, 2, ..., N  1 . Количество условий N  1 4. P3,i ( xi )  P3,i 1 ( xi ) , i  1, 2, ..., N  1 . Количество условий N  1 2. Лекция 4. Стр. 7 5. Одному из граничных условий I. S ' (a )  f ' (a ), S ' (b)  f ' (b); II. S ' ' (a )  f ' ' (a ), S ' ' (b)  f ' ' (b); III. S ( k ) (a )  S ( k ) (b), k  1,2; IV. S ' ' ' ( x p  0)  S ' ' ' ( x p  0), p  1, N  1; нет _ дополнительной _ информации _ о  производных _ на _ концах  отрезка V. S ' ' (a )  S ' ' (b)  0. . Количество условий 2. Воспользуемся последними из них, так называемыми "естественными условиями", опишем задачу, вычисления сплайна. На каждом из отрезков xi , xi 1  будем записывать сплайн в виде S i ,3 ( x)   i   i x   i x 2   i x 3 . Тогда S i,3   i  2 i x  3 i x 2 а, S i,3  2 i  6 i x Для вычисления его 4N коэффициентов требуется записать 4N уравнения. Производные сплайна вычисляем аналитически — для производных функции f (x) во внутренних узлах используем формулы центральных разностных производных f xi 1   f xi 1  , в точке a — правую разностную производную xi 1  xi 1 f x N 1   f b f x1   f a  , а точке b — левую — f ' b   . Имеем N  1 равенство f ' a   x N 1  b x1  a значений функции и сплайна в узлах сетки, 3( N  1) уравнений непрерывности сплайна и его f '  xi   первых и вторых производных во внутренних узлах сетки и еще 2 уравнения из естественных граничных условий, т.е. имеем систему N  1  3( N  1)  2  4 N уравнений относительно 4N неизвестных коэффициентов. Относительно этой системы известно, что система имеет невырожденную трех диагональную матрицу. Единственное решение системы находят специальным методом решения систем с трехдиагональными матрицами — методом прогонки. Теорема 1. Пусть функция f (x) имеет отрезке a, b непрерывную производную четвертого порядка и M 4  max f [ a ,b ] ( 4) ( x) . Тогда для интерполяционного кубического сплайна S 3 ( x) , удовлетворяющего граничным условиям типов I., II., III., IV, справедлива следующая оценка погрешности: 4 . max f ( x)  S 3 ( x)  CM 4 hmax [ a ,b ] Приведем пример построения квадратичного (параболического) сплайна для функции y  y (x) , заданной таблицей своих значений, с дополнительным условием S’(1)=2 x 1 2 3 6 y 2 5 Êîëè÷åñòâî òî÷åê 4, êîëè÷åñòâî ñïëàéíîâ 3. Çàïèøåì îáùèé âèä ñïëàéíîâ íà òðåõ îòðåçêàõ. [x0,x1]: P1( x) a10  a11 ( x  x0)  a12 ( x  x0) ( x  x1) [x1,x2]: P2( x) a20  a21 ( x  x1)  a22 ( x  x1) ( x  x2) [x1,x2]: P3( x) a30  a31 ( x  x2)  a32 ( x  x2)  ( x  x3) 10 6 Лекция 4. Стр. 8 P1( x) a10  a11  ( x  1)  a12  ( x  1) ( x  2) P1'( x) P2( x) a20  a21  ( x  2)  a22  ( x  2) ( x  3) ( P2'( x) ) a21  a22  ( 2x  5) P3( x) a30  a31  ( x  3)  a32  ( x  3)  ( x  4) ( P3'( x) ) a31  a32  ( 2x  7) a11  a12  ( 2x  3) Çàïèøåì óñëîâèÿ èç êîòîðûõ íàéäåì êîýôôèöèåíòû ñïëàéíîâ. P1( x0) y0 P1( x1) y1 P1'( x1) P2'( x1) P2( x1) y1 P2( x2) y2 P2'( x2) P3'( x2) P3( x2) y2 P3( x3) y3 P1'( x0) 2 P1( 1) 2 P1( 1) a10  a11  ( 1  1)  a12  ( 1  1) ( 1  2) a10  2 P1( 2) 5 P1( 2) a10  a11  ( 2  1)  a12  ( 2  1)  ( 2  2) a11  3 P2( 2) 5 P2( 2) a20  a21  ( 2  2)  a22  ( 2  2)  ( 2  3) a20  5 P2( 3) 10 P2( 3) a20  a21  ( 3  2)  a22  ( 3  2)  ( 3  3) a21  5 P3( 3) 10 P3( 3) a30  a31  ( 3  3)  a32  ( 3  3)  ( 3  4) a30  10 P3( 4) 6 P3( 4) a30  a31  ( 4  3)  a32  ( 4  3)  ( 4  4) a31  4 P1'( 1) 2 a12  1 P1'( 2) P2'( 2) a22  1 P2'( 3) P3'( 3) a32  11  0 x0  X  1 x1  X  2 x2  X  3 x3  X S1 ( x)  a10  a11  ( x  x0)  a12  ( x  x0)  ( x  x1) S1 ( x) exp and  x  S2( z)  [ a20  a21 ( z  x1)  a22 ( z  x1)  ( z  x2) ] S2( z) expand z  S3( p)  [ a30  a31 ( p  x2)  a32 ( p  x2)  ( p  x3) ] S3( p) expand p  f1( x) f2( x) f3( x) Y x x x X Вычислив однажды коэффициенты сплайна, можно в дальнейших вычислениях заменять значения функции значениями сплайна, поскольку программы, реализующие вычисления сплайна имеют метку для повторного обращения. Т.е. при последующих обращениях производится вычисление приближенного значения функции (значения сплайна) по вычисленным при первом обращении коэффициентам сплайна, и вычисления организованы так, что погрешности округления минимальны. Лекция 4. Стр. 9 Аппроксимация данных методом наименьших квадратов Пусть функция y  f (x ) задана таблицей приближенных значений xi , yi *, xi  a, b, yi *  f xi , i  0,1, ..., N  , полученных с ошибками  i  f  xi   y i * . В этом случае требование g ( xi , x0 , x1 , ..., x N )  yi * для аппроксимирующей функции g ( x, x0 , x1 , ..., x N ) может привести к неоправданным дополнительным погрешностям. Выберем другой подход. Будем использовать для аппроксимации функции y  f (x ) линейную модель y   m ( x)  m   x  , где  (x) — заданные базисные функции, а  i i 0 i i i — параметры модели, коэффициенты обобщенного многочлена. Отказываясь от требования выполнения в точках xi точных равенств, следует все же стремится к тому, чтобы в этих точках выполнялись соответствующие приближенные равенства Фm ( xi )  yi , i  0,1,..., N . Наиболее часто используется линейная модель с базисными функциями  i ( x)  x i . Система приближенных равенств: a 0  a1 x0  a 2 x0  ...  a m x0  y 0 2 m a 0  a1 x1  a 2 x1  ...  a m x0  y1 2 m ..................................................... относительно коэффициентов a 0  a1 x N  a 2 x N  ...  a m x N  y N 2 m многочлена a0 ,..., am Одним из критериев выбора параметров a0 ,..., am линейной модели является критерий наименьших квадратов: параметры выбирают так, чтобы среднеквадратичное отклонение  ( m , y*)  1 N N  y i 0 *  m  xi  было минимальным. Ясно, что минимум 2 i среднеквадратичного отклонения достигается в той же точке, что и минимум функции 2 m   s 0 ,  1 , ...,  m     y i *  m  xi    y i *   j  j xi   i 0 i 0  j 1  2  y 0 *  0 0 x0    11 x0   ...   m m x0   ...   y N *  0 0 x N    11 x N   ...   m m x N 2 N 2 N В силу необходимого условия экстремума функции нескольких переменных параметры линейной модели удовлетворяют условию производную функции s 0 , 1 , ...,  m  по  0 : s  0 . Посчитаем частную  k s  2 y 0 *  0 0 x0    11 x0   ...   m m x0  0  x0   ...  0  2 y N *  0 0 x N    11 x N   ...   m m x N  0  x N  После несложных вычислений получаем нормальную систему метода наименьших   N  N        x  x    j  j i k i     y i *  k  xi  , k  0, 1, 2, ..., m . j 1   i 0   i 0 m квадратов Доказано, что для линейно независимых базисных функций система имеет единственное решение. Очевидно, что в случае m  N и  i ( x)  x i ,  (x ) совпадает с Лекция 4. Стр. 10 интерполяционным многочленом. Однако метод наименьших квадратов обычно применяют при m  N . В случае приближения алгебраическими многочленами  i ( x)  x i нормальная система принимает следующий вид:        x     y m N j 1 j  N jk i 0 i  i 0 i * xik , k  0, 1, 2, ..., m Запишем систему в развернутом виде в двух наиболее простых случаях m=1,m=2. 1. m=1, приближение осуществляется многочленом 1-ой степени P1(x)=a0+a1x, нормальная система имеет вид: N  N  ( N  1)a 0    xi a1   y i * i 0  i 0  N  N   N 2   xi a 0    xi a1   y i *xi i 0  i 0   i 0  2. m=2, используется многочлен 2-ой степени P1(x)=a0+a1x+a2x2, N  N   N  ( N  1)a 0    xi a1    xi2 a 2   y i * i 0  i 0   i 0  N N N N       нормальная система имеет вид:   xi a 0    xi2 a1    xi3 a 2   y i *xi i 0  i 0   i 0   i 0  N N N N         xi2 a 0    xi3 a1    xi4 a 2   y i *xi2 i 0  i 0   i 0   i 0  Рассмотрим пример. Пусть функция y  y (x) задана таблицей своих значений x y -1 1 2 1 3 2 5 Используя метод наименьших квадратов, аппроксимируем ее многочленами первой и второй степени и найдем соответствующие среднеквадратичные уклонения  1 ,  2 . Вычислим коэффициенты и правые части нормальных систем: 3 x i 0 i  2, 3 x i 0 2 i 6, 3 x i 0 3 i  8, 3 x i 0 4 i  18 , 3 y i 0 i  11 , 3 y i 0 i * xi 11 , 3 y i 0 i * xi2  23 Для многочлена первой степени нормальная система имеет вид 4a0  2a1  11 2a0  6a1  11 , решив ее, получим значения a0  2.2, a1  1.1 Рисунок многочлена P1(x)=2.2+1.1x наилучшего среднеквадратичного приближения: yi F( t ) xi  t   Средне квадратичное уклонение вычислим по формуле: 1 4 3  2  Fxi  yi i 0  Лекция 4. Стр. 11 Для многочлена второй степени нормальная система имеет вид 4a0  2a1  6a 2  11 2a0  6a1  8a 2  11 , решив ее, получим значения a0  1.95, a1  0.85, a2  0.25 6a0  8a1  18 a 2  23 Рисунок многочлена P1(x)=1.95+0.85x+0.25 x2 наилучшего среднеквадратичного приближения: yi F( t ) xi  t   Средне квадратичное уклонение вычислим по формуле: 3 2 F x   y    i i 4 1  i 0  Нормальную систему метода наименьших квадратов можно получить из других соображений. Рассмотрим несовместную линейную систему Ax  b , x  R N , b  R m . Если причина несовместности системы заключена в том, что элементы матрицы системы и/или правые части содержат ошибки, то задача об отыскании ее приближенного решения имеет смысл. Несовместность системы означает, что вектор b не принадлежит линейному пространству столбцов матрицы А. Назовем нормальным обобщенным решением несовместной системы Ax  b такой вектор x * , для которого коэффициенты невязка Ax  b минимальна. Из линейной алгебры (или из геометрических соображений (см. рис.)) понятно, что невязка минимальна тогда и только тогда, когда вектор невязки r  Ax  b ортогонален пространству столбцов матрицы А: Ax  b, Ax  0 или, что то же самое, A Ax  b, x  0 для всех x  R T всем векторам пространства R N N . Известно, что единственный вектор, ортогональный — нулевой вектор, т.е. A T Ax  b   0 , откуда A T Ax  A T b . Эта последняя система и есть нормальная система метода наименьших квадратов. Пример. Вернемся к задаче аппроксимации функции. Для простоты записи ограничимся случаем линейной аппроксимации линейными функциями: yi *  a0  a1 xi , i  0,1, ..., N . Если потребовать точного выполнения равенств yi *  a0  a1 xi , то получим систему N линейных уравнений относительно двух неизвестных a0  a1 xi  yi * , i  0,1, ..., N , с  1 x1   y1 *       1 x2   y2 *  матрицей A   , правой частью b   и вектором неизвестных ... ...  ...      1 x   y * N    N   a0    .  a1  Лекция 4. Стр. 12  a0    A T b . Если a  1 Нормальная система метода наименьших квадратов в этом случае — A T A все узлы xi различны, матрица A T A обратима и искомое решение определяется равенством  a0     A T A  a1    1 A T b . Заметим, что нормальная система метода наименьших квадратов часто оказывается плохо обусловленной.