40831

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

Лекция

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

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

Русский

2013-10-22

939 KB

84 чел.

 ТЕМА 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


 

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

50964. Критика А. Шопенгауэром концепции соотношения рассудка и разума в теории познания И. Канта 247.5 KB
  Идеи Шопенгауэра невозможно адекватно постичь без знания философии Канта. Структура и проблематика кантовской системы – вот та основа, на которой в первую очередь формируются взгляды Шопенгауэра. Это относится как к прямым заимствованиям у Канта
50965. Организация данных. Типы и структуры данных 96.5 KB
  Понятие тип данных делает манипулирование данными с использованием средств вычислительной техники абстрактным процессом и скрывает лежащее в основе обращения с ними представление их в виде двоичного кода. Виды типов данных: Аналоговые данные...
50966. Можливості використання здобутків теорії поля для моделювання та прогнозування реальної поведінки споживача 25.1 KB
  Передбачення майбутнього неможливе за багатьох обставин. Жоден екстрасенс не зможе сказати, наскільки успішним буде той чи інший товар, який підприємство планує вивести на ринок. Навіть з урахуванням безлічі математичних моделей, значної кількості змінних, залишається так звана «чорна скринька» свідомості споживача.
50967. Средства вычислительной техники. Принципы построения функциональных узлов и устройств ЭВМ 5.49 MB
  Для отечественных системотехников и специалистов в области ВТ отсутствие отечественных микросхем современного уровня компилируется допустимостью зарубежной элементной базы, поэтому Вам, как специалистам в области информационных технологий, изучение аппаратных средств ВТ, то есть цифровых узлов и устройств во всем ее разнообразии имеет большое практическое значение.
50968. Информация, сообщения, сигналы. Структурная схема системы передачи информации 66 KB
  В узком смысле кодирование – это отображение дискретных сообщений сигналами в виде определенных сочетаний символов. Под помехами подразумеваются любые мешающие внешние возмущения или воздействия атмосферные помехи влияние посторонних источников сигналов а также искажения сигналов в самой аппаратуре аппаратурные помехи вызывающие случайное отклонение принятого сообщения сигнала от передаваемого. Решающее устройство помещенное после приемника осуществляет обработку принятого сигнала с целью наиболее полного извлечения из него...
50969. ИНФОРМАЦИОННАЯ МЕРА ШЕННОНА 431 KB
  Количество информации и избыточность. Пусть и случайные величины с множествами возможных значений Количество информации при наблюдении случайной величины с распределением вероятностей задается формулой Шеннона: Единицей измерения количества информации является бит который представляет собой количество информации получаемое при наблюдении случайной величины имеющей два равновероятных значения. При равномерном распределении количество информации задается формулой Хартли: . Имеются два источника информации алфавиты и...
50970. Измерение информации 79 KB
  Информация и теории информации Информация лат. Из Энциклопедии кибернетики В широком смысле – отражение реального мира; В узком смысле – любые сведения являющиеся объектом хранения передачи и преобразования информации. Теории информации Структурная теория информации рассматривает структуру построения отдельных информационных сообщений.
50971. Информационная мера Шеннона 440 KB
  Количество информации и избыточность Дисктретные системы передачи информации Непрерывные системы передачи информации Слайды к лекции Количество информации и избыточность Количество информации и избыточность.