Допустим, что требуется заменить некоторую величину и делается n измерений, результаты которых равны x i = x + e i (i =1, 2, …, n), где e i - это ошибки (или шум) измерений, а х - истинное значение. Метод наименьших квадратов утверждает, что наилучшее приближённое значение есть такое число, для которого минимальна сумма квадратов отклонений от:
Один из наиболее частых случаев применения этого метода заключается в том, что имеющиеся n наблюдений (x i, y i) (i =1, 2, …, n) требуется приблизить многочленом степени m < n
y (x) =a 0 +a 1 x+a 2 x 2 +…+ a m x m
Вычисленная кривая у (х) в некотором смысле создаёт сложное множество значений у i. Метод наименьших квадратов утверждает, что следует выбирать многочлен, который приводит функцию к минимуму
Для нахождения минимума дифференцируем � по каждой из неизвестных a k. В результате получим:
Определитель этой системы отличен от нуля и задача имеет единственное решение. Но система степеней не ортогональна, и при больших значениях n задача плохо обусловлена.
Эту трудность можно обойти, используя многочлены ортогональные с заданным весом на заданной системе точек, но к этому прибегают только в задачах, связанных с особенно тщательной статической обработкой эксперимента
Полиномы Чебышева
Критерии согласия данного метода - минимизация максимальной ошибки Полиномы Чебышева определяются следующим образом: T n (x) = cos (n Ч arccos (x))
Например: T 0 (x) = cos (0) =1,T 1 (x) = cos (q) = x,
T 2 (x) = cos (2 q) =cos 2 (q) - sin 2 (q) =2x 2 - 1
Можно было бы и дальше использовать тригонометрические соотношения для нахождения полиномов Чебышева любого порядка, но будет лучше установить для них рекурентное соотношение, связывающее T n +1 (x), T n (x) и T n - 1 (x):
T n+1 (x) = cos (n q + q) = cos (n q) cos (q) - sin (n q) sin (q),
T n-1 (x) = cos (n q - q) = cos (n q) cos (q) - sin (n q) sin (q)
Складывая эти неравенства, получим:
T n +1 (x) + T n - 1 (x) =2 cos (n q) cos (q) =2 xT n (x);
T n+1 (x) =2xT n (x) - T n-1 (x)
Применяя полученные формулы можно найти любой полином Чебышева. Например, Т 3 (x) =2 xT 2 (x) - T 1 (x). Подставляя значения T 2 (х) и Т 1 (х) имеем Т 3 (х) =2х (2х 2 - 1) - х=4х 3 - 3х. Графически первые 10 полиномов Чебышева изображены ниже. Последующие полиномы по-прежнему колеблются между +1 и - 1, причём период колебания уменьшаются с ростом порядка полинома
Преобразования q = arccos (x) можно рассмотреть как проекцию пересечений полукруга с множеством прямых, имеющих углы равные между собой (рис.1). Таким образом, множество точек x j, на котором система чебышевских многочленов T n (x) ортогональна, есть:
(j =0, 1, 2, …, N - 1)
Так как T n (x) есть, по существу, cos (n q), то они являются равноколеблющимися функциями, и так как они многочлены, то обладают всеми свойствами, которые имеют ортогональные многочлены
Чебышев доказал, что из всех многочленов Р n (x) степени n старшим коэффициентом 1, у многочлена точная верхняя грань абсолютных значений на интервале - 1 Ј x Ј 1 наименьшая. Так как верхняя грань T n (x) =1, указанная верхняя грань равна
Практическое задание
На практике нам необходимо было изучить приближение нашей функции полиномами Тейлора.
Как уже упоминалось выше, многочлены Тейлора легко вычисляются, а так же превращаются в степенные ряды. В этом нам удалось убедится на практике.
Ниже приведена таблица коэффициентов первых двенадцати полиномов Чебышева, а также таблица коэффициентов перед полиномами Чебышева, выражающие первые двенадцать степеней.
Эти данные мы получили, используя программы на страницах.
В этих программах были использованы следующие алгоритмы: Преобразование коэффициентов полинома Чебышева в коэффициенты традиционного многочлена.
Вводим коэффициенты a 0, a 1, …, a n многочлена T (x) и образуем массив a i. Для j =2, 3, …, n и k = n, n - 1, …, j в первом случае поднимаясь, а во втором спускаясь, осуществляем преобразование коэффициентов по следующим формулам:
а) a k-1 =a k-2 - a k
б) a k =2a k
В результате получаем коэффициенты полинома P n (x)
Преобразование коэффициентов полинома P n (x) в коэффициенты полинома T n (x)
Вводим коэффициенты полинома P n (x) - а i.
Для j = n, n - 1, …, 2 и k = j, j +1, …, n в первом случае спускаясь, а во втором поднимаясь, проводим преобразование коэффициентов по следующим формулам:
а) a k =a k /2
б) a k-2 =a k-2 +a k
с) a 0 =2 a 0
В результате получаем коэффициенты полинома Т n (x). Интересно было бы узнать, какую ошибку мы получаем при разложении степенной функции по полиномам Чебышева. Для этого, используя выше описанные алгоритмы, мы сначала представляем функцию y = x n (где n берем от 1 до 10) через полиномы Чебышева (T n), а затем, чтобы оценить ошибку, чебышевское разложение снова превращаем в многочлен. Выполнив эти операции, мы получаем очень необычные результаты. Для нечётных n ошибка настолько мала, что её едва можно различить на графиках. Для чётных же степеней мы можем наблюдать смещение графика, полученного в результате преобразования, вниз относительно оригинала. Это можно объяснить следующим образом. За смещение графика несёт ответственность коэффициент перед x 0. Вспомним алгоритмы, они построены так, что каждый предыдущий коэффициент вычисляется через последующий. В результате накапливающаяся ошибка вычисления больше всего влияет на коэффициент при x 0. Следствием этого является смещение графиков чётных степеней, так как в их разложении присутствует этот коэффициент. Можно отметить также, что смещение при разложении функции y = x 2 больше, чем при разложении функции y = x 10. Этот тоже можно легко объяснить, так как при увеличении степени вклад T 0 в разложении степенной функции значительно уменьшается. Что же будет, если коснуться нечётных степеней. Тогда мы получим такое хорошее совпадение, так как чётные коэффициенты в разложении нечётных степеней равны 0, а коэффициенты при всех степенях x, кроме нулевой, влияют только на отклонение ветвей. Подтверждением этого служат графики
Следующим этапом работы являлось приближение полиномами Чебышева произвольной функции. В качестве начальной функции мы взяли функцию y = sin (4 x /3). Используемая в работе программа имела нижеприведенный алгоритм:
Приближение функции f (x) по Чебышеву
Задаём степень n многочлена T n (x) и пределы [a; b] изменения аргумента функции f (x)
Для i =0, 1, …, n на отрезке [-1; 1] формируем сетку оптимальных значений аргумента в узлах чебышевской интерполяции:
Переводим в отрезок [a; b]: и вычисляем f (x i)
Для k =0, 1, …, n и i =0, 1, …, n вычисляем:
В результате получаем коэффициенты a 0, a 1, …, a n многочлена T (), приближающего функцию f (x)
Вычисление значений T (x) выполняется по следующему алгоритму:
Считая заданным массив a k, необходимо задать память под массив из n +2 вспомогательных коэффициентов b k. Полагаем b n +2 =0, b n +1 =0
Задаём значения x на [a; b] и переводим их в отрезок [-1; 1] с помощью преобразований:
Для k = n, n - 1, …, 1 вычисляем b k = a k - b k +2 +2 xb k +1
Находим T () =a 0 /2 - b 2 +xb 1
Также в программе было использовано разложение в ряд Тейлора для сравнения с разложением по полиномам Чебышева. Прежде всего, было рассмотрено приближение на интервале [-1; 1]. Наложив на график sin (4 x /3) график его приближения полиномами Чебышева и график, построенный с помощью разложения в ряд Тейлора, получаем очень точное совпадение. Визуально невозможно различить три кривых. Рассматриваем график ошибок. В соответствии с теорией ошибка Чебышева знакопеременна и распределена более или менее равномерно по всему интервалу. Ошибка же Тейлора небольшая около 0 и сильно увеличивается при приближении к 1 (заметим, что в этом и в других случаях ряд Тейлора содержит те же степени x, но с иными коэффициентами). Наиболее интересно рассмотреть приближение на более длинных интервалах. На интервале [-1; 1] приближение полиномами Чебышева седьмой степени достаточно хорошее, но уже на интервале [-10; 10] приближение этой же степенью очень плохое. Рассмотрим приближение на этом же интервале полиномом более высокой степени (T 11). Получим достаточно неплохое приближение, причём на графике очень отчётливо видно, что ошибка распределена равномерно. Здесь опять хочется сравнить с разложением в ряд Тейлора. Если посмотреть на графики, мы увидим, что приближение с помощью рядов Тейлора очень хорошее в середине интервала, но имеет сильное отклонение от эталона на концах. Сравним ошибки чебышевского приближения и приближения с помощью рядов Тейлора. При таком сравнении ясно проявляются свойства полиномов Чебышева - максимальная ошибка меньше, чем при использовании ряда Тейлора
В итоге, мы получили, что на большом интервале хорошее приближение можно построить только, используя достаточно большие степени. В действительности, трудно представить себе приближение нескольких периодов синуса с помощью полиномов 3-й, 4-й, 5-й степеней, и тем более - невозможно 1-й и 2-й степени
Полиномы Чебышева дают великолепное приближение функции в том смысле, что максимальная ошибка этого приближения очень мала, но эти приближения достаточно сложно вычисляются. Обычно относительно малое уменьшение ошибки не стоит того труда, который необходимо потратить на нахождение этого приближения. Именно поэтому полиномы Чебышева используют для корректировки разложения в ряд Тейлора. Нахождение исправленных коэффициентов не составляет особой сложности, поэтому этот метод, называемый экономизацией степенного ряда легко может применяться для повседневного программирования.