Вернуться наверх
aco.ifmo.ru photonic
вернуться в оглавление предыдущая глава предыдущий параграф следующий параграф следующая глава


4. Аппроксимация

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

4.1. Задача аппроксимации

Предположим, имеется набор из n точек (xi yi), полученных в результате эксперимента, и необходимо аппроксимировать (описать) эти данные некоторой функцией f(x). Если исходные данные были получены с высокой точностью и количество точек не очень большое, то можно аппроксимировать данные функцией, которая проходит через все узловые точки. На практике экспериментально полученные данные всегда обладают погрешностью, часто довольно значительной, тогда при аппроксимации можно провести кривую таким образом, чтобы ее отклонение от всех точек было минимальным, но при этом она не обязательно будет проходить через каждую точку (рис.4.1). Такая аппроксимация сгладит погрешность первоначальных данных.

y1 x1
y2 x2
yi xi
yn xn

Рис.4.1. Задача аппроксимации

Представим аппроксимирующую функцию в виде суммы произведений коэффициентов с0, с1, …, сm и базисных функций g0, g1, …, gm:

,           (4. 1)

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

Во многих случаях в качестве базисной функции выбирают степенной полином:

,           (4.2)

4.2. Система линейных алгебраических уравнений (СЛАУ)

Для определения неизвестных коэффициентов составим систему линейных уравнений. В общем случае система линейных алгебраических уравнений (СЛАУ) – это система из m линейных алгебраических уравнений с n  неизвестными:

          (4. 3)

где m – количество уравнений,  n – количество неизвестных, x1, x2, …, xn – неизвестные, которые надо определить, a11, a12, …, amn – коэффициенты системы, b1, b2, … bm – свободные члены (известны).

Систему линейных алгебраических уравнений можно записать в матричной форме:

          (4.4)

или

          (4.5)

где A – матрица системы, X – столбец неизвестных, B – столбец свободных членов:

          (4.6)

Решение системы линейных алгебраических уравнений сводиться к нахождению значений элементов столбца неизвестных X (корней системы) по известным A и B. Необходимым и достаточным условием существования единственного решения системы линейных алгебраических уравнений является условие , то есть определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A называется вырожденной, и при этом СЛАУ либо не имеет решения, либо имеет бесчисленное множество решений.

Если матрица системы квадратная, и ее определитель не равен нулю, систему можно решить одним из следующих методов.

Метод Крамера

При небольшой размерности системы m для решения часто используют метод Крамера:

          (4.7)

где  – определитель матрицы системы,  – определитель матрицы системы, где вместо i-го столбца стоит столбец правых частей.

Для больших матриц решение методом Крамера является слишком долгим и трудоемким.

Метод Гаусса

Наиболее известным и популярным прямым методом решения СЛАУ является метод Гаусса. Этот метод заключается в последовательном исключении неизвестных, когда система уравнений (матрица A) приводится к равносильной системе треугольного вида (прямой ход метода Гаусса). Затем  из полученной треугольной матрицы последовательно, начиная с последних по номеру, находятся все переменные системы (обратный ход метода Гаусса).

Метод обратной матрицы

Если , то существует обратная матрица . Тогда решение СЛАУ можно записать в виде:

          (4.8)

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

4.3. Пример использование СЛАУ для решения задачи аппроксимации

Систему линейных алгебраических уравнений можно применить и для решения задачи аппроксимации. Например, аппроксимируем n имеющихся точек (xi yi) параболой:

          (4.9)

Тогда в столбец неизвестных можно записать искомые коэффициенты с0, с1, с2, в столбец свободных членов – известные значения y0,…, yn, а в матрицу системы – вычисленные значения для каждого yi при каждом коэффициенте с0, с1, с2:

, ,           (4.10)

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

Для переопределенных СЛАУ (количество уравнений больше количества неизвестных m > n) система не имеет единственного точного решения, но можно найти “оптимальный” вектор X. В этом случаем для решения СЛАУ используется метод наименьших квадратов (МНК). При помощи этого метода коэффициенты аппроксимирующей функции вычисляются таким образом, чтобы среднеквадратичное отклонение экспериментальных данных от найденной аппроксимирующей функции (сумма квадратов отклонений между векторами  и  уравнения (4.5)) было наименьшим:

, где           (4.11)

Для вывода решения системы линейных уравнений методом наименьших квадратов перепишем выражение (4.5), с добавлением вектора погрешности :

          (4.12)

          (4.13)

Теперь задача сводится к минимизации квадрата нормы вектора погрешности :

          (4.14)

          (4.15)

          (4.16)

Для нахождения минимума необходимо вычислить частную производную по X уравнения (4.16) и приравнять ее к 0:

          (4.17)

Отсюда находим значение вектора X:

          (4.18)

Таким образом, метод наименьших квадратов сводится к нахождению обратной матрицы.

Взвешенный метод наименьших квадратов

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

          (4.19)

где W — диагональная матрица весов:

          (4.20)