метод наименьших квадратов код программы
Метод наименьших квадратов
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Метод наименьших квадратов
Дано функцию f(x). Найти линейную функцию ax+b которая наилучшим способом апроксимирует её.
Метод наименьших квадратов
Ребят,вот в чем беда. нужно для курсового решить задачу. нужно апроксимировать данные линейной.
10 меняем кодировку символов для нормального вывода сообщений на русском языке
11 создаём указатели на массивы (2 на одномерные и 1 на двумерный)
20 ожидаем нажатия любой клавиши
21-22 создаём 2 динамических одномерных массива
23-25 создаём динамический двумерный массив
77 выводим значение элемента массива и ограничиваем поле вывода данных(т.е. не более 15 символов)
остальные строки это сам метод наименьших квадратов, его думаю знаете
Помощь в написании контрольных, курсовых и дипломных работ здесь.
МНК (Метод наименьших квадратов)
Помогите с реализацией аппроксимации МНК. Есть экспериментальные данные, хочу аппроксимировать их.
Метод наименьших квадратов! (с Pascal на C++)
Писал прогу на Паскале, так как не владею должными знаниями по С++ приходится просить помочь вас.
Метод наименьших квадратов(численные методы)
Совсем не знаю как сделать задачу, если кто то сможет сделать буду очень благодарен и отблагодарю.
Метод наименьших квадратов для экспонентой функции
y = a(1-exp(-x/a) то есть это аппроксимирующая функция необходимо подобрать такое а, чтобы.
Линейный Метод Наименьших Квадратов, ошибка в расчетах
Разработка программы аппроксимации табличной функции степенным рядом( линейный метод наименьших.
Реализовать метод наименьших квадратов
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Метод наименьших квадратов
Есть ли у кого пример реализации МНК (например, даны значения уровня безработицы за период.
Метод наименьших квадратов
Всем привет 🙂 Есть ли у кого реализованный метод МНК в случае линейной модели или может кто.
Метод наименьших квадратов
Здравствуйте! Помогите пожалуйста составить программу в C#, а то я полный ноль в этом( Линейная.
Метод МНК(наименьших квадратов)
Здравствуйте, помогите с заданием: С помощью МНК, найти уравнение который наиболее подходит.
Собственно, вот, что сделал.
Для реализации метода наименьших квадратов нам понадобится:
а) Разобраться в теории и выбрать какие-то примеры для тестирования. В инете много инфы на эту тему. За основу я взял главу этой книги и примеры из конца этой главы
б) Создать класс Matrix в которой должен уметь:
— Транспонировать матрицу
— Умножать матрицу на чисто и/или на другую матрицу
— Находить минор матрицы по заданным индексам. (подсмотрел на этом форуме)
— Находить определитель (детерминант) матрицы. Это рекурсивная статическая функция. Так как минор находится путем вычеркивания строки и столбца, это не самый оптимальный способ. В случаях когда под главной диагональю стоят нули (треугольная матрица), то определитель такой матрицы равен произведению членов главной диагонали. Поэтому если на больших объемах данных будет тормозить, то следует реализовать это.
— Находить матрицу миноров (алгебраических дополнений)
— Находить обратную матрицу
Класс приведен ниже:
в) Теперь можно приступить к созданию нашего класса реализующего МНК. В нем реализован МНК полиномиальной функцией, а также есть возможность оценить среднеквадратичное отклонение. Класс LSM (Least Square Method) приведен ниже:
Методы наименьших квадратов без слёз и боли
Итак, очередная статья из цикла «математика на пальцах». Сегодня мы продолжим разговор о методах наименьших квадратов, но на сей раз с точки зрения программиста. Это очередная статья в серии, но она стоит особняком, так как вообще не требует никаких знаний математики. Статья задумывалась как введение в теорию, поэтому из базовых навыков она требует умения включить компьютер и написать пять строк кода. Разумеется, на этой статье я не остановлюсь, и в ближайшее же время опубликую продолжение. Если сумею найти достаточно времени, то напишу книгу из этого материала. Целевая публика — программисты, так что хабр подходящее место для обкатки. Я в целом не люблю писать формулы, и я очень люблю учиться на примерах, мне кажется, что это очень важно — не просто смотреть на закорючки на школьной доске, но всё пробовать на зуб.
Итак, начнём. Давайте представим, что у меня есть триангулированная поверхность со сканом моего лица (на картинке слева). Что мне нужно сделать, чтобы усилить характерные черты, превратив эту поверхность в гротескную маску?
Пример 1: сглаживание данных
Давайте расскажу, как это работает. Начнём издалека, представьте, что у нас есть обычный массив f, например, из 32 элементов, инициализированный следующим образом:
А затем мы тысячу раз выполним следующую процедуру: для каждой ячейки f[i] мы запишем в неё среднее значение соседних ячеек: f[i] = ( f[i-1] + f[i+1] )/2. Чтобы было понятнее, вот полный код:
Каждая итерация будет сглаживать данные нашего массива, и через тысячу итераций мы получим постоянное значение во всех ячейках. Вот анимация первых ста пятидесяти итераций:
Если вам неясно, почему происходит сглаживание, прямо сейчас остановитесь, возьмите ручку и попробуйте порисовать примеры, иначе дальше читать не имеет смысла. Триангулированная поверхность ничем принципиально от этого примера не отличается. Представьте, что для каждой вершины мы найдём соседние с ней, посчитаем их центр масс, и передвинем нашу вершину в этот центр масс, и так десять раз. Результат будет вот таким:
Разумеется, если не остановиться на десяти итерациях, то через некоторое время вся поверхность сожмётся в одну точку ровно так же, как и в предыдущем примере весь массив стал заполнен одним и тем же значением.
Пример 2: усиление/ослабление характеристических черт
Полный код доступен на гитхабе, а здесь я приведу самую важную часть, опустив лишь чтение и запись 3Д моделей. Итак, триангулированная модель у меня представлена двумя массивами: verts и faces. Массив verts — это просто набор трёхмерных точек, они же вершины полигональной сетки. Массив faces — это набор треугольников (количество треугольников равно faces.size()), для каждого треугольника в массиве хранятся индексы из массива вершин. Формат данных и работу с ним я подробно описывал в своём курсе лекций по компьютерной графике. Есть ещё третий массив, который я пересчитываю из первых двух (точнее, только из массива faces) — vvadj. Это массив, который для каждой вершины (первый индекс двумерного массива) хранит индексы соседних с ней вершин (второй индекс).
Первое, что я делаю, это для каждой вершины моей поверхности считаю вектор кривизны. Давайте проиллюстрируем: для текущей вершины v я перебираю всех её соседей n1-n4; затем я считаю их центр масс b = (n1+n2+n3+n4)/4. Ну и финальный вектор кривизны может быть посчитан как c=v-b, это не что иное, как обычные конечные разности для второй производной.
Непосредственно в коде это выглядит следующим образом:
Ну а дальше мы много раз делаем следующую вещь (смотрите предыдущую картинку): мы вершину v двигаем v := b + const * c. Обратите внимание, что если константа равна единице, то наша вершина никуда не сдвинется! Если константа равна нулю, то вершина заменяется на центр масс соседних вершин, что будет сглаживать нашу поверхность. Если константа больше единицы (заглавная картинка сделана при помощи const=2.1), то вершина будет сдвигаться в направлении вектора кривизны поверхности, усиливая детали. Вот так это выглядит в коде:
Кстати, если меньше единицы, то детали будут наоборот ослабляться (const=0.5), но это не будет эквивалентно простому сглаживанию, «контраст картинки» останется:
Пример 3: добавляем ограничения
Давайте вернёмся к самому первому примеру, и сделаем ровно то же самое, но только не будем переписывать элементы массива под номерами 0, 18 и 31:
Остальные, «свободные» элементы массива я инициализировал нулями, и по-прежнему итеративно заменяю их на среднее значение соседних элементов. Вот так выглядит эволюция массива на первых ста пятидесяти итерациях:
Вполне очевидно, что на сей раз решение сойдётся не к постоянному элементу, заполняющему массив, а к двум линейным рампам. Кстати, действительно ли всем очевидно? Если нет, то экспериментируйте с этим кодом, я специально привожу примеры с очень коротким кодом, чтобы можно было досконально разобраться с происходящим.
Лирическое отступление: численное решение систем линейных уравнений.
Пусть нам дана обычная система линейных уравнений:
Её можно переписать, оставив в каждом из уравнений с одной стороны знака равенства x_i:
Пусть нам дан произвольный вектор , приближающий решение системы уравнений (например, нулевой).
Тогда, воткнув его в правую часть нашей системы, мы можем получить обновлённый вектор приближения решения .
Чтобы было понятнее, x1 получается из x0 следующим образом:
Повторив процесс k раз, решение будет приближено вектором
Давайте на всякий случай запишем рекурретную формулу:
При некоторых предположениях о коэффициентах системы (например, вполне очевидно, что диагональные элементы не должны быть нулевыми, т.к. мы на них делим), данная процедура сходится к истинному решению. Эта гимнастика известна в литературе под названием метода Якоби. Конечно же, существуют и другие методы численного решения систем линейных уравнений, причём значительно более мощные, например, метод сопряжённых градиентов, но, пожалуй, метод Якоби является одним из самых простых.
Пример 3 ещё раз, но уже с другой стороны
А теперь давайте ещё раз внимательно посмотрим на основной цикл из примера 3:
Я стартовал с какого-то начального вектора x, и тысячу раз его обновляю, причём процедура обновления подозрительно похожа на метод Якоби! Давайте выпишем эту систему уравнений в явном виде:
Потратьте немного времени, убедитесь, что каждая итерация в моём питоновском коде — это строго одно обновление метода Якоби для этой системы уравнений. Значения x[0], x[18] и x[31] у меня зафиксированы, соответственно, в набор переменных они не входят, поэтому они перенесены в правую часть.
Итого, все уравнения в нашей системе выглядят как — x[i-1] + 2 x[i] — x[i+1] = 0. Это выражение не что иное, как обычные конечные разности для второй производной. То есть, наша система уравнений нам просто-напросто предписывает, что вторая производная должна быть везде равна нулю (ну, кроме как в точке x[18]). Помните, я говорил, что вполне очевидно, что итерации должны сойтись к линейным рампам? Так именно поэтому, у линейной функции вторая производная нулевая.
А вы знаете, что мы с вами только что решили задачу Дирихле для уравнения Лапласа?
Кстати, внимательный читатель должен был бы заметить, что, строго говоря, у меня в коде системы линейных уравнений решаются не методом Якоби, но методом Гаусса-Зейделя, который является своебразной оптимизацией метода Якоби:
Пример 4: уравнение Пуассона
А давайте мы самую малость изменим третий пример: каждая ячейка помещается не просто в центр масс соседних ячеек, но в центр масс плюс некая (произвольная) константа:
В прошлом примере мы выяснили, что помещение в центр масс — это дискретизация оператора Лапласа (в нашем случае второй производной). То есть, теперь мы решаем систему уравнений, которая говорит, что наш сигнал должен иметь некую постоянную вторую производную. Вторая производная — это кривизна поверхности; таким образом, решением нашей системы должна стать кусочно-квадратичная функция. Проверим на дискретизации в 32 сэмпла:
При длине массива в 32 элемента наша система сходится к решению за пару сотен итераций. А что будет, если мы попробуем массив в 128 элементов? Тут всё гораздо печальнее, количество итераций нужно уже исчислять тысячами:
Метод Гаусса-Зейделя крайне прост в программировании, но малоприменим для больших систем уравнений. Можно попытаться его ускорить, применяя, например, многосеточные методы. На словах это может звучать громоздко, но идея крайне примитивная: если мы хотим решение с разрешением в тысячу элементов, то можно для начала решить с десятью элементами, получив грубую аппроксимацию, затем удвоить разрешение, решить ещё раз, и так далее, пока не достигнем нужного результата. На практике это выглядит следующим образом:
А можно не выпендриваться, и использовать настоящие солверы систем уравнений. Вот я решаю этот же пример, построив матрицу A и столбец b, затем решив матричное уравнение Ax=b:
А вот так выглядит результат работы этой программы, заметим, что решение получилось мгновенно:
Таким образом, действительно, наша функция кусочно-квадратичная (вторая производная равна константе). В первом примере мы задали нулевую вторую производную, в третьем ненулевую, но везде одинаковую. А что было во втором примере? Мы решили дискретное уравнение Пуассона, задав кривизну поверхности. Напоминаю, что произошло: мы посчитали кривизну входящей поверхности. Если мы решим задачу Пуассона, задав кривизну поверхности на выходе равной кривизне поверхности на входе (const=1), то ничего не изменится. Усиление характеристических черт лица происходит, когда мы просто увеличиваем кривизну (const=2.1). А если const Скрытый текст
Это результат по умолчанию, рыжий Ленин — это начальные данные, голубая кривая — это их эволюция, в бесконечности результат сойдётся в точку:
А вот результат с коэффицентом 2.:
Домашнее задание: почему во втором случае Ленин сначала превращается в Дзержинского, а затем снова сходится к Ленину же, но большего размера?
Заключение
Очень много задач обработки данных, в частности, геометрии, могут формулироваться как решение системы линейных уравнений. В данной статье я не рассказал, как строить эти системы, моей целью было лишь показать, что это возможно. Темой следующей статьи будет уже не «почему», но «как», и какие солверы потом использовать.
Кстати, а ведь в названии статьи присутствуют наименьшие квадраты. Увидели ли вы их в тексте? Если нет, то это абсолютно не страшно, это именно ответ на вопрос «как?». Oставайтесь на линии, в следующей статье я покажу, где именно они прячутся, и как их модифицировать, чтобы получить доступ к крайне мощному инструменту обработки данных. Например, в десяток строк кода можно получить вот такое:
МНК алгоритм
Метод наименьших квадратов
Задача написать алгоритм для нахождения коэффициентов полинома N степени с помощью МНК по M точек. То есть даны 10 точек, и сказано аппроксимировать для полинома 3-й степени:
Для этого полинома надо найти a, a1, a2, a3; если для 1 и 2 степени можно написать вручную, то даже для 3-й степени придётся решать систему 4-х уравнений с 4 неизвестными.
Вот тут можно посмотреть, как выглядит аппроксимация для разных функций с помощью мнк.
Как запрограммировать алгоритм, который будет составлять СЛОУ и решать её?
Обновление
Как в составлении так и в решении. Начал решать пока что такая система получается для полинома N степени. Ex сумма от 1 до M (кол-во точек).
Решение
Прошу меня простить за кривые отступы. Функция которая находит коэф. полинома N степени
Функция которая решает СЛАУ
1 ответ 1
Задача о полиномиальной регрессии (аппроксимации табличной функции) требует большой аккуратности, поскольку при обычных методах решения расчёт главного определителя СЛАУ (определителя Вандермонда) приводит к вычитанию близких чисел и в итоге снижает относительную погрешность вычислений, что проявляется уже для полиномов 8-10 порядка.
От этих недостатков свободны методы разложения в ряды по ортогональным функциям (например, разложение в ряды Фурье по косинусам), и хотелось бы так же просто обращаться с полиномами. Однако классические ортогональные полиномы (Лежандра, Чебышёва и пр.) в дискретном варианте ортогональны только на специально подобранных неравномерных сетках.
Удачный выход из такой ситуации даёт малоизвестный метод ортогональной полиномиальной регрессии (Orthogonal Polynomial Curve Fitting, Jeff Reid), в котором сначала по абсциссам заданных точек конструируются ортогональные полиномы, а затем с помощью МНК рассчитываются коэффициенты при этих полиномах.
1. ТЕОРИЯ
1.1. Постановка задачи
и условия ортогональности
1.2. Построение ортогональных полиномов.
1.3. Построение полинома регрессии
Формулы (6-7) позволяют построить алгоритм расчёта коэффициентов aj полинома g(x), если ортогональные полиномы известны.
2. АЛГОРИТМ
2.1. Значения ортогональных полиномов в узлах сетки
Значения полиномов Pji = pi(xi) в узлах сетки можно вычислить по формулам (1,4-5) :
Для полинома третьего порядка ( m=3 ) алгоритм имеет вид:
2.2. Коэффициенты ортогональных полиномов
Для полинома третьего порядка ( m=3 ):
2.3. Коэффициенты полинома регрессии.
Для полинома третьего порядка:
Для полинома третьего порядка ( m=3 ):
2.4. Об алгоритме
Разработанный алгоритм в общем виде применим для аппроксимации заданного массива точек полиномом любого порядка при условии достаточности исходных данных и вычислительных средств.
На примере полинома третьего порядка показано, что никакие СЛАУ при этом решать не требуется.
3. ТЕСТИРОВАНИЕ АЛГОРИТМА
Тестирование алгоритма проведено с использованием пакета MathCAD.
Для тестирования были выбраны 10-точечные массивы x и y и полиномиальная модель третьего порядка (см. скриншот).
Тестирование подтвердило правильность алгоритма.
Сравнение результатов расчёта с функцией regress() пакета MathCAD показало, что при одинаковой разрядности расчётов (определяемой исходными данными) алгоритм ортогональной полиномиальной регрессии точнее.
4. ПРОГРАММА НА PHP
5. РЕЗУЛЬТАТЫ.
Результаты на тестовой выборке:
Результаты работы программы на тестовой выборке соответствуют ожидаемым. На выборке в n=1000 точек при порядке модели 80 получено:
Таким образом, расчёт регрессии через ортогональные полиномы более устойчив по отношению к ошибкам округления.
6. ВЫВОДЫ.
Метод наименьших квадратов
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Метод наименьших квадратов
Ребят,вот в чем беда. нужно для курсового решить задачу. нужно апроксимировать данные линейной.
Метод наименьших квадратов
Можете около сложных строчек написать что там происходит(комментарии) #include «stdafx.h».
Жаль только в первом посте про диапазон ничего не говорится. Но, поскольку без него все равно аппроксимация невозможна, как-то он там задается
Добавлено через 43 минуты
Вложения
 | res.rar (517.7 Кб, 36 просмотров) |
А как тогда ТС разберется с алгоритмом если ему готовое решение дать?
Добавлено через 47 секунд
Хотя «для школьников» я погорячился, они частные производные вроде бы не проходят
Помощь в написании контрольных, курсовых и дипломных работ здесь.
МНК (Метод наименьших квадратов)
Помогите с реализацией аппроксимации МНК. Есть экспериментальные данные, хочу аппроксимировать их.
Метод наименьших квадратов! (с Pascal на C++)
Писал прогу на Паскале, так как не владею должными знаниями по С++ приходится просить помочь вас.
Метод наименьших квадратов(численные методы)
Совсем не знаю как сделать задачу, если кто то сможет сделать буду очень благодарен и отблагодарю.