Составители:
Первый способ поиска оптимальных cj состоит в решении системы уравнений (т.н. метод
нормальных уравнений). С учетом особенностей задачи, равенство производных нолю является не только
необходимым, но и достаточным условием минимума. Кроме того, эта система уравнений является линейной
относительно c
j
и записывается как !!!!(A TA)c - A Tb = 0. Основным недостатком этого метода является то,
что полученная система уравнений часто бывает плохо обусловленной. Число обусловленности матрицы A
само по себе может быть велико (например, в случае использования базиса из полиномов), а возведение
матрицы A в квадрат увеличивает его ещё больше (также возводит в квадрат). По этой причине метод
нормальных уравнений на практике обычно не применяется.
Второй способ основан на том, что задачу минимизации функции E можно записать в матричной форме, как
поиск
. Таким образом, задача сведена к поиску псевдорешения системы линейных уравнений,
которое может быть найдено с использованием сингулярного разложения (SVD). Этот способ является
наиболее естественным, хотя и требует более сложного программного кода для своей реализации.
Достоинством этого метода является то, что в этом случае не происходит возведения в квадрат числа
обусловленности базиса. Мы решаем систему, обусловленность которой равна обусловленности базиса, что
позволяет получать достаточно точные решения даже в тех случаях, когда использование метода нормальных
уравнений приводит к возникновению системы с вырожденной матрицей коэффициентов. Следует отметить,
что хотя для осуществления сингулярного разложения мог бы использоваться предназначенный для этого
общий алгоритм, в этом нет необходимости. С учетом специфики задачи предпочтительнее использовать
более компактную и быструю версию алгоритма, учитывающую тот факт, что требуется не само сингулярное
разложение матрицы A, а произведение отдельных компонент этого разложения на вектор b.
Также существует третий способ, применяющий QR-разложение, и работающий несколько быстрее метода на
основе SVD-разложения. Сначала матрица A представляется в виде произведения прямоугольной
ортогональной матрицы Q и квадратной верхнетреугольной матрицы R. Затем решается система уравнений
Rx = Q Tb. Достоинством этого метода является относительно высокая скорость работы, недостатком -
применимость только к невырожденным задачам (т.е. задачам, имеющим одно и только одно решение). Для
того, чтобы задача аппроксимации была невырожденной, требуется выполнение двух условий. Во-первых,
система базисных функций должна быть линейно-независимой. Во-вторых, число точек должно быть не
меньше числа базисных функций. Как правило, в практических задачах эти условия выполняются. Но все же
очень редко встречаются задачи, в которых алгоритм на основе QR-разложения оказывается неприменим из-
за нарушения одного из условий. Кроме того, обычно число строк в матрице A намного больше числа
столбцов, а правильно реализованное SVD разложение таких матриц по трудоемкости сравнимо с QR
разложением. Таким образом, более целесообразным представляется использование второго способа, т.е.
SVD-разложения.
4.2 Линейная аппроксимация по МНК
При линейной аппроксимации по МНК в качестве набора базисных функций используются f0 = 1 и f1 = x.
Линейная комбинация функций из этого базиса позволяет получить произвольную прямую на плоскости.
Особенностью этого базиса является то, что в данном случае оказывается применим метод нормальных
уравнений. Базис небольшой, хорошо обусловленный, и поэтому задача аппроксимации легко сводится к
решению системы линейных уравнений 2x2. Для решения используется модификация метода вращений,
которая позволяет корректно обрабатывать вырожденные случаи (например, точки с совпадающими
абсциссами).
Этот алгоритм реализован в подпрограмме BuildLinearLeastSquares.
Полиномиальная аппроксимация по МНК
Частой ошибкой является использование для полиномиальной аппроксимации следующего набора базисных
функций: fi = x
i
. Этот базис является наиболее естественным и, пожалуй, первым приходящим в голову
вариантом. Но хотя с этим базисом удобно работать, он очень плохо обусловлен. Причем проблемы
появляются даже при умеренном числе базисных функций (порядка десяти). Эта проблема была решена путем
выбора базиса из полиномов Чебышева вместо базиса из степеней x. Полиномы Чебышева линейно
выражаются через степени x и наоборот, так что эти базисы эквивалентны. Однако обусловленность базиса из
полиномов Чебышева значительно лучше, чем у базиса из степеней x. Это позволяет без проблем
осуществлять аппроксимацию полиномами практически любой степени.
Алгоритм работает следующим образом. Входной набор точек масштабируется и приводится к интервалу
[−1,1], после чего на этом отрезке строится базис из полиномов Чебышева. После аппроксимации по МНК
пользователь получает набор коэффициентов при полиномах Чебышева. Эта задача решается подпрограммой
BuildChebyshevLeastSquares. Полученные коэффициенты могут быть переданы в подпрограмму
CalculateChebyshevLeastSquares, которая вычисляет значение аппроксимирующей функции в требующей
точке.
Если специфика решаемой задачи требует использования именно базиса из степеней x, то можно
воспользоваться подпрограммой BuildPolynomialLeastSquares. Эта подпрограмма решает задачу с
84
Страницы
- « первая
- ‹ предыдущая
- …
- 83
- 84
- 85
- 86
- 87
- …
- следующая ›
- последняя »
