WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 |
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики, механики и информатики Гудович Н. Н.

ИЗБРАННЫЕ ВОПРОСЫ КУРСА ЧИСЛЕННЫХ МЕТОДОВ Выпуск 1.

Интерполяция алгебраическими многочленами.

Многочлен Лагранжа.

Воронеж 2002 10. Существование и единственность интерполяционного многочлена.

Алгебраическим многочленом степениневыше n называют функцию вида p( x ) = a0 + a1x + a2x2 +...+ anxn, (1.1) где вещественная переменная, а a0, a1,..., an – вещественные константы; при x - an0 говорят о многочлене n-ой степени.

Многочлены ввиду простоты вычисления их значений широко используются для приближения функций. Именно, используя тот или иной критерий близостифункций, по заданной функции f строят многочлен p и принимают в качестве приближения для f (x) значение p(x) многочлена p в этой точке: f (x) p(x). Если в качестве критерия близости двух функций принимается совпадениеих значений внекотором фиксированном набореточек, то получается метод приближения, называемый интерполяцией алгебраическими многочленами.

Пусть f – заданная на отрезке [ a, b ] функция, а x0, x1,..., xn (1.2) -попарно различные точкиэтого отрезка.

Определение 1.1. Интерполяционным многочленом степени не выше n (обозначение pn (x;{xi}i=0,...,n ; f)) называют многочлен (1.1), значения которого в точках (1.2) совпадают со значениями функции f:

pn ( x k ; { xi }i=0,..., n ; f )= f (x k ), k = 0, 1,..., n; (1.3) при этом точки (1.2) называются узлами интерполяции, а функция f - интерполируемой функцией.

Замечание 1.2. Многочлен pn( x; {xi}, f ) как функция переменной x зависит во-первых, от функции f и, во-вторых, от выбора узлов интерполяции, (1.2), что иотражено в обозначении. В том случае, когда ясно, о каком наборе узлов и какой функции идет речь, естественно использовать более простое обозначение: pn(x).

Теорема 1.3. Для любого набора (1.2) попарно различных узлов интерполяции на отрезке [a,b] и любой заданной на [a,b] функции f интерполяционный многочлен pn( x; {xi}; f ) существует и единственен.

Доказательство. Воспользовавшись (1.1), перепишем условия (1.3) в виде:

a0 + a1xk + a2(xk)2 +... + am(xk)m +... + an(xk)n = f(xk), k=0,1,...,n. (1.4) Если набор узлов (1.2) зафиксировать, то соотношения (1.4) можно рассматривать как систему линейных алгебраических уравнений относительно неизвестных коэффициентов a0,a1,...,am,...,an интерполяционного многочлена pn( x; {xi}, f ), и потому вопрос о существовании и единственности этого многочлена эквивалентен вопросу об однозначной разрешимостиэтой системы прилюбых правых частях f(x0), f(x1),..., f(xk),..., f(xn). (1.5) Матрица системы (1.4) имеет специальный вид: её m-тый ( m=0,1,...,n ) столбец составлен из m-тых степеней чисел (1.2). Матрицы такого типа в алгебре называют матрицами Вандермонда; для построения матрицы B этого класса выбирают ( необязательно различные ) числа b0, b1,..., bk,... bn, (1.6) возводят их в m-тую степень иполученный упорядоченный набор чисел (b0)m, (b1)m,..., (bk)m,..., (bn)m записывают в виде m-того столбца матрицы B. Известен способ вычисления определителя такой матрицы: сначала следует образовать всевозможные разности bi – bj, i>j (1.7) чисел (1.6), а затем их перемножить:

det B (b -= b ) (1.8) ji > ji В нашем случае роль чисел (1.6) играют числа (1.2): bk=xk, k=0,1,...,n. В силу предположения о том, что узлы интерполяции – попарно различные точки отрезка [a,b], разности(1.7), а значит и их произведение (1.8) – определитель, системы (1.4) – отличны от нуля. Но тогда система однозначно разрешима при любых правых частях (1.5), что и гарантирует существованиеи единственность интерполяционного многочлена.

Замечание1.4. Проведенные рассуждения указывают и способ построения интерполяционного многочлена: по заданным узлам интерполяции (1.2) и значениям (1.5) интерполируемой функции составляем систему (1.4), решаем её относительно a0,a1,...,an и подставляем полученные ai в (1.1). Такой способ построения pn(x) называют методом неопределённых коэффициентов.

Замечание 1.5. Если в результате решения системы (1.4) для старших коэффициентов an,an-1,...,an-r получены нулевые значения, то фактическая степень интерполяционного многочлена строго меньше n.

20. Многочлен Лагранжа.

Лагранжем предложен способ построения интерполяционного многочлена, который нетребует решения системы (1.4) и состоит следующем.

в 1.Фиксируя k ( k=0,1,...,n), образуем всевозможные разности x-xi, ik, а затем, перемножая эти разности, получаем многочлен n-ой степени n (2.1) x( -xi), =0i ki равный нулю во всех узлах, кроме xk, и принимающий вузле xk ненулевое значение n x( -xik ). (2.2) =0i ki Для произведения (2.1) будет использоваться и более подробное обозначение (x – x0)(x – x1)...(x – xk-1)(x – xk+1)...(x – xn), (2.1’) которое при 1 k n-1 следует понимать буквально, а при и k=n - считать k=символическим обозначением произведений (x – x1)(x – x2)...(x – xn), (x – x0)(x – x1)...(x – xn-1) ;

аналогичное обозначение будет использоваться и для (2.2).

2.Делим многочлен (2.1) на величину (2.2) и получаем многочлен n-ой степени n x( - xi ) =0i x( x )(x -- x10 )...(x - xk 1)(x - xk+- )...(x - xn ) ki (l x) = = (, 2.3) k n x( x0k )(xk -- x1)...(xk - xk 1)(xk - xk+- )...(xk - xn ) x( - xik ) =0i ki равный единице в узле xk и нулю в остальных узлах,1 i = k (2.4) (l xik ) =,0 i k. (2.5) 3.Умножаем многочлен (2.3) на f(xk) и, суммируя по k, приходим к многочлену Лагранжа x( - xi ) n n x( x )...(x -- xk0 )(x - xk+- )...(x - xn ) 1 1 ki (p x) = ) = (f xk ) = f(xkn x( x0k )...(xk -- xk 1)(xk - xk+- )...(xk - xn ) x( - xik ) =0k =0k ki n = (f x ) l ( )x. (2.6) kk =0k Теорема 2.1. Многочлен (2.6) есть интерполяционный многочлен для функции f, отвечающий набору узлов x0,x1,...,xn.



Доказательство. Многочлен (2.6) как линейная комбинация многочленов (2.3) степени n неможет иметь степень выше n. Далее, фиксируем номер k узла интерполяции и полагаем x=x k в формуле (2,6). В силу (2.5) слагаемые суммы (2.6), отвечающие значениям k k, обратятся в нуль, а оставшееся слагаемое в силу (2.4) окажется равным f(x k). Следовательно, pn(x k)=f(x k), что ввиду произвольности k и завершает доказательство.

Замечание 2.2. В силу единственности интерполяционного многочлена многочлен Лагранжа (2.6) совпадает с интерполяционным многочленом (1.1), полученным методом неопределённых коэффициентов. Представления (1.1) и (2.6) – лишь разные формы записи интерполяционного многочлена: первое из них есть разложение интерполяционного многочлена по базису из функций 1,x,x2,...,xn, а второе – по базису из функций (2.3). Достоинство второго разложения состоит втом, что коэффициенты в разложении по базису (2.3) совпадают со значениями f(xk) функции f в узлах интерполяции, тогда как связь коэффициентов ai разложения (1.1) с величинами f(xk) достаточно сложна.

30. Поведение погрешности интерполяционного многочлена на отрезке интерполяции.

Определение 3.1. Погрешностью интерполяционного многочлена в точке x[a,b] ( или погрешностью интерполяции в x ) называется величина точке rn(x) = f(x) – pn(x;{xi};f). (3.1) Выведем формулу для погрешности интерполяции втом частном случае, когда функция f является многочленом степени n+1 ( т.е. когда речь идёт о приближении многочлена f степени n+1 многочленом pn степениневыше n ).

Теорема3.2. Для любого многочлена f степени справедлива формула n+n( +1) n( +1) n (f x) (f x) (f x) pn(x) =- x10 )...(x-xn). (3.2) x( xi) =- n( +1)! x( x )(x-n( +1)! =0i Доказательство. Функция (3.1) как разность многочлена f степени и n+многочлена pn степени не выше n есть многочлен степени n+1. По определению интерполяционного многочлена pn функция rn(x) обращается в нуль во всех узлах интерполяции xk, а значит, и в узле x0. Но тогда по теореме Безу многочлен rn делится без остатка на (x-x0), так что rn(x) = (x – x0)qn(x), где qn – многочлен степени n. Так как при x=x1 множитель (x – x0) в нуль не обращается, узел x1 есть корень многочлена qn, а тогда вторичное применение теоремы Безу даёт rn(x) = (x – x0)(x – x1)qn-1(x), где qn-1 – многочлен степени n-1. Продолжая этирассуждения, окончательно придём к формуле rn(x) = (x – x0)(x – x1)...(x – xn)q0(x), где q0 – многочлен нулевой степени, т.е. константа: q0=const=K.

Итак, f(x) – pn(x) = K(x – x0)(x – x1)...(x – xn). (3.3) Старший член в правой части (3.3) имеет вид: Kxn+1, а потому f(x) – pn(x) = Kxn+1 + gn(x), (3.4) где gn(x) – многочлен степениневыше n.

Найдём константу K. Беря от обеих частей равенства (3.4) (n+1)-ю производную по x и учитывая, что эта производная от xn+1 равна (n+1)!, а от многочленов pn, gn степени n – нулю, получим f(n+1) (x) = K(n+1)!.

Выражая отсюда константу K и подставляя результат в (3.3), приходим к формуле (3.2).

Замечание 3.3. Припереходепеременной x через узел xk множитель x –xk меняет знак, тогда как остальные множители знак сохраняют. Поэтому график погрешности интерполяции на отрезке [a,b] - осциллирующая (т.е.

колеблющаяся) кривая, пересекающая ось x в узлах интерполяции:

x0 x1 x2 x Рис. 3. Выясним, как меняется размах этих колебаний приперемещении точки x по отрезку интерполяции [a,b],считая узлы xk упорядоченными по возрастанию a x0 < x1 < x2 <... < xk <... < xn b ( чего ранее мы непредполагали ) и равноотстоящими xk = x0 + kh, k=0,1,...,n (3.5) ( здесь h > 0 – расстояние между соседними узлами ).

Введём новую вещественную переменную - xx t = (, 3.6) h принимающую в узлах интерполяции целые значения 0,1,...,n и по этой причине условно называемую «целочисленной» (рис. 3.2).

В силу (3.3) погрешность интерполяции лишь числовым множителем K отличается от функции n x( ) = (x -x0)(x -x1)...(x -xn) = -xi), (3.7) +1n (x =0i поэтому характер изменения погрешности при изменении x полностью определяется функцией (3.7). При этом в формуле (3.7) удобно перейти к переменной t с помощью вытекающего из (3.6) соотношения x = x0 + th. (3.8) Из соотношений (3.8),(3.5) получаем x – x0 = th, x – x1 = x – x0 – h = th – h = (t – 1)h,..., x – xn = x – x0 – nh = (t – n)h, а потому +1n t( ) = n++ (x) = h t(t+1)...(t+k)...(t+n). (3.9) 1n xx += th Выберем точку x, отличную от узлов интерполяции, правее середины отрезка [x0,xn] (что соответствует t>n/2) и выясним, как связаны значения функции (3.7) в точках x и x + h (или, что то же самое, как связаны значения функции (3.9) в точках t и t + 1).

В силу (3.9) имеем +1t 1n n++ t( + 1)=h (t+1)t(t-1)...(t-n+1)= th (t 1)...(t-- n+1)(t-n), +1n t-n следовательно +1t t( + 1) = n++ t( ). (3.10) 1n t -n Множитель t+1 / t – n по абсолютной величинебольше единицы.

В самом деле, как видно из рис.3, n tn <- < +1t а потому +1t +1t 1< = (. 3.11) -tn -nt Соотношения (3.10),(3.11) позволяют сделать Вывод 3.1. Приперемещении точки от середины отрезка [x0,xn] к его x правому концу ( при перемещении к левому ситуация аналогична ) размах колебаний погрешности интерполяции увеличивается.





40. Общая формула для погрешности интерполяции.

В данном пункте мы отказываемся от предположения о том, что интерполируемая функция есть многочлен степени n+1, а требуем лишь, чтобы она принадлежала классу C n+1 [a,b], т.е. имела на отрезке [a,b] непрерывные производные до порядка n+1 включительно.

Теорема 4.1. Для любой функции f C n+1 [a,b] справедлива формула n( +1) (f (x)) (f x) p (x;{xin };f )=- x( x )(x-- x10 )...(x-xk )...(x-xn ), (4.1) n( +1)! где (x) – точка, принадлежащая наименьшему отрезку вещественной оси, содержащему точку x и все узлы интерполяции:

(x)[ min{x,x0,x1,...,xn}, max{x,x0,x1,...,xn} ] [a,b]. (4.2) Замечание 4.2. Отличиеформулы (4.1) от ранее выведенной формулы (3.2) состоитвтом, что множитель f (n+1)(x) в формуле (3.2), как производная порядка n+1 от многочлена степени n+1, фактически от x не зависит тогда как, аналогичный множитель f (n+1)((x)) в (4.1) с изменением x, вообще говоря, меняется.

Доказательство теоремы 4.1. Зафиксируем отличную от узлов интерполяции точку x и подберём константу K так, чтобы имело место равенство f(x ) – pn(x ) = K (x -x0)(x -x1)...(x -xn) (4.3) ( для этого, очевидно, следует положить K = ( f(x ) – pn(x ) ) / (x - x0)(x - x1)...(x - xn) ).

Составим теперь вспомогательную функцию переменной x h(x) = f(x) – pn(x) – K (x – x0)(x – x1)...(x – xn). (4.4) В силу (1.3) функция h обращается в ноль во всех узлах интерполяции, а в силу (4.3) – и в точке x. Переобозначим эти n+2 точкисимволами yi(0), i=0,1,...,n+1, чтобы получить упорядоченный по возрастанию y0(0) < y1(0) < y2(0) <... < yn+1(0) (4.5) наборкорней нулевой производной функции h h(yi(0)) = 0, i = 0,1,...,n+1, (4.6) расположенных, очевидно, на подотрезке [y0(0),yn+1(0)] = [ min{x,x0,x1,...,xn}, max{x,x0,x1,...,xn} ] (4.7) отрезка [a,b].

На концах отрезка [yi(0),yi+1(0)] функция h принимает ( см. (4.6) ) равные ( а именно, нулевые ) значения. Но тогда по теореме Ролля найдётся точка yi(1) внутриэтого отрезка yi(0) < yi(1) < yi+1(0), (4.8) в которой обращается в нуль первая производная функции h h(yi(1)) = 0, i=0,1,... n ;

приэтом в силу (4.5),(4.8) точки образуют упорядоченный по возрастанию yi(1) наборточек y0(1) < y1(1) < y2(1) <... < yn(1) отрезка (4.7). Применяя затем теорему Ролля к отрезку [yi(1),yi+1(1)] и функции h, приходим к упорядоченному набору y0(2) < y1(2) < y2(2) <... < yn-1(2) расположенных на отрезке (4.7) корней второй производной функции h h(yi(2)) = 0, i=0,1,...,n-1, и так далее. В конце концов приходим к точке y0(n+1) y0(n) < y0(n+1) < y1(n) отрезка (4.7), в которой обращается в нуль (n+1)-я производная функции h h(n+1)(y0(n+1)) = 0. (4.9) Вычислим h(n+1)(x) из (4.4) и подставим результат в (4.9). Тогда получим 0 = f(n+1)(y0(n+1)) – K (n+1)!, откуда K = f (n+1)(y0(n+1)) / (n+1)!. (4.10) Переобозначая здесь точку y0(n+1) через (x ) ( зависимость y0(n+1) от выбора x очевидна ) и подставляя (4.10) в (4.3), получим требуемое равенство (4.1) для x = x, что ввиду произвольности x и завершает доказательство.

Замечание 4.3. Из формулы (4.1) следует неравенство n( +1) (f x) pn (x) - max f (x) max (x x )(x-- x10 )...(x-xn ), xa b xa b n( +1)! а затем и неравенство n( +1) max f (x) p (x) - max f (x) max (x x )(x-- x10 )...(x-x ). (4.11) n n xa b xa b xa b n( +1)! Фигурирующее в левой части этого неравенства выражение называют погрешностью интерполяции функции f на отрезке [a,b] ; неравенство (4.11) даёт оценку этой погрешности.

Замечание 4.4. Если на отрезке между крайними узлами интерполяции (n+1)-я производная интерполируемой функции меняется мало, то поведение погрешности при перемещении точки x по этому отрезку имеет характер, указанный в предыдущем пункте. Поэтому на практике узлы интерполяции стараются выбирать так, чтобы точка x, в которой требуется найти значение интерполируемой функции, была бы поближе к центру упомянутого отрезка.

Ситуации же, когда точка x вообще лежит вне этого отрезка (такой случай интерполирования называют экстраполяцией ), стараются избегать.

50. Задача об оптимальном выбореузлов интерполяции.

Пусть M – фиксированная постоянная: 0 < M <.

Обозначим через CM n+1[a,b] совокупность всех функций f, имеющих на [a,b] непрерывные производные до порядка n+1 включительно итаких, что n( +1) max f (x) M. (5.1) xa b Зафиксируем на [a,b] набор узлов интерполяции x0,x1,...,xn, один и тот же для всех функций f из класса CM n+1[a,b].

Качество интерполяции как способа приближённого нахождения значения функции f в точке естественно характеризовать величиной x x( ;{x };f ) = f (x)-pni (x;{xi};f ), (5.2) качество интерполяции как способа приближенной замены функции f многочленом на всём отрезке [a,b] - величиной {( xi};f ) = max f (x)-p (x;{xin };f ), (5.3) xa b а качество замены всех функций f класса CM n+1[a,b] их интерполяционными многочленами – величиной {( xi })= sup max f(x)-p (x;{xin };f). (5.4) +1n xa b Cf [a, ]b M Последняя величина ( её называют погрешностью интерполяции на классе функций CM n+1[a,b] ) уже независитот точки из [a,b] и функции f из CM n+1, x а определяется исключительно выбором узлов x0,x1,...,xn на отрезке [a,b]. В связи с этим возникает следующая оптимизационная Задача 5.1. Подобрать узлы интерполяции x0,x1,...,xn на отрезке [a,b] так, чтобы погрешность интерполяции на классе CM n+1[a,b] оказалась минимальной:

( x0,x1,...,xn ) min. (5.5) Переформулируем задачу (5.1), выразиввеличину (5.4) непосредственно через узлы x0,x1,...,xn.

Pages:     || 2 | 3 | 4 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.