есть набор данных эксперимента N*{x,y}
нужно подобрать коэффициенты полинома степени M для аппроксимации эксперимента
для решения данной задачи использую метод наименьших квадратов, в качестве полинома базисные функции полиномы чебышева, при решении матрицы используется сингулярное разложение
ВОПРОС
как оценить необходимую разрядную сетку представления чисел в ЭВМ необходимую для обеспечения данного метода
в литературе как то смутно написано что типа работает и при больших степенях полинома
но хотелось бы
1 посмотреть на вывод данного утверждения
2 посмотреть формулы для разрядности представления чисел не влияющей на точность аппроксимации
или дайте ссылку с данными выводами
спасибо
Полная версия этой страницы: метод наименьших квадратов
Форум разработчиков электроники ELECTRONIX.ru > Cистемный уровень проектирования > Математика и Физика
Цитата(net @ Apr 19 2009, 17:15) 
для решения данной задачи использую метод наименьших квадратов, в качестве полинома базисные функции полиномы чебышева, при решении матрицы используется сингулярное разложение
Может быть сказать, что энергия ошибок, минимизируемая методом наименьших квадратов, определяется с весовой функцией, с которой полиномы Чебышева ортогональны, и тогда ничего обращать не нужно будет?
PS Что касается разрядности - думаю нужно действовать стандартным образом. Каждое округление вносит независимо известную энергию ошибки.
Для матричных вычислений основы теории изложены, например, у Голуба и товарищей http://www.ozon.ru/context/detail/id/96591/
Цитата(Oldring @ Apr 20 2009, 13:04)
. Каждое округление вносит независимо известную энергию ошибки.
все дело в том что при правильном составлении матрицы эта энергетика меняется - именно этот момент и интересует
Цитата(net @ Apr 20 2009, 15:39)
все дело в том что при правильном составлении матрицы эта энергетика меняется - именно этот момент и интересует
Все умножается на константную матрицу?
Цитата(Oldring @ Apr 20 2009, 16:16)
Все умножается на константную матрицу?
в каком то смысле и так - поскольку чебышев и обычные степени линейны
но еще и за счет ортогональности чебышева и нормировки для чебышева {-1;1} уменьшается ошибка
кроме того сингулярное разложение дает выигрыш для плохообусловленных матриц
поэтому это все улучшает положение - и по литературе это лучшение носит принципиальный характер
если обычны канонической формы МНК работает до 5 степени то указанным способом можно считать и 100 степень
вот и хочется узнать ошибку от разрядность представления чисел для данного метода
Цитата(net @ Apr 20 2009, 19:16)
но еще и за счет ортогональности чебышева и нормировки для чебышева {-1;1} уменьшается ошибка
Ортогональны для неравномерного веса. Для равномерного веса - почти ортогональны. Впрочем, это в данном случае не принципиально. Для полного лиапазона [-1,1] число обусловленности матрицы, составленной из достаточно подробной дискретизации первых 100 полиномов Чебышева, равно всего 8.6. Но только для полного диапазона [-1,1] Если же взять диапазон x = [-0.99,0.99] - то число обусловленности тут же подскочит до полмиллиона
Так что не все так просто с большими степенями и ортогональностью полиномов Чебышева, как кажетсяч на первый взгляд.
Цитата(Oldring @ Apr 20 2009, 20:20)
Ортогональны для неравномерного веса. Для равномерного веса - почти ортогональны. Впрочем, это в данном случае не принципиально. Для полного лиапазона [-1,1] число обусловленности матрицы, составленной из достаточно подробной дискретизации первых 100 полиномов Чебышева, равно всего 8.6. Но только для полного диапазона [-1,1] Если же взять диапазон x = [-0.99,0.99] - то число обусловленности тут же подскочит до полмиллиона Так что не все так просто с большими степенями и ортогональностью полиномов Чебышева, как кажетсяч на первый взгляд.
Так что не все так просто с большими степенями и ортогональностью полиномов Чебышева, как кажетсяч на первый взгляд.вы по делу чтото сказать можете?
интересует разрядность чисел для представления
а все остальное что вы пишите известно из литературы и выводы уже сделаны в этой литературе
все что вы говорите не несет никакой информации - по вопросу есть что сказать?
решение задачи в принципе никого не волнует - меня интересует решение задачи в приборе
Цитата(net @ Apr 21 2009, 09:17)
вы по делу чтото сказать можете?
Нет, по делу ничего сказать не могу. Разбирайтесь сами в деталях своей реализации.
В подобных ситуациях иногда можно выкрутится с помощью MATLAB. Задаетесь известным полиномом из рабочего диапазона, по нему строите массив измерений (с максимально возможной точностью), после чего обрабатываете алгоритмом идентификации с заданной размерностью переменных (по крайней мере стандартные типы С всегда можно задать, или работать с целыми числами в масштабе, масштаб и будет определять размерность). По разнице между исходным полиномом и оценкой смотрите погрешность. Если устраивает, берете 5-10 точек в рабочем диапазоне (равномерно по всему диапазону) и проверяете.
Цитата(314 @ May 3 2009, 20:10)
В подобных ситуациях иногда можно выкрутится с помощью MATLAB. Задаетесь известным полиномом из рабочего диапазона, по нему строите массив измерений (с максимально возможной точностью), после чего обрабатываете алгоритмом идентификации с заданной размерностью переменных (по крайней мере стандартные типы С всегда можно задать, или работать с целыми числами в масштабе, масштаб и будет определять размерность). По разнице между исходным полиномом и оценкой смотрите погрешность. Если устраивает, берете 5-10 точек в рабочем диапазоне (равномерно по всему диапазону) и проверяете.
не очень понял совет
особенно про 5-10 точек
мнк применяется чтобы убрать случайную составляющую и число точек примерно 5000 чтобы получить приличное усреднение
кроме того применение полиномов с нормировкой делается для того чтобы убрать порядки в х, так как при малых или больших значениях возведение в степень приводит к плохой обусловленности
да и сингулярное разложение позволяет тоже улучшить решение при плохой обусловленности
вообщем не понял ваше сообщение
Прошу прощения, если не очень понятно выразился. Предлагалось просто провести компьютерный эксперимент. При максимальной разрядной сетке по известному полиному генерируете матрицу (ваши 5000 точек). Потом обрабатываете эту матрицу своим алгоритмом, но разрядность представления чисел в нем ограничиваете (используя стандартные типы переменных С или другим способом, на Ваше усмотрение). В итоге получаете оценочный полином. Имея перед глазами оба полинома, исходный и оценочный, делаете выводы о применимости как разрядной сетки, так и алгоритма. Если все выглядит приемлемо, то зная вероятный диапазон величины, которую Вы усредняете, этот самый диапазон разбиваете на 5-10 отрезков и для каждого отрезка повторяете проверку. Так более вероятно, что при изменении усредняемой величины Вы не выйдете за пределы допустимой погрешности. При желании так же можно умножая исходную матрицу на функцию типа гауссового шума, и постепенно шаг за шагом увеличивая шумовую составляющую определить допустимый порог уровня шума.
Цитата(314 @ May 12 2009, 23:32)
Предлагалось просто провести компьютерный эксперимент. При максимальной разрядной сетке по известному полиному генерируете матрицу (ваши 5000 точек). Потом обрабатываете эту матрицу своим алгоритмом, но разрядность представления чисел в нем ограничиваете (используя стандартные типы переменных С или другим способом, на Ваше усмотрение). В итоге получаете оценочный полином. Имея перед глазами оба полинома, исходный и оценочный, делаете выводы о применимости как разрядной сетки, так и алгоритма.
это все было проделано и дало нормальный результат
после чего возник вопрос как оценить теоретически необходимую разрядность
чтобы можно было теоретически обосновывать необходимую разрядность чисел необходимых для решения задачи
Кто подскажет, как из коэффициентов разложения в ряд Чебышева, можно получить коэффициенты обычного степенного разложения типа ax5+bx4+cx3+dx2+ex+f ?
Когда-то даже видела рекомендацию, не считайте, мол, степенные коэффициенты в лоб, т.к. при решении нормальных уравнений матрица окажется плохо обусловлена. А считайте сперва полиномы Чебышева, а степенные коэффициенты получите из них.
Несколько раз бросалась искать ту рекомендацию в Google, но из-за обилия паразитных ссылок так и не нашла. А в этой теме, похоже, как раз намекается на тот метод. Подскажите, где искать про это, если кто помнит!
P.S. Среди студенческих рефератов (большего я так и не нашла) бродит такой абзац:
Однако ж ничего из этого объяснения не поняла
, а большего там и не было.
Когда-то даже видела рекомендацию, не считайте, мол, степенные коэффициенты в лоб, т.к. при решении нормальных уравнений матрица окажется плохо обусловлена. А считайте сперва полиномы Чебышева, а степенные коэффициенты получите из них.
Несколько раз бросалась искать ту рекомендацию в Google, но из-за обилия паразитных ссылок так и не нашла. А в этой теме, похоже, как раз намекается на тот метод. Подскажите, где искать про это, если кто помнит!
P.S. Среди студенческих рефератов (большего я так и не нашла) бродит такой абзац:
Цитата
Преобразование коэффициентов полинома Чебышева в коэффициенты традиционного многочлена
Вводим коэффициенты a0, a1, …, an многочлена T(x) и образуем массив ai
Для j = 2, 3, …, n и k = n, n-1, …, j в первом случае поднимаясь, а во втором спускаясь, осуществляем преобразование коэффициентов по следующим формулам:
а) ak-1 = ak-2 - ak
б) ak = 2ak
В результате получаем коэффициенты полинома Pn(x)
http://100balov.com/data/rus/Drygoe/26/POL...ChEBIrShEVA.rtf
Вводим коэффициенты a0, a1, …, an многочлена T(x) и образуем массив ai
Для j = 2, 3, …, n и k = n, n-1, …, j в первом случае поднимаясь, а во втором спускаясь, осуществляем преобразование коэффициентов по следующим формулам:
а) ak-1 = ak-2 - ak
б) ak = 2ak
В результате получаем коэффициенты полинома Pn(x)
http://100balov.com/data/rus/Drygoe/26/POL...ChEBIrShEVA.rtf
Однако ж ничего из этого объяснения не поняла
, а большего там и не было.
Цитата(Xenia @ Nov 29 2011, 20:47)
Когда-то даже видела рекомендацию, не считайте, мол, степенные коэффициенты в лоб, т.к. при решении нормальных уравнений матрица окажется плохо обусловлена. А считайте сперва полиномы Чебышева, а степенные коэффициенты получите из них.
У Вас координаты сетки интерполяции на чебышевских точках, или на равномерных заданы? Если на равномерных, то при конвертации из Чебышевской в степенное представление, Вы и получите опять эту же ошибку. Если у Вас сетка на Чебышевских точках, то матрица интерполяционных коэффициентов будет хорошо обусловлена.
Цитата(iiv @ Nov 29 2011, 21:33)
У Вас координаты сетки интерполяции на чебышевских точках, или на равномерных заданы?
У меня равномерная сетка. Физически это замеры АЦП в периодическом режиме.
Цитата(iiv @ Nov 29 2011, 21:33)
Если на равномерных, то при конвертации из Чебышевской в степенное представление, Вы и получите опять эту же ошибку.
А я согласна получить ошибку, вы только скажите, как конвертировать!
Цитата(Xenia @ Nov 30 2011, 01:52)
А я согласна получить ошибку, вы только скажите, как конвертировать!
А в лоб по определению разве сложно?
Код
T_0 = 1;
T_1(x) = x;
T_{k+1}(x) = 2 x T_k(x) – T_{k–1}(x).
T_1(x) = x;
T_{k+1}(x) = 2 x T_k(x) – T_{k–1}(x).
Пишем простенькую программку, которая вычисляет коэффициенты полинома исходя из этой рекурсии. Коэффициенты все целочисленные, при их вычислении ошибок не будет, только рости они будут очень не по-децки, полином 40-ей степени уже не влезет в 64-битную арифметику:
Код
#include <stdio.h>
int main()
{ unsigned int i, j, k, N=64;
long long A[N][N];
A[0][0]=1;
A[1][0]=0;
A[1][1]=1;
for(i=2; i<40; i++)
{ for(j=0; j<i-1; j++)
A[i][j]=-A[i-2][j];
A[i][i]=2*A[i-1][i-1];
for(j=1; j<i; j++)
A[i][j]+=2*A[i-1][j-1];
for(j=0; j<i+1; j++)
printf("%lld ", A[i][j]);
printf("\n");
}
return 0;
}
int main()
{ unsigned int i, j, k, N=64;
long long A[N][N];
A[0][0]=1;
A[1][0]=0;
A[1][1]=1;
for(i=2; i<40; i++)
{ for(j=0; j<i-1; j++)
A[i][j]=-A[i-2][j];
A[i][i]=2*A[i-1][i-1];
for(j=1; j<i; j++)
A[i][j]+=2*A[i-1][j-1];
for(j=0; j<i+1; j++)
printf("%lld ", A[i][j]);
printf("\n");
}
return 0;
}
Цитата(iiv @ Nov 30 2011, 00:42)
Коэффициенты все целочисленные, при их вычислении ошибок не будет, только рости они будут очень не по-децки, полином 40-ей степени уже не влезет в 64-битную арифметику:
Для полиномов первого рода все операции fixed point, рост разрядности отменяется.
Али я неправ?
Цитата(_Pasha @ Nov 30 2011, 03:33)
Для полиномов первого рода все операции fixed point, рост разрядности отменяется.
Али я неправ?
Али я неправ?
А Вы программку-то скомпилите, запустите и на результат-то посмотрите
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.