40831

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

Лекция

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

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

Русский

2013-10-22

939 KB

91 чел.

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


 

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

81648. Марійка Підгірянка «Співанка про місяці», «Діти й ластівка». Загадка 191.5 KB
  Мета: збагачувати та розширювати знання учнів про життєвий і творчий шлях Марійки Підгірянки; розвивати мовлення учнів; виховувати любов до природи і рідного слова. Обладнання: портрет поетеси, збірки її творів, мультимедійна дошка, ілюстра ції до творів, презентація до уроку.
81649. В. Сухомлинський «Хлопчик і Дзвіночок Конвалії» 77 KB
  Подивіться, будь ласка, мабуть немає людини, байдужої до чарівної краси цих ніжних, витончених, дуже ароматних квітів. Наче якісь зачаровані сріблясті дзвіночки, повисають вони на зелених струнких ніжках посеред зеленого листя.
81650. Осінні мотиви в поезії Ліни Костенко 52 KB
  Обладнання: таблиці Шульте картки для читання карткилисточки зі словами робочий зошит зоровий диктант Хід уроку І. Читання віршів напам’ять. Учитель виразно у повільному темпі читає текст а потім запитує: Чи сподобався вам вірш Який настрій у вас після його слухання Підготовка до читання тексту.
81651. В.Нестайко «Жевжик» 72.5 KB
  Всеволод Зіновійович Нестайко народився на Житомирщині. Тож все своє свідоме життя Всеволод Нестайко прожив у Києві. Нестайка була вчителькою Коли Всеволод Нестайко був маленьким хлопчиком він страшенно хотів швидше вирости і стати великим та дорослим.
81652. «Коли тобі сутужно – прийде на поміч дружба А. Костецький «Буває все...», «Краще — з друзями разом!», «Словник Славка» 58.5 KB
  Удосконалювати вміння виразно читати вірші визначати головну думку прочитаного; розвивати мовлення учнів уміння аналізувати віршовані твори виділяти головне висловлювати оцінні судження збагачувати словниковий запас; виховувати почуття товариськості.
81653. Поетичні картини ранньої і пізньої осені в творах Ліни Костенко 37.5 KB
  Книга природи – наймудріша книга. Спілкування з природою дає нам радість. Природа – це джерело краси, яка не може залишити байдужою навіть найнезворушливішу людину. Не випадково багато видатних мислителів і письменників, художників і поетів, зодчих і композиторів прагнули втілити у своїх творах нетлінну красу природи.
81654. Ми тебе не забули, Тарасе! 871 KB
  Шевченка виставка книг Шевченка виставка літератури про Шевченка Ім’я освячене любов’ю портфоліо Життєвий шлях плакат літопис долі Кобзаря газета Шевченко художник репродукції картин квітка пам’яті Вінок Заповітів Шевченка кросворд плакат Шануємо Кобзаря карта Шевченківських місць в Україні дитячі малюнки до пейзажної лірики.
81655. Краса мрій про майбутнє і нове 83 KB
  У гірській країні на схилі великої і старої гори знайшов прихисток маленький Горбик. А маленький Горбок мріяв про казки чарівні далекІ країни і чудеса які йому ніяк не вдавалося побачити самому. З усіх боків його оточували високі гори і тому Горбок міг мріючи дивитися тільки вгору на безмежно таємниче і загадкове зоряне небо.
81656. Перенос слова 36.5 KB
  Задачи: Образовательная: на основе занимательной литературы развивать умение переносить слова с учетом особенностей слогов и изученных правил; Развивающая: развивать умение сравнивать, анализировать, обобщать; развивать наблюдательность, внимание, память, активность, грамотную речь учащихся;