40831

АППРОКСИМАЦИЯ ФУНКЦИЙ

Лекция

Информатика, кибернетика и программирование

Как упростить вычисление известной функции fx или же ее характеристик если fx слишком сложная Ответы на эти вопросы даются теорией аппроксимации функций основная задача которой состоит в нахождении функции y=x близкой т. Обоснование способов нахождения удачного вида функциональной зависимости и подбора параметров составляет задачу теории аппроксимации функций. В зависимости от способа подбора параметров получают различные методы аппроксимации; наибольшее распространение среди них получили интерполяция и среднеквадратичное...

Русский

2013-10-22

939 KB

97 чел.

 ТЕМА 3. АППРОКСИМАЦИЯ ФУНКЦИЙ

3.1. Зачем нужна аппроксимация функций?

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

В практике расчетов, связанных с обработкой экспериментальных данных, вычислением f(x), разработкой вычислительных методов, встречаются следующие две ситуации:

1. Как установить вид функции y=f(x), если она неизвестна? Предполагается при этом, что задана таблица ее значений , которая получена либо из экспериментальных измерений, либо из сложных расчетов.

2. Как упростить вычисление известной функции f(x) или же ее характеристик , если f(x) слишком сложная?

Ответы на эти вопросы даются теорией аппроксимации функций, основная задача которой состоит в нахождении функции y=(x), близкой (т.е. аппроксимирующей) в некотором нормированном пространстве к исходной функции y=f(x). Функцию (x) при этом выбирают такой, чтобы она была максимально удобной для последующих расчетов.

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

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

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

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

      .       (3.1)

Здесь  – известная система линейно независимых (базисных) функций. В качестве  в принципе могут быть выбраны любые элементарные функции, например: тригонометрические, экспоненты, логарифмические или комбинации таких функций. Важно, чтобы система базисных функций была полной, т.е. обеспечивающей аппроксимацию f(x) многочленом (3.1) с заданной точностью при .

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

;

.

Заметим, что если функция  задана на отрезке [a, b], то при использовании этой системы необходимо предварительно осуществить преобразование координат , приводящее интервал  к интервалу .

Для аппроксимации периодических функций используют ортогональную на [a, b] систему тригонометрических функций  . В этом случае обобщенный многочлен (3.1) записывается в виде .

3.2. Что такое интерполяция?

 Интерполяция является одним из способов аппроксимации функций. Суть ее состоит в следующем. В области значений x, представляющей некоторый интервал [a, b], где функции f и  должны быть близки, выбирают упорядоченную систему точек (узлов)  (обозначим ), число которых равно количеству искомых параметров . Далее параметры  подбирают такими, чтобы функция  совпадала с f(x) в этих узлах,  (рис.3.1), для чего решают полученную систему из n алгебраических в общем случае нелинейных уравнений.

В случае линейной аппроксимации (3.1) система для нахождения коэффициентов  линейна и имеет следующий вид:

 (3.2)

Система базисных функций , используемых для интерполяции, должна быть чебышевской, т.е. такой, чтобы определитель матрицы системы (3.2) был отличен от нуля и, следовательно, задача интерполяции имела единственное решение.

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

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

Общий вид алгебраического многочлена 

   .    (3.3)

Матрица системы (3.2) в этом случае имеет вид

        ,     (3.4)

и ее определитель (это определитель Вандермонда) отличен от нуля, если точки xi разные. Поэтому задача (3.2) имеет единственное решение, т.е. для заданной системы различных точек существует единственный интерполяционный многочлен.

 Погрешность аппроксимации функции f(x) интерполяционным многочленом степени , построенным по n точкам, можно оценить, если известна ее производная порядка n, по формуле

           (3.5)

Из (3.5) следует, что при h0 порядок погрешности p (см. подразд. 1.4) при интерполяции алгебраическим многочленом равен количеству выбранных узлов p=n. Величина  может быть сделана малой как за счет увеличения n, так и уменьшения h. В практических расчетах используют, как правило, многочлены невысокого порядка (n  6), в связи с тем что с ростом n резко возрастает погрешность вычисления самого многочлена из-за погрешностей округления.

3.3. Какие бывают многочлены и способы интерполяции?

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

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

Интерполяционный многочлен Ньютона (PN)

.      (3.6)

Здесь  – текущая точка, в которой надо вычислить значение многочлена,         – разделенные разности порядка k, которые вычисляются по следующим рекуррентным формулам:

Схема расчета многочлена Ньютона представлена на рис. 3.2.

Линейная (PNL) и квадратичная(PNS) интерполяция

Вычисления по интерполяционной формуле (3.6) для n > 3 используют редко. Обычно при интерполяции по заданной таблице из m>3 точек применяют квадратичную n=3 или линейную n=2 интерполяцию. В этом случае для приближенного вычисления значения функции f в точке x находят в таблице ближайший к этой точке i-узел из общей таблицы, строят интерполяционный многочлен Ньютона первой или второй степени по формулам

     (3.7)

и за значение f(x) принимают  (линейная интерполяция) или  (квадратичная интерполяция). Схема расчета для линейной и квадратичной интерполяции приведена на рис. 3.3.

Интерполяционный многочлен Лагранжа (PL)

             (3.8)

Многочлены  выбраны так, что во всех узлах, кроме k-го, они обращаются в ноль, в k-м узле они равны единице:

Поэтому из выражения (3.8) видно, что .

Схема расчета интерполяционного многочлена Лагранжа представлена на рис. 3.4.

Интерполяция общего вида, использующая прямое                                          решение системы (3.2) методом Гаусса (POG)

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

Поэтому когда требуется производить много вычислений многочлена, построенного по одной таблице, оказывается выгодно вначале один раз найти коэффициенты  и затем использовать формулу (3.3). Коэффициенты  находят прямым решением системы (3.2) c матрицей (3.4), затем вычисляют его значения по экономно программируемой формуле (алгоритм Горнера)

   .     (3.9)

Схема расчета интерполяционного многочлена общего вида по формуле (3.9) с прямым решением системы (3.2) приведена на рис.3.5.

Интерполяция общего вида, использующая расчет коэффициентов          многочлена (3.3) через  многочлен Лагранжа (POL)

Находить коэффициенты  многочлена (3.3) можно, не решая прямо систему (3.2), а используя разложение коэффициентов Лагранжа (3.8):

  .     (3.10)

Рекуррентные формулы для нахождения коэффициентов :

             (3.11)

получаются из вида многочленов , если использовать очевидное представление

Схема алгоритма вычисления коэффициентов многочлена общего вида по формулам (3.10), (3.11) представлена на рис. 3.6.

3.4. Что такое среднеквадратичная аппроксимация?

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

            .         (3.12)

В случае линейной аппроксимации (3.1) задача (3.12) сводится к решению СЛАУ для нахождения необходимых коэффициентов :

               (3.13)

Здесь  – скалярные произведения в L2.

Матрица системы (3.13) симметричная, и ее следует решать методом квадратного корня.

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

Тогда матрица СЛАУ (3.13) диагональная и параметры  находятся по формуле

.

В этом случае представление (3.1) называется обобщенным рядом Фурье, а  называются коэффициентами Фурье.

Метод наименьших квадратов (МНК)

МНК является частным случаем среднеквадратичной аппроксимации. При использовании МНК в области значений x, представляющей некоторый интервал [a, b], где функции f и должны быть близки, выбирают систему различных точек (узлов) x1, ..., xm, число которых обычно больше, чем количество искомых параметров ,  Далее, потребовав, чтобы сумма квадратов невязок во всех узлах была минимальна (рис. 3.7):

)

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

                   (3.14)

получаем систему n линейных уравнений относительно n неизвестных  следующего вида:

        или  .      (3.15)

Здесь  – векторы-таблицы функ-ций. Элементы матрицы G и вектора  в (3.15) определяются выражениями

 – скалярные произведения векторов.

 Система (3.15) имеет симметричную матрицу G и решается методом квадратного корня.

При аппроксимации по МНК обычно применяют такие функции , которые используют особенности решаемой задачи и удобны для последующей обработки.

Схема расчета коэффициентов многочлена вида (3.3) по методу наименьших квадратов представлена на рис. 3.8.

Приведем пример аппроксимации по МНК. Предположим, что известна таблица значений f(x): {x1=1, y1=0.5, x2=2, y2=1.2, x3=3, y3=0.8}, т.е. m=3. Требуется найти параметры аппроксимирующей функции  вида         ,  (n=2).

Составляем сумму квадратов невязок

Условия минимума (3.14):

 

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

  

Решая ее, находим  .

На рис. 3.9 приведена таблица функции f(x) и полученная по МНК функция (x).

Порядок расчета по МНК следующий. Вначале по исходной таблице формируется матрица G и рассчитываются коэффициенты (см. рис. 3.8) (в качестве jk(x) здесь берется функция xk-1). Затем, используя полученные коэффициенты, рассчитывается значение функции в искомой точке (см. рис. 3.5, б).

3.5. Варианты заданий

Во всех вариантах (табл. 3.1.) требуется аппроксимировать заданную исходную функцию f(x) многочленом на интервале [a, b]. Задано количество неизвестных параметров n, вид аппроксимации и m – количество точек, в которых задана функция. Таблица исходной функции yi=f(xi) вычисляется в точках  Используя полученную таблицу  требуется вычислить значения функций  и погрешность  в точках , построить графики и проанализировать качество полученной аппроксимации.

           Таблица 3.1

N вар.

Функция f(x)

a

b

m

n

Вид аппроксимации

1

–2

3

11

3

МНК

2

0

3

4

4

Ньютона PN

3

1

8

4

4

Лагранжа PL

4

4

7

4

4

Общего вида POG

5

5

8

4

4

Общего вида POL

6

3

6

11

2

Линейная PNL

7

1

4

11

4

МНК

8

0

4

11

3

Квадратичная PNS

9

–8

2

5

5

Ньютона PN

10

–2

5

5

5

Лагранжа PL

11

–5

3

5

5

Общего вида POG

12

–1

4

5

5

Общего вида POL

13

1

7

11

5

МНК

14

–2

5

11

3

Квадратичная PNS

15

–4

2

11

2

Линейная PNL

3.6. Контрольные вопросы

1. Как ставится задача линейной аппроксимации функций?

2. Что такое интерполяция, ее геометрическая интерпретация?

3. Напишите интерполяционный многочлен Ньютона 2-го порядка.

4. Напишите интерполяционный многочлен Лагранжа 2-го порядка.

5. Как осуществляется аппроксимация по методу наименьших квадратов и его геометрическая интерпретация?

6. Выведите СЛАУ относительно коэффициентов функции  по МНК для таблицы .

PAGE  30


 

А также другие работы, которые могут Вас заинтересовать

60955. РОЗГАЛУЖЕНІ АЛГОРИТМИ. ОПЕРАТОРИ ВИБОРУ 70.5 KB
  Структура умовного оператора. В Паскалі такими засобами є умовний оператор і оператор варіанту. Кожный умовний оператор припускає виконування однієї з двох дій в залежності від істинності деякої умови.
60956. КЛАСИФІКАЦІЯ КОМПЮТЕРНИХ МЕРЕЖ 91.5 KB
  За правом доступу до ресурсів виділяють такі види компютерних мереж: персональні PN англ. Персональна мережа обєднує власні електронні пристрої користувачів персональні компютери ноутбуки кишенькові компютери мобільні телефони смартфони комунікатори тощо...
60957. 8 Березня – свято весни 51 KB
  Кожна команда отримує назву страви і конверт з інгридієнтами що входять до неї або ні. Переможець: команда що дасть правильну відповідь. Виграє та команда у якої буде правильна відповідь Лунає аудіо запис пісні...
60958. СВЯТА МОЯ КИЇВСЬКА РУСЬ 64.5 KB
  Князь Володимир який на той час правив державою спочатку теж служив язичницьким богам ставив ідолів приносив їм жертви. А що може їх обєднати Князь Володимир прийшов до думки про єдину віру.
60960. Роль читання в процесі навчання мовного спілкування на уроках англійської мови 115.5 KB
  Читання є одним з найважливіших засобів отримання інформації та в житті сучасної освіченої людини займає значне місце. У реальному житті читання виступає як окремий самостійний вид комунікативної діяльності мотивом...