atesting.ru Новости Lagrange interpolating polynomial

Lagrange interpolating polynomial

Введение

Постановка математической задачи

Одной из основных задач численного анализа является задача об интерполяции функций.
Пусть на отрезке задана сетка и в её узлах заданы значения функции , равные . Требуется построить интерполянту — функцию , совпадающую с функцией в узлах сетки:

( 1 )

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

Интерполируюшие функции , как правило строятся в виде линейных комбинаций некоторых элементарных функций:

где — фиксированный линейно независимые функции, — не определенные пока коэффициенты.

Из условия получаем систему из уравнений относительно коэффициентов :

.

Тогда по заданным однозначно определяются коэффициенты .

Виды интерполяции

Самым простым видом является интерполяция методом ближайшего соседа. С помощью этого способа мы получаем очень приблизительный график, состоящий из прямоугольников. Если вы видели хоть раз объяснение геометрического смысла интеграла на графике, то поймёте, о каком графическом виде идёт речь.

Кроме этого, существуют и другие методы интерполяции. Самые известные и популярные связаны с многочленами. Они более точны и позволяют предсказывать поведение функции при достаточно скудном наборе значений. Первым методом интерполяции, который мы рассмотрим, будет линейная интерполяция многочленами. Это самый простой способ из данной категории, и им наверняка каждый из вас пользовался в школе. Суть его заключается в построении прямых между известными точками. Как известно, через две точки плоскости проходит единственная прямая, уравнение которой можно найти исходя из координат данных точек. Построив эти прямые, мы получаем ломаный график, который худо-бедно, но отражает примерные значения функций и в общих чертах совпадает с реальностью. Так и осуществляется линейная интерполяция.

Интерполяция (координат)

Есть сетка координат на карте (изображении).
На ней есть некоторые известные опорные точки (n>3), имеющие по два значения x,y — координаты в пикселах, и координаты в метрах.
Необходимо найти промежуточные значения координат в метрах, зная координаты в пикселах.
Линейная интерполяция не подходит — слишком большая погрешность за пределами линии.
Вот так: (Xc — коорд. в метрах по ох, Xp — коорд. в пикселах по ох, Xc3 — искомое значение по ох)
Xc3= (Xc1-Xc2)/(Xp1-Xp2)*(Xp3-Xp2)+Xc2
Yc3= (Yc1-Yc2)/(Yp1-Yp2)*(Yp3-Yp2)+Yc2

Как найти такую же формулу для нахождения Xc и Yc, учитывая не две (как тут), а N известных опорных точек?

Joka fern lowd

Судя по выписанным формулам, оси систем координат в пикселах и в метрах совпадают?
То есть независимо интерполируется Xp -> Xc и независимо Yp -> Yc. Если нет, то надо использовать двумерную интерполяцию Xp,Yp->Xc и Xp,Yp->Yc, что несколько усложняет задачу.
Далее подразумевается, что координаты Xp и Xc связаны некоторой зависимостью.
Если характер зависимости известен (или предполагается, например, предполагаем, что Xc=a*Xp^2+b*Xp+c), то можно получить параметры этой зависимости (для приведенной зависимости a, b, c) с помощью регрессионного анализа (Метод наименьших квадратов) . В этом методе, если задаться определенной зависимостью Xc(Xp) можно получить формулу для параметров зависимости от опорных данных. Этот метод позволяет, в частности, найти и линейную зависимость, наилучшим образом удовлетворяющую данному набору данных.
Недостаток: В этом методе координаты Xc, полученные по данным опорных точек Xp, могут отличаться от заданных. Как например, аппроксимационная прямая проведенная по экспериментальным точкам, не проходит точно через сами эти точки.
Если же требуется точное соответствие и характер зависимости неизвестен, нужно использовать интерполяционные методы. Простейшим математически является интерполяционный полином Лагранжа, точно проходящий через опорные точки. Однако в силу высокой степени этого полинома при большом числе опорных точек и плохого качества интерполяции, лучше его не использовать. Преимуществом является сравнительно простая формула.
Лучше использовать интерполяцию сплайнами. Суть этого метода в том, что на каждом участке между двумя соседними точками, исследуемая зависимость интерполируется полиномом, а в точках сшивки двух интервалов записываются условия гладкости. Преимуществом этого метода является качество интерполяция. Недостатками — практически невозможно вывести общую формулу, приходится находить коэффициенты полинома на каждом участке алгоритмически. Другим недостатком является сложность обобщения на двумерную интерполяцию.

Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных.

Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты , какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах.

Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса-Торина (Riesz-Thorin theorem) и теорема Марцинкевича (Marcinkiewicz theorem), являющиеся основой для множества других работ.

Усложнённые виды интерполяции

Есть более интересный, но при этом более сложный способ интерполяции. Его придумал французский математик Жозеф Луи Лагранж. Именно поэтому расчет интерполяции по этому методу назван его именем: интерполяция по методу Лагранжа. Фокус тут вот в чём: если способ, изложенный в предыдущем абзаце, использует для расчета только линейную функцию, то разложение методом Лагранжа предполагает также использование многочленов более высоких степеней. Но не так просто найти сами формулы интерполяции для разных функций. И чем больше точек известно, тем точнее получается формула интерполяции. Но есть и масса других методов.

Существует и более совершенный и приближенный к реальности метод расчета. Формула интерполяции, используемая в нём, представляет собой совокупность многочленов, применение каждого из которых зависит от участка функции. Такой метод называется сплайн-функцией. Кроме того, есть ещё и способы, позволяющие провести такую вещь, как интерполяция функций двух переменных. Тут всего два метода. Среди них билинейная или двойная интерполяция. Этот способ позволяет без труда построить график по точкам в трёхмерном пространстве. Другие методы затрагивать не будем. Вообще, интерполяция — это универсальное называние для всех этих способов построения графиков, но многообразие способов, которыми можно осуществить это действие, заставляет делить их на группы в зависимости от вида функции, которая подлежит этому действию. То есть интерполяция, пример которой мы рассмотрели выше, относится к прямым способам. Есть также обратная интерполяция, которая отличается тем, что позволяет вычислить не прямую, а обратную функцию (то есть x от y). Рассматривать последние варианты мы не будем, так как это достаточно сложно и требует хорошей математической базы знаний.

Перейдём к, пожалуй, одному из важнейших разделов. Из него мы узнаем, как и где обсуждаемая нами совокупность методов применяется в жизни.

1.4. Интерполяционная формула Лагранжа

Предложенный Лагранжем алгоритм построения интерполирующих

функций по таблицам (1) предусматривает построение интерполяционного многочлена Ln(x) в виде

Очевидно, что выполнение для (10) условий (11) определяет выполнение условий (2) постановки задачи интерполяции.

Многочлены li(x) записываются следующим образом

Отметим, что ни один множитель в знаменателе формулы (14) не равен нулю. Вычислив значения констант сi, можно использовать их для вычисления значений интерполируемой функции в заданных точках.

Формула интерполяционного многочлена Лагранжа (11) с учётом формул (13) и (14) может быть записана в виде

qi (x − x0)(x − x1) K (x − xi −1)(x − xi +1) K (x − xn)

1.4.1.Организация ручных вычислений по формуле Лагранжа

Непосредственное применение формулы Лагранжа приводит к большому числу однотипных вычислений. Для таблиц небольшой размерности эти вычисления могут быть выполнены как вручную, так и в среде программ

На первом этапе рассмотрим алгоритм вычислений, выполняемых вручную. В дальнейшем эти же вычисления следует повторить в среде

Microsoft Excel или OpenOffice.org Calc.

На рис. 6 приведён пример исходной таблицы интерполируемой функции, определяемой четырьмя узлами.

Рис.6. Таблица, содержащая исходные данные для четырёх узлов интерполируемой функции

В третий столбец таблицы запишем вычисляемые по формулам (14) значения коэффициентов qi. Ниже приведена запись этих формул для n=3.

q0=Y0/(x0-x1)/(x0-x2)/(x0-x3)q1=Y1/(x1-x0)/(x1-x2)/(x1-x3)(16) q2=Y2/(x2-x0)/(x2-x1)/(x2-x3)q3=Y3/(x3-x0)/(x3-x1)/(x3-x2)

Следующим шагом в реализации ручных вычисления являются вычисления значений li(x) (j=0,1,2,3), выполняемые по формулам (13).

Запишем эти формулы для рассматриваемого нами варианта таблицы с четырьмя узлами:

l0(x)=q0(x-x1)·(x-x2)·(x-x3),

l1(x)=q1(x-x0)·(x-x2)·(x-x3),

l2(x)=q2(x-x0)·(x-x1)·(x-x3),(17) l3(x)=q3(x-x0)·(x-x1)·(x-x2).

Вычислим значения многочленов li(xj) (j=0,1,2,3) и запишем их в ячейки таблицы. Значения функцииYрасч(x), согласно формуле (11) будут получены в результате суммирования значенийli(xj) по строкам.

Формат таблицы, включающей столбцы вычисленных значений li(xj) и столбец значенийYрасч(x), показан на рис.8.

Рис. 8. Таблица с результатами ручных вычислений, выполненных по формулам (16), (17) и (11) для всех значений аргумента xi

Выполнив формирование таблицы, приведённой на рис. 8, по формулам (17) и (11) можно вычислить значение интерполируемой функции для любого значения аргумента Х. Например, дляХ=1 вычисляем значенияli(1) (i=0,1,2,3):

l0(1)= 0,7763; l1(1)= 3,5889; l2(1)=-1,5155;l3(1)= 0,2966.

Суммируя значения li(1) получим значениеYинтерп(1)=3,1463.

Реальный пример: Клиническое испытание лекарств

Вернемся к реальному примеру использования сплайнов в клинических испытаниях лекарств, о котором уже упоминалось в самом начале.

Очень важной характеристикой лекарственного препарата является т.н. AUC (Area under the plasma drug concentration-time curve) — площадь под кривой концентрация-время

Данная кривая отражает фактическое воздействие препарата на организм человека после введения определенной дозы. Величина AUC измеряется в мг · ч / л. Площадь под кривой зависит от скорости выведения препарата из организма и введенной дозы. Общее количество препарата, выведенного из организма, можно подсчитать суммированием или интегрированием количества препарата, выведенного в каждый отдельный момент времени.

Величина AUC прямо пропорциональна дозе введенного препарата для препаратов с линейной фармакокинетикой и обратно пропорциональна т.н. показателю клиренс (clearance) препарата. Чем больше клиренс, тем меньше времени препарат находится в кровеносной системе и тем быстрее снижается его концентрация в плазме. В этом случае воздействие препарата на организм и площадь под кривой концентрация-время меньше.

В ходе клинических исследований, зависимость концентрации препарата в крови от времени может быть определена путем измерения концентрации в отдельные моменты времени. Затем, строится график концентрации и производится оценка AUC.

Часто для оценки AUC применяют метод трапеций: площадь под графиком концентрация-время разбивается на трапеции и AUC вычисляется суммированием площадей этих трапеций (что по сути эквивалентно интерполяции линейными функциями).

AUC = AUC0-2+AUC2-4+AUC4-6+AUC6-8+AUC8-10+AUC10-12+AUClast-infinity

В данной же статье приведем пример более точной оценки AUC, полученной, когда функция концентрации интерполируется кубическими сплайнами.

Пусть имеются данные о концентрации, полученные в ходе исследования:

Построим по ним диаграмму рассеяния и интерполируем значения при помощи сплайна в программе STATISTICA.

Как видно из графика, максимальное значение концентрации Сpmax = 29,78 мг/л соответствует времени tmax = 8 ч. Воспользуемся редактором данных графика и получим значения подгонки:

Рассчитаем по ним описанным выше методом трапеций значение AUC. Получим, AUC = 716,11 мг · ч / л.

Список литературы:

В.П.Боровиков. STATISTICA. Искусство анализа данных на компьютере: для профессионалов (2-е издание), СПб.: Питер, 2003. – 688 с.: ил.

E.A.Волков. Численные методы. Москва, “Наука”, Главная редакция физико-математической литературы, 1987 г.

Онлайн ресурс Лозаннского университета:http://sepia.unil.ch/pharmacology

Матричная форма

можно записать P(x) = ax + b следующим образом P(x)=(ab)(x1){\displaystyle P(x)={\begin{pmatrix}a&b\end{pmatrix}}{\begin{pmatrix}x\\1\\\end{pmatrix}}}

условия будут записаны так:
(ab)(xx111)=(PP1){\displaystyle {\begin{pmatrix}a&b\end{pmatrix}}{\begin{pmatrix}x_{0}&x_{1}\\1&1\\\end{pmatrix}}={\begin{pmatrix}P_{0}&P_{1}\\\end{pmatrix}}}

отсюда можно найти:
(ab)=(PP1)(xx111)−1{\displaystyle {\begin{pmatrix}a&b\end{pmatrix}}={\begin{pmatrix}P_{0}&P_{1}\\\end{pmatrix}}{\begin{pmatrix}x_{0}&x_{1}\\1&1\\\end{pmatrix}}^{-1}}
Получаем:P(x)=(PP1)(xx111)−1(x1){\displaystyle P(x)={\begin{pmatrix}P_{0}&P_{1}\\\end{pmatrix}}{\begin{pmatrix}x_{0}&x_{1}\\1&1\\\end{pmatrix}}^{-1}{\begin{pmatrix}x\\1\\\end{pmatrix}}}
Распространяя на:

двухмерный случай (треугольник):

P(x,y)=(PP1P2)(xx1x2yy1y2111)−1(xy1){\displaystyle P(x,y)={\begin{pmatrix}P_{0}&P_{1}&P_{2}\\\end{pmatrix}}{\begin{pmatrix}x_{0}&x_{1}&x_{2}\\y_{0}&y_{1}&y_{2}\\1&1&1\\\end{pmatrix}}^{-1}{\begin{pmatrix}x\\y\\1\\\end{pmatrix}}}

трёхмерный случай (тетраэдр):

P(x,y,z)=(PP1P2P3)(xx1x2x3yy1y2y3zz1z2z31111)−1(xyz1){\displaystyle P(x,y,z)={\begin{pmatrix}P_{0}&P_{1}&P_{2}&P_{3}\\\end{pmatrix}}{\begin{pmatrix}x_{0}&x_{1}&x_{2}&x_{3}\\y_{0}&y_{1}&y_{2}&y_{3}\\z_{0}&z_{1}&z_{2}&z_{3}\\1&1&1&1\\\end{pmatrix}}^{-1}{\begin{pmatrix}x\\y\\z\\1\\\end{pmatrix}}}

/ Material_studentam_po_RGR_BZhD / Как выполнить интерполяцию

Формула для интерполяции табличных данных

Используется во 2-ом действии, когда количество НХР (Q, т) из условия имеет промежуточное значение между
100 т и 300 т.

(Исключение:
если Q по условию равно 100 или 300 – то интерполяция не нужна).

y
o
— Ваше исходное количество НХР из условия, в тоннах

(соответствует букве Q)

y
1
меньшее

(из табл.11-16, как правило равно 100
).

y
2
большее

ближайшее к Вашему значение количества НХР, в тоннах

(из табл.11-16, как правило равно 300
).

x
1
y
1
(x
1
расположено напротив y
1
), км.

x
2
– табличное значение глубины распространения облака зараженного воздуха (Г т), соответственно y
2
(x
2
расположено напротив y
2
), км.

x
– искомое значение Г
т
соответствующее y
o
(по формуле).

Пример.

НХР – хлор; Q = 120 т;

Вид СВСП (степень вертикальной стойкости воздуха) – инверсия.

Найти Г
т
— табличное значение глубины распространения облака зараженного воздуха.

Просматриваем таблицы 11-16 и находим данные соответствующие вашему условию (хлор, инверсия).

Подходит таблица 11.

Выбираем значения y
1
,
y
2,
x
1
,
x
2
.
Важно

– скорость ветра берем 1 м/с., температуру берем – 20 оС. Подставляем выбранные значения в формулу и находим x

Подставляем выбранные значения в формулу и находим x
.

Важно

– расчет правильный, если x
будет иметь значение где-то междуx
1
,
x
2
.

Геометрическая интерполяция

При геометрической интерполяции значения результирующей динамики пропорциональны
значению инкремента и обратно пропорциональны фактору, вычисленному на
основе инкремента. Инкремент экспоненциально зависит от логарифма относительного
прироста исходной динамики, умноженного на длину периода результирующей
динамики.

Рассмотрим принцип геометрического метода на примере вычисления квартальных
данных на основе годовых.

  • X[t]
    – исходные данные по годам;

  • Inc[t] = exp(log(X[t+1] / X[t]) / 4)
    – значение инкремента;

  • Factor[t] = (1 + Inc[t] + Inc[t]^2 + Inc[t]^3) / 4
    – значение фактора;

  • X[t,1], X[t,2], X[t,3], X[t,4]
    – квартальные данные в год t.

Из этого следует:

  • X[t,1] = X[t] / Factor[t];

  • X[t,2] = X[t] * Inc[t] / Factor[t];

  • X[t,3] = (X[t] * Inc[t]^2) / Factor[t];

  • X[t,4] = (X[t] * Inc[t]^3) / Factor[t].

Интерполяция для других динамик осуществляется аналогичным образом.